Eötvös Loránd Tudományegyetem Természettudományi Kar
Optimalizálás a Microsoft Excel Solver b®vítménye segítségével Szakdolgozat
Tóth Ádám Matematika B.Sc., elemz® szakirány
Témavezet®:
Mádi-Nagy Gergely,
egyetemi adjunktus
Operációkutatás Tanszék
Budapest 2011
Tartalomjegyzék
1. Bevezetés
3
2. A Microsoft Excel Solver használata
4
3. Lineáris programozás 3.1.
3.2.
3.3.
3.4.
Termelési feladat
10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1.
Modell felírása
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.1.2.
Megoldás Solver segítségével . . . . . . . . . . . . . . . . . . . . . .
11
3.1.3.
Megoldás elemzése
. . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Szállítási feladat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.2.1.
Modell felírása
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.2.2.
Megoldás Solver segítségével . . . . . . . . . . . . . . . . . . . . . .
18
3.2.3.
Megoldás elemzése
. . . . . . . . . . . . . . . . . . . . . . . . . . .
19
Hozzárendelési feladat
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.3.1.
Modell felírása
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.3.2.
Megoldás Solver segítségével . . . . . . . . . . . . . . . . . . . . . .
23
3.3.3.
Megoldás elemzése
24
. . . . . . . . . . . . . . . . . . . . . . . . . . .
Minimális költség¶ hálózati folyam problémák
. . . . . . . . . . . . . . . .
25
3.4.1.
Modell felírása
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.4.2.
Megoldás Solver segítségével . . . . . . . . . . . . . . . . . . . . . .
28
3.4.3.
Megoldás elemzése
29
. . . . . . . . . . . . . . . . . . . . . . . . . . .
4. Nemlineáris programozás 4.1.
11
Folytonos feladat
32
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
4.1.1.
Modell felírása
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.1.2.
Megoldás Solver segítségével . . . . . . . . . . . . . . . . . . . . . .
34
1
4.1.3. 4.2.
Megoldás elemzése
. . . . . . . . . . . . . . . . . . . . . . . . . . .
35
Nem folytonos feladat
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.2.1.
Modell felírása
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.2.2.
Megoldás Solver segítségével . . . . . . . . . . . . . . . . . . . . . .
36
4.2.3.
Megoldás elemzése
37
. . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1. fejezet
Bevezetés
Lehet®ségeihez mérten az ember mindig törekedett a legjobb eredmény elérésére. Legyen az egy gyár autógyártásából származó bevétel, vagy a fogyasztó oldaláról nézve az autó ár-érték arányának minimalizálása. Nap mint nap optimalizációs problémákkal találjuk szembe magunkat, még ha nem is vesszük észre. Elég ha csak egy átlagos bevásárlásra gondolunk.
Persze a megoldandó feladatok nagysága és súlya nem ugyanakkora.
Vilá-
gos, hogy a kisboltban vásárolható két tej között könnyebb választani, mintha egy lakást szeretnénk venni, vagy akár egy nagyvállalat vezetésével vagyunk megbízva és döntéseinken komoly bevételek múlnak. Itt jön a kérdés: hogyan is tudnánk de niálni ezt az egész folyamatot? Az optimalizálás a gazdasági er®forrásokkal való ésszer¶ gazdálkodás, a legjobb állapot illetve cselekvés kiválasztására alkalmas eljárás, valamely el®re meghatározott feltételek alapján. A gyorsaság és pontosság mindig is nagy szerepet kapott az optimalizálásban. Számítógépünk segítségével hatékonyabban tudunk megoldani nagyméret¶ problémákat, vagy akár olyanoknak is meg tudjuk adni eredményét, amelyeket szinte lehetetlen lenne papíron kiszámolni.
Ezt a célt szolgálja a Microsoft Excel Solver b®vítménye.
Ennek a
programnak az a m¶ködési elve, hogy a megszorítások gyelembevételével megvizsgálja a lehetséges megoldásokat, majd azok közül kiválasztja a számunkra legkedvez®bbet. Egy feladatnak lehet egy, több vagy akár végtelen sok optimális megoldása, de el®fordulhat az is, hogy egy sincs. A kés®bbiekben minden problématípusnál ismertetni fogjuk a modell fontosabb tulajdonságait egy feladat segítségével, amelyet a Solverrel megoldunk, majd a kapott eredményeket, jelentéseket kielemezzük. A példafeladatokat Wayne L. Winston Operációkutatás - Módszerek és alkalmazások cím¶ könyvéb®l merítettem.
3
2. fejezet
A Microsoft Excel Solver használata
A Solver használatát egy feladat segítségével mutatjuk be a könnyebb megértés kedvéért.
2.1. Feladat. Giapetto fafaragó cége kétfajta fából készült játékot gyárt: katonákat és vonatokat. Egy katonát 27$-ért lehet eladni, és el®állításához 10$ érték¶ nyersanyag szükséges. Minden legyártott katona 14 dollárral növeli Giapetto bérben jelentkez® változó költségét és az általásnos költséget. Egy vonat 21$-ért adható el, el®állításához 9$ érték¶ nyersanyag szükséges. Minden legyártott vonat 10 dollárral növeli a változó- és általános költségeket. A fakatonák és favonatok gyártása kétféle szakképzett munkát igényel: fafaragó és felületkezel® munkát. Egy katona el®állításához 2 óra felületkezel® munka és 1 óra fafaragó munka szükséges. Egy vonathoz 1 óra felületkezel® és 1 óra fafaragó munka kell. Giapettonak minden héten korlátlan mennyiség¶ nyersanyag áll rendelkezésére, de csak 100 felületkezel® munkaóra és 80 fafaragó munkaóra használható fel. A vonatok iránti kereslet korlátlan, katonákból azonban legfeljebb csak 40-et vesznek meg hetente. Maximalizáljuk Giapetto heti pro tját (bevétel - költségek)!1 Els® lépésként írjuk fel a feladatunk matematikai modelljét. Döntési változók:
x1 = ahány
katonát gyárt egy héten
x2 = ahány
vonatot gyárt egy héten
Korlátozó feltételek:
2 · x1 + x2 ≤ 100 1 Wayne L. Winston:
Operációkutatás,
Aula
, 2003, 51. oldal
4
x1 + x2 ≤ 80 x1 ≤ 40 El®jelkorlátozó feltételek:
x1 ≥ 0 x2 ≥ 0 Célfüggvény:
max
z = (27 − 10 − 14) · x1 + (21 − 9 − 10) · x2 = 3 · x1 + 2 · x2
A matematikai modell felírása után nyissunk meg egy új Excel munkalapot. Az els® sorban feltüntetjük a döntési változók jelöléseit. Ezt nem kötelez® megtennünk, mivel a program nem fogja a táblázatnak ezt a részét használni, viszont nekünk hasznos lehet átláthatóság szempontjából. Az alatta lév® sorban rögzítjük a kezd®értékeket (pl. 0), a megoldás során ezek az értékek változnak meg. A modellünkb®l kiszedjük az együtthatókat és rögzítjük a táblánkban. A relációkat csak az áttekinthet®ség kedvéért tüntetjük fel. Kiszámoljuk a korlátozó feltételek baloldalának értékét az adott változóértékek mellett.
5
A célfüggvény értékét is a változók függvényében számoljuk ki.
A feladatunkat rögzítettük a táblánkban, ezek után megoldást keresünk a Solver segítségével, amelyet az Adatok menü Solver parancsával futtathatunk. Az el®ugró ablakban megadjuk a célcella valamint a módosuló cellák helyét, kiválasztjuk, hogy maximalizálni vagy minimalizálni szeretnénk a célfüggvényünket és rögzítjük a korátozó feltételeinket.
6
A feltételeket az alábbi párbeszédpanel segítségével vehetjük fel, amelyet a fenti ablakon lév® Hozzáadás gomb segítségével hívhatunk el®.
A Beállítás gombra kattintva szintén egy párbeszédpanel ugrik el®, amelynek segítségével kiválaszthajuk a számunkra legkedvez®bb megoldó algoritmust.
A Max.
id®-
nél megadjuk, hogy mennyi id® után álljon le a megoldás keresésével a program.
A
Lépésszám mez®nél beírjuk, hogy maximálisan hány közelítést szeretnénk végrehajtani. A Pontosság-nál minél kisebb számot tüntetünk fel, annál nagyobb lesz a pontosság. A kívánt t¶rést százalékban tudjuk megadni. A Konvergencia mez®ben adjuk meg, hogy az utolsó öt iterációban mekkora relatív változást engedünk meg addig, amíg a Solver a megoldást megtalálva le nem áll. A jelöl®négyzeteknél be tudunk állítani további tulajdonságokat: lineáris modell, nemnegatív feltételezése, nagyságrendek felismerése, kijelzés lépésenként, amelyek közül elnevezésükb®l kifolyólag csak az utolsó kett® szorul némi magyarázatra.
A nagyságrend
felismerésére akkor van szükségünk, ha bizonyos bemeneti értékek több nagyságrenddel különböznek, vagy pedig az input és az output tér el egymástól nagy mértékben. A lépések kijelzésével pedig minden lépés eredményét megvizsgálhatjuk. A Solver az általánosított redukált gradiens (GRG - Generalized Reduced Gradient) módszert használja nem lineáris problémák optimalizálása során, míg lineáris esetben a szimplex és a branch and bound (elágazás és korlátozás) módszereket alkalmazza. A rádiógombok segítségével tovább tudjuk alakítani megoldó algoritmusunkat.
A
Közelítés-nél az egydimenziós keresési eljárásokban az alapváltozók kezdeti értékének becslésére használt módszert határozhatjuk meg.
Ha az érint®t választjuk, akkor az
értéket az érint® lineáris függvényeként írjuk fel, ha a kvadratikusat, akkor négyzetes extrapolációt alkalmazunk. A Dierenciák beállítás segítségével meghatározhatjuk, hogy a cél- és a feltételfüggvények parciális deriváltjainak becslésére a haladó vagy centrális dierenciálás módszerét használja-e a program.
El®bbit alkalmazzuk, ha a korlátozó
feltételek függvényértékei nem változnak túl gyorsan, utóbbit ha ennek ellentéte áll fenn.
7
A Keresés-nél a keresési irányt meghatározó módszert választjuk ki. A Newton módszer általában több memóriát, de kevesebb lépésszámot igényel, mint a konjugált gradiens módszer. Utóbbi nagyobb problémák esetén ajánlott, ahol számít a felhasznált memória.
Az algoritmusunk beállítása után az OK gombra kattintva visszatérünk a paramétereket tartalmazó ablakhoz. Itt már nincs más teend®nk, mint megnyomni a Megoldás gombot.
Amennyiben jól állítottuk be eljárásunkat, a Solver közli velünk, hogy op-
timális megoldást talált, vagy az nem is létezik esetleg több is van bel®le.
Ha hibát
vélünk felfedezni, mondjuk a program megállt, miel®tt megoldást talált volna vagy nem az elvárt eredmény keletkezett, akkor érdemes visszatekinteni a beállításokhoz, és leellen®rizni azokat. A jelentések közül kiválaszthatjuk, hogy melyeket szeretnénk megvizsgálni. Ezek részletes magyarázatára a példákon keresztül kerül sor.
8
Ezután az OK gomb megnyomásával a D16 cellában megjelenik Giapetto heti pro tjának maximuma, az A2 és B2 mez®kben pedig a katonák és vonatok gyártásának optimális száma.
9
3. fejezet
Lineáris programozás
Számos optimalizálási problémában segítségül szolgál a lineáris programozás. A gazdaság szinte minden területén alkalmazzák a legjobb eredmény elérésének érdekében, például pénzügyi, termelési, szállítási, munkaszervezési problémák esetén.
3.1. De níció. A lineáris programozási feladat (LP) egy olyan optimalizálási feladat, amelyben a következ®k történnek: 1. Maximalizáljuk (vagy minimalizáljuk) a döntési változók egy lineáris függvényét. A maximalizálandó vagy minimalizálandó függvényt célfüggvénynek nevezzük. 2. A döntési változók értékeinek ki kell elégíteniük a korlátozó feltételeket. Minden feltételnek vagy lineáris egyenletnek vagy lineáris egyenl®tlenségnek kell lennie. 3. Minden változóhoz tartozik egy el®jelkorlátozás (vagy annak hiánya). Bármely xi változóra az el®jelkorlátozás vagy azt írja el®, hogy xi csak nemnegatív lehet (xi ≥ 0), vagy azt írja el®, hogy xi el®jelkorlátozatlan. A megoldandó feladataink modelleinek el®állításához a következ® néhány alapfogalmat kell megismernünk: döntési változók, célfüggvény, korlátozó feltételek. A döntési változó azt a célt szolgálja, hogy le tudjuk írni a jöv®ben meghozandó döntéseket. Például az évente el®állított televíziók száma vagy a naponta betakarított búza mennyisége. A célfüggvényt a döntési változók súlyozásával állítjuk el®, amelyet minimalizálni vagy maximalizálni szeretnénk. Például egy gyárnál a lehet® legnagyobb pro t elérése vagy a ráfordítások minimalizálása. A korlátozó feltételek megszabnak bizonyos határokat a feladatnak. Például a rendelkezésre álló nyersanyag mennyisége, a munkaid® korlátozása.
10
3.1. 3.1.1.
Termelési feladat Modell felírása
3.1. Feladat. Jones farmernek el kell döntenie, hogy ebben az évben hány hold kukoricát és hány hold búzát ültessen. Egy hold hozama 25 mázsa búza, és ez az egy hold heti 10 óra munkát igényel. Egy hold hozama 10 mázsa kukorica, és ez az egy hold heti 4 óra munkát igényel. A búza mázsánként 4$-ért adható el, és a kukorica eladási ára 3$ mázsánként. A farmernak hét hold földje van és heti 40 munkaóra áll rendelkezésére. Kormányzati el®írás értelmében ebben az évben legalább 30 mázsa kukoricát kell termelni. Maximalizáljuk a búzából és kukoricából származó teljes jövedelmet!1 Döntési változók:
x1 = ahány x2 = ahány
hold búzát ültet
hold kukoricát ültet
Korlátozó feltételek:
x1 + x2 ≤ 7 10 · x1 + 4 · x2 ≤ 40 10 · x2 ≥ 30 El®jelkorlátozó feltételek:
x1 ≥ 0 x2 ≥ 0 Célfüggvény:
max
3.1.2.
z = 4 · 25 · x1 + 3 · 10 · x2 = 100 · x1 + 30 · x2
Megoldás Solver segítségével
A matematikai modellünket már elkészítettünk, keressünk optimális megoldást a Solver segítségével! A feljebb leírtak fényében töltsünk fel egy táblát az együtthatókkal, adjuk meg a Solver paramétereket (célcella, módosuló cellák, korlátozó feltételek), majd a megoldó
1 Wayne L. Winston:
Operációkutatás,
Aula
, 2003, 58. oldal
11
algoritmusunk beállítását is végezzük el. Esetünkben a jelöl®négyzeteknél a lineáris modell és a nemnegatív feltételezéseket kell alkalmaznunk.
El®bbit használva megjegyzend®,
hogy a nemlineáris eszközök (közelítés, dierenciák, keresés) beállításai ekkor már nem mérvadóak.
A Megoldás gombra kattintva elkészíthetjük a jelentéseket, valamint a
megfelel® cellákban megjelennek az optimális megoldáshoz tartozó értékek.
3.1.3.
Megoldás elemzése
A táblázatunkban mind a döntési változók, mind a célfüggvény optimális értéke megjelent. A megoldás szerint 2,8 hold búzát és 3 hold kukoricát kell Jones farmernek ültetni a teljes jövedelem maximalizálásához, amely 370$-t jelent.
Az eredmény, érzékenység, határok
jelentések három különböz® munkalapra generálódtak. Az eredmény jelentés három kisebb táblázatból áll. A Célcella és a Módosuló cellák tartalmazzák a feladat megoldását, amelyet már az imént említettünk. feltételek-nél a kritériumokra vonatkozó adatokat láthatjuk.
A Korlátozó
A Status oszlopban két
érték jelenhet meg. Az Éppen azt jelzi, hogy az adott feltétel határán vagyunk, tehát
≤
vagy
≥
estén teljesül az egyenl®ség, egyéb esetben B®ven jelenik meg. Az Eltérés
12
oszlopból kiolvashatjuk, hogy az optimális megoldáshoz tartozó baloldal és a jobboldal milyen mértékben tér el egymástól.
Tehát ezek tükrében a következ®ket állapíthatjuk
meg:
•
a farmer 7 hold földb®l csak 5,8 holdat ültet be, amelyek különbségét az Eltérés-nél láthatjuk, számszerint 1,2.
•
a rendelkezésre álló heti 40 munkaórának maximális a kihasználtsága.
•
a kormányzati el®írásnak megfelel®en, Jones éppen eléri az elvárt, legalább 30 mázsányi kukorica termelést.
Az érzékenység jelentésb®l nyert adatok segítségével egy feladatot nem feltétlenül kell újra megoldanunk, ha egy paraméter megváltozik. Ez akkor lehet kifejezetten hasznos számunkra, amikor egy jóval nagyobb problémát kell optimalizálnunk. Az érzékenységvizsgálat elemzése lehet®séget nyújt, hogy az eredeti megoldásból megállapítsuk, hogy a paraméterek változtatására miképp változik eredményünk. A Módosuló cellák táblázatban szerepl® Redukált költség a szimplex tábla alsó sorának értékeire utal. A Megengedhet® növekedés/csökkenés oszlopok a megfelel® célfüggvény együttható változásainak azon határait adják meg, melyen belül a feladat optimális megoldása nem változik (természetesen a célfüggvény értéke igen), míg a másik táblázatban szerepl® azonos elnevezés¶ oszlopok a megfelel® feltétel jobboldala változatásainak azon határait adják meg, melyen belül az optimális bázis nem változik.
13
3.2. De níció. Ha az i-edik korlátozó feltétel jobb oldalának növelése nem módosítja az optimális bázist, akkor egy LP feladat i-edik korlátozó feltételéhez tartozó árnyékár az az érték, amennyivel az optimális z érték javul (maximumfeladat esetén a javulás növekedést, minimumfeladat esetén pedig csökkenést jelent), amikor az i-edik korlátozó feltétel jobb oldalát 1-gyel növeljük. Írjuk fel modellünket a következ® alakban: Célfüggvény: max
z = c1 · x 1 + c2 · x 2
Korlátozó feltételek:
x1 + x2 ≤ k1 10 · x1 + 4 · x2 ≤ k2 10 · x2 ≥ k3 Ekkor a lenti táblázatokból a következ®ket sz¶rhetjük ki:
•
A feladat optimális megoldása nem változik, ha (a felsoroltak közül egyszerre csak egy változtatható meg):
◦ 75 ≤ c1 < ∞. ◦ −∞ < c2 ≤ 40. •
Az optimális bázis nem változik, ha (a felsoroltak közül egyszerre csak egy változtatható meg):
◦
5,8
≤ k1 < ∞.
◦ 12 ≤ k2 ≤ 52. ◦ 0 ≤ k3 ≤ 50. •
Ha az optimális bázis nem változik, akkor:
◦ k1 = 7 + 1 = 8
esetén max(z )=
370 + 0 = 370.
◦ k2 = 40 + 1 = 41
esetén max(z )=
370 + 10 = 380.
◦ k3 = 30 + 1 = 31
esetén max(z )=
370 − 1 = 369.
14
Csináljuk egy próba ellen®rzést a Solverrel, hogy ténylegesen igazak-e a fenti állítások. Az együtthatókat tartalmazó táblánkban növeljük meg a rendelkezésre álló munkaórák számát 1-gyel.
A többi paramatér változtatása nélkül a farmer így már heti 41 órát
dolgozhat.
15
Az érzékenységjelentésb®l kiolvasva a munkaóra feltétel árnyékára 10, tehát az alapfeladatra kapott maximális
z
értéknek ennyivel kellett n®nie, amelyet az ellen®rz® táblánkban
is láthatunk. A határok jelentésben az alsó, fels® határ és a hozzájuk tartozó Cél eredmény oszlopok hordoznak számunkra érdekes információkat. Az alsó és fels® határ elárulja, hogy az optimális megoldásból kiindulva a változóknak mekkora a legkisebb és legnagyobb felvehet® értékük a korlátozó feltételek teljesülése mellett, a Cél eredmény pedig meghatározza, hogy az adott pontban milyen értéket vesz fel a célfüggvény. Például estén (természetesen a többi paraméter változtatása nélkül)
3.2.
x1 = 0
z = 90.
Szállítási feladat
kínálati pontok azon pontok halmaza, amelyekb®l a szállítás történik, a keresleti pontok pedig azok, ahová a szállítás történik. A köztük zajló transzferálásnak költségét a változó költség írja le minden egyes kínálati-keresleti pontpárra külön-külön. Feladatunkban A szállítási feladat megoldásához meg kell ismernünk néhány alapfogalmat.
A
meghatározhatjuk, hogy a kínálati helyeinkr®l hány egységet vagyunk képesek szállítani, felvev® részr®l pedig a szükséges mennyiséget tudjuk meghatározni. A szállítási feladatnak alapvet®en három fajtája van. Az egyik amikor az összkínálat nagyobb az összkeresletnél, a másik amikor kisebb, a harmadik pedig ha megegyeznek. Utóbbi esetben kiegyensúlyozott szállítási feladatról beszélünk. Az els® két esetben bevezethetünk egy
ktív keresleti pontot,
amelynek célja a fel nem használt készlet vagy
a kielégítetlen kereslet jelzése. Utóbbi általában büntet®költséget von maga után.
16
3.2.1.
Modell felírása
3.2. Feladat. Egy vállalat három fogyasztónak szállít termékeket, mindegyiknek 30 egységet. A vállalatnak két raktára van. Az 1. raktárban 40 egység, a második raktárban pedig 30 egység áll rendelkezésre. Az alább látható táblázatban szerepelnek a raktárakból a fogyasztókhoz történ® szállítások egységköltségei ($-ban). Minden egyes kielégítetlen fogyasztói keresletegységhez bírság tartozik: az 1. vev®nél 90$ bírságköltség van, a 2. vev®nél 80$, a 3. vev®nél 110$. Minimalizáljuk a szállítási és hiányköltségek összegét.2
Döntési változók:
xij = az i-edik
raktárból a
j -edik
i = 1, 2 x3j = a j -edik
vev®höz szállított egységek száma, ha és
j = 1, 2, 3.
vev® kielégítetlen keresletegységének száma, ha
Korlátozó feltételek:
•
Kínálati feltételek:
x11 + x12 + x13 ≤ 40 x21 + x22 + x23 ≤ 30 •
Keresleti feltételek:
x11 + x21 + x31 ≥ 30 x12 + x22 + x32 ≥ 30 x13 + x23 + x33 ≥ 30 El®jelkorlátozó feltételek:
xij ≥ 0 2 Wayne L. Winston:
ha,
Operációkutatás,
i = 1, 2, 3
Aula
és
j = 1, 2, 3
, 2003, 294. oldal
17
j = 1, 2, 3.
Célfüggvény:
szállítási költségek min
z }| { z = 35 · x11 + 25 · x12 + 15 · x13 + 50 · x21 + 40 · x22 + 10 · x23 + +90 · x31 + 80 · x32 + 110 · x33 | {z } hiányköltségek
3.2.2.
Megoldás Solver segítségével
Ahogy azt eddig is tettük, töltsünk fel egy excel táblát az együtthatókkal. Kiszámoljuk a korlátozó feltételek baloldalának és a célfüggvény értékét az adott változóértékek mellett. A K18 mez®re kattintva ezt a képletet fogjuk látni a szerkeszt®lécben:
Adjuk meg a Solver paramétereket.
A célcella a K18 (ezt szeretnénk minimalizálni), a
módosuló cellák pedig az A2, B2, ..., I2 lesznek.
Felvesszük a korlátozó feltételeinket,
majd beállítjuk a lineáris modell és a nemnegatív feltételezéseket. A Megoldás gombra kattintva táblázatunkban megjelenik feladatunk optimális eredménye:
18
3.2.3.
Megoldás elemzése
Megoldásunk szerint a költségünk akkor lesz minimális, számszerint 3200$, ha az els® raktárból 10 egységet az 1-es, 30-at a 2-es vev®nek, a második raktárból a teljes készletet a 3-as vev®nek szállítjuk. Így 20 kiegyenlítetlen keresletegysége lesz az els® vev®nek, amely után járó büntetés a teljes költségünk 56,25%-át teszi ki. A továbbiakban eredmény jelentésb®l csak a korlátozó feltételek táblázatot fogom taglalni, mivel a másik kett® a kapott eredmény vizsgálata után már nem információérték¶.
A Status oszlop minden sorában az éppen értéket láthatjuk, ez elárulja,
hogy mindegyik feltételnek a határán vagyunk.
Írjuk fel modellünket a következ® alakban: Célfüggvény:
min
z = c11 · x11 + c12 · x12 + c13 · x13 + c21 · x21 + c22 · x22 + c23 · x23 + +c31 · x31 + c32 · x32 + c33 · x33
Korlátozó feltételek:
x11 + x12 + x13 ≤ k1 x21 + x22 + x23 ≤ k2 x11 + x21 + x31 ≥ k3 x12 + x22 + x32 ≥ k4 x13 + x23 + x33 ≥ k5 Ekkor az érzékenységvizsgálat segítségével a következ®ket állapíthajuk meg:
•
A feladat optimális megoldása nem változik, ha (a felsoroltak közül egyszerre csak egy változtatható meg):
19
•
◦ 35 ≤ c11 ≤ 55.
◦ 30 ≤ c21 < ∞.
◦ 35 ≤ c31 ≤ 90.
◦ −55 ≤ c12 ≤ 25.
◦ 20 ≤ c21 < ∞.
◦ 80 ≤ c32 < ∞.
◦ −5 ≤ c13 ≤ 55.
◦ −∞ < c23 ≤ 30.
◦ 70 ≤ c32 < ∞.
Az optimális bázis nem változik, ha (a felsoroltak közül egyszerre csak egy változtatható meg):
◦ 30 ≤ k1 ≤ 60.
◦ 10 ≤ k4 ≤ 40.
◦ 20 ≤ k2 ≤ 30.
◦ 30 ≤ k5 ≤ 40.
◦ 10 ≤ k3 < ∞. •
A
Ha az optimális bázis nem változik, akkor:
◦ k1 = 40 + 1 = 41
esetén min(z )=
3200 − 55 = 3145.
◦ k3 = 30 + 1 = 31
esetén min(z )=
3200 + 90 = 3290.
◦ k4 = 30 + 1 = 31
esetén min(z )=
3200 + 80 = 3280.
◦ k5 = 30 + 1 = 31
esetén min(z )=
3200 + 70 = 3270.
k2
nem véletlenül lett kihagyva a felsorolásból. A táblázatban látható, hogy a hozzá
tartozó Megengedhet® növekedés 0, így nem tudjuk növelni a jobb oldal értékét 1-gyel, mert az optimális bázis változik. Tehát ez esetben az árnyékár nem értelmezhet®.
20
A határok jelentésb®l kiolvashatjuk, hogy az
x11 , x12 , x13 , x21 , x22 és x23 közül egyiknek
sem tudnánk értékét úgy növelni vagy csökkenteni az optimális megoldásból kiindulva, hogy ne sérüljenek a korlátozó feltételek. Az
x31 , x32
és
x33
Fels® határára és Cél ered-
ményére azért kaptunk #HIÁNYZIK-ot, mert ezeket a változókat akárhogy növeljük, a feltételek mindig teljesülni fognak.
3.3.
Hozzárendelési feladat
A hozzárendelési feladat általában egy speciális esete egy kiegyensúlyozott szállítási feladatnak, amelyben minden kínálat és kereslet 1.
3.3.1.
Modell felírása
3.3. Feladat. Doc Councillman a 4 × 100 méteres vegyes váltóra válogatja össze úszócsapatát. Minden úszónak 100 métert kell úsznia vagy mellen, vagy háton, vagy pillangón, 21
vagy gyorson. Doc úgy gondolja, hogy mindegyik úszó tudja hozni az alábbi táblázatban leírt id®ket (másodpercben). Ha a csapat összidejének minimalizálása a cél, akkor melyik úszó melyik úszásnemben induljon?3
Legyen Gary Hall az egyes, Mark Spitz a kettes, Jim Montgomery a hármas és Chet Jastremski a négyes számú úszó. A gyors, mell, pillangó, hát pedig rendre az els®, második, harmadik és negyedik versenyszám. Döntési változók:
xij = 1, xij = 0,
ha az
ha az
i-edik
i-edik
úszót indítjuk a
j -edik
úszót nem indítjuk a
versenyszámban
j -edik
versenyszámban
Korlátozó feltételek:
•
Minden úszó csak egy versenyszámban indulhat:
x11 + x12 + x13 + x14 = 1
x31 + x32 + x33 + x34 = 1
x21 + x22 + x23 + x24 = 1
x41 + x42 + x43 + x44 = 1
•
Minden úszásnemben csak egy versenyz® indulhat:
x11 + x21 + x31 + x41 = 1
x13 + x23 + x33 + x43 = 1
x12 + x22 + x32 + x42 = 1
x14 + x24 + x34 + x44 = 1
El®jelkorlátozó feltételek:
xij ≥ 0 3 Wayne L. Winston:
ha,
i = 1, 2, 3, 4
Operációkutatás,
Aula
és
j = 1, 2, 3, 4
, 2003, 323. oldal
22
Célfüggvény: min
z = 54 · x11 + 54 · x12 + 51 · x13 + 53 · x14 +
+51 · x21 + 57 · x22 + 52 · x23 + 52 · x24 + +50 · x31 + 53 · x32 + 54 · x33 + 56 · x34 + +56 · x41 + 54 · x42 + 55 · x43 + 53 · x44 3.3.2.
Megoldás Solver segítségével
Meglév® paramétereinket rögzítsük egy excel táblázatban és használjuk az eddig alkalmazott Solver beállításokat! Az egyedüli különbség az el®z® feladatokhoz képest az az, hogy most a döntési változóink csak 0 vagy 1 értéket vehetnek fel. A korlátozó feltételeknél lév® Hozzáadás gomb segítségével állítsuk be a megfelel® cellákra a bin (bináris) feltételt. Esetünkben az összes második sorban szerepl® mez®re. Táblázatunkban az összetartozó sorokat azonos színnel jelöltem.
23
3.3.3.
Megoldás elemzése
Az optimális megoldás megjelent a táblázatunkban, amely szerint a csapat összideje a lehet® legjobb esetben 207 másodperc. Ehhez az kell, hogy Gary Hall induljon pillangón, Mark Spitz háton, Jim Montgomery gyorson, Chet Jastremski pedig mellen. A Solver azon túl, hogy közölte velünk, optimális megoldást talált, a következ®t is üzente, amikor a jelentéseket akartam elkészíteni: Az Érzékenység jelentés és a Határok jelentés nem bír jelentéssel egész érték¶ korlátozó feltételek esetén. Ezt az okozta, hogy a módosuló cellákra bináris feltételt szabtunk. Létezik olyan algoritmus, amely nagyon hatékonyan megoldja a hozzárendelési feladatot. Ezt az algoritmust
1. lépés
magyar módszernek
Keressük meg az
m × m-es
hívjuk, három lépésb®l áll:
költségmátrix minden sorában a legkisebb elemet.
Képezzünk egy új mátrixot úgy, hogy a sor minden költségeleméb®l kivonjuk a legkisebb költségelemet.
Ebben az új mátrixban keressük meg minden oszlopban
a legkisebb költségelemet. Képezzünk egy új mátrixot (ezt redukált költségmátrixnak nevezzük) úgy, hogy az oszlop minden költségeleméb®l kivonjuk a legkisebb költségelemet.
2. lépés
Rajzoljuk be a lehet® legkevesebb olyan vonalat (vízszintesen és/vagy függ®lege-
sen), amelyek segítségével a redukált költségmátrixban található összes nulla lefedhet®. Ha ehhez
m fed®vonal szükséges, akkor a mátrixban lév® lefedett nullák között
rendelkezésünkre áll az optimális megoldás. Ha
m-nél
kevesebb vonallal fedtük le
az összes nullát, akkor a 3. lépés következik.
3. lépés
Keressük meg a redukált költségmátrixban azt a legkisebb nemnulla elemet amelyiket a 2. lépésben nem fedtünk le. Most vonjuk ki
k -t
a
redukált költségmátrix minden nem lefedett eleméb®l, valamint adjunk hozzá
k -t
a
(nevezzük
k -nak),
kétszer lefedett elemekhez. Térjünk vissza a 2. lépéshez. Ha a hozzárendelési feladat során maximalizálni szeretnénk, akkor a pro tmátrix minden elemét szorozzuk meg -1-gyel és ezután oldjuk meg minimum feladatként. Ha a sorok és oszlopok száma nem egyezik, akkor vezessünk be ktív pontokat, mert a magyar módszer kiegyensúlyozatlan feladatra nem feltétlenül ad helyes megoldást. A leírt algoritmus segítségével ellen®rizzük le, hogy feladatunkra valóban optimális megoldást kaptunk-e a Solver által. Esetünkben a költségmátrix elemeit az egyes úszók úszásnemekben elért id®eredményeik adják. Mátrixunk a következ®képpen alakul:
24
A magyar módszer szerint a lefedett nullák között rendelkezésünkre áll az optimális megoldás (zölddel jelölve).
Viszont vannak olyan sorok és oszlopok, amelyekben több
nulla is szerepel. Keressünk olyanokat, amelyekben csak egyetlen nulla található. Esetünkben az els® és harmadik sorban, valamint a második oszlopban egyetlen nulla van, így ezeken a helyeken szerepl® költségelemek biztosan részei lesznek az optimális megoldásnak. Mivel minden sorból és oszlopból egy elemet választhatunk ki, így a már meglév® három meghatározza a negyediket. Az algoritmusra hagyatkozva Gary Hallnak pillangón, Mark Spitznek háton, Jim Montgomerynek gyorson, Chet Jastremskinek pedig mellen kell indulnia ahhoz, hogy a csapat összideje a legkisebb legyen. Ez a megoldás megegyezik a Solver által kiszámolttal.
3.4.
Minimális költség¶ hálózati folyam problémák
Egyes optimalizációs feladatoknál sokat használhat, ha gra kusan tudjuk szemléltetni. A soron következ® példánál egy hálózat segítségével fogunk modellezni.
3.4.1.
Modell felírása
Az eddig ismertetett feladatok mind speciális esetei a minimális költség¶ hálózati folyam problémának (MKHFP). A modell felírása során a következ®ket fogjuk használni:
• xij =
az
i
csúcsból a
j
csúcsba az
(i, j)
élen keresztül haladó folyam mennyisége
25
• bi =
az
• cij =
i
az
csúcs nettó kibocsátása (kiáramlás-beáramlás)
i
csúcsból a
j
(i, j)
csúcsba az
élen keresztül küldött egységnyi folyam
szállítási költsége
• Lij = az (i, j) élen átmen® folyam alsó korlátja (ha nincs alsó korlát, legyen Lij = 0) • Uij =
az
(i, j)
élen átmen® folyam fels® korlátja (ha nincs fels® korlát, legyen
Uij =
∞) Ezeket használva az MKHFP felírása:
min
X
cij · xij
minden élre
X j
xij −
X
(∀
xki = bi
i
csúcsra)
k
Lij ≤ xij ≤ Uij
(∀
(i, j)
élre)
3.4. Feladat. Az Oilco olajkútjai San Diego, illetve Los Angeles közelében vannak. A San Diego melletti mez®b®l napi legfeljebb 500 000 hordó, a Los Angeles melletti mez®b®l napi legfeljebb 400 000 hordó olaj termelhet® ki. A nyersolajat a dallasi vagy a houstoni nomítóba küldik, amelyek közül egyik sem képes napi 500 000 hordónál több olajat feldolgozni. Dallasban 100 000 hordó nomítása 700$-ba, Houstonban 900$-ba kerül. A nomított olajat Chicagoba, illetve New Yorkba szállítják: Chicagoba 400 000 hordónyit, New Yorkba 300 000 hordónyit naponta. Az alábbi táblázat mutatja, hogy mennyi 100 000 hordó (nyers vagy nomított) olaj szállítási költsége ($-ban) az egyes helyszínek között. Adjunk meg egy MKHFP-t, amellyel minimalizálható az igények kielégítésének összes költsége!4
4 Wayne L. Winston:
Operációkutatás,
Aula
, 2003, 381. oldal
26
A megoldás során egy egység alatt 100 000 hordó olajat értünk. Egy irányított gráf segítségével szemléltetem a feladatot. A csúcsok számai mögött a városok kezd®bet¶jét tüntettem fel zárójelben az átláthatóság kedvéért.
Döntési változók:
xij = az i-edik
városból a
j -edikbe
szállított olaj mennyisége
Nettó kibocsátás:
b1 + b2 = −7
b3 = 0
b5 + b6 = 7
b4 = 0
Az egyes pontpárokra vetített költségek (szállítási + nomítási):
c13 = 300 + 700 = 1000
c35 = 450
c14 = 110 + 900 = 1010
c36 = 550
c23 = 420 + 700 = 1120
c45 = 470
c24 = 100 + 900 = 1000
c46 = 530
A városok közötti szállítások alsó korlátja:
Lij = 0
(∀
(i, j)
élre)
A városok közötti szállítások fels® korlátja:
Ui3 = 500000 Ui4 = 500000 minden más esetben:
27
Uij = ∞
Korlátozó feltételek:
•
Kínálati feltételek:
x13 + x14 ≤ 4 x23 + x24 ≤ 5 •
A nomítók kapacitására vonatkozó feltételek:
x13 + x23 ≤ 5 x14 + x24 ≤ 5 •
Keresleti feltételek:
x35 + x45 = 3 x36 + x46 = 4 •
A nettó kibocsátásra vonatkozó feltételek:
x35 + x36 − x13 − x23 = 0 x45 + x46 − x14 − x24 = 0 El®jelkorlátozó feltételek:
xij ≥ 0
(∀
ij -re)
Célfüggvény:
min
z = 1000 · x13 + 1010 · x14 + 1120 · x23 + 1000 · x24 + +450 · x35 + 550 · x36 + 470 · x45 + 530 · x46
3.4.2.
Megoldás Solver segítségével
Az együtthatókkal feltöltött táblázat 4-5. sorában a kínálatra, 6-7-ben a kapacitásra, 89-ben a keresletre, 10-11-ben pedig a nettó kibocsátásra vonatkozó feltételeket láthatjuk. A hozzájuk tartozó befüggvényezett mez®ket velük azonos színnel jelöltem. használt beállításainkon nem kell változtatni.
28
Az eddig
3.4.3.
Megoldás elemzése
A kapott eredmény szerint Los Angelesb®l a dallasi nomítóba kell küldeni 300 000 hordó olajat, majd azt tovább New Yorkba. San Diegoból pedig a houstoni nomítóba célszer¶ szállítani 400 000 hordó olajat és onnan továbbítani Chicagoba. A J oszlopban látható, feltételek jobb oldalának feleltessük meg rendre a
k8
k1 , k2 ,
...,
paramétereket. Az érzékenység jelentésb®l a következ®ket olvashatjuk ki:
•
A feladat optimális megoldása nem változik, ha (a felsoroltak közül egyszerre csak egy változtatható meg):
29
•
◦ 980 ≤ c13 ≤ 1020.
◦ −∞ < c35 ≤ 470.
◦ 1000 ≤ c14 < ∞.
◦ 530 ≤ c36 < ∞.
◦ 1000 ≤ c23 < ∞.
◦ 450 ≤ c45 < ∞.
◦ 980 ≤ c24 ≤ 1010.
◦ −∞ < c46 ≤ 550.
Az optimális bázis nem változik, ha (a felsoroltak közül egyszerre csak egy változtatható meg):
•
◦ 3 ≤ k1 < ∞.
◦ 0 ≤ k5 ≤ 4.
◦ 4 ≤ k2 < ∞.
◦ 0 ≤ k6 ≤ 5.
◦ 3 ≤ k3 < ∞.
◦ −1 ≤ k7 ≤ 3.
◦ 4 ≤ k4 < ∞.
◦ −1 ≤ k8 ≤ 4.
Ha az optimális bázis nem változik, akkor:
◦ k5 = 3 + 1 = 4
esetén min(z )=
10470 + 1450 = 11920.
◦ k6 = 4 + 1 = 5
esetén min(z )=
10470 + 1530 = 12000.
◦ k7 = 0 + 1 = 1
esetén min(z )=
10470 − 1000 = 9470.
◦ k8 = 0 + 1 = 1
esetén min(z )=
10470 − 1000 = 9470.
A városok kapacitásának egységnyi növelésével a célfüggvény értéke nem változik.
30
A határok jelentésb®l kiolvashatjuk, hogy egyetlen változónak sem tudnánk értékét úgy növelni vagy csökkenteni az optimális megoldásból kiindulva, hogy ne sérüljenek a korlátozó feltételek. Ez azért van így, mert a korlátozó feltételek között nem csak egyenl®tlenségek, hanem egyenletek is szerepelnek.
31
4. fejezet
Nemlineáris programozás
A nemlineáris programozási (NLP) feladatoknak tulajdonképpen ugyanaz a lényege, mint a lineárisoknak, csak az a különbség, hogy a célfüggvény és a feltételek lehetnek nemlineáris függvények is.
4.1. De níció. Egy általános nemlineáris programozási feladat a következ®képpen adható meg: keressük azokat az x1 , x2 , ..., xn döntési változókat, amelyekre célfüggvény korlátozó feltételek
max (vagy min) z = f (x1 , x2 , . . . , xn ) g1 (x1 , x2 , . . . , xn ) (≤, = vagy ≥) k1 g2 (x1 , x2 , . . . , xn ) (≤, = vagy ≥) k2 .. . gm (x1 , x2 , . . . , xn )
4.1.
(≤, = vagy ≥) km
Folytonos feladat
4.2. De níció. Pontok S halmaza konvex halmaz, ha S bármely két pontját összeköt® szakasz teljes egészében S-ben van. Legyen
f (x1 , x2 , . . . , xn )
egy
S
konvex halmaz összes
(x1 , x2 , . . . , xn )
pontján értelme-
zett függvény.
4.3. De níció. Az f (x1 , x2 , . . . , xn ) konvex függvény az S konvex halmazon, ha bármely a ∈ S , b ∈ S és 0 ≤ c ≤ 1 esetén f (ca + (1 − c)b) ≤ cf (a) + (1 − c)f (b)
teljesül. 32
Amennyiben a 4.3. de nícióban megfordítjuk a relációt, a konkáv függvény de nícióját kapjuk. Ezek a fogalmak azért fontosak számunkra, mert ha egy függvény se nem konvex, se nem konkáv, akkor a Solver csak lokális optimumot talál.
4.1.1.
Modell felírása
4.1. Feladat. Egy kémiai folyamat hozama függ egyrészt a folyamat lezajlásának T id®tartamától (percekben megadva), másrészt a folyamat T EM P m¶veleti h®mérsékletét®l (Celsius-fokban megadva). Az összefüggést a következ® egyenlet írja le: YIELD = 87 − 1, 4 · T 0 + 0, 4 · T EM P 0 − 2, 2 · T 02 −3, 2 · T EM P 02 − 4, 9 · (T 0 )(T EM P 0 ),
ahol
T − 90 10 T EM P − 150 T EM P 0 = . 5 A T értéke 60 és 120 perc, míg a T EM P értéke 100 és 200 fok között kell hogy legyen. T0 =
Maximalizáljuk a folyamat hozamát!1 Döntési változók:
T0 = a
feladatban de niált
T -t®l
T EM P 0 = a
feladatban de niált
T EM P -t®l
Mivel a Solverrel
T 0 -re
és
T EM P 0 -re
függ® érték
függ® érték
fogjuk megoldani a feladatot ezért a korlátozó
feltételek:
60 ≤ T ≤ 120 ⇒ −3 ≤ T 0 ≤ 3 100 ≤ T EM P ≤ 200 ⇒ −10 ≤ T EM P 0 ≤ 10 Célfüggvény:
max
z = 87 − 1, 4 · T 0 + 0, 4 · T EM P 0 − 2, 2 · T 02 −3, 2 · T EM P 02 − 4, 9 · (T 0 )(T EM P 0 )
1 Wayne L. Winston:
Operációkutatás,
Aula
, 2003, 550. oldal
33
4.1.2.
Megoldás Solver segítségével
Kijelenthetjük célfüggvényünkr®l, hogy konkáv függvény, tehát bármely két pontját összeköt® szakasz sehol sem halad a görbe felett. Így ha találunk a Solverrel optimumot, akkor az biztosan globális optimum lesz. Az alábbi kép a célfüggvényünket ábrázolja, amelyen jól látható, hogy konkáv függvénnyel van dolgunk.
Az eddigiekben alkalmazott megoldási menetünkön annyit változtatunk, hogy a célfüggvény együtthatói helyett most magát a képletet rögzítjük (a Solver ezt nem fogja használni). Az alábbi táblázatban láthatjuk a feladat eredményét, valamint a szerkeszt®lécben a célfüggvény értékére vonatkozó képletet.
34
4.1.3.
Megoldás elemzése
A kémiai folyamat hozama akkor lesz maximális (89,26), ha 63,69 másodperc alatt zajlik le 160,39 fokos h®mérsékleten. A lineáris esett®l eltér® érzékenység jelentést kapunk. Amennyiben a Redukált gradiens oszlopban csak nullák szerepelnek, akkor az azt jelenti, hogy a megoldásunk optimális. A Lagrange multiplikátorok pedig a feladat Lagrange duáljának optimális megoldásvektorának megfelel® koordinátáinak ellentettjét mutatják.
A határok jelentésb®l kiolvasható, hogy az optimális megoldásból kiindulva
T EM P 0
értékének redukálása esetén a folyamat hozama nagy mértékben csökken.
4.2. 4.2.1.
Nem folytonos feladat Modell felírása
4.2. Feladat. A Q & H cég szappanoperák és futballmérk®zések közben reklámoztat. Egy reklám egyszeri leadásának költsége szappanopera közben 50 000$, futballmérk®zés közben 100 000$. Ha a néz®számot milliókban adjuk meg, akkor S számú szappanopera közbeni √ √ hirdetés megvásárlása esetén a reklámot 5 S fér és 20 S n® fogja látni. Ha F számú √ √ futballmérk®zés közbeni hirdetést vásárolnak, akkor a reklámot 17 F fér és 7 F n® fogja látni. A Q & H azt akarja, hogy a reklámokat legalább 40 millió fér és legalább 60 millió n® lássa. Minimalizáljuk a Q & H költségeit a kívánt néz®szám elérése mellett.2 2 Wayne L. Winston:
Operációkutatás,
Aula
, 2003, 550. oldal
35
Döntési változók:
S = ahány F = ahány
szappanopera közbeni hirdetést vásárol a cég
futballmérk®zés közbeni hirdetést vásárol a cég
Korlátozó feltételek:
√ S + 17 · F ≥ 40 √ √ 20 · S + 7 · F ≥ 60
5·
√
Továbbá feltételezzük, hogy csak egész érték¶ hirdetést lehet vásárolni:
S ∈ N0 F ∈ N0 Célfüggvény: min
4.2.2.
z = 50000 · S + 100000 · F
Megoldás Solver segítségével
A lineáris esethez képest annyit változtatunk a Solverrel való megoldáson, hogy a korlátozó feltételeknek és a célfüggvénynek nem csak az együtthatóit tüntetjük fel a táblázatunkban, hanem a változók hatványát is.
Megoldandó feladatunkban most csak a kritériumok
nemlineárisak. Az F14 mez®ben változatlanul az eddig használt szorzatösszeg szerepel, míg ha a D11 cellára kattintunk, akkor az alábbi képletet olvashatjuk a szerkeszt®lécben (D12 is hasonlóképpen a megfelel® paraméterek használatával):
A feltételek rögzítésénél ne feledkezzünk meg arról, hogy a változóknak egész értéket kell felvenniük.
Ezért feltétel hozzáadása segítségével állítsuk be a C2 és D2 mez®kre
az int (integer) értéket. A beállításoknál értelemszer¶en most nem jelöljük be a lináris modell feltételezést, az eddig használt nemnegatív opcióra viszont szükségünk lesz. közelítés, dierenciák és keresési beállításokat hagyjuk alapértelmezett állapotban.
A Az
egyes sorok összetartozását ismételten egyforma színekkel jelöltem. A leírtaknak megfelel®en a táblázatunk és benne a feladat megoldása:
36
4.2.3.
Megoldás elemzése
A kapott eredmény szerint a Q & H cég költségei akkor lesznek minimálisak, ha szappanopera közben hatszor és futballmérk®zés közben háromszor reklámoznak. Ebben az esetben a hirdetéseket majdnem 42 millió fér és több mint 61 millió n® fogja látni, amelyek összesen 600 ezer $-ba kerülnek.
A jelentéseket nem tudta elkészíteni a Solver az
egész érték¶ feltételezés miatt (a hozzárendelési feladathoz hasonlóan): Az Érzékenység jelentés és a Határok jelentés nem bír jelentéssel egész érték¶ korlátozó feltételek esetén. A következ® oldalon egy táblázatot láthatunk, amely azt mutatja, hogy S és F adott értékei mellett milyen értékeket vesz fel a fér ak (f1) és a n®k (f2) számára vonatkozó feltételek (millió f®ben), valamint a célfüggvény (c - ezer $-ban). Az ábrán zöld színnel jelöltem, ahol a feltétel teljesül, és pirossal ahol nem.
Sárgával az optimális megoldást
tüntettem fel. A lehetséges megoldások között azok szerepelnek, amelyeknél az f1 és f2 oszlopok egyaránt zöld szín¶ek. Az ábrából jól kivehet®, hogy nem célszer¶ csak az egyik hirdetés típust választani. Ha például csak az olcsóbb, szappanopera közbeni reklámozást er®ltetné a cég, akkor 64 adásmegszakítást kellene vásárolniuk, amely 3,2 millió $-ba kerülne.
37
38
Nyilatkozat
A szakdolgozat szerz®jeként fegyelmi felel®sségem tudatában kijelentem, hogy a dolgozatom önálló munkám eredménye, saját szellemi termékem, abban a hivatkozások és idézések standard szabályait következetesen alkalmaztam, mások által írt részeket a megfelel® idézés nélkül nem használtam fel.
39
Irodalomjegyzék
[1] Wayne L. Winston: Operációkutatás,
Aula, 2003
[2] http://www.math.bme.hu/∼gnagy/ExcelSolver.htm [3] http://o ce.microsoft.com/hu-hu/excel-help/CH001000457.aspx [4] http://www.epab.bme.hu/epinf1/Gy-ExcelSzamarhatCsarnok/Solver_beallitasok_sugo.htm [5] http://miau.gau.hu/mediawiki/index.php/Optimalizálás
40
