Majandusmatemaatika IIE eksami kordamisküsimused (5)

Majandusmatemaatika TEM0222 konspekt 1. Gaussi meetod e. elimineerimise meetod täpselt määratud süsteemi korral (võrrandite arv=tundmatute arv): maatriksis jäätakse kõik peadiagonaali elemendid 1ks, kõik ülejäänud elemendid muudetakse 0ks. Selleks valitakse igast reast ja veerust ühe korra juhtelement. Ühest reast või veerust mitu korda juhtelementi valida ei saa. Juhtelemendi rida lahutatakse või liidetakse teistele ridadele, et ülejäänud ridadest saada samasse veergu kus juhtelemend asub nullid . N: -1 2 1 1 ! 7 1 3 -1 1 ! 4 1 8 1 1 ! 13 11 11!6 Mittestabiilse süsteemi korral: Kasutusele tuleb Crameri valem. X1=x1( maatriks )/kogumaatriks Crameri valemit ei kasuta ükski arvutiprogramm , sest see võib anda väga suure vea. Gaussi meetodis saab arvutusvigade vähendamiseks valida juhtelemendiks maksimaalse absoluutväärtusega arvu (antud veerus kui ka kogu süsteemis).
Gaussi meetodiga saab leida ka pöördmaatriksit. Pöördmaatriks on olemas vaid regulaarsel maatriksil. Def: Ruutmaatriksit A nim regulaarseks kui selle determinant ei võrdu 0ga ja singulaarseks kui võrdub 0. Def: Regulaarse maatriksi A pöördmaatriks A-1 peab rahuldama võrrandit A*A-1=A-1*A=E, kus E on vastavat järku ühikmaatriks. Lahendskeem: (A!E)- >Gaussi teisend->(E!A-1). N: 248 -2 0 2 468
2. Leontjevi staatiline mudel 1 2 lõpptoodang y kogutoodang x 1 100=x11 160=x12 240 500 2 275 40 85 400 sisemine tarbimine Leontjevi mudel aitab leida samasugust tabelit järgmise aasta jaoks, kui uus lõpptoodang y=(200, 100) Otsekulude maatriks A, aij=xij/xj (1) 100/500 160/400 A= 275/500 40/400 Ax+y=x (2) ­ tasakaaluvõrrand sisemise tarbimise, lõpp- ja kogutoodangu vahel
Teades lõpptoodangu uut vektorit same koostada sarnase tabeli järgmise aasta jaoks. Selleks teisendame valemit 2. x-Ax=y (E-A)x=y x=(E-A)-1y=By (3) ­ B on täiskulude maatriks. Leiame E-A ning selle pöördmaatriksi ning same uue kogutoodangu maatriksi: Uusx=By a11=0,2=uusx11/uusx1=uusx11/440, uusx11=0,2*440=88
Esimese toote kogutoodang peab selle võrra suurenema, et saaks teist toodet müüa ühe ühiku võrra rohkem.
Staatilise Leontjevi mudeli puuduseks on investeeringute arvestamine lõpptoodangu hulka. Dünaamilises Leontevi mudelis arvestatakse investeeringuid eraldi maatriksina. 3. Vähimruutude meetod Meetodit kasutatakse ligikaudse sõltuvuse leidmiseks. Näiteks süsteemi puhul: Süsteemi kordajatest ning vabaliikmetest tuleb välja kirjutada veerummatriksid A1, A2, ... , An ja b. Uue süsteemi leidmiseks tuleb süsteemi igas reas vasakul pool korrutada vastava järjekorranumbriga tundmatu veerumaatriks esimese tundmatu veerumaatriksiga, seejärel teisega jne. Paremale poole jääb vastava järjekorranumbriga tundmatu veerumaatriksi korrutis vabaliikmete veerumaatriksiga. Märkused. 1) Saame võrrandisüsteemi lahendid , kui projekteerime parema poole b veergude ruumi. 2) Kui parem pool b kuulub veergude ruumi, on Ax = b täpne lahend leitav Gaussi meetodiga. 3) TEOREEM : Normaalvõrrandisüsteemil ATA = ATb on ühene lahend, kui maatriksi A veerud on lineaarselt sõltumatud. 4) Gaussi teisenduste korral vähimruutude lahend muutub, see pole vähimruutude ülesandes lubatud.
4. Kumerad hulgad Def: Hulk QcR2 on kumer , kui kõikide punktipaaride x1,x2 jaoks kogu neid punkte ühendav sirglõik kuulub sellesse hulka. Teoreem: Kumerate hulkade Q1...Qk ühisosa on kumerhulk. Tõestus: =!!!! ! Võtame 2 mistahes punkti x1,x2 Q ja moodustame: x= x1+x2Q. Kuna kõik Qi on kumerad, siis x1,x2 kuuluvad igasse Qi-sse. Kumerte hulkade ühisosa võib olla ka tühihulk, mis omakorda on kumer hulk, kuna ei sisalda ühtegi elementi.
5. Lineaarsete võrratuste süsteemid, vastuoluline süsteem !! ... !! ! ! Axb, kus = ... ... ... ,= ... ,= ... . !! ... !" ! ! Lineaarseid võrratusi saab enamasti lahendada graafiliselt. Kui võrratused on vastuolulised, siis lahend puudub (ühine osa puudub). Leidub ka ülearuseid võrratusi, ehk mõni võrratus järeldub teisest/teistest.
6. LP ülesande graafiline lahendamine I meetod ­ nivoojoonte abil N: z= 2x1-x2àmina, max x1+x2 4 (I) x1-2x2 -2 (II) x1, x2 0 *teen joonise ning leian, et nelinurk ABCD on lubatavate lahendite hulk Lisan joonisele nivoojoone z=0. Ülejäänud nivoojooned saab tõsta paralleelsete sirgetena. Nivoojoonte äärmise taseme viirutatud piirkonnas määravad miinimum- ja maksimumpunkti.
II meetod ­ põhineb lubatavate lahendite hulga 3. teoreemil , et ülesande min ja max saavutatakse mingite lubatavate lahendihulkade tipus .
LP ülesandes on alati kolm võimalus 1) optimaalne lahend eksisteerib 2) sihifunktsioon on tõkestamata ­ zmax= lõpmatus 3) lahend puudub. ­ kitsendused vastuoluline
7. Kaks näidet LP ülesande kohta 1. Dieediülesanne: leib juust päevanorm 1. a11=1 a12=2 b1=3kcal 2. a21=1 a22=4 b2=4 ühik valku hind: c1=6 c2=21 Koostada selline menu , mille summa maks zàmin x1, x2 ­ planeeritavad toidukogused (leib, juust) z=6x1+21x2àmin x1+ 2x2 3 x1+ 4x2 4 x0 2. Transpordiülesanne ai varud 1 4 2 5 ...!" = 3 5 1 10 vajad bj 7 5 3 Kaupa on kahes laos (varud), kolme kaupluse vajadused on bj. C on vedude maatriks. Iga cij näitab vastava lao kauba veo maksumust vastavasse kauplusesse. Ülesandeks on koostada selline vedude plaan, et summaarne vedude maksumus zàmin. x11 ­ vedu I ladu II kauplus. Jne z= x11+4x12+2x13+3x21+5x22+x23 à min x11+x12+x13 =5 ... (vastavad read liidad = a, vastavaad veerud liida = b) xij 0
8. LP ülesande püstitus (kanoonilise kuju teisendamine standardseks ja vastupidi) Standardne kuju: z=c1x1 + ... + cnxn à max a11x1 + ... + a1nxn b1 ... am1x1 + ... + amnxn bm x0 Kasutades vektoreid c, b, x ja m*n-maatriksit A kirjutame ülesande vektorkujul: z = (c,x) à max Ax b, x0. Kanooniline kuju: z=(c,x) àmin Ax = b x0 Standardse ülesande teisendamisel kanooniliseks, lisandub igale reale üks mittenegatiivne muutuja , et võrdused oleksid õiged. Maksimumi miinimumiks saamisel korrutame rida läbi -1-ga. Kanoonilise ülesande teisendamisel standardseks korrutame samuti esimese rea -1ga läbi. Kitsendusele lisandub sama kitsenduse vastasmärgiline kitsendus . N: 3x1+x2 = 5 à 3x1+x2 5; -3x1-x2 -5.
9. Lubatavate lahendite hulga omadused (kolm teoreemi) Teoreem 1: Lubatud lahendite hulk Q on kumer. *võtame kaks punkti ning tõmbame nende vahele joone. Joon x = 1x1+2x2 1 + 2 = 1, 1, 2 > 0 Võtame mistahes x1 ja x2, mis kuuluvad Q-sse, siis kehtib: Ax1=b1 +Ax2=b2 1Ax1+2Ax2= 1b + 2b=b(1+2)=b A(1x1+2x2)=Ax=b
x10 1 +x20 2 1x1+2x2 0 à x0 Teoreem 2: Lubatavate lahendite hulga Q iga punkt on esitatav selle hulga tippudekumera kombinatsiooniga. N: z=5x1+2x2 à max x1+x2 3 I x1 2 II x0 Q=ABCD. Iga xQ on esitatav kujul: x=1A ... (A on vekor (x,y))
Teoreem 3: Kui LP ülesande optimaalne lahend x* on ühene, siis x* on lubatud lahendite hulga mingi tipp. Kui x* ei ole ühene, siis on vähemalt 2 hulga Q tippu optimaalsed lahendid. Sellel teoreemil põhineb teine graafilise lahendamise meetod. x1, x2, ..., xs on hulga Q tipud . Teoreem 2 järgi, saab teisendada: z=(c,x)=1(cx1)+...+ s(cxs) 1(cxk)+...+ s(cxk)=(1+...+s)cxk=1*cxk=cxk. xk on selline tipp, milles cx saavutab miinimumi. Iga xQ, (c,x)(c,xk). Tipp xk on ühene optimaalne lahend.
10. Simpleksmeetodi kirjeldus (krit I ja II põhjendus, tõkestamatus) Simpleksmeetodil lahendatakse LP ülesannet järgmiselt: · Nullindale reale lisatakse x0, millest lahutatakse algse z-muutujad ning pannakse see võrduma 0ga. N: z= 2x1+3x2àmax à x0-2x1-3x2=0 · Igale järgmisele reale (kitsendustele) liidetakse simpleksmuutuja ning pannakse võrduma algse b-ga. N: x1+x24 à x1+x2+x3=4 · Saadakse baasimuutujad N: Antud näites x0=0, x3=4, x1=x2=0 Simpleksmeetodiga LP ülesande lahendamine käib kahe kriteeriumi järgi. I krit: Baasi tuuakse muutuja mille ees on 0-ndas reas kõige negatiivsem kordaja ­ see on juhtveerg. ! N: x0-2x1-3x2=0 - -3x2 on 0nda rea 2. veerg . Sellest veerust tuleb leida =min !!!"#$%&% ; !!!"#$%&% ; ... - leitakse iga rea b ja vastava x-kordaja jagatis , millest väikseim ongi ning antud rea, kus see arv asub baasimuutuja viiakse baasist välja, selle asemele tuleb antud juhtveeru element. NB! arvutatakse kordajate absoluutväärtustega. II krit: (on juba tegelikult seletatud eelpool ) Baasist viiakse välja see muutuja, mille korral =min. I krit pole kohustuslik, II krit on! Optimaalsuse kriteerium on täidetud kui 0nda rea kõik elemendid on 0. Tehtud arvutuste kontrollimiseks tuleb antud lahendus panna 0. süsteemi. Tõkestamatuse kriteerium: kõik juhtveeru elemendid on 0.
11. Kunstliku baasi meetod, M valimine Kunstliku baasi meetodit kasutatakse kui LP ülesanne on antud kanoonilisel kujul. 0ndas rida korrutatakse läbi -1ga, et saavutada maksimiseerimine. Seejärel pannakse z=x0 ning lahutatakse 0nda rea muutujatest My1,My2,... (muutujaid on täpselt nii palju, kui on kitsendusi) N: z=x1+2x2-x3àmin x1+x2+x3=6 x1 +x3=4 x0 x0=-z= x1+2x2-x3-My1-My2àmax àx0-x1-2x2+x3+My1+My2 =0 Kitsendustele liituvad vastavad muutujad: x1+x2+x3+y1 =6 x1 +x3 +y2=4 Kui ülesandel on kitsenduste kaudu näha, et lahendid on olemas, võib M asendada piisavalt suure positiivse arvuga. Antud ülesandes 10ga. Seejärel tuleb 0ndast reast lahutada piisavalt suure arvuga korrutatud kitsenduste read, et y-muutujad võrduksid 0ndas reas 0ga. Järgnevalt tuleb ülesanne lahendada nagu tavaline simpleksmeetod , kuni optimaalsuse kriteerium on täidetud ning kunstlikud muutujad on võrdsed 0ga. Kui valitud M korral mõni yi*0, siis a) M pole piisavalt suur või b) kuitahes suure M korral, kitsendused on vastuolulised à lahend puudub. Ülesande võib alati lahendada üldkujul, andmata M-le väärtust. Kui kõik juhtveeru elemendid on 0, siis zmin=-lõpmatus.
12. Simpleksmeetodi teooria (kidunud baas, teoreem baasist, geomeetriline tõlgendus) Kidunud baas: Kui mõni baasi muutuja võrdub 0ga, siis võib sihifuntsiooni väärtus mitte kasvada (mitmel sammul ) ja võime jõuda tagasi olnud baasi juurde. Tekib lõpmatu tsükkel, seega lahend puudub. Teoreem baasist: Kui LP ülesandel on tõkestatud optimaalne lahend, siis eksisteerib optimaalne baasilahend. Seda pole vaja tõestada, sest meil on kirjeldatud alati töötav konstruktsioon optimaalse baasilahendi leidmiseks. Sammude arv: 0,5msimplekssammude arv3m, kus m-kitsenduste arv LP ülesandes. Geomeetriline tõlgendus: Võib tõestada, et igale baasilahendile vastab lubatavate lahendite hulga mingi tipp. Simpleksmeetodi samm tähendab üleminekut ühest lubatud lahendite hulga tipust selle naabertippu, kus sihifunktsiooni väärtus on suurem või samasugune.
13. Duaalne simpleksmeetod, kitsenduste vastuolulisus Simpleksmeetodit saab kasutada vaid, kui b0, Kui vähemalt üks parem pool on väikse 0st, tuleb ülesanne lahedada duaalse simpleksmeetodiga. Tavalise simpleksmeetodi kirjelduses tuleb asendada sõnad "rida" ja "veerg", "positiivne" ja "negatiivne", "minimaalne" ja "maksimaalne". I krit: Baasist viiakse välja see negatiivne muutuja, millel on suurim absoluutväärtus. Vastavat rida nimetatakse juhtreaks. Sihifunktsioonile vastavat muutujat x0 ei viida kunagi baasist välja. Optimaalsuse krit on täidetud kui kõik baasimuutujad peale x0 on mittenegatiivsed ja kehtib tavalise simpleksmeetodi optimaalsuse krit (0nda rea kordajad on mitteneg). II krit: Tähistame need veerud, kus juhtrea elemendid on rangelt negatiivsed. Leiame ­ maksimaalse !!"# !"# !"!#!$% !!"# !" !"!#!!" nullinda rea ja juhtrea elementide suhte tähistatud veergudes. =max !!!"#$%&% ; !!!"#$%&% ; ... . Maksimumile vastav veerg võetakse juhtveeruks ja seal olev muutuja tuuakse baasi. Juhtelement on alati negatiivne. Vastuolulisuse krit: Kõik juhtrea elemendid on mittenegatiivsed
14. Duaalülesande koostamine Duaalülesanne koostatakse tavalise LP ülesande põhjal. Sihifunkts kordajad võrduvad lähteülesande paremate pooltega, duaalülesande paremad pooled ­ sihifunkts kordajatega. Kitsenduste maatriks transponeeritakse ­ read lähevad veergudeks. Lühidalt öeldes keeratakse ülesannet 900. Klassikalises optimiseerimisteoorias nim duaalmuutujaid Lagrange'I kordajateks. Standardsel kujul: kitsendused muutuvad à, y0. Kanoonilisel, muutuvad =à, Y kitsendused puuduvad. SKEEM: Lähteülesanne Duaalülesanne Kitsendus Muutuja Muutuja Kitsendus Kitsenduste paremad pooled Sihifunktsiooni kordajad Maatriksi i-s rida Maatriksi i-s veerg Maatriksi j-s veerg Maatriksi j-s rida i-s kitsendus kui võrratus i-s mittenegatiivne muutuja i-s kitsendus kui võrdus Mis tahes märgiga i-s muutuja Mis tahes märgiga muutuja Kitsendus kui võrdus Mittenegatiivne muutuja Kitsendus kui võrratus Maksimiseerimine minimiseerimine N: 3x1+x2àmin 2x1+5x2=4 x1 +7x2=-1 x0 15. Duaalsusteoreemid Teoreem 1: Kui x ja y on vastavalt lathe-ja duaalülesande mis tahes lubatavad lahendid, siis z=(c,x)(y,b)=w. (1) Tõestus: Eeldame, et on vaid kaks kitsendust ja kaks muutujad, üldjuhul on tõestus analoogiline. Korrutades lähteülesande esimest kitsendust a11x1+a12x2b1 duaalmuutuja y1 ja teist y2 ning liites need avaldised kokku, same (y,Ax)(y,b). Analoogiliselt duaalülesanet korrutades x1 ja x2 saame (yA,x)(c,x) ning kuna (y,Ax)= (yA,x), siis (c,x)(yA,x)(y,b), mis tõestabki teoreemi. Teoreem 2: Kui x^ ja y^ on sellised duaalülesannete paari lubatavad lahendid, mille korral sifikuntsioonid võrduvad, siis x^ ja y^ on nende ülesannete optimaalsed lahendid. Tõestus: Oletame vastuväiteliselt, et x^ ei ole optimaalne lahend, eksisteerib vektor x*, et (c,x*)>(c,x^)=(y^,b). See võrratus on aga vastuolus võrratusega (1), mis on täidetud mis tahes lubatavate lahendite jaoks. Teoreem 3: Kui duaalülesannete paaril on optimaalsed lahendid x* ja y*, siis z*=(c,x*)=(y*,b)=W*. See on eelmise teoreemi pöördteoreem, pole vaja tõestada. Teoreem 4: Kui lähteülesande sihifunktsioon pole tõkestatud, z*=+lõpmatus, siis duaalülesanne on vastuoluline. Kui duaalülesandes on sihifunktsioon tõkestamata, w*=-lõpmatus, siis lähteülesanne on vastuoluline. Tõestus: z*=+lõpmatus. Kui duaalülesandel oleks mingi lubatav lahend y, siis votes sellise lubatava lahendi x, et (c,x)>(y,b), same vastuolud võrratusega (1). Samamoodi tõestatakse teoreemi teine pool. Teoreem 5: (kokkuvõttev teoreem eelmise nelja jaoks) Sümmeetriliste duaalülesannetel on optimaalsed lahendid üheaegselt ja sihifunktsioonide väärtused nende korral võrduvad. Kui ühel nendest ülesannetest on sihifunktsioon tõkestamata, siis teine on vastuoluline. Kui üks ülesanne on vastuoluline, siis teisel (duaalülesandel) on sihifunktsioon tõkestamata või ta on vastuoluline.
16. Optimaalsuse piisavad ja tarvilikud tingimused Duaalülesannet saab lahendada: 1) graafiliselt 2) simpleksmeetodi, kunstliku baasi või duaalse simpleksmeetodiga 3) viimase simlekstabeli järgi, kui lähteülesanne on juba lahendatud otsese või duaalse simpleksmeetodiga. Duaalmuutujate optimaalsed väärtused võrduvad nullindas reas neile vastavate lisamuutujate ees olevate kordajatega. Tingimuse on toodud teoreemis: Teoreem 1: Sümmeetriliste duaalülesannete lubatavad lahendid x* ja y* on optimaalsed siis ja ainult siis, kui on täidetud tingimused: a) yi*[(ai,x*)-bi]=0, i=1,...,m (1) b) xj*[(y*,Aj)-cj]=0, j=1,...n (2) Neid nim täiendava mitteranguse tingimusteks. Kui meil on mingid ülesannete (1) ja (2) lubatavad lahendid x ja y, siis teoreemi põhjal saab kontrollida nende optimaalsust. Duaalülesannete lahendamine lähteülesande jaoks leitud optimaalse simplekstabeli abil pole otseselt rakendatav siis, kui me kasutame kunstliku baasi meetodit. Sel juhul sõltuvad nullinda rea kordajad valitud arvust M.
17. Duaalmuutujate majanduslik tähendus I Majanduslik analüüs duaalmuutujate abil. Tootmise planeerimise ülesanne. Leiame millist toorainet jääb üle, millist puudu, mis kulutatakse täpselt ära kui tootlikkus on maksimaalne. Näitab varjatud kulu. II Dieediülesanne. Lähteülesandeks oli dieediülesanne kus leidsime maksimaalse kalorsuse ja valgusuurusega toiduainete minimaalne maksumus, kui teda oli kui palju teatud toiduainet pidi ostma. Selle järgi saab välja arvutada maksumuse. Duaalülesandes huvitab meid aga kalorsus ja valgusus, mitte toiduained ning üritame leida maksimaalse kasulikkuse w*, mis peab võrduma minimaalse maksumusega z*. III Transpordiülesanne: Duaalülesannetes on võimalik leida ühe firma kulutused transpordile ­ minimiseerimine, ja teise firma tulud ­ maksimiseerimine. 18. Transpordiülesande lahendamine Potentsiaalide kaudu lahendamine. Igal sammul peab olema veoplaanis m+n-1 komponenti, kus m on ladude ja n on kaupluste arv. 0. Sammul leiame loodenurga reegli järgi alglahendi: näide lahendist. Kontrollime vedude arvu. Juhul kui vedude arv on vale lisame sinna 0 kuskile? Järgmise sammune lisame algsest tabelist arvud uude tabelisse, kuid kirjutame ainult need arvud, mis loodenurga reegli järgi olid olemas. (punkt2) Seejärel arvutame valemi c^ij=ui+vj, kus u on ladude ja v kaupluste arv. Seejärel leiame =max(c^ij-cij) (optimaalsuse kriteerium =0). Selle arvu asukoha veoplaanide tabelid märgime ga. Lisan tabelisse ka veoplaanid, mis algse loodenurga reegli järgi leidsin. Äärtele lisan ladude võimalused ja kaupluste soovid ning panen vastavad read kus on olemas võrduma vastavate asjadega. on suurim arv, mis ühtegi teist arvu tabelis ei muuda negatiivseks. Saame uued veod , mille järgi algsest tabelist leiame arvud asemele ja kordame punktist 2.
19. Transpordiülesande teooria Märkused: 1. Kui tabelis leidub selline vedu (k,l) , mille korral c^kl-ckl=0 ja see vedu ei ole optimaalses plaanis, siis pole x* ühene. Alternatiivse optimaalse lahendi leidmiseks tome veo lahtrisse (k,l) , tehes veel ühe potentsiaalide meetodi sammu. 2. Kui kolmandal sammul on mingis lahtris 0-, siis =0. Sellest lahtrist vedu kaob, nullvedu tuleb lahtrisse, kus asub . 3. Kui mitme sammu jooksul muutub vaid nullveo asukoht ja lõpuks selline vedu jõuab esialgsesse lahtrisse, tekib tsükkel.Saab vältide proovimise teel. Nullvedu võib panna igasse lahtrisse. 4. Kui lahutamisel võrduvad nulliga korraga mitu vedu, siis on mõistlikum ära jätta selline, millele vastab suurim maksumus cij . Alati peab olema m+n-1 vedu 5. Kui süsteemil pole v1=0 korral lahendit, võib nulliks võtta mõne muu vj või ui. 6. Suunamisül on üls transpordiül erijuhte, kus kõik varud ai ja vajadused bj võrduvad ühega. Seda saab ka lahendada potentsiaalide meetodiga, aga selle jaoks on lisaks välja töötatud ungari meetod. 7. Transpordiül võrgul on üks erijuht. Antud graafikakaarte läbilaskevõimete ja veomaksumuste korral tuleb leida kaupluste vajadusi rahuldav veoplaan, mille maksumus on minimaalne. On välja töötatud spetsiaalsed algoritmid , mis erinevad potentsiaalide meetodist ja arvestavad selle ül eripära. Teoreem: Transpordiül ja tema duaalülesande lubatavad lahendid x*, u*, v* on optimaalsed tarajasti siis kui on täidetud järgmised tingimused: (cij ­ui*-vj*)xij*=0 (1) i=1,...,m, j=1,...,n . Kui mingis lahtris on vedu xij 0, siis potentsiaalid rahuldavad võrrandit ui+vj=cij ja avaldis (1) võrdub 0-ga. Veo puudumisel on samuti avalid (1) täidetud. Optimaalsuseks on vaja, et potentsiaalid rahuldaksid duaalül kitsendusi. Tähistame c^ij= ui+vj , siis need kitsendused on samaväärsed c^ij-cij 0. Viimased võrratused on täidetud kui =max (c^ij-cij )=0, i=1,...,m , j=1,...,n. Seega on põhjendatud potentsiaalide meetodi optimaalsuse kriteerium.
20. Mittelineaarne ülesanne, selle omadused ja duaalülesanne Lahendatakse graafiliselt kujul z=f(x1,...,xn)max gi(x1,...,xn)bi , i=1,...,m T f,g1,...gm on vektori x(x1,...,xn) antud reaalfunktsioonid, b1,...,bm- antud arvud. Ülesanne on üldine, universaalne meetod lahendamiseks puudub.Tuleb mää . Hulk võib olla mittekumer ja koosneda mitmest osast. Maksimum-ja miinimumpunkt võivad asuda mistahes lubatavates punktides, mitte tipus nagu LP ülesandes. LP ülesandes oli sihifunktsiooni gradient konstantne vector nt z=5x1-6x2, grad z=z=(5;-6). Mittelineaarses ! ! z=x12x2+ ! ! ; = 2! ! + ! !! ! !! + ! !! ! ! ! ! ! Duaalülesanne: z=f(x)max y:gi(x)bi (1) i=1,....,m duaalül: L(x,y)=f(x)+ ! !!! ! [! - ! ()] L'x1=f'x1- ! (! )!! = 0 L'xn=f'xn- ! (! )!" = 0 y0 Täiendava mitteranguse tingimused: Yi[bi-gi(x)]=0 , st et duaalülesande sihifunktsioonis kõik liidetavad peale esimese peavad võrduma nulliga. Duaalül kitsendused võib vektorkujul kirjutada: grad f= !!!! ! ! () . Kui (x*, y*) on duaalül optimaalne lahend, siis teatud tingimuste korral on x* ühtlasi lähteülesande optimaalne lahend. Lähteülesande maksimumpunktis x* on sihifunktsiooni gradient f(x*) esitatav kitsendusfunktsioonide gradientide gi(x*) lineaarse kombinatsioonina mittenegatiivsete kordajate y*i abil
21. Wolfe 'i meetod Wolfe'I meetodit kasutatakse ruutplaneerimises. Antud juhul on simpleksmeetodit täiendatud vaid ühe lisatingimusega. Kitsendused esitatakse kanoonilisel kujul ning seejärel avaldatakse igal real lisamuutuja. Kitsenduse x0 kirjutame lahti ­x10,-x20. Kitsendused ja sihifunktisoon liidetakse ühiseks funktsiooniks, mille kitsendused saadakse algmuutujate kaudu tuletiste leidmisel. N: w=32x1+120x2-4x12-15x22+y1(20-2x1-5x2)+y2(8-2x1+x2)+y3x1+y4x2àmin w'x1=32-8x1-2y1-2y2+y3 ... x0, y0 Saadud duaalülesande kitsendused ja lähteülesande kitsendused kogume kokku ning saame uue ruutplaneerimise ülesande, mille sihifunktsiooniks minimeerime kunstlikke muutujaid t1+t2, ehk minimeerime x0=-x1-x2àmin. Uued kunstlikud muutujad on võrdsed w tuletistega (duaalülesande w kitsendused). Saame ülesande: x0-8x1-30x2 -7y1 -y2+y3+y4 =-152 2x1+5x2+x3 =20 2x1-x2 +x4 =8 8x1 +2y1+2y2-y3 +t1 =32 30x2 +5y1 ­y2 -y4 +t2 =120 Baasis ei või korraga olla y1 ja x3; y2 ja x4; y3 ja x1 ning y4 ja x2, sest kehtima peab täiendava miteranguse tingimus: yi[bi-gi(x)]=0. Optimaalsuse krit: Sihifunktsiooni x0 maksimum võrdub nulliga. See väärtus (0nda rea viimane arv) kasvab igal sammul või jääb samaks.
22. Kriitilise tee leidmine Kriitilise tee leidmist kasutatakse võrkgraafikus. Võrkgraafik on graafika alaliik, graafik koosneb tippudest ja kaartest. Võrkgraafikule vastavad tippude sündmused ja kaartele tööd. Kriitiline tee on pikim tee alg- ja lõppsündmuse vahel. Võrkgraafikut lahendatakse alates viimasest punktist ning järjest vaadeldakse läbi kõik punktid (9, 8, 7,...,1). Võrkgraafikuid koostatakse ehituses, uute toodete juurutamisel , auditi tegemisel, on olemas vastavad programmid.
23. Bellman'i printsiip Dünaamiliste mitmeetapiliste ülesannete lahendamiseks kasutatakse Bellman'i optimaalsuse printsiipi . Olgu T1, ..., Tn+1 süsteemi seisundid . ! ! ! ! ! ... ! !!! . ! ! ! Summaarne kasum F=f1+f2+...+fnàmax Bellmani printsiibis on optimaalne trajektoor optimaalne iga oma osa jaoks. See tähendab seda, et punktide eemaldamisel muutub ka kriitiline tee. Lahendamisel ongi oluline, et summaarne sihifunktsioon on etappidel tulevate sihifunktsioonide summa. Bellmani printsiipi kasutatakse ranitsaülesande lahendamisel. 24. Kahe tööpingi ülesanne Kahe tööpingi ülesande on kalenderplaneerimise ülesanne, kus tuleb leida millises järjekorras esemeid töödelda. Seda lahendatakse Johnsoni algoritmiga: 1) leida minimaalne element ai ja bi-de seast, 2) kui min=ai, siis seda töödelda esimesena (saab hakata kiiremini teist tööd tegema, 3) kui min=bi, siis seda töödelda viimaseda (võtab lõpus vähe aega, kui a tööd on juba tehtud) 4) kõrvaldada min vastav rida ja korrata . N: ai bi 1 6 7 2 8 4 3 5 9 4 7 8 Lahendamisel joonistad pika joone, kuhu peavad kõik tunnid ära mahtuma (nii palju kui kõikide tööde jaoks a või b reas läheb. Seejärel hakkad lahendama Johsoni algoritmiga. I tööd tehakse ilma pausideta, II töö tegemiel võivad tekkida paused kui I töö ei ole lõppenud. (antud esemel ).
25. Ranitsaülesanne Bellmani printsiipi kasutatakse ranitsaülesande korral, kus igat eset saab võtta kas 1 või 0 ning saadakse tabel, mille liikmed vastavad valemile: + ! - , mille maksimaalne vastus ongi ranitsaülesande tabelis (alati 2 vastust). Valemis c on vastav muutujakordaja sihifunktsioonis, a kitsenduses. Tabel täidetakse vastavalt valemile, ning vastus saadakse viimase elemendi kaudu. Vaadeldakse, millise arvu kaudu eelmisest veerust on saadud antud arv, jne kuni iga x* elemendi kohta on teada, kas teda võeti 1 või 0. NB! Vastuseks ei ole mitte tabelis olev arv, vaid see arv (1 või 0) mille kaudu see arvutati. N: z=7x1+9x2+15x3+6x4+10x5àmax 5x1+7x2 +3x3+2x4+4x516 1 .! = 0 26. Mänguteooria põhimõisted (majandusülesande taandamine mänguks) Majanduses sõltub tihti, mis otsuseid teevad teised inimesed. Seega tekivad huvide konfliktid. Konfliktisituatsiooniks nim olukorda, kus lõpptulemus sõltub vähemalt kahe erineva huviga osaleja tegevusest. Mänguteooria uurib konfliktide matemaatilisi mudeleid ja nende lahendamise täpseid meetodeid . Täisinformatsiooniga mängu korral on kõikidel mängijatel kasutada kogu teave eelmistel sammudel tehtud otsuste ja tulemuste kohta. Mittetäieliku informatsiooniga mängus on teave osaline. Kooperatiivsete mängude korral moodustavad mängijad ühiste huvidega rühmi, neid nim koalitsioonideks. Võimalik koostada ühiskoalitsioon ning jaotada võit "õiglaselt". Koalitsioonideta mängu korral on igal osalejal oma huvid, koopereerumist ei toimu. Enamasti on vaadeldud kahe isiku mänge, kuigi tegelikus elus on tavaliselt osalejaid rohkem. Mängu kirjeldus peab määrama osalejate hulga, nende kõikvõimalike strateegiate koetelu, käikude sooritamise järjekorra ja nende tulemuste arvnäitajate kujul. Käik on ühe võimaluse valimine mängu reeglitega määratud variantide hulgast. Mäng on normaalkujul, kui iga mängija jaoks on antud tema strateegiate hulk ja võidufunktsiooni väärtus selle hulga elementidel. Koalitsioon on mängijate hulga alamhulk.
27. Mängu lahendamine domineerivate strateegiate ja sadulpunkti abil Mängu lahendamiseks domineeriavte strateegiate korral on vaja mõlemal mängijal leida enda parim strateegia. Kuna mängumaatriks kujutab endast I mängija võite ja II kaotusi, peab I mängija leidma maatriksist maksimaalse rea ja II mängija minimaalse veeru . I maksimeerib oma võite, teine minimeerib kaotusi. Selleks, et selline rida peab iga element antud reas olema suurem või võrdne elementidega samas veerus, kuid teistes ridades. Stateegiate lõikepunkt(element) on sadulpunkt . Juhul kui maksimaalne rida ja minimaalne veerg puuduvad, tuleb leida sadulpunkt. Sadulpunkt leitakse, kui igast reast leitakse minimaalne element, mille seast leiame maksimaalse. Seda suurust nim mängu alumiseks hinnaks ja tähistatakse -ga. Igast veerust leitakse maksimaalne element, mille seast valitakse minimaalne. Seda suurust nim mängu ülemiseks hinnaks, ning tähistatakse -ga. Juhul kui = ongi antud element sadulpunkt. Sadulpunkte võib olla ka mitu. Üldjuhul kehtivad võrratused: = ! ! !" ! ! !" = Kui domineerivaid stateegijaid ja sadulpunkti ei leidu, tuleb ülesanne lahendada optimaalsete segastrateegiate kaudu, lahendades LP ülesande.
28. Mängu taandamine LP ülesandeks (võidufunktsioon, optimaalsete segastrateegiate definitsioon) Esimese mängija segastrateegia P=(p1,p2,...,pm) on vektor, mille komponendid võrduvad vastavate mängumaatriksi ridade valimise tõenäosustega. Puhta strateegia korral on üks component pk=1 ning ülejäänud komponendid 0d. Vastasmängija segastrateegia on Q=(q1,q2,...,qn)T on veeruvektor. Võidufunktsion M(P,Q) võrdub definitsiooni kohaselt I võidu matemaatiliste ootustega, kui mängijad kasutavad segastrateegiaid P ja Q. ! !
, = !" ! ! !!! !!! 1 2 N: P=(1/7, 6/7), Q=(3/7,4/7)T, A= . -3 4 M(P,Q)=1/7(3/7+8/7)+6/7(-9/7+16/7)=53/49. See tähendab, et esimese mängija keskmine võit 53/49 ja teise mängija kaotus on sama suur. Optimaalne segastrateegia P* on selline vector, mis rahuldab võrratust M(P*,j) mis tahes II mängija puhta strateegia j korral, teise mängija optimaalne segastrateegia Q* peab rahuldama võrratust M(I,Q*) mis tahes I mängija puhta strateegia I korral, arvu nim mängu hinnaks. Seletada näite põhjal: 4 2 = 3 4 ; vajadusel tuleb maatriksi kõikidele liikmetele liita positiivne arv, et kõik arvud maatriksis 5 1 oleksid positiivsed. Saame M(P,j=1) =M(P,Q)=(1,0)T. M(P,j=1)=4p1+3p2+5p31 M(P,j=2)=2p1+4p2+p31 p1+p2+p3=1 P0 Analoogiliselt koostame valemi 2 jaoks. Hiljem leiame, et 1= 2. Tähistame xi=pi/1, yi=qi/2 I mängija tahab oma võite maksimeerida, ehk kui me asendame p'd x'dega, tahab ta seda funktsiooni minimeerida. Saame teisendades LP ülesande: (teisendused jagan läbi -ga) z=x1+x2+x3=1/1àmin 4x1+3x2+5x31, 2x1+4x2+x31 x0. Sarnaselt koostame ka LP ülesande II mängija kaotuse kohta, kus sihifunktsioon on vastassuunaline. Need kaks ülesannet on duaalülesanded. Kuna optimaalsed lahendid z*=w*, siis järelikult 1/1=1/2, seega 1=2=. Lahendades ühe neist LP ülesannetest saamegi optimaalse segastrateegia, mida saab laiendada duaalülesande kaudu ka teisele mängijale. Märkused: Iga nullusummalist kahe isiku mängu saab lahendada LP ülesane abil, kui selleks pole vajadust lui leidub sadulpunkt. LP ülesande lahendamine käib tavalsite simpleksülesannete reeglite järgi.
29. Mänguteooria põhiteoreem, järeldused J. von Neumann : Mis tahes maatriksiga kahe isiku nullsummalises mängus on optimaalsed strateegiad. Teoreemi pole vaja tõestada, sest eelmises punktis toodud optimaalsete strat arvutamise eeskiri. Märkused: 1. Opt strat võib olla mitteühene 2. Optimaalsetel segastrat on sadulpunktiga sarnased omadused. Mängu hind on I mängija keskmine garanteeritud võit ja II mängija keskmine garanteeritud kaotus optimaalsete strat P* ja Q* korral. 3. . Alumine hind on esimese mängija maksimaalne garant võit puhaste strat korral, mängu hind aga maksimaalne keskmine garant võit segastrat kasutamisel . Kuna puhas strat on üks segastrat erijuhus, siis kehtibki vasakpoolne võrratus. Analoogselt tõestatakse ka parem pool. 4. Mänguteooria põhiteooria kaudu võib tõestada duaalsusteooria. 5. Linaarset ülesannet saab teisendada kahe isiku nullsummaliseks maatriksmänguks.
30. Kooperatiivse mängu karakteristlik funktsioon, tulemusvektor Mängijate hulka tähistame sümboliga I=(1,2,...,n). Hulga I alamhukli nim koalitsioonideks ja kasutame nende jaoks tähistusi S ja T. Karatelislikuks funktsiooniks nim seost, mis iga koalitsiooni korral määrab üheselt postiivse reaalarvu (S). Kooslus (I, ) määrab mängu, mida nim kooperatiivseks. Karakterislik funktsioon on tõlgendatav kui koalitsiooni S garanteeritud võit ülejäänud mängijate mis tahes otsuste korral. Mängu nim superaditiivseks, kui mis tahes kahe ühisosata koalitsiooni S ja T korral onkahe koalitsiooni võimalused eraldi väiksemad/võrdsed kui koos. Mängu tulemusvektor määrab kõigi mängijate võidud xi, mis peaksid olema väiksemad kui üheliikmeliste koalitsioonide garanteeritud võidud i. Mängu nim mitteoluliseks, kui kõikide mängijate ühinemisel koalitsiooni ei suurene nedne võidud.
31. Kooperatiivse mängu taandamine LP ülesandeks N-tuuma kasutamine kooperatiivse ülesande lahendamisel annab võimaluse lahendada nii sellist ülesannet kus tuum on tühi hulk, kui ka siis kui tuum on liiga lai. Otsime sellist tulemusvektorit x, mille korral koalitsioon S saab kasumit, mis erineb võimalikult vähe karakteristliku funktsiooni väärtusest (S). Võtame kasutusele mõiste ekstsess : = - !! ! Mängu N-tuumaks nim sellist tulemusvektorit x*, mille korral kõikvõimalike koalitsioonide järgi leitud maksimaalne ekstsess on minimaalne tulemusvektorite x järgi, mis on kollektiivselt ratsionaalsed. LP ülesande koostamisel vaadeldakse kõiki koalitsioone, mis on võimelised töö ära tegema. Tulemus on 1, ning igale koalitsioonile liidetakse muutuja y. Samal ajal yàmin. y on võrdne -ga, ehk siis kitsendustel on kõikide koalitsioonide võrratused.
32. Diferentsiaalvõrrandid (põhimõisted, Cauchy'i ülesanne) Esimest järku difvõrrandil on kuju F(x,y,y')=0. Kui seda võrrandit saab lahendada võib teda esitada kujul y'=f(x,y). Esimest järku dif.võrrandi üldlahendiks nim funktsiooni y=(x,C), mis sõltub konstandist C ja rahuldab tingimusi a)rahuldab dif.võrrandit C mistahes konkreetsel väärtusel ; b) olenemata algtingimusest võib leida C väärtuse C=C0 , et funktsioon y= (x,C0) rahuldab antud algtingimust. Eeldatakse , et väärtused x0 ja y0 kuuluvad suuruste x ja y muutumispiirkonda, milles on täidetud lahendi olemasolu ja ühesuse teoreemi tingimused. Erilahendiks nim mistahes funktsiooni y= (x,C0), mis saadakse üldlahendist y=(x,C), kui selles suvalisele konstandile C anda konkreetne väärtus C=C0. Seost (x,y,C0)=0 nim sel juhul võrrandi eriintegraaliks. Üldlahendi geomeetriliseks tõlgenduseks on koordinaattasandil asetsev joonteparv, mis sõltub ühest suvalisest konstandist C. Neid jooni nim antud dif.võrrandi integraaljoonteks. Cauchy'i ülesanne: y'=f(x,y). Leida selline lahend, mis algtingimustel y(x0)=y0 ???
33. Eralduvate muutujatega ja homogeenne võrrand M(y)dy=N(x)dx ­ võrrandi teisendavust sellisele kujule nim muutujate eraldamiseks. ! Homogeenset võrrandit iseloomustab võrrand: y'=f ! . Asendusega u=y/x saab homogeense võrrandi teisendada eralduvate muutujatega võrrandiks u ja x-i suhtes. !" ! ! N: !" - ! = ! ! ! ! = ! + ! = + ! , = ! = , = + ' !" + = + !. !" !! !" ! = !! = ! . 34. Lineaarne difvõrrand, teoreem Lineaarseks esimest järku võrrandiks nim võrrandit, mis on lineaarne tundmatu funktsiooni ja selle esimest järku tuletise suhtes. Tal on kuju dy/dx+P(x)y=Q(x), kus P(x) ja Q(x) on argumendi x pidevad funktsioonid. Mittehomogeenne: y'+p(x)y=q(x) (1) Homogeenne: y'+p(x)y=0 (2) Homogeenses dif.võrrandis saab muutujaid eraldada. dy/dx=-p(x)y (dy/y)=-p(x)dx lny=-p(x)dx+lnc elny =c*e-p(x)dx See on homogeense võrrandi üldlahend Teoreem: Mittehomogeense võrrandi (1) üldlahend=homoheense võrrandi üldlahend+mittehomogeense võrrandi erilahend . Seega : y= e-p(x)dx [ ep(x)dx*q(x)dx+c] . Kui sulud avada, siis teine liidetav on homogeense võrrandi üldlahend : y=c* e-p(x)dx
35. Teist järku homogeenne difvõrrand, kolm juhust On antud teist järku homog.dif.võrrand : y''+py'+qy=0 , p ja q on konkreetsed reaalarvud . Üldlahendi leidmiseks piisab kahe lineaarselt sõltumatu erilahendi leidmisest . y=ekx, kus k= const , siis y'=kekx, y''=k2ekx . Asendades need esimesse võrrandisse, same ekx (k2+pk+q)=0, kuna ekx 0, siis k2+pk+q=0. Viimast võrrandit nimetatakse karakteristlikuks võrrandiks. See on ruutvõrand, millel on kaks lahendit. Võimalikud on 3 juhtu: 1) Karakteristliku võrrandi lahendid on reaalsed ja erinevad : k1k2 . Erilahenditeks on funktsioonid y1=ek1x, y2=ek2x , need lahendid on lineaarselt sõltumatud, sest y2/y1const. Üldlahendil on kuju y=C1ek1x+C2ek2x 2) Karakteristliku võrrandi lahendid on komplekssed : k1=+i , k2= ­ i, kus =-(p/2) , !! = - ! Erilahendi võib kirjutada kujul y1=e(+i)x, y2=e( - i)x. Üldlahendil on kuju y=C1excosx+C2 exsinx. Erijuht on see kui karakteristliku võrrandi lahendid on puhtimaginaarsed, selleks peab p=0 ja tal on kuju y''+qy=0, karakteristlik k2+q=0 ja üldlahend y= C1cosx+C2sinx 3) Karakteristliku võrrandi lahendid on reaalsed ja võrdsed: k1=k2 . Üks erialhend y1=ek1x saadakse varasemate arutluste põhjal. Leida on vaja teine, mis oleks esimesest lineaarselt sõltumatu.Otsime teist kujul y2=u(x)ek1x , u(x) on määratav tundmatu funktsioon. Lahendada tuleb võrrandi ek1x u''=0 või u''=0, integreerides same u=Ax+B, kui A=1 ja B=0, siis u=x. Teiseks erilahendiks saab võtta y2=xek1x See on esimesest lineaarselt sõltumatu, kuna y2/y1 =xconst. Üldlahendiks on funktsioon : y=C1ek1x+C2xek1x
36. Diferentsiaalvõrrandi lahendi stabiilsus Uurime seda esimest järku konstantsete kordajatega lin.dif.võrrandi näite abil : y'+ay=b Tasakaaluväärtus y* on selline suurus, mis ei muutu ajas. Kui y ei muutu, siis tema tuletis aja järgi =0, seega tasakaaluväärtus y*=b/a ; a0. Kui a=0, siis y'=b, y(t)=bt+c, integreerimise constant c=y(0) y(t)=bt+y(0). Eeldame nüüd et a0, siis lineaarse DV lahendamise valemis p=a, q=b. Leiame üldlahendi : y(t)=e-t( etbdt+c)= e-t(et b/a+c)=b/a +c*e-t .Leiame konstandi c, votes t=0,c=y(0)-y*. Seegay(t)=y*+y(0)-y* e-t .Selle valemi järgi saab leida süsteemi seisundi igal ajamomendil t, arvestades algseisundit y(0) ja tasakaaluseisundit y*. Üldjuhul võib öelda, et dünaamiline protsess on stabiilne (läheneb tasakaaluväärtusele), kui constant a0. Kui a0, on protsess ebastabiilne, y läheneb lõpmatusele.
37. Dünaamilised süsteemid (turu tasakaalu mudel) Joonis Sellel on eeldatud, et nii nõudlusfunkts qD kui ka pakkumisfunkts qS on lineaarsed. Nende argument p on 1 ühiku kauba hind, kantud vertikaalteljele, horisontaalteljel kauba kogus q kui hinna funktsioon. Sirglõigu AB pikkus iseloomustab defitsiidi suurust antud hinna p0 korral. Tasakaalupunkti p* leidmiseks võrdsustame pakkumise ja nõudluse ­a+bp=c-dp, p*=(a+c)/(b+d) . Oletame, et hinnamuutus ajas on lineaarses sõltuvuses nõudluse ja pakkumise vahest, see on kirjeldatav järgmise võrrandi abil dp/dt=k(qD ­ qS ). Kui hind ei võrdu tasakaaluväärtusega p*, algab hinna muutumise protsess, mis on määratud eelmise diferentsiaalvõrrandiga.Asendame selles võrranis nõudluse ja pakkumise toodud lineaarsete avaldistega: (dp/dt)+k(b+d)p=k(a+c). Selle protsessi tasakaaluväärtus on eelmise punkti põhjal samasugune nagu esimeses valemis. Hinna muutumist aja jooksul kirjeldab : p(t)=p*+[p(0)-p*]e-k(b+d)t . Tasakaaluks on vaja, et k(b+d)0, st k0. +k tähendab, et defitsiidi (qD ­ qS 0) korral hind suureneb, sest p'0 , p hakkab lähenema oma tasakaaluväärtusele, defitsiit väheneb, kuni saavutatakse p*. Antud näites dp/dt=k(qD ­ qS ) turg tasakaalustub ise väärtuse p* korral.
38. Diferentsiaalvõrrandi arvuline lahendamine y'=f '(x)=limx0 (y/x) ; y'(y/x), kui x on väike, siis y'x y; y1-y0= yy'x; y1=x0+y' x ; y'=F(x,y). Kui x on väike, siis y1=y(x1) ; y1y0+y'(x0)* x ; ; y1y0+F(x0, y0 )x (1) Näide: y'=(dy/dx)=x . Antud: y(1)=2. (1 on x0 ja 2 on y0). dy=xdx y=(x2/2)+C 2=1/2+C C=3/2. Erilahend y=(x2+3)/2 ; y(1,01)=[(1,01)2+3]2=2,01005 Lahend valemi (1) abil : y1=2+(dy/dx)x(1,01-1)=2,01. Arvuline lahendamine valemi (1) abil on universaalne meetod, mis on rakendatav ka siis, kui integraalid ei ole võetavad. Meetodi täpsus on x2.