Теорема 3.4.

Если ИЗ разрешима, то разрешима и ДЗ и наоборот, причем

Если ИЗ неразрешима, то ДЗ тоже неразрешима и наоборот.
Пусть ИЗ разрешима и имеет вид основной ЗЛП:

(1)

(2)

(3)

Тогда ДЗ имеет вид (3.12, 3.14):

(4)

(5)

(6)

Предположим, что исходная задача имеет решение, т.е. существует ее оптимальный план x*.

Приведем ИЗ к каноническому виду:

(1´)

(2´)

(3´)

Ее решение может быть получено симплекс – методом, т.к. расширенная матрица системы (2´) имеет вид К -матрицы.
Исходную К - матрицу запишем в виде:

(7)

На S -ой итерации симплекс-метода получим матрицу , которая определяет оптимальный опорный план ИЗ:

, (8)

или в развернутом виде эти матрицы можно представить:

(7´)

(8´)

Вектор задает номера базисных компонент оптимального опорного плана ИЗ:

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

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

Матрица в матрице расположена на месте единичной подматрицы исходной матрицы .
Из (9) следует, что (3.16)

, (3.17)

, (3.18)

т.е. вся необходимая информация может быть получена с помощью матрицы .
Следовательно, можно перебирать не К -матрицы, а только обращенные базисы.

Так как на S-ой итерации получен оптимальный опорный план,

то отвечающие матрице симплекс – разности, являются неотрицательными

(3.19)

Или с учетом (3.17) получим:

(3.20)

Обозначим

(3.21)

Покажем, что вектор является решением двойственной ЗЛП.

Действительно, рассматривая первые n неравенств (3.20) и записывая их в векторно-матричной форме, имеем:

, или с учетом (3.21)

(3.22)

Аналогично, рассматривая неравенства (3.20) для j=n+1, n+m и учитывая, что

получаем

(3.23)

,

или

(3.24)

Из (3.22) и (3.24) следует, что - план двойственной ЗЛП.

Далее, т.к.

(3.25)

то, по теореме 3.3 - решение двойственной ЗЛП.

Пусть ИЗ не имеет решения. Предположим противное, что ДЗ имеет решение, тогда по доказанному в первой части теоремы его имеет и ИЗ. Что противоречит условию теоремы.

Следствие 1.

Из выражения (3.23)

, (3.26)

следует, что i-ая компонента решения двойственной ЗЛП есть (n+i)-я симплекс-разность матрицы , определяющей оптимальный план исходной ЗЛП.

Следствие 2.

Из выражения (3.21) следует, что j-я симплекс-разность матрицы (j=1, n) равна разности между левой и правой частями ограничений двойственной ЗЛП.

(3.27)

Следствие 3.

Из теорем 3.3 и 3.4 следует, что равенство целевых функций ИЗ и ДЗ является необходимым и достаточным условием оптимальности планов обеих задач.