ÌÖØÐÓÑÝÞ ÚÞØ ÞÖØ ÑÓÑÒØÙÑ ÔÖÓÐÑ Þ ÝÚ ÐØÓÞ ÞÖØ ÑÓÑÒØÙÑ ÔÖÓÐÑ ØÚ ÐØÓÞ ÞÖØ ÑÓÑÒØÙÑ ÔÖÓÐÑ ÌÚ ÐØÓÞ ÞÖØ ÚÒÝ Ñ ÖÒò ÓÒÚÜØ Ý ØØÐ ØÚ ÐØÓÞ ÄÖÒ ÒØÖÔÓÐ Ö ÃÓÖÐ ØÓ ÌÅ

Többváltozós diszkrét momentum problémák Doktori értekezés

írta

Nagy Gergely Matematikus

ELTE Matematika Doktori Iskola Vezet®je: La zkovi h Miklós Alkalmazott matematika doktori program Vezet®je: Prékopa András 2002.

Témavezet®: Prékopa András

Tartalomjegyzék

Bevezetés

2

1. Diszkrét momentum problémák

5

1.1. Az egyváltozós diszkrét momentum probléma . . . . . . . . . . . . . . . . . . . 1.2. A többváltozós diszkrét momentum probléma . . . . . . . . . . . . . . . . . . .

5 14

2. Többváltozós diszkrét függvények magasabb rend¶ konvexitása

20

3. Egy tétel többváltozós Lagrange interpolá ióra

24

4. Korlátok TDMP feladatokra

34

5. Példák, numerikus eredmények

51

Tanulságok, további kutatási irányok

63

Köszönetnyilvánítás

65

Összefoglaló

66

Summary

67

Irodalom

68

Függelék

70

4.1. Korlátok rendezett tartók esetén . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2. Egy dekompozí iós eljárás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3. További duál megengedett bázisok, algoritmusok és korlátok a kétváltozós esetre 46

5.1. Kétváltozós feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.2. Egy többváltozós hasznossági függvény . . . . . . . . . . . . . . . . . . . . . . . 59

1

Bevezetés

A momentum problémák fontos szerepet játszanak számos gyakorlati szto hasztikus programozási feladat esetében, mivel ezen feladatok megoldásán keresztül közelítéséket adhatunk valószín¶ségekre és várható értékekre. Gyakran el®fordul, hogy egy valószín¶ségi változóhoz tartozó valószín¶ségi eloszlás ismeretlen, azonban ismert néhany momentuma, és ezen informá iók birtokában akarunk alsó illetve fels® korlátokat adni az eloszlás kvantiliseire vagy pedig a valoszín¶ségi változó egy nemlineáris (de általában konvex) függvényének várható értékére. Legyen P egy valószín¶ségi eloszlás az a; b véges intervallumon, és jelölje 1 ; 2 ; : : : a hozzá tartozó hatvány momentumokat, i.e.,

[ ℄

Zb z k dP a

= k ; k = 1; 2; : : : :

(0.1)

=0

esetre, bár tudjuk, hogy Az egységes jelölés kedvéért gyakran hasznaljuk a 0 jelölést a k 0 . A (0.1) hatvány momentumoknál általánosabb momentumokat deniálhatunk az uk t ; k ; ; : : : függvény sorozat segítségével, ahol feltesszük, hogy a sorozat tagjai folytonosak az a; b intervallumon, és lineárisan függetlenek. (A függvények bármely, véges elemb®l álló, nemtriviális lineáris kombiná iója négyzetének az a; b intervallumon vett integrálja nem nulla.) A P , fuk t g sorozathoz tartozó momentumai az alábbiak:

=1 =01 [ ℄

() =

[ ℄

()

Zb a

uk (z )dP

= k ; k = 1; 2; : : : :

(0.2)

A momentum problémához kap solódó kutatási területek a következ® kérdésekkel foglalkoznak: -Adott a 0 ; 1 ; 2 ; : : : számsorozat, keressünk szükséges és elégséges feltételeket arra, hogy ez momentumok egy sorozata. -Adottak a 0 ; : : : ; m momentumok, vagy egyéb véges momentum halmazok, mi a legjobb alsó és fels® korlát a Z b

a

f (z )dP

integrál értékére, ahol f egy adott függvény, míg a P eloszlás ismeretlen. A momentum problémák területének mélyebb kidolgozása Csebisev, Stieltjes és Markov nevéhez f¶z®dik, a 19. század végér®l. A klasszikus eredmények és a történeti háttér részletes leírása megtalálható Karlin and Studden [4℄ illetve Krein and Nudelman [5℄ könyveiben. Diszkrét momentum problémának hívjuk azt az esetet, amikor a P valószín¶ségi eloszlás tartója véges diszkrét halmaz. Ez esetben lehet®ség nyílik a feladat lineáris programozási feladatként való reprezentálására, mely egyúttal azt is jelenti, hogy használhatóak az LP területén 2

eddig elért eredmények, módszerek. A diszkrét momentum problémák ilyen fajta megközelítése Prékopa [12℄ nevéhez f¶z®dik, akinek sikerült, az f függvényre tett bizonyos feltételek mellett, a momentum problémához tartozó LP feladat összes duál megengedett bázisát kombinatorikai úton megtalálni, és ezáltal alapot adni a legjobb korlát gyors megtalálására illetve konkrét képletszer¶ korlátok megadására. Tovább haladva ezen a gondolatmeneten, sokszor hasznosnak és érdekesnek bizonyul a momentum problémák azon fajtájának vizsgálata, amikor nem sak egy valószín¶ségi változót, hanem egy valószín¶ségi vektort vizsgálunk, melynek az egyváltozós tiszta momentumain kív¶l adott még néhány vegyes momentuma is. Az ilyen fajta momentum probléma véges, diszkrét tartójú esetére ugyan sak alkalmazhatók LP eszközök. Az ebben a témakörben elért eddigi eredmények jó összefoglalását adja Prékopa [15℄, míg a probléma felvetésének hasznosságára jó bizonyítékul szolgál [17℄. Megjegyezzük, hogy ez esetben, ellentétben az egyváltozós esettel, még semmilyen nem triviális feltétel mellett sem sikerült az összes duál megengedett bázis kombinatorikus megtalálása, hanem supán sak néhány struktúráé. Dolgozatunkban az utóbbi, többváltozós diszkrét momentum problémával foglalkozunk. Egyrészt egy, az eddigieknél általánosabb probléma lesz vizsgálatunk tárgya, melyre lényegében a Prékopa [12℄ és [15℄ ikkeiben szerepl® tételek közös általánosítását kapjuk. Másrészt, feltárjuk a kapott bázisstruktúrák mögötti feladatok szerkezetét, és ezt kihasználva adunk egy dekompozí iós módszert a legjobb struktúrán belüli korlát megtalálására. Ezentúl bemutatunk egy új kombinatorikus módszert, mellyel a duál megengedett bázisoknak olyan nagyságú halmaza állítható el®, mely általában már alkalmas használható közelítések megadására a kétváltozós esetben. Végül numerikus példákon keresztül mutatjuk be eredményeink használhatóságát. A dolgozat felépítése a következ®. Az 1. Fejezetben a diszkrét momentum probléma (DMP) felvetése, a kés®bbiekben tárgyalt konkrét feladatok, alapfogalmak, jelölésrendszerek bevezetése szerepel. Szó esik még a diszkrét momentum probléma és a Lagrange interpolá ió kap solatáról. Id®rendi és logikai sorrendben haladva, az els® szakasz a klasszikus egyváltozós esetet mutatja be, mely alapul szolgál a második szakasz többváltozós általánosításaihoz. Az egyváltozós esethez b®vebb áttekintést nyújt [12℄ illetve [11, Se tion 5℄, míg a többváltozós eset bevezetése az [7℄ ikket követi. A 2. Fejezet a diszkrét függvények konvexitását vezeti be, osztott dieren iák segítségével. Szó esik még a folytonos és a diszkrét konvex függvények kap solatáról. A témakörr®l jó összefoglalást ad pl. [15℄. A 3. Fejezetben szerepl® tétel szolgáltat alapot az utána következ® módszerek bevezetéséhez, s egyszersmind általánosítása mind az egyváltozós DMP, mind pl. a [15℄ ikkben tárgyalt többváltozós DMP (TDMP) hasonló jelleg¶ tételeinek. A 4. Fejezet els® szakaszában az el®z® fejezet általánosabb tételének segítségével találunk duál megengedett bázis struktúrákat a TDMP feladathoz, az egyváltozós ill. a [15℄-beli többváltozós DMP struktúra tételeinek általánosításaiként. A második szakaszban feltárjuk a struktúra 3

szerinti megoldások szerkezetét, és ennek segítségével megadunk egy egyszer¶ dekompozí iós eljárást a struktúrán belüli legjobb korlátok megtalálására. Végül a fejezet utolsó szakasza bemutat egy mer®ben új módszert, mely segítségével jóval több duál megengedett bázis található, de sajnos sak a kétváltozós esetre. Mint az 5. Fejezetben látni fogjuk, numerikus jelent®sége így sem lebe sülend®. Az utolsó fejezet az elmélet használhatóságát hivatott bizonyítani. Konkrét feladatokon keresztül vizsgálja, hasonlítja össze a különböz® módszerek pontosságát, hatékonyságat. Remélhet®leg sikerül azt is megvilágítani, hogy milyen el®nyökkel jár a dolgozatban tárgyalt általánosabb TDMP használata az el®zményként szolgáló [15℄-beli feladathoz képest. A dolgozatban saját eredmények: a 3.1. Tétel bizonyítása illetve a 4.2. és 4.3. szakaszokban szerepl® módszerek. Az 5. fejezet numerikus példái ugyan sak saját munkák.

4

1. Diszkrét momentum problémák 1.1. Az egyváltozós diszkrét momentum probléma

A dolgozat témájául szolgáló többváltozós diszkrét momentum problémák el®zményeként az egyváltozós diszkrét momentum problémák (DMP) területén a lineáris programozás eszközeivel elért els® eredményeket említhetjük. Szakaszunkban ezekr®l az eredményekr®l adunk némi összefoglalót Prékopa [12℄ ikke alapján. Megjegyezzük, hogy a diszkrét momentum problémák témakörének más megközelítése is létezik, lásd pl. Samuels and Studden [19℄. Legyen X egy valószín¶ségi változó, mely tartója a z0 < z1 < < zn számokból álló véges halmaz. Vezessük be a következ® jelöléseket:

pi = P (X = zi ); i = 0; 1; : : : ; n:

(1.1)

= ( )

=

Feltesszük, hogy a fenti valószín¶ségek nem ismertek, viszont a k E Xk ; k i h ismertek X ; : : : ; m binomiális ; : : : ; m hatvány momentumok, vagy pedig az Sk E k ; k momentumok, ahol m < n adott. Célunk egy a fpi g halmazon deniált lineáris funk ionál minimalizálása illetve maximalizálása, gyelembe véve a momentumok által meghatározott megszorításokat. Más szóval, tekintsük a következ® lineáris programozás feladatokat:

=1

=

=1

feltéve, hogy

feltéve, hogy

min(max) ff0p0 + f1p1 + + fnpng p0 + p1 + + pn = 1 z0 p 0 + z 1 p 1 + + z n p n = 1 z02 p0 + z12 p1 + + zn2 pn = 2 z0m p0 + z1m p1 + + znm pn = m p0 0; p1 0; : : : ; pn 0; min(max) ff0p0 + f1p1 + + fnpng p0 + p1 + + pn = 1 z p + z p + + z 1 1 n pn = S1 0 0 z p + z p + + z p = S 0 1 n 2 2 2 2 z p + z p + + z p = S m m n m 0 m 1 p0 0; p1 0; : : : ; pn 0: 0

1

n

0

1

n

(1.2)

(1.3)

A továbbiakban az (1.2) problémát hatvány, míg az (1.3) problémát binomiális momentum problémának fogjuk hívni. A korlátozó egyenletrendszer mátrixát, oszlopait illetve a jobboldalon 5

álló vektort rendre az A; a0 ; a1 ; : : : ; an és hatvány momentum problémára 1 0 B B C zi C B C 2 C B zi C ; i ai B B B ... C C A

b bet¶kkel jelöljük, mindkét probléma esetén. 1 0 B C B 1 C C B B 2 C ; C B C B B ... C A

1

=

1

= 0; 1; : : : ; n; b =

zim

míg a binomiális momentum problémára 1 0 C B B zi C C B zi C B B ai B 2 C C; i .. C B B . C A

(1.4)

m

1

=

Így a

1 0 B C B S1 C C B B S2 C C B C: B B ... C A

1

= 0; 1; : : : ; n; b =

(1.5)

Sm

zi m

Az (1.2) illetve az (1.3) problémák egymásba átkonvertálhatók az els® illetve másodfajú Stirling számok segítségével. Ezeket jelöljék rendre az s l; k és az S l; k szimbólumok, és deniálják ®ket az alábbi egyenletek. l X k

( )

(z)l = =

zl

() = (

ahol z k zz Riordan [18℄), hogy

1) (z

k + 1), k

s(n; k)

=

=

=

k=0

s(l; k)z

(1.6)

S (l; k)(z )k ;

= 1; 2; : : : ; esetén,

másrészt

( 1)n+k n! k k k +2k ++nk =n k1 !1 kn !n X

k

+kn =k

;:::;kn0 X

k1 +2k2 ++nkn =n k1 +k2 ++kn =k k1 0;:::;kn 0

= ( )!

n

1

n

2 k 1 +k 2 + 1 0

1

S (n; k)

k=0 l X

( )

k1 !1k

(z)0 = 1.

Ismert (lásd

;

n!

1

kn!nk : n

=

s(l;k) S l; k k . Alkalmazva a (1.6) egyenleteket z X esetére, majd Legyen slk l! ; Slk tekintve mindkét oldal várható értékét, látható, hogy ha az (1.4) vektorokat balról megszorozzuk

6

a

T1 =

0 B B B B B B B

s00 s10 s11 s20 s21 s22 .. .

.. .

.. .

sm0 sm1 sm2

..

.

smm

1 C C C C C C C A

(1.7)

mátrixszal, akkor pont a (1.5) vektorokat kapjuk meg, míg ha az (1.5) vektorokat szorozzuk meg balról a 0 1 S00 B C B C S10 S11 B C B C S20 S21 S22 (1.8) T2 B C B C .. .. .. B ... C . . . A

=

Sm0 Sm1 Sm2

Smm

=

mátrixszal, akkor pedig pont az (1.4) vektoraihoz jutunk. Vegyük észre, hogy teljesül a T2 T1 1 relá ió is. Az f vektor tekintetében három fajta feltevéssel szoktak élni. Ám miel®tt ezeket felvázolnánk, megjegyezzük, hogy fk helyett néha az f zk jelölést fogjuk használni, néha pedig az f függvény értelmezési tartományát kiterjesztjük az egész z0 ; zn intervallumra. Az említett három fajta eset a következ®.

=

( )

[

℄

+1

(1) Az f függvény fz0 ; z1 ; : : : ; zs g halmazon vett m rend¶ osztott dieren iái pozitívak (lásd a kés®bbi dení iót), más szóval a diszkrét halmazon értelmezett f függvény m rendben konvex. A feltételt, többek közt kielégítik azok a z0 ; zn intervallumon értelmezett folytonos függvények, melyekre f (m+1) z > az intervallum bels® pontjaiban. Ez esetben az (1.2) illetve (1.3) feladatok optimális megoldásai éles korlátokat szolgáltatnak az E f z várható értékre.

+1

()

0

[ ( )℄

=1

0

[

℄

+

=0 =

; fi i 6 r esetén. Ez esetben az (1.2) illetve (1.3) (2) Egy adott r n értékre fr feladatok optimális megoldásai éles korlátokat szolgáltatnak a P X zr valószín¶ségre. (3)

( = ) Egy adott 0 r n értékre f0 = = fr 1 = 0, fr = = fn = 1. Ez esetben az (1.2) illetve (1.3) feladatok optimális megoldásai éles korlátokat szolgáltatnak a P (X zr ) valószín¶ségre.

()

Az f z , z 2 fz0 ; : : : ; zn g diszkrét függvény els®rend¶ osztott dieren iáit az alábbi módon jelöljük, illetve deniáljuk:

[zi ; zi ; f ℄ = f (zzi ) 1

1

2

i1

7

f ( zi ) : zi 2

2

(1.9)

A k rend¶ osztott dieren iákat, a szokásos, induktív módon értelmezzük (lásd pl. Jordan [3℄, Popovi iu [10℄, Prékopa [15℄), tehát

[zi; : : : ; zi+k ; f ℄ = [zi+1 ; : : : ; zi+k ;zf ℄ [zzi; : : : ; zi+k 1; f ℄ ; k 2: i+k

i

Az f diszkrét függvényt k rendben konvexnek nevezzük, ha valamennyi ren iája nemnegatív. Ismert (lásd például [3℄), hogy

1

1

zi

[zi ; : : : ; zi+k ; f ℄ =

1 zi+k

zi+1

.. .

.. .

..

zi .. .

.

1 zi+1

zik 1 zik+11 f (zi ) f (zi+1 )

1

k rend¶ osztott diffe-

.. .

zik 1 zik+11 zik zik+1

..

.

.. .

zik+k1 f (zi+k )

1

;

0in

k:

(1.10)

zi+k .. .

zik+k1 zik+k

A fenti (1.10) formula nevez®je egy Vandermonde determináns, amely mindig pozitív, így zi ; : : : ; zi+k f el®jele mindig a számláló el®jelével egyezik meg. Az els®rend¶ konvexitás a függvény monoton növekv® voltát, a másodrend¶ konvexitás a függvény konvexitását jelenti, a hagyományos értelemben. A fenti dení ió némileg eltér Popovi iu [10℄ dení iójától. ® ugyanis a k rend¶ konvexitást a k rend¶ osztott dieren iák nemnegatívitásával értelmezte. A kés®bbiekben szükségünk lesz a (2) illetve a (3) esetekben felírt függvényosztályok osztott dieren iái el®jelének meghatározására. Könnyen látható, hogy a (2) esetre az (1.10) képlet segítségével választ kaphatunk. A (3) esetben az alábbi tétel lesz segítségünkre.

[

; ℄

+1

1.1. Tétel.

Legyen

1 i1 < i2 < < it < < im+2 n. Ekkor ( 1)t t = ( 1)t a0i a0i ai1 ai1 t

1

ahol az

ai ; : : : ; ai 1

Bizonyítás.

m+2

t+1

m+2

> 0;

(1.11)

vektorok mindegyike vagy (1.4) vagy (1.5) típusú.

Tekintsük el®ször azt a a spe iális esetet, amikor

8

ai

k

(1.5) típusú és zik egész,

k = 1; : : : ; m + 2.

Vezessük be a következ® jelölést: 1 0

1

B B l B l B B 2 B . B B ..

vl :=

l m

C C C C C ; C C C A

ahol l tetsz®leges egész szám. Nyilvánvalóan

ai = vz ; k = 1; : : : ; m + 2: ik

k

Bizonyításunk kul sa az alábbi kombinatorikus azonosság: ! ! !

k i

Ekképpen

1

vk vk 1 = Ha

0 B B k B k B B 2 B . B B .. k m

1 l < k n, akkor:

k

1 = i 1 C C C C C C C C A

0 B B k B k 1 B B 2 B . B B ..

1 C C C C C C C C A

1

1

k 1 m

vk vl = vk vk 1 + + v l+1 v l =

1 1

k i

=

:

0 B B B B k B B .. B .

0 1

k m

0 B B B B k B B .. B .

0 1

k m

1

1 1

1 C C C C ; C C C A

1 C C C C C C C A

k = 1; : : : ; n:

1 ++

1 1

0 B B B B l B B .. B .

0 1

m

+1

l

i1

i2

vz ; : : : ; vz i1

it

vz ; vz it 1

Behelyettesítve v zi1 helyére az alábbi összeget

vz = (v z i1

i1

9

it+2

v0) + v0;

vz ; : : : ; vz it+1

(1.12)

1

Kivonva az (1.11) els® oszlopát a másodikból, ..., az m -ik oszlopát az kifejtve a determinánst az els® sora szerint, a következ®t kapjuk:

t = ( 1)t j(vz ; vz

1 C C C C C : C C A

m + 2-ikb®l, majd

im+2

vz

im+1

)j:

majd a többi oszlopban a különbségeket az (1.12) jobboldala szerinti alakba átírva, látható, hogy t t szétesik zi2 zi1 zit zit 1 zit+2 zit+1 zim+2 zim+1 darab determinánsra, melyek közül sak azok nem t¶nnek el, melyek els® oszlopa v 0 (a többi determinánsban az els® sor supa elemb®l áll). Ezen determinánsokat els® oszlopuk (v 0 ) szerint kifejtve viszont mindig egy (1.5) típusú oszlopokból álló (m m ) determinánshoz jutunk, melyr®l pedig tudjuk, hogy pozitív. Ezzel a fenti spe iális esetet beláttuk. Tekintve egyrészt, hogy ha aik (1.5) típusú, akkor T2 aik éppen (1.4) típusú és ugyanez igaz fordítva a T1 T2 1 mátrixszal való balról szorzás esetén, másrészt, hogy jT2 j =jT1 j > , látható, hogy a tétel állítása pontosan akkor igaz (1.4) típusú oszlopvektorokra, ha igaz (1.5) típusúakra. Továbbhaladva, feloldandó a zik egészérték¶ségére tett feltételt, tekintsünk egy (1.4) típusú oszlopokból álló t determinánst, ahol zik értékei ra ionálisak, k ; : : : ; m . Legyen a zik értékek nevez®inek legkisebb közös többszöröse L. Megszorozva t i-edik sorát az L(i 2) értékkel, i ;:::;m , máris egy, a spe iális esetnek megfelel® egészérték¶ mátrixszot kapunk, míg a determináns el®jele nem változott. Ezzel beláttuk a ra ionális esetet. Az általános, valós zik értékekre vonatkozóan az állítás már adódik határátmenettel a ra ionális esetb®l. 2 esetén Tételünk következménye, hogy g zi1 g zit , g zit+1 g zim+2

( 1)

2(

) (

)(

) (

0

:=

)

1

=

=1

=2

=1

+2

( )= = ( )=0 ( )= ( 1)t+m+1 [zi ; : : : ; zi ; g℄ > 0:

= (

0

+2

)=1

m+2

1

Tovább haladva az (1.2) illetve (1.3) feladatok vizsgálatában, látható, hogy az A mátrix teljes sorrangú. Legyen B az A mátrix egy m m méret¶ minorja, és jelölje I a B oszlopaihoz tartozó változók indexeinek halmazát. A B mátrixot illetve a benne szerepl® oszlopokat bázisnak fogjuk hívni. Ha szükséges, akkor B helyett a B I jelölést fogjuk használni. Jelölje f B az f bázisbeli komponenseit. Az y vektort, mely teljesíti az

( + 1) ( + 1)

()

y B = fB T

T

(1.13)

egyenl®séget, a B mátrixhoz tartozó duál vektornak nevezzük. A B bázist duál megengedettnek nevezzük, ha minimum (maximum) feladatra

y ap fp p 2 f0; : : : ; ng I esetén (y ap fp p 2 f0; : : : ; ng I esetén): T

T

(1.14)

Legyenek b; a0 ; : : : ; an az (1.4) vektorai. Az (1.2) feladat korlátozó egyel®ségeit az alábbi módon is felírhatjuk:

(T1 a0) p0 + + (T1an) pn = T1 b

másrészt

fp

(T1 B1) 1 T1b = f B (T1 B ) (T1 ap) = T

10

B 1b fp fBT B 1 ap :

(1.15)

Így T1 B pontosan akkor primál megengedett bázisa a (1.3) problémának, ha B primál megengedett az (1.2) problémában. Másrészt T1 B pontosan akkor duál megengedett az (1.3) minimum (maximum) problémában, ha B duál megengedett bázisa az (1.2) minimum (maximum) problémának. Legyen LI z a zi ; i 2 I fi0 ; : : : ; im g alappontokhoz tartozó, m fokú Lagrange polinom. Newton féle alakban felírva

()

=

LI (z ) = Deniáljuk a valós

m X k=0

kY1

[zi ; : : : ; zi ; f ℄ (z k

0

z értékeken értelmezett

zil ):

l=0

(1.16)

1 0 B C B z C C B 2 C B z C B C B B ... C A

1

b=

zm

vektort. Ekkor igaz az alábbi egyel®ség:

f B B 1(I )b(z) = LI (z): T

Valóban,

(1.17)

b(zi ) = ai; i 2 I esetén, így f B B 1(I )b(zi ) = f (zi); i 2 I; T

(1.18)

tehát (1.17) áll minden valós z értékre. Tekintsük még a Lagrange polinom maradéktagját, ugyan sak Newton féle alakban:

f (z ) LI (z ) = [zi ; : : : ; zim ; z ; f ℄ 0

m Y

(z

l=0

zil ); z 2 IR:

(1.19)

A fentiekb®l következik, a duál megengedettség Lagrange approximá ióval való megfogalmazása, miszerint B I duál megengedett bázisa az (1.2) minimum (maximum) feladatnak pontosan akkor, ha az f z függvény az LI z polinom fölött (alatt) halad minden zi ; i 62 I esetén. Ha az zi ; i 2 I; z f osztott dieren iák el®jelér®l megfelel® informá ióink vannak, akkor az (1.19) egyenl®ség segítségével megtalálhatók azok az I indexhalmazok, melyek duál megengedett bázisokat határoznak meg. Erre mutatnak példákat a fejezet hátralev® részében szerepl® állítások.

[

() ()

; ℄

()

11

1.2. Tétel.

Tegyük fel, hogy az

dieren iája pozitív.

f (z ); z 2 fz0 ; z1 ; : : : ; zn g függvény összes m + 1 rend¶ osztott

Ekkor mind az (1.2) mind az (1.3) probléma összes duál megengedett

bázisának index strukturája az alábbiak valamelyikét követi:

m + 1 paros min feladat fj; j + 1; : : : ; k; k + 1g max feladat f0; j; j + 1; : : : ; k; k + 1; ng

m + 1 paratlan f0; j; j + 1; : : : ; k; k + 1g fj; j + 1; : : : ; k; k + 1; ng

Bizonyítás. Tekintsük a minimum problémát, ahol a duál megengedettség a következ®t jelenti: f z LI z ; z 62 fzi ; i 2 I g esetén. Mivel zi ; i 2 I; z f > z 62 fzi ; i 2 I g esetén, így pontosan az alábbinak kell teljesülnie: Y

()

() 0

[

i2I

(z

; ℄ 0

zi ) 0:

+ 1 esetén, illetve ha f (z ) LI (z ) 0;

Ez pedig akkor és sak akkor igaz, ha I konzekutív párokból áll páros m a 0 és konzekutív párok alkotják páratlan m esetén. Maximum probléma esetén a duál megengedettség azt jelenti, hogy z 62 fzi ; i 2 I g esetén, ekképpen a Y

+1

i2I

(z

zi ) 0

egyenl®tlenséget követeljük meg. Ez pedig pont a tételben szerepl® index halmazok esetén teljesül. 2

1.3. Tétel.

Tegyük fel, hogy

fr

= 1 és fi = 0 i 6= r esetén, ahol 0 r n.

Ekkor mind az

(1.2) mind az (1.3) probléma összes duál megengedett bázisának index strukturája az alábbiak valamelyikét követi. Minimum probléma,

m + 1 páros:

r 62 I , f0; i; i + 1; : : : ; j; j + 1; r 1; r; r + 1; k; k + 1; : : : ; t; t + 1g, ha 2 r n fi; i + 1; : : : ; j; j + 1; r 1; r; r + 1; k; k + 1; : : : ; t; t + 1; ng, ha 1 r n f0; 1; i; i + 1; : : : ; j; j + 1g, ha r = 0, és fi; i + 1; : : : ; j; j + 1; n 1; ng, ha r = n; Minimum probléma,

1, 2,

m + 1 páratlan:

r 62 I , f0; i; i + 1; : : : ; j; j + 1; r 1; r; r + 1; k; k + 1; : : : ; t; t + 1; ng, ha 2 r n fi; i + 1; : : : ; j; j + 1; r 1; r; r + 1; k; k + 1; : : : ; t; t + 1g, ha 1 r n 1, f0; 1; i; i + 1; : : : ; j; j + 1; ng, ha r = 0, és 12

2,

f0; i; i + 1; : : : ; j; j + 1; n 1; ng, ha r = n; m + 1 páros: fi; i + 1; : : : ; j; j + 1; r; k; k + 1; : : : ; t; t + 1; ng, ha 0 r n f0; i; i + 1; : : : ; j; j + 1; r; k; k + 1; : : : ; t; t + 1g, ha 1 r n;

Maximum probléma,

1,

m + 1 páratlan: fi; i + 1; : : : ; j; j + 1; r; k; k + 1; : : : ; t; t + 1g, ha 0 r n, f0; i; i + 1; : : : ; j; j + 1; r; k; k + 1; : : : ; t; t + 1; ng, ha 1 r n

Maximum probléma,

1;

ahol a kap sos zárójelben álló számok növekv® sorrendben rendezettek.

Bizonyítás. A bizonyítás az (1.10), (1.17) és (1.19) relá iók felhasználásával az el®z® tételhez hasonló módon kivitelezhet®, ezért a módszert sak egy példán illusztráljuk. Tekintsük a minimum feladatot, m legyen páros, r n , r 2 I és I elemei közül páros számú kisebb, mint r . Ekkor (1.10) szerint

+1

2

[z; zi ; i 2 I ; f ℄ [z; zi ; i 2 I ; f ℄ Így a

Y j 2I

< >

(z

1

0; ha z < zr 0; ha z > zr : zj )

szorzatnak z < zr esetén negatívnak, míg z > zr esetén pozitívnak kell lennie. Ennek pedig a tételben felsoroltak közül a második struktúra felel meg. 2

1.4. Tétel.

Tegyük fel, hogy

f0 = = fr

1

= 0, fr = = fn = 1, ahol 1 r n.

Ekkor

mind az (1.2) mind az (1.3) probléma összes duál megengedett bázisának index strukturája az alábbiak valamelyikét követi.

m + 1 páros: I f0; : : : ; r 1g, ha r m + 1, f0; i; i + 1; : : : ; j; j + 1; r 1; k; k + 1; : : : ; t; t + 1g, ha 2 r n fi; i + 1; : : : ; j; j + 1; r 1; k; k + 1; : : : ; t; t + 1; ng, ha 1 r n;

Minimum probléma,

1,

m + 1 páratlan: I f0; : : : ; r 1g, ha r m + 1, f0; i; i + 1; : : : ; j; j + 1; r 1; k; k + 1; : : : ; t; t + 1; ng, ha 2 r n,

Minimum probléma,

13

fi; i + 1; : : : ; j; j + 1; r 1; k; k + 1; : : : ; t; t + 1g, ha 1 r n 1; m + 1 páros: I fr; : : : ; ng, ha n r m, fi; i + 1; : : : ; j; j + 1; r; k; k + 1; : : : ; t; t + 1; ng, ha 1 r n f0; i; i + 1; : : : ; j; j + 1; r; k; k + 1; : : : ; t; t + 1g, ha 1 r n;

Maximum probléma,

1,

m + 1 páratlan: I fr; : : : ; ng, ha n r m, fi; i + 1; : : : ; j; j + 1; r; k; k + 1; : : : ; t; t + 1g, ha 1 r n, f0; i; i + 1; : : : ; j; j + 1; r; k; k + 1; : : : ; t; t + 1; ng, ha 1 r n

Maximum probléma,

1;

ahol a kap sos zárójelben álló számok növekv® sorrendben rendezettek.

Bizonyítás.

A bizonyítás az (1.10), (1.17) és (1.19) relá iók illetve a 1.1. Tétel felhasználásával az el®z® tételekhez hasonló módon kivitelezhet®. 2 1.2. A többváltozós diszkrét momentum probléma

A TDMP felvetése és tárgyalása Prékopa [13, 15, 16℄ ikkeihez f¶z®dik. A problémát, az X1 ; : : : ; Xs valószín¶ségi vektorváltozóra fogalmazzuk meg. Feltesszük, hogy Xj értelmezési tartománya egy ismert véges halmaz: Zj fzj 0 ; : : : ; zjnj g, j ; : : : ; s. Vezessük be a következ® jelölést:

(

)

=

pi :::is 1

=1 = P (X1 = z1i ; : : : ; Xs = zsi ); 0 ij nj ; j = 1; : : : ; s; n n X X z1i zsi pi :::i ; ::: = s

1

1

s

1

i1 =0

s

is =0

1 1

s s

1

s

(

) +

ahol 1 ; : : : ; s nemnegatív egész számok. A 1 :::s számot az X1 ; : : : ; Xs valószín¶ségi vektorváltozó 1 ; : : : ; s rend¶ (hatvány)momentumának nevezzük. Az 1 s összeg a momentum teljes rendje. Tekintsük az f z , z 2 Z , Z Z1 Zs függvényt és vezessük be a következ® jelölést: fi1 :::is f z1i1 ; : : : ; zsis . A többváltozós diszkrét momentum probléma egyik megfogalmazása

(

= (

)

()

)

=

14

+

a következ® lineáris programozási feladat:

min(max) feltéve, hogy

n1 X

n1 X i1 =0

ns X

ns X is =0

fi :::is pi :::is 1

1

(1.20)

z1i zsi pi :::i = ::: i =0 i =0 j 0; j = 1; : : : ; s; 1 + s m pi :::i 0; minden i1 ; : : : ; is esetén: s s

1 1

1

s

1

s

s

1

s

1

A fenti problémát általánosíthatjuk, ha bevezetünk néhány, az m számnál magasabb rend¶ egyváltozós momentumra vonatkozó korlátozó feltételt is. Ennek egyik lehetséges módját fejezi ki a következ® modell:


n1 X

ns X

1

s

n1 X i1 =0

ns X is =0

fi :::is pi :::is 1

1

z1i zsi pi :::i = ::: i =0 i =0 j 0; j = 1; : : : ; s; 1 + s m és s s

1 1

1

s

1

(1.21)

s

j = 0; j = 1; : : : ; k 1; k + 1; : : : ; s; m k mk ; k = 1; : : : ; s; pi :::is 0; minden i1 ; : : : ; is esetén: 1

Az (1.20) és a (1.21) problémákban a pi1 :::is szimbólumok a változók, míg a többi érték adott. A fenti problémák korlátokat szolgáltatnak az

E [f (X1 ; : : : ; Xs )℄

(1.22)

értékre, a megfelel® momentumok ismeretében. A (1.22) várható érték spe iális esetei, alkalmas f függvények esetén, a P X 1 r1 ; : : : ; X s r s (1.23)

(

)

és a

P (X1 = r1 ; : : : ; Xs = rs ); valószín¶ségek, ahol (r1 ; : : : ; rs ) 2 Z .

(1.24)

A (1.20) és a (1.21) feladatok egyszer¶bb alakban is felírhatók, mátrixok tenzorszorzatának segítségével. Az m1 n1 méret¶ B bij mátrix és az m2 n2 méret¶ C

ij mátrix tenzorszorzata a B C , m1 m2 n1 n2 méret¶ mátrix, ahol B C

ij B . Ismert (lásd pl.

=( )

=(

15

)

=( )

Horn és Johnson [2℄), hogy a tenzorszorzat asszo iatív, de nem kommutatív. Vezessük be a következ® jelöléseket: 1 0 B zj 0 zj 1 zjnj C C B C B Aj B .. .. C . A .

=

1

1

1

mj zjm0j zjm1j zjn j A = A1 A s

b = E [(1; X1; : : : ; X1m ) (1; Xs; : : : ; Xsm )℄ s

1

= (00:::0 ; 10:::0; : : : ; m 0:::0 ; 010:::0; 11:::0 ; : : :) p = (pi :::i ; 0 i1 n1; : : : ; 0 is ns) f = (fi :::i ; 0 i1 n1; : : : ; 0 is ns) ;

T

T

1

1

s

1

s

T

T

ahol p és f komponenseinek a sorrendje megegyezik az A mátrix megfelel® oszlopainak sorrendjével. Az A megfelel® sorainak, illetve a b megfelel® komponenseinek a kiválasztásával, a fenti problémák tömör alakban is felírhatók. Az (1.20) feladat tömör formája:

min(max) f p T

feltéve, hogy

a (1.21) feladaté pedig:

(1.25)

= be p 0;

Aep

min(max) f p T

feltéve, hogy

(1.26) = bb p 0: Az A mátrix mérete [(m1 +1) (ms +1)℄ [(n1 +1) (ns +1)℄, míg az Ae mátrixé N [(n1 + + 1) (ns + 1)℄, ahol N = s+mm . Az Ab mátrix mérete N 0 [(n1 + 1) (ns + 1)℄, ahol P N 0 = N + sj=1(mj m). Az Ae mátrix teljes rangú, ha m nj ; j = 1; : : : ; s; az Ab mátrix teljes rangú, ha mj nj ; j = 1; : : : ; s. Jelölje Vmin (Vmax ) az (1.20) vagy (1.21) probléma minimumát (maximumát). Jelölje továbbá B1 (B2 ) a minimum (maximum) probléma egy duál megengedett bázisát (olyan bázist,

Abp

melyre az optimalitási feltételek teljesülnek). Ezek után, a lineáris programozás elméletét felhasználva, felírhatjuk a következ® egyenl®tlenségeket:

f B pB Vmin E [f (X1; : : : ; Xs)℄ Vmax f B pB : T

T

1

1

2

16

2

(1.27)

( )

Ha B1 B2 primál megengedett is, tehát optimális bázis a minimum (maximum) problémában, akkor az els® (utolsó) egyenl®tlenség egyenl®séggel teljesül. Ekkor azt mondjuk, hogy Vmin és Vmax éles alsó és fels® korlátok az f X1 ; : : : ; Xs függvény várható értékére. A többváltozós diszkrét hatvány momentum problémákhoz hasonlóan felírhatók a többváltozós diszkrét binomiális momentum problémák is. Mivel ezen problémáknak különösen esemény sorozatok vizsgálatánál van nagy jelent®sége, ahol Xj a j -edik sorozatban az esemény el®fordulásának számosságát jelenti, ezért a feladatokat a Zj f ; : : : ; nj g; j ; : : : ; s esetre írjuk fel. Az 1 ; : : : ; s rend¶ (1 ; : : : ; s nemnegatív egészek) binomiális momentumot az alábbi módon deniáljuk: " !# !

(

)

= 0

(

=1

)

X1 1

S :::s = E 1

X s :

(1.28)

s

Az el®z®ekhez hasonlóan két fajta feladatot írunk fel. Egyrészt n1 ns X X

min(max)

feltéve, hogy

n1 X

i1 =0

is =0

1

1

!

!

ns X

fi :::is pi :::is

is i1 = S :::s p s i :::is i =0 is =0 i j 0; j = 1; : : : ; s; 1 + s m pi :::is 0; minden i1 ; : : : ; is esetén; 1

(1.29)

1

1

1

másrészt


n1 X

n1 X i1 =0

ns X

!

ns X is =0

fi :::is pi :::is 1

1

!

is i1 = S :::s p s i :::is is =0 i i =0 j 0; j = 1; : : : ; s; 1 + s m és j = 0; j = 1; : : : ; k 1; k + 1; : : : ; s; m k mk ; k = 1; : : : ; s; pi :::is 0; minden i1 ; : : : ; is esetén: 1

1

(1.30)

1

1

A fenti problémák rendre (1.20) illetve (1.21) megfelel®i. Ha az (1.20) illetve (1.21) feladatban feltesszük, hogy Zj f ; : : : ; nj g; j ; : : : ; s, akkor léteznek nemszinguláris lineáris transzformá iók, melyekkel mind az (1.20), (1.29) probléma pár, mind az (1.21), (1.30) probléma pár tagjai egymásba átkonvertálhatók. Pontosabban, ha az (1.29) ((1.30)) feladatot, az (1.25) ((1.26)) feladathoz hasonlóan, mátrix alakban írjuk fel, akkor a korlátozó egyenletrendszerek mátrixai egy nemszinguláris mátrix illetve inverze segítségével egymásba áttranszformálhatók. Ebb®l, az el®z® szakaszhoz hasonlóan, következik, hogy az (1.25) probléma ((1.26)

= 0

=1

17

probléma) egy bázisa pontosan akkor duál megengedett, ha duál megengedett az (1.29) ((1.30)) feladatban is. Valóban, legyen D az a nemszinguláris mátrix, melyre DA az (1.29) feladat korlátozó egyenleteinek mátrixát adja. Ekkor az (1.25) feladatban a B bázisra vonatkozó optimalitási feltétel: f BT B 1ak fk minden k index esetén; (1.31)

( )

míg (1.30) transzformált bázisára a következ®nek kell teljesülnie:

f TB (DB ) 1Dak ()fk minden k index esetén:

(1.32)

Nyilvánvaló, hogy (1.31) és (1.32) egy és ugyanaz. A fenti gondolatmenet ugyanígy alkalmazható az (1.26) és (1.30) feladatok esetében is. Végül, hogy kap solatot teremthessünk a többváltozós Lagrange interpolá ió és a (1.25), (1.26) problémák között, bevezetjük a következ® terminológiát. Legyen az U fu1 ; : : : ; uM g az IRs tér egy halmaza, és H f 1 ; : : : ; s g az 1 ; : : : ; s nemnegatív egész komponensekb®l alkotott s dimenziós vektorok egy véges halmaza. Azt mondjuk, hogy U megenged egy H -típusú Lagrange interpolá iót, ha bármilyen valós f z , z 2 U függvény esetén létezik olyan p z polinom, mely a következ® alakban írható, X

1 ; : : : ; s z11 zss ; (1.33) pz

=

= (

()

( )=

ahol

(1 ;:::;s )2H

() (

)

(

)

)

(1 ; : : : ; s) valós számok, és p(ui ) = f (ui ); i = 1; : : : ; M:

(

) ( =1

(1.34)

)

b ) vektorhoz hasonlóan, azzal a különbDeniáljuk a be z1 ; : : : ; zs (bb z1 ; : : : ; zs ) vektort a be (b séggel, hogy elhagyjuk a várható értéket és az Xj valószín¶ségi változó helyére a zj determinisztikus változót írjuk, j ; : : : ; s. A (1.25) ((1.26)) probléma esetén deniáljuk a H , I és U halmazokat a következ® módon:

H (H

= f(1; : : : ; s)j 0 j ; j egész, 1 + + s m; j = 1; : : : ; sg = f(1; : : : ; s)j 0 j ; j egész, 1 + + s m; j = 1; : : : ; s; vagy j = 0; j = 1; : : : ; k 1; k + 1; : : : ; s; m k mk ; k = 1; : : : ; sg); I (I U

= f(i1; : : : ; is)j aei i 2 Be g = f(i1; : : : ; is)j abi i 2 Bb g); 1

s

1

s

= f(z1i ; : : : ; zsi )j (i1 ; : : : ; is) 2 I g: 1

s

18

(1.35)

Ekkor az

LI (z1 ; : : : ; zs) (LI (z1 ; : : : ; zs)

= f BeBe 1 be(z1; : : : ; zs) = f BbBb 1 bb(z1; : : : ; zs)) T

(1.36)

T

polinom megegyezik az U halmazhoz tartozó H -típusú, egyértelm¶en adott Lagrange polinommal. A Be illetve Bb bázis duál megengedettsége a minimum (maximum) problémára a következ®ket jelenti:

f (z1 ; : : : ; zs ) LI (z1 ; : : : ; zs ); minden (z1 ; : : : ; zs) 2 Z esetén (f (z1; : : : ; zs) LI (z1; : : : ; zs); minden (z1 ; : : : ; zs) 2 Z esetén);

(

(1.37)

)

ahol z1 ; : : : ; zs 2 U esetén egyenl®ség áll. A (1.37) relá iót a minimum (maximum) probléma optimalitási feltételének nevezzük. Ha a (1.37) relá iókban z1 ; : : : ; zs helyére az X1 ; : : : ; Xs valószín¶ségi vektorváltozót helyettesítjük és vesszük a kifejezés várható értékét, akkor korlátot kapunk az E f X1 ; : : : ; Xs várható értékre. Ha a bázis egyben primál megengedett is, akkor a kapott korlát éles.

(

)

(

)

19

[(

)℄

2. Többváltozós diszkrét függvények magasabb rend¶ konvexitása

Az el®z® fejezetben, már vizsgáltuk a konvexitás fogalmát egyváltozós diszkrét függvények esetére. Az f z , z 2 fz0 ; : : : ; zn g diszkrét függvény els®rend¶ osztott dieren iáit (1.9) szerint deniáltuk, míg a magasabb rend¶ osztott dieren iákat a szokásos induktív módon vezettük be. Megjegyeztük azt is, hogy a k rend¶ konvexitást a k rend¶ osztott dieren iák nemnegatívitásával jellemezzük. Dolgozatunkban a többváltozós diszkrét függvényeket a számegyenes véges részhalmazainak Des artes szorzatain értelmezzük. Az f z , z z 1 ; : : : ; z s 2 Z Z 1 Z s , Zj fzj0; : : : ; zjnj g, j ; : : : ; s függvény k1; : : : ; ks rend¶ osztott dieren iáját a Z halmaz valamely

()

() =( ) = = = =1 ( ) ZI :::I = fz1i ; i 2 I1 g fzsi ; i 2 Is g = (2.1) = Z1I ZsI ; részhalmazához rendeljük, ahol jIj j = kj + 1; j = 1; : : : ; s, és az alábbi módon értelmezzük. 1

s

s

1

Vesszük a z1 változó szerinti k1 rend¶ osztott dieren iát, majd a z2 szerinti k2 rend¶ osztott dieren iát, és így tovább, végül a zs szerinti ks rend¶ osztott dieren iát. E m¶veleteket tetsz®leges sorrendben végrehajthatjuk, az eredmény mindig ugyanaz. Az f függvény k1 ; : : : ; ks rend¶ osztott dieren iájának a jelölésére a

(

)

[z1i; i 2 I1; ; zsi; i 2 Is; f ℄ (2.2) szimbólumot használjuk. A k1 + + ks összeget az osztott dieren ia teljes rendjének nevezzük. Az osztott dieren iákra érvényesek az alábbi állítások. Ha f (z ); z 2 Z egyváltozós diszkrét függvény és V1 ; V2 2 Z; V1 \ V2 = ;, akkor [V1; [V2 ; f ℄℄ = [V2 ; [V1; f ℄℄ = [V1 [ V2; f ℄: Ha f (z ); z 2 Z = Z1 Z2 diszkrét függvény és z1 2 Z1 , z2 2 Z2 , V1 Z1 , V2 Z2 , akkor [V1; [z1 ; V2; f ℄℄ = [V2; [V1; z2 ; f ℄℄ = [V1; V2; f ℄: 2.1. Dení ió. Az f (z ); z 2 Z (többváltozós) függvényt (m1 ; : : : ; ms ) rendben konvex diszkrét függvénynek hívjuk, ha bármely fzji ; i 2 Ij g, jIj j = mj + 1; j = 1; : : : ; s esetén fennáll az alábbi relá ió: [z1i ; i 2 I1 ; ; zsi; i 2 Is; f ℄ 0: (2.3) 2.2. Dení ió. Egy f (z ); z 2 Z (többváltozós) függvényt m rend¶ konvex függvénynek nevezünk, ha valamennyi

m teljes rend¶ osztott dieren iája nemnegatív. 20

Ha f (z ); g (z ); z 2 Z ugyanolyan rendben konvex, akkor ez a tulajdonság igaz az f (z ) + + g(z); z 2 Z összegre is. A szorzat esetét tekintve, a következ® állítást kapjuk. 2.1. Tétel. Ha f (z ) 0, g (z ) 0, z 2 Z bármilyen i rendben konvex, 1 i m, akkor ugyanez igaz az f (z )g (z ), z 2 Z függvényre is.

Bizonyítás. A szorzat osztott dieren iája hasonló szabállyal kapható meg, mint a szorzat deriváltja. Ebb®l a tényb®l az állítás már könnyen levezethet®. 2 A magasabb rend¶ konvexitásra adott dení iónkban sak a koordináta tengelyek irányában vett osztott dieren iákat használtuk. El®fordulhat, hogy egy függvénynek az összes második teljes rend¶ osztott dieren iája nemnegatív, viszont valamely (a tengelyekt®l különböz®) egyenes mentén nem konvex a függvény. Erre példa a következ®. Legyen Z1 Z2 f ; ; g, és deniáljuk az f z ; z 2 Z1 Z2 függvényt az alábbi módon:

= = 012 () f (0; 0) = 0; f (1; 0) = 1:2; f (2; 0) = 2:6; f (0; 1) = 0:4; f (1; 1) = 2; f (2; 1) = 3:6; (2.4) f (0; 2) = 1; f (1; 2) = 2:8; f (2; 2) = 4:6: A függvény nem konvex a (0; 2); (1; 1); (2; 0) egyenes mentén, mivel 1 + 2:6 = f (0; 2) + f (2; 0) : f (1; 1) = 2 > 2 2 Ha az f (z ); z 2 Z függvényt az f (z ), z 2 Z , Z = [z10 ; z1n ℄ [zs0 ; zsn ℄ folytonos függvényb®l származtatjuk oly módon, hogy f (z ) = f (z ); z 2 Z , és f (z ) (k1 ; : : : ; ks ) rend¶ deriváltjai Z belsejében folytonosak és nemnegatívak, akkor f (z ); z 2 Z összes (k1 ; : : : ; ks ) rend¶ osztott dieren iája nemnegatív. Egy f (z ); z 2 Z , diszkrét, m rendben konvex függvény esetén általában nem könny¶ konstruálni egy olyan f (z ); z 2 Z folytonos, nemnegatív m rend¶ deriváltakkal rendelkez® függvényt, mely a Z diszkrét halmazon megegyezik f (z ) értékeivel. Ha azonban az f függvény 1

s

értelmezési tartományát megszorítjuk, akkor bizonyos esetekben mégis tudunk adni ilyen konstruk iót. Ezt fejezi ki az alábbi

2.2. Tétel.

Deniáljuk a

ZI

diszkrét halmazt a következ® módon:

ZI = f(zi ; : : : ; zis )j (i1 ; : : : ; is) 2 I g; 1

ahol

I = f(i1 ; : : : ; is)j i1 + + is m; 21

0 ij nj ; j = 1; : : : ; sg;

(2.5) (2.6)

9 8 7 6 5 4 3 2 1 0

Æ Æ Æ Æ Æ 0

Æ Æ Æ Æ Æ Æ 1

Æ Æ Æ Æ Æ Æ Æ 2

Æ Æ Æ Æ Æ Æ Æ Æ

3

Æ Æ Æ Æ Æ Æ Æ Æ Æ 4

Æ Æ Æ Æ Æ Æ Æ Æ Æ Æ


5

6

Æ Æ Æ Æ Æ Æ Æ Æ Æ Æ 7


8


9 8 7 6 5 4 3 2 1 0

9

0

1

Æ

2

3

=2

I

4

Æ Æ Æ 5

Æ Æ Æ Æ 6

Æ Æ Æ Æ Æ 7

Æ Æ Æ Æ Æ Æ 8


(b)

(a) 1. ábra: s ; n1 esetet szemlélteti.

Æ Æ

= n2 = 9, I elemeit jelöli. Az (a) ábra az m = 4, míg a (b) ábra az m = 11 m n1 + + n s :

lehetséges struktúráit a 1. ábra szemlélteti. Ekkor létezik pontosan egy olyan

LI (z ) polinom, melyre

LI (z ) = f (z ), z 2 ZI ; kj nj ; j = 1; : : : ; s, k1 + +ks = m esetén LI (z ) (k1 ; : : : ; ks ) rend¶ deriváltjai megegyeznek az f függvény (k1 ; : : : ; ks ) rend¶ osztott dieren iáival az alábbi halmazon:

és

f(z1i ; : : : ; zsi )j 0 ij kj ; j = 1; : : : ; sg: 1

Az

s

LI (z ) polinom a következ®: LI (z1 ; : : : ; zs ) =

ahol, dení ió szerint,

X i1 ++is m 0ij nj ; j =1;:::;s

ij = 0 esetén

[z10 ; : : : ; z1i ; ; zs0; : : : ; zsi ; f ℄ 1

iY j 1 h=1

(zj

zjh) = 1.

22

s

j 1 s iY Y

j =1 h=0

(zj

zjh );

(2.7)

A polinom maradéktagját az alábbi képlettel adhatjuk meg:

s X h=1

RI (z1 ; ; zs ) = z1 ; ; zh 1 ; zh0 ; : : : ; zhih ; zh; z(h+1)0 ; : : : ; z(h+1)ih

h

X 0ij nj ; j =h;:::;s ih ++is =m; vagy ih ++is <m és ih =nh :

+1

; (2.8)

ih Y

j 1 s iY Y

l=0

h+1 k=0

; zs0; : : : ; zsi ; f ℄ (zh zhl ) s

(zj

zjk ) :

()

Bizonyítás. Könnyen ellen®rizhet®, hogy LI z megfelel® deriváltjai eleget tesznek a kívánalmaknak. A polinom egyértelm¶ségének illetve a maradéktag képlete spe iális esetének (m nj ; j ; : : : ; s) bizonyítása megtalálható Prékopa [15℄ ikkében (362. old., Theorem 4.1). A maradéktag általános esete a hivatkozott bizonyítás triviális módosításával látható be. 2

=1

2.1. Megjegyzés.

Az

LI (z ) polinomot a ZI ponthalmazhoz tartozó Lagrange polinom Newton

féle alakjának nevezzük.

A továbbiakban, különösen a fenti tétel általánosításának bizonyításakor, gyakran felhasználjuk az egyváltozós Lagrange interpolá ió elméletéb®l jól ismert alábbi formulát:

f (z ) L(z ) = [z0 ; : : : ; zk ; z ; f ℄ ahol

L(z ) a z0 ; : : : ; zk

k Y j =0

(z

zj );

(2.9)

alappontokhoz tartozó Lagrange polinom,

L(z ) =

k X i=0

f (zi )

(z

(zi

z0 ) (z z0 ) (zi

zi zi

)(z 1 )(zi 1

zi+1 ) (z zk ) : zi+1 ) (zi zk )

(2.10)

Az (2.9) formulát általában intervallumon értelmezett függvények esetében használják. A mi esetünkben azonban nem sak az alappontok halmaza, hanem az f függvény értelmezési tartománya is véges.

23

3. Egy tétel többváltozós Lagrange interpolá ióra

Szakaszunkban nem tesszük fel, hogy a Z1 ; : : : ; Zs halmazok rendezett lennének. Az alábbi tétel bármilyen az IRs halmazon értelmezett Lagrange interpolá ió esetére érvényes. Tekintsük a következ® indexhalmazt: I I0 [ [sj=1 Ij ; (3.1)

=

ahol és

I0 = f(i1 ; : : : ; is )j 0 ij m

1;

egészek,

j = 1; : : : ; s; i1 + : : : + is mg

Ij = f(i1 ; : : : ; is)j ij 2 Kj ; il = 0 l 6= j g Kj = fkj(1) ; : : : ; kj(jKj j) g fm; m + 1; : : : ; nj g; j = 1; : : : ; s: 9 8 7 6 5 4 3 2 1 0

Æ Æ Æ 0

Æ Æ Æ Æ Æ Æ 1

Æ Æ Æ Æ Æ Æ Æ


2

3

Æ Æ Æ Æ Æ Æ Æ Æ Æ

4



5

6



8

(3.2) (3.3)


2. ábra: A fenti ábra a fejezetben deniált I index halmazt mutatja, ahol az I0 index halmazhoz tartozó pontokat jelöli, feltéve, hogy m=4, míg az I1 és I2 index halmazokhoz tartozókat , feltéve, hogy K1 f ; ; ; g f ; ; : : : ; g; K2 f ; ; g f ; ; : : : ; g.

= 4579

45

9

= 568

Vezessük be az alábbi jelöléseket:

Zji Zji0 Kji

ZjKji ZjKj

45

= fzj0; : : : ; zjig = fzj0; : : : ; zji; zj g; i = 0; : : : ; nj ; j = 1; : : : ; s; = fkj(1) ; : : : ; kj(i) g = fzjk ; : : : ; zjk g; i = 1; : : : ; jKj j; j = 1; : : : ; s; = ZjK j j ; j = 1; : : : ; s: (i)

(1)

j

j

j Kj

24

9

) (

= (

A ZI f z1i1 ; : : : ; zsis j i1; : : : ; is Newton-féle alakkal adjuk meg:

= +

Kj j h s jX X j =1 i=1

) 2 I g pontokhoz tartozó Lagrange polinomot az alábbi LI (z1 ; : : : ; zs ) =

X i1 +:::+is m 0ij m 1; j =1;:::;s

Z10 ; ; Z(j

1)0

[Z1i ; ; Zsi ; f ℄ s

1

j 1 s iY Y

j =1 k=0

; Zj(m 1) [ ZjK ; Z(j+1)0; ; Zs0; f

(zj

i

ji

ahol, dení ió szerint

iY j 1 k=0

(zj

zjk ) = 1;

zjk ) +

ha ij

Y k2f0;:::;m

1g[Kj (i

(zj

zjk ) ;

1)

= 0: Kj0 := ;:

(3.4) A (3.4) kifejezésben az f függvény bármilyen függvényt jelölhet, melynek a Z halmaz elemeihez tartozó értékei megegyeznek az eredeti diszkrét függvény értékeivel. A maradéktagot a következ® módon adjuk meg:

RI (z1 ; : : : ; zs ) = R1I (z1 ; : : : ; zs ) + R2I (z1 ; : : : ; zs); ahol

=

s h X j =1

z10 ; ; z(j

1)0

; Zj(m

R1I (z1 ; : : : ; zs ) = i 1) [ ZjKj [ fzj g; z(j +1)0 ; ; zs0 ; f

és

=

s X

X

h=1

ih ++is =m 0ij m 1; j =h;:::;s

h

R2I (z1 ; : : : ; zs ) =

z1 ; ; zh

+

s h X j =h+1

z1 ; ; zh

1

1

Y k2f0;:::;m

; Zhi0 ; Z(h+1)i ; ; Zsi ; f h+1

h

j 1 s iY Y

h+1 k=0

(zj

s

(3.5)

ih iY l=0

1g[Kj

(zh

mY1 k=0

(3.6)

(3.7)

i

(zj

zjk )

zhl )

zjk )+

; Zh0 0; Z(h+1)0 ; ; Z(j 1)0 ; Zj0 (m 1); Z(j+1)0; ; Zs0 (zh

(zj

zh0 )

zjk ) :

A következ® tétel általánosítása mind az egyváltozós (2.9) formulának, mind a 2.2. Tételben szerepl® (2.7) és (2.8) többváltozós formuláknak. 25

3.1. Tétel.

f

Tetsz®leges, az

függvény értelmezési tartományába es®,

z = (z1 ; : : : ; zs) pontra

igaz a következ® egyenl®ség:

LI (z1 ; : : : ; zs ) + RI (z1 ; : : : ; zs) = f (z1 ; : : : ; zs ):

(3.8)

= =1

+1

Bizonyítás. Az általánosság megszorítása nélkül feltehetjük, hogy Kj fm; m ; : : : ; mj g, ahol mj m; j ; : : : ; s. Valóban, ha tekintjük a Zj Zj (m 1) [ ZjKj ; j ; : : : ; s; halmazt, majd erre bebizonyítjuk az állítást, akkor lényegében az eredeti általános esetre vonatkozó állítást láttuk be. A Kj ; j ; : : : ; s; halmazokra tett feltétel szerint az LI z1 ; : : : ; zs és R1I z1 ; : : : ; zs függvények a következ® formát öltik:

=

=1

=1

(

X

=

+

LI (z1 ; : : : ; zs ) =

i1 +:::+is m 0ij m 1; j =1;:::;s mj h s X X Z10 Z(j j =1 ij =m

;;

[Z1i ; ; Zsi ; f ℄ s

1

j 1 s iY Y

j =1 k=0

)

(zj

1)0 ; Zji ; Z(j +1)0 ; ; Zs0 ; f j

(

zjk ) +

j 1 i iY

k=0

)

(3.9)

(zj

zjk )

és

R1I (z1 ; : : : ; zs ) = Az R2I be:

s h X j =1

Z10 ; ; Z(j

0 1)0 ; Zjm ; Z(j +1)0 ; ; Zs0 ; f

mj iY

j

k=0

(zj

zjk ) :

(3.10)

(z1 ; : : : ; zs) függvényre adott képlet változatlan marad. El®ször a következ® állítást látjuk

3.2. Lemma.

Érvényes az alábbi egyenl®ség:

LI (z1 ; : : : ; zs) + R1I (z1 ; : : : ; zs) =

=

+

X

i1 ++is m 0ij m 1; j =1;:::;s s h X Z10 Z(j j =1

;;

[Z1i ; ; Zsi ; f ℄ 1

s

j 1 s iY Y

j =1 k=0

(zj

0 1)0 ; Zj (m 1) ; Z(j +1)0 ; ; Zs0 ; f

A 3.2. Lemma bizonyítása Tekintsük a zj

zjk )+ i mY1 k=0

(zj

zjk ) :

változó alábbi függvényét:

[Z10; ; Z(j 1)0; Zj0 (m 1) ; Z(j+1)0; ; Zs0; f ℄: 26

(3.11)

Az ezzel a függvénnyel vett, zjm ; : : : ; zjmj pontokhoz tartozó Lagrange polinom így írható: mj X ij =m

[Z10 ; ; Z(j 1)0 ; Zji ; Z(j+1)0; ; Zs0; f ℄ j

iY j 1 k=m

(zj

zjk ):

Ezek után, az (2.9) képletet használva, felírhatjuk, hogy

[Z10 ; ; Z(j 1)0 ; Zj0 (m 1); Z(j+1)0; ; Zs0; f ℄ = iY1 m X = [Z10; ; Z(j 1)0; Zji ; Z(j+1)0; ; Zs0; f ℄ (zj j

j

+

j

ij =m

h

Z10 ; ; Z(j

1)0

0 ;Z ; Zjm (j +1)0 ; ; Zs0 ; f

j =1

[Z10; ; Z(j

1)0

mj i Y

j

Ha a (3.12) egyenl®ség minden sorát megszorozzuk a összegezzük j szerint, akkor a következ®t kapjuk: s X

k=m

; Z0

j (m

1)

Qm

k=m 1

k=0

(zj

; Z(j+1)0; ; Zs0; f ℄

mj h s X X

(zj

k=0

j

j

(3.12)

zjk ) :

zjk ) tényez®vel,

mY1

Z10 ; ; Z(j 1)0 ; Zji ; Z(j +1)0 ; ; Zs0 ; f = j =1 i =m +R1I (z1 ; : : : ; zs):

zjk )+

(zj

majd ezeket

zjk ) =

j 1 i iY

k=0

(zj

zjk ) +

(3.13)

A (3.9) és (3.13) képletekb®l már adódik a lemma állítása. 2 Ha (3.11) harmadik sorában külön vesszük a j tagot, akkor a következ® formulát kapjuk:

=1 L1I (z1 ; : : : ; zs ) + R1I (z1 ; : : : ; zs ) = s iY1 Y X (zj [Z1i ; ; Zsi ; f ℄ = j

Hasonlóan, ha

+

h

+

s h X

R2I

Z0

1(m 1)

j =2

s

1

i1 ++is m 0ij m 1; j =1;:::;s

; Z20; ; Zs0; f

Z10 ; ; Z(j

1)0

i mY1

; Z0

j (m

képletében leválasztjuk a

k=0 1)

(z1

j =1 k=0

zjk ) +

z1k ) +

; Z(j+1)0; ; Zs0; f

(3.15)

i mY1 k=0

(zj

h = 1 tagot, azt kapjuk hogy:

R2I (z1 ; : : : ; zs ) = 27

(3.14)

zjk ) :

(3.16)

= +

h

X i1 +:::+is =m 0ij m 1; j =1;:::;s s h X

0 s B X B B h=2 ih Y

; Z2i ; ; Zsi ; f

j =h+1

z1 ; ; zh

(zh zh0 )

mY1 k=0

1

l=0

(z1

z1l )

j 1 s iY Y

j =2 k=0

i

h

h+1 k=0

i1 iY

0 1)0 ; Zj (m 1) ; Z(j +1)0 ; ; Zs0 (z1

ih ++is =m 0ij m 1; j =h;:::;s j 1 s iY Y

l=0 s h X

s

2

X

(zh zhl )

+

1i1

0 ;Z ;;Z Z10 20 (j

j =2

+

Z0

z1 ; ; zh

(zj

(zj

z10 )

zjk ) +

mY1 k=0

(zj

zjk ) +

(3.17)

(3.18)

i

1

; Zhi0 ; Z(h+1)i ; ; Zsi ; f s

h+1

h

zjk ) + i

(3.19)

; Zh0 0; Z(h+1)0; ; Z(j 1)0; Zj0 (m 1); Z(j+1)0 ; ; Zs0 !

(zj

zjk ) :

A következ® lépésben meghatározzuk a (3.14), (3.15) és (3.17) tagok összegét. El®ször felírjuk a (3.14) sort az alábbi formában: 1 0 iY m iX 1 1 2 is X Z1i1 Z2i2 Zsis f z1 z1l A 0

+

Y Y

j =2 k=0 m X1 Z1i1 i1 =0

[

(zj

i1 =0

[

;

; ;

; ℄

l=0

(

)

(3.20)

zjk )+

; Z20; ; Zs0; f ℄

iY 1 1 l=0

(z1

z1l ):

(3.21)

Ezt követ®en a (3.17) kifejezést az alábbi alakba írjuk:

X 0
h

Z0

1(m

i1

is ) ; Z2i2 ; ; Zsis ; f

i1 iY l=0

(z1

! s ij 1 Y Y

z1l )

j =2 k=0

(zj

zjk ) :

(3.22)

Célunk az, hogy összeadjuk a (3.20), (3.21), (3.22) és (3.15) formulákat. Egyrészt (3.21) és (3.15) összege (felhasználva az (2.9) képletet) a következ®:

[z1; Z20 ; ; Zs0; f ℄: 28

(3.23)

Másrészt, (3.20) és (3.22) összege (el®ször a zárójelben lév® tagokat adjuk össze) a következ®:

X 0
[z1 ; Z2i ; ; Zsi ; f ℄ s

2

j 1 s iY Y

j =2 k=0

(zj

zjk ) :

(3.24)

A (3.23) és (3.24) összege, és egyben a bizonyítás ezen lépésének eredménye:

X i2 ++is m 0ij m 1; j =2;:::;s

[z1 ; Z2i ; ; Zsi ; f ℄ s

2

j 1 s iY Y

j =2 k=0

(zj

zjk ) :

(3.25)

A következ® lépés az, hogy kiszámoljuk a még gyelembe nem vett (3.16) és (3.18) tagok Q összegét. Tekintve a j indexhez tartozó tagokat a (3.16) és (3.18) sorokban, a km=01 zj zjk tényez® nélkül, a két tag összege (felhasználva az (2.9) képletet a z1 változóra) az alábbi:

(

)

[z1 ; Z20; ; Z(j 1)0 ; Zj0 (m 1); Z(j+1)0; ; Zs0; f ℄:

(3.26)

Eszerint a (3.16) és (3.18) képletek összege az alábbival egyenl®: s X

[z1 ; Z20; ; Z(j 1)0; Zj0 (m 1) ; Z(j+1)0; ; Zs0; f ℄

j =2

(

)+

mY1 k=0

(

(zj )+

zjk ):

(3.27)

(

)

Idáig azt az eredményt kaptuk, hogy az LI z1 ; : : : ; zs R1I z1 ; : : : ; zs R2I z1 ; : : : ; zs összeg megegyezik a (3.25), (3.27) és (3.19) formulák összegével. Deniáljuk a J indexhalmazt I halmazhoz hasonlóan, de sak i2 ; : : : ; is -re vonatkoztatva, és tekintsük az s változós f z1 ; z2 ; : : : ; zs függvényt, ahol z1 2 Z , kötött. Ekkor a (3.25) és a (3.27) képlet összege egyenl® a LJ R1J összeggel, míg (3.19) egyenl® az R2J taggal. Ha feltesszük, hogy (3.8) igaz bármely s változós függvényre, akkor, a fenti érvelés szerint, igaz minden s változós függvényre is. 2

(

) +

1

1

m 1 nj ; j = 1; : : : ; s. Vizsgáljuk meg, hogy mi is a helyzet, ha m 1 > nj valamely j 2 f1; : : : ; sg esetén, lásd például

3.1. Megjegyzés.

A 3.1. Tételben hallgatólagosan feltettük, hogy

a 3. ábrát. Ebben az esetben is megtalálható mind a ponthalmazhoz tartozó Lagrange polinom, mind

m 1 > nj . Vezessük be a = fzj0; : : : ; zjnj ; zju(jnj +1) ; : : : ; zju(jm 1) g. A Zjuj Végezzük el ezt a b®vítést minden olyan j -re,

annak maradéktagja. Módszerünk a következ®. Tegyük fel, hogy

zju(jnj +1) ; : : : ; zju(jm

1) szimbólumokat. Legyen uj

halmaz esetén már igaz, hogy melyre

m

1 > nj teljesült.

m

Zjuj

1 nj .

29

9 8 7 6 5 4 3 2 1 0

0

1

2

3

Æ 4

Æ Æ

Æ Æ Æ

5

6

Æ Æ Æ Æ

7

Æ Æ Æ Æ Æ

8

Æ Æ Æ Æ Æ Æ 9



10


11

12


13



14

15


16



17

18


19

3. ábra: A fenti ábra a megjegyzésben deniált I index halmazt mutatja, ahol az I0 index halmazhoz tartozó pontokat jelöli, feltéve, hogy m=12, míg az I1 (és I2 ;) index halmazokhoz tartozókat , feltéve, hogy K1 f ; ; ; g f ; ; : : : ; g; K2 ; f ; ; : : : ; g.

= 14 15 16 18

A szükséges

Zjuj

11 12

= =

19

11 12

19

halmazokkal vett Des artes szorzaton már m¶ködik a fejezet tétele, így fel

tudjuk írni, mind a (3.4) képlet szerinti Lagrange polinomot, mind annak (3.6) és (3.7) szerinti maradéktagjait. Az így kapott tagokban még szerepelnek az újonnan bevezetett szimbólumok. Ahhoz, hogy az eredetileg keresett

LI (z )

és

R1I (z ); R2I (z )

képleteit megkapjuk, szükségünk van még az

alábbi átalakításokra.

El®ször, törüljük ki az (3.4) illetve (3.7) összegek összes olyan tagját, ahol az osztott dieren iában újonnan bevezetett szimbólum szerepel a koordinátához tartozó szabad változó nélkül, i.e., a

h

i

; zj0; : : : ; zjn ; zju(jn +1) ; : : : ; zjiuj ; ; f j

j

j

iY j 1 k=0

(zj

zjk )

(3.28)

alakú tagokat.

Az így kapott összegekben, illetve a (3.6) képletben a még el®forduló új szimbólumokat (és a hozzá tartozó szabad változót) tartalmazó

h

;

zj 0; : : : ; zjnj ; zju(jnj +1) ; : : : ; zjiujj ; zj

i

ij Y

; ; f (zj k=0

zjk )

(3.29)

alakú tagokat helyettesítsük a nekik megfelel® új szimbólumot nem tartalmazó tagokkal.

30

I.e., írjuk a (3.29) tag helyett az alábbit:

h

nj Y

i

; zj0; : : : ; zjn ; zj ; ; f (zj zjk ) : j

k=0

(3.30)

3.3. Lemma. A 3.1. Megjegyzés módszerét követve valóban a megfelel® Lagrange polinomhoz,

és annak maradéktagjaihoz jutunk.

Bizonyítás. Tekintsük az egyváltozós esetet. Z := fz0 ; z1 ; : : : ; zn g, és legyen m j Z uj = fz0 ; z1 ; : : : ; zn ; znu+1 ; : : : ; zmuj 1 g. A Lagrange polinom (3.4) szerinti alakja LuIj (z ) =

m X1 h i=0

z0 ; : : : ; zi(uj ) ; f

i iY1

(z

k=0

zk(uj ) );

1 > n. Ekkor (3.31)

míg a maradéktag (3.6) szerinti alakja

h

j RIuj (z ) = z0 ; z1 ; : : : ; zn ; znu+1 ; : : : ; zmuj 1 ; z ; f

i mY1 k=0

(z

zk(uj ) ):

(3.32)

Elvégezve a megjegyzés módszerét a (3.31) képletre ( sak a (3.28) alakú tagokat kell törölni), az alábbi polinomot kapjuk:

LI (z ) = ami pedig pont az eredeti

Z

n X i=0

iY1

[z0 ; : : : ; zi; f ℄ (z k=0

zk );

(3.33)

halmazra illeszked® Lagrange polinom.

Alkalmazva a fent leírt módszert a maradéktagra (esetünkben sak a (3.30) alakú tag helyettesítésére van szükség), éppen az

RI (z ) = [z0 ; z1 ; : : : ; zn ; z ; f ℄ képletet kapjuk, amely megegyezik a

n Y k=0

(z

zk ):

(3.34)

Z halmazhoz tartozó Lagrange polinom maradéktagjával.

Ezzel az egyváltozós esetre beláttuk az állítást. Vegyük észre, hogy a 3.1.

Tétel bizonyításában végig sak az egyváltozós Newton féle

alakban megadott Lagrange polinom és annak maradéktagja képleteit használtuk fel (egész pontosan azt, hogy a maradéktag ilyen alakban felírható), ezentúl még a szummázások megfelel® sorrendje, struktúrája segített az átláthatóságban. Mivel lemmánk állítása egyváltozós esetben igaz, így ezt kihasználva, ezt a tényt a 3.1. Tétel bizonyításán végigvezetve, megkapjuk a lemma

2

állítását a többváltozós esetre.

31

3.1. Példa. A 3.1. Megjegyzés módszerére jó példa, ha tekintjük a 3. Ábrán szerepl® esetet: m = 12, Z1 = fz10 ; : : : ; z1;19 g, Z2 = fz20 ; : : : ; z29 g. Mivel 11 = m 1 > n2 = 9, ezért uj uj uj új szimbólumok bevezetésére van szükség, így Z2 = fz20 ; : : : ; z29 ; z2;10 ; z2;11 g. írjuk fel ezek segítségével a 3.1. Tételhez tartozó Lagrange polinomot illetve maradéktagokat. A (3.4) szerinti képlet

=

LuIj (z1 ; z2 ) =

X i1 +i2 12 0ij 11; j =1;2 4 X

[z10 ; : : : z1i ; z20 ; : : : ; z2(ui j); f ℄ 1

iY 1 1

2

k=0

(z1

z1k )

iY 2 1 l=0

(z1

Y

z2(ul j ) )+

(z1

z1k ):

(z1 Yk2f0;:::;11g[K(uj ) +[z10 ; z20 ; : : : ; z29 ; z2u;j10 ; z2u;j11; z2 ; f ℄ (z2 z2k );

z1k )+

+ [z10 ; : : : ; z1;11 ; z1k i=1

(1) 1

; : : : ; z1k i ; z20 ; f ℄ ( ) 1

k2f0;:::;11;k1(1) ;:::;k1(i

1)

g

(3.35)

A (3.6) formula szerint:

R1uIj (z1 ; z2 ) = = [z10 ; : : : ; z1;11 ; z1;14; z1;15 ; z1;16; z1;18 ; z1 ; z20; f ℄

Y

(3.36)

1

k2f0;:::;11g

Végül (3.7) formája:

=

X i1 +i2 =12 0ij 11; j =1;2

R2uIj (z1 ; z2 ) =

i1 Y

[z10 ; : : : ; z1i ; z1; z20 ; : : : ; z2(ui j); f ℄ (z1 1

2

+[z10 ; z1 ; z20; : : : ; z29 ; z2u;j10 ; z2u;j11; z2 ; f ℄(z1

z10 )

l=0

9 Y

k=0

(z2

iY 2 1

z1l )

(z2

k=0

z2k )(z2

z2(ukj ) )+

z2u;j10 )(z2

(3.37)

z2u;j11 ):

Most végezzük el a (3.28) szerinti tagok törlését. A (3.35) képletre:

=

X i1 +i2 12 0i1 11; 0i2 9

LI (z1 ; z2 ) =

[z10 ; : : : z1i ; z20 ; : : : ; z2i ; f ℄ 1

4 X

+ [z10 ; : : : ; z1;11 ; z1k i=1

(1) 1

2

; : : : ; z1k i ; z20 ; f ℄ ( ) 1

32

iY 1 1 k=0

(z1

z1k )

iY 2 1 l=0

(z1

z2l )+

(z1

z1k ):

Y k2f0;:::;11;k1(1) ;:::;k1(i

1)

g

(3.38)

Mivel a fenti képletben már nem szerepel új szimbólum, így máris megkaptuk a 3.

Ábra

indexhalmazához tartozó Lagrange polinomot. Az (3.36) képletben nin senek (3.28) szerint tagok, viszont vannak a (3.37) maradéktagban. Ebb®l kitörölve a megfelel® tagokat, azt kapjuk, hogy:

=

R2kIoztes (z1 ; z2 ) =

X i1 +i2 =12 0i1 11; 0i2 9

i1 Y

[z10 ; : : : ; z1i ; z1 ; z20; : : : ; z2i ; f ℄ (z1 1

2

+[z10 ; z1 ; z20; : : : ; z29 ; z2u;j10 ; z2u;j11; z2 ; f ℄(z1

z10 )

l=0

9 Y

k=0

(z2

z1l )

iY 2 1 k=0

z2k )(z2

(z2

z2k )+

z2u;j10 )(z2

(3.39)

z2u;j11 ):

Következik a (3.29) szerinti tagok helyettesítése (3.30) tagokkal. A (3.36) képletre:

R1I (z1 ; z2 ) = Y = [z10 ; : : : ; z1;11 ; z1;14; z1;15 ; z1;16; z1;18 ; z1 ; z20; f ℄ (z1 Y k2f0;:::;11g[K +[z10 ; z20; : : : ; z29 ; z2; f ℄ (z2 z2k );

z1k )+

1

(3.40)

k2f0;:::;9g

Míg a (3.39) formulát tovább alakítva:

=

R2I (z1 ; z2 ) =

X i1 +i2 =12 0i1 11; 0i2 9

i1 Y

[z10 ; : : : ; z1i ; z1 ; z20; : : : ; z2i ; f ℄ (z1 1

2

+[z10 ; z1 ; z20; : : : ; z29 ; z2; f ℄(z1

l=0

z10 )

9 Y

k=0

(z2

z1l )

iY 2 1 k=0

(z2

z2k )+

z2k ):

Végül, tehát megkaptuk az eredeti ponthalmazhoz tartozó maradéktagokat is.

33

(3.41)

4. Korlátok TDMP feladatokra

+ +

Fejezetünkben végig a TDMP feladatok azon fajtájával foglalkozunk, ahol a 1 :::s , 1 s m, momentumokon kívül ismertek az E Xj j ; j ; : : : ; mj momentumok is, ahol m mj nj ; j ; : : : ; s. Eddigi jelölésünket használva

+

(

=1

)

=1

E (Xj j ) = 0:::0 j 0:::0 ; j = 1; : : : ; s; ahol a jobb oldalon j a j -edik index. 4.1. Korlátok rendezett tartók esetén

H a (1.35) zárójelében deniált halmazt. A 3. Fejezetben bevezetett Kj fm; m + + 1; : : : ; nj g halmazokra vonatkozólag az alábbi struktúrák valamelyikének az érvényességét

Jelölje

fogjuk megkívánni:

jKj j páros

jKj j páratlan

m; u ; u + 1; : : : ; v (j ) ; v (j ) + 1 min u ; u + 1; : : : ; v ; v + 1 max m; u(j ) ; u(j ) + 1; : : : ; v (j ); v (j ) + 1; nj u(j ) ; u(j ) + 1; : : : ; v (j ) ; v (j ) + 1; nj : (j )

(j )

(j )

(j )

(j )

(j )

(4.1)

Az eddigiekben nem tételeztük fel, hogy a Z1 ; : : : ; Zs halmazok elemei rendezettek. A most következ® tételekben azonban elemeiket növekv® vagy sökken® sorrendben rendezzük el.

4.1. Tétel. Legyen zj 0 < zj 1 < < zjnj ; j = 1; : : : ; s. Tegyük fel, hogy az f (z ); z 2 Z m + 1 rend¶ osztott dieren ái nemnegatívak, továbbá, hogy a zj változója szerinti m + jKj j rend¶ osztott dieren iái is nemnegatívak, ahol Kj (4.1) valamelyik min struktúráját követi, j = 1; : : : ; s. Ekkor igaz az, hogy a (3.4) képlettel deniált LI (z1 ; : : : ; zs ) megegyezik a ZI halmazhoz tartozó, H -típusú, egyértelm¶en adott Lagrange polinommal, és teljesíti az alábbi egyenl®tlen-

függvény

séget:

f (z1 ; : : : ; zs) LI (z1 ; : : : ; zs ); (z1 ; : : : ; zs ) 2 Z: (4.2) b mátrixának I indexhalmazhoz tartozó oszlopaiból álló Eszerint, a (1.26) minimum probléma A Bb bázis duál megengedett, és E [f (X1 ; : : : ; Xs)℄ E [LI (X1 ; : : : ; Xs)℄: Ha

Bb

(4.3)

egyben primál megengedett is, akkor a (4.3) képlettel adott korlát éles.

Ha a fent említett osztott dieren iák mindegyike nempozitív, akkor (4.2) és (4.3) fordított relá iójelekkel állnak.

34

A (3.9) H -típusú Lagrange polinom egyértelm¶ségét, illetve, azt hogy Bb a (1.26) LP feladat bázisa, a következ®képp láthatjuk be. Abból, hogy (z z 1 ; : : : ; z s ) LI z b f z , z 2 ZI esetén, következik, hogy f Bb el®áll B sorainak lineáris kombiná ióiként. Mivel b mátrix nem szinguláris. ez bármilyen f függvényre, és így bármilyen f Bb vektorra igaz, ezért a B Ebb®l már következik a Lagrange polinom egyértelm¶sége. Azt, hogy a (4.2) egyenl®tlenség ekvivalens a Bb bázis (1.26) feladatbeli duál megengedettségével, a 1.2. szakaszban már levezettük. A (4.2) relá ió bizonyításához használjuk a (3.8) egyenletet. Mivel RI z1 ; : : : ; zs R1I z1 ; : : : ; zs R2I z1 ; : : : ; zs , ezért elég, ha belátjuk, hogy R1I z1 ; : : : ; zs és R2I z1 ; : : : ; zs , z1 ; : : : ; zs 2 Z esetén. Az R1I z1 ; : : : ; zs függvény (3.6) képlettel adott alakjából és Kj spe iális struktúrájából következik, hogy Y zj zjk > , ha zj 62 fzj 0 ; : : : ; zjm 1 g [ ZjKj : (4.4)

Bizonyítás.

=(

= ()

( (

)+ ( ) 0( ( )

k2f0;:::;m

)

1g[Kj

)

)

(

(

(

)

( )=

) = 0

) 0

Ha pedig zj 2 fzj 0 ; : : : ; zjm 1 g [ ZjKj , akkor a fenti szorzat elt¶nik. Mivel a feltétel szerint az f függvény zj ; j ; : : : ; s változó szerinti m jKj j rend¶ osztott dieren iái nemnegatívak, ezért R1I z1 ; : : : ; zs minden z1 ; : : : ; zs 2 Z esetén. Az R2I z1 ; : : : ; zs függvény (3.7) képletével adott összeg tagjaiban mind az osztott dieren iák, melyek teljes rendje m , mind pedig azok szorzói nemnegatívak bármely z1 ; : : : ; zs 2 Z esetén. Ebb®l következik, hogy R2I z1 ; : : : ; zs , z1 ; : : : ; zs 2 Z , ami egyenérték¶ a (4.2) relá ióval. Ebb®l viszont (4.3) relá ió érvényessége közvetlenül adódik. Végül, ha Bb egyszerre primál és duál megengedett bázisa a (1.26) problémának, akkor ez optimális bázis, és élfüggvény értéke az alábbi:

(

=1 ) 0 )

(

(

+1

)

(

+

) 0 (

minE [f (z1 ; : : : ; zs )℄ = = fBTb pBb = fBTb Bb 1bb = = fBTb Bb 1E [bb(X1 ; : : : ; Xs)℄ = = E [fBTb Bb 1bb(X1 ; : : : ; Xs)℄ = = E [LI (X1; : : : ; Xs)℄:

)

(

)

2

Az következ® tétel, a fenti feltételek módosítása mellett, alsó illetve fels® korlátot szolgáltat az f z1 ; : : : ; zs , z1 ; : : : ; zs 2 Z függvény várható értékére.

(

)(

)

4.2. Tétel. Legyen zj 0 > zj 1 > > zjnj ; j = 1; : : : ; s. Tegyük fel, hogy az f (z ); z 2 Z függvény m + 1 rend¶ osztott dieren ái nemnegatívak, továbbá, hogy a zj változója szerinti m + jKj j rend¶ osztott dieren iái ugyan sak nemnegatívak, ahol Kj (4.1) valamelyik, az alábbiakban jelzett, struktúráját követi, j = 1; : : : ; s. Ekkor igazak a következ®k: 35

m + 1 páros, jKj j páros és Kj (4.1) megfelel® max struktúráját követi vagy ha m + 1 jKj j páratlan és Kj (4.1) megfelel® min struktúráját követi, akkor a (3.4) képlettel deniált LI (z1 ; : : : ; zs ) megegyezik a ZI halmazhoz tartozó, H -típusú, egyértelm¶en adott

(a) Ha

páros,

Lagrange polinommal, és teljesíti az alábbi egyenl®tlenséget:

f (z1 ; : : : ; zs ) LI (z1 ; : : : ; zs ); (z1 ; : : : ; zs ) 2 Z: Eszerint, a (1.26) minimum probléma

Bb

álló

Ha

Bb

(4.5)

Ab mátrixának I indexhalmazhoz tartozó oszlopaiból

bázis duál megengedett, és

E [f (X1 ; : : : ; Xs)℄ E [LI (X1 ; : : : ; Xs )℄:

(4.6)


m +1 páratlan, jKj j páros és Kj (4.1) megfelel® max struktúráját követi vagy ha m +1 páratlan, jKj j páratlan és Kj (4.1) megfelel® min struktúráját követi, akkor a (3.4) képlettel deniált LI (z1 ; : : : ; zs ) megegyezik a ZI halmazhoz tartozó, H -típusú, egyértelm¶en

(b) Ha

adott Lagrange polinommal, és teljesíti az alábbi egyenl®tlenséget:

f (z1 ; : : : ; zs ) LI (z1 ; : : : ; zs ); (z1 ; : : : ; zs ) 2 Z: Eszerint, a (1.26) maximum probléma álló

Ha

Bb

Bb

(4.7)



E [f (X1 ; : : : ; Xs)℄ E [LI (X1 ; : : : ; Xs )℄:

(4.8)


Bizonyítás.

Bizonyításunkat az (a) pont els® feltételei szerint mondjuk el, a többi állítás ugyanígy igazolható. A 4.1. Tétel bizonyításában már beláttuk, hogy Bb bázisa az (1.26) LP feladatnak. Azt is tisztáztuk, hogy (4.5) ekvivalens a Bb bázisnak az (1.26) minimum feladatra vonatkozó duál megengedettségével. Lényegében sak (4.5) bizonyítására van szükség, mivel egyrészt (4.6) triviális következménye a (4.5) egyenl®tlenségnek, másrészt (4.6) esetén a korlát élességére tett megjegyzés igazolása b egyúttal primál megengedett is) a 4.1. Tétel bizonyításában szerepl® úton véghezvi(mikor B het®. Egész pontosan, belátjuk, hogy R1I z és R2I z minden z z 1 ; : : : ; zs 2 Z esetén. R1I z nemnegatívitása abból következik, hogy R1I z tagjai nemnegatív osztott differen iák illetve az alábbi képlet szorzatai: Y zj zjk : (4.9)

()

()

k2f0;:::;m

0

1g[Kj

36

()

(

)

0 ()

=(

)

m + 1 páros, így igaz az alábbi egyenl®tlenség:

Mivel

Y

k2f0;:::;m

A (4.10) szorzat elt¶nik, ha zj het®en, zj 2 ZjKj esetén:

(zj

zjk ) 0:

(4.10)

2 fzj0; : : : ; zjm 1g. Másrészt, Kj spe iális struktúrájának köszönY k2Kj

Tehát

1g

(zj

zjk ) 0:

(4.11)

R1I (z1 ; : : : ; zs ) 0 minden (z1 ; : : : ; zs ) 2 Z

esetén. R2I z nemnegatívitása abból következik, hogy minden egyes tagja nemnegatív osztott dieren iák illetve páros számú zj zjk alakú tényez® szorzata. Így, R2I z1 ; : : : ; zs minden z1 ; : : : ; zs 2 Z esetén. 2 Következ® tételünkben az alábbi jelöléseket használjuk: I I0 [ [sj=1 Ij ; ahol I0 f i1 ; : : : ; is j ij egész; nj ij m ; j ; : : : ; s; n1 i1 ns is mg;

(

() )

0

= = ( ) Ij = f(i1 ; : : : ; is)j (nj

A

ZI

(

0

1 =1

) 0

+ +

ij ) 2 Kj ; il = 0; l 6= j g; j = 1; : : : ; s:

(4.12)

alappontrendszerhez tartozó Lagrange polinom:

X i1 +:::+is m 0ij m 1; j =1;:::;s Kj j s jX X z1n1 z(j j =1 ij =1

;;

LI (z1 ; : : : ; zs ) =

h

z1n ; : : : ; z1(n 1

1)nj

1

1

i1 )

; ; zsn ; : : : ; zs(n

; zjn ; : : : ; zj(m j

nj Y m+1 k=0

(zj

s

1)

; zj (nj

zjk )

is )

;f

(zj

zj (nj

kj(l) )

nj Y

j =1 k=nj ij +1

kj(1) ) ; : : : ; zj (nj kj(ij ) )

iY j 1 l=1

s

s iY

(zj

zjk ) +

; z(j+1)n ; ; zsn ; f j +1

s

): (4.13)

4.3. Tétel. Legyen zj 0 < zj 1 < < zjnj ; j = 1; : : : ; s. Tegyük fel, hogy az f (z ); z 2 Z m + 1 rend¶ osztott dieren ái nemnegatívak, továbbá, hogy a zj változója szerinti m + jKj j rend¶ osztott dieren iái ugyan sak nemnegatívak, ahol nj Kj (4.1) valamelyik, az alábbiakban jelzett, struktúráját követi, j = 1; : : : ; s. Ekkor igazak a következ®k:

függvény

m + 1 páros, jKj j páros és nj Kj (4.1) megfelel® max struktúráját követi vagy ha m + 1 páros, jKj j páratlan és nj Kj (4.1) megfelel® min struktúráját követi, akkor

(a) Ha

37

a (3.4) képlettel deniált

LI (z1 ; : : : ; zs )

megegyezik a

ZI

halmazhoz tartozó,

H -típusú,

egyértelm¶en adott Lagrange polinommal, és teljesíti az alábbi egyenl®tlenséget:

f (z1 ; : : : ; zs ) LI (z1 ; : : : ; zs ); (z1 ; : : : ; zs ) 2 Z: Eszerint, a (1.26) minimum probléma

Bb

álló



E [f (X1 ; : : : ; Xs)℄ E [LI (X1 ; : : : ; Xs )℄: Ha

Bb

(4.14)

(4.15)


m +1 páratlan, jKj j páros és nj Kj (4.1) megfelel® max struktúráját követi vagy ha m + 1 páratlan, jKj j páratlan és nj Kj (4.1) megfelel® min struktúráját követi, akkor a (3.4) képlettel deniált LI (z1 ; : : : ; zs ) megegyezik a ZI halmazhoz tartozó, H -típusú,

(b) Ha

egyértelm¶en adott Lagrange polinommal, és teljesíti az alábbi egyenl®tlenséget:

f (z1 ; : : : ; zs ) LI (z1 ; : : : ; zs ); (z1 ; : : : ; zs ) 2 Z: Eszerint, a (1.26) maximum probléma álló

Bb



E [f (X1 ; : : : ; Xs)℄ E [LI (X1 ; : : : ; Xs )℄: Ha

Bb

(4.16)

(4.17)


b bázis, a szokásos úton látható be. Egyébként pedig tételünk a Az, hogy B 4.2. Tétel következménye, sak fel kell serélnünk a zj (nj 0) ; zj (nj 1) ; : : : ; zj (nj nj ) jelöléseket a zj 0 ; zj 1 ; : : : ; zjnj jelölésekkel, j ; : : : ; s illetve z1 ; : : : ; zs 2 Z . 2 Mint az el®z®ekben is utaltunk rá, a függvény várható értékének éles alsó (fels®) korlátait a megfelel® TDMP minimum (maximum) probléma optimális élfüggvény értéke szolgáltatja. A TDMP feladatot megoldhatjuk duál szimplex algoritmussal. Ebben az esetben a fenti állításokban szerepl® duál megengedett bázisok, azontúl, hogy korlátokat szolgáltatnak a függvény várható értékére, a duál algoritmus kezdeti bázisaiként is nagy segítséget nyújthatnak. Egy kezdeti duál megengedett bázis ismerete két lényeges el®nnyel is jár: egyrészt a duál algoritmus els® fázisának elhagyásával megtakarítjuk a futási id® körülbelül felét, másrészt a kevesebb m¶velet miatt a numerikus pontosság is jobb lesz. Befejezésül, nézzünk egy-egy példát alsó illetve fels® korlátokat szolgáltató Lagrange polinomokra a kétdimenziós esetben.

Bizonyítás.

=1

(

38

)

4.1. Példa.

f (z1 ; z2 ); z1 2 Z1 ; z2 2 Z2 függvény 3 rend¶ osztott dieren ái zj változója szerinti 5 rend¶ osztott dieren iái ugyan sak Ebben az esetben (m = 2, jK1 j = jK2 j = 3) a 4.1. Tétel a következ®

Tegyük fel, hogy az

nemnegatívak, továbbá, hogy a nemnegatívak,

j

= 1; 2.

fajta, alulról közelít® Lagrange polinomot adja:

LI (z1 ; z2 ) = = [z10 ; z20 ; f ℄ + [z10 ; z11 ; z20 ; f ℄(z1 z10 )+ +[z10 ; z20 ; z21 ; f ℄(z2 z20 )+ +[z10 ; z11 ; z20 ; z21; f ℄(z1 z10 )(z2 z20 )+ +[z10 ; z11 ; z12 ; z20; f ℄(z1 z10 )(z1 z11 )+ +[z10 ; z11 ; z12 ; z1i; z20 ; f ℄(z1 z10 )(z1 z11 )(z1 z12 )+ +[z10 ; z11 ; z12 ; z1i; z1(i+1) ; z20; f ℄(z1 z10 )(z1 z11 )(z1 z12 )(z1 z1i)+ +[z10 ; z20 ; z21 ; z22; f ℄(z2 z20 )(z2 z21 )+ +[z10 ; z20 ; z21 ; z22; z2k ; f ℄(z2 z20 )(z2 z21 )(z2 z22 )+ +[z10 ; z20 ; z21 ; z22; z2k ; z2(k+1) ; f ℄(z2 z20 )(z2 z21 )(z2 z22 )(z1 z2k ): Ugyanekkor a 4.3.

(4.18)

Tétel (b) részének segítségével az alábbi, felülr®l közelít® Lagrange

polinomot kapjuk:

LI (z1 ; z2 ) = = [z1n ; z2n ; f ℄ + [z1n ; z1(n 1) ; z2n ; f ℄(z1 z1n )+ +[z1n ; z2n ; z2(n 1) ; f ℄(z2 z2n )+ +[z1n ; z1(n 1); z20 ; z2(n2 1) ; f ℄(z1 z1n )(z2 z2n )+ +[z1n ; z1(n 1); z1(n 2) ; z2n ; f ℄(z1 z1n )(z1 z1(n 1) )+ +[z1n ; z1(n 1); z1(n1 2) ; z1i; z2n ; f ℄(z1 z1n )(z1 z1(n 1) )(z1 z1(n 2) )+ +[z1n ; z1(n 1); z1(n 2) ; z1i ; z1(i+1) ; z2n ; f ℄(z1 z1n )(z1 z1(n 1) )(z1 z1(n +[z1n ; z2n ; z2(n 1) ; z2(n 2) ; f ℄(z2 z2n )(z2 z2(n 1) )+ +[z1n ; z2n ; z2(n 1) ; z2(n2 2) ; z2i; f ℄(z2 z2n )(z2 z2(n 1) )(z2 z2(n 2) )+ +[z1n ; z2n ; z2(n 1) ; z2(n 2) ; z2k ; z2(k+1) ; f ℄(z2 z2n )(z2 z2(n 1) )(z2 z2(n 1

1

2

2

1

1

1

1

1

1

1

1

1

2

1

1

2

2

2

1

2

1

1

2

1

1

2

2

1

2

2

1

2

2

1

1

1

2

2

2

1

1

1

2)

)(z1

z1i )+

)(z2

z2k ):

2

2

2

2

2

2

Ha a (4.18), (4.19) polinomokban a

1

z 1 ; z2

változókat az

2

X1 ; X2

2

2)

(4.19)

valószín¶ségi változókkal

helyettesítjük, és vesszük a nyert valószín¶ségi változók várható értékét, akkor alsó és fels® korlátokat kapunk

E [f (X1 ; X2 )℄ értékére.

Az

X1 ; X2 valószín¶ségi változók fent említett polinomjai

várható értékét könnyen megkaphatjuk, ha ismerjük az

E (Xjk ); k = 1; 2; 3; 4; j = 1; 2 momentumokat és a

Cov (X1 ; X2 ) kovarian iát. 39

4.2. Egy dekompozí iós eljárás

=1

A 4.1. szakasz tételeiben az I0 illetve Ij ; j ; : : : ; s indexhalmazok rögzítettek voltak, viszont a Kj ; j ; : : : ; s halmazok megválasztásában volt némi szabadságunk. Ez azt jelenti, hogy általában mind a minimum, mind a maximum problémához több duál megengedett bázist találtunk, melyek mindegyike korlátot szolgáltat a élfüggvény értékére. A következ®kben bemutatunk egy módszert, mely segítségével egyszer¶bben találhatjuk meg ezek közül a legszorosabb korláthoz tartozókat. Els® lépésként, a Z halmazra illetve a élfüggvényre tett, az általánosságot nem megszorító, feltételek mellett, a változók (oszlopok) megfelel® rendezésével a (1.21) feladatot megfelel® alakra hozzuk. Az így kapott struktúra, azon túl, hogy feltárja a feladat szerkezetét, alkalmas lesz egy egyszer¶bb dekompozí iós eljárás bevezetésére is, mely lényege hogy a legoptimálisabb struktúrához tartozó Kj ; j ; : : : ; s halmazokat egymástól függetlenül, kisebb feladatokon keresztül találja meg. Az említett feltételek a következ®k:

=1

=1

és

zj 0 = 0; j = 1; : : : ; s

(4.20)

f (z10 ; : : : ; zs0 ) = 0:

(4.21)

Könnyen látható, hogy ezek nem jelentenek megszorítást, mivel bármely feladat átkonvertálható egy, a fentieknek megfelel® ekvivalens alakra. Egyrészt, az (4.20) feltételnek megfelel®

regi f uj (z ) = f regi (z1 + z10 ; : : : ; zs + zsr0egi ) regi függvény a régivel megegyez® konvexitású marad a Z uj = Z regi (z10 ; : : : ; zsr0egi ) tartományon,

és ugyanazt a élfüggvényértéket adja a fenti eltolásnak megfelel®en átkonvertált momentumok esetén. Másrészt, a (4.21) egyenl®séget kielégít®

f uj (z ) = f regi (z ) f regi (z10 ; : : : ; zs0 )

=1

függvényt eltolással kaptuk, így gyelembe véve, hogy eT p , a megfelel® élfüggvényérték pontosan a konstans f regi z10 ; : : : ; zs0 értékkel lesz kisebb bármely megoldás esetén. A következ®kben a 4.1. Tétel szerinti (minimum feladathoz tartozó) bázisstruktúrák szerint fogunk továbbhaladni, de eljárásunk az el®z® szakasz bármely tételére hasonlóan alkalmazható. Célunk azon Kj halmazrendszer megtalálása, mely a (4.3) egyenl®tlenségben a leger®sebb be slést adja, i.e., melyre az E LI X1 ; : : : ; Xs várható érték a legnagyobb lesz. Képletekkel felírva ez pontosan az alábbi problémát jelenti:

(

)

[ (

)℄

max f p T

feltéve, hogy

= bb p 2 a 4.1. Tétel szerinti bázismegoldásoknak.

Abp

40

(4.22)

A feladat megfelel® alakba történ® átírásához tekintsük az alábbi index halmazokat:

I0int = f(i1 ; : : : ; is )j 1 ij m 1; egész, j = 1; : : : ; s; i1 + + is mg ; Ijaxes = f(i1 ; : : : ; is )j 1 ij nj ; egész; il = 0 l 6= j eseténg

(4.23)

Ha átrendezzük az (4.22) feladat oszlopait és sorait a fenti indexhalmazok szerint, akkor a következ®, jobban áttekinthet® szerkezethez jutunk:

f : T

Ab :

ZI1axes

ZI2axes

0 1

0

0

z}|{

z}|{

fI

2

fI

fI

11

11

11

11

0

0

AbII int

1

z11 : : : z1n .. bI axes .. .AI axes . m z11 : : : z1mn

1

1 1

0

1 1


2

2 2

2

.. .

0

0

0

0

k

[

T axes 1

T axes

[ 2

(pI )B T axes 2

.. .

0

.. .

pI

0:::0 10:::0

axes

..

0

1

11

1

AbII int

0

T axes

bb

0

0

0

pI

z}|{

T int

zs1 : : : zsns .. bIsaxes .. .AIsaxes . m ms zs1s : : : zsn s

.. .

a tobbi oszlop

m 0:::0 01:::0

=1 I

axes

I

axes

1

1

.. .

pB : (p0)B (pI )B T

2 2

T axes s

.. .

p0

0 z}|{

fI

0

T

z}|{

T axes

T axes

1

p :

ZIsaxes

ZI int

.

pI

T axes s

[

0

.. .

0

k

0:::01

I

axes s

int

0

0

0

2

I

int

0

T int

2

.. .

0:::0ms

AbII int

pI

0m :::0 .. .

AbII

axes s int

(pI )B (pI )B T axes s

.. .

axes

2

0

T int 0

(4.24) Az (4.24) feladat felírása során sor került új jelölések bevezetésére, melyek további érveléseinkben is segítségünkre lesznek. Egyrészt, az alábbi elveket követjük: az alsó index a mátrixban részt vev® oszlopokat jelöli, míg a fels® index a sorokra utal. Ezentúl (lásd majd kés®bb), ha az indexben a sorok negatív el®jellel szerepelnek, az azt jelenti, hogy minden más sor részt vesz a mátrixban, kivéve ezek. 41

Másrészt, különösen fontos, és talán némi magyarázatra szorul az utolsó két sor. Esetünkben

sak a bázisváltozók komponenseit tartalmazza. A 4.1. tételbeli bázisstruktúrából következ®en pT utolsó blokkjához nem tartozik bázisváltozó, így az itteni értékek nullák lesznek. A másik fontos megjegyzés az a tény, melyre a pTB és a pT sorai viszonyában függ®leges egyenl®ségjelekkel utaltunk, hogy p0:::0 és pI0int minden változója egyben bázisváltozó is, bármely tételbeli bázismegoldás esetén. Kihasználva, hogy egy 4.1. tételbeli p bázismegoldás utolsó blokkja supa nulla értékeket vesz fel, a (4.24) struktúrát tovább egyszer¶síthetjük:

p egy megfelel® bázismegoldást jelöl, míg pB

0 1 0

ZI int

fI

fI

11

11

11

0

0

AbII int

ZI2axes

fI

fI

T axes 2

11

z}|{

z}|{

0

ZIsaxes

ZI1axes T axes 1


1

1 1

1

0

0

1 1


2

2 2

2

2 2

.. .

.. .

0

0

0

I

pI

T axes 2

0

..

0

1

axes

1

AbII int

0

T axes

bb

0

0

0

pI

T int

.. .

p0

T axes s

0 z}|{

0:::0 10:::0 .. .

m 0:::0 01:::0

=1 I

axes

I

axes

1

1

.. .

.. .

z}|{

.

axes

2 0

zs1 : : : zsns axes .. bIsaxes .. AbIIsint .AIsaxes . ms zsm1s : : : zsn s 0

0 pI

T axes s

AbII int int

0 0

.. .

0m :::0

2

(4.25)

2

.. .

0:::01 .. .

0:::0ms

I

I

axes s

int

0

pI

T int 0

Mivel az AbI0int minor négyzetes mátrix, és mivel sak az ® oszlopai szerepelnek I0int bázisbeli 0 el®állításában, így függetlenül a tengelyekhez tartozó bázisoszlopok megválasztásától (i.e., a Kj halmazok megválasztásától), a pI0int vektor egyértelm¶en adott az alábbi egyenl®ség által: int 1 pI0int AbII0int I0int : (4.26) int

=

0

42

Ezáltal, tekintve, hogy pI0int konstans, a (4.22) feladatot az alábbi alakba írhatjuk át: 0 konstans 1 z }| { C f T(0;I1axes;:::;Isaxes) p(0;I1axes;:::;Isaxes) B f TI0 int pI0 int A

+

max

feltéve, hogy

Ab(0;I axes ;:::;Isaxes ) p(0;I axes ;:::;Isaxes ) 1

p(0;I

1

1

axes

;:::;Is axes )

= bb =

AI int pI int = bb1 0

(4.27)

0

egy 4.1. Tétel szerinti bázismegoldás megfelel® komponenseivel. A feladat mátrixalakja az alábbi: ZI1axes

ZI2axes

0

fI

1

11

0

0

T

axes

1


fI

2

fI

11

11

0

0

I

0

I

..

.. .

1

1

0

0

1 1


2

2 2

2

2 2

T

axes s

.. .

.. .

0

0

0

zs1 : : : zsns .. bIsaxes .. .AIsaxes . m ms zs1s : : : zsn s

0

0

0

0

p0

pI

T axes 1

b 1

z}|{

T axes

1

1

ZIsaxes

z}|{

z}|{

.. .

pI

T

axes

2

.

1T pI0 int

0:::0 axes

AbII int pI int

axes

AbII int pI int

axes

1

1

0

0

axes

2

2

0

0

(4.28)

.. .

I

axes s

I

AbIIsint pI int axes

0

0

AbII int pI int = 0 int

int

0

0 0

0

pI

T axes s

A fenti feladatban az I0int indexekhez tartozó sorokban már sak supa nulla szerepel, ezért 43

ezeket elhagyjuk. Az így kapott, továbbra is ekvivalens, feladatot a következ®képp írhatjuk fel:

max f (0;I T

feltéve, hogy

1

axes

;:::;Is axes ) p(0;I1 axes ;:::;Is axes )

) Ab((0I;I axes ;:::;Is axes ) p(0;I axes ;:::;Is axes ) int

0

1

p(0;I

1

1

axes

;:::;Is axes )

= bb(1 I =

int )

(4.29)

0

egy 4.1. Tétel szerinti bázismegoldás megfelel® komponenseivel.

(

)=0

Mivel az (4.21) feltétel szerint f z10 ; : : : ; zs0 , másrészt mivel Ab els® oszlopának sak a legels® komponense nem t¶nik el, így a korlátozó feltételeket érdemes az alábbi módon soportosítani: ZI1axes

ZI2axes

0

fI

fI

T axes 2

fI

1

11

11

11

0


0

0

b 1I

0

axes

I2

..

.. .

0

T axes 1

1

1

1

1

0

0

.. .

.. .

0

0

ZIsaxes

z}|{

z}|{

1 1


2

2

2

2

.. .

2 2

0

.

z}|{

T axes s

zs1 : : : zsns .. bIsaxes .. .AIsaxes . ms zsm1s : : : zsn s

bb(1

I0int )

b 1 0 axes

1

b1

.. .

b 1I

axes s

p0 pTI axes pTI axes pTIsaxes Látható, hogy p0 megválasztásától nem függ a élfüggvényérték, másrészt, hogy p0 1

(4.30)

2

sak a (4.30) felírásban külön vett, els® feltételben vesz részt. Ezeket gyelembe véve, feladatunkat optimalizálhatjuk sak az I1 ; : : : ; Is indexekhez tartozó változókon, majd p0 értékét utána szá-

44

moljuk ki, az els® sorban szerepl® korlátozó feltételnek megfelel®en. i.e.,

max f (I T

feltéve, hogy

1

axes

;:::;Is axes ) p(I1 axes ;:::;Is axes )

= bb1( I 0) = (bb1 )0 (1; : : : ; 1) p(I =

0) Ab((I Iaxes ;:::;I axes ) p(I axes ;:::;I axes ) s s p0

int

int

0

0

1

1

pI

1

axes

;:::;Is

T

axes )

1

axes

;:::;Is

(4.31) axes )

egy 4.1. Tétel szerinti bázismegoldás megfelel® komponenseivel. Írjuk fel (4.31) els® korlátozó feltételét illetve a élfüggvényt mátrix alakban, úgy hogy a supa nullából álló minorokat kihagyjuk: ZI1axes

ZI2axes

fI

fI

ZIsaxes

z}|{

z}|{

T axes

T axes

1

2


z}|{

fI

T axes s

1

1

1 1


2

2

2

pI

2 2

pI

T axes

T axes

1

2

..

.

zs1 : : : zsns .. bIsaxes .. .AIsaxes . ms zsm1s : : : zsn s

Látható, hogy a (4.31) feladat ezen része szétesik részfeladatra: feltéve, hogy

T axes j

pI

AbIIjj axes pIj axes axes

pI

j

0)

b 1I

axes

b 1I

axes

2

2

max f I

I0int

1

1

1

bb1(

axes

j

(4.32)

.. .

b 1I

axes s

pI

T axes s

s

darab alábbi alakú, egymástól független

axes

= bbI1 =

axes j

(4.33)

egy 4.1. Tétel szerinti bázismegoldás megfelel® komponenseivel. 45

j = 1; : : : ; s.

Vegyük észre, hogy az utolsó korlátozó feltétel azt jelenti, hogy a pIj axes vektorban szerepl® bázisváltozók indexeinek egyrészt a (3.2) által deniált I0 halmazba (annak a tengelyt tartalmazó részébe), másrészt egy, a (3.3) által deniált, Kj által meghatározott Ij halmazba kell esnie. Így, megfejtve a (4.22) feladat szerkezetét, kihasználva, hogy a tengelyeken egymástól függetlenül kereshetjük meg a legjobb bázismegoldást, máris adódik a dekompozi iós eljárás. Metódusunk, pontosabban leírva a következ®: int 1 (i) Az (4.26) egyenl®ség alapján tudjuk, hogy pI0int AbII0int I0int .

=

(ii) Az (4.27) feladatban szerepl® dení ió szerint, bb 1 feladatok könnyen felírhatók.

=1

0

= bb

AbI int pI int . 0

0

Innen már az (4.33)

(iii) Minden j ; : : : ; s értékre megoldjuk az (4.33) problémát. Az optimális megoldásokat opt jelölje pIj axes ; j ; : : : ; s.

=1

(iv) Az (4.31) feladatból, popt 0

= (bb1 )0 (1; : : : ; 1) popt (I T

1

axes

;:::;Is axes ) .

(v) A többi változó értéke nulla, így máris megkaptuk (4.22) optimális megoldását:

(popt) = (p0; (popt (I T

1

axes

;:::;Is axes )

4.3. További duál megengedett bázisok,

) ; 0): T

algoritmusok és korlátok a

kétváltozós esetre

A kétváltozós esetben, az alább bemutatandó módszer segítségével, a (1.26) feladathoz jóval több duál megengedett bázisstruktúra található. Ezek segítségével általában jobb be slések kaphatók a 4.1. szakasz korlátainál. A továbbiakban eltekintünk az X1 ; X2 valószín¶ségi változók tartóinak rendezettségét®l, supán azt tesszük fel, hogy mind a Z1 fz10 ; : : : ; z1n1 g, mind a Z2 fz20 ; : : : ; z2n2 g halmaz különböz® elemekb®l áll. Az átláthatóság kedvéért, újra felírjuk a (3.4) Lagrange polinomot,illetve a maradéktag

=

=

46

(3.6), (3.7) képleteit az

= jX K1 j

s = 2 esetre: LI (z1 ; z2 ) =

X i1 +i2 m 0ij m 1; j =1;2

+ [z10 ; : : : ; z1(m i=1 jX K2 j

1)

1

2

; z1k ; : : : ; z1k i ; z20 ; f ℄

+ [z10 ; z20 ; : : : ; z2(m i=1

[z10 ; : : : z1i ; z20 ; : : : ; z2i ; f ℄ (1) 1

1)

( ) 1

j =1 k=0

( ) 2

Y

k2f0;:::;m 1;k2(1) ;:::;k2(i

=

X i1 +i2 =m 0ij m 1; j =1;2

1

1)

; Z2K ; z2 ; f ℄ 2

R2I (z1 ; z2 ) =

Y

k2f0;:::;m Y 1g[K1 k2f0;:::;m

+[z10 ; z1 ; z20; : : : ; z2(m

2

1)

; z2 ; f ℄(z1

i1 Y

l=0

z10 )

1)

(z1

z1k )+

(z2

z2k );

g

1)

(z1 (z2

g

z1k )+ z2k );

1g[K2

[z10 ; : : : ; z1i ; z1 ; z20; : : : ; z2i ; f ℄ (z1 1

zjk )+

k2f0;:::;m 1;k1(1) ;:::;k1(i

R1I (z1 ; z2 ) = 1) ; Z1K ; z1 ; z20 ; f ℄

= [z10 ; : : : ; z1(m +[z10 ; z20 ; : : : ; z2(m

(zj

Y

; z2k ; : : : ; z2k i ; f ℄ (1) 2

j 1 2 iY Y

mY1 k=0

z1l )

(z2

iY 2 1 k=0

(z2

z2k )+

(4.34)

(4.35)

(4.36)

z2k ):

Célunk, hogy a ZI alappontokhoz tartozó Lagrange polinom, i.e., (4.34), kielégítse a következ® feltételek valamelyikét:

LI (z1 ; z2 ) f (z1 ; z2 ); (z1 ; z2 ) 2 Z

(4.37)

illetve

LI (z1 ; z2 ) f (z1 ; z2 ); (z1 ; z2 ) 2 Z: (4.38) Az (4.37) ((4.38)) képlet teljesüléséhez elégséges, ha R1I (z1 ; z2 ) 0 és R2I (z1 ; z2 ) 0 (R1I (z1 ; z2 ) 0 és R2I (z1 ; z2 ) 0), minden (z1 ; z2 ) 2 Z esetén. R1I (z1 ; z2 ) együtthatói m + jKj j rend¶, míg R2I (z1 ; z2 ) együtthatói m + 1 rend¶ osztott dieren iák. Feltesszük, hogy ezek nemnegatívak. Ez azt jelenti, hogy a (4.37) ((4.38)) feltétel teljesüléséhez úgy kell az I index halmazt megválasztani, hogy az (4.35) és (4.36) képletekben szerepl®, együttható utáni szorzatok nemnegatívak (nempozitívak) legyenek.

47

Tekintsük az alábbi

m (m + 1) méret¶ mátrixot: z10 z11 z12 z10 z11 z12 z10 z11 z20 z10 z20 z21

z1(m z1(m

2)

z2(m z2(m

4)

.. .

2)

3)

z1(m 1) z20 z2(m z2(m

3) 2)

z20 z21 (4.39)

z2(m 2) z2(m 1) ;

1

és feleltessük meg az els® m sort a (4.36) második sorában szerepl®, hozzá tartozó szorzatnak. Hasonlóan, feleltessük meg (4.39) utolsó sorát a (4.36) harmadik sorában lév® szorzatnak. Annak, hogy az R2I z1 ; z2 maradéktagot deniáló, (4.36) szorzatai nemnegatívak legyenek minden z1 ; z2 2 Z esetén, elégséges feltétele, ha (4.39) minden sorára, i.e., minden i1 ; i2 egészre, melyre i1 i2 m igaz, hogy

(

( ) + =

)

( + =

1 jfij 0 i i1 ; + jfij 0 i i2 ;

0

z1i > z1 gj z2i > z2 gj

) 1

= páros szám

0

(4.40)

(

)

minden z1 ; z2 2 Z esetén. Hasonlóan, (4.36) szorzatai nemnegatívitásának ( z1 ; z2 2 Z esetén) elégséges feltétele, ha (4.39) minden sorára, i.e., minden i1 ; i2 egészre, melyre i1 i2 m igaz, hogy

0

jfij 0 i i1; z1i > z1gj + jfij 0 i i2; z2i > z2gj = páratlan szám

(

0

(4.41)

)

minden z1 ; z2 2 Z esetén. Tekintsük el®ször azt az esetet, amikor alsó korlátot akarunk konstruálni, i.e., amikor a (4.37) feltételt akarjuk kielégíteni. Az alábbiakban bemutatunk egy algoritmust, mely a feltételnek megfelel® z10 ; : : : ; z1(m 1) z20 ; : : : ; z2(m 1) sorozatokat szolgáltat, a hozzájuk tartozó ZjKj halmazokkal együtt. Az általánosság megszorítása nélkül feltehetjük, hogy a Z1 és Z2 halmazok elemei növekv® sorrendben a következ®k: Z1 f ; ; : : : ; n1 g, Z2 f ; ; : : : ; n2 g.

;

= 01

= 01

Minimum algoritmus Algoritmus a (4.40) feltételt kielégít® z10 ; : : : ; z1(m 1) ; z20 ; : : : ; z2(m 1) sorozatok megtalálására 0. Lépés Legyen t = 0, 1 q1 m 1, L = f0; 1; : : : ; q1 g, U = fn1 ; n1 1; : : : ; n1 (m q1 2)g, V 0 = faz L és U halmazok tetsz®leges összefésüléseg = fv0; v1; : : : ; vm 1g. Ha jU j páros, akkor legyen h0 = 0, l0 = 1, u0 = n2 , ha pedig jU j páratlan, akkor legyen h0 = n2 , l0 = 0, u0 = n2 1. Ugorjunk az 1. Lépésre. 48

Megjegyzés: Az L; U; V 0 halmazok rendezett halmazok (sorozatok)! (4.39) els® sorának az els® m elemét a V 0 sorozattal tesszük egyenl®vé, míg az m -ik elem legyen h0 . 1. Lépés Ha t m, ugorjunk a 3. Lépésre. Egyébként ugorjunk a 2. Lépésre. 2. Lépés Legyen V t fv 0 ; v 1 ; : : : ; v m 1 t g, H t fh0 ; h1 ; : : : ; ht g. Ha v m 1 t 2 L, akkor legyen ht+1 lt , lt+1 lt , ut+1 ut , és ha v m 1 t 2 U , akkor legyen ht+1 ut , ut+1 ut , lt+1 lt . t t és ugorjunk az 1. Lépésre. Megjegyzés: A (4.39) mátrix t-edik sorát a V t ; H t sorozatok ilyen sorrendben történ® összelán olásával tesszük egyenl®vé. 3. Lépés Állj, a (4.39) mátrixnak mind az m sorát meghatároztuk, i.e., a t -edik sor fV t ; H tg; t ; ; : : : ; m . Írjuk fel a (1.26) probléma I0 indexhalmazhoz tartozó oszlopait reprezentáló pontokat:

+1

=

= = = +1 := + 1

=

=

=0 1

=

=

=

.. .

1

+1

1

(z10 ; z20 ); (z10 ; z21 );

=

(z11 ; z20 ); (z11 ; z21 ); .. .

(z1(m 2) ; z20 ); (z1(m 1) ; z20 ); (z1(m 2) ; z21 );

(4.42)

(z10 ; z2(m 2) ); (z11 ; z2(m 2) ); (z10 ; z2(m 1) ): Hátra van még a R1I (z1 ; z2 ) 0, (z1 ; z2 ) 2 Z feltételt kielégít® K1 és K2 halmazok megtalálása. Tegyük fel, hogy a z20 ; z21 ; : : : ; z2(m 1) sorozat megkonstruálásához a 0; 1; : : : ; q2 ; n2 ; : : : ; n2 (m q2 2) számokat használtuk fel. Ekkor a Kj elemeit a fqj +1; qj +2; : : : ; nj (m qj 1)g halmazból fogjuk kiválasztani, j = 1; 2, mivel ezeket nem használtuk (4.42) megkonstruálásakor. Mindkét

j

esetén igaz, hogy a

mY1 k=0

(zj

zjk ); (z1 ; z2 ) 2 Z

(4.43)

szorzat nem vált el®jelet, zj 0 ; : : : ; zj (m 1) konstruk iójától függ®en végig nemnegatív illetve nempozitív marad, j ; . Ha (4.43) nemnegatív, akkor a fqj ; qj ; : : : ; n j m q j g halmazt a sorrend megtartásával a fm; m ; : : : ; nj g halmazra képezve, a Kj képének (4.1) egy min struktúrájával, míg ha (4.43) nempozitív, akkor a Kj képének max struktúrával kell rendelkeznie. Készen vagyunk az I index halmazhoz tartozó duál megengedett bázis konstruk iójával. 2

=1 2 +1

+1 +2

(

1)

;

A (4.38) relá ió teljesítéséhez, i.e., fels® korlát konstruálásához a fenti, z10 ; : : : ; z1(m 1) 1) sorozatot deniáló, algoritmusnak supán némi módosítása szükséges. Így sak a 0. Lépését írjuk újra, a többi lépés változatlan marad.

z20 ; : : : ; z2(m

49

Maximum algoritmus Az (4.41) feltételt kielégít® z10 ; : : : ; z1(m 1) ; z20 ; : : : ; z2(m 1) sorozatokat megtaláló algoritmus 0. Lépése 0. Lépés Legyen t = 0, 1 q1 m 1, L = f0; 1; : : : ; q1 g, U = fn1 ; n1 1; : : : ; n1 (m q1 2)g, V 0 = faz L és U halmazok tetsz®leges összefésüléseg = fv 0 ; v 1 ; : : : ; v m 1 g. Ha jU j páratlan, akkor h0 = 0, l0 = 1, u0 = n2 , ha pedig jU j páros, akkor legyen h0 = n2 , l0 = 0, u0 = n2 1. Ugorjunk az 1. Lépésre stb. Az (1.26) feladat I0 index halmazhoz tartozó oszlopait reprezentáló pontokat a (4.42)

táblázatban találjuk. Hátra van még a megfelel® K1 és K2 halmazok megtalálása, melyekre R1I z1 ; z2 minden z1 ; z2 2 Z esetén. Kj elemeit a fqj ; qj ; : : : ; nj m qj g halmazból fogjuk választani, j ; . Fels® korlát keresésénél Kj megválasztása pont fordítva történik, mint a Minimum algoritmusnál. Ha (4.43) nemnegatív, akkor Kj megfelel® képe max struktúrát, egyébként pedig min struktúrát kell, hogy kövessen. Készen vagyunk, megkaptuk az I indexhalmazhoz tartozó duál megengedett bázis struktúrát. 2

(

(

)

+1 +2

(

1)

) 0 =1 2

01

Az általános esetben, mikor Z1 nem feltétlenül a f ; ; : : : ; n1 g és Z2 sem feltétlenül a f ; ; : : : ; n2g halmaz, a következ®képp járhatunk el. Rendezzük Z1 és Z2 elemeit növekv® sorrendbe, majd létesítsünk köl sönösen egyértelm¶ megfeleltetést (párosítást) Z1 és a f ; ; : : : ; n1 g rendezett halmaz elemei közt. Tegyük ugyanezt a Z2 és f ; ; : : : ; n2 g halmazokkal. Ezután hajtsuk végre a Minimum vagy Maximum algoritmust a f ; ; : : : ; n1 g, f ; ; : : : ; n2 g halmazokkal. Az így kapott (4.42) illetve Kj ; j ; halmazokra alkalmazva a fenti párosítást (annak inverzét) megkapjuk a megfelel® duál megengedett bázist. Látható, hogy a fenti eljárással, az el®z®ekhez képest, jóval több duál megengedett bázis (struktúra) állítható el®. Azonban, ellentétben pl. a duál módszerrel, nem áll rendelkezésünkre semmilyen egyszer¶ kritérium, mely megmondaná, hogy a fenti Minimum illetve Maximum algoritmussal kapott bázis javít-e a korláton (a élfüggvényen). Ennek ellenére, mivel a fenti konstruk ió egyszer¶ és gyors, azon túl, hogy megkapjuk a duál megengedett bázist illetve a hozzá tartozó LI z1 ; z2 Lagrange polinomot, az esetek többségében az E LI X1 ; X2 korlát is egyszer¶en számolható. Ekképpen aránylag kevés id® alatt tesztelhetünk aránylag sok duál megengedett bázist, majd ezek közül kiválasztva a legjobbat, korlátozhatjuk illetve be sülhetjük az E f X1 ; X2 értéket. Tapasztalatok szerint (lásd a következ® fejezetet), módszerünkkel meglehet®sen szoros korlátok adhatóak, a duál algoritmus lefutásánál jóval rövidebb id® alatt.

01

01 01

=12

(

[(

)

01

01

[ (

)℄

50

)℄

5. Példák, numerikus eredmények 5.1. Kétváltozós feladatok

Szakaszunk els® felében bemutatunk két példát, melyekkel egyrészt illusztráljuk a 4. Fejezetben leírtakat, másrészt a numerikus eredményeken keresztül bemutatjuk a különböz® módszerek pontosságát, hatékonyságát. Ezek után is hasonlóan járunk el, sak eltekintünk a módszerek részletes leírásától, és inkább a számszer¶ eredményekre helyezzük a hangsúlyt.

= Z2 = f0; : : : ; 9g, m = 4, m1 = m2 = 6. Alapul véve a 4.1. Tétel K1 = K2 = f4; 8; 9g halmazokat, melyek (4.1) egy min struktúráját követik, megadhatunk egy duál megengedett bázis a (1.25) minimum problémára, és egyúttal egy alsó korlátot a E [f (X1 ; X2 )℄ várható értékre, (4.3) segítségével. Bázisunk szemléletes képe

5.1. Példa.

Legyen

Z1

feltételeit, és tekintve a

a 4.(a) ábrán látható. Felhasználva a 4.3.

Tételt, az (1.25) maximum problémára ugyan sak megadhatunk egy

duál megengedett bázist, és ezzel együtt egy fels® korlátot a Legyen

K1 ; K2 ugyanaz, mint az el®bb.

9 8 7 6 5 4 3 2 1 0

Æ Æ Æ

Æ Æ Æ Æ Æ Æ

0

1


Æ Æ Æ Æ Æ Æ Æ Æ 3





= 0

várható értékre.

A bázishoz tartozó indexhalmazt a 4.(b) ábra mutatja.



9 8 7 6 5 4 3 2 1 0

9



0

1


(a)

=

E [f (X1 ; X2 )℄






Æ Æ Æ Æ Æ Æ 8

Æ Æ Æ 9

(b)

9

=4

=

=6

=

= 489

4. ábra: Z1 Z2 f ; : : : ; g. m ; m 1 m2 . K1 K2 f ; ; g. Az (a) ábra az (1.25) minimum feladat 4.1. Tétel szerint kapott duál megengedett bázisát mutatja, míg a (b) ábra az (1.25) maximum feladat 4.3. Tétel által kapott duál megengedett bázisát szemlélteti. Az I0 index halmazhoz tartozó pontokat jelöli, míg az I1 és I2 index halmazokhoz tartozókat . Tekintsük az alábbi kétváltozós függvényt,

f (z1 ; z2 ) = log [(ez +a 1

51

1)(e z +b 1) 1℄; 2

(5.1)

az következ® értelmezési tartománnyal,

ez +a > 2; e z +b > 2; 1

ahol

;

positív konstans.

2

Függvényünk a biztosítás matematikában használatos Frank-féle

függvény (lásd Bowers Jr., Hi kman, Jones and Nesbitt [1℄) némileg módosított alakja. Könnyen belátható, hogy

f 2f 3f 4f 5f > 0; 2 < 0; 3 > 0; 4 < 0; 5 > 0; : : : ; zj zj zj zj zj j = 1; 2; f 3f f < 0; 2 > 0; > 0; z1 z2 z1 z2 z1 z22 2

3

stb.

Tehát a függvény minden páros (páratlan) rend¶ deriváltja negatív (pozitív). Így, a függvény értelmezési tartományát a

Z = Z1 Z2 halmazra megszorítva, az kielégíti a = = 1; a = b = 0, másrészt

4.1. Tétel és a 4.3. Tétel feltételeit. Feltesszük, hogy egyrészt hogy az alábbi momentumok ismertek:

0 1 2 3 4 5 6 0 1 3:1855 18:5564 133:5470 1057:8635 8786:6576 74906:2014 1 3:1855 13:9179 91:0830 693:3256 2 18:5564 91:0830 623:6111 3 133:5470 693:3256 4 1057:8635 5 8786:6576 6 74906:2014 T b 1b b Az E [f (X1 ; X2 )℄ várható értékre alsó és fels® korlátot nyerhetünk, ha kiszámoljuk a f b B B ij

kifejezés értékét, ahol a lopok alkotják.

Bb

mátrix oszlopait a szakasz elején deniált két bázishoz tartozó osz-

Az alsó korlátra kapott eredmény

23:0067,

míg a fels® korlátra a

8:1465

értéket kapjuk. Korlátaink közt nagy a dieren ia, így nem alkalmasak használható be slésre. Azonban, a 4.3.

szakasz algoritmusai segítségével javithatunk a korlátokon.

A alábbiak-

ban bemutatunk egy-egy példát alsó illetve fels® korlátot szolgáltató, duál megengedett bázis megtalálására. El®ször a Minimum algoritmust futtatjuk le a következ®képp:

= 0, q1 = 1, L = ;, U = f9; 8; 7; 6g, V 0 = U , jU j páros, így h0=0, l0 = 1, u0 = 9. 2. Lépés v m 1 2 U , ezért h1 = u0 = 9, l1 = l0 = 0, u1 = u0 1 = 8. t = t + 1 = 1. 2. Lépés v m 1 2 U , ezért h2 = u1 = 8, l2 = l1 = 0, u2 = u1 1 = 7. t = t + 1 = 2. 0. Lépés

t

52

2. Lépés v m 2. Lépés v m 3. Lépés t

1 1

2 U , ezért h3 = u2 = 7, l3 = l2 = 0, u3 = u2 1 = 6. t = t + 1 = 3. 2 U , ezért h1 = u0 = 9, l1 = l0 = 0, u1 = u0 1 = 8. t = t + 1 = 1.

= 3 = m 1, ezért megállunk.

Eddig a pontig a

z10 ; z11 ; z12 ; z13

és

(4.39) szerinti elrendezésben:

A

teljes

duál

megengedett

z20 ; z21 ; z22 ; z23

9 9 9 9 bázis

8 8 8 0

7 7 0 9

6 0 9 8

értékeket deniáltuk.

Írjuk fel ®ket a

0 9 8 7:

indexhalmaz

megtalálásához

szükség

van

még

a

f0; : : : ; 5g és K2 f1; : : : ; 6g halmazokra. Legyen K1 = f0; 1; 2g, amely min struktúrát követ, és K2 = f1; 2; 6g, amely max struktúrát követ.

K1

Alább egy példa következik fels® korlátot szolgáltató duál megengedett bázis megtalálására. Futtassuk le a Maximum algoritmust.

l

0

= 1, L = ;, U = f9; 8; 7; 6g, V 0 = f9; 8; 7; 6g, jU j páros, így h0 = 9, = 0, u = 8. 2. Lépés v 3 2 U , ezért h1 = u0 = 8, l1 = l0 = 0, u1 = u0 1 = 7. t = t + 1 = 1. 2. Lépés v 2 2 U , ezért h2 = u1 = 7, l2 = l1 = 0, u2 = u1 1 = 6. t = t + 1 = 2. 2. Lépés v 1 2 U , ezért h3 = u2 = 6, l3 = l2 = 0, u3 = u2 1 = 5. t = t + 1 = 3. 3. Lépés t = m 1 = 3. Állj. 0. Lépés 0

t = 0, q1

Eredményünket a (4.39) formátumban felírva:

9 9 9 9 Legyen

8 8 8 9

7 7 9 8

6 9 8 7

9 8 7 6:

K1 = K2 = f0; 1; 5g, amely max struktúrát követ.

Az összes így kapható duál megengedett bázist megvizsgálva a legjobb alsó korlát míg a legjobb fels® korlát

8:1465 lett.

Végül, megoldjuk a feladatot a duál algoritmus segítségével is.

8:0402,

A fenti bázisok bárme-

lyikét választhatjuk kiinduló bázisnak, és elég sak a módszer második fázisát lefuttatni. Problémánkra a következ® eredményeket kaptuk:

8:06605 az éles alsó korlátra, a 6.(a) ábrán szerepl®

bázis esetén;

8:1256 az éles fels® korlátra, a 6.(b) ábrán szerepl® bázis esetén.

5.2. Példa.

Tekintsük az alábbi függvényt:

f (z1 ; z2 ) = e

z1

20

53

+

z1 z2 200

+

z1 5

;

(5.2)


9 8 7 6 5 4 3 2 1 0

0








Æ Æ Æ Æ Æ Æ 8

Æ Æ Æ

9 8 7 6 5 4 3 2 1 0

9









Æ Æ Æ Æ Æ Æ 8

Æ Æ Æ 9

(b)

(a)

= Z2 = f0; : : : ; 9g. m = 4; m1 = m2 = 6. Az (a) esetben K1 = f0; 1; 2g, K2 = = f1; 2; 6g, és az ábrázolt bázis duál megengedett az (1.25) minimum feladatra; a (b) esetben K1 = K2 = f0; 1; 5g és az ábrázolt bázis duál megengedett az (1.25) maximum feladatra. A bázisokat a 4.3. szakasz algoritmusaival kaptuk. Az I0 index halmazhoz tartozó pontokat jelöli, míg az I1 és I2 index halmazokhoz tartozókat . Z1

5. ábra:

a

z1 ; z2

0 értelmezési tartományon.

A függvény összes deriváltja pozitív a nemnegatív or-

tánsban.

Legyen Z1 = f2; 4; : : : ; 20g, Z2 = f0:5; 1; : : : ; 5g, Z = Z1 Z2 . m = 4, m1 = m2 = 6.

Az el®z® példához hasonlóan

Látható, hogy a függvény kielégíti a 4.1. és 4.3. Tételek feltételeit. Eképpen az 4. ábra bázisai duál megengedettek az (1.25) minimum illetve maximum feladatban. A következ® momentumok ismertek:

ij

0 1 2 3 4 5 6

0 1 2 3 4 5 6 1 11 154 2420 40532:8 706640 12661792 2:75 29:5928 408:6112 6353:312 9:625 102:368 1399:2232 37:8125 398:8574 158:33125 690:078125 3091:25781

A 4.1. és a 4.3. Tételek összes bázisát megvizsgálva a 4. ábra bázisai szolgáltatták a legjobb be sléseket. Alsó korlátra a

3:857 értéket,

míg fels® korlátra a

4:635 értéket

Mindkét korlát javítható a 4.3. szakasz algoritmusai segítségével.

54

kaptuk.


9 8 7 6 5 4 3 2 1 0

Æ Æ Æ Æ Æ Æ

0


1

2



Æ Æ Æ Æ Æ Æ 5




7

8


9 8 7 6 5 4 3 2 1 0

9


Æ Æ Æ Æ Æ Æ 1


= 0

3







(b)

(a)

=


9

=4

=

=6

6. ábra: Z1 Z2 f ; : : : ; g, m ; m 1 m2 . (a) az (1.25) minimum probléma optimális bázisát mutatja, míg (b) az (1.25) maximum problémáét. Bázisainkat a duál algoritmus szolgáltatta. El®ször a minimum feladathoz tartozó duál megengedett bázis megtalálását írjuk le.

l

0

= 1, L = f0; 1g, U = f9; 8g, V 0 = f0; 9; 1; 8g, jU j páros, ezért h0 = 0, = 1, u = 9. 2. Lépés v 3 2 U , ezért h1 = u0 = 9, l1 = l0 = 1, u1 = u0 1 = 8. t = t + 1 = 1. 2. Lépés v 2 2 L, ezért h2 = l1 = 1, l2 = l1 + 1 = 2, u2 = u1 = 8. t = t + 1 = 2. 2. Lépés v 1 2 U , ezért h3 = u2 = 8, l3 = l2 = 2, u3 = u2 1 = 7. t = t + 1 = 3. 3. Lépés t = m 1 = 3. Állj. 0. Lépés 0

t = 0, q1

Megvannak a

V 0 és H m

1

sorozatok. Írjuk fel a

a (4.39) mátrixot:

Legyen

K1 = K2 = f2; 5; 6g.

2 2 2 2

20 20 20 0:5

4 4 0:5 5

Z1 , Z2 rendezett halmazokból vett elemekkel

18 0:5 5 1

0:5 5 1 4:5

A bázist a 7.(a) ábra szemlélteti. A kapott korlát

Hajtsuk most végre a fels® korlátot szolgáltató algoritmust.

l

0

= f9g, V 0 = f0; 1; 9; 2g, jU j páratlan, ezért h0 = 0, = 1, u = 9. 2. Lépés v 3 2 L, ezért h1 = l0 = 1, l1 = l0 + 1 = 2, u1 = u0 = 9. t = t + 1 = 1. 2. Lépés v 2 2 U , ezért h2 = u1 = 9, l2 = l1 = 2, u2 = u1 1 = 8. t = t + 1 = 2. 2. Lépés v 1 2 L, ezért h3 = l2 = 2, l3 = l2 + 1 = 3, u3 = u2 = 8. t = t + 1 = 3. 0. Lépés 0

t = 0, q1 = 2, L = f0; 1; 2g, U

3:9122.

55

3. Lépés

t=m

1 = 3. Állj.

Eredményünket a (4.39) formátumban felírva:

2 2 2 2 Legyen

K1 = K2 = f3; 6; 7g.

4 4 4 0:5

20 20 0:5 1

6 0:5 1 5

0:5 1 5 1:5

A bázist a 7.(b) ábra szemlélteti. A kapott korlát

A feladatot duál módszerrel megoldva az alábbi eredményeket kapjuk: látra és

3:9619 a fels® korlátra.

5 4.5 4 3.5 3 2.5 2 1.5 1 0.5

Æ Æ Æ


2

4








Æ Æ Æ Æ Æ Æ

5 4.5 4 3.5 3 2.5 2 1.5 1 0.5

8 10 12 14 16 18 20 (a)

Æ Æ Æ 2

Æ Æ Æ Æ Æ Æ 4





4:0103.

3:9489 az alsó kor-





8 10 12 14 16 18 20 (b)

Z1 = f2; 4; : : : ; 20g, Z2 = f0:5; 1; : : : ; 5g. m = 4; m1 = m2 = 6. Az (a) esetben = K2 = f2; 5; 6g, és a pontok az (1.25) minimum feladat egy duál megengedett bázisát mutatják. A (b) esetben K1 = K2 = f3; 6; 7g és a pontok az (1.25) maximum feladat egy duál megengedett bázisát mutatják. Az I0 index halmazhoz tartozó pontokat jelöli, míg az I1 és I2 index halmazokhoz tartozókat .

7. ábra:

K1

A következ® három példában sak a 4.3. szakaszbeli Minimum és Maximum algoritmusok által szolgáltatott legjobb korlátokat adjuk meg.

5.3. Példa.

A feladat Prékopa, Vizvári and Reg®s [17℄ ikkéb®l származik.

Tekintsünk

40

20 elem¶ soportba osztva; az Xj valószín¶ségi változó a j -edik soportban bekövetkezett események száma, j = 1; 2, Z1 Z2 = f0; : : : ; 20g f0; : : : ; 20g.

eseményt, két

56

40 esemény közül legalább egy bekövetP (X1 + X2 1) = E [f (X1 ; X2 )℄;

Korlátot keresünk annak a valószín¶ségére, hogy a kezik, i.e.,

ahol

f (z1 ; z2 ) =

(

0; 1;

Prékopa [15℄ ikkében megmutatta, hogy ha

if

(z1; z2 ) = (0; 0)

(5.3)

különben.

m+1

páros (páratlan), akkor (5.3) összes

m+

+ 1 rend¶ osztott dieren iája nempozitív (nemnegatív). Tegyük fel, hogy az alábbi (kereszt) binomiális momentumok ismertek:

1:

soport 0 1 2 3 4 5 6

0 1:00 6:23 46:04 216:09 724:30 1848:66 3739:79:

Alkalmazva a 4.3. kapjuk:

1 1:93 3:28 31:15 186:89 794:26 2541:64

2: soport 2 3 4 5 6 4:70 12:19 41:05 127:37 317:72 31:15 186:89 794:26 2541:64 295:90 1775:41 7545:49 1775:41 10652:46 7545:49

szakasz algoritmusait az (1.30) feladatra, a következ® eredményeket

m m1 m2

4 4 4 4 6 6 6 6 6

alsó korlát

0:54074 0:78259 0:64435

fels® korlát

1 0:81423 1

A legjobb korlátokat a második esetben kaptuk, amikor is

m

= 4;

m1

=

ellenére, hogy a harmadik esetben több momentumot vettünk gyelembe.

m2

= 6,

annak

A jelenség azzal

magyarázható, hogy a második esetben van némi szabadságunk (az (4.1) struktúrán belül) a

K1 , K2 halmazok megválasztásában.

Prékopa, Vizvári and Reg®s [17℄ ikkében a minimum feladat optimális élfüggvény értéke

0:80325,

míg a maximum feladaté

0:80410

az

m = m1

= m2 = 6 esetben.

Eredményeiket a

duál módszer végrehajtásával nyerték.

=1 2

Az alábbi példában korlátokat keresünk abban az esetben, ha az Xj ; j ; valószín¶ségi változók várható értéke, szórása, ferdesége és sú sossága illetve kovarian iájuk ismert, i.e., adott az els® négy momentum illetve a Cov X1 ; X2 kovarian ia.

(

)

57

5.4. Példa. Tekintsük = Z2 = f1; : : : ; 10g. 1. eset

Feltesszük, hogy a

( 00

11

a (5.1) hasznossági függvényt. Legyen

=

= 1, a = b = 0 és Z1 =

vegyes momentumon kívül, a következ® tiszta momentumok ismertek:

= 1), 10 = 01 = 11=2; 20 = 02 = 33=2; 30 = 03 = 33; 40 = 04 = 231=5.

A kapott eredményeket az alábbiakban soroljuk fel. Az alsó korlát és fels® korlát oszlopok a 4.3. szakasz Minimum és Maximum algoritmusaival kapott értékeket, míg a min és max oszlopok a duál algoritmus által szolgáltatott eredményeket tartalmazzák.

11

Megjegyzés:

alsó korlát

fels® korlát

min

max

30:25 10:77220 10:89995 10:7761 10:89184 35 10:77218 10:89995 10:77590 10:88837 25 10:77224 10:89995 10:8224 10:89191 2 Az els® sorban 11 = 30:25 = (11=2) = 01 10 , tehát a két valószín¶ségi változó

korrelálatlan. 2. eset

= 1), 10 = 01 = 2615937=625000, 20 = 02 = 5435467=500000, 30 = 03 = 108634563=5000000, 40 = 04 = 162205043=5000000, 11 = 2615937=625000.

Most azt tesszük fel, hogy ( 00

A következ® eredményeket kapjuk: alsó korlát

5.5. Példa. a

8:00326

fels® korlát

min

8:1915

max

8:05739 8:1590

Végül, tekintsük az alábbi függvényt:

f (z1 ; z2 ) = e

z1

10

z

+ 102 +

z1 z2 200

;

Z1 Z2 = f0; : : : ; 20g f0; : : : ; 20g tartón. A következ® hatvány momentumok ismertek: ij 0 1 2 3 4 5 6 0 1:00 6:23 98:31 1579:01 25813:23 429472:13 7269694:11 1 1:93 3:28 65:58 1311:52 26229:7 524590 2 11:33 65:58 1311:48 26229:5 524590 3 103:27 1311:52 26229:5 524590 4 1491:77 26229:7 524590 5 27107:8 524590

6 528938

Eredményeink az alábbiak:

m m1 m2

alsó korlát

3 6 6 6:000222 4 6 6 6:003941 58

fels® korlát

6:004789 6:00455:

5.2. Egy többváltozós hasznossági függvény

Tekintsük a (5.1) kétváltozós függvény, az alábbiakban felírt, többváltozós általánosítását: h i u z1 ; : : : ; zs log k e1 z1 +a1 es zs+as ; (5.4)

(

)=

(

1) (

1) 1

1

ahol k ; 1 ; : : : ; s pozitív, a1 ; : : : ; as pedig nemnegatív állandók, a függvény értelmezési tartománya pedig a o n z1 ; : : : ; zs jei zi +ai > ; i ; : : : ; s (5.5) D

= (

)

2 =1

halmaz. Nyilvánvaló, hogy az u z1 ; : : : ; zs függvény az értelmezési tartományában mindegyik változója szerint (mint egyváltozós függvény) szigorúan növekv®. Nem nyilvánvaló, de igaz az az állítás is, hogy az (5.4) függvény az értelmezési tartományában konkáv. Ugyan sak igaz az alábbi

(

5.1. Tétel.

Minden

)

z 2 D esetén fennáll, hogy i ++is u > 0; z1i zsis 1

1

illetve

ha

i ++is u < 0; z1i zsis

i1 + + is páratlan,

1

1

ha

i1 + + is páros.

A konkávitás illetve a tétel bizonyítása Nagy és Prékopa [9℄ ikkében található. A fentiek egyrészt azt jelentik, hogy a (5.4) függvény teljesíti a hasznossági függvényekre jellemz® tulajdonságokat, másrészt pedig a 5.1. Tétel szerint a függvény véges diszkrét halmazok Des artes szorzatára való megszorításai megfelelnek a 4.1. és a 4.3. Tételekben szerepl® feltételeknek. Az alábbiakban numerikus korlátokat mutatunk be az u X1 ; X2 ; X3 várható értékére, ahol X1 ; X2 ; X3 diszkrét valószín¶ségi változók. A vizsgálandó élfüggvény illetve a hozzá tartozó értelmezési tartomány (egyben az X1 ; X2 ; X3 véletlen vektor tartója) a következ®: h i

(

u(z1 ; z2 ; z3 ) = log

)

( ) (e z +a 1)(e z +a 1)(e z +a 1) 1 (z1 ; z2 ; z3) 2 Z; 1 1

1

2 2

2

3 3

3

ahol

Z = (0; 1; 2; 3; 4; 5; 6; 7; 8; 9) (0; 1; 2; 3; 4; 5; 6; 7; 8; 9) (0; 1; 2; 3; 4; 5; 6; 7; 8; 9): Tegyük fel, hogy ej zj +aj

> 2; j = 1; 2; 3; (z1 ; z2 ; z3 ) 2 Z 59

esetén.

(5.6)

=123

Tekintve a 4.1. és a 4.3. Tételeket, adott m, mj , j ; ; , páros számok esetén a (5.6) függvénnyel vett TDMP problémák közül mind a maximum mind a minimum feladathoz találhatóak duál megengedett bázisok. Ezt kihasználva, a következ® konkrét példák megoldásában elég sak a duál algoritmus második fázisát lefuttatni, (például) az alábbi kiinduló bázisokkal. Minimum feladat esetén az

f(i1 ; i2; i3 )ji1 + i2 + i3 m vagy ik = 0; k 6= j; m ij mj ; j = 1; : : : ; sg

(5.7)

változókhoz tartozó oszlopokkal, míg maximum feladat esetén az

f(i1 ; i2; i3 )ji1 + i2 + i3 27 m vagy ik = 9; k 6= j; 9 m ij 9 mj ; j = 1; : : : ; sg

(5.8)

változókhoz tartozó oszlopokkal.

5.6. Példa.

Tekintsük a (5.6) függvényt az

feltételeink jobb oldalán pedig álljanak a

1 = 2 = 3 = a1 = a2 = a3 = 1 esetre.

Korlátozó

ZI tartójú egyenletes eloszlás megfelel® momentumai.

Ha a vegyes momentumok közül sak a kovarian iákat vesszük gyelembe, akkor a tiszta momentumok maximális rendjét®l függ®en a következ® eredményeket kapjuk:

m m1 m2 m3

2 2 2 2

2 4 6 8

2 4 6 8

2 4 6 8

Minimum

1. táblázat: Lépés Maximum

16:083862403 93 16:236742070 124 16:265375750 211 16:272378408 309

Lépés

16:439400518 69 16:337970820 128 16:297838921 123 16:294804990 294

Tekintve a fentieket, látható, hogy a függvény várható értékére kapott alsó illetve fels® korlátok, a peremeloszlások egyre több momentumának gyelembe vételével, egyre közelebb kerülnek egymáshoz, az utolsó két esetben már három jegy pontossággal be sülve a élfüggvényt. Ki sit pontosabban vizsgálva az eredményeket az is kiderül, hogy az utolsó esetben a minimum és maximum értékek relatív eltérése kisebb mint

2 ezrelék.

Ha a megfelel® tiszta momentumok mellett az összes, legfeljebb

4 rend¶ vegyes momentumot

szerepeltetjük a korlátozó feltételek között, akkor a 2. táblázat eredményeit kapjuk. Összehasonlítva a két táblázatot a következ® tanulságokat sz¶rhetjük le.

Egyrészt, mint

az várható volt, a második esetben pontosabb eredményeket kaptunk. Az utolsó sor esetén a relatív eltérés kevesebb mint

4 tízezrelék.

Másrészt viszont ennek a pontosságnak ára van. A táblázatokban az eredmények mellett szerepel, hogy a CPLEX program hány lépésben jut el az optimális megoldásig. Láthatjuk,

60

m m1 m2 m3

4 4 4 6 4 8

4 6 8

Minimum


4 16:256237098 331 6 16:284878189 466 8 16:288316597 802

hogy hasonló pontosság (pl. lépésre volt szükség.

Lépés

16:337929898 364 16:297815868 686 16:294784936 669

három számjegy) eléréséhez az 1.

táblázatban jóval kevesebb

Ha emellett még azt is gyelembe vesszük, hogy a 2.

táblázat esetén

jóval több sorral (és így persze nagyobb mátrixszal) számolunk, akkor máris vonzóbbnak t¶nik újabb tiszta momentumok gyelembe vétele a be slés javítására, mintsem a momentumok teljes rendjének növelése. Természetesen, bizonyos határon túl, mikor már a pontosság tiszta momentumok gyelembe vételével már nem, vagy sak elhanyagolható mértékben javítható, szükség lehet magasabb rend¶ momentumok gyelembe vételére. Általánosságban annyit mondhatunk, hogy ajánlott el®ször a tiszta momentumokban rejl® lehet®ségeket kiaknázni, és sak utána ugrani egy nagyságrendet a vegyes momentumok teljes rendjével.

A fenti példában mind az u függvény, mind a momentumok generálására használt eloszlás szimmetrikus volt. Érdemes egy általánosabb példát is megvizsgálni, egyrészt abból a szempontból hogy a kapott be slések lesznek-e olyan pontosak mint a 5.6 példában, másrészt hogy az eddig leírt következtetéseket más példával is alátámaszthassuk. A következ® feladat korlátozó momentumait el®állító eloszlás egyrészt aszimmetrikus lesz, másrészt, az el®z® példától eltér®en, peremeloszlásai sem lesznek függetlenek egymástól. Az (5.6) függvény paramétereinek is új értéket adunk. Megjegyezzük, hogy ezen paraméterek változtatása lényegében ekvivalens az 5.6 példában szerepl® u függvény Z értelmezési tartományának eltolásával (ha az aj tagokat tekintjük) illetve nyújtásával (ha az j tényez®ket vesszük gyelembe).

5.7. Példa.

Tekintsük a következ®, Poisson eloszlású, valószín¶ségi változókat,

rendre a következ®

paraméterekkel, 1; 2; 2:5; 3.

X; Y1 ; Y2 ; Y3 ,

Korlátozó feltételeink jobb oldalára az alábbi

valószín¶ségi vektorváltozó megfelel® momentumai kerülnek:

(min (X + Y1; 9) ; min (X + Y2; 9) ; min (X + Y3; 9)) : Az

u

függvény, melynek várható értékét be sülni fogjuk, legyen a (5.6) függvény az alábbi

paraméterekkel:

1 = 1:75; 2 = 1:25; 3 = 0:75; a1 = 3; a2 = 2; a1 = 1: 61

Ha a vegyes momentumok közül sak a kovarian iákat vesszük gyelembe, akkor a 3. táblázat eredményeit kapjuk, míg az

= 4 esethez tartozó be sléseket a 4.

m

táblázat tar-

talmazza.

m m1 m2 m3

2 2 2 2

2 4 6 8

2 4 6 8

2 4 6 8

m m1 m2 m3

4 4 4 6 4 8

4 6 8

Minimum


Lépés

Minimum


Lépés

18:466954935 62 18:532630264 111 18:541879509 178 18:543136443 263

4 18:532852070 254 6 18:541926465 742 8 18:543148260 542

18:572924791 46 18:550298509 126 18:544391959 148 18:543344110 191

18:550297658 325 18:544391052 658 18:543343503 736

Megvizsgálva a fenti adatokat, az összes legfeljebb

8 rend¶ tiszta momentumot tekintve, az

alsó illetve fels® be slés közti relatív eltérés mind kovarian ia, mind a legfeljebb negyedrend¶ vegyes momentumok esetén kisebb mint

2 10

5

, ami a 5.6. példánál jobb eredmény. A most

kapott lépésszámok és pontosságok összevetése pedig alátámasztja az el®z® példa következtetéseit.

62

Tanulságok, további kutatási irányok

Befejezésül, érdemes áttekinteni egyrészt mégegyszer, hogy milyen eredmények, módszerek állnak rendelkezésünkre a TDMP területén, támaszkodva a dolgozatban szerepl® eredményekre. Másrészt szót kell ejtenünk arról is, hogy mely alapvet® kérdések maradtak megválaszolatlanul. Megemlítjük még az ezek megoldására felmerült, egyel®re kidolgozatlan ötleteket, melyek egyúttal tükrözik a szerz® gondolkodását, véleményét a további kutatások irányairól, módszereir®l. Az elért konkrét eredményeket a dolgozat 4. Fejezete tartalmazza, melynek alapját a 3. Fejezet tétele adja, alkalmazhatóságát az 5. Fejezet mutatja. Disszertá iónk analízálásához érdemes a 4. Fejezet pontjain keresztül haladni. A 4.1. szakaszban szerepel® duál megengedett bázisstruktúrák jellemz®je, hogy bármennyi dimenziós feladat esetén alkalmazhatóak, azonban sajnos nemhogy nem találtuk meg az összes duál megengedett struktúrát, szemben az egyváltozós esettel, hanem általában a struktúrák számossága általában szoros korlátok megadására sem elégséges. Az itt felsorolt tételeknek, elméleti jelent®ségükön túl, fontos alkalmazási területe a kezdeti bázisok legyártása a duál algoritmus második fázisához. A struktúrák számosságának növelésére több kiút is lehetségesnek t¶nik. Egyrészt érdemesnek t¶nik egy olyan TDMP feladat kit¶zése, melyben a momentumok rendszere lehet®vé teszi a 4.3. szakaszhoz hasonló algoritmusok kidolgozását, ezáltal jóval nagyobb számosságú struktúrarendszer megadását, mely már alkalmas lenne szoros korlátok megadására. Másrészt érdekes kérdés, hogy lehetséges-e sak a függvény osztott dieren iáira tett feltételek alapján az összes duál megengedett bázis megtalálása, és ha nem, akkor milyen (további) tulajdonságokat kellene a függvényt®l megkövetelnünk. Azt, hogy valószín¶leg a sak az osztott dieren iákra vonatkozó feltételek nem lesznek elegend®ek, az a tény is sugallja, hogy míg az egyváltozós esetben (ahol ismert az összes duál megengedett bázisstruktúra) az osztott dieren ia szoros összefüggésben van a függvény konvexitási tulajdonságaival, addig a többváltozós esetben, mint azt a (2.4) függvénye is mutatja, sak a tengelyek mentén biztosított ez a kap solat. A 4.2. szakasz eljárása jelen formájában inkább sak elméleti jelent®séggel bír, tekintve a 4.1. szakasz által adott sz¶kös lehet®ségeket. Könnyen látható viszont, hogy a leírt módszer analóg módon alkalmazható a 4.3. szakasz bázisstruktúrái esetében is, lehet®séget adva annak gyakorlati alkalmazására. Annak, hogy a dolgozatban sak a 4.1. szakasz struktúrájára vonatkoztatva dolgoztuk ki az eljárást, két f® oka van. Egyrészt a módszer lényege ezen belül is megfogható, másrészt így egy egyszer¶bb, jobban érthet® eljáráshoz jutottunk, amely emellett alkalmazások szerint könnyen általánosítható. A 4.3. szakasz eredményei széleskör¶ gyakorlati alkalmazhatóságot tesznek lehet®vé, mint ezt az 5.1. szakasz példái is alátámasztják. Annak ellenére, hogy itt a kétváltozós esetben, nagy számosságú duál megengedett struktúrát találtunk, erre is vonatkozik, a 4.1. szakasznál már említett kritika, mely szerint az összes megengedett duál bázis itt sem ismert. 63

Összefoglalva elmondhatjuk, hogy ugyan dolgozatunk, az egyváltozós esettel ellentétben, nem tárta fel a duál megengedett bázisok teljes rendszerét, de viszont egy, az eddigieknél általánosabb, jobban alkalmazható feladatra a duál megengedett bázisok eddigieknél jóval b®vebb halmazát tárta fel (különösen a kétváltozós esetben). Így, és ezt az 5. Fejezet eredményei is alátámasztják, jelent®sen közelebb kerültünk a TDMP problémák kezeléséhez, megoldásához.

64

Köszönetnyilvánítás

El®ször is, szeretnék köszönetet mondani Prékopa Andrásnak a témavezetésért, beleértve mind a számomra igen érdekes téma kiválasztásában, mind annak kidolgozásában nyújtott segítségét. Ugyan sak köszönettel tartozom Vizvári Bélának, akinek a matematikus szakon harmadévben tartott kurzusa irányította rá gyelmemet az operá iókutatás témakörére, és akit®l a sável®adások folyamán a lineáris és egészérték¶ programozás alapjait elsajátítottam. Köszönettel tartozom még mind az ELTE Operá iókutatási Tanszék, mind a BME Dieren iálegyenletek Tanszék munkatársainak, külön köszönet Szántai Tamásnak és Garay Barnának tudományos pályám alakításában nyújtott segítségükért, taná saikért. Köszönet jár még az Eberhard Karls Universität Tübingen Funk ionálanalízis Tanszékének, illetve vezet®jének Prof. Rainer Nagelnek, akik a doktori értekezés megírásához szükséges hátteret biztosították. Az anyagi támogatásért a Tempus és a DAAD ösztöndíjbizottságokat illeti köszönet. Végezetül hálás vagyok saládomnak és barátn®mnek, akik mindvégig támogattak élom elérésében és türelemmel viseltettek irántam.

65

Összefoglaló a `Többváltozós diszkrét momentum problémák'

ím¶ doktori értekezéshez Nagy Gergely Témavezet®: Prékopa András

A diszkrét momentum probléma (DMP) élja, egy diszkrét (általában véges) tartójú, ismeretlen valószín¶ségi eloszláson deniált lineáris funk ionál maximumának illetve minimumának megtalálása, bizonyos momentumok ismeretében. Tekinthetünk binomiális, hatvány vagy általánosabb típusú momentumokat. A többváltozós diszkrét momentum probléma (TDMP) bevezetése Prékopa nevéhez f¶z®dik, aki egyrészt kidolgozta DMP illetve TDMP problémák lineáris programozási elméletét, másrészt bizonyos, a élfüggvény együtthatók osztott dieren iáira tett, feltételek mellett módszereket adott azok megoldására. Legfontosabb eredményei a duál megengedett bázisok struktúráival kap solatosak. A doktori értekezésben további, a TDMP területén született, eredményeket mutatunk be, mind a hatvány, mind a binomiális momentumok esetére. A 3. Fejezet tétele illetve annak 4. fejezetbeli alkalmazásai lehet®séget adnak duál megengedett bázisok megadására, feltételezve, hogy a élfüggvény együtthatók függvényének adott teljes rend¶ osztott dieren iái illetve néhány további, sak egy változó szerinti, osztott dieren iája nemnegatív. Egy duál megengedett bázis alsó vagy fels® korlátot szolgáltat mind a élfüggvény együtthatóiból képzett diszkrét függvényre, mind magára a lineáris funk ionálra. Az utóbbira kapott korlát éles, ha a bázis egyben duál megengedett is. Tekintve a 4. Fejezetet, az els® szakasz a duál megengedett bázisok struktúrájáról szóló tételeket tartalmaz, melyek általánosításai az eddigi eredményeknek. A következ® szakasz egy dekompozí iós eljárást mutat be az említett struktúrákon belüli legjobb korlát megtalálására. A harmadik szakaszban található algoritmusok segítségével további, jóval nagyobb számosságú duál megengedett struktúra található a kétváltozós esetre. Végül az utolsó fejezetben numerikus példákat mutatunk be, mind véletlen vektorok függvényei várható értékének, mind eseménysorozatok Boole függvényeinek korlátokon keresztüli be slésére. 66

Summary of Ph.D. dissertation entitled `Többváltozós diszkrét momentum problémák' (`Multivariate Dis rete Moment Problems') Gergely Nagy Supervisor: András Prékopa

The dis rete moment problem (DMP) has been formulated as a methodology to nd the minimum and/or maximum of a linear fun tional a ting on an unknown probability distribution, the support of whi h is a known dis rete (usually nite) set, where some of the moments are known. The moments may be binomial, power or of more general type. The multivariate dis rete moment problem (MDMP) has been initiated by Prékopa who developed a linear programming theory and methodology for the solution of the DMP's and MDMP's under some assumptions, that on ern the divided dieren es of the oe ients of the obje tive fun tion. The entral results in this respe t are there that on ern the stru ture of the dual feasible bases. In the Ph.D. dissertation further results are presented in onne tion with MDMP's for the

ase of power and binomial moments. The theorem in Se tion 3 and its appli ations in Se tion 4 help us to nd dual feasible bases under the assumption that the obje tive oe ient fun tion has nonnegative divided dieren es of a given total order and further nonnegative divided dieren es related to ea h variable. Any dual feasible basis provides us with a bound for the dis rete fun tion that onsists of the oe ients of the obje tive fun tion and also for the linear fun tional. The latter bound is sharp if the basis is primal feasible as well. Detailing Se tion 4, the rst subse tion ontains generalizations of the former theorems

on erning dual feasible basis stru tures. In the following subse tion, there is a de omposition method to nd the best bound among these dual feasible bases. The last subse tion shows algorithms providing mu h larger variety of dual feasible stru tures in the bivariate ase. Finally, in the last se tion numeri al examples are presented for bounding the expe tations of fun tions of random ve tors as well as probabilities of Boolean fun tions of event sequen es.

67

Irodalom

[1℄ Bowers Jr., N. L., H. U. Gerber, J. C. Hi kman, D. A. Jones and C. J. Nesbitt (1997).A tuarial Mathemati s, 2nd edition, The So iety of A tuaries, Itha a, Ill. [2℄ Horn, R.A. and C.R. Johnson (1991). Press, New York.

Topi s in Matrix Analysis. Cambridge University

[3℄ Jordan, C. (1947). Cal ulus of Finite Dieren es. Chelsea Publishing Company, New York. [4℄ Karlin, S. and W.J. Studden (1966). T heby he and Statisti s. Inters ien e, New York.

Systems: With Appli ations in Analysis

[5℄ Krein, M. and A. Nudelman (1977). The Markov Moment Problem and Extremal Problems. In Translations of Mathemati al Monographs 50, Ameri an Mathemati al So iety, Providen e, RI. [6℄ Lemke, C. E. (1954). The Dual Method for Solving the Linear Programming Problem. Naval Resear h Logisti s Quarterly 1, 3647. [7℄ Nagy, G. and A. Prékopa (2000). On Multivariate Dis rete Moment Problems and their Appli ations to Bounding Expe tations and Probabilities. RUTCOR Resear h Report 412000. [8℄ Nagy G. és Prékopa A. (2000). Többváltozós diszkrét függvények féloldalas approximá iója polinomokkal. Alkalmazott Matematikai Lapok 20, 195-215. [9℄ Nagy G. és Prékopa A. (2001). Egy többváltozós hasznossági függvény. matikai Lapok 21, közlésre elfogadva.

Alkalmazott Mate-

[10℄ Popovi iu, T. (1944). Les Fon tions Convexes. A tualités S ientiques et Industrielles 992, Hermann, Paris. [11℄ A. Prékopa (1995).

Sto hasti Programming. Akadémia Kiadó, Budapest.

[12℄ Prékopa, A. (1990). The Dis rete Moment Problem and Linear Programming. Applied Mathemati s 27, 235-254.

Dis rete

[13℄ Prékopa, A. (1992). Inequalities on Expe tations Based on the Knowledge of Multivariate Moments. In: Sto hasti Inequalities (M. Shaked and Y.L. Tong, eds.), Institute of Mathemati al Statisti s, Le ture Notes Monograph Series, Vol 22, 309331.

68

[14℄ Prékopa, A. (1996). A Brief Introdu tion to Linear Programming. entist 21, 85-111.

The Mathemati al S i-

[15℄ Prékopa, A. (1998). Bounds on Probabilities and Expe tations Using Multivariate Moments of Dis rete Distributions. Studia S ientiarum Mathemati arum Hungari a 34, 349378. [16℄ Prékopa, A. (2000). On Multivariate Dis rete Higher Order Convex Fun tions and their Appli ations. RUTCOR Resear h Report 39-2000. Also in: Pro eedings of the Sixth International Conferen e on Generalized Convexity and Monotoni ity, Karlovasi, Samos, Gree e, August 29 - September 2, to appear. [17℄ Prékopa, A., Vizvári, B. and Reg®s, G. (1997). Lower and Upper Bounds on Probabilities of Boolean Fun tion of Events, RUTCOR Resear h Report 21-97. [18℄ Riordan, J. (1968).

Combinatorial Identities. Wiley, New York.

[19℄ Samuels, S. M., and W. J. Studden (1989). Bonferroni-Type Probability Bounds as an Appli ation of the Theory of T heby he System. Probability, Statisti s and Mathemati s, Papers in Honor of Samuel Karlin. A ademi Press, 271-289.

69

Függelék: a numerikus számításokhoz használt programkódok

70

ÌÖØÐÓÑÝÞ ÚÞØ ÞÖØ ÑÓÑÒØÙÑ ÔÖÓÐÑ Þ ÝÚ ÐØÓÞ ÞÖØ ÑÓÑÒØÙÑ ÔÖÓÐÑ ØÚ ÐØÓÞ ÞÖØ ÑÓÑÒØÙÑ ÔÖÓÐÑ ÌÚ ÐØÓÞ ÞÖØ ÚÒÝ Ñ ÖÒò ÓÒÚÜØ Ý ØØÐ ØÚ ÐØÓÞ ÄÖÒ ÒØÖÔÓÐ Ö ÃÓÖÐ ØÓ ÌÅ

Recommend Documents