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

1986 / 1-2. sz. - Klafszky Emil és Terlaky Tamás: Magyar módszer típusú algoritmusok lineáris programozási feladatok megoldására

2 KLAFSZKY E. ÉS TERLAKY T. Mielőtt az algoritmusok ismertetésére rátérnénk, röviden összefoglaljuk a bázistábla alaptulajdonságait, és közöljük a criss-cross módszert definiáló pivotálási szabályt. Jelöléseinkkel kapcsolatban megjegyezzük, hogy a mátrixokat nagy, a vektorokat kis latin betűkkel jelöljük, valamint a vektorok koordinátáit és a skalárokat a megfelelő görög betűkkel. Tekintsük az alábbi lineáris programozási feladatpárt : min cx feltéve, hogy Ax=b xsrO max yb feltéve, hogy yA=c Ahol A tetszőleges m-szer n-es mátrix (feltehetjük, hogy rang (A)—rrí), c= = (Vx, •••‡ Уя), X=(ci, •••‡ ›n, b=(pu ..., pj és y=0h, ..., Í/1. írjuk fel egy adott bázisnak megfelelően a bázistáblát. Megjegyezzük, hogy a tábla i-edik során az a bázisvektorhoz tartozó sort értjük, eltérően a szokásos „földrajzi" koordinátáknak megfelelő sorszámozástól. Jól ismert, hogy у=свВ \ z=(Ci, ..., £„)=свВ *A=yA és Ç0=cBxB=yb, ahol cB, illetve xB a c, illetve x vektor JB-hez tartozó koordinátáit tartalmazza. Legyen t(i=(% Tf)=y(f)A, ha ieJB és t0)=(T0)1, ..., т0)я), ha Д/в, ahol Az alábbiakban közölt definíciók, észrevételek jól ismertek, illetve könnyen ellenőrizhetőek. Bizonyításukra most nem térünk ki, a bizonyítások megtalálhatók például PRÉKOPA ANDRÁS [8] könyvében. 1.1. DEFINÍCIÓ. AZ a. vektor i£jtí esetén nem prímás megengedett, ha FJ-10. 1.2. DEFINÍCIÓ. Az ay vektor$JB esetén nem duál megengedett, ha 0j—yj^-0. 1.3. Megjegyzés. Ha x primál megengedett, y duál megengedett megoldás, és (yA—c)x=0, akkor x és x optimális megoldások. (Függetlenül attól, hogy bázismegoldások-e vagy sem). 1.4. Megjegyzés. Ha ^,1 0 és t(i)S0 valamely i£/B esetén, akkor nem létezik primár megengedett megoldás, a„ b 1. ábra TU)i -t is, ha i6/B — 1, ha isj 0, máskor. Alkalmazott Matematikai Lapok 12 (1986)