Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 14
Текст из файла (страница 14)
В таблице приведены пять векторов, являющихся решениями прямой и двойственной задач. х'г! х'2! х'З! у!!) у(2! хо У! Уг -гз Уз 3.4. Гкомитгичвская инткгпгктхция Нетрудно проверить, что любой вектор х<'> (~'= 1, 2, 3) ортогонален каждому вектору у<е (>=1, 2); х<'>, х<э> и хм> — допустимые решения, в то время как у<'> допустимо, а у<э> — нет; х<з> и у<'> образуют пару оптимальных решений, поскольку з = — х, = = +7/3=уз=к>. 3.4. Геометрическая интерпретация двойственности и дополняющей нежесткости (Гомори [831) Рассмотрим задачу: найти минимум при условиях 2' а»х> ) Ь< хт)О (< = 1, ..., и>), (>' = 1, ..., и), или, в другой форме записи: минимизировать сх при условиях а,*х Ь; (2) (>=1, ..., т, ..., т+и), 6 т.хт где а*;(Ь;") при >=1, ..., >и совпада>от с а< (Ь>); а~>.< есть единичный орт ео а Ь,*„+;=О при 1=1, ..., и. Обычное условие наличия без- !,"<" ','„"', „...
условного экстремума функции во внутренней точке есть обращение в О градиента функции в этой точко. Если при этом должны выполняться некоторые ограничения па переменные в виде равенств, то условном паличия экстремума в допустимой точке будет требование, чтобы в этой точке градиент функции и нормали к поверхностям, соответствующим ограничениям, были направлены Р в с. 3.<. в «одну сторону». Более точно, градиент функции в этой точке должен быть линейной комбинацией этих нормалей к поверхностям-ограничениям.
В задаче линейного программирования каждое неравенство определяет допустимую область — полупространство. Для того чтобы допустимая точка х была оптимальной, необходимо, чтобы градиент в х гл. з. двоиствгпность 82 т+и с= 1 у!а', (За) !=! у! ) 0 =о а!х = дт.
(Зб) Покажем, что х является оптимальным решением задачи (1), (2). Умножим обе части равенства (За) на х: .т+и ЗВ+в сх= ~ у!а,",х= у!д,*. 5=1 1=! (4а) Для других у!)О, удовлетворяющих равенству (За), ЯВ+Ф ЗЦ-В ох=- ~ у!атх) ~, у!дт!. !=- ! ! —.— ! (4б) Из условий (4а) и (4б) следует, что у — оптимальное решение вадачи! найти максимум (5) уЬ* при условиях т+и с= ~, у;а,', у!)О. (6) з=! Поскольку последние л вектор-строк аа являются единичными т ортами, а уЬ* = ~ у!д! в силу д +!= 0 (! = 1, ..., !г), то задача (5), !=! (6) эквивалентна следующей: найти максимум (7) при условиях (6) (0) (з=т! ..., т). выражался в виде неотрицательной линейной комбинации навравлягощих векторов тех (и только тех) ограничений, которые в точке х обращатотся в равенства (сзт. рис.
ЗЛ). Таким образом, если х — допустимая точка, в которой функция сх достигает минимума, то должна существовать неотрицательная линейная комбинация нормалей векторов а,', дающая вектор с— градиент функции сх: 83 з„ч гвомвтРнчвскля нптРРЛРзтлпня Распишем векторное неравенство (8) по компонентам, учтя при этом, что а,*=а! при 1=1, ..., лз.
Получим Х у!а!1(с! Ц=-1, ..., п). (8') 1=1 Итак, вектор (р1, ..., р„) является оптимальным решением задачи (7), (8), (9), двойственной к (1), (2). Так как х — допустин~ нт мая точка, а ех= х~' „р1ЬР = ~~~ р;Ьь то в силу теоремы двойствен1=1 * * 1=! ности х — оптимальное решение задачи (1), (2), т. е. исходной задачи.
В теоремах о дополняющей пежесткости утверждалось, что рз (а1х — Ь1) = 0') (1 = 1, ..., пт). В слабой форме теоремы о дояолпяющей нежесткости утвержда- лось, что если р1 О, то а1х — Ь;=О, если азх — Ь1) О, то у!=0. В сильной форме теоремы о дополняющей нежесткости утвержда- лось: если у!=0, то а;х — Ь;- О, если а;х — Ь;=О, то уз- О. Дадим геометрическую интерпретацито этим результатам. На рис.
3.2 изображены три гиперплоскости а;х = Ь, = О (1 = 1, 2, 3) и нормали к ним а„аю а,. Если вектор с — такой, как показано па рис. 3.2, то он моягет быть выражен и инде неотрицательной линейной комбинации векторов а, и аю вертпина в кружке дает оптимальное решение. Пусть у„рз и уз — соответствующие коэффициенты линейной комбинации. Заметим, что здесь р1) Ос~а,х — Ь,=О, рз ) О сс а,х — Ьз = О, рз = 0 1 азх — Ьз ) О.
!) Другое утверждение атих теорем яу (с) — уа ) = О симметрично рассмотренному и интерпретируется аналогично,— Прим. рад. зе гл. 3. двойствннность В этом случае оптимальное решение удовлетворяет как слабой, так и сильной форме условий дополняющей нежесткости. С другой стороны, если вектор с в такой, как показано на рис.
3.3 (т. е. с — нормаль к одной из гиперплоскостей; а,х— — Ьз = О), то оптимальная вершина в кружке не удовлетворяет .аа, с аз аз аз Р и с. 3.4. Р и с. 3.3. Р в с. 3.2. сильной форме условия дополняющей нежесткости, поскольку и рг =- О, и а,х — Ь, = О. Однако точка, взятая в кружок ка рис.
3.4, являющаяся также оптимальным решением, удовлетворяет и сильной, и слабой форме дополняющей нежесткости: у,) Осе а,х — Ь,=О, уз= О::г агх — Ь,=О, уз — — О з=~ азх — Ьз) О. Упражнения 1. Рассмотрим задачу линейного программирования: минимизировать г = хз + хг + хз при условиях хз+ хг хз(~ 4, хз +хз= 3. Запишите условия двойственной задачи с двойственными переменными: а) пе имеющими ограничений на знак, б) подчиненнымн требованию неотрицательности.
ДОПОЛНЕНИЕ 2. Приведите примеры прямой и двойствеппой задач, ни одва из которых не имеет допустимых решений. 3. Покажите, что если прямая задача обладает вырожденпым оптимальпым решением, то двойственная задача имеет более чем одпо оптимальпое решение. 4. Если оптимальное решение удовлетворяет некоторому ограничению задачи линейного программирования как строгому перавепству, то двойствеппая переменная у;, соответствующая этому иеравенству, равна нулю. Коли оптимальное решение удовлетворяет ограничению как равенству, то двойсгвеппая переменная у;, соответствующая этому ограпичекию, принимает положительное зпачение. Дайте экономическую интерпретацию этому результату.
Дополнение Доказательство теоремы двойствеппости, предло1кенное в настоящей главе, основывается на теореме 1.4, которая в свою очередь использует теорему о разделяющей гиперплоекоотпи или эквивалентные ей утверждепия. Мояшо доказать теорему двойственности, пользуясь симплекс-методом (см. Дапциг 1371). Другое доказательство теоремы двойственности, использующее вычисления, приводится в приложении В. ДВОЙСТВЕННЫИ СИМПЛЕКС-МЕТОД 4 1.
Двойственный симплекс-метод (Лемке 1141]) Как видно из гл. 3, с каждой задачей линейного программирования тесно связана другая задача, двойственная к ней. В гл. 2 был изложен способ решения аадачи линейного программирования, называемый симплекс-методом. В атой главе будет описан другой способ решения задачи линейного программирования, называемый двойственным сиьшлекс-методом. Эти два метода связаны между собой теорией двойственности. Напомним, что симплекс-метод для задачи минимизации состоит из следующих шагов. 1. Из п вектор-столбцов матрицы А выбирается т векторов в качестве бааиса. 2.
С помощью метода исключения соответствующие базисным столбцам компоненты вектора с преобразуются в нули, а (и х т)- матпипа базиснь х столбпов приводится к единичной. В результате все компоненты правой части Ь должны стать неотрицательными. (Если не удается легко получить такой базис, то в качестве векторов начального базиса используются искусственные векторы; см. $2.3.) 3. Для введения в базис выбирается столбец а, с относительной оценкой с, ( О.
Для выведения нз базиса предназначается столбец а„, выбранный по правилу проверки отношения так, чтобы сохранялось условие Ь; ) О. 4. Элемент а„, — ведущий. С помощью метода исключения базис преобразуется. Возврат к шагу 3. Если на шаге 3 все ст ) О, то текущее решение является оптимальным. Заметим, что на калгдом шаге симплекс-метод сохраняет прямую допустимость решения, т. е. Ь~ ~ )О, а в конце су ) О. Позтому текущее решение в последней таблице является и прямо, и двойственно допустимым, а следовательно, оптимальным. Напомним, что условие ст ) О влечет за собой двойственную допустимость.
Действительно, если с~ = с~ — наг ) О (для всех 1), т. е. с=с — нА~О, или с> яА, то н — допустимое решение двойственной задачи. мь двоиствкнныя симппккс-мктод ' Двойственный симплекс-метод начинает с двойственно допустимого решения и сохраняет его двойственно допустимым на протяжении всех шагов. Двойственный симплекс-метод реализуется посредством таких же таблиц, что и прямой симплекс-метод. Сначала определяется, какая переменная должна быть выведена из базиса, а затем — какая должпа быть введена в базис. Двойствеппый симплекс-метод для задачи минимизации состоит из следующих шагов.
О. Пачать с таблицы, в которой аьв ) 0 для 1 =- 1, ..., л. 1. Если Ьг = агв )~ 0 для всех 1 = 1,..., т, то задача решена. В противном случае выбрать Ь„(0; переменная х„должна стать пебазисной переменной. Пусть шах — з = — ' (а„; ( 0) или ш! и ! — ~ ! = ~ — ' ! (а„, ( 0) а,~ а„ !а,. ! !а,.~ (условие двойственной допустимости аш = ет = е; — маг >~0 должно сохраниться). 2. Ведущий элемент а„, с помощью метода исключения дол кен быть сделап равным +1. (Все элементы в э-м столбце, кроме а„„ становятся нулевыми.) Заметим, что в роли ведущего элемента могут высту ать только отрицательные элементы. Шаги 1 и 2 повторяются до тех пор, пока среди Ь, не найдется ни одного строго отрицательного (Ь~ 0). Решим следующий пример двойственным симнлекс-методом: минимиаировать з = — 1 + Зхг+ бхв при условиях х,— Зхз — х,= — 4, хе+ х, +хе = 3, х~ > 0 (1 = 1, 2, 3, 4).
Система представляет собой диагопальнуьо форму относительно хь и хз. Представив условия задачи в виде обычной симплекспой таблицы, получим табл. 4.1. Заметим, что а„; ~ )0 (1 = — 1, ..., 4), следовательно, табл. 4.1 двойственно допустима. В ее левом столбце имеется элемент аг, -= — 4 ( О, т. е. таблица не является прямо допустимой. Выберем переменную х~ для вывода из базиса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
