Turėtumėte išmokti pagrindinių operacijų tyrimo sąvokų ir apibrėžimų.

Operacija yra bet kokia kontroliuojama veikla, kuria siekiama tikslo. Operacijos rezultatas priklauso nuo jos įgyvendinimo būdo, organizavimo, kitu atveju – nuo ​​tam tikrų parametrų pasirinkimo. Bet koks konkretus parametrų pasirinkimas vadinamas sprendimu. Optimaliais sprendimais laikomi tie, kurie dėl vienokių ar kitokių priežasčių yra geresni už kitus. Todėl pagrindinis operacijų tyrimo uždavinys – išankstinis kiekybinis optimalių sprendimų pagrindimas.

1 pastaba

Atkreiptinas dėmesys į problemos formulavimą: pats sprendimų priėmimas išeina už operacijų tyrimo ribų ir priklauso atsakingo asmens ar asmenų grupės kompetencijai, kuri gali atsižvelgti ir į kitus, nei matematiškai pagrįstus, sumetimus.

2 pastaba

Jei kai kuriose operacijų tyrimo užduotyse optimalus sprendimas yra tas, kuriame pasirinktas efektyvumo kriterijus įgauna didžiausią arba mažiausią reikšmę, tai kitose užduotyse tai visai nereikalinga. Taigi problemoje optimaliu galime laikyti, pavyzdžiui, tokį prekybos vietų ir darbuotojų skaičių juose, kuriuose vidutinis klientų aptarnavimo laikas neviršija, pavyzdžiui, 5 minučių, o vidutinė eilės trukmė bet kuriuo metu būti ne daugiau kaip 3 žmonės (1, psl. .10-11).

Gamybos ir komercinės veiklos efektyvumą didele dalimi lemia įvairių lygių vadovų kasdien priimamų sprendimų kokybė. Šiuo atžvilgiu didelę reikšmę turi sprendimų priėmimo procesų tobulinimo uždaviniai, kuriuos leidžia išspręsti operacijų tyrimai. Terminas „operacijų tyrimas“ pirmą kartą buvo pavartotas 1939–1940 m. karinėje srityje. Iki to laiko karinė įranga ir jos valdymas dėl mokslo ir technologijų revoliucijos tapo iš esmės sudėtingesnis. Ir todėl iki Antrojo pasaulinio karo pradžios iškilo būtinybė skubiai atlikti mokslinius tyrimus efektyvaus naujos karinės įrangos panaudojimo, kiekybinio vadovybės sprendimų įvertinimo ir optimizavimo srityje. Pokariu naujosios mokslo disciplinos sėkmė buvo paklausi taikiose srityse: pramonėje, verslinėje ir komercinėje veikloje, valdžios institucijose, švietimo įstaigose.

Operacijų tyrimas – tai matematinių kiekybinių metodų taikymo metodika, pagrįsti problemų sprendimus visose kryptingos žmogaus veiklos srityse. Operacijų tyrimo metodai ir modeliai leidžia gauti sprendimus, geriausiai atitinkančius organizacijos tikslus.

Operacijų tyrimai – tai mokslas, susijęs su efektyviausio (arba optimaliausio) organizacinių sistemų valdymo metodų kūrimu ir praktiniu taikymu.

Pagrindinis operacijų tyrimo postulatas yra toks: optimalus sprendimas (kontrolė) yra toks kintamųjų reikšmių rinkinys, kuris pasiekia optimalią (maksimalią arba mažiausią) operacijos efektyvumo kriterijaus (objektyviosios funkcijos) reikšmę ir stebi nurodyti apribojimai.

Operacijų tyrimo objektas – optimalių sprendimų priėmimo problema sistemoje su kontrole, pagrįsta jos funkcionavimo efektyvumo įvertinimu. Būdingos operacijų tyrimo sąvokos yra: modelis, kintamieji kintamieji, apribojimai, tikslo funkcija.

Operacijų tyrimo objektas tikrovėje yra organizacijų valdymo sistemos (organizacijos), kurios susideda iš daugybės tarpusavyje sąveikaujančių padalinių, o padalinių interesai ne visada dera tarpusavyje ir gali būti priešingi.

Operacijų tyrimo tikslas – kiekybiškai pagrįsti priimtus sprendimus dėl organizacijų valdymo.

Visai organizacijai naudingiausias sprendimas vadinamas optimaliu, o vienam ar keliems padaliniams naudingiausias sprendimas bus neoptimalus.

Kaip tipinės organizacijos valdymo užduoties pavyzdį, kai susiduria prieštaraujantys padalinių interesai, apsvarstykite įmonės inventoriaus valdymo problemą.

Gamybos skyrius stengiasi pagaminti kuo daugiau gaminių už mažiausią kainą. Todėl jam rūpi kuo ilgesnė ir nenutrūkstama gamyba, t.y., gaminių gamyba didelėmis partijomis, nes tokia gamyba sumažina įrangos perkonfigūravimo kaštus, taigi ir bendrus gamybos kaštus. Tačiau gaminant gaminius dideliais kiekiais reikia sukurti didelius medžiagų, komponentų ir kt.

Pardavimo skyrius taip pat domisi didelėmis gatavų gaminių atsargomis, kad bet kuriuo metu patenkintų bet kokį klientų poreikį. Sudarant kiekvieną sutartį, pardavimo skyrius, stengdamasis parduoti kuo daugiau prekių, turi pasiūlyti vartotojui kuo platesnį prekių asortimentą. Dėl to dažnai kyla konfliktas tarp gamybos skyriaus ir pardavimų skyriaus dėl prekių asortimento. Tuo pačiu metu pardavimų skyrius primygtinai reikalauja, kad į planą būtų įtraukta daug gaminių, pagamintų nedideliais kiekiais, net kai jie neduoda didelio pelno, o gamybos skyrius reikalauja tokius produktus išbraukti iš asortimento.

Finansų skyrius, siekdamas kuo labiau sumažinti įmonės veiklai reikalingą kapitalą, stengiasi sumažinti „susijusių“ apyvartinių lėšų kiekį. Todėl jis suinteresuotas, kad atsargos būtų sumažintos iki minimumo. Kaip matote, skirtingiems organizacijos padaliniams keliami reikalavimai dėl atsargų dydžio yra skirtingi. Kyla klausimas, kokia atsargų strategija bus naudingiausia visai organizacijai. Tai tipiška organizacijos valdymo užduotis. Tai susiję su visos sistemos veikimo optimizavimo problema ir paveikia prieštaringus jos padalinių interesus.

Pagrindinės operacijų tyrimo savybės:

1. Sisteminis požiūris į keliamos problemos analizę. Sisteminis požiūris, arba sistemų analizė, yra pagrindinis operacijų tyrimo metodologinis principas, kuris yra toks. Bet kuri užduotis, kad ir kokia privati ​​ji atrodytų iš pirmo žvilgsnio, yra vertinama atsižvelgiant į jos įtaką visos sistemos funkcionavimo kriterijui. Aukščiau sisteminis požiūris buvo iliustruotas atsargų valdymo problemos pavyzdžiu.

2. Operacijų tyrimams būdinga, kad sprendžiant kiekvieną problemą iškyla vis daugiau naujų uždavinių. Todėl, jei iš pradžių keliami siauri, riboti tikslai, veiklos metodų taikymas nėra efektyvus. Didžiausią efektą galima pasiekti tik nuolatiniais tyrimais, užtikrinant tęstinumą pereinant nuo vienos užduoties prie kitos.

3. Vienas iš esminių operacijų tyrimo bruožų – noras rasti optimalų problemos sprendimą. Tačiau toks sprendimas dažnai pasirodo nepasiekiamas dėl turimų išteklių (pinigų, kompiuterinio laiko) ar šiuolaikinio mokslo lygio apribojimų. Pavyzdžiui, daugeliui kombinatorinių uždavinių, ypač planavimo uždavinių, susijusių su mašinų skaičiumi n > 4, optimalų sprendimą su šiuolaikine matematikos raida galima rasti tik paprasčiausiai išvardijus parinktis. Tuomet tenka apsiriboti „pakankamai gero“ arba neoptimalaus sprendimo paieškomis. Todėl vienas jo kūrėjų T. Saaty operacijų tyrimus apibrėžė kaip „... meną duoti blogus atsakymus į tuos praktinius klausimus, į kuriuos kitais metodais pateikiami dar blogesni atsakymai“.

4. Operatyvinio tyrimo bruožas yra tai, kad jis atliekamas kompleksiškai, daugelyje sričių. Tokiam tyrimui atlikti kuriama operatyvinė grupė. Ją sudaro įvairių žinių sričių specialistai: inžinieriai, matematikai, ekonomistai, sociologai, psichologai. Tokių operatyvinių grupių kūrimo uždavinys – visapusiškas problemos sprendimui įtakos turinčių veiksnių visumos tyrimas, įvairių mokslų idėjų ir metodų panaudojimas.

Kiekvienas operatyvinis tyrimas iš eilės pereina šiuos pagrindinius etapus:

1) planavimo užduoties aprašymas,

2) sukurti matematinį modelį,

3) rasti sprendimą,

4) modelio tikrinimas ir taisymas,

5) rasto sprendimo įgyvendinimas praktikoje.

Planavimo užduoties aprašymas:

Tinklo planavimo ir valdymo užduotys

apsvarstykite santykį tarp didelio operacijų (darbų) komplekso atlikimo terminų ir visų komplekso operacijų pradžios momentų. Šios užduotys susideda iš minimalios operacijų rinkinio trukmės, optimalaus sąnaudų santykio ir jų įgyvendinimo laiko nustatymo.

Eilių sudarymo užduotys yra skirtos eilių sistemų su taikomųjų programų ar reikalavimų eilėmis tyrimui ir analizei ir susideda iš sistemų veikimo rodiklių, optimalių jų charakteristikų nustatymo, pavyzdžiui, nustatant aptarnavimo kanalų skaičių, aptarnavimo laiką ir kt.

Atsargų valdymo užduotys – surasti optimalias atsargų lygių (užsakymo taškų) ir užsakymų dydžių vertes. Tokių užduočių ypatumas slypi tame, kad didėjant atsargų lygiui, viena vertus, didėja jų saugojimo kaštai, tačiau, kita vertus, mažėja nuostoliai dėl galimo sandėliuojamo produkto trūkumo.

Išteklių paskirstymo problemos kyla su tam tikru operacijų (darbų) rinkiniu, kuris turi būti atliktas turint ribotus turimus išteklius, ir reikia rasti optimalų išteklių paskirstymą tarp operacijų ar operacijų sudėties.

Įrangos remonto ir keitimo užduotys aktualios dėl įrangos nusidėvėjimo ir būtinybės ją laikui bėgant keisti. Užduotys sumažinamos iki optimalaus laiko nustatymo, prevencinių remontų ir patikrų skaičiaus bei įrangos keitimo į modernizuotą momentų.

Planavimo (planavimo) uždaviniai yra nustatyti optimalią operacijų seką (pavyzdžiui, dalių apdorojimą) įvairių tipų įrenginiuose.

Planavimo ir išdėstymo uždaviniai yra nustatyti naujų objektų skaičių ir vietą, atsižvelgiant į jų sąveiką su esamais objektais ir tarpusavyje.

Maršruto pasirinkimo problemos, arba tinklo problemos, dažniausiai susiduriama tiriant įvairias transporto ir ryšių sistemos problemas ir susideda iš ekonomiškiausių maršrutų nustatymo (1, p. 15).

Operacija vadinamas bet koks įvykis (veiksmų sistema), kurį vienija vienas planas ir nukreiptas į konkretų tikslą. Operacija visada kontroliuojamas renginys, t.y. galima disponuoti kai kurių jo organizaciją apibūdinančių parametrų pasirinkimo metodu. Šios parinktys vadinamos valdymo kintamieji.

Bet koks konkretus tokių kintamųjų pasirinkimas vadinamas sprendimą. Sprendimai gali būti sėkmingi ir nesėkmingi, pagrįsti ir nepagrįsti. Optimalusįvardykite tokius sprendimus, kurie pagal vienus kriterijus yra geresni už kitus.

Operacijų tyrimo tikslas – išankstinis kiekybinis optimalių sprendimų, kurių gali būti ne vienas, pagrindimas. Galutinis sprendimo pasirinkimas išeina už operacijų tyrimo ribų ir priimamas taikant vadinamąją sprendimų teoriją.

Bet kuri operacijų tyrimo užduotis turi pradines „disciplinines“ sąlygas, t.y. tokie pradiniai duomenys, kurie yra fiksuoti nuo pat pradžių ir negali būti pažeisti. Kartu jie sudaro vadinamąjį galimų sprendimų rinkinį.

Norint palyginti skirtingų sprendimų efektyvumą, reikia turėti kiekybinį kriterijų, vadinamą veiklos rodiklis(arba tikslo funkcija). Šis rodiklis parenkamas taip, kad atspindėtų operacijos tikslinę orientaciją.

Dažnai operaciją lydi atsitiktinių veiksnių veikimas. Tada efektyvumo rodikliu imama ne pati reikšmė, kurią norėtume optimizuoti, o jos vidutinė reikšmė (arba matematinis lūkestis).

Kartais atsitiktinių veiksnių lydima operacija siekia tokio tikslo. BET, kurį galima pasiekti visiškai arba nepasiekti iš viso (pvz., „taip – ​​ne“). Tuomet efektyvumo rodikliu pasirenkama šio tikslo pasiekimo tikimybė. p(A). (Jeigu p(A) = 0 arba 1, tada pasiekiame gerai žinomą kibernetikos „juodosios dėžės“ problemą.)

Neteisingas veiklos rodiklio pasirinkimas yra labai pavojingas. Operacijos, organizuojamos pagal nesėkmingai pasirinktą kriterijų, gali sukelti nepagrįstų išlaidų ir nuostolių. (Pavyzdžiui, „šafas“ yra pagrindinis įmonės ekonominės veiklos vertinimo kriterijus.)

1.3. Bendras operacijų tyrimo uždavinio teiginys

Operacijų tyrimo užduotys skirstomos į dvi kategorijas: a) tiesioginės ir b) atvirkštinės.

Tiesioginės užduotys atsakyti į klausimą: koks bus efektyvumo rodiklis Z jei tam tikromis sąlygomis y  Y bus priimtas koks nors sprendimas x  X. Tokiai problemai išspręsti yra sukurtas matematinis modelis, leidžiantis išreikšti efektyvumo rodiklį tam tikromis sąlygomis ir sprendimą, būtent:

kur
nurodyti veiksniai (pradiniai duomenys),

valdymo kintamieji (sprendimas),

Z– veiklos rodiklis (objektyvi funkcija),

F– funkcinė priklausomybė tarp kintamųjų.

Ši priklausomybė skirtinguose modeliuose išreiškiama skirtingai. Priklausomybė tarp ir paprastai išreiškiamas kaip ribos

Jei priklausomybės tipas Fžinomas, tada Z randamas tiesioginiu pakeitimu ir šiai funkcijai.

Atvirkštinės problemos atsakyti į klausimą: kaip, esant nurodytoms sąlygoms pasirinkti sprendimą
kad veiklos rodiklis Z pasukta iki maksimumo (minimumo). Tokia problema vadinama sprendimo optimizavimo problema.

Tegul išsisprendžia tiesioginė problema, t.y. nustatomas veikimo modelis ir priklausomybės tipas Fžinomas. Tada atvirkštinę problemą (tai yra optimizavimo problemą) galima suformuluoti taip.

Norėjosi rasti toks sprendimas
prie kurio efektyvumo rodiklis Z = opt:

Ši formulė skamba taip: Z yra optimali vertė
perėmė visus sprendinius, įtrauktus į galimų sprendimų rinkinį X.

Efektyvumo rodiklio ekstremumo paieškos metodas Z ir su juo susijusį optimalų sprendimą visada turėtų būti parenkamas atsižvelgiant į funkcijos ypatybes F ir sprendimui taikomų apribojimų tipas. (Pavyzdžiui, klasikinė linijinio programavimo problema.)

1. Pagrindinės IO sąvokos

IR APIE – mokslinė disciplina, užsiimanti efektyviausio įvairių organizacinių sistemų valdymo metodų kūrimu ir praktiniu taikymu.

IO apima šiuos skyrius:

1) matematinė programa. (ūkinės veiklos planų, programų pagrindimas); joje yra skyriai: linijinė programa, nelinijinė programa, dinaminė programa

2) eilių teorija, pagrįsta atsitiktinių procesų teorija;

3) žaidimo teorija, leidžianti pagrįsti sprendimus, priimtus informacijos neišsamumo sąlygomis.

Sprendžiant konkrečią valdymo problemą, IO metodų naudojimas apima:

Ekonominių ir matematinių modelių kūrimas sprendimų priėmimo problemoms sudėtingose ​​situacijose ar neapibrėžtumo sąlygomis;

Ištirti tarpusavio ryšius, lemiančius vėlesnį sprendimų priėmimą, ir nustatyti veiklos kriterijus, leidžiančius įvertinti vienos ar kitos veiklos naudą.

Pagrindinės IO sąvokos ir apibrėžimai.

Operacija – bet kokia kontroliuojama veikla, kuria siekiama tikslo. Operacijos rezultatas priklauso nuo jos įgyvendinimo būdo, organizavimo, kitu atveju – nuo ​​tam tikrų parametrų pasirinkimo. Operacija visada yra kontroliuojamas įvykis, tai yra, nuo mūsų priklauso, kaip pasirinkti kai kuriuos jos organizavimą apibūdinančius parametrus. „Organizacija“ čia suprantama plačiąja šio žodžio prasme, įskaitant operacijoje naudojamų techninių priemonių rinkinį.

Iškviečiamas bet koks duotas parametrų pasirinkimas sprendimą . Sprendimai gali būti sėkmingi ir nesėkmingi, pagrįsti ir nepagrįsti. Optimalus apsvarstyti tuos sprendimus, kurie dėl vienokių ar kitokių priežasčių yra geresni už kitus. Pagrindinis operacijų tyrimo uždavinys – išankstinis kiekybinis optimalių sprendimų pagrindimas.

Veikimo modelis – tai gana tikslus operacijos, naudojant matematinį aparatą, aprašymas (įvairios funkcijos, lygtys, lygčių ir nelygybių sistemos ir kt.). Sudarant operacijos modelį reikia suprasti aprašomo reiškinio esmę ir išmanyti matematinį aparatą.

Veikimo efektyvumas – jos prisitaikymo prie užduoties laipsnis – kiekybiškai išreiškiamas efektyvumo kriterijaus – tikslinės funkcijos – forma. Veiksmingumo kriterijaus pasirinkimas lemia praktinę tyrimo vertę. (Neteisingai pasirinktas kriterijus gali būti žalingas, nes pagal tokį efektyvumo kriterijų organizuojamos operacijos kartais sukelia nepagrįstų išlaidų.)

Tinklo planavimo ir valdymo užduotys apsvarstykite santykį tarp didelio operacijų (darbų) komplekso atlikimo terminų ir visų komplekso operacijų pradžios momentų. Šios užduotys susideda iš minimalios operacijų komplekso trukmės, optimalaus sąnaudų santykio ir jų įgyvendinimo laiko nustatymo.

Eilės užduotys skirtas eilių sistemų su programų ar reikalavimų eilėmis tyrimui ir analizei ir susideda iš sistemų veikimo rodiklių, optimalių jų charakteristikų nustatymo, pavyzdžiui, nustatant aptarnavimo kanalų skaičių, aptarnavimo laiką ir kt.

Atsargų valdymo užduotys susideda iš optimalių atsargų lygio (pertvarkymo taško) ir užsakymo dydžio verčių radimo. Tokių užduočių ypatumas yra tas, kad didėjant atsargų lygiui, viena vertus, didėja jų saugojimo sąnaudos, tačiau, kita vertus, mažėja nuostoliai dėl galimo sandėliuojamo produkto trūkumo.

Išteklių paskirstymo užduotys atsiranda su tam tikra operacijų (darbų) visuma, kurią reikia atlikti turint ribotus turimus išteklius, ir reikia rasti optimalų išteklių paskirstymą tarp operacijų ar operacijų sudėties.

Įrangos remonto ir keitimo darbai aktualus dėl įrangos susidėvėjimo ir būtinybės ją laikui bėgant pakeisti. Užduotys sumažinamos iki optimalaus laiko nustatymo, prevencinių remontų ir patikrų skaičiaus bei įrangos keitimo į modernizuotą momentų.

Užduočių planavimas (planavimas). susideda iš optimalios operacijų sekos (pavyzdžiui, dalių apdorojimo) su įvairių tipų įranga nustatymu.

Planavimo ir išdėstymo užduotys nia Tai yra optimalaus naujų objektų skaičiaus ir vietos nustatymas, atsižvelgiant į jų sąveiką su esamais objektais ir tarpusavyje.

Maršruto pasirinkimo užduotys, arba tinklą užduotys, su kuriomis dažniausiai susiduriama tiriant įvairias transporto ir ryšių sistemos problemas, ir susideda iš ekonomiškiausių maršrutų nustatymo.

2. Bendroji linijinės programos užduotis. Optimalus sprendimas

Ekonominis ir matematinis modelis

LP yra matematikos sritis, kurianti teoriją ir skaitinius metodus, kaip spręsti daugelio kintamųjų tiesinės funkcijos ekstremumo (maksimalaus arba minimumo) nustatymo problemas, kai yra tiesinių apribojimų, ty šiuos kintamuosius jungiančios lygybės ar nelygybės.

LP metodai taikomi sprendžiant praktines problemas, kuriose: 1) iš galimų aibės reikia pasirinkti geriausią sprendimą (optimalų planą); 2) sprendimas gali būti išreikštas kai kurių dydžių kintamųjų verčių rinkiniu; a) apribojimai, kuriuos galimiems sprendimams nustato konkrečios problemos sąlygos, formuluojami tiesinių lygčių arba nelygybių forma; 4) tikslas išreiškiamas kaip pagrindinių kintamųjų tiesinė funkcija. Tikslinės funkcijos reikšmės, leidžiančios palyginti skirtingus sprendimus, yra sprendimo kokybės kriterijus.

Praktiniam ekonominės problemos sprendimui matematiniais metodais, pirmiausia, ji turėtų būti parašyta naudojant ekonominį-matematinį modelį. Ekonominis-matematinis modelis – matematinis tiriamo ekonominio proceso ar objekto aprašymas. Šis modelis išreiškia ekonominio proceso modelius abstrakčia forma, naudojant matematinius ryšius.

Bendra modelio formavimo schema: I

1) tam tikro skaičiaus kintamųjų pasirinkimas, kurių priskyrimas - skaitinės reikšmės vienareikšmiškai nustato vieną iš galimų tiriamo reiškinio būsenų;

2) tiriamam reiškiniui būdingų santykių raiška matematinių ryšių (lygčių, nelygybių) forma. Šie santykiai sudaro problemų suvaržymų sistemą;

3) pasirinkto optimalumo kriterijaus kiekybinė išraiška tikslo funkcijos forma; aš

4) matematinis uždavinio formulavimas kaip tikslo funkcijos ekstremumo radimo problema, atsižvelgiant į kintamiesiems taikomus apribojimus.

Bendroji linijinio programavimo problema atrodo kaip:

Duota m tiesinių lygčių ir nelygybių sistema su n kintamųjų

ir tiesinė funkcija

Reikia rasti tokį sistemos X=(x1,x2,…,xj,…,xn) sprendimą, kur tiesinė funkcija F įgauna optimalią (t.y. maksimalią arba mažiausią) reikšmę.

Sistema (1) vadinama apribojimų sistema, o funkcija F vadinama tiesine funkcija, tiesine forma, tikslo funkcija arba tikslo funkcija.

Trumpiau tariant, bendrąją linijinio programavimo problemą galima pavaizduoti taip:

su apribojimais:

Optimalus sprendimas (arba optimalus planas) LP uždavinys – tai apribojimų sistemos (1) sprendimas X=(x1,x2,…,xj,…,xn), tenkinantis sąlygą (3), pagal kurią tiesinė funkcija (2) įgauna optimalų (maksimalus arba minimalią) vertę.

Su sąlyga, kad visi kintamieji yra neneigiami, apribojimų sistema (1) susideda tik iš nelygybių – tokia linijinio programavimo problema vadinama standartine (simetriška); jei apribojimų sistema susideda tik iš lygčių, tai problema vadinama kanonine.

Ypatingas kanoninės problemos atvejis yra pagrindinės formos problema, kuri skiriasi tuo, kad visi apribojimo vektoriaus koeficientai b yra neneigiami, ir kiekvienoje lygtyje yra kintamasis, kurio koeficientas yra 1, kuris nėra įtrauktas į jokią kitą lygtį. Kintamasis, turintis šią savybę, vadinamas baziniu kintamuoju.

Standartinės ir kanoninės problemos yra specialūs bendrosios problemos atvejai. Kiekvienas iš jų naudojamas tam tikroje srityje. Be to, visos trys formuluotės yra lygiavertės viena kitai: bet kurią linijinio programavimo problemą galima redukuoti į kanoninę, standartinę ar bendrąją problemą, naudojant paprastas matematines transformacijas.

4 . Tiesinės algebros elementai

M tiesinių lygčių sistema su n kintamųjų turi formą

arba stenografiškai

Bet kurie m kintamieji iš m tiesinių lygčių sistemos su n kintamųjų (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

Išspręsti sistemą (2.1) su sąlyga m< n сформулируем утверждение.

Pareiškimas 2.1. Jei dėl sistemosmtiesines lygtis sunkintamieji (m < n) kintamųjų koeficientų matricos rangas yra lygus m, t.y. yra bent viena pagrindinių kintamųjų grupė, tada ši sistema yra neapibrėžta, o kiekviena savavališka nepagrindinių kintamųjų reikšmių rinkinys atitinka vieną sistemos sprendimą.

Sprendimas Sistemos (2.1) X=(x1,x2,…,xn) vadinamas leistinu, jei joje yra tik neneigiami komponentai, t.y. xj>=0 bet kuriam j=1,n. Priešingu atveju sprendimas vadinamas negaliojančiu.

Tarp begalinės sistemos sprendinių aibės išskiriami vadinamieji pagrindiniai sprendiniai.

Bazinis sprendimas m tiesinių lygčių sistema su n kintamųjų vadinama sprendiniu, kuriame visi n–m nepagrindinių kintamųjų yra lygūs nuliui.

Linijinio programavimo problemose ypač domina leistini pagrindiniai sprendimai arba, kaip jie dar vadinami, paramos planai. Pagrindinis sprendimas, kuriame bent vienas iš pagrindinių kintamųjų yra lygus nuliui, vadinamas išsigimusiu.

Išgaubtos taškų aibės

Bendra apibrėžianti savybė, skirianti išgaubtą daugiakampį nuo neišgaubto, yra ta, kad jei paimsite bet kuriuos du jo taškus ir sujungsite juos su atkarpa, visa atkarpa priklausys šiam daugiakampiui. Ši savybė gali būti laikoma išgaubtos taškų aibės apibrėžimu.

Taškų aibė vadinama išgaubta, jei jame kartu su bet kuriais dviem jo taškais yra visa atkarpa, jungianti šiuos taškus.

Išgaubti rinkiniai turi svarbų nuosavybė: bet kokio skaičiaus išgaubtų aibių sankirta (bendroji dalis) yra išgaubta aibė.

Tarp išgaubtos aibės taškų galima išskirti vidinius, ribinius ir kampinius taškus.

Aibės taškas vadinamas vidiniu, jei kai kuriose jo apylinkėse yra tik šios aibės taškų.

Aibės taškas vadinamas riba, jei kurioje nors jo apylinkėje yra ir taškai, priklausantys duotai aibei, ir taškai, kurie jai nepriklauso.

Kampiniai taškai yra ypač svarbūs tiesinio programavimo problemomis. Aibės taškas vadinamas kampinis(arba kraštutinis), jei jis nėra vidinis jokiam segmentui, kuris visiškai priklauso nurodytai aibei.

Ant pav. 2.4 pateikiami įvairių daugiakampio taškų pavyzdžiai: vidinis (taškas M), riba (taškas N) ir kampas (taškai A, B, C, D, E). Taškas A yra kampinis, nes bet kuriai atkarpai, kuri visiškai priklauso daugiakampiui, pavyzdžiui, atkarpai AP, jis nėra vidinis; taškas A yra atkarpos KL vidinis, tačiau ši atkarpa ne visiškai priklauso daugiakampiui.

Išgaubtoje aibėje kampiniai taškai visada sutampa su daugiakampio (daugiakampio) viršūnėmis, o tuo pačiu metu tai nėra būtina neišgaubtai aibei. Taškų aibė vadinama uždara, jei ji apima visus jos ribinius taškus. Taškų rinkinys vadinamas ribotas, jei bet kuriame aibės taške, kuriame pilna duotoji aibė, yra baigtinio ilgio spindulio rutulys (apskritimas); kitu atveju aibė vadinama neribota.

Išgaubta uždara taškų aibė plokštumoje, turinti baigtinį kampinių taškų skaičių, vadinama išgaubtu daugiakampiu, jei ji apribota, ir išgaubta daugiakampio sritimi, jei ji neapribota.

Nelygybių, lygčių ir jų sistemų sprendinių geometrinė reikšmė

Panagrinėkime nelygybių sprendimus.

1 teiginys. Nelygybės su dviem kintamaisiais a11x1+a12x2 sprendinių aibė<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

Norint nustatyti pageidaujamą pusiau plokštumą (viršutinę arba apatinę), rekomenduojama nustatyti savavališką valdymo tašką, kuris nėra ant jo ribos - pastatytos linijos. Jei nelygybė tenkinama valdymo taške, tada ji tenkinama ir visuose pusės plokštumos, kurioje yra valdymo taškas, taškuose, o ne visuose kitos pusės plokštumos taškuose. Ir atvirkščiai, jei nelygybė netenkinama valdymo taške, ji netenkinama visuose pusės plokštumos, kurioje yra valdymo taškas, taškuose, o tenkinama visuose kitos pusės plokštumos taškuose. Kaip valdymo tašką patogu paimti koordinačių O (0; 0) pradžią, kuri nėra pastatytoje tiesėje.

Apsvarstykite nelygybių sistemų sprendimų rinkinį.

2 teiginys. Dviejų kintamųjų tiesinių nelygybių suderinamos sistemos m sprendinių aibė yra išgaubtas daugiakampis (arba išgaubta daugiakampio sritis).

Kiekviena nelygybė pagal 1 teiginį apibrėžia vieną iš pusplokštumų, kuri yra išgaubta taškų rinkinys. Jungtinės tiesinių nelygybių sistemos sprendinių aibė yra taškai, priklausantys visų nelygybių sprendinių pusplokštumoms, t.y. priklauso jų sankirtai. Pagal teiginį apie išgaubtų aibių sankirtą, ši aibė yra išgaubta ir joje yra baigtinis kampinių taškų skaičius, t.y. yra išgaubtas daugiakampis (išgaubtas daugiakampis plotas).

Kampinių taškų koordinatės – daugiakampio viršūnės randamos kaip atitinkamų tiesių susikirtimo taškų koordinatės.

Konstruojant sprendinių sritis nelygybių sistemoms, gali pasitaikyti ir kitų atvejų: sprendinių aibė yra išgaubta daugiakampė sritis (2.9 pav., a); vienas taškas (2.9 pav., b); tuščia aibė, kai nelygybių sistema nenuosekli (2.9 pav., c).

5 . Geometrinis LP uždavinių sprendimo metodas

optimalus LP problemos sprendimas

1 teorema. Jei LP uždavinys turi optimalų sprendimą, tai tiesinė funkcija įgauna didžiausią reikšmę viename iš sprendimo daugiakampio kampinių taškų. Jei tiesinė funkcija įgauna didžiausią reikšmę daugiau nei viename kampiniame taške, tada ji įgauna ją bet kuriame taške, kuris yra išgaubta tiesinė tų taškų kombinacija.

Teorema nurodo pagrindinį LP uždavinių sprendimo būdą. Iš tiesų, pagal šią teoremą, užuot tyrinėjus begalinę leistinų sprendinių aibę, norint tarp jų rasti norimą optimalų sprendimą, reikia ištirti tik baigtinį sprendinio daugiakampio kampinių taškų skaičių.

Toliau pateikta teorema skirta analitiniam kampinių taškų radimo metodui.

2 teorema. Kiekvienas leistinas LP uždavinio pagrindinis sprendinys atitinka sprendinio daugiakampio kampinį tašką, ir atvirkščiai, kiekvieną sprendinio daugiakampio kampinį tašką atitinka leistinas pagrindinis sprendinys.

Iš 1 ir 2 teoremų iš karto išplaukia svarbi pasekmė: jei LP problema turi optimalų sprendimą, tai ji sutampa su bent vienu iš galimų pagrindinių sprendimų.

Taigi, LP uždavinio tiesinės funkcijos optimalumo reikia ieškoti tarp baigtinio skaičiaus leistinų pagrindinių sprendinių.

Taigi, LP uždavinio leistinų sprendinių aibė (sprendinio daugiakampis) yra išgaubtas daugiakampis (arba išgaubtas daugiakampis), o optimalus uždavinio sprendimas yra bent viename iš sprendimo daugiakampio kampinių taškų.

Apsvarstykite standartinės formos problemą su dviem kintamaisiais (P = 2).

Tegul geometrinis apribojimų sistemos vaizdas yra daugiakampis A B C D E(4.1 pav.). Tarp šio daugiakampio taškų reikia rasti tokį tašką, kuriame tiesinė funkcija F=c1x1+c2x2 įgauna didžiausią (arba mažiausią) reikšmę.

Apsvarstykite vadinamąjį lygio linija tiesinė funkcija F, t.y. linija, išilgai kurios ši funkcija įgauna tą pačią fiksuotą reikšmę a, t.y. F = a, arba c1x1+c2x2=a.

Sprendimo daugiakampyje raskite tašką, per kurį eina funkcijos lygio linija F su didžiausiu (jei tiesinė funkcija maksimali) arba mažiausiu (jei ji sumažinta) lygiu.

Funkcijos c1x1+c2x2=a lygio linijos lygtis yra tiesės lygtis. Įvairiuose lygiuose a lygio linijos yra lygiagrečios, nes jų nuolydžius lemia tik koeficientų c1 ir c2 santykis ir todėl yra lygūs. Taigi funkcijų lygio linijos F – tai savotiškos „paralelės“, dažniausiai išsidėsčiusios kampu į koordinačių ašis.

Svarbi tiesinės funkcijos lygio linijos savybė yra ta, kad lygiagrečiai paslinkus tiesei viena kryptimi, lygis tik didėja, o pasislinkus kita kryptimi – tik mažėja. Vektorius c=(c1,c2), prasidedantis nuo pradžios, rodo funkcijos F sparčiausio didėjimo kryptį. Tiesinės funkcijos lygio linija statmena vektoriui c=(c1,c2).

LP uždavinio grafinio sprendimo procedūra:

1. Sukurkite sprendimo daugiakampį.

2. Sukurkite vektorių c = (c1, c2) ir nubrėžkite jam tiesinės funkcijos lygio liniją. F, pavyzdžiui, F=0.

3. Lygiagretus tiesės F=0 poslinkis vektoriaus c(-c) kryptimi, norint rasti tašką Amax(Bmin), kuriame F pasiekia savo maksimumą (minimumą).

1. Kartu spręsdami tiesių, susikertančių optimaliame taške, lygtis, raskite jo koordinates.

2. Apskaičiuokite Fmax(Fmin).

komentuoti. Mažiausias taškas yra „įėjimo“ taškas į sprendimo daugiakampį, o didžiausias – „išėjimo“ iš daugiakampio taškas.

6. Bendra simplekso metodo idėja. Geometrinė interpretacija

Grafinis metodas taikomas labai siaurai linijinio programavimo uždavinių klasei: jis gali efektyviai išspręsti problemas, kuriose yra ne daugiau kaip du kintamieji. Buvo nagrinėjamos pagrindinės linijinio programavimo teoremos, iš kurių išplaukia, kad jei tiesinio programavimo uždavinys turi optimalų sprendimą, tai jis atitinka bent vieną sprendinio daugiakampio kampinį tašką ir sutampa su bent vienu iš leistinų pagrindinių sprendinių. suvaržymo sistema. Nurodytas būdas bet kokiai linijinio programavimo problemai išspręsti: surašyti baigtinį skaičių įmanomų pagrindinių apribojimų sistemos sprendinių ir iš jų pasirinkti tą, pagal kurį tikslo funkcija priima optimalų sprendimą. Geometriškai tai atitinka visų sprendinio daugiakampio kampinių taškų išvardijimą. Toks išvardijimas ilgainiui lems optimalų sprendimą (jei toks yra), tačiau jo praktinis įgyvendinimas yra susijęs su didžiuliais sunkumais, nes realioms problemoms įmanomų pagrindinių sprendimų skaičius, nors ir baigtinis, gali būti labai didelis.

Išvardintų leistinų pagrindinių sprendinių skaičius gali būti sumažintas, jei surašymas atliekamas ne atsitiktinai, o atsižvelgiant į tiesinės funkcijos pokyčius, t.y. siekiant užtikrinti, kad kiekvienas kitas sprendimas būtų „geresnis“ (arba bent jau „ne prastesnis“) už ankstesnį tiesinės funkcijos reikšmių atžvilgiu (didinant jį ieškant maksimumo, mažinant ieškant minimumo) . Toks surašymas leidžia sumažinti žingsnių skaičių ieškant optimalaus. Paaiškinkime tai grafiniu pavyzdžiu.

Tegul įmanomų sprendimų sritis pavaizduota daugiakampiu A B C D E. Tarkime, jo kampinis taškas BET atitinka pradinį leistiną pagrindinį sprendimą. Atsitiktinai suskaičiuojant reikėtų išbandyti penkis įmanomus pagrindinius sprendimus, atitinkančius penkis daugiakampio kampinius taškus. Tačiau brėžinyje matyti, kad po viršaus BET naudinga eiti į kitą viršūnę AT, ir tada iki optimalaus taško NUO. Vietoj penkių buvo įveiktos tik trys viršūnės, nuosekliai gerinant tiesinę funkciją.

Idėja nuosekliai tobulinti sprendimą sudarė pagrindą universaliam linijinio programavimo problemų sprendimo metodui - simplex metodas arba nuoseklaus plano tobulinimo būdas.

Geometrinė simplekso metodo reikšmė susideda iš nuoseklaus perėjimo iš vienos apribojimo daugiakampio viršūnės (vadinamos pradine) į gretimą, kurioje tiesinė funkcija įgauna geriausią (bent jau ne blogiausią) reikšmę, palyginti su problemos tikslas; kol bus rastas optimalus sprendimas – viršūnė, kurioje pasiekiama optimali tikslo funkcijos reikšmė (jei problema turi baigtinį optimalumą).

Pirmą kartą simplekso metodą 1949 metais pasiūlė amerikiečių mokslininkas J. Dancigas, tačiau dar 1939 metais metodo idėjas plėtojo rusų mokslininkas L. V. Kantorovičius.

Simpleksinis metodas, leidžiantis išspręsti bet kokią linijinio programavimo problemą, yra universalus. Šiuo metu jis naudojamas kompiuteriniams skaičiavimams, tačiau paprastus pavyzdžius naudojant simplekso metodą galima išspręsti ir rankiniu būdu.

Norint įgyvendinti simplekso metodą – nuoseklų sprendimo tobulinimą – būtina įsisavinti trys pagrindiniai elementai:

metodą, kaip nustatyti pradinį įmanomą pagrindinį problemos sprendimą;

perėjimo prie geriausio (tiksliau, ne blogiausio) sprendimo taisyklė;

rasto sprendimo optimalumo patikrinimo kriterijus.

Norint naudoti simplekso metodą, tiesinio programavimo uždavinį reikia redukuoti iki kanoninės formos, t.y. apribojimų sistema turi būti pateikta lygčių pavidalu.

Literatūroje pakankamai išsamiai aprašyta: pradinio atskaitos plano (pradinio įmanomo pagrindinio sprendimo) suradimas, taip pat naudojant dirbtinio pagrindo metodą, optimalaus atskaitos plano suradimas, uždavinių sprendimas naudojant simpleksines lenteles.

7 . Simplekso metodo algoritmas.

Panagrinėkime LLP sprendimą simplekso metodu ir pateiksime jį maksimizavimo uždavinio atžvilgiu.

1. Pagal uždavinio sąlygą sudaromas jo matematinis modelis.

2. Sukurtas modelis konvertuojamas į kanoninę formą. Tokiu atveju gali išsiskirti pagrindas su pradiniu orientaciniu planu.

3. Kanoninis uždavinio modelis parašytas simpleksinės lentelės forma, kad visi laisvieji terminai būtų neneigiami. Jei pasirinktas pradinis atskaitos planas, pereikite prie 5 veiksmo.

Paprastoji lentelė: ribojamųjų lygčių sistema ir tikslo funkcija įvedami pradinio pagrindo atžvilgiu išspręstų išraiškų forma. Tiesė, kurioje įrašomi tikslo funkcijos F koeficientai, vadinama F-line arba tikslo funkcijos linija.

4. Pradinis atskaitos planas randamas atliekant simpleksines transformacijas su teigiamos skiriamosios gebos elementais, atitinkančiais minimalius simplekso santykius, ir neatsižvelgiant į F-eilės elementų požymius. Jeigu transformacijų eigoje yra 0 eilutė, kurios visi elementai, išskyrus laisvąjį narį, yra nuliai, tai uždavinio ribojamųjų lygčių sistema yra nenuosekli. Jei, atvirkščiai, yra 0 eilutė, kurioje, be laisvojo nario, nėra kitų teigiamų elementų, tai ribojamųjų lygčių sistema neturi neneigiamų sprendinių.

Bus iškviestas sistemos (2.55), (2.56) sumažinimas į naują pagrindą simplex transformacija . Jei simpleksinė transformacija laikoma formalia algebrine operacija, tai matyti, kad dėl šios operacijos vaidmenys perskirstomi tarp dviejų kintamųjų, įtrauktų į tam tikrą tiesinių funkcijų sistemą: vienas kintamasis pereina iš priklausomo į nepriklausomą ir kitas atvirkščiai – iš nepriklausomo į priklausomą. Ši operacija algebroje žinoma kaip Jordano pašalinimo žingsnis.

5. Rastas pradinis pagrindinis planas yra patikrinamas dėl optimalumo:

a) jei F eilutėje nėra neigiamų elementų (neskaičiuojant laisvo termino), tai planas yra optimalus. Jei nulių nėra, optimalus planas yra unikalus; jei yra bent vienas nulis, tai yra be galo daug optimalių planų;

b) jei F eilutėje yra bent vienas neigiamas elementas, atitinkantis neteigiamų elementų stulpelį, tada;

c) jei F eilutėje yra bent vienas neigiamas elementas, o jos stulpelyje yra bent vienas teigiamas elementas, tada galime pereiti prie naujo atskaitos plano, kuris yra arčiau optimalaus. Norėdami tai padaryti, nurodytas stulpelis turi būti priskirtas kaip skiriamasis, pagal minimalų vienakrypčių santykį, rasti sprendžiamąją eilutę ir atlikti vienakryptę transformaciją. Gautas bazinis planas dar kartą peržiūrimas dėl optimalumo. Aprašytas procesas kartojamas tol, kol gaunamas optimalus planas arba kol problema neišsprendžiama.

Į pagrindą įtraukto kintamojo koeficientų stulpelis vadinamas sprendžiamuoju. Taigi, pasirinkdami kintamąjį, įvestą į pagrindą (arba pasirinkdami sprendžiamąjį stulpelį) neigiamu F eilutės elementu, užtikriname, kad funkcija F padidės .

Šiek tiek sunkiau yra nustatyti kintamąjį, kuris turi būti neįtrauktas į pagrindą. Norėdami tai padaryti, jie sudaro laisvųjų narių ir teigiamų sprendžiamojo stulpelio elementų santykius (tokie santykiai vadinami simpleksais) ir suranda mažiausią tarp jų, kuris nustato eilutę (sprendžiančią), kurioje yra neįtraukiamas kintamasis. Kintamojo, kuris bus pašalintas iš pagrindo, pasirinkimas (arba skiriamosios eilutės pasirinkimas) pagal minimalų vienakrypčių santykį garantuoja, kaip jau nustatyta, bazinių komponentų pozityvumą naujajame atskaitos projekte.

3 algoritmo žingsnyje daroma prielaida, kad visi laisvųjų terminų stulpelio elementai yra neneigiami. Šis reikalavimas nėra būtinas, tačiau jei jis yra įvykdytas, tada visos vėlesnės simpleksinės transformacijos atliekamos tik su teigiamos skiriamosios gebos elementais, o tai patogu skaičiavimams. Jei laisvųjų narių stulpelyje yra neigiami skaičiai, tada sprendžiamasis elementas pasirenkamas taip:

1) pažvelkite į eilutę, atitinkančią kurį nors neigiamą laisvąjį narį, pavyzdžiui, t eilutę, ir pažymėkite joje bet kurį neigiamą elementą, o jį atitinkantis stulpelis bus laikomas leidžiančiu (manome, kad uždavinio apribojimai yra suderinami );

2) sudaro laisvųjų elementų stulpelio elementų ir atitinkamų skiriamosios stulpelio elementų, turinčių vienodus ženklus, santykius (simpleksiniai santykiai);

3) pasirinkti mažiausią iš simpleksinių ryšių. Tai nustatys leidimo eilutę. Tegul tai būna pvz. R- linija;

4) skiriamųjų stulpelių ir eilučių sankirtoje randamas skiriamasis elementas. Jei y eilutės elementas pasirodė esąs sprendžiamasis, tai po simpleksinės transformacijos šios eilutės laisvasis narys taps teigiamas. Kitu atveju kitame žingsnyje vėl kreipiamasi į t eilutę. Jei problema yra išspręsta, po tam tikro žingsnių skaičiaus laisvųjų terminų stulpelyje neigiamų elementų nebus.

8. Atvirkštinės matricos metodas

Apsvarstykite formos LP:

A yra apribojimo matrica;

C=(c1,c2,…,cn)–vektorius–eilutė;

X=(x1,x2,…,xn) – kintamieji;

yra dešiniosios pusės vektorius.

Darome prielaidą, kad visos lygtys yra tiesiškai nepriklausomos, t.y. rangas(a)=m. Šiuo atveju pagrindas yra matricos A eilės minorinis. Tai yra, yra bent viena m eilės submatrica B, kad |B|<>0. Visi nežinomieji, atitinkantys B, vadinami pagrindiniais. Visi kiti yra nemokami.

Tegul B yra tam tikras pagrindas. Tada, permutuojant A matricos stulpelius, A visada galima perkelti į formą A=(B|N),

kur N yra submatrica, susidedanti iš matricos A stulpelių, kurie nepriklauso pagrindui. Lygiai taip pat vektorių x galima skaidyti į – pagrindinių kintamųjų vektorių ir.

Bet koks (1) uždavinio sprendimas tenkina sąlygą A*x=b, todėl sistema įgauna tokią formą:

Nes |B|<>0, tada yra atvirkštinė matrica. Padauginus iš atvirkštinio kairėje pusėje, gauname:

– bendras sprendimas.

Pagrindinis sprendimas (pagrindo B atžvilgiu) yra konkretus problemos (2) sprendimas, gautas esant sąlygai. Tada jis yra vienareikšmiškai nulemtas.

Pagrindinis sprendimas vadinamas realizuojamas, jei.

Pagrindas, atitinkantis įgyvendintą pagrindinį sprendimą. paskambino realizuojamas pagrindas. Pagrindinis sprendimas vadinamas išsigimusiu, jei vektorius turi nulį komponentų.

Bendrajame sprendime yra visi egzistuojantys sprendimai. Grįžkime prie tikslo funkcijos. Prieš pagrindinius kintamuosius pateikiame Cb koeficientus, o kitus Cn.

Taigi, mes gauname. Mes pakeičiame iš bendro sprendimo:

pareiškimas. Pagrindinio sprendimo optimalumo kriterijus.

Tarkim. Tada pagrindinis sprendimas yra optimalus. Jei, tada pagrindinis sprendimas nėra optimalus.

Doc-in: Leisti. Apsvarstykite pagrindinį sprendimą, .

Todėl yra pagrindinio sprendimo tikslo funkcijos reikšmė.

Tebūnie kitas sprendimas: (Xb,Xn).

Tada žiūrime

Taigi pagrindinis sprendimas yra min. Tegul, atvirkščiai, nelaiko, t.y. egzistuoja.

Tada yra sprendimas, kurio tikslo funkcijos reikšmė bus mažesnė už pagrindinio sprendinio tikslo funkcijos reikšmę.

Tegul atitinka laisvąjį kintamąjį Xi:Xj, priskirkite reikšmę ir įveskite ją į pagrindą, o išveskite kitą kintamąjį ir vadinkite jį laisvuoju.

Kaip nustatyti? Visi laisvieji kintamieji, išskyrus , vis dar yra 0.

Tada bendrame sprendime, kur.

Išimame: - būtina sąlyga.

Pagrindinis sprendimas vadinamas įprastu, jei. Kintamąjį išvedame iš pagrindo. Taikant naują sprendimą, tikslo funkcija mažėja, nes

Algoritmas:

1. LP problema standartine forma.

2. Paliekame tiesiškai nepriklausomas lygtis.

3. Raskite tokią matricą B, kad |B|<>0 ir pagrindinis sprendimas.

Skaičiuojame:

jei, tada yra optimalus sprendimas - tai yra pagrindinis sprendimas;

jei tada rasime komponentą, pritvirtiname, taip rasime kitą sprendimą; – kuriame vienas iš pagrindinių kintamųjų =0. Išmetame šį kintamąjį iš pagrindo, įveskite xi. Gavome naują pagrindo B2 konjugatą su pagrindu B1. Tada vėl skaičiuojame.

1. Jei yra optimalus sprendimas, tai po baigtinio žingsnių skaičiaus jį gausime.

Geometriškai procedūra interpretuojama kaip perėjimas nuo kampinio taško į konjuguotą kampinį tašką išilgai aibės X, problemos sprendimų rinkinio, ribos. Nes kampinių taškų yra baigtinis skaičius ir griežtas funkcijos F(x) sumažėjimas draudžia du kartus pereiti per tą patį kraštutinį tašką, tai jei yra optimalus sprendimas, tai po baigtinio žingsnių skaičiaus jį gausime.

9. Ekonominis problemos aiškinimas, dvilypė išteklių naudojimo problema

Užduotis. Dviejų tipų gaminiams P1 ir P2 gaminti naudojami keturių tipų ištekliai S1, S2, S3, S4. Atsižvelgiant į išteklių atsargas, išteklių vienetų, išleistų produkcijos vienetui pagaminti, skaičius. Pelnas, gautas iš gamybos vieneto P1 ir P2, yra žinomas. Būtina sudaryti produktų gamybos planą, kuriame pelnas iš jo pardavimo būtų maksimalus.

Užduotisaš(originalas):

F=c1x1+c2x2+…+CnXn->max su apribojimais:

ir neneigiamumo sąlyga x1>=0, x2>=0,…,Xn>=0

Sudarykite tokį gamybos planą X=(x1,x2,…,Xn), kuriame pelnas (pajamos) pardavus produkciją bus maksimalus, jei resursų sunaudojimas kiekvienai gaminio rūšiai neviršys turimų. akcijų

UžduotisII(dvigubas)

Z=b1y1+b2y2+…+BmYm->min

su apribojimais:

ir neneigiamumo sąlyga

y1>=0, y2>=0,…,yn>=0.

Raskite tokią išteklių Y=(y1,y2,…,yn) kainų (įverčių) aibę, kuriai esant bendra išteklių kaina bus minimali, su sąlyga, kad kiekvienos rūšies produkto gamybos išteklių sąnaudos bus ne mažiau kaip pelnas (pajamos) iš šios produkcijos pardavimo

Aukščiau pateiktame modelyje bi(i=1,2,…,m) reiškia išteklių Si atsargas; aij- produkcijos vieneto gamybai sunaudotų išteklių vienetų Si skaičius Pj(j=1,2,…,n); cj- pelnas (pajamos) pardavus produkcijos vienetą Pj (arba produkcijos kainą Pj) .

Tarkime, kad kuri nors organizacija nusprendė įsigyti įmonės išteklių S1,S2,…,Sm ir reikia nustatyti optimalias šių išteklių kainas y1,y2,…,ym. Akivaizdu, kad perkančiąją organizaciją domina tai, kad visų išteklių Z sąnaudos kiekiais b1,b2,…,bm kainomis y1,y2,…,ym atitinkamai buvo minimalios, t.y. Z=b1,y1+b2y2+…+bmym->min.

Kita vertus, išteklius parduodanti įmonė suinteresuota, kad gaunamos pajamos būtų ne mažesnės už sumą, kurią įmonė gali gauti perdirbdama išteklius į gatavą produkciją.

Gaminio P1 vieneto gamybai išleidžiami A11 vienetai resurso S1, a21 vienetai ištekliaus S2,…., aj1 vienetai resurso Si1 ,……, am1 vienetai išteklių Sm išleidžiami gaminio P1 vieneto gamybai už y1,y1,…,yi kainą. ,…,ym, atitinkamai. Todėl, kad atitiktų pardavėjo reikalavimus, produkcijos vieneto P1 gamybai sunaudotų išteklių savikaina turi būti ne mažesnė nei jo kaina c1, t.y. a11y1+a21y2+…+am1ym>=c1.

Panašiai galima sudaryti apribojimus nelygybių pavidalu kiekvienam produkto tipui P1,P2,…Pn. Taip gautos dvejopos II uždavinio ekonominis-matematinis modelis ir prasmingas aiškinimas pateiktas dešinėje lentelės dalyje.

Išteklių kainos y1,y1,…,yi,…,ym ekonominėje literatūroje gavo įvairius pavadinimus: apskaita, numanomas, šešėlis . Šių pavadinimų prasmė ta sąlyginis , „netikros“ kainos. Skirtingai nuo „išorinių“ produktų kainų c1,c2,…,cn, kurios, kaip taisyklė, žinomos iki gamybos pradžios, išteklių kainos y1,y2,…,ym yra vidinis , nes jie nustatomi ne iš išorės, o nustatomi tiesiogiai dėl problemos sprendimo, todėl dažnai vadinami sąmatos išteklių.

10. Abipusiai dualūs LP uždaviniai ir jų savybės

Formaliai panagrinėkime dvi lentelėje pateiktas linijinio programavimo I ir II problemas, abstrahuodami nuo prasmingo į jų ekonominius ir matematinius modelius įtrauktų parametrų interpretacijos.

Abi užduotys turi šiuos dalykus savybės:

1. Viename uždavinyje jie ieško tiesinės funkcijos maksimumo, kitame – minimumo.

2. Vienos problemos tiesinės funkcijos kintamųjų koeficientai yra laisvieji apribojimų sistemos nariai kitoje.

3. Kiekviena užduotis pateikiama standartine forma, o maksimizavimo uždavinyje visos formos "nelygybės"<=", а в задаче минимизации – все неравенства вида ">=".

4. Abiejų uždavinių apribojimų sistemose kintamųjų koeficientų matricos perkeliamos viena į kitą.

5. Vieno uždavinio apribojimų sistemos nelygybių skaičius yra toks pat kaip kitos problemos kintamųjų skaičius.

6. Abiejuose uždaviniuose išsaugomos kintamųjų neneigiamumo sąlygos.

komentuoti. Jei pradinės problemos j-ajam kintamajam taikoma neneigiamumo sąlyga, tai dvigubos problemos j-asis apribojimas bus nelygybė, bet jei j-asis kintamasis gali turėti ir teigiamas, ir neigiamas reikšmes, tada j-asis dvigubo uždavinio apribojimas bus lygtis; pradinės problemos apribojimai ir dualinės problemos kintamieji yra panašiai susiję.

Dvi linijinio programavimo I ir II uždaviniai su nurodytomis savybėmis vadinami simetriniais abipusiai dualiais uždaviniais. Toliau, kad būtų paprasčiau, mes juos tiesiog pavadinsime dvigubos užduotys.

Kiekviena LP problema gali būti susieta su dviguba problema.

11. Dvigubo uždavinio sudarymo algoritmas:

1. Įveskite visas pradinės problemos apribojimų sistemos nelygybes į tą pačią reikšmę: jei pirminėje užduotyje ieškoma tiesinės funkcijos maksimumo, tada visos apribojimų sistemos nelygybės redukuojamos į formą "<=", а если минимум – к виду ">=". Tas nelygybes, kuriose šis reikalavimas neįvykdytas, padauginkite iš -1.

2. Sudarykite A sistemos padidintą matricą, kuri apima kintamųjų koeficientų matricą, apribojimų sistemos laisvųjų narių stulpelį ir tiesinės funkcijos kintamųjų koeficientų eilutę.

3. Raskite matricą, perkeltą į A matricą .

4. Suformuluokite dvigubą uždavinį pagal gautą matricą ir kintamųjų neneigiamumo sąlygos: sudaryti dvigubos problemos objektyviąją funkciją, kintamųjų koeficientais imdami laisvuosius pradinės problemos apribojimų sistemos narius; sudaryti dvigubos problemos suvaržymų sistemą, matricos elementus paimdama kaip kintamųjų koeficientus, o kintamųjų koeficientus pirminio uždavinio tikslinėje funkcijoje kaip laisvuosius narius ir užrašydama priešingos reikšmės nelygybes; užrašykite dualinės problemos kintamųjų neneigiamumo sąlygą.

12. Pirmoji dvilypumo teorema

Ryšys tarp optimalių dualumo uždavinių sprendinių nustatomas naudojant dualumo teoremas.

Pakankamas optimalumo ženklas.

Jeigu X*=(x1*,x2*,…,xn*) ir Y*=(y1*,y2*,…,ym*) yra priimtini abipusių dvigubų problemų sprendimai, kuriems taikoma lygybė,

tada yra optimalus pirminio uždavinio sprendimas I, ir yra optimalus dvigubos problemos sprendimas II.

Be pakankamo abipusiai dvigubų problemų optimalumo kriterijaus, tarp jų sprendimų yra ir kitų svarbių ryšių. Visų pirma, kyla klausimai: ar visada yra vienu metu optimalus kiekvienos dvigubų problemų sprendimas? ar gali būti, kad viena iš dviejų problemų turi sprendimą, o kita – ne. Į šiuos klausimus atsako tokia teorema.

Pirmoji (pagrindinė) dvilypumo teorema. Jei viena iš abipusių dvigubų problemų turi optimalų sprendimą, tai ir kita, o optimalios jų tiesinių funkcijų reikšmės yra:

Fmaks = Zmin arba F(X*)=Z(Y*) .

Jei vienos iš uždavinių tiesinė funkcija nėra ribojama, tai kitos problemos sąlygos yra prieštaringos (uždavinys neturi sprendimo).

komentuoti. Teiginys, priešingas pagrindinės dvilypumo teoremos antrajai daliai, nėra teisingas bendruoju atveju, t.y. iš to, kad pradinio uždavinio sąlygos yra prieštaringos, nereiškia, kad dualinės problemos tiesinė funkcija nėra apribota.

Pirmosios dvilypumo teoremos ekonominė reikšmė.

Gamybos planas X*=(x1*,x2*,…,xn*) ir išteklių kainų (įvertinimų) rinkinys Y*=(y1*,y2*,…,ym*) yra optimalus tada ir tik tada, kai pelnas (pajamos) iš produktų, randamas „išorinėmis“ (žinomomis iš anksto) kainomis c1,c2,…,cn, yra lygus išteklių sąnaudoms „vidinėmis“ (nustatoma tik). nuo uždavinio sprendimo) kainos y1 ,y2,…,ym. Dėl visų kitų planų X ir Y abiejų užduočių atveju pelnas (pajamos) iš produkto visada yra mažesnis (arba lygus) išteklių sąnaudoms.

Pirmosios dvilypumo teoremos ekonominę prasmę galima interpretuoti ir taip: įmonei nerūpi, ar gaminti produktus pagal optimalų planą X*=(x1*,x2*,…,xn*) ir gauti maksimalų pelną ( pajamos) Fmax arba parduoti išteklius optimaliomis kainomis Y* =(y1*,y2*,…,ym*) ir kompensuoti iš pardavimo jam lygią minimalią išteklių kainą Zmin.

13. Antroji dvilypumo teorema

Tegu pateikiamos dvi abipusiai dvigubos problemos. Jei kiekviena iš šių problemų išspręsta simplekso metodu, tuomet reikia jas redukuoti iki kanoninės formos, kuriai būtina įvesti į I problemos (trumpai tariant) apribojimų sistemą. t ne neigiamus kintamuosius, bet į II uždavinio apribojimų sistemą () – n neneigiami kintamieji, kur i(j) yra nelygybės, kurioje įvedamas papildomas kintamasis, skaičius.

Kiekvienos abipusiai dvigubos problemos apribojimų sistemos bus tokios formos:

Nustatykime atitikmenį tarp vienos iš dvigubų uždavinių pradinių kintamųjų ir kitos problemos papildomų kintamųjų (lentelės).

Teorema. Teigiamos (nenulinės) vienos iš abipusiai dvigubų uždavinių optimalaus sprendimo komponentai atitinka nulines kitos problemos optimalaus sprendimo dedamąsias, t.y. bet kuriam i=1,2,…,m u j=1,2,…,n: jei X*j>0, tai; jeigu , tada ir panašiai,

jei tada ; jei tada.

Iš šios teoremos išplaukia svarbi išvada, kad įvestas atitikimas tarp abipusiai dvigubų uždavinių kintamųjų pasiekus optimalumą (t. y. paskutiniame kiekvienos problemos sprendimo žingsnyje simplekso metodu) reiškia atitiktį pagrindinis(paprastai nelygu nuliui) vienos iš dvigubų uždavinių kintamieji ir nepagrindinis(lygus nuliui) kitos problemos kintamieji, kai jie sudaro leistinus pagrindinius sprendimus.

Antroji dvilypumo teorema. Optimalaus dvigubos problemos sprendimo komponentai yra lygūs absoliučioms koeficientų vertėms prie atitinkamų pradinės problemos tiesinės funkcijos kintamųjų, išreikštų mažesniais optimalaus sprendimo kintamaisiais.

komentuoti. Jei vienoje iš abipusiai dvejopų problemų pažeidžiamas optimalaus sprendimo unikalumas, tai optimalus dvigubos problemos sprendimas yra išsigimęs. Taip yra dėl to, kad jei pažeidžiamas pirminio uždavinio optimalaus sprendimo unikalumas, jo optimalaus sprendimo tiesinės funkcijos išraiškoje nepagrindinių kintamųjų atžvilgiu trūksta bent vieno iš pagrindinių kintamųjų.

14. Objektyviai nustatyti vertinimai ir jų reikšmė

Optimalaus dvigubo uždavinio sprendimo komponentai vadinami optimaliais (dvigubais) pirminės problemos įverčiais. Akademikas L. V. Kantorovičius jiems paskambino objektyviai sąlygotasįvertinimai ( literatūroje jie taip pat vadinami paslėptomis pajamomis) .

Papildomi pradinės problemos I kintamieji, atspindintys skirtumą tarp išteklių S1,S2,S3,S4 atsargų bi. ir jų vartojimą, išreikšti likusių išteklių , ir papildomi dvigubos problemos II kintamieji, atspindintys skirtumą tarp išteklių sąnaudų produkcijos vienetui pagaminti iš jų ir produktų kainų cj P1,P2 , išreikšti išlaidų viršija kaina.

Taigi, objektyviai nustatyti išteklių įverčiai nulemia išteklių trūkumo laipsnį: pagal optimalų gamybos planą riboti (t. y. pilnai panaudoti) ištekliai gauna nulinius įverčius, o nereiklūs – nulinius. Reikšmė y*i yra i-ojo ištekliaus įvertis. Kuo didesnė įverčio y*i reikšmė, tuo didesnis išteklių trūkumas. Neribotam ištekliui y*i=0.

Taigi į optimalų gamybos planą gali patekti tik ekonomiškos, nepelningos gaminių rūšys (nors pelningumo kriterijus čia yra savotiškas: prekės kaina neviršija jo gamybai sunaudotų išteklių sąnaudų, o yra lygiai lygi jiems).

Trečioji dvilypumo teorema . Optimalaus dvigubos problemos sprendimo komponentai yra lygūs tiesinės funkcijos dalinių išvestinių reikšmėms Fmaks(b1, b2,…, bm)pagal atitinkamus argumentus, t.y.

Objektyviai nustatyti išteklių įverčiai parodo, kiek piniginių vienetų pasikeis maksimalus pelnas (pajamos) iš produkcijos pardavimo, kai atitinkamo resurso atsargos pasikeičia vienu vienetu.

Dvigubi įvertinimai gali būti analizės ir teisingų sprendimų priėmimo įrankis nuolat besikeičiančioje pramonės šakoje. Taigi, pavyzdžiui, objektyviai nustatytų išteklių sąmatų pagalba galima palyginti optimalias sąlygines sąnaudas ir gamybos rezultatus.

Objektyviai nustatyti išteklių įverčiai leidžia spręsti apie ne bet kokių, o tik santykinai nedidelių išteklių pokyčių poveikį. Staigiai pasikeitus, patys įverčiai gali skirtis, o tai lems, kad jų nebus galima panaudoti gamybos efektyvumo analizei. Pagal objektyviai nustatytų įverčių koeficientus gali būti nustatomos skaičiuojamos išteklių pakeitimo normos, kurioms esant vykstantys keitimai dvigubų įverčių stabilumo ribose neturi įtakos optimalaus plano efektyvumui. Išvada. Dvigubi balai yra šie:

1. Išteklių ir produktų trūkumo rodiklis.

2. Apribojimų įtakos tikslo funkcijos vertei rodiklis.

3. Tam tikrų rūšių produktų gamybos efektyvumo rodiklis optimalumo kriterijaus požiūriu.

4. Bendrų neapibrėžtųjų kaštų ir rezultatų palyginimo įrankis.

15. Transporto užduoties išrašas pagal kaštų kriterijų.

TK - ekonomiškiausio plano, skirto vienarūšio ar keičiamo produkto transportavimui iš gamybos vietos (išvykimo stočių) į vartojimo taškus (paskirties stotis) užduotis - yra svarbiausia privati ​​LP užduotis, turinti platų praktinį pritaikymą. tik dėl transporto problemų.

TK LP išsiskiria ekonominių charakteristikų tikrumu, matematinio modelio ypatumais, specifinių sprendimo būdų buvimu.

Paprasčiausia TOR formuluotė sąnaudų atžvilgiu yra tokia: in t Išvykimo taškai A1,…,Am yra atitinkamai a1,…,am pristatomų vienarūšių krovinių (resursų) vienetai n vartotojų B1,…,Bn kiekiais b1,…,bn vienetų (poreikių). Yra žinomos krovinio vieneto gabenimo iš i-ojo išvykimo taško į j-ojo vartojimo taško transportavimo išlaidos Cij.

Būtina sudaryti pervežimo planą, t. y. išsiaiškinti, kiek krovinių reikia išsiųsti iš i-ojo išvykimo taško į j-ąjį vartojimo tašką taip, kad poreikiai būtų visiškai patenkinti ir bendros transportavimo išlaidos minimalios.

Aiškumo dėlei TK sąlygos bus pateiktos lentelės forma, kuri vadinama paskirstymas .

Teikėjas	Vartotojas			Krovinių atsargos
Reikia

Čia krovinio kiekis, gabenamas iš i-ojo pradinio taško į j-tą paskirties vietą, lygus xij, krovinio atsargos i-tajame išvykimo taške nustatomas pagal reikšmę ai>=0, o j-osios paskirties vietos paklausa krovinyje yra bj>=0 . Daroma prielaida, kad visi xij>=0.

Matrica vadinama tarifų matrica (išlaidos arba transportavimo išlaidos).

Transporto užduočių planas vadinama matrica, kur kiekvienas skaičius xij reiškia krovinių vienetų skaičių, kuris turi būti pristatytas iš i-ojo išvykimo taško į j-ąjį paskirties vietą. Matrica xij vadinama eismo matrica.

Bendras bendras išlaidas, susijusias su transportavimo plano įgyvendinimu, galima pavaizduoti tiksline funkcija

Kintamieji xij turi atitikti atsargų, vartotojų apribojimus ir neneigiamumo sąlygas:

– atsargų apribojimai (2);

– apribojimai vartotojams (2);

yra neneigiamumo sąlygos (3).

Taigi matematiškai transporto problema suformuluota taip. Pateikta apribojimų sistema (2) pagal sąlygą (3) ir tikslo funkcija (1). Tarp (2) sistemos sprendinių rinkinio reikia rasti tokį neneigiamą sprendimą, kuris sumažintų funkciją (1).

(1) - (3) uždavinių apribojimų sistemoje yra m + n lygčių su tn kintamieji. Daroma prielaida, kad bendrieji rezervai yra lygūs bendriems poreikiams, t.y.

16. Transporto problemos išsprendžiamumo ženklas

Tam, kad susisiekimo problema turėtų leistinus planus, būtina ir pakanka lygybės

Yra dviejų tipų transportavimo užduotys: uždaryta , kurioje bendra tiekėjų krovinių apimtis lygi bendrai vartotojų paklausai, ir atviras , kurioje bendri tiekėjų gamybos pajėgumai viršija vartotojų paklausą arba vartotojų paklausa yra didesnė už faktinį bendrąjį tiekėjų pajėgumą, t.y.

Atvirą modelį galima konvertuoti į uždarą. Taigi, jei, tada fiktyvus (n + 1)-tas tikslas yra įtrauktas į transporto problemos matematinį modelį. Norėdami tai padaryti, užduočių matricoje pateikiamas papildomas stulpelis, kurio poreikis yra lygus skirtumui tarp bendro tiekėjų pajėgumo ir faktinės vartotojų paklausos:

Visi tarifai už prekių pristatymą iki šio taško bus laikomi lygiais nuliui. Tokiu būdu atviras problemos modelis transformuojamas į uždarą. Dėl naujos problemos tikslo funkcija visada yra ta pati, nes papildomo transportavimo kaina yra lygi nuliui. Kitaip tariant, fiktyvus vartotojas nepažeidžia apribojimų sistemos nuoseklumo.

Jei, tada įvedamas fiktyvus (m + 1)-tas išvykimo taškas, kuriam priskiriamas lygus krovinio kiekis.

Prekių pristatymo iš šio fiktyvaus tiekėjo tarifai vėlgi yra lygūs nuliui. Į matricą bus įtraukta viena eilutė, tai neturės įtakos tikslo funkcijai, o problemos suvaržymų sistema taps suderinama, t.y., bus galima rasti optimalų planą.

Didelę reikšmę transporto problemai turi tokia teorema.

Teorema. Transporto uždavinio matricos rangas yra vienu mažesnis už lygčių skaičių, t.y. r ( a )= m + n -1.

Iš teoremos išplaukia, kad kiekvienas atskaitos projektas turi turėti (m-1)(n-1) laisvuosius kintamuosius, lygius nuliui, ir m+n-1 pagrindinių kintamųjų.

Transporto užduoties transportavimo plano ieškosime tiesiai paskirstymo lentelėje. Darome prielaidą, kad jei kintamasis xij įgauna reikšmę, tai šią reikšmę įrašysime į atitinkamą langelį (I,j), bet jei xij=0, tai langelį (I,j) paliksime laisvą. Atsižvelgiant į teoremą apie matricos rangą paskirstymo lentelėje į pagrindinį planą turėtų būti įtraukta m+n-1 užimtos ląstelės o visa kita bus nemokami.

Šie bazinio plano reikalavimai nėra vieninteliai. Baziniai planai turi atitikti kitą su ciklais susijusį reikalavimą.

Srauto matricos langelių rinkinys, kuriame du ir tik du gretimi langeliai yra vienoje eilutėje arba viename stulpelyje, o paskutinis rinkinio langelis yra toje pačioje eilutėje ar stulpelyje kaip ir pirmasis, vadinamas uždaru. ciklas .

Grafiškai ciklas yra uždara laužta linija, kurios viršūnės yra užimtose lentelės langeliuose, o nuorodos yra tik eilutėse arba stulpeliuose. Be to, kiekvienoje ciklo viršūnėje yra tiksliai dvi nuorodos, iš kurių viena yra eilutėje, o kita - stulpelyje. Jei ciklą formuojanti polilinija susikerta pati, tai savaiminio susikirtimo taškai nėra viršūnės.

Šios svarbios transportavimo užduočių planų savybės yra susietos su ciklo langelių rinkiniu:

1) leistinas transportavimo užduoties planas yra nuoroda tada ir tik tada, kai iš šio plano užimamų langelių negalima sudaryti ciklo;

2) jei turime pagrindinį planą, tai kiekvienai laisvai ląstelei galima suformuoti tik vieną ciklą, kuriame yra ši ląstelė ir dalis užimtų langelių.

17. Pradinės bazinės linijos kūrimas

Šiaurės vakarų kampo taisyklė.

Norint sudaryti pradinį transportavimo planą, patogu naudoti šiaurės vakarų kampo taisyklę, kuri yra tokia.

Mes užpildysime, pradėdami nuo viršutinio kairiojo kampo, paprastai vadinamo „šiaurės vakarų kampu“, judėdami toliau linija į dešinę arba stulpeliu žemyn. Į langelį (1; 1) įdedame mažesnįjį iš skaičių a1 ir b1, t.y. Jei, tada pirmasis stulpelis yra „uždarytas“, ty pirmojo vartotojo paklausa yra visiškai patenkinta. Tai reiškia, kad visoms kitoms pirmos stulpelio ląstelėms – krovinio kiekis .

Jei, tada pirmoji eilutė yra panašiai „uždaryta“, ty už . Mes pradedame užpildyti gretimą langelį (2; 1), į kurį patenkame.

Užpildę antrą langelį (1; 2) arba (2; 1), pradedame pildyti kitą trečią langelį antroje eilutėje arba antrame stulpelyje. Šį procesą tęsime tol, kol tam tikru etapu bus išnaudoti ištekliai ir milijardai milijardų poreikių. Paskutinis užpildytas langelis bus paskutiniame n-tajame stulpelyje ir paskutinėje m-oje eilutėje.

Minimalaus elemento taisyklė.

Pradinis orientacinis planas, sudarytas pagal „šiaurės vakarų kampo“ taisyklę, dažniausiai pasirodo labai toli nuo optimalaus, nes jį nustatant neatsižvelgiama į kaštus cij. Todėl atliekant tolesnius skaičiavimus, norint pasiekti optimalų planą, reikės atlikti daug iteracijų. Iteracijų skaičius gali būti sumažintas, jei pradinis planas sudarytas pagal „minimalaus elemento“ taisyklę. Jo esmė slypi tame, kad kiekviename žingsnyje atliekamas maksimalus įmanomas krovinio „perkėlimas“ į kamerą su minimaliu tarifu cij. Lentelę pradedame pildyti nuo langelio, kuris atitinka mažiausią tarifų matricos elementą cij. Mažiausias iš skaičių ai arba bj dedamas į langelį su mažiausiu tarifu . Tada eilutė, atitinkanti tiekėją, kurio atsargos yra visiškai išnaudotos, arba stulpelis, atitinkantis vartotoją, kurio paklausa yra visiškai patenkinta, nenagrinėjama. Gali pasirodyti, kad eilutė ir stulpelis turėtų būti neįtraukti tuo pačiu metu, jei tiekėjo atsargos yra visiškai išnaudotos ir vartotojo paklausa yra visiškai patenkinta. Tada iš likusių lentelės langelių vėl parenkamas mažiausią tarifą turintis langelis ir tęsiamas atsargų paskirstymo procesas, kol visos jos bus paskirstytos ir paklausa patenkinama.

18. Potencialų metodas

Bendrasis optimalaus transporto problemos plano nustatymo potencialo metodu principas yra panašus į LP uždavinio sprendimo simplekso metodu principą, būtent: pirmiausia randamas pagrindinis transporto problemos planas, o po to iš eilės. patobulinta, kad būtų gautas optimalus planas.

Potencialaus metodo esmė yra tokia. Suradus pirminį orientacinį transportavimo planą, kiekvienam tiekėjui (kiekvienai eilutei) priskiriamas tam tikras skaičius, vadinamas tiekėjo potencialu Ai , o kiekvienam vartotojui (kiekvienam stulpeliui) priskiriamas tam tikras skaičius, vadinamas vartotojo potencialu.

Krovinio tonos savikaina taške lygi tonos krovinio kainai prieš transportavimą + jo transportavimo kaina: .

Norint išspręsti transporto problemą galimu metodu, būtina:

1. Sukurkite pagrindinį transportavimo planą pagal vieną iš nurodytų taisyklių. Užpildytų langelių skaičius turi būti m+n-1.

2. Apskaičiuokite potencialą ir atitinkamai tiekėjus bei vartotojus (užimtiems elementams): . Užpildytų langelių skaičius m+n-1, o lygčių skaičius m+n. Nes lygčių skaičius yra vienu mažesnis už nežinomųjų skaičių, tada vienas iš nežinomųjų yra laisvas ir gali turėti bet kokią skaitinę reikšmę. Pavyzdžiui, . Likę tam tikro etaloninio tirpalo potencialai nustatomi vienareikšmiškai.

3. Patikrinkite optimalumą, t.y. laisvoms ląstelėms apskaičiuokite balus. Jei, tai transportavimas tikslingas ir planas X optimalus – optimalumo ženklas. Jei yra bent vienas skirtumas, pereikite prie naujo informacinio plano. Ekonomine prasme vertė apibūdina bendrų transportavimo kaštų pokytį, kuris atsiras i-tam tiekėjui įgyvendinus vieną tiekimą j-ajam vartotojui. Jei, tada vienas pristatymas leis sutaupyti transporto išlaidas, jei - jų padidėjimą. Todėl, jei tarp nemokamų tiekimo krypčių nėra krypčių, taupančių transportavimo išlaidas, tada gautas planas yra optimalus.

4. Tarp teigiamų skaičių pasirenkamas maksimalus, pastatytas laisvai langeliui, kuriam jis atitinka perskaičiavimo ciklą. Sukūrę pasirinkto laisvo langelio ciklą, turėtumėte pereiti prie naujo atskaitos plano. Norėdami tai padaryti, perskaičiavimo ciklu turite perkelti apkrovas ląstelėse, susietose su šia laisva langeliu.

a) Kiekviena ląstelė, sujungta ciklu su tam tikra laisvąja ląstele, yra priskiriama tam tikru ženklu, ir ši laisva ląstelė yra „+“, o visos kitos ląstelės (ciklo viršūnės) yra pakaitomis ženklais „–“ ir „+“. . Šias ląsteles vadinsime minusu ir pliusu.

b) Ciklo minuso langeliuose randame minimalią pasiūlą, kurią žymime. Mažesnis iš skaičių xij neigiamose ląstelėse perkeliamas į šią laisvą langelį. Tuo pačiu metu šis skaičius pridedamas prie atitinkamų skaičių langeliuose su „+“ ženklu ir atimamas iš skaičių, esančių minuso langeliuose. Langelis, kuris anksčiau buvo laisvas, tampa užimtas ir patenka į atskaitos planą; o minuso langelis, kuriame stovėjo skaičių xij minimumas, laikomas laisvu ir palieka atskaitos planą.

Taigi buvo nustatyta nauja bazinė linija. Aukščiau aprašytas perėjimas nuo vienos bazinės linijos prie kitos vadinamas perskaičiavimo ciklo poslinkiu. Perskaičiavimo ciklą keičiant, užimtų langelių skaičius išlieka nepakitęs, ty jis išlieka lygus m+n-1. Be to, jei minuso langeliuose yra du ar daugiau identiškų skaičių xij, tada tik viena iš šių langelių atlaisvinama, o likusios lieka užimtos nulinėmis atsargomis.

5. Gautas orientacinis planas tikrinamas dėl optimalumo, t.y. pakartokite visus 2 pastraipos veiksmus.

19. Dinaminio programavimo samprata.

DP (planavimas) – tai matematinis metodas ieškant optimalių daugiapakopių (daugiapakopių) problemų sprendimų. Kai kurios iš šių problemų natūraliai suskaidomos į atskirus etapus (etapus), tačiau yra problemų, kai skaidinys turi būti įvestas dirbtinai, kad būtų išspręstas DP metodu.

Paprastai DP metodais optimizuojamas kai kurių valdomų sistemų veikimas, kurio poveikis įvertinamas priedas, arba dauginamasis, objektyvi funkcija. Priedas yra kelių kintamųjų f(x1,x2,…,xn) funkcija, kurios reikšmė apskaičiuojama kaip kai kurių funkcijų fj, kurios priklauso tik nuo vieno kintamojo xj, suma: . Adityvinės tikslo funkcijos terminai atitinka atskiruose kontroliuojamo proceso etapuose priimtų sprendimų poveikį.

R. Bellmano optimalumo principas.

Dinaminio programavimo metodo prasmė slypi pirminės daugiamatės problemos sprendimo pakeitime žemesnės dimensijos uždavinių seka. Pagrindiniai reikalavimai užduotims:

1. tyrimo objektas turėtų būti valdoma sistema (objektas) su duotu galiojimu teigia ir leistina skyriai;

2. užduotis turi leisti interpretuoti kaip daugiapakopį procesą, kurio kiekvienas žingsnis susideda iš priėmimo sprendimus apie pasirenkant vieną iš leistinų kontrolės priemonių, dėl kurių būsenos pasikeitimas sistemos;

3. užduotis neturėtų priklausyti nuo žingsnių skaičiaus ir būti apibrėžta kiekvienam iš jų;

4. sistemos būsena kiekviename žingsnyje turi būti aprašyta tuo pačiu (sudėtiniu) parametrų rinkiniu;

5. vėlesnė būsena, kurioje sistema atsiduria pasirinkusi sprendimą k-ojižingsnis, priklauso tik nuo pateikto sprendimo ir pradinės būsenos iki pradžios k- žingsnis. Ši savybė yra pagrindinė dinaminio programavimo ideologijos požiūriu ir vadinama pasekmių nebuvimas .

Apsvarstykite dinaminio programavimo modelio taikymą apibendrinta forma. Tegul yra užduotis valdyti kokį nors abstraktų objektą, kuris gali būti skirtingose ​​būsenose. Esama objekto būsena bus identifikuojama su tam tikru parametrų rinkiniu, kuris toliau bus žymimas S ir vadinamas būsenos vektorius. Daroma prielaida, kad duota visų galimų būsenų aibė S. Aibė taip pat apibrėžiama objektui leistinos kontrolės priemonės(kontrolės veiksmai) x, kurią neprarandant bendrumo galima laikyti skaitine aibe. Valdymo veiksmai gali būti atliekami atskirais laiko momentais ir kontrolė sprendimas susideda iš vieno iš valdiklių pasirinkimo. planą užduotis arba valdymo strategija iškviečiamas vektorius x=(x1,x2,…,xn-1), kurio komponentai yra kiekviename proceso žingsnyje parinkti valdikliai. Atsižvelgiant į numatomą poveikio nebuvimas tarp kiekvienos dviejų nuoseklių objekto būsenų Sk ir Sk+1 yra žinoma funkcinė priklausomybė, kuri apima ir pasirinktą valdiklį: . Taigi, nustatant pradinę objekto būseną ir pasirenkant planą X vienareikšmiškai apibrėžti elgesio trajektorija objektas.

Valdymo efektyvumas kiekviename žingsnyje k priklauso nuo esamos būsenos Sk, pasirinkto valdiklio xk ir yra kiekybiškai įvertinamas naudojant funkcijas fk(xk,Sk), kurios yra sumos adityvinė tikslo funkcija , charakterizuojantys bendrą patalpų valdymo efektyvumą. ( Pastaba , kad funkcijos fk(xk,Sk) apibrėžimas apima leistinų reikšmių diapazoną xk , ir ši sritis, kaip taisyklė, priklauso nuo esamos Sk) būklės). Optimalus valdymas , tam tikrai pradinei būsenai S1 sumažina iki tokio optimalaus plano pasirinkimo x* , kuriame maksimali suma fk reikšmės atitinkamoje trajektorijoje.

Pagrindinis dinaminio programavimo principas yra tas, kad kiekviename žingsnyje reikia siekti ne izoliuoto funkcijos fk(xk,Sk) optimizavimo, o pasirinkti optimalų valdymą x*k, darant prielaidą, kad visi tolesni žingsniai yra optimalūs. Formaliai šis principas realizuojamas ieškant kiekviename žingsnyje k sąlyginės optimalios kontrolės , užtikrinantis didžiausią bendrą efektyvumą, pradedant nuo šio žingsnio, darant prielaidą, kad dabartinė būsena yra S.

Žymėkite Zk(s) maksimalią funkcijų sumos fk reikšmę per visus žingsnius nuo k prieš P(gaunama optimaliai valdant tam tikrame proceso segmente), su sąlyga, kad objektas veiksmo pradžioje k yra S būsenoje. Tada funkcijos Zk(s) turi tenkinti rekursinį ryšį:

Šis santykis vadinamas pagrindinis pasikartojimo ryšys (pagrindinė funkcinė lygtis) dinaminis programavimas. Jis įgyvendina pagrindinį dinaminio programavimo principą, dar žinomą kaip Bellmano optimalumo principas :

Optimali valdymo strategija turi atitikti šią sąlygą: kad ir kokia būtų pradinė būsena sk k-ajame žingsnyje ir šiame etape pasirinktą valdiklį xk, vėlesnė kontrolė (valdymo sprendimai) turėtų būti optimali cocomo yanyu ,dėl sprendimo, priimto žingsnyje k .

Pagrindinis ryšys leidžia rasti funkcijas Zk(s) tik in kartu su pradinė būklė kuri mūsų atveju yra lygybė.

Aukščiau suformuluotas optimalumo principas taikomas tik tiems valdymo objektams, kuriems optimalaus valdymo pasirinkimas nepriklauso nuo kontroliuojamo proceso priešistorės, tai yra nuo to, kaip sistema atėjo į esamą būseną. Būtent ši aplinkybė leidžia išskaidyti problemą ir padaryti praktinį jos sprendimą.

Kiekvienai konkrečiai užduočiai funkcinė lygtis turi savo specifinę formą, tačiau ji tikrai turi išlaikyti pasikartojantį pobūdį, būdingą išraiškai (*) ir įkūnijančią pagrindinę optimalumo principo idėją.

20. Žaidimo modelių samprata.

Matematinis konfliktinės situacijos modelis vadinamas žaidimas , konflikte dalyvaujančios šalys žaidėjų ir konflikto baigtį laimėti.

Kiekvienam formalizuotam žaidimui pristatome reglamentas , tie. sąlygų sistema, kuri lemia: 1) žaidėjų veiksmų variantus; 2) kiek informacijos kiekvienas žaidėjas turi apie partnerių elgesį; 3) atlygis, į kurį atveda kiekvienas veiksmų rinkinys. Paprastai pelną (arba nuostolį) galima įvertinti kiekybiškai; pavyzdžiui, pralaimėjimą galite įvertinti nuliu, pergalę - vienetu, o lygiąsias - 1/2. Žaidimo rezultatų kiekybinis įvertinimas vadinamas mokėjimas .

Žaidimas vadinamas garinė pirtis , jei dalyvauja du žaidėjai ir daugkartinis , jei žaidėjų skaičius didesnis nei du. Mes apsvarstysime tik porinius žaidimus. Jas žaidžia du žaidėjai BET ir AT, kurių interesai yra priešingi, o žaidimu turime omenyje daugybę veiksmų BET ir AT.

Žaidimas vadinamas nulinės sumos žaidimas arba antagonistinis skoy , jeigu vieno iš žaidėjų pelnas lygus kito praradimui, t.y. abiejų šalių išmokų suma lygi nuliui. Norint atlikti žaidimo užduotį, pakanka nurodyti vieno iš jų vertę . Jei paskirsime a- laimėti vieną iš žaidėjų, b – kito atlyginimas, tada už nulinės sumos žaidimą b= –a, todėl pakanka apsvarstyti, pavyzdžiui a.

Vieno iš taisyklėse numatytų veiksmų pasirinkimas ir įgyvendinimas vadinamas judėti žaidėjas. Judesiai gali būti Asmeninis ir atsitiktinis . asmeninis žingsnis – tai sąmoningas žaidėjo vieno iš galimų veiksmų pasirinkimas (pavyzdžiui, ėjimas šachmatų partijoje). Kiekvieno asmeninio ėjimo galimų variantų rinkinys yra reguliuojamas žaidimo taisyklių ir priklauso nuo ankstesnių abiejų pusių ėjimų visumos.

Atsitiktinis judesys – tai atsitiktinai pasirinktas veiksmas (pavyzdžiui, kortos pasirinkimas iš sumaišytos kaladės). Kad žaidimas būtų matematiškai apibrėžtas, žaidimo taisyklės turi būti nurodytos kiekvienam atsitiktiniam ėjimui tikimybių skirstinys galimus rezultatus.

Kai kuriuos žaidimus gali sudaryti tik atsitiktiniai ėjimai (vadinamieji grynieji azartiniai žaidimai) arba tik asmeniniai ėjimai (šachmatai, šaškės). Dauguma kortų žaidimų priklauso mišraus tipo žaidimams, tai yra, juose yra ir atsitiktinių, ir asmeninių ėjimų. Toliau nagrinėsime tik asmeninius žaidėjų judesius.

Žaidimai klasifikuojami ne tik pagal ėjimų pobūdį (asmeninis, atsitiktinis), bet ir pagal kiekvieno žaidėjo turimos informacijos apie kito veiksmus pobūdį bei kiekį. Ypatinga žaidimų klasė yra vadinamieji „žaidimai su visa informacija“. Žaidimas su visa informacija Vadinamas žaidimas, kuriame kiekvienas žaidėjas žino visų ankstesnių asmeninių ir atsitiktinių ėjimų rezultatus kiekviename asmeniniame ėjime. Žaidimų, kuriuose pateikiama visa informacija, pavyzdžiai yra šachmatai, šaškės ir gerai žinomas „tic-tac-toe“ žaidimas. Dauguma praktinės svarbos žaidimų nepriklauso žaidimų klasei su visa informacija, nes nežinojimas apie priešininko veiksmus dažniausiai yra esminis konfliktinių situacijų elementas.

Viena iš pagrindinių žaidimų teorijos sąvokų yra koncepcija strategijos .

strategija Žaidėjas vadinamas taisyklių rinkiniu, kuris lemia jo veiksmo pasirinkimą kiekvienam asmeniniam ėjimui, priklausomai nuo situacijos. Paprastai žaidimo metu kiekvienam asmeniniam ėjimui žaidėjas pasirenka priklausomai nuo konkrečios situacijos. Tačiau iš esmės gali būti, kad visus sprendimus žaidėjas priima iš anksto (atsižvelgdamas į bet kurią situaciją). Tai reiškia, kad žaidėjas pasirinko tam tikrą strategiją, kuri gali būti pateikta taisyklių sąrašo arba programos pavidalu. (Taigi galite žaisti žaidimą naudodami kompiuterį). Žaidimas vadinamas galutinis , jei kiekvienas žaidėjas turi ribotą skaičių strategijų ir begalinis .– kitaip.

Į nuspręsti žaidimas , arba rasti žaidimo sprendimas , kiekvienam žaidėjui būtina pasirinkti strategiją, kuri tenkintų sąlygą optimalumas , tie. turi gauti vienas iš žaidėjų maksimalus laimėjimas, kai antrasis laikosi savo strategijos, Tuo pačiu metu antrasis žaidėjas turi turėti minimalus nuostolis , jei pirmasis laikosi savo strategijos. Tokios strategijos vadinamos optimalus . Optimalios strategijos taip pat turi atitikti sąlygą tvarumą , tie. bet kuriam žaidėjui turėtų būti nenaudinga atsisakyti savo strategijos šiame žaidime.

Jei žaidimas kartojamas pakankamai kartų, žaidėjai gali nebūti suinteresuoti laimėti ir pralaimėti kiekviename žaidime, a vidutinis laimėjimas (pralaimėjimas) visose partijose.

Žaidimo teorijos tikslas yra nustatyti optimalią strategiją kiekvienam žaidėjui.

21. Mokėjimo matrica. Žemutinė ir viršutinė žaidimo kaina

Baigti žaidimą, kuriame žaidėjas BET Tai turi t strategijas ir žaidėją B - p strategijos vadinamos m×n žaidimu.

Apsvarstykite dviejų žaidėjų žaidimą m × n BET ir AT(„mes“ ir „priešininkas“).

Leisk žaidėjui BET turi t asmeninės strategijos, kurias žymime A1,A2,…,Am. Leisk žaidėjui AT prieinama n asmeninės strategijos, jas žymime B1,B2,…,Bn.

Tegul kiekviena pusė pasirenka tam tikrą strategiją; mums tai bus Ai, oponentui Bj. Žaidėjams pasirinkus bet kurią strategijų porą Ai ir Bj (), žaidimo baigtis yra vienareikšmiškai nulemta, t.y. laimėti aij žaidėją BET(teigiamas arba neigiamas) ir žaidėjo praradimas (-aij). AT.

Tarkime, kad reikšmės aij yra žinomos bet kuriai strategijų porai (Ai, Bj) . Matrica P=aij , kurių elementai yra išmokos, atitinkančios strategijas Ai ir Bj, paskambino mokėjimo matrica arba žaidimo matrica. Šios matricos eilutės atitinka žaidėjo strategijas BET, o stulpeliai yra žaidėjo strategijos B. Šios strategijos vadinamos grynosiomis.

m × n žaidimo matrica yra tokia:

Apsvarstykite m × n žaidimą su matrica ir nustatykite geriausią iš strategijų A1, A2,…, Am . Ai žaidėjo strategijos pasirinkimas BET turėtų tikėtis žaidėjo AT atsakys į jį viena iš strategijų Bj, už kurią žaidėjo atsipirkimas BET minimalus (žaidėjas AT siekia „pakenkti“ žaidėjui A).

Žymi mažiausiu žaidėjo laimėjimu BET kai jis pasirenka strategiją Ai visoms įmanomoms žaidėjo strategijoms AT(mažiausias skaičius i-išmokėjimo matricos eilutė), t.y.

Iš visų skaičių () pasirinkite didžiausią: .

Paskambinkime mažesnė žaidimo kaina, arba maksimalus laimėjimas (maxmin). Tai garantuotas žaidėjo A atlyginimas už bet kokią žaidėjo B strategiją. Vadinasi,

Vadinama strategija, atitinkanti maksimumą maksimino strategija . Žaidėjas AT suinteresuotas sumažinti žaidėjo atlyginimą BET, pasirinkdamas strategiją Bj, jis atsižvelgia į didžiausią galimą atsipirkimą už BET. Pažymėti

Iš visų skaičių pasirinkite mažiausią

ir paskambink aukščiausia žaidimo kaina arba minimalus atlygis(minimax). Ego garantuotas žaidėjo B praradimas. Todėl,

Minimax strategija vadinama Minimax strategija.

Principas, diktuojantis žaidėjams „atsargiausių“ minimalaus ir maksimalaus strategijų pasirinkimą, vadinamas Minimax principas . Šis principas išplaukia iš pagrįstos prielaidos, kad kiekvienas žaidėjas siekia pasiekti priešingą varžovo tikslą.

Teorema. Žemesnė žaidimo kaina niekada neviršija viršutinės žaidimo kainos. .

Jei žaidimo viršutinė ir apatinė kainos yra vienodos, tai bendra viršutinės ir apatinės žaidimo kainų vertė vadinama grynoji žaidimo kaina, arba žaidimo kaina. Minimax strategijos, atitinkančios žaidimo kainą, yra optimalios strategijos , ir jų visuma optimalus sprendimas arba žaidimo sprendimas. Šiuo atveju žaidėjas BET gauna maksimalią garantiją (nepriklausomai nuo žaidėjo elgesio) AT) laimėti v, ir grotuvas AT pasiekia garantuotą minimumą (nepriklausomai nuo žaidėjo elgesio) BET) pralaimi v. Teigiama, kad žaidimo sprendimas yra tvarumą , tie. jei vienas iš žaidėjų laikosi savo optimalios strategijos, kitam negali būti naudinga nukrypti nuo savo optimalios strategijos.

Jei vienas iš žaidėjų (pvz BET) laikosi savo optimalios strategijos, o kitas žaidėjas (AT) bet kokiu būdu nukryps nuo savo optimalios strategijos žaidėjui, kuris padarė nukrypimą, tai niekada negali būti naudinga; toks žaidėjo nukrypimas AT geriausiu atveju gali nepakeisti pelno. o blogiausiu atveju – padidinti.

Priešingai, jei AT laikosi savo optimalios strategijos ir BET nukrypsta nuo savo, tada tai jokiu būdu negali būti naudinga BET.

Grynų strategijų pora suteikia optimalų žaidimo sprendimą tada ir tik tada, kai atitinkamas elementas yra didžiausias savo stulpelyje ir mažiausias savo eilutėje. Tokia situacija, jei ji yra, vadinama maitinimo taškas. Geometrijoje vadinamas taškas ant paviršiaus, turintis savybę: vienalaikis minimumas išilgai vienos koordinatės ir maksimumas išilgai kitos. galia taškas, pagal analogiją šis terminas vartojamas žaidimų teorijoje.

Žaidimas, kuriam , paskambino power point žaidimas. Elementas, turintis šią savybę, yra matricos galios taškas.

Taigi kiekvienam žaidimui su galios tašku yra sprendimas, kuris nustato porą optimalių strategijų abiem pusėms, kurios skiriasi šiomis savybėmis.

1) Jei abi pusės laikosi savo optimalių strategijų, vidutinė išmoka yra lygi grynajai žaidimo kainai v, tai yra ir apatinė, ir viršutinė jo kaina.

2) Jei viena iš šalių laikosi savo optimalios strategijos, o kita nukrypsta nuo savo, tai nukrypusi šalis gali tik pralaimėti ir jokiu būdu negali padidinti savo pelno.

Žaidimų teorijoje įrodyta, kad visų pirma kiekvienas žaidimas su visa informacija turi galios tašką, taigi kiekvienas toks žaidimas turi sprendimą, t. y. yra pora optimalių strategijų vienai ir kitai pusei, suteikiant vidutinis atlygis, lygus žaidimo kainai. Jei žaidimas su tobula informacija susideda tik iš asmeninių ėjimų, tai kai kiekviena pusė taiko savo optimalią strategiją, jis visada turi baigtis gana aiškiu rezultatu, ty atsipirkimu, tiksliai lygiu žaidimo kainai.

22. Žaidimo sprendimas mišriomis strategijomis.

Tarp baigtinių praktinės svarbos žaidimų žaidimai su jėgos tašku yra gana reti; labiau būdingas atvejis, kai skiriasi apatinė ir viršutinė žaidimo kainos. Analizuodami tokių žaidimų matricas, prieiname prie išvados, kad jei kiekvienam žaidėjui duota pasirinkti vieną strategiją, tai, remiantis protingai veikiančiu priešininku, šis pasirinkimas turėtų būti nulemtas minimax principu. Laikydamiesi savo maksimalios strategijos, už bet kokį priešininko elgesį garantuojame sau atlyginimą, lygų žemesnei žaidimo kainai α. mišrios strategijos

mišri strategija Sa žaidėjas A vadinamas grynųjų strategijų A1,A1,…,Ai,…,Am taikymu su tikimybėmis p1,p2,…pi,…pm, o tikimybių suma lygi 1: . Mišrios žaidėjo A strategijos parašytos kaip matrica

arba kaip eilutę Sa=(p1,p2,…,pi,…,pm).

Panašiai žaidėjo B mišrios strategijos žymimos taip:

Arba Sb=(q1,q2,…,qi,…,qn),

kur strategijų atsiradimo tikimybių suma lygi 1: .

Akivaizdu, kad kiekviena grynoji strategija yra ypatingas mišrios strategijos atvejis, kai visos strategijos, išskyrus vieną, taikomos nuliniais dažniais (tikimybėmis), o ši – 1 dažniu (tikimybe).

Pasirodo, taikant ne tik grynąsias, bet ir mišrias strategijas, galima gauti kiekvieno baigtinio žaidimo sprendimą, t. y. porą tokių (paprastai mišrių) strategijų, kad abiem žaidėjams jomis pasinaudojus, atlygis būtų vienodas. į žaidimo kainą, o kai bet koks vienpusis nukrypimas nuo optimalios strategijos, atsipirkimas gali keistis tik nukrypusiam nepalankia kryptimi. Taigi, remiantis minimax principu, nustatoma optimalus sprendimas (arba sprendimas)žaidimai: tai yra optimalių strategijų pora bendru atveju mišrus, turintis tokią savybę: jei vienas iš žaidėjų laikosi savo optimalios strategijos, tai kitam negali būti pelninga nukrypti nuo savo. Vadinamas atlygis, atitinkantis optimalų sprendimą žaidimo kaina v . Žaidimo kaina tenkina nelygybę:

Kur α ir β yra apatinė ir viršutinė žaidimo kaina.

Šis teiginys yra vadinamojo turinys pagrindinė žaidimų teorijos teorema. Pirmą kartą šią teoremą įrodė Johnas von Neumannas 1928 m. Žinomi teoremos įrodymai yra gana sudėtingi; todėl pateikiame tik jos formuluotę.

Kiekvienas baigtinis žaidimas turi bent vieną optimalų sprendimą, galbūt tarp mišrių strategijų.

Iš pagrindinės teoremos išplaukia, kad kiekvienas baigtinis žaidimas turi kainą.

Leiskite ir – optimalių strategijų pora. Jei grynoji strategija yra įtraukta į optimalią mišrią strategiją su ne nuline tikimybe, tada ji vadinama aktyvus (naudingas) .

šviesus aktyviosios strategijos teorema: jei vienas iš žaidėjų laikosi savo optimalios mišrios strategijos, tada atlygis išlieka nepakitęs ir lygus žaidimo kainai v, jei antrasis žaidėjas neperžengia savo aktyvių strategijų ribų.

Žaidėjas gali naudoti bet kurią iš savo aktyvių strategijų gryna forma, taip pat gali jas maišyti bet kokia proporcija.

Ši teorema turi didelę praktinę reikšmę – joje pateikiami konkretūs modeliai, kaip rasti optimalias strategijas, kai nėra balno taško.

Apsvarstykite 2x2 dydžio žaidimas, kuris yra paprasčiausias baigtinio žaidimo atvejis. Jei toks žaidimas turi balno tašką, tai optimalus sprendimas yra grynųjų strategijų pora, atitinkanti šį tašką.

Žaidimas be balno taško pagal pagrindinę žaidimo teorijos teoremą optimalus sprendimas egzistuoja ir yra nulemtas mišrių strategijų poros ir.

Norėdami juos rasti, naudojame teoremą apie aktyvias strategijas. Jei žaidėjas BET laikosi savo optimalios strategijos , tada jo vidutinis atlyginimas bus lygus žaidimo kainai v, nesvarbu, kokią aktyvią strategiją žaidėjas naudoja AT. 2v2 žaidime bet kurio priešininko grynoji strategija yra aktyvi, jei nėra ssdl taško. Žaidėjas laimi BET(žaidėjo pralaimėjimas AT)– atsitiktinis dydis, kurio matematinis lūkestis (vidutinė reikšmė) yra žaidimo kaina. Todėl vidutinis žaidėjo atlyginimas BET(optimali strategija) bus lygus v ir 1-ajai, ir 2-ajai priešo strategijai.

Tegul žaidimą suteikia išmokėjimo matrica.

Vidutinis žaidėjo atlyginimas BET, jei jis naudoja optimalią mišrią strategiją ir žaidėją AT – gryna strategija B1 (tai atitinka 1 išmokėjimo matricos stulpelį R), lygus žaidimo kainai v: .

Žaidėjas gauna tą patį vidutinį atlyginimą BET, jei 2-as žaidėjas naudoja strategiją B2, t.y. . Atsižvelgdami į tai, gauname lygčių sistemą optimaliai strategijai nustatyti ir žaidimų kainos v:

Išsprendę šią sistemą gauname optimalią strategiją

ir žaidimo kaina.

Taikant aktyviosios strategijos teoremą rasti – optimali žaidėjo strategija AT, tai gauname bet kuriai grynai žaidėjo strategijai BET (A1 arba A2) vidutinis žaidėjo pralaimėjimas AT lygus žaidimo kainai v, t.y.

Tada optimali strategija nustatoma pagal formules: .

Užduotis išspręsti žaidimą, jei jo matricoje nėra balno taško, yra sunkesnė, tuo didesnė reikšmė m ir n. Todėl matricinių žaidimų teorijoje nagrinėjami metodai, kuriais vienų žaidimų sprendimas redukuojamas į kitų, paprastesnių, visų pirma sumažinant matricos matmenį. Galima sumažinti matricos matmenį išskiriant dublikatas ir aišku nepalankus strategijos.

Pasikartoti vadinamos strategijos, kurios atitinka tas pačias išmokėjimo matricos elementų reikšmes, t.y. matricoje yra tos pačios eilutės (stulpeliai).

Jei visi i-osios matricos eilutės elementai yra mažesni už atitinkamus k-osios eilutės elementus, tada žaidėjo i-oji strategija BET nepelninga (laimi mažiau).

Jei visi r-ojo matricos stulpelio elementai yra didesni už atitinkamus j-ojo stulpelio elementus, tada žaidėjui AT R-oji strategija nepelninga (nuostolis didesnis).

Pasikartojančių ir akivaizdžiai nepelningų strategijų išbraukimo procedūra visada turėtų būti atliekama prieš žaidimo sprendimą.

23. Geometrinė žaidimo 2×2 interpretacija

Žaidimo sprendimas 2×2 leidžia aiškiai interpretuoti geometriją.

Tegu žaidimą pateikia išmokėjimo matrica P=(aij), i, j=1,2.

Ant abscisės (pav.) Atidėkite į šalį vienetas segmentas A1A2; taškas A1 ( X=0) vaizduoja strategiją A1, tašką A2 ( X=1) vaizduoja strategiją A2, o visi tarpiniai šio segmento taškai yra mišrios pirmojo žaidėjo strategijos Sa, o atstumas nuo Sa iki dešiniojo segmento galo yra strategijos A1 tikimybė p1 , atstumas iki kairiojo galo yra strategijos A2 tikimybė p2 .

Per taškus A1 ir A2 nubrėžkime du statmenus x ašiai: ašis I-I ir ašis II-II. Aš-I ašyje naudos pagal strategiją A1 atidėsime; II-II ašyje – išmokos pagal strategiją A2.

Jei žaidėjas A naudoja strategiją A1, tada jo išmokėjimas pagal žaidėjo B strategiją B1 yra a11, o pagal strategiją B2 - a12. Skaičiai a11 ir a12 I ašyje atitinka taškus B1 ir B2.

Jei žaidėjas A naudoja strategiją A2, tai jo išmokėjimas pagal žaidėjo B strategiją B1 yra a21, o pagal strategiją B2 lygus a22. Skaičiai a21 ir a22 atitinka II ašies taškus B1 ir B2.

Sujungiame taškus B1 (I) ir B1 (II); B2 (I) ir B2 (II). Turi dvi tiesias linijas. Tiesi linija B1B1 – jei žaidėjas BET taiko mišrią strategiją (bet koks strategijų A1 ir A2 derinys su tikimybėmis p1 ir p2), o žaidėjas B taiko strategiją B1. Laimėjęs žaidėjas BET atitinka tam tikrą šios linijos tašką. Vidutinis išmokėjimas, atitinkantis mišrią strategiją, nustatomas pagal formulę a11p1+a21p2 ir pavaizduotas tašku M1 B1B1 linijoje.

Panašiai sudarome segmentą B2B2, atitinkantį antrojo žaidėjo strategijos B2 naudojimą. Šiuo atveju vidutinis padidėjimas nustatomas pagal formulę a12p1+a22p2 ir yra pavaizduotas tašku M2 tiesėje B2B2.

Turime rasti optimalią strategiją S*a, t.y. tokią, kuriai būtų minimalus atsipirkimas (už bet kokį elgesį AT) kreiptųsi į maksimumą. Norėdami tai padaryti, mes pastatysime apatinė pelno riba su B1B2 strategijomis , y., trūkinė linija B1NB2, pažymėta fig. stora linija. Tai apatinė riba išreikš minimalų žaidėjo atlyginimą BET bet kuriai mišriai strategijai; taškasN , kurioje šis minimalus atsipirkimas pasiekia maksimumą, ir lemia sprendimą (optimalią strategiją) bei žaidimo kainą. Taško ordinatė N ar yra kaina žaisti v. Taško koordinatės N randame kaip tiesių B1B1 ir B2B2 susikirtimo taškų koordinates. Mūsų atveju žaidimo sprendimą lėmė strategijų susikirtimo taškas. Tačiau taip bus ne visada.

Geometriškai galima nustatyti optimalią žaidėjo strategiją BET, taip pat žaidėjas AT; abiem atvejais naudojamas minimax principas, tačiau antruoju atveju statoma ne apatinė, o viršutinė išmokos riba, o ant jos nustatoma ne maksimali, o minimali.

Jei išmokėjimo matricoje yra neigiamų skaičių, tada grafiniam problemos sprendimui geriau pereiti prie naujos matricos su neneigiamais elementais; tam pakanka prie pradinės matricos elementų pridėti atitinkamą teigiamą skaičių. Žaidimo sprendimas nepasikeis, tačiau šiuo skaičiumi žaidimo kaina padidės. Grafiniu metodu galima išspręsti žaidimą 2×n, m×2.

24. Matricinio žaidimo redukcija į linijinio programavimo uždavinį

Žaidimas m × n paprastai neturi vaizdinės geometrinės interpretacijos. Jo sprendimas yra gana sunkus dideliems t ir n, tačiau jis neturi esminių sunkumų, nes gali būti sumažintas iki linijinio programavimo problemos sprendimo. Parodykime.

Tegul m × n žaidimą pateikia išmokėjimo matrica . Žaidėjas BET turi strategijas A1,A2,..Ai,..Am , žaidėjas AT – strategijos B 1,B 2,..B aš,.. B n. Būtina nustatyti optimalias strategijas ir kur yra atitinkamų grynųjų strategijų Ai,Bj taikymo tikimybės,

Optimali strategija tenkina šį reikalavimą. Tai suteikia žaidėjui BET vidutinė išmoka ne mažesnė už žaidimo kainą v, bet kokiai žaidėjo strategijai AT ir atlyginimas, lygus žaidimo kainai v, su optimalia žaidėjo strategija AT. Neprarasdami bendrumo, mes nustatėme v> 0; tai galima pasiekti padarius visus elementus . Jei žaidėjas BET taiko mišrią strategiją prieš bet kurį grynos strategijos Bj žaidėją AT, tada jis gauna vidutinis atlyginimas , arba matematinis tikėjimasis laimėti (t. y. elementai j-Go išmokėjimo matricos stulpeliai terminas po termino dauginami iš atitinkamų strategijų A1,A2,..Ai,..Am tikimybių ir sumuojami rezultatai).

Siekiant optimalios strategijos, visi vidutiniai laimėjimai yra ne mažesni už žaidimo kainą v, todėl gauname nelygybių sistemą:

Kiekvieną nelygybę galima padalyti iš skaičiaus. Pristatykime naujus kintamuosius: . Tada sistema įgauna formą

Žaidėjo tikslas BET - maksimaliai padidinti savo garantuotą atlyginimą, t.y. žaidimo kaina v.

Padalinę iš lygybės, gauname, kad kintamieji tenkina sąlygą: . Žaidimo kainos maksimizavimas v yra tolygus kiekio sumažinimui , taigi problemą galima suformuluoti taip: apibrėžti kintamąsias reikšmes , mamakad būtų patenkinti tiesiniai apribojimai(*) ir o tiesinė funkcija (2*) pasuko iki minimumo.

Tai linijinio programavimo problema. Išspręsdami uždavinį (1*)–(2*), gauname optimalų sprendimą ir optimali strategija .

Norint nustatyti optimalią strategiją, reikėtų atsižvelgti į tai, kad žaidėjas AT siekia kuo labiau sumažinti garantuotą atsipirkimą, t.y. rasti maks. Kintamieji tenkina nelygybes

kurios išplaukia iš to, kad vidutinis žaidėjo pralaimėjimas AT neviršija žaidimo vertės, nesvarbu, kokią gryną strategiją žaidėjas naudoja BET.

Jei pažymėsime (4*) , gausime nelygybių sistemą:

Kintamieji tenkina sąlygą.

Žaidimas buvo sumažintas iki kitos užduoties.

Nustatykite kintamąsias reikšmes , kurios tenkina nelygybių sistemą (5*)ir padidinti tiesinę funkciją

Linijinio programavimo uždavinio sprendimas (5*), (6*) lemia optimalią strategiją. Tuo pačiu ir žaidimo kaina. (7*)

Sudarę išplėstines uždavinių matricas (1*), (2*) ir (5*), (6*), įsitikiname, kad viena matrica buvo gauta iš kitos perkeliant:

Taigi linijinio programavimo uždaviniai (1*), (2*) ir (5*), (6*) yra abipusiai dualūs. Akivaizdu, kad nustatant optimalias strategijas konkrečiose problemose, reikėtų pasirinkti vieną iš abipusiai dualinių uždavinių, kurių sprendimas yra mažiau pastangų reikalaujantis, o kitos problemos sprendimą rasti naudojant dualumo teoremas.

Sprendžiant savavališką baigtinį m × n dydžio žaidimą, rekomenduojama laikytis šios schemos:

1. Išskirkite akivaizdžiai nepelningas strategijas iš išmokų matricos, palyginti su kitomis strategijomis. Tokios strategijos žaidėjui BET

Pagal operacija suprantamas kaip bet koks įvykis, kurį vienija viena idėja ir kryptis konkrečiam tikslui pasiekti.

Operacija visada yra valdomas įvykis, t.y. Mes turime pasirinkti parametrus, apibūdinančius jo organizavimo būdą.

Bus vadinamas bet koks konkretus parametrų pasirinkimas, priklausantis nuo mūsų sprendimą.

Optimalūs sprendimai yra tie, kurie dėl vienokių ar kitokių priežasčių yra geresni už kitus.

Pagrindinis operacijų tyrimo tikslas yra preliminarus kiekybinis optimalių sprendimų pagrindimas. Operacijų tyrimais nesiekiama visiškai automatizuoti sprendimų priėmimo. Sprendimą visada priima žmogus. Operacijų tyrimo tikslas – gauti kiekybinius duomenis ir rekomendacijas, kurios palengvintų žmogui apsispręsti.

Kartu su pagrindine užduotimi - optimalių sprendimų pagrindimas; Operacijų tyrimo apimtis apima kitas užduotis:

Lyginamasis įvairių operacijos organizavimo variantų įvertinimas,

Įvairių parametrų poveikio įvertinimas,

„Kropščių“ tyrimas, t.y. elementai, kurių sutrikimas ypač stipriai atsiliepia operacijos sėkmei ir kt.

Šios pagalbinės užduotys yra ypač svarbios, kai tam tikra operacija vertinama ne atskirai, o kaip neatskiriama visumos dalis. sistemos operacijos. „Sisteminis“ požiūris į operacijų tyrimo uždavinius reikalauja atsižvelgti į visos eilės veiklų tarpusavio priklausomybę ir sąlygiškumą, t.y. priimti galutinį sprendimą atsižvelgdami į šios operacijos vaidmenį ir vietą sistemoje.

Pagal efektyvumą operacija suprantama kaip jos prisitaikymo prie užduoties, su kuria ji susiduria, atlikimo laipsnis.

Norint įvertinti operacijos efektyvumą ir palyginti skirtingai organizuotų operacijų efektyvumą, reikia turėti tam tikrą skaičių vertinimo kriterijus arba veiklos rodiklis.

Veiksmų seka operacijų tyrime.

1. Suformuluojamas tyrimo tikslas ir parengiamas problemos teiginys.

2. Norint taikyti kiekybinius metodus bet kurioje srityje, visada būtina sukurti matematinį reiškinio modelį. Šis modelis sukurtas remiantis originalo savybių analize.

3. Sukūrus modelį, gaunami jo rezultatai

4. Jie interpretuojami pagal originalą ir perkeliami į originalą.

5. Palyginimo pagalba modeliavimo rezultatai lyginami su rezultatais, gautais tiesiogiai tiriant originalą.

Jei naudojant modelį gauti rezultatai yra artimi rezultatams, gautiems tiriant originalą, tai pagal šias savybes modelis gali būti laikomas adekvačiu originalui.

Projektuojant ir eksploatuojant automatizuotas valdymo sistemas, dažnai iškyla užduotys, susijusios su tiek kiekybinių, tiek kokybinių jų veikimo modelių analize, optimalios struktūros nustatymu ir kt.

Tiesioginis eksperimentavimas su objektais, siekiant išspręsti šias problemas, turi keletą reikšmingų trūkumų:

1. Pažeidžiamas nustatytas objekto veikimo režimas.

2. Viso masto eksperimento metu neįmanoma išanalizuoti visų alternatyvių sistemos kūrimo variantų ir pan.

Šias problemas patartina spręsti nuo objekto atskirtame modelyje, įdiegtame kompiuteryje.

Modeliuojant informacines sistemas plačiai naudojami matematiniai modeliai.

Matematinio modeliavimo metodas – tai įvairių objektų tyrimo metodas, sudarant atitinkamą matematinį aprašymą ir jo pagrindu apskaičiuojant tiriamo objekto charakteristikas.

Būtina sukurti matematinį modelį. Ji formaliai atspindi originalo funkcionavimo procesą ir apibūdina pagrindinius jo elgesio modelius. Šiuo atveju visi antriniai, nereikšmingi veiksniai neįtraukiami.

Matematinio modeliavimo objektas yra sudėtingos sistemos. Sudėtinga sistema yra tam tikru būdu organizuotas ir kryptingai veikiantis daugybės su informacija susijusių ir sąveikaujančių elementų rinkinys, veikiamas išorinių veiksnių.

Yra 4 pagrindiniai sistemų modeliavimo kompiuteriu etapai:

Koncepcinio sistemos modelio sukūrimas ir jo formalizavimas;

Sistemos modelio algoritmizavimas ir modeliavimo programos kūrimas;

Preliminarių modeliavimo rezultatų gavimas ir interpretavimas;

Modelio ir sistemos tinkamumo tikrinimas; modelio koregavimas

Pagrindinis sistemos funkcionavimo kokybės rodiklių skaičiavimas remiantis modeliavimo rezultatais, modelio įgyvendinimas.

Paskaita 3. Pagrindinės ekspertinio vertinimo metodo sampratos. Ekspertų grupių formavimas. balsavimo procedūros. Reitingavimo metodai, porinis palyginimas, vertinimas santykine skale.

1. Operacijų ekonomikoje tyrimo dalykas ir uždaviniai. Pagrindinės operacijų tyrimo teorijos sampratos.

Operacijų tyrimo objektas – organizacijos valdymo sistemos arba organizacijos, susidedančios iš daugybės tarpusavyje sąveikaujančių vienetų, kurie ne visada dera tarpusavyje ir gali būti priešingi.

Operacijų tyrimo tikslas – kiekybiškai pagrįsti priimtus sprendimus dėl organizacijų valdymo

Sprendimas, kuris pasirodo esąs naudingiausias visai organizacijai, vadinamas optimaliu, o vienam ar keliems padaliniams naudingiausias sprendimas bus neoptimalus.

Operacijų tyrimai – tai mokslas, nagrinėjantis optimaliausio organizacinių sistemų valdymo metodų kūrimą ir praktinį taikymą.

Operacija – tai bet koks įvykis (veiksmų sistema), kurį vienija vienas planas ir nukreiptas į kažkokį tikslą.

Operacijų tyrimo tikslas – išankstinis kiekybinis optimalių sprendimų pagrindimas.

Bet koks konkretus parametrų pasirinkimas, priklausantis nuo mūsų, vadinamas sprendimu. Sprendimai vadinami optimaliais, jei dėl vienokių ar kitokių priežasčių jiems teikiama pirmenybė prieš kitus.

Parametrai, kurių visuma sudaro sprendimą, vadinami sprendimo elementais.

Priimtinų sprendimų rinkiniui pateikiamos sąlygos, kurios yra fiksuotos ir kurių negalima pažeisti.

Veiklos rodiklis – kiekybinis matas, leidžiantis palyginti skirtingus sprendimus efektyvumo požiūriu.

2. Tinklo planavimo ir valdymo samprata. Proceso ir jo elementų tinklinis modelis.

Darbo su tinklo grafikais metodas – tinklo planavimas – paremtas grafų teorija. Išvertus iš graikų kalbos, grafikas (grafpho – rašau) reiškia taškų sistemą, kai kurie iš jų yra sujungti linijomis – lankais (arba briaunomis). Tai topologinis (matematinis) sąveikaujančių sistemų modelis. Grafikų pagalba galima išspręsti ne tik tinklo planavimo, bet ir kitas problemas. Tinklo planavimo metodas naudojamas planuojant tarpusavyje susijusių darbų kompleksą. Tai leidžia vizualizuoti organizacinę ir technologinę darbų seką ir nustatyti tarpusavio ryšį. Be to, tai leidžia koordinuoti įvairaus sudėtingumo operacijas ir nustatyti operacijas, nuo kurių priklauso viso darbo (t. y. organizacinio įvykio) trukmė, taip pat sutelkti dėmesį į kiekvienos operacijos atlikimą laiku.

Tinklo planavimo ir valdymo pagrindas yra tinklo modelis (SM), kuris modeliuoja tarpusavyje susijusių veiklų ir įvykių rinkinį, atspindintį konkretaus tikslo siekimo procesą. Jis gali būti pateiktas grafiko arba lentelės pavidalu.

Pagrindinės tinklo modelio sąvokos:

Renginys, darbas, būdas.

Įvykiai yra vienos ar kelių veiklų vykdymo rezultatai. Jie neturi laiko pratęsimo.

Kelias – tai vienas po kito einančių darbų grandinė, jungianti pradinę ir galutinę viršūnes.

Kelio trukmė nustatoma pagal jį sudarančių darbų trukmių sumą.

3. Tinklo schemos konstravimas ir užsakymas.

Tinklo modelis naudojamas kaip modelis, atspindintis statybos ir montavimo darbų proceso technologines ir organizacines sąsajas tinklų planavimo ir valdymo sistemose (SPU).

Tinklo modelis – tai grafinis procesų atvaizdavimas, kurį įgyvendinus pasiekiamas vienas ar keli tikslai, nurodant tarp šių procesų nusistovėjusius ryšius. Tinklo diagrama yra tinklo modelis su apskaičiuotais laiko parametrais.

Tinklo diagramos struktūra, kuri lemia darbų ir įvykių tarpusavio priklausomybę, vadinama jos topologija.

Darbas – tai laiko, darbo ir materialinių išteklių reikalaujantis gamybos procesas, kurį atlikus pasiekiami tam tikri rezultatai.

Priklausomybė (fiktyvus darbas), nereikalaujantis laiko sąnaudų, pavaizduotas punktyrine rodykle. Manekeno darbas naudojamas tinklo diagramoje, norint parodyti įvykių ir veiklos ryšius.

Tinklo grafike naudojamas laikas, kaina ir kitos darbo charakteristikos.

Darbo trukmė – šio darbo atlikimo laikas darbo dienomis ar kitais laiko vienetais, vienodas visiems darbams tinkle. Darbo trukmė gali būti arba tam tikras (deterministinis), arba atsitiktinis dydis, nurodytas jo pasiskirstymo dėsnio.

Darbo kaina – tai tiesioginės išlaidos, būtinos jam įgyvendinti, priklausomai nuo šių darbų trukmės ir sąlygų.

Ištekliams būdingas fizinių vienetų, reikalingų šiam darbui atlikti, poreikis.

Darbo kokybė, patikimumas ir kiti rodikliai tarnauja kaip papildomos darbo charakteristikos.

Įvykis – tai vienos ar kelių darbų atlikimo faktas, būtinas ir pakankamas vienos ar kelių vėlesnių darbų pradžiai. Kiekvienam įvykiui priskiriamas numeris, vadinamas kodu. Kiekvienas darbas apibrėžiamas dviem įvykiais: pradžios įvykio kodas, žymimas i, ir pabaigos įvykio kodas, žymimas j.

Įvykiai, kurie neturi ankstesnės veiklos, vadinami pradiniais įvykiais; įvykiai, kurie neturi vėlesnių – galutinių.

1 Tinklo kūrimo kryptis gali būti kitokio pobūdžio. Tinklo grafikas gali būti sudarytas nuo pradinio įvykio iki galutinio ir nuo galutinio iki pradinio (pradinio), taip pat nuo bet kurio įvykio iki pradinio ar galutinio.

2 Kuriant tinklą sprendžiami šie klausimai:

Kokį darbą (darbą) reikia atlikti norint pradėti šį darbą;

Kokius darbus reikėtų atlikti lygiagrečiai su šiuo darbu;

3 Pradinis tinklo grafikas sudaromas neatsižvelgiant į tinklą sudarančių veiklų trukmę.

4 Grafiko forma turi būti paprasta ir vizualiai lengvai suvokiama.

5 Tarp dviejų įvykių gali būti tik vienas darbas. Statant pastatus ir statinius darbai gali būti atliekami nuosekliai, lygiagrečiai arba vienu metu, dalis nuosekliai, o dalis lygiagrečiai, dėl ko susidaro įvairios priklausomybės tarp atskirų darbų.

Įvykių numeravimas (kodavimas) atliekamas baigus tinklo tiesimą, pradedant nuo pradinio įvykio iki baigiamojo.

4. Kritinis tinklo diagramos kelias. Laiko rezervai. Ankstyvos ir vėlyvos įvykių ir veiklos datos tinklo diagramoje.

Tinklo diagramoje gali būti keli keliai tarp pradžios ir pabaigos įvykių. Ilgiausios trukmės kelias vadinamas kritiniu keliu. Kritinis kelias lemia bendrą veiklos trukmę. Visi kiti takai trumpesnės trukmės, todėl juose atliekami darbai turi laiko rezervų.

Tinklo schemoje kritinis kelias nurodomas pastorintomis arba dvigubomis linijomis (rodyklėmis).

Rengiant tinklo schemą ypač svarbios dvi sąvokos:

Ankstyva darbų pradžia – laikotarpis, iki kurio neįmanoma pradėti šių darbų nepažeidžiant priimtos technologinės sekos. Jį lemia ilgiausias kelias nuo inicijuojančio įvykio iki šio darbo pradžios.

Pavėluota pabaiga – tai vėliausia darbo pabaigos data, kuri nepailgina bendros darbo trukmės. Jį lemia trumpiausias kelias nuo tam tikro įvykio iki viso darbo užbaigimo.

Ankstyvas užbaigimas – tai terminas, iki kurio negalima užbaigti darbų. Tai lygu ankstyvam startui plius šio darbo trukmei.

Vėlyva pradžia – laikotarpis, po kurio neįmanoma pradėti šių darbų nepadidinus bendros statybos trukmės. Jis lygus pavėluotai apdailai atėmus nurodyto darbo trukmę.

Jei įvykis yra tik vieno darbo pabaiga (tai yra, į jį nukreipta tik viena rodyklė), tada ankstyva šio darbo pabaiga sutampa su ankstyva kitos užduoties pradžia.

Bendras (pilnas) rezervas – tai maksimalus laikas, kuriam šio darbo atlikimas gali būti atidėtas nedidinant bendros darbų trukmės. Jį lemia skirtumas tarp vėlyvo ir ankstyvo starto (arba vėlyvojo ir ankstyvo finišo – tai tas pats).

Privatus (nemokamas) rezervas – tai maksimalus laikas, kuriam galite atidėti šio darbo atlikimą, nekeisdami ankstyvos kito pradžios. Šis atsarginis variantas galimas tik tada, kai įvykis apima dvi ar daugiau veiklų (priklausomybių), t.y. dvi ar daugiau rodyklių (vientisos arba punktyrinės) rodo į jį. Tada tik vienas iš šių darbų turės ankstyvą pabaigą, kuri sutampa su ankstyva tolesnio darbo pradžia, o kitiems tai bus skirtingos vertybės. Šis kiekvieno kūrinio skirtumas bus jo privatus rezervas.

5. Dinaminis programavimas. Bellmano optimalumo ir valdymo principas.

Dinaminis programavimas yra vienas iš galingiausių optimizavimo metodų. Racionalių sprendimų priėmimo, geriausių variantų pasirinkimo, optimalios kontrolės užduotis sprendžia įvairaus profilio specialistai. Dinaminis programavimas užima ypatingą vietą tarp optimizavimo metodų. Šis metodas itin patrauklus dėl savo pagrindinio principo – optimalumo principo – paprastumo ir aiškumo. Optimalumo principo taikymo sritis itin plati, problemų, kurioms jis gali būti taikomas, spektras dar nėra iki galo nubrėžtas. Nuo pat pradžių dinaminis programavimas veikia kaip praktinio optimizavimo problemų sprendimo priemonė.

Be optimalumo principo, pagrindinio tyrimo metodo, svarbų vaidmenį dinaminio programavimo aparate atlieka idėja panardinti konkrečią optimizavimo problemą į panašių problemų šeimą. Trečias jo bruožas, išskiriantis jį iš kitų optimizavimo metodų, yra galutinio rezultato forma. Optimalumo principo ir panardinimo į daugiapakopius, diskrečius procesus principo taikymas lemia rekursines-funkcines lygtis, atsižvelgiant į optimalią kokybės kriterijaus reikšmę. Gautos lygtys leidžia nuosekliai užrašyti optimalius pirminės problemos valdiklius. Privalumas yra tas, kad viso proceso kontrolės skaičiavimo užduotis yra padalinta į keletą paprastesnių užduočių, skirtų atskirų proceso etapų kontrolės apskaičiavimui.

Pagrindinis metodo trūkumas yra, Bellmano žodžiais tariant, „dimensijų prakeiksmas“ – jo kompleksiškumas katastrofiškai didėja didėjant problemos dimensijai.

6. Lėšų paskirstymo tarp įmonių problema.

Galima sakyti, kad optimalaus valdymo konstravimo procedūra naudojant dinaminio programavimo metodą yra padalinta į du etapus: preliminarų ir galutinį. Preliminariame etape kiekvienam žingsniui SOC nustatomas atsižvelgiant į sistemos būseną (pasiekiamas dėl ankstesnių žingsnių), o sąlyginai optimalus padidėjimas visuose likusiuose etapuose, pradedant nuo šio, taip pat priklauso nuo valstybė. Paskutiniame etape nustatoma (besąlygiška) optimali kiekvieno žingsnio kontrolė. Preliminarus (sąlyginis) optimizavimas žingsnis po žingsnio atliekamas atvirkštine tvarka: nuo paskutinio žingsnio iki pirmo; galutinis (besąlyginis) optimizavimas – taip pat žingsniais, bet natūralia tvarka: nuo pirmo žingsnio iki paskutinio. Iš dviejų optimizavimo etapų pirmasis yra nepalyginamai svarbesnis ir daug laiko reikalaujantis. Pasibaigus pirmajam etapui, antrojo etapo įgyvendinimas nesukelia jokių sunkumų: belieka „perskaityti“ jau pirmame etape parengtas rekomendacijas.

7. Linijinio programavimo problemos teiginys.

Linijinis programavimas yra populiarus įrankis sprendžiant ekonomines problemas, kurioms būdingas vienas kriterijus (pavyzdžiui, maksimaliai padidinti pajamas iš gamybos per optimalų gamybos programos pasirinkimą arba, pavyzdžiui, sumažinti transportavimo išlaidas ir pan.) . Ekonominėms užduotims būdingi išteklių apribojimai (materialiniai ir (arba) finansiniai). Jie parašyti kaip nelygybių sistema, kartais kaip lygybės.

Prognozuojant priimtinus kainų intervalus (ar pardavimų apimtis) taikant apibendrintą neparametrinį metodą, linijinio programavimo naudojimas reiškia:

Kriterijus yra MAX kaina kitos prekės iš dominančios grupės f.

Valdomi kintamieji yra visų f grupės produktų kainos.

Mūsų prognozavimo problemos, naudojant apibendrintą neparametrinį metodą, apribojimai yra šie:

a) nelygybių sistema (vartotojų elgsenos racionalumo suvaržymai) (žr. 4.2. Prognozavimas apibendrinto neparametrinio metodo rėmuose);

b) valdomų kintamųjų neneigiamumo reikalavimas (savo prognozavimo uždavinyje reikalausime, kad f grupės produktų kainos nenukristų žemiau 80% paskutinio laiko momento kainų);

c) biudžeto suvaržymas lygybės pavidalu – reikalavimas, kad f grupės produktų pirkimo išlaidų suma būtų pastovi (pavyzdžiui, atsižvelgiant į 15 % infliaciją).

8. Grafinis metodas linijinio programavimo uždaviniams spręsti.

Grafinis metodas yra paremtas geometrine linijinio programavimo uždavinio interpretacija ir daugiausia naudojamas sprendžiant dvimatės erdvės uždavinius ir tik kai kuriuos trimatės erdvės uždavinius, kadangi gana sunku sukonstruoti sprendinių daugiasparnį, kuris būtų suformuotas kaip pustarpių susikirtimo rezultatas. Didesnių nei trijų matmenų erdvės užduotis apskritai negali būti pavaizduota grafiškai.

Tegul linijinio programavimo uždavinys yra pateiktas dvimatėje erdvėje, ty apribojimuose yra du kintamieji.

Raskite mažiausią funkcijos reikšmę

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) x1 0, x2 0

Tarkime, kad sistema (2.2) pagal sąlygą (2.3) yra nuosekli, o jos sprendimo daugiakampis yra ribotas. Kiekviena nelygybė (2.2) ir (2.3), kaip minėta aukščiau, apibrėžia pusplokštumą su ribinėmis linijomis: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Tiesinė funkcija (2.1) fiksuotoms Z reikšmėms yra tiesės lygtis: C1x1 + C2x2 = const. Sukonstruokime apribojimų sistemos (2.2) sprendinių daugiakampį ir tiesinės funkcijos (2.1) grafiką, kai Z = 0 (2.1 pav.). Tada pateiktą linijinio programavimo problemą galima interpretuoti taip. Raskite sprendinio daugiakampio tašką, kuriame tiesė C1x1 + C2x2 = const yra atramos linija, o funkcija Z pasiekia minimumą.

Reikšmės Z = C1x1 + C2x2 didėja vektoriaus N = (C1, C2) kryptimi, todėl tiesę Z = 0 perkeliame lygiagrečiai sau vektoriaus X kryptimi. Iš fig. 2.1 iš to seka, kad tiesė du kartus tampa atskaita sprendinių daugiakampio atžvilgiu (taškuose A ir C), o mažiausia reikšmė yra taške A. Taško A koordinates (x1, x2) randame išsprendę tiesių AB ir AE lygčių sistema.

Jei sprendimo daugiakampis yra neapribotas daugiakampis plotas, galimi du atvejai.

1 atvejis. Tiesė C1x1 + C2x2 = const, judanti vektoriaus N kryptimi arba priešinga jam, nuolat kerta sprendinio daugiakampį ir nėra jo nuoroda jokiame taške. Šiuo atveju tiesinė funkcija yra neapribota sprendinio daugiakampyje tiek aukščiau, tiek žemiau (2.2 pav.).

2 atvejis. Tiesi linija, judanti, vis dėlto tampa atrama sprendinių daugiakampio atžvilgiu (2.2 pav., a - 2.2, c). Tada, priklausomai nuo ploto tipo, tiesinė funkcija gali būti ribojama iš viršaus ir neribota iš apačios (2.2 pav., a), ribojama iš apačios ir neribota iš viršaus (2.2 pav., b), arba ribojama ir iš apačios, ir iš apačios, ir neribota iš apačios. iš viršaus (2.2 pav., c).

9. Simpleksinis metodas.

Simpleksinis metodas yra pagrindinis linijinio programavimo metodas. Uždavinio sprendimas pradedamas nagrinėjant vieną iš daugiakampio sąlygų viršūnių. Jei tiriama viršūnė neatitinka maksimumo (minimumo), tada jos pereina į gretimą, padidindamos tikslo funkcijos reikšmę sprendžiant uždavinį iki maksimumo ir sumažindamos sprendžiant uždavinį iki minimumo. Taigi, perėjimas iš vienos viršūnės į kitą pagerina tikslo funkcijos reikšmę. Kadangi daugiabriaunio viršūnių skaičius yra ribotas, tai baigtiniu žingsnių skaičiumi garantuojama rasti optimalią reikšmę arba nustatyti faktą, kad problema yra neišsprendžiama.

Šis metodas yra universalus, taikomas bet kokiai linijinio programavimo problemai kanonine forma. Apribojimų sistema čia yra tiesinių lygčių sistema, kurioje nežinomųjų skaičius yra didesnis už lygčių skaičių. Jei sistemos rangas yra r, tai galime pasirinkti r nežinomųjų, kuriuos išreikšime likusiais nežinomaisiais. Tikslumui darome prielaidą, kad pasirenkami pirmieji iš eilės nežinomieji X1, X2, ..., Xr. Tada mūsų lygčių sistemą galima parašyti kaip

Simplekso metodas pagrįstas teorema, vadinama pagrindine simplekso metodo teorema. Tarp optimalių kanoninės formos linijinio programavimo problemos planų būtinai yra jos apribojimų sistemos pamatinis sprendimas. Jei optimalus problemos planas yra unikalus, tai jis sutampa su kokiu nors etaloniniu sprendimu. Yra labai daug skirtingų apribojimų sistemos palaikymo sprendimų. Todėl problemos sprendimo kanonine forma galima būtų ieškoti išvardijant etaloninius sprendinius ir iš jų pasirenkant tą, kurio F reikšmė yra didžiausia. Bet, pirma, visi pamatiniai sprendimai yra nežinomi ir juos reikia rasti, antra, realiose problemose šių sprendimų yra daug ir tiesioginis surašymas sunkiai įmanomas. Simpleksinis metodas yra tam tikra etaloninių sprendinių nukreipto surašymo procedūra. Remdamiesi kokiu nors anksčiau rastu pamatiniu sprendiniu, naudojant tam tikrą simplekso metodo algoritmą, apskaičiuojame naują etaloninį sprendimą, kuriame tikslo funkcijos F reikšmė yra ne mažesnė nei senosios. Atlikę keletą veiksmų, pasiekiame pamatinį sprendimą, kuris yra optimalus planas.

10. Transporto problemos pareiškimas. Bazinių planų nustatymo metodai.

Tam tikros identiškos prekės yra m išvykimo ("tiekėjų") ir n vartojimo taškų ("vartotojų"). Kiekvienam elementui yra apibrėžti:

ai - i-ojo tiekėjo gamybos apimtys, i = 1, …, m;

вj - j-ojo vartotojo paklausa, j= 1,…,n;

cij – vieno produkcijos vieneto transportavimo kaina iš taško Ai – i-tas tiekėjas, į tašką Bj – j-asis vartotojas.

Aiškumo dėlei duomenis patogu pateikti lentelės forma, kuri vadinama transportavimo išlaidų lentele.

Būtina rasti tokį transportavimo planą, kuris pilnai patenkintų visų vartotojų poreikius, o tiekėjų pakaktų ir bendros transportavimo sąnaudos būtų minimalios.

Pagal susisiekimo planą suprantama eismo apimtis, t.y. prekių kiekis, kuris turi būti gabenamas iš i-ojo tiekėjo iki j-ojo vartotojo. Norint sukurti matematinį uždavinio modelį, reikia įvesti m n kintamųjų хij, i= 1,…, n, j= 1, …, m, kiekvienas kintamasis хij žymi srauto apimtį iš taško Ai į tašką Bj. Kintamųjų rinkinys X = (xij) bus planas, kurį reikia rasti remiantis problemos teiginiu.

Tai yra uždarų ir atvirų transporto užduočių (ZTZ) sprendimo sąlyga.

Akivaizdu, kad 1 uždaviniui išspręsti būtina, kad bendra paklausa neviršytų tiekėjų produkcijos apimties:

Jei ši nelygybė įvykdoma griežtai, tada problema vadinama „atvira“ arba „nesubalansuota“, jei , tada problema vadinama „uždara“ transporto problema ir bus tokia forma (2):

Balanso būklė.

Tai yra uždarų transporto užduočių (ZTZ) sprendimo sąlyga.

11. Transporto problemos sprendimo algoritmas.

Norint taikyti algoritmą, reikia laikytis kelių būtinų sąlygų:

1. Turi būti žinomos gaminio vieneto transportavimo iš kiekvienos gamybos vietos į kiekvieną paskirties vietą išlaidos.

2. Turi būti žinomos produkcijos atsargos kiekviename gamybos taške.

3. Turi būti žinomi maisto reikalavimai kiekvienoje vartojimo vietoje.

4. Bendra pasiūla turi būti lygi bendrai paklausai.

Transporto problemos sprendimo algoritmas susideda iš keturių etapų:

I etapas. Duomenų pateikimas standartinės lentelės forma ir bet kokio priimtino išteklių paskirstymo paieška. Priimtinas išteklių paskirstymas yra toks, kad jis patenkina visą paklausą paskirties vietose ir pašalina visą produktų pasiūlą iš gamybos taškų.

2 etapas. Gauto išteklių paskirstymo optimalumo tikrinimas

3 etapas. Jei gaunamas išteklių paskirstymas nėra optimalus, tada ištekliai perskirstomi, sumažinant transportavimo išlaidas.

4 etapas. Pakartotinis gauto išteklių paskirstymo optimalumo patikrinimas.

Šis kartotinis procesas kartojamas tol, kol gaunamas optimalus sprendimas.

12. Atsargų valdymo modeliai.

Nepaisant to, kad bet kuris atsargų valdymo modelis yra skirtas atsakyti į du pagrindinius klausimus (kada ir kiek), yra nemažai modelių, kurių kūrimui naudojami įvairūs matematiniai įrankiai.

Ši situacija paaiškinama pradinių sąlygų skirtumais. Pagrindinis atsargų valdymo modelių klasifikavimo pagrindas yra sandėliuojamų produktų paklausos pobūdis (prisiminkime, kad bendresnės gradacijos požiūriu dabar svarstome tik tuos atvejus, kai paklausa nepriklauso).

Taigi, priklausomai nuo paklausos pobūdžio, atsargų valdymo modeliai gali būti

deterministinis;

tikimybinis.

Savo ruožtu deterministinė paklausa gali būti statinė, kai vartojimo intensyvumas laikui bėgant nekinta, arba dinaminė, kai patikima paklausa laikui bėgant gali keistis.

Tikimybinė paklausa gali būti stacionari, kai paklausos tikimybės tankis laikui bėgant nekinta, ir nestacionari, kai tikimybių tankio funkcija kinta laikui bėgant. Aukščiau pateiktą klasifikaciją iliustruoja paveikslas.

Paprasčiausias yra deterministinės statinės produktų paklausos atvejis. Tačiau toks vartojimo būdas praktikoje yra gana retas. Sudėtingiausi modeliai yra nestacionaraus tipo modeliai.

Be produktų paklausos pobūdžio, kuriant atsargų valdymo modelius, reikia atsižvelgti į daugelį kitų veiksnių, pavyzdžiui:

pavedimų vykdymo terminai. Pirkimo laikotarpio trukmė gali būti pastovi arba atsitiktinis dydis;

papildymo procesas. Gali būti momentinis arba paskirstytas laikui bėgant;

apyvartinių lėšų, sandėliavimo vietos ir kt. apribojimų buvimas.

13. Eilių sistemos (QS) ir jų efektyvumo rodikliai.

Eilių sistemos (QS) – tai specialaus tipo sistemos, įgyvendinančios pakartotinį to paties tipo užduočių vykdymą. Tokios sistemos atlieka svarbų vaidmenį daugelyje ekonomikos, finansų, gamybos ir kasdienio gyvenimo sričių. Kaip BRO pavyzdžiai finansų ir ekonomikos srityse; Sferoje įvairių tipų bankai (komerciniai, investiciniai, hipotekos, inovatyvūs, taupomieji), draudimo organizacijos, valstybinės akcinės bendrovės, įmonės, firmos, asociacijos, kooperatyvai, mokesčių inspekcijos, audito paslaugos, įvairios ryšių sistemos (įskaitant telefono stotis). ), pakrovimo ir iškrovimo kompleksai (uostai, krovinių stotys), degalinės, įvairios paslaugų sektoriaus įmonės ir organizacijos (parduotuvės, informacijos punktai, kirpyklos, bilietų kasos, valiutos keityklos, remonto dirbtuvės, ligoninės). Tokios sistemos kaip kompiuterių tinklai, informacijos rinkimo, saugojimo ir apdorojimo sistemos, transporto sistemos, automatizuotos gamybos vietos, gamybos linijos, įvairios karinės sistemos, ypač oro gynybos ar priešraketinės gynybos sistemos, taip pat gali būti laikomos QS rūšimi.

Kiekvienas QS į savo struktūrą įtraukia tam tikrą skaičių paslaugų įrenginių, kurie vadinami aptarnavimo kanalais (įrenginiais, linijomis). Kanalų vaidmenį gali atlikti įvairūs įrenginiai, tam tikras operacijas atliekantys asmenys (kasininkai, operatoriai, kirpėjai, pardavėjai), ryšio linijos, automobiliai, kranai, remonto komandos, geležinkeliai, degalinės ir kt.

Eilių sistemos gali būti vieno kanalo arba kelių kanalų.

Kiekvienas QS skirtas aptarnauti (vykdyti) tam tikrą programų (reikalavimų) srautą, kuris dažniausiai patenka į sistemos įvestį ne reguliariai, o atsitiktiniu laiku. Užklausų aptarnavimas šiuo atveju taip pat trunka ne pastovų, žinomą, o atsitiktinį laiką, kuris priklauso nuo daugelio atsitiktinių, kartais mums nežinomų priežasčių. Aptarnavus užklausą, kanalas atleidžiamas ir yra pasirengęs priimti kitą užklausą. Atsitiktinis programų srauto pobūdis ir jų aptarnavimo laikas lemia netolygų QS darbo krūvį: kitu metu QS įvestyje gali kauptis neaptarnautos užklausos, dėl ko QS perkraunama, o kartais ir ten. nebus jokių užklausų prie QS su laisvais kanalais įvesties, dėl to QS per mažai apkraunama, t.y. kad jo kanalai veiktų tuščiąja eiga. Prie QS įėjimo besikaupiančios aplikacijos arba „patenka“ į eilę, arba dėl to, kad neįmanoma toliau likti eilėje, palieka QS neaptarnaujamą.

Poros „QS – vartotojas“ veiklos rodikliai, kur vartotojas suprantamas kaip visas programų rinkinys arba kai kurie jų šaltiniai (pavyzdžiui, vidutinės QS atnešamos pajamos per laiko vienetą ir pan.). Ši rodiklių grupė naudinga tais atvejais, kai kai kurios pajamos, gautos iš aptarnavimo užklausų, ir paslaugų kaštai matuojami tais pačiais vienetais. Šie rodikliai dažniausiai yra gana specifiniai ir yra nulemti QS specifikos, paslaugų užklausų ir aptarnavimo disciplinos.

14. Tikimybinių būsenų dinamikos lygtys (Kolmogorovo lygtys). Apriboti būsenų tikimybes.

Formaliai diferencijuodami Kolmogorovo-Chapman lygtį s atžvilgiu, kai s = 0, gauname tiesioginę Kolmogorovo lygtį:

Formaliai diferencijuodami Kolmogorovo-Chapman lygtį t atžvilgiu, kai t = 0, gauname atvirkštinę Kolmogorovo lygtį

Reikia pabrėžti, kad begalinių matmenų erdvėse operatorius nebūtinai yra tęstinis ir gali būti ne visur apibrėžtas, pavyzdžiui, kad būtų diferencinis operatorius skirstinių erdvėje.

Tuo atveju, kai sistemos S būsenų skaičius yra baigtinis ir iš kiekvienos būsenos (vienam ar kitam žingsnių skaičiui) galima pereiti į vieną kitą būseną, tada ribinės būsenų tikimybės egzistuoja ir taip pat nepriklauso. apie pradinę sistemos būseną.

Ant pav. rodo būsenų ir perėjimų, kurie tenkina sąlygą, grafiką: iš bet kurios būsenos sistema anksčiau ar vėliau gali pereiti į bet kurią kitą būseną. Sąlyga nebus įvykdyta, kai rodyklės 4-3 kryptis grafike pav. bus pakeista.

Tarkime, kad nurodyta sąlyga yra įvykdyta, todėl egzistuoja ribinės tikimybės:

Ribinės tikimybės bus žymimos tomis pačiomis raidėmis kaip ir būsenų tikimybės, tuo tarpu jos reiškia skaičius, o ne kintamuosius (laiko funkcijas).

Akivaizdu, kad ribojančios būsenų tikimybės turėtų susidėti į vienybę: Vadinasi, sistemoje nustatomas tam tikras ribojantis stacionarus režimas: tegul sistema keičia savo būsenas atsitiktinai, bet kiekvienos iš šių būsenų tikimybė nepriklauso nuo laiko ir kiekvienas iš jų atliekamas su tam tikra pastovia tikimybe, kuri yra vidutinis santykinis laikas, kurį sistema praleidžia šioje būsenoje.

15. Mirties ir dauginimosi procesas.

Markovo mirties ir dauginimosi procesu su nepertraukiamu laiku turime omenyje s.p., kuris gali turėti tik neneigiamas sveikųjų skaičių reikšmes; šio proceso pokyčiai gali įvykti bet kuriuo metu t, tuo tarpu bet kuriuo metu jis gali padidėti vienu arba likti nepakitęs.

Daugybos srautai λi(t) yra Puasono srautai, lemiantys funkcijos X(t) padidėjimą. Atitinkamai, μi (t) yra mirties srautai, dėl kurių sumažėja funkcija X (t).

Sudėkime Kolmogorovo lygtis pagal grafiką:

Jei gija su baigtiniu būsenų skaičiumi:

Kolmogorovo lygčių sistema mirties ir dauginimosi procesui su ribotu būsenų skaičiumi turi tokią formą:

Grynojo dauginimosi procesas yra toks mirties ir dauginimosi procesas, kuriame visų mirties srautų intensyvumas lygus nuliui.

Grynosios mirties procesas – tai toks mirties ir dauginimosi procesas, kuriame visų dauginimosi srautų intensyvumas lygus nuliui.

16. Eilių sistemos su gedimais.

Paprasčiausia iš nagrinėjamų problemų rikiuotės teorijos rėmuose yra vieno kanalo QS modelis su gedimais ar nuostoliais.

Reikėtų pažymėti, kad šiuo atveju kanalų skaičius yra 1 (). Šis kanalas gauna Puasono užklausų srautą, kurio intensyvumas lygus . Laikas turi įtakos intensyvumui:

Jei programa atkeliavo į kanalą, kuris šiuo metu nėra nemokamas, ji atmetama ir nebebus įtraukta į sistemą. Programos aptarnaujamos atsitiktiniu laiku, kurio paskirstymas įgyvendinamas pagal eksponentinį dėsnį su parametru:

17. Eilių sistemos su laukimu.

Užklausa, gauta tuo metu, kai kanalas yra užimtas, yra eilėje ir laukia aptarnavimo.

Sistema su ribotu eilės ilgiu. Pirmiausia darykime prielaidą, kad vietų skaičių eilėje riboja skaičius m, t.y., jei klientas atvyksta tuo metu, kai eilėje jau yra m klientų, jis palieka sistemą neaptarnaujamą. Ateityje, jei m links į begalybę, gausime vieno kanalo QS charakteristikas be eilės ilgio apribojimų.

QS būsenas sunumeruosime pagal užklausų skaičių sistemoje (tiek aptarnaujamų, tiek laukiančių paslaugų):

— kanalas nemokamas;

— kanalas užimtas, eilės nėra;

— kanalas užimtas, viena užklausa yra eilėje;

— kanalas užimtas, eilėje yra k - 1 užklausos;

- kanalas užimtas, eilėje yra daugybė programų.

18. Sprendimų priėmimo būdai konfliktinėmis sąlygomis. Matriciniai žaidimai. Gryni ir mišrūs strateginiai žaidimai.

Matricos žaidimas – tai galutinis dviejų žaidėjų žaidimas su nuline suma, kuriame 1 žaidėjo laimėjimas pateikiamas matricos pavidalu (matricos eilutė atitinka 2 žaidėjo taikomos strategijos numerį, stulpelis atitinka prie 2 žaidėjo taikomos strategijos skaičiaus; matricos eilutės ir stulpelio sankirtoje yra 1 žaidėjo laimėjimas, susijęs su taikytomis strategijomis).

Matriciniams žaidimams įrodyta, kad bet kuris iš jų turi sprendimą ir jį galima lengvai rasti sumažinus žaidimą iki linijinio programavimo uždavinio.

Dviejų žaidėjų nulinės sumos matricos žaidimą galima žiūrėti kaip šį abstraktų dviejų žaidėjų žaidimą.

Pirmasis žaidėjas turi m strategijų i = 1,2,...,m, antrasis turi n strategijų j = 1,2,...,n. Kiekvienai strategijų porai (i, j) priskiriamas skaičius aij, kuris išreiškia 1 žaidėjo atsipirkimą 2 žaidėjo sąskaita, jei pirmasis žaidėjas priima savo i-ąją strategiją, o 2 - savo j-ąją strategiją.

Kiekvienas iš žaidėjų atlieka vieną ėjimą: 1 žaidėjas pasirenka savo i-tąją strategiją (i=), 2 - j-ąją strategiją (j=), po to 1 žaidėjas gauna išmokėjimą aij 2 žaidėjo sąskaita (jei aij

Kiekviena žaidėjo strategija i=; j = dažnai vadinama grynąja strategija.

Apibrėžimas. Mišri žaidėjo strategija yra visas tikimybių rinkinys, kad jis pritaikys grynąsias strategijas.

Taigi, jei 1 žaidėjas turi m grynųjų strategijų 1,2,...,m, tai jo mišri strategija x yra skaičių x = (x1,..., xm) aibė, tenkinanti santykius

xi³ 0 (i= 1,m), =1.

Panašiai 2 žaidėjui, kuris turi n grynų strategijų, mišri strategija y yra skaičių rinkinys

y = (y1, ..., yn), yj ³ 0, (j = 1, n), = 1.

Kadangi kiekvieną kartą, kai žaidėjas naudoja vieną gryną strategiją, nenaudojama kita, grynos strategijos yra nesuderinami įvykiai. Be to, jie yra vieninteliai galimi įvykiai.

Gryna strategija yra ypatingas mišrios strategijos atvejis. Iš tiesų, jei mišrioje strategijoje kuri nors i-oji grynoji strategija taikoma su 1 tikimybe, tada visos kitos grynosios strategijos netaikomos. Ir ši i-oji grynoji strategija yra ypatingas mišrios strategijos atvejis. Norėdami išlaikyti paslaptį, kiekvienas žaidėjas taiko savo strategijas, nepaisant kito žaidėjo pasirinkimo.

19. Geometrinis matricinio žaidimo sprendimo metodas.

2xn arba nx2 dydžio žaidimų sprendimas leidžia aiškiai geometrinę interpretaciją. Tokius žaidimus galima išspręsti grafiškai.

XY plokštumoje išilgai abscisės atidedame vieną segmentą A1A2 (5.1 pav.). Kiekvienas atkarpos taškas yra susietas su kokia nors mišria strategija U = (u1, u2). Be to, atstumas nuo kokio nors tarpinio taško U iki dešiniojo šios atkarpos galo yra tikimybė u1 pasirinkti strategiją A1, atstumas iki kairiojo galo yra tikimybė u2 pasirinkti strategiją A2. Taškas A1 atitinka grynąją strategiją A1, taškas A2 – grynąją strategiją A2.

Taškuose A1 ir A2 atstatome statmenas ir atidedame ant jų esančių žaidėjų išmokas. Pirmajame statmenyje (sutampančiame su OY ašimi) rodome žaidėjo A laimėjimą naudojant A1 strategiją, antroje - naudojant strategiją A2. Jei žaidėjas A naudoja strategiją A1, tai jo laimėjimas su žaidėjo B strategija B1 yra 2, o su strategija B2 – 5. OY ašies skaičiai 2 ir 5 atitinka taškus B1 ir B2. Panašiai ant antrojo statmens randame taškus B "1 ir B" 2 (išmokos 6 ir 4).

Sujungus taškus B1 ir B"1, B2 ir B"2, gauname dvi tiesias linijas, nuo kurių atstumas iki OX ašies lemia vidutinį atlygį bet kokiam atitinkamų strategijų deriniui.

Pavyzdžiui, atstumas nuo bet kurio atkarpos B1B"1 taško iki ašies OX nustato vidutinį žaidėjo A išmokėjimą už bet kokį strategijų A1 ir A2 derinį (su tikimybėmis u1 ir u2) ir žaidėjo B strategiją B1.

Polilinei B1MB"2 priklausančių taškų ordinatės nustato minimalų žaidėjo A laimėjimą, kai jis naudoja bet kokias mišrias strategijas. Ši minimali reikšmė yra didžiausia taške M, todėl šis taškas atitinka optimalią strategiją U* = ( ,), o jo ordinatė lygi žaidimo kainai v.

Taško M koordinates randame kaip tiesių B1B"1 ir B2B"2 susikirtimo taško koordinates.

Norėdami tai padaryti, turite žinoti linijų lygtis. Tokias lygtis galite sudaryti naudodami tiesės, einančios per du taškus, lygties formulę:

Sudarykime tiesių lygtis mūsų uždaviniui.

B1B eilutė"1: = arba y = 4x + 2.

Tiesioginis B2B "2: = arba y = -x + 5.

Gauname sistemą: y = 4x + 2,

Išspręskime: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Taigi U = (2/5, 3/5), v = 22/5.

20. Bimatrix žaidimai.

Bimatricinis žaidimas – tai baigtinis dviejų žaidėjų žaidimas su ne nuline suma, kuriame kiekvieno žaidėjo laimėjimai pateikiami matricomis atskirai atitinkamam žaidėjui (kiekvienoje matricoje eilutė atitinka 1 žaidėjo strategiją, stulpelis atitinka 2 žaidėjo strategiją, pirmosios matricos eilutės ir stulpelio sankirtoje yra 1 žaidėjo laimėjimas, antroje matricoje - 2 žaidėjo laimėjimas.)

Bimatriciniams žaidimams taip pat sukurta optimalaus žaidėjų elgesio teorija, tačiau tokius žaidimus išspręsti yra sunkiau nei įprastus matricinius žaidimus.

21. Statistiniai žaidimai. Sprendimų priėmimo visiško ir dalinio neapibrėžtumo sąlygomis principai ir kriterijai.

Operacijų tyrimuose įprasta skirti tris neapibrėžčių tipus:

tikslų neapibrėžtumas;

mūsų žinių apie aplinką ir šį reiškinį veikiančius veiksnius neapibrėžtumas (gamtos neapibrėžtumas);

aktyvaus ar pasyvaus partnerio ar priešininko veiksmų neapibrėžtumas.

Aukščiau pateiktoje klasifikacijoje neapibrėžčių tipas vertinamas vieno ar kito matematinio modelio elemento požiūriu. Taigi, pavyzdžiui, tikslų neapibrėžtumas atsispindi formuluojant problemą pasirenkant atskirus kriterijus arba visą naudingo poveikio vektorių.

Kita vertus, kiti du neapibrėžčių tipai daugiausia turi įtakos suvaržymo lygčių tikslinės funkcijos formulavimui ir sprendimo metodui. Žinoma, aukščiau pateiktas teiginys yra gana sąlyginis, kaip ir bet kuri klasifikacija. Pateikiame jį tik norėdami pabrėžti dar kai kuriuos neapibrėžtumo bruožus, kuriuos reikia turėti omenyje priimant sprendimus.

Faktas yra tas, kad, be aukščiau pateiktos neapibrėžčių klasifikacijos, reikia atsižvelgti į jų tipą (arba „rūšį“) jų santykio su atsitiktinumu požiūriu.

Tuo remiantis galima atskirti stochastinę (tikimybinę) neapibrėžtį, kai nežinomi veiksniai yra statistiškai stabilūs ir todėl yra įprasti tikimybių teorijos objektai – atsitiktiniai dydžiai (arba atsitiktinės funkcijos, įvykiai ir pan.). Tokiu atveju nustatant problemą turi būti žinomos arba nustatytos visos būtinos statistinės charakteristikos (paskirstymo dėsniai ir jų parametrai).

Tokių užduočių pavyzdys gali būti visų pirma bet kokio tipo įrangos priežiūros ir remonto sistema, retinimo organizavimo sistema ir kt.

Kitas kraštutinis atvejis gali būti nestochastinis neapibrėžtumas (pagal E. S. Wentzel – „blogas neapibrėžtumas“), kuriame nėra prielaidų apie stochastinį stabilumą. Galiausiai galime kalbėti apie tarpinį neapibrėžtumo tipą, kai sprendimas priimamas remiantis kai kuriomis hipotezėmis apie atsitiktinių dydžių pasiskirstymo dėsnius. Tuo pačiu sprendimus priimantis asmuo turi turėti omenyje pavojų, kad jo rezultatai gali neatitikti realių sąlygų. Ši neatitikimo rizika įforminama rizikos koeficientų pagalba.

Sprendimas dėl rizikos gali būti priimtas remiantis vienu iš šių kriterijų:

tikėtinos vertės kriterijus;

tikėtinos vertės ir dispersijos deriniai;

žinomas ribinis lygis;

labiausiai tikėtinas įvykis ateityje.