Метод искусственного базиса. L - функция. L – задача

Метод искусственного базиса заключается в следующем: в каждое уравнение, дающее отрицат. компоненту в базисном решении, вводим свою новую неотрицат. искусственную переменную u1, u2,…, , которая имеет тот же знак, что и свободной член в правой части уравнения. В первой таблице включаем в число основных все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицат. компоненты базисного решения. Составляем новую линейную функцию (L – функцию)¸ где L-произвольно большое число, и ищем ее минимум (L-задача). L – функция выражение вида L(u1+u2+…+ ).

Теорема о L-функции и следствие из нее

Если в оптимал. решении L-задачи все искусствен. переменные равны 0 (т.е. вышли из базиса), то значения оставшихся переменных дают опорные базисные решения исходной задачи. Если в оптимал. решении

L-задачи хотя бы одна искусствен. переменная не равна 0, то исходная задача реш-я не имеет, т.к. СО будет противоречивой. Если Lmax= , то исходная задача также неразрешима, причем либо Zmax= , либо условия задачи противоречивы.

Формулировка симметричных взаимно-двойственных ЗЛП

Задача I (исходная)

Задача II (двойственная)

F=c1x1+c2x 2+...+cnxn max при ограничениях: a11x1 + a12x2+...+ a1nxn b1 a21x1 + a22x2+...+ a 2nxn ≤ b2 am1x1 + am2x2+...+ amnxn ≤ bm и условии неотрицательности x1 ≥0; x2 0,…, xn 0 Составить такой план выпуска продукции Х = (х1, х2, ..., хn), при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

Z=b1y1+b2y2+...+bm ym min при ограничениях: a11у1 + a21у2+...+ am1уm c1 a12у1 + a22у2+...+ am2уm ≥c2 a1nу1 + a2nу2+...+ amnуm ≥ cn и условии неотрицательности y1 0; y2 0,…, ym 0 Найти такой набор цен ресурсов Y = (у1, y2, ..., уm), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли от реализации этой продукции.

Свойства симметричных взаимно-двойственных ЗЛП

Симметричные взаимно-двойственные ЗЛП обладают следующими свой­ствами:

1.В одной задаче ищут максимум линейной функции, в другой – минимум.

2.Коэффициенты при переменных в линейной функции одной за­дачи являются свободными членами системы ограничений в другой.

3.Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида " ", а в задаче минимизации – все неравенства вида "≥".

4.Матрицы коэффициентов при переменных в системах ограни­чений обеих задач являются транспонированными друг к другу.

5.Число неравенств в системе ограничений одной задачи совпа­дает с числом переменных в другой задаче.

6.Условия неотрицательности переменных сохраняются в обеих за­дачах.

Алгоритм составления симметричной двойственной ЗЛП

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду " ", а если минимум - к виду "≥". Для этого неравенства, в которых данное требование не выполняется, умножить на -1.
2. Составить расширенную матрицу системы А₁ в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.
3. Найти матрицу А'₁, транспонированную к матрице А₁.
4. Сформулировать двойственную задачу на основании полученной матрицы A'₁ и условия неотрицательности переменных.

Основное неравенство теории двойственности

Для любых допустимых решений Х= (х1, х2,…, хn) и Y= (y1, y2,..., ym) исходной и двойственной задач справедливо неравенство Z(X) ≤ F(Y), т.е. Прибыль от реализации продукции не превосходит прибыли от реализации сырья. Док-во: Z(x) = ( ) = ( ) = F(y) Z(X) ≤ F(Y),