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

Поскольку в индексной строке таблицы 4 имеются положительные оценки, основной опорный план xосн 0, 0, 20, 24, 0,18 , не является оптимальным. По-

этому переходим к новому опорному плану. Это можно сделать, так как в столбцах переменных x1 и x5 , которым соответствуют положительные оценки, имеют-

ся положительные элементы. Для перехода к новому основному опорному плану вводим в число базисных переменную x5 (ей соответствует наибольшая положи-

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

Как видно из таблицы 5 новый основной опорный план не является оптимальным, так как в индексной строке имеется положительная оценка 11 / 3 . Поскольку над этой оценкой нет ни одного положительного элемента, данная ЗЛП не имеет решения, так как ее целевая функция не ограничена снизу на допустимом множестве.

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

min z x1 x2 x3 x4 ,

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

Из последней симплексной таблицы видно, что план x 0,18 / 5, 0, 4 / 5 является оптимальным и ему соответствует zmin 22 / 5 .

73

§ 7. Метод искусственного базиса

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

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

min z c1x1 c2 x2 c3x3,

Будем предполагать, что b1 0, b2 0 (этого всегда можно достигнуть умноже-

нием обеих частей уравнения с отрицательным свободным членом на 1). Задачу (7.1) будем называть основной задачей.

Введем во все ограничения задачи (7.1) базисные переменные. Для этого к левой части каждого уравнения прибавим по одной новой переменной с коэффициентом 1. На эти переменные наложим требование неотрицательности и будем

74

называть их искусственными переменными. При полученной системе ограничения рассмотрим задачу минимизации новой целевой функции S , равной сумме всех искусственных переменных,

Эту каноническую ЗЛП с простейшей системой ограничений принято называть вспомогательной задачей.

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

Д о к а з а т е л ь с т в о. Необходимость. Пусть x o x1o , x2o , x3o – некото-

рый план основной задачи (7.1). Тогда x o x1o , x2o , x3o , 0, 0 будет, очевидно, пла-

ном вспомогательной задачи (7.2), для которого S xo 0 . Но целевая функция S

неотрицательна на всех планах, следовательно, вспомогательная задача имеет решение и Smin 0 .

Достаточность. Пусть вспомогательная задача (7.2) имеет решение и Smin 0 . Тогда в оптимальном плане x этой задачи все искусственные переменные равны нулю, т.е. x x1 , x2 , x3 , 0, 0 , где x1 0 , x2 0 , x3 0 . Но при равных нулю искусственных переменных системы ограничений задач (7.1) и (7.2) совпадают. Поэтому вектор x x1 , x2 , x3 является планом основной задачи

(7.1), т.е. ее допустимое множество не пусто. На практике используются различные модификации метода искусственного

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

Пусть дана произвольная ЗЛП. Ее решение двухфазным симплекс-методом состоит из следующих трех этапов.

I. Построение вспомогательной задачи

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

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

75

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

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

II. Решение вспомогательной задачи

Решая вспомогательную задачу симплекс-методом, найдем наименьшее

значение ее целевой функции Smin . Могут представиться следующие возможности.

а) Smin 0 . Тогда исходная ЗЛП является недопустимой и не имеет реше-

ния.

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

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

III. Решение основной задачи

Заменив систему ограничений исходной канонической ЗЛП найденной простейшей системой, решаем симплекс-методом полученную задачу.

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

За м е ч а н и е 2. Применение двухфазного симплекс-метода приводит к тому, что для решения ЗЛП вначале приходится решать вспомогательную задачу,

азатем основную. Оба этих этапа позволяют объединить другой не рассматриваемый в настоящем пособии вариант метода искусственного базиса, называемый M-методом.

Пример 1. Для задачи

min z 5x1 x2 4x3,

составить вспомогательную задачу.

76

Р е ш е н и е. Рассмотрим систему ограничений данной ЗЛП и, вводя дополнительные переменные x4 и x5 , преобразуем ее к равносильной системе ра-

венств:

Поскольку свободный член второго уравнения отрицателен, изменим знак у обеих частей этого уравнения:

В первом уравнении полученной системы нет базисной переменной, поэтому прибавим к левой части этого уравнения искусственную переменную x6 и запи-

шем искомую вспомогательную задачу

Пример 2. Двухфазным симплекс-методом решить ЗЛП min z 2x1 x2 4x3,

Р е ш е н и е. Вспомогательная задача для данной ЗЛП имеет вид

Решим эту задачу симплекс-методом

77

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

ности ее системы ограничений.

Пример 3. Двухфазным симплекс-методом решить ЗЛП min z 2x1 6x2 5x3 x4 4x5 ,

Р е ш е н и е. Составим для данной ЗЛП вспомогательную задачу

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

78

Smin 0 и среди базисных переменных завершающей симплексной таблицы нет

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

Решаем теперь симплекс-методом исходную ЗЛП, заменив ее систему ограничений на полученную простейшую.

79

В индексной строке последней симплексной таблицы нет положительных оценок, следовательно, x 0, 0,16, 31,14 – оптимальный план исходной ЗЛП, а

z x 7 – наименьшее значение ее целевой функции на допустимом множестве.

80

ГЛАВА 4. ДВОЙСТВЕННОСТЬ

ВЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

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

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

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

Определение. Пусть дана стандартная задача минимизации

Задачей, двойственной к (1.1), будем называть следующую стандартную задачу максимизации

Сравнивая задачи (1.1) и (1.2), отмечаем следующие пять особенностей:

1)одна из задач является задачей минимизации, другая – задачей максими-

зации;

2)в задаче минимизации все неравенства – типа , в задаче максимизации

–типа ;

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

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

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

Построим теперь задачу, двойственную к (1.2). Для этого заменим задачу (1.2) равносильной стандартной задачей минимизации:

и запишем, в соответствии с определением, к ней двойственную:

Учитывая, что AT T A, и умножая на 1 целевую функцию и обе части всех

ограничений, получаем задачу (1.1).

Таким образом, задачи (1.1) и (1.2) являются взаимно двойственными.

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

Пример 1. Для задачи

min 2x1 3x2 4x3 ,

составить двойственную задачу.

Р е ш е н и е. В соответствии с общими правилами сформулируем ЗЛП, двойственную к данной. Обращаем особое внимание на расположение сопряжен-

82