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

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

F= с₁х₁ + с₂х₂ +…+ с_пх_п (1)

при условиях

x₁P₁+ x₂P₂+…+ x_mP_m+ x_m+1P_m+1+…+ x₁P₁=P₀ , (2)

xj≥0 (j=1,n) , (3)

где Р₁ ; Р₂ ; …; Р_m ;

= ; …; Р_n= _; Р₀=

и Р_m среди чисел b_i, (i=1,m) имеются отрицательные.

В данном случае Х=( b₁ ;b₂; ...; b_т; 0;...;0) есть решение системы линейных уравнений (1). Однако это решение не является планом задачи, так как среди его компонент имеются отрицательные числа.

Поскольку ректоры Р₁, Р₂,...,Р_т — единичные, каждый из векторов P_j (j=1,n) можно представить в виде линейной комби­нации данных векторов, причем коэффициентами разложения векторов P_j по векторам

P₁, Р₂, ..., Р_т служат числа х_ij=a_ij (i=1,m; j=1,n). Таким образом, можно _m

∆_j =z_j-c_j=∑ c_ia_ij-с_j (j=1,n).

ⁱ⁼¹

Решение Х=( b₁ ;b₂; ...; b_т; 0;...;0) системы линейных уравнений (1), определяемое базисом Р₁, Р₂,...,Р_т, называется псевдопланомзадачи (1) — (3), если ∆_j≥0 для любого j (j=1,n).

Теорема 1. Если в псевдоплане Х=( b₁ ;b₂; ...; b_т; 0;...;0), определяемом базисом Р₁, Р₂,...,Р_т, есть хотя бы_одно отрица­тельное число bi<0 такое, что все a_ij ≥ 0 (j=1,n),то задача (1) — (3) вообще не имеет планов.

Теорема 2. Если в псевдоплане Х=( b₁ ;b₂; ...; b_т; 0;...;0), определяемом базисом Р₁, Р₂,...,Р_т имеются отрицательные числа bi<0 такие, что для любого из них существуют числа a_ij<0, то можно перейти к новому псевдоплану, при котором зна­чение целевой функции задачи (1) — (3) не уменьшится.

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

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

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

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

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

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

Таблица 2

Контрольные вопросы

1. Перечислить этапы алгоритма двойственного симплексного метода.
2. Каким образом можно судить об оптимальности полученного решения?
3. Когда задача не имеет решения?
4. Как определяется разрешающая строка?
5. Как определяется разрешающий столбец?
6. Дать сравнительную характеристику симплексного метода и двойственного симплексного метода.