ИсследОпераций

§ 2. Несимметричные двойственные задачи

Пусть дана произвольная ЗЛП. Для того, чтобы построить двойственную ей задачу, можно преобразовать данную ЗЛП к стандартной форме, а затем записать задачу, двойственную к полученной стандартной. Однако было бы нерационально повторять подобные преобразования всякий раз для построения двойственной ЗЛП. Проделав эти выкладки в общем виде, можно получить общие правила для составления задачи, двойственной к произвольной ЗЛП. Эти правила, характеризующие особенности любых взаимно двойственных ЗЛП, формулируются следующим образом:

1)одна из взаимно двойственных ЗЛП является задачей минимизации, другая – задачей максимизации;

2)число переменных в одной задаче равно числу ограничений в другой;

3)в задаче минимизации все ограничения-неравенства имеют знак , а в задаче максимизации – знак ;

4)каждому ограничению-неравенству в одной из задач соответствует неотрицательная переменная в другой;

5)каждому ограничению-равенству в одной задаче в другой соответствует переменная произвольного знака;

6)матрицы систем ограничений обеих задач получаются друг из друга транспонированием;

7)свободные члены ограничений одной задачи являются коэффициентами целевой функции другой.

З а м е ч а н и е 1. Компоненты (ограничения и переменные) несимметричных взаимно двойственных задач, соответствие между которыми установлено правилами 4 и 5, принято располагать при записи этих задач в одной строке и называть сопряженными условиями.

З а м е ч а н и е 2. В записи взаимно двойственных ЗЛП для обозначения переменных произвольного знака будем использовать квантор всеобщности – .

Пример 1. Составить двойственные задачи для следующих ЗЛП

Р е ш е н и е. а) Согласно сформулированным семи правилам записываем двойственную к данной канонической ЗЛП задачу

83

б) Исходная ЗЛП является задачей максимизации и, согласно правилу 2, все ее ограничения-неравенства должны быть типа . Поэтому сначала умножим на 1 обе части первого ограничения данной ЗЛП, а затем, руководствуясь об-

щими правилами, записываем двойственную задачу

§ 3. Основные свойства взаимно двойственных задач

Рассмотрим теперь, ограничиваясь формулировками, некоторые основные результаты теории двойственности, имеющие фундаментальное значение в линейном программировании и его приложениях.

Пусть дана пара взаимно двойственных задач:

Теорема 3.1. (Основное неравенство двойственности) Значение целевой функции задачи максимизации для любого ее плана не превосходит значения целевой функции двойственной к ней задачей минимизации для любого ее плана, т.е. для любых планов x D, y D1 выполняется неравенство z x z1 y .

Теорема 3.2. (Основная теорема двойственности) Если одна из взаимно двойственных задач имеет решение, то имеет решение и другая, причем значения целевых функций для оптимальных планов обеих задач совпадают. Если же одна из задач (3.1) неограничена, то другая недопустима.

84

Теорема 3.3. Если каждая из пары взаимно двойственных задач имеет хотя бы по одному плану, то обе задачи имеют оптимальные решения.

Теорема 3.4. Для того чтобы некоторые планы x и y взаимно двойствен-

ных задач (3.1) были оптимальными, необходимо и достаточно чтобы значения целевых функций для этих планов были равны.

В заключение отметим, что при рассмотрении пары взаимно двойственных задач (3.1) могут представиться следующие три возможности:

1)обе задачи обладают планами и в этом (и только в этом) случае имеют оптимальные решения;

2)одна из задач обладает планами, а другая не обладает. Тогда (и только тогда) задача с непустым допустимым множеством неограничена.

3)Обе задачи планов не имеют.

§ 4. Критерии оптимальности планов взаимно двойственных задач

При рассмотрении ЗЛП часто удается определить каким-либо способом некоторый план данной задачи, и тогда возникает вопрос, является ли этот план оптимальным. В этом параграфе приведены формулировки двух критериев оптимальности, установленных Л.В. Канторовичем.

Теорема 4.1. (Критерий Канторовича для одного плана) Для того чтобы план x0 данной ЗЛП был оптимальным, необходимо и достаточно, чтобы суще-

ствовал план y0 двойственной задачи, такой что при подстановке этих планов в

соответствующие системы ограничений всякому строгому неравенству в условиях данной ЗЛП соответствовало бы равенство в сопряженном условии двойственной задачи.

Теорема 4.2. (Критерий Канторовича для двух планов) Пусть задано по плану x0 и y0 у каждой из взаимно двойственных задач. Для того чтобы эти

