Operacijų tyrimas teorija

 1. Operacijų tyrimo esmė 1) Operacijų tyrimo uždaviniuose visada nagrinėjamos organizacinės sistemos, t.y tokios sistemos, kurias sudaro tikslingai veikiantys organizuoti žmonių kolektyvai, naudojantys įvairias technines priemones. (Nagrinėjami mikro lygiu) 2) OT uždaviniai visada orientuoti į sprendimo priėmimo procesą. Jų tikslas – ne tik smulkiai ištirti nagrinėjamą, bet ir paruošti mokslines rekomendacijas racionaliam sprendimui priimti. Sprendimams, kuriems pagrįsti naudojami OT metodai – paprastai ne “einamieji”, o “strateginiai” sprendimai. 3) OT uždavinių sprendimas visada remiasi nagrinėjamos sistemos modelių, dažniausiai matematinių modelių, sudarymu ir sprendimu. OT uždavinio sprendimas visada remiasi sistemiškumo principu. OT dėmesio centre – konkretus praktinių problemų sprendimas. 2. Operacijų tyrimo uždavinių klasės ir sprendimo etapai UŽDAVINIŲ KLASĖS: 1) Paskirstymo uždaviniai. Juos sprendžiant, siekiama racionaliai paskirstyti ribotus išteklius įvairiems darbams atlikti. Optimaliam gamybos planui sudaryti, materialinio techninio aprūpinimo uždaviniams spręsti, transporto priemonių, įrengimų paskirstymui, darbams optimizuoti. 2) Masinio aptarnavimo uždaviniai. Šiais uždaviniais modeliuojamos situacijos, kuriose tam tikri nuolat atsirandantys darbai turi būti atliekami keliais įrengimais (aptarnavimo kanalais). Sprendžiama kaip organizuoti aptarnavimą, kad nuostoliai dėl eilių susidarymo ir kanalų prastovų būtų minimalūs. 3) Pakeitimo ir remonto uždaviniai. Sprendžiant šiuos uždavinius nustatomas optimalus įrengimų pakeitimo arba profilaktinių remontų laikas, kad išlaidos remontams (pakeitimams) ir nuostoliai dėl avarinių prastovų būtų minimalūs. 4) Atsargų valdymo uždaviniai. Šiuose uždaviniuose nagrinėjamas optimalios atsargų apimties nustatymas įvairiose ūkinės veiklos baruose. 5) Sutvarkymo ir tvarkaraščių teorijos uždaviniai. Šie uždaviniai formuluojami ir sprendžiami, norint nustatyti optimalią tam tikrų darbų atlikimo tvarką. 6) Maršruto sudarymo ir tinklinio planavimo uždaviniai. Šie uždaviniai sprendžiami, kai reikia susieti kelis punktus trumpiausia arba pigiausia ryšių linija, nutiesti komunikacijas, suplanuoti transporto srautus. 7) Paieškos uždaviniai. Formuluojami ir sprendžiami, kai turint ribotus laiko, darbo, įrengimų išteklius, reikia taip organizuoti paiešką, kad tikimybė surasti ieškomą objektą būtų didžiausia. 8) Konfliktinių situacijų uždaviniai. Sprendžiami, kai reikia priimti sprendimą interesų nesutapimo sąlygomis. SPRENDIMO ETAPAI: 1) Problemos formulavimas. Šiame etape būtina kuo smulkiau išnagrinėti ekonominę situaciją, su įmonės vadovais patikslinti užduotį, nuspręsti į kokius dalinius uždavinius verta padalinti visą sprendimą, kaip detaliai nagrinėti problemą. Gerai išnagrinėti ir suprasti tikslą. Išrinkti esminius modeliuojamossituacijos faktorius, apsispręsti dėl įvairių kintamųjų skaičiaus ir jų ryšių formalizavimo galimybių, paruošti formaliam užrašymui sistemos tikslus, išsiaiškinti, ar yra OT uždavinių klasė, kuriai galima priskirti nagrinėjamą problemą. Reali ekonominė situacija paprastinama – kai kurie faktoriai atmetami 2) Modelio sudarymas. Reikia apsispręsti dėl modelio tipo (statiniai, dinaminiai, stochastiniai, imitaciniai išrinkti geriausią) ir jo nežinomųjų, juos galutinai formalizuoti 3) Sprendimas. Šiame etape reikia išsiaiškinti sprendimo metodus, juos pateikti aiškių algoritmų pavidalu. Šiame etape turi būti surinkti visi reikalingi duomenys, statistikos metodais įvertintos priklausomybės. 4) Modelio tyrimas. Šiame etape tiriama, ar modelis pakankamai gerai atvaizduoja modeliuojamą situaciją. Modelio sprendimai turi teisingai reaguoti į įvairius paramatrų ir duomenų pasikeitimus. Patikrinamas jo jautrumas. Jei nedaug pasikeitus modelio parametrams sprendinys lb keičiasi, tai naudojant tokį modelį bus sunku gauti pagrįstus rezultatus. (gaunami kai kurie įdomūs rezultatai) 5) Įdiegimo etapas. Pagrįstos ir detaliai išbagrinėtos rekomendacijos pateikiamos įmonės vadovams ir pradedamos įgyvendinti. MATEMATINIAI OT UŽDAVINIŲ SPRENDIMO METODAI: 1) Tiesinės algebros ir matematinės analizės. Patogu operuoti vektoriais,matricomis, f-cjomis, jų diferencijavimu ir pan. 2) Kombinatorikos. Sprendžiant sutvarkymo, paskirstymo,maršruto sudarymoir kt uždavinius, kuriuose iš didžiulio variantų skaičiaus reikia išrinkti geriausią. 3) Grafų teorija. Tiesiogiai susijusi su tinklinio planavimo, maršrutų sudarymo ir sutvarkymo užd. 4) Tikimybių teorijos metodais sprendžiami masinio aptarnavimo, paieškos, kai kurie paskirtymo, atsargų valdymo, pakeitimo ir remonto užd. 5) Matematinės statistikos būtina įvertinti sudaromų modelių parametrus turimos info pagrindu. 6) Funkcinė analizė kai susiduriame su begalinio laiko procesais, ieškome f-cijų, išreiškiančių geriausią nagrinėjamų ekon procesų raidą. 7) Lošimų teorija konfliktiniams uždaviniams 8) Matematinis programavimas(surasti ekstremalią reikšmę): a. Tiesinis programavimas formuluojant tiesinio programavimo užd. b. Diskretinis modeliavimui tokių situacijų, kuriose geriausią sprendimą reikia priimti baigtinėje arba skaičioje alternatyvų aibėje. (sveikaskaitinis,kai sprendinys turi būti išreikštas sveikaisiais skaičiais) paskistymo, sutvarkymo, maršrutų sudarymo užd.) c. Stochastinis kai atsižvelgiama į atsitiktinumo elementus 9) Optimalaus valdymo teorija naudojamos dvi nžn grupės – valdymai ir būsenos(pasekmės) a. Dinaminis daug kartų priimamiems sprendimams optimizuoti. Paskirstymo, atsargų valdymo, pakeitimo ir remonto, paieškos užd. 3. Gamybos planavimo uždavinys ir jo taikymai Nagrinėkime įmonę, kuri gali gaminti n skirtingų produktų tipų, naudodama m išteklių rūšių. Laikysime, kad yra žinoma: b1, b2, ..., bm – visų išteklių apimtys aji – kiek i-tojo ištekliaus vienetų reikia j-tojo produkto vienetui pagaminti. (i=1,m j=1,n) cj – kiek litų pelno duoda j-tojo prdukto vieneto gamyba. Reik surasti gamybos planą duodantį maksimalų pelną nurodytomis sąlygomis. Ieškomasis planas yra vektrius (x1, x2,..., xn). Gamybos planavimo uždavinys: c1x1 + c2x2 + ... + cnxn (max) – tikslo f-cija a11x1 + a21x2 + ... + an1xn  b1 (reikės 1rūšies išteklių) a12x1 + a22x2 + ... + an2xn  b2 .............................................. a1mx1 + a2mx2 + ... + anmxn  bm x1  0, x2  0, ... , xn  0 4. Dietos (mišinių) uždavinys ir jo taikymai Sakykim mes galim pirkti n maisto produktų rūšių. Kiekviename iš tų maisto produktų yra keletas arba visos iš m maistingųjų medžiagų. Žinome: b1, b2, ..., bm – kiek šių maistingųjų medžiagų organizmui reikia per parą aji – i-tosios maistingosios medžiagos kiekis j-tojo maisto produkto vienete (i=1,m j=1,n) cj – j-tojo produkto vieneto kaina. Reikia kuo pigiau nupirkti tokį maisto produktų rinkinį, kad organizmo poreikis maistingosioms medžiagoms būtų patenkintas. (x1, x2,..., xn) – maisto produktų pirkimo planas. Dietos (mišinių) uždavinys: c1x1 + c2x2 + ... + cnxn (min) a11x1 + a21x2 + ... + an1xn  b1 (1osios maistingosios medžegos kiekis) a12x1 + a22x2 + ... + an2xn  b2 .............................................. a1mx1 + a2mx2 + ... + anmxn  bm x1  0, x2  0, ... , xn  0 (negalime pirkti neigiamos apimties) Kartais šis uždavinys vadinamas mišinių uždaviniu. Tokiu atveju kalbama ne apie maisto produktus, o apie tam tikrų naudingų medžiagų mišinius. Paėmus kokį nors kiekvieno iš šių mišinių kiekį ir kartu apdorojus, gaunamas produktas su pageidaujamu naudingų medžiagų santykiu (pvz., metalų lydinys). 5. Geometrinis tiesinio programavimo uždavinių interpretavimas ir sprendimas Geometriškai interpretuosime tiesinio programavimo uždavinį su dviem nežinomaisiais, nes tik tokį uždavinį galima atvaizduoti plokščiame dvimačiame brėžinyje. Nagrinėsime uždavinį c1x1 + c2x2 (max) a1ix1 + a2ix2  bi (i=1,2,..,m) x1  0, x2  0 Nelygybę a1ix1 + a2ix2  bi užrašykime kaip lygybę a1ix1 + a2ix2 = bi. Nubrėžiame šią tiesę. Aibė taškų (x1, x2), kurių koordinatės tenkina nelygybę a1ix1 + a2ix2  b1 priklausys vienai plokštumos, perskirtos šia tiese, pusei. Kuriai, sužinome patikrinus ar taškas (0;0) yra ieškomoje plokšumos pusėje. Taip atžymime ir kitus apribojimus. Tada atvaizduojama neneigiamus apribojimus x1  0, x2  0. Kadangi ieškomi taškai turi tenkinti visus apribojimus, jie priklauso nubrėžtų plokštumų sankirtai ir sudaro daugiakampį (briaunainį). Kiekvienas šio briaunainio taškas yra leistinas kandidatas į optimalius. Atvaizduojama tikslo funkciją c1x1 + c2x2 =  Šios funkcijos grafikas yra plokštuma trimatėje koordinačių sistemoje (x1, x2, ), todėl brėžinyje vaizduosime ne funkcijos grafiką, o jos lygio linijas. Šios linijos jungia plokštumos taškus, kuriose tikslo funkcijos reikšmė ta pati.(c1x1 + c2x2=1) Taškas su didžiausia tikslo funkcijos reikšme yra uždavinio sprendinys. grafikas Taškai, kurių koordinatės tenkina uždavinio apribojimus (leistini planai), sudaro daugiabriaunes aibes. Sprendinį (optimalų planą) visada gauname tokių aibių viršūnėse (kraštutiniuose taškuose). Tiesinio programavimo uždavinys gali būti neišsprendžiamas dėl dviejų priežasčių: apribojimų prieštaringumo tikslo funkcijos neaprėžtumo. grafikai Optimalus planas ne vienintelis Optimalus planas gali būti ten, kur lygio linija kerta apribojimą grafikai 6. Pagrindinės iškiliosios analizės sąvokos Tiesinės erdvės Rn aibė X  Rn vadinama iškiliąja aibe, jei bet kokiems x1  X ir x2  X ir bet kokiam skaičiui   0, 1 galioja sąlyga  x1 + (1 - ) x2  X. brėžinys Aibė X yra iškilioji, jei bet kuriuos du jos taškus jungianti atkarpa visa priklauso tai aibei. Tiesinė erdvė Rn yra iškilioji aibė. Aibė H vadinama erdvės Rn hiperplokšuma, jei H = x  Rn h1x1 + h2x2 + ... + hnxn = h Čia h1, h2, ..., hn ir h – hiperplokšumos padėtį nusakantys skaičiai. Erdvėje R2 hiperplokštuma vadinama tiese, erdvėje R3 – plokštuma. Hiperplokštuma yra iškilioji aibė. Aibė P vadinama puserdve, jei P =  x  Rn h1x1 + h2x2 + ... + hnxn  h  Puserdvę sudaro visi Rn taškai, esantys vienoje pusėje nuo kažkurios hiperplokštumos. Puserdvė taip pat yra iškilioji aibė. Dviejų iškiliųjų aibių X ir Y sankirta X ∩Y (jei ji netuščia) yra iškilioji aibė.(jų sąjunga nėra iškilioji aibė) Iškiluma nagrinėja speciali matematikos sritis – iškilioji analizė. Vektorių x1, x2,...., xn iškiliuoju dariniu (arba iškiliaja kombinacija) vadiname vektorių x = 1x1 + 2x2 + … + nxn, kai 1 + 2 + … + n =1 ir 1, 2, …, n  0 brėžinys Iškiliosios aibės X taškas x  X vadinamas šios aibės kraštutiniu tašku, jei jis negali būti išreikštas kaip dviejų skirtingų šios aibės taškų iškilusis darinys. brėžinys Iškilioji aibė vadinama daugiabriaune, jei jos kraštutinių taškų skaičius yra baigtinis. Aprėžta daugiabriaunė aibė vadinama briaunainiu.(kiekvienas briaunainio taškas gali būti išreikštas kaip jo kraštutinių taškų iškilusis darinys) Brėžinys Hiperplokštuma atskiria dvi netuščias aibes X ir Y, jeigu visiems x X galioja Jeigu dvi netuščios iškiliosios aibės neturi bendrų vidinių taškų, tai egzistuoja jas atskirianti hiperplokštuma. Hiperplokštuma H griežtai atskiria netuščias aibes X ir Y, jei bent viena iš šių nelygybių griežta. Hiperplokštuma H vadinama aibės X atramine hiperplokštuma, jei . Jei aibė X uždara, tai su atramine plokštuma ji turi bent vieną bendrą tašką. Visi aibės X taškai yra vienoje atraminės hiperplokštumos tiesėje, nes pagal apibrėžimą be to ši hiperplokštuma liečia aibę ta prasme, kad aibėje yra taškų, kaip norima artimų hiperplokštumai. Pirmoji atskyrimo teorema. Jei dvi netuščios iškiliosios tiesinės erdvės Rn aibės neturi bendrų vidinių taškų, tai egzistuoja jas atskirianti hiperplokštuma. Antroji atskyrimo teorema. Jei dvi netuščios uždaros iškiliosios tiesinės erdvės Rn aibės neturi bendrų taškų ir bent viena jų aprėžta, tai egzistuoja jas griežtai atskirianti hiperplokštuma. Išvada. Tegu X – iškilioji uždara aibė, o taškas z  X. Tada egzistuoja aibės X atraminė hiperplokštuma, griežtai atskirianti X ir z. Laikysime, kad visi vektoriai yra vektoriai – stulpeliai, tik c ir p yra eilutės 7. Tiesinio programavimo uždavinių tipai ir jų pavertimas vienas kitu. Bendras tiesinio programavimo uždavinys: c1x1 + c2x2 + ... + cnxn (extr) di  a1ix1 + a2ix2 + ... + anixn  bi , i = 1,m. =cx (extr) d  Ax  b, u  x  v. uj  xj  vj , j = 1, n. Vektorius x vadinamas planu, kadangi jis išreiškia planuojamas gaminti arba pirkti produktų apimtis, staklių paskirstymo darbams planą ir kitus analogiškus techninius-ekonominius sprendimus. (tikslo f-cija, apribojimų sistema, matrica, vektoriai) Tikslo funkcija išreiškia modeliuojamo obkekto tikslą ir yra maksimizuojama arba minimizuojama. Apribojimų sistema parodo kokie planai potencialiai gali būti realizuoti. Dydžiai di ir bi gali būti baigtiniai arba begaliniai (neapribojama iš viršaus ar apačios jei begalinis) Uždavinio leistinų planų aibe vadinsime aibę X = x  Rn  d  Ax  b, u  x  v . Šios aibės elementus vadinsime leistinais planais. Leistinas uždavinio planas x*  X vadinamas jo optimaliu planu arba sprendiniu, jei cx*  cx  x  X (kai uždavinys sprendžiamas maksimumui) arba cx*  cx  x  X (kai uždavinys sprendžiamas minimumui). Kanoninis tiesinio programavimo uždavinys: Kai tikslo funkcija maksimizuojama, di = bi (i = 1,m); uj = 0, vj =  (j = 1, n). (max) cx, Ax = b, x  0. Standartinis tiesinio programavimo uždavinys: Kai tikslo funkcija maksimizuojama, di = -  (i = 1,m); uj = 0, vj =  (j = 1, n). (max) cx, Ax  b, x  0. Uždavinio vertimas į standartiniu: (min) cx = - cx (max) aix  di /(-1) - aix  - di xj  vj galima užrašyti kaip ejx  vj ir įtrauktas į apribojimus-nelygybes. uj  xj (uj > -) gali būti pertvarkytas panaudojus naują nežinomajį xj = xj – uj, tada visur vietoj xj reikės įstatyti xj + uj ir reikalauti xj  0. Jei uj = - , tai xj = x’j – x’’j, x’j  0, x’’j  0. Standartinio uždavinio vertimas kanoniniu: Paimkime m papildomų nežinomųju y1, y2, ..., ym vektorių y  Rm. Užrašykime tokį uždavinį: (max) cx, Ax + y = b, x  0, y  0. Įrodymas: X1={x≥0|Ax≤b} X2={ x≥0|Зy≥0, Ax+y=b} įrodyti, kad X1=X2: x X1rodykl x X2 x≥0 Ax≤b y=b-Ax≥0 rod Зy≥0, Ax+y=b rod x X2 x X2 rodykl x X1 x≥0 Зy≥0, Ax+y=b rod Ax≤b rod x X1 X1=X2 ranka 8. Kanoninio tiesinio programavimo uždavinio savybės Leistinų planų aibė X={x Rn |Ax=b, x≥0 } 1 prielaida. Kanonio uždavinio leistinų planų aibė X netuščia, t.y. X Ø 2 prielaida. Tikslo funkcija cx aprėžta aibėje X iš viršaus. Apribojimai vienas kitam neprieštarauja ir tikslo f-cija gali įgyti kaip norima dideles reikšmes Laikysime kad m  n, r(A) = m. (jei m>n, tai turėtume daugiau lygčių nei nežinomųjų: lygtys gali prieštarauti viena kitai aba dalį lygčių galėtume pašalinti) 1 savybė. Jei patenkinta 1 prielaida, tai kanoninio uždavinio leistinų planų aibė X – uždara iškilioji aibė. Įrodymas. Aibę X sudaro m hiperplokštumų, apibrėžiamų lygtimis aix = bi ir n puserdvių xj  0, j = 1,n sankirta. Kadangi hiperplokštumos ir puserdvės – uždaros iškiliosios erdvės Rn aibės, tai uždara ir iškilioji ir jų sankirta. Apibrėžimas. Leistinas kanoninio uždavinio planas x  X vadinamas šio uždavinio atraminiu planu, jei matricos A stulpeliai aj su numeriais j, kuriems xj  0, yra tiesiškai nepriklausomi. (300240)(tik tie kurie ne nuliai) Lema. Tegul patenkintos 1 ir 2 prielaidos. Tada bet kokiam leistinam kanoninio uždavinio planui x  X galima rasti tokį atraminį šio uždavinio planą xa , kad galiotų nelygybė cxa  cx. Įrodymas. Imkim bet kokį x  X. Jei x – atraminis planas, tai xa = x , ir įrodymas baigtas. Jei x ne atraminis planas, tai stulpeliai aj su numeriais j  J tiesiškai priklausomi. (Čia J = 1  j  n  xj > 0. Todėl egzistuoja skaičiai j, j  J, ne visi lygūs nuliui, su kuriais galioja ajj = 0 t.y. tiesinis stulpelių aj darinys lygus nuliui. Apskaičiuokime sumą . Jei suma neigiama, padauginame visus j iš –1 ir galime užrašyti Imkim bet kokį skaičių  ir sudarykim planą x+  Rn pagal taisyklę xj + j , j J; x+j = 0 , j  J. Koks bebūtų  galioja Ax+ = ajx+j = ajxj +  ajj = ajxj = b. Taigi bet kokiam  lygybė Ax+ = b bus patenkinata. cx+ = cjx+j = cjxj +  cjj, cx+ = cx +  cjj Didinkime . 1) Tegu cjj > 0. Jei visiems jJ galiotų j  0, tai cx+ neaprėžtai didėtų, didinant . Tuo pat metu x+ liktų leistinas planas. Todėl tikslo funkcija būtų neparėžta, kas prieštarauja 2 prielaidai. Vadinasi j tarpe yra neigiamų. Didinkime  kol bent vienas kuris nors x+j taps lygus nuliui. Taip gausime leistiną planą x+ su bent viena nuline koordinate daugiau ir cx+ > cx. 2) cjj = 0. Jei visi j  0, tai galime pakeisti jų ženklus, nepažeisdami lygybės. Taigi j tarpe būtinai turi būti neigiamų. Didindami  gauname leistiną planą x+, cx+ = cx. Tikriname ar x+ atraminis planas. Kadangi jis turi viena nuline koordinate daugiau, negu x, tai stulpelių sistema, kuri turi būti tiesiškai nepriklausoma, vienu stulpeliu mažesnė. Jei x+ atraminis, tai ieškomas xa = x+ ir įrodymas baigtas. Priešingu atveju su planu xa atliekame visus veiksmus, kuriuos atlikome su planu x ir gauname dar vieną planą su dar viena nuline koordinate. Šį procesą tesiame tol kol gauname atraminį planą. Vėliausiai tai gali atsitikti paskutiniame žingsnyje, kai x+ turi vienintelę teigiamą koordinatę. Ją atitinkantis stulpelis,pagal padarytas prielaidas TN ir x+ ieškomas atraminis planas. 2 savybė. Tegul patenkintos 1 ir 2 prielaidos. Tada kanoninis uždavinys turi atraminį planą, ir šių planų skaičius baigtinis. Įrodymas. Kadangi X Ø, tai uždavinys turi bent vieną leistiną planą x  X. Pagal lemą tada egzistuoja ir atraminis planas xa : cxa  cx. Kiekvieną atraminį planą xa atitinka tiesiškai nepriklausoma matricos A stulpelių sistema, su kuria jis susietas lygybe ajxaj = b , čia J = j xaj > 0. Ši lygčių sistema dėl aj tiesinės nepriklausomybės turi vienintelį sprendinį, būtent xa . Taigi viena stulpelių sistema atitinka ne daugiau kaip vieną atraminį planą. Tačiau iš n stulpelių galime išrinkti tik baigtinį skaičių skirtingų stulpelių sistemų. Todėl ir atraminių planų skaičius baigtinis. 3 savybė. Kanoninis tiesinio programavimo uždavinys išsprendžiamas tada ir tik tada, kai patenkintos 1 ir 2 prielaidos. Įrodymas. Jei uždavinys išsprendžiamas, jis turi optimalų planą, kuris yra ir leistinas, o tikslo funkcija aprėžta. Taigi abi prielaidos patenkintos. Jei prielaidos patenkintos, tai pagal 2 savybę uždavinys turi baigtinį atraminių planų skaičių. Išrinksime iš jų tą, kuriame tikslo funkcijos reikšmė didžiausia. Pažymėkime jį x*: cx*  cxa visiems atraminiams xa. Akivaizdu, kad cx*  cx  x  X. Jei atsirastų x  X, kuriam galiotų cx  cx, tai pagal lemą atsirastų ir atraminis xa toks, kad cxa  cx > cx*. Bet juk x* - “geriausias” atraminis planas. Prieštara rodo, kad x* optimalus, taigi uždavinys išsprendžiamas. 4 savybė. Jei patenkintos 1 ir 2 prielaidos, tai tarp optimalių kanoninio uždavinio planų yra ir atraminių planų. Įrodymas. Jei x* - optimalus planas, tai egzistuoja atraminis xa , kuriam galioja cxa  cx*. Kadangi x* optimalus, tai cxa = cx*, ir xa taip pat optimalus. (tarp optimalių planų ne visi atraminiai, atraminiai būna tik kampuose) 5 savybė. Tegu x – kanoninio uždavinio atraminis planas. Tada teigiamų jo koordinačių skaičius ne didesnis už m, o likusios koordinatės nuliai. Įrodymas. Teigiamiems xj turi atitikti tiesiškai nepriklausomų stulpelių aj sistema. Kadangi šie stulpeliai m-mačiai, tai jų negali būti daugiau negu m. Todėl ir teigiamų xj skaičius neviršija m. (optimaliame atraminiame kanoninio uždavinio plane gali būti ir mažiau negu m teigiamų koordinačių, jei šis planas išsigimęs) Apibrėžimas. Kanoninio uždavinio atraminis planas vadinamas išsigimusiu, jei jo teigiamų koordinačių skaičius griežtai mažesnis už m. Uždavinys, turintis išsigimusį atraminį planą, vadinamas išsigimusiu uždaviniu. Teorema.Kanoninio uždavinio atraminis planas yra jo leistinų planų aibės X kraštutinis taškas. Atvirkščiai, kiekvienas X kraštutinis taškas yra uždavinio atraminis planas. 6 savybė. Kanoninio uždavinio leistinų planų aibė X yra iškila daugiabriaunė aibė. Įrodymas. X iškilumas įrodytas 1 savybėje. Kiekvienas X kraštutinis taškas yra uždavinio atraminis planas. Tačiau šių planų skaičius baigtinis, taigi ir X kraštutinių taškų skaičius baigtinis. 7 savybė. Tegu patenkintos 1 ir 2 prielaidos ir X* - optimalių kanoninio uždavinio planų aibė. Tada X* yra iškilioji daugiabriaunė aibė. Įrodymas. Pažymėsime optimalų uždavinio planą x* (toks planas egzistuoja, nes patenkintos abi prielaidos). Tegu * = cx*. Tada galima užrašyti X* = x  0  Ax = b, cx = * Aibei X* tinka visi samprotavimai išdėstyti 1, 3, 6 savybių įrodymuose ( tik vietoj m apribojimų-lygybių turime jų m+1). Todėl tinka ir 6 savybės teiginys. 9. Simpleksinio metodo esmė. Atraminio plano bazė. (max) cx, Ax = b, x  0. (1) Paimam kokį nors atraminį planą ir peržiūrime visus tam tikra prasme “kaimyninius” atraminius planus. Jei tarp jų nėra geresnio, t.y. su didesne tikslo funkcijos reikšme, turimas atraminis planas optimalus. Jei geresnis planas atsiranda, pereiname prie jo ir visą procesą kartojame iš naujo. Taip per baigtinį žingsnių skaičių pasiekiamas optimalus planas (arba įrodoma, kad jo nėra). x - atraminis uždavinio planas. Jei jis neišsigimęs, tai lygiai m jo koordinačių teigiamos, o jų numerių aibė J = 1  j  n  xj > 0 turi m narių. Jei x- išsigimęs planas, tai J papildysime iki m narių taip, kad stulpeliai aj jJ būtų tiesiškai nepriklausomi. Matricos A stulpelių sistemą ajjJ – baziniai stulpeliai; atraminio plano x bazė. Aibe J vadinsime plano x bazinių nr aibe, o nžn xj baziniais nžn. Praleisdami nebazines xj reikšmes, lygybę Ax = b užrašykime Ax = ajxj = ajxj = b (3) Kadangi stulpeliai aj , jJ tiesiškai nepriklausomi, tai bet koks kitas stulpelis, sakykim as (as=0) gali būti išreikštas kaip jų tiesinis darinys: as = xsjaj , sJ (4) Čia xsj – koeficientai. Juos naudojant galima susieti atraminį planą x ir bet kokį vektorių z , tenkinantį lygybę Az = b. b = Az = ajzj = ajzj + aszs = ajzj + (xsjaj)zs = (zj + xsjzs)aj sulyginę gautąją lygybę su (3), matome,kad turime dvi to paties vektoriaus b išraiškas, todėl xj = zj + xsjzs (5) 10. Simpleksinio metodo esmė. Pagrindinis žingsnis. Tarkim, kad mums žinomas bent vienas atraminis uždavinio planas x. Bandysime sukonstruoti „kaimyninį“ atraminį planą su didesne tikslo f-cijos reikšme. Imame bet kurią nebazinę x koordinatę xs=0 ir suteikiame jai teigiamąreikšmę xs=Q>0 norint,kad niekas nepakistų, reikia prie visų xj pridėti pataisas Δxj, tada: aj(xj+ Δxj)+ as Q= b ajxj+aj Δxj+ as Q= b aj Δxj+ as Q=0 įstatę as išraišką iš iš (4), gauname aj Δxj+Qxsjaj =0 kadangi stulpeliai aj jJ TN,tai jų tiesinis darinys =0 tik tada, kai lygūs 0 visi koeficientai prie aj Δxj+Qxsj=0  jJ (6) Δxj=­-Qxsj  jJ pažiūrėkime kaip pasikeičia tikslo f-cijos reikšmė Δφ= cj(xj+ Δxj)+cs Q - cjxj=cjΔxj+cs Q = cj(-Qxsj)+ cs Q= -Q(cjxsj- cs) Pažymėję Δs = cjxsj- cs(7), gauname Δφ=-Q Δs (8) Kadangi Q>0, tai Δφ ženklas priklauso nuo Δs ženklo: kai Δs>0 tikslo f-cijos reikšmė sumažėja, o kai Δs0 sJ, tai x – vienintelis optimalus planas. Įrodymas. Imkime bet kokį leistiną uždavinio planą z ir apskaičiuokime tikslo f-cijos reikšmę cz= cjzj+cszs Kadangi Δs≥0, tai iš (7) matome, kad cs≤ cjxsj pasinaudoję tuo, kad zs≥0 įstatome šią nelygybę į cz išraišką, gauname cz≤cjzj+(cjxsj) zs= cj(zj+xsj zs) iš (5) cz≤cjxj=cx taigi bet kokiame leistiname plane z tikslo f-cijos reikšmė ne didesnė už cx, todėl x optimalus. Jei Δs>0 sJ ir z≠x, tai bent viena iš zs >0 ir įrodymas bus tas pats. Iš (8) žinome,kad tikslo f-ciją galėsime padidinti tik tada, kai Δs≤0. iš nebazinių s išsirenkame r (patį mažiausią) taip, kad Δr0, nes xk ir xrk>0. [xk]= xk- (xk / xrk)* xrk=0. k išėjoiš bazės,o r įėjo. Naujai gautas planas [x] taip pat atraminis, nes jo bazė gaunama iš TN stulpelių sistemos { aj } jJ pašalinus stulpelį ak ir vietoj jo įdėjus ar. Kadangi ar išraiškoje bazės { aj } vektoriai stulpeliai ak dauginami iš nelygaus nuliui koeficiento xrk>0, tai pagal teoremą naujai gauta stulpelių sistema taip pat TN. Nauja tikslo f-cijos reikšmė (iš (8) ir (11) formulių): [φ]=φ-(xk / xrk)* Δr. Ši reikšmė didesnė už senąją, nes neišsigimusiame plane xk>0. dabar vėl reikia patikrinti, ar [x] ne optimalus planas. 11. Simpleksinio metodo esmė. Tranformacijos. Užrašytoji simpleksinė lentelė atspindi atraminį planą x ir visus su juo susijusius koeficientus (kairiajame stulpelyj bazinių nžn nr, o viršuje nebaziniai). Perėjimas nuo vieno atraminio plano prie kito virsta simpleksinių lentelių transformavimu.Laikysime, kad x plano bazę sudaro pirmieji m matricos A stulpelių, t.y. J={1,2,...,m}. Atlikę simpleksinį žingsnį, gavome naują atraminį planą [x]. Jo bazė nuo ankstesnės skiriasi tuo, kad vietoj stulpelio ak įtrauktas ar. Norėdami gauti naujus koeficientus [xsj], atitinkančius planą x, visus nebazinius stulpelius turime išreikšti per naują bazę. J‘=J/{k}. ak išreikšime per naują bazę. Turėjome: aj , jJ as = xsjaj , sJ (1). s=r, tuomet (1) užrašysime taip: ar = xrjaj + xrkak. Kadangi xrk>0, tai ak= aj + ar (2). Pasinaudoję (1) išreiškiame stulpelius as: as= xsjaj +xskak = xsjaj +xsk (ar + aj ) = ar +(xsj -xsk)aj. Suskaičiuosime[∆k] ir [∆s] (s≠k) išraiškas: [∆k] = [xkj]cj + [xkr]cr – ck =cj + cr – ck= - = -∆r/xrk [∆s] = [xsj]cj+[xsr]cr-cs== -+xsjcj-cs+xskck-xskck=∆s-∆k. [xsj] kaip per seminarus Pagal turimas formules galima užrašyti simpleksinę lentelę, atitinkančią planą [x]. Jei planas išsigimęs tikslo f-cijos reikšmė nepadidės. Gali būti užsiciklinimas. 12. Simpleksinio metodo esmė. Pradinis atraminis planas papraščiausiu atveju. Ieškome standartiniam tiesinio programavimo uždaviniui. (max) cx, Ax  b, x  0 (1). Laikysime, kad b 0. Naudodami papildomus nežinomuosius, gauname: (max) cx, Ax+y=b, x  0, y 0 (2) arba (max) (c 0T) , (AE)=b,  0 (3). Pažymėję [c]= (c 0T), [A]=(AE) ir tapatindami y1,y2,..., ym su xn+1, xn+2,..., xn+m, (3) uždavinį perrašome į: (max) [c]x, [A]x=b, x  0 (4). Randame atraminį planą (4) uždavinyje: xj=0 (j=1,n) ir xn+1=bi (i=1,m), pagal (2) ar (3) uždavinio žymėjimus x=0, y=b. Kadangi b 0, tai (AE) =b,  0, taigi apribojimai patenkinti ir planas leistinas. Patikrinsim, ar matricos [A] stulpeliai su numeriais, kuriems xj gali būti teigiamas, yra TN. Reikia patikrinti, ar m paskutinių stulpelių yra teigiami. TN turi būti [a]n+1, [a]n+2,..., [a]n+m stulpeliai, jie yra vienetinės matricos stulpeliai e1, e2,.., em, kurie yra TN. Taigi planas tikrai atraminis. Sprendimo procesas: J={n+1,n+2,...,n+m}-bazinių nežinomųjų numerių aibė.as išreikšime per bazę (e1, e2,.., em): as=, iš čia: as=, gauname xsn+1=asi, i=1,m; sJ, t.y.,xsj yra pati matrica A(užima koeficientų vietą). ∆s=. Pradinė f-ijos reikšmė lygi nuliui =0. Gauname simpl. lentelę Jei  ar1....... arm0, tai aix*=bi (duali kaina >0, ištekliai panaudojami pilnai) (1a) 2. Jei p*aj> cj, tai x*j=0 (išteklių, sunaudojamų j-tojo produkto vnt gamybai,duali kaina yra>negu jo pelnas, produkto optimaliame plane negaminsime); Jei x*j>0, tai p*aj= cj (produktas gaminamas, panaudotų išteklių vertė lygi pelningumui) (1b) Įrodymas: Būtinumas. x* ir p*- optimalūs planai. Iš savybių cx*≤ p*A x* ≤p*b ir cx*=p*b. Taigi cx*= p*A x* =p*b. Iš čia p*(A x* -b)=0 ir (p*A -c) x*=0, t.y. (2a) kadangi p*i≥0 ir aix*≤ bi (i=1,m), tai visi dėmenys sumoje neteigiami. Be to nei vienas iš jų negali būti neigiamas, nes visa suma būtų 0, tai aix*=bi ir atvirkščiai. (2b) visi dėmenys neneigiami, nes x*j≥0, ir p*aj≥ cj (j=1,n). Nė vienas dėmuo negali būti teigiamas, nes tada teigiama būtų visa suma. Pakankamumas. Jei leistiniems planams galioja (1) priklausomybės, tai galioja ir (2) lygybės. Todėl cx*= p*A x* =p*b ir šie planai optimalūs. 16. Transporto uždavinys. Būtinos ir pakankamos jo išsprendžiamumo sąlygos. Transporto uždavinyje nagrinėjama m tiekėjų, turinčių tam tikro produkto atsargas a1, a2, ... am vienetų, ir n gavėjų, kurių poreikiai šiam produktui lygūs b1, b2,...., bn vienetų. cij kiek kainuoja pervežimas i-tojo tiekėjo j-tajam gavėjui (i=1,m, j=1,n) sudaryti tokį pervežimų planą,kad visos tiekėjų atsargos būtų išvežtos, gavėjų poreikiai patenkinti,o bendra visų pervežimų kaina minimali. xij - produkto apimtis, pervežama iš i-tojo tiekėjo j-tajam gavėjui. Transporto uždavinys: (min) cx, (iš i tiek) = Tx = d, (gauna j gav) x  0. Laikysime, kad ai >0 ir bj >0 ; m  2, n  2. Transporto uždavinio planu vadinsime mn skaičių xij . Leistinas jei patenkina 3sąlygas, optimalus, jei suteikia min tikslo f-cijai. Transporto uzdavinį vadiname subalansuotu, jei patenkinta sąlyga Šios sąlygos prasmė: bendra visų tiekėjų atsarga lygi visų gavėjų bendram poreikiui. 1 savybė. Transporto uždavinys turi leistiną planą tada ir tik tada, kai jis subalansuotas. Įrodymas. Tarkime xij – leistinas uždavinio planas. Sumuodami pagal i, gauname sumuodami pagal j, gauname lygybę sumuojame tą patį tik kita tvarka. Pažymėkime . Imkime planą Nesunku įsitikint, kad šis planas leistinas. 2 savybė. Suablansuotas transporto uždavinys visada išsprendžiamas. Įrodymas. Pagal 1 savybę subalansuoto transporto uždavinio leistinų planų aibė netuščia. Akivaizdu, kad 0  xij  min(ai, bj), todėl cijxij ir visa sandauga cx aprėžta iš apačios(viršaus). Šių savybių pakanka, kad uždavinys būtų išsprendžiamas. 3savybė Transporto uždavinio matricos T rangas lygus m+n-1. Neišsprendžiamas,kai : • Neturi leistinų planų; • Tikslo f-cija neaprėžta. 17. Nesubalansuotas transporto uždavinys. Prioritetai fiktyviems tiekėjams ir gavėjams. Praktika dažniausiai iškelia nesubalansuotus uždavinius: atsargos ir poreikiai nesutampa. Tokiais atvejais transporto uždavinyje nagrinėjamas vadinamasis fiktyvus tiekėjas arba gavėjas. Jei atsargos viršija poreikius, tai transporto uždavinys papildomas fiktyviu gavėju, kurio poreikis lygus atsargų pertekliui. Jei poreikiai didesni už atsargas, tai uždavinys papildomas fiktyviu tiekėju, patenkinančiu trūkstama poreikių apimtį. Produkto apimtis, pervežama iš kurio nors tiekėjo fiktyviam gavėjui, paprasčiausiai lieka pas šį tiekėją. Jei kuris nors gavėjas ima dalį produkto iš fiktyvaus tiekėjo, tai šios produkto dalies jis tiesiog iš niekur negauna. Kadangi abiem atvejais niekas faktiškai nepervežama, tai pervežimo kainos iš visų tiekėjų fiktyviam gavėjui ir iš fiktyvaus tiekėjo visiems gavėjams laikomos lygios nuliui. 1) Įvedamas n+1 fiktyvus gavėjas. Jam reikia bn+1=. Pervežimo kainos ci,n+1=0(nieko nevešim) x*ij Pvz. x*7,n+1 =12 ( 7 tiekėjo sandėly liks neišvežta 12 vnt.) 2) . Tiekėjų atsargos mažesnės nei gavėjų poreikiai. Patenkinamtuos, kuriuos pigiausia. Įvedamas m+1 fiktyvus tiekėjas, jo atsargos am+1=.kaina cm+1,j=0. x*ij Pvz. x*m+1,5 =12 (5 gavėjas negaus 12 vnt.) 3) Uždrausti srautai. Reikia paskirti be galo dideles kainas tarp nurodytų tiekėjų ir gavėjų. 4) Nelygiaverčiai tiekėjai arba gavėjai. a. Kai kurie tiekėjai turi prioritetą – iš jų visas produktas turi būti išvežtas. Tuomet jis negali vežti fiktyviam gavėjui. Todėl ši kaina turi būti nustatyta lb didelė. Optimaliame plane lieka nepanaudoti ne jo, o kitų tiekėjų produktai. (pas 7 tiekėją gali būti neišvežta šiek tiek produkcijos. Jo vnt kaina yra 4lt. Jei x*7,n+1 =12, tai mūsų nuostoliai 48lt. Bus įskaičiuoti į tikslo f-ciją ir tada žiūrėsim,kas geriau.) b. Kai poreikiai didesni už atsargas gali atsirasti prioritetinių gavėjų, kurie gaus visą reikiamą produktą. Reikia iš fiktyvaus tiekėjo paskirti lb didelę kainą šiam gavėjui, kad jam produkciją pristatytų bet kas tik ne fiktyvus tiekėjas. (nuostoliai- bauda už neatvežtą produkciją tam gavėjui) 5) Privalomi pervežimai. Iš kurio nors tiekėjo kuriam nors gavėjui turi būti pervežama ne mažesnė negu nuodyta produkto apimtis. xkl≥d. Tuomet srautą xkl=d laikome jau suformuotu. K-tojo tiekėjo atsargos [ak]= ak-d, l-tojo gavėjoporeikis sumažėja [bl]= bl-d (ak>d bl>d). Taip modifikavę uždavinį sprendžiame iš naujo, o prie gautos optimalios x*kl reikšmės sprendimo pridedame dydį d. 6) Riboti pervežimai. xkl≤d. Vietoj l-tojo gavėjo nagrinėjame du l1 ir l2. gavėjo l1 poreikis d, o l2 - bl-d pervežimų kainos sutampa su cil i=1,m išskyrus ckl2, kuri priskiriama lb didelė. Todėl k-tasis tiekėjas gali normaliomis kainomis nusiųsti l-tajam gavėjui produkto apimtį, neviršijančią d, o ją viršyti gali tik su lb dideliais nuostoliais. Išsprendus uždavinį reikia tik sudėti l1 ir l2. gavėjų kiekius ir žinosime l-tojo. 18. Gamybinių pajėgumų išdėstymo uždavinys ir jo ryšys su transporto uždaviniu. Turime m miestų, kuriuos reikia aprūpinti tam tikru produktu. Šio produkto poreikius kiekviename mieste žymėsime b1, b2, ...., bm. Kiekviename iš miestų galima statyti įmonę, gaminančią nagrinėjamą produktą. Kadangi miestų galimybės nevienodos, tai maksimalios produkto apimtys, kurias galima pagaminti įvairiuose miestuose, skiriasi. Žymėsime šias apimtis a1, a2, ..., am. Įmonių nebūtina statyti kiekviename mieste, nes produktą galima vežti iš vienų miestų į kitus. Produkto vieneto pervežimo iš i-tojo miesto į j-tąjį išlaidos yra cij litų. Kuriuose miestuose ir kokio galingumo įmones reikia statyti, kad transporto išlaidos, eksploatuojant šias įmones, būtų minimalios? xij – produkto pervežimo iš i-tojo į j-tąjį miestą apimtis. Išdėstymo uždavinys: (nelygybė išreiškia reikalavimą į kiekvieną miestą atvežti ne mažiau produkto, negu būtina) (nelyg. neleidžia iš kiekvieno miesto išvežti daugiau, negu ten būtų galima pagaminti) i-tajam mieste statomos įmonės galingumas xi lengvai apskaičiuojamas pagal lygybę . Mieste statomos įmonės galingumas lygus išvežamo iš jo ir jame paliekamo produkto apimčiai. Jei , t.y. potencialių gamybos apimčių suma mažesnė užbendrą poreikį, uždavinio išspręsti negalima. Jei , tai kiekviename mieste būtina statyti maksimalaus galingumo įmonę. Uždavinio nelygybės šiuo atveju pakeičiame lygybėmis ir sprendžiame paprastą transporto uždavinį. Jei , įtraukiame į uždavinį fiktyvų miestą m+1. Poreikį šiame mieste laikomas lygiu Fiktyvus miestas negali būti produkto gamintoju, todėl uždavinyje turime m miestų – potencialių tiekėjų ir m+1 miestą-gavėją. Visos pervežimo kainos ci m+1 lygios nuliui, nes į fiktyvų miestą nieko nevežame. Jei sprendinyje, kuris nors xi m+1 >0, tai reiškia, kad i-tajame mieste statoma ne maksimalaus, o xi m+1 vienetų mažesnio galingumo įmonė. Vietoj nelygybių imame lygybes, kadangi vežti produkciją į kurį nors miestą virš poreikio nuostolinga. Tai gauname tokį uždavinį: Tai uždavinys su m tiekėjų ir m+1 gavėjų. Jis subalansuotas. x*ij – optimalus planas, x*i =(tik realiems miestams)- kokio dydžio įmonę statyti i-tajame mieste. x*i

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!