20. Свойства симметричных взаимно-двойственных злп

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

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

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

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

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

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

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

21. Алгоритм составления симметричной двойственной злп

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

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

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

23. Следствия из основного неравенства теории двойственности

Если X* = (, ,…, ) и Y*=(, ,…, ) – допустимые решения взаимно двойственных задач, для к-ых выполняется равенство F(X*) = Z(Y*), то Х*- оптимал. решение исходной задачи, а Y*- двойственной задачи.

24. 1 Теорема двойственности и ее экономический смысл

Если одна из взаимно двойственных задач имеет оптимал. решение, то его имеет и другая, причем оптимал. значения их линейных функций равны: F max = Z min или F(X*) = Z(Y*). Если линейная функция одной из задач не ограничена, то условия др. задачи противоречивы. Эконом. смысл : План производства X*=(x1*,x2*,…,xn*) и набор оценок ресурсов Y*=(y1*,y2*,…,ym*) оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции по внешним ценам c1,c2,…,cn, равна затратам на ресурсы по внутренним ценам ,,…,.

25. Теорема о соответствии компонент решений взаимно-двойственных злп

Положительным (ненулевым) компонентам оптимально­го решения одной из взаимно двойственных задач соответствуют нулевые (свободные) компоненты оптимального решения другой задачи.

> 0  = 0; > 0  = 0

>0  =0; > 0  = 0

26. II теорема двойственности. Экономический смысл компонент взаимно- двойственных злп

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