MOP uždavinių sprendimas (optimizavimo metodai). Valdymo sprendimų rengimo metodinis pagrindas Sprendimas vadinamas optimaliu

Linijinis programavimas yra matematikos šaka, tirianti metodus, leidžiančius rasti baigtinio skaičiaus kintamųjų tiesinės funkcijos minimumą arba maksimumą, jei kintamieji tenkina ribotą apribojimų skaičių tiesinių lygčių arba tiesinių nelygybių pavidalu.

Taigi, bendra užduotis linijinis programavimas(ZLP) gali būti suformuluotas taip.

Raskite realių kintamųjų, kuriems objektyvią funkciją

įgauna mažiausią taškų, kurių koordinatės tenkina, aibės reikšmę apribojimų sistema

Kaip žinoma, sutvarkytas vertybių rinkinys n kintamieji , , … yra vaizduojamas tašku n-matės erdvėje. Toliau mes pažymėsime šį tašką X=( , , … ).

Matricos formoje linijinio programavimo problemą galima suformuluoti taip:

, A- dydžio matrica,

Taškas X=( , , … ), tenkinantis visas sąlygas, vadinamas galiojantis taškas . Iškviečiama visų leistinų taškų aibė galiojantis plotas .

Optimalus sprendimas (optimalus planas) linijinio programavimo uždavinys vadinamas sprendimu X=( , , … ), priklausanti leistinai sričiai ir kuriai taikoma tiesinė funkcija K paima optimalią (didžiausią arba mažiausią) reikšmę.

Teorema. Visų galimų linijinio programavimo uždavinio apribojimų sistemos sprendimų rinkinys yra išgaubtas.

Taškų rinkinys vadinamas išgaubtas , jei jame kartu su bet kuriais dviem jo taškais yra jų savavališkas išgaubtas tiesinis derinys.

Taškas X paskambino išgaubtas linijinis derinys taškų, jei tenkinamos sąlygos

Visų galimų linijinio programavimo problemos sprendimų rinkinys yra išgaubta daugiakampė sritis, kurią nuo šiol vadinsime sprendinių daugiakampis .

Teorema. Jei ZLP turi optimalų sprendimą, tai tikslo funkcija įgauna didžiausią (minimalią) reikšmę vienoje iš sprendinio daugiakampio viršūnių. Jei tikslo funkcija įgauna didžiausią (minimalią) reikšmę daugiau nei viename taške, tada ji įgauna šią reikšmę bet kuriame taške, kuris yra išgaubta tiesinė šių taškų kombinacija.

Tarp daugybės sistemos sprendimų m tiesinės lygtys, apibūdinančios sprendinių daugiakampį, išskiriami vadinamieji pagrindiniai sprendiniai.

Pagrindinis sistemos sprendimas m tiesinės lygtys su n kintamųjų yra sprendimas, kuriame visi n-m nepagrindiniai kintamieji yra nulis. Tiesinio programavimo uždaviniuose tokie sprendimai vadinami leistini pagrindiniai sprendiniai (pavyzdiniai planai).

Teorema. Kiekvienas leistinas pagrindinis tiesinio programavimo uždavinio sprendinys atitinka sprendinio daugiakampio viršūnę, ir atvirkščiai, kiekvieną sprendinio daugiakampio viršūnę atitinka leistinas pagrindinis sprendinys.

Iš aukščiau pateiktų teoremų išplaukia svarbi išvada:

Jei linijinio programavimo uždavinys turi optimalų sprendimą, tada jis sutampa su bent vienu iš galimų pagrindinių sprendimų.

Vadinasi, tiesinio programavimo uždavinio tikslo tiesinės funkcijos optimumo reikia ieškoti tarp baigtinio skaičiaus įmanomų pagrindinių sprendimų.

Ekonominių problemų sprendimo pagrindas yra matematiniai modeliai.

Matematinis modelis problema yra matematinių ryšių, apibūdinančių problemos esmę, visuma.

• problemos kintamųjų pasirinkimas
• apribojimų sistemos sudarymas
• objektyvios funkcijos pasirinkimas

Užduočių kintamieji vadinami dydžiais X1, X2, Xn, kurie visiškai apibūdina ekonominį procesą. Paprastai jie rašomi kaip vektorius: X=(X 1, X 2,...,X n).

Apribojimų sistema problemos – tai lygčių ir nelygybių rinkinys, apibūdinantis ribotus nagrinėjamos problemos išteklius.

Objektyvi funkcija užduotys vadinamos užduoties kintamųjų funkcija, kuri apibūdina užduoties kokybę ir kurios ekstremumą reikia rasti.

IN bendras atvejis Linijinio programavimo uždavinį galima parašyti taip:

Šis įrašas reiškia: suraskite tikslo funkcijos (1) ekstremumą ir atitinkamus kintamuosius X=(X 1, X 2,...,X n) su sąlyga, kad šie kintamieji atitinka apribojimų (2) ir ne sistemą. -neigiamumo sąlygos (3) .

Tinkamas sprendimas Tiesinio programavimo uždavinio (planas) yra bet koks n matmenų vektorius X=(X 1 , X 2 ,...,X n), kuris tenkina apribojimų ir neneigiamumo sąlygų sistemą.

Problemos formų galimų sprendimų (planų) rinkinys galimų sprendimų regionas(ODR).

