Задачи ЛП и методы их решения

109

Пусть матрица A = A[1: m,1: m] имеет обратную A−1 , а матрица S отличается от А только l-м столбцом ( Sl ). Тогда и матрица S имеет обратную, если только отлична от нуля l-я компонента вектора Z = A−1 Sl . При этом S −1 = D A−1 , где матрица D отличается от единичной только l-м столбцом ( D - называется левым мультипликатором)

Доказательство Покажем, что (D A−1 ) S = E

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

Пусть j ≠ l. Тогда (см. схему)

(D A−1 ) S j = (D A−1 ) Aj = D ej = Dj = ej

Таким образом новая матрица A[M , N1' ], столбцы которой соответствуют положительным компонентам решения Xθ [N] имеет обратную, т.е. является базисной, и, следовательно,

базисным является и новое решение ЗЛП Xθ [N]

Согласно лемме для матрицы B[N1' , M ] обратной к новой базисной A[M , N1' ] имеет место соотношение

B[N1' , M ] = D[N1' , N ' ] B[N ' , M ] где B[N ' , M ] - “старая” обратная матрица к базисной.

Рассмотрим основную часть “старой” симплекс-таблицы прямого симплекс-алгоритма (см. в п. 3.3. выделенную часть С-Т на шаге 3 перехода к новому решению) и убедимся, что соответствующая “новая” основная часть С-Т получается из нее преобразованием Гаусса-Жордана с ведущим элементом z[i0 , j0 ] ( i0 - строка С-Т, на которой

определялась θ , j0 - столбец, оценка которого нарушает критерий оптимальности ε[ j0 ] < 0)

Чтобы убедиться в идентичности перехода к новому решению с помощью левого мультипликатора и преобразований Гаусса-Жордана, проведем соответствующие выкладки параллельно (см. схемы на следующей странице).

Для полного обновления С-Т остается в столбце базисных индексов записать N1' вместо N ' (т.е. заменить номер i0 на номер j0) и в столбце коэффициентов целевой функции при

базисных неизвестных заменить C[N ' ] на C[N1' ] (записать c[ j0 ] вместо c[i0 ] ).

111

7.10. Пары двойственных задач. Теоремы двойственности

Рассмотрим ЗЛП в общей форме записи ( M1 , M 2 M , M1 M 2 = M , N1 , N2 N ,

N1 N2 = N )

f (X ) = C[N] X[N] → max

A[M1 , N] X[N] ≤ b[M1 ] A[M 2 , N] X[N] = b[M 2 ]

X[N1 ] ≥ 0[N1 ]

X[N2 ] >< 0[N2 ]

С ней тесно связана некоторая другая ЗЛП, которая носит название ЗЛП двойственной к данной.

g(Y) = Y[M ] b[M ] → min

Y[M ] A[M, N1 ] ≥ C[N1 ]

Y[M ] A[M , N2 ] = C[N2 ]

Y[M1 ] ≥ 0[M1 ]

Y[M 2 ] >< 0[M 2 ]

Построение двойственной задачи сводится к следующей схеме:

1-2Число переменных в двойственной задаче равно числу ограничений в исходной, а число ограничений в двойственной равно числу переменных в исходной.

3 В двойственной задаче меняется вид экстремума (max на min и наоборот).

4 Векторы правой части ( в[M] ) и коэффициентов целевой функции (C[N]) в двойственной задаче меняются местами: первый становится вектором коэффициентов целевой функции, а второй - вектором правой части в системе ограничений.

5Левая часть системы ограничений строится по транспонированной матрице AT [N, M ] (строки в A[M , N] становятся столбцами и наоборот), которая умножается на вектор переменных двойственной задачи Y[M ]

6Знаки в системе ограничений двойственной задачи определяются знаками ограничений неотрицательности в исходной задаче:

- ограничения неотрицательности на переменные X[N1 ] дают нежесткие ограничения с номерами из N1 (типа ≥ для задачи на min и ≤для задачи на max); - отсутствие ограничений неотрицательности на переменные X[N2 ] определяет

жесткие ограничения (равенства) с номерами из N2 . И, наоборот,

- нежесткие ограничения с номерами из M1 дают ограничения неотрицательности на

переменные Y[M1 ];

- жесткие ограничения с номерами из M 2 не накладывают условий неотрицательности на переменные Y[M 2 ](в дальнейшем запись Y >< 0 будем опускать).

hДвусторонние стрелки на схеме показывают, что ее можно применять в обе стороныh