Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 56
Текст из файла (страница 56)
е. требуется, чтобы только компоненты вектора у были целыми. Для заданного значения у задача (1) примет следующий вид: минимизировать с2х 2) при условиях А,х)Ь вЂ” А,у, х)0. (2) Задача (2) является обычной задачей линейного программирования. Выпишем двойственную задачу к (2): максимизировать н (Ь вЂ” Азу) при условиях ИА, » (с„п ) О. (3) Отметим два интересных свойства задачи (3). Во-первых, область допустимых решений, определяемая условием ИА2 ' е2, не зависит от у. Во-вторых, вне зависимости от величины у максимум линейной формы н (Ь вЂ” А,у) всегда достигается.
в одной из вершин выпуклого многогранника, определяемого условием ИА2 с2, в предположении, что это мноясество ограниченное. Пусть и" (р =- 1,..., Р) — произвольная вершина этого выпуклого многограпннка. Тогда задачу (3) можно переписать в виде ') Для заданного у слагаемое сзу является константой и может быть опущено.— Прим. ред. ГЛ. НС СМЕШАННЫЙ АЛГОРИТМ максимизировать н" (Ь вЂ” А,у) ИР ) О (р = 1,..., Р). (3') при условиях Если задача (3) не имеет допустимых решений, то по теореме двойственности задача (2) либо не имеет допустимых решений, либо целевая функция па множестве допустимых решений неограничена.
Если у задачи (3)пет конечного оптимального решения, то задача (2) не имеет допустимых решений. И в том и в другом случае задача (1) не имеет конечного оптимального решения. оеичени Р н с. 153. Поэтому пас интересует лишь тот случай, когда задача (3) обладает оптимальным решением. Следует заметить, что в этом случае выпуклое множество, определяемое условиями ИА1 (~ с„н ) О, непусто, но необязаточьпо ограничено.
Вполне возможно, что на неограниченном множестве (н ! ИА1 - с1, н ) О) для определенных значений (Ь вЂ” Азу) целевая функция н (Ь вЂ” Азу) пеограничена, однако оптимальная вершина, связанная с оптимальной величиной у, имеет конечные координаты. Такая ситуация показана на рис. 15.1, где кружком обозначена оптимальная вершина, а выпуклое множество неограничено.
В случае когда н принимает нсограничепныо значения.для определенных значений (Ь вЂ” Азу), можно добавить к ограничениям ИА1 ( с„н ) О еще одно: ,'~~ и1 ( ЛХ, где Лт — достаточно большая положительная константа. Такое ограничение показано на рис. 15.1 пунктирной линней. 1эл, метОд РАЗвяення 317 Если выпуклое множество, определяемое условиями нА, ( с„ н ) О, ограничено или сделано ограниченным добавлением неравенства ~ и1 М, то задачи (3) и (3') эквивалентны, что является интересующим пас случаем. Копочпо, мы не можем узнать, является ли множество (н ! пА1( с„н ~~ О) ограниченны»1, прежде чем решим задачу (3).
Подставив условия задачи (3') в (1), получим следующую задачу: минимизировать г при условиях г ) с»у + шах и" (Ь вЂ” А«у), нв н»)О (р=1, ..., Р); у>О. Каждое значение воктора пн дает одно ограничение для задачи (1 ), а сама задача является «чистой» задачей целочисленного программирования, т. е. все ое перел«еппые у» долншы принимать целые значения. Если известна оптимальная вершина и*, задачу (1') можно решить как «чистую» целочисленную задачу любым из существующих способов и получить оптимальные значения гн и у*. Подставив ун в условия (2), найдем минимум с,х прн условиях А1х» - Ь вЂ” А«у*, х ) О, и получим оптимальное значение х*. Подставив хн и ун в условия (1), получим г = с,хн +. с»ун.
Это значение должно, конечно, совпадать с эн, полученным из (1 ). Если оптимальная вершина и* не извостна, то можно, перебрав все вершины нг, найти решение задачи (1'). Трудность такого подхода состоит в том, что обычно существует сли1пком много вершин «Р, поэтому для получения оптимальной вершины пн будем использовать следующую итеративную процедуру.
Возьмем любое допустимое значение и (по обязательно веригину), которое удовлетворяет условиям нА1 < с1, и ) О, подставим его в (1'). Пусть для этого значения н ре1нением задачи (1') будут г и у. Используя у для решения задачи (3), найдем значение н, максимизирующее и (Ь вЂ” А»у). Пусть решением будет и. Подставим н в условия (1'), т. е.
добавим еще одно неравенство, после чего опять найдем у. Итеративная процедура продолжается, пока не будет получено' оптимальное значение пн. Для оптимальных значений в*, у* и з* из (1 ) имеем э* = с»у*+ н* (Ь вЂ” А»у') > а для произвольного н из (1') получим з = с«у + н (Ь вЂ” А,у), ГЛ.
15. СМЕШАННЫЙ АЛГОРИТМ откуда з(з*, поскольку з)с»у+в(Ь вЂ” Азу) является лишь подмножеством всех ограничений в. (1'). Оптимальное значение гь в (1) будет получено, если используются все значения и" или оптимальное и*. Для того чтобы проверить, является ли и оптимальной вершиной, решим сначала задачу (1 ), используя и„ и получим у и г, а затем, используя у в задаче (3), найдем максимум п(Ь вЂ” Азу). Если з — с»у=шахи(Ь вЂ” А»у), то и — оптималь- Н иая вершине.
Теперь выпишем алгоритм разбиения формально. Ш а г О. Начать с п ) О, удовлетворяющего условию ИА» ( ( с,; и не обязательно должно быть вершиной. Если такого и ие существует, то задача (1) не имеет допустимых решений. Перейти к шагу 1.
Ш а г 1. Решить «чистую» целочисленную задачу: минимизировать г при условиях з~ )с»у+ и (Ь вЂ” Азу), уз О, у ва 0 (шой 1). Если з не ограничено снизу, то з качестве з взять любое небольшое значение. Шаг 2. Используя у, полученное на шаге 1, решить линейную программу максимизировать и (Ь вЂ” А»у) при условиях ИА,(со п)0.
Если и не ограничено, а и (Ь вЂ” А»у) ограничено, то добавить ограничение ~и;(М, где М вЂ” большая положительная константа, и решить задачу. Пусть решением этой программы будет и. Проверим выполнение неравенства з — с»у( и (Ь вЂ” А,у). Если опо выполняется как равенство, то перейти к шагу 3. Если не выполняется, перейти к шагу 1 и добавить ограничение г ) ~) с»у + и (Ь вЂ” А»у) к существующему множеству ограничений м,2. метод РАЭБиения в задаче (1').
Неравенство в задаче (1') монсет быть опущено, если соответствующая ему слабая переменная принимает положительное значение. ' Ш а г 3. Используя у, полученное на шаге 1> решить задачу линейного программирования: найти минимум с,х при условиях А,х)Ь вЂ” Азу, х)О. Пусть решением етой задачи будет х. Тогда х и у — оптимальные решения и з' = с,х + сзу. Теперь докажем, что, во-первых, алгоритм конечен, во-вторых, оп дает оптимальное решение и, в-третьих, в любое время моноло получить верхнюю и нижнюю границы оптимального решения зе.
Для того чтобы доказать конечность алгоритма, заметим, что существует лишь конечное число вершин множества, задаваемого а(Ь вЂ” Аиуб/ г 0птамаяьяая г / и [Ь-А~у") Г / / / Р л с. 15.2. условиями ИА1 ( см н ) О, если оно ограничено. Если оно не ограничено, то после добавления условия ~ и; ( М множество (н ) ИА~ ( с„н ) О, ,"„и~ ( М) становится ограниченным. Для доказательства конечности алгоритма следует выяснить только один вопрос: будет ли в итерационном процессе, состоящем из шагов 1 и 2, при решении задачи (3) получаться каждый раз новая 'вершина нгр Выглядит вполне правдоподобным, что два неоптимальных значения у' и у" могут давать одну и ту же вершину н. Такой случай показан на рис.
15.2. К счастью, такая ситуация ГЛ. ПС СМКШАННЫИ АЛГОРИТМ 320 никогда не возникает. ' Пусть з и у — решение, полученное на шаге 1, т. е. з=сзу —;п(Ь вЂ” Азу) или г — сзу=п(Ь вЂ” Азу). (4) Поскольку з получается из подмножества ограничений в (т'), то з(з*, (5) где з* — оптимальное значение з. Из теории двойственности шах и (Ь вЂ” Азу) = шгп с,х, где и принадлежит множеству, опрсделяев1оиу условиями пА1 ~ с„ и ) О, и па х наложены ограничения А,х ) Ъ вЂ” Азу, х ) О. Пусть и — решение, полученное па шаге 2.
Тогда (б) п(Ь вЂ” Азу) = с,х. Заметим, что х и у дают. допустимое ре1пенис, поскольку А,х+А,у> Ь, откуда следует, что с1х1.сзу>г*, т. е. (7) с,х )~ 3* — сзу. Из условий (4), (5), (6) н (7) получим и (Ь вЂ” А,у) = с,х >~ з' — с,у > з — сзу = и (Ь вЂ” Азу), где равенство возможяо, лишь осли з — оптимальное значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
