Betekintés: Imreh Balázs - Operációkutatás

Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!




o o El˝sz´

Jelen jegyzet a J´zsef Attila Tudom´nyegyetem programoz´ matematikus ´s o a o e k¨zgazdas´gi programoz´ hallgat´i sz´m´ra k´sz¨lt, akik m´sodik f´l´vt˝l hallgatnak o a o o a a e u a ee o oper´ci´kutat´st. a o a A feldolgozott anyag bevezet˝ jelleg˝. o u N´h´ny karakterisztikus, ma m´r e a a klasszikusnak sz´m´ o r´szter¨letet ¨lel fel, ´rintve ezek alapk´rd´seit ´s n´h´ny isa ıt´ e u o e e e e e a mertebb, egyszer˝bb megold´si technik´t. Nem ´rinti a jegyzet az ut´bbi id˝ben igen u a a e o o el˝t´rbe ker¨lt kombinatorikus optimaliz´l´s t´mak¨r´t, amely k¨l¨n tant´rgyk´nt szeoe u aa e oe uo a e repel az oktat´sban. A t´rgyal´s sor´n mind line´ris algebr´b´l, mind anal´ a a a a a a o ızisb˝l csak o a legsz¨ks´gesebb fogalmak, alap¨szef¨gg´sek ismeret´t t´telezz¨k fel. A fel´p´ u e o u e e e u e ıtett elj´r´sok rendre egyszer˝ numerikus p´ld´kon kereszt¨l ker¨lnek bemutat´sra. Az aa u e a u u a egyes fejezeteket feladatok k¨vetik, amelyek r´szben az algoritmusoknak a hallgat´k o e o altal t¨rt´n˝ ¨n´ll´ v´grehajt´s´t szolg´lj´k, r´szben egyszer˝ bizony´ asok kit˝z´s´vel ´ o e oo a o e aa a a e u ıt´ u ee a fogalmak maradand´bb megismer´s´t c´lozz´k. o ee e a A jegyzet meg´ asa sor´n nagy seg´ eget jelentett Csirik J´nos, Gr˝ger Hans ır´ a ıts´ a o Dietmar ´s M´t´ E¨rs munkat´rsaim sz´mos hasznos tan´csa, konstrukt´ ´szrev´e ae o a a a ıv e e teleik. V´g¨l itt szeretn´k k¨sz¨netet mondani lektoraimnak, Megyesi L´szl´nak, a e u e o o a o JATE docens´nek, ´s Sz´ntai Tam´snak, az ELTE docens´nek a k´zirat igen alapos e e a a e e ´s gondos lektor´l´s´´rt. e a a ae

Szeged, 1993. febru´r 2. a Imreh Bal´zs a

1



2



´ 1. BEVEZETES

a ıt´ 1.1 Az optimumsz´m´ asi modellek

Az oper´ci´kutat´s viszonylag uj tudom´ny´g, amelynek fejl˝d´se ´s sz´lesa o a ´ a a o e e e k¨r˝ alkalmaz´sa szorosan ¨sszef¨gg a sz´m´ og´pek kialakul´s´val, fejl˝d´s´vel. ou a o u a ıt´ e aa o ee Maga az ”oper´ci´kutat´s” kateg´ria a m´sodik vil´gh´bor´ idej´n alakult ki. A a o a o a a a u e sz¨vets´ges hadseregek vez´rkarai mellett l´trehoztak olyan k¨l¨nb¨z˝ szakm´j´ o e e e uo o o au tud´sokb´l ´ll´ kutat´csoportokat, amelyeknek az volt a f˝ feladata, hogy tudom´nyos o o a o o o a eszk¨z¨k seg´ eg´vel javaslatokat dolgozzanak ki a hadm˝veletek legeredm´nyesebb o o ıts´ e u e ir´ny´ as´hoz. Innen ered az elnevez´s, amelyben az oper´ci´ sz´ katonai m˝veletre, a ıt´ a e a o o u hadm˝veletre utalt. A vil´gh´bor´ ut´n, a sz´m´ og´pek fejl˝d´s´vel p´rhuzamosan az u a a u a a ıt´ e o ee a oper´ci´kutat´s mind tartalm´ban, mind alkalmaz´si k¨r´t illet˝en gyorsan fejl˝d¨tt, a o a a a oe o o o ´s napjainkban a t´rsadalmi-gazdas´gi ´let majd minden ter¨let´n alkalmaz´st nyer. e a a e u e a Az oper´ci´kutat´s feladat´nak szeml´ltet´s´hez tekints¨k a k¨vetkez˝ gyakorlati a o a a e ee u o o probl´m´t. Adott egy m˝hely, amely asztalokat, sz´keket ´s szekr´nyeket gy´rt. A e a u e e e a gy´rt´s sor´n k´tf´le anyagot haszn´lnak fel, egyfajta lemezt ´s egyfajta deszk´t. Ezek a a a e e a e a egym´ssal nem helyettes´ a ıthet˝k ´s korl´tozott mennyis´gben ´llnak rendelkez´sre. A o e a e a e feladat: olyan term´k¨sszet´tel meghat´roz´sa, amely mellett a m˝hely nyeres´ge e o e a a u e maxim´lis. A fenti probl´m´hoz egy matematikai modellt konstru´lhatunk. E c´lb´l a e a a e o jel¨lje rendre o x1 , x2 , x3 a gy´rt´sra ker¨l˝ asztalok, sz´kek, szekr´nyek sz´m´t, a a uo e e a a e e e ıt´ e u e a a l1 , l2 , l3 egy asztal, egy sz´k, egy szekr´ny k´sz´ es´hez sz¨ks´ges lemezek sz´m´t, d1 , d2 , d3 egy asztal, egy sz´k, egy szekr´ny k´sz´ es´hez sz¨ks´ges deszk´k e e e ıt´ e u e a sz´m´t, a a e e a aa o a o e c1 , c2 , c3 egy asztal, egy sz´k, egy szekr´ny gy´rt´s´b´l sz´rmaz´ nyeres´get, l, d a rendelkez´sre ´ll´ lemezek ´s deszk´k sz´m´t. e a o e a a a A bevezetett jel¨l´sekkel a tekintett probl´ma az al´bbi, ugynevezett optimumsz´m´ aoe e a ´ a ıt´ si modellel ´ ırhat´ le, amely matematikai szempontb´l egy felt´teles sz´ls˝´rt´k feladat. o o e e oe e l1 x1 + l2 x2 + l3 x3 ≤ l d1 x1 + d2 x2 + d3 x3 ≤ d xi eg´sz & xi ≥ 0 (i = 1, 2, 3) e —————————————– c1 x1 + c2 x2 + c3 x3 = z → max A fentiekkel kapcsolatban vegy¨k ´szre, hogy a kapott modell le´ u e ırhatn´ m´s a a olyan m˝helyek probl´m´j´t is, amelyek h´romf´le term´ket gy´rtanak k´tf´le u e aa a e e a e e ´ l´nyeg´ben a modellhez egy probl´macsoport rendelanyag felhaszn´l´s´val. Igy e aa a e e het˝. A probl´m´t, probl´macsoportot le´ o modell ismerete ¨nmag´ban pe
Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!


rsze o e a e ır´ o a m´g nem jelenti a probl´ma megold´s´t. Ehhez sz¨ks´ges lenne olyan elj´r´s e e aa u e aa ismerete, amely a modell ´ltal meghat´rozott matematikai feladat megold´s´ra a a aa 3



o e e a a a o u o szolg´l. K¨vetkez´sk´ppen az al´bbi h´rom, egym´ssal szorosan ¨sszef¨gg˝ fogalmat a k¨l¨nb¨ztethetj¨k meg: uo o u (1) gyakorlati probl´m´k, tev´kenys´gek formaliz´lhat´s´g szempontj´b´l k¨z¨s e a e e a oa a o o o tulajdons´g´ csoportja, a u (2) a fenti probl´macsoportot le´ o optimumsz´m´ asi modell, e ır´ a ıt´ (3) a sz´ban forg´ optimumsz´m´ asi modell ´ltal meghat´rozott matematikai o o a ıt´ a a feladat megold´s´ra szolg´l´ elj´r´s. aa ao a a A gyakorlati probl´m´k csoportos´ e a ıthat´s´g´t, az ezzel kapcsolatos meggonoa a dol´sokat f˝k´ppen a rendszerszervez´snek ´s a konkr´t alkalmaz´si ter¨let, ter¨letek a o e e e e a u u szakembereinek kell vizsg´lniuk. Mi els˝sorban a (2) ´s (3) pontokhoz tartoz´ a o e o probl´m´kkal fogunk foglalkozni. e a K´zenfekv˝ az a k´rd´s, hogy adott probl´macsoporthoz hogyan hat´rozhat´ meg e o e e e a o az illet˝ probl´macsoportot le´ o optimumsz´m´ asi modell. A modellalkot´s ´ltal´ban o e ır´ a ıt´ a a a igen bonyolult tev´kenys´g, amely sor´n a jelens´gek t¨meg´b˝l ki kell emelni a e e a e o e o l´nyeges, meghat´roz´ ´s tart´s jegyeket, ¨sszef¨gg´seket ´s a t¨bbi ¨sszef¨gg´st˝l, e a o e o o u e e o o u e o ism´rvt˝l el kell tekinteni a modell kezelhet˝s´g´nek ´rdek´ben. A modellekkel szeme o oe e e e ben k´tir´ny´ k¨vetelm´nnyel l´p¨nk fel: e a u o e e u t¨kr¨zz´k min´l h˝ebben a val´s´got, u o e e u oa legyenek matematikailag, sz´m´ astechnikailag kezelhet˝k. a ıt´ o Sok esetben ez k´t ellent´tes szempont utk¨ztet´s´t jelenti, ´s a modell kialak´ as´n´l e e ¨ o ee e ıt´ a a olyan kompromisszumra kell t¨rekedni, amelyn´l az matematikailag, sz´m´ astechnio e a ıt´ kailag m´g kezelhet˝ ´s emellett a vizsg´lat szempontj´b´l h˝en t¨kr¨zi a val´s´got e oe a a o u u o oa is. Tekintettel a modellalkot´s bonyolults´g´ra, nem adhat´ meg olyan elj´r´s, a a a o aa amely alapj´n b´rmely probl´macsoporthoz a megfelel˝ modell elk´sz´ a a e o e ıthet˝ lenne. o Megadhat´k viszont olyan ´ltal´nos elvek, amelyek seg´ eget ny´jthatnak a modello a a ıts´ u alkot´sban. A tov´bbiakban ´ttekintj¨k ezeket az elveket, mik¨zben v´grehajt´sukat a a a u o e a az el˝z˝ek sor´n megadott probl´m´n szeml´ltetj¨k. o o a e a e u

1.2 A modellalkot´s elemei a

1. A vizsg´lat t´rgy´t k´pez˝ tev´kenys´get bontsuk fel v´ges sok, ugynevezett a a a e o e e e ´ elemi tev´kenys´gre. Elemi tev´kenys´gen a teljes tev´kenys´g azt a pontosan e e e e e e k¨r¨lhat´rolt r´sz´t ´rtj¨k, amelyet tov´bb bontani m´r nem sz´nd´kozunk. Jel¨lje a ou a e e e u a a a e o felbont´s sor´n el˝´ll´ elemi tev´kenys´geket E1 , . . . , En . a a oa o e e A szeml´ltet´s¨l v´lasztott probl´m´n´l a m˝hely termel´s´t h´rom elemi e eu a e a a u ee a tev´kenys´gre bontottuk fel: asztalgy´rt´sra, sz´kgy´rt´sra ´s szekr´nygy´rt´sra. e e a a e a a e e a a Nyilv´nval´, hogy v´laszthatn´nk finomabb felbont´st is, de a probl´ma megfogala o a a a e maz´sa nem teszi ezt sz¨ks´gess´. Ilyen finomabb felbont´s lehetne p´ld´ul az, amikor a u e e a e a a h´rom term´kfajta gy´rt´s´hoz sz¨ks´ges r´szeket (fed˝lap, l´bak, stb.) k¨l¨na e a aa u e e o a uo k¨l¨n is figyelembe venn´nk, ´s ennek megfelel˝en az anyagok kiv´laszt´s´t is tov´bb uo e e o a aa a bontan´nk. L´thatjuk, hogy a teljes tev´kenys´g felbont´sa elemi tev´kenys´gekre a a e e a e e 4



o e aa a a o a bizonyos tekintetben ¨nk´nyes elj´r´s, ami ´ltal´ban igen alapos k¨zgazdas´gi, rendszerelm´leti, modellalkot´si megfontol´sokat ig´nyel. e a a e 2. Minden egyes Ei elemi tev´kenys´ghez rendelj¨nk hozz´ egy xi val´s v´ltoz´t, e e u a o a o amely arra n´zve ad felvil´gos´ ast, hogy Ei milyen m´rt´kben vesz r´szt a teljes e a ıt´ e e e tev´kenys´gben. Az xi v´ltoz´t az Ei elemi tev´kenys´g szintj´nek, intenz´ as´nak e e a o e e e ıt´ a nevezz¨k. u P´ld´nkban az asztalgy´rt´s elemi tev´kenys´g intenz´ as´nak vegy¨k a gy´re a a a e e ıt´ a u a tand´ asztalok sz´m´t, ´s ehhez hasonl´an, a m´sik k´t term´kf´les´gn´l is legyen a o a a e o a e e e e e legy´rtand´ term´kek sz´ma az illet˝ elemi tev´kenys´g intenz´ asa. Ekkor a h´rom a o e a o e e ıt´ a elemi tev´kenys´g aktu´lis intenz´ asait az (x1 , x2 , x3 ) vektorral ´ e e a ıt´ ırhatjuk le. Nyilv´na val´, hogy a lemez ´s deszka korl´tozott volta miatt az intenz´ as´rt´kek korl´tosak ´s o e a ıt´ e e a e nem f¨ggetlenek egym´st´l. u a o 3. Hat´rozzuk meg azokat a kapcsola
Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!


tokat, ¨sszef¨gg´seket, amelyeket az intena o u e z´ as´rt´keknek k¨l¨n-k¨l¨n ´s egy¨ttesen ki kell el´g´ ıt´ e e uo uo e u e ıteni. Ezeket fogjuk felt´teleknek e nevezni. Itt teh´t egyr´szt az xi v´ltoz´kra (i = 1, . . . , n), m´sr´szt az (x1 , . . . , xn ) a e a o a e vektorv´ltoz´ra vonatkoz´ felt´teleket kell meghat´rozni. Egy (¯1 , . . . , xn ) val´s veka o o e a x ¯ o tort a feladat lehets´ges megold´s´nak nevez¨nk, ha x az intenz´ as´rt´kekre vonatkoz´ e a a u ıt´ e e o o ¨sszes, az el˝z˝ekben meghat´rozott felt´telt kiel´g´ A lehets´ges megold´sok halo o a e e ıti. e a o maz´t a tov´bbiakban L-lel fogjuk jel¨lni. a a P´ld´nkban az intenz´ as´rt´kekre vonatkoz´, a probl´ma szempontj´b´l l´nyeges e a ıt´ e e o e a o e o ¨sszef¨gg´sek a k¨vetkez˝k: mivel xi a gy´rtand´ term´kek sz´ma, ez´rt xi ≥ 0 ´s u e o o a o e a e e e a a e a o e a a xi eg´sz (i = 1, 2, 3), tov´bb´, mivel a rendelkez´sre ´ll´ lemezek ´s deszk´k sz´ma l ´s d, ez´rt az l1 x1 + l2 x2 + l3 x3 ≤ l ´s d1 x1 + d2 x2 + d3 x3 ≤ d felt´teleknek is e e e e teljes¨lnie kell. Ekkor a lehets´ges megold´sok halmaza a 3-dimenzi´s euklideszi t´r u e a o e azon r´szhalmaza, amelyet a felsorolt felt´telek hat´roznak meg. Ezen r´szhalmaz e e a e minden pontja egy terv abban az ´rtelemben, hogy v´gre lehet hajtani. e e 4. A tev´kenys´g vizsg´lat´nak ´ltal´ban valamilyen c´lja van. Fogalmazzuk e e a a a a e meg ezt a c´lt a v´lasztott elemi tev´kenys´gek seg´ eg´vel, azaz adjunk meg egy e a e e ıts´ e olyan z : L → V val´s f¨ggv´nyt, amely a lehets´ges megold´sok ”´rt´k´t”, ”j´s´g´t” o u e e a e e e oa a e u e u jellemzi a kit˝z¨tt c´l szempontj´b´l. Ezt a f¨ggv´nyt c´lf¨ggv´nynek nevezz¨k. u o e a o u e A vizsg´lt probl´m´ban c´lunk a nyeres´g maximaliz´l´sa. A nyeres´g mennyis´ge a e a e e aa e e c1 x1 +c2 x2 +c3 x3 , ´ a vizsg´lat szempontj´b´l alkalmas c´lf¨ggv´ny a z(x1 , x2 , x3 ) = ıgy a a o e u e c1 x1 + c2 x2 + c3 x3 f¨ggv´ny. u e A modellalkot´s nagy k¨r¨ltekint´st ig´nyl˝ feladat´val a tov´bbiakban nem a ou e e o a a foglalkozunk, hanem a modellek ´ltal meghat´rozott matematikai feladatok megola a d´s´ra szolg´l´ elj´r´sokat fogjuk vizsg´lni. aa ao a a a

1.3 Az optimumsz´m´ asi modellekkel megadott matematikai a ıt´ feladatok megold´s´ra szolg´l´ elj´r´sok a a ao a a

Az el˝z˝ekb˝l ad´dik, hogy az optimumsz´m´ asi modell matematikai szemo o o o a ıt´ pontb´l egy felt´teles sz´ls˝´rt´k feladatnak tekinthet˝, nevezetesen a felt´telek ´ltal o e e oe e o e a 5



u e u e e oe e e e meghat´rozott L halmazon keress¨k a c´lf¨ggv´ny sz´ls˝´rt´k´t. Maximum keres´s a eset´n maximum feladatr´l, minimum keres´sn´l minimum feladatr´l besz´l¨nk. Maxie o e e o eu mum feladatn´l egy maximumhelyet optim´lis megold´snak, a maximum ´rt´k´t pedig a a a e e e optimumnak nevezz¨k. (Ugyanezen elnevez´seket haszn´ljuk minimum feladat eset´n u e a e is.) Teh´t x ∈ L optim´lis megold´sa egy maximum feladatnak, ha z(x) ≥ z(x) teljes¨l a a u a b´rmely x ∈ L lehets´ges megold´sra, ´s ebben az esetben az optimum z(x). Nyila e a e v´nval´, hogy egy felt´teles sz´ls˝´rt´k feladatnak nem sz¨ks´gk´pp l´tezik optim´lis a o e e oe e u e e e a megold´sa, tov´bb´ ha l´tezik optim´lis megold´s, akkor az optimumot egyidej˝leg a a a e a a u t¨bb helyen is felveheti a c´lf¨ggv´ny. o e u e Az ´ltalunk vizsg´land´ elj´r´sok ´ltal´ban egy optim´lis megold´s meghat´roa a o aa a a a a a z´s´t biztos´ ak, felt´ve, hogy a feladatnak l´tezik optim´lis megold´sa. Ellenkez˝ aa ıtj´ e e a a o esetben az elj´r´s alapj´n v´ges l´p´sben kider¨l, hogy a feladatnak nincs optim´lis aa a e e e u a megold´sa. Az egyetlen optim´lis megold´s meghat´roz´s´ra vonatkoz´ t¨rekv´st a a a a aa o o e ´ gyakorlati meggondol´sok motiv´lt´k. Altal´ban gyakorlati szempontb´l egy opa a a a o tim´lis megold´s ismerete is kiel´g´ o. Gondoljunk p´ld´ul a tekintett m˝hely tera a e ıt˝ e a u mel´s´re. A maxim´lis nyeres´get biztos´ o valamely terv ismeret´ben nem okvetlen¨l ee a e ıt´ e u sz¨ks´ges ugyanekkora nyeres´get biztos´ o m´s tervet is meghat´rozni. u e e ıt´ a a Az eddig elmondottak lehet˝v´ teszik sz´munkra, hogy a tov´bbiakban v´zoljuk o e a a a az oper´ci´kutat´s feladat´t, ´s oszt´lyozzuk az optimumsz´m´ asi modelleket. a o a a e a a ıt´

1.4 Az oper´ci´kutat´s feladata, az optimumsz´m´ asi a o a a ıt´ modellek oszt´lyoz´sa a a

Az oper´ci´kutat´snak, mint tudom´ny´gnak a feladat´t a k¨vetkez˝k´ppen a o a a a a o o e hat´rozhatjuk meg: a Az oper´ci´kutat´s feladata a gyakorlati ´let k¨l¨nb¨z˝ probl´macsoportjaihoz a o a e uo o o e az illet˝ probl´macsoporto
Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!


kat le´ o optimumsz´m´ asi modellek konstru´l´sa, tov´bb´ o e ır´ a ıt´ aa a a a megl´v˝ modellekhez az optim´lis megold´st meghat´roz´ elj´r´sok kidolgoz´sa. e o a a a o aa a Igen fontos, ´s gazdas´gi okokb´l egyre ink´bb el˝t´rbe ker¨l az oper´ci´kutat´s e a o a oe u a o a gyakorlati alkalmaz´sa. Ez abban ´ll, hogy a megl´v˝ modelleket ´s elj´r´sokat a a a e o e aa gyakorlati ´let probl´m´inak megold´s´ra haszn´ljuk fel. Ahhoz, hogy ezt megtee e a aa a hess¨k, meg kell ismerkedn¨nk a modellekkel ´s a kapcsol´d´ elj´r´sokkal. Miel˝tt u u e o o aa o erre r´t´rn´nk megk´ erl¨nk r¨vid ´ttekint´st adni a fontosabb modellt´ ae e ıs´ u o a e ıpusokr´l. o Az optimumsz´m´ asi modellek t¨bb szempont szerint oszt´lyozhat´k. A k¨veta ıt´ o a o o kez˝kben ismertetj¨k a f˝bb szempontokat ´s a megfelel˝ oszt´lyoz´sokat. o u o e o a a I. Az elemi tev´kenys´gek intenz´ as´rt´keit˝l f¨gg˝en megk¨l¨nb¨ztet¨nk e e ıt´ e e o u o uo o u 1. folytonos modelleket, 2. diszkr´t modelleket, e 3. vegyes modelleket. Egy modellt folytonosnak nevez¨nk, ha a benne szerepl˝ xi (i = 1, . . . , n) v´ltoz´k u o a o mindegyik´re teljes¨l az, hogy xi a modell ´ltal meghat´rozott, i-t˝l f¨gg˝ intervallume u a a o u o ban b´rmilyen ´rt´ket felvehet. Diszkr´t modellr˝l besz´l¨nk akkor, ha a modellben a e e e o eu 6



a o a e o o szerepl˝ minden xi v´ltoz´ a sz´megyenes bizonyos diszkr´t pontjait tartalmaz´, i-t˝l o f¨gg˝ halmazb´l veheti fel az ´rt´keit. Ha a modell v´ltoz´ira az el˝z˝ felt´telek egyike u o o e e a o o o e sem teljes¨l, akkor vegyes modellr˝l besz´l¨nk. Megjegyezz¨k, hogy ´ltal´ban akkor u o eu u a a neveznek egy modellt vegyesnek, ha a fenti t´ u v´ltoz´kat ´s csak ilyeneket tartalıpus´ a o e maz. Az ut´bbi meghat´roz´ssal nem kapn´nk oszt´lyoz´st. P´ld´ul az x ∈ [a, b] vagy o a a a a a e a x ∈ {i1 , . . . , ik } felt´tel˝ modellt nem sorolhatn´nk sehov´. Ennek kik¨sz¨b¨l´s´re e u a a u o oe e haszn´ljuk a vegyes modellre a fenti, ´ltal´nosabb meghat´roz´st. a a a a a II. A modellekben szerepl˝ param´terek szerint megk¨l¨nb¨ztet¨nk o e uo o u 1. determinisztikus modelleket, 2. sztochasztikus modelleket. Determinisztikus modellr˝l akkor besz´l¨nk, ha a modellben szerepl˝ param´terek o eu o e pontosan meghat´rozhat´ konstansok. Abban az esetben, ha a modellnek van olyan a o u param´tere, amely val´sz´ us´gi v´ltoz´, akkor a modellt sztochasztikusnak nevezz¨k. e o ın˝ e a o III. Az olyan modellek k¨z¨tt, amelyekben a felt´telek mindegyike line´ris egyeno o e a l˝s´g vagy egyenl˝tlens´g, a c´lf¨ggv´ny szerint megk¨l¨nb¨ztet¨nk oe o e e u e uo o u 1. line´ris programoz´si modelleket, a a 2. nemline´ris programoz´si modelleket. a a Line´ris programoz´si modellr˝l vagy feladatr´l besz´l¨nk, ha a c´lf¨ggv´ny maga is a a o o eu e u e line´ris f¨ggv´ny. Ellenkez˝ esetben haszn´ljuk a modellre a nemline´ris programoz´si a u e o a a a feladat elnevez´st. e E r¨vid bevezet´sb˝l is kit˝nik, hogy az oper´ci´kutat´s igen nagy ´s sokr´t˝ o e o u a o a e eu anyagot foglal mag´ba. Ennek a nagy anyagnak csak egy kis r´sz´vel fogunk a e e megismerkedni a tov´bbiak sor´n. Els˝k´nt a line´ris programoz´s t´mak¨r´vel a a o e a a e oe foglalkozunk. Ismertetj¨k a line´ris programoz´si feladatok megold´s´ra szolg´l´ u a a aa ao szimplex algoritmust ´s ennek k¨l¨nb¨z˝ v´ltozatait. Ezt k¨vet˝en a lehets´ges e uo o o a o o e megold´sok halmaz´nak tulajdons´gait vizsg´ljuk, ´s ´rintj¨k a dualit´s, valamint a a a a e e u a az eg´sz´rt´k˝ line´ris programoz´s t´mak¨r´t, majd k´t speci´lis line´ris proe e e u a a e oe e a a gramoz´si feladatot vizsg´lunk, a hozz´rendel´si feladatot ´s a sz´ll´ asi feladatot. a a a e e a ıt´ Ezek ut´n a nemline´ris programoz´s n´h´ny speci´lis, viszonylag j´l kezelhet˝ felaa a a e a a o o dat´t t´rgyaljuk. a a ´ ´ 2. LINEARIS PROGRAMOZAS

2.1 A line´ris programoz´s ´ltal´nos feladata, a a a a standard feladat

Az el˝z˝ pontban megismerkedt¨nk az optimumsz´m´ asi modellek oszt´lyoz´s´o o u a ıt´ a aa val. Ennek kapcs´n defini´ltuk a line´ris programoz´si feladatot, amelyben a felt´telek a a a a e line´ris egyenl˝s´g, egyenl˝tlens´g form´j´ban adottak, ´s ezen felt´telek mellett kell a oe o e aa e e egy line´ris f¨ggv´ny maximum´t vagy minimum´t meghat´rozni. Tekintettel arra, a u e a a a hogy tetsz˝leges line´ris programoz´si feladatra max{z(x) : x ∈ L} ´s min{−z(x) : o a a e 8



u e e a a x ∈ L} egyidej˝leg l´teznek illetve nem l´teznek, tov´bb´ max{z(x) : x ∈ L} = −min{−z(x) : x ∈ L}, az optim´lis megold´s l´tez´se ´s meghat´roz´sa szempontj´b´l a a e e e a a a o elegend˝ a k´t t´ o e ıpus k¨z¨l
Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!


az egyik vizsg´lat´ra szor´ o u a a ıtkozni. Ennek megfelel˝en a o tov´bbiakban csak minimum feladatokat vizsg´lunk. a a Nyilv´nval´, hogy tetsz˝leges minimum feladat sorcser´kkel az al´bbi alakban a o o e a ´ ırhat´ fel: o a11 x1 + ... + a1m xm ≤ b1 . . . . . . . . . ak1 x1 + ... + akm xm ≤ bk ak+1,1 x1 + ... + ak+1,m xm = bk+1 . . . . . . . . . al1 x1 + ... + alm xm = bl al+1,1 x1 + ... + al+1,m xm ≥ bl+1 . . . . . . . . . an1 x1 + ... + anm xm ≥ bn —————————————————— α + c1 x1 + ... + cm xm = z → min

(2.1.1)

ahol 1 ≤ k ≤ l ≤ n. A feladatot m´trixokkal ´s vektorokkal a k¨vetkez˝k´ppen adhatjuk meg: a e o o e A1 x ≤ b(1) A2 x = b(2) A3 x ≥ b(3) ——————— α + cx = z(x) → min ahol A1 , A2 , A3 , b(1) , b(2) , b(3) , c a megfelel˝ egy¨tthat´kb´l ´ll´ m´trixokat illetve o u o o a o a vektorokat jel¨lik. A sor- ´s oszlopvektorokat k¨l¨n jel¨l´ssel nem fogjuk megk¨l¨no e uo oe uo b¨ztetni, az egyes formul´kb´l mindig ki lehet k¨vetkeztetni, hogy az illet˝ vektor soro a o o o e vektor vagy oszlopvektor. P´ld´ul a fenti fel´ asban c = (c1 , . . . , cm ) ´s x pedig olyan e a ır´ oszlopvektor, amelynek komponensei x1 , . . . , xm . Hasonl´an fogunk elj´rni a m´trixok, o a a vektorok m´reteit illet˝en is, azaz a t´ e o ıpust csak akkor ´ ırjuk ki, ha ez az ¨sszef¨gg´sekb˝l o u e o nem k¨vetkeztethet˝ ki, vagy a t´rgyal´s sz¨ks´gess´ teszi azt. A fenti fel´ asban A1 o o a a u e e ır´ p´ld´ul egy k × m-es m´trix. Megjegyezz¨k m´g, hogy szisztematikusan x-szel fogjuk e a a u e jel¨lni a vektorv´ltoz´t, ´s x, x∗ mindig egy-egy konkr´t vektort fog jel¨lni. o a o e ¯ e o ¯ Tekints¨k most a (2.1.1) feladatot. Nyilv´nval´, hogy egy x vektor akkor u a o ¯ ´s csak akkor el´g´ ki egy egyenl˝s´get, egyenl˝tlens´get, ha x kiel´g´ ennek az e e ıt oe o e e ıti egyenl˝s´gnek, egyenl˝tlens´gnek a −1-szeres´t is. K¨vetkez´sk´ppen, ha a (2.1.1) oe o e e o e e feladatban −1-gyel megszorozzuk azokat az egyenl˝s´geket, egyenl˝tlens´geket, ameoe o e lyek jobboldala negat´ akkor olyan line´ris programoz´si feladatot kapunk, amelyıv, a a nek felt´telrendszer´t azok ´s csak azok a vektorok el´g´ e e e e ıtik ki, amelyek kiel´g´ e ıtik a (2.1.1) feladat felt´telrendszer´t is. Ez azt jelenti, hogy e k´t felt´telrendszerhez tare e e e ´ a k´t feladatnak egyidej˝leg toz´ lehets´ges megold´sok halmaza megegyezik. Igy o e a e u ¯ l´tezik optim´lis megold´sa, tov´bb´, ha x optim´lis megold´sa az egyik feladatnak, e a a a a a a ¯ akkor x optim´lis megold´sa a m´sik feladatnak is. Ez azt jelenti, hogy az optim´lis a a a a 9



a aa o a ıpus´ a a megold´s l´tez´s´t ´s meghat´roz´s´t illet˝en az al´bbi t´ u feladatok vizsg´lat´ra a e ee e szor´ ıtkozhatunk: A1 x ≤ b(1) A2 x = b(2) A3 x ≥ b(3) , (b(i) ≥ 0, i = 1, 2, 3) ——————————————— α + cx = z(x) → min

(2.1.2)

Konstru´ljunk a (2.1.2) feladatb´l egy tov´bbi line´ris programoz´si feladatot a o a a a ugy, hogy a feladatban szerepl˝ xi v´ltoz´k mindegyik´t az ui , vi nemnegat´ v´ltoz´k ´ o a o e ıv a o k¨l¨nbs´g´vel helyettes´ uk. Ekkor a k¨vetkez˝ feladathoz jutunk: uo e e ıtj¨ o o A1 (u − v) ≤ b(1) A2 (u − v) = b(2) A3 (u − v) ≥ b(3) u ≥ 0, v ≥ 0, (b(i) ≥ 0, i = 1, 2, 3) —————————————— α + c(u − v) = z (u, v) → min ˜

(2.1.3)

A (2.1.2) ´s (2.1.3) feladatok k¨z¨tt igen szoros kapcsolat van, ezt adja meg az e o o al´bbi seg´dt´tel. a e e 1.seg´dt´tel. A (2.1.2) ´s (2.1.3) feladatoknak egyidej˝leg l´tezik optim´lis mege e e u e a old´sa, ´s az optim´lis megold´sok k¨zvetlen¨l sz´rmaztathat´k egym´sb´l. a e a a o u a o a o Bizony´ as. Tegy¨k fel, hogy a (2.1.2) feladatnak l´tezik optim´lis megold´sa, ´s ıt´ u e a a e ¯ ¯ jel¨lj¨n x egy optim´lis megold´st. K´pezz¨k az u, v vektorokat a k¨vetkez˝ m´don: o o ¯ a a e u o o o uj = ¯ xj , ha xj ≥ 0, ¯ ¯ 0 k¨l¨nben, uo vj = ¯ 0, −¯j x ha xj ≥ 0, ¯ k¨l¨nben. uo

Megmutatjuk, hogy (¯ , v) optim´lis megold´sa a (2.1.3) feladatnak. Ehhez els˝k´nt u ¯ a a o e e a e ıti e igazoljuk, hogy (¯ , v) lehets´ges megold´sa (2.1.3)-nak, azaz kiel´g´ annak felt´telu ¯ ¯ ¯ rendszer´t. Az (¯ , v) defin´ oj´b´l k¨vetkezik, hogy u ≥ 0, v ≥ 0. M´sr´szt vegy¨k e u ¯ ıci´ a o o a e u ¯ ¯ ¯ ¯ ´szre, hogy u − v = x. Mivel x a (2.1.2) feladat lehets´ges megold´sa, ez´rt e e a e ¯ ¯ ¯ A1 x ≤ b(1) , A2 x = b(2) , A3 x ≥ b(3) teljes¨l. De akkor A1 (¯ − v) ≤ b(1) , A2 (¯ − v) = b(2) , A3 (¯ − v) ≥ b(3) is telu u ¯ u ¯ u ¯ jes¨l, ´s ´ (¯ , v) lehets´ges megold´sa a (2.1.3) feladatnak. Most megmutatjuk, u e ıgy u ¯ e a hog
Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!


y (¯ , v) optim´lis megold´s is. Ehhez elegend˝ bel´tni, hogy a (2.1.3) feladat u ¯ a a o a ∗ ∗ ∗ ∗ e aa ˜ tetsz˝leges (u , v ) lehets´ges megold´s´ra z (u , v ) ≥ z (¯ , v) teljes¨l. Legyen x∗ = o ˜u ¯ u ∗ ∗ ∗ ∗ e a e u − v . Mivel (u , v ) lehets´ges megold´sa (2.1.3)-nak, ez´rt A1 (u∗ − v∗ ) ≤ b(1) , e u A2 (u∗ −v∗ ) = b(2) ´s A3 (u∗ −v∗ ) ≥ b(3) teljes¨l. De akkor A1 x∗ ≤ b(1) , A2 x∗ = b(2) ¯ ´s A3 x∗ ≥ b(3) , ´s ´ x∗ lehets´ges megold´sa a (2.1.2) feladatnak. Mivel x ope e ıgy e a tim´lis megold´s, ez´rt z(x∗ ) ≥ z(¯ ). M´sr´szt z(¯ ) = z (¯ , v) ´s z(x∗ ) = z (u∗ , v∗ ), a a e x a e x ˜u ¯ e ˜ amib˝l z (u∗ , v∗ ) ≥ z (¯ , v) k¨vetkezik, azaz (¯ , v) a (2.1.3) feladatnak egy optim´lis o ˜ ˜u ¯ o u ¯ a megold´sa. a ¯ Ezzel igazoltuk, hogy amennyiben x optim´lis megold´sa a (2.1.2) feladatnak, a a akkor a fentieknek megfelel˝en megkonstru´lt (¯ , v) optim´lis megold´sa a (2.1.3) o a u ¯ a a 10



o a o u ¯ a feladatnak. Teljesen hasonl´ gondolatmenettel bel´that´, hogy ha (¯ , v) optim´lis ¯ ¯ ¯ megold´sa (2.1.3)-nak, akkor az x = u − v vektor optim´lis megold´sa a (2.1.2) a a a feladatnak. Ebb˝l a k´t ´ll´ asb´l k¨vetkezik, hogy a (2.1.2) ´s (2.1.3) feladatoko e a ıt´ o o e nak egyidej˝leg l´tezik optim´lis megold´sa, ´s az optim´lis megold´sok k¨zvetlen¨l u e a a e a a o u sz´rmaztathat´k egym´sb´l. Ezzel az 1.seg´dt´tel bizony´ as´t befejezt¨k. a o a o e e ıt´ a u K¨vetkezm´ny. Az optim´lis megold´s l´tez´s´t ´s meghat´roz´s´t illet˝en eleo e a a e e e e a a a o gend˝ az al´bbi, (2.1.4) t´ u feladatok vizsg´lat´ra szor´ o a ıpus´ a a ıtkozni. A1 x ≤ b(1) A2 x = b(2) (2.1.4) A3 x ≥ b(3) x ≥ 0, (b(i) ≥ 0, i = 1, 2, 3) ————————————– α + cx = z(x) → min Val´ban, hiszen a z´r´jelek felbont´s´val ´s ´tjel¨l´sek alkalmaz´s´val a (2.1.3) feladat o ao aa e a oe aa (2.1.4) alak´ra hozhat´. Megjegyezz¨k, hogy a fenti Ai m´trixok nem egyeznek meg a u o u a (2.1.2)-ben szerepl˝ m´trixokkal, az azonos szimb´lumokat csak az egyszer˝bb jel¨l´so a o u oe technika ´rdek´ben haszn´ljuk. e e a Vizsg´ljuk ezek ut´n (2.1.4)-et. Konstru´ljuk meg hozz´ az al´bbi (2.1.5) feladaa a a a a tot, amelyben E(1) , E(3) megfelel˝ m´ret˝ egys´gm´trixok ´s u,v megfelel˝ dimenzi´j´ o e u e a e o ou vektorv´ltoz´k. a o A1 x + E(1) u = b(1) A2 x = b(2) A3 x −E(3) v = b(3) x ≥ 0, u ≥ 0, v ≥ 0, (b(i) ≥ 0, i = 1, 2, 3) ————————————————— α + cx = z(x) → min

(2.1.5)

A k´t feladat k¨z¨tt ism´t szoros kapcsolat van, amint azt a k¨vetkez˝ seg´dt´tel e o o e o o e e mutatja. 2.seg´dt´tel. A (2.1.4) ´s (2.1.5) feladatoknak egyidej˝leg l´tezik optim´lis e e e u e a megold´sa, ´s az optim´lis megold´sok k¨zvetlen¨l sz´rmaztathat´k egym´sb´l. a e a a o u a o a o ¯ Bizony´ as. Els˝k´nt igazoljuk, hogy amennyiben x (2.1.4) optim´lis megold´ıt´ a a o e ¯ ¯ sa, akkor (¯ , u, v) optim´lis megold´sa (2.1.5)-nek, ahol u = b(1) − A1 x, tov´bb´ x ¯ ¯ a a a a ¯ ¯ ¯ ¯ ¯ v = A3 x − b(3) . Az u, v defin´ oj´b´l ´s abb´l, hogy x lehets´ges megold´sa a (2.1.4) ıci´ a o e o e a ¯ ¯ ¯ feladatnak k¨vetkezik egyr´szt az, hogy x ≥ 0, u ≥ 0, v ≥ 0, m´sr´szt az, hogy o e a e ¯ ¯ ¯ ¯ ¯ A1 x + E(1) u = b(1) , A2 x = b(2) , A3 x − E(3) v = b(3) teljes¨l. Ez pontosan azt jelenti, u e a hogy (¯ , u, v) lehets´ges megold´sa a (2.1.5) feladatnak. Ahhoz, hogy (¯ , u, v) opx ¯ ¯ x ¯ ¯ tim´lis megold´s is, azt kell igazolnunk, hogy (2.1.5) tetsz˝leges (x∗ , u∗ , v∗ ) lehets´ges a a o e ∗ ∗ ∗ ∗ megold´s´ra z(x ) ≥ z(¯ ) teljes¨l. Ehhez vegy¨k ´szre, hogy ha (x , u , v ) lehets´ges aa x u u e e ∗ ¯ megold´sa (2.1.5)-nek, akkor x lehets´ges megold´sa (2.1.4)-nek. De akkor x opa e a tim´lis megold´s volta miatt z(x∗ ) ≥ z(¯ ) teljes¨l, amivel igazoltuk, hogy (¯ , u, v) a a x u x ¯ ¯ optim´lis megold´s. a a 11



o a o x ¯ ¯ Teljesen hasonl´ gondolatmenettel bel´that´, hogy amennyiben (¯ , u, v) a (2.1.5) ¯ feladat egy optim´lis megold´sa, akkor x a (2.1.4) feladat egy optim´lis megold´sa. a a a a A fenti k´t ´ll´ asb´l k¨vetkezik, hogy a k´t feladatnak egyidej˝leg l´tezik optim´lis e a ıt´ o o e u e a megold´sa, ´s ezek egym´sb´l k¨zvetlen¨l sz´rmaztathat´k. a e a o o u a o K¨vetkezm´ny. Az optim´lis megold´s l´tez´s´t ´s meghat´roz´s´t illet˝en eleo e a a e e e e a a a o gend˝ az al´bbi, (2.1.6) t´ u feladatok vizsg´lat´ra szor´ o a ıpus´ a a ıtkozni. (2.1.6) Ax = b x ≥ 0, (b ≥ 0) ————————– α + cx = z(x) → min

¨ Osszegezve az el˝z˝eket, igazol´st nyert, hogy tetsz˝leges line´ris program
Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!


oz´si o o a o a a feladat megold´sa visszavezethet˝ egy alkalmas (2.1.6) t´ u feladat megold´s´ra. a o ıpus´ aa Tekintettel ezen feladatok ilyen ´rtelm˝ kit¨ntetett szerep´re, a (2.1.6) t´ u feladae u u e ıpus´ tokat standard feladatoknak nevezz¨k. Az elmondottak egyben az al´bbi elj´r´st is u a aa szolg´ltatj´k, amely tetsz˝leges line´ris programoz´si feladat standard feladatra val´ a a o a a o visszavezet´s´re alkalmas. ee Elj´r´s: a a 1.l´p´s. Ha a megoldand´ feladat maximum feladat, akkor szorozzuk meg a c´le e o e f¨ggv´nyt −1-gyel, ´s keress¨k ennek az uj c´lf¨ggv´nynek a minimum´t. u e e u ´ e u e a 2.l´p´s. Ha szerepel negat´ mennyis´g a jobboldalon, akkor szorozzuk meg a e e ıv e megfelel˝ egyenl˝s´get vagy egyenl˝tlens´get −1-gyel. o oe o e 3.l´p´s. Ha szerepelnek olyan v´ltoz´k a feladatban, amelyekre nincs el˝´ e e a o oırva nemnegativit´si felt´tel, akkor helyettes´ uk rendre ezeket a v´ltoz´kat k´t nemnegat´ a e ıts¨ a o e ıv v´ltoz´ k¨l¨nbs´g´vel. a o uo e e o e a a 4.l´p´s. Minden egyes egyenl˝tlens´g baloldal´hoz adjunk hozz´ illetve vonjunk e e ki egy nemnegat´ v´ltoz´t att´l f¨gg˝en, hogy a tekintett egyenl˝tlens´gben ≤ illetve ıv a o o u o o e ≥ szerepel, ´s v´ltoztassuk az egyenl˝tlens´geket egyenl˝s´gekre. e a o e oe Az elj´r´s alkalmaz´s´t az al´bbi p´ld´n illusztr´ljuk: aa aa a e a a 1.p´lda. e 2x + 3y ≤ 5 −4x + 7y = 3 2x + 5y ≥ 5 8x− y ≥ −3 ——————————— 17 + 4x + 5y = z(x, y) → max Az els˝ l´p´s ut´n a k¨vetkez˝ feladatot kapjuk: o e e a o o 2x + 3y ≤ 5 −4x + 7y = 3 2x + 5y ≥ 5 12



8x− y ≥ −3 ———————————– −17 − 4x − 5y = z (x, y) → min ˜ V´grehajtva a m´sodik l´p´st, az al´bbi feladat ad´dik: e a e e a o 2x + 3y ≤ 5 −4x + 7y = 3 2x + 5y ≥ 5 −8x+ y ≤ 3 ———————————– −17 − 4x − 5y = z (x, y) → min ˜ A harmadik l´p´sben az x = x1 − x2 , y = x3 − x4 helyettes´ essel a k¨vetkez˝ e e ıt´ o o feladatot nyerj¨k: u 2x1 − 2x2 + 3x3 − 3x4 ≤ 5 −4x1 + 4x2 + 7x3 − 7x4 = 3 2x1 − 2x2 + 5x3 − 5x4 ≥ 5 −8x1 + 8x2 +x3 −x4 ≤ 3 xj ≥ 0, (j = 1, . . . , 4) ——————————————————– −17 − 4x1 + 4x2 − 5x3 + 5x4 = z (x1 , . . . , x4 ) → min ¯ V´g¨l a negyedik l´p´sben, bevezetve az x5 , x6 , x7 v´ltoz´kat, az al´bbi standard e u e e a o a feladathoz jutunk: 2x1 − 2x2 + 3x3 − 3x4 +x5 =5 −4x1 + 4x2 + 7x3 − 7x4 =3 2x1 − 2x2 + 5x3 − 5x4 −x6 =5 +x7 = 3 −8x1 + 8x2 +x3 −x4 xj ≥ 0, (j = 1, . . . , 7) ————————————————————— −17 − 4x1 + 4x2 − 5x3 + 5x4 = z ∗ (x1 , . . . , x7 ) → min A standard feladatok vizsg´lat´n´l igen hasznos lesz a k¨vetkez˝ fogalom. K´t a a a o o e standard feladatot ekvivalensnek nevez¨nk, ha a lehets´ges megold´sok halmazai egyu e a beesnek, ´s ezen a k¨z¨s L halmazon a k´t c´lf¨ggv´ny megegyezik. A bevezetett e o o e e u e rel´ci´r´l k¨nnyen bel´that´, hogy reflex´ szimmetrikus, valamint tranzit´ ´s ´ a oo o a o ıv, ıv, e ıgy a standard feladatok halmaz´n egy ekvivalenciarel´ci´. Ismeretes, hogy egy ekvivaa a o lenciarel´ci´hoz hozz´rendelhet˝ az illet˝ halmaz egy oszt´lyoz´sa, ha az egym´ssal a o a o o a a a ´ a bevezetett rel´ci´ alapj´n a stanekvivalens elemeket egy oszt´lyba soroljuk. Igy a a o a dard feladatok egy oszt´lyoz´s´hoz jutunk: k´t feladat akkor ´s csak akkor ker¨l egy a aa e e u oszt´lyba, ha ekvivalensek. Az ilyen m´don meghat´rozott oszt´lyokat az ekvivalena o a a u ıci´ a o o ciarel´ci´ oszt´lyainak nevezz¨k. Az ekvivalencia defin´ oj´b´l k¨vetkezik, hogy ekvia o a valens feladatok optim´lis megold´sai megegyeznek. Ez azt jelenti, hogy az optim´lis a a a megold´s l´tez´s´t ´s meghat´roz´s´t illet˝en adott feladat helyett tekinthet¨nk egy a e ee e a aa o u m´sik, az el˝z˝vel ekvivalens feladatot. Az ekvivalenci´nak ezt a k¨vetkezm´ny´t a a o o a o e e tov´bbiakban gyakran fel fogjuk haszn´lni. a a 13



Feladatok

a a a a 1. Hat´rozzuk meg az al´bbi line´ris programoz´si feladatokhoz rendre azokat a standard feladatokat, amelyekre az illet˝ line´ris programoz´si feladatok visszavezeto a a het˝k. o 3x1 + x2 − 4x3 ≥ −2 2x1 − x2 + x3 ≤ 8 x1 + x2 + x3 = 4 x1 ≥ 0 ——————————— 3x1 + x2 − 2x3 = z(x) → max 4x1 + x2 − 5x3 ≤ 7 2x1 + x2 + 2x3 ≤ 8 −5x1 + x2 ≥ −2 x1 ≤ 0, x2 ≥ 0 ————————————−2x1 − 4x2 + x3 = z(x) → min

(a)

(b)

2. Mutassuk meg, hogy az al´bbi standard feladatok ekvivalensek: a 2x − y = 0 x+y =1 x ≥ 0, y ≥ 0 ——————– 5x + 4y = z(x, y) → min −x + 2y = 1 −3x + 3y = 1 x ≥ 0, y ≥ 0 ———
Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!


——– −x + 7y = z(x, y) → min

3. Adjunk meg olyan standard feladatot, amely ekvivalens az al´bbi feladattal. a −8x + 12y = 9 −2x − 2y = 1 x ≥ 0, y ≥ 0 —————————– 2x + 3y = z(x, y) → min 4. Igazoljuk, hogy az al´bbi m˝veletek egy standard feladathoz olyan feladatot a u rendelnek, amely ekvivalens az eredetivel. (a) A feladat valamely egyenlet´t helyettes´ uk az illet˝ egyenlet egy pozit´ e ıts¨ o ıv konstansszoros´val. a 14



e a a (b) A feladat valamely egyenlet´nek konstansszoros´t adjuk hozz´ a feladat egy m´sik egyenlet´hez, ´s az eredm´nnyel helyettes´ uk az ut´bbi egyenletet, felt´ve, a e e e ıts¨ o e hogy az uj egyenlet jobboldala nemnegat´ ´ ıv. (c) A feladat valamely egyenlet´nek konstansszoros´t adjuk hozz´ a c´lf¨ggv´nyt e a a e u e meghat´roz´ egyenlethez, ´s az el˝all´ egyenlettel helyettes´ uk a c´lf¨ggv´ny egyena o e o´ o ıts¨ e u e let´t. e 5. Vezess¨k be a standard feladatok halmaz´n a k¨vetkez˝ rel´ci´t: k´t standard u a o o a o e feladat gyeng´n ekvivalens, ha lehets´ges megold´saik halmazai egybeesnek, ´s ezen e e a e a k¨z¨s halmazon a k´t c´lf¨ggv´ny elt´r´se konstans. Igazoljuk, hogy a bevezetett o o e e u e ee rel´ci´ ekvivalenciarel´ci´, tov´bb´ mutassuk meg, hogy gyeng´n ekvivalens feladatok a o a o a a e optim´lis megold´sai megegyeznek. a a

2.2 Szimplex algoritmus

A tov´bbiakban egy olyan elj´r´st ´p´ unk fel, amely alapj´n tetsz˝leges stana a a e ıt¨ a o dard feladatr´l eld¨nthet˝, hogy l´tezik-e optim´lis megold´sa, ´s ha l´tezik, akkor o o o e a a e e az elj´r´s alapj´n egy optim´lis megold´s meg is hat´rozhat´. Ezen elj´r´s fel´p´ ese aa a a a a o aa e ıt´ t¨bb l´p´sen kereszt¨l t¨rt´nik, ´s az algoritmus konkr´t megad´s´ra a 2.6 fejezetben o e e u o e e e aa ker¨l sor. Els˝ l´p´sk´nt egy speci´lis standard feladatot vizsg´lunk, ´s ehhez adunk u o e e e a a e meg egy, a megold´st szolg´ltat´ algoritmust. a a o Egy standard feladatot lehets´ges kanonikus alak´ feladatnak nevez¨nk, ha sore u u ´s oszlopcser´kkel, a v´ltoz´k ´tjel¨l´s´vel az al´bbi form´ban ´ e e a o a oe e a a ırhat´ fel: o a1,n+1 xn+1 + . . . + a1,n+m xn+m = b1 x2 + a2,n+1 xn+1 + . . . + a2,n+m xn+m = b2 . . . .. . . . . . . . xn + an,n+1 xn+1 + . . . + an,n+m xn+m = bn xj ≥ 0 (j = 1, . . . , n + m), (bi ≥ 0, i = 1, . . . , n) ——————————————————————————α+ +cn+1 xn+1 + . . . + cn+m xn+m = z(x) → min x1 +

(2.2.1)

A (2.2.1) feladattal kapcsolatban vegy¨k ´szre, hogy k¨zvetlen¨l leolvashat´ egy u e o u o trivi´lis lehets´ges megold´sa, nevezetesen xs = bs (s = 1, . . . , n), xn+t = 0 (t = a e a ¯ ¯ 1, . . . , m). Ezt a trivi´lis lehets´ges megold´st b´zismegold´snak, az xs (s = 1, . . . , n) a e a a a v´ltoz´kat pedig b´zisv´ltoz´knak nevezz¨k. Ha van olyan 1 ≤ i ≤ n index, hogy a o a a o u bi = 0, akkor a fenti b´zismegold´st szok´sos degener´lt b´zismegold´snak nevezni. a a a a a a A b´zismegold´st illet˝en vegy¨k ´szre, hogy az xs b´zisv´ltoz´ egy¨tthat´ib´l a a o u e a a o u o o a o ´ll´ oszlopvektor pontosan az n-dimenzi´s euklideszi t´r s-edik egys´gvektora, ´s o e e e 15



u o e u e e o e u u xs egy¨tthat´ja a c´lf¨ggv´ny egyenlet´ben 0-val egyenl˝. V´g¨l egyszer˝ behelyettes´ essel meg´llap´ ıt´ a ıthatjuk, hogy a z(x) c´lf¨ggv´ny a b´zismegold´son az α e u e a a ´rt´ket veszi fel. e e A k¨vetkez˝ t´tel elegend˝ felt´telt ad arra n´zve, hogy a (2.2.1) feladat b´zismeo o e o e e a gold´sa mikor lesz optim´lis megold´s. a a a 1.t´tel. A (2.2.1) feladat b´zismegold´sa egyben optim´lis megold´s is, ha e a a a a cn+t ≥ 0 (t = 1, . . . , m) teljes¨l. u Bizony´ as. Mivel a b´zismegold´son felvett c´lf¨ggv´ny´rt´k α, ez´rt elegend˝ ıt´ a a e u e e e e o ¯ igazolni, hogy a (2.2.1) feladat tetsz˝leges x lehets´ges megold´s´ra z(¯ ) ≥ α teljes¨l. o e aa x u ¯ Val´ban, x lehets´ges megold´s l´v´n nemnegat´ M´sr´szt a felt´tel szerint cn+t ≥ 0 o e a e e ıv. a e e m m (t = 1, . . . , m), ´ ıgy t=1 cn+t xn+t ≥ 0. De akkor z(¯ ) = α + t=1 cn+t xn+t ≥ α, ¯ x ¯ amivel az ´ll´ ast igazoltuk. a ıt´ A t´telben megfogalmazott el´gs´ges felt´telt szok´sos optimum-krit´riumnak e e e e a e nevezni. Azt, hogy a fenti felt´tel nem sz¨ks´ges, p´ld´ul a k¨vetkez˝ lehets´ges e u e e a o o e kanonikus alak´ feladat mutatja: u x1 +x3 = 0 x2 + x3 = 0 0 ≤ xj (j = 1, 2, 3) —————————−5x3 = z(x) → min ¯ Nyilv´nval´, hogy a fenti feladatnak egyetlen lehets´ges megold´sa van, az x = (0, 0, 0) a o e a vektor, amely egyben b´zismegold´s is, ´s optim´lis megold´s is. Ennek ellen´re az a a e a a e optimum-krit´rium nem teljes¨l
Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!


. e u a a a e e o e A k¨vetkez˝ t´tel, amely b´zisv´ltoztat´s t´tele n´ven ismeretes, lehet˝v´ teszi, o o e hogy bizonyos esetben a (2.2.1) feladatr´l ´tt´rj¨nk egy vele ekvivalens lehets´ges o a e u e kanonikus alak´ feladatra ugy, hogy az uj feladat b´zismegold´s´n felvett c´lf¨ggu ´ ´ a aa e u v´ny´rt´k ne legyen nagyobb, mint α. e e e 2.t´tel. Ha a (2.2.1) feladat c´lf¨ggv´ny´ben a cj (n + 1 ≤ j ≤ n + m) egy¨tthat´ e e u e e u o negat´ tov´bb´ l´tezik a ∆ = min{br /arj : arj > 0, 1 ≤ r ≤ n} mennyis´g, akkor ıv, a a e e megadhat´ egy olyan, a (2.2.1) feladattal ekvivalens lehets´ges kanonikus alak´ feladat, o e u amelynek x∗ b´zismegold´s´ra z(x∗ ) = α + cj ∆ teljes¨l. a a a u o e e e Bizony´ as. Els˝ l´p´sk´nt megkonstru´ljuk az uj feladatot. E c´lb´l tegy¨k fel, ıt´ a ´ e o u hogy cj < 0, ∆ = bk /akj ´s jel¨lje (2.2.1) i-edik egyenlet´t ri , a c´lf¨ggv´ny egyenlet´t e o e e u e e e a a ıt´ pedig z. Hajtsuk v´gre a (2.2.1) feladaton az al´bbi ´talak´ asokat: rk = ri = ri − aij rk akj 1 rk , akj (1 ≤ i ≤ n, i = k), cj rk , akj

z =z− 16



e ´ ahol rt az uj feladat t-edik egyenlet´t (t = 1, . . . , n), z pedig az uj feladat ´ c´lf¨ggv´nyegyenlet´t jel¨li. e u e e o Megmutatjuk, hogy a fenti m´don el˝´ll´ o oa ıtott feladat rendelkezik a k´ ant tulajıv´ dons´gokkal, azaz ekvivalens a (2.2.1) feladattal, lehets´ges kanonikus alak´, tov´bb´ a e u a a ∗ ∗ az x b´zismegold´s´ra z(x ) = α + cj ∆ teljes¨l. a aa u Az ekvivalencia igazol´s´hoz jel¨lje L a (2.2.1) feladat, ´s L az uj feladat aa o e ´ ¯ ¯ lehets´ges megold´sainak a halmaz´t. Legyen x ∈ L tetsz˝leges. Akkor x ≥ 0 e a a o n+m ´s x kiel´g´ az rt (t = 1, . . . , n) egyenletek mindegyik´t, azaz e ¯ e ıti e ¯ s=1 ats xs = bt (t = 1, . . . , n) teljes¨l, ahol tetsz˝leges 1 ≤ p ≤ n; 1 ≤ q ≤ n indexekre u o apq = 1, ha p = q, 0 k¨l¨nben. uo

Vizsg´ljuk az uj feladat ri egyenlet´t, ahol 1 ≤ i ≤ n, i = k. Az ri − (aij /akj )rk a ´ e osszef¨gg´ssel meghat´rozott ri egyenlet a k¨vetkez˝: ¨ u e a o o
n+m

ais −
s=1

aij aij aks xs = bi − bk . akj akj

¯ u ıt´ a o e ıti u Egyszer˝ behelyettes´ essel bel´that´, hogy x kiel´g´ a fenti egyenletet. Tekints¨k n+m ezek ut´n rk -t. Ez defin´ o szerint a k¨vetkez˝: a ıci´ o o e s=1 (aks /akj )xs = bk /akj . Ism´t ¯ ¯ behelyettes´ essel ad´dik, hogy x kiel´g´ ezt az egyenletet is. K¨vetkez´sk´pp x ıt´ o e ıti o e e kiel´g´ az uj feladat minden egyenlet´t, amib˝l x ∈ L , ´s ´ L ⊆ L k¨vetkezik. A e ıti ´ e o ¯ e ıgy o ¯ ford´ ıtott ir´ny´ tartalmaz´s igazol´s´hoz legyen x ∈ L tetsz˝leges. Akkor a u a aa o
n+m

ais −
s=1

aij aij aks xs = bi − bk ¯ akj akj
n+m s=1

(1 ≤ i ≤ n, i = k),

bk aks xs = ¯ akj akj

teljes¨l. Az ut´bbi egyenletb˝l s=1 aks xs = bk ad´dik. Ezt felhaszn´lva, az els˝ u o o ¯ o a o n+m n − 1 egyenletb˝l azt kapjuk, hogy s=1 ais xs = bi (1 ≤ i ≤ n, i = k) teljes¨l, azaz o ¯ u ¯ oe x ∈ L, amivel L ⊆ L ad´dik. Az igazolt k´t tartalmaz´sb´l az L = L egyenl˝s´g o e a o k¨vetkezik. Ezek ut´n az ekvivalenci´hoz m´g azt kell megmutatnunk, hogy az L o a a e halmazon a k´t c´lf¨ggv´ny megegyezik. Az uj c´lf¨ggv´nyt meghat´roz´ egyenlet a e e u e ´ e u e a o k¨vetkez˝: o o
n+m

n+m

α+
s=1

cs −

cj cj aks xs = z(x) − bk , akj akj

ahol ct = 0 (t = 1, . . . , n). Az egyenlet ´ltal meghat´rozott uj f¨ggv´nyt jel¨lje z (x). a a ´ u e o Rendez´ssel z (x)-re a k¨vetkez˝ kifejez´st kapjuk: e o o e
n+m

z (x) = α +
s=1

cj cs xs + akj 17

n+m

bk −
s=1

aks xs

.



¯ e o a o o e a x A fenti kifejez´sb˝l nyilv´nval´, hogy tetsz˝leges x ∈ L lehets´ges megold´sra z(¯ ) = z (¯ ) teljes¨l, amivel az ekvivalenci´t igazoltuk. x u a Ezek ut´n megmutatjuk, hogy az uj feladat lehets´ges kanonikus alak´. Ehhez a ´ e u els˝k´nt igazoljuk az el˝´ll´ o e oa ıtott feladat b1 , . . . , bn jobboldal´nak nemnegativit´s´t. a aa Val´ban, bk = bk /akj nemnegat´ mivel bk ≥ 0 ´s akj > 0. Most legyen 1 ≤ i ≤ n, o ıv, e i = k tetsz˝leges. Akkor bi = bi − (aij /akj )bk . Az aij el˝jel´t˝l f¨gg˝en k´t esetet o o eo u o e k¨l¨nb¨ztet¨nk meg. Ha aij ≤ 0, akkor bi ≥ 0 ´s bk /akj ≥ 0 alapj´n bi ≥ 0 teljes¨l. uo o u e a u Ha aij > 0, akkor ∆ = bk /akj miatt bi /aij ≥ bk /akj , ´s ´ bi ≥ (aij /akj )bk , amivel e ıgy bi ≥ 0 ad´dik. o Most vegy¨k ´szre, hogy egyr´szt az ´talak´ as sor´n az x1 , . . . , xk−1 , xk+1 , . . . , xn u e e a ıt´ a v´ltoz´k egy¨tt
Figyelem! Ez itt a doksi tartalma kivonata.
Kérlek kattints ide, ha a dokumentum olvasóban szeretnéd megnézni!


hat´i sem az egyenletrendszerben, sem a c´lf¨ggv´nyben nem v´ltoza o u o e u e a u nak, m´sr´szt kisz´m´ a e a ıtva az uj feladatban az xj v´ltoz´ aij (i = 1, . . . , n), cj egy¨tt´ a o hat´it, a k¨vetkez˝ket kapjuk: o o o 1, ha i = k, 0 k¨l¨nben. uo K¨vetkez´sk´pp, ha az uj feladatban az xs v´ltoz´kr´l ´tt´r¨nk az xs v´ltoz´kra o e e ´ a o a o o a eu ıt´ az xs = xs (1 ≤ s ≤ n + m, s = k, s = j), xj = xk , xk = xj helyettes´ essel, u ´s ´trendezz¨k az oszlopokat az uj v´ltoz´k indexei szerint, akkor egy (2.2.1) alak´ e a u ´ a o feladatot kapunk, azaz az uj feladat lehets´ges kanonikus alak´. ´ e u V´g¨l vizsg´ljuk az uj feladat x∗ b´zismegold´s´n a c´lf¨ggv´ny ´rt´k´t. A b´zise u a ´ a aa e u e e e e a ∗ ∗ ∗ megold´s defin´ oja szerint xj = bk , xi = bi (1 ≤ i ≤ n, i = k) ´s xs = 0 a tov´bbi s a ıci´ a e n+m ∗ ∗ ∗ indexekre. Az ekvivalencia miatt z (x ) = z(x ). M´sr´szt z(x ) = α + s=1 cs x∗ = a e s n+m ∗ α + t=n+1 ct xt = α + cj bk = α + cj bk /akj = α + cj ∆. cj = 0 , aij = Ezzel a 2.t´tel bizony´ as´t befejezt¨k. e ıt´ a u u Vegy¨k ´szre, hogy a fenti bizony´ asban alapvet˝ szerepet j´tszott az akj egy¨ttu e ıt´ o a u o ao hat´. Tekintettel ezen kit¨ntetett szerepre, az akj egy¨tthat´t gener´l´ elemnek o u nevezz¨k. Felt´telez´s¨nk szerint min{br /arj : arj > 0, 1 ≤ r ≤ n} = bk /akj . u e eu Nyilv´nval´, hogy A j-edik oszlop´nak t¨bb eleme is rendelkezhet ezzel a tulaja o a o dons´ggal. Mivel akj tetsz˝leges ilyen elem volt, ez´rt a bizony´ asban szerepl˝ a o e ıt´ o a ´talak´ as b´rmelyik, a fenti tulajdons´ggal rendelkez˝ egy¨tthat´ra ´rv´nyes. ıt´ a a o u o e e A 2.t´tellel kapcsolatban vegy¨k m´g ´szre, hogy pozit´ ∆ eset´n a r´gi feladatr´l e u e e ıv e e o az uj feladatra t¨rt´n˝ ´tt´r´s egyidej˝leg egy jobb megold´st is eredm´nyez abban ´ o e o a ee u a e az ´rtelemben, hogy az uj b´zismegold´son felvett c´lf¨ggv´ny´rt´k kisebb, mint az e ´ a a e u e e e eredeti b´zismegold´shoz tartoz´ c´lf¨ggv´ny´rt´k. Val´ban, ez ut´bbi ´rt´k α, m´ a a o e u e e e o o e e ıg az uj b´zismegold´shoz tartoz´ f¨ggv´ny´rt´k α + cj ∆, ami kisebb α-n´l, ha ∆ > 0. ´ a a o u e e e a Ezek ut´n vizsg´ljuk a 2.t´tel felt´tel´t. Nyilv´nval´, hogy min{br /arj : arj > 0, a a e e e a o 1 ≤ r ≤ n} akkor ´s csak akkor l´tezik, ha az arj (r = 1, . . . , n) elemek k¨z¨tt van e e o o legal´bb egy pozit´ Ellenkez˝ esetben a feladatnak nem l´tezik optim´lis megold´sa, a ıv. o e a a amint azt az al´bbi ´ll´ as mutatja. a a ıt´ 3.t´tel. Ha a (2.2.1) feladatban valamely n + 1 ≤ j ≤ n + m indexre cj < 0 ´s az e e (r = 1, . . . , n) elemek egyike sem pozit´ akkor a feladat c´lf¨ggv´nye alulr´l nem ıv, e u e o 18

arj



e a a korl´tos a lehets´ges megold´sok halmaz´n. a ¯ ¯ Bizony´ as. Felt´tel¨nk szerint arj ≤ 0 (r = 1, . . . , n). Defini´ljuk az x(1) , x(2) , . . . ıt´ e u a vektorsorozat elemeit a k¨vetkez˝k´ppen: o o e xj ¯
(k)

=k,

= br − arj k (r = 1, . . . , n) , = 0 (n + 1 ≤ s ≤ n + m, s = j), ahol k tetsz˝leges pozit´ eg´sz. Mivel arj ≤ 0 ´s br ≥ 0 teljes¨l b´rmely 1 ≤ r ≤ n o ıv e e u a indexre, tov´bb´ k > 0, ez´rt a fenti sorozat elemei rendre nemnegat´ vektorok. a a e ıv ¯ M´sr´szt egyszer˝ behelyettes´ essel ad´dik, hogy b´rmely k pozit´ eg´szre x(k) a e u ıt´ o a ıv e (k) ¯ kiel´g´ a (2.2.1) feladat egyenletrendszer´t, azaz x e ıti e lehets´ges megold´sa a felae a (1) (2) datnak. Vizsg´ljuk most a c´lf¨ggv´ny´rt´kek z(¯ ), z(¯ ), . . . sorozat´t. Behea e u e e e x x a e u e e lyettes´ x(k) -t a c´lf¨ggv´ny egyenlet´be, azt kapjuk, hogy z(¯ (k) ) = α + cj k. Ekkor ıtve ¯ x a cj < 0 felt´tel miatt, ha k → ∞, akkor z(¯ (k) ) → −∞. Ebb˝l viszont m´r ad´dik, e x o a o hogy z(x) alulr´l nem korl´tos a lehets´ges megold´sok halmaz´n, amivel az ´ll´ ast o a e a a a ıt´ igazoltuk. Az 1., 2. ´s 3.t´telekkel kapcsolatban megjegyezz¨k, ´s a tov´bbiakban felhasze e u e a n´ljuk a k¨vetkez˝ket. Tekintettel arra, hogy tetsz˝leges lehets´ges kanonikus alak´ a o o o e u feladat sor- ´s oszlopcser´kkel, a v´ltoz´k ´tjel¨l´s´vel (2.2.1) alak´ra hozhat´, ´s a e e a o a oe e u o e felsorolt m˝veletek az eredeti feladattal ekvivalens feladatot eredm´nyeznek, ez´rt az u e e eml´ ıtett h´rom t´tel tetsz˝leges lehets´ges kanonikus alak´ feladatra is ´rv´nyes. a e o e u e e A h´rom t´telt felhaszn´lva fel´p´ a e a e ıthet¨nk egy olyan elj´r´st, amely alkalmas u aa lehets´ges kanonikus alak´ feladatok megold´s´ra. Miel˝tt erre r´t´rn´nk, vegy¨k e u aa o ae e u ´szre, hogy a 2.t´tel alkalmaz´sa adott esetben nem egy´rtelm˝. Az eml´ e e a e u ıtett t´tel e k´t helyen i