Optimalus sprendimas linijinio programavimo uždavinio (planas) yra toks leistinas problemos sprendimas (planas), kuriame tikslo funkcija pasiekia kraštutinumą.

Matematinio modelio sudarymo pavyzdys

Išteklių (žaliavų) naudojimo problema

Būklė: Norint pagaminti n rūšių produktus, sunaudojama m rūšių išteklių. Sukurkite matematinį modelį.

Žinomas:

• b i (i = 1,2,3,...,m) — kiekvieno i-to tipo išteklių atsargos;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - kiekvieno i-to tipo išteklių sąnaudos tūrio vieneto gamybai j-osios prekės rūšies;
• c j (j = 1,2,3,...,n) - pelnas pardavus j-osios rūšies gaminio tūrio vienetą.

Būtina sudaryti gamybos planą, kuris užtikrintų maksimalų pelną esant tam tikriems išteklių (žaliavų) apribojimams.

Sprendimas:

Įveskime kintamųjų X=(X 1, X 2,...,X n) vektorių, kur x j (j = 1,2,...,n) yra j-ojo tipo gamybos apimtis. produktas.

I-ojo tipo išteklių sąnaudos tam tikro tūrio x j produktų gamybai yra lygios a ij x j , todėl išteklių naudojimo apribojimas visų rūšių gaminių gamybai turi tokią formą:
Pelnas pardavus j-osios rūšies produktą yra lygus c j x j, taigi tikslo funkcija lygi:

Atsakymas- Matematinis modelis turi formą:

Linijinio programavimo uždavinio kanoninė forma

Bendruoju atveju linijinio programavimo uždavinys yra parašytas taip, kad apribojimai yra ir lygtys, ir nelygybės, o kintamieji gali būti arba neneigiami, arba savavališkai kintantys.

Tuo atveju, kai visi apribojimai yra lygtys ir visi kintamieji tenkina neneigiamumo sąlygą, linijinio programavimo uždavinys vadinamas kanoninis.

Jis gali būti pavaizduotas koordinačių, vektorių ir matricų užrašais.

Kanoninio linijinio programavimo problema koordinačių žymėjime yra tokia:

Kanoninio linijinio programavimo problema matricos žymėjime yra tokia:

• A – lygčių sistemos koeficientų matrica
• X – užduoties kintamųjų matrica-stulpelis
• Ао — apribojimų sistemos dešiniųjų dalių matrica-stulpelis

Dažnai naudojamos linijinės programavimo problemos, vadinamos simetrinėmis, kurios matricoje yra tokios formos:

Bendrosios linijinio programavimo problemos sumažinimas iki kanoninės formos

Daugumoje linijinio programavimo problemų sprendimo metodų daroma prielaida, kad apribojimų sistema susideda iš lygčių ir natūralių kintamųjų neneigiamumo sąlygų. Tačiau, sudarant ekonominių problemų modelius, apribojimai daugiausia formuojami nelygybių sistemos pavidalu, todėl reikia mokėti pereiti nuo nelygybių sistemos prie lygčių sistemos.

Paimkime tiesinę nelygybę a 1 x 1 +a 2 x 2 +...+a n x n ≤b ir prie jos kairiosios pusės pridėkime tam tikrą reikšmę x n+1, kad nelygybė virstų lygybe a 1 x 1 +a 2 x 2 + ...+a n x n +x n+1 =b. Be to, ši reikšmė x n+1 yra neneigiama.

Pažvelkime į viską naudodami pavyzdį.

Pateikite linijinio programavimo problemą kanonine forma:

Sprendimas:
Pereikime prie tikslo funkcijos maksimumo radimo problemos.
Tam pakeičiame tikslo funkcijos koeficientų ženklus.
Antrąją ir trečiąją apribojimų sistemos nelygybes paversti lygtimis, įvedame neneigiamus papildomus kintamuosius x 4 x 5 (matematiniame modelyje ši operacija žymima raide D).
Kintamasis x 4 įvedamas į kairę antrosios nelygybės pusę su „+“ ženklu, nes nelygybė turi formą „≤“.
Kintamasis x 5 įvedamas į kairę trečiosios nelygybės pusę su ženklu „-“, nes nelygybė turi formą „≥“.
Kintamieji x 4 x 5 įvedami į tikslo funkciją su koeficientu. lygus nuliui.
Uždavinį rašome kanonine forma.

Operacijų tyrimas yra sudėtinga matematinė disciplina, nagrinėjanti matematinių modelių konstravimą, analizę ir taikymą, kad būtų galima priimti optimalius sprendimus operacijų metu.

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

Operacijų tyrimo tikslas- priimtų sprendimų dėl organizacijų valdymo kiekybinis pagrindimas

Operacija- kontroliuojamų veiksmų sistema, kurią vienija vienas planas ir siekiama konkretaus tikslo.

Vadinamasis valdymo parametrų (kintamųjų) rinkinys operacijos metu sprendimą. Sprendimas vadinamas priimtina , jei jis atitinka tam tikras sąlygas. Sprendimas vadinamas optimalus

, jei jis yra priimtinas ir, pagal tam tikrus kriterijus, geresnis už kitus arba bent jau ne blogesnis. Pirmenybės ženklas

vadinamas optimalumo kriterijumi. Optimalumo kriterijus

apima tikslo funkciją, optimizavimo kryptį arba tikslo funkcijų rinkinį ir atitinkamas optimizavimo kryptis. Objektyvi funkcija

yra kiekybinis sprendimų pirmenybės arba efektyvumo rodiklis. Optimizavimo kryptis

- tai didžiausia (minimali), jei geriausia (mažiausia) tikslo funkcijos reikšmė.

Pavyzdžiui, kriterijus gali būti maksimalus pelnas arba išlaidų mažinimas.

Matematinis IO problemos modelis apima:

1) kintamųjų, kuriuos reikia rasti, aprašymas;

2) optimalumo kriterijų aprašymas;– kiekybiškai ir kokybiškai pagrįsti priimamą sprendimą. Galutinį sprendimą priima atsakingas asmuo arba žmonių grupė, vadinama sprendimų priėmėju.

Vektorius, kuris tenkina apribojimų sistemą, vadinamas priimtinas sprendimasarba planą ZLP. Visų planų rinkinys vadinamas galiojantis plotas arbagalimų sprendimų sritis. Iškviečiamas planas, suteikiantis maksimalų (minimumą) tikslo funkcijąoptimalus planas arbaoptimalus ZLP sprendimas. Taigi,išspręsti PIL – reiškia rasti optimalų planą.

Labai paprasta perkelti bendrąjį ZLP į pagrindinį, laikantis šių akivaizdžių taisyklių.

Tikslinės funkcijos sumažinimas f yra tolygus funkcijos padidinimui g = – f.

Nelygybės apribojimas yra lygiavertis lygčiai, jei papildomas kintamasis.

Jei tam tikram kintamajam x j neneigiamumo sąlyga netaikoma, tada atliekamas kintamojo pakeitimas.

Lygio linija funkcijas f, ty linija, išilgai kurios ši funkcija įgauna tą pačią fiksuotą reikšmę Su, t.y. f(x 1 , x 2)= c

Taškų rinkinys vadinamas išgaubtas, jei joje kartu su bet kuriais dviem jo taškais yra visa atkarpa, jungianti šiuos taškus.

Dviejų kintamųjų atveju tiesinės nelygybės (lygties) sprendinių aibė yra pusplokštuma (tiesė).

Šių pusiau plokštumų (ir tiesių, jei apribojimų sistema turi lygtis) sankirta parodo įmanomą sritį. Jei jis nėra tuščias, tada jis yra išgaubtas ir vadinamas.

sprendimo daugiakampis Trijų kintamųjų atveju leistina ZLP sritis yra pustarpių ir, galbūt, plokštumų sankirta, ir vadinama

sprendinių daugiakampisTiesinių lygčių sistema vadinama, sistema su pagrindu jei kiekvienoje lygtyje yra nežinomasis, kurio koeficientas lygus 1, kurio nėra kitose sistemos lygtyse. Šie nežinomieji vadinami, pagrindinis – poilsis.

nemokamai Tiesinių lygčių sistemą vadinsime, kanoninisjei tai sistema su pagrindu ir viskas b i ≥ 0. Pagrindinis sprendimas šiuo atveju yra planas, nes jo komponentai yra neneigiami. Paskambinkime jam pagrindinis (arba) planą remiant

kanoninė sistema. Tiesinių lygčių sistemą vadinsime Mes tai vadinsime OZLP

(KZLP), jei šio uždavinio tiesinių lygčių sistema yra kanoninė, o tikslo funkcija išreiškiama tik laisvaisiais nežinomaisiais. Jei simpleksinėje lentelėje tarp bet kurio laisvojo nežinomojo koeficientų yra bent vienas teigiamas elementas, tada galimas perėjimas prie naujos kanoninės problemos, lygiavertės pradinei, kurioje nurodytas laisvasis nežinomasis pasirodo esąs pagrindinis (in šiuo atveju vienas iš pagrindinių nežinomųjų tampa laisvas) .

2 teorema. (dėl pradinio lygio pagerinimo) j ir x stulpelyje j Jei yra bent vienas teigiamas elementas, o raktinis ryšys yra >0, tai galimas perėjimas prie lygiavertės kanoninės problemos su ne prastesniu pagrindiniu dizainu.

3 teorema. (pakankama sąlyga optimalumui). 0 Jei visi maksimizavimo uždavinio simpleksinės lentelės indekso eilutės elementai yra neneigiami, tada pagrindinis šios problemos dizainas yra optimalus ir su

probleminių planų rinkinyje yra tikslo funkcijos maksimumas.. 4 teorema(neribotos tikslo funkcijos atvejis) j . j Jei maksimizavimo uždavinio simpleksinės lentelės indekso eilutėje yra neigiamas elementas su

, o nežinomame stulpelyje x

visi elementai yra neteigiami, tada problemų planų aibėje tikslo funkcija nėra ribojama iš viršaus.

Paprastas metodas:

Įrašome šį KZLP į pradinę simplekso lentelę.

Jei visi simpleksinės lentelės indekso eilutės elementai yra neneigiami, tai pagrindinis uždavinio planas yra optimalus (3 teorema).

Jei indekso eilutėje yra neigiamas elementas, kurio teigiamo elemento lentelėje nėra, tai tikslo funkcija nėra apribota planų aibėje iš viršaus ir uždavinys neturi sprendimų (4 teorema).

Jei lentelėje virš kiekvieno neigiamo indekso eilutės elemento yra bent vienas teigiamas elementas, tuomet reikėtų pereiti prie naujos simpleksinės lentelės, kurios pagrindinis planas nėra prastesnis už ankstesnį (2 teorema). Šiuo tikslu (žr. 1 teoremos įrodymą) jei tai sistema su pagrindu ir viskas b lentelėje pasirinkite raktinį stulpelį, kurio apačioje yra koks nors neigiamas indekso eilutės elementas;

pasirinkite raktinį ryšį (mažiausią iš santykių

Nagrinėjant gautą simpleksinę lentelę, vienas iš trijų pastraipose aprašytų atvejų tikrai atsiras. 2, 3, 4. Jei pastraipose susidaro situacijos. 2 arba 3, tada problemos sprendimo procesas baigiasi, bet jei susidaro situacija 4 veiksme, procesas tęsiamas.

Jei atsižvelgsime į tai, kad skirtingų pagrindinių planų skaičius yra baigtinis, galimi du atvejai:

po baigtinio žingsnių skaičiaus problema bus išspręsta (atsiras 2 arba 3 situacijos);

pradedant nuo tam tikro žingsnio atsiranda kilpa(periodinis simpleksinių lentelių ir pagrindinių planų kartojimas).

Šios užduotys vadinamos simetriškos dvigubos problemos.

Atkreipkime dėmesį į šias funkcijas, jungiančias šias užduotis:

Viena iš problemų yra maksimizavimo problema, o kita – sumažinimo problema.

Maksimizavimo uždavinyje visos nelygybės yra ≤, o minimizavimo uždavinyje visos nelygybės yra ≥.

Vienos problemos nežinomųjų skaičius yra lygus kitos problemos nelygybių skaičiui.

Abiejų uždavinių nelygybėse nežinomųjų koeficientų matricos yra tarpusavyje perkeltos.

Vieno uždavinio laisvieji nelygybių dėmenys yra lygūs atitinkamų nežinomųjų koeficientams kitos problemos tikslo funkcijos išraiškoje.

Dvigubo uždavinio konstravimo algoritmas.

1. Visas pirminės problemos suvaržymų sistemos nelygybes suvesti į vieną reikšmę – į kanoninę formą.

2. Sukurkite išplėstinę sistemos A matricą, kuri apima b i stulpelį ir tikslo funkcijos F koeficientus.

3. Raskite transponuotą matricą A T.

4. Užrašykite dvigubą problemą. 5 teorema.

f(x) ≤ g(Maksimizavimo uždavinio objektyvios funkcijos vertė nė vienam iš jos planų neviršija dvigubos minimizavimo problemos objektyvios funkcijos vertės jokiam jo planui, t. y. galioja ši nelygybė:),

y paskambino.

pagrindinė dvilypumo nelygybė (6 teorema.pakankama sąlyga optimalumui

). (Jei kai kuriems dvigubų problemų planams tikslinių funkcijų reikšmės yra vienodos, tada šie planai yra optimalūs.7 teorema. pamatinė dvilypumo teorema).

Jei ZLP turi baigtinį optimalumą, tada jo dualas taip pat turi baigtinį optimalumą, ir (optimalios vertėstikslinės funkcijos sutampa. Jei vienos iš dvejopų uždavinių objektyvi funkcija nėra ribojama, tai kitos problemos sąlygos yra prieštaringos.

8 teorema.

Dvigubo ZLP optimalaus sprendimo komponentai yra lygūs atitinkamiems tiesioginės problemos optimalios simpleksinės lentelės indekso eilutės elementams, atitinkantiems papildomus kintamuosius.

11 teorema.(transporto problemos plano optimalumo kriterijus). Kad transportavimo planas) būtų optimalus, būtina ir pakanka, kad būtų skaičiai () ir (), atitinkantys šias sąlygas:

a) visoms pagrindinėms plano ląstelėms (>0);

b) visoms laisvoms ląstelėms (=0).

Potencialus metodas

1 veiksmas. Patikrinkite, ar ši transportavimo užduotis uždaryta. Jei taip, pereikite prie antrojo veiksmo. Jei ne, sumažinkite ją iki uždaros problemos, pristatydami arba fiktyvų tiekėją, arba fiktyvų vartotoją.

2 veiksmas. Raskite pradinį pamatinį uždaros transporto problemos sprendimą (pradinį atskaitos planą).

3 veiksmas. Patikrinkite gauto palaikymo sprendimo optimalumą:

apskaičiuoti tiekėjo potencialą u i ir vartotojai v j

visoms laisvoms ląstelėms ( b, j) apskaičiuoti sąmatas;

jei visi įverčiai nėra teigiami (), tada problemos sprendimas baigtas: pirminis atskaitos planas yra optimalus. Jei tarp vertinimų yra bent vienas teigiamas, pereiname prie ketvirto žingsnio.

4 veiksmas. Pasirinkite langelį ( b * ,j * ) su didžiausiu teigiamu įvertinimu ir jam sukurti uždarą krovinių perskirstymo ciklą. Ciklas prasideda ir baigiasi pasirinktoje ląstelėje. b * , j * Gauname naują palaikymo sprendimą, kuriame ląstelė (

) bus užimtas. Grįžkime prie trečiojo žingsnio.

Atlikus baigtinį žingsnių skaičių, bus gautas optimalus sprendimas, t.y., optimalus produkcijos transportavimo nuo tiekėjų iki vartotojų planas. Taškas vadinamas tašku vietinis maksimumas

, jei yra šio taško kaimynystė tokia, kad

Būtinos sąlygos optimalumui x * Kad vieno kintamojo funkcija taške turėtų

vietinis ekstremumas, būtina, kad funkcijos išvestinė šiame taške būtų lygi nuliui,

Kad funkcija taške turėtų lokalinį ekstremumą, būtina, kad visos jos dalinės išvestinės šiame taške išnyktų x * Jei taške x * pirmoji funkcijos išvestinė lygi nuliui, o antroji išvestinė >0, tada funkcija taške<0 то функция в точке x * turi vietinį minimumą, jei 2 produktai,

turi vietinį maksimumą. 4 teorema. x * Jei vieno kintamojo funkcija turi taške n - dariniai iki (

1) eilės lygios nuliui, o n eilės išvestinė nėra lygi 0, tada n Jeigu x * net, tada taškas

yra mažiausias taškas if,fn(x)>0<0.

maksimalus taškas, jei fn(x) n Jeigu x * nelyginis, tada taškas

– vingio taškas. kvadratinės formos matrica .

Kvadratinė forma (5) vadinama teigiamas apibrėžtas, jei Q(X) >0 ir neigiamai apibrėžtas, jei už.Q(X)<0

Simetrinė matrica A paskambino teigiamas apibrėžtas, jei iš jos sudaryta kvadratinė forma (5) yra teigiama apibrėžtoji.

Vadinama simetriška matrica neigiamai apibrėžtas, jei iš jos sudaryta kvadratinė forma (6) yra neigiama apibrėžtoji.

Sylvesterio kriterijus: matrica yra teigiama, jei visi jos kampiniai mažumai yra didesni už nulį.

Matrica yra neigiama, jei kampinių nepilnamečių ženklai pakaitomis.

Kad matrica būtų teigiama apibrėžtoji, visos jos savosios reikšmės turi būti didesnės už nulį.

Savosios vertybės– daugianario šaknys.

Pakankama optimalumo sąlyga pateikiama tokia teorema.

5 teorema. Jei stacionariame taške Heseno matrica yra teigiama apibrėžtoji, tai šis taškas yra vietinis minimumas, jei Heseno matrica yra neigiama apibrėžta, tai šis taškas yra vietinis maksimalus taškas.

Konfliktas yra prieštaravimas, kurį sukelia priešingi šalių interesai.

Konfliktinė situacija- situacija, kai šalys, kurių interesai visiškai arba iš dalies prieštarauja.

Žaidimas - tai realus arba formalus konfliktas, kuriame dalyvauja bent du dalyviai, kurių kiekvienas siekia savo tikslų

Žaidimo taisyklėsįvardykite leistinus kiekvieno žaidėjo veiksmus, skirtus tam tikram tikslui pasiekti.

Sumokėjus vadinamas kiekybiniu žaidimo rezultatų įvertinimu.

Dvejetų žaidimas– žaidimas, kuriame dalyvauja tik dvi partijos (du žaidėjai).

Nulinės sumos žaidimas arba antagonistinis - dvigubas žaidimas, kuriame mokėjimo suma lygi nuliui, tai yra, jei vieno žaidėjo pralaimėjimas yra lygus kito laimėjimui.

Vieno iš taisyklėse numatytų veiksmų pasirinkimas ir įgyvendinimas vadinamas žaidėjo ėjimas. Judėjimai gali būti asmeniški ir atsitiktiniai.

Asmeninis judėjimas yra sąmoningas žaidėjo vieno iš galimų veiksmų pasirinkimas (pavyzdžiui, ėjimas šachmatų partijoje).

Atsitiktinis judesys yra atsitiktinai pasirinktas veiksmas (pavyzdžiui, kortos pasirinkimas iš sumaišytos kaladės).

strategijažaidėjas – tai nedviprasmiškas žaidėjo pasirinkimas kiekvienoje iš galimų situacijų, kai šis žaidėjas turi atlikti asmeninį ėjimą.

Optimali strategija- tai žaidėjo strategija, kuri, kai žaidimas kartojamas daug kartų, suteikia jam didžiausią įmanomą vidutinį laimėjimą arba minimalų galimą vidutinį pralaimėjimą.

Mokėjimo matrica– gautą matricą A arba, kitaip tariant, žaidimo matrica s.

Baigtinis matmenų žaidimas(m  n) yra žaidimas, apibrėžiamas matmens A matrica (m  n).

Maksiminas arba mažesnė žaidimo kaina pavadinkime skaičių alpa = max(i)(min aij)(j)

ir atitinkama strategija (eilutė) maksimalus.

Minimax arba aukščiausia žaidimo kaina pavadinkime skaičių Beta = min(j)(max aij)i

ir atitinkama strategija (stulpelis) minimalus maks.

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

Žaidimas su balno smaigaliu vadinamas žaidimas, kuriam. Alp = beta

Žaidimo kaina vadinamas dydžiu v if.v = alp = beta

Mišri strategijažaidėjas yra vektorius, kurio kiekvienas komponentas rodo santykinį žaidėjo naudojimosi atitinkama gryna strategija dažnį.

Teorema 2 .

Pagrindinė matricinių žaidimų teorijos teorema.

Kiekvienas nulinės sumos matricos žaidimas turi mišrių strategijų sprendimą.3

T

Jei vienas iš žaidėjų naudoja optimalią mišrią strategiją, tada jo išmokėjimas yra lygus žaidimo kainai  nepriklausomai nuo to, kaip dažnai antrasis žaidėjas naudoja savo strategijas (įskaitant grynąsias strategijas).

žaidimas su gamta - žaidimas, kuriame mes neturime informacijos apie partnerio elgesįRizika r ij

Rizika r = jei tai sistema su pagrindu ir viskas j - žaidėjas renkantis strategiją A i sąlygomis H j vadinamas skirtumu b ,

a jei tai sistema su pagrindu ir viskas j Kur j- maksimalus elementas

- stulpelis.

Grafas yra netuščios aibės rinkinys, vadinamas

grafo viršūnių aibė ir viršūnių porų aibė, kurios vadinamos

grafiko briaunos.

Jei nagrinėjamos viršūnių poros yra sutvarkytos, tai grafikas

vadinamas orientuotu (digrafu), kitaip –

neorientuotas.

IN

Vadinamas maršrutas (kelis) grafe, jungiantis viršūnes A ir B

briaunų seka, iš kurių pirmoji ateina iš viršūnės A, pradžios

kitas sutampa su ankstesnio pabaiga, o paskutinis kraštas įtraukiamas

viršuje V.

Grafas vadinamas sujungtu, jei bet kurioms dviem jo viršūnėms yra kelias

juos sujungiant. Kitu atveju grafikas vadinamas atjungtu.

Grafas vadinamas baigtiniu, jei jo viršūnių skaičius yra baigtinis.

Jei viršūnė yra briaunos pradžia arba pabaiga, tada viršūnė ir briauna

vadinami incidentu. Viršūnės laipsnis (tvarka) yra į ją patenkančių briaunų skaičius.

Eulerio kelias (Eulerio grandinė) grafe yra kelias, einantis per visus

grafiko briaunų ir, be to, tik vieną kartą.

Eulerio ciklas yra Eulerio kelias, kuris yra ciklas.

Eulerio grafikas yra grafikas, kuriame yra Eulerio ciklas.

Eulerio ciklas egzistuoja tada ir tik tada, kai grafikas yra prijungtas ir jame

nelyginio laipsnio viršūnių nėra.

Teorema. Eulerio kelias grafe egzistuoja tada ir tik tada, kai grafikas

sujungti, o nelyginio laipsnio viršūnių skaičius yra nulis arba du.

Medis yra sujungtas grafikas be ciklų, turintis pradinę viršūnę

(šaknis) ir kraštutinės viršūnės (1 laipsnis); takai nuo šaltinio viršūnės iki išorinių viršūnių vadinami šakomis.

Tinklas (arba tinklo diagrama) yra orientuotas baigtinis

sujungtas grafikas, turintis pradinę viršūnę (šaltinį) ir baigiamąją viršūnę (sink).

Kelio svoris grafike yra jo kraštinių svorių suma.

Trumpiausias kelias iš vienos viršūnės į kitą bus vadinamas keliu

minimalus svoris.

Šio kelio svoris bus vadinamas atstumu tarp

viršūnės.

Darbas yra daug laiko reikalaujantis procesas, reikalaujantis išteklių,

arba loginė priklausomybė tarp dviejų ar daugiau darbų

Įvykis yra vieno ar kelių darbų atlikimo rezultatas

Kelias yra nuoseklių darbų grandinė, jungianti

pradžios ir pabaigos viršūnes.

Kelionės trukmė nustatoma pagal trukmių sumą

jo steigiamųjų darbų.

Tinklo schemų sudarymo taisyklės.

1. Tinklo diagramoje neturėtų būti jokių aklavietės įvykių (išskyrus

galutinis), t. y. tuos, po kurių nėra jokio kūrinio.

2. Neturi būti įvykių (išskyrus pradinį), prieš kuriuos nebūtų nors

tik vienas darbas.

3. Tinklo diagramoje neturi būti ciklų.

4. Bet kuriuos du įvykius sieja ne daugiau kaip vienas darbas.

5. Tinklo schema turi būti tvarkinga.

Bet koks kelias, kurio pradžia sutampa su pradiniu įvykiu ir kurio pabaiga sutampa

nutraukimas vadinamas užbaigtu keliu. Visas kelias su maksimumu

darbo trukmė vadinama kritiniu keliu

Hierarchija yra tam tikras sistemos tipas, pagrįstas prielaida, kad sistemos elementus galima sugrupuoti į nesusijusius rinkinius

Hierarchinės analizės metodo aprašymas

Porinių palyginimo matricų konstravimas

Raskite lambda max ir išspręskite sistemą svorių vektoriaus atžvilgiu

Vietos prioritetų sintezė

Porinių palyginimų matricų nuoseklumo tikrinimas

Pasaulinių prioritetų sintezė

Visos hierarchijos nuoseklumo įvertinimas

Simpleksinis metodas yra linijinio programavimo uždavinio sprendimo būdas. Metodo esmė – rasti pradinį įmanomą planą, o vėliau planą tobulinti tol, kol bus pasiekta maksimali (arba minimali) tikslo funkcijos reikšmė duotoje išgaubtoje daugiakampėje aibėje arba nustatomas problemos neišsprendžiamumas.

Apsvarstykite šią linijinio programavimo problemą kanonine forma:

Dirbtinio pagrindo metodas

Kaip parodyta aukščiau, problemai, parašytai kanonine forma, jei tarp matricos stulpelių vektorių A Yra m vienetas ir tiesiškai nepriklausomas, galite tiesiogiai nurodyti atskaitos planą. Tačiau daugeliui linijinio programavimo problemų, parašytų kanonine forma ir turinčių atskaitos planus, tarp matricos stulpelių vektorių A ne visada prieinama m vienetinis ir tiesiškai nepriklausomas. Apsvarstykite šią problemą:

Tarkime, kad turime rasti funkcijos maksimumą

sąlygomis

kur pirmieji n elementų yra nulis. Kintamieji vadinami dirbtiniais. Vektorių stulpeliai

(28)

sudaro vadinamąjį dirbtinį pagrindą m-dimensinė vektorinė erdvė.

Kadangi išplėstinė problema turi atskaitos planą, jos sprendimą galima rasti simplekso metodu.

4 teorema. Jei optimaliame plane dirbtinių kintamųjų išplėstinės problemos (24)−(26) reikšmės , Tai yra optimalus problemos (21)−(23) planas.

Taigi, jei rastas optimalus išplėstinės problemos planas, dirbtinių kintamųjų reikšmės yra lygios nuliui, tada gaunamas optimalus pradinės problemos planas. Išsamiau pagyvenkime, kaip rasti išplėstinės problemos sprendimą.

Tikslinės funkcijos reikšmė atskaitos planui (27):

Mes tai pastebime F(X) ir susideda iš dviejų nepriklausomų dalių, iš kurių viena priklauso nuo M, o kitas – ne.

Po skaičiavimo F(X) ir jų reikšmės, taip pat pradiniai išplėstinės užduoties duomenys įvedami į simpleksinę lentelę, kaip parodyta aukščiau. Vienintelis skirtumas yra tas, kad šioje lentelėje yra viena eilutė daugiau nei įprastoje vienareikšmėje lentelėje. Tuo pačiu metu ( m+1) eilutėje yra koeficientai, kurių nėra M, ir ( m+2) eilutė − koeficientai už M.

Pereinant iš vieno atskaitos plano į kitą, vektorius, atitinkantis didžiausią neigiamą skaičių absoliučia verte ( m+2) eilutės. Dirbtinis vektorius, neįtrauktas į pagrindą, nėra prasmės jį vėl įtraukti į bazę. Pereinant prie kito atskaitos plano, gali atsitikti taip, kad nė vienas dirbtinis vektorius nebus pašalintas iš pagrindo. Paprastosios lentelės perskaičiavimas pereinant iš vieno atskaitos plano į kitą atliekamas pagal įprastas simplekso metodo taisykles (žr. aukščiau).

Iteracinis procesas vykdomas pagal m+2 eilutės, kurių ilgis yra elementų m+2 eilutės, atitinkančios kintamuosius netaps neneigiamu. Be to, jei dirbtiniai kintamieji neįtraukiami į pagrindą, rastas išplėstinės problemos planas atitinka tam tikrą pradinės problemos atskaitos planą.

m+2 eilutės, stulpeliai x 0 yra neigiamas, tada pradinė problema neturi sprendimo.

Jei ne visi dirbtiniai kintamieji neįtraukiami į pagrindą ir elementą m+2 eilutės, stulpeliai x 0 yra lygus nuliui, tada pradinio uždavinio atskaitos planas yra išsigimęs ir bazėje yra bent vienas dirbtinio pagrindo vektorius.

Jei pradinėje užduotyje yra keli vienetiniai vektoriai, jie turėtų būti įtraukti į dirbtinį pagrindą.

Jei iteracijų metu m+2 eilutėje nebėra neigiamų elementų, tada iteracijos procesas tęsiamas m+1 eilutė, kol bus surastas optimalus išplėstinės problemos planas arba atskleistas problemos neišsprendžiamumas.

Taigi, tiesinio programavimo problemos (21)–(23) sprendimo, naudojant dirbtinio pagrindo metodą, paieškos procesas apima šiuos pagrindinius etapus:

• Sudarykite išplėstinę užduotį (24)−(26).
• Raskite išplėstinės problemos atskaitos planą.
• Taikant simplekso metodą, dirbtiniai vektoriai neįtraukiami į bazę. Dėl to randamas pirminės problemos atskaitos planas arba fiksuojamas jos neišsprendžiamumas.
• Naudodami rastą atskaitos planą ZLP (21)−(23), jie arba randa optimalų pradinės problemos planą, arba nustato jos neišsprendžiamumą.

Norėdami išspręsti linijinio programavimo problemas internete, naudokite skaičiuotuvą

Matematinio modelio komponentai

Ekonominių problemų sprendimo pagrindas yra matematiniai modeliai.

Matematinis modelis problema yra matematinių ryšių, apibūdinančių problemos esmę, visuma.

• problemos kintamųjų pasirinkimas
• apribojimų sistemos sudarymas
• objektyvios funkcijos pasirinkimas

Užduočių kintamieji vadinami dydžiais X1, X2, Xn, kurie visiškai apibūdina ekonominį procesą. Paprastai jie rašomi kaip vektorius: X=(X1, X2,...,Xn).

Apribojimų sistema problemos – tai lygčių ir nelygybių rinkinys, apibūdinantis ribotus nagrinėjamos problemos išteklius.

Objektyvi funkcija užduotys vadinamos užduoties kintamųjų funkcija, kuri apibūdina užduoties kokybę ir kurios ekstremumą reikia rasti.

Paprastai linijinio programavimo uždavinį galima parašyti taip:

Šis įrašas reiškia: suraskite tikslo funkcijos (1) ekstremumą ir atitinkamus kintamuosius X=(X1, X2,...,Xn), jei šie kintamieji atitinka apribojimų (2) ir neneigiamumo sistemą. sąlygos (3).

Tinkamas sprendimas Linijinio programavimo uždavinio (planas) yra bet koks n matmenų vektorius X=(X1, X2,...,Xn), kuris tenkina apribojimų ir neneigiamumo sąlygų sistemą.

Problemos formų galimų sprendimų (planų) rinkinys galimų sprendimų regionas(ODR).

Optimalus sprendimas linijinio programavimo uždavinio (planas) yra toks leistinas problemos sprendimas (planas), kuriame tikslo funkcija pasiekia kraštutinumą.

Būklė: Norint pagaminti n rūšių produktus, sunaudojama m rūšių išteklių. Sukurkite matematinį modelį.

Žinomas:

• bi (i = 1,2,3,...,m) - kiekvieno i-to tipo išteklių atsargos;
• aij (i = 1,2,3,...,m; j=1,2,3,...,n) - kiekvienos i-osios rūšies išteklių sąnaudos tūrio vienetui pagaminti. j-oji produkto rūšis;
• cj (j = 1,2,3,...,n) - pelnas pardavus j-osios rūšies gaminio tūrio vienetą.

Būtina sudaryti gamybos planą, kuris užtikrintų maksimalų pelną esant tam tikriems išteklių (žaliavų) apribojimams.

Sprendimas:

Įveskime kintamųjų X=(X1, X2,...,Xn) vektorių, kur xj (j = 1,2,...,n) – j-ojo tipo gaminio gamybos apimtis.

I-ojo tipo išteklių sąnaudos tam tikros apimties xj produktų gamybai yra lygios aijxj, todėl išteklių naudojimo apribojimas visų rūšių gaminių gamybai turi tokią formą:
Pelnas pardavus j-osios rūšies prekę yra lygus cjxj, taigi tikslo funkcija lygi:

Atsakymas- Matematinis modelis atrodo taip:

Linijinio programavimo uždavinio kanoninė forma

Bendruoju atveju linijinio programavimo uždavinys yra parašytas taip, kad apribojimai yra ir lygtys, ir nelygybės, o kintamieji gali būti arba neneigiami, arba savavališkai kintantys.

Tuo atveju, kai visi apribojimai yra lygtys ir visi kintamieji tenkina neneigiamumo sąlygą, linijinio programavimo uždavinys vadinamas kanoninis.

Jis gali būti pavaizduotas koordinačių, vektorių ir matricų užrašais.

Kanoninio linijinio programavimo problema koordinačių žymėjime yra tokia:

Kanoninio linijinio programavimo problema matricos žymėjime yra tokia:

• A - lygčių sistemos koeficientų matrica
• X - užduočių kintamųjų matrica-stulpelis
• Ао - apribojimų sistemos dešiniųjų dalių matrica-stulpelis

Dažnai naudojamos linijinės programavimo problemos, vadinamos simetrinėmis, kurios matricoje yra tokios formos:

Bendrosios linijinio programavimo problemos sumažinimas iki kanoninės formos

Daugumoje linijinio programavimo problemų sprendimo metodų daroma prielaida, kad apribojimų sistema susideda iš lygčių ir natūralių kintamųjų neneigiamumo sąlygų. Tačiau, sudarant ekonominių problemų modelius, apribojimai daugiausia formuojami nelygybių sistemos pavidalu, todėl reikia mokėti pereiti nuo nelygybių sistemos prie lygčių sistemos.

Paimkime tiesinę nelygybę a1x1+a2x2+...+anxn≤b ir jos kairėje pusėje pridėkime tam tikrą reikšmę xn+1, kad nelygybė virstų lygybe a1x1+a2x2+...+anxn+xn+1=b . Be to, ši reikšmė xn+1 nėra neigiama.

Pažvelkime į viską naudodami pavyzdį.

Pateikite linijinio programavimo problemą kanonine forma:

Sprendimas:
Pereikime prie tikslo funkcijos maksimumo radimo problemos.
Tam pakeičiame tikslo funkcijos koeficientų ženklus.
Antrąją ir trečiąją apribojimų sistemos nelygybes paversti lygtimis, įvedame neneigiamus papildomus kintamuosius x4 x5 (matematiniame modelyje ši operacija žymima raide D).
Kintamasis x4 įvedamas į kairę antrosios nelygybės pusę su „+“ ženklu, nes nelygybė turi formą „≤“.
Kintamasis x5 įvedamas į kairę trečiosios nelygybės pusę su ženklu „-“, nes nelygybė turi formą „≥“.
Kintamieji x4 x5 įvedami į tikslo funkciją su koeficientu. lygus nuliui.
Uždavinį rašome kanonine forma: