Matematika | Felsőoktatás » Csergőffy Tibor - Benders Dekompozíció általánosítása a Farkas tétel felhasználásával

Benders Dekompozcio altalanostasa a Farkas tetel felhasznalasaval } ffy Tibor Csergo V. eves matematikus hallgato Temavezet}o: Vizvari Bela docens ELTE TTK 1998. 2 Tartalomjegyzek 1 Bevezetes 1.1 1.2 1.3 1.4 Dekompozcios elv : : : : : : : : : : Farkas es Haar tetele, Farkas lemma : Benders dekompozcio : : : : : : : : Algoritmus : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 Tobbcelu optimalizalas 3 3 4 6 11 12 2.1 A ltalanostott Benders dekompozcio : : : : : : : : : : : : : : 12 3 Sok linearis valtozos feladat 3.1 3.2 3.3 3.4 3.5 3.6 Konvex halmazok : : : : : : : : : : : Projekcio : : : : : : : : : : : : : : : Halmazok elvalasztasa hiperskkal : : Sokfelteteles Farkas tetel : : : : : : : A ltalanostott Benders dekompozcio Algoritmus : : : : : : : : : : : : : : : 4 A ltalanostas konvex, zart kupra :

: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14 14 16 18 19 25 28 29 4.1 Farkas tetel konvex, zart kupra : : : : : : : : : : : : : : : : : 29 4.2 Dekompozcio konvex, zart kupbol vett linearis valtozokra : : 30 5 Gyakorlati megfontolasok Irodalomjegyzek 31 34 3 1 Bevezetes 1.1 Dekompozcios elv Az alkalmazott matematikaban szep szamban fordulnak el}o nagy meret}u feladatok. Ezen problemak szamtasi- es tarigenyuk miatt nehezen vagy egyaltalan nem kezelhet}ok. Ilyen es hasonlo nehezsegek kikuszobolesere talaltak ki a dekompozcios eljarasokat. Ezek lenyege, hogy egy nagyobb, esetenkent specialis alaku feladatot, tobb kisebb feladatra osztanak. Kulonbseg adodik a szeparalas modjaban A legismertebb az 1960-ban publikalt Dantzig-Wolfe dekompozcio 3]. Ennek lenyege abban foghato

meg, hogy a feladatot a feltetelek menten vagja fel. Ezzel szemben a dolgozat cmeben megjelolt Benders dekompozcio 1] a valtozok menten vagja ket, illetve iteratve tobb reszre. Ez az eljaras valojaban a Dantzig-Wolfe dekompozcio dualisa, viszont sokkal konnyebben altalanosthato nemlinearis felteteleket is tartalmazo feladatokra. A Benders dekompozcio altalanos kimondasaban a valtozok eleve ket reszre vannak osztva: egy linearisra es egy nemlinearisra. A dekompozcio lenyege abban van, hogy a feladat megoldasa soran sok hasonlo, azonos alaku, csak a feltetelekben modosulo feladatot kell megoldani. Szamtasi szempontbol a legm}uveletigenyesebb az un. f}ofeladat (angolul: master problem). Ez kepezi a feladat magjat Itt lenyegeben a nemlinearis valtozokat rogztjuk, es csak egy linearis programot oldunk meg. Valojaban a f}ofeladat - feltetelek elhagyasaval keletkez}o - relaxaltjait kell megoldani, majd

egy-egy linearis programozasi feladattal ellen}orizni, hogy a relaxalt feladat optimalis megoldasa megengedett megoldasa-e a f}ofeladatnak. Amenynyiben megengedett, akkor a rogztett nemlinearis valtozohoz, mely egy optimalis megoldas resze, egy masik linearis program segtsegevel megkeressuk az optimalis linearis valtozot. Amennyiben a relaxalt f}ofeladat megoldasa nem megengedett megoldas a f}ofeladatban, akkor megadja egy korabban megkonstrualt kup extremalis iranyat, mellyel egy uj feltetelt runk fel, amit beveszunk a feltetelek koze. Mivel veges sok extremalis irany van, ezert az algoritmus azert all le, mert a feladat nemkorlatos, vagy nincs megengedett megoldasa, vagy pedig megtalalta az optimumot. Az elmeleti hatterhez hozzatartozik, hogy a Benders dekompozcio semmi bonyolult eredmenyt nem hasznal fel, csak a Farkas tetel t. Bar a Benders dekompozcionak letezik altalanostasa, ezek nem a Farkas 4 tetel

altalanostasait hasznaljak, hanem a szamtasi sebesseg csokkentesere iranyulnak, kozelt}o eljarasokrol van szo. A legismertebb es a gyakorlatban valoban sokat hasznalt algoritmus a Generalized Benders decompsition eljaras 7], mely Georion tol szarmazik. Ismert egy sztochasztikus programozasbeli altalanostasa is: a Nested Benders decomposition 12] Ebben a munkaban a Farkas tetel altalanostasait felhasznalva kiterjesztjuk azon feladatok koret, melyekre hasznalhato a Benders dekompozcio. Tobbek kozott a tobbcelfuggvenyes esetre, vegtelen sok linearis valtozo esetere, illetve olyan esetre, amikor a linearis valtozorol nem csak azt tehetjuk fel, hogy a nemnegatv ortansban van, hanem, hogy egy tetsz}oleges konvex, zart kup eleme. 1.2 Farkas es Haar tetele, Farkas lemma Az operaciokutatas egyik talan legregibb, de minden bizonnyal a legismertebb tetele a Farkas Gyularol elnevezett tetel es lemma. Mar

1894-ben publikalta ezt az eredmenyt 4] Bar a tetel bizonytasa ekkor meg hianyos, a teljes bizonytas megtalalhato kes}obbi publikacioiban (5], 6]). Prekopa Andras reszletes torteneti attekintest ad a tetel fejl}odeser}ol 9]. A Farkas tetel homogen linearis egyenl}otlensegek megoldhatosagat vizsgalja: 1.1 Tetel: A kovetkez}ok ekvivalensek: aT x 5 0 kovetkezmenye Ax 5 0 -nak  (i) 9 = 0, hogy aT = T A : (ii) Bizonytas: (i) ) (ii) Tekintsuk a kovetkez}o feladatot: max aT x (P ) Ax 5 0 : Ennek a feladatnak letezik optimalis megoldasa: x = 0, mivel aT x 5 0 kovetkezik a feltetelb}ol. Ebb}ol az is kovetkezik, hogy a dualisnak is letezik optimalis megoldasa, azaz a kovetkez}o feladatnak: min 0T y AT y = a (D) y = 0: 5 Innen az  = y valasztas megfelel. (ii) ) (i) A feltetelb}ol aT x = T Ax 5 T 0 = 0:  A Haar tetel pedig az inhomogen linearis egyenl}otlensegek megoldhatosagat vizsgalja: 1.2 Tetel: A kovetkez}ok

ekvivalensek: aT x 5 b kovetkezmenye AT x 5 b-nek  (i) 9 = 0   = 0 , hogy 8x 2 Rn : aT x ; b = T (AT x ; b) ;  : (ii) 0 0 0 0 A Farkas lemma viszont egy alternatva tetel: 1.3 Tetel: Legyen D 2 Rm n matrix, d 2 Rm egy vektor A ket feladat kozul pontosan egynek van megoldasa:  (i) Dx = d  x = 0 (ii) yT D = 0T  yT d < 0 : Bizonytas: 1. lepes: Egyszerre nem oldhatok meg Indirekten tegyuk fel, hogy az (i)-nek letezik x megoldasa es (ii)-nek y . Kovetkezeskeppen: x = 0 yT Dx = (y| T{zD}) |{z} =0 yT Dx = yT d < 0 : =0T Ez viszont ellentmondas. 2. lepes: Tegyuk fel, hogy az (i)-nek nincs megoldasa, ekkor eleg bizonytani, hogy (ii)-nek van. Ehhez tekintsuk a max 0T x : Dx = d  x = 0 (P ) es min dT y : DT y = 0 (D) primal-dual feladatpart. A feltevesb}ol jon, hogy (P )-nek nem letezik megengedett megoldasa, viszont a (D)-nek letezik (y = 0). Ebb}ol az kovetkezik, hogy a dual nemkorlatos, azaz: 9 y : D T y = 0  dT y < 0 

6 ami azt jelenti, hogy (ii)-nek van megoldasa.  Hogy bizonytsuk a Farkas tetel es a Farkas lemma kozotti szoros kapcsolatot, megadjuk az el}obbi bizonytasat felhasznalva az utobbit. 1.1 Tetel bizonytasa: (i) ) (ii) Legyen D := AT es d := a Ekkor Ax 5 0 kovetkezmenye aT x 5 0 rhato a kovetkez}o alakban is: A(;x) = 0 kovetkezmenye aT (;x) = 0 : Ez eppen azt jelenti, hogy az 1:3 tetel (ii) alternatvaja nem teljesul, azaz (i) teljesul: 9x : AT x = a  x = 0 ahol  := x valasztassal igazoltuk ezt az iranyt. (ii) ) (i) Tudjuk, hogy fennall: 9 : AT  = a  =0: Ez nem mas, mint 1:3 tetel (i) alternatvaja, gy (ii) nem allhat fenn, tehat 8y : Ay = 0 kovetkezmenye aT y = 0 igaz.  1.3 Benders dekompozcio A kovetkez}o feladatot akarjuk megoldani: max cT x + f (y) Ax + F (y) x=0 y2S 5 b ahol x c 2 Rn y 2 S  Rk ahol S tetsz}oleges, b 2 Rm  F : S ! Rm  f : S ! R es F (S ) f (S ) korlatosak. (F ) 7 Tekintsuk

ehelyett a max z z ; cT x ; f (y) 5 0 Ax + F (y) 5 b x=0 y2S feladatot. Bevezetjuk a kovetkez}o jeloleseket: (   ) u  0 T C = u  A u ; cu0 = 0  u0 = 0  u = 0  n  o C0 = u  AT u = 0  u = 0  n  o P = u  AT u ; c = 0  u = 0 : 1.1 Lemma: 8(z y) 2 R  S -re ekvivalensek: 9 x : x = 0  Ax + F (y) 5 b  z ; f (y) ; cT x 5 0   u   8 0 2 C : u0 (z ; f (y)) + uT F (y) 5 uT b : u (1) (2) Bizonytas: Letezik x, ami kielegti az (1) rendszert. Ez pontosan akkor all fenn, ha letezik (v v0) kiegeszt}o valtozo: Ax + v = b ; F (y) ;cT x + v0 = ;z + f (y) (x v v0) = 0  0 T 1  Ax + v  A ;c B C T T D = @ E 0 A jelolessel (x  v  v0)D = ;cT x + v : 0 0T 1 u A Farkas tetel szerint pontosan akkor, ha D = 0 rendszernek kovetkezmenye a  b ; F (y) T  u  ;z + f (y) u0 = 0 : u0 8 Az el}obbit reszletesen kifejtve AT u ; cu0 = 0 u = 0 () u0 = 0 u  0 u 2C mg az utobbi: bT u = uT F (y) + u0(z ; f (y)), es ez az, amit akartunk. 

Vezessuk be a  o n G= (z y)  u0(z ; f (y)) + uT F (y) 5 uT b  z 2 R  y 2 S (u0 uT )T 2C jelolest. Ez alapjan a feladatot visszavezettuk a kovetkez}o ket feladat megoldasara: n  o max z  (z y) 2 G : (F}ofeladat) n  o Hasznalva a (z y) = arg max z  (z y) 2 G jelolest: max cT x Ax 5 b ; F (y) (2) x = 0: Mivel a (2) egy linearis programozasi feladat, ezert szamunkra csupan a f}ofeladat vizsgalata fontos. 1.4 Tetel: Tegyuk fel, hogy G 6= Ekkor a f}ofeladat pontosan akkor nemkorlatos, ha P = . Bizonytas: (() A felteves miatt letezik (z y) 2 G . Ha P = , C -ben csak olyan vektorok lehetnek, melyekre u0 nulla, mert C kup. Igy azt kapjuk (z y) 2 G -b}ol, hogy uT F (y) 5 uT b . Ebb}ol minden valos z-re a (z y) 2 G Ekkor a f}ofeladat nyilvan nem korlatos,  1mert  G nem fugg z-t}ol. ()) Ha viszont P 6= , akkor letezik u 2 C , ekkor z ; f (y) + uT F (y) 5 uT b , ami egy fels}o becslest ad z-re, mivel F (S ) f (S ) korlatosak, tehat a

f}ofeladat korlatos.  1.2 Lemma: Legyen a Q C , es legyen  o n G = (z y)  u0(z ; f (y)) + uT F (y) 5 uT b  z 2 R y 2 S : 0 (u0 uT )T 2Q 9 A f}ofeladat gyengebb feltetelekkel: n  o max z  (z y) 2 G  (MP ) 0 0 melynek (z y) optimalis megoldasa. Ekkor a (z y) a f}ofeladat optimalis megoldasa, akkor es csak akkor, ha  o n min (b ; F (y))T u  u 2 P = z ; f (y) :   Bizonytas: ()) (z y) optimalis, akkor 8 uu0 2 C eseten u0(z ; f (y)) 5 uT (b ; F (y)), azaz 8u 2 P 8u 2 C0 Nezzuk most a z ; f (y) 5 uT (b ; F (y))  0 5 uT (b ; F (y)) : eseten: eseten: min (bT ; F (y)T )u AT u = c u = 0 (P ) feladatot. Ez nyilvan korlatos, mivel P -t a ket feltetel denialja, es a korabbi tetel miatt a f}ofeladat korlatos, azaz a z ; f (y) 5 uT (b ; F (y)) jo korlatot ad a celfuggvenyre. Ebb}ol kovetkezik, hogy letezik optimalis megoldas, gy a dualnak is van optimalis megoldasa, es ezek egyenl}ok. A dual: max cT x Ax 5 b ; F (y)

(D) x = 0: Tegyuk fel, hogy az optimalis megoldasok: u  x . Ekkor a celfuggvenyertekek egyenl}osegeb}ol adodik: (bT ; F (y)T )u = cT x = z ; f (y) : (() Nezzuk a kovetkez}o problemat: min (bT ; F (y)T )u AT u = c u = 0: ( = z ; f (y) ) 10 T Mivel a feladat celfuggvenye korl  0atos, ezert u 2 C0-bol kovetkezik, hogy (b ; F (y)T )u = 0T , azaz minden u -ra teljesul, a G -t denialo egyenl}otlenseg, u  gy a fentiekkel egyutt 8 0 2 C -re is teljesul u (z ; f (y)) 5 uT (b ; F (y)). u Tehat (z y) 2 G , gy optimalis is. 0  11 1.4 Algoritmus Ezek utan a megoldasi algoritmus gy nez ki: BEGIN Q :=  z := +1  y2S (tetsz}oleges) WHILE true DO BEGIN w := min(b ; F (y))T u  (Az optimalitasi feltetel.) u2P ) THEN BEGIN IF w = z ; f (yn o x := arg max cT x j Ax 5 b ; F (y)  x = 0  STOP. (Az (x y) optimalis megoldas.) END ELSE BEGIN (Az optimalitasi kriterium nem teljesult.) IF w > ;1 THEN n BEGIN o u := arg min

(bT ; F (y)T )u j u 2 P  Q := Q  f(1 u)g  END ELSE BEGIN u 2 Ext(P )  (Ext( v 2 (C0 extremalis iranyai)  Q := Q  f(1 u) (0 v) g  P END END G (Q) := ) a extremalis pontjainak halmaza.)1 P n o (z y) j y 2 S  u0(z ; f (y)) + uT F (y) 5 uT b  (u0 uT )T IF G (Q) = THEN STOP. ELSE (z y) := arg max f z j END END. 2Q (Nincs megengedett megoldas.) (z y) 2 G (Q) g 2 (Vege a WHILE ciklusnak. ) A szimplex modszer leallasakor szolgaltatott u extremalis pont es v extremalis irany veend}o be a Q-ba. 2 A relax alt feladat optimalis megoldasa. Ez a WHILE ciklus elejere kerul, ahol ellen}orizzuk, hogy a f}ofeladatnak megengedett megoldasa-e? 1 12 1.5 Tetel: A fenti algoritmus veges lepesben vegeter Bizonytas: Vegyuk eszre, hogy az eljaras soran a Q-t mindig a C0 extremalis iranyaval es/vagy P extremalis pontjaval b}ovtettuk. Mivel ezekb}ol vegessok van, gy az eljaras veges.  2 Tobbcelu optimalizalas 2.1 A

ltalanostott Benders dekompozcio Legyen S egy tetsz}oleges nemures halmaz. Legyenek p m n pozitv egeszek es f : S ! Rp es g : S ! Rm fuggvenyek, tovabba Cp n  Am n  bm 1 matrixok. A kovetkez}o tobbcelu optimalizalasi feladatra fogunk Benders dekompozciot keszteni: max C x + f (y) Ax + g(y) 5 b (1) x = 0 y 2 S : Legyen z 2 Rp a celfuggveny vektorvaltozoja. Ekkor a feladat a kovetkez}o alakra hozhato: max z z ; C x ; f (y) 5 0 Ax + g(y) 5 b x = 0 y 2 S:    Legyen G olyan (z y) parok halmaza, melyekhez letezik megengedett x megoldas, azaz  n o G = (z y)  z 2 Rp  y 2 S  9x 2 Rn+ : z ; f (y) 5 C x  Ax 5 b ; g (y) : Mint az egycelfuggvenyes dekompozcional itt is fontos szerepe lesz a   s    T T  C= t  ; C s + A t = 0 s = 0 t = 0 kupnak. 13 2.1 Tetel: A (z y) par akkor es csak akkor eleme a G halmaznak, ha a (;z + f (y))T s + (b ; g(y))T t = 0 s egyenl}oseg fenall minden t 2 C -re. Bizonytas: A (z

y) par pontosan akkor eleme a G halmaznak, ha leteznek x 2 Rn+ , u 2 Rm+ es w 2 Rp+ vektorok, melyek kielegtik a -z + f(y) = -Cx + w b { g(y) = Ax + u egyenl}osegeket. Ez ekvivalens a kovetkez}o matrixegyenl}oseggel: 0 1  ;z + f (y)   ;C 0 I  B x C p b ; g(y) = A Im 0 @ wu A  (2) ahol Im es Ip az m  m-es illetve p  p-es egysegmatrixok. A Farkas tetel alapjan: (;z + f (y)T s + (b ; g(y))T t = 0 (3) kovetkezmenye a kovetkez}o rendszernek: ;C T s + AT t = 0 Imt = 0 (4) Ip s = 0 mivel (3) a (2) egyenlet bal oldalan allo vektor, mg (2) jobboldalan allo matrix eppen a (4) rendszert adja.  2.2 Tetel: Tegyuk fel, hogy az (1) feladatnak van legalabb egy megoldasa Legyen k(1 5 k 5 p) egy tetsz}oleges index es  s  Ck = 2 C  sk > 0 : t Ha Ck = akkor a feladat k-dik celfuggvenye nem korlatos. Bizonytas: A feltetelekb}ol kovetkezik, hogy C minden elemere sk = 0. A 2:1 tetel miatt minden (z y) 2 G -re igaz: s T T 8 t 2 C : (;z + f

(y)) s + (b ; g(y)) t = 0 : 14 Legyen  > 0 tetsz}oleges pozitv valos szam. Ekkor (z + ek  y) 2 G , ahol ek a k-dik egysegvektort jeloli, mivel s T T T T 8 t 2 C : (;z;ek +f (y)) s+(b;g(y)) t = (;z+f (y)) s+(b;g(y)) t = 0 gy a 2:1 tetel miatt (z + ek  y) 2 G , amib}ol az alltas kovetkezik.  3 Sok linearis valtozos feladat 3.1 Konvex halmazok 3.1 Caratheodory tetel: Legyen U Rn U 6= : 8u 2 convU el}oallthato n + 1-nel nem tobb U -beli vektor konvex kombinaciojakent. Bizonytas: m m X X u 2 convU ) u = iui  i = 1  i = 0  ui 2 U  8i = 1 : : :  m: i=1 i=1 Legyen m > n + 1 es 8i = 1 : : :  m -re i > 0. Vegyuk az ui 2 Rn+1  ui = (ui  1) 8i = 1 : : : m (1) vektorokat. Mivel m > n + 1 , fuigmi=1 linearisan osszefugg}ok, ezt kifejtve: m m X X 9i  i = 1 : : :  m : ji j 6= 0  iui = 0  i=1 vagyis Innet m X i=1 iui = m X m X i=1 iui ; t m X i = 0 : m X iui = (i ; ti)ui : i=1 i=1 |i=1{z }

i=1 =0 m m X X Ha t eleg kicsi, akkor i ; ti = 0 es jij 6= 0  i = 0 ) 9i > 0. i=1 i=1 Jelolje i : t :=  s = min i >0 i s u= m X i ui = 0  i=1 15 Innen i ; ti = 0  8i = 1 : : :  m, mikozben s ; ts = 0, gy m X u= (i ; ti)ui  i=1i=s 6 azaz az u-t el}oallto vektorok szama eggyel csokkent. Ez a csokkentes mindaddig folytathato az el}obbiek szerint, amg az (1) vektorrendszer linearis osszefugg}osege meg nem sz}unik, azaz az el}oallto komponensek szama legfeljebb n + 1.  3.2 Tetel: Ha U Rn kompakt, akkor convU is kompakt Bizonytas: Azt kell belatnunk, hogy convU korlatos es zart. U korlatossaga azt jelenti, hogy letezik R > 0 ugy, hogy  n o U B(0 R) = u 2 Rn  kuk 5 R : B (0 R) konvex, ezert convU B (0 R), hiszen convU a legsz}ukebb U -t tartalmazo konvex halmaz, azaz convU is korlatos. Legyen u a convU torlodasi pontja. Ekkor leteznek uk 2 convU  k = 1 2 : : : vektorok, melyekre klim uk = u.

Caratheodory tetele alapjan leteznek uik 2 U es ik = 0  i = 1 : : : n + 1 ugy, hogy nX +1 uk = ik uik : !1 i=1 A kovetkez}okben az un. atlos eljarast alkalmazzuk U korlatos, gy alkalmas R-re kuik k 5 R es 0 5 ik 5 1, gy fu1k g  f1k g-b}ol kivalaszthatok konvergens fu1k1 g es f1k1 g reszsorozatok, melyekre u1k1 k;! u~1 2 U  1k1 k;! 1  1 1 !1 !1 az fu2k1 g  f2k1 g-b}ol kivalaszthato fu2k2 g  f2k2 g konvergens reszsorozatok, hogy u2k2 k;! u~2 2 U  2k2 k;! 2  2 !1 2 !1 es gy folytatva, vegul funkn+1 g  fnkn+1g-b}ol kivalaszthatok funkn+1+1 g  fnkn+1+1 g konvergens reszsorozatok, hogy unkn+1+1 k ;! u~n+1 2 U  nkn+1+1 k ;! n+1 : n+1 !1 n+1 !1 16 Nyilvan a fkn+1g indexhalmazhoz tartozo elemekre uikn+1 kn;! u~i 2 U  ikn+1 kn;! n+1  i = 1 : : : n + 1  +1 +1 !1 gy ukn = +1 es !1 nX +1 i=1 ikn+1 uikn+1 1= nX +1 i=1 ;! kn+1 ikn+1 Ezzel belattuk, hogy convU zart. nX +1 !1 i=1 ;! kn+1 !1 iu~i =

u 2 convU nX +1 i=1 i :  3.2 Projekcio 3.1 Dencio: Legyen U Rn es u 2 Rn Az u pont vetulete az U halmazra az u-hoz legkozelebbi U -beli pont, azaz p = ProjU (u) 2 U , ha ku ; pk = inf ku ; vk =  : v U 2 3.3 Tetel: Legyen U Rn zart, konvex halmaz Akkor 8u 2 Rn-re p = ProjU (u) letezik es egyertelmu. Bizonytas: Ha u 2 U , akkor nyilvanvaloan ProjU (u) = u. Legyen u 62 U Az inmum dencioja szerint letezik egy fuk g U sorozat ugy, hogy lim kuk ; uk =  : k !1 Legyen >  tetsz}oleges szam. Ekkor egy N kuszobindext}ol minden k-ra kuk ; uk 5 . Innen latjuk, hogy az fuk gk=N U O (u) kompakt halmaz resze. A sorozatbol kivalaszthato egy konvergens reszsorozat: lim uki = p 2 U : i 1 !1 A norma folytonossaga miatt kp ; uk =  . Tegyuk fel, hogy a projekcio nem egyertelm}u, azaz 9p1  p2 2 U p1 6= p2 es kp1 ; uk = kp2 ; uk =  : 17 U konvex, ezert z = 12 p1 + 21 p2 2 U es 1 1 1 1 kz ; uk = k (p1 ; u) + (p2 ; u)k < kp1 ; uk + kp2 ;

uk =   2 2 2 2 ami ellentmond  denciojanak. A fenti egyenl}otlenseg azert szigoru, mert a normara vonatkozo haromszogegyenl}otlenseg miatt egyenl}oseg akkor es csak akkor all fenn, ha a mi esetunkben 12 (p1 ; u) = r 12 (p2 ; u), valamely r 2 R szamra fennall. De ez p1 6= p2 es kp1 ; uk = kp2 ; uk miatt nem lehet  3.4 Tetel: Legyen az U 2 Rn konvex, zart halmaz Pontosan akkor igaz, hogy p = ProjU (u) , ha 8v 2 U : hu ; p v ; pi 5 0 : Bizonytas: Szuksegesseg. Legyen p = ProjU (u) es v 2 U tetsz}oleges Tekintsuk a z = v + (1 ; )p pontot. Mivel U konvex, ezert z 2 U 8 2 0 1]-re. kz ; uk2 = k(v ; p)+(p ; u)k2 = 2 kv ; pk2 +2hv ; p p ; ui + kp ; uk2 : Felhasznalva, hogy p = ProjU (u) , dencio alapjan: kp ; uk 5 kz ; uk . Ezt es a fenti egyenl}oseget osszevetve azt kapjuk, hogy 2kv ; pk2 + 2hv ; p p ; ui = 0 azaz 8 2 0 1]  1 kv ; pk2 8 2 (0 1] : 2  ! 0 eseten a tetelbeli egyenl}otlenseget kapjuk. Elegsegesseg. A

tetelbeli feltetel miatt minden v 2 U -ra hu ; p v ; pi 5 kv;uk2 = k(v;p)+(p;u)k2 = kv;pk2;2hv;p u;pi+kp;uk2 = kp;uk2  azaz kp ; uk a minimalis tavolsag az u es U pontjai kozott.  18 3.3 Halmazok elvalasztasa hiperskkal 3.2 Dencio: Legyen U V Rn. A hc ui =  hipersk c = 6 0 normalvektorral tenylegesen elvalasztja U es V halmazokat, ha 2 hc ui =  8u 2 U emellett 9u0 2 U  v0 2 V 3.3 Dencio: Legyen U V es hc vi 5  8v 2 V   melyre hc v0i < hc u0i : Rn. A hc ui =  hipersk c = 6 0 normalvektorral szigoruan elvalasztja U es V halmazokat, ha 2 sup hc vi <  < uinfU hc ui  8u 2 U  8v 2 V : v2V 2 3.5 Tetel: Legyen U Rn konvex, zart halmaz, U 6= Legyen tovabba v 62 U tetsz}oleges Rn-beli vektor. Letezik c 6= 0 vektor es  2 R szam, hogy hc xi =  hipersk szigoruan elvalasztja v-t U -tol. Bizonytas: A 3.3 tetel alapjan legyen p = ProjU (v) 2 U es a 34 tetel alapjan hp ; v u ; pi = 0 8u 2 U :

Legyen c = p ; v . Ekkor c 6= 0 es hc u ; vi = hp ; v u ; pi + kck2 = kck2 8u 2 U : () {z } | {z } | =0 >0 Legyen  = hc vi + 12 kck2 . A fenti egyenl}otlenseget gyelembe veve hc xi =  szigoruan elvalasztja v-t es U -t.  3.6 Tetel: Legyen U Rn konvex, zart, V Rn konvex, kompakt halmaz es tegyuk fel, hogy U V = . Akkor U es V szigoruan elvalaszthato Bizonytas: Legyen X = U ; V . Legyen x az X halmaz egy torlodasi pontja. Akkor letezik fxk g X , melyre xk ! x xk 2 X ) 9uk 2 U  vk 2 V : xk = uk ; vk : 19 V kompakt, ezert fvk g-bol kivalaszthato konvergens fvkm g reszsorozat, azaz vkm ! v 2 V . Akkor U zartsaga miatt ukm = xkm + vkm ! x + v = u 2 U Ezert x = u ; v  u 2 U  v 2 V , azaz X = U ; V zart halmaz. A U V = feltetel miatt 0 62 X = X . A 35 tetelben lattuk, hogy 0 es X szigoruan elvalaszthatoak a hc xi =  hiperskkal, ahol c = ProjX (0) es hc xi = kck2  8x 2 X  illetve () alapjan hc ui = hc vi + kck2 8u 2 U

 v 2 V : Innen inf hc ui = sup hc vi + kck2 8u 2 U  v 2 V : u U 2 v2V Legyen  egy tetsz}oleges eleme a supv V hc vi infu U hc ui intervallum nak. Akkor a hc xi =  hipersk szigoruan elvalasztja U -t es V -t 2 2 3.4 Sokfelteteles Farkas tetel 3.1 Lemma : Legyen B Rn kompakt halmaz. Letezik s 2 Rn vektor, hogy T max b s < 0 ekvivalens a 0 62 convB alltassal. b B Bizonytas: ()) Amennyiben a 0 2 convB , akkor a 0 el}oall veges sok B beli vektor konvex linearis kombinaciojakent. Mivel minden B -beli vektorra a bT s < 0 a feltetelezes miatt igaz, ezert linearis kombinaciojukra, a 0 vektorra is, tehat 0 = 0T s < 0 is igaz. Ez ellentmondas 2 (() Mivel B kompakt, ezert 3.2 tetel miatt convB is kompakt Igy 35 tetel miatt szigoruan elvalaszthato 0-tol egy hc xi =  hiperskkal. Reszletesen ez azt jelenti, hogy hc bi <  , ha b 2 convB  (a) illetve hc 0i >  : (b) A (b) sorbol azt kapjuk, hogy  negatv, azaz az (a) sor azt

mondja, hogy minden convB -beli b vektorra a cT b < 0 . Ez azt jelenti, hogy s = c valasztas megfelel.  20 A kovetkez}o tetel bizonytassal egyutt megtalalhato 10]-ben. 3.7 Tetel: Legyenek A B Rn kompakt halmazok Tegyuk fel, hogy letezik olyan s 2 Rn , hogy max bT s < 0 : (1) b B 2 Ekkor a kovetkez}o ket alltas ekvivalens: max aT x = 0  kovetkezmenye max bT x 5 0 -nak  a A b B (i) 9 > > > > > t0 X > i i i i 9a 2 A es 9 2 R = 0 i = 1 : : :  t0 = 1 > > > i=1 = > 9bj 2 B es 9j 2 R j = 0 j = 1 : : :  t hogy > > > > > t0 t X X > i ai + j j >  b = 0: >  i=1 j =1 (ii) 2 9t0 2 Z : 2 1 5 t0 5 n + 1 es 9t 2 Z : 0 5 t 5 n Bizonytas: (i) ) (ii) Letezik egy s 2 Rn, hogy max bT s < 0. A lemma b B alapjan 0 62 convB . A conv B a korabbi lemmak alapjan kompakt es konvex 2 halmaz. Ehhez a conv B halmazhoz konstrualunk egy  n o Z = z 2 Rn  z = ; b b 2 convB  = 0

(2) halmazt, amely termeszetesen konvex, s}ot belatjuk, hogy zart is. 3.1 A lltas: A fenti Z halmaz zart Bizonytas: Minden z 2 Z -hez letezik b 2 convB , hogy z = ; b valamilyen nemnegatv  -ra. Ha z es b kozott fennall a fenti kapcsolat, akkor nevezzuk }oket par nak. Legyen fzigi=1 Z egy tetsz}oleges sorozat, mely tart z-hez Be kell latnunk, hogy z Z -ben van. A fzig sorozathoz tatozik egy fbig convB sorozat, amelyre igaz, hogy minden i 2 f1 2 : : :g-re zi es bi part alkotnak. A convB kompakt, gy letezik fbik g reszsorozat, mely konvergens es egy b vektorhoz tart. A lltom, hogy z es b part alkotnak Tegyuk fel, hogy nem 1 21 Ekkor letezik a z-nek es az e = fx 2 Rn j x = b  2 Rg egyenesnek diszjunkt kornyezeteik ( Uz, ill. Ue ) Az Ue valojaban egy olyan korkup, melynek tengelye b iranyu. Leteznek az N (Uz) es N (Ue ) kuszobindexek, hogy 8k = N (Uz ) : zik 2 Uz  (3a) 8k = N (Ue ) : bik 2 Ue : (3b) Legyen N = max fN (Uz) N (Ue

)g. Ekkor (3a) miatt minden N -nel nagyobb k-ra zik 2 Uz es zik = k bik . Illetve (3b) miatt bik 2 Ue , de ekkor az Ue kupnak eleme k bik is. Ami ellentmondas, hisz zik 2 Uz Ue  3.2 A lltas: convA Z nem ures Bizonytas: Tegyuk fel indirekten, hogy a metszet ures. A convA-rol tudjuk, hogy konvex es kompakt. A szeparacios tetel miatt letezik egy convA-t es Z -t szigoruan elvalaszto hipersk fx 2 Rn j cT x =  c 6= 0g, azaz 8a 2 convA cT a <   cT z >  : (4a) max cT a 5 a max cT a < 0 : a A convA (5) : 8z 2 Z : (4b) A z = 0 2 Z valasztassal (4b)-b}ol azt kapjuk, hogy  < 0. Igy (4a) alapjan minden a 2 convA-ra cT a < 0. Tovabba 2 2 Masreszr}ol cT z = ; cT b es (4b) alapjan fennall: cT z = ; cT b >   8b 2 convB  8 = 0 : (6) Ha cT b > 0 valamilyen b 2 B -re, akkor eleg nagy  -t valasztva cT z = ; cb 5  , ami ellentmond (6)-nak. Tehat azt kaptuk, hogy minden b 2 B re cT b 5 0 igaz Ez azt jelenti, hogy max

cT b 5 0 : (7) b B 2 (7)-b}ol felhasznalva (i)-t, azt kapjuk, hogy Ta = 0 max c a A 2 22 ami ellentmond (5)-nek.  Letezik egy a0 eleme convA-nak, mely benne van a Z kupban is, ami azt jelenti, hogy letezik egy  0 = 0 es b0 2 convB , hogy a0 = ; 0b0: (8) A Caratheodory tetel miatt b0 el}oall legfeljebb n + 1 B -beli pont konvex kombinaciojakent: 9bj 2 B  9#j 2 0 1]  b0 = nX +1 j =1 j = 1 : : : n + 1 : nX +1 #j bj  ahol j =1 #j = 1: (9) Mivel B Rn, ezert ami el}oall n + 1 darab B -beli vektor konvex kombinaciojakent, az el}oall n darab B -beli vektor nemnegatv linearis kombinaciojakent is. (8)-bol a kovetkez}o rendszert kapjuk: t X ;a0 = j bj  j =1 j = 0  j = 1 : : : t  (10) 0 5 t 5 n: Ha az a0 2 convA helyere berjuk az n + 1 darab A-beli vektoros konvex linearis kombinaciokent valo el}oalltasat, akkor eppen (ii)-t kapjuk. (ii) ) (i) Ez az irany nagyon egyszer}u. Tudjuk: t0 Xt j j X  b = ; i ai  (11) j =1

i=1 innen, ha max bT x 5 0, akkor b B 2 t X t0 X j j T i (ai )T x : 0 =  (b ) x = ; j =1 i=1 (12) 23 Ha max aT x < 0, akkor (12) jobboldala pozitv. Ez viszont ellentmondas  a A 2 Az fentiekben megismert Farkas tetel egy lenyegesen gyengebb valtozatat hasznaljuk fel. Pontosabban azt a specialis esetet, amikor A = fag Rn egyelem}u halmaz. Ekkor a tetel gy szol: 3.7 Tetel: Legyen a 2 Rn vektor es B Rn kompakt halmaz Tegyuk fel, hogy letezik olyan s 2 Rn , hogy min bT s > 0 : (1) b B 2 Ekkor a ket alltas ekvivalens: bT x = 0 -nak  aT x = 0  kovetkezmenye min b B 2 9 > > > > j j j = 9b 2 B es 9 2 R  = 0 j = 1 : : :  t hogy > > > Xt j j > >  b = a:  j =1 9t 2 Z : (i) 0 5 t 5 n (ii) A 3.1 lemma mutatja, hogy az (1) feltetel nagyon er}os, hiszen ekvivalens azzal, hogy 0 62 convB . A 38 tetel egy gyengebb feltetel mellett bizonyt ekvivalenciat. 3.8 Tetel: A 3:7 tetel jeloleseit alkalmazva (i)

es (ii)ekvivalensek, felteve: 0 0-nak letezik n ; 1 dimenzios kornyezete convB -ben, vagy 0 62 convB: (1 ) Bizonytas: (ii) ) (i) Ehhez az iranyhoz nem kell a feltetel, tehat nem kell 0 ujra belatnunk. (i) ) (ii) Ha a 0 vektor teljesti (1 )-et, akkor harom eset lehetseges. 1. eset: 0 62 convB Ezt az esetet targyalja a 3:7 tetel 2. eset: 0 2 int(convB ) Ez esetben a 3:7 tetelben denialt Z halmaz eppen az Rn . A tetel bizonytasa azon mulik, hogy Z fag nemures, ami itt trivialisan teljesul. 0 0 24 3. eset: 0 2 @ (convB ) es teljesti (1 )-et, akkor Z egy zart felter lesz, melynek hatarololapja eppen az (1 )-ben megkovetelt kornyezetet tartalmazo hipersk. A bizonytas innen ugyanugy tortenik, mint a 3.7 tetelben, hasznalhato a szetvalasztasi tetel Z -re es convA-ra.  A kovetkez}o pelda azt mutatja meg, hogy a 3.8 tetelben kimondott (1 ) feltetelen nem lehet sokat javtani. 0 0 0 1. kep: A pelda 3.1 Pelda: Legyen

a 38 tetel jeloleseit alkalmazva  n o n = 2  B = x 2 R2  kx ; (0 1)k 5 1 A = f(1 0)g : Mivel A egyelem}u ezert A = convA . Mivel B konvex, kompakt, ezert B = convB . Megmutatjuk, hogy a 37 tetel (i) alltasat a pelda teljesti, de a (ii) megsem igaz ra. Lenyegeben csak egyetlen x vektor a (0 ;1) (es pozitv konstansszorosai) elegti ki a Tx 5 0 b (i1) max b B 2 feltetelt. Ebb}ol kovetkezik, hogy max aT x = 0  a A (i2) 2 azaz (1 0)  (0 ;1) skalaris szorzat nempozitv. Tehat (0 ;1) kielegti (i)-et (ii) azt mondja ki, hogy Xt 9t 5 n j 2 R  bj 2 B j = 1 : : :  t : ;(1 0) = j bj (ii) j =1 25 Szorozzuk be mindket oldalt skalarisan (0 ;1)-gyel. A baloldal erteke 0 lesz, mg a jobboldal (i) miatt nemnegatv. Egyetlen B -beli vektorra lehet a skalarszorzat 0, ez pedig a (0 0) vektor. Tehat (ii) jobboldali szummajaban minden j -re bj = 0 , azaz a szumma maga is a 0 vektor, viszont a baloldalon nem az all. Ez azt jelenti, hogy

(ii) nem lehet igaz Ebben a peldaban egyebkent a Z halmaz azon vektorokbol allo felter, melyek masodik koordinatajukban negatvak, tovabba a (0 0) vektor. Jol latszik, hogy Z nem zart.  3.5 A ltalanostott Benders dekompozcio 3.7 tetel segtsegevel erre a feladatra is hasznalhato a dekompozcio: max cT x + f (y) K x + F (y) 5 b x 2 X y2S  n o X = x 2 R  x-nek csak veges sok komponense pozitv : (2) +  Tovabba c 2 R  S Rk tetsz}oleges, F : S ! Rm  f : S ! R b 2 Rm  K 2 Rm  , ahol legfeljebb kontinuum szamossag es F (S ) f (S )  korlatosak. Vegyuk eszre, hogy az X halmaz kup Kes}obb latjuk, hogy fel kell tennunk meg, hogy letezik u 2 Rm minden komponenseben pozitv vektor, melyre K T u > c . Hasonloan az eredeti Benders dekompozciohoz a C kup itt is fontos szerepet tolt be:  u    0 T C=  K u ; u0c = 0  u = 0  u0 = 0 : u Bevezetjuk a z celfuggvenyvaltozot, es ahogyan ezt korabban is tettuk

egy uj feltetelt: z ; cT x ; f (y) 5 0 . A f}ofeladat megfogalmazasahoz a kovetkez}o lemma szukseges: 3.2 Lemma: Minden (z y) 2 R  S parra ekvivalens a kovetkez}o ket alltas, felteve, hogy (K T  ;c) sorai Rm+1-ben kompakt halmazt alkotnak. 9x : x 2 X  K x + F (y) 5 b  z ; f (y) ; cT x 5 0  (a)  u   8 0 2 C : bT u = F (y)T u + u (z ; f (y)) : (b) u 0 26 Bizonytas: Ha letezik x, ami (a)-t kielegti, akkor letezik v v0 slack valtozo, hogy Kx + v = b ; F (y) T ;c x + v0 = ;z + f (y) (x v v0) = 0 : Ez az egyenl}osegrendszer felrhato matrixegyenl}osegkent: 0 1  T I m 0 ( vT  v0 xT ) B @ 0T 1 CA = ;bz;+Ff((yy)) : T | K {z ;c } =D A D 2 R m+1 , ezert alkalmazhato ra az altalanostott Farkas tetel. A matrixegyenl}oseg szerint a Farkas tetel (ii) alltasa igaz, tehat (i) is teljesul. Vegyuk eszre, hogy ez eppen lemmank (b) alltasa, ha D sorai az Rm+1ben kompakt halmazt alkotnak, de ez a feltetel miatt teljesul. Nem

szabad elfelejteni, hogy csak akkor volt jogos 3:7 tetelt alkalmazni, ha (1) feltetel teljesul: u u u m +1 90 < 2R : D > 0 , KT > c  u0 u0 u0 amit korabban fel is tettunk.   0 Ezen lemma alapjan felrhatjuk a f}ofeladatot: n  o max z  (z y) 2 G  ahol G =  n o (z y)  bT u = F (y)T u + u0(z ; f (y)) : (u0 uT )T 2C Ha az optimalis z y a kezunkben van, akkor az optimalis x-et ez a feladat talalja meg: max cT x K x 5 b ; F (y) x 2 X: 27 A 3.8 tetel segtsegevel b}ovebb feladatosztalyra is elvegezhet}o a dekompozcio, de nehezebb ellen}orizni az (1 ) feltetelt a D matrix soraibol alkotott halmaz konvex burkara. Vegyuk eszre, hogy az 1.4 tetel itt is ervenyes a n  o P = u  K T u = 0  u = 0 jelolessel. Nemcsak a tetelkimondas, hanem a bizonytas is szorol szora megegyezik Szuksegunk lesz meg az 1.2 lemma analogonjara is az algoritmushoz 3.3 Lemma: Legyen Q C , es legyen  o n G (Q) = (z y)  u0(z ; f (y))

+ uT F (y) 5 uT b  z 2 R  y 2 S : 0 (u0 uT )T 2Q A f}oproblema gyengebb feltetelekkel: n  o max z  (z y) 2 G (Q)  melynek (z y) optimalis megoldasa. Ekkor a (z y) a f}ofeladat optimalis megoldasa, akkor es csak akkor, ha  n o min (b ; F (y))T u  u 2 P = z ; f (y): () Bizonytas: ()) Feltesszuk, hogy (z y) , a relaxalt f}ofeladat optimalis megoldasa a f}ofeladatnak is megengedett, gy optimalis megoldasa. Ez azt jelenti, hogy minden C -beli vektorra fennall: u0(z ; f (y)) + uT F (y) 5 uT b . Ha u0 = 0 , akkor a kapott feltetel nem ad Z -re megkotest, ha pedig u0 > 0 , akkor az egyenl}otlenseg mindket oldala leoszthato u0-val. Amit kapunk az az uu0 2 P -vel felrt egyenl}otlenseg. Ennek kovetkezteben a G -t lero egyenl}otlensegrendszer ekvivalens a min uT (b ; F (y)) = z ; f (y) () u 2P rendszerrel. Ha itt az egyenl}otlenseg szigoru, az azt jelenti, hogy z novelhet}o anelkul, hogy a feltetelrendszer serulne. Ez azt jelenti,

hogy (z y) nem lehetett a relaxaltnak optimalis megoldasa, de meg a f}ofeladatnak sem. (() Eleg megmutatnunk, hogy (z y) 2 G . A masik irany bizonytasaban lattuk, hogy G feltetelrendszere ekvivalens ()-gal. (z y) teljesti ()-ot, gy ()-ot is.  28 3.6 Algoritmus Az algoritmus lefuttatasa el}ott eldontjuk, hogy P ures-e? Amennyiben nemures, lefuttatjuk az alabbi algoritmust. Az algoritmus alapotletet megtalaljuk 11]-ben Mivel vegtelen szamossag, ezert C -r}ol nem lehet alltani, hogy veges sok extremalis iranya van (meg = @0 eseten sem). Ez ket problemat vet fel. A kevesbe lenyeges, hogy az algoritmus nem lesz veges Ami nagyobb gond, hogy amennyiben Q elemei nem fesztik ki C -t, akkor el}ofordulhat, hogy az algoritmus elveti az optimumot. Tehat biztostani kell, hogy a cone(Q) = C egyenl}oseg fennalljon, hacsak vegtelen sok lepes utan is. BEGIN Q0 := Q1 :=   z := +1  y2S (tetsz}oleges) WHILE true DO BEGIN w :=

min(b ; F (y))T u  (Az optimalitasi feltetel.) u2P ) THEN BEGIN IF w = z ; f (yn x := arg max cT x j K x 5 b ; F (y)  STOP. END ELSE BEGIN n o x=0  (Az (x y) optimalis megoldas.) (Az ooptimalitasi kriterium nem teljesult.) T U := u j (b ; F (y)) u < z ; f (y)  (A fentiek miatt = ) u2U (tetsz}oleges) 1 u^0 := (1uT )T  (normalas) U 6 k u^ :=  n v := arg max  j  5 ku ; k u T k(1u )T k k (1vT )T k  (1vT )T k v^0 := (1v1T )T  v^ := (1vvT )T n w := arg max  j  5 ku ; w^ := ww  Q1 := Q1  f(^u0  u^ )  (^v0 v^ )g  ^ )g  Q0 := Q0  f(0 w k k k k  k k k (1wT )T k  (1wT )T k o u 2 Q1  v 2 P  (normalas) o u 2 Q0  w 2 C0  (normalas) 29 Q := Q0   o Q1  n (z y)  u0(z ; f (y)) + uT F (y) 5 uT b  G (Q) := (u0 uT )T 2Q IF G (Q) = THEN STOP. (A relaxaltnak sincs megengedett megoldasa. ) ELSE (z y) := arg max f z j (z y) 2 G (Q) g END END (Vege a WHILE ciklusnak. ) END. 3.9 Tetel: Ha zart kup,

akkor z konvergal az optimalis megoldas celfuggvenyertekehez. Bizonytas: Legyen T a C es az egyseggomb metszete. T zart, korlatos halmaz, ezert kompakt C minden eleme ravetthet}o normalassal a T halmazra Az algoritmus biztostja, hogy coneQ mindenutt s}ur}u C -ben.  C 4 A ltalanostas konvex, zart kupra 4.1 Farkas tetel konvex, zart kupra 4.1 Dencio: Legyen K 2 Rn tetsz}oleges kup Ekkor K adjungalt kupja:  n o K = c 2 Rn  cT x = 0  8x 2 K :  Konnyen ellen}orzhet}o, hogy K is kup.  4.1 Tetel: Tegyuk fel, hogy K Rn konvex, zart kup, A 2 Rn m  b 2 Rm  A kovetkez}o ket alltas ekvivalens: 9x 2 K : Ax = b  (i) yT A 2 K -nak kovetkezmenye yT b = 0 : (ii) Bizonytas: (i) ) (ii) Tegyuk fel, hogy a tetel (i) alltasa fennall, de indirekten van olyan y 2 Rm , hogy  yT A 2 K (1a) T y b < 0: (1b) (1a) miatt yT Ax = 0 , mg (1b) miatt yT Ax = yT b < 0 . Ez ellentmondas  30 (ii) ) (i) Tegyuk fel, hogy

(ii) teljesul, de nem letezik K-beli x , melyre Ax = b . Ekkor A(K) = fAx j x 2 Kg konvex, zart kup es b vektor Rm-ben hiperskkal elvalaszthatok. Azaz 9y 2 Rm (y 6= 0) : yT Ax = 0 8x 2 K  yT b < 0 : Ez ellentmond (ii)-nek.  4.2 Dekompozcio konvex, zart kupbol vett linearis valtozokra Legyen K Rn tetsz}oleges konvex, zart kup, S Rm tetsz}oleges halmaz, A 2 Rm n , L Rm konvex, zart kup. Tekintsuk a max cT x + f (y) b ; Ax ; F (y) 2 L  x2K y2S feladatot. Bevezetve a z celfuggvenyvaltozot max z z ; cT x ; f (y) 5 0 b ; Ax ; F (y) 2 L x2K y2S feladatra transzformaljuk. Azt a kerdest szeretnenk megvalaszolni, hogy milyen rogztett (z y) ertekre letezik kiegeszt}o, megengedett x vektor. Ha ilyen x letezik, akkor a 0 1  ;cT 0T 1  B x C  f (y) ; z  A Im 0 @ vv A = b ; F (y)  ahol x 2 K  v 2 L  v0 = 0 (2) 0 kiegeszt}o valtozokat tartalmazo matrixegyenl}osegnek is van megoldasa. A Farkas tetelben szerepl}o kup: F = f(x v

v0) j x 2 K  v 2 L  v0 = 0g . Ez nylvan konvex es zart. A (2) egyenl}oseg eppen a Farkas tetel (i) pontja, gy igaz (ii) is. Legyen  u      0  ( u  uT ) ;cT 0T 1 2 F : C= u  0 A Im 0  31 A Farkas tetel (ii) alltasa alapjan pontosan akkor letezik kiegeszt}o x , ha u   f (y) ; z  0 T 8 u 2 C -ra ( u0 u ) b ; F (y) = 0 igaz. Ekkor a f}ofeladat a kovetkez}o alakot olti: n  o max z  (z y) 2 G  ahol  f (y) ; z     T G= (z y)  (u0 u ) b ; F (y) = 0  z 2 R y 2 S : (u0 uT )T 2C Ha (z y) optimalis megoldasa a f}ofeladatnak, akkor max cT x b ; Ax ; F (y) 2 L x 2 K kupprogramozasi feladat megadja az optimalis x-et. 5 Gyakorlati megfontolasok Gyakorlati, szamtasi szempontbol egy algoritmusnak azontul, hogy veges sok lepesben veget kell ernie, ha megalltjak { valamilyen technikai okbol, vagy az iteraciok nagy szama, vagy a hosszu futasi id}o miatt { szolgalnia kell reszeredmennyel. Az 1 fejezet vegen

ismertetett algoritmus ezzel a tulajdonsaggal nem rendelkezik, de kis modostassal elerhet}o, hogy a megszaktas utan az eddig talalt legjobb megengedett megoldast megadja. A modostas megtalalhato 8]-ban. A problema azert merul fel, mivel mindig egy relaxalt feladatot oldunk meg, melynek megoldasairol rendre kiderul, hogy a f}ofeladatnak nemmegengedett megoldasai. A megoldas kulcsa, hogy a celfuggvenyre nem csak fels}o, hanem also becslest is szamontartunk. Ezt alapozza meg a kovetkez}o lemma. 5.1 Lemma: Tekintsuk a min (bT ; F (y)T )u AT u = c (P ) u = 0 32 max cT x Ax 5 b ; F (y) x = 0 (D) primal-dual feladatpart. a) Ha a (P ) feladat celfuggvenye nem korlatos, akkor az y vektorhoz nem talalhato olyan x vektor, hogy az els}o fejezetben (F )-fel jelolt eredeti feladatnak megengedett megoldasa legyen (x y) . b) Ha a (P ) feladatnak optimalis megoldasa van, akkor az adott y mellett az (F ) feladat lehet}o legjobb

celfuggvenyerteket az az x vektor adja, mely rendelkezesunkre all, ha a (P ) feladatot modostott szimplex modszerrel oldjuk meg es a f (y) + uT (b ; F (y)) ertek az (F ) feladat optimalis celfuggvenyenek also becslese. Bizonytas: a) Ebben az esetben a dualitas tetel szerint (D) feladatnak nincs megengedett megoldasa, tehat nincs kiegeszt}o x vektor sem. b) Szinten a dualitas tetel miatt (D)-nek optimalis megoldasa van (x ). Ez azt jelenti, hogy (x y) megengedett megoldas, celfuggvenyerteke also becsles az optimumra.  A lemma felhasznalasaval konnyen beepthet}o nehany uj valtozo, melyekben a celfuggveny aktualis also becsleset, illetve az aktualis megengedett (x y) megoldast taroljuk. Az algoritmust csak kiegeszteni kell egy szubrutinnal, melyet akkor kell lefuttatni, ha az 1.4 alfejezetben lert algoritmus jelolesei alapjan w > ;1 . A szubrutin azt ellen}orzi le, hogy az uj y es gy a modostott

szimplex modszer adta, plusz szamtast nem igenyl}o x altal adott celfuggvenyertek, nevezetesen cT x + f (y) = f (y)+ uT (b ; F (y)) nagyobb-e, mint a tarolt ertek. Amennyiben a valasz igenl}o, akkor kicsereli a megfelel}o valtozokat az uj ertekekre, kulonben azokat valtozatlanul hagyja. Az algoritmus soran tarolt also illetve fels}o becslesek arra is lehet}oseget adnak, hogy leallasi kriteriumot adjunk meg. Az alabbiakban megadunk nehany lehetseges leallasi kriteriumot:  az elert also becsles kell}oen nagy, egy korlat folott van  a fels}o es also becsles elterese egy kuszob ala esik  az el}oz}o ket kriterium kiegesztve egy id}okorlattal. 33 Ezen kriteriumok beeptese a szamtasi id}ot lerovidti, melyre 8]-ban talalunk peldakat. Koszonetnyilvantas Koszonettel tartozom Kassay Gabor nak3, aki ertekes megjegyzesekkel segtette a dolgozat elkeszteset, es hozzajarult a tetelek

elestesehez. Tovabba koszonetet mondok Kovacs Margit nak4, akinek Nemlinearis programozas es Konvex analzis el}oadasa nelkul ez a dolgozat nem keszulhetett volna el. Koszonet illeti temavezet}omet, Vizvari Bela t5, aki rendkvuli alapossaggal tanulmanyozta at ujra meg ujra a dolgozatot, ertekes tanacsaival hozzajarult, hogy a dolgozat mind tartalmilag, mind szerkezetileg folyamatosan csiszolodjon, es elnyerje vegs}o formajat. Babes-Bolyai Egyetem, Analzis es Operaciokutatasi Tanszek, 3400 Cluj-Napoca, Kogalniceanu 1., Romania 4 E otvos Lorand Tudomanyegyetem, Operaciokutatasi Tanszek, H-1088 Budapest, Muzeum krt. 6-8, margo@cseltehu 5 E otvos Lorand Tudomanyegyetem, Operaciokutatasi Tanszek, H-1088 Budapest, Muzeum krt. 6-8, vizvari@cseltehu 3 34 Irodalomjegyzek 1] Benders J. F, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik 4 (1962), 238-252 2] Craven B.D,

Koliha JJ, Generalizations of Farkas` Theorem, SIAM J. Math Anal, 8 (1977), 983-997 3] Dantzig G.B, Wolfe P, Decomposition principle for linear programs, Operations Research 8 (1960), 101-111. 4] Farkas Gyula, A Fourier-fele mechanikai elv alkalmazasai, Matematikai es Termeszettudomanyi E rtest}o 12 (1894), 457-472. 5] Farkas Gyula, A Fourier-fele mechanikai elv alkalmazasanak alapja, Matematikai es Termeszettudomanyi E rtest}o 16 (1898), 361-364. 6] Farkas Gyula, Theorie der einfachen Ungleichungen, J. fur Reine und Angewandte Mathematik 124 (1901), 1-27. 7] Geoffrion A.M, Generalised Benders decomposition, Journal of Optimization Theory and Applications, 10 (1972), 237-260 8] Hoffer Janos, Megengedett megoldasok vizsgalataval b}ovtett Benders dekompozcios algoritmus, Alkalmazott Matematikai Lapok, 5 (1979), 177190. 9] Prekopa Andras, On the development of optimization theory, Amer. Math. Monthly 87 (1980), 527-542 10] Shimizu K., Aiyoshi

E, Katayama R, Generalized Farkas` Theorem and Optimization of Innitely Constrained Problem, Journal of Optimization Theory and Applications, 40 (1983) 451-463. 11] Vizvari Bela, Benders Decomposition for cone programming, A. Gopfert, J. Seelander, Chr Tammer (eds) Proceedings of the 6th Workshop of the DGOR-Working Group Multicriteria Optimization and Decision Theory Alexisbad 1996, Deutsche Hochschuleschriften 2398, Verlag HanselHohenhausen, Engelsbach/Frankfurt/Washington, (1997), 109-116. 35 12] Wittrock R. J, Advances in a nested decomposition algorithm for solving staircase linear programs, Technical Report SOL 83-2, System Optimization Laboratory, Stanford University (1983)