Metody_optimizatsii
.pdf81
аналоги чны таки м жеотчетам для задачли нейного программи ровани я. О тчет
Изм е няе м ы е яче й ки |
|
|
|
|
|
Ре зультат |
Норм ир. |
Яче йка |
И м я |
зн аче н ие |
градие н т |
$B$4 |
зна че ния а |
1.29 |
0.00 |
$C$4 |
зна че ния b |
1.29 |
0.00 |
$D$4 |
зна че ния h |
1.29 |
0.00 |
Огр а ниче |
ния |
|
|
|
|
Ре зульт. |
Лагран ж а |
Яче йка |
И м я |
зн аче н ие |
М н ож ите ль |
$C$10 |
С в е личина |
100.00 |
0.03 |
по устойчи вости состои ти з двух табли ц .
Впервой табли ц епри водятся значени я для переменны х:
∙результатреш ени я задачи
∙ норми рованны й гради ент - вели чи на, при води мая при вы боре некоторы х методовв ди алоговом окнеПараметры пои скареш ени я.
Во второй табли ц епри водятся значени я для ограни чени й:
∙вели чи настои мости
∙множи тельЛ агранжа, показы ваю щ и й, каки змени тся ц елевая функц и я
при и зменени и правой части вограни чени и наеди ни ц у. |
|
|
|
|
|
|||||||||||||
|
Д ля |
задач ли нейного программи ровани я можно прои звести |
также |
|||||||||||||||
параметри чески й анали з, |
реш ая и х при |
разли чны х значени ях параметров. |
||||||||||||||||
А лгори тм |
вы полнени я |
|
параметри чески х |
расчетов |
аналоги чен |
схеме, |
||||||||||||
рассмотренной при реш ени и задачли нейного программи ровани я, |
поэтому в |
|||||||||||||||||
данном разделе разби раться |
не будет. |
В |
табли ц е при веден |
и тоговы й |
||||||||||||||
сц енари й, |
построенны й |
в результате реш ени я рассматри ваемой |
задачи |
|||||||||||||||
нели нейного программи ровани я при |
разли чны х значени ях стои мости : 100, |
|||||||||||||||||
200, 300, 400, 500. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
ИТОГОВ Ы |
Й СЦ ЕНА РИЙ |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
Те кущ ие зна че ния |
с=100 |
|
с=200 |
|
с=300 |
с=400 |
|
с=500 |
|
|
|||||
|
Изме н яе мы е яче йки |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
$B$4 |
|
|
2.89 |
|
|
1.29 |
|
1.83 |
|
2.24 |
2.58 |
|
2.89 |
|
|
||
|
$C$4 |
|
2.89 |
|
|
1.29 |
|
1.83 |
|
2.24 |
2.58 |
|
2.89 |
|
|
|||
|
$D$4 |
|
2.89 |
|
|
1.29 |
|
1.83 |
|
2.24 |
2.58 |
|
2.89 |
|
|
|||
|
Яче йки ре |
зультата |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
$C$9 |
|
24.06 |
|
|
2.15 |
|
6.09 |
|
11.18 |
17.21 |
|
24.06 |
|
|
|||
|
$C$10 |
500.00 |
|
|
100.00 |
|
200.00 |
|
300.00 |
400.00 |
|
500.00 |
|
|
||||
|
Пр име ча ние: в сто лбце |
Те кущ |
ие зна че ния п р ив е де ны да нные |
|
|
|
|
|
|
|||||||||
|
в изме няе мых яче й ка х на мо ме нт со зда ния о тче та |
Ито го в ый |
|
|
|
|
|
|
||||||||||
|
сце на р ий . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ЗА Д А Н И Я Д Л Я Л А БО РА Т О РН О ГО |
ПРА К Т И К У М |
А |
|
|
|
|||||||||||
|
Л абораторны й |
практи кум |
ори енти рован |
на |
форми ровани е |
практи чески х навы ков построени я математи чески х моделей для разли чны х
82
классов задачопти мального вы бораи реш ени я и х си спользовани ем средств EXCEL. Н и же при водятся задачи , для которы х необходи мо состави ть
математи ческую |
модель, реш и ть средствами EXCEL и проанали зи ровать |
|
полученны ерезультаты . |
|
|
1. И з пункта А в пункт В |
ежедневно отправляю тся пассажи рски е и |
|
скоры е поезда. |
В следую щ ей |
табли ц е указаны нали чны й парк вагонов |
разны х ти пов, и з которы х ежедневно можно комплектоватьданны епоезда, и коли чество пассажи ров, вмещ аю щ и хся вкаждом и з вагонов:
|
П о езда |
|
Ва го ны |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
Багажн. |
|
Почт. |
Ж .плац к. |
|
|
К упе |
|
М ягк. |
|
|||
|
Скоры й |
|
|
|
1 |
|
1 |
5 |
|
6 |
|
|
3 |
|
|
|||
|
Пассажи рски й |
|
|
|
1 |
|
- |
8 |
|
4 |
|
|
1 |
|
|
|||
|
Ч и сло |
|
|
|
- |
|
- |
58 |
|
40 |
|
|
32 |
|
|
|||
|
пассажи ров |
|
|
|
12 |
|
8 |
81 |
|
70 |
|
|
26 |
|
|
|||
|
Парквагонов |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
О предели ть опти мальное коли чество скоры х и пассажи рски х поездов, |
||||||||||||||||||
при котором чи сло перевози мы х пассажи ров дости гаетмакси мума. |
Реш и ть |
|||||||||||||||||
задачу в предположени и , |
что пропускная способностьдороги непозволяетв |
|||||||||||||||||
день пройти болеечем ш ести пассажи рски м поездам. |
|
|
|
|
|
|
|
|||||||||||
2. |
Д ля и зготовлени я двух ви дов и здели й А и В фабри ка расходует в |
|||||||||||||||||
качестве сы рья сталь и |
ц ветны е металлы , |
и мею щ и еся |
в ограни ченном |
|||||||||||||||
коли честве. Н а и зготовлени и указанны х двух и здели й заняты |
токарны е и |
|||||||||||||||||
фрезерны естанки . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
В |
следую щ ей табли ц епри ведены и сходны еданны езадачи : |
|
|
|
|
|
|||||||||||
Виды |
р есур со в |
|
|
|
Объем |
|
Но р ма р а схо да на о дно изделие |
|
||||||||||
|
|
|
|
|
|
Ресур со в |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А |
|
|
|
В |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Сталь(кг) |
|
|
|
570 |
|
|
|
10 |
|
|
|
70 |
|
|
|
|||
Ц ветны еметаллы (кг) |
|
420 |
|
|
|
20 |
|
|
|
50 |
|
|
|
|||||
Т окарны ест. (стан.ч.) |
|
5600 |
|
|
|
300 |
|
|
|
400 |
|
|
||||||
Ф резерны ест.(стан.ч.) |
|
3400 |
|
|
|
200 |
|
|
|
100 |
|
|
||||||
О предели ть план вы пуска продукц и и , при котором будет дости гнута |
||||||||||||||||||
макси мальная при бы ль. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
3. |
|
Прои зводи тельвы пускаетдвапродукта: продуктР, продаваемы й по |
||||||||||||||||
2000 дол. за1 т., и продуктQ, продаваемы й по 1000 дол. за1 т. Продукты |
||||||||||||||||||
могутпрои зводи ться и з двух ти пов сы рья: А |
по 600 дол. за1 т. и В |
по 900 |
||||||||||||||||
дол. за1 т. И з кажды х 100 тоннсы рья А прои зводят30 тоннР и 50 тоннQ, а |
||||||||||||||||||
и з 100 тонн сы рья В |
прои зводят60 тонн Р и 10 тонн Q. Е сли прои зводи тель |
|||||||||||||||||
обрабаты вает х тонн А |
и у тонн В , |
|
покажи те, что его при бы ль состави т |
|||||||||||||||
(500х+400у). Ф абри ка способна обработать не более 10000 |
тонн сы рья |
ежегодно. Поставщ и ки сы рья могутобеспечи тьнеболее6000 тоннсы рья А и
83
неболее8000 тоннсы рья В в год. Прои зводи тельможетпродаватьежегодно
по 5000 тоннпродуктаР и до 3200 тоннпродуктаQ. |
|
||
∙ |
О предели те, сколько сы рья А |
и В должно |
бы ть заказано для |
|
макси ми зац и и его при бы ли ? |
|
|
Поставщ и ки сы рья А угрожаю тповы си тьц ену. |
|
||
∙ |
Н асколько можно поднятьц ену, чтобы прои зводи телю при ш лось |
||
|
и змени тьзаказ? |
|
|
4. |
И мею тся три технологи чески х |
проц есса (I,II |
и III), связанны х с |
прои зводством некоторого продуктаи потреблени ем при этом четы рех ви дов сы рья.
П р о дукты |
Ра схо дсы р ья по типа м |
|
|
с |
|
|
1 |
2 |
3 |
4 |
|
|
|
|
|
|
|
I |
5 |
8 |
3 |
6 |
10 |
II |
4 |
3 |
9 |
5 |
15 |
III |
6 |
7 |
4 |
2 |
8 |
b |
50 |
50 |
20 |
60 |
|
Пустьсi означаетц ену продукта, полученного в результатепри менени я 1-го
проц ессаседи ни чной и нтенси вностью , b – ресурсы k-го ви дасы рья и а –
k ki
расход k-го ви да сы рья при i-м проц ессе с еди ни чной и нтенси вностью . О предели те и нтенси вности и спользовани я каждого проц есса и з услови я обеспечени я макси муматоварной продукц и и .
5. Предпри яти е может вы пускать продукц и ю по трем технологи чески отработанны м способам прои зводства. При этом за1 часпо первому способу
прои зводстваоно вы пускает20 еди ни ц |
продукц и и , по 2-му – 25 еди ни ц и по |
|||||||||
третьему – 30 |
еди ни ц продукц и и . К оли чество прои зводственны х факторов, |
|||||||||
расходуемы х за час при |
разли чны х способах прои зводства, и |
и мею щ и еся |
||||||||
ресурсы эти х факторовпредставлены вследую щ ей табли ц е: |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
Способ |
Ф а кто р ы |
|
|
|
|
|
|
|
|
|
пр-ва |
|
|
|
|
|
|
|
|
|
|
Сы рье |
|
Станочн |
Рабочая |
Э нерги я |
Т ранс- |
|
Прочи е |
||
|
|
|
|
|||||||
|
|
|
|
ы й парк |
|
си ла |
|
порт |
|
расходы |
|
1 |
2 |
|
3 |
|
7 |
2 |
1 |
|
4 |
|
2 |
1 |
|
4 |
|
3 |
1 |
0 |
|
2 |
|
3 |
3 |
|
2 |
|
4 |
3 |
1 |
|
1 |
|
И мею щ и еся |
|
|
|
|
|
|
|
|
|
|
ресурсы |
60 |
|
80 |
|
70 |
50 |
40 |
|
50 |
|
факторов |
|
|
|
|
|
|
|
|
|
Сплани роватьработу предпри яти я и з услови я получени я макси мума продукц и и , если и звестно, что общ еевремя работы предпри яти я составляет 30 часов.
84
6.Ф и рмапрои зводи ттри ви дапродукц и и (А ,В ,С), для вы пускакаждого
из которы х требуется определенноевремя обработки навсех четы рех устройствах I, II, III, IV.
В и д |
|
В ремя обработки , ч |
|
При бы ль, дол |
|
продукц и и |
|
|
|
|
|
I |
II |
III |
IV |
|
|
A |
1 |
3 |
1 |
2 |
3 |
B |
6 |
1 |
3 |
3 |
6 |
C |
3 |
3 |
2 |
4 |
4 |
|
|
|
|
|
|
Пусть время |
работы на устройствах |
– соответственно 84, |
42, 21, 42 ч. |
|||||
О предели те, |
какую продукц и ю |
и в каки х коли чествах следуетпрои зводи ть. |
||||||
(М ожете предположи ть, |
что |
ры нок сбы та для каждого |
и з |
продуктов |
||||
неограни чен; |
временем, |
требуемы м |
для |
переклю чени я |
устройства в |
|||
зави си мости |
от ви да продукц и и , |
можно пренебречь; рассмотри те только |
||||||
задачу макси ми зац и и при бы ли .) |
|
|
|
|
|
|
||
7.Ф и рма реклами рует свою |
продукц и ю |
с и спользовани ем четы рех |
||||||
средств: телеви дени я, ради о, |
газет и |
афи ш . И з разли чны х |
рекламны х |
экспери ментов, которы епроводи ли сьв прош лом, и звестно, что эти средства при водят к увели чени ю при бы ли соответственно на 10, 3, 7 и 4 доллара в расчетена1 доллар, затраченны й нарекламу.
Распределени ерекламного бю джетапо разли чны м средствам подчи нено следую щ и м ограни чени ям:
полны й бю джетнедолженпревосходи ть500000 долларов; Следует расходовать не более 40% бю джета на телеви дени е и не более 20% бю джетанаафи ш и ;
вследстви е при влекательности для подростков ради о на него следует расходовать по крайней мере полови ну того, что плани руется на телеви дени е.
Сформули руйтезадачу распределени я средств по разли чны м и сточни кам как задачу ли нейного программи ровани я и и спользуйте си мплекс-метод для ее реш ени я.
8.Н ефтяная компани я закупает необработанную нефть и з нескольки х и сточни ков W, X, Y, Z и зани мается ее очи сткой, вы рабаты вая разли чны е
ви ды А , |
В , С смазочны х масел, |
готовы х к продаже. И мею тся также |
||
ограни чени я при продаженаколи чество каждого ви дасмазочны х масел. |
||||
М асло |
Состав, % |
|
В озможное коли чество для продажи , |
|
|
|
|
галлоны |
|
А |
Н еменьш е10 (W) |
90000 |
|
|
|
Н ебольш е25 (Z) |
|
|
|
В |
Н еменьш е15 |
(W) |
100000 |
|
С |
Н еменьш е20 |
(X) |
120000 |
|
|
Н ебольш е50 (Y) |
|
|
85
Ц ены (в условны х еди ни ц ах) 1 галлонасы рья и смазочны х маселпри ведены ни же.
Сы рье |
|
|
|
М асло |
|
|
|
|
|
|
|
|
|
X |
Y |
Z |
W |
A |
B |
C |
72 |
60 |
67 |
75 |
90 |
87 |
84 |
Предполагая, что необработанная нефть доступна в неограни ченном коли честве, сформули руйте задачу макси ми зац и и при бы ли как задачу ли нейного программи ровани я, найди теопти мальноереш ени е.
9.Предпри яти е располагает ресурсами сы рья, рабочей си лой и оборудовани ем, необходи мого для прои зводства лю бого и з четы рех ви дов прои зводи мы х товаров. Затраты ресурсов наи зготовлени ееди ни ц ы данного
ви да товара, при бы ль, |
получаемая предпри яти ем, |
а также запасы ресурсов |
|||||||
указаны вследую щ ей табли ц е: |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
В и д |
|
В и д товара |
|
|
|
|
|
|
|
ресурса |
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
3 |
|
4 |
О бъ ем |
||
|
|
|
|
|
|
|
|
ресурсов |
|
Сы рье, кг |
|
3 |
|
5 |
2 |
|
4 |
60 |
|
Рабочая си ла, ч |
|
22 |
|
14 |
18 |
|
30 |
400 |
|
О борудовани е, ст-ч. |
|
10 |
|
14 |
18 |
|
16 |
128 |
|
|
|
|
|
|
|
|
|
|
|
При бы льнаеди ни ц у товарав рублях соответственно составляет30, 25, 56, 48. По и сходны м данны м реш и тьследую щ и езадачи :
∙ О предели ть ассорти мент товара, обеспечи ваю щ и й макси мальную при бы ль.
∙О предели тьопти мальны й ассорти ментпри дополни тельном услови и : 1-го товаравы пусти тьнеболее5 ед., 2-го – неменее8 ед., а3-го и 4-го – в соотнош ени и 1:2.
∙ Д ополни тельно к первой задаче заданы |
прои зводственны е и здержки в |
рублях на еди ни ц у каждого и здели я: 6, |
9, 12, 3. Н айти опти мальны й |
ассорти мент, ми ни ми зи рую щ и й при бы ль, при услови и , что суммарны е прои зводственны еи здержки недолжны превы ш ать96 р.
10. Н ефтеперерабаты ваю щ и й завод получает4 полуфабри ката: 400 ты с.
л. алки лата, |
250 ты с. л. креки нг-бензи на, 350 ты с. |
л. бензи на прямой |
|
перегонки и |
100 ты с. л. и зопетона. В |
результатесмеш и вани я эти х четы рех |
|
компонентов |
в разны х пропорц и ях |
образуется три |
сорта ави ац и онного |
бензи на: бензи нА – 2:3:5:2, бензи нВ |
– 3:1:2:1, бензи нС– 2:2:1:3. Стои мость |
1 ты с. л. указанны х сортов бензи нахарактери зуется чи слами : 120 р., 100 р., 150 р.
∙О предели тьплан смеш ени я компонентов, при котором будетдости гнута макси мальная стои мостьвсей продукц и и .
∙ О предели ть опти мальны й план смеш ени я и з услови я макси мального и спользовани я компонентов.
86
11. Д ля и зготовлени я определенного сплаваи з сви нц а, ц и нкаи олова и спользуется сы рье в ви де следую щ и х пяти сплавов и з тех же металлов,
отли чаю щ и хся составом и стои мостью |
|
1 кг. |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
Сплав |
|
|
Содержани ев% |
|
|
|
|
||
К омпонен |
I |
|
II |
|
III |
IV |
|
V |
|
|
|
|
|
|
|
|
|
|
|
ты |
|
|
|
|
|
|
|
|
|
Сви нец |
10 |
|
10 |
|
40 |
60 |
|
30 |
|
Ц и нк |
10 |
|
30 |
|
50 |
30 |
|
20 |
|
О лово |
80 |
|
60 |
|
10 |
10 |
|
50 |
|
Стои мость |
4 |
|
4,5 |
|
5,8 |
6,0 |
|
7,5 |
|
∙О предели ть, сколько |
нужно |
взять сплава |
каждого ви да, |
чтобы |
|||||
и зготови тьсми ни мальной себестои мостью |
сплав, содержащ и й 20% |
||||||||
сви нц а, 30% ц и нкаи 50% олова. |
|
|
|
|
∙Реш и ть ту же задачу, если для нового сплава задаю тся следую щ и е ограни чени я: оловаот40 до 60% и ц и нкаот20 до 30%.
∙Реш и тьту жезадачу при следую щ и х ограни чени ях насостав сплава:
олованеболее405 и ц и нка– неменее20%. |
|
|
|
12. И з четы рех |
ви дов основны х матери алов (медь, |
ц и нк, |
сви нец , |
ни кель) составляю т три |
ви да сплава латуни : обы чны й, спец и альны й и для |
||
художественны х и здели й. Ц ены еди ни ц ы весамеди , ц и нка, |
сви нц а, |
ни келя |
составляю т0.8 р., 0.6 р., 0.4 р., 1 р., аеди ни ц ы весасплавасоответственно: 2 р., 3 р., 4 р.
Сплав для художественны х и здели й должен содержать не менее 6% ни келя, неменее50% меди и неболее30% сви нц а; спец и альны й – неменее 4% ни келя, неменее70% меди , неменее10% ц и нкаи неболее20% сви нц а. В обы чны й сплавкомпоненты могутвходи тьбез ограни чени й.
Прои зводственная мощ ность предпри яти я позволяет вы пускать (за определенны й срок) неболее400 еди ни ц весаобы чного сплава, неболее700
еди ни ц |
весаспец и ального сплаваи |
неболее100 еди ни ц весадекорати вного |
сплава. |
Н айти прои зводственны й |
план, обеспечи ваю щ и й макси маль-ную |
при бы ль.
12. Д ля и зготовлени я брусьевтрех размеров: 0.6 м., 1.5 м., 2.5 м. В соотнош ени и 2:1:3 нараспи лпоступаю тбревнадли ной в3 м. О предели ть планраспи ла, обеспечи ваю щ и й макси мальноечи сло комплектов.
Л И Т Е РА Т У РА
Основная:
1.А ттетков А . В . М етоды опти ми зац и и / А . В . А ттетков, С.В . Галки н, В .С.
Заруби н.- М |
.: И зд-во М ГТ У и м. Баумана, 2001.- 480 с. |
2. ГаллеевЭ . |
. К урслекц и й по вари ац и онному и счи слени ю и |
опти мальному управлени ю .-М .: И зд-во М ГУ , 1996.-160 с.
87
3.К ури ц ки й Б.Я . Пои скопти мальны х реш ени й средствами EXCEL 7.0. – СПб.: BHV-Санкт-Петербург,1997.- 280 с.
4. |
Л етоваТ .А . М етоды опти ми зац и и в |
при мерах и задачах/ Т .А .Л етова, |
|
А .В . Пантелеев.-M.: В ы сш ая ш кола, |
2002.- 544 с. |
5. |
Л еси нВ .В О сновы методовопти ми зац и и : У чеб. пособи е/ В .В . Л еси н, |
|
|
Ю .П. Л и совец . - М .: И зд-во М А И , 1998. - 344 с. |
Допол нит ел ьная:
1. |
А ш манов С.А . Т еори я опти ми зац и и взадачах и упражнени ях/ С.А . |
||
|
А ш манов, А .В . Т и мохов. - М .: Н аука, 1991.- 448 с. |
||
2. |
Базара |
. Н ели нейноепрограмми ровани е. Т еори я и алгори тмы ./ М . |
|
|
Базара, К . Ш |
етти - М .: М и р, 1982. -583 с. |
|
3. |
Бати щ евД .И |
О пти ми зац и я вСА ПР/ Д .И . Бати щ ев, Я .Е . Л ьвови ч, В .Н .. |
|
|
Ф ролов.- |
В оронеж: И зд-во В ГТ У , 1997 - 541 c. |
|
4. |
Ги ллФ . Практи ческая опти ми зац и я/ Ф .Ги лл, У . М ю ррей, М . Райт.- М .: |
М и р, 1985.-509 с.
5.Реклейти сГ. О пти ми зац и я втехни ке. / Г. Реклейти с, А . Рейви ндран,
К .Рагcдел: В 2 т. - М .: М и р, 1986.