планы были оптимальными, необходимо и достаточно, чтобы при подстановке их в соответствующие системы ограничений в каждой паре сопряженных условий строгому неравенству в ограничениях одной задачи соответствовало бы равенство в ограничениях другой.

Следствием теорем 3.2 и 4.2 является то, что, встретившись с ЗЛП, мы вольны выбирать, решать ли задачу в том виде, в котором она поставлена, или, решив двойственную задачу, найти решение исходной ЗЛП. Таким образом можно сильно сэкономить объем вычислений, который для ЗЛП связан скорее с количеством ограничений, чем с количеством переменных.

85

Пример 1. Исследовать на оптимальность план x0 2, 2, 0 задачи min 2x1 x2 3x3 ,

x1 2x2 x3 6,x1 x2 2x3 1,

2x1 x2 x3 2.

Подставим во все ограничения-неравенства и условия неотрицательности переменных исходной ЗЛП заданный план x0 . Ограничения, обращающиеся при

этом в равенства, пометим знаком = , а обращающиеся в строгие неравенства – знаком >.

Если заданный план x0 оптимален, то по теореме 4.1 у двойственной ЗЛП должен существовать план y0 y1, y2, y3 , для которого

Кроме того, так как y0 план двойственной задачи, его компоненты удовлетворяют ограничению-равенству

Решая систему (4.1), (4.2), находим вектор y0 4 / 5; 0; 3 / 5 .

Проверим, является ли найденный вектор y0 планом двойственной ЗЛП. Подставляя компоненты вектора y0 во все ограничения двойственной задачи, видим, что нарушено условие y3 0 . Таким образом, плана y0 , удовлетворяющего

86

Так как двойственная ЗЛП имеет решение, то по основной теореме двойственности имеет решение и исходная задача. Обозначим xопт x1, x2, x3 – оп-

тимальный план исходной ЗЛП. Подставив во все ограничения-неравенства двой-

Решая система (4.3), находим xопт 0, 4, 7 .

Итак, для рассмотренной пары взаимно двойственных задач xопт 0, 4, 7 ,

y 4, 4 , z z 16 .

опт min max

§ 5. Двойственный симплекс-метод

Двойственный симплекс-метод, как и симплекс-метод, используется для решения канонической ЗЛП, система ограничений которой является системой с единичным базисом. Различие лишь в том, что свободные члены ограничений задачи, решаемой двойственным симплекс-методом, могут быть любыми числами (при применении симплекс-метода эти числа неотрицательны). Оба этих метода заключаются в последовательном переходе от одного опорного решения системы ограничений к другому, так, что через конечное число переходов либо получается оптимальное решение рассматриваемой ЗЛП, либо устанавливается ее неразрешимость. Однако, в отличие от симплекс-метода эти последовательно получаемые опорные решения не обязательно удовлетворяют условиям неотрицательности переменных решаемой задачи.

Определение. Пусть дана каноническая ЗЛП, система ограничений которой является системой с единичным базисом. Основное опорное решение системы ограничений будем называть псевдопланом, если оценки всех переменных данной ЗЛП неположительны.

Пример 1. Является ли псевдопланом основное решение системы ограни-

Р е ш е н и е. Для ответа на поставленный вопрос нужно найти оценки всех переменных данной ЗЛП. Составим первую симплексную таблицу

88

Рассматривая индексную строку полученной таблицы, убеждаемся, что k 0 , k 1, 4 . Следовательно, основное опорное решение xосн 0, 2, 1, 0 – псевдо-

план.

З а м е ч а н и е. Нетрудно видеть, что если все компоненты псевдоплана неотрицательны, то этот псевдоплан является оптимальным решением рассматриваемой канонической ЗЛП.

Рассмотрим теперь алгоритм двойственного симплекс-метода.

Пусть дана каноническая ЗЛП, у которой система ограничений представляет собой систему с единичным базисом, а основное опорное решение является псевдопланом. Двойственный симплекс-метод решения такой задачи состоит из следующих этапов:

1.Составление первой симплексной таблицы.

2.Проверка псевдоплана на оптимальность.

Если все компоненты псевдоплана (его ненулевые компоненты содержатся в столбце B симплексной таблицы) неотрицательны, то этот псевдоплан является оптимальным планом данной ЗЛП.

3. Проверка задачи на допустимость.

Если в столбце B симплексной таблицы содержится отрицательное число такое, что в той же строке нет больше ни одного отрицательного элемента, то данная ЗЛП является недопустимой и не имеет решения.

4. Улучшение псевдоплана.

Если условия пунктов 2 и 3 данного алгоритма не выполнены, то переходим к новой симплексной таблице, соответствующей равносильной системе ограничений с другим набором базисных переменных и новым псевдопланом. Для этого:

а) выбираем переменную, выводимую из числа базисных. Это переменная,

встроке которой содержится наибольший по абсолютной величине отрицательный элемент столбца свободных членов;

б) выбираем переменную, вводимую в число базисных. Для этого выделяем

ввыбранной строке все отрицательные коэффициенты системы ограничений и для каждого из них ищем частное от деления соответствующей оценки на этот коэффициент. Столбец, в котором получено наименьшее из вычисленных значений (ключевое отношение), соответствует переменной, вводимой в число базисных;

89

в) выполняя жорданово исключение с ведущим элементом, расположенным на пересечении выбранных строки и столбца, переходим к новой симплексной таблице и повторяем все действия, начиная с этапа 2 данного алгоритма.

Пример 2. Решить ЗЛП

min z 2x1 2x2 x3,

Р е ш е н и е. Поскольку система ограничений данной канонической ЗЛП является системой с единичным базисом, мы можем составить первую симплексную таблицу (табл. 7).

Таблица 7

Оценки, расположенные в индексной строке табл. 7, неположительны. Следовательно, основное опорное решение xосн 0, 0, 8, 1, 6 является псевдопланом

и для решения данной ЗЛП можно применить двойственный симплекс-метод. Так как в столбце B табл. 7 имеются два отрицательных числа ( 1 и 6 ) и

в соответствующих им строках содержатся отрицательные элементы, то в соответствии с алгоритмом двойственного симплекс-метода переходим к новой симплексной таблице. Переменная, исключаемая из числа базисных, определяется наибольшим по модулю отрицательным числом из столбца B . В данном случае это число 6 . Следовательно, из числа базисных исключаем переменную x5 . Что-

бы определить переменную, вводимую в число базисных, находим ключевое от-

ношение для строки переменной x5 . Это отношение 1 / 2 12 достигается в

столбце переменной x2 . Значит, переменную x2 вводим в число базисных. Вы-

полняя жорданово исключение, переходим к новой симплексной таблице (табл. 8).

90

Таблица 8

Так как в столбце B таблице 8 нет отрицательных чисел, задача решена:

В рассмотренном примере 2 использование двойственного симплексметода позволило избежать применения искусственных переменных. В общем же случае для решения канонической ЗЛП двойственным симплекс-методом необходимо сначала при помощи специальных методов преобразовать систему ограничений к виду, определяющему один из псевдопланов данной задачи. Однако, имеется целый ряд стандартных ситуаций, в которых для применения двойственного симплекс-метода не требуется никаких предварительных преобразований. Так особенно удобен двойственный симплекс-метод при введении дополнительных ограничений в уже решенной задаче.

91

ГЛАВА 5. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

§ 1. Методы отсечения

x 0.

Потребуем дополнительно, чтобы переменные xi принимали только целочисленные значения, т.е.

Задачу (5.1) с дополнительным условием (5.2) называют задачей линейного целочисленного программирования.

З а м е ч а н и е. Требование целочисленности (5.2) может быть наложено лишь только на некоторые переменные задачи (5.1). Соответственно будем различать полностью и частично целочисленные ЗЛП.

Введем понятие правильного отсечения, которое лежит в основе многих численных методов решения целочисленных ЗЛП, называемых методами отсечения.

Определение. Пусть x – оптимальный план задачи (5.1) (без условия целочисленности переменных), не являющийся целочисленным. Неравенство

k 1

называется правильным отсечением, если оно удовлетворяет требованиям:

а) для вектора x неравенство (5.3) не выполняется;

б) любой целочисленный план задачи (5.1) удовлетворяет этому неравен-

ству.

Понятно, что добавление неравенства (5.3) к системе ограничений задачи (5.1) сужает ее допустимое множество, сохраняя при этом все его целочисленные точки.

Идея методов отсечения состоит в следующем.

На первом этапе решается ЗЛП, получающаяся из данной целочисленной задачи отбрасыванием требования целочисленности переменных. Если найденное

решение x1 целочисленно, то оно является решением исходной целочисленной задачи. Если нет, то к системе ограничений ЗЛП, решаемой на первом этапе, добавляется правильное отсечение, которое «отсекает» точку x1 и сохраняет в допустимом множестве все целочисленные планы исходной задачи.

92