NU VERSIUNEA FINALĂ

Cea mai importantă dintre toate problemele este selectarea variabilelor. Vom atribui acum variabilele noastre alimentelor, iar valoarea variabilei va fi cantitatea de alimente care trebuie consumată (în porții). Marcați x 1 numărul de porții de fulgi de ovăz de mâncat, x 2 puiul, x 3 ouăle, x 4 laptele, x 5 plăcinta de cireșe, x 6 numărul de porții cu fasole de porc! Dieta trebuie să îndeplinească următoarele condiții: Doză/zi în limită Cerința zilnică 0 x 1 4 0 x 2 3 0 x 3 2 0 x 4 8 0 x 5 2 0 x 6 2 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 Aici am luat în considerare faptul că nu ar trebui să consumăm o cantitate negativă sau prea multă mâncare sau am rezumat valoarea nutritivă din ele. În cele din urmă, costul dietei poate fi exprimat prin variabilele introduse și constantele date: 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 După aceasta, descrierea matematică a problemei dietei este următoarea: min 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 x 1 4 x 2 3 x 3 2 x 4 8 x 5 2 x 6 2 x 1, x 2, x 3, x 4, x 5, x 6 0 3

2.2. Dualitate Luați în considerare următorul LP standard! max 4x 1 + x 2 + 5x 3 + 3x 4 x 1 x 2 x 3 + 3x 4 1 (1) 5x 1 + x 2 + 3x 3 + 8x 4 55 (2) x 1 + 2x 2 + 3x 3 5x 4 3 (3) x 1, x 2, x 3, x 4 0 În loc să rezolvați problema, dați o estimare superioară pentru valoarea z a funcției obiective. Înmulțirea inegalității (2) cu 5/3 dă o limită superioară pe z. 5 3 (5x 1 + x 2 + 3x 3 + 8x 4 55) 4x 1 + x 2 + 5x 3 + 3x 4 25 3 x 1 + 5 3 x 2 + 5x 3 + 40 3 x 4 275 3 z 275 3 A (2) + (3) dă o limită superioară dreaptă: 5x 1 + x 2 + 3x 3 + 8x 4 55 x 1 + 2x 2 + 3x 3 5x 4 3 4x 1 + 3x 2 + 6x 3 + 3x 4 58 4x 1 + x 2 + 5x 3 + 3x 4 4x 1 + 3x 2 + 6x 3 + 3x 4 58 z 58 Continuând ideea, luați combinația liniară non-negativă a inegalităților, adică înmulțiți prima cu y 1 și a doua cu y 2, al treilea cu y 3, apoi adăugați-le! (Evident, inegalitatea finală este valabilă dacă y 1, y 2, y 3 nu este negativ.) (Y 1 + 5y 2 y 3) x 1 + (y 1 + y 2 + 2y 3) x 2 + (y 1 + 3y 2 + 3y 3) x 3 + + (3y 1 + 8y 2 5y 3) x 4 y 1 + 55y 2 + 3y 3 4

Dacă sunt îndeplinite următoarele condiții, atunci y 1 + 55y 2 + 3y 3 dă o limită superioară asupra valorii funcției obiective: Dacă cele de mai sus sunt îndeplinite, obținem: y 1 + 5y 2 y 3 4 y 1 + y 2 + 2y 3 1 y 1 + 3y 2 3y 3 5 3y 1 + 8y 2 5y 3 3 4x 1 + x 2 + 5x 3 + 3x 4 y 1 + 55y 2 + 3y 3 zy 1 + 55y 2 + 3y 3 Căutarea unui limita superioară, obținem următoarea problemă LP: min y 1 + 55y 2 + y 3 y 1 + 5y 2 y 3 4 y 1 + y 2 + 2y 3 1 y 1 + 3y 2 3y 3 5 3y 1 + 8y 2 5y 3 3 y 1, y 2, y 3 0 Problema inițială este primară, iar cea obținută mai sus se numește sarcină duală sau duală. LP într-o formă standard și dualul său în general: Primar Dual max c j x j j = 1 min m b i y i a ij x j b i i = 1. m j = 1 m a ij y i c j j = 1. n x j 0 j = 1. n y i 0 i = 1. m 1. Teorema. (Dualitate slabă) Dacă (x 1. x n) este o posibilă soluție a problemei primare și (y 1. y m) este o posibilă soluție a problemei duale, atunci m c j x j b i y i j = 1 5

Dovadă. Este evident din construcția dublei probleme. Formal: (m) mmcjxja ij yixj = a ij xjyibiyi, j = 1 j = 1 j = 1 deoarece astăzi ij yicj, xj 0 (j = 1. n) și nj = 1 este ij xjbi, yi 0 (i = 1 m). Înainte să afirmăm și să dovedim așa-numitul. o teoremă puternică a dualității, ia în considerare ultimul dicționar al unei probleme LP. Se poate observa următoarea caracteristică foarte surprinzătoare: Soluția problemei duale poate fi citită din ultimul dicționar al problemei originale. Dacă soluția originală a fost optimă, așa să fie. De exemplu, în cazul în care ultimul dicționar al problemei principale este: x 2 = 14 2x 1 4x 3 5x 5 3x 7 x 4 = 5 x 1 x 3 2x 5 x 7 x 6 = 1 + 5x 1 + 9x 3 + 21x 5 + 11x 7 z = 29 x 1 2x 3-11 x 5 + 0 x 6-6 x 7 x 5 y 1 y 1 = 11 x 6 y 2 y 2 = 0 x 7 y 3 y 3 = 6 Corespondența: duală variabilele într-un anumit sens pot fi atribuite variabilelor artificiale ale LP-ului original. Valoarea variabilelor duale este exact de 1 ori coeficienții funcției obiective instantanee a variabilelor artificiale. Această proprietate dovedită în curând este extrem de utilă atât în demonstrarea teoremei dualității, cât și în rezolvarea problemelor practice. Teorema 2. (Dualitate puternică) Dacă problema primară are o soluție optimă (x 1. x n), atunci problema duală are o soluție optimă (y 1. y m) pentru care m c j x j = b i yi j = 1 6

Dovadă. Datorită teoremei slabe a dualității văzută mai devreme, este suficient să găsim o posibilă soluție (y1, y 2. y n) pentru problema duală pentru care se menține ecuația nj = 1 c j x j = m b i yi. În rezolvarea problemei primare, introducem variabilele artificiale x n + i = b i a ij x j (i = 1. m) j = 1. Să presupunem că am ajuns la ultimul dicționar: n + mz = z + ckxkk = 1 ck 0, (k = 1. n + m), z = cjxjj = 1 După cum sa menționat, încercați yi = c n + i (i = 1. m ) înlocuire! Susținem că aceasta este o posibilă soluție la dual, este doar o chestiune de alte aspecte. x n + i < >> < m z = c j x j = z + c j x j yi b i a ij x j j=1 j=1 j=1 ( ) ( ) m m c j x j = z b i yi + c j + a ij yi x j j=1 j=1 Ezt az egyenlőséget egyszerű algebrai manipulációval kaptuk az előzőből, azaz minden x 1, x 2. x n értékre igaznak kell lennie. Ebből adódnak a m z = b i yi, m c j = c j + a ij yi egyenlőségek. Mivel c k 0 minden k = 1. n + m esetén, így m a ij yi c j (j = 1. n) yi 0 (i = 1. m) 7

Deci yi = c n + i (i = 1. m) este o posibilă soluție a dualului și m b i yi = n j = 1 c j x j, și cu aceasta vedem teorema. În matematică, un operator se numește dualizare atunci când este aplicat de două ori la rând pentru a reveni la problema inițială. Legitimitatea numelui nostru este justificată de faptul că dualitatea sarcinii duale este sarcina primară. Problema duală m max (bi) yim (a ij) yicj (j = 1. n) yi 0 (i = 1. m) Problema duală a problemei duale min (cj) xjj = 1 (a ij) xjbi ( i = 1 m) j = 1 xj 0 (j = 1. n) Aceasta este în mod evident echivalentă cu problema primară: max cjxjj = 1 j = 1 a ij xjbi (i = 1. m) xj 0 (j = 1. n) între sarcina primară și cea duală Teorema dualității arată că sarcina primară și cea duală nu pot fi în nici o relație. Posibilitatea diferitelor variații (optimă, fără soluție posibilă, funcția obiectivă nu este limitată) este rezumată în tabelul de mai jos. 8

Media V este suma averii unei persoane, K este prejudiciul care poate fi probabil p și d este prima de asigurare care o rambursează. Apoi, inconvenientul plății taxei: log (1 + V) + log (1 + V d) d V în timp ce scăderea (așteptată) a utilității cauzată de accident () 1 + V p (log (1 + v) + log (1 + v K)) = p log 1 + VK Deci merită să încheiem asigurare dacă (d V p log 1 + K 1 + VK (= p log 1 +).) K. 1 + VK Să ne uităm la unele cazuri speciale: K c) vinde un ziar pentru o unitate. Dacă cumpărați x piese, atunci pentru ξ x, în timp ce dacă ξ> x dξ cx = c (x ξ) + (d c) ξ, dx cx = (d c) (ξ x) + (d c) ξ va fi util. Desigur, un răspuns semnificativ poate fi de așteptat numai dacă avem unele presupuneri cu privire la distribuția cererii. Fie această distribuție mai întâi discretă și denotăm probabilitatea evenimentului ξ = i cu p i, adică P r (ξ = i) = p i. Beneficiile așteptate vor fi astfel:

(dc) eξ c (xi) pic) (ix) pi, ix (d care este maximă dacă suma lui c (xi) pi + (dc) (ix) piix este minimă, ceea ce poate fi interpretat ca o valoare așteptată penalizare dacă Valoarea curentă a lui eltér este diferită de x, c trebuie plătit pentru ξ xf (x): = 2 (xi) λi e λ + (ix) λi e λ i! i! ix Considerăm că x este o variabilă continuă; și diferențiat ad dx f (x) 2 λi e λ λ ie λ i! i! ix Trebuie să găsim rădăcina ecuației pentru fiecare distribuție discretă ipi = 1, deci în mod specific i = 0 λ adică λ/i! = 1, adică ix = 0 λ adică λ 5 Distribuția Poisson apare într-o mulțime de procese aleatorii, de ex. Rătăciri sau apeluri telefonice etc., deci este mult mai natural să o presupunem în acest caz decât distribuția uniformă (i!) . 18

calculul n (n + 1)/2 elemente ale matricei simetrice C. (Acestea trebuie, desigur, să fie determinate din observațiile anterioare.) Ambele dificultăți pot fi depășite dacă, în loc să minimalizăm covarianța, suntem mulțumiți cu minimizarea deviației absolute medii E [j (ξ j µ j) x j]. 8 Metoda modelului MAD al lui Konno-Yamazaki propusă de Konno și Yamazaki în 1990 urmează acest lucru și evită calcularea valorilor așteptate ale µ i și a coeficienților de covarianță c ij; utilizați direct datele observate. (Deviația absolută medie după denumirea în engleză, deviația absolută medie, denumirea modelului este MAD.) Dacă am făcut observația T în trecut, r jt denotă rentabilitatea investiției j-a la a t-a observație și rj = 1 TT r jt, jt = r jt rj, t = 1 atunci optimizarea portofoliului poate fi scrisă în următoarea formă: min 1 TT t = 1 nj = 1 a jt xj () rjxj ρ j = 1 xj = 1 xj 0 j = 1 . n. Problema () nu este LP, dar în mod similar cu ideea utilizată în jocurile cu matrice, LP poate fi redusă la o problemă: min 1 TT ytt = 1 ytnj = 1 j = 1 a jt xtytt = 1. T rjxj ρ () xj = 1 xj 0 j = 1. n. 8 De fapt, în cel mai important caz, pentru o distribuție normală multivariată, cele două metode sunt echivalente. 23

Cu acest model, devine posibilă rezolvarea unor probleme destul de mari, din viața reală. Cu toate acestea, nu trebuie să uităm că soluția obținută este doar o sugestie: există numeroase alte aspecte de luat în considerare la alegerea unui portofoliu propriu-zis. Modelul semi-nebun S-ar putea să doriți să vă gândiți la modelul MAD și să-l schimbați puțin. Amintiți-vă că expresia n j = 1 a jt x j dă abaterea semnului de la (estimat) rentabilitatea așteptată la momentul j. Este evident că nu minimizăm suma valorilor absolute ale acestora, ci doar suma valorilor absolute ale acelor membri negativi. (Într-adevăr, întrucât dacă portofoliul are performanțe mai bune decât randamentul așteptat la momentul j, nu este un eveniment neplăcut, ci un eveniment favorabil.) Introducerea notării x: = x dacă x 0 și x: = 0 dacă x> 0, problema ia următoarea formă: max 1 TT nj = 1 a jt xjt = 1 rjxj ρ j = 1 xj = 1 xj 0 j = 1. n. Forma LP pentru această problemă este ușor de specificat și este, de asemenea, mai simplă pentru modelul MAD: max 1 TT ytt = 1 a jt xtytt = 1. T j = 1 rjxj ρ j = 1 xj = 1 yt 0 t = 1 . T xj 0 j = 1. n. Notă: metodele MAD și sem-mad sunt aproximativ echivalente dacă distribuția randamentelor portofoliilor optime este aproximativ simetrică. 24

Acest lucru nu este neapărat cazul, astfel încât în studiile actuale pare mai util să se utilizeze modelul semi-nebun, deoarece timpul de calcul așteptat este cu siguranță mai scurt. 25

m x i = 1 () x i 0 (i = 1, 2. m) Observația crucială este că, deși această problemă nu este LP, este echivalentă cu un LP. max zzma ij xi 0 (j = 1, 2. n) mxi = 1 () xi 0 (i = 1, 2. m) Într-adevăr, soluția optimă a problemei () la orice z, x 1. xm este la cel puțin un za ij xi 0 satisface inegalitatea cu egalitatea, deci optimul LP z = min este ij x j. În mod analog, min max ia ij yj (i = 1, 2. m) j = 1 yj = 1 j = 1 yj 0 (j = 1, 2. n) care descrie strategia optimă a jucătorului coloană este echivalent cu min wwna ij yj 0 (i = 1, 2. m) j = 1 myj = 1 () yj 0 (j = 1, 2. n) cu problemă LP. Observați că () și () sunt duale între ele și ambele au soluții posibile. Astfel, conform teoremei dualității, () are o soluție optimă de z, x 1. x m și () are un w, y1. soluția optimă a y n astfel încât z = w. Deoarece z = min y x Ay, w = max x xay, am văzut teorema. 29