Eng | Rus | Ukr | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Исследование операций
|
04.10.2008
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2.6. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОДИспользование идей двойственности в сочетании с общей идеей симплекс-метода позволило разработать еще один метод решения задач ЛП - двойственный симплекс-метод. Впервые этот метод был предложен Лемке в 1954г. Решение задачи ЛП двойственным симплекс-методом сводится к отысканию оптимального плана прямой задачи последовательным переходом от одного базиса к другому. Задача ЛП в канонической форме имеет вид: максимизировать L(x) = (2.6.1) при условиях ( ) (2.6.2) или , j = . Предположим, что n m и ранг матрицы А равен m. Двойственная задача к задаче (2.6.1), (2.6.2) записывается так: минимизировать (2.6.3) при условиях , , . (2.6.4) Назовем сопряженным базисом, или базисом двойственной задачи такую систему из m линейно-независимых векторов матрицы ограничений прямой задачи , для которой базисное решение y соответствующей системы линейных уравнений вида , i есть (2.6.5) удовлетворяет всем ограничением (2.6.4). Разложим вектор b по сопряженному базису . (2.6.6) Решив систему (2.6.6), получим некоторое ее базисное решение { } iÎ , которое называется псевдопланом прямой задачи, так как для него может выполняться условие неотрицательности переменных . Таким образом, псевдоплан прямой задачи есть базисное решение относительно сопряженного базиса. Как известно, оценки для небазисных векторов определяется в соответствии с = , j = . (2.6.7) Псевдоплан можно найти и независимо от двойственной задачи. Пусть { } i Î - произвольная система линейно-независимых векторов прямой задачи. Выразим все небазисные векторы { } через базисные: , (2.6.8) . (2.6.9) Обозначим решение (2.6.9) через х0. Тогда можно дать дополнительное определение псевдоплана: n-мерный вектор , для которого = при iÎ , и = 0 при j Iб, является псевдопланом тогда и только тогда, когда все 0, j = . Доказательство. Векторы { } i Î Iб, линейно независимы. Поэтому можно вычислить такой y ={ }, для которого , i Î Iб (2.6.10) Тогда
С учетом (2.6.4) получим , (2.6.11) что и требовалось доказать. Рассмотрим некоторый сопряженный базис и соответствующий ему псевдоплан. Справедлив следующий признак оптимальности: если среди базисных компонентов псевдоплана Х нет отрицательных, то псевдоплан Х={ } оказывается оптимальным решением прямой задачи. Доведение. Имеет место такая цепочка равенств: . Равенство (1) следует из (2.6.2), равенство (2) получено переменой порядка суммирования, равенство (3) следует из (2.6.10). Так как хj = 0 при j ¹ Iб (2.6.12) то (2.6.13) Таким образом, , что и является признаком оптимальности планов х и у, если х 0 (теорема 2.5). Этот признак является необходимым и достаточным условием оптимальности в случае невыродженности базисного решения двойственной задачи (18). Пусть известен некоторый сопряженный базис {Ai}, и Iб которому соответствует псевдоплан х. Очевидно, Аj = , А0 = . При этом в зависимости от знаков {xi} и {xij} может иметь место один из трех случаев: 1) базисные компоненти хi = хi0 0 для всех i Iб; 2) среди хi имеются отрицательные, причем для некоторого i: хi0<0, а все хij 0 j = 1, ., n; 3) псевдоплан содержит отрицательные компоненты хi0<0, но для каждой из них среди элементов {хij}, j = 1, ., n , имеются отрицательные. В первом случае, как следует из достаточного признака оптимальности, псевдоплан х - оптимальное решение. Во втором случае задача не разрешима. В третьем случае можно перейти к некоторому новому сопряженному базису и, следовательно, к новому псевдоплану с меньшим значением L. Итак, последовательные переходы от одного сопряженного базиса к другому производят до тех пор , пока не получат решение задачи или не установят ее неразрешимость. Каждый переход от одного псевдоплана к другому составляет одну итерацию (один шаг) двойственного симплекс-метода. Каждая итерация содержит два этапа. На первом этапе выясняют, не является ли псевдоплан оптимальным планом прямой задачи, и если нет, то разрешима ли задача. Для этого необходимо вычислить { }, i Iб и установить их знаки. Второй этап состоит в осуществлении элементарного преобразования - (одной итерации) метода полного исключения Жордана-Гауса, приводящего к новому псевдоплану с меньшим значением целевой функции. Описание алгоритма. Задача ЛП должна быть задана в канонической форме (2.6.1), (2.6.2) или сведена к ней. Отыскивают сопряженный базис двойственной задачи и обозначают его {Ai}, i Iб . Разложим А0 по векторам базиса Аі1, . ,Аіm в соответствии с (2.6.9) и найдем псевдоплан {хi0}, i Iб прямой задачи. Исследуем знаки {хi0}. Если имеет место случай хi0 0, i Iб , то начальный псевдоплан является оптимальным планом прямой задачи. При наличии отрицательных компонент {хi0} вычисляем коэффициенты разложения векторов Aj по векторами сопряженного базиса {хij} в соответствии с (2.6.8). Если для некоторого r такого, что хr0<0, все хrj 0 то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается. Если имеет место третий случай (то есть для каждого r такого, что хr0<0, по крайней мере одна из компонент хrj<0), то переходим к второму этапу. С этой целью составляют таблицу k-й итерации (аналогичную симплекс-таблице), которая состоит (m + 2) строк и (n+1)-го столбца(табл. 2.24). Столбец Вх таблицы, как обычно, содержит векторы {Ai} базиса псевдоплана хk, а столбец А0 - базисные компоненти псевдоплана{хi0(k) }. Строка (m + 1)-индексная, ее заполняют параметрами , являющимися оценками векторов Аj: , величина - значение целевой функции при псевдоплане . Итерацию k завершают заполнением главной части таблицы (от первой до (m + 1)-й строк). Таблица 2.24.
На первом этапе (k + 1)-и итерации выясняют, имеет ли место первый, второй или третий случай. В третьем случае переходим ко второму этапу. Сначала определяют вектор Аr, который необходимо вывести из базиса. Его индекс r определяют из условия хr0= , (2.6.14) т.е. по максимальной по модулю отрицательной компоненте базисного решения. Затем заполняют элементы { } (m + 2)-й строки, которые вычисляют по формуле ={ }. (2.6.15) В строке заполняют лишь те позиции, для которых xrj<0. Вектор Аl , который должен быть введен в базис, находят из условия . Определив направляющую строку r и столбец l, вычисляют элементы главной части таблицы (k + 1)-й итерации по рекуррентным соотношениям (2.6.16) где - направляющий элемент преобразования. Вычислительная схема алгоритма двойственного симплекс метода похожа на вычислительную схему симплекс-метода. Аналогичны и формы таблиц. Различие между методами заключается в том, что при симплекс-методе производят последовательный переход от одного допустимого базисного решения (опорного плана) задачи к другому, а при двойственном симплеск-методе - переход от одного псевдоплана к другому. Формальное различие между вычислительными схемами этих методов проявляется только в правилах перехода от одного базиса к другому, а также в признаках оптимальности и неразрешимости задачи. В симплекс-методе сначала определяют вектор, вводимый в базис, а затем - вектор,исключаемый из базиса, а в двойственном симплекс-методе этот порядок - обратный. Отметим некоторые важные свойства двойственного симплекс-метода. В отличие от прямого симплекс-метода, двойственный симплекс-метод не требует нахождения начального базисного решения (опорного плана), а поиск начального псевдоплана часто может оказаться легче, чем поиск ДБР. Рассмотрим, например, типичную задачу минимизаци (2.6.17) при условиях , и = , (2.6.18) , (2.6.19) . (2.6.20) Для задачи такого вида найти сразу начальный опорный план нельзя, и поэтому необходимо применить метод искусственных переменных и выполнить значительный объем вычислений. В то же время псевдоплан находится почти автоматически. Действительно, перейдем от (2.6.17) - (2.6.19) к эквивалентной задаче в расширенной форме, введя свободные переменные xn+1, xn+2, . , xn+m... максимизировать (2.6.21) при условиях . (2.6.22) Запишем ограничения двойственной задачи j =, (2.6.23) i =. (2.6.24) Из неравенств (2.6.23) - (2.6.24) видим, что поскольку решение при i=1,m удовлетворяет всем ограничениям (2.6.23), то сопряженный базис образуют векторы при свободных переменных. При этом начальный псевдоплан такой: , i = . Итак, для задачи вида (2.6.17) - (2.6.18) пpи условии (2.6.20) применение двойственного симплес-метода оказывается предпочтительнее в сравнении с прямым. Двойственный симплекс-метод позволяет в процессе итерации добавлять новые дополнительные ограничения к уже найденному некоторому промежуточному решению. Это важное его свойство широко используется при решении задач целочисленного программирования. Пример 2.9. Решить задачу линейного программирования двойственным симплекс-методом. максимизировать (x1+x2) при ограничениях 2 x1 + 11 x2£38, x1 + x2£7, 4 x1 - 5 x2 £5, x1, x2 ³0, или в расширенной форме 2 x1 + 11 x2 + 1 x3 + 0 x4 + 0 x5 = 38, 1 x1 + 1 x2 + 0 x3 + 1 x4 + 0 x5 = 7, 4 x1 - 5 x2 + 0 x3 + 0 x4 + 1 x5 = 5, x1, . , x5 ³0... Двойственная задача записывается так: минимизировать ( ) при ограничениях
Выберем в качестве сопряженного базиса векторы {A1, A3, A5}. Тогда решением системы линейных уравнений
является Подставив это решение в ограничения{A2} и {A4}, замечаем, что они также удовлетворяются, а потому {A1, A3, A5} - сопряженный базис двойственной задачи. Находим псевдоплан X0 прямой задачи. Для этого решим систему уравнений Вычисляем коэффициенты разложения { хij } A2 = A1х12 + A3х32 + A5х52
и находим х12 = 1; х32 = 9; х52 = -9. Аналогично имеем A4 = A1х14 + A3х34 + A5х54 Решение этой системы уравнений: х14 = 1; х34 = -2; х54 = -4. Таблица. 2.25.
Первая итерация. Определяем направляющую строку. Это строка X5, так как X50 = -23 < 0. Находим направляющий столбец, для чего заполняем строку . Направляющая строка А2, так как . Следовательно, направляющий элемент Х52 = -9. Выполнив первую итерацию симплекс-метода, получим таблицу 2.26. Таблица 2.26.
Так как все элементы столбца А0 хі0 ³ 0, "и Î Іб, то найден оптимальный план, причем Целевая функция Lmax = 7. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Copyright © 2002-2004 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||