Оптимальное планирование и оптимальные оценки

1. Экономический смысл двойственной задачи линейного программирования.

2. Взаимосвязь прямой и двойственной задач линейного программирования.

3. Свойства двойственных оценок. Их экономическое содержание.

1. Экономический смысл двойственной задачи линейного программирования:

Допустим мы имеем прямую задачу об использовании сырья. Для изготовления двух видов продукции А и В используются s₁, s₂, s₃, s₄ – виды сырья. Необходимо определить план выпуска продукции с целью получения максимального дохода.

Исходные данные о наличии и использовании сырья:

Вид сырья	Нормы расхода сырья		Запас сырья
	А	В
s1 s2 s3 s4	2 2 0 3	3 1 3 0	19 13 15 18
Доход	7	5

Пусть х₁ – количество продукции А, х₂ – продукции В.

Прямая задача: z = 7  x₁ + 5  x₂  max

2  х₁ + 3  х₂  19 | у₁ х₃

2  х₁ + х₂  13 | у₂ х₄

3  x₂  15 | у₃ х₅

3  x₁ + 0  18 | у₄ х₆

x₁, x₂  0

Оценка ресурсов, которые ограничивают выпуск продукции. Формально каждому ограничению ставится в соответствие переменные двойственной задачи.

Правила для построения двойственной задачи:

1. Коэффициенты системы ограничений двойственной задачи есть матрица, полученная путем транспонирования матрицы коэффициентов системы ограничений исходной задачи.

2. Если прямая задача на max, то двойственная на min и наоборот.

3. Неравенства в системе ограничений направлены в противоположную сторону.

4. Коэффициенты целевой функции двойственной задачи есть свободные члены прямой и наоборот (коэффициенты целевой функции двойственной задачи есть свободные члены исходной).

5. Между переменными прямой и двойственной задач есть соответствие: дополнительные переменные прямой соответствуют основным двойственной и наоборот.

6. О чем речь идет в неравенстве, то и оцениваем.

Решив прямую задачу, мы автоматически находим ответ и для двойственной задачи: переменные двойственной задачи равны оценкам соответствующих переменных прямой задачи в оптимальном плане.

Экономический смысл: Решение двойственной задачи дает оптимальную систему условных оценок применяемых ресурсов.

Двойственная задача линейного программирования устанавливает связь между оптимальным распределением ресурсов и некоторой системой оценок на ресурсы.

Н овая задача:

2  у₁ + 2  у₂ + 3  у₄  7

3  у₁ + у₂ + 3  у₃  5,

где у₁, у₂, у₃, у₄  0.

Рассмотрим первое уравнение: 2  у₁ + 2  у₂ + 3  у₄ – оценка всего сырья (затрат), идущего на единицу продукции, а 7 – результат от единицы продукции.

F = 19  у₁ + 13  у₂ + 15  у₃ + 18  у₄  min

Переменные у показывают оценку единицы соответствующего ресурса, показывает как повлияет на конечный результат деятельности (суммарный доход) дополнительная единица соответствующего ресурса. Целевая функция F – оценивает все ресурсы, которыми располагает предприятие.

Основные переменные двойственной задачи соответствуют дополнительным переменным исходной задачи. Основным переменным исходной задачи соответствуют дополнительные переменные двойственной задачи.

х₁ х₂ х₃ х₄ х₅ х₆

у₅ у₆ у₁ у₂ у₃ у₄

Если знаем решение двойственной задача, то решение исходной задачи получаем автоматически.

Переменные двойственной задачи у₁, у₂, у₃, у₄ равны оценкам соответствующих переменных исходной задачи в оптимальном плане.

2. Взаимосвязь прямой и двойственной задач линейного программирования.

2  х₁ + 3  х₂ + х₃ = 19,

2  х₁ + х₂ + х₄ = 13,

3  x₂ + х₅ = 15,

3  x₁ + х₆ = 18.

x₃ = 19, x₄ = 13, х₅ = 15, х₆ = 18.

БП		План	7	5	0	0	0	0
			х1	х2	х3	х4	х5	х6
х3 х4 х5 х6	0 0 0 0	19 13 15 18	2 2 0 3	3 1 3 0	1 0 0 0	0 1 0 0	0 0 1 0	0 0 0 1
∆j			-7	-5	0	0	0	0

… …

х6 х2 х5 х1	0 5 0 7	3 3 6 5	0 0 0 1	0 1 0 0	9/4 2/4 -3/2 -1/4	-9/4 -2/4 3/2 3/4	0 0 1 0	1 0 0 0
∆j		50	0	0	3/4	11/4	0	0

y₅ y₆ y₁ y₂ y₃ y₄

х₁ = 5, х₂ = 3, х₃ = 0, х₄ = 0, х₅ = 0, х₆ = 3 – выпускаем продукции А – 5 штук, В – 3 штуки, сырье s₁ и s₂ используется полностью, s₃ – недоиспользовано 6 единиц, s₄ – 3 единицы.

у₁ = 3/4, у₂ = 11/4, у₃ = 0, у₄ = 0, у₅ = 0, у₆ = 0, F = 50 – в первую очередь необходимо закупать ресурс s₂. Чем выше оценка, тем эффективнее ресурс.

Прямая задача: max

, i = ; х_j  0, j = .

Двойственная задача: min

, .

y_i  0, .

Теорема 1: если в прямой и двойственной задаче существуют оптимальные решения, то значения целевых функций на оптимальных решениях равны.

, - оптимальные решения

f ( ) = g ( )

Теорема 2: пусть = (х₁*, х₂*, … х_n*) - допустимое решение прямой задачи, а = (y₁*, y₂*, … y_m*) - допустимое решение двойственной задачи. Для того чтобы и были оптимальными решениями необходимо и достаточно, чтобы выполнялись следующие соотношения:

(1)

(2)

Из теоремы 2 вытекает четыре условия дополняющей нежесткости:

1. Если переменная исходной задачи равна нулю x_j* =0, то  a_ij  y_i* > c_j отлично от нуля, т.е. если изделие невыгодно и оно не вошло в оптимальный план, то оценка затрат больше ре-зультата (дополнительная переменная соответствующего неравенства двойственной задачи > 0).

2. Если в оптимальном плане переменная исходной задачи больше нуля x_j* > 0, то из (1)  a_ij  y_i* = c_j соответствующее ограничение двойственной задачи выполняется как строгое равенство. Изделие, которое выгодно производить и оно вошло в оптимальный план, для него оценка затрат на одну единицу продукции равно результату от единицы продукции. Дополнительная переменная двойственной задачи равна нулю (если ограничения в виде равенства, соответствующая переменная больше нуля). Можно судить о выгодности производства по дополнительным переменным соответствующих ограничений двойственной задачи. Чем меньше дополнительные переменные, тем выгоднее производить эту продукцию. Самая выгодная продукция, у которой дополнительная переменная равна нулю.

3. Если сумма  a_ij  x_j*  b_i = 0, то из (2) y_i* > 0, если какое-либо ограничение прямой задачи выполняется как строгое равенство, то соответствующие переменные двойственной задачи больше нуля, т.е. если какой-либо вид ресурса полностью тратится на оптимальный план, то его оценка больше нуля.

4. Если  a_ij  x_j*  b_i < 0, то из (2) y_i* = 0, если какое-то ограничение прямой задачи выполняется как неравенство, то соответствующая переменная двойственной задачи равна нулю, т.е. если какой-либо ресурс потрачен не полностью на оптимальный план, то его оценка равна нулю.

Из пунктов 3 и 4 следует, что можно использовать переменные двойственной задачи для оценки дефицитности какого-либо: чем выше оценка переменной двойственной задачи, тем эффективнее ресурс.

3. Свойства двойственных оценок. Их экономическое содержание.

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

Свойства двойственных оценок:

1. Оценки, как мера дефицитности ресурсов. Дефицитный ресурс - полностью используемый в оптимальном плане, он имеет положительную оценку  а_ij  x_j = b_i, y_i > 0.

Избыточный (недефицитный) ресурс – не полностью используемый в оптимальном плане, имеет нулевую оценку.  а_ij  x_j < b_i,  y_i = 0 чем больше оценка, тем дефицитнее (эффективнее) ресурс.

2. Оценки, как мера влияния ограничения на целевую функцию. f ( ) = y_i^*  b_i (из 1-ой теоремы) – величина двойственной оценки характеризует прирост / снижение значения целевой функции при увеличении / уменьшении ресурса b_i на одну единицу.

3. Оценки, как инструмент для определения эффективности отдельных вариантов плана. Это свойство вытекает из 1 и 2 условия дополняющей не жесткости, по величине  a_ij  y_i^*  c_j можно судить об эффективности того или иного варианта плана. Если  =  a_ij  y_i^*  c_j = 0, то этот вариант плана оптимальный. Если  =  a_ij  y_i^*  c_j  0, то этот вариант плана рациональный (не плохой). Дополнительная переменная двойственной задачи характеризует соответствующий вариант плана.

4. Оценки, как инструмент балансирования суммарных затрат и результата z (x^*)= F(y^*)

5. Двойственная оценка относительно устойчива, т.е. при небольших изменениях свободных членов прямой задачи двойственная оценка не меняется  1, 2, 3 действительны для небольших изменений.