Copyright (C) 2009 Gergely Mádi-Nagy.
Permission is granted to copy, distribute
and/or modify this document
under the terms of the GNU
Free Documentation License, Version 1.3
or any later version published by the Free Software
Foundation;
with the Invariant Sections being title and author, no Front-Cover Texts, and no Back-Cover Texts.
A copy of the license is included in the
section entitled "GNU
Free Documentation License".
Példa egy szöveges feladat Solverrel
történõ megoldására
Szerző: Mádi-Nagy Gergely (BME Diff.egyenletek Tsz., ELTE TTK Operációkutatási Tsz.)
A feladat szövege:
Egy ruhagyár ötféle ruházati terméket gyárt, melyekhez különféle erőforrásokat használ fel. Egy adott időszakban felhasználható erőforrások mennyiségét (erőforrások kapacitása), a termékek fajlagos erőforrásigényét és a termékek darabján keletkező nyereséget (fajlagos nyereség) az alábbi táblázatban foglaltuk össze.
|
Erőforrások |
Termékek |
Erőforrások kapacitása |
||||
|
Nadrág |
Zakó |
Blúz |
Ing |
Szoknya |
||
|
1. szövet (m) 2. szövet (m) 3. szövet (m) Cérna (m) Munkaóra |
2,3 0,4 0 20 0,5 |
3,1 1,1 0,5 40 1 |
0 0,5 1,2 10 0,3 |
0 0 2,0 15 1 |
1,9 1,3 0,5 15 0,4 |
300 400 120 4000 100 |
|
Fajlagos nyereség (Ft) |
2000 |
4000 |
600 |
1500 |
1800 |
|
A feladat: Mennyit termeljen a gyár az egyes termékekből, ha az a célja, hogy nyeresége maximális legyen?
A feladat megoldása
A probléma modellje:
x1: A legyártandó nadrágok száma
x2: A legyártandó zakók száma
x3: A legyártandó blúzok száma
x4: A legyártandó ingek száma
x5: A legyártandó szoknyák száma
|
2,3 x1 |
+3,1 x2 |
+0 x3 |
+0 x4 |
+1,9 x5 |
≤ |
300 |
|
0,4 x1 |
+1,1 x2 |
+0,5 x3 |
+0 x4 |
+1,3 x5 |
≤ |
400 |
|
0 x1 |
+0,5 x2 |
+1,2 x3 |
+2,0 x4 |
+0,5 x5 |
≤ |
120 |
|
20 x1 |
+40 x2 |
+10 x3 |
+15 x4 |
+15 x5 |
≤ |
4000 |
|
0,5 x1 |
+1 x2 |
+0,3 x3 |
+1 x4 |
+0,4 x5 |
≤ |
100 |
x1, x2, x3, x4, x5 ≥0
|
2000x1 |
+4000x2 |
+600x3 |
+1500x4 |
+1800x5 |
->max |
Az optimum
meghatározása:
Az optimális megoldás megkereséséhez, illetve a további vizsgálatokhoz az Excel Solver programját vettem segítségül. A megtalált optimális megoldáshoz tartozó eredményjelentés így nézett ki:
|
Célcella
(Max) |
|
|
|
|
||
|
|
Cella |
Név |
Eredeti
érték |
Végérték |
|
|
|
|
$B$24 |
Profit
(Ft) |
0 |
382558,1395 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Módosuló
cellák |
|
|
|
|
||
|
|
Cella |
Név |
Eredeti
érték |
Végérték |
|
|
|
|
$C$16 |
Nadrág
(db) |
0 |
15,50387597 |
|
|
|
|
$D$16 |
Zakó
(db) |
0 |
85,27131783 |
|
|
|
|
$E$16 |
Blúz
(db) |
0 |
0 |
|
|
|
|
$F$16 |
Ing
(db) |
0 |
6,976744186 |
|
|
|
|
$G$16 |
Szoknya
(db) |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Korlátozó
feltételek |
|
|
|
|
||
|
|
Cella |
Név |
Cellaérték |
Képlet |
Status |
Eltérés |
|
|
$B$18 |
1.
szövet (m) |
300 |
$B$18<=$I$5 |
Éppen |
0 |
|
|
$B$19 |
2.
szövet (m) |
100 |
$B$19<=$I$6 |
Éppen |
0 |
|
|
$B$20 |
3.
szövet (m) |
56,58914729 |
$B$20<=$I$7 |
Bőven |
63,41085271 |
|
|
$B$21 |
Cérna
(m) |
3825,581395 |
$B$21<=$I$8 |
Bőven |
174,4186047 |
|
|
$B$22 |
Munka
(óra) |
100 |
$B$22<=$I$9 |
Éppen |
0 |
A megoldás
értelmezése:
A gyár akkor tesz szert maximális profitra, ha az adott időszak alatt átlagosan (mivel nem egész szám jött ki) 15,50387597 darab nadrágot, 85,27131783 darab zakót, 6,976744186 inget, a többi termékből pedig semennyit sem gyárt. Ekkor a maximális profit nagysága 382558,1395 Ft. Az optimális termelés során az 1., 2. szövetből és munkaórából az összes rendelkezésre álló mennyiséget felhasználja.
A feladat duálisa:
|
2,3 y1 |
+0,4 y2 |
+0 y3 |
+20 y4 |
+0,5 y5 |
≥ |
2000 |
|
3,1 y1 |
+1,1 y2 |
+0,5 y3 |
+40 y4 |
+1 y5 |
≥ |
4000 |
|
0 y1 |
+0,5 y2 |
+1,2 y3 |
+10 y4 |
+0,3 y5 |
≥ |
600 |
|
0 y1 |
+0 y2 |
+2,0 y3 |
+15 y4 |
+1 y5 |
≥ |
1500 |
|
1,9 y1 |
+1,3 y2 |
+0,5 y3 |
+15 y4 |
+0,4 y5 |
≥ |
1800 |
y1, y2, y3, y4, y5 ≥0
|
300y1 |
+400y2 |
+120y3 |
+4000y4 |
+100y5 |
->min |
A duális értelmezése:
Tegyük fel, hogy valaki fel szeretné vásárolni a gyár erőforrásait (kapacitásait). Jelölje az yi változó azt az árat amennyit a vásárló ajánl fel az i-edik erőforrásért. Ezeket az árakat árnyékáraknak nevezzük.
A duális feladat korlátozó egyenlőtlenségei azt biztosítják, hogy az ajánlott árak versenyképesek legyenek. Például az első egyenlőtlenség azt mondja, hogy egy nadrág alapanyagaiért kifizetett ár ne legyen kisebb a nadrágon nyert profitnál. Ez azért fontos, mivel ellenkező esetben a gyár még akkor is jobban járna az erőforrások eladásánál, ha csak nadrágot gyártana.
A célfüggvény értéke az összes erőforrásért felajánlott összeg. A minimalizálás az erőforrás vásárlójának érdekeit tükrözi, tehát azt, hogy az erőforrásokat minél olcsóbban tudja megvenni.
A primál-duál tétel:
Az eredeti (primál) feladat célfüggvényértéke nem lehet nagyobb a duál feladat célfüggvényértékénél. Ha a primálfeladatnak van optimális megoldása, akkor a duálnak is, és a két optimális célfüggvényérték megegyezik. Az első mondatban szereplő matematikai állítást logikusan tükrözi a duális értelmezésében leírt szituáció (a gyár és az erőforrást vevő viszonya). A második mondatot alátámasztja a duális feladat megoldása, amely az Excel Solver érzékenység jelentésében az árnyékáraknál található. A feladatra az alábbi érzékenység jelentést kaptuk:
|
Módosuló
cellák |
|
|
|
|
|
||
|
|
|
|
|
Redukált |
Objective |
Megengedhető |
Megengedhető |
|
|
Cella |
Név |
Végérték |
költség |
Célegyüttható |
növekedés |
csökkenés |
|
|
$C$16 |
Nadrág
(db) |
15,50387597 |
0 |
2000 |
480 |
340,9090909 |
|
|
$D$16 |
Zakó
(db) |
85,27131783 |
0 |
4000 |
937,5 |
646,9565217 |
|
|
$E$16 |
Blúz
(db) |
0 |
-576,744186 |
600 |
576,744186 |
1E+30 |
|
|
$F$16 |
Ing
(db) |
6,976744186 |
0 |
1500 |
2153,225806 |
1500 |
|
|
$G$16 |
Szoknya
(db) |
0 |
-1241,860465 |
1800 |
1241,860465 |
1E+30 |
|
|
|
|
|
|
|
|
|
|
Korlátozó
feltételek |
|
|
|
|
|
||
|
|
|
|
|
Shadow |
Feltétel |
Megengedhető |
Megengedhető |
|
|
Cella |
Név |
Végérték |
Árnyékár |
jobb
oldala |
növekedés |
csökkenés |
|
|
$B$18 |
1.
szövet (m) |
300 |
290,6976744 |
300 |
60 |
18,18181818 |
|
|
$B$19 |
2.
szövet (m) |
100 |
1453,488372 |
100 |
6,451612903 |
47,82608696 |
|
|
$B$20 |
3.
szövet (m) |
56,58914729 |
0 |
120 |
1E+30 |
63,41085271 |
|
|
$B$21 |
Cérna
(m) |
3825,581395 |
0 |
4000 |
1E+30 |
174,4186047 |
|
|
$B$22 |
Munka
(óra) |
100 |
1500 |
100 |
11,62790698 |
6,976744186 |
A duál feladat megoldását, mint említettük, az árnyékárak adják meg. Eszerint az erőforrásokat megvásárolni szándékozó akkor jár a legjobban, ha az 1. szövet méteréért 290,697644 forintot, a 2. szövet méteréért 1453,488372 forintot, egy munkaóráért pedig 1500 forintot ajánl (természetesen a gyakorlatban ezen összegek forintra való kerekítéséről lenne szó). Ekkor az ő vásárlással járó minimális költsége 382558,1395 forint lenne, amely megegyezik a gyár maximális profitjával.
Érzékenység vizsgálat:
Az érzékenység jelentésben a „Módosuló cellák” táblázat utolsó két oszlopa arról ad információt, hogy az egyes termékek darabjához tartozó fajlagos nyereségek mekkora változtatása esetén kapjuk még mindig ugyanazt az optimális megoldást. Eszerint csak akkor kéne változtatni a termelésen, ha
· vagy a nadrág darabjának fajlagos nyeresége több mint 480 forinttal nő, vagy több mint 340,9090909 forinttal csökken,
· vagy a zakó darabjának fajlagos nyeresége több mint 937,5 forinttal nő, vagy több mint 646,9565217 forinttal csökken,
· vagy a blúz darabjának fajlagos nyeresége több mint 576,744186 forinttal nő (ha csökken, akkor nem változik az optimális termelés),
· vagy a ing darabjának fajlagos nyeresége több mint 2153,225806 forinttal nő, vagy több mint 1500 forinttal csökken,
· vagy a szoknya darabjának fajlagos nyeresége több mint 1241,860465 forinttal nő (ha csökken, akkor nem változik az optimális termelés).
A „Korlátozó feltételek” című táblázat utolsó két oszlopa arról ad információt, hogy az erőforrások kapacitása meddig változtatható úgy, hogy a primál feladat optimális megoldás bázisa ne változzék. Tehát továbbra is csak a nadrágot, zakót és inget kell gyártani abban az esetben, ha
· vagy az 1. szövet (adott időszakban rendelkezésre álló) mennyisége kevesebb mint 60 méterrel nő, vagy kevesebb mint 18,18181818 méterrel csökken,
· vagy az 2. szövet mennyisége kevesebb mint 6,451612903 méterrel nő, vagy kevesebb mint 47,82608696 méterrel csökken,
· vagy az 3. szövet mennyisége kevesebb mint 63,41085271 méterrel csökken (nőni bármeddig nőhet),
· vagy a cérna mennyisége kevesebb mint 174,4186047 méterrel csökken (nőni bármeddig nőhet),
· vagy a rendelkezésre álló munka mennyisége kevesebb mint 11,62790698 órával nő, vagy kevesebb mint 6,976744186 órával csökken.
A termelés határai
A „Határok jelentés”-ben kapott alsó táblázat megmutatja, hogy az optimális termelésből kiindulva egy-egy termék termelt mennyisége (a többi termelését változatlanul hagyva) milyen határok közt mozoghat, és emellett mekkora lenne a profit értéke.
|
|
Módosuló |
|
|
Alsó |
Cél |
|
Felső |
Cél |
|
Cella |
Név |
Végérték |
|
határ |
eredmény |
|
határ |
eredmény |
|
$C$16 |
Nadrág
(db) |
15,50387597 |
|
0 |
351550,3876 |
|
15,50387597 |
382558,1395 |
|
$D$16 |
Zakó
(db) |
85,27131783 |
|
0 |
41472,86822 |
|
85,27131783 |
382558,1395 |
|
$E$16 |
Blúz
(db) |
0 |
|
0 |
382558,1395 |
|
0 |
382558,1395 |
|
$F$16 |
Ing
(db) |
6,976744186 |
|
0 |
372093,0233 |
|
6,976744186 |
382558,1395 |
|
$G$16 |
Szoknya
(db) |
0 |
|
0 |
382558,1395 |
|
0 |
382558,1395 |
Tehát például Zakóból 0 és 85,27131783 darab közt termelhetünk. Ha nem termelünk belőle, akkor a profit 41472,86822, ha a felső határnak megfelelő terméket állítunk elő, akkor a profit a maximális értékkel megegyező.