Krekó Béla
ÚJ MÓDSZER AZ OPTIMUMSZÁMÍTÁSBAN
Még két éve sincs annak, hogy az újságírói fantázia a kelleténél nagyobb mértékben keltette fel a közvélemény érdeklődését egy olyan matematikai eljá rással kapcsolatban, amelyet elliptikus módszernek szoktak nevezni. Az események hátterében az a tény áll, hogy L. G. H A C S I J A N szovjet matematikus 1979 februárjában közzétett egy új algoritmust a lineáris progra mozási feladatok megoldására. A közlemény mindjárt felkeltette a szakemberek érdeklődését, és ennek nyomán elég széles körben indult meg az új eljárás vizsgálata. Erre annál is inkább szükség volt, mert a szerző az említett, lényegé ben csak a bejelentést célzó cikkében nem adta meg a matematikai indoklást. (A legfontosabb irodalmi adatokról a cikk végén található jegyzék nyújt tájé koztatást.) A matematikusok előtt tehát a dolog már távolról sem volt ismeret len, amikor az üggyel a napi sajtó is elkezdett foglalkozni. S amint ilyenkor gyakran megtörténik, az újságírók inkább az olvasók fantáziájának felcsigázására, mintsem a kérdés reális megítélésére törekedtek. N e m lehetünk biztosak abban, hogy ezzel jó szolgálatot tettek ennek a kétségtelenül jelentős vállal kozásnak. A jelen cikknek az a célja, hogy valós képet nyújtson az olvasónak. /. A módszer
alapgondolata
Az elliptikus algoritmus tulajdonképpen arra ad lehetőséget, hogy segítsé gével megkeressük egy adott lineáris egyenlőtlenség-rendszer valamelyik lehet séges megoldását. (Feltéve természetesen, hogy ilyen megoldás egyáltalában létezik.) Az eljárás lényegére egy egyszerű példa segítségével is könnyen rávilá gíthatunk. E cél érdekében tekintsük a következő feladatot: (H,) 3x,-5x =-20 (H ) -3x,-2x =- 6 (Hj) x = 7 2
2
2
2
* Elsősorban arra a cikkre gondolunk, amely a N E W Y O R K TIMES címoldalán jelent meg 1979 novemberében: "A SOVIET D I S C O V E R Y R O C K S W O R L D O F M A T H E M A T I C S "
E feladat könnyen megoldható elemi eszközökkel is, de az elliptikus módszer bemutatása érdekében ezeket az eszközöket most nem vesszük igénybe. Az algoritmus azzal kezdődik, hogy megnézzük, megoldást jelent-e az origó, azaz az x = 0 pont. Mivel az x i = 0 és x = 0 helyettesítéssel már az első egyenlőt lenségnél ellentmondásra jutunk, megállapíthatjuk, hogy az x vektor nem ad megoldást. A következő lépés abban áll, hogy az origóból, mint középpontból, húzunk egy olyan kört, amely biztosan tartalmaz legalább egy megoldást. H a a sugarat elég nagyra választjuk, ilyen kör mindig található, hacsak a lehetséges megoldások halmaza nem üres. Annak vizsgálatába, hogy e sugár hosszát hogyan kell megválasztani, itt nem bocsátkozunk, csupán arra a tényre szorít kozunk, h o g y az R = 5 összefüggésnek megfelelő E k ö r eleget tesz a kikötések nek.' A z E k ö r t és a (Hi) egyenlőtlenséggel megadott félsíkot az 1. ábra szemlélteti. ^\ o
2
0
0
0
i ABRH A félsík határvonalát a 3xi-5x2=—20 reláció meghatározta egyenes képezi. E z az egyenes az E k ö r t az A i és az A2 p o n t b a n metszi. S h a ezt az egyenest önmagával párhuzamosan eltoljuk, a H ' i szimbólummal jelölt érintőhöz jutha tunk, amely az E k ö r t az Aj p o n t b a n érinti. Á következő lépésben meg kell keresnünk azt a minimális területű Ei ellip szist, amely egyrészt keresztülmegy az A j , A , A p o n t o k mindegyikén, másrészt pedig a H ' i egyenessel ugyancsak az A 3 p o n t b a n érintkezik. A számí tások szerint az Ej középpontja az -2 ¥1 = 3,4 vektornak megfelelő p o n t . " Mivel ez a ( H ) egyenlőtlenséget még n e m elégíti ki, az előbbi e l j á r á s t - t á m a s z k o d v a a 2 . á b r á r a 0
0
2
2
* Az R az £ kör sugarát jelenti. ' A számításokat egy tizedes jegyre terjedő pontosággal végeztük. 0
3
\ y
^r
1 1
\
yyi
\ \
\
>
\ j»c
\
: ABf
megismételjük. A ( H ) egyenlőtlenséghez tartozó félsíkot a -3xj—2x2=—6 egyenlőség által meghatározott egyenes határolja. E z az egyenes az E p e t az A4 és az A 5 pontban metszi, a H V v e l jelölt értintő pedig az E|-et az A pontban érinti. Most olyan ú j , minimális területű ellipszist kell konstruálni, amely átmegy az előbbi három p o n t o n , s amelyet a H% egyenes ugyancsak az A pontban érint. E követelményeket - a számítások szerint - teljesíti az az E ellipszis, amelynek középpontja 2
6
6
2
X 2
_0 ~4,5
K ö n n y e n meggyőződhetünk arról, hogy ez már kielégíti mind a három egyen lőtlenséget. Feladatunkat ezzel meg is oldottuk. Lényegében ugyanerről van szó az általános esetben is. A magasabb dimenzi ójú terekben persze eleve le kell m o n d a n u n k a szemléltetésről. A z egyes egyen lőtlenségeknek megfelelő halmazok határát nem egyenesek, hanem hipersíkok képezik, az ellipszisek szerepét pedig ellipszoidok veszik át. A módszer alap gondolata azonban változatlan marad. Alkalmasan megválasztott ellipszoido kon keresztül mindaddig folytatjuk a számításokat, amíg olyan ellipszoidhoz nem jutunk, amelynek középpontja már minden egyenlőtlenséget kielégít. Bebizonyítható, hogy ez véges számú lépésben elérhető, amennyiben a feladat nak van megoldása.
2. Az algoritmus
leírása
S most megadjuk az. algoritmus formális leírását, mellőzve a részletes mate matikai indokolást.'' Itt csupán az a célunk, hogy érthetővé tegyük az eljárás „működését". Tegyük fel, hogy az (1)
A* á
íz
összefüggéssel megadott egyenlőtlenségrendszerről van szó, amelyben az A egy adott m.n tipusú mátrix, a b pedig egy adott m-elemű vektor. A z x az n-dimenziós euklideszi tér bármely olyan pontja lehet, amely kielégíti az (1) alatti relá ciót. Eleve feltesszük, h o g y az [A., b] mátrix elemei mind egész számok. H a az eredeti feladat paraméterei a racionális számtesthez tartoznak, ez a követelmény mindig biztosítható. A trivialitások elkerülése végett feltesszük azt is, h o g y az [A, b] mátrixnak nincsen olyan oszlopa, az A-nak pedig nincsen olyan sora, amelyben minden elem 0 lenne. A z o n x vektorok halmazát, amelyek kielégítik az (1) alatti.egyenlőtlenséget M-mel fogjuk jelölni. A z a feladat, hogy határoz zuk meg az M egyik elemét. H a a b-nek nincs egyetlen negatív komponense sem, akkor az x=0_ vektor máris megoldást jelent. Ellenkező esetben azzal folytatjuk az eljárást, h o g y megkonstruáljuk az
(2)
-JT-K'x
á
1
1
összefüggésnek megfelelő E halmazt.'" A z E olyan n-dimenziós gömböt jelent, amelynek a sugara R. A z R-et úgy kell megválasztani, hogy ez a gömb minden képpen tartalmazzon M-beli elemet, amennyiben az M nem üres. Be lehet bizonyítani, hogy az alábbi elgondolás célhoz vezet: Először is képezzük az [A, bj mátrix oszlopvektorainak euklideszi normáit.*"' Legyenek ezek rendre az 0
0
A
A
f
*
»i> 22» • • • > a >
D
n
skalárok, amelyek az adott kikötések mellett mind pozitívok. E z u t á n e n o r m á k segítségével definiáljuk az R^n-áiáj. •. á b + l n
" A matematikában kellő jártassággal rendelkező olvasó számára az irodalomjegyzékre utalunk. ** Az x'x oszlopvektor transzponáltja, így az x ' x a z x vektornak önmagával alkotott skaláris szorzatát jelenti. '** Valamely a vektor euklideszi normáján az Vl*ji skalárt értjük. Ha az a nem nullvektor akkor ez a skalár pozitív.
előírásnak megfelelő pozitív valós számot. Ez az R már biztosan megfelel a kitű zött célnak. A z előbbiek alapján egy közbeeső - itt a k indexszel jelölt - iteráció tárgya lásánál már ismertnek tételezzük fel az
(3)
(í-ík)*
fi'(x-a)
^ i
formulával definiált ellipszoidot, ahol az X|< az ellipszoid középpontja, a Pk pedig az ellipszoid alakját meghatározó pozitív definit mátrix. Feltesszük azt is, hogy az Xk eleme az M-nek, az Ek mindazonáltal tartalmazza mindazon M-beli elemeket, amelyek bennefekszenek az E -ban is. Az induláskor k = 0 , x = Q és Pb=R E, ahol az R az előbb definiált pozitív skalár, az E p e d i g az egységmátrix szimbóluma. A z iteráció lebonyolításánál az az első teendőnk, hogy meghatározzuk min den i = l , 2 , . . . , m indexre nézve az n
e
m
0
2
0
H x k - b;
ViÍPkii 1
hányados értékét, ahol az a*, az A mátrix i-edik sorvektorát, a b; pedig a b vektor i-edik komponensét szimbolizálja. E hányadosok közül azután kiválasztjuk a maximálisát, amelyet d^-val fogunk jelölni. H a ugyanekkor a megfelelő aj vektort egyszerűen a'-val, a b, komponenst meg b-vel jelöljük, akkor
i
A dk az Xk pontnak az a ' x = b egyenlettel megadott hipersíktól való távolságát jellemzi. így a dk meghatározása úgy interpretálható, hogy az e'|(Ax)=elb alakú egyenlőségek* által meghatározott hipersíkok közül kiválasztjuk azt amelyik legtávolabb fekszik az Xk ponttól. Mivel az Xk az (1) által képviselt egyen lőtlenségek közül legalább egyet nem teljesít, biztosak lehetünk abban, hogy d > 0 k
A z a kérdés azután, hogy a dk mekkora pozitív szám, a további vizsgálatok szempontjából alapvető jelentőségű. a/ H a történetesen dk > 1, ez azt jelenti, hogy az induló E ellipszoid tu lajdonképpen egyetlen M-beli elemet sem tartalmaz. Ez azonban csakis akkor következhet be, ha a feladat nem oldható meg, azaz M = 0 . A dk > 1 esetben te hát az algoritmust azzal a megállapítással fejezhetjük be, hogy az adott feladat nak nincs megoldása. b / H a d k = l , akkor arról van szó, hogy a további vizsgálatoknál csupán az 0
s
* Az e ; [0, , . . , 1 , . . . , 0] vektor az i-edik egységvektor.
(5)
^"TTEI**
p o n t jöhet s/óba. H a ugyanis az E tartalmaz M-beli elemet, akkor az a jelen £setben csupán az Xk pont lehet. így már csak annak a vizsgálata van hátra, hogy teljesül-e az Axk = b reláció, vagy sem. H a teljesül, akkor az Xk eleme az M-nek, ha azonban nem teljesül, akkor az M halmaz üres. így az algoritmus mindenképpen befejeződik. cl H a dk < 1, akkor az E , s így az Ek is, t ö b b M-beli pontot is tartalmaz hat. A feladat most az, hogy határozzunk meg egy minimális térfogatú E k ellipszoidot, amely az előbb említett pontokat ugyancsak tartalmazza. A vizsgá latok szerint az új ellipszoid középpontja az 0
0
+)
W
Xk+i =
Xi--7===
Eá
V l'Pki vektor, ahol (7)
h =k
ndk+1 n+ 1
H a az xy kielégíti az A x k + i = b előírást, akkor azzal a megállapítással, hogy az j f k + i megoldása a feladatnak, az algoritmust befejezettnek tekinthetjük. Ellenkező esetben meg kell határozni az Ek+i ellipszoidhoz tartozó Pj^+i mátrixot is. E mátrixot a +]
formula szolgáltatja, ahol
n
1-dk
Ezután rátérhetünk a következő iterációra. Felmerülhet még a kérdés; Mi biztosítja az algoritmus végességét? A felelet a következő: H a az algoritmus nem fejeződnék be a 2
4 (n + 1 ) • 1 n (nR) kifejezésnek megfelelő számú iteráció lebonyolítása után, akkor biztosak lehetünk abban, hogy a fela datnak nincs lehetséges megoldása. Az eljárás tehát mindenképpen véges. Ezzel az algoritmus leírását be is fejeztük. 3. Mire használható
az elliptikus
módszer?
Mindenekelőtt lineáris egyenlőtlenség-rendszerek megoldására. Ez már ön magában véve is széles körű alkalmazási lehetőséget biztosít. Legfontosabb alkalmazási területének azonban most is a lineáris programozási feladatok megoldását tekintik.
K ö n n y e n megmutatható, h o g y bármely lineáris programozási feladat m e g oldása visszavezethető egy alkalmas egyenlőtlenségrendszer megoldására. Tekintsük ugyanis a következő feladatot:
XÍ=P_ As^b c_*x —> max Mint ismeretes, ehhez - az ú n . primális feladathoz - az alábbi duális feladat tartozik:
u* b —> min A dualitási tételek értelmében a két célfüggvény kapcsolatát a C'X
= u'b
reláció jellemzi, ahol az x bármely lehetséges megoldása lehet a primális feladatnak, az u pedig bármely lehetséges megoldása a duális feladatnak. Egyen lőség csakis olyan (xo>lío) vektorpár mellett jöhet létre, ahol az XQ a primális feladatra nézve, az u pedig a duális feladatra nézve optimális megoldást jelent. A z elmondottakból következik, h o g y az 0
x £ Q,u. ^ £ - A*u ^ - c _
hja - c_*x ^ 0 egyenlőtlenség-rendszer bármely lehetséges megoldása optimális megoldást szolgáltat mindkét duális feladatra nézve. S az elliptikus módszer éppen arra nyújt lehetőséget, h o g y meg tudjuk határozni egy adott lineáris egyenlőtlenségredszer valamelyik lehetséges megoldását. Megjegyezzük, h o g y számítástechnikai szempontból az előbbinél gazdasá gosabb utat is lehet találni a lineáris programozási feladatok megoldására. S m i vel bármely hiperbolikus programozással kapcsolatban lehet szerkeszteni egy vele ekvivalens lineáris programozási feladatot, világos, h o g y a hiperbolikus probléma is megoldható az elliptikus módszerrel. Folynak a vizsgálatok a tekintetben is, hogyan lehetne az elliptikus eljárás hatókörét egyéb matemetikai programozási feladatok megoldására is kiterjesz teni. Ilyen vizsgálatról ad számot pl. az [5] alatti tanulmány.
4. A módszer
értékelése
Elméleti szempontból az elliptikus módszer kétségtelenül nagy jelentőségű. Számos teoretikus problémát magasabb szinten old meg, mint a matematikai programozás egyéb eljárásai. A z ezzel kapcsolatos megjegyzéseinket két pont ban foglalhatjuk össze: a/ A z elliptikus módszer bizonyítottan polinomiális algoritmus. Ez végső fokon azt jelenti, h o g y a végrehajtás során felmerülő elemi műveletek száma a feladat paramétereinek felírásához szükséges bináris k ó d o k számának poli nomiális függvénye. A szakemberek jól tudják, hogy az algoritmus alkalmazása szempotjából ez igen előnyös tulajdonság. A matematikai programozás ismert algoritmusai közül számos eljárás nem rendelkezik ezzel a sajátossággal. b / A numerikus stabilitás az elliptikus algoritmusnál elvben eldöntött kér désnek tekinthető. Ezzel szemben az általánosan ismert szimplex módszernél a stabilitás kérdésére még nem t u d u n k egzakt feleletet adni. A gyakorlati alkalmazásokat illetően már más a helyzet. Ezt legjobban akkor tudjuk megítélni, ha az összehasonlításnál a szimplex módszert vesszük alapul. Találtak ugyan olyan speciális feladattípusokat, amelyeknél az ellipti kus algoritmus gyorsabban vezet eredményre, mint a szimplex módszer, általá nosan szemlélve azonban a kérdést, azt állíthatjuk, hogy az elliptikus módszer hatékonysága még távolról sem közelíti meg a szimplex módszer hatékonysá gát. Ennek két alapvető oka van: a/ A z indulásnál szereplő R sugár a tapasztalat szerint olyan nagy szám, hogy több nagyságrenddel haladja meg a szükséges mértéket. b / A konvergencia a gyakorlatban felmerült feladatoknál rendkívül lassúnak bizonyult. E nehézségek kiküszöbölésére számos kísérlet történt már, de folynak a próbálkozások ma is. Reális a remény, hogy a kutatások kellő eredménnyel fognak járni.
IRODALOM [ 1] XaHMHH, JIT.: ITojnmoMMajibHbiM a J i r o p w T M b JIMHCMHOM nporpaMMHHOBaHMM. floKji. AH CCCP, 1979b 244, N? 5, 1093-1096. [2] Gács, P.-Lovász, L.: KHACHIAN'S ALGORITHM FOR LINEAR PRO GRAMMING, Report STAN-CS-79-750, Stanford University, 1979. [3) Wolfe, P. THE ELLIPSOID ALGORITHM, Optima, Mathematical Program ming Society Newsletter, 1980 Nr. 1 [4] Walukiewicz, S.: ELLIPSOIDAL ALGORITHM FOR LINEAR PROGRAM MING, Linköping Institut of Technologic LiTH-MAT-R-80-11, 1980. [5] Grötschel, M.-Lovász, L.-Schrijver, A.: THE ELLIPSOID METHOD AND ITS CONSEQUENCES IN COMBINATORIAL OPTIMIZATION, kéz iratban [6] XaHMHH, Jl.r.: nojiHHOMnajibHbie aJiropwTMbi b JIMHCMHOM n p o r p a M M a p o B&HHM. )K. BblHMCJI. M f l T e M . M MaTeb. ( p M 3 . , 1980, 20, JN? 1, 5fl-68.
Summary
N e w method of Optimization In the past few years, both professional and daily news, magazines have been occupied more or less with Hacsijan's new method of optimization, socalled elliptical method. This article is to give a realistic picture of this circle of problems. Serving this interest it gives, the algorithm and information on the effectiveness of this method as well as possibilities of application. For those who want to get deeply involved with the problems there is a list of literature and instructions.
Rezime
Novi metod u izračunavanju optimuma U zadnjih godinu i po dana, stručno javno mnenje, kao i dnevna štampa, mnogo se bavila, novim načinom izračunavanja optimuma, koji je razvio HAČIJAN, sa tzv. elip tičnim metodom. Cilj ovog članka je, da pruža realnu sliku o čitavoj toj problematici. U tom cilju opisuje se algoritam, daje se obaveštenje o efektivnosti i mogućnosti korišćenja postupka. Za one, koji i dalje žele da se pozabave sa ovom problematikom dublje, daje se na kraju članka spisak literature i potrebna uputstva.
