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

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

(54)

при условиях

(55)

(56)

где

и среди чисел имеются отрицательные.

В данном случае есть решение системы линейных уравнений (55). Однако это решение не является планом задачи (54) - (56), так как среди его компонент имеются отрицательные числа.

Поскольку векторы — единичные, каждый из векторов можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов по векторам служат числа Таким образом, можно найти

Определение 1.13. Решение системы линейных уравнений (55), определяемое базисом , называется псевдопланом задачи (54) - (56), если для любого

Теорема 1.13. Если в псевдоплане , определяемом базисом , есть хотя бы одно отрицательное число такое, что все , то задача (54) - (56) вообще не имеет планов.

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

Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода.

Итак, продолжим рассмотрение задачи (54) - (56). Пусть — псевдоплан этой задачи. На основе исходных данных составляют симплекс-таблицу (табл. 15), в которой некоторые элементы столбца вектора являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (54) - (56), поскольку, по предположению, все . Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс-таблицы к другой до тех пор, пока из столбца вектора не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)-й строки, т.е. для любого

Таким образом, после составления симплекс-таблицы проверяют, имеются ли в столбце вектора отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое-нибудь одно из них: пусть это число b_l. Выбор этого числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор P_l. Чтобы определить, какой вектор следует ввести в базис, находим , где

Пусть это минимальное значение принимается при , тогда в базис вводят вектор Р_r. Число является разрешающим элементов. Переход к новой симплекс-таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р₀ не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i-й строке симплекс-таблицы (табл. 15) в столбце вектора Р₀ стоит отрицательное число b_i,а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

Таким образом, отыскание решения задачи (54) - (56) двойственным симплекс-методом включает следующие этапы:

1. Находят псевдоплан задачи.

2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р₀ и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)-и строки к соответствующим отрицательным элементам разрешающей строки.

4. Находят новый псевдоплан и повторяют все действия, начиная с этапа 2.

Таблица 15

i

Базис

Cб

P0

c1

c2

…

ce

…

cm

cm+1

…

cr

…

cn

P1

Р2

…

Рe

Рm

Рm+1

Рr

Рn

1.16. Найти максимальное значение функции при условиях

Решение. Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях

Умножим второе и третье уравнения системы ограничении последней задачи на -1 и переходим к следующей задаче: найти максимум функции

(57)

при условиях

(58)

(59)

Составим для последней задачи двойственную. Такой является задача, в результате решения которой требуется найти минимальное значение функции

(60)

при условиях

(61)

(62)

Выбрав в качестве базиса векторы и , составим симплексную таблицу (табл. 16) для исходной задачи (57) - (59).

Таблица 16

Из этой таблицы видим, что планом двойственной задачи (57) - (59) является . При этом плане Так как в столбце вектора Р₀ таблица 16 имеются два отрицательных числа (-4 и -6), а в 4-й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс-метода переходим к новой симплекс-таблице. (В данном случае это можно сделать, так как в строках векторов Р₄и Р₅ имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима.) Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р₀. В данном случае это число -6. Следовательно, из базиса исключаем вектор Р₅. Чтобы определить, какой вектор необходимо ввести в базис, находим где Имеем

Значит, в базис вводим вектор P₂. Переходим к новой симплекс-таблице (табл. 17).

Таблица 17

Из этой таблицы видно, что получен новый план двойственной задачи При этом плане значение ее линейной формы равно Таким образом, с помощью алгоритма двойственного симплекс-метода произведен упорядоченный переход от одного плана двойственной задачи к другому.

Так как в столбце вектора Р₀ таблицы 17 стоит отрицательное число -7, то рассмотрим элементы 2-й строки. Среди этих чисел есть одно отрицательное -3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случая переходим к новой симплекс-таблице (табл. 18).

Таблица 18

Как видно из таблицы 18, найдены оптимальные планы исходной и двойственной задач. Ими являются и . При этих планах значения линейных форм исходной и двойственной задач равны:

1.17. Найти максимальное значение функции при условиях

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

Взяв в качестве базиса векторы Р₃, Р₄ и Р₅, составляем симплекс-таблицу (табл. 19).

Таблица 19

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

Таблица 20

Так как в строке вектора Р₃ нет отрицательных чисел, то исходная задача не имеет решения.