El˝ osz´ o Ez a k´ezirat a szerz˝o az Eszterh´azy K´aroly F˝oiskol´an tartott Oper´aci´okutat´as c´ım˝ u el˝oad´asai v´ azlat´ anak f´ elk´ esz v´ azlat´ at tartalmazza.
Juh´asz Tibor
1.
Optimumsz´ am´ıt´ asi modellek 1.1. Mintafeladatok
Horg´ asz probl´ ema. Horg´aszunk egy olyan t´oban horg´aszik, ahol h´aromf´ele hal van: ponty, keszeg ´es s¨ ull˝o. Ezekb˝ol a halfajt´akb´ol 1 kilogrammnyi kifog´asa a horg´asz sz´am´ara k¨ ul¨onb¨oz˝o ,,´elvezeti ´ert´ekkel” b´ır: a ponty est´en 3, a keszegn´el 2 a s¨ ull˝on´el 4 ez az ´ert´ek. A t´onak h´arom gazd´aja van, akik a k¨ovetkez˝o szab´alyokat t´amasztj´ak: 1. tulaj: 1 kg ponty ´es keszeg 1 EUR, 1 kg s¨ ull˝o 2 EUR ´es egy nap max. 4 EUR ´ert´ek˝ u hal foghat´o ki a t´ob´ol; 2. tulaj: 1 kg ponty 2 EUR, 1 kg s¨ ull˝o 3 EUR, a keszeg ingyen van ´es egy nap max. 5 EUR ´ert´ek˝ u hal foghat´o ki a t´ob´ol; 3. tulaj: 1 kg ponty ´es keszeg 2 EUR, 1 kg s¨ ull˝o 4 EUR ´es egy nap max. 7 EUR ´ert´ek˝ u hal foghat´o ki a t´ob´ol. Mennyi halat kell kifognia a horg´asznak egy nap alatt ahhoz, hogy a tulajdonosok ´altal ´ırt szab´alyokat betartva a horg´aszatot a lehet˝o legjobban ´elvezze? Keresked˝ o probl´ ema. Egy gyermek elmegy egy keresked˝oh¨oz kim´ert u ¨d´ıt˝ot v´as´arolni. A rostos u ¨d´ıt˝ob˝ol 1 liternyi t¨omege 2 kg ´es a keresked˝onek ezen 3 EUR haszna van. A sz´ensavas u ¨d´ıt˝ob˝ol 1 liternyi t¨omege 1 kg ´es a keresked˝onek ezen 1 EUR haszna van. A gyerek kicsi l´ev´en max. 5 kg t¨omeg˝ uu ¨d´ıt˝ot tud hazavinni, m´asr´eszt az apja azt k´eri t˝ole, hogy legal´abb egy literrel t¨obb sz´ensavas u ¨d´ıt˝ot hozzon, mint rostosat, az anyja pedig azt, hogy legal´abb 3 liter u ¨d´ıt˝ot hozzon haza. Mennyi rostos ´es sz´ensavas u ¨d´ıt˝ot adjon el a keresked˝o a gyereknek u ´gy, hogy min´el t¨obb haszna legyen, a gyerek haza tudja vinni az ´arut ´es a sz¨ ul˝ok is el´egedettek legyenek? Termel´ esi feladat. Adott egy m˝ uhely, amely asztalokat, sz´ekeket ´es szekr´enyeket gy´art. A gy´art´ashoz k´etf´ele anyagot haszn´alnak fel, egyfajta lemezt ´es egyfajta deszk´at. Ezek egym´assal nem helyettes´ıthet˝ok ´es korl´atozott sz´amban ´allnak rendelkez´esre. A feladat olyan term´ek¨osszet´etel meghat´aroz´asa, amely mellett a m˝ uhely nyeres´ege maxim´alis. (Nyilv´an ez a feladat ´altal´anosabban is megfogalmazhat´o: m f´ele term´eket gy´artunk n f´ele alapanyagb´ ol.) 1
2
1.2. A modellalkot´as elemei, egy lehets´eges modellalkot´asi elv Jelens´egek t¨omeg´eb˝ol kiv´alasztjuk a probl´ema szempontj´ab´ol l´enyeges, meghat´aroz´o jegyeket ¨osszef¨ ugg´eseket, a t¨obbit˝ol a modell kezelhet˝os´ege ´erdek´eben eltekint¨ unk. K¨ovetelm´enyek: t¨ ukr¨ozz´ek min´el h´ıvebben a val´os´agot ´es legyenek matematikailag, sz´am´ıt´astechnikailag kezelhet˝ok. Kompromisszumok. Elemi tev´ ekenys´ egek meghat´ aroz´ asa: A vizsg´alat t´argy´at k´epez˝o tev´ekenys´eget bontsuk fel elemi tev´ekenys´egekre, azaz olyan pontosan k¨or¨ ulhat´arolt r´eszekre, amit m´ar nem sz´and´ekozunk tov´abb bontani. Jel¨olje ezeket E1 , E2 , . . . , En . – a horg´asz probl´em´an´al: k¨ ul¨onb¨oz˝o halfajt´akra t¨ort´en˝o horg´asz´asok; – a keresked˝o probl´em´an´al: rostos ´es sz´ensavas u ¨d´ıt˝o v´as´arl´asa; – a termel´esi feladatn´al: asztal-, sz´ek- ´es szekr´enygy´art´as. Elemi tev´ ekenys´ egek intenzit´ as´ anak meghat´ aroz´ asa: minden egyes Ei elemi tev´ekenys´eghez rendelj¨ unk hozz´a egy xi val´os sz´amot, ami arr´ol ad felvil´agos´ıt´ast, hogy Ei milyen m´ert´ekben vesz r´eszt a teljes tev´ekenys´egben. Vektorral ´ırhat´ok le. – a horg´asz probl´em´an´al: az egyes halfajt´akb´ol (ponty, keszeg, s¨ ull˝o) kifogand´o mennyis´egek (x1 , x2 , x3 ); – a keresked˝o probl´em´an´al: rostos ´es sz´ensavas u ¨d´ıt˝ob˝ol megv´as´arl´asra ker¨ ul˝o mennyis´egek (x1 , x2 ); – a termel´esi feladatn´al: a gy´artand´o asztalok, sz´ekek ´es szekr´enyek sz´ama (x1 , x2 , x3 ). Ezek ´altal´aban korl´atosak ´es nem f¨ uggetlenek. Intenzit´ as´ as´ ert´ ekek k¨ oz¨ otti ¨ osszef¨ ugg´ esek meghat´ aroz´ asa: felt´etelek, melyeket az intenzit´ asoknak k¨ ul¨on-k¨ ul¨on is ´es egy¨ uttesen is ki kell el´eg´ıteni. Teh´at az egyes xi v´altoz´okra ´es az (x1 , x2 , . . . , xn ) vektorv´altoz´ora vonatkoz´o felt´eteleket hat´arozzuk meg. Egy val´os vektort a feladat egy lehets´eges megold´ as´ anak mondunk, ha kiel´eg´ıti az ¨osszes el˝oz˝oekben megadott felt´etelt. A lehets´eges megold´ asok halmaz´ at L-lel fogjuk jel¨olni. – a horg´asz probl´em´an´al: xi x1 + x2 + 2x3 2x1 + 3x3 2x1 + 2x2 + 4x3
≥0 ≤4 ≤5 ≤7
– a keresked˝o probl´em´an´al: xi −x1 + x2 x1 + x2 2x1 + x2
≥0 ≥1 ≥3 ≤5
´ ´ITASI ´ OPTIMUMSZAM MODELLEK
3
– a termel´esi feladatn´al: xi ≥ 0 ´es xi eg´esz. Legyen a rendelkez´esre ´all´o lemezek sz´ama l, a deszk´ak´e d, l1 , l2 , l3 ill. d1 , d2 , d3 egy asztal, egy sz´ek, egy szekr´eny el˝o´all´ıt´as´ahoz sz¨ uks´eges lemez ill. deszka. Ekkor a felt´etelek: l1 x1 + l2 x2 + l3 x3 ≤ l d 1 x1 + d 2 x2 + d 3 x3 ≤ d x1 , x2 , x3 ≥ 0 eg´eszek C´ el megfogalmaz´ asa az elemi tev´ ekenys´ egek seg´ıts´ eg´ evel: megadunk egy olyan z : L → R f¨ uggv´enyt, amely a lehets´eges megold´asok ,,j´os´ag´at” jellemzi a kit˝ uz¨ott c´el szempontj´ab´ol. Ezt c´elf¨ uggv´enynek h´ıvjuk. – a horg´asz probl´em´an´al: a horg´asz ´elvezete z(x) = 3x1 + 2x2 + 4x3 max; – a keresked˝o probl´em´an´al: a keresked˝o haszna z(x) = 3x1 + x2 max; – a termel´esi feladatn´al: az egy¨ uttes nyares´eg z(x) = c1 x1 + c2 x2 + c3 x3 max, ahol c1 , c2 , c3 az egy asztal, sz´ek, ill. szekr´eny elad´as´ab´ol sz´armaz´o nyeres´eg. Kompromisszumok: pl. feltessz¨ uk, hogy minden megtermelt ´aru eladhat´o, stb. Optimumsz´ am´ıt´ asi modell : a gyakorlati ´elet probl´emacsoportjait form´alisan le´ır´o modell, amely egy felt´etelrendszerb˝ol ´es egy vagy esetleg t¨obb ´ ´ O ˝ ERT ´ EK-FELADAT, ´ c´elf¨ uggv´enyb˝ol ´all. FELTETELES SZELS a felt´etelek ´altal meghat´arozott L halmazon keress¨ uk a c´elf¨ uggv´eny sz´els˝o´ert´ek´et. Maximumkeres´es eset´en maximum-feladatr´ ol, m´ıg minimumkeres´es eset´en minimum-feladatr´ ol besz´el¨ unk, a maximum ill. minimumhelyet optim´ alis megold´ asnak nevezz¨ uk. Optim´alis megold´as nem sz¨ uks´egk´eppen l´etezik, ill. ha l´etezik, akkor t¨obb is lehet. ¨ 1. feladat. Az Uveg Diszkont´aruh´az egy u ´j r´eszleg megnyit´as´at tervezi egy 10000 n´egyzetm´eteres ter¨ uleten. A menedzsment 4 term´ek ´arus´ıt´as´at fontolgatja az u ´j r´eszlegben. – Az A term´ek k¨olts´ege 55$, elad´asi ´ara 130$, ´es a helyig´enye 24 nm/egys´eg. – A B term´ek k¨olts´ege 100$, elad´asi ´ara 120$, ´es a helyig´enye 20 nm/egys´eg. – A C term´ek k¨olts´ege 200$, elad´asi ´ara 295$, ´es a helyig´enye 36 nm/egys´eg. – A D term´ek k¨olts´ege 300$, elad´asi ´ara 399$, ´es a helyig´enye 50 nm/egys´eg. Sz¨ uks´eges, hogy minden egyes term´ekb˝ol legyen legal´abb 10 egys´eg forgalomban. A Diszkont´aruh´ az c´elja a profitmaximaliz´al´as. K´erd´es, hogy a maxim´alis profit el´er´es´ehez mennyi term´eknek kell forgalomban lennie, ha ¨ az Uveg Diszkont´aruh´aznak 600000$-ja van a term´ekek megv´as´arl´as´ara? ´Irja fel a feladat matematikai modellj´et!
4
u- ´es apr´oszeggy´art´o 2. feladat. A Vegyesipari Szolg´altat´o V´allalat gombost˝ u ¨zeme n´egyf´ele alapanyag´ u (ac´el, vas, r´ez, alpakka) gombost˝ ut gy´art. A gy´art´asi technol´ogia f˝o folyamatai a gy´art´as, a nikkelez´es ´es a csomagol´as. Egy adott h´onapban rendre a k¨ovetkez˝o kapacit´asok ´allnak rendelkez´esre: 300, 200, illetve 240 munka´ora. A term´ekek elsz´amol´asi ´arai: 230, 210, 280, 330 Ft/kg gombost˝ ufajt´ank´ent. Az u ¨zemi felm´er´esekb˝ol ismert, hogy 1 kg gombost˝ u el˝o´all´ıt´asa mennyi munka´or´at vesz ig´enybe a k¨ ul¨onb¨oz˝o technol´ogiai folyamatokb´ol. Ezt mutatja a k¨ovetkez˝o t´abl´azat: technol´ ogia ac´el vas r´ez alpakka gy´art´ as 5 3 2 2 nikkelez´es 0 2 4 0 csomagol´as 2 1 3 3 ´ ekes´ıt´esi Oszt´aly az el˝orendel´esek alapj´an meg´allap´ıtotta, hogy az Az Ert´ adott h´onapban maxim´alisan 200 kg gombost˝ ut tud ´ert´ekes´ıteni. Enn´el t¨obbet nem szabad gy´artania az u ¨zemnek. Az el˝orendel´esek alapanyag szerinti kik¨ot´eseket nem tartalmaznak. Hat´arozza meg – az adott felt´etelek figyelembev´etel´evel – azt a termel´esi programot, amelyik a maxim´alis brutt´o termel´esi ´ert´eket hozza a gy´art´o u ¨zemnek! ´Irja fel a feladat matematikai modellj´et! 3. feladat. H´arom k¨ ul¨onb¨oz˝o sz˝ol˝ofajt´ab´ol (S1, S2, S3) k´etf´ele Cuv´ee (C1, C2) k´esz¨ ul. Az al´abbi t´abl´azat mutatja, hogy az egyes Cuv´ee-k milyen ar´anyban tartalmazz´ak a egyes alapanyagokat, m´asr´eszt az egys´egnyi mennyis´eg˝ u (liter must) komponensek ´ar´at, valamint a komponensekb˝ol rendelkez´esre ´all´o mennyis´eget. alapanyag C1-ben (%) C2-ben (%) ´ar (Ft/l) kapacit´as (l) S1 30 25 300 30000 S2 25 40 275 40000 S3 45 35 250 50000 Figyelembe v´eve a bor´aszat kapacit´as´at, a v´egterm´ekekb˝ol ¨osszesen legfeljebb 125000 litert tudunk el˝o´all´ıtani. Az eddigi felm´er´esek C1-b˝ol m´ar 20000, C2-b˝ol pedig m´ar 25000 literre t¨ort´ent megrendel´es. Milyen termel´es mellett lesz a bor´aszat nyeres´ege a lehet˝o legnagyobb, ha a C1 piaci ´ara 950, a C2 ´ara pedig 800 forint literenk´ent? ´Irja fel a feladat matematikai modellj´et!
1.3. Optimumsz´am´ıt´asi modellek oszt´alyoz´asa Az elemi tev´ekenys´egek intenzit´as´ert´ek´et˝ol f¨ ugg˝oen: – diszkr´et (megsz´aml´alhat´o az ´ert´ekk´eszlet); – folytonos (egy intervallum b´armilyen ´ert´eke sz´oba j¨ohet); – vegyes (egyik sem) modellek.
´ ´ LINEARIS PROGRAMOZAS
5
A modellekben szerepl˝o param´eterek szerint: – determinisztikus; – sztochasztikus modellek. Line´ aris programoz´ asi feladat: olyan optimumsz´am´ıt´asi modell, melyben a felt´etelek mindegyike line´aris egyenl˝os´eg vagy megenged˝o egyenl˝otlens´eg ´es a c´elf¨ uggv´eny egy line´aris f¨ uggv´eny. Nemline´ aris programoz´ asi feladat: olyan optimumsz´am´ıt´asi modell, melyben a felt´etelek mindegyike line´aris egyenl˝os´eg vagy megenged˝o egyenl˝otlens´eg ´es a c´elf¨ uggv´eny nemline´aris f¨ uggv´eny.
2.
Line´ aris programoz´ as
´ Altal´ anos LP -feladat: olyan felt´eteles sz´els˝o´ert´ek-feladat, melyben a felt´etelek line´aris egyenl˝os´eg ´es egyenl˝otlens´eg form´aj´aban adottak ´es ezen felt´etelek mellett keress¨ uk egy line´aris f¨ uggv´eny, a c´elf¨ uggv´eny minimum´at vagy maximum´at. Mindazon vektorok halmaz´at, melyek kiel´eg´ıtik az LP -feladat valamennyi felt´etel´et, az LP -feladat lehets´eges megold´ asai halmaz´ anak nevezz¨ uk ´es L-lel jel¨olj¨ uk. Az L halmaz egy elem´et az LP -feledat egy lehets´eges megold´as´anak mondjuk. Egy maximaliz´al´asi/minimaliz´al´asi LP -feladat egy x0 lehets´eges megold´as´at optim´ alis megold´ asnak nevezz¨ uk, ha x0 maximumhelye/minimumhelye az LP -feladat c´elf¨ uggv´eny´enek. Alapk´erd´esek : a feladatnak van-e optim´alis megold´asa, ´es ha igen, hogyan lehet azt meghat´arozni? Egy maximaliz´al´asi/minimaliz´al´asi LP -feladat megoldhat´ o, ha L nem¨ ures halmaz ´es a c´elf¨ uggv´eny fel¨ ulr˝ol/alulr´ol korl´atos az L halmazon; ellenkez˝o esetben azt mondjuk, hogy az LP -feladat nem oldhat´ o meg.
2.1. Solver Most bemutatjuk, hogyan oldhatjuk meg a horg´asz probl´em´at a Microsoft Excel Solver nev˝ u b˝ov´ıtm´enye seg´ıts´eg´evel. El˝osz¨or k´esz´ıts¨ uk el a k¨ovetkez˝o t´abl´azatot: A B3 : D6 tartom´anyban az x1 , x2 , x3 v´altoz´ok c´elf¨ uggv´eny-, illetve felt´etelekbeli egy¨ utthat´oi szerepelnek, az F 4 : F 6-ban pedig a felt´etelek jobboldal´an ´all´o konstansok. (A nemnegativit´asi felt´eteleket kihagyhatuk.) Az E oszlopba pedig a c´elf¨ uggv´eny ill. a felt´etelek baloldal´anak B2 : D2 beli he¨ lyettes´ıt´esi ´ert´eke ker¨ ul, ami p´eld´aul a SZORZATOSSZEG nev˝ u f¨ uggv´ennyel sz´amolhat´o. Ha a k´eplet az E3 cell´aba az ´abr´an l´athat´o m´odon ker¨ ul, akkor az m´ar m´asolhat´o az alantas cell´akba. Ezt k¨ovet˝oen v´alasszuk az Eszk¨ oz¨ ok
6
men¨ u Solver... men¨ upontj´at, majd a megjelen˝o p´arbesz´edablakot a k¨ovetkez˝ok´eppen t¨olts¨ uk ki.
A korl´atoz´o felv´etelek felv´etele a Hozz´ aad´ as gombra kattintva t¨ort´enhet. Kattintsunk most a Be´ all´ıt´ as gombra, majd enged´elyezz¨ uk a ,,line´ aris modell ” ´es ,,nemnegat´ıv ” felt´etelez´es´et, az OK gombbal nyugt´azzuk, majd a Megold´ as gombra klikkelve a k¨ovetkez˝o eredm´enyt kapjuk: Mint az leolvashat´o, a probl´em´anak l´etezik optim´alis megold´asa, nevezetesen 2, 5 kg ponty ´es 1 kg keszeg kifog´asa. Ekkor a horg´asz ¨osszes´ıtett ´elvezeti mutat´oja 9, 5.
2.2. Grafikus megold´as K´etdimenzi´os LP feladat megold´as´ara alkalmas. L´enyege, hogy az egyenl˝otlens´eg-t´ıpus´ u felt´etelek f´els´ıkokat hat´aroznak meg a k´etdimenzi´os t´erben ´es ezen f´els´ıkok metszetek´ent ´all´ıthat´o el˝o a lehets´eges megold´asok halmaza, melynek ismeret´eben m´ar meghat´arozhat´ o az optim´alis megold´as. Tekints¨ unk egy tetsz˝oleges ax + by ≤ c egyenl˝otlens´eget.
´ ´ LINEARIS PROGRAMOZAS
7
– Ha a = 0 ´es b ̸= 0, akkor b el˝ojel´et˝ol f¨ ugg˝oen vagy az y ≤ cb vagy az b y ≥ c egyenl˝otlens´eghez jutunk, melyet kiel´eg´ıt˝o pontok halmaza az y tengelyt a cb pontban metsz˝o, x tengellyel p´arhuzamos egyenes ´altal hat´arolt f´els´ıkok egyike. – Az a ̸= 0 ´es b = 0 esetben ugyanez a helyzet, csak a sz´obanforg´o f´els´ıkot egy az y tengellyel p´arhuzamos egyenes hat´arolja. – V´eg¨ ul ha a ̸= 0 ´es b ̸= 0, akkor a hat´aregyenes egyenlete: y = − ab x+ cb . Ez nyilv´ an a (0, cb ) ´es a ( ac , 0) pontokhoz illeszked˝o egyenes. ´ azolva a 2-dimenzi´os t´erben az egyes egyenl˝otlens´egeket kiel´eg´ıt˝o ponAbr´ tokb´ol ´all´o f´els´ıkokat, ´es ezek k¨oz¨os r´eszek´ent megkapjuk azon pontok L halmaz´at, amelyek a feladat minden felt´etel´et kiel´eg´ıtik. Keress¨ uk az L azon pontj´at, melyen a c´elf¨ uggv´eny ´ert´eke minim´alis (vagy maxim´alis). Legyen a c´elf¨ uggv´eny z(x, y) = dx + ey alak´ u. Azon pontok halmaza, melyen z ´ert´eke ´eppen z0 , pontosan a z0 = dx + ey egyenes, amely az e ̸= 0 esteben a z0 /e helyen metszi az y tengelyt. Teh´at a lehets´eges c´elf¨ uggv´eny ´ert´ekekhez p´arhuzamos egyenesek tartoznak. Ezek k¨oz¨ ul keress¨ uk azt, melynek van k¨oz¨os pontja L-lel ´es a y-tengelymetszete minim´alis (vagy maxim´alis). Ez itt m´ar az e el˝ojel´et˝ol is f¨ ugg. Ha e = 0, akkor ugyanez a helyzet, csak az x tengellyel val´o tengelymetszetet vizsg´aljuk. 4. feladat. Oldjuk meg grafikus m´odszerrel a k¨ovetkez˝o LP-feladatokat:
8
a) x+y x−y −x + 2y x ≥ 0, y
≤7 ≤1 ≤8 ≥0
z(x, y) = −x − 2y → min b) x−y ≤3 x+y ≥4 x ≥ 0, y ≥ 0 z(x, y) = x + 2y → min c) x−y ≤3 x+y ≥4 x ≥ 0, y ≥ 0 z(x, y) = x + 2y → max d) x−y ≥5 x+y ≤3 −x + y ≤ 4 x≤4 z(x, y) = x + y → max e) x−y ≤4 2x + 2y ≥ 2 x + 2y ≤ 7 −2x + y ≤ 1 x, y ≥ 0 z(x, y) = 4x − 2y → min
2.3. Fourier m´odszere Az elj´ar´ast Fourier javasolta, helyess´eg´enek igazol´asa Motzkin-t´ol sz´armazik. Az elj´ar´as maximum feladatra ismertetj¨ uk, ´es a keresked˝o probl´em´an illusztr´aljuk.
´ ´ LINEARIS PROGRAMOZAS
9
uk, hogy a felt´etelek lin. egyenl˝otlens´egek legyenek. Tov´abb´a, 1. l´ep´es: El´erj¨ ha z0 egy optimum ´ert´ek, akkor a z(x) ≥ z0 egyenl˝otlens´eget m´ar csak az optim´alis megold´asok el´eg´ıtik ki. 2. l´ep´es: Kiv´alasztunk egy z0 -t´ol k¨ ul¨onb¨oz˝o x v´altoz´ot, majd kifejezz¨ uk minden egyenl˝otlens´egb˝ol. Az ´ıgy kapott egyenl˝otlens´egeket k´et csoportra osztjuk: az egyik csoportba tartoznak azok, ahol x kisebb vagy egyenl˝o, a m´asikba pedig ahol x nagyobb vagy egyenl˝o mint egy line´aris kifejez´es. 3. l´ep´es: Az els˝o csoportba taroz´o egyenl˝otlens´egeket p´aros´ıtsuk a m´asodik csoport ¨osszes egyenl˝otlens´eg´evel. Egy u ´j egyenl˝otlens´eg-rendszert kapunk, ami m´ar nem tartalmazza az x v´altoz´ot. 4. l´ep´es: Ha van m´eg z0 -t´ol k¨ ul¨onb¨oz˝o v´altoz´o, akkor 2. l´ep´es. 5. l´ep´es: A z-re kapott fels˝o korl´atok k¨oz¨ ul a legkisebb lesz az optimum. Ezt visszahelyettes´ıtve a megel˝oz˝o egyenl˝otlens´eg-rendszerekbe: az als´o korl´atok maximuma ´es a fels˝o korl´atok minimuma fogja meghat´arozni a megfelel˝o komponens ´ert´ek´et.
Most megoldjuk a keresked˝o-probl´em´at Fourier m´odszer´evel. Itt a felt´etelek egyenl˝otelens´egek, a c´elf¨ uggv´eny pedig z(x) = 3x1 + x2 , melynek a maximumhely´et keress¨ uk. Ha z0 a z f¨ uggv´eny maximuma, akkor a z0 ≤ 3x1 + x2 egyenl˝otlens´eget m´ar csak az optim´alis megold´asok el´eg´ıtik ki. Fejezz¨ uk ki minden egyenl˝otlens´egb˝ol pl. az x1 v´altoz´ot!
(1)
0 ≤ x2
(2)
0 ≤ x1
(3) (4) (5) (6)
ebben nem volt x1
x1 ≤ x2 − 1 −x2 + 3 ≤ x1 1 5 x1 ≤ − x2 + 2 2 1 1 − x2 + z0 ≤ x1 3 3
A (2) egyenl˝otlens´eget p´aros´ıtva a (3) ´es (5) egyenl˝otlens´egekkel, majd a (4)-et ugyanezekkel ´es v´eg¨ ul pedig a (6)-ot a k¨ovetkez˝o egyenl˝otlens´eg-rendszerhez jutunk
10
0 ≤ x2 0 ≤ x2 − 1 1 0 ≤ − x2 + 2 −x2 + 3 ≤ x2 − 1 1 −x2 + 3 ≤ − x2 + 2 1 1 − x2 + z0 ≤ x2 − 1 3 3 1 1 1 − x2 + z0 ≤ − x2 + 3 3 2
5 2 5 2
5 2
melyben m´ar nem szerepel x1 . Fejezz¨ uk ki most az x2 -t mindegyik egyen´ l˝otlens´egb˝ol! Igy kapjuk, hogy 0 ≤ x2 1 ≤ x2 x2 ≤ 5 2 ≤ x2 1 ≤ x2 1 3 z0 + ≤ x2 4 4 x2 ≤ −2z0 + 15 ami az egyes egyenl˝otlens´egek k¨oz¨otti ,,´atfed´esek” miatt az al´abbi egyenl˝otlens´egekre reduk´alhat´o: x2 ≤ 5
(7) (8) (9) (10)
2 ≤ x2 1 3 z0 + ≤ x2 4 4 x2 ≤ −2z0 + 15
Elv´egezve u ´jra a p´aros´ıt´asokat a 2≤5 1 3 z0 + ≤ 5 4 4 2 ≤ −2z0 + 15 1 3 z0 + ≤ −2z0 + 15 4 4
´ ´ LINEARIS PROGRAMOZAS
11
egyenl˝otlens´egeket kapjuk, melyek m´ar az x2 v´altoz´ot sem tartalmazz´ak. Kifejezve mindegyikb˝ol z0 -t, az z0 ≤ 17 13 z0 ≤ 2 19 z0 ≤ 3 egyenl˝otlens´egek ad´odnak. A c´elf¨ uggv´eny maximuma pedig a fels˝o korl´atok legkissebbike lesz, azaz z(x) = 19 aroz´as´ahoz helyettes´ıts¨ uk 3 . x2 meghat´ 19 vissza a z0 = 3 ´ert´eket a (7) − (10) egyenl˝otlens´egekbe. Ekkor a x2 -re a k¨ovetkez˝o korl´atokat kapjuk: x2 ≤ 5 2 ≤ x2 7 ≤ x2 3 7 x2 ≤ 3 ahonnan x2 = 73 k¨ovetkezik. V´eg¨ ul behelyettes´ıtve az (1) − (6) egyenletekbe a m´ar ismert ´ert´ekeket, x1 -re kapjuk az al´abbi korl´atokat: 0 ≤ x1 x1 ≤
4 3
2 ≤ x1 3 4 ≤ x1 3 melyb˝ol x1 = 43 ad´odik. 4 Teh´at a keresked˝o haszna akkor a legnagyobb ( 19 3 EUR), ha 3 liter rostos ´es 73 liter sz´ensavas u ¨d´ıt˝ot ad el a gyermeknek. 5. feladat. Minden eddigi feladat megold´asa Fourier m´odszerrel.
2.4. Standard LP feladat Defin´ıci´ o. Az Ax = b x≥0 z(x) = cx → max t´ıpus´ u LP feladatot, ahol A az x1 , x2 , . . . , xn v´altoz´ok egy¨ utthat´oit tartalmaz´o m´atrix, b ≥ 0, standard LP feladatnak nevezz¨ uk.
12
Mj: Egy val´os vektor nagyobb vagy egyenl˝o mint nulla, ha minden komponense nagyobb vagy egyenl˝o mint nulla. ´ ıt´ All´ as. Tetsz˝oleges LP feladathoz megkonstru´alhat´o egy olyan standard feladat, hogy a k´et feladatnak egyidej˝ uleg l´etezik optim´alis megold´asa, ´es a standard feladat megold´as´ ab´ol k¨ozvetlen¨ ul megkaphatjuk az eredeti feladat megold´as´at. Bizony´ıt´ as. A konstrukci´o l´ep´esei: (1) Alulr´ ol korl´ atos v´ altoz´ o helyettes´ıt´ese. Amennyiben valamely xi v´altoz´o nemnulla als´o korl´attal szerepel a felt´etelek k¨oz¨ott: pl. xi ≥ r, akkor vezess¨ unk be egy u ´j v´altoz´ot: legyen y = xi − r. Vil´agos, hogy ekkor y ≥ 0 ´es ez a v´altoz´ocsere a megoldhat´os´agot nem befoly´asolja, tov´abb´a az u ´ j feladatot megoldva k¨ovetkeztethet¨ unk xi ´ert´ek´ere. (2) Alulr´ ol nem korl´ atos v´ altoz´ ok helyettes´ıt´ese k´et nemnegat´ıv v´ altoz´ o k¨ ul¨ onbs´eg´evel. A feladatban szerepl˝o alulr´ol nem korl´atos xi v´altoz´ok mindegyik´et az ui , vi nemnegat´ıv v´altoz´ok k¨ ul¨onbs´eg´evel helyettes´ıthetj¨ uk: xi = ui − vi , ahol ui ≥ 0 ´es vi ≥ 0. (3) Az ¨ osszes negat´ıv jobboldali ´ert´ek megv´ altoztat´ asa. Szorozzuk meg az ¨osszes olyan egyenl˝otlens´eget −1-gyel, melynek jobboldala negat´ıv. (4) Az ¨ osszes egyenl˝ otlens´eg ´ at´ır´ asa egyenl˝ os´egg´e. Ha az i-edik felt´etel egyenl˝otlens´eg, pl. ai1 x1 + ai2 x2 + · · · + ain xn ≤ b1 , akkor ezt egy ui u ´j nemnegat´ıv v´altoz´o bevezet´es´evel ´ırjuk ´at a k¨ovetkez˝ok´eppen: ai1 x1 +ai2 x2 +· · ·+ain xn +ui = b1 . Ford´ıtott ir´any´ u egyenl˝otlens´eg eset´en pedig ui kivon´asa sz¨ uks´eges. ´ er´es maximum feladatra. Mivel a min{z(x) : x ∈ L} ´es (5) Att´ a max{−z(x) : x ∈ L} ´ert´ekek egyidej˝ uleg l´eteznek ill. nem l´eteznek, tov´abb´a min{z(x) : x ∈ L} = − max{−z(x) : x ∈ L}, az optim´alis megold´as l´etez´ese ´es meghat´aroz´asa szempontj´ab´ol elegend˝o pl. csak maximum-feladatok vizsg´alat´ara szor´ıtkozni. (Teh´at minimum feladat eset´en az eredeti c´elf¨ uggv´enyt szorozzuk meg −1gyel ´es keress¨ uk annak maximum´at.) V´eg¨ ul, ha a c´elf¨ uggv´enyben szerepel konstans, akkor hagyjuk el azt. K¨onnyen igazolhat´o, hogy a r´egi ´es a fenti l´ep´esek alkalmaz´as´aval el˝o´all´ıtott u ´j feladatoknak egyidej˝ uleg l´etezik optim´alis megold´asa, ´es az optim´alis megold´asok k¨ozvetlen¨ ul sz´armaztathat´ok egym´asb´ol.
K¨ ovetkezm´ eny. Az optim´alis megold´as l´etez´es´et ´es meghat´aroz´as´at illet˝oen elegend˝o a standard feladatok vizsg´alat´ara szor´ıtkozni.
´ ´ LINEARIS PROGRAMOZAS
13
P´ elda. Hat´arozzuk meg az 3x1 + x2 − 4x3 2x1 − x2 + 5x3 x1 + x2 + x3 x1 ≥ 3, x2
≥ −2 ≥8 =4 ≥0
z(x) = −2x1 + 6x2 + x3 → min LP feladathoz azt a standard feladatot, amelyre az visszavezethet˝o. Az x1 v´altoz´o alulr´ol korl´atos ugyan, de als´o korl´atja nem nulla. Legyen y = x1 − 3, ahonnan x1 = y + 3, s helyettes´ıts¨ uk ezt be mindegyik felt´etelbe ´es a c´elf¨ uggv´enybe. A k¨ovetkez˝o feladathoz jutunk: 3y + x2 − 4x3 2y − x2 + 5x3 y + x2 + x3 y ≥ 0, x2
≥ −11 ≥2 =1 ≥0
z1 (x2 , x3 , y) = −2y + 6x2 + x3 − 6 → min . A k¨ovetkez˝o l´ep´esben az x3 v´altoz´ot fogjuk helyettes´ıteni a v1 ´es v2 nemnegat´ıv v´altoz´ok k¨ ul¨onbs´eg´evel: 3y + x2 − 4v1 + 4v2 2y − x2 + 5v1 − 5v2 y + x2 + v1 − v2 y, x2 , v1 , v2
≥ −11 ≥2 =1 . ≥0
z2 (x2 , y, u, v) = −2y + 6x2 + v1 − v2 − 6 → min, Az els˝o felt´etel jobboldala negat´ıv, ez´ert szorozzuk be az egyenl˝otlens´eget −1-gyel: −3y − x2 + 4v1 − 4v2 ≤ 11, majd az egyenl˝otlens´egeket sz¨ untetj¨ uk meg: −3y − x2 + 4v1 − 4v2 + u1 2y − x2 + 5v1 − 5v2 − u2 y + x2 + v1 − v2 y, x2 , v1 , v2 , u1 , u2
= 11 =2 =1 ≥0
z2 (x2 , y, u, v) = −2y + 6x2 + v1 − v2 − 6 → max . V´eg¨ ul ´att´er¨ unk maximum feladatra, azaz z2 minimuma helyett a z3 (x2 , y, u, v) = 2y − 6x2 − v1 + v2 + 6
14
f¨ uggv´eny maximum´at keress¨ uk. A c´elf¨ uggv´enyb˝ol a konstanst elhagyva a −3y − x2 + 4v1 − 4v2 + u1 2y − x2 + 5v1 − 5v2 − u2 y + x2 + v1 − v2 y, x2 , v1 , v2 , u1 , u2
= 11 =2 =1 ≥0
z4 (x2 , y, u, v) = 2y − 6x2 − v1 + v2 → max feladat ad´odik, amely m´ar a keresett standard feladat. Defin´ıci´ o. Azt mondjuk, hogy k´et standard feladat ekvivalens, ha a megengedett megold´asainak halmaza mindk´et feladatn´al ugyanaz ´es ezen a halmazon a k´et feladat c´elf¨ uggv´enye egyenl˝o. Mj. Nyilv´an a fenti ekvivalencia ekvivalencia-rel´aci´o a standard LP feladatok halmaz´an.
2.5. B´azis, b´azismegold´as Tekints¨ uk az Ax = b x≥0 z(x) = c1 x1 + · · · + cn xn → max standard LP feladatot, ahol
a11 a21 A = .. .
a12 a22 .. .
a1n a2n .. , .
... ... .. .
am1 am2 . . .
amn
valamint x = (x1 , x2 , . . . xn )T ,
´es
b = (b1 , b2 , . . . bm )T .
Jel¨olje Aj az A m´atrix j-edik oszlopvektor´at, azaz Aj = (a1j , a2j , . . . , amj )T . Ekkor az LP feladat felt´etelrendszere n ∑
Aj xj = b
j=1
alakba ´ırhat´o. Feltehet˝o, hogy az A m´atrix rangja m. (Mi´ert?) Defin´ıci´ o. Az A m´atrix pontosan m darab line´ariasan f¨ uggetlen oszlopvektor´at tartalmaz´o B = {As1 , As2 , . . . , Asm } halmazt az LP feladat b´ azis´ anak, m´ıg a JB = {s1 , s2 , . . . , sm } halmazt pedig a B-hez tartoz´o b´ azisindexek halmaz´ anak nevezz¨ uk.
´ ´ LINEARIS PROGRAMOZAS
15
Haszn´aljuk m´eg a k¨ovetkez˝o jel¨ol´eseket: J = {1, 2, . . . n} ´es J B = J \ JB .
Vil´agos, hogy ha B b´azis, akkor a m ∑
Asi xsi = b
i=1
egyenletrendszer pontosan egy x′ = (x′s1 , x′s2 , . . . , x′sm )T megold´assal rendelkezik. ´ ıt´ All´ as. Az x = (x1 , x2 , . . . , xn )T vektor, ahol { x′j ha j ∈ JB ; xj = 0 ha j ̸∈ JB , az Ax = b line´aris egyenletrendszer megold´asa. Ezt az LP feladat b´ azismegold´ as´ anak nevezz¨ uk. Bizony´ıt´ as. n ∑
Aj xj =
j=1
∑ j∈JB
=
∑ j∈JB
Aj xj +
∑
Aj xj
j∈J B
Aj xj + 0 =
m ∑
Asi xsi = b.
i=1
Defin´ıci´ o. Ha x olyan b´azismegold´as, melynek egyik komponense sem negat´ıv, akkor azt mondjuk, hogy az x vektor lehets´ eges b´ azismegold´ asa (LBM), B pedig lehets´ eges b´ azisa az LP feladatnak. P´ elda. Legyen (
( ) ) x1 10 1 0 2 x2 = . 0 1 1 15 x3
Ha JB = {1, 2}, akkor B lehets´eges b´azis. Ha JB = {1, 3}, akkor B b´azis, de nem lehets´eges b´azis.
2.6. Szimplex m´odszer (1) Tetsz˝oleges LBM el˝o´all´ıt´asa. (2) Aktu´alis LBM vizsg´alata: ha optim´alis: v´ege, ha nem: goto (3). (3) Jobb LBM el˝o´all´ıt´asa, goto (2).
16
Legyen k ∈ J B ´es a jelenleg nulla xk ´ert´ek´et v´altoztassuk λ > 0-ra. Ennek hat´as´ara az xsi ´ert´ekek v´altozhatnak: xλsi , ´es hogy lehets´eges megold´ast kapjunk teljes¨ ulnie kell a m ∑
Asi xλsi + Ak λ = b
i=1
egyenl˝os´egnek. Fejezz¨ uk ki Ak -t a B elemeinek line´aris kombin´aci´ojak´ent: Ak =
m ∑
αik Asi ,
i=1
majd helyettes´ıts¨ uk az el˝oz˝ o egyenletbe: m ∑
Asi xλsi + Ak λ =
i=1
=
m ∑ i=1 m ∑
Asi xλsi +
m ∑
αik Asi λ
i=1
Asi (xλsi + αik λ) = b.
i=1
Innen xsi = xλsi + αik λ, vagyis xλsi = xsi − αik λ k¨ovetkezik b´armely i ∈ {1, 2, . . . , m}-re. Ahhoz, hogy lehets´eges megold´ashoz jussunk, m´eg teljes¨ ulnie kell az xλsi = xsi − αik λ ≥ 0 felt´etelnek is b´armely i ∈ {1, 2, . . . , m} eset´en. M´as sz´oval λ≤
xsi αik
minden olyan i-re, melyre αik > 0, ´es λ≥
xsi αik
minden olyan i-re, melyre αik < 0. Ebb˝ol { } { } xsi xsi (11) max ≤ λ ≤ min , i:αik <0 αik i:αik >0 αik s˝ot λ > 0 miatt
{ 0 < λ ≤ min
i:αik >0
k¨ovetkezik.
xsi αik
}
´ ´ LINEARIS PROGRAMOZAS
17
Most n´ezz¨ uk meg, mi t¨ort´enik a c´elf¨ uggv´eny ´ert´ek´evel. λ
z(x ) = = (12) =
m ∑ i=1 m ∑ i=1 m ∑
csi xλsi
+ ck λ =
m ∑
csi (xsi − αik λ) + ck λ
i=1
csi xsi − λ
m ∑
csi αik + ck λ
i=1 m ∑
csi xsi − λ(
i=1
i=1
|
csi αik −ck ) {z
}
zk
= z(x) − λ(zk − ck ) = z(x) − λ∆k . | {z } ∆k
Bizony´ıtottuk: ´ ıt´ All´ as (Optimalit´ asi krit´ erium). Ha x LBM-a egy standard LP feladatnak, ´es ∆k > 0 minden k ∈ J B eset´en, akkor x optim´alis megold´as. Ha van olyan k ∈ J B , melyre ∆k < 0, akkor a k¨ovetkez˝o esetek lehets´egesek: (1) αik < 0 b´armely i ∈ {1, 2, . . . , m} eset´en. Ekkor (11) szerint λ tetsz˝olegesen nagy lehet, ez´ert a z fel¨ ulr˝ol nem korl´aros az L halmazon. (2) L´etezik i ∈ {1, 2, . . . , m} melyre αik > 0. Ekkor a c´elf¨ uggv´eny a legnagyobb lehets´eges λ ´ert´ek mellett n¨ovekszik legink´abb, teh´at (11) szerint legyen { } xsi xs λ = min = r. i:αik >0 αik αrk Ekkor xλsr = 0 ´es xk = λ. Ak az u ´j b´azisban az r-edik poz´ıci´oba ker¨ ul˝o vektor, Asr pedig a b´azist elhagy´o vektor. Az u ´j b´azis: B ′ = {As1 , As2 , . . . , Asr−1 , Ak , Asr+1 , . . . , Asm }, az u ´j LBM xλ = (xλ1 , xλ2 , . . . , xλn )T , ahol
xj − αjk λ, 0, xλj = λ, 0,
ha j ha j ha j ha j
∈ JB , j ̸= sr ; ∈ JB , j = sr ; = k; ∈ J B , j ̸= k.
18
2.7. Szimplex t´abla B As1 As2 .. . Asm
zB cs1 cs2 .. .
c1 A1 α11 α21 .. .
xB xs1 xs2 .. .
csm xsm z(x)
c2 A2 α12 α22 .. .
αm1 αm2 ∆1 ∆2
··· ··· ··· ··· ··· ··· ···
cn An α1n α2n .. . αmn ∆n
A szimplex t´abla v´altoz´asa b´aziscsere eset´en: – αrk elemet gener´al´o elem – r-edik sor: gener´al´o sor – k-adik oszlop: gener´al´o oszlop (1) A gener´al´o sor ¨osszes elem´et osztjuk a gener´al´o elemmel. α αik (2) A t¨obbi sorhoz tartoz´o αij elemek u ´j ´ert´eke: αij − rj αrk . (3) A gener´al´o oszlop minden m´as elem´et null´ara v´altoztatjuk.
Koncepci´ok: Bel´ep˝o vektor meghat´aroz´as´ara: v´alasszuk a negat´ıv ∆j -k minimum´at! (Igaz´ab´ol (12) szerint a c´elf¨ uggv´eny´ert´ek a negat´ıv ∆j λ ´ert´ekek minimum´anak v´alaszt´asa eset´en n¨ovekedne a legnagyobb m´ert´ekben, de ennek figyel´es´et˝ol ´altal´aban eltekint¨ unk.) Kil´ep˝o vektor meghat´aroz´asa: mimim´alis index szerint. (Probl´ema!!!)
P´ elda. Tekints¨ uk a k¨ovetkez˝o standard LP feladatot: x1 + 2x3 + x4 = 100 x2 + x3 + 2x4 = 150 x1 , x2 , x3 , x4 ≥ 0 z(x) = 5x1 + 8x2 + 19x3 + 6x4 → max Indul´o LBM: B = {A1 , A2 },
JB = {1, 2},
B zB xB A1 5 100 A2 8 150 z(x) = 1700
x = (100, 150, 0, 0)
5 8 19 6 A1 A2 A3 A4 1 0 2 1 0 1 1 2 0 0 −1 15
´ ´ LINEARIS PROGRAMOZAS
B A3 A2 z(x) 6. feladat. Oldja meg
19
5 8 19 6 zB xB A1 A2 A3 A4 19 50 0, 5 0 1 0, 5 8 100 −0, 5 1 0 1, 5 = 1750 0, 5 0 0 15, 5 szimplex m´odszerrel a horg´asz probl´em´at!
7. feladat. Oldja meg szimplex m´odszerrel a k¨ovetkez˝o feladatokat! a) x+y x−y −x + 2y x ≥ 0, y
≤7 ≤1 ≤8 ≥0
z(x, y) = x + 2y → max b) 2x1 + 2x2 + 8x3 x1 + 3x2 + 2x3 3x1 + 2x2 + 1x3 x1 , x2 , x3
≤ 600 ≤ 600 ≤ 400 ≥0
z(x, y) = x1 + 2x2 + 3x3 → max
2.8. Indul´o LBM meghat´aroz´asa 2.8.1. Nagy M m´ odszer. Legyen adva egy standard LP feladat. Az ehhez tartoz´o M -feladat: vezess¨ uk be a felt´etelrendszer i. egyenlet´ebe az xn+i nemnegat´ıv mesters´eges v´altoz´ot egy egy¨ utthat´oval, a c´elf¨ uggv´enyben pedig legyen ezen v´altoz´ok egy¨ utthat´oja −M , ahol M egy el´eg nagy pozit´ıv sz´am. Ekkor a M -feladatban a B = {An+1 , An+2 , . . . , An+m } halmazt haszn´alhatjuk indul´o lehets´eges b´azisk´ent (hiszen ezek ´eppen az m dimenzi´os standard b´azis vektorai), melyhez tartoz´o LBM x e = (0, 0, . . . , 0, b1 , b2 , . . . , bm ). | {z } n
´ ıt´ All´ as (Nagy M m´ odszer f˝ ot´ etele). Tegy¨ uk fel, hogy x e = (e x1 , x e2 , . . . , x en , x en+1 , x en+2 , . . . , x en+m ) optim´alis megold´asa a M -feladatnak. Ha x en+i = 0 minden i ∈ {1, 2, . . . , m}re, azaz minden mesters´eges v´altoz´o ´ert´eke z´er´o, akkor az x = (e x1 , x e2 , . . . , x en ) optim´alis megold´asa az eredeti LP feladatnak. Egy´ebk´ent az eredeti LP feladat lehets´eges megold´asainak halmaza u ¨res.
20
P´ elda. Oldjuk meg a x1 + x2 + 4x3 = 120 2x1 + 4x2 + 3x3 = 150 x1 , x2 , x3 ≥ 0 z(x) = x1 + 3x2 + 2x3 → max standard LP feladatot. Az ehhez tartoz´o M -feladat: x1 + x2 + 4x3 + x4 = 120 2x1 + 4x2 + 3x3 + x5 = 150 x1 , x2 , x3 , x4 , x5 ≥ 0 z(x) = x1 + 3x2 + 2x3 − M x4 − M x5 → max Indul´o LBM: B = {A4 , A5 }, B zB A4 −M A5 −M z(x) = B zB A3 2 A5 −M z(x) =
x = (0, 0, 0, 120, 150)
1 3 2 −M A1 A2 A3 A4 1 1 4 1 2 4 3 0 −3M − 1 −5M − 3 −7M − 2 0
xB 120 150 −270M
xB 30 60 −60M + 60
1 A1
3 A2
1 4 5 4
1 4 13 4
− 45 M − 1/2 − 13 4 M −
5 2
2 A3 1 0 0
−M A5 0 1 0
−M A4 1 4
− 34 7 4M +
3 4
1 3 2 −M −M B zB xB A1 A2 A3 A4 A5 A3 2 330/13 2/13 0 1 4/13 −1/13 A2 3 240/13 5/13 1 0 −3/13 4/13 z(x) = 1380/13 6/13 0 0 M − 1/13 M + 10/13 Teh´at az M -feladat optim´alis megold´asa x e = (0, 240/13, 330/13, 0, 0), ´es a M -m´odszer f˝ot´etele ´ertelm´eben az x = (0, 240/13, 330/13) optim´alis megold´asa az eredeti feladatnak. 8. feladat. Oldja meg M -m´odszerrel az al´abbi feladatot! x1 + x2 ≤ 10 −x1 + x2 ≥ 2 x1 , x2 ≥ 0 z(x, y) = 2x1 + x2 → max
−M A5 0 1 0
´ ´ LINEARIS PROGRAMOZAS
21
9. feladat. Egy v´allalat k´etf´ele fest´eket gy´art, melyekhez k´etf´ele alapanyagot haszn´al. Jel¨olje ezeket az anyagokat A ´es B. Az alapanyagok naponta korl´atozott mennyis´egben ´allnak rendelkez´esre; az A anyagb´ol 6 a B anyagb´ol 8 egys´eg. Az els˝o fest´ekhez 1 egys´egnyi A ´es 2 egys´egnyi B kell, m´ıg a m´asodikhoz 2 egys´egnyi A ´es 1 egys´egnyi B sz¨ uks´eges. A piackutat´as azt mutatja, hogy a napi kereslet az els˝o fest´ekre legfeljebb egy egys´egnyivel t¨obb, mint a m´asodikra, tov´abb´a a m´asodikra nem haladja meg a napi k´et egys´eget. A els˝o fest´ek ´ara egys´egenk´ent 3 a m´asodik´e 2. Hat´arozza meg a szimplex algoritmus seg´ıts´eg´evel, hogy melyik fest´ekb˝ol mennyit kell gy´artania a v´allalatnak, ha maximaliz´alni akarja a bev´etelt? 10. feladat. Bevco c´eg egy Oranj nev˝ u narancs ´ızes´ıt´es˝ u u ¨d´ıt˝oitalt gy´art narancs-sz´oda ´es narancsl´e kombin´al´as´aval. Egy deka narancs-sz´oda 0, 5 deka cukrot ´es 1 mg C-vitamint, 1 deka narancsl´e pedig 0, 25 deka cukrot ´es 3 mg C-vitamint tartalmaz. A Bevconak 1 deka narancssz´oda 2 centbe ker¨ ul, 1 deka narancsl´e pedig 3 centbe. A Bevco marketing oszt´alya elhat´arozta, hogy minden 10 dek´as Oranj-palack legal´abb 20 mg C-vitamint ´es legfeljebb 4 deka cukrot tartalmazhat. Line´aris programoz´as seg´ıts´eg´evel hat´arozzuk meg, hogy a Bevco c´eg hogyan tud eleget tenni a marketing oszt´aly k¨ovetelm´enyeinek minim´alis k¨olts´eggel! 2.8.2. K´etf´ azis´ u szimplex m´ odszer. Adott standard LP feladathoz tartoz´o 1. f´azis´ u feladat: vezess¨ uk be a felt´etelrendszer i. egyenlet´ebe az xn+i nemnegat´ıv mesters´eges v´altoz´ot egy egy¨ utthat´oval. Az eredeti c´elf¨ uggv´eny helyett pedig keress¨ uk a ze(x) = −xn+1 − xn+2 − · · · − xn+m f¨ uggv´eny maximum´at. Ekkor az 1. f´azis´ u feladatban a B = {An+1 , An+2 , . . . , An+m } halmazt haszn´alhatjuk indul´o lehets´eges b´azisk´ent (hiszen ezek ´eppen az m dimenzi´os standard b´azis vektorai), melyhez tartoz´o LBM x e = (0, 0, . . . , 0, b1 , b2 , . . . , bm ). | {z } n
´ ıt´ All´ as (K´ etf´ azis´ u szimplex m´ odszer f˝ ot´ etele). Tegy¨ uk fel, hogy x e = (e x1 , x e2 , . . . , x en , x en+1 , x en+2 , . . . , x en+m ) optim´alis megold´asa az 1. f´azis´ u feladatnak. Ha x en+i = 0 minden i ∈ {1, 2, . . . , m}-re, azaz minden mesters´eges v´altoz´o ´ert´eke z´er´o, akkor az x = (e x1 , x e2 , . . . , x en ) lehets´eges b´azismegold´asa az eredeti LP feladatnak. Egy´ebk´ent az eredeti LP feladat lehets´eges megold´asainak halmaza u ¨res.
22
P´ elda. Oldjuk meg a x1 + x2 + 4x3 = 120 2x1 + 4x2 + 3x3 = 150 x1 , x2 , x3 ≥ 0 z(x) = x1 + 3x2 + 2x3 → max standard LP feladatot. Az ehhez tartoz´o 1. f´azis´ u feladat: x1 + x2 + 4x3 + x4 = 120 2x1 + 4x2 + 3x3 + x5 = 150 x1 , x2 , x3 , x4 , x5 ≥ 0 z(x) = −x4 − x5 → max Indul´o LBM: B = {A4 , A5 }, B zB xB A4 −1 120 A5 −1 150 z(x) = −270 B zB xB A3 0 30 A5 −1 60 z(x) = −60 B zB xB A3 0 330/13 A2 0 240/13 z(x) = 0
x = (0, 0, 0, 120, 150) 0 0 0 −1 −1 A1 A2 A3 A4 A5 1 1 4 1 0 2 4 3 0 1 −3 −5 −7 0 0
0 0 0 −1 −1 A1 A2 A3 A4 A5 1/4 1/4 1 1/4 0 5/4 13/4 0 −3/4 1 −5/4 −13/4 0 7/4 0 0 0 0 −1 −1 A1 A2 A3 A4 A5 2/13 0 1 4/13 −1/13 5/13 1 0 −3/13 4/13 0 0 0 1 1
Teh´at az 1. f´azis´ u feladat optim´alis megold´asa x e = (0, 240/13, 330/13, 0, 0), amely a B = {A2 , A3 } b´azishoz tartozik. 2. f´azis. B zB xB A3 2 330/13 A2 3 240/13 z(x) = 1380/13
1 3 2 A1 A2 A3 2/13 0 1 5/13 1 0 6/13 0 0
´ ´ LINEARIS PROGRAMOZAS
2.9. Lexikografikus szimplex m´odszer Oldjuk meg a k¨ovetkez˝o LP feladatot! (A. W. Tucker) x1 − 2x4 − 9x5 + x6 + 9x7 1 1 x2 + x4 + x5 − x6 − 2x7 3 3 x3 + x4 + x5 + x6 + x7 x1 , x2 , x3 , x4 , x5 , x6 , x7
=0 =0 =1 ≥0
z(x) = 2x4 + 3x5 − x6 − 12x7 → max 1. iter´aci´o B zB xB A1 0 0 A2 0 0 A3 0 1 z(x) = 0
0 0 0 2 3 −1 −12 A1 A2 A3 A4 A5 A6 A7 1 0 0 −2 −9 1 9 0 1 0 1/3 1 −1/3 −2 0 0 1 1 1 1 1 0 0 0 −2 −3 1 12
2. iter´aci´o sz. B zB xB A1 0 0 A5 3 0 A3 0 1 z(x) = 0
0 0 0 2 3 −1 −12 A1 A2 A3 A4 A5 A6 A7 1 9 0 1 0 −2 −9 0 1 0 1/3 1 −1/3 −2 0 −1 1 2/3 0 4/3 3 0 3 0 −1 0 0 6
3. iter´aci´o B zB xB A4 2 0 A5 3 0 A3 0 1 z(x) = 0
0 0 0 2 3 −1 −12 A1 A2 A3 A4 A5 A6 A7 1 9 0 1 0 −2 −9 −1/3 −2 0 0 1 1/3 1 −2/3 −7 1 0 0 8/3 9 1 12 0 0 0 −2 −3
4. iter´aci´o sz. B z B xB A4 2 0 A7 −12 0 A3 0 1 z(x) = 0 5. iter´aci´o
0 0 0 2 3 −1 −12 A1 A2 A3 A4 A5 A6 A7 −2 −9 0 1 9 1 0 −1/3 −2 0 0 1 1/3 1 7/3 11 1 0 −9 −1/3 0 0 6 0 0 3 −1 0
23
24
0 0 0 2 3 −1 −12 B zB xB A1 A2 A3 A4 A5 A6 A7 A6 −1 0 −2 −9 0 1 9 1 0 A7 −12 0 1/3 1 0 −1/3 −2 0 1 A3 0 1 5/3 8 1 1/3 −6 0 0 z(x) = 0 −2 −3 0 1 12 0 0 6. iter´aci´o sz. 0 0 0 2 3 −1 −12 B zB xB A1 A2 A3 A4 A5 A6 A7 A6 −1 0 1 0 0 −2 −9 1 9 A2 0 0 1/3 1 0 −1/3 −2 0 1 A3 0 1 −1 0 1 3 10 0 −8 z(x) = 0 −1 0 0 0 6 0 3 7. iter´aci´o 0 0 0 2 3 −1 −12 B zB xB A1 A2 A3 A4 A5 A6 A7 A1 0 0 1 0 0 −2 −9 1 9 A2 0 0 0 1 0 1/3 1 −1/3 −2 A3 0 1 0 0 1 1 1 1 1 z(x) = 0 0 0 0 −2 −3 1 12 L´athat´o, hogy v´eg¨ ul a kiindul´o t´abl´at nyert¨ uk vissza, teh´at az eddigi koncepci´ok szerint v´egrehajtott elj´ar´as v´egtelen. Kider¨ ult, hogy az algoritmus v´egess´eg´et a gener´al´o elem kiv´alaszt´as´anak strat´egi´aja d¨ont˝oen befoly´asolja. Defin´ıci´ o. Legyen x, y ∈ Rn . Azt mondjuk, hogy x lexikografikusan kisebb vagy egyenl˝ o mint y, ha az x − y vektor els˝o null´at´ol k¨ ul¨onb¨oz˝o komponense negat´ıv. Ennek kifejez´es´ere az x ≼ y jel¨ol´est haszn´aljuk. Mj. A fent bevezetett rel´aci´o teljes rendez´es Rn -ben. P´ elda. (1, 2, 3, 4, 2) ≼ (1, 2, 5, 6, 1).
Lexikografikus szimplex m´ odszer : Tegy¨ uk fel, hogy } { xsrl xsr1 xsr2 xsi = = = ··· = . λ = min i:αik >0 αik αr1 k αr2 k αrl k Tekints¨ uk a hrj = (xrj , αrj 1 , αrj 2 , . . . αrj n )/αrj k vektorokat, ahol j ∈ {1, 2, . . . , l}. Ezek nyilv´an a szimplex t´abla soraihoz rendelhet˝ok. V´alasszuk gener´al´o sornak azt, amelyhez tartoz´o vektor lexikografikusan a legkisebb. Ez a v´alaszt´as nyilv´an egy´ertelm˝ u, ugyanis a szimplex t´abla mindig tartalmaz egys´egm´atrixot, ´ıgy nem lehet k´et azonos sora. ´ ıt´ All´ as. A lexikografikus szimplex algoritmus v´eges sok l´ep´es ut´an befejez˝odik.
´ ´ LINEARIS PROGRAMOZAS
25
11. feladat. Oldjuk meg Tucker feladat´at a lexikografikus szimplex m´odszerrel!
2.10. Alternat´ıv optim´alis megold´as El˝ofordulhat, hogy egy LP feladatnak t¨obb optim´alis megold´asa is van. Ez a szimplex t´abl´aban u ´gy l´atszik, hogy valamely Aj0 nemb´azis vektorhoz tartoz´o ∆j0 = 0. Ekkor az Aj0 vektort a b´azisba bevezethetj¨ uk, a c´elf¨ uggv´eny ´ert´eke nem v´altozik, ugyanis l´attuk, hogy P (xλ ) = P (x) − λ∆j0 = P (x). 12. feladat. Oldjuk meg az 1-4. feladatokat szimplex m´odszerrel!
2.11. Dualit´as Defin´ıci´ o. Az Ax ≤ b x≥0 z(x) = cx → max LP feladat du´ alis´ an a yA ≥ c y≥0 ζ(y) = yb → min LP feladatot ´ertj¨ uk. Ez esetben az eredeti feladatot pr´ım´ al feladatnak is nevezz¨ uk. Nyilv´an a du´alis feladat du´alisa a pr´ım´al feladat.
P´ elda. Egy u ¨zem k´etf´ele term´eket (T1 , T2 ) gy´art h´arom anyagf´eles´eg (A, B, C) felhaszn´al´as´aval. Minden T1 term´eken 8 p´enzegys´eg a nyeres´eg, m´ıg a T2 term´eken 12 p´enzegys´eg. Egy T1 term´ek el˝o´all´ıt´as´ahoz rendre 6 darab A, 2 darab B ´es 2 darab C anyagf´eles´eg sz¨ uks´eges. Ugyanezek az ´ert´ekek a T2 term´ek eset´eben rendre 4, 6, 2 darab. Az rendelkez´esre ´all´o anyagmennyis´egek: 60, 46, illetve 22 darab. Milyen napi termel´es maximaliz´alja az u ¨zem nyeres´eg´et? A probl´ema modellje: – x1 : legy´artand´o mennyis´eg a T1 term´ekb˝ol – x2 : legy´artand´o mennyis´eg a T2 term´ekb˝ol
26
6x1 + 4x2 2x1 + 6x2 2x1 + 2x2 x1 , x2
≤ 60 ≤ 46 ≤ 22 ≥0
z(x) = 8x1 + 12x2 → max A feladat du´ alisa: 6y1 + 2y2 + 2y3 ≥ 8 4y1 + 6y2 + 2y3 ≥ 12 y 1 , y2 , y3 ≥ 0 ζ(y) = 60y1 + 46y2 + 22y3 → min A du´ alis ´ertelmez´ese: Tegy¨ uk fel, hogy valaki fel szeretn´e v´as´arolni az u ¨zem er˝oforr´asait. Jel¨olje az yi v´altoz´o azt az ´arat amennyit a v´as´arl´o aj´anl fel az i-edik anyagf´eles´eg´ert. Ezeket az ´arakat ´ arny´ ek´ araknak nevezz¨ uk. A du´alis feladat korl´atoz´o egyenl˝otlens´egei azt biztos´ıtj´ak, hogy az aj´anlott ´arak versenyk´epesek legyenek. P´eld´aul az els˝o egyenl˝otlens´eg azt mondja, hogy egy T1 term´ek alapanyagai´ert kifizetett ´ar ne legyen kisebb a T1 term´eken nyert profitn´al. Ez az´ert fontos, mivel ellenkez˝o esetben a gy´ar m´eg akkor is jobban j´arna az er˝oforr´asok elad´as´an´al, ha csak T1 -et gy´artana. A c´elf¨ uggv´eny ´ert´eke az ¨osszes er˝oforr´as´ert felaj´anlott ¨osszeg. A minimaliz´al´as az er˝oforr´as v´as´arl´oj´anak ´erdekeit t¨ ukr¨ozi, teh´at azt, hogy az er˝oforr´asokat min´el olcs´obban tudja megvenni. ´ ıt´ All´ as. Ha x∗ lehets´eges megold´asa a pr´ım´al feladatnak ´es y ∗ lehets´eges megold´asa a du´al feladatnak, akkor z(x∗ ) ≤ ζ(y ∗ ). Bizony´ıt´ as. Jel¨olje LP a pr´ım´al ´es LD a du´al feladat lehets´eges megold´asainak halmaz´at. Mivel x∗ ∈ LP , ez´ert n ∑
aij x∗j ≤ bi
i ∈ {1, 2, . . . m}.
j=1
M´asr´eszt y ∗ ∈ LD miatt y ∗ ≥ 0, ´ıgy n ∑
aij x∗j yi∗ ≤ bi yi∗
i ∈ {1, 2, . . . m}.
j=1
¨ Osszegezve az egyenl˝otlens´egek bal- ´es jobboldalain szerepl˝o mennyis´egeket, m ∑ n ∑ i=1 j=1
aij x∗j yi∗ ≤
m ∑ i=1
bi yi∗ = ζ(y ∗ )
´ ´ LINEARIS PROGRAMOZAS
27
ad´odik. Vizsg´aljuk ezek ut´an a baloldali ¨osszeget. Ha az aij x∗j yi∗ elemet egy m × n- es m´atrix ij index˝ u elem´enek tekintj¨ uk, akkor a kifejez´es ezen m´atrix elemeinek ¨osszege, m´egpedig el˝osz¨or soronk´ent ¨osszegz¨ unk, majd a sor¨osszegeket adjuk ¨ossze. Nyilv´an ugyanezt az ¨osszeget kapjuk, ha el˝osz¨or oszloponk´ent ¨osszegz¨ unk, majd az oszlop¨osszegeket adjuk ¨ossze. ´Igy m m ∑ n n ∑ m n ∑ ∑ ∑ ∑ ∗ ∗ ∗ ∗ ∗ aij yi∗ . aij xj yi = aij xj yi = xj i=1 j=1
j=1 i=1
j=1
i=1
x∗j
egy¨ utthat´oja a du´alis feladat j-edik egyenl˝otlens´eA kapott kifejez´esben g´enek baloldala. Tov´abb´a x∗ ∈ LP , ´ıgy x∗ ≥ 0. Mindezek alapj´an m ∑ ∗ xj aij yi∗ ≥ cj x∗j , j ∈ {1, 2, . . . n}. i=1
Az oldalak ¨osszegz´ese ut´an az ´all´ıtott rel´aci´o k¨ozvetlen¨ ul ad´odik.
K¨ ovetkezm´ eny. Ha a pr´ım´al feladat c´elf¨ uggv´enye fel¨ ulr˝ol nem korl´atos a lehets´eges megold´asok halmaz´an, akkor a du´al feladatnak nincsen lehets´eges megold´asa. Bizony´ıt´ as. Ha y ∗ lehets´eges megold´asa lenne a du´alis feladatnak, akkor ulne. De ekkor az ´all´ıt´as alapj´an tetsz˝oleges x∗ ∈ LP -re z(x∗ ) ≤ ζ(y ∗ ) teljes¨ ζ(y ∗ ) fels˝o korl´atja lenne a z(x∗ ) x∗ ∈ LP ´ert´ekeknek, ami ellentmond´as. Hasonl´oan: K¨ ovetkezm´ eny. Ha a du´al feladat c´elf¨ uggv´enye alulr´ol nem korl´atos a lehets´eges megold´asok halmaz´an, akkor a pr´ım´al feladatnak nincsen lehets´eges megold´asa. ´ ıt´ All´ as (Dualit´ as f˝ ot´ etele). Ha a pr´ım´al, du´al feladatok k¨oz¨ ul valamelyiknek l´etezik optim´alis megold´asa, akkor mindk´et feladatnak l´etezik optim´alis megold´asa ´es az optimum´ert´ekek megegyeznek. 2.11.1. A pr´ım´ al ´es du´ al feladat felt´etelei. Defin´ıci´ o. Egy LP feladat felt´etelei k¨oz¨ ul egy adott egyenl˝otlens´eget r¨ ogz´ıtett felt´ etelnek nevez¨ unk, ha a feladat b´armely optim´alis megold´as´an´al abban egyenl˝os´eg teljes¨ ul. Ellenben, ha van legal´abb egy olyan optim´alis megold´asa a feladatnak, melyn´el a sz´obanforg´o felt´etelben szigor´ u egyenl˝otlens´eg ´all fenn, akkor azt szabad felt´ etelnek mondjuk. Defin´ıci´ o. Legyen adott egy du´alis feladatp´ar. Az i-edik n ∑ aij xj ≤ bi , yi ≥ 0 j=1
felt´eteleket ´es a j-edik m ∑ i=1
aij yi ≥ cj ,
xj ≥ 0
28
felt´eteleket du´ alis felt´ etelp´ aroknak nevezz¨ uk. P´ elda. Tekints¨ uk a k¨ovetkez˝o (pr´ım´al) LP feladatot! x1 + 2x2 + 3x3 + 4x4 ≤ 100 5x1 + 6x2 + 7x3 + 8x4 ≤ 150 x1 , x2 , x3 , x4 ≥ 0 z(x) = 15x1 + 16x2 + 17x3 + 18x4 → max Az ehhez tartoz´o du´alis feladat: y1 + 5y2 2y1 + 6y2 3y1 + 7y2 4y1 + 8y2 y1 , y 2
≥ 15 ≥ 16 ≥ 17 ≥ 18 ≥0
ζ(y) = 100y1 + 150y2 → min Du´alis felt´etelp´arok: x1 + 2x2 + 3x3 + 4x4 ≤ 100 5x1 + 6x2 + 7x3 + 8x4 ≤ 150 ≥0 ≥0 ≥0 ≥0
x1 x2 x3 x4
y1 ≥ 0; y2 ≥ 0; y1 + 5y2 ≥ 15; 2y1 + 6y2 ≥ 16; 3y1 + 7y2 ≥ 17; 4y1 + 8y2 ≥ 18;
´ ıt´ All´ as. Minden du´alis felt´etelp´arban az egyik felt´etel szabad, a m´asik pedig r¨ogz´ıtett. Az el˝oz˝o p´eld´at folytatva: – a pr´ım´al feladat egyetlen optim´alis megold´asa x∗ = (30, 0, 0, 0),
z(x∗ ) = 450;
– a du´alis feladat egyetlen optim´alis megold´asa y ∗ = (0, 3),
ζ(y ∗ ) = 450.
´ ´ LINEARIS PROGRAMOZAS
x∗1 + 2x∗2 + 3x∗3 + 4x∗4 = 30 < 100 sz.
y1∗ = 0 r.;
5x∗1 + 6x∗2 + 7x∗3 + 8x∗4 = 150 r.
y2∗ = 3 > 0 sz.;
x∗1 = 30 > 0 sz. x∗2 x∗3 x∗4
29
y1 + 5y2 = 15 r.;
= 0 r.
2y1∗ + 6y2∗ = 18 > 16 sz.;
= 0 r.
3y1∗ + 7y2∗ = 21 > 17 sz.;
= 0 r.
4y1∗ + 8y2∗ = 24 > 18 sz.;
´ ekenys´egvizsg´alat 2.12. Erz´ Tekints¨ uk az Ax = b x≥0 z(x) = c1 x1 + · · · + cn xn → max standard LP feladatot, tegy¨ uk fel, hogy x∗ = (x∗1 , x∗2 , . . . , x∗m , 0, . . . , 0) ennek optim´alis megold´asa, mely a B = {A1 , A2 , . . . , Am } b´azishoz tartozik. Ekkor JB = {1, 2, . . . , m}. Jel¨olje tov´abb´a AB azt az m × m-es m´atrixot, melynek oszlopvektorai a B elemei, tov´abb´a legyen x∗B = (x∗1 , x∗2 , . . . , x∗m ). 2.12.1. V´ altoz´ as a jobboldali vektorban. El˝osz¨or azt elemezz¨ uk, hogy a b vektor komponenseinek v´altoz´asa hogyan hat az optim´alis b´azisra ´es megold´asra, meddig lehet v´altoztatni ezeket az ´ert´ekeket an´elk¨ ul, hogy az optim´alis b´azis v´altozna. Mivel x∗ lehets´eges megold´as, ´ıgy AB x∗B = b teljes¨ ul, melyb˝ol x∗B = A−1 B b ad´odik. Ha az A−1 inverzm´ a trix elemeit u jel¨ o li, akkor ij B x∗i =
(13)
m ∑
uik bk
i ∈ {1, 2, . . . , m}.
k=1
V´altoztassuk meg a b vektor t-edik bt komponens´et bt + ε-ra. Ekkor (13) miatt az x′ vektor, ahol x′i
=
m ∑
uik bk + uit ε = x∗i + uit ε
i ∈ {1, 2, . . . , m}
k=1
´es x′i = 0 ha i > m, egy B b´ azishoz tartoz´o b´azismegold´asa a megv´altoztatott feladatnak. Ahhoz, hogy ez lehets´eges megold´as legyen, teljes¨ ulnie kell az ′ xi ≥ 0 felt´etelnek minden lehets´eges i-re. Az eddigiek alapj´an ez a felt´etel az uit ε ≥ −x∗i , i ∈ {1, 2, . . . , m} vagyis a ε≥−
x∗i , uit
ha uit > 0;
30
x∗i , ha uit < 0; uit felt´etelekkel ekvivalens. Kaptuk teh´at, hogy pontosan { } { } x∗i x∗i max − ≤ ε ≤ min − uit >0 uit <0 uit uit ε≤−
teljes¨ ul´ese eset´en lesz x′ lehets´eges megold´as. K´erd´es m´eg, hogy x′ optim´alis megold´as lesz-e, azaz v´altozik-e a c´elf¨ uggv´eny ´ert´eke a kiindul´o z(x∗ ) ´ert´ek´ehez k´epest. Az optimalit´asi krit´erium szerint egy lehets´eges megold´as akkor optim´alis, ha m ∑ ∆j = ci αij − cj ≥ 0 i=1
minden j ∈ {1, 2, . . . , n} eset´en. De eml´ekezz¨ unk arra, hogy x∗ optim´alis megold´as volt, teh´at arra ez a felt´etel teljes¨ ult, a b vektorban t¨ort´ent v´altoz´as ′ pedig erre nincs hat´assal. Teh´at x is optim´alis megold´as. Teh´at bizony´ıtottuk, hogy a b vektor t-edik komponens´eben bek¨ovetkezett bt → bt + ε v´altoz´as mindaddig nincs hat´assal az optim´alis b´azisra, m´ıg a { } { } x∗i x∗i max − ≤ ε ≤ min − uit >0 uit <0 uit uit felt´etel teljes¨ ul. A megkonstru´alt x′ vektor a feladat lehets´eges ´es optim´alis megold´asa. 2.12.2. V´ altoz´ as a c´elf¨ uggv´eny egy¨ utthat´ oiban. Helyettes´ıts¨ uk a c vektor t-edik komponens´et ct + ε-nal, ´es n´ezz¨ uk meg, hogy ez a v´altoz´as hogyan hat az optim´alis megold´asra. K´et esetet k¨ ul¨onb¨oztet¨ unk meg: 1. eset: t nem b´azisindex, azaz t ∈ J B . Ekkor csak ∆t v´altozik: ∆′t
=
m ∑
ci αit − (ct + ε) =
i=1
m ∑
ci αit − ct − ε = ∆t − ε.
i=1
Teh´at mindaddig, am´ıg ∆′t ≥ 0, azaz ε ≤ ∆t az optim´alis b´azis ´es megold´as nem v´altozik, s˝ot, m´eg maga az optimum´ert´ek sem. 2. eset: t b´azisindex, azaz t ∈ JB . A t b´azisindex volta miatt az ¨osszes ∆j , j ∈ {m + 1, m + 2, . . . , n} v´altozik: ∑ ∆′j = ci αij + (ct + ε)αtj − cj = ∆j + εαtj . i∈JB \{t}
Mivel a felt´etelek nem v´altoznak, x∗ tov´abbra is lehets´eges megold´as. Ahhoz, hogy optim´alis is maradjon, az ¨osszes nem b´azis index˝ u ∆′j = ∆j + εαtj -nek nemnegat´ıvnak kell lenni. M´as sz´oval a ε≥−
∆j , αtj
ha αtj > 0;
´ ´ LINEARIS PROGRAMOZAS
ε≤−
∆j , αtj
31
ha αtj < 0; ,
vagyis a { } { } ∆j ∆j ≤ε≤ min − max − j̸∈JB ,αtj <0 j̸∈JB ,αtj >0 αtj αtj felt´etel teljes¨ ul´ese sz¨ uks´eges ´es nyilv´an el´egs´eges. ¨ Osszefoglalva: A c vektor t-edik b´azisindex˝ u komponens´eben bek¨ovetkezett ct → ct + ε v´altoz´as mindaddig nincs hat´assal az optim´alis megold´asra, m´ıg a } { } { ∆j ∆j ≤ε≤ min − max − j̸∈JB ,αtj <0 j̸∈JB ,αtj >0 αtj αtj felt´etel teljes¨ ul. Az optimum´ert´ek nyilv´an ε f¨ uggv´eny´eben v´altozik.
2.13. Sz´all´ıt´asi feladat Adott m db rakt´ar, ahol egy bizonyos anyagf´eles´eg (a1 , a2 , . . . , am ), (a ≥ 0) mennyis´egben ´all rendelkez´esre, tov´abb´a adott n db felvev˝ohely (bolt), ahol erre az anyagf´eles´egre (b1 , b2 , . . . , bn ), (b ≥ 0)mennyis´egben van sz¨ uks´eg. Az i-edik rakt´arb´ol a j-edik felvev˝ohelyre egys´egnyi anyag ´atsz´all´ıt´as´anak a k¨olts´ege cij . Sz´all´ıtsuk el a rakt´arakban l´ev˝o anyagot a k´ıv´ant mennyis´egben a felvev˝ohelyekre u ´gy, hogy a sz´all´ıt´assal kapcsolatos k¨olts´egek ¨osszege minim´alis legyen. Az ´altal´anoss´ag megszor´ıt´asa n´elk¨ ul tehetj¨ uk fel, hogy m ∑ i=1
ai =
n ∑
bj .
j=1
Val´oban, ugyanis ha ez nem ´ıgy van, akkor u ´gynevezett fikt´ıv rakt´arak vagy fikt´ıv felvev˝ohelyek beiktat´as´aval el´erhet˝o az egyenl˝os´eg. Ha pl. az ¨osszig´eny m n ∑ ∑ nagyobb mint az ¨osszk´ın´alat, azaz ai < bj , akkor bevezet¨ unk egy i=1
fikt´ıv m + 1-edik telephelyet, am+1 =
n ∑ j=1
j=1
bj −
m ∑
ai k´eszlettel. Ebb˝ol a
i=1
rakt´arb´ol minden felvev˝ohelyre 0 lesz a sz´all´ıt´as k¨olts´ege. Teh´at olyan sz´all´ıt´ast kell megval´os´ıtanunk, amelynek sor´an minden telephelyr˝ol minden ´arut elsz´all´ıtanak, az egyes felvev˝ohelyek ig´enyeit kiel´eg´ıtik, ´es ezt mind u ´gy teszik, hogy az ¨ossz-sz´all´ıt´asi k¨olts´eg minim´alis.
32
Modell: jel¨olje xij az i-edik rakt´arb´ol a j-edik felvev˝ohelyre ´atsz´all´ıtand´o mennyis´eget. n ∑ j=1 m ∑
xij = ai
i ∈ {1, 2, . . . m}
xji = bi
i ∈ {1, 2, . . . n}
j=1
xij ≥ 0 z(x) =
m ∑ n ∑
cij xij → min
i=1 j=1
Ez tulajdonk´eppen egy LP feladat. P´ elda. – – – –
h´arom rakt´ar: R1 , R2 , R3 k´eszlet: (350, 200, 250) n´egy felvev˝ohely: F1 , F2 , F3 , F4 ig´enyek: (200, 200, 250, 150)
A k¨olts´egek: R1 R2 R3
F1 F2 F3 F4 2 1 6 5 3 4 3 2 4 2 2 8 200 200 250 150
350 200 250 800 = 800
2.13.1. Indul´ o LBM keres´ese ´eszaknyugat sarok m´ odszerrel. Induljunk ki a k¨ovetkez˝o t´abl´azatb´ol: F1 F2 · · · Fn R1 a1 R2 a2 ... ... Rm am b1 b2 · · · b n A m´odszer nem haszn´alja a k¨olts´egm´atrixot, ez´ert nem ´ırtuk be. A v´egrehajt´as a t´abl´azat bal fels˝o sark´aban kezd˝odik: legyen x11 = min{a1 , b1 }, ´ırjuk be ezt az els˝o sor els˝o oszlop´aba. ´Irjuk ´at a1 -et ´es b1 -et a k¨ovetkez˝o m´odon: a′1 = a1 − x11 , b′1 = b1 − x11 . Ha x11 = a1 , akkor els˝o sor, ha pedig x11 = b1 , akkor az els˝o oszlop t¨obbi cell´aj´aba ´ırjunk null´at! Ha x11 = a1 = b1 , akkor vagy az els˝o sort, vagy az els˝o oszlopot null´azzuk ki! Folytassuk az elj´ar´ast a megmaradt u ¨res m´atrix bal fels˝o sark´aban az x12 vagy az x21 v´altoz´oval! P´ elda.
´ ´ LINEARIS PROGRAMOZAS
F1
F2
F3
33
F4
R1 R2 R3
350 200 250 200 200 250 150
x11 = min{350, 200} = 200; R1 R2 R3
F1 F2 F3 F4 200 0 0 0 200 250 150
x12 = min{150, 200} = 150; R1 R2 R3
R1 R2 R3
R1 R2 R3
b′′2 = b′2 − x22 = 0;
0 150 250 b′3 = b3 − x23 = 100;
0 0 250
a′3 = a3 − x33 = 150;
F1 F2 F3 F4 200 150 0 0 0 50 150 0 0 0 100 0 0 0 150
x34 = min{150, 150} = 150;
b′2 = b2 − x12 = 50;
0 200 250
a′′2 = a′2 − x23 = 0;
F1 F2 F3 F4 200 150 0 0 0 50 150 0 0 0 0 0 100 150
x33 = min{250, 100} = 100;
150 200 250
a′2 = a2 − x22 = 150;
F1 F2 F3 F4 200 150 0 0 0 50 0 0 0 0 250 150
x23 = min{150, 250} = 150;
b′1 = b1 − x11 = 0;
a′′1 = a′1 − x12 = 0;
F1 F2 F3 F4 200 150 0 0 0 0 0 50 250 150
x22 = min{200, 50} = 50; R1 R2 R3
a′1 = a1 − x11 = 150;
b′′3 = b′3 − x33 = 0;
0 0 150
a′′3 = a′3 − x34 = 0;
b′4 = b4 − x34 = 0;
34
R1 R2 R3
F1 F2 F3 F4 200 150 0 0 0 50 150 0 0 0 100 150 0 0 0 0
0 0 0
B´aziscell´ak sz´ama: m+n−1=3+4−1=6 B´azisindexek: JB = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4)} B´azisv´altoz´ok: x11 = 200, x12 = 150, x22 = 50, x23 = 150, x33 = 100, x34 = 150 ´ ıt´ All´ as. B´armely sz´all´ıt´asi probl´em´anak van optim´alis megold´asa. Bizony´ıt´ as. A 0 ≤ xij ≤ min{ai , bj } i ∈ {1, 2, . . . , m}; j ∈ {1, 2, . . . , n} egyenl˝otlens´egek garant´alj´ak, hogy a lehets´eges megold´asok halmaza korl´atos ´es z´art. Tov´abb´a ez a halmaz nem u ¨res; a fenti algoritmus minden esetben el˝o´all´ıt egy lehets´eges megold´ast. Korl´atos ´es z´art halmaz felett pedig egy folytonos f¨ uggv´eny mindig felveszi minimum´at. 2.13.2. LBM ´es
Hurokszerkeszt´eses szimplex m´ odszer. Legyen adott az x indul´o
JB = {(i1 , j1 ), (i2 , j2 ), . . . , (im+n−1 , jm+n−1 )}. Rendelj¨ unk minden rakt´arhoz egy ui ´es minden felvev˝ohelyhez egy vj v´altoz´ot! ´Irjuk fel az ui + vj = cij egyenletet minden (i, j) ∈ JB eset´en. Ez egy m + n − 1 db egyenletet ´es m + n v´altoz´ot tartalmaz´o egyenletrendszerk´ent is felfoghat´o; legyen v1 = 0 ´es oldjuk meg! A megold´as ismeret´eben sz´amoljuk ki a dij = cij −(ui +vj ) ´ert´ekeket amikor (i, j) ∈ J B ! (Nyilv´an, ha (i, j) ∈ JB , akkor dij = 0.) Ha dij -k k¨oz¨ott nincs negat´ıv, akkor a vizsg´alt LBM optim´alis. Ha van k¨ozt¨ uk negat´ıv, akkor ki kell v´alasztani az egyiket ´es bevinni a b´azisba. P´ elda (folytat´ as). u1 + v1 u1 + v2 u2 + v2 u2 + v3 u3 + v3 u3 + v4
=2 =1 =4 =3 =2 =8
Ennek egy megold´asa: u1 = 2, u2 = 5, u3 = 4, v1 = 0, v2 = −1, v3 = −2, v4 = 4.
´ ´ LINEARIS PROGRAMOZAS
35
Disztrib´ uci´os t´abla:
v2 = −1
v1 = 0 2 u1 = 2
v3 = −2
1 200
v4 = 4
6
5
150 −1
6 3 u2 = 5
4
3 50
2 150
−2 4
−7 2
2
u3 = 4
8 100
150
−1
0
Defin´ıci´ o. Egy legal´abb n´egy cell´ab´ol ´all´o rendezett cellarendszert huroknak nevez¨ unk, ha az al´abbi felt´etelek mindegyike teljes¨ ul. – B´armely k´et egym´ast k¨ovet˝o cella vagy azonos sorhoz, vagy azonos oszlophoz tartozik. – H´arom egym´ast k¨ovet˝o cella nincs ugyanabban a sorban vagy oszlopban. – Az els˝o ´es utols´o cella vagy ugyanabban a sorban, vagy ugyanabban az oszlopban van.
P´ elda hurokra. 1
2 3 4
6
5
V´alasszuk a negat´ıv dij -k k¨oz¨ ul a legkisebbet; legyen ez drs ! K´epezz¨ unk az (r, s)-b˝ol indul´o olyan hurkot, amelyben csak b´azisindexek szerepelnek (r, s)en k´ıv¨ ul. Legyen λ az (r, s)-t˝ol p´aratlan t´avols´agra elhelyezked˝o hurokbeli cell´akhoz tartoz´o ´ert´ekek minimuma. Az u ´j t´abl´aban legyen xrs = λ, a hurokban t˝ole p´aratlan t´avols´agra l´ev˝o ´ert´ekeket λ-val cs¨okkentj¨ uk, a p´arosra l´ev˝oket λ-val n¨ovelj¨ uk, a t¨obbit nem v´altoztatjuk. Amelyik cell´ab´ol a λ-t v´alasztottuk, azt elhagyjuk a b´azisb´ol (ha λ t¨obb helyen is el˝ofordul, akkor is csak az egyiket hagyjuk el). P´ elda (folytat´ as).
36
v2 = −1
v1 = 0 2 u1 = 2
v3 = −2
1 200
v4 = 4
6
5
150 −1
6 3
4
u2 = 5
3 50
2 150
−2 4
-7 2
2
u3 = 4
8 100
150
−1
0
λ = 150
v2 = −1
v1 = 0 2 u1 = 2
v3 = −9
1 200
v4 = −3
6
5
150 13
3
4
u2 = 5
3
6 2
50
150
−2
7
4
2
u3 = 11
2
8 250
−7
0
-8
Megjegyezz¨ uk, hogy a sz¨ uks´eges egyenletrendszer megold´asa k¨ozvetlen¨ ul a t´abl´aban is megt¨ort´enhet. Most λ = 0.
v2 = −1
v1 = 0 2 u1 = 2
1 200
v3 = −1
v4 = −3
6
5
150 5
3
4
u2 = 5
3
6 2
50
150 −1
-2 4
2
u3 = 3
2 0
1
8 250 8
´ PROGRAMOZAS ´ DISZKRET
v2 = −1
v1 = 0 2 u1 = 2
v3 = −1
1 150
37
v4 = −1
6
5
200 5
3 u2 = 3
4
3
4 2
50
150 2
4
2
1 2
8
u3 = 3
0 250 1 6 Mivel most a dij -k egyike sem negat´ıv, optim´alis megold´ast kaptunk, ami a k¨ovetkez˝o: – az els˝o rakt´arb´ol sz´all´ıtsunk 150-et az els˝o, 200-at a m´asodik felvev˝ohelyre; – az els˝o rakt´arb´ol 50-et az els˝ore, 150-et a negyedikre; ul a harmadik rakt´ar k´eszlet´et vigy¨ uk a harmadik felvev˝ohelyre. – v´eg¨ A sz´all´ıt´asi k¨olts´eg ekkor: 2 · 150 + 1 · 200 + 3 · 50 + 2 · 150 + 2 · 250 = 1450. 13. feladat. Oldja meg az al´abbi t´abl´azattal adott sz´all´ıt´asi feladatot! F1 F2 F3 F4 R1 8 2 4 7 30 R2 7 4 3 2 40 R3 2 5 5 9 50 20 16 42 42
3.
Diszkr´ et programoz´ as
Ebbe a t´emak¨orbe olyan matematikai programoz´asi probl´em´ak tartoznak, amelyekn´el a v´altoz´ok egy r´esze (ak´ar az ¨osszes is) csak v´eges sok, vagy megsz´aml´alhat´oan v´egtelen sok ´ert´eket vehet fel. Mind a korl´atoz´o felt´etelekben szerepl˝o f¨ uggv´enyek, mind pedig a c´elf¨ uggv´eny lehetnek nem´ line´arisak is. Altal´ anos alakjuk az fi (x, y) = bi y≥0 x∈S
i ∈ {1, 2, . . . , m}
z(x, y) → max ahol x ´es y p illetve q dimenzi´os vektorok, az S halmaz pedig valamilyen diszkr´et halmaz. A p > 0 ´es q > 0 eset´en kevert (vegyes) diszkr´et programoz´asi, a p > 0 ´es q = 0 eset´en pedig tiszta diszkr´et feladatr´ol besz´el¨ unk. Az irodalomban ezen t´emak¨orre szokt´ak m´eg az ,,eg´esz´ert´ek˝ u programoz´as”
38
elnevez´est is haszn´alni. Ez az elnevez´es az´ert tekinthet˝o jogosnak, mert minden tiszta diszkr´et programoz´asi feladathoz meg lehet konstru´alni olyan vele ekvivalens feladatot, amelyben a v´altoz´ok csak eg´esz ´ert´ekeket vehetnek fel. Ha ugyanis p´eld´aul egy xi v´altoz´o az a1 , a2 , . . . , ak ´ert´ekeket veheti fel, akkor az xi = a1 δ1 + a2 δ2 + · · · + ak δk jel¨ol´est bevezetve, ahol δj csak 0 vagy 1 ´ert´eket vehet fel u ´gy, hogy
k ∑
δj = 1,
j=1
a probl´em´at visszavezett¨ uk egy olyanra, amelyben a diszkr´et v´altoz´ok m´ar csak eg´esz ´ert´ekeket vesznek fel. Az el˝obbiek alapj´an k¨onnyen bel´athatjuk azt is, hogy minden diszkr´et programoz´asi feladathoz meg lehet konstru´alni olyan vele ekvivalens feladatot is, amelyben a diszkr´et v´altoz´ok csak 0-t, vagy 1-et vehetnek fel ´ert´ek¨ ul. Megold´ as grafikus m´ odszerrel : ua. mint folytonos esetben, de most csak a r´acspontokat vessz¨ uk figyelembe. Egy IP feladat laz´ıt´ as´ an vagy relax´ aci´ oj´ an, azt a feladatot ´ertj¨ uk, amely az eredeti IP feladatt´ol annyiban t´er el, hogy nem vessz¨ uk figyelembe az eg´esz´ert´ek˝ us´egre vonakoz´o felt´eteleket. Egy IP feladat relax´aci´oj´at megoldva, ha az optim´alis megold´asvektor minden komponense eg´esz, akkor ez a vektor az IP feladatnak is optim´alis megold´asa. Vigy´azat! A relax´aci´o optim´alis megold´as´ab´ol olyan egyszer˝ u eszk¨oz¨okkel, mint pl. a kerek´ıt´es, ´altal´aban nem hat´arozhat´o meg az eg´esz´ert´ek˝ u feladat optim´alis megold´asa. Eredm´enyesnek bizonyult viszont a k¨ovetkez˝o m´odszer: ha a relax´aci´o x∗ optim´alis megold´asa nem eg´esz, akkor b˝ov´ıts¨ uk ∗ a feladat felt´etelrendszer´et egy tov´abbi olyan felt´etellel, amelyet x nem el´eg´ıt ki, de az IP feladat lehets´eges megold´ashalmaz´anak minden pontja kiel´eg´ıt. ´Igy eg´esz megold´ast nem vesz´ıt¨ unk el, ´es az u ´j folytonos feladatra ´att´erve, egy iter´aci´os elj´ar´ashoz jutunk.
3.1. Korl´atoz´as ´es sz´etv´elaszt´as (Branch and Bound) Defin´ıci´ o. Az x val´os sz´am [x]-szel jel¨olt eg´eszr´esz´en az x-n´el nem nagyobb eg´esz sz´amok maximum´at ´ertj¨ uk, t¨ortr´esz´enek pedig az x − [x] val´os sz´amot nevezz¨ uk, melynek jele {x}. P´ elda. [5, 4] = 5;
[−5, 4] = −6;
{5, 4} = 0, 4;
{−5, 4} = 0, 6
Vil´agos, hogy b´armely x val´os sz´amra teljes¨ ul, hogy 0 ≤ {x} < 1. Legyen adott egy IP feladat, melyet most (IP0 )-lal jel¨ol¨ unk ´es legyen k = 0, N = −∞. 1. l´ep´es: Oldjuk meg az (IP0 ) feladat (R) relax´aci´oj´at! Ha (R)-nek nincs megold´asa, akkor (IP0 )-nak sincs. Egy´ebk´ent: jel¨olje x∗ az (R) egy optim´alis megold´as´at. Ha x∗ minden komponense eg´esz, akkor
´ PROGRAMOZAS ´ DISZKRET
39
x∗ az (IP0 ) optim´alis megold´asa is ´es k´esz vagyunk, egy´ebk´ent: 2. l´ep´es. 2. l´ep´es: V´alasszuk ki az x∗ vektor egy nem eg´esz ´ert´ek˝ u elem´et, mondjuk ∗ xj -ot ´es tekints¨ uk a k¨ovetkez˝o k´et feladatot (´ agaztat´ as): uk a xj ≤ [x∗j ] felt´e– (IPk+1 ): az (IPk ) felt´eteleihez hozz´avessz¨ telt; – (IPk+2 ): az (IPk ) felt´eteleihez hozz´avessz¨ uk a xj ≥ [x∗j ] + 1 felt´etelt. 3. l´ep´es: V´alasszuk ki az (IPk+1 ) vagy az (IPk+2 ) feladatot! 3a. l´ep´es: Ha a feladat nem oldhat´o meg, akkor felder´ıtettnek tekintj¨ uk ∗ ´es a 4. l´ep´esn´el folytatjuk. Ha a kapott x megold´as eg´esz´ert´ek˝ u, akkor a 3b, egy´ebk´ent a 3c l´ep´essel folytatjuk. 3b. l´ep´es: Ha z(x∗ ) > N , akkor legyen N = z(x∗ ) ´es ezt a feladatot megold´ as-jel¨ oltnek tekintj¨ uk. Egy´ebk´ent a feladatot felder´ıtettnek tekintj¨ uk. A folytat´as mindk´et esetben a 4. l´ep´es. 3c. l´ep´es: Ha z(x∗ ) > N , akkor k = k + 1 vagy k = k + 2, att´ol f¨ ugg˝oen, hogy a harmadik l´ep´esn´el melyiket v´alasztottuk; ´es folytassuk a 2. l´ep´esn´el. Egy´ebk´ent a 4. l´ep´es a folytat´as. 4. l´ep´es: Ha van m´eg meg nem oldott r´eszfeladat, akkor oldjuk meg, majd folytassuk a 3a l´ep´essel. Egy´ebk´ent, ha N = −∞, akkor (IP0 ) nem oldhat´o meg. Ha N > −∞, akkor az utols´o megold´as-jel¨olt feladat megold´asa lesz (IP0 ) optim´alis megold´asa. A m´odszer kezel´esi strukt´ ur´aja: bin´ aris fa. P´ elda. Oldjuk meg a k¨ovetkez˝o IP feladatot! x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1 , x2 ≥ 0 ´es eg´esz z(x) = 8x1 + 5x2 → max
3.2. A Lower-Bell algoritmus L´enyege az, hogy az S halmaz elemei k¨oz¨ ul az S sz´amoss´ag´ahoz k´epest l´enyegesen kisebb sz´amoss´ag´ u r´eszhalmaz´at kell el˝o´all´ıtani ´es annak elemeit k¨ozvetlen¨ ul megvizsg´alni. A meg nem vizsg´alt S-beli elemek olyanok lesznek, hogy azokban a c´elf¨ uggv´eny ´ert´eke pl. minimum feladat eset´en nem kisebb, mint a megvizsg´altakhoz tartoz´o c´elf¨ uggv´eny´ert´ekek minimuma. Az fi1 (x) − fi2 (x) ≥ 0 xj ∈ {0, 1}
i = (1, 2, . . . , m) j = (1, 2, . . . , n
f (x) → min feladatok megold´as´ara haszn´alhat´o, ahol az fi1 , fi2 ´es az f f¨ uggv´enyek monoton n¨ovekv˝oek.
40
Tekints¨ uk a 0 − 1 komponens˝ u vektorok halmaz´an a lexikografikus rendez´est. Ez tulajdonk´eppen ugyanaz, mintha ezteket a vektorokat, mint bin´aris sz´amokat hasonl´ıtan´ank ¨ossze. Ezt a rendez´est szok´as numerikus rendez´esnek is nevezni. 1. l´ep´es: Kiindulunk az x = 0 vektorb´ol. Amennyiben ez megold´as, akkor egyben optim´alis megold´as is. Ellenkez˝o esetben legyen x b = f (0) ´es folytassuk az elj´ar´ast a 2. l´ep´essel. 2. l´ep´es: Az x vektort helyettes´ıtj¨ uk a numerikus rendez´esben r´ak¨ovetkez˝ovel. Amennyiben az x vektorhoz l´etezik olyan r, q indexp´ar, hogy 2 ≤ r < q ≤ n, ´es xr−1 = 0, xr = xr+1 = · · · = xq = 1, xq+1 = · · · = xn = 0, akkor legyen x∗i = xi x∗r−1 = 1; x∗j = 0
ha i ≤ r − 2; ha j ≥ r;
tov´abb´a, jel¨olje x∗− az x∗ -ot a numerikus rendez´esben k¨ozvetlen¨ ul megel˝oz˝o vektort. Ha x∗ nem l´etezik, akkor legyen x∗− = (1, 1, . . . , 1). A 3. l´ep´esn´el folytatjuk. 3. l´ep´es: Kisz´am´ıtjuk a vizsg´alt x-hez tartoz´o f (x) f¨ uggv´eny´ert´eket. Amenynyiben f (x) ≥ f (b x), a 6., k¨ ul¨onben pedig a 4. l´ep´esn´el folytatjuk az elj´ar´ast. 4. l´ep´es: Megvizsg´aljuk, hogy az x vektor megold´asa-e a feladatnak. Ha igen, akkor az x vektor lesz az x b, a hozz´atartoz´o f (x) lesz az fb = f (b x) ´es a 6. l´ep´esn´el, k¨ ul¨onben pedig az 5.-n´el folytatjuk az algoritmust. 5. l´ep´es: Megvizsg´aljuk, hogy l´etezik olyan i ∈ {1, 2, . . . , m} amelyre teljes¨ ul, ∗− hogy fi1 (x ) − fi2 (x) < 0. Ha igen, akkor a 6., k¨ ul¨onben pedig a 2. l´ep´esn´el folytatjuk. 6. l´ep´es: Amennyiben x∗ l´etezik, akkor x∗ veszi ´at x szerep´et ´es a 3. l´ep´esn´el folytassuk az elj´ar´ast. Ha nem l´etezik x∗ , akkor v´ege van az elj´ar´asnak. Ha az algoritmus l´ep´esei sor´an tal´altunk megold´ast, akkor az x b hely´en l´ev˝o lesz az optim´alis ´es fb = f (b x) lesz az optim´alis ´ert´ek. Amennyiben nem tal´altunk megold´ast, akkor meg´allap´ıtjuk, hogy a feladat felt´etelrendszere ellentmond´asos. A l´enyeg, hogy bizonyos felt´etelek teljes¨ ul´ese eset´en az x vektorr´ol k¨ozvet∗ len¨ ul ´att´erhet¨ unk az x vektorra, a k¨ozb¨ uls˝o vektorok vizsg´alata n´elk¨ ul.
3.3. Hozz´arendel´esi feladat Adott bizonyos sz´am´ u dolgoz´o ´es ugyanennyi munka. Az egyes dolgoz´ok a munk´akat k¨ ul¨onb¨oz˝o k¨olts´egekkel tudj´ak v´egrehajtani. Osszuk sz´et a dolgoz´ok k¨oz¨ott az ¨osszes munk´at u ´gy, hogy minden dolgoz´o pontosan egy munk´at kapjon, ´es a munkav´egz´es ¨osszk¨olts´ege minim´alis legyen.
´ PROGRAMOZAS ´ DISZKRET
41
Vezess¨ uk be a k¨ovetkez˝ o jel¨ol´eseket. Jel¨olje n a dolgoz´ok sz´am´at, cij a j-edik munka elv´egz´es´enek k¨olts´eg´et, ha azt az i-edik dolgoz´o hajtja v´egre (i = 1, 2, . . . , n; j = 1, 2, . . . , n). Tetsz˝oleges 1 ≤ i, j ≤ n indexp´arra legyen { 1 ha az i-edik dolgoz´o hajtja v´egre a j-edik munk´at; xij = 0 k¨ ul¨onben. Ekkor az optimumsz´am´ıt´asi modell n ∑ xit = 1 ,
i = 1, · · · , n
t=1 n ∑
xtj = 1 ,
j = 1, · · · , n
t=1
xij ∈ {0, 1} , i = 1, · · · , n ; j = 1, · · · , n n ∑ n ∑
cij xij = z(x) −→ min
i=1 j=1
Telepesek egy 10 leg´enyemberb˝ol ´all´o kol´oni´aja kieg´esz¨ ul 10 potenci´alis menyasszonnyal. R¨ovid udvarl´as ut´an a fiatalemberek elhat´arozz´ak, hogy halad´ektalanul megh´azasodnak. Minden egyes menyasszonyjel¨olt kap egy n´evsort, amelyen a 10 fiatalember neve szerepel, ´es ezen kell pontoznia a f´erjjel¨olteket, a sz´am´ara legink´abb megfelel˝ot 10 ponttal, a k¨ovetkez˝o v´alasztottj´at 9 ponttal, ´es ´ıgy tov´abb. Tegy¨ uk fel, hogy b´armely r¨ogz´ıtett p´arv´alaszt´asn´al az eg´esz telep boldogs´aga a menyasszonyjel¨oltek ´altal adott pontsz´amok ¨osszeg´evel ar´anyos. Hat´arozzunk meg egy olyan p´arv´alaszt´ast, amely az eg´esz telep sz´am´ ara maxim´alis boldogs´agot eredm´enyez. Nyilv´anval´o, hogy a fenti probl´ema egy hozz´arendel´esi feladattal ´ırhat´o le, amelyben az i-edik menyasszonyjel¨oltnek a j-edik fiatalemberre adott pontsz´ama −cij . Vegy¨ uk ´eszre, hogy a tekintett feladat lehets´seges megold´asai olyan 0 ´es 1 elemekb˝ol ´all´o m´atrixok, amelyeknek minden sora ´es minden oszlopa pontosan egy darab 1-est tartalmaz. Az ilyen m´atrixok sz´ama n!. Kism´eret˝ u probl´ema eset´en m˝ uk¨odik az a m´odszer, hogy valamilyen algoritmussal el˝o´all´ıtjuk ezen m´atrixok mindegyik´et, majd mindegyikhez kisz´am´ıtjuk a c´elf¨ uggv´eny ´ert´eket ´es vessz¨ uk ezek minimum´at.
3.4. Magyar m´odszer H. W. Kuhn dolgozta ki Egerv´ary Jen˝o egy t´etele alapj´an. Adott m´atrix 0 elemeinek egy rendszer´et f¨ uggetlen 0-rendszernek nevezz¨ uk, ha a m´atrix minden sora ´es minden oszlopa legfeljebb egy elem´et tartalmazza a rendszernek. Valamely f¨ uggetlen 0-rendszer elemeit a tov´abbiakban 0∗ -gal fogjuk jel¨olni.
42
P´ elda. ∗ 0 1 4 2 3 4 0 0
2 0 0 1
3 0 4 0 0 3 2 0
∗ ∗ 1 2 3 0 1 2 3 0 1 2 3 ∗ ∗ 2 0∗ 0 0 4 2 0∗ 0 4 2 0 ∗ ∗ 4 0 0 3 4 0 0 3 4 0 0 ∗ ∗ 0 1 2 0 0 1 2 0 0 1 2
Egy m´atrix valamely sor´at (oszlop´at) k¨ot¨ott sornak (oszlopnak) nevezz¨ uk, ha mellette (felette) egy ,,+” jel ´all. A m´atrix valamely elem´et szabad elemnek nevezz¨ uk, ha nincs semmif´ele jellel ell´atva, ´es sem a sora, sem az oszlopa nincsen lek¨otve. Speci´alisan, ha az illet˝o elem 0, akkor szabad 0-r´ol besz´el¨ unk. El˝ ok´esz´ıt˝ o r´esz: A C k¨olts´egm´atrix minden sor´ab´ol vonjuk ki az illet˝o sor minimum´at! Az ´ıgy kapott m´atrix minden oszlop´ab´ol vonjuk ki a sz´oban forg´o oszlop minimum´at! A kapott m´atrix az al´abbi iter´aci´o nulladik eleme, jele: C(0) . Jel¨olj¨ unk ki C(0) -ban oszlopfolytonosan egy f¨ uggetlen null´akb´ol ´all´o rendszert, majd kezdj¨ uk el az iter´aci´ot! (r) uggetlen 0-rendszer elemeinek a sz´ama n, 1. l´ep´es: Ha a C -ben kijel¨olt f¨ akkor k´eszen vagyunk. Ellenkez˝o esetben k¨oss¨ uk le a f¨ uggetlen null´akat tartalmaz´o oszlopokat ´es folytassuk az elj´ar´ast a m´asodik l´ep´essel. 2. l´ep´es: Keress¨ unk sorfolytonosan szabad null´at, ha nincs, akkor az ¨ot¨odik l´ep´es k¨ovetkezik. Ha tal´alunk szabad null´at, akkor vizsg´aljuk meg a sor´at. Ha ez a sor nem tartalmaz csillagozott null´at, akkor a negyedik l´ep´es k¨ovetkezik, ellenkez˝o esetben a harmadik. 3. l´ep´es: A tekintett szabad null´at l´assuk el vessz˝ovel, k¨oss¨ uk le a sor´at, ´es sz¨ untess¨ uk meg a sor´aban l´ev˝o csillagozott nulla oszlop´anak lek¨ot´es´et, majd folytassuk a m´asodik l´ep´essel! 4. l´ep´es: A tekintett szabad null´at l´assuk el vessz˝ovel, ´es ebb˝ol kiindulva k´epezz¨ unk l´ancot a k¨ovetkez˝o m´odon.: minden l´ancbeli vessz˝os nulla ut´an az oszlop´aban l´ev˝o csillagos null´aval folytat´odik a l´anc, ´es minden l´ancbeli csillagos nulla ut´an a sor´aban l´ev˝o vessz˝os null´aval folytat´odik a l´anc, felt´eve, hogy vannak ilyen elemek. Ellenkez˝o esetben a l´anc v´eget ´er. Ezek ut´an legyen C(r+1) a jel¨ol´esek n´elk¨ uli (r) C m´atrix, ´es l´assuk el csillaggal az olyan null´akat, amelyek csillagozva voltak ´es nem szerepelnek a l´ancban, vagy vessz˝osek ´es szerepelnek a l´ancban. Folytassuk az els˝o l´ep´essel. 5. l´ep´es: K´epezz¨ uk a szabad elemek minimum´at, majd azt a minimumot vonjuk ki az ¨osszes szabad elemb˝ol ´es adjuk hozz´a a k´etszer k¨ot¨ott elemekhez. Folytassuk a m´asodik l´ep´essel! A feladat optim´alis megold´asa az a m´atrix, melyben a legv´eg¨ ul kapott m´atrix f¨ uggetlen 0 rendszere hely´en 1 szerepel, a t¨obbi helyen 0. 3.4.1. Tiltott hozz´ arendel´esek kezel´ese. El˝ofordulnak olyan gyakorlati probl´em´ak, amelyek hozz´arendel´esi feladathoz vezetnek, de bizonyos hozz´arendel´esek nincsenek megengedve. Ilyenkor tiltott hozz´arendel´esekr˝ol besz´el¨ unk. Nyilv´anval´o, hogy ezeknek a feladatoknak nem okvetlen l´etezik
´ PROGRAMOZAS ´ DISZKRET
43
lehets´eges megold´asa. A k¨ovetkez˝o algoritmus l´attatja, hogy a tilt´asos feladatok mindig visszavezethet˝ok egy alkalmas hozz´arendel´esi feladat megold´as´ara. Tilt´asok megad´asa: xit jt = 0 (t = 1, 2, . . . r). 1. l´ep´es: Ha a C m´atrix nem tartalmaz negat´ıv elemeket, akkor a m´asodik l´ep´es k¨ovetkezik. Ellenkez˝o esetben vonjuk ki a legkisebb elemet a m´atrix minden elem´eb˝ol. Folytassuk a m´asodik l´ep´essel. 2. l´ep´es: Adjuk ¨ossze a m´atrix elemeit, az ´ıgy kapott sz´amhoz adjunk m´eg 1-t. Az ´ıgy kapott sz´amot M -mel jel¨olj¨ uk. ´Irjunk M -t az ¨osszes tiltott hozz´arendel´esi helyre, a t¨obbit v´altozatlanul hagyjuk. Az ´ıgy kapott u ´j feladatot oldjuk meg magyar m´odszerrel. Ha a kapott optimum kisebb, mint M akkor ez az optim´alis megold´as az eredeti feladatnak is optim´alis megold´asa. Ellenkez˝o esetben az eredeti feladatnak nem l´etezik optim´alis megold´asa. 14. feladat. Oldja meg azt a hozz´arendel´esi feladatot melynek k¨olts´egm´atrixa a) 4 5 3 2 3 3 2 4 3 4 A= 3 3 4 4 3 ; 2 4 3 2 4 2 1 3 4 3 b) 5 6 5 8 9 4 5 4 3 7 B= 3 5 5 3 6 . 2 7 3 4 5 3 6 4 5 6 15. feladat. Oldja meg az
0 1 0 −1 2 1 −1 0 1 2 2 0 2 A= −1 2 1 1 −1 2 1 0 1 −1 2 1
k¨olts´egm´atrix´ u tilt´asos hozz´arendel´esi feladatot, ahol a tilt´asok a k¨ovetkez˝ok: x11 = x12 = x13 = 0 x22 = x23 = x24 = 0 x33 = x34 = x35 = 0 x44 = x45 = 0.
44
4.
Instrukci´ ok a sz´ amonk´ er´ esekhez Kifejtend˝o t´emak¨or¨ok
(1) Optimumsz´am´ıt´asi feladatok. Matematikai programoz´as ´es feladata. Line´aris programoz´as ´es alap feladata. Standard alak. F˝o defin´ıci´ok (c´el-f¨ uggv´eny, felt´etelek, lehets´eges, optim´alis megold´as). (2) Grafikus ´es Fourier-m´odszer alkalmaz´asa LP feladatok megold´as´ara. uggetlens´eg, (3) LP feladat m´atrix form´aja: oszlop-vektorok, line´aris f¨ b´azis fogalma, b´azismegold´as, lehets´eges b´azismegold´as (4) Szimplex m´odszer, szimplex-iter´aci´o, gener´al´o sor/oszlop/elem, transzform´aci´os k´epletek. Szimplex-t´abla. (5) Szimplex m´odszer ind´ıt´asa. Indul´o lehets´eges b´azismegold´as (LBM) el˝o´all´ıt´asa. ¨ (6) Megoldhatatlan LP feladat kezel´ese szimplex-m´odszerben. Ures lehets´eges halmaz´ u LP feladat jele M-m´odszer illetve, 2-f´azis´ u szimplex m´odszer eset´en. Alternat´ıv optim´alis megold´as felismer´ese szimplex t´abl´aban. (7) Dualit´as line´aris programoz´asban: Prim´al ´es du´alis feladat, kapcsolatuk. (8) LP feladatok ´erz´ekenys´egvizsg´alata. (9) Sz´all´ıt´asi feladat manu´alis megold´asa - indul´o lehets´eges megold´as megkeres´ese. ´ (10) Diszkr´et, eg´esz´ert´ek˝ u ´es 0/1 LP feladatok. Atalak´ ıt´asok. Tiszta ´es vegyes eg´esz´ert´ek˝ u LP feladat. Relax´aci´os feladat. Korl´atoz´as ´es sz´etv´alaszt´as (B&B - branch and bound) m´odszere. (11) A Lower-Bell algoritmus. (12) Hozz´arendel´esi feladat, tiltott hozz´arendel´esek kezel´ese.
´ A SZAMONK ´ ´ ESEKHEZ ´ INSTRUKCIOK ER
45
´cio ´ kutata ´s c. tant´ MINTA z´ arthelyi dolgozat Opera argyb´ ol PTI hallgat´ ok r´esz´ere 1. H´ aromf´ele n¨ ov´eny termeszt´esi ter¨ ulet´et szeretn´enk megtervezni, legfeljebb 400 ter¨ uletegys´egnyi f¨ oldet felhaszn´ alva. A m´ asodik n¨ ov´enyfajt´ at a felhaszn´ alt ter¨ ulet legfeljebb 40%-´ an k´ıv´ anjuk termeszteni. Az els˝ o n¨ ov´eny termeszt´esi ter¨ ulete legal´ abb 60 ter¨ uletegys´eggel nagyobb legyen a harmadik n¨ ov´eny termeszt´esi ter¨ ulet´en´el. A n¨ ov´enyfajt´ ak hozama ter¨ uletegys´egenk´ent rendre 3, 6, 4 p´enzegys´eg. Milyen nagys´ ag´ u ter¨ uleteken termessz¨ uk az egyes n¨ ov´enyeket, hogy az ¨ osszhozam maxim´ alis legyen? ´Irja fel a feladat matematikai modellj´et! (5 pont) arozzuk meg azt a standard feladatot, amelyre az az al´ abbi LP feladat 2. Hat´ visszavezethet˝ o! (5 pont) 3x1 + x2 − 4x3 ≥ −2 2x1 − x2 + x3 ≤ 8 x1 + x2 + x3 = 4 x1 , x2 ≥ 0 3x1 + x2 − 2x3 = z(x) → min 3. Oldja meg grafikusan is ´es Fourier m´ odszer´evel is a k¨ ovetkez˝ o feladatot! (10 pont) −x + y ≤ 1 −x + 2y ≥ −2 3x + y ≤ 3 x, y ≥ 0 2x + y → max 4. Oldja meg szimplex m´ odszerrel a k¨ ovetkez˝ o feladatot! (10 pont) 2x1 + x2 + x3 = 16 x1 + 3x2 − x4 = 20 x1 + x2 = 10 x1 , x2 , x3 , x4 ≥ 0 −2x1 − 3x2 = z(x) → max 5. Oldja meg a k¨ ovetkez˝ o sz´ all´ıt´ asi feladatot! (10 pont) F1 F2 F3 F4 R1 1 2 6 5 350 R2 3 4 3 2 200 R3 4 2 2 5 250 200 200 250 150 6. Oldja meg azt a hozz´ arendel´esi feladatot melynek k¨ olts´egm´ atrixa 4 5 3 2 3 3 2 4 3 4 A= 3 3 4 4 3! 2 4 2 2 4 2 1 3 4 3 (10 pont)
