Лекция 3. Двойственные задачи ЛП

помощью теории двойственности:
1)нахождение дефицитных ресурсов,
2) анализ на чувствительность

(интервалы изменений коэффициентов целевой функции, при которых оптимальные значения переменных остаются неизменными)

Z(Y)=

к одному смыслу: если в исходной задач ищут максимум линейной

функции, то все неравенства системы ограничений приводят к виду «≤», а если минимум – к виду «≥».
Составляют расширенную матрицу системы А1, в которую включают матрицу коэффициентов при переменных, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.
Находят матрицу А, транспонированную к матрице А1.
Формулируют двойственную задачу на основании полученной матрицы А и условия неотрицательности переменных.

допустимых решений Х= (x1,x2, …,хn) и У=(y1,y2,…,ym) исходной и двойственной

задач справедливо неравенство:
F(X) ≤ Z(Y)

оптимальное решение, то его имеет и другая, причём оптимальные значения

их целевых функций равны:
Fmax=Zmin или F(X*) =Z(Y*) (1)

план исходной задачи и Y*=(y1* , y2* ,….. yn* )

- план двойственной задачи.
X*и Y* являются оптимальными только тогда и только тогда, когда для любого j, (j=1,2,..n) выполняется равенство

вида сырья. каждый из них используется в объёме, не превышающем

180, 210 и 236кг. Определить план выпуска изделий, обеспечивающий получение оптимального дохода при условии, что потребление ресурсов по каждому виду продукции не превзойдёт имеющихся запасов.

Экономико-математическая модель задачи:
F= 10x1+14x2+12x3→max






x1≥0, x2≥0, х3≥0.

затраты на ресурсы будут минимальными при условии, что затраты на

ресурсы при производ-стве каждого вида продукции будут не менее прибыли от реализации этой продукции.

Z(У)= 180y1+210y2+236y3→min





y1≥0, у2≥0, у3≥0.
Симметричная задача

двух видов П1 и П2. Для производства продукции используются три

вида сырья А,В,С, максимально возможные запасы их составляют 6,8 и 5 тонн соответственно. Расходы сырья А,В,С на 1 тыс. изделий П1 и П2 приведены в таблице. Изучение рынка сбыта показало, что суточный спрос на изделия П2 не превышает спроса на изделия П1 более чем на 1 тыс.шт. Установлено, что спрос на изделия П2 не превышает 2 тыс.шт. в сутки. Какое количество изделий 9в тыс.шт.) должна производить фабрика, чтобы доход от реализации продукции был максимальным?

при ограничениях:
х1+2х2≤6
2х1+х2≤8 y1+2y2+y3-y4 ≥3
х1+0,8х2≤5 2y1+y2+y3+y4 +y5 ≥2
- х1+х2≤1 y1 ≥0, y2 ≥0, .. y5 ≥0
х2≤2
x1≥0, x2≥0.

1 т. доход от реализации продукции увеличится на 1/3 тыс.руб.,

а при увеличении запаса сырья В на 1 т. доход от реализации продукции увеличится на 4/3 тыс.руб. Изменение запаса С или изменение в соотношениях спроса не приводят к изменению дохода. Ресурсы А и В являются дефицитными, ресурс С - недифицитный.

получим пределы изменения С2 , при которых будет выгодно выпускать

продукцию П2 -1/2≤ С2 ≤4
2 -1/2≤ С2 ≤ 2+ 4
3/2≤ С2 ≤ 6
Ответ:
1 ≤ С1 ≤ 4,
1,5 ≤ С2 ≤ 6.