Двойственность ЗЛП

 

П.п.12.2. Двойственность ЗЛП

     Замечание. Произвольную ЗЛП можно сопоставить с другой ЗЛП, называемой двойственной (первоначальная задача является исходной). Они связаны между собой и образуют единую двойственную пару. Различают по виду записи: симметрические, несимметрические, смешанные двойственные задачи.

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

а) для симметричных (стандартный вид исходной)

1. каждому неравенству системы ограничений исходной задачи соответствует двойственная переменная ;
2. составляется целевая функция двойственной задачи с коэффициентами, которой являются свободные члены системы ограничений исходной задачи; критерий оптимальности обратный исходной;
3. составляется система ограничений, коэффициенты которой образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи, причем знаки неравенств меняется на противоположный;
4. свободными членами системы ограничений являются коэффициенты целевой функции исходной задачи;

б) для несимметричных (канонический вид исходной)

5. ограничениями двойственной задачи являются неравенства, если со знаком , если со знаком ;
6. двойственная переменная - произвольные по знаку;

Например, в случае а)

Исходная  задача 

при условии 

. 

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

при условии 

.

     в случае б)

Исходная  задача 

при условии 

. 

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

при условии 

.

     Замечание. В случае в) - при составлении смешанной двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.

     Утверждения, позволяющие определять оптимальное решение одной из задач по решению другой:

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

     ).

     Утверждение 2. Для оптимальности допустимых опорных решений X и Y необходимо и достаточно, чтобы они удовлетворяли системе уравнений: 
 

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

      Вывод: 1) если мало, то значительному увеличению i-го ресурса будет соответствовать небольшое увеличение оптимального дохода и ценность ресурса невелика;

            2) если , то при увеличении i-го ресурса оптимальный доход остается неизменным и ценность этого ресурса равна нулю;

            3) если  велико, то незначительному увеличению i-го ресурса будет соответствовать существенное увеличение оптимального дохода и ценность ресурса высока. Уменьшение ресурса ведет к существенному сокращению выпуска продукции.

      Замечание:  1) считают характеристикой ценности i-го ресурса. В частности, при увеличении i-го ресурса на единицу оптимальный доход возрастает на , что позволяет рассматривать как «условную цену», оценки единицы i-го ресурса, т.е. как обусловленную оценку;

                  2) - это частная производная от оптимального дохода по i-му ресурсу, т.е. характеризует скорость изменения оптимального дохода при изменении i-го ресурса;

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

, 

где элементы матрицы =(, матрица A – матрица базиса оптимального решения системы ограничения; - значение переменной в оптимальном решении.

                  4) если в план  включаются новые виды продукции,  то их оценка находится по  формуле

 

Вывод: а) если , то новый вид продукции улучшает план;

          б) при нецелесообразно включать новый вид продукции.

Экономический смысл утверждения 1

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

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

Экономический смысл утверждения 2

      1) Следуют следующие требования на оптимальный производственный план X и оптимальный вектор оценок Y:

а) если ;

б) если .

      2) Следуют следующие требования на оптимальный производственный план Y и оптимальный вектор оценок X:

а) если ;

б) если .

     Замечание. Анализ модели чувствительность к определенным изменениям исходной модели из последней симплексной таблицы коэффициенты замещения означает:

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

 

Задача  стратегического  планирования выпуска  изделий

с учетом имеющихся  ресурсов

      Фирма выпускает 3 вида изделий, располагая при  этом сырьем 4-х типов:  соответственно в количествах 18, 16, 8 и 6 т. Нормы затрат сырья на единицу изделия 1-го вида, составляет соответственно 1, 2, 1, 0, второго вида – 2, 1, 1, 1 третьего – 1,1, 0, 1. Прибыль от реализации единицы изделия 1-го вида равна 3 у.д.е., 2-го – 4  у.д.е., 3-го – 2 у.д.е.

Требуется:

1. составить план производства 3-х видов изделий, максимизирующих прибыль;
2. определить дефицитность сырья;
3. установить размеры максимизирующей прибыли при изменении сырья 1-го вида на 6 т, 2-го – на 3 т, 3-го – на 2 т, 4-го – на 2 т. Оценить раздельное влияние этих изменений и суммарное их влияние на прибыль;
4. оценить целесообразность введения в план производства фирмы нового вида изделия, нормы затрат на единицу которого соответственно равны 1, 2,2, 0, а прибыль составляет 15 у.д.е.

Решение.

1. Исходная задача

 

при условиях ограничения на сырье 

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

при условии 

.

.

Согласно утверждения 1: )=33 у.д.е.

Согласно  утверждения 2, подставляем в систему ограничений исходной задачи 

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

отсюда  .

2. Согласно утверждения 3, так как наибольшая оценка , то сырье 3-го вида наиболее дефицитное; , то сырье 2-го вида менее дефицитное; , то сырье 1-го вида  не является дефицитным.
3. Для определения интервала устойчивости оценок согласно замечания 3 найдем матрицу для матрицы А коэффициентов при базисных переменных в оптимальном решении системы ограничений исходной задачи. Базисными переменными в оптимальном решении являются :

 
 

Найдем  интервал устойчивости оценок по видам  сырья:

Интервал  устойчивости оценок по отношению к 1-му виду сырья

 

,

,

. 

Интервал  устойчивости оценок по отношению к  2-му виду сырья

 
 

.

Интервал  устойчивости оценок по отношению к  3-му виду сырья

 
 

.

Интервал  устойчивости оценок по отношению к  4-му виду сырья

 
 

.

4. Изменение сырья согласно условиям задачи на +6, +3, +2, +2 т приводят к ограничению запаса сырья до 24, 19, 10, 8 т соответственно. Поскольку эти изменения находятся в пределах устойчивости оценок, на что указывают интервалы, то раздельное их влияние на прибыль определяется по формуле согласно утверждения 3:

.

Отсюда             

 

Суммарное влияние на прибыль ,

Наибольшая  прибыль составит

.

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

5. Для оценки целесообразности введения в план производства фирмы нового (4-го вида) изделия используем формулу

 
так как прибыль превышает затраты, то введения в план производства4-го вида изделий целесообразно.

Задачи  для самопроверки

Задача  оптимального использования  ресурсов

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