Орлова И.В. Экономико-математические методы и модели. Выполнение расчетов в среде EXCEL. Практикум

Подождите немного. Документ загружается.

Добавление ограничения

Ссылка

на

ячейку:

Ограничение:

ок

Отмена

Добавить

ШШЯШЯШШШШШЯШШЯвШвШИШШШЩШЮШЯввшШтшШЯ

Рис.

2.2.4. Ввод правых и левых частей ограничений.

''0-Я'Л

J J

Справка

значение

коэф.

в ЦФ

Вид ресурсов

труд

сырье

оборудование

Ограничения

левая часть знак правая часть

0-<-

3 0i<= 480

130

Поиск решения

гановить целевую

[ЖЯИ И "У

Равной:

максимальному

значению С

значению:

f инициальному

значении»

вняр

ячейки:

—

|$В$3:$Е$3

фаничен*

Предположить

$F$7

<= $Н$7

$F$8

$Н$8

$F$9

$Н$9

£J

;

Добавить

ИЗМЗННТЬ

Удалить

Й=1ПОЛНИТЬ

Закрыть

Параметры

Восстановить

Справка

Рис. 2.2.5. Введены

все}

словия для решения задачи.

•

ОК.

(На экране диалоговое окно Поиска решения).

•

Выполнить. (На экране диалоговое окно Результаты поиска

решения - рис. 2.2.7).

100

секунд

ОК

Предельное

чекпа

итерации:

] 100

Отмен*

0з«сеитедьная

погрешность:

j0.000001

Ддрустимое

отклонение:

'•

Сводимость:

0.001

Загруяльявдеяь,,

Ссофакип»

модель..

Справка

Р Идейная модель

Автоматическое масштабирование

[7 НебтринательнЁР »нвч««ия

Г"

Показьвать^ультаты

итераций

гОценки i

Разности••—

- -Метод поиска

<•

пикейная

I»

доаные

<• Ньютона

;

<~ драдратичная s «

центральные

<"" соломенных

градиентов

Рис.

2.2.6. Ввод параметров.

*- ."•::- •*•

.."-•;:

а значение

1коэф.вЦФ

|Вид

ресурсов

|сырье

оборудование

Переменные

1X2 iX3 :Х4

,.,

Ограничения

левая часть знак

280

130

правая часть

480

130

—г

Результаты

поиска решения

Решение

найдено.

Все ограничения и условия

оптимальности

выполнены.

Тип

отчета

рзхранить найденное решение

Восстаноеить

исходные значения

Результаты

Устойчивость

Пределы

(Ж

Отмена Сохранить

сценарии,.,

Справка

Рис.

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

Полученное решение означает, что максимальный доход

150

тыс. руб.

фабрика может получить при выпуске 30 ковров второго вида и 10 ковров

третьего вида. При этом ресурсы труд и оборудование будут использованы

полностью, а

из

480 кг пряжи (ресурс сырье) будет использовано 280 кг.

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

EXCEL позволяет представить результаты поиска решения в форме

отчета. Существует три типа таких отчетов:

Результаты

(Answer).

В отчет включаются исходные и конечные значе-

ния целевой и влияющих ячеек, дополнительные сведения об ограничениях.

Устойчивость

(Sensitivity).

Отчет, содержащий сведения о чувстви-

тельности решения к малым изменениям в изменяемых ячейках или в

формулах ограничений.

Пределы (Limits). Помимо исходных и конечных значений изме-

няемых и целевой ячеек в отчет включаются верхние и нижние границы

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

ограничений.

Отчет по

результатам

Целевая ячейка (Максимум)

Ячейка

SFS4

Изменяемые ячейки

Ячейка

$В$3

$с$з

SDS3

$Е$3

Ограничения

Ячейка

$F$7

$F$8

$FS9

Имя

коэф в

ЦФ

Имя

значение

значение Х2

значение ХЗ

значение Х4

Имя

труд левая часть

сырье левая часть

оборудование левая часть

Исходно

Значение

280

130

Результат

150

Результат

Формула

SFS7

< $Н$7

$F$8<$H$8

$F$9 < SH$9

В отчете по результатам содержатся оптимальные значения пере-

менных

X],

Хт,,

Хц,

которые соответственно равны 0, 30, 10, 0, значе-

ние целевой функции -

150,

а также левые части ограничений.

2.3.

ДВОЙСТВЕННОСТЬ

ЗАДА ЧАХ

ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ.

АНАЛИЗ ПОЛУЧЕННЫХ

ОПТИМАЛЬНЫХ РЕШЕНИЙ

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

гая линейная задача, называемая двойственной; первоначальная задача

называется исходной, или прямой.

Связь исходной и двойственной задач заключается, в частности, в

том, что решение одной из них может быть получено непосредственно

из решения другой.

Хорошо разработанный математический аппарат линейного про-

граммирования позволяет не только получать с помощью эффективных

вычислительных процедур оптимальный план, но и делать ряд экономиче-

ски содержательных выводов, основанных на свойствах задачи, двойст-

венной к исходной ЗЛП. Переменные двойственной задачи

у,

называют

объективно обусловленными оценками, или двойственными оценками,

или «ценами» ресурсов, или теневыми ценами.

Каждая из задач двойственной пары фактически является самостоя-

тельной задачей линейного программирования и может быть решена

независимо от другой.

Двойственная задача по отношению к исходной составляется со-

гласно следующим правилам:

Целевая функция исходной задачи формулируется на максимум,

а целевая функция двойственной задачи - на минимум, при этом в задаче

на максимум все неравенства в функциональных ограничениях имеют

вид <, в задаче на минимум - вид >.

Матрица А, составленная из коэффициентов при неизвестных в

системе ограничений исходной задачи, и аналогичная матрица

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

Число переменных в двойственной задаче равно числу функцио-

нальных ограничений исходной задачи, а число ограничений в системе

двойственной задачи - числу переменных в исходной задаче.

Коэффициентами при неизвестных в целевой функции двойст-

венной задачи являются свободные члены в системе ограничений исход-

ной задачи, а правыми частями в ограничениях двойственной задачи -

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

Каждому ограничению одной задачи соответствует переменная

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

этом ограничению, записанному в виде неравенства <, соответствует

переменная, связанная с условием неотрицательности. Если функцио-

нальное ограничение исходной задачи является равенством, то соответ-

ствующая переменная двойственной задачи может принимать как поло-

жительные, так и отрицательные значения.

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

симметричными и несимметричными. В несимметричных двойствен-

ных задачах система ограничений исходной задачи задается в виде ра-

венств, а двойственной - в виде неравенств, причем в последней пере-

менные могут быть и отрицательными. В симметричных задачах сис-

тема ограничений как исходной, так и двойственной задачи задается

неравенствами, причем на двойственные переменные налагается усло-

вие неотрицательности.

Модель исходной (прямой) задачи в общем виде может быть запи-

сана следующим образом:

/(*)=£c

Jf,->max,

(23.1)

j=i

ta^-Xjub,,

(2.3.2)

7=1

Xj > 0.

(2.3.3)

Модель двойственной задачи имеет вид:

g(y) =

->nun,

(2.3.4)

;=1

-Y,>Cj,

(2.3.5)

(=1

> 0.

(2.3.6)

Две приведенные задачи образуют пару симметричных двойствен-

ных задач. Согласно теории линейного программирования каждой

ЗИП

вида (2.3.1) - (2.3.3) соответствует двойственная ей ЗЛП: (2.3.4) - (2.3.6).

Основные утверждения о взаимно двойственных задачах содержатся в

двух следующих теоремах.

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

Для взаимно двойственных задач (2.3.1) - (2.3.3) и (2.3.4) - (2.3.6)

имеет место один из взаимоисключающих случаев:

В прямой и двойственной задачах имеются оптимальные реше-

ния, при этом значения целевых функций

совпадают:/(х)

g(y).

В прямой задаче допустимое множество не пусто, а целевая

функция на этом множестве не ограничена сверху. При этом у двойст-

венной задачи будет пустое допустимое множество.

В двойственной задаче допустимое множество не пусто, а целе-

вая функция на этом множестве не ограничена снизу. При этом у прямой

задачи допустимое множество оказывается пустым.

Обе из рассматриваемых задач имеют пустые допустимые мно-

жества.

Экономический смысл 1-й теоремы двойственности следующий.

План производства X и набор оценок ресурсов Y оказываются опти-

мальными тогда и только тогда, когда общая стоимость продукции,

определенная при известных заранее ценах продукции, равна затратам

на ресурсы по «внутренним» (определяемым только из решения зада-

чи) ценам ресурсов у,. Для всех же других планов X и Y обеих задач

прибыль от продукции всегда меньше (или равна) стоимости затрачен-

ных ресурсов:/(X) < g

(У),

т.е. ценность всей выпущенной продукции

не превосходит суммарной оценки имеющихся ресурсов. Значит, вели-

чина g

(Y) -f(X)

характеризует производственные потери в зависимо-

сти от рассматриваемой производственной программы и выбранных

оценок ресурсов.

Из 1-й теоремы двойственности следует, что при оптимальной про-

изводственной программе и векторе оценок ресурсов производственные

потери равны нулю.

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

претировать и так: предприятию безразлично, производить ли продук-

цию по оптимальному плану X

получить максимальную прибыль либо

продать ресурсы по оптимальным ценам Y

возместить от продажи рав-

ные ей минимальные затраты на ресурсы.

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

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

ПустьX

(х/,

..., х„) -допустимое решение прямой задачи (2.3.1)

- (2.3.3), а

У =

...,

)

- допустимое решение двойственной задачи

(2.3.4) - (2.3.6). Для того, чтобы они стали оптимальными решениями

соответственно задач (2.3.1) - (2.3.3) и (2.3.4) - (2.3.6), необходимо и

достаточно, чтобы выполнялись следующие соотношения:

У,-

( т

0; (2.3.7)

••

(2.3.8)

H^j-y.-Cj

Условия (2.3.7) и (2.3.8) позволяют, зная оптимальное решение од-

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

задачи.

Из 2-й теоремы двойственности в данном случае следуют такие

требования на оптимальную производственную программу X

(х;,

..., х„)

и оптимальный вектор оценок Y

{у,,

....

если

Y,>0,

то^а,

j • Xj

=b,

i-\,...,m;

7=1

если

X°I,J'-^v

^i,

^=°>

i-\,...,m;

(2.3.9)

7=1

если

Xj>0,

то^а,j

-Y,

j-\,...,n;

i=l

если

^a,j

TOXJ=0,

l,...,n. (2.3.10)

/=l

Условия (2.3.9) можно интерпретировать так: если оценка

едини-

цы ресурса /-го вида положительна, то при оптимальной производствен-

ной программе этот ресурс используется полностью, если же ресурс ис-

пользуется не полностью, то его оценка равна нулю. Из условия (2.3.10)

следует, что если

у'-й

вид продукции вошел в оптимальный план, то он в

оптимальных оценках неубыточен, если

же^'-й

вид продукции убыточен,

то он не войдет в план, не будет выпускаться.

Рассмотрим еще одну теорему, выводы которой будут использова-

ны в дальнейшем.

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

Значения переменных

в оптимальном решении двойственной за-

дачи представляют собой оценки влияния свободных членов

Ь,

системы

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

Af(x)

y,.

(2.3.11)

Решая ЗЛП (2.3.1) - (2.3.3) симплексным методом, мы одновремен-

но решаем двойственную ЗЛП (2.3.4) - (2.3.6). Переменные двойствен-

ной задачи

у,

называют объективно обусловленными оценками.

Рассмотрим экономическую интерпретацию двойственной задачи

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

Сформулируем экономико-математическую модель двойственной

задачи к задаче 2.1.2.

Количество неизвестных в двойственной задаче равно числу функ-

циональных ограничений в исходной задаче. В исходной задаче три

ограничения: по труду, по сырью и по оборудованию. Следовательно, в

двойственной задаче - три неизвестных:

- двойственная оценка ресурса труд, или «цена» труда;

- двойственная оценка ресурса сырье, или «цена» сырья;

- двойственная оценка ресурса оборудование, или «цена» обору-

дования.

Целевая

функция

двойственной задачи формулируется на минимум.

Коэффициентами при неизвестных в целевой функции двойственной зада-

чи являются свободные члены в системе ограничений исходной задачи.

g(y) =

80 •

+ 480 •

+130

•

min.

Необходимо найти такие «цены» на ресурсы

(YJ,

чтобы общая

стоимость используемых ресурсов была минимальной.

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

равно числу переменных в исходной задаче. В исходной задаче четыре

переменных, следовательно, в двойственной задаче четыре ограничения.

Правыми частями в ограничениях двойственной задачи являются коэф-

фициенты при неизвестных в целевой функции исходной задачи. Левая

часть ограничения определяет стоимость ресурсов, затраченных на про-

изводство единицы продукции. Каждое ограничение соответствует оп-

ределенному виду продукции.

7-Г

+5-Г

+2-7

>3,

2-7

+8Г

+4-Г

>4,

2-Г,+4-Г

+1-Г

>3,

6-Г1+3-У

+8Г

>1,

2i,l2,r

>0.

Решение двойственной задачи можно найти в отчете

Поиска

реше-

ний - отчете по устойчивости. Теневые цены ресурсов труд, сырье и обо-

рудование соответственно равны 4/3, 0, 1/3 или в десятичных дробях:

1,3333;

0,3333.

Отчет

по устойчивости 1

Изменяемые ячейки

Ячейка

$В$3

$С$3

SDS3

$Е$3

Ограничения

Ячейка

$F$7

$F$8

$F$9

Имя

значение

значение Х2

значение X3

значение X4

Имя

труд левая часть

сырье левая часть

оборудование

левая част

Результ

значение

Результ

значение

280

130

Нормир

стоимость

-7

-9 6667

Теневая

цена

1.3333

0 3333

Целевой

коэффи-

циент

Ограни-

чение

правая

часть

480

130

Допустимое

увеличение

9 6667

Допустимое

увеличение

150

1Е+30

Допусти-мое

уменьше-

ние

1Е+30

Допусти-мое

уменьше-

ние

200

Проведем анализ полученного оптимального решения исходной за-

дачи с помощью двойственных оценок.

Анализ использования ресурсов в оптимальном плане выполня-

ется с помощью соотношений 2-й теоремы двойственности:

если

Y,>0,

то^а,

j • Xj

=b, i

\,...,m;

7=1

если

£<з,

j • Xj

<b,

то^=0,

\,...,m.

7=1

Ресурсы труд и оборудование имеют отличные от нуля оценки 4/3 и

1/3 - эти ресурсы полностью используются в оптимальном плане, явля-

ются дефицитными, сдерживающими рост целевой функции. Правые

части этих ограничений равны левым частям:

JT,

2Х

6Х

80,

2Х\+АХ

+%Х

<Ш,

7-0

2-30

2-10

6-0

= 80 =

80,

2-0

4-30

+1-10 +

8-0

= 130 = 130.

Ресурс «сырье» используется не полностью (280 < 480), поэтому

имеет нулевую двойственную оценку

= 0).

5Хх +

8Х

4Х

ЗХ

480,

5-0

+ 8 • 30 +

4-10

+3-0 = 280 <

480.

Этот ресурс не влияет на план выпуска продукции.

Общая стоимость используемых ресурсов при выпуске 30 ковров

второго вида и

ковров третьего вида составит

150

тыс. руб.

g(y)

80-

+480-

+130-

= 80-4/3 + 480-0+130-1/3

150тыс.

руб.

Экономическое истолкование оценок есть интерпретация их общих

экономико-математических свойств, применительно к конкретному со-

держанию задачи. По условию (2.3.9) не использованный полностью в

оптимальном плане ресурс получает нулевую оценку. Нулевая оценка

ресурса свидетельствует о его недефицитности. Ресурс недефицитен не

из-за его неограниченных запасов (они ограничены величиной

Ь,),

а из-за

невозможности его полного использования в оптимальном плане. Так

как суммарный расход недефицитного ресурса меньше его общего коли-

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

препятствует и дальше максимизировать целевую

функцию/(

X).