4.1.2 Связь между прямой и двойственной задачами

Лемма1

Если х - некоторый план прямой задачи, а y - некоторый произвольный план ДЗ, то значение целевой функции прямой задачи при плане х всегда не превосходит значение целевой функции двойственной задачи при плане у.

Y(x)<=S(y)

Лемма 2

Если Y(x*)<=S(y*), то х*- оптимальный план прямой задачи,

                                    y*- оптимальный план двойственной задачи.

Теорема 1

(1-я теорема двойственности)

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

Y_max=S_min

Если же целевая функция одной из пары двойственных задач не ограничена, то другая задача вообще не имеет планов.

Теорема 2

(2-я теорема двойственности)

План X*=(x₁*…x_n*) – исходная задача

План Y*=(y₁*…y_m*) – двойственная задача

Являются оптимальными планами этих задач тогда и только тогда, когда для любого j=[1,n] выполняется равенство:

(a_ij*y_i*-c_j)x_j*=0

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

Алгоритм симплекс-метода:

1. Выражение целевой функции через небазисные переменные.

2. Проверка базисного решения на оптимальность. Если в полученном выражении целевой функции все коэффициенты при небазисных переменных неотрицательны, то исходный базис является оптимальным и находится соответствующее базисное решение, оптимизирующее целевую функцию. Для этого всем небазисным переменным присваивается 0, а значение базисных переменных находится из системы ограничений. После чего задача считается завершенной. Если в полученном выражении целевой функции хотя бы один коэффициент при небазисных переменных отрицательный, переходят к следующему этапу.

3. Проверка задачи на наличие решения.

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

4. Выбор из небазисных переменных той, которая способна при введении ее в базис увеличить значение её целевой функции. Наиболее простой и чаще всего применяемый способ состоит в выборе небазисной переменной, которой соответствует наибольший отрицательный коэффициент в целевой функции.

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

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

7. Выражение остальных базисных переменных и целевой функции через новые небазисные переменные.

8. Повторение операций, указанных в пунктах 2-7 до тех пор, пока не будет найдено оптимальное решение.

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

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