LINEBURG


<< Пред. стр.

страница 7
(всего 15)

ОГЛАВЛЕНИЕ

След. стр. >>

Переменные
1X2 iX3 :Х4
а значение
1коэф.вЦФ § ,., 3
Ограничения
|Вид ресурсов левая часть знак правая часть
2 80
80 <=
6
з
|сырье 280 <= 480
4
оборудование 8 130 <= 130
1
—г
Результаты поиска решения

Решение найдено. Все ограничения и условия
оптимальности выполнены. Тип отчета
Результаты
Устойчивость
(* рзхранить найденное решение |
Пределы
f* Восстаноеить исходные значения


(Ж Справка
Отмена Сохранить сценарии,.,

Рис. 2.2.7. Решение найдено.

51
Полученное решение означает, что максимальный доход 150 тыс. руб.
фабрика может получить при выпуске 30 ковров второго вида и 10 ковров
третьего вида. При этом ресурсы труд и оборудование будут использованы
полностью, а из 480 кг пряжи (ресурс сырье) будет использовано 280 кг.

Создание отчета по результатам поиска решения

EXCEL позволяет представить результаты поиска решения в форме
отчета. Существует три типа таких отчетов:
Результаты (Answer). В отчет включаются исходные и конечные значе­
ния целевой и влияющих ячеек, дополнительные сведения об ограничениях.
Устойчивость (Sensitivity). Отчет, содержащий сведения о чувстви­
тельности решения к малым изменениям в изменяемых ячейках или в
формулах ограничений.
Пределы (Limits). Помимо исходных и конечных значений изме­
няемых и целевой ячеек в отчет включаются верхние и нижние границы
значений, которые могут принимать влияющие ячейки при соблюдении
ограничений.
Отчет по результатам
Целевая ячейка (Максимум)
Исходно
Имя Результат
Ячейка
0 150
SFS4 коэф в ЦФ

Изменяемые ячейки
Исходно Результат
Ячейка Имя
0 0
$В$3 значение XI
$с$з 0 30
значение Х2
0 10
SDS3 значение ХЗ
0
$Е$3 0
значение Х4

Ограничения
Значение
Имя Формула
Ячейка
80
труд левая часть SFS7 < $Н$7
$F$7
280
сырье левая часть
$F$8 $F$8<$H$8
$FS9 оборудование левая часть 130 $F$9 < SH$9

В отчете по результатам содержатся оптимальные значения пере­
менных X], Х2, Хт,, Хц, которые соответственно равны 0, 30, 10, 0, значе­
ние целевой функции - 150, а также левые части ограничений.

52
2.3. ДВОЙСТВЕННОСТЬ В ЗАДА ЧАХ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
АНАЛИЗ ПОЛУЧЕННЫХ ОПТИМАЛЬНЫХ РЕШЕНИЙ

С каждой задачей линейного программирования тесно связана дру­
гая линейная задача, называемая двойственной; первоначальная задача
называется исходной, или прямой.
Связь исходной и двойственной задач заключается, в частности, в
том, что решение одной из них может быть получено непосредственно
из решения другой.
Хорошо разработанный математический аппарат линейного про­
граммирования позволяет не только получать с помощью эффективных
вычислительных процедур оптимальный план, но и делать ряд экономиче­
ски содержательных выводов, основанных на свойствах задачи, двойст­
венной к исходной ЗЛП. Переменные двойственной задачи у, называют
объективно обусловленными оценками, или двойственными оценками,
или «ценами» ресурсов, или теневыми ценами.
Каждая из задач двойственной пары фактически является самостоя­
тельной задачей линейного программирования и может быть решена
независимо от другой.
Двойственная задача по отношению к исходной составляется со­
гласно следующим правилам:
1. Целевая функция исходной задачи формулируется на максимум,
а целевая функция двойственной задачи - на минимум, при этом в задаче
на максимум все неравенства в функциональных ограничениях имеют
вид <, в задаче на минимум - вид >.
2. Матрица А, составленная из коэффициентов при неизвестных в
системе ограничений исходной задачи, и аналогичная матрица Ат в
двойственной задаче получаются друг из друга транспонированием.
3. Число переменных в двойственной задаче равно числу функцио­
нальных ограничений исходной задачи, а число ограничений в системе
двойственной задачи - числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции двойст­
венной задачи являются свободные члены в системе ограничений исход­
ной задачи, а правыми частями в ограничениях двойственной задачи -
коэффициенты при неизвестных в целевой функции исходной задачи.
53
5. Каждому ограничению одной задачи соответствует переменная
другой задачи: номер переменной совпадает с номером ограничения; при
этом ограничению, записанному в виде неравенства <, соответствует
переменная, связанная с условием неотрицательности. Если функцио­
нальное ограничение исходной задачи является равенством, то соответ­
ствующая переменная двойственной задачи может принимать как поло­
жительные, так и отрицательные значения.
Математические модели пары двойственных задач могут быть
симметричными и несимметричными. В несимметричных двойствен­
ных задачах система ограничений исходной задачи задается в виде ра­
венств, а двойственной - в виде неравенств, причем в последней пере­
менные могут быть и отрицательными. В симметричных задачах сис­
тема ограничений как исходной, так и двойственной задачи задается
неравенствами, причем на двойственные переменные налагается усло­
вие неотрицательности.
Модель исходной (прямой) задачи в общем виде может быть запи­
сана следующим образом:

/(*)=?crJf,->max, (23.1)
j=i

ta^-Xjub,, (2.3.2)
7=1
Xj > 0. (2.3.3)
Модель двойственной задачи имеет вид:
т
g(y) = JJbrYl->nun, (2.3.4)
;=1
т
^a4-Y,>Cj, (2.3.5)
(=1
Y, > 0. (2.3.6)
Две приведенные задачи образуют пару симметричных двойствен­
ных задач. Согласно теории линейного программирования каждой ЗИП
вида (2.3.1) - (2.3.3) соответствует двойственная ей ЗЛП: (2.3.4) - (2.3.6).
Основные утверждения о взаимно двойственных задачах содержатся в
двух следующих теоремах.

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

Для взаимно двойственных задач (2.3.1) - (2.3.3) и (2.3.4) - (2.3.6)
имеет место один из взаимоисключающих случаев:
1. В прямой и двойственной задачах имеются оптимальные реше­
ния, при этом значения целевых функций совпадают:/(х) = g(y).
2. В прямой задаче допустимое множество не пусто, а целевая
функция на этом множестве не ограничена сверху. При этом у двойст­
венной задачи будет пустое допустимое множество.
3. В двойственной задаче допустимое множество не пусто, а целе­
вая функция на этом множестве не ограничена снизу. При этом у прямой
задачи допустимое множество оказывается пустым.
4. Обе из рассматриваемых задач имеют пустые допустимые мно­
жества.
Экономический смысл 1-й теоремы двойственности следующий.
План производства X и набор оценок ресурсов Y оказываются опти­
мальными тогда и только тогда, когда общая стоимость продукции,
определенная при известных заранее ценах продукции, равна затратам
на ресурсы по «внутренним» (определяемым только из решения зада­
чи) ценам ресурсов у,. Для всех же других планов X и Y обеих задач
прибыль от продукции всегда меньше (или равна) стоимости затрачен­
ных ресурсов:/(X) < g (У), т.е. ценность всей выпущенной продукции
не превосходит суммарной оценки имеющихся ресурсов. Значит, вели­
чина g (Y) -f(X) характеризует производственные потери в зависимо­
сти от рассматриваемой производственной программы и выбранных
оценок ресурсов.
Из 1-й теоремы двойственности следует, что при оптимальной про­
изводственной программе и векторе оценок ресурсов производственные
потери равны нулю.
Экономический смысл 1-й теоремы двойственности можно интер­
претировать и так: предприятию безразлично, производить ли продук­
цию по оптимальному плану X и получить максимальную прибыль либо
продать ресурсы по оптимальным ценам Y и возместить от продажи рав­
ные ей минимальные затраты на ресурсы.

55
Вторая теорема двойственности
(теорема о дополняющей нежесткости)

ПустьX = (х/, х2, ..., х„) -допустимое решение прямой задачи (2.3.1)
- (2.3.3), а У = (ylt у2, ..., ут) - допустимое решение двойственной задачи
(2.3.4) - (2.3.6). Для того, чтобы они стали оптимальными решениями
соответственно задач (2.3.1) - (2.3.3) и (2.3.4) - (2.3.6), необходимо и
достаточно, чтобы выполнялись следующие соотношения:
п
= 0; (2.3.7)
У,-

(т Л
H^j-y.-Cj •• 0 . (2.3.8)
X
J

Условия (2.3.7) и (2.3.8) позволяют, зная оптимальное решение од­
ной из взаимно двойственных задач, найти оптимальное решение другой
задачи.
Из 2-й теоремы двойственности в данном случае следуют такие
требования на оптимальную производственную программу X = (х;, х2, ..., х„)
и оптимальный вектор оценок Y = {у,, у2, .... ут):
п
если Y,>0, то^а, j • Xj =b, i-\,...,m;
7=1
н
если X ° I , J ' - ^ v < ^i, T0
^=°> i-\,...,m; (2.3.9)
7=1
m
если Xj>0, то^а,j -Y, =CJt j-\,...,n;
i=l
m
если ^a,j Y, >CJt TOXJ=0, j = l,...,n. (2.3.10)
/=l
Условия (2.3.9) можно интерпретировать так: если оценка Y, едини­
цы ресурса /-го вида положительна, то при оптимальной производствен­
ной программе этот ресурс используется полностью, если же ресурс ис­
пользуется не полностью, то его оценка равна нулю. Из условия (2.3.10)
следует, что если у'-й вид продукции вошел в оптимальный план, то он в
56
оптимальных оценках неубыточен, если же^'-й вид продукции убыточен,
то он не войдет в план, не будет выпускаться.
Рассмотрим еще одну теорему, выводы которой будут использова­
ны в дальнейшем.

Теорема об оценках

Значения переменных Y, в оптимальном решении двойственной за­
дачи представляют собой оценки влияния свободных членов Ь, системы
ограничений-неравенств прямой задачи на величину
Af(x) = Abry,. (2.3.11)
Решая ЗЛП (2.3.1) - (2.3.3) симплексным методом, мы одновремен­
но решаем двойственную ЗЛП (2.3.4) - (2.3.6). Переменные двойствен­
ной задачи у, называют объективно обусловленными оценками.
Рассмотрим экономическую интерпретацию двойственной задачи
на примере задачи оптимального использования ресурсов.
Сформулируем экономико-математическую модель двойственной
задачи к задаче 2.1.2.
Количество неизвестных в двойственной задаче равно числу функ­
циональных ограничений в исходной задаче. В исходной задаче три
ограничения: по труду, по сырью и по оборудованию. Следовательно, в
двойственной задаче - три неизвестных:
Y] - двойственная оценка ресурса труд, или «цена» труда;
Y2 - двойственная оценка ресурса сырье, или «цена» сырья;
Ys - двойственная оценка ресурса оборудование, или «цена» обору­
дования.
Целевая функция двойственной задачи формулируется на минимум.
Коэффициентами при неизвестных в целевой функции двойственной зада­
чи являются свободные члены в системе ограничений исходной задачи.
g(y) = 80 • Yx + 480 • Y2 +130 • Y3 -> min.
Необходимо найти такие «цены» на ресурсы (YJ, чтобы общая
стоимость используемых ресурсов была минимальной.
Ограничения. Число ограничений в системе двойственной задачи
равно числу переменных в исходной задаче. В исходной задаче четыре

57
переменных, следовательно, в двойственной задаче четыре ограничения.
Правыми частями в ограничениях двойственной задачи являются коэф­
фициенты при неизвестных в целевой функции исходной задачи. Левая
часть ограничения определяет стоимость ресурсов, затраченных на про­
изводство единицы продукции. Каждое ограничение соответствует оп­
ределенному виду продукции.
7-Г 1 +5-Г 2 +2-7 3 >3,
2-71+8Г2+4-Г3>4,
2-Г,+4-Г 2 +1-Г 3 >3,
6-Г1+3-У 2 +8Г 3 >1,
2i,l2,r 3 >0. ^
Решение двойственной задачи можно найти в отчете Поиска реше­
ний - отчете по устойчивости. Теневые цены ресурсов труд, сырье и обо­
рудование соответственно равны 4/3, 0, 1/3 или в десятичных дробях:
1,3333; 0; 0,3333.

Отчет по устойчивости 1
Изменяемые ячейки
Допусти-мое
Результ Нормир Целевой Допустимое
Ячейка Имя коэффи­
значение стоимость увеличение уменьше­
циент ние
$В$3 значение XI 0 -7 3 7 1Е+30
$С$3 значение Х2 30 4 1
0 8
SDS3 значение X3 10 0 1
3 1 75
значение X4 1Е+30
$Е$3 0 -9 6667 1 9 6667
Ограничения
Ограни­ Допусти-мое
Результ Теневая чение Допустимое
Имя
Ячейка значение цена правая увеличение уменьше­
часть ние
$F$7 труд левая часть 150
80 1.3333 80 15
$F$8 сырье левая часть 0 1Е+30 200
280 480
$F$9 оборудование 30 90
130 0 3333 130
левая част ь


Проведем анализ полученного оптимального решения исходной за­
дачи с помощью двойственных оценок.
1. Анализ использования ресурсов в оптимальном плане выполня­
ется с помощью соотношений 2-й теоремы двойственности:

58
п
если Y,>0, то^а, j • Xj =b, i = \,...,m;
7=1
n
если ?<з, j • Xj <b, т о ^ = 0 , i = \,...,m.
7=1
Ресурсы труд и оборудование имеют отличные от нуля оценки 4/3 и
1/3 - эти ресурсы полностью используются в оптимальном плане, явля­
ются дефицитными, сдерживающими рост целевой функции. Правые
части этих ограничений равны левым частям:
7 JT, + 2Х2 + 2Хг + 6Х4 < 80,
2Х\+АХ2 + ХЪ+%Х4<Ш,
7-0 + 2-30 + 2-10 + 6-0 = 80 = 80,
2-0 + 4-30 +1-10 + 8-0 = 130 = 130.
Ресурс «сырье» используется не полностью (280 < 480), поэтому
имеет нулевую двойственную оценку (Y2 = 0).
5Хх + 8Х2 + 4Х3 + ЗХ4 < 480,
5-0 + 8 • 30 + 4-10 +3-0 = 280 < 480.
Этот ресурс не влияет на план выпуска продукции.
Общая стоимость используемых ресурсов при выпуске 30 ковров
второго вида и 10 ковров третьего вида составит 150 тыс. руб.
g(y) = 80- Yx +480- Y2+130- Г3 = 80-4/3 + 480-0+130-1/3 = 150тыс. руб.
Экономическое истолкование оценок есть интерпретация их общих
экономико-математических свойств, применительно к конкретному со­
держанию задачи. По условию (2.3.9) не использованный полностью в
оптимальном плане ресурс получает нулевую оценку. Нулевая оценка
ресурса свидетельствует о его недефицитности. Ресурс недефицитен не
из-за его неограниченных запасов (они ограничены величиной Ь,), а из-за
невозможности его полного использования в оптимальном плане. Так
как суммарный расход недефицитного ресурса меньше его общего коли­
чества, то план производства им не лимитируется. Данный ресурс не
препятствует и дальше максимизировать целевую функцию/( X).

59
Заметим, что ценность видов ресурсов нельзя отождествлять с дей­
ствительными ценами, по которым осуществляется его закупка. В дан­
ном случае речь идет о некоторой мере, имеющей экономическую при­
роду, которая характеризует ценность ресурса только относительно по­
лученного оптимального решения.
2. Анализ эффективности отдельных вариантов плана выполняется
на основе соотношений из 2-й теоремы двойственности:
т
если Xj>0, то^а,j -Y, =Cj^ j-\,...,n;
i=\
m
если X a ',y Y,>CJt T O X , = 0 , j=\,...,n.
(=1

Если изделие вошло в оптимальный план (X, > 0), то в двойствен­
ных оценках оно не убыточно, т.е. стоимость ресурсов, затраченных на
производство единицы изделия, равна его цене. Такие изделия эффек­
тивны, выгодны с точки зрения принятого критерия оптимальности. В
нашей задаче это ковры второго и третьего видов.
Если стоимость ресурсов, затраченных на производство одного из­
делия, больше его цены, то это изделие не войдет в оптимальный план
из-за его убыточности. В нашей задаче в план выпуска не вошли ковры
первого и четвертого видов, потому что затраты по ним превышают цену
на 7 (10 - 3) тыс. руб. и 9.666 (10.666 - 1) тыс. руб. соответственно. Это
можно подтвердить, подставив в ограничения двойственной задачи оп­
тимальные значения вектора Y.
7-4/3 + 5-0 + 2-1/3 = 30/3 =10 > 3 ,
2-4/3 + 8-0 + 4-1/3 = 12/3=4 = 4,
2.4/3 + 4-0 + 11/3 = 9/3 = 3 = 3,
6-4/3 + 3 0 + 8 1/3 = 32/3 =10.666>1.
Разницу между правыми и левыми частями ограничений двойст­
венной задачи можно найти в Отчете по устойчивости в столбце
«Нормируемая стоимость».
3. Анализ влияния изменения правых частей ограничений на зна­
чения целевой функции (чувствительность решения к изменению запа­
сов сырья) выполняется с помощью теоремы об оценках.
60

<< Пред. стр.

страница 7
(всего 15)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign