Kumerad hulgad ja nende omadused. LPP omaduste uurimiseks on vaja anda kumera hulga range definitsioon. Varem määratleti kumer hulk kui hulka, mis koos mis tahes kahe punktiga sisaldab neid ühendavat lõiku.
Lõigu kontseptsiooni üldistus mitme punkti jaoks on nende kumer lineaarne kombinatsioon.
Punkti X nimetatakse kumer lineaarne kombinatsioon punktid, kui tingimused on täidetud
Punktide kogum on kumer, kui see koos mõne selle kahe punktiga sisaldab nende suvalist kumerat lineaarset kombinatsiooni.
Tõestatav on järgmine teoreem kumera hulktahuka esituse kohta.
Teoreem 1.1. Kumer n-polütoop on selle nurgapunktide kumer lineaarne kombinatsioon.
Teoreemist 1.1 järeldub, et kumer hulktahuka genereeritakse selle nurgapunktide ehk tippude abil: lõik kahe punktiga, kolmnurk kolmega, tetraeedr nelja punktiga jne. Samal ajal ei ole kumer hulktahuline piirkond, mis on piiramata hulk, üheselt määratud selle nurgapunktidega: ühtegi selle punkti ei saa esitada nurgapunktide kumera lineaarse kombinatsioonina.
Lineaarse programmeerimise ülesande omadused. Varem käsitleti lineaarse programmeerimise ülesande erinevaid vorme ja näidati, et iga lineaarse programmeerimise probleemi saab esitada üldise või kanoonilise probleemina.
Lineaarse programmeerimisprobleemi omaduste ja selle lahendamise meetodite põhjendamiseks on soovitatav kaaluda veel kahte kanoonilise ülesande kirjutamise tüüpi.
Maatriksi tähistus:
Siin KOOS- rea maatriks, A- süsteemimaatriks, X- muutujate maatriksveerg, V- vabaliikmete maatriks-veerg:
Vektori tähistus:
kus vektorid vastavad tundmatute koefitsientide veergudele.
Järgnev teoreem oli ülalpool öeldud, kuid seda ei tõestatud üldises vormis.
Teoreem 1.2. Lineaarse programmeerimise ülesande piirangute süsteemi kõigi võimalike lahenduste hulk on kumer.
Tõestus: Lase - LPP kaks lubatavat lahendust maatriksi kujul. Siis ja . Vaatleme kumerat lineaarset lahenduste kombinatsiooni, s.t.
ja näidata, et see on ka süsteemi (1.3) vastuvõetav lahendus. Tõepoolest
st. lahendus X rahuldab süsteemi (1.3). Aga sellest ajast peale X> 0, st. lahendus rahuldab mittenegatiivsuse tingimust.
Seega on tõestatud, et lineaarse programmeerimise ülesande kõigi lubatavate lahenduste hulk on kumer või täpsemalt kujutab see kumerat hulktahukat või kumerat hulktahukat domeeni, mida edaspidi nimetatakse ühe terminiga - lahuste hulktahukas.
Vastuse küsimusele, millises lahenduste polütoobi punktis on võimalik lineaarse programmeerimise ülesande optimaalne lahendus, annab järgmine fundamentaalne teoreem.
Teoreem 1.3. Kui lineaarprogrammeerimise ülesandel on optimaalne lahendus, siis lineaarfunktsioon võtab oma maksimaalse väärtuse lahenduspolütoobi ühes nurgapunktis. Kui lineaarfunktsioon võtab oma maksimaalse väärtuse rohkem kui ühes nurgapunktis, siis võtab see selle igas punktis, mis on nende punktide kumer lineaarne kombinatsioon.
Tõestus: Eeldame, et lahenduspolütoop on piiratud. Tähistame selle nurgapunkte tähega , ja optimaalne lahendus on läbi X*... Siis F (X *)³ F (X) kõigi punktide jaoks X lahuste hulktahukas. Kui X* Kas nurgapunkt, siis on teoreemi esimene osa tõestatud.
Teeskleme seda X* ei ole nurgapunkt, siis teoreemi 1.1 järgi X* võib kujutada lahenduspolühedri nurgapunktide kumera lineaarse kombinatsioonina, s.o.
Sest F (X) Kas on lineaarne funktsioon, saame
Selles laienduses valime väärtuste hulgast maksimaalse väärtuse. Las see vastab nurgapunktile X k(1 nael k£ R); tähistagem seda tähisega M, need. . Asendage iga väärtus avaldises (1.5) selle maksimaalse väärtusega M. Siis
Eelduse järgi X* On seega ühelt poolt optimaalne lahendus, kuid teisest küljest on see tõestatud
F (X *)£ M, seega, kus X k- nurgapunkt. Seega on nurgapunkt olemas X k milles lineaarfunktsioon võtab maksimaalse väärtuse.
Teoreemi teise osa tõestamiseks eeldame, et sihtfunktsioon võtab oma maksimaalse väärtuse rohkem kui ühes nurgapunktis, näiteks punktides , kus , siis
Lase X- nende nurgapunktide kumer lineaarne kombinatsioon, s.o.
Sel juhul arvestades, et funktsioon F (X)- lineaarne, saame
need. lineaarne funktsioon F võtab suvalises punktis maksimaalse väärtuse X mis on nurgapunktide kumer lineaarne kombinatsioon.
kommenteerida. Nõue, et lahenduste polütoop oleks teoreemis piiratud, on oluline, kuna teoreemi 1.1 kohaselt ei saa sellise domeeni igat punkti esitada selle nurgapunktide kumera lineaarse kombinatsiooniga. .
Tõestatud teoreem on põhiline, kuna see näitab lineaarse programmeerimise ülesannete lahendamise põhimõttelist viisi. Tõepoolest, selle teoreemi kohaselt on selle asemel, et uurida teostatavate lahenduste lõpmatut hulka, et leida nende hulgast soovitud optimaalne lahendus, vaid uurida ainult lõplikku arvu lahenduste hulktahuka nurgapunkte.
Järgmine teoreem on pühendatud nurgapunktide leidmise analüütilisele meetodile.
Teoreem 1.4. Lineaarse programmeerimise ülesande iga lubatav põhilahendus vastab lahenduspolütoobi nurgapunktile ja vastupidi, lahenduspolüeedri iga nurgapunkt vastab lubatavale põhilahendusele.
Tõestus: Olgu LPP piirangute süsteemi (1.4) lubatav põhilahendus, milles esimene T komponendiks on peamised muutujad ja ülejäänud n - t komponent - põhilahenduses nulliga võrdsed väiksemad muutujad (kui see nii ei ole, saab vastavad muutujad ümber nummerdada). Näitame seda X
Oletame vastupidist, s.t. mida X ei ole nurgapunkt. Siis punkt X saab esitada segmendi sisepunktina, mis ühendab kahte erinevat segmenti, mis ei lange kokku X, punktid
teisisõnu kumer lineaarne punktide kombinatsioon lahenduste hulktahukas, s.o.
kus (oletame, et muidu punkt X langeb kokku punktiga X 1 või X 2).
Kirjutame vektori võrdsuse (1.6) koordinaatide kujul:
Sest kõik muutujad ja koefitsiendid on mittenegatiivsed, siis viimasest p-t võrdsustest järeldub, et s.t. otsustes X 1 , X 2 ja X võrrandisüsteemi (1.4) väärtused n - t komponendid on sel juhul võrdsed nulliga. Neid komponente võib pidada väiksemate muutujate väärtusteks. Kuid väiksemate muutujate väärtused määravad üheselt peamiste muutujate väärtused, seetõttu
Nii et kõik P komponent lahustes X 1 , X 2 ja X langevad kokku ja seega ka punktid X 1 ja X 2 liidetakse, mis on eeldusega vastuolus. Seega X Kas lahenduse hulktahuka nurgapunkt.
Tõestame vastupidist väidet. Laskma olla lahenduste polütoobi nurgapunkt ja selle esimene T koordinaadid on positiivsed. Näitame seda X- vastuvõetav põhilahendus. ei ole nurgapunkt, mis on tingimusega vastuolus. Seetõttu on meie oletus vale, s.t. vektorid on lineaarselt sõltumatud ja X Kas ülesande (1.4) lubatav põhilahendus.
Teoreemidest 1.3 ja 1.4 tuleneb otseselt oluline tagajärg: kui lineaarse programmeerimise ülesandel on optimaalne lahendus, siis langeb see kokku vähemalt ühe lubatava põhilahendusega.
Niisiis, lineaarse programmeerimise probleemi lineaarfunktsiooni optimumi tuleks otsida selle lõpliku arvu vastuvõetavate põhilahenduste hulgast.
Teostatakse lineaarmudelite optimeerimine MS Excelis simpleks meetod- lineaarse programmeerimise ülesande tugilahenduste eesmärgipärane loetlemine. Simpleksmeetodi algoritm taandatakse kumera hulktahuka konstrueerimisele mitmemõõtmelises ruumis ja seejärel itereerimisele üle selle tippude, et leida äärmuslik väärtus objektiivne funktsioon.Tõhusad abinõud lineaarne programmeerimine on keerukamate optimeerimisprobleemide jaoks nii täisarvude kui ka mittelineaarse programmeerimise aluseks. Need meetodid nõuavad aga pikemat arvutusaega.
Järgnevates loengutes analüüsitakse üksikasjalikult näiteid tüüpiliste optimeerimisprobleemide lahendamisest ja juhtimisotsuste tegemisest MS Exceli lisandmooduli "Otsi lahendust" abil. Selle tööriistaga kõige paremini täidetavatel ülesannetel on kolm peamist omadust.
- on üksainus eesmärk, mis on funktsionaalselt seotud süsteemi teiste parameetritega, mida on vaja optimeerida (leida selle maksimum, miinimum või teatud arvväärtus);
- on piiranguid, mis väljenduvad tavaliselt ebavõrdsusena (näiteks ei tohi kasutatava tooraine maht ületada laos olevat toorainet või masina tööaeg ööpäevas ei tohi ületada 24 tundi, millest on maha arvatud teenus);
- on sisendmuutujate väärtuste komplekt, mis mõjutavad optimeeritud väärtusi ja piiranguid.
Ülesande parameetrid on piiratud järgmiste piirväärtustega:
- tundmatute arv - 200;
- tundmatute valemipiirangute arv - 100;
- tundmatute piiravate tingimuste arv on 400.
Optimaalsete lahenduste leidmise algoritm koosneb mitmest etapist:
- ettevalmistustööd;
- lahenduse silumine;
- lahenduse analüüs.
Majandusliku ja matemaatilise modelleerimise ülesannete lahendamisel MS Exceli abil tehtavate vajalike ettevalmistustööde järjekord on näidatud joonise 1.6 plokkskeemil.
Riis. 1.6.
Ettevalmistava tööplaani viiest punktist vormistatakse vaid viies punkt. Ülejäänud tööd nõuavad loovust – ja neid saavad erinevad inimesed teha erineval viisil. Selgitame lühidalt planeeringu punktide sõnastuse olemust.
Ülesande püstitamisel on teada sihtkoefitsiendid ja normaliseeritud koefitsiendid. Eelmises näites olid sihtfunktsiooni moodustavateks koefitsientideks tüübi normaliseeritud kasumi väärtused riiuli kohta ( 
) ja üks riiul tüüpi ( 
). Normaliseeritud koefitsiendid olid iga tüübi materjalikulu ja masina ajakulu riiuli kohta. Maatriks nägi välja selline:
Lisaks on ressursside väärtused alati teada. Eelmises näites oli see iganädalane laudade varu ja masinaaja kasutamise võimalus: 
, 
... Sageli tuleb ülesannetes muutujate väärtusi piirata. Seetõttu on vaja kindlaks määrata nende muutuste ala alumine ja ülemine piir.
Seega peame optimeerimisprogrammi "Otsi lahendust" dialoogiboksis määrama järgmise sihtalgoritmi:
Eesmärk on võrdne muutujate soovitud väärtuste vektori korrutisega objektiivsete koefitsientide vektoriga
Muutujate otsitavate väärtuste vektori normaliseeritud koefitsiendid ei tohiks ületada antud ressursside vektori väärtust
Muutuja väärtused peavad jääma süsteemi algelementide arvu määratud piiridesse
Süsteemi algelementide arv
Määratud tüüpi ressursside arv
Lahenduse silumine on vajalik juhul, kui programm väljastab teate negatiivsete tulemuste kohta (joonis 1.7):
Riis. 1.7.
- kui teostatavat lahendust ei leita, siis korrigeerida lähteandmete mudelit;
- kui kätte ei saa optimaalne lahendus, seejärel kehtestage täiendavad piirangud.
Programmi probleemid optimaalne lahendus ainult tegeliku probleemi modelleerimiseks, mitte probleemi enda lahenduseks. Mudeli koostamisel tehti erinevaid lihtsustavaid oletusi tegelikust olukorrast. See võimaldas vormistada protsessi, peegeldades ligilähedaselt tegelikke kvantitatiivseid seoseid süsteemi parameetrite ja eesmärgi vahel. Ja kui tegelikud parameetrid erinevad mudelis sisalduvatest, siis kuidas otsus muutub? Selle väljaselgitamiseks analüüsitakse enne juhtimisotsuse tegemist näidisotsust.
Analüüs optimaalne lahendus, mis on programmi sisse ehitatud, on majandusprotsesside matemaatilise modelleerimise viimane etapp. See võimaldab põhjalikumalt kontrollida mudeli sobivust protsessiga, samuti optimaalse lahenduse usaldusväärsust. See on andmepõhine optimaalne lahendus ja aruanded, mis väljastatakse "Otsi lahendust". Kuid see ei välista ega asenda plaani traditsioonilist analüüsi majanduslikust seisukohast enne juhtimisotsuse tegemist.
Majandusanalüüsil on järgmised eesmärgid:
- mudeli parameetri muutmisel võimalike tagajärgede kindlaksmääramine süsteemis tervikuna ja selle elementides;
- optimaalse plaani stabiilsuse hindamine probleemi üksikute parameetrite muutustele: kui see ei ole enamiku parameetrite muutustele vastupidav, väheneb selle rakendamise ja arvutatud optimumi saavutamise garantii;
- variantarvutuste läbiviimine ja planeeringu uute variantide saamine ilma probleemi algsetest alustest korrigeerimise teel uuesti lahendamata.
Võimalikud analüüsimeetodid on näidatud diagrammil joonisel 1.8.
Pärast optimaalse lahenduse saamist analüüsitakse seda vastavalt saadud aruannetele. Stabiilsuse analüüs- mudeli üksikute parameetrite muutuste mõju uurimine optimaalse lahenduse näitajatele. Piirianalüüs- optimaalse plaani vastuvõetavate muudatuste analüüs, milles plaan jääb optimaalseks.
Arvestades vastutust majanduslikuks muutmise eest juhtimisotsus, peab juht veenduma, et saadud optimaalne plaan on ainuõige. Selleks on vaja mudeli alusel saada vastused järgmistele küsimustele:
- "mis siis kui…"
- "Mida on vaja, et..."
Esimesele küsimusele vastamiseks kutsutakse analüüs variantide analüüs; analüüs, et vastata teisele küsimusele kohandatud lahendused.
Variantanalüüs on järgmist tüüpi:
- Parameetriline- analüüs, mis seisneb teatud parameetri erinevate väärtuste probleemi lahendamises.
- Struktuurianalüüs- kui optimeerimisprobleemile otsitakse lahendust erineva piirangute struktuuriga.
- Mitme kriteeriumi analüüs- See on erinevate sihtfunktsioonide probleemi lahendus.
- Analüüs tingimuslike sisendandmetega- kui probleemi lahendamisel kasutatavad lähteandmed sõltuvad lisatingimuste järgimisest.
Pärast analüüsi tuleks tulemused esitada graafiliselt ning koostada aruanne koos soovitustega otsuse tegemiseks, arvestades konkreetset majanduslikku olukorda.
Definitsioon... Kõiki piirangute süsteemi lahendusi nimetatakse LPP lubatavaks lahenduseks.
Definitsioon... Teostatavat lahendust, mille puhul eesmärkfunktsioon saavutab maksimaalse või minimaalse väärtuse, nimetatakse optimaalseks lahenduseks.
Nende definitsioonide abil saab LP probleemi sõnastada järgmiselt: piirangute süsteemi lahenduseks oleva kumera piirkonna punktide hulgast vali üks, mille koordinaadid minimeerivad (maksimeerivad) lineaarfunktsiooni. F = Koos 1 x + Koos 2 y.
Pange tähele, et muutujad x, y LPP-s võtavad reeglina mittenegatiivsed väärtused ( x≥ 0, y≥ 0), seega asub piirkond koordinaattasandi I kvartalis.
Vaatleme lineaarset funktsiooni F = Koos 1 x + Koos 2 y ja fikseerige mõned selle väärtused F... Olgu näiteks F= 0, st. Koos 1 x + Koos 2 y= 0. Selle võrrandi graafik on sirge, mis läbib koordinaatide alguspunkti (0; 0) (joonis).
Joonistamine
Selle fikseeritud väärtuse muutmisel F = d, sirge Koos 1 x+ Koos 2 y = d liigub paralleelselt ja "jälgib" kogu tasapinna. Lase D- hulknurk - piirangute süsteemi lahendamise ala. Kui see muutub d otse Koos 1 x + Koos 2 y = d, teatud väärtuses d = d 1 jõuab hulknurgani D, nimetame seda punkti A"Sisenemispunkt" ja seejärel hulknurgast möödudes teatud väärtuses d = d 2 saame sellega viimase ühise punkti V, helistame V"Väljumise punkt".
Ilmselgelt selle väikseima ja suurima väärtuse eesmärkfunktsioon F=Koos 1 x + Koos 2 y jõuab sisenemispunktidesse A ja "välju" V.
Arvestades, et sihtfunktsioon võtab piirkonna tippude teostatavate lahenduste hulga optimaalse väärtuse D, saab LPP lahendamiseks välja pakkuda järgmise kava:
- rajada piirangute süsteemi lahenduste ala;
- looge sihtfunktsioonile vastav sirgjoon ja leidke selle sirge paralleelse ülekandega "sisenemis-" või "väljapääsu" punkt (olenevalt eesmärgifunktsiooni minimeerimise või maksimeerimise nõudest);
- määrata selle punkti koordinaadid, arvutada neis sihtfunktsiooni väärtus.
LPP graafilisel lahendamisel on kaks võimalikku juhtumit, mis nõuavad erilist arutelu.
Juhtum 1
Joonis 6
Otse liikumisel Koos 1 x + Koos 2 y= d"Sisenemine" või "väljapääs" (nagu pildil) toimub polügooni küljel. See juhtub siis, kui hulknurga küljed on sirgjoonega paralleelsed. Koos 1 X+ Koos 2 juures = d .
Sel juhul on "väljapääsu" ("sisenemise") punkte lugematu arv, nimelt lõigu mis tahes punkti AB... See tähendab, et sihtfunktsioon võtab maksimaalse (minimaalse) väärtuse mitte ühes punktis, vaid kõigis punktides, mis asuvad hulknurga vastaval küljel. D.
Juhtum 2
Mõelge juhtumile, kui lubatud väärtuste vahemik on piiramatu.
Piiramata ala puhul saab sihtfunktsiooni määrata nii, et vastaval sirgel ei oleks “väljumise” (või “sisenemise”) punkti. Siis ei saavutata kunagi funktsiooni maksimaalset väärtust (miinimum) - nad ütlevad, et funktsioon pole piiratud. 
Joonistamine
On vaja leida sihtfunktsiooni maksimaalne väärtus F = 4x + 6y→ max, piirangute süsteemiga
Konstrueerigem teostatavate lahenduste piirkond, s.o. lahendame graafiliselt võrratuste süsteemi. Selleks konstrueerime iga sirge ja defineerime võrratustega antud pooltasandid.
x + y = 18
|
x |
12 |
9 |
|
y |
6 |
9 |
0,5x + y = 12
|
x |
12 |
18 |
|
y |
6 |
3 |
x= 12 - teljega paralleelne OY ;
y= 9 - teljega paralleelne HÄRG ;
x= 0 - telg OY ;
y = 0 - telg HÄRG;
x OY;
y≥ 0 – pooltasapind telje kohal HÄRG;
y≤ 9 – pooltasapind allpool y = 9;
x ≤ 12 - pooltasapind vasakule x = 12;
0,5x + yx + y = 12;
x + y x + y = 18.
Joonistamine
Kõigi nende pooltasandite ristumiskoht on ilmselgelt viisnurk OAVSD, mille tipud on punktides O(0; 0), A(0; 9), V(6; 9), KOOS(12; 6), D(12; 0). See viisnurk moodustab probleemi võimalike lahenduste piirkonna.
F = 4x + 6y→ max.
|
x |
3 |
0 |
|
y |
–2 |
0 |
F = 0: 4x + 6y x+ 6y KOOS(12; 6). See on temas F = 4x + 6y
Seega, selleks x = 12, y= 6 funktsiooni F F= 4 ∙ 12 + 6 ∙ 6 = 84, võrdne 84. Koordinaatidega punkt (12; 6) rahuldab kõik piirangute süsteemi ebavõrdsused ja sihtfunktsiooni väärtus selles on optimaalne F* = 84 (optimaalne väärtus on tähistatud tähega "*").
Probleem on lahendatud. Seega on vaja toota 12 I tüüpi toodet ja 6 II tüüpi toodet, samas kui kasum on 84 tuhat rubla.
Graafilist meetodit kasutatakse probleemide lahendamiseks, millel oli piirangute süsteemis ainult kaks muutujat. Seda meetodit saab rakendada ka kolme muutujaga võrratussüsteemide puhul. Geomeetriliselt on olukord erinev, sirgjoonte rolli täidavad ruumilises ruumis olevad tasapinnad ja kolme muutuja võrratuse lahenduseks on tasandi ühel küljel paiknev poolruum. Piirkondade rolli hakkavad mängima hulktahukad, mis on poolruumide ristumiskohad.
Näide nr 2. Kaevanduses tekib kaks õmblust. Esimese kihi lõike väljund on a1%; teisel - a2%. Esimese kihi pikkseina maksimaalne toodang on B1 tuhat tonni aastas, teise kihi puhul - B2 tuhat tonni aastas. Töötehnoloogia järgi ei saa teisest kihist toodang ületada esimese kihi toodangut. Kaevanduse toodang kaevanduses ei tohiks ületada C1 tuhat tonni aastas. Kahe kihi kogukoormus aastas peaks olema vähemalt C2 tuhat tonni aastas. Looge matemaatiline mudel ja koostage esimese ja teise kihi lubatud koormusväärtuste komplekt aastas.
Näide nr 3. Poes on müügil 2 sorti karastusjooke: Cola ja limonaad. Ühe koolapurgi tulu on 5 senti, limonaadipurgilt aga 7 senti. Keskmiselt ei müü pood mõlemat jooki rohkem kui 500 purki päevas. Vaatamata sellele, et koolat toodab tuntud kaubamärk, eelistavad ostjad limonaadi, sest see on palju odavam. Arvatakse, et koola ja limonaadi müük peaks olema vähemalt 2:1 ning poes müüakse teadaolevalt vähemalt 100 purki koolat päevas. Mitu purki iga jooki peaks poel päeva alguses olema, et tulu maksimeerida?
Näide nr 4. Lahendage lineaarse programmeerimise ülesanne ligikaudu graafiliselt koos järgneva sihtfunktsiooni väärtuse täpse väärtuse ja max (min) arvutamisega.
Näide nr 5. Reisibüroo nõuab mitte rohkem kui kolmetonniseid ja mitte rohkem kui viietonniseid busse. Esimese margi busside müügihind on 20 000 USD, teise margi 40 000 USD. Reisibüroo ei saa busside ostmiseks eraldada rohkem kui 1 dollar. Mitu iga margi bussi tuleks eraldi osta, et nende kogu (kogu) kandevõime oleks maksimaalne. Lahendage probleem graafiliselt.
Näide nr 6. Graafilise meetodi abil leia tabelis toodud ülesande jaoks optimaalne tootmisplaan.
Näide nr 7. Lahendage lineaarse programmeerimise ülesanne graafilise meetodiga, allutades ülesande piirangute süsteemi Jordani-Gaussi teisendustele. Probleemipiirangute süsteem on järgmine:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Juhised... Jordani-Gaussi teisendusi saab teha selle teenuse või SLAE-de uurimise kaudu.
Näide nr 8. Ettevõte toodab kahte tüüpi A ja B tooteid, mille valmistamiseks kasutatakse kolme tüüpi toorainet. Toote A ühiku valmistamiseks on vaja kulutada igat tüüpi toorainet vastavalt a1, a2, a3 kg ja toote ühiku B jaoks - b1, b2, b3 kg. Tootmine on varustatud igat tüüpi toorainega vastavalt Р1, Р2, Р3 kg. Toote A ühiku maksumus on C1 rubla ja toote B ühiku maksumus on C2 rubla. Toodete A ja B tootmiseks on vaja koostada plaan, mis tagab valmistoote maksimaalse maksumuse.
Näide nr 2. On vaja leida sihtfunktsiooni maksimaalne väärtus F = 4x + 6y→ max, piirangute süsteemiga:
Konstrueerigem teostatavate lahenduste piirkond, s.o. lahendame graafiliselt võrratuste süsteemi. Selleks valige piirangute arv, mis on võrdne 4-ga (joonis 1). 
1. pilt
Seejärel täidame muutujate ja piirangute endi koefitsiendid (joonis 2). 
2. pilt 
Joonis 3
x= 12 - teljega paralleelne OY;
y= 9 - teljega paralleelne HÄRG;
x> = 0 - telg OY
y= 0 - telg HÄRG;
x≥ 0 – pooltasapind teljest paremal OY;
y≥0 – pooltasapind telje kohal HÄRG;
y≤ 9 – pooltasapind allpool y = 9;
x≤ 12 - pooltasapind vasakule x = 12;
0,5x + y≤ 12 - pooltasand allpool sirgjoont 0,5 x + y = 12;
x + y≤ 18 - pooltasand allpool sirgjoont x + y = 18.
Kõigi nende pooltasandite ristumiskoht on viisnurk ABCDE, mille tipud on punktides A(0; 0), B(0;9), C(6; 9), D(12;6), E(12; 0). See viisnurk moodustab probleemi võimalike lahenduste piirkonna. 
Mõelge probleemi objektiivsele funktsioonile F = 4x + 6y→ max.
|
x |
3 |
0 |
|
y |
–2 |
0 |
Ehitame funktsiooni väärtusele vastava sirge F = 0: 4x + 6y= 0. Liigutame seda sirget paralleelselt. Kogu liinide perekonnast on 4 x + 6y= const viimane tipp, mida läbib sirge hulknurga piirist kaugemale minnes, on tipp KOOS(12; 6). See on temas F = 4x + 6y saavutab maksimaalse väärtuse. 
Seega, selleks x = 12, y= 6 funktsiooni F saavutab maksimaalse väärtuse F= 4 ∙ 12 + 6 ∙ 6 = 84, võrdne 84. Koordinaatidega punkt (12; 6) rahuldab kõik piirangute süsteemi ebavõrdsused ja sihtfunktsiooni väärtus selles on optimaalne F* = 84.
Test distsipliinil "Operatsiooniuuringud"
(õiged vastused on esimesed)
1. Ilmus termin "operatsiooniuuringud" ...
teise maailmasõja ajal
XX sajandi 50ndatel
XX sajandi 60ndatel
XX sajandi 70ndatel
XX sajandi 90ndatel
XXI sajandi alguses
2. Operatsioonide uurimise vahendid (valige sobivaim variant) ...
teaduslike meetodite kogum organisatsioonisüsteemide tõhusa juhtimise probleemide lahendamiseks
teatud toimingute rakendamiseks võetud meetmete kogum
meetodite kogum väljamõeldud plaani elluviimiseks
teaduslikud meetodid ressursside jaotamiseks tootmise korraldamisel
3. Korraldage toimingud, mida mis tahes operatiivuuringud tavaliselt läbivad.
probleemi sõnastus
vaadeldava objekti (protsessi) tähendusliku (verbaalse) mudeli konstrueerimine
matemaatilise mudeli ehitamine
konstrueeritud matemaatilise mudeli alusel sõnastatud ülesannete lahendamine
saadud tulemuste kontrollimine uuritava süsteemi olemuse adekvaatsuse kohta
saadud lahenduse rakendamine praktikas
4. Operatsiooniuuringutes mõistetakse operatsiooni ...
mis tahes sündmus (tegevuste süsteem), mida ühendab üks kontseptsioon ja mille eesmärk on saavutada eesmärk
mis tahes kontrollimatu sündmus
tehniliste meetmete kogum tarbekaupade tootmise tagamiseks
5. Lahendust nimetatakse optimaalseks, ...
kui see on ühel või teisel põhjusel eelistatav
kui see on ratsionaalne
kui see on ametivõimudega kokku lepitud
kui üldkoosolek on heaks kiitnud
6. Matemaatiline programmeerimine ...
tegeleb äärmuslike probleemide uurimisega ja nende lahendamise meetodite väljatöötamisega
on arvutiprogrammide loomise protsess matemaatikute juhendamisel
lahendab matemaatilisi ülesandeid arvutis
7. Lineaarse programmeerimise ülesanne on ...
lineaarfunktsiooni suurima (väikseima) väärtuse leidmine lineaarsete piirangute olemasolul
ülesande lahendamiseks mõeldud lineaarse programmi loomine valitud programmeerimiskeeles
lineaarse algoritmi kirjeldus antud ülesande lahendamiseks
8. Ruutprogrammeerimise ülesandes ...
sihtfunktsioon on ruut
lubatavate lahenduste pindala on ruut
piirangud sisaldavad ruutfunktsioone
9. Täisarvulise programmeerimise ülesannetes ...
tundmatud võivad võtta ainult täisarvulisi väärtusi
sihtfunktsioon peab tingimata võtma täisarvu ja tundmatud võivad olla mis tahes
sihtfunktsioon on arvkonstant
10. Parameetrilise programmeerimise ülesannetes ...
eesmärgifunktsioon ja/või piirangusüsteem sisaldab parameetrit (parameetreid)
lubatavate lahenduste pindala on rööpkülik või rööptahukas
muutujate arv saab olla ainult paaris
11. Dünaamilise programmeerimise probleemide korral ...
lahenduse leidmise protsess on mitmeetapiline
dünamiidi tootmist on vaja ratsionaliseerida
soovite optimeerida kõlarite kasutamist
12. Esitatakse järgmine lineaarse programmeerimise probleem:
F(X 1, X 2) = 5X 1 + 6X 2→ max
0.2X 1 + 0.3X 2 ≤ 1.8,
0.2X 1 + 0.1X 2 ≤ 1.2,
0.3X 1 + 0.3X 2 ≤ 2.4,
X 1 ≥ 0, X 2 ≥ 0.
Valige selle ülesandega samaväärne ülesanne.
F(X 1, X 2)= 5X 1 + 6X 2 → max,
2X 1 + 3X 2 ≤ 18,
2X 1 + X 2 ≤ 12,
X 1 + X 2 ≤ 8,
X 1 ≥ 0,
X 2 ≥ 0.
F(X 1, X 2)= 6X 1 + 5X 2 → min,
2X 1 + 3X 2 ≤ 18,
2X 1 + X 2 ≤ 12,
X 1 + X 2 ≤ 8,
X 1 ≥ 0,
X 2 ≥ 0.
F(X 1, X 2)= 50X 1 + 60X 2 → max,
2X 1 + 3X 2 ≤ 18,
2X 1 + X 2 ≤ 12,
X 1 + X 2 ≤ 8,
X 1 ≥ 0,
X 2 ≥ 0.
F(X 1, X 2)= 5X 12 + 6X 22 → max,
2X 1 + 3X 2 ≤ 18,
2X 1 + X 2 ≤ 12,
3X 1 + X 2 ≤ 2.4,
X 1 ≥ 0,
X 2 ≥ 0.
13. Lineaarse programmeerimisülesande sihtfunktsiooniks võib olla funktsioon:
F=12x1+20x2-3 0x3→min
F= →min
F=
→max
F=→max.
14. Lineaarse programmeerimise ülesande piirangute süsteem võib olla süsteem:
15. Simpleksmeetod on järgmine:
analüütiline meetod lineaarse programmeerimise põhiprobleemi lahendamiseks
meetod lineaarse programmeerimisprobleemi teostatavate lahenduste piirkonna leidmiseks;
graafiline meetod lineaarse programmeerimise põhiprobleemi lahendamiseks;
meetod üldise lineaarse programmeerimise probleemi taandamiseks kanooniliseks vormiks.
16. Lineaarse programmeerimise ülesanne on:
lineaarfunktsiooni suurima või väikseima väärtuse leidmine lineaarsete piirangute olemasolul
lineaarse algoritmi väljatöötamine ja selle realiseerimine arvutis
lineaarvõrrandisüsteemi koostamine ja lahendamine
etteantud piirangute süsteemiga kirjeldatud protsessi arengu lineaarse trajektoori otsimine.
17. Lineaarse programmeerimise ülesande teostatavate lahenduste valdkond ei saa näeb välja selline:
18. Lineaarse programmeerimisülesande sihtfunktsiooniks võib olla funktsioon:
F=12x1+20x2-3 0x3→min
F= →min
F=→max
F=→max.
19. Lineaarse programmeerimise ülesande piirangute süsteem võib olla süsteem:
20. Lineaarse programmeerimise probleemi võimalike lahenduste piirkond on järgmine:
F(X 1, X 2)= 3X 1 + 5X 2 võrdub...
21. Lineaarse programmeerimise ülesande teostatavate lahenduste piirkond on kujul:
Siis funktsiooni maksimaalne väärtus F(X 1, X 2)= 5X 1 + 3X 2 võrdub...
22. Lineaarse programmeerimise ülesande teostatavate lahenduste piirkond on kujul:
Siis funktsiooni maksimaalne väärtus F(X 1, X 2)= 2X 1 - 2X 2 võrdub...
23. Lineaarse programmeerimise ülesande teostatavate lahenduste piirkond on kujul:
F(X 1, X 2)= 2X 1 - 2X 2 võrdub...
24. Mittelineaarse programmeerimise probleemi võimalike lahenduste piirkond on järgmine:
Siis funktsiooni maksimaalne väärtus F(X 1, X 2)= X 2 – X 12 võrdub...
25. Sihtfunktsiooni maksimaalne väärtus F(X 1, X 2)= 5X 1 + 2X 2 piirangutega
X 1 + X 2 ≤ 6,
X 1 ≤ 4,
X 1 ≥ 0, X 2 ≥ 0, võrdub ...
26. Väikeettevõte toodab kahte tüüpi tooteid. Ühe A-tüüpi toote valmistamiseks kulub 2 kg toorainet, ühe B-tüüpi toote valmistamiseks - 1 kg. Kokku on toorainet 60 kg. Nõutav on koostada tootmisplaan, mis tagab suurima tulu laekumise, kui ühe A-tüüpi toote müügimaksumus on 3 ühikut, B-tüüpi 1 ühikut. See tähendab, et A-tüüpi tooteid ei tohi teha rohkem kui 25 ja B-tüüpi mitte rohkem kui 30.
See ülesanne on...
lineaarse programmeerimise probleem
dünaamilise programmeerimismeetodi abil lahendatud probleem
võrgu planeerimise ülesanne.
27. Väikeettevõte toodab kahte tüüpi tooteid. Ühe A-tüüpi toote valmistamiseks kulub 2 kg toorainet, ühe B-tüüpi toote valmistamiseks - 1 kg. Kokku on toorainet 60 kg. Nõutav on koostada tootmisplaan, mis tagab suurima tulu laekumise, kui ühe A-tüüpi toote müügimaksumus on 3 ühikut, B-tüüpi 1 ühikut. See tähendab, et A-tüüpi tooteid ei tohi teha rohkem kui 25 ja B-tüüpi mitte rohkem kui 30.
Selle ülesande eesmärk on funktsioon ...
F(x1, x2)=3x1+x2→max
F(x1, x2)=25x1+30x2→max
F(x1, x2)=2x1+x2→max
F(x1, x2)=60 -2x1 -x2→min
28. Väikeettevõte toodab kahte tüüpi tooteid. Ühe A-tüüpi toote valmistamiseks kulub 2 kg toorainet, ühe B-tüüpi toote valmistamiseks - 1 kg. Kokku on toorainet 60 kg. Nõutav on koostada tootmisplaan, mis tagab suurima tulu laekumise, kui ühe A-tüüpi toote müügimaksumus on 3 ühikut, B-tüüpi 1 ühikut. See tähendab, et A-tüüpi tooteid ei tohi teha rohkem kui 25 ja B-tüüpi - mitte rohkem kui 30
Selle ülesande kehtiv plaan on plaan:
X =(20, 20)
X =(25, 15)
X =(20, 25)
X =(30, 10)
29. Kahes punktis A1 ja A2 on vastavalt 60 ja 160 ühikut kaupa. Kõik kaubad tuleb transportida punktidesse B1, B2, B3 vastavalt 80, 70 ja 70 ühikut. Tariifimaatriks on järgmine:. Planeerige transport nii, et kulud oleksid minimaalsed.
See ülesanne on...
transpordi ülesanne
mittelineaarse programmeerimise probleem
reisimüüja probleem
ülesande ülesanne
30. Kahes punktis A1 ja A2 on vastavalt 60 ja 160 ühikut kaupa. Kõik kaubad tuleb transportida punktidesse B1, B2, B3 vastavalt 80, 70 ja 70 ühikut. Tariifimaatriks on järgmine:. Planeerige transport nii, et kulud oleksid minimaalsed
Selle ülesande põhiplaan on plaan:
;
31. Kahes punktis A1 ja A2 on vastavalt 60 ja 160 kaubaühikut. Kõik kaubad tuleb transportida punktidesse B1, B2, B3 vastavalt 80, 70 ja 70 ühikut. Tariifimaatriks on järgmine:. Planeerige transport nii, et kulud oleksid minimaalsed.
Selle ülesande eesmärk on funktsioon:
F=4x11+6x12+ 8x13+5x21+8x22+7x23→min
F= →min
F=60x1+160x2 + 80x3+70x4+705 →max
F=60x1+160x2– 80x3- 70x4– 705 →min
32. Kahes punktis A1 ja A2 on vastavalt 60 ja 160 ühikut kaupa. Kõik kaubad tuleb transportida punktidesse B1, B2, B3 vastavalt 80, 70 ja 70 ühikut. Tariifimaatriks on järgmine:. Planeerige transport nii, et kulud oleksid minimaalsed.
Selle ülesande optimaalne plaan on plaan:
;
.
;
;
33. Transpordiprobleem
suletakse, kui...
34. Transpordiprobleem
on…
avatud
suletud
lahustumatu
35. Transpordiprobleem
on…
suletud
avatud
lahustumatu
36. Lahendada järgmine transpordiülesanne
peate sisestama ...
fiktiivne tarbija
fiktiivne tarnija;
kehtiv tariif
37. Lahendada järgmine transpordiülesanne
peate sisestama ...
fiktiivne tarnija;
fiktiivne tarbija
kehtiv tariif
efektiivne intressimäär.
38. Nende transpordiülesannete hulgas
suletud on...
39. Transpordiprobleemi esialgse lähteplaani saab koostada ...
kõigi ülaltoodud meetoditega
Loodenurga meetod
miinimumtariifi meetodil
kahekordse eelistuse meetod
Vogeli lähendamise meetodil
40. Kui lineaarse programmeerimise ülesande sihtfunktsioon on seatud maksimumile, siis ... duaalülesande sihtfunktsioon on seatud miinimumile
duaalülesandes pole objektiivset funktsiooni
topeltprobleemil pole lahendusi
duaalprobleemil on lõputult palju lahendusi
41. Lineaarse programmeerimise ülesanne on antud:
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 ≤ 14,
X 1 + X 2 ≤ 8,
X 1 ≥ 0, X 2 ≥ 0.
Selle ülesande jaoks on järgmised kaks...
F*(y1, y2) = 14y1 + 8y2 → min,
3a 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
F*(y1, y2) = 2y1 + 7y2 → min,
2y1 + 3y2 ³ 14,
y 1 + y2 ³ 8,
y 1 0 £, y2 0 £.
F*(y1, y2) = 2y1 + 7y2 → min,
3 y 1 + y2 ³ 7,
y 1 0 £, y2 0 £.
F*(y1, y2) = 14y1 + 8y2 → min,
y 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
42. Kui ühel kahest probleemist on optimaalne plaan, siis ...
ja teisel on optimaalne plaan
teisel puudub optimaalne plaan
teisel pole teostatavaid lahendusi
43. Kui ühel kahest probleemist on optimaalne plaan, siis ...
ja teisel on optimaalne plaan ja nende optimaalsete plaanide sihtfunktsioonide väärtused on üksteisega võrdsed
ja teisel on optimaalne plaan, kuid nende optimaalsete plaanide sihtfunktsioonide väärtused ei ole üksteisega võrdsed
teisel probleemil ei pruugi olla optimaalset plaani, kuid sellel on teostatavad lahendused
44. Kui ühe duaalülesannete paari objektiivne funktsioon ei ole piiratud (maksimaalse ülesande jaoks - ülalt, minimaalse ülesande jaoks - alt), siis
teisel ülesandel pole kehtivaid plaane
teisel ülesandel on teostatavad plaanid, kuid sellel pole optimaalset plaani
ka teise ülesande eesmärkfunktsioon ei ole piiratud
45. Mõne mittelineaarse programmeerimise ülesande lahendamisel kasutatakse seda ...
Lagrange'i kordaja meetod
Gaussi meetod
Vogeli lähendamise meetod
Gomori meetod
46. Mittelineaarse programmeerimise probleem on seatud
F(X 1, X 2)= X 12 + X 22 → max,
X 1 + X 2 =6,
X 1 ≥ 0, X 2 ≥ 0.
F(X 1, X 2) …
ei ole kättesaadav (+ ¥)
47. Püstitatakse mittelineaarse programmeerimise probleem
F(X 1, X 2)= X 12 + X 22 → msisse,
X 1 + X 2 =6,
X 1 ≥ 0, X 2 ≥ 0.
F(X 1, X 2) …
48. Püstitatakse mittelineaarse programmeerimise probleem
F(X 1, X 2)= X 12 + X 22 → max,
X 1 + X 2 =6,
X 1, X 2 - mis tahes.
Sihtfunktsiooni suurim väärtus F(X 1, X 2) …
ei ole kättesaadav (+ ¥)
49. Püstitatakse mittelineaarse programmeerimise probleem
F(X 1, X 2)= X 12 + X 22 → msisse,
X 1 + X 2 =6,
X 1, X 2 - mis tahes.
Sihtfunktsiooni väikseim väärtus F(X 1, X 2) …
ei ole kättesaadav (- ¥)
50. Mittelineaarse programmeerimise probleemi võimalike lahenduste piirkond on järgmine:
Siis funktsiooni maksimaalne väärtus F(X 1, X 2)= X 12 +X 22 võrdub...
51. Mittelineaarse programmeerimise probleemi võimalike lahenduste piirkond on järgmine:
Siis funktsiooni minimaalne väärtus F(X 1, X 2)= X 12 +X 22 võrdub...
52. Transpordiprobleemi lahendamiseks saab rakendada ...
potentsiaalne meetod
Lagrange'i kordaja meetod
Gaussi meetod
desorientatsiooni meetod
53. Üldise lineaarse programmeerimise ülesande piirangute süsteemis ...
54. Standardse (sümmeetrilise) lineaarse programmeerimise ülesande piirangute süsteemis ...
esineda saab ainult ebavõrdsust
esineda võivad nii võrrandid kui ka võrratused
ainult võrrandid võivad esineda
55. Kanoonilise (põhi) lineaarse programmeerimise ülesande piirangute süsteemis ...
võivad esineda ainult võrrandid (eeldusel, et muutujad on mittenegatiivsed)
võib esineda ainult ebavõrdsust (eeldusel, et muutujad on mittenegatiivsed)
esineda võivad nii võrrandid kui ka võrratused (eeldusel, et muutujad on mittenegatiivsed)
56. Lineaarse programmeerimise probleem
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 ≤ 14,
X 1 + X 2 ≤ 8,
X 1 ≥ 0, X 2 ≥ 0.
salvestatud ...
standardne (sümmeetriline) vorm
kanooniline (põhi)vorm
verbaalne vorm
57. Ülesande salvestamiseks
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 ≤ 14,
X 1 + X 2 ≤ 8,
X 1 ≥ 0, X 2 ≥ 0.
kanoonilisel kujul...
58. Ülesande salvestamiseks
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 ≤ 14,
X 1 + X 2 ≤ 8,
X 1 + 4X 2 ≥ 10,
X 1 ≥ 0, X 2 ≥ 0.
kanoonilisel kujul...
on vaja sisse viia kolm täiendavat mittenegatiivset muutujat
on vaja sisse viia kaks täiendavat mittenegatiivset muutujat
on vaja sisse viia neli täiendavat mittenegatiivset muutujat
59. Ülesande salvestamiseks
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 = 14,
X 1 + X 2 ≤ 8,
X 1 + 4X 2 ≥ 10,
X 1 ≥ 0, X 2 ≥ 0.
kanoonilisel kujul...
on vaja sisse viia kaks täiendavat mittenegatiivset muutujat
on vaja sisse viia kolm täiendavat mittenegatiivset muutujat
on vaja sisse viia neli täiendavat mittenegatiivset muutujat
on vaja sisse viia viis täiendavat mittenegatiivset muutujat
60. Täisarvulise programmeerimise ülesannete lahendamisel saab seda kasutada ...
Gomori meetod
Lagrange'i kordaja meetod
Gaussi meetod
Vogeli lähendamise meetod
61. Dünaamilise programmeerimise meetodil probleemide lahendamise keskmes on ...
Occami habemenuga
põhimõte "hammas hamba vastu, silm silma eest"
Heisenbergi põhimõte
62. Olukorda, millesse on kaasatud osapooled, kelle huvid on täielikult või osaliselt vastandlikud, nimetatakse ...
(konflikt, konflikt, konflikt, konflikt)
63. Tegelikku või formaalset konflikti, milles on vähemalt kaks osalejat (mängijat), kellest igaüks püüab saavutada oma eesmärke, nimetatakse ...
(mäng, mäng)
64. Iga mängija lubatud tegevust, mille eesmärk on saavutada teatud eesmärk, nimetatakse ...
(mängureeglid, mängureeglid)
65. Mängu tulemuste kvantitatiivset hindamist nimetatakse ...
(makse, makse, maksmise teel)
66. Kui mängus osaleb ainult kaks poolt (kaks inimest), siis nimetatakse mängu ...
(paarismäng, paarismäng, paarismäng, paarismäng)
67. Kui paarismängus on maksete summa võrdne nulliga, see tähendab, et ühe mängija kaotus on võrdne teise mängija võiduga, siis nimetatakse mängu mänguks ...
(null summa)
68. Mängija valiku ühemõttelist kirjeldust igas võimalikus olukorras, kus ta peab tegema isikliku käigu, nimetatakse ..
(mängija strateegia, mängija strateegia, strateegia, strateegia)
69. Kui mängu mitme korduse korral annab strateegia mängijale maksimaalse võimaliku keskmise kasu (minimaalse võimaliku keskmise kaotuse), siis nimetatakse sellist strateegiat ...
(optimaalne, optimaalne, optimaalne strateegia, optimaalne strateegia)
70. Olgu a nullsummaga paarismängu madal hind ja b kõrge hind. Siis on väide tõene...
71. Olgu a nullsummaga paarismängu madal hind ja b kõrge hind. Kui a = b = v, siis nimetatakse arvu v ...
mängu hinnaga
tasakaalupunkt
optimaalne strateegia
segastrateegia
72. Olgu a nullsummaga paarismängu madal hind ja b kõrge hind. Kui a = b, siis mängu nimetatakse ...
sadulapunkti mäng
lahendamatu konflikt
reegliteta mäng
73. Vektorit, mille iga komponent näitab suhtelist sagedust, kuidas mängija vastavat puhast strateegiat kasutab, nimetatakse ...
segastrateegia
suunavektor
normaalvektor
gradient
74. Maksemaatriksiga antud maatriksmängu madalam hind on võrdne ...
Rohkem alumine hind
võrdne alumise hinnaga
ei eksisteeri
81. Maatriksmäng, mille annab väljamakse maatriks, ...
on sadula ots
pole sadulapunkti
pole paaristatud
82. Väljamakse maatriksiga antud mängu hind on ...
83. Maatriksmäng, mille annab väljamakse maatriks ...
on paaris
on sadula ots
pole paaristatud
84. Nullsumma paarismängu, mis on antud selle väljamaksemaatriksiga, saab taandada ...
lineaarse programmeerimise probleem
mittelineaarse programmeerimise probleem
täisarvu lineaarse programmeerimise probleem
klassikaline optimeerimise probleem
85. Maksemaatriksi poolt antud maatriksmängu madalam hind on...
Rohkem alumine hind
võrdne alumise hinnaga
ei eksisteeri
92. Maatriksimäng, mille annab väljamakse maatriks ...
pole sadulapunkti
on sadula ots
pole paaristatud
93. Maksemaatriksiga antud mängu hind jääb ...
94. Kui sündmuste voos järgnevad sündmused üksteisele etteantud ja rangelt määratletud ajavahemike järel, siis nimetatakse sellist voogu ...
regulaarne
organiseeritud
95. Kui tõenäosus, et suvaline arv sündmusi langeb ajaintervallile, sõltub ainult selle intervalli pikkusest ja ei sõltu sellest, kui kaugel see intervall asub aja algusest, siis nimetatakse vastavat sündmuste voogu:
statsionaarne
vool ilma tagajärgedeta
kõige lihtsam
Poisson
96. Kui ühele meelevaldselt valitud ajaintervallile langevate sündmuste arv ei sõltu teisele, samuti meelevaldselt valitud ajavahemikule langevate sündmuste arvust eeldusel, et need intervallid ei ristu, siis nimetatakse vastavat sündmuste voogu. ...
vool ilma tagajärgedeta
regulaarne
soovituslik
normaalne
97. Kui tõenäosus, et kaks või enam sündmust tabavad korraga väga lühikest ajavahemikku, on tühine võrreldes tõenäosusega tabada ainult ühte sündmust, siis nimetatakse vastavat sündmuste voogu ...
tavaline
erakordne
normaalne
Poisson
98. Kui sündmuste voolul on samaaegselt statsionaarsuse, tavapärasuse ja tagajärgede puudumise omadused, siis nimetatakse seda:
lihtsaim (Poisson)
normaalne
99. Riketega ühe kanaliga süsteem on igapäevane autopesula teenindusjaam. Taotlus - auto, mis saabus hetkel, kui post on hõivatud - saab teenusest keeldumise. Auto voolukiirus λ = 1,0 (auto tunnis). Keskmine teenindusaeg on 1,8 tundi. Autovoog ja teenindusvoog on kõige lihtsamad. Seejärel püsiolekus suhteline läbilaskevõime q võrdub...
100. Riketega ühe kanaliga süsteem on igapäevane autopesula teenindusjaam. Taotlus - auto, mis saabus hetkel, kui post on hõivatud - saab teenusest keeldumise. Auto voolukiirus λ = 1,0 (auto tunnis). Keskmine teenindusaeg on 1,8 tundi. Autovoog ja teenindusvoog on kõige lihtsamad. Siis on püsiseisundis teenusest keeldumise saanud autode protsent ...
Lineaarse programmeerimise probleemi (LPP) üldine sõnastus. LPP näited
Lineaarne programmeerimine on matemaatika haru, mis uurib äärmuslike probleemide lahendamise meetodeid, mida iseloomustab muutujate lineaarne seos ja lineaarne optimaalsuse kriteerium. Paar sõna lineaarse programmeerimise termini kohta. See nõuab õiget arusaamist. Sel juhul ei ole programmeerimine loomulikult arvutiprogrammide kirjutamine. Programmeerimist tuleks siin tõlgendada kui planeerimist, plaanide koostamist, tegevusprogrammi väljatöötamist. Lineaarse programmeerimise matemaatilised probleemid hõlmavad konkreetsete tootmis- ja majandusolukordade uurimist, mida ühel või teisel kujul tõlgendatakse kui piiratud ressursside optimaalse kasutamise probleeme. Lineaarsete programmeerimismeetodite abil lahendatavate ülesannete ring on üsna lai. See on näiteks:
- - ressursside optimaalse kasutamise probleem tootmise planeerimisel;
- - segude probleem (toodete koostise planeerimine);
- - ladudes ladustamiseks optimaalse kombinatsiooni leidmine erinevat tüüpi toodetest (laovarude juhtimine või "seljakoti probleem");
- - transpordiülesanded (ettevõtte asukoha analüüs, kaupade liikumine). Lineaarne programmeerimine on enim arenenud ja laialdasemalt kasutatav matemaatilise programmeerimise haru (lisaks hõlmab see: täisarv, dünaamiline, mittelineaarne, parameetriline programmeerimine). See on tingitud järgmistest asjaoludest:
- - paljude majandusprobleemide matemaatilised mudelid on otsitavate muutujate suhtes lineaarsed;
- - seda tüüpi probleeme on praegu kõige rohkem uuritud. Tema jaoks on välja töötatud spetsiaalsed meetodid, mille abil neid ülesandeid lahendatakse, ja vastavad arvutiprogrammid;
- - paljud lineaarse programmeerimise probleemid on lahendatud, leidnud laialdast rakendust;
- - mõned probleemid, mis algses sõnastuses ei ole lineaarsed, võivad pärast mitmeid täiendavaid piiranguid ja eeldusi muutuda lineaarseks või taandada sellisele kujule, et neid saab lahendada lineaarsete programmeerimismeetoditega. Iga lineaarse programmeerimise probleemi majanduslik ja matemaatiline mudel sisaldab: sihtfunktsiooni, mille optimaalne väärtus (maksimaalne või miinimum) on vaja leida; piirangud lineaarsete võrrandite või võrratuste süsteemi kujul; muutujate mittenegatiivsuse nõue. Üldiselt on mudel kirjutatud järgmiselt:
- - objektiivne funktsioon:
C1x1 + c2x2 + ... + cnxn> max (min); - piirangud:
a11x1 + a12x2 + ... + a1nxn (? =?) b1,
a21x1 + a22x2 + ... + a2nxn (? =?) b2
am1x1 + am2x2 + ... + amnxn (? =?) bm;
Mittenegatiivsuse nõue:
Sel juhul on aij, bi, cj () antud konstandid. Probleem seisneb funktsiooni (2.1) optimaalse väärtuse leidmises vastavalt piirangutele (2.2) ja (2.3). Piirangute süsteemi (2.2) nimetatakse ülesande funktsionaalseteks piiranguteks ja piiranguid (2.3) otsesteks. Vektorit, mis vastab piirangutele (2.2) ja (2.3), nimetatakse lineaarse programmeerimise ülesande teostatavaks lahenduseks (plaaniks). Kujundust, milles funktsioon (2.1) saavutab maksimaalse (minimaalse) väärtuse, nimetatakse optimaalseks.
Allpool on näited mõnedest tüüpilistest probleemidest, mis on lahendatud lineaarsete programmeerimismeetodite abil. Sellistel ülesannetel on tõeline majanduslik sisu. Nüüd sõnastame need ainult LPP-ga ja käsitleme allpool selliste probleemide lahendamise meetodeid.
1. Ressursside optimaalse kasutamise probleem tootmise planeerimisel. Selle klassi ülesannete üldine tähendus on järgmine. Ettevõte toodab n erinevat toodet. Nende tootmine nõuab m erinevat tüüpi ressursse (tooraine, materjalid, tööaeg jne). Ressursid on piiratud, nende varud planeerimisperioodil on vastavalt b1, b2, ..., bm kokkuleppelised ühikud. Tuntud on ka tehnoloogilised koefitsiendid aij, mis näitavad, mitu ühikut i-ndat ressurssi on vaja j-ndat tüüpi toote ühiku tootmiseks (). Kasum, mis ettevõte saab j-ndat tüüpi toote müügist, võrdub cj-ga. Planeerimisperioodil jäävad aij, bi ja cj väärtused muutumatuks. On vaja koostada selline tootmisplaan, mille elluviimisel oleks ettevõtte kasum suurim. Allpool on selle klassi ülesande lihtne näide.
Ettevõte on spetsialiseerunud hokikeppide ja malekomplektide tootmisele. Iga klubi teenib ettevõttele 2 dollarit kasumit ja 4 dollarit iga malekomplekti eest. Ühe klubi valmistamiseks kohas A kulub neli tundi ja platsil B kaks tundi. Malekomplekt valmistatakse kuus tundi kohas A, kuus tundi kohas B ja üks tund kohas C. Olemasolev tootmisvõimsus kohapeal A on 120 Nm - tundi ööpäevas, lõik B - 72 n-tundi ja lõik C - 10 n-tundi. Kui palju nuppe ja malekomplekte peaks ettevõte iga päev tootma, et kasumit maksimeerida?
Selle klassi ülesannete tingimused esitatakse sageli tabelina (vt tabel 2.1).
Selle tingimuse korral sõnastame lineaarse programmeerimise probleemi. Märgime: x1 - päevas toodetud hokikeppide arv, x2 - päevas toodetud malekomplektide arv. ZLP sõnastus:
4x1 + 6x2? 120,
Rõhutagem, et iga ebavõrdsus funktsionaalsete piirangute süsteemis vastab antud juhul ühele või teisele tootmiskohale, nimelt: esimene kohas A, teine kohas B ja kolmas kohas C.
Külvipindade struktuuri optimeerimise probleemi muutujate süsteem, võttes arvesse külvikordi
