ALKALMAZOTT MATEMATIKAI LAPOK 6. KÖTET (A MTA Matematikai és Fizikai Tudományok Osztályának Közleményei, 1980)

1980 / 1-2. sz. - Maros István: A bázisból kilépő vektor meghatározásának egy módja a szimplex módszer első fázisában

ÚJ ELJÁRÁS A SZIMPLEX MÓDSZER ELSŐ FÁZISÁBAN Jelöljük ß-val az aktuális bázismegoldást, vagyis (2.3) ß = В^Б, ahol ν-1 a bázisinverz és ρ az eredeti b jobb oldal vektorból keletkezik oly módon, hogy a bázison kívül felső korláton levő változóknak (ezek indexhalmaza: 1) meg­felelő oszlopok hatását figyelembe vesszük: (2.4) Б = Ь -2»j*j­jíf További jelölések: IB a bázisváltozók indexhalmaza, /0 a 0 típusú bázisváltozók indexhalmaza, /, az 1 típusú bázisváltozók indexhalmaza, /2 a 2 típusú bázisváltozók indexhalmaza, /3 a 3 típusú bázisváltozók indexhalmaza. Nyilvánvalóan fennáll az (2.5) IB­M /0U/10/10/a összefüggés. Említettük, hogy a lineáris programozás első fázisa egy fizibilis (megengedett) megoldás megkeresésére szolgál, továbbá infizibilis értéken levő változók csak bázis­változók lehetnek. A bázisváltozókat ennek megfelelően feloszthatjuk fizibilitás szempontjából. Az egységes tárgyalás érdekében a 0 típusú változókra is értelmez­zük a felső korlátot és ennek értékét értelemszerűen 0-nak tekintjük. Ezek előre­bocsátásával a bázisváltozók fizibilitási állapotát kifejező három indexhalmazt definiálunk: Af = {/: in t/3Aft· 0}, P ={i: iC/oU/jA^ F = IB\(MDP). M tehát a mínusz irányban, P a plusz irányban infizibilis változók indexhalmaza, F pedig a fizibilis értéken levő változóké. Egy 3-as típusú bázisváltozó mindig az F halmazhoz tartozik. Egy bázismegoldás infizibilitásának mértékét a következőképpen definiáljuk: (2.6) w = 2 pi-Z(p,-»il ií) ií) Ezt úgy értelmezhetjük, hogy w az infizibilis bázisváltozók fizibilitási tartomány­tól való távolságának a 2 1-szerese. Megjegyezzük, hogy ez a definíció érdemben különbözik az Orchard—Hays [4] által használt (2-7) w = Z ßi~ 2 ß. i(M iíP mértéktől, amint azt a későbbiekben kimutatjuk. Nyilvánvaló, hogy és a 0-t éppen akkor éri el, amikor a definícióban szereplő két halmaz üressé válik, azaz a bázismegoldás fizibilis. Az első fázisban a cél tehát egy olyan megoldás megtalálása, melyre a 1­0 teljesül. Ez elérhető azáltal, hogy maximalizáljuk iv-t a (2.1) feltételek

Next