Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 61
Текст из файла (страница 61)
С.-С. Ап 0()Е!!оя !ой! 1'!) А!ь>огц!цп 1о> г!пд>пй М>пцпигп Зрапп!пй Тгеез, !п1. Ргос. (.е!!егь, 4 (!975), 21 — 25. Множество близких алгоритмов, включая алгоритм со сложностью 0(Е) для разреженных графов, опн.гно в работе Комментарии и ссылки 315 [СТ) СЬегйоп $)., Тат!ап К. Е.
Е!пгйпй М!пппшп 5раппгпй Тгеез, 2. 51АМ Совр., 5 (!976), 724 — 742. Жадный алгеритм для задачи МГЗД представлен в статье [Кг] Кгизйа! Л. В. Оп )па 3Ьог)ез) 5раппгпй 5нЫгее о$ а ОгарЬ апб 1Ье Тгаче)!пй 5а)аавап РгоЫет, Ргас. Атег. МаКп 5ес., 7 (1956), 48 — 50. Матроиды (известные также как предгеометрии по причинам, связанным с задачей 13) были впервые изучены в работе [г[г)г) ТзгЫ)пеу Н.
Оп (йе АЬз1гас$ Ргорег))ез о$ Е)пеаг Оерепбепсе, Атег. Л. Магп., 57 (1935), 509 — 533. Для более глубокого изучения матроидов см, также [Тп) ТнНе %. Т. асс!игах оп Ма!го!бз, 2. Кт. ХВ5, 69В (1965), 1 — 48. [СК) Старо Н. Н., Ко$а О.-С. Оп (йе Еоипба1юпз о1 СотЫпа1ог!а) Тйеогу СогпИпа1ог!а! Оеогпе1ыез. СавЬг)бйе, Маззл М. 1. Т.
Ргезз, 1970. Связь теории матроидоа с комбинаторной оптимизацией и алгоритмом Краскала была впервые показана в работе [Е61) Ебвопбз 2. Ма!го)бз апб )йе Огеебу А1йоПНпп, Ма)Ь. Ргой., 1 (1971), 127— 136. В этой статье также анонсировано полиномиальное решение задачи о пересечении двух матроидов. Алгоритм, приведенный на рис. 12.21, впервые опубликован в работе [).а)) Санг)ег Е. 1.. Ма1гоМ )п1егзес1!оп А)йог!1Ьвз, Ма1Ь. Ргой., 9 (1975), 31 — 56. Эквивалентная задача о разбиении матроида (задача 18) решена в статье [Е02) Ебвопбз Л.
М~п)внв Раг(йюп о1 а Ма1гоМ гп1о )пберсгтбеп) бпЬзейм 2. Кез. Ь)В5, 69В (1965), 67 — 77. Задачи 4 и 5 взяты из [5Ь) 5Ьапюз М. 1. Согпри1аНопа) Оеове1гу (неопубликованная диссертация, Уа1е $)п!чегз!1у, 1978). Задачи 10 и 11 взяты из [ЕР) Ебвопбз 3., Гн)йегзоп О. К. Тгапзчегза)з апб Ма1гоМ Раг)!1!оп, 3. Кез. Ь)В5, 69В (1965), 147 — 153, а задачи 13, 14 — из оригинальной статьи Уитни [%Ъ). Эффективные алгоритмы для нахождения кратчайигего ордереаа во взвешенном орграфе можно найти в работах 1Е83] Ебтопбз ) Ор1ипит Вгапсвпйз, ). Кез, Г(В5, 71В (1967), 233 — 240.
[Ка) Кагр К. М А 5ппр)е ОепчаНоп о$ Ебтопбзп А18огйвп $ог Ор!!гппв Вгапсп!пй, Ке)шог1гз, 1 (1971), 265 — 272. [Та) Тат!ап К. Е. Р!пб)пй Ор$!пппп Вгапспшйз, )п1. Ргсс !.еыегз, 3 (1974), 25 — 35. Задача о матроиде с соответствием (равд 12.6.2) для матричных матроидоа ре. шается в работе [Ео) Еочазх 1.. Тйе Ма1гогй Ма1сЫпй РгоЫет, Ргос. Соп1. оп А18еЬгаю Огарп ТЬеогу, 5гедеб, Нппйагу, 1978 Факт, использованный в задаче 2, взят нз [ВГРКТ) В)пв 51., Е)оуб К.
Уч*., ГгаН Ч. К., К!чез1 К. Е., Тат)ап К. Е, Типе Воипбз 1ог 5е1есыоп, ЗС55, 7 (1973), 448 — 461. !3 Целочисленное линейное лрограммирование 1З.1 Введение Задачей целочисленного линейноео программирования (ЦЛП) называют следующую задачу оптимизации: пйпс'х, Ах=)т, х)0, х целочисленно. Аналогично можно определить задачу ЦГ!П в канонической и обшей формах, при этом утверждение о том, что все эти формы эквивалентны (см. 5' 2.!), остается справедливым.
Элементы магрицы А и векторов ?т и с предполагаются целыми. К необходимости формулировки и решения задач ЦЛП первоначально привел тот факт, что в некоторых приложениях ЛГ! дробные ииие ости х, Рис !3.!. Четыре цело гислсипые гочки, алижейшие к оптимуму зехичи Лг!. челопустимы решения нежелагельны — представьте себе, например, приложение, в котором х, — число самолетов, назначаемых на маршруг !. Первая реакция на задачу ЦЛП обычно бывает гакой: «Почему бы не решить соответствующую задачу ЛГ! и округлить решения до ближайшего целого числа?» Конечно, во многих случаях эта страте. гия даег неплохой резульгаг, особенно гогда, когда ожидается, что решение будет содержа г ь большие целые числа и буде г, следови гель- 1З.1.
Введение 317 ю, не чувствительно к округлению. Однако и здесь возникают проб«емы: не всегда ясно, как провести округление до допустимого цеючнсленного решения (см. рис. 13.1 и 14.1). Имеются и другие очень :ерьезные факторы, ограничивающие этот подход. Большинство «риложений ЦЛГ! не являются просто задачами ЛП, в которых не«звестные принимают значения с единичным шагом.
Чаще задача (ЛП является результатом сознательного применения целочислен. «ых ограничений к модельным комбинаторнь«.««ограничениям или «елинейностям различного рода. Такие задачи ЦЛП по своей приюде не допускают подхода, основанного на округлении, в основном ютому, что при округлении теряется основная цель формулировки «адачи в виде задачи Ц.«!П, н правильно выполнить такое округле.
«ие так же тяжело, как решить с самого начала исходную комби«атор««ую задачу. Рассмотрим несколько «эких примеров Пример 13.1 (формулировка задачи коммивояжера как задачи це«очисленного линейного программирования). Рассмотрим задачу ком. яивояжера с и+1 городами, представленными вершинами О, 1,... ..., и н ма«рицей !с;,! (не обязагельно симметричной) расстояний ЯеждУ гоРодами. Сопоставив дУге («, 1) пеРеменнУю хн и положив хы=!, если дуга («, 1) содержится в обходе, и О в противном слу«ае, можно для начала сформулировать ЗК следующим образом: ш!пх = ~ снх«, и /ьв «М« О< х«, <1 для всех «, 1, хг — целые длЯ всех «', 1', а (а) ~ х, = 1, 1 = О, ..., и, =о (!3Л) (б) ~х, =1, «'=1, ...,и. «=о Равенства (а) выражают гот факт, что в каждую вершину входит ровно одна дуга, а равенства (б) — тот факт, что из каждой вершины 1,, и выходит ровно одна дуга (из (а) и (б) вместе вытекае«, что из вершины 0 также выходит одна дуга; см, задачу 7).
Однако все эти условия не описывают полностью ограничений ЗК, так как любое множесгво непересекающихся циклов будет удовлетворять (13.1), что проиллюстрировано на рис. 13.2(а). В действительности (13.1) описывает задачу о назначенаях (Э 11.1), которая, очевидно, легче, чем ЗК. Нам нужны ограничения, которые исключали бы непересекающиеся циклы, или подооходы, как они буду«называться в данном контексте. Один из возможных вариантов состои«с следующем Юрз !. Г!ус«ь(5, 5) — не«риииальнос разби 'пие чножес«ва («', 1, ..., п). Для каждого такого разбиения погребуем, чтобы выполня- 3)В Гл.
!8. Целочисленное линеа)нее программирование лось неравенство ~л хг >!, г ев /еЯ (13.2) Эта идея проиллюстрирована на рис. !3.2(б) — все такие ограничения вместе обеспечивают то, что граф является единым обходом. Однако эта г)ормулировка едва ли может использоваться на (а) (б) Рис. 1Зид а) лхопустимос решение задачи !3.), ие являющееся обходом.
б) Ограннчение, исключающее подобходм. практике даже для задач среднего размера, так как имеется 2"" — 2 нетривиальных разбиений, для каждого из которых вводится ограничение. В более краткой формулировке, принадлежащей Таккеру !МТ2), ограничения (!3.2), устраняющие подобходы, заменяются неравен- ствами и,— ну+ ггхгг ( и — 1, ! ( г' ~ ! < и, (13.3) где и„г=!, ..., и,— неограниченные действительные переменные. Покажем, что эти неравенства ие только требуют, чгобы решения были обходами, но и не 1гсключают никаких обходов.
Предложение. Ограничения (!3. !) и (!3.3) определяюг ЗК. Доказательство. Покажем сначала, что любое допустимое решение является обходом. Лля этого покажем, что каждый цикл проходит через город О. Лопустим противное, т, е. что последовательность городов г„..., 1я является циклом, несодержащим города О. 11.1. Введение 319 Неравенства (13.3) для дуг этого цикла дают и, — и, +п~(п — 1, 1=-1, ... в — 1 '1 'ее! и~,— пи+ и (и — 1.
Складывая зти неравенства, получаем противоречие. Для завершения доказательства вокал<ем, что для каждого допустимого обхода существукп значения переменных ио удовлетворяющие (1З.З). Действительно, пусть ив=О и и;=1, если город 1 при данном обходе посещается 1-м по сче1у, 1--=1, ..., п. Если хм=О, то должно быть и,— и1 п — 1, 1е лвь)' -и, что всегда выполняется, так как случай и;=и и из=0 исключен, поскольку иначе дуга (1, О) содержится в обходе и, следовательно, х,,= — 1.
Если хи=1, то должно быть и,— и1+пе.п — 1, что выполняется, так как если ( и )в последовательные города на обходе, то и; — и1 — — — 1 (заметим, что случай и,=п и ив=О исключен из (13.3)) Описанная формулировка содержит переменные хы, которые должны быть целыми, и переменные иь которые могут принимать произвольные значения, Токая задача называется слеешанной задачей целочисленного линейного программирования (СЦЛП). Пример 13.2 (общая задача о расписании). Задачи о расписании образуют важный класс комбинаторных задач оптимизации. Они касаются оптимального выполнения заданного множества заданий с использованием нескольких процессоров и других ресурсов при определенных ограничениях, таких, как приоритез одного задания над другим, ограничения на время окончания заданий и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
