Введение в прикладную комбинаторику, Кофман А. (984071), страница 41
Текст из файла (страница 41)
Это достигается, как видно выбором произведений А, С, Р. 334 наименьшим числом из таблицы (55.51), Решение задачи о музыкантах') методом ветвления и ограничения. Мы рассмотрим тот же пример, хотя обычно метод ветвления и ограничения применяют тогда, когда простой перебор невозможен. Воспроизводим на рис. 367 таблицу (55.50), добавив к ней снизу строку, а справа столбец. Элемент этой строки равен й-му а Ь с Ы е ! Х Ь Суммы Вычисление ни ж ней г ранним ллл Б Минимальное еначенне Рис. 387. (третьему) элементу соответствующего столбца в порядке возрастания, а элемент столбца — общее число исполнителей для каждого из произведений.
Курснвнымн цифрами отмечены положительные разности между элементами соответствующего а Ь с Ы е ) а Ь суммы Вычисление нижней гранины йлл Н, гг Минимальные еначеннн Рис. Зба. столбца (исключая последний) и элементом нижней строки (в последнем столбце — сумма чисел, набранных курсивом) Пусть Š— множество решений.
Рассмотрим свойство У;; подмножество Еу содержит произведение й Найдем границу снизу для Е. Располагач числа, набранные курсивом в последнем столбце, в порядке возрастания: 2, 5, 11, 13, 14, заключаем, что граница для Е есть 23 + 11 = 34 (см. рис. 373). Выбираем свойство Уо, соответствуюьцее минимальному из чисел, набранных курсивом г) На зту задачу обратил мое нниманпе Барба (Р. Вагьапб), а решил ее этим методом Талансе (М. Йе Та)апсе) — инженер-математик компании Белл Лжеиерагг Электрик. 838 в последнем столбце. Найдем нижнюю границу для Ес —— = Š— Ес.
Выбрасывая строку С из матрицы на рис. 367 и действуя, как раньше, получаем (рис. 368). Располагая числа, набранные курсивом в последнем столбце, в порядке 1, 4, 5, 9, заключаем, что граница для Ес есть 35+ 5 = 40 (см. рис. 373). Найдем границу для Ес. Вычитая а Ь е й е 1 К Ъ Суммы Вмчиеленне нижней границы дли Е и Минимальные эначении Рис. 369. строку С из всех строк (последний столбец матрицы на рис. 367 не учитывается) и полагая х',.
=гпах(0, х, — х,), !=А, В, О, Е; /=а, Ь,..., й, получаем (рис. 369). (Числа последнего столбца — суммы соответствующих элементов строки.) Так как должны быть исполнены С и еще два произведения, то нужно прибавить к 19, а Ь е А и ! К Ь Сумма А Вычисление нингней и границы дли Е П Е с в Минимальнле эначеине Рнс. 370, во-первых, 6, а во-вторых, ! 1 (так как курсивные числа в последнем столбце — это 11, 5, 11, 14). Итак, нижняя граница для Ес есть 19 + 6 + 11 = 36. Теперь нам следует применить свойство Ув к Ес. Используя Ус Л Ув, строим Ес Й Ев Лля этого вычеркиваем строку В в матрице на рис. 369 и, действуя, как раньше, получаем (рис.
370). Так как должны быть исполнены С и еще два произведе. ния, то нужно прибавить к 19, во-первых, 17, а во-вторых, 3 (так как курсивные числа в последнем столбце — это 1, 3, 10). Итак, нижняя граница для Есй Ез есть 19+17+ 3=39. Используя Ус Л Ув, строим Ес() Ез. Вычитая строку В из всех 336 строк (последний столбец не учитывается) матрицы на рис. 369 и полагая х,".=гпах(0,х,' — хв ), 1=А, 0,Е; 1=а, Ь,..., й, получаем (рис. 371). (Числа последнего столбца — суммы соответствующих элементов строки.) Так как В и С должны быть а Ь л д е 1 Х Ь Сумма А Вычнеленне нннгнее границЫ длн Е П Е С В Мнннмальнее еначенне Рис. 37Е исполнены, то к ~щах(хс,п хв, )=-2+3+3+ + + + 1 с,у в,г =- -«-4+ 3 = 29 нужно прибавить, во-первых, 1, а во-вторых, 11 (так как курсивные числа в последнем столбце — это 11, 11, 13).
Итак, нижняя граница для Ес П Ев есть 29+ 1+ 11 = 41, а ь л и е 7 х д суммы Вычнеленне нннгнел В границы длн Е В Е а Е С В А Е Мнннмальнее нначенне Рис. 372. Теперь нам следует применить свойство УА и, исходя из Ес П Ев, построить Ес П Ев П ЕА и Ес П Ев П ЕА. Граница для ЕсПЕвПЕА: ~н щах (хс Р хр Р хв 1) = 3 + 8 + 9 + 6 + 9 + 2 + 5 + 7 = 49. 1 Вычитая строку А из всех строк матрицы на рис. 370 (последний столбец не учитывается) и полагая х,'" = щах(0, х,'— — хд,.), 1 = О, Е; 1 = а, Ь, ..., Ь, получаем (рис.
372). (Числа последнего столбца — суммы соответствующих элементов строки.) Так как должны быть исполнены С, А и еще одно произведение, то к ~~ гпах(кс 1, хд 1) =3+ 2+ 5+6+ 8+1+6+ 4 = ! = 35 нужно прибавить, во-первых, 2, а во-вторых, 3, т. е. 35-«- -«- 2+ 3 = 40 есть нижнЯЯ гРаница Ес П Ев П ЕА. Далее, пРименяя Ур, строим Ес П Ев П ЕА П Ев и Ес П Ев П ЕА П Ев. 337 Граница для первого ~2~ шах (хс /, хл /, хз;) = 3 + 8 + 9 + 6 + 8 + 2 + 6 -1- 5 = 47, / а для второго ~'.~шах(хс,/, х/ь/, хо,/)=3+ 2+ 5+6+9+ 2+6+7=40.
l Рис. 373. Следовательно, искомое оптимальное решение есть (А, С, 0) со значением 40 (рис. 373). ф 56. Применение методов Монте-Карло Если не знают ни алгоритма оптимизации, ни приемлемого эвристического метода улучшения решения, то применяют метод Монте-Карло, выбирая решения в соответствии с некоторыми вероятностными законами (число решений должно быть достаточно большим). Закон частот полученных значений выводится статистически. Решения с наименьшим (соответственно наибольшим) значением в той или иной мере характеризуют Л % пользуют индекс дисперсии а и минимум (макспмум). Часто ис- (56А) где ьм — наибольшее, о — наименьшее значение (рис. 374), Даже в том случае, когда число выбранных решений велико, методом Монте-Карло следует пользоваться с осторожностью; 333 й а о й ~ ю Г о ~' ~и ы а с 3 $ О О.
с С С ь о 3 Ф Ц д о а а М $ о ~\ Ф У Р Ф о О аы ао Р3 ь Х Дь О а~ ( а ~' о $ ы $" ф > о ~о ы й а Ы Б 3 $ "о ы ~ И 1 ~о Х -а о= С оь х— ы е С И СУ 22 ~ ф ва 2 а й ао р ~ К Ф з щ Р В ы 53 й. ~С оа Ю "= а И И ок пй ~а О М а Ю Ю й 4 Ы о Л~ о Ю Ю И И -Ф Е вЂ” Ф ач аМ 5" "3 3 о ~а ~ !! К И ~ У $ „. о Е У $ о ( ао о ~~ Е Ф й к 339 однако для решения некоторых задач неизвестны другие методы и, как говорится, на безрыбье и рак рыба! На примере из 3 55 (см.
рис. 360) посмотрим, как можно воспользоваться указанным методом. Программа вычислений изображена на рис. 375. сд м ~п а и ж и ьлюачсстс Рис. 376. На рис. 376 представлено распределение частот значений выбранных 375 решений (некоторые из них указаны ниже), Стоимость доставки = 54: (О Е В С В О), (О 0 0), (О Е В 0), (О А 0): 19 + 14 + 15 + 6 = 54; (0 00), (О В С 00), (О ВЕЕО), (О А О): 14+ 17+ 17+6=54; (О ВЕ 0), (О ЕОО), (О С ВЕО), (О А 0): 17+ 15+ 16+ 6 =54; (ОЕВ О), (О А ГО), (О В С В 0), (О В 0); 13+ 14+17+ 10=54; (О В О 0), (О Е О 0), (О В С Е 0), (О А О): 17 + 15 + 16 + 6 = 54. Стоимость доставки = 56: (О Е В 0), (О С В 0), (О Е В В О), (О А 0): 17 + 17 + 16 + 6 = 56; (О ЕВ О), (0 00), (О ОСВЕ 0), (О АО): 17+ 14+ 19+6=56; 340 (О С Р 0), (О ВЕРО), (О РР 0), (О А 0): 17+ 18+ 15+ 6=56; (О Е Р 0), (О Р В 0), (О В Р С 0), (О А 0): 13 + 17 + 20 -1- 6 = 56, Стоимость доставки = 57: (О Е В С А 0), (О Р 0), (О Р Р 0), (О Р 0): 18 + 14+ 15 + 10 = 57; (О Е Р 0), (О А Р 0), (О С Р В 0), (О В О): 13 + 14+ 20 + 10 = 57; (О СРО), (О РРО), (О Е Р В О), (О А 0): 20+ 15+ 16+6 =57; (ОС РО), (О ВР 0), (ОЕРР 0), (О А 0); 17+ 17+ 17+6= 57;.
(О В Е С Р 0), (О Р 0), (О Р Р 0), (О Л 0): 22 + 14 + 15 + 6 = 57; (ОЕРО), (О В РРО), (ОРСО), (О А 0): 13+ 18+ 20+6 =57; (О Р 0), (О ВРО), (О С РРЕО), (О АО): 14+ 17+ 20+ 6=57; (О С В Р 0), (О Р Р 0), (О Е .0 0), (О А 0): 23 + 15 + 13 + 6 = 57; (О А С В Е 0), (О Р 0), (О Р Р 0), (О Р 0): 18 + 14+ 15 + 10 = 57; (ОЕСР О), (О ЛРО), (О РВ О), (О ВО): 16+ 14+17+ 10=57. Стоимость доставки = 58: (О РЕВО), (О ВРО), (ОС РО), (О А 0): 18+ 17+ 17+6 =58; (О В С Р 0), (О А Р 0), (О Р 0), (О Е Р 0): 17 + 14+14 + 13 = 58; (О С В А Е 0), (О Р 0), (О Р Р 0), (О Р 0): 19 + 14+ 15 + 10 = 58.
й 57. Понятие й-оптимальности Пусть 8 — конечное множество решений комбинаторной задачи. Связывая с каждым решением 5 ен 8 число о(5), приходим к разбиению 8 на классы эквивалентности, каждый из которых состоит из решений с одним и тем же о(5). Эти классы можно упорядочить, и мы изложим алгоритм ') получения первых й классов для последовательного графа (2 53) со значением на дугах. Предварительно введем определения. Пусть Е = (Е„Е„..., Е„...,, Ен) (57.1) — конечное множество, упорядоченное числовой функцией и, =Р(Ег).
(57.2) Назовем подмножество Е!'! 1-максимальным подмножеством, или 1-максимальным классом, если *) Ег ен Е, Е ен Еиг =фи,.)ог! (57.3) ') Этот параграф воспроизводит частично статью автора и !х рю о н а !й. С г и оп), йечпе ггапеа!зе г)е й. О. 8, 3 )пшез!ге !964, М 32, 293 — 302. *) Заметим, что Еп! состоит из всех элементов с одним и тем же оь Это же относится и к Е!"!. !))рим. перев.) 34! подмножество Е<М назовем 2-максимальным, или 2-максималь- ным классом, если Е< ~ Š— Еп', Е ~ Е<" Ф о; ) он ...; (57.4) подмножество Е<ю назовем н-максимальным, или й-л<аксималь- ным классом, если Е<ев Е 0 Еы', Е! ~ Е" ~о< хоо (57.5) а«о Элемент Е, ен Е<м называют п-максимальным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
