 |
Экономический смысл 1-ой (основной) теоремы двойственности.
|
|
|
|
План производства Х* = (х1*, х2*, …,хn*) и набор цен (оценок) ресурсов Y* = (y1*, y2*, …, ym*) оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная по известным заранее «ценам» с1, с2,.., сn, равна затратам на ресурсы по «внутренним» (определенным только из решения задачи) ценам y1, y2, …, ym. Так в рассмотренной выше задаче оптимумы F max и Z min = 24, для всех остальных планов F(X) <= 24, а Z(Y) >= 24.
Можно интерпретировать экономический смысл 1-ой (основной) теоремы двойственности и так: предприятию безразлично, производить ли продукцию на основе оптимального плана Х* = (х1*, х2*, …, хn*) и получить максимальную прибыль (выручку) F max либо продавать ресурсы по оптимальным «внутренним» ценам Y* = (y1*, y2*, …, ym*) и возместить от продажи равные ей минимальные затраты на ресурсы Z min.
Вторая теорема двойственности
Теорема: Для того чтобы два допустимых решения 
и 
пары двойственных задач были их оптимальными решениями необходимо и достаточно, чтобы они удовлетворяли системе уравнений
(1)
Замечание: Теорема верна для симметричной двойственной пары, для задач в канонической и общей форме соотношения (1) верны только для ограничений в виде неравенств и для неотрицательных переменных.
В некоторой литературе под второй теоремой двойственности понимается другая теорема, следствием которой является предыдущая.
Теорема: Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через неосновные переменные ее оптимального решения.
Соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи:
|
|
|
| Переменные исходной задачи | |
| Первоначальные | Дополнительные |
 Х1 Х2 … Хj … Xn
|        Xn+1 Xn+2 … Xn+I … Xn+m
|
| Ym+1 Ym+2 … Ym+j … Ym+n | Y1 Y2 … Yi … Ym |
| Дополнительные | Первоначальные |
| Переменные двойственной задачи |
Пример.
При решении прямой задачи
F = 2x1 + 3х2 à max при ограничениях:
|
х1 + 3х2 <= 18
2х1 + х2 <= 16
х2 <= 5
3x1 <= 21
х1, х2 >= 0
симплекс-методом получили на последнем шаге:
F= 24 – 4/5х3 – 3/5х4 при оптимальном БР Х* =(6; 4; 0; 0; 1; 3).
| Базис | Свободный член | Переменные | Оценочное отношение | |||||
| Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | |||
| Х1 | -1/5 | 3/5 | ||||||
| Х5 | -2/5 | 1/5 | ||||||
| Х2 | 2/5 | -1/5 | ||||||
| Х6 | 3/5 | -9/5 | ||||||
| F | 4/5 | 3/5 |
Если решить симплекс-методом двойственную задачу:
Z =18y1 + 16y2 +5y3 + 21y4 à min при ограничениях:
y1 + 2y2 + 3y4 >= 2
3y1 + y2 + y3 >= 3
y1, y2, y3, y4 >= 0
то получим на последнем шаге:
Z = 24 + y3 + 3y4 + 6y5 + 4y6 при оптимальном БР Y* =(4/5; 3/5; 0; 0; 0; 0).
| Базис | Свободный член | Переменные | Оценочное отношение | |||||
| Y1 | Y2 | Y3 | Y4 | Y5 | Y6 | |||
| Y1 | 4/5 | 2/5 | -3/5 | 1/5 | -2/5 | |||
| Y2 | 3/5 | -1/5 | 9/5 | -3/5 | 1/5 | |||
| Z |
Замечание. Если в одной из взаимно двойственных задач нарушается единственность оптимального решения, то оптимальное решение другой двойственной задачи вырожденное.
С помощью теорем двойственности можно, решив симплекс-методом исходную задачу, найти оптимум и оптимальное решение ДЗ.
Метод, при котором сначала решают симплекс-методом ДЗ, а потом оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплекс-методом. Этот метод применяется, когда первое БР исходной задачи недопустимое или, например, число ее ограничений m больше числа переменных n.
Экономическая интерпретация двойственных задач.
|
|
|
Экономическую интерпретацию двойственных задач и двойственных оценок рассмотрим на примере.
Пример.
Для производства трех видов изделий А, В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице.
| Нормы затрат сырья (кг) на единицу продукции | ||
| А | В | С | |
| I II III | |||
| Цена единицы продукции (руб.) |
Определить план выпуска продукции, при котором обеспечивается ее максимальная стоимость, и оценить каждый из видов сырья, используемых для производства продукции. Оценки, приписываемые каждому из видов сырья, должны быть такими, чтобы оценка всего используемого сырья была минимальной, а суммарная оценка сырья, используемого на производство единицы продукции каждого вида,– не меньше цены единицы продукции данного вида.
Решение. Предположим, что производится x1 изделий А, х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 кг.
|
|
|
Продолжим рассмотрение оптимальных двойственных оценок. Вычисляя минимальное значение целевой функции двойственной задачи
видим, что оно совпадает с максимальным значением целевой функции исходной задачи.
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем
Первое ограничение двойственной задачи выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия вида А, выше цены этого изделия и, следовательно, выпускать изделия вида А невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи. Второе и третье ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий В и С, равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.
Таким образом, двойственные оценки тесным образом связаны с оптимальным планом прямой задачи. Всякое изменение исходных данных прямой задачи может оказать влияние как на ее оптимальный план, так и на систему оптимальных двойственных оценок. Поэтому, чтобы проводить экономический анализ с использованием двойственных оценок, нужно знать их интервал устойчивости. К рассмотрению этого мы сейчас и перейдем.
|
|
|
