Лекция 6. Двойственная задача линейного программирования

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

Рассмотрим задачу линейного программирования следующего вида:

В задаче требуется максимизировать целевую функцию; все ограничения являются неравенствами со знаком , все переменные неотрицательны. Задача содержит n управляющих переменных и m ограничений. Коэффициенты при переменных в целевой функции: ; свободные члены:

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

В двойственной задаче требуется найти минимум целевой функции; ограничения- неравенства со знаком , переменные неотрицательны. Задача содержит m управляющих переменных и n ограничений. Коэффициенты при переменных в целевой функции задачи являются свободными членами исходной задачи линейного программирования, а свободные члены двойственной задачи - коэффициентами целевой функции исходной задачи линейного программирования. Матрица коэффициентов двойственной задачи транспонирована.

Для пары двойственных задач верна следующая теорема.

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

Замечание. Если переменная исходной задачи может принимать только положительные значения, то i -тое условие в системе двойственной задачи является неравенством вида «». Если же переменная может принимать как положительные, так и отрицательные значения, то i -тое соотношение в системе двойственной задачи представляет собой уравнение. Если j - тое соотношение в системе исходной задачи является неравенством, то j - тая переменная двойственной задачи 0. В противном случае переменная может принимать как положительные, так и отрицательные значения.

Пример 1. Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции

при условиях

Решение. Для данной задачи

Число переменных в двойственной задаче равно числу уравнений в системе исходной задачи, т.е. равно трём. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений исходной задачи, т.е. числа 12, 24, 18.

Целевая функция исходной задачи исследуется на максимум, а система условий содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а её переменные могут принимать любые значения, в том числе и отрицательные. Т.к. все три переменные исходной задачи принимают только неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида «». Итак, сформулируем двойственную задачу:

Пример 2. Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции

при условиях

Решение. Для данной задачи

В соответствии с общими правилами задача, двойственная по отношению к данной, формулируется следующим образом:

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

Пусть в качестве управляющих переменных , , исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметров - количество ресурсов, используемых для изготовления изделий. Через обозначено количество ресурсов i -того типа, идущее на изготовление одного изделия j - того вида, _j - прибыль от реализации одного изделия j - того вида. Тогда исходная модель соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль.

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

j =1,…, m. Цены на ресурсы должны удовлетворять следующим двум условиям: во-первых, они не должны быть слишком высокими, иначе ресурсы невозможно будет продать; а во-вторых, цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реализации готовой продукции. Первое условие выражается формулой , второе условие – ограничениями

В левой части каждого из неравенств стоит прибыль от продажи ресурсов всех типов, идущих на изготовление j - того изделия, в правой части – прибыль от продажи j - того изделия ().

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

Значения переменных часто называют теневыми ценами.

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

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

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

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

Предположим, что производится изделий А, изделий В, изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции (общая стоимость произведённой предприятием продукции)

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

(1)

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

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

(2)

Задачи (1) и (2) образуют пару двойственных задач. Решение прямой задачи даёт оптимальный план производства изделий А, В, С, а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой-либо одной из них. Так как система ограничений задачи (1) содержит лишь неравенства вида «», то лучше сначала найти решение этой задачи. Её решение приведено в таблице.

Базис
	19/8 23/8 -3/4			5/8 1/8 -1/4		-1/8 -5/8 1/4
f	57/4			23/4		5/4

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

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

Так, увеличение количества сырья I вида на 1 кг приведёт к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастёт на 5,75 руб. и станет равной 1340 +5,75 = 1345,75 руб.

Точно так же увеличение на 1 кг сырья Ш вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастёт на 1,25 руб. и станет равной 1340 +1,25 = 1341,25 руб.

Вычисляя минимальное значение целевой функции двойственной задачи

,

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

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

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

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

Дата добавления: 2014-01-11