Metody_optimizatsii

4.4.3. Наж ат ь

кнопк у Добавит ь.

Появи тся

ди алоговое окно для

построени я

ограни чени й задачи .В

левой

части

указы вается ячейка

(группа ячеек), в которой

содержи тся

левая

часть ограни чени я,

в

ц ентре - знак ограни чени я,

в правой части - ячейка (группа ячеек)

с

правой частью

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

Послевводакаждого ограни чени я нужно

нажи мать

на

кнопку Д о ба в ить.

К огда все ограни чени я задачи

построены ,

нужно нажатьнакнопку О тменаи вернуться в ди алоговое

С помощ ью команд, находящ и хся в этом ди алоговом окне,

можно

вводи ть услови я для реш ени я задачопти ми зац и и всех классов. В

ряде

К оманды , и спользуемы е по умолчани ю , подходят для

больш ей части

практи чески х задач. К оманда М а ксима льно е в р емя

служи т для

72

назначени я времени в секундах,

вы деляемого напои скреш ени я задачи . В

это поле можно ввести

значени е, не превы ш аю щ ее 32767

с (более 9

часов).

Значени е 100,

и спользуемое по

умолчани ю , подходи т для

реш ени я

больш и нства задач.

К оманда П р едельно е

число

итер а ций

служи тдля назначени я чи слаи терац и й…

4.4.5.

У ст ановит ь флаж ок

Линейная

мод ел ь.

Э то

обеспечи т

при менени еси мплекс– метода.

4.4.6.

Наж ат ь накнопк у Выпол нит ь. Н ачнется реш ени есоставленной

математи ческой модели задачи . Ч ерез

какое-то

время появи тся

ди алоговоеокно Результа ты

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

Н ужно вы брать и нтересую щ и е ви ды

отчетов по реш ени ю

задачи и

проанали зи ровать полученное реш ени е.

К ажды й и з вы бранны х ти пов

отчетасоздается наотдельном ли сте.

Отчет по

р езульта та м состои т

и з трех табли ц . Т а блица 1

при води тсведени я о ц елевой функц и и . В

столбц е И

схо дно

при ведены значени я

ц елевой

функц и и

до начала

вы чи слени й.

Т а блица

2 при води т значени я

и скомы х переменны х,

полученны е в результате реш ени я задачи.

Т а блица

3 показы вает

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

для грани чны х

услови й. Отчет по усто йчив о сти состои ти з двух табли ц . В

Т а блице 1

при водятся

следую щ и е значени я

переменны х:

результат реш ени я

задачи ; редуц и рованная стои мость,

т.е. дополни тельны едвойственны е

переменны е,

которы е

показы ваю т,

насколько

и змени тся

ц елевая

функц и я при

при нуди тельном вклю чени и еди ни ц ы этой продукц и и в

опти мальное реш ени е;

коэффи ц и енты

ц елевой функц и и ; предельны е

значени я при ращ ени я каждого коэффи ц и ента ц елевой функц и и ,

при

которы х сохраняется набор бази сны х

переменны х

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

реш ени и .

В

Т а блице

2

при водятся

аналоги чны е значени я

для

ограни чени й: вели чи на и спользованны х ресурсов; теневая ц ена,

т.е.

двойственны е оц енки ,

которы е показы ваю т,

как и змени тся

ц елевая

функц и я при

и зменени и ресурсов на еди ни ц у; значени я при ращ ени я

каждого

ресурса,

при

которы х

сохраняется

опти мальны й

набор

переменны х,

входящ и х в опти мальное реш ени е.

Отчет по

пр едела м

показы вает,

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

вош едш ей

в опти мальное реш ени е,

при

сохранени и

структуры

73

В

качестве

при мера рассмотри м

реш ени е

следую щ ей

задачи

прои зводственного плани ровани я

П р имер 1. Предпри яти евы пускаеттри ви дапродукц и и : Прод1, Прод2,

Прод3, Прод4. Т ребуется определи ть, в каком коли чественадо вы пускатьэти

продукты , чтобы

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

при бы ль. И звестно,

что

для

и зготовлени я данны х продуктов требую тся ресурсы трех ви дов: трудовы е,

сы рьевы е, фи нансы . Н ормы расхода (коли чество ресурса каждого ви да,

необходи мое для

вы пуска еди ни ц ы

продукц и и

каждого ти па),

а также

при бы ль, получаемая от реали зац и и

еди ни ц ы

каждого

ти па продукц и и ,

при ведены вследую щ ей табли ц е.

р есур с

П р о д1

П р о д2

П р о д3

П р о д4

Т рудовы е

60

70

120

130

Сы рье

1

1

1

1

Ф и нансы

6

5

4

3

М

При бы ль

4

6

10

13

атемати ческая модельданной задачи и меетви д

+

+

+

4

® max

x

130

x

120

3 1

2

+ + + 4 ≤1631

2x x x

+

+

+

4

£110

x3

x4

x5

6x

31

2

+

+

+

4

≤100 3 1

x 213

x 10

x6

4x

³

³

3 ³

4 ³ 0

1 x, 0 2 x, 0 x x, 0

ПЕР ЕМ ЕННЫ Е

им я

п р о д1

п р о д2

п р о д3

п р о д4

зна че ние

0

0

0

0

ниж н. гр

в е р х. гр

ко эф.в ЦФ

60

70

120

130

=СУ М М ПР ОИЗ В (B4:E4;B7:E7)

м а кс

ОГР

АНИЧЕНИЯ

п р а в а я

в ид

зна к

ча с ть

тр удо в ы е

1

1

1

1

=СУ М М ПР ОИЗ В ($B$4:$E$4;B10:E10)

<=

16

с ы р ье

6

5

4

3

=СУ М М ПР ОИЗ В ($B$4:$E$4;B11:E11)

<=

110

фина нс ы

4

6

10

13

=СУ М М ПР ОИЗ В ($B$4:$E$4;B12:E12)

<=

100

У слови я неотри ц ательности переменны х можно ввести

в ди алоговом окне

П а р а метр ы

по иска р еш ения. В окне П а р а метр ы

по иска

р еш ения

устанавли вается такжефлажокЛ инейна я мо дель.

4. З апуст им программу на выполнение из окна поиск

решения. Н а экране

появи тся

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

данном

ПЕР ЕМ ЕННЫ Е

им я

п р о д1

п р о д2

п р о д3

п р о д4

зна че ние

10

0

6

0

ниж н. гр

в е р х. гр

ко эф.в ЦФ

60

70

120

130

1320

м а кс

ОГР АНИЧЕНИЯ

п р а в а я

в ид

ле в а я ча с ть

зна к

ча с ть

тр удо в ы е

1

1

1

1

16

<=

16

с ы р ье

6

5

4

3

84

<=

110

фина нс ы

4

6

10

13

100

<=

100

Д анная табли ц а показы вает, что макси мальная при бы ль

(F7=1320) будет

дости гнута

предпри яти ем

при

следую щ ем вы пуске

продукц и и :

прод1=B4=10,

прод2=C4=0,

прод3=D4=6, прод2=E4=0.

В

спец и ально

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

12

10

8

6

4

2

0

п р о д1

п р о д2

п р о д3

п р о д4

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

Яче йка

Им я

Исходн о

Ре зультат

$F$7

ко эф.в ЦФ B5

0

1320

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

Яче йка

Им я

Исходн о

Ре зультат

$B$4

зна че ние

п р о д1

0

10

$C$4

зна че ние

п р о д2

0

0

$D$4

зна че ние

п р о д3

0

6

$E$4

зна че ние

п р о д4

0

0

Огр а ниче ния

Яче йка

Им я

З н аче н ие

ф орм ула

Статус

Разн ица

$F$10

тр удо в ы е

B5

16

$F$10<=$H$10

с в яза нно е

0

$F$11

с ы р ье B5

84

$F$11<=$H$11

не с в яза н.

26

$F$12

фина нс ы B5

100

$F$12<=$H$12

с в яза нно е

0

76

Т рудовы е ресурсы и спользованы

в коли честве 16, сы рье – 84, фи нансы

–

100. В графе Ра зница показано коли чество неи спользованного ресурса.

Т рудовы е ресурсы и спользованы

полностью , остаток сы рья составляет 26,

фи нансы и спользованы полностью . Е сли ресурси спользуется полностью ,

то

наотдельном ли стеи состои ти з двух табли ц .

В столбц е Результир ующ ее зна чение табли ц ы 1 при води тся

опи санны й

ранее результат реш ени я задачи. Столбец Но р мир о в а нна я

сто имо сть

показы вает, что при при нуди тельном вклю чени и еди ни ц ы

прод1 в

В столбц е Результир ующ ее

зна чение табли ц ы 2

при водятся

вели чи ны

и спользованны х

ресурсов. Столбец Т енев а я

цена

показы вает,

что при

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

функц и и

увели чи тся

на 20, при увели чени и

сы рья на еди ни ц у ц елевая

функц и я неи змени тся, при увели чени и

наеди ни ц у фи нансов опти мальное

значени ец елевой функц и и возрастетна10.

Microsoft Excel 8.0a Отче т по устойчивости

Рабочий лист: [Лист в F: metod exel_lab1.doc]Лист1

Отче т создан : 03.08.00 15:20:33

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

Ре зульт.

Норм ир.

Ц е ле вой

Д опустим ое

Д опустимое

Яче йка

Им я

зн аче н ие

стоимость

коэф ф ицие н т

уве личе н ие

уме н ьш е н ие

$B$4

зна че ние

п р о д1

10

0

60

40

12

$C$4

зна че ние

п р о д2

0

-10

70

10

1E+30

$D$4

зна че ние

п р о д3

6

0

120

30

13,33333333

$E$4

зна че ние

п р о д4

0

-20

130

20

1E+30

Огр а ниче ния

Ре зульт.

Те н е вая

Огран иче н ие

Д опустим ое

Д опустимое

Яче йка

Им я

зн аче н ие

це н а

правая часть

уве личе н ие

уме н ьш е н ие

$F$10

тр удо в ые

B5

16

20

16

3,545454545

6

$F$11

с ы р ье B5

84

0

110

1E+30

26

$F$12

фина нс ы B5

100

10

100

60

36

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

ц ену, по которой стои т

покупать

дополни тельны е

еди ни ц ы ресурсов.

Столбц ы Д о пустимо е

ув еличение и Д о пустимо е

уменьш ение показы ваю т,

что и зменени е

трудовы х

ресурсов в пределах от 16-3,545454

до 16+6

не при води т к

и зменени ю

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

аналоги чно для

Т рети й ти п отчета– Отчет по пр едела м.

Д анны й отчетсостои ти з одной

табли ц ы .

Це ле в о е

Яче й ка

Имя

зна че ние

$F$7

ко эф.в ЦФ

1320

Изме няе мо е

Нижний

Це ле в о й

В е р хний

Це ле в о й

Яче й ка

Имя

зна че ние п р е де л

р е зульта т

п р е де л

р е зульта т

$B$4

зна че ние

10

0

720

10

1320

п р о д1

$C$4

зна че ние

0

0

1320

0

1320

п р о д2

$D$4

зна че ние

6

0

600

6

1320

п р о д3

$E$4

зна че ние

0

0

1320

0

1320

Задачи нели нейной опти ми зац и и

могут реш аться разны ми методами . Д ля

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

→ extr

) x(f

x Rn

в Excel реали зовано 2 метода:

метод

Н ью тона и

метод сопряженны х

гради ентов

Ф летчера-Ри вса. В ы бор

метода

осущ ествляется в

окне

Параметры

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

В

качестве кри тери я останова в

Excel

k +1

−

k )

x( f

)

x(f

и спользуется услови е fk =

≤ ε .

Значени е ε вводи тся в

k

)

x(f

Д ля реш ени я задачусловной опти ми зац и и

) → extr

f

x

(

£ i

=

; ,i1 bg, x( )

i

m

j ³

=x

, , 1j

0,

n

вExcel и спользуется метод множи телей Л агранжа, позволяю щ и й реш ени е

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

задачи безусловной

опти ми зац и и . Работареали зованного вExcel методамножи телей Л агранжа

прои сходи тпо следую щ ей схеме.

1. В сеограни чени я –неравенствапреобразую тся вограни чени я- равенства.

Т аки м образом, задачапри ни маетви д

→ extr

) xf (

; m,

i,

) vx (

i

= 0 = 1

2. Полученная задачаперепи сы вается спомощ ью

функц и и Л агранжа

m

å i

i

x

®v y

= minx ,f+

Lymaxx

) (

) (

)(

i=1

x

y

где yi - двойственны епеременны е(множи тели Л агранжа).

3. Рассматри вается си стемауравнени й, ли нейная относи тельно yi :

∂

Ly)(

x=,

j =

0,

, n1

¶x j

Н аходи тся реш ени е этой

си стемы

-

вектор

y 0 ,

где коорди наты

yi0

вы ражены через x j :

i0 =

i0y(x) . y

4. Значени я yi0 подставляю тся

в функц и ю

Л агранжа и

реш ается

задача

безусловной опти ми зац и и

m

+ å i0

i

x ®v xmaxy f )x (

) (

( )

i=1

x

5. Е ереш ени е x * берется вкачествереш ени я и сходной задачи .

Реш ени е задачи

нели нейного

программи ровани я

рассмотри м на

следую щ ем при мере.

Пусть требуется

определи ть размеры

бака a,b,h,

При ни маем, что стои мостьматери ала C=kS,

гдеk-стои мостьеди ни ц ы площ ади матери ала.

В результатеполучи м C=2k(ab+(a+b)h)

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

сформули руем задачу

опти ми зац и и следую щ и м образом:

V = abh → max

£ C+ ))h+ b

a( ab (2k

зад

£100+ + ) h) b a(

ab ( 20

³ 0

h, ab,

Реш и м данную задачу си спользовани ем средствEXCEL.

Реш ени е задачи нели нейного программи ровани я

отли чается от

реш ени я задачи ли нейного программи ровани я следую щ и м:

·

назначаю тся начальны езначени я и скомы х переменны х xj0

·

в окне П а р а метр ы

по иска

р еш ения не надо вводи ть Л инейна я

мо дель.

Н ачальны езначени я xj0 желательно назначатьбли зки ми кожи даемы м

опти мальны м значени ям,

что ускори т реш ени е задачи .

О бязательны м

бы тьнеравнанулю (и начевозможно делени енанольпри вы чи слени и

fk ).

Н еобходи мо сделатьформу для вводауслови й задачи , в которую

далее

вводятся

80

∙

зави си мости для объ емаи стои мости (ячейки С8, С9);

∙

начальны е значени я xj0 (ячейки В 3, С3, D3). В данном случае в

В

ячейках,

в которы х будет представлен результат (B3:D3),

перед

реш ени ем задачи

надо назначи ть чи сло знаков после запятой. В

наш ем

при мереназначаем вячейках 2 знакапослезапятой.

П Е Р Е М Е ННЫ

Е

a

b

h

зна че ния

1

1

1

ниж н.

гр

З А В И СИ М О СТ И

о бо зна че ние

в е личина

зна к

п р а в а я ча с ть

о бъ е м

V

=B3^C3^D3

м а кс

с то им о с ть

C

=20^(B3^C3+(B3+C3)^D3)

<=

100

Д алее вы зы вается

программа П о иск р еш ения

и в

появи вш емся

ди алоговом окне вводи тся ячейка для ц елевой функц и и

(С8),

направлени е

Д о ба в ить и

в появи вш емся окне Д о ба в ление

о гр а ничений вводятся

ограни чени я

B3>=B4; C3>=C4; D3>=D4, C9<=E9. После ввода всех

ограни чени й

в окне пои ска реш ени я вы би рается

команда П а р а метр ы и

осущ

ествляется переход в ди алоговоеокно П а р а метр ы по иска р еш ения. В

нем

назначаю тся параметры пои ска реш ени я. В ы берем в качестве метода

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

гради ентов,

параметры

точности можно остави тьбез и зменени я .

После ввода всех

и сходны х данны х и параметров прои зводи тся реш ени е задачи.

Результаты

ди алогового окна можно

вы звать

отчеты трех ти пов:

р езульта ты ,

усто йчив о сть и пр еделы .

О тчеты

анали за по результатам

и пределам