Теория двойственности в анализе оптимальных решений экономических задач
Общую задачу линейного программирования можно записать следующим образом:
→max
,
С задачей линейного программирования тесно связана линейная задача, называемая двойственной; первоначальная задача называется исходной или прямой.
Переменные в двойственной задачи называют объектно-обусловленными оценками, или двойственными оценками. Модель двойственной задачи имеет вид: →min,
,
.
При определении симплексным методом оптимального плана одной из задач находится решение и другой (элементы строки оценок последней симплекс-таблицы, расположенные в столбцах, соответствующих первоначальным базисным переменным исходной задачи).
Двойственная задача по отношению к исходной задаче составляется согласно правилам:
1) целевая функция исходной задачи стремится к максимуму, а целевая функция двойственной задачи - к минимуму, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид: , а в задаче минимума ;
2) матрица А= , составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, транспонируется для двойственной задачи:
3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи равно числу переменных в исходной задаче;
4) коэффициентами при неизвестных в целевой функции двойственной задаче является свободные члены системы ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи;
5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничение записанному в виде неравенства , соответствует переменная, связанная условием не отрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.
Математические модели пары двойственных задач могут быть симметричными и несимметричными. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а в двойственной задаче имеют знак . В симметричных задачах системы ограничений как исходной, так и двойственной задачи задается неравенством, причем на двойственные переменные накладывается условие неотрицательности.
Первая теорема двойственности. Для взаимодвойственных задач линейно программирования имеет место один из взаимоисключающих случаев:
1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: .
2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.
3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.
4. Обе из рассматриваемых задач имеют пустые допустимые множества.
Вторая теорема двойственности. Пусть - допустимое решение прямой задачи, а - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответствующих взаимодвойственных задач, необходимо и достаточно, чтобы выполнялось следующие соотношения:
Теорема об оценках. Значения переменных в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов системы ограничений прямой задачи на величину : .
Как правило, если исходная задача имеет определённый содержательный смысл, то и двойственная задача имеет интерпретацию. Так, для прямой задачи, сформулированной как задача о производстве продукции из ресурсов экономическая интерпретация поясняется следующими выводами. Экономический смысл первой теоремы: план производства Х и набор оценок ресурсов оказывается оптимальным тогда и только тогда, когда прибыль от реализации продукции, определенная при известных заранее ценах продукции , равна затратам на ресурсы по внутренним ценам (определяющимися только из решения задачи) ресурсов . Для других планов обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов. Для любой производственной программы , то есть ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов, значит, величина характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных оценок ресурсов. Следовательно, из первой теоремы следует, что при оптимальной производственной программе и оптимальном векторе оценок ресурсов производственные потери равны нулю.
Предприятию безразлично производить продукцию по оптимальному плану и получать максимальную прибыль либо продать ресурсы по оптимальным ценам и возместить от продажи равные ей минимальные затраты на ресурсы.
Из второй теоремы следуют требования на оптимальную производственную программу и оптимальный вектор оценок :
если то , и если то (*)
если то , и если , то (**)
Условия (*) можно объяснить так: если оценка единицы ресурса - го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью; если же ресурс используется не полностью, то его оценка равна нулю.
Из условия (**) следует, что если -й вид продукции вошел в оптимальный план, то он в оптимальных оценках неубыточен, если же -й вид продукции убыточен, то он не войдет в план, не будет выпускаться.
Существуют два направленияанализа модели на чувствительность:
1) Вариантные расчеты по моделям с сопоставлением различных вариантов плана. (Вариантные расчеты могут осуществляться при неизменной структуре самой модели, но с изменением численной величины конкретных показателей модели или при варьировании самой модели).
2) Анализ каждого из полученных решений с помощью двойственных оценок.
Двойственные оценки могут иметь следующий смысл:
- мера дефицитности ресурсов и продукции;
- мера влияния ограничений на функцию;
- инструмент определения эффективности отдельных вариантов;
- инструмент балансирования суммарных затрат и результатов.
Пример(задача о планировании выпуска).
Пусть фабрика выпускает три вида тканей, причем суточное плановое задание составляет не менее 90 метров тканей первого вида, 70 метров второго и 60 метров третьего вида. В таблице указаны нормы расхода ресурсов трёх видов на производство одного метра ткани каждого вида:
| Ресурсы | Нормы расхода ресурсов на 1м ткани каждого вида | Общие запасы | ||
| Оборудование | ||||
| Сырье | ||||
| Электроэнергия |
Цена за один метр ткани 1- го вида 80 денежных единиц; 2-го вида - 70 денежных единиц; 3-го вида – 60 денежных единиц. Необходимо определить, сколько метров ткани всех видов следует выпустить, чтобы общая стоимость выпускаемой продукции была максимальной.
Решение. Составим математическую модель. Неизвестные величины – объемы выпуска ткани всех видов. Пусть
- количество выпуска ткани 1-го вида;
- количество выпуска ткани 2-го вида;
- количество выпуска ткани 3-го вида, тогда
С учетом имеющихся данных модель примет вид:
ограничение по ресурсам:
- плановое задание:
Целевая функция указывает общую стоимость выпускаемой продукции: →max
В результате решения задачи симплекс методом получен оптимальный план: метров 1, 2, 3 вида ткани соответственно, при котором достигается максимум общей стоимости продукции .
Решение двойственной задачи получим с использование теорем двойственности.
Введем обозначения:
- двойственная оценка оборудования.
- двойственная оценка сырья.
- двойственная оценка электроэнергии.
- двойственная оценка ткани вида 1.
- двойственная оценка ткани вида 2.
- двойственная оценка ткани вида 3.
Модель двойственной задачи имеет вид:
→min
.
Из второй теоремы двойственности следует для ресурса:
если , то ; если то .
Для задания по выпуску продукции:
если , то ; если , то .
Подставим, , , в ограничения прямой задачи:
2*112,5+3*70+4*86,25=780.
112,5+4*70+5*86,25=823,75<850.
3*112,5+4*70+2*86,25=790.
112,5>90
70=70
86.25>60.
Суточные ресурсы по оборудованию и электроэнергию использованы полностью. Сырьё используется не полностью, имеется остаток в размере 850-823,75=26,25(кг). План выпуска по тканям вида 1и 2 перевыполнен.
Из второй теоремы двойственности выясняем, что , остается . Так как , то все три ограничения двойственной задачи выполняются как равенства:
.
Так как ,то , , , отсюда
y1=2.5, y3=25, y5=-37.5. Подставив значения переменных y в целевую функцию двойственной задачи, проверяем, выполняется ли условие для оптимального плана .
Условие первой теоремы двойственности выполняется следующим образом: рассматриваемый план выпуска тканей и соответствующая ему система оценок ресурсов и продукции, оптимальны. По условию, не использованный полностью в оптимальном плане ресурс получает нулевую оценку. Нулевая оценка свидетельствует о его дефицитности. Данный ресурс не препятствует и даже максимизирует целевую функцию . Ограничивает целевую функцию дефицитные ресурсы, в данном примере – оборудование и электроэнергия. Они полностью использованы в оптимальном плане. По условию, оценка таких ресурсов положительна.
Задание
1)На основе индивидуальных численных значений исходных данных о деятельности производственной системы предприятия, выпускающего два вида продукции из сырья А и В, составьте математическую модель задачи, для этого введите переменные, определите целевую функцию, запишите ограничение на сырьё, выпишите дополнительные ограничения на спрос.
2)
Таблица 6
| Сырьё | Нормы расхода сырья на единицу продукции | Запасы сырья | |
| А | a1 | a2 | Аmax |
| В | b1 | b2 | Bmax |
| Прибыль | c1 | c2 |
Таблица 7
| № вар-та | C1 | С2 | А1 | A2 | B1 | B2 | Amax | Bmax | Ограничения на спрос x1 x2 | |
| x1 2x2 | x1 +x2 6,5 | |||||||||
| x1 3x2 | x1 +x2 6,5 | |||||||||
| x1 4x2 | x1 +x2 8 | |||||||||
| x1 2x2 | x1 +x2 13 | |||||||||
| x1 3x2 | x1 +x2 13 | |||||||||
| x1 4x2 | x1 +x2 16 | |||||||||
| x2 18 | x1 3+x2 | |||||||||
| x2 17 | x1 2+x2 | |||||||||
| x2 20 | x1 5+x2 | |||||||||
| x1 9 | x2 1,5+x1 | |||||||||
| x1 18 | x2 4+x1 | |||||||||
| x1 10 | x2 4+x1 | |||||||||
| x1 x2 | 2x1 +x2 6,5 | |||||||||
| 2x1 3x2 | 2x1 +x2 6,5 | |||||||||
| x1 2x2 | 2x1 +x2 8 | |||||||||
| 0.5x2 2x1 | 2x1 +x2 13 | |||||||||
| 0.5x2 3x1 | 2x1 +x2 13 | |||||||||
| 0.5x2 4x1 | 2x1 +x2 16 | |||||||||
| x2 18 | 2x1 3+x2 | |||||||||
| x2 17 | 2x1 2+x2 | |||||||||
| x2 20 | 2x1 5+x2 | |||||||||
| 2x1 9 | x2 1,5+2x1 | |||||||||
| x1 9 | x2 4+2x1 | |||||||||
| x1 5 | x2 4+2x1 | |||||||||
| x1 2x2 | x1 +x2 12 | |||||||||
| x1 3x2 | x1 +x2 6,5 | |||||||||
| x2 18 | x1 4+x2 | |||||||||
| x1 9 | x2 2+x1 | |||||||||
| x2 18 | 2x1 3+x2 | |||||||||
| x2 4x1 | x1 5+x2 |
3)Решите задачу линейного программирования графически.
4)Решите задачу симплекс методом.
5) Решите двойственную задачу линейного программирования, определите двойственные оценки и выполните анализ двойственных оценок.
Контрольные вопросы.
1. Какого типа задачи могут быть решены с помощью линейного программирования?
2. Что понимается под оптимальным решением?
3. Что такое условный экстремум функции?
4. Что такое целевая функция?
5. При каких условиях математическую модель можно назвать линейной?
6. Опишите процесс решения прямой задачи.
7. В чем отличие функций минимизации и максимизации?
8. Перечислите отличительные особенности решения двойственной задачи.
9. Опишите процесс формирования системы ограничений при решении прямой и двойственной задач.
Список литературы.
1. Акулич, И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич. – М.: Высш. шк., 1995.
2. Вагнер, Г. Основы исследования операций: в 3 т. / Г. Вагнер. – М.: Мир, 1973.
3. Давыдов, Э.Г. Исследование операций / Э.Г. Давыдов. – М.: Высш. шк., 1990.
4. Замков, О.О. Математические методы в экономике / О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемных. – М.: ДИС, 1997.
5. Справочник по математике для экономистов / Под ред. проф. В.И. Ермакова. – М.: Высш. шк., 1987.
Практическое занятие №9