Двойственные задачи линейного программирования

Двойственные задачи линейного программирования

Каждой задаче ЛП соответствует другая задача, называемая двойственной или сопряженной по отношению к исходной. Теория двойственности оказалась полезной для проведения исследования ЗЛП.

Экономическая интерпретация двойственной задачи к задаче об использовании ресурсов

Пусть математическая формулировка задачи об использовании ресурсов такова: (1) (Слайд 2) при ограничениях

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

Теорема:Если однаиз сопряженныхзадач имеет оптимальное решение , то и вторая имеет оптимальное решение , при этом

Fmax = Zmin или F(X*) = Z(Y*).

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

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

Задача. Дана задача (рассматривали в лекции по симплекс-методу):

 

F = 2x1 + 3х2 à max при ограничениях:

 

х1 + 3х2 <= 18

2х1 + х2 <= 16

х2 <= 5

3x1 <= 21

х1, х2 >= 0

и двойственная к ней:

Z =18y1 + 16y2 +5y3 + 21y4 à min при ограничениях:

 

y1 + 2y2 + 3y4 >= 2

3y1 + y2 + y3 >= 3

y1, y2, y3, y4 >= 0

 

Прямая задача была решена в лекции о симплекс-методе и был получен ответ F max = 24. если решить симплекс-методом двойственную задачу, то будет получен ответ, что Z min = 24. Т.е. заключение первой части теоремы двойственности верно.

 

Экономический смысл 1-ой (основной) теоремы двойственности.

Можно интерпретировать экономический смысл 1-ой (основной) теоремы двойственности и так: предприятию безразлично, производить ли продукцию на основе…

Вторая теорема двойственности

(1) Замечание: Теорема верна для симметричной двойственной пары, для задач в… В некоторой литературе под второй теоремой двойственности понимается другая теорема, следствием которой является…

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

Экономическую интерпретацию двойственных задач и двойственных оценок рассмотрим на примере.

Пример.

Для производства трех видов изделий А, В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице.

(Слайд 7) Вид сырья	Нормы затрат сырья (кг) на единицу продукции
А	В	С
I II III
Цена единицы продукции (руб.)

 

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

Решение. Предположим, что производится x₁ изделий А, х2 изделий В и х3 изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции

(1)

при следующих условиях

(2)

(3)

Припишем каждому из видов сырья, используемых для производства продукции, двойственную оценку, соответственно равную у1, у2 и у3. Тогда общая оценка сырья, используемого на производство продукции, составит

(4)

Согласно условию, двойственные оценки должны быть такими, чтобы общая оценка сырья, используемого на производство единицы продукции каждого вида, была не меньше цены единицы продукции данного вида, т. е. у1, у2 и у3 должны удовлетворять следующей системе неравенств:

(5)

(6)

Задачи (1) – (3) и (4) – (6) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий A, В и С, а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой–либо одной из них. Так как система ограничений задачи (1) – (3) содержит лишь неравенства вида “ ”, то лучше сначала найти решение этой задачи. Ее решение приведено в таблице:

Базис	Св.член	Х1	Х2	Х3	Х4	Х5	Х6
Х2 Х5 Х3		19/8 23/8 –3/4 57/4		0	5/8 1/8 –1/4 23/4		–1/8 –5/8 1/4 5/4

 

Из этой таблицы видно, что оптимальным планом производства изделий является такой, при котором изготовляется 82 изделия В и 16 изделий С. При данном плане производства остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна 1340 руб. Из таблицы также видно, что оптимальным решением двойственной задачи является

Переменные у1* и у3* обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье 1 и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.

Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 5,75 руб. и станет равной 1340+5,75=1345,75 руб. При этом числа, стоящие в столбце вектора Х4 таблицы, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий В на 5/8 ед. и сокращения выпуска изделий С на 1/4 ед. Вследствие этого использование сырья II вида уменьшится на 1/8 кг. Точно так же увеличение на 1 кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. и уменьшения изготовления изделий В на 1/8 ед., причем объем используемого сырья II вида возрастет на 5/8 кг.

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

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

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем

Первое ограничение двойственной задачи выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия вида А, выше цены этого изделия и, следовательно, выпускать изделия вида А невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи. Второе и третье ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий В и С, равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.

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

Анализ чувствительности в линейном программировании

Таким образом, после математического решения задачи линейного программирования, расчета ее оптимального плана и оптимума, необходимо… Общая задача такого анализа - определить устойчивость полученного решения к… Обычно результаты анализа охватывают несколько разделов. Важность тех или иных разделов зависит от конкретной…

Критические границы и допустимые изменения ресурса

Для производства двух видов изделий А и В используется четыре различных вида сырья. Каждый из видов сырья может быть использован в количестве,…   Вид сырья Нормы затрат сырья (кг) на единицу… Определить план выпуска продукции, при котором обеспечивается ее максимальная стоимость, и провести анализ…

Ценовой анализ

Обратимся к нашему примеру. Цена изделия А составляет 3 руб. за ед. Предположим, что отпускная цена изменилась, и теперь изделие А продается по… Предположим, что цена Изделия А изменились на Δс1. Тогда прибыль в…