INFORMATICA1/85 REDUCIRANJE SIMPLEKSNE TABELE SPLOŠNE METODE SIMPLEKSOV TALIBDAMIJ JANEZ GRAD UDK: 519.852.61 ISKRA DELTA, LJUBLJANA, UNIVERZA EDVARDA KARDELJA V LJUBLJANI, EKONOMSKA FAKULTETA BORISA KIDRIČA, LJUBLJANA Metoda simpleksov je iteracijski postopek, ki se odlikuje po enostavnosti in hitrosti, Vendar pa je velik porabnik pomnilnika. V našem članku opišemo, kako je možno postopek simpleksov modifici­ rati ter s tem zmanjšati zahteve po pomnilniku samo na prostor, ki ga potrebuje vhodna matrika neenačb. REDUCTION OF THE SIMPLEX TABLEAU HITHIN THE GENERAL SIMPLEK METHOD. The general simplex method is known as a simple and fast iterative prooess but it as alsb known as a hig computer storage consumer. In our paper we describe the necessary modifications of this method which enable us to reduce the size of simplex tableau to the size of the input matrix of the set of linear unequations. 1. UVOD 2. SPLOŠNA METODA SIMPLEKSOV Metoda simpleksov je najbolj splošna metoda za numerično reševanje problemov linearnega pro­ gramiranja; z njo lahko rešimo sleherni line­ arni program, kar je izrednega pomena za njeno uporabo pri različnih-problemih optimizacije v gospodarstvu. Metoda simpleksov je v bistvu iteracijski po­ stopek, pri katerem v okviru vsakega iteracij- skega koraka iz že znane bazne možne rešitve iščemo novo optimalnejšo možno rešitev. Odli­ kuje se po tem, da je zelo primerna za raču­ nalniško obdelavo, vendar pa je pri velikih sistemih tudi velik porabnik pomnilnika. Za metodo je namreč značilno, da temelji na tako Imenovani simpleksni tabeli, v katero morajo biti razvrščene vse spremenljivke ter da je potrebno na vsakem koraku izračunati in shra­ niti v pomnilniku celotno tabelo. Tak način' dela pa zahteva precej računalniškega pomnil­ nika, kar predstavlja osnovni problem uporabe te metode. To je tudi pomemben razlog, zaradi katerega se uporabniki raje odločajo za upora­ bo drugih metod, kot na primer revidirane me­ tode simpleksov, ki so sicer bolj zapletene, vendar pa so manjši porabniki pomnilnika. V tem prispevku opišemo, kako je možno postor pek simpleksov modificirati ter s tem zmanjša­ ti zahteve po pomnilniku samo na prostor, ki ga potrebuje vhodna matrika neenačb. Pri tem podajamo metodo simpleksov le toliko, kolikor je potrebno za spremljanje razvoja postopka re­ duciranja simpleksne tabele, podroben opis teo- ret-.čnlh osnov te metode pa je opisan na prl- n^-.r v I 2] in |'3| . 2.1. Definicija linearnega programa Splošni problem linearnega programiranja za minimum namenske funkcije definiramo v mate­ matični obliki takole: dol.očiti je treba vred­ nosti spremenljivk x,,...,x , ki zadoščajo po­ gojem nenegativnosti X. >^ O in linearnim pogojem (i=l,...,s) ^l^^l * + ^is^^s 1 '=1 ml 1 ms s — m tako, da ima namenska funkcija c^x^ +,... + c^Xg minimum. Vsi koeficienti so realna števila. Zgornji zapis linearnega programa ni uporaben za numerično reševanje, ker nastopajo v obliki neenačb. Take pogoje spremenimo v enačbe s .privzemom dopolnilnih spremenljivk. Če odšte­ jemo spremenljivke ^^c+i <••• »''-+-, zaporedoma od levih strani neenačb, preidejo te neenačbe v enačbe. Dopolnilne spremenljivke upoštevamo tudi v namenski funkciji, kjer je 's+1 "s+m 0." Da bi omogočili začetek numeričnega reševanja, vrinemo v vsako pogojno enačbo še po eno umet­ no spremenljivko, torej k levi strani enačb prištejemo zaporedoma spremenljivke X , ...,x .2_,- Umetne spremenljivke upošte­ vamo tudi v namenski funkciji, kjer je "s+m+1 's+2m = M. Tako dopolnjen linearni procjram lahko zapišemo v matrični obliki takole: potrebno je izratunatl vektor x, ki zadošča ne- enačbl X >_ O In enačbi Ax " b tako, da Ima namenska funkcija cx minimum. l'rl tem BOI A n ^11 ••• '»in ^nl a mn b = ^n] C = [Cj . kjer je n •= 8+2m. Problem llnearnecja programiranja zapišemo lah­ ko v vektorski obliki tudi takole: potrebno je Izračunati vektor x, ki zadošča necnačbi X > O in enačbi 1 , n Xjp- + ... + x^p" = p tako, da ima namenska funkcija cx minimum. Pri tem soi 1 •u "ml s s+1 . , P . P . ^In a mn 8+m Vektorji p , p , pS+ra+1^ ... p" 8o vektorji m-dimenzionalnega vektorskega prostora V". Med njimi sestavlja zadnjih m vektorjev sistem m linearno neodvi­ snih vektorskih enot. To ao vektorji s+ra+1 ,, n p ° (1, o , 0), p" •= (O,. O, 1) Isto velja za matriko D, saj ima vsak vektor te matrike samo en element različen od nič in sicer (-1). Koeficienti vektorjev matrike D v namenski funkciji pa so enaki 0. Iz tega sledi, da jo struktura vektorjev, ki so v matrikah U in B ter njihovi koeficienti v namenski funkciji že vnaprej določeni s pred­ pisanimi oblikami pogojnih enačb In neonačb linearnega programa. Ce najdemo način, s katerim lahko na začetku reševanja linearnega programa ugotovimo, kate­ ri vektorji pridejo v sestavo začetne baze ter v ustreznem trenutku reSevanja, kateri vektor matrike D je potrebno transformlrati, potem lahko opustimo formiranje matrik D In D ter o- mejimo reševanje linearnega problema samo na matriko dimenzije m x s. Z raču/ialniSkega vi­ dika pomeni tako zmanjSanje dimenzije alm[)lek- sne tabele zadostno zmanjšanje računalniškega pomnilnika, potrebnega za izvajanje programov, ki rešujejo probleme linearnega programiranja z uporabo splošne metode simpleksov. V ta namen naj bo q vektor reda m, ki ima za svoje elemente simbole relacij v pogojnih enač­ bah in neenačbah obravnavanega linearnega pro­ grama (>, = , <), Ta vektor ima odločilno vlo­ go v modificiranem postopku, kajti s pomočjo tega vektorja lahko določimo vektorje matrik D in B ter njihove koeficiente v namenski funkciji. Za določitev začetne baze je potrebno ugotovi­ ti indekse baznih vektorjev ter njihovo koefi­ ciente v namenski funkciji. Zato definirajno naslednje vrednosti: g naj bo število, ki nam pove, koliko je po­ gojnih neonačb v linearnem programu (t ' tli gq naj bo Število pogojnih neenačb ali enačb oblike (>_) ali ( = ) i d naj bo število vhodnih in dopolnilnih spremenljivk v sestavi matrike A) to vred­ nost dobimo kot d = 3 + gl n je Število vseh spremenljivk matrike A) to vrednost dobimo kot n= s+gl +gq Z njimi moremo določiti indekse baznih vektor­ jev ter njihovo koeficiente v namenski funkci­ ji brez oblikovanja matrik D in B. Nadalje definirajmo še naslednja vektorja re­ da m: 2.2. Določitev začetne baze Dogovorimo se, da začetno bazo vektorskega prostora V"" določimo iz vektorjev umetnih spremenljivk ter vektorjev dopolnilnih spre­ menljivk, ki so vektorske enote. TI vektorji torej sestavljajo bazno matriko B, ostali vek­ torji dopolnilnih spremenljivk pa naj sestav­ ljajo matriko, ki jo označimo z D. Potem lahko matriko A napišemo kot; F, D, [;.| (1) Struktura vektorjev bazne matrike B je znana, saj je sestavljena iz vektorskih enot. Koefi­ cienti baznih vektorjev v namenski funkciji so ravno tako znani in sicer so enaki M (kjer je M primerno velika vrednost) za umetno spremen­ ljivke in O za dopolnilne spremenljivke. C , ki vsebuje koeficiente baznih vektorjev v namenski funkciji in V , ki Ima za elemente Indekse baznih vektor­ jev. Postopek kreiranja začetne baze je takle; A) Izračunajo se vrednosti gl, gq, d in n. B) Glede na vrednost elementa q,, 1 = l,...,m, se Izračuna indeks i-tega baznega vektorja In njegov koeficient v namenski funkciji z naslednjim algoritmom; 1) i = 1 2) q. ima vrednost (>^) ) potem je m = gq-i gl = gl-1 VT •= n-gq 3) q. Ima vrednost (O> potem je gl - gl-1 ..B d-gl O 4) g. Ima vrednost (••) j potem Je gq = gq-l ..B =? n-gq M 5) 1 " 1+1 6) Če je 1 < m, se postopek nadaljuje na točki 2). " . S takim postopkom kreiranja začetne baze ell" miniramo oblikovanje matrike B, kajti vse zna­ čilnosti te matrike so dosegljive z uporabo vektorjev c^ in vB. Razlika med prvotno in novo vrednostjo namen­ ske funkcije^^je tem večja, čim večja je dife­ renca z. - o?. Ker Selimo to razliko povečati, da dobimo čim boljSo rtovo možno reSitev, uve­ demo v novo bazo tisti vektor pi , ki mu ustre­ za največja pozitivna diferenca z. - c^. Vze­ mimo, da ustreza vektorju p'' največja diferen­ ca 'y^' kjer °k :)e C3 *j max j -'] '?) > 0 • °'' in j (2) l,...,s. Ce nobena od diferenc ni'pozitivna, obstoječe reSitve ni mogoče več izboljSati, zato je to že optimalna reSitev. 2.4. Zamenjava baze k V bazo uvedemo tisti vektor p , pri katerem ima izraz (2) največjo vrednost. Iz baze pa odstranimo vektor p"^, ki ga določimo tako, da vsako komponento p^ delimo s homologno kompo­ nento vektorja pl', pri tem pa uppStevamo samo pozitivne komponente vektorja pJ^, najmanjSi od teh ulomkov določa vektor p^^i ' 2.3. Izboljšanje možne reSitve V Izrazu (1) je A matrika dimenzije m x n. '• Vendar zaradi zgoraj prikazanega postopka eli­ minacije matrike B ter zaradi postopka elimi­ nacije matrike D, katerega opis je podan v naslednjem, velja, da je A matrika dimenzije m X s, kar označimo * A^^ „• Kljub temu pa mo­ ra matrika A ohraniti vse značilnosti celot- : ne simpleksne tabele, potrebne za reševanje i linearnega programa. V ta namen definlrajmo naslednja vektorjai A C naj bo vektor reda s> ki ima za svoje ele­ mente koeficiente vektorjev matrike A^ v namenski funkciji, A V pa naj bo vektor reda s; ki ima za svoje elemente indekse vektorjev matrike A_ . m,s Iz prvotne baze dobimo novo bazo tako, da kak njen vektor zamenjamo s kakim drugim vektor­ jem, ki ga fie ni v bazi. 6 = min m, s *lk 'rk kjer a.. > O, za 1 <^ i <_ m. Ce noben koeficient a., ni večji od O, je re­ Sitev neomejena. . Vrstico (m+l) vpeljemo tudi za. vektor p ,. ka­ terega koeficient je definiran s ,pj+i >• ^0 Vse koeficiente v slmpleksni tabeli (koefici­ enti vektorja pP in matrike A„., „) transfor- .- , m+l.s miramo po naslednjem transformacijskem zakonui . • - X • a) x; " 'rk rj 'rk kjer j = li,,. .,8 (3) Vzemimo, da odstranimo iz baze vektor p in ga zamenjamo z vektorjem p''. Za vsako možno rešitev ima namenska funkcija določeno vrednost. Pri prehodu iz prvotne v novo možno rešitev se vrednost namenske funk- ciJ6 izboljša. b) Definlrajmo sledeče količinet z "J ,B -1 °lj kjer z J pomeni vrednost vektorja p-", izraže­ nega z bajsnimi vektorji,' in BO °I Pi + kjer ZQ pomeni vrednost namenske funkcije, ki ustreza prvotni bazi. ''i' ^'j. kjei j - - "i " ^Ij • je i 1,..., " -• = IS *rk ^rk I" . • 'ik 'ik I ,m+l , i J* r in Uvedba vektorja p v bazo in odstranitev vek­ torja p"^ iz baze se Izvrši tako, da se v v^ A • • k ' '^ ' • vnese vrednost Iz v. (indeks vektorja p^), v B •• 'A • • c_ pa se vnese vrednost iz c^. (koeficient vek- • k . '^ • • , • • tprja p v namenski funkciji); P»votni vred- B B nostl komponent v in c se predhodno shranita v postavkah, ki ju označimo z vbr in cbr. To­ rej je; V matriko A vpeljemo (m+l) vrstico, katere koeficienti a^^^^j . so definirani- z . a_.,, ^ = Zj - Oj, J = i,...,s •m+l, j 'J -j' vbr cbr 2.5. Zamenjava vektorjev matrike A Matrika A ima na začetku numeričnega reSevanja isto strukturo kot matrika F, torej predstav­ lja matriko vektorjev vhodnih spremenljivk. Prav tako pa sta na začetku numeričnega reše- A A ' vanja v in c vektorja indeksov vhodnih spre­ menljivk oziroma njihovih koeficientov v na­ menski funkciji. V matriki A in v vektorjih A A v ter C se v dani iteraciji vrši zamenjava vektorjev, njihovih Indeksov ter koeficientov v namenski funkciji. Smisel zamenjave vektorjev matrike A je v na­ slednjem i 1) izkoriščanje prostora vektorja p v matriki A, saj postane vektor p'' po uvedbi v bazo vektorska enota; 2) ohranitev značilnosti vektorjev dopolnilnih spremenljivk v simpleksni tabeli tako, da ob določenih pogojih dane iteraclje uvede­ mo ustrezni dopolnilni vektor namesto vek­ torja p'^ v matriko Aj 3) ohranitev značilnosti vektorja p*^, ki ga odstranimo iz baze z uvedbo tega vektorja v matriko A na mesto vektorja p*^ zaradi njegove možne vrnitve v bazo. Izvršitev zamenjave vektorjev matrike A je odvisna od vektorjev q in c^. S pomočjo teh vektorjev lahko sklepamo, če je potrebno iz­ vršiti zamenjavo, poleg tega pa, kateri vek­ tor je treba v dani Iteraciji uvesti v matri­ ko A. Definirajmo vrednost-gl, ki naj pove, koliko pogojnih enačb je v prvih r enačbah ali nee- načbah linearnega programa. To vrednost potre­ bujemo za ugotavljanje Indeksa ustreznega do­ polnilnega vektorja, ki ga moramo uvesti v matriko A. Preden realiziramo postopek zamenjave vektor­ jev matrike A, moramo zaradi degenieraclje in zamenjave vektorjev shraniti značilnosti vek­ torjev matrike A, ki imajo po odstranitvi Iz baze možnost ponovne vrnitve v bazo. To so vektorji vhodnih in dopolnilnih spremenljivk. V ta namen vpeljemo vektor v reda d, ki ima za svoje elemente značilnosti teh vektorjev. Vrednost elementa v-i (j «" 1, .. ., d) mora zagotavljati hitro dgotavljanje mesta in strukture vektorja p3 v dani iteraciji. Postopek oblikovanja vektorja v: A) Za j = 1, .,., s velja Gre za vektorje vhodnih spremenljivk, ki sestavljajo matriko A na začetku numerič­ nega reševanja. pJ je vektor j-te vhodne spremenljivke, njegove komponente pa so shranjene v j-tem stolpcu matrike A. B) Za j = s + 1, ... , d 1. j = s , r = O 2. j = j + 1 3. r = r + 1 4. q ima vrednost (<^) ; potem je v^ = d + r taka vrednost elementa v. pomeni, da je p-^ vektorska enota, katere, r-ti element je enak 1 in se trenutno nahaja na r-tem mestu v bazi. 5. q ima vrednost (>_),• potem je 'j -(3 + r) negativna vrednost elementa v. pomeni, da je pj nebazni vektor dopolnilne spre­ menljivke X., njegov r-ti element pa je enak -1. 6. q ima vrednost (=)» Ce r < m,se postopek nadaljuje na točki 3, sicer pa se konča. 7. če je j < d, se postopek nadaljuje na toč­ ki 2. 8. konec postopka. Postopek zamenjave vektorjev matrike A: A) Vrednost q je (>_) in vrednost cbr (vred- n r nost C pred zamenjavo) je enaka M. Iz tega sledi, da je p"^ umetni vektor, zato ga po odstranitvi iz baze zanemarimo, ker nima nobene možnosti vrnitve v bazo, name­ sto trans formiranega vektorja p"^ uvedemo ustrezni dopolnilni vektor pd. Vsi elementi vektorja p° so enaki nič, ra­ zen r-tega elementa, ki je enak (-1). Koe­ ficient P_,^i pa je definiran s •m+1 c (vrednost pred zamenjavo). Za uvedbo p° v matriko A je potrebno v - shraniti vrednost vektorja p ; za ta na­ men definirajmo vektor p reda (m+1), kjer Pi = ^k • pri i = 1, m+1 uvesti vektor p v k-tl stolpec matrike A, kjer za i = 1, ..., m, i. ^ r ^ik = ° "rk - cbr "m+l.k za r Izračunati ql ugotoviti indeks vektorja p in njegov koeficient v namenski funkciji ter ažurl- ratl vektor v s tem, da A A j = v^ u = s + r - ql c^ = 0 A ^k = " V. = d+r B) Vrednost q je (=) in vrednost cbr (vred- n nost C pred zamenjavo) je enaka M. V tem primeru ne izvršimo nobene zamenjave, ker je p*^ umetni vektor, poleg tega pa ne obstoji v tej situaciji kak ustrezni dopol­ nilni vektor. Za uvedbo vektorja p v bazo je treba ažu- riratl vektor v s tem, da v^ = d+r C) Za vse druge možnosti moramo ugotoviti na- ; slednje I 1. vektor p"^ ja v sestavi matrike'Aj potem se zadovoljimo z ažuriranjem vektorja v a.tem, da ^(vbr) ""^'^ 2. izvršiti moramo zamenjavo vektorjev, tako da uvedemo namesto vektorja pl^ v matriko A vektor p^^ zaradi možnosti njegove po­ novne vrnitve v bazo. • Vektor p"^ kot bazni vektor ima strukturo vektorske enote, katere r-ta komponenta je enaka Ij koeficient Pj+j pa je enak niC. Za uvedbo p v matriko A je potrebnoi k - shraniti vrednost vektorja p , kjer Pl "^ ^ik ' P"^^ ^ " ^' '"' "'''^ - uvesti vektor p"^ v matriko A s tem, da postavimo °ik " ° ' pri 1 = 1, .../ m, 1 J« r «rk ' ^ %+l,k " ° - ugotoviti indeks vektorja p*^ in njegov koeficient v namenski funkciji ter ažu- rlrati vektor v s tem, da . A J = v^ A V. » vbr A C. « cbr ^(vbr) = " v. = d+r 2.6. Degeneracija število e oziroma p"^ določimo z naJmanjSim iz­ med ulomkov >t 0) . Če je teh naj­ manjših ulomkov več, dobimo novo možno rešitev, ki ima manj kot m pozitivnih komponent in je zato degenerirana, V primeru degeneraclje ni enollfino določen vektor p*^, ki ga odstranimo Iz baze. Denimo, da pridemo v linearnem programu do de­ generaclje in sicer zato, ker sta vsaj dva od navedenih ulomkov enaka. Vzemimo, da sta enaka ulomka "^/a^j^ in Xg/ag|^, Zato primerjamo druga dva ulomka a^l^^rk ^" *8l''^sk' ^^^ njima izbe­ remo tistega, ki je najmanjši. Če sta pa tudi ta dva ulomka enaka, Se ne pridemo do odločit­ ve in naprej primerjamo Se naslednja dva ulom­ ka a_2''''rk ^" *s2''''ak ^^"^ izberemo tistega:, ki je manjši. Če še ne pridemo do odločitve, nadaljujemo primerjanje, dokler ne pridemo do nje. Denimo, da ugotovimo s takim primerjanjem, da je ulomek y_/a_j^ manjši od ulomka Vo/a i.. Šte­ vilo r določa zato enolično vektor p'^, ki ga odstranimo iz baze p|. Zaradi postopka zamenjave vektorjev, je potreb­ no v primeru degeneraclje uporabiti vektor v, kjer element Vj (j •» l,...,d) rabi za ugotovi­ tev značilnosti (indeks, struktura in mesto) vektorja pii - indeks elementa Vj predstavlja Indeks vek­ torja pj, •' vrednost elementa Vj pa omogoča ugotoviti strukturo In pozicijo vektorja p-* s tem, da a) če v. > d J -t pomeni, da se vektor p-" nahaja v bazi, nje­ gov r-ti element je enak 1 in vrednost In­ deksa r dobimo z r o> Va - d b) če v. <^ B In Vj J* k pomeni, da je vektor p^ v sestavi matrike A, njegova struktura pa daje v^rti stolpec matrike A c) če v. < O pomeni, da Je p-" vektor dopolnilne spre menljlvke x., njegov r-ti element enak In vrednost Indeksa r dobimo z r (Vj + s) 3. POSTOPEK REŠEVANJA Z METODO SIMPLEKSOV Postopek reševanja linearnega programa z meto­ do slmpleksov obsega naslednje korake: 1) - Določitev začetne baze vektorskega prosto­ ra V« z vključitvijo postopka kreiranja začetne baze (podpoglavje 2.2.) A - Vstavitev začetnih vrednosti vektorjev c in v* 2) Vključitev postopka oblikovanja vektorja v (podpoglavje 2.5.) 3) Izračun naslednjih vrednosti) *j "5? ^IJ + ••• + =m «mj ' ^^ i - 1.....8 A a_., J = Zj - Cj n>+l.J j J B B i O m+1 11 mm •= c!* b, + ... + c^ b„ - p° , i 1 mm "^m+l k ~ 4) Določitev vektorja p oziroma indeksa ki z^ - c^ «• max (Zj - Cj) , za Zj - c. > O V primeru, da Je Zj^ - c^ <^ e, kjer Je c primerno majhno vnaprej predpisano pozitiv­ no število, je obstoječa možna rešitev opti­ malna in iteracljskl postopek se Iconča. 5) če so vse vrednosti a^^j^ < O, (i •> l,...,m), se Iteracljskl postopek konča in rešitev je neomejena. 6) Določitev vektorja p*^ oziroma indeksa r« X ; O < e o T— = min (x./a.. ) , za a.. > O rk l<^i