Izliektās kopas un to īpašības. Lai izpētītu LPP īpašības, ir jāsniedz stingra izliektas kopas definīcija. Agrāk izliekta kopa tika definēta kā kopa, kas kopā ar jebkuriem diviem punktiem satur segmentu, kas tos savieno.

Vairāku punktu segmenta jēdziena vispārinājums ir to izliekta lineārā kombinācija.

Tiek izsaukts punkts X izliekta lineāra kombinācija punktus, ja nosacījumi ir izpildīti

Punktu kopums ir izliekta, ja tas kopā ar kādu no diviem punktiem satur to patvaļīgu izliekto lineāro kombināciju.

Var pierādīt šādu teorēmu par izliekta daudzskaldņa attēlojumu.

Teorēma 1.1. Izliekts n-politops ir izliekta lineāra tā stūra punktu kombinācija.

No 1.1. teorēmas izriet, ka izliekts daudzskaldnis tiek ģenerēts ar tā stūra punktiem vai virsotnēm: segmentu ar diviem punktiem, trijstūri ar trim, tetraedru ar četriem punktiem utt. Tajā pašā laikā izliekts daudzskaldnis apgabals, kas ir neierobežota kopa, nav viennozīmīgi noteikts pēc stūra punktiem: nevienu tā punktu nevar attēlot kā izliektu lineāru stūra punktu kombināciju.

Lineārās programmēšanas uzdevuma īpašības. Iepriekš tika aplūkotas dažādas lineārās programmēšanas problēmas formas un parādīts, ka jebkuru lineārās programmēšanas problēmu var attēlot kā vispārīgu vai kanonisku problēmu.

Lai pamatotu lineārās programmēšanas problēmas īpašības un tās risināšanas metodes, ieteicams apsvērt vēl divus kanoniskās problēmas rakstīšanas veidus.

Matricas apzīmējums:

Šeit AR- rindu matrica, A- sistēmas matrica, NS- mainīgo lielumu matricas kolonna, V- bezmaksas dalībnieku matricas kolonna:

Vektoru apzīmējums:

kur vektori atbilst nezināmo faktoru koeficientu kolonnām.

Sekojošā teorēma tika izteikta iepriekš, bet nav pierādīta vispārīgā veidā.

Teorēma 1.2. Lineārās programmēšanas problēmas ierobežojumu sistēmas visu iespējamo risinājumu kopa ir izliekta.

Pierādījums:Ļaujiet būt - divi pieļaujamie LPP risinājumi, kas doti matricas formā. Tad un . Apsveriet izliektu lineāru risinājumu kombināciju, t.i.

un parādīt, ka tas ir arī pieļaujams risinājums sistēmai (1.3.). Patiešām

t.i. risinājums X atbilst sistēmai (1.3). Bet kopš tā laika NS> 0, t.i. risinājums apmierina nenegatīvisma nosacījumu.

Tātad ir pierādīts, ka visu lineārās programmēšanas uzdevuma pieļaujamo atrisinājumu kopa ir izliekta jeb, precīzāk, tā attēlo izliektu daudzskaldni vai izliektu daudzskaldņu apgabalu, ko turpmāk nosauksim ar vienu terminu - risinājumu daudzskaldnis.

Atbilde uz jautājumu, kurā risinājumu politopa punktā ir iespējams optimālais lineārās programmēšanas problēmas risinājums, ir sniegta sekojošā fundamentālajā teorēmā.

Teorēma 1.3. Ja lineārās programmēšanas uzdevumam ir optimāls risinājums, tad lineārā funkcija iegūst maksimālo vērtību vienā no atrisinājuma politopa stūra punktiem. Ja lineāra funkcija iegūst maksimālo vērtību vairāk nekā vienā stūra punktā, tad tā ņem to jebkurā punktā, kas ir šo punktu izliekta lineāra kombinācija.

Pierādījums: Mēs pieņemsim, ka risinājuma politops ir ierobežots. Apzīmēsim tā stūra punktus ar , un optimālais risinājums ir cauri X*... Tad F (X *)³ F (X) visiem punktiem NS risinājumu daudzskaldnis. Ja X* Ir stūra punkts, tad tiek pierādīta teorēmas pirmā daļa.

Izliksimies tā X* nav stūra punkts, tad pēc teorēmas 1.1 X* var attēlot kā risinājuma daudzskaldņa stūra punktu izliektu lineāru kombināciju, t.i.

Jo F (X) Ir lineāra funkcija, mēs iegūstam

Šajā paplašinājumā mēs izvēlamies maksimālo vērtību no vērtībām. Ļaujiet tai atbilst stūra punktam X k(1 £ k£ R); apzīmēsim to ar M, tie. . Aizstāt katru izteiksmes vērtību (1.5) ar šo maksimālo vērtību M. Tad

Pēc pieņēmuma NS* Tas ir optimālais risinājums, tāpēc, no vienas puses, bet, no otras puses, tas ir pierādīts
F (X *)£ M, tātad, kur X k- stūra punkts. Tātad ir stūra punkts X k kurā lineārā funkcija iegūst maksimālo vērtību.

Lai pierādītu teorēmas otro daļu, pieņemsim, ka mērķa funkcija iegūst maksimālo vērtību vairāk nekā vienā stūra punktā, piemēram, punktos , kur , tad

Ļaujiet būt NS- šo stūra punktu izliekta lineāra kombinācija, t.i.

Šajā gadījumā, ņemot vērā, ka funkcija F (X)- lineāri, mēs saņemam

tie. lineārā funkcija Fņem maksimālo vērtību patvaļīgā punktā NS kas ir izliekta lineāra stūra punktu kombinācija.

komentēt. Prasība, lai atrisinājumu politops teorēmā būtu ierobežots, ir būtiska, jo neierobežota daudzskaldņu domēna gadījumā, kā norādīts 1.1. teorēmā, ne katru šāda domēna punktu var attēlot ar tā stūra punktu izliektu lineāru kombināciju. .

Pierādītā teorēma ir fundamentāla, jo norāda uz principiālu lineārās programmēšanas problēmu risināšanas veidu. Patiešām, saskaņā ar šo teorēmu tā vietā, lai pētītu bezgalīgu iespējamo risinājumu kopu, lai atrastu starp tiem vēlamo optimālo risinājumu, ir nepieciešams izpētīt tikai ierobežotu skaitu risinājumu daudzskaldņa stūra punktu.

Nākamā teorēma ir veltīta analītiskajai metodei stūra punktu atrašanai.

Teorēma 1.4. Katrs lineārās programmēšanas uzdevuma pieļaujamais pamatrisinājums atbilst risinājuma politopa stūra punktam, un otrādi, katrs risinājuma daudzskaldņa stūra punkts atbilst pieļaujamam pamatrisinājumam.

Pierādījums:Ļaut ir pieļaujams pamata risinājums LPP ierobežojumu sistēmai (1.4), kurā pirmais T komponents ir galvenie mainīgie un pārējie n - t komponents - mazie mainīgie, kas pamatrisinājumā ir vienādi ar nulli (ja tas tā nav, tad atbilstošos mainīgos var pārnumurēt). Ļaujiet mums to parādīt NS

Pieņemsim pretējo, t.i. kas NS nav stūra punkts. Tad punkts NS var attēlot ar segmenta iekšējo punktu, kas savieno divus dažādus, kas nesakrīt ar X, punktus

citiem vārdiem sakot, izliekta lineāra punktu kombinācija risinājumu daudzskaldnis, t.i.

kur (mēs pieņemam, ka pretējā gadījumā punkts NS sakrīt ar punktu NS 1 vai NS 2).

Mēs rakstām vektoru vienādību (1.6) koordinātu formā:

Jo visi mainīgie un koeficienti nav negatīvi, tad no pēdējiem p-t vienlīdzības no tā izriet, ka, t.i. lēmumos NS 1 , NS 2 un NS vienādojumu sistēma (1.4) vērtības n - t komponenti šajā gadījumā ir vienādi ar nulli. Šos komponentus var uzskatīt par nelielu mainīgo vērtībām. Bet mazāko mainīgo vērtības viennozīmīgi nosaka galveno mainīgo vērtības, tāpēc

Tātad viss NS sastāvdaļa šķīdumos NS 1 , NS 2 un NS sakrīt, un tāpēc punkti NS 1 un NS 2 sapludināšana, kas ir pretrunā ar pieņēmumu. Tāpēc X Ir risinājuma daudzskaldņa stūra punkts.

Pierādīsim pretējo apgalvojumu. Ļaut būt risinājumu politopa stūra punktam un tā pirmajam T koordinātas ir pozitīvas. Ļaujiet mums to parādīt NS- pieļaujamais pamata risinājums. nav stūra punkts, kas ir pretrunā ar nosacījumu. Tāpēc mūsu pieņēmums ir nepareizs, t.i. vektori ir lineāri neatkarīgi un NS Ir pieļaujams problēmas (1.4) pamata risinājums.

Svarīgs secinājums tieši izriet no 1.3. un 1.4. teorēmas: ja lineārās programmēšanas problēmai ir optimāls risinājums, tad tas sakrīt ar vismaz vienu no tās pieļaujamajiem pamata risinājumiem.

Tātad, lineārās programmēšanas problēmas lineārās funkcijas optimums ir jāmeklē starp ierobežotu skaitu tās pieļaujamo pamata risinājumu.

Tiek veikta lineāro modeļu optimizācija programmā MS Excel simpleksa metode- mērķtiecīga lineārās programmēšanas problēmas atbalsta risinājumu uzskaitīšana. Simpleksās metodes algoritms tiek reducēts uz izliekta daudzskaldņa konstruēšanu daudzdimensiju telpā un pēc tam uz iterāciju pa tā virsotnēm, lai atrastu galējo vērtību mērķa funkcija.

Efektīvi līdzekļi lineārā programmēšana ir pamatā gan veselu skaitļu, gan nelineārai programmēšanai sarežģītākām optimizācijas problēmām. Tomēr šīm metodēm ir nepieciešams ilgāks aprēķina laiks.

Turpmākajās lekcijās tiks detalizēti analizēti piemēri tipisku optimizācijas problēmu risināšanai un vadības lēmumu pieņemšanai, izmantojot MS Excel pievienojumprogrammu "Meklēt risinājumu". Uzdevumiem, kurus vislabāk var veikt, izmantojot šo rīku, ir trīs galvenās īpašības:

• ir viens mērķis, funkcionāli saistīts ar citiem sistēmas parametriem, kas ir jāoptimizē (atrast tā maksimālo, minimumu vai noteiktu skaitlisko vērtību);
• pastāv ierobežojumi, kas parasti tiek izteikti nevienlīdzības veidā (piemēram, izlietoto izejvielu apjoms nedrīkst pārsniegt noliktavā esošo izejvielu krājumu, vai arī mašīnas darbības laiks dienā nedrīkst pārsniegt 24 stundas, atskaitot laiku apkalpošana);
• ir ievades mainīgo vērtību kopa, kas ietekmē optimizētās vērtības un ierobežojumus.

Uzdevuma parametrus ierobežo šādas robežvērtības:

• nezināmo skaits - 200;
• formulas ierobežojumu skaits nezināmajiem - 100;
• ierobežojošo nosacījumu skaits nezināmajiem ir 400.

Optimālo risinājumu atrašanas algoritms ietver vairākus posmus:

• sagatavošanas darbi;
• risinājuma atkļūdošana;
• risinājuma analīze.

Nepieciešamo sagatavošanās darbu secība, kas veikta ekonomiskās un matemātiskās modelēšanas uzdevumu risināšanā, izmantojot MS Excel, parādīta 1.6.attēla blokshēmā.

Rīsi. 1.6.

No pieciem sagatavošanas darba plāna punktiem formalizēts ir tikai piektais punkts. Pārējie darbi prasa radošumu – un tos dažādi cilvēki var paveikt dažādi. Īsi izskaidrosim plāna punktu formulējuma būtību.

Uzstādot problēmu, ir zināmi mērķa koeficienti un normalizētie koeficienti. Iepriekšējā piemērā koeficienti, kas veido mērķa funkciju, bija normalizētās peļņas vērtības uz vienu plauktu tipa ( ) un viens plaukts tipa ( ). Normalizētie koeficienti bija materiāla patēriņa un mašīnas laika likmes uz katra veida plauktu. Matrica izskatījās šādi:

Turklāt resursu vērtības vienmēr ir zināmas. Iepriekšējā piemērā tas bija iknedēļas dēļu piegāde un iespēja izmantot mašīnas laiku: , ... Bieži vien uzdevumos ir jāierobežo mainīgo lielumu vērtības. Tāpēc ir jānosaka to izmaiņu apgabala apakšējā un augšējā robeža.

Tādējādi optimizācijas programmas "Meklēt risinājumu" dialoglodziņā mums ir jānorāda šāds mērķa algoritms:

Mērķa funkcija ir vienāda ar vēlamo mainīgo vērtību vektora reizinājumu ar mērķa koeficientu vektoru

Normalizētie koeficienti meklēto mainīgo vērtību vektoram nedrīkst pārsniegt dotā resursu vektora vērtību

Mainīgā vērtībām jāatbilst noteiktajām sistēmas sākotnējo elementu skaita robežām

Sistēmas sākotnējo elementu skaits

Norādīto veidu resursu skaits

Risinājuma atkļūdošana ir nepieciešama gadījumā, ja programma izdod ziņojumu par negatīviem rezultātiem (1.7. attēls):

Rīsi. 1.7.

• ja izpildāms risinājums netiek iegūts, tad labo sākotnējo datu modeli;
• ja nav saņemts optimāls risinājums, pēc tam ieviesiet papildu ierobežojumus.

Programmas problēmas optimāls risinājums tikai, lai modelētu reālu problēmu, nevis pašas problēmas risinājumu. Konstruējot modeli, tika izdarīti dažādi vienkāršojoši pieņēmumi par reālo situāciju. Tas ļāva formalizēt procesu, aptuveni atspoguļojot reālās kvantitatīvās attiecības starp sistēmas parametriem un mērķi. Un, ja reālie parametri atšķiras no modelī iekļautajiem, kā mainīsies lēmums? Lai to noskaidrotu, pirms vadības lēmuma pieņemšanas tiek analizēts parauglēmums.

Analīze optimāls risinājums, kas iebūvēts programmā, ir ekonomisko procesu matemātiskās modelēšanas beigu posms. Tas ļauj padziļināti pārbaudīt modeļa piemērotību procesam, kā arī optimālā risinājuma uzticamību. Tas ir balstīts uz datiem optimāls risinājums un ziņojumi, kas tiek izsniegti sadaļā "Risinājuma meklēšana". Taču tas neizslēdz un neaizstāj tradicionālo plāna analīzi no ekonomiskā viedokļa pirms vadības lēmuma pieņemšanas.

Ekonomiskajai analīzei ir šādi mērķi:

• iespējamo seku noteikšana sistēmā kopumā un tās elementos, mainot modeļa parametru;
• optimālā plāna stabilitātes novērtējums atsevišķo problēmas parametru izmaiņām: ja tas nav izturīgs pret lielāko daļu parametru izmaiņām, samazinās tā īstenošanas un aprēķinātā optimālā sasniegšanas garantija;
• variantu aprēķinu veikšana un jaunu plānojuma variantu iegūšana, nerisinot problēmu no sākotnējās bāzes ar korekciju palīdzību.

Iespējamās analīzes metodes ir parādītas diagrammā 1.8. attēlā.

Pēc optimālā risinājuma saņemšanas tas tiek analizēts atbilstoši saņemtajiem ziņojumiem. Stabilitātes analīze- modeļa atsevišķu parametru izmaiņu ietekmes uz optimālā risinājuma rādītājiem izpēte. Robežu analīze- pieņemamo izmaiņu analīze optimālajā plānā, kurā plāns paliek optimāls.

Ņemot vērā atbildību padarīt ekonomisku vadības lēmums, vadītājam jāpārliecinās, vai saņemtais optimālais plāns ir vienīgais pareizais. Lai to izdarītu, pamatojoties uz modeli, ir jāiegūst atbildes uz šādiem jautājumiem:

• "kas būtu, ja..."
• "Kas ir nepieciešams, lai ..."

Tiek izsaukta analīze, lai atbildētu uz pirmo jautājumu variantu analīze; tiek saukta analīze, lai atbildētu uz otro jautājumu pielāgotus risinājumus.

Variantu analīze ir šāda veida:

• Parametrisks- analīze, kas sastāv no problēmas risināšanas noteikta parametra dažādām vērtībām.
• Strukturālā analīze- kad optimizācijas problēmas risinājums tiek meklēts ar atšķirīgu ierobežojumu struktūru.
• Daudzkritēriju analīze- Tas ir problēmas risinājums dažādām mērķa funkcijām.
• Analīze ar nosacījumiem ievades datiem- kad problēmas risināšanā izmantotie sākotnējie dati ir atkarīgi no papildu nosacījumu ievērošanas.

Pēc analīzes rezultāti jāatspoguļo grafiskā veidā un jāsastāda pārskats ar ieteikumiem lēmuma pieņemšanai, ņemot vērā konkrēto ekonomisko situāciju.

Definīcija... Jebkurš ierobežojumu sistēmas risinājums tiek saukts par LPP pieļaujamo risinājumu.
Definīcija... Īstenojamu risinājumu, kurā mērķa funkcija sasniedz maksimālo vai minimālo vērtību, sauc par optimālo risinājumu.

Pamatojoties uz šīm definīcijām, LP problēmu var formulēt šādi: starp visiem izliekta apgabala punktiem, kas ir ierobežojumu sistēmas risinājums, izvēlieties vienu, kura koordinātes minimizē (maksimizē) lineāro funkciju. F = ar 1 x + ar 2 y.
Ņemiet vērā, ka mainīgie x, y LPP parasti ņem nenegatīvas vērtības ( x≥ 0, y≥ 0), tātad apgabals atrodas koordinātu plaknes I ceturtdaļā.

Apsveriet lineāro funkciju F = ar 1 x + ar 2 y un labot dažas tās vērtības F... Ļaujiet, piemēram, F= 0, t.i. ar 1 x + ar 2 y= 0. Šī vienādojuma grafiks būs taisne, kas iet caur koordinātu sākumpunktu (0; 0) (Zīm.).
Zīmējums
Mainot šo fiksēto vērtību F = d, taisni ar 1 x+ ar 2 y = d pārvietosies paralēli un "izsekos" visai plaknei. Ļaujiet būt D- daudzstūris - apgabals ierobežojumu sistēmas risināšanai. Kad tas mainās d taisni ar 1 x + ar 2 y = d, par kādu vērtību d = d 1 sasniegs daudzstūri D, sauksim šo punktu A"Ieejas punkts" un pēc tam, šķērsojot daudzstūri, noteiktā vērtībā d = d 2 mums būs pēdējais kopīgais punkts ar to V, piezvanīsim V"Izejas punkts".
Acīmredzot, mērķa funkcija tās mazākā un lielākā vērtība F=ar 1 x + ar 2 y sasniegs ieejas punktos A un "iziet" V.
Ņemot vērā, ka mērķa funkcija apgabala virsotnēs ņem optimālo vērtību iespējamo risinājumu kopai D, LPP risināšanai var piedāvāt šādu plānu:

1. apbūvēt ierobežojumu sistēmas risinājumu laukumu;
2. izveido taisnu līniju, kas atbilst mērķa funkcijai, un, paralēli pārnesot šo taisni, atrod "ieejas" vai "izejas" punktu (atkarībā no prasības samazināt vai palielināt mērķa funkciju);
3. nosaka šī punkta koordinātas, aprēķina mērķfunkcijas vērtību tajās.

Ņemiet vērā, ka vektors ( ar 1 , ar 2), perpendikulāri taisnei, parāda mērķa funkcijas augšanas virzienu.

Atrisinot LPP grafiski, ir iespējami divi gadījumi, kas prasa īpašu apspriešanu.

1. gadījums
6. attēls
Pārvietojoties taisni ar 1 x + ar 2 y= d"Ieeja" vai "izeja" (kā attēlā) notiks daudzstūra malā. Tas notiks, ja daudzstūrim ir malas, kas ir paralēlas taisnei. ar 1 NS+ ar 2 plkst = d .
Šajā gadījumā "izejas" ("ieejas") punkti ir neskaitāmi, proti, jebkurš segmenta punkts AB... Tas nozīmē, ka mērķa funkcija iegūst maksimālo (minimālo) vērtību nevis vienā punktā, bet visos punktos, kas atrodas attiecīgajā daudzstūra pusē. D.

2. gadījums
Apsveriet gadījumu, kad pieļaujamo vērtību diapazons ir neierobežots.
Neierobežota apgabala gadījumā mērķa funkciju var norādīt tā, lai atbilstošajai taisnei nebūtu “izejas” (vai “ieejas”) punkta. Tad funkcijas maksimālā vērtība (minimums) nekad netiek sasniegta - viņi saka, ka funkcija nav ierobežota.
Zīmējums
Nepieciešams atrast mērķa funkcijas maksimālo vērtību F = 4x + 6y→ max, ar ierobežojumu sistēmu
Konstruēsim iespējamo risinājumu reģionu, t.i. grafiski atrisināsim nevienādību sistēmu. Lai to izdarītu, mēs konstruējam katru taisni un definējam nevienādību dotās pusplaknes.
x + y = 18

x	12	9
y	6	9

0,5x + y = 12

x	12	18
y	6	3

x= 12 - paralēli asij OY ;
y= 9 - paralēli asij VĒRSIS ;
x= 0 - ass OY ;
y = 0 - ass VĒRSIS;
x OY;
y≥ 0 - pusplakne virs ass VĒRSIS;
y≤ 9 - pusplakne zemāk y = 9;
x ≤ 12 - pusplakne pa kreisi x = 12;
0,5x + yx + y = 12;
x + y x + y = 18.
Zīmējums
Visu šo pusplakņu krustpunkts acīmredzot ir piecstūris OAVSD, ar virsotnēm punktos O(0; 0), A(0; 9), V(6; 9), AR(12; 6), D(12; 0). Šis piecstūris veido iespējamo problēmas risinājumu reģionu.

F = 4x + 6y→ maks.

x	3	0
y	–2	0

F = 0: 4x + 6y x+ 6y AR(12; 6). Tas ir viņā F = 4x + 6y
Līdz ar to, par x = 12, y= 6 funkcija F F= 4 ∙ 12 + 6 ∙ 6 = 84, vienāds ar 84. Punkts ar koordinātām (12; 6) apmierina visas ierobežojumu sistēmas nevienādības, un mērķa funkcijas vērtība tajā ir optimāla F* = 84 (optimālā vērtība tiks apzīmēta ar "*").
Problēma ir atrisināta. Tātad ir jāsaražo 12 I tipa produkti un 6 II tipa produkti, savukārt peļņa būs 84 tūkstoši rubļu.

Grafiskā metode tiek izmantota, lai atrisinātu problēmas, kurām ierobežojumu sistēmā bija tikai divi mainīgie. Šo metodi var pielietot arī nevienādību sistēmām ar trīs mainīgajiem. Ģeometriski situācija būs atšķirīga, taisnu līniju lomu trīsdimensiju telpā spēlēs plaknes, un nevienādības risinājums trīs mainīgajos būs pustelpa, kas atrodas plaknes vienā pusē. Reģionu lomu spēlēs daudzskaldnis, kas ir pustelpu krustpunkts.

Piemērs Nr.2. Raktuvēs veidojas divas šuves. Izgriezuma izlaide pirmajā kārtā ir a1%; otrajā - a2%. Maksimālais garensiena ražošanas apjoms pirmajam slānim ir B1 tūkst.t gadā, otrajam slānim - B2 tūkst.t gadā. Atbilstoši darba tehnoloģijai produkcija no otrā slāņa nevar pārsniegt produkciju no pirmā slāņa. Raktuves izlaide šahtā nedrīkst pārsniegt C1 tūkst.t gadā. Kopējai slodzei uz diviem slāņiem gadā jābūt vismaz C2 tūkst.t gadā. Izveidojiet matemātisko modeli un izveidojiet pieļaujamo slodzes vērtību kopu pirmajam un otrajam slānim gadā.

Piemērs Nr.3. Veikals pārdod 2 veidu bezalkoholiskos dzērienus: kolu un limonādi. Ienākumi no vienas kolas skārdenes ir 5 centi, savukārt no vienas limonādes skārdenes – 7 centi. Vidēji veikalā tiek pārdotas ne vairāk kā 500 skārdenes abu dzērienu dienā. Neskatoties uz to, ka kolu ražo pazīstams zīmols, pircēji dod priekšroku limonādei, jo tā ir daudz lētāka. Tiek lēsts, ka kolas un limonādes pārdošanas apjomiem jābūt vismaz 2:1, un zināms, ka veikalā tiek pārdotas vismaz 100 kolas skārdenes dienā. Cik skārdeņu katra dzēriena vajadzētu būt veikalam dienas sākumā, lai palielinātu ieņēmumus?

Piemērs Nr.4. Lineārās programmēšanas uzdevumu atrisiniet aptuveni grafiski ar sekojošu mērķa funkcijas vērtības precīzās vērtības un max (min) aprēķinu.

Piemērs Nr.5. Tūrisma aģentūrai nepieciešami ne vairāk kā trīs tonnu autobusi un ne vairāk kā piecu tonnu autobusi. Pirmās markas autobusu pārdošanas cena ir 20 000 USD, otrās markas – 40 000 USD. Tūrisma aģentūra autobusu iegādei var atvēlēt ne vairāk kā USD 1. Cik katras markas autobusus vajadzētu iegādāties atsevišķi, lai to kopējā (kopējā) kravnesība būtu maksimāla. Atrisiniet problēmu grafiski.

Piemērs Nr.6. Izmantojot grafisko metodi, atrodiet optimālo ražošanas plānu tabulā norādītajam uzdevumam.

Piemērs Nr.7. Lineārās programmēšanas uzdevumu atrisināt ar grafisku metodi, pakļaujot uzdevuma ierobežojumu sistēmu Džordana-Gausa transformācijām. Problēmu ierobežojumu sistēma ir šāda:
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
Vadlīnijas... Jordan-Gauss transformācijas var veikt, izmantojot šo pakalpojumu vai pētot SLAE.

Piemērs Nr.8. Uzņēmums ražo divu veidu A un B produkciju, kuru ražošanai izmanto trīs veidu izejvielas. Produkta A vienības ražošanai ir nepieciešams iztērēt katra veida izejvielas attiecīgi a1, a2, a3 kg, bet produkta B vienībai - b1, b2, b3 kg. Ražošana tiek nodrošināta ar katra veida izejvielām attiecīgi Р1, Р2, Р3 kg apjomā. Produkta A vienības izmaksas ir C1 rublis, un produkta B vienības cena ir C2 rubļi. Nepieciešams sastādīt A un B produktu ražošanas plānu, kas nodrošina gatavās produkcijas maksimālās izmaksas.

Piemērs Nr.2. Nepieciešams atrast mērķa funkcijas maksimālo vērtību F = 4x + 6y→ max, ar ierobežojumu sistēmu:

Konstruēsim iespējamo risinājumu reģionu, t.i. grafiski atrisināsim nevienādību sistēmu. Lai to izdarītu, atlasiet ierobežojumu skaitu, kas vienāds ar 4 (1. attēls).
1. attēls

Tad mēs aizpildām mainīgo lielumu un pašu ierobežojumu koeficientus (2. attēls).
2. attēls

3. attēls
x= 12 - paralēli asij OY;
y= 9 - paralēli asij VĒRSIS;
x> = 0 - ass OY
y= 0 - ass VĒRSIS;
x≥ 0 - pusplakne pa labi no ass OY;
y≥0 - pusplakne virs ass VĒRSIS;
y≤ 9 - pusplakne zemāk y = 9;
x≤ 12 - pusplakne pa kreisi x = 12;
0,5x + y≤ 12 - pusplakne zem taisnes 0,5 x + y = 12;
x + y≤ 18 - pusplakne zem taisnes x + y = 18.

Visu šo pusplakņu krustpunkts ir piecstūris ABCDE, ar virsotnēm punktos A(0; 0), B(0;9), C(6; 9), D(12;6), E(12; 0). Šis piecstūris veido iespējamo problēmas risinājumu reģionu.

Apsveriet problēmas objektīvo funkciju F = 4x + 6y→ maks.

x	3	0
y	–2	0

Mēs izveidojam taisnu līniju, kas atbilst funkcijas vērtībai F = 0: 4x + 6y= 0. Šo taisni pārvietosim paralēli. No visas līniju saimes 4 x + 6y= const pēdējā virsotne, caur kuru iet taisne, izejot ārpus daudzstūra robežas, būs virsotne AR(12; 6). Tas ir viņā F = 4x + 6y sasniedz savu maksimālo vērtību.

Līdz ar to, par x = 12, y= 6 funkcija F sasniedz savu maksimālo vērtību F= 4 ∙ 12 + 6 ∙ 6 = 84, vienāds ar 84. Punkts ar koordinātām (12; 6) apmierina visas ierobežojumu sistēmas nevienādības, un mērķa funkcijas vērtība tajā ir optimāla F* = 84.

Ieskaite disciplīnā "Operāciju izpēte"

(pareizās atbildes ir pirmās)

1. Termins "operāciju izpēte" parādījās ...

otrā pasaules kara laikā

XX gadsimta 50. gados

XX gadsimta 60. gados

XX gadsimta 70. gados

XX gadsimta 90. gados

XXI gadsimta sākumā

2. Operāciju izpētes līdzekļi (izvēlies atbilstošāko variantu) ...

zinātnisku metožu kopums organizācijas sistēmu efektīvas vadības problēmu risināšanai

pasākumu kopums, kas veikts noteiktu darbību īstenošanai

metožu kopums iecerētā plāna īstenošanai

zinātniskās resursu piešķiršanas metodes ražošanas organizēšanā

3. Sakārtojiet darbības, kas parasti tiek veiktas jebkurā operatīvajā izpētē:

problēmas formulējums

aplūkotā objekta (procesa) jēgpilna (verbālā) modeļa konstruēšana

matemātiskā modeļa veidošana

uz konstruētā matemātiskā modeļa bāzes formulētu uzdevumu risināšana

iegūto rezultātu pārbaude pētāmās sistēmas rakstura atbilstībai

iegūtā risinājuma ieviešana praksē

4. Operāciju izpētē ar operāciju saprot ...

Jebkurš notikums (darbību sistēma), ko vieno vienots jēdziens un kura mērķis ir sasniegt mērķi

jebkurš nekontrolējams notikums

tehnisko pasākumu kopums patēriņa preču ražošanas nodrošināšanai

5. Risinājumu sauc par optimālo, ...

ja viena vai otra iemesla dēļ tas ir vēlams

ja tas ir racionāli

ja tas ir saskaņots ar iestādēm

ja to apstiprina kopsapulce

6. Matemātiskā programmēšana ...

nodarbojas ar ekstrēmu problēmu izpēti un to risināšanas metožu izstrādi

ir datorprogrammu izveides process matemātiķu vadībā

risina matemātikas uzdevumus datorā

7. Lineārās programmēšanas uzdevums ir ...

lineārās funkcijas lielākās (mazākās) vērtības atrašana lineāru ierobežojumu klātbūtnē

lineāras programmas izveide izvēlētā programmēšanas valodā, kas paredzēta problēmas risināšanai

lineāra algoritma apraksts noteiktas problēmas risināšanai

8. Kvadrātiskās programmēšanas uzdevumā ...

mērķa funkcija ir kvadrātiska

pieļaujamo risinājumu laukums ir kvadrāts

ierobežojumi satur kvadrātiskās funkcijas

9. Veselo skaitļu programmēšanas uzdevumos ...

nezināmie var ņemt tikai veselas vērtības

mērķa funkcijai noteikti ir jābūt veselam skaitlim, un nezināmie var būt jebkuri

mērķa funkcija ir skaitliskā konstante

10. Parametriskās programmēšanas uzdevumos ...

mērķa funkcija un/vai ierobežojumu sistēma satur parametru(-us)

pieļaujamo risinājumu laukums ir paralelograms vai paralēlskaldnis

mainīgo lielumu skaits var būt tikai pāra

11. Dinamiskās programmēšanas problēmās ...

risinājuma atrašanas process ir vairākos posmos

jāracionalizē dinamīta ražošana

vēlaties optimizēt skaļruņu izmantošanu

12. Tiek izvirzīta šāda lineārās programmēšanas problēma:

F(NS 1, NS 2) = 5NS 1 + 6NS 2→ maks

0.2NS 1 + 0.3NS 2 ≤ 1.8,

0.2NS 1 + 0.1NS 2 ≤ 1.2,

0.3NS 1 + 0.3NS 2 ≤ 2.4,

NS 1 ≥ 0, NS 2 ≥ 0.

Izvēlieties uzdevumu, kas ir līdzvērtīgs šim uzdevumam.

F(NS 1, NS 2)= 5NS 1 + 6NS 2 → maks,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

F(NS 1, NS 2)= 6NS 1 + 5NS 2 → min,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

F(NS 1, NS 2)= 50NS 1 + 60NS 2 → maks,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

F(NS 1, NS 2)= 5NS 12 + 6NS 22 → maks,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

3NS 1 + NS 2 ≤ 2.4,

NS 1 ≥ 0,

NS 2 ≥ 0.

13. Lineārās programmēšanas uzdevuma mērķfunkcija var būt funkcija:

F=12x1+20x2-3 0x3→min

F= →min

F=→maks

F=→maks.

14. Lineārās programmēšanas problēmas ierobežojumu sistēma var būt sistēma:

15. Simpleksā metode ir:

analītiskā metode lineārās programmēšanas galvenās problēmas risināšanai

metode lineārās programmēšanas problēmas iespējamo risinājumu apgabala atrašanai;

grafiskā metode lineārās programmēšanas galvenās problēmas risināšanai;

metode vispārīgas lineārās programmēšanas problēmas samazināšanai līdz kanoniskajai formai.

16. Lineārās programmēšanas uzdevums ir:

lineārās funkcijas lielākās vai mazākās vērtības atrašana lineāru ierobežojumu klātbūtnē

lineārā algoritma izstrāde un realizācija datorā

lineāro vienādojumu sistēmas sastādīšana un risināšana

noteiktas ierobežojumu sistēmas aprakstītā procesa attīstības lineāras trajektorijas meklēšana.

17. Lineārās programmēšanas problēmas iespējamo risinājumu joma nevar izskatās šādi:

18. Lineārās programmēšanas uzdevuma mērķa funkcija var būt funkcija:

F=12x1+20x2-3 0x3→min

F= →min

F=→maks

F=→maks.

19. Lineārās programmēšanas problēmas ierobežojumu sistēma var būt sistēma:

20. Lineārās programmēšanas problēmas iespējamo risinājumu apgabals ir šāds:

F(NS 1, NS 2)= 3NS 1 + 5NS 2 vienāds...

21. Lineārās programmēšanas problēmas iespējamo risinājumu apgabalam ir šāda forma:

Pēc tam funkcijas maksimālā vērtība F(NS 1, NS 2)= 5NS 1 + 3NS 2 vienāds...

22. Lineārās programmēšanas problēmas iespējamo risinājumu apgabalam ir šāda forma:

Pēc tam funkcijas maksimālā vērtība F(NS 1, NS 2)= 2NS 1 - 2NS 2 vienāds...

23. Lineārās programmēšanas problēmas iespējamo risinājumu apgabalam ir forma:

F(NS 1, NS 2)= 2NS 1 - 2NS 2 vienāds...

24. Nelineārās programmēšanas problēmas iespējamo risinājumu apgabalam ir šāda forma:

Pēc tam funkcijas maksimālā vērtība F(NS 1, NS 2)= NS 2 – NS 12 ir vienāds...

25. Mērķa funkcijas maksimālā vērtība F(NS 1, NS 2)= 5NS 1 + 2NS 2 ar ierobežojumiem
NS 1 + NS 2 ≤ 6,

NS 1 ≤ 4,

NS 1 ≥ 0, NS 2 ≥ 0, vienāds ar ...

26. Mazais uzņēmums ražo divu veidu produkciju. Viena A tipa produkta ražošanai tiek patērēti 2 kg izejvielu, viena B tipa produkta ražošanai - 1 kg. Kopā ir 60 kg izejvielu. Nepieciešams sastādīt ražošanas plānu, kas nodrošina lielāko ieņēmumu saņemšanu, ja viena A tipa preces realizācijas pašizmaksa ir 3 vienības, B tipa – 1 vienība. Tas ir, A tipa izstrādājumi ir jāizgatavo ne vairāk kā 25, bet B tipa izstrādājumi - ne vairāk kā 30.

Šis uzdevums ir...

Lineārās programmēšanas problēma

problēma, kas atrisināta ar dinamiskās programmēšanas metodi

tīkla plānošanas uzdevums.

27. Mazais uzņēmums ražo divu veidu produkciju. Viena A tipa produkta ražošanai tiek patērēti 2 kg izejvielu, viena B tipa produkta ražošanai - 1 kg. Kopā ir 60 kg izejvielu. Nepieciešams sastādīt ražošanas plānu, kas nodrošina lielāko ieņēmumu saņemšanu, ja viena A tipa preces realizācijas pašizmaksa ir 3 vienības, B tipa – 1 vienība. Tas ir, A tipa izstrādājumi ir jāizgatavo ne vairāk kā 25, bet B tipa izstrādājumi - ne vairāk kā 30.

Šī uzdevuma mērķa funkcija ir funkcija ...

F(x1, x2)=3x1+x2→maks

F(x1, x2)=25x1+30x2→maks

F(x1, x2)=2x1+x2→maks

F(x1, x2)=60 -2x1 - x2→min

28. Mazais uzņēmums ražo divu veidu produkciju. Viena A tipa produkta ražošanai tiek patērēti 2 kg izejvielu, viena B tipa produkta ražošanai - 1 kg. Kopā ir 60 kg izejvielu. Nepieciešams sastādīt ražošanas plānu, kas nodrošina lielāko ieņēmumu saņemšanu, ja viena A tipa preces realizācijas pašizmaksa ir 3 vienības, B tipa – 1 vienība. Tas ir, A tipa izstrādājumi jāizgatavo ne vairāk kā 25, bet B tipa izstrādājumi - ne vairāk kā 30

Derīgs šī uzdevuma plāns ir plāns:

X =(20, 20)

X =(25, 15)

X =(20, 25)

X =(30, 10)

29. Divos punktos A1 un A2 ir attiecīgi 60 un 160 preču vienības. Visas preces nepieciešams transportēt uz punktiem B1, B2, B3 attiecīgi 80, 70 un 70 vienību apjomā. Tarifu matrica ir šāda:. Plānojiet transportu tā, lai izmaksas būtu minimālas.

Šis uzdevums ir...

transporta uzdevums

nelineārās programmēšanas problēma

ceļojošā pārdevēja problēma

uzdevuma uzdevums

30. Divos punktos A1 un A2 ir attiecīgi 60 un 160 preču vienības. Visas preces nepieciešams transportēt uz punktiem B1, B2, B3 attiecīgi 80, 70 un 70 vienību apjomā. Tarifu matrica ir šāda:. Plānojiet transportu tā, lai izmaksas būtu minimālas

Šī uzdevuma pamatplāns ir šāds:

;

31. Divos punktos A1 un A2 ir attiecīgi 60 un 160 preču vienības. Visas preces nepieciešams transportēt uz punktiem B1, B2, B3 attiecīgi 80, 70 un 70 vienību apjomā. Tarifu matrica ir šāda:. Plānojiet transportu tā, lai izmaksas būtu minimālas.

Šī uzdevuma mērķa funkcija ir funkcija:

F=4x11+6x12+ 8x13+5x21+8x22+7x23→min

F= →min

F=60x1+160x2+ 80x3+70x4+705 →maks

F=60x1+160x2– 80x3– 70x4– 705 →min

32. Divos punktos A1 un A2 ir attiecīgi 60 un 160 preču vienības. Visas preces nepieciešams transportēt uz punktiem B1, B2, B3 attiecīgi 80, 70 un 70 vienību apjomā. Tarifu matrica ir šāda:. Plānojiet transportu tā, lai izmaksas būtu minimālas.

Optimālais šī uzdevuma plāns ir šāds plāns:

;

.

;

;

33. Transporta problēma

tiks slēgts, ja...

34. Transporta problēma

ir…

atvērts

slēgts

nešķīstošs

35. Transporta problēma

ir…

slēgts

atvērts

nešķīstošs

36. Atrisināt šādu transporta problēmu

jāievada...

fiktīvs patērētājs

fiktīvs piegādātājs;

spēkā esošais tarifs

37. Atrisināt šādu transporta problēmu

jāievada...

fiktīvs piegādātājs;

fiktīvs patērētājs

spēkā esošais tarifs

efektīvā procentu likme.

38. Starp šiem transporta uzdevumiem

slēgti ir...

39. Transporta problēmas sākotnējo bāzes plānu var sastādīt ...

ar visām iepriekš minētajām metodēm

Ziemeļrietumu stūra metode

ar minimālā tarifa metodi

dubultā priekšroka metode

ar Vogela aproksimācijas metodi

40. Ja lineārās programmēšanas uzdevuma mērķfunkcija ir iestatīta uz maksimālo, tad ... duālā uzdevuma mērķfunkcija ir iestatīta uz minimumu.

duālajā problēmā nav objektīvas funkcijas

duālajai problēmai nav risinājumu

duālajai problēmai ir bezgala daudz risinājumu

41. Dota lineārās programmēšanas uzdevums:

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → maks,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

Šis uzdevums būs duāls ...

F*(y1, y2) = 14y1 + 8y2 → min,

3 g 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. Ja vienai no divu problēmu pāra ir optimāls plāns, tad ...

un otram ir optimāls plāns

otram nav optimāla plāna

otram nav reālu risinājumu

43. Ja vienam no duālo problēmu pāra ir optimāls plāns, tad ...

un otram ir optimāls plāns, un to optimālo plānu mērķa funkciju vērtības ir vienādas viena ar otru

un otram ir optimāls plāns, bet mērķfunkciju vērtības to optimālajiem plāniem nav vienādas viena ar otru

citai problēmai var nebūt optimāla plāna, bet tai ir iespējami risinājumi

44. Ja viena no duālo uzdevumu pāra mērķfunkcija nav ierobežota (maksimālajai problēmai - no augšas, minimālajai problēmai - no apakšas), tad

citam uzdevumam nav derīgu plānu

citam uzdevumam ir īstenojami plāni, bet nav optimāla plāna

nav ierobežota arī cita uzdevuma mērķa funkcija

45. Risinot dažus nelineārās programmēšanas uzdevumus, tiek izmantots ...

Lagranža reizinātāja metode

Gausa metode

Vogela aproksimācijas metode

Gomori metode

46. ​​Ir uzstādīta nelineārās programmēšanas problēma

F(NS 1, NS 2)= NS 12 + NS 22 → maks,

NS 1 + NS 2 =6,

NS 1 ≥ 0, NS 2 ≥ 0.

F(NS 1, NS 2) …

nav sasniedzams (+ ¥)

47. Uzstādīts nelineārās programmēšanas uzdevums

F(NS 1, NS 2)= NS 12 + NS 22 → miekšā,

NS 1 + NS 2 =6,

NS 1 ≥ 0, NS 2 ≥ 0.

F(NS 1, NS 2) …

48. Uzstādīts nelineārās programmēšanas uzdevums

F(NS 1, NS 2)= NS 12 + NS 22 → maks,

NS 1 + NS 2 =6,

NS 1, NS 2 - jebkura.

Mērķa funkcijas augstākā vērtība F(NS 1, NS 2) …

nav sasniedzams (+ ¥)

49. Uzstādīts nelineārās programmēšanas uzdevums

F(NS 1, NS 2)= NS 12 + NS 22 → miekšā,

NS 1 + NS 2 =6,

NS 1, NS 2 - jebkura.

Mērķa funkcijas mazākā vērtība F(NS 1, NS 2) …

nav sasniedzams (- ¥)

50. Nelineārās programmēšanas problēmas iespējamo risinājumu apgabalam ir šāda forma:

Pēc tam funkcijas maksimālā vērtība F(NS 1, NS 2)= NS 12 +NS 22 vienāds...

51. Nelineārās programmēšanas problēmas iespējamo risinājumu apgabalam ir šāda forma:

Pēc tam funkcijas minimālā vērtība F(NS 1, NS 2)= NS 12 +NS 22 vienāds...

52. Transporta problēmas risināšanai var pielietot ...

potenciālā metode

Lagranža reizinātāja metode

Gausa metode

dezorientācijas metode

53. Vispārējās lineārās programmēšanas problēmas ierobežojumu sistēmā ...

54. Standarta (simetriskas) lineārās programmēšanas uzdevuma ierobežojumu sistēmā ...

var būt tikai nevienlīdzība

var būt gan vienādojumi, gan nevienādības

var būt tikai vienādojumi

55. Kanoniskās (pamata) lineārās programmēšanas uzdevuma ierobežojumu sistēmā ...

var būt tikai vienādojumi (ar nosacījumu, ka mainīgie ir nenegatīvi)

var būt tikai nevienlīdzības (ar nosacījumu, ka mainīgie ir nenegatīvi)

var būt gan vienādojumi, gan nevienādības (ar nosacījumu, ka mainīgie ir nenegatīvi)

56. Lineārās programmēšanas problēma

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → maks,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

ierakstīts ...

standarta (simetriska) forma

kanoniskā (pamata) forma

verbālā forma

57.Uzdevuma ierakstīšanai

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → maks,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

kanoniskā formā...

58. Lai ierakstītu uzdevumu

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → maks,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 + 4NS 2 ≥ 10,

NS 1 ≥ 0, NS 2 ≥ 0.

kanoniskā formā...

nepieciešams ieviest trīs papildu nenegatīvus mainīgos

ir nepieciešams ieviest divus papildu nenegatīvus mainīgos

ir nepieciešams ieviest četrus papildu nenegatīvus mainīgos

59. Lai ierakstītu uzdevumu

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → maks,

2NS 1 + 3NS 2 = 14,

NS 1 + NS 2 ≤ 8,

NS 1 + 4NS 2 ≥ 10,

NS 1 ≥ 0, NS 2 ≥ 0.

kanoniskā formā...

ir nepieciešams ieviest divus papildu nenegatīvus mainīgos

nepieciešams ieviest trīs papildu nenegatīvus mainīgos

ir nepieciešams ieviest četrus papildu nenegatīvus mainīgos

nepieciešams ieviest piecus papildu nenegatīvus mainīgos

60. Risinot veselo skaitļu programmēšanas uzdevumus, var izmantot ...

Gomori metode

Lagranža reizinātāja metode

Gausa metode

Vogela aproksimācijas metode

61. Problēmu risināšanas ar dinamiskās programmēšanas metodes pamatā ir ...

Occam skuveklis

princips "zobs par zobu, acs pret aci"

Heizenberga princips

62. Situāciju, kurā ir iesaistītas puses, kuru intereses ir pilnīgi vai daļēji pretējas, sauc par ...

(konflikts, konflikts, konflikts, konflikts)

63. Faktisku vai formālu konfliktu, kurā ir vismaz divi dalībnieki (spēlētāji), no kuriem katrs cenšas sasniegt savus mērķus, sauc par ...

(spēle, spēle)

64. Katra spēlētāja pieļaujamās darbības, kas vērstas uz noteikta mērķa sasniegšanu, tiek sauktas par ...

(spēles noteikumi, spēles noteikumi)

65. Spēles rezultātu kvantitatīvo novērtēšanu sauc par ...

(ar maksājumu, samaksu, samaksu)

66. Ja spēlē piedalās tikai divas puses (divas personas), tad spēli sauc ...

(dubultspēles, dubultspēles, dubultspēles, dubultspēles)

67. Ja dubultspēlē maksājumu summa ir vienāda ar nulli, tas ir, viena spēlētāja zaudējums ir vienāds ar otra ieguvumu, tad spēli sauc par spēli ...

(nulles summa)

68. Spēlētāja izvēles nepārprotams apraksts katrā no iespējamām situācijām, kurās viņam jāveic personisks gājiens, tiek saukts par ..

(spēlētāja stratēģija, spēlētāja stratēģija, stratēģija, stratēģija)

69. Ja ar vairākiem spēles atkārtojumiem stratēģija nodrošina spēlētājam maksimālo iespējamo vidējo ieguvumu (minimālo iespējamo vidējo zaudējumu), tad šādu stratēģiju sauc par ...

(optimālā, optimālā, optimālā stratēģija, optimālā stratēģija)

70. Ļaujiet a ir nulles summas dubultspēļu zemā cena un b augstā cena. Tad apgalvojums ir patiess...

71. Pieņemsim, ka a ir nulles summas dubultspēles zemā cena un b augstā cena. Ja a = b = v, tad skaitli v sauc ...

par spēles cenu

līdzsvara punkts

optimāla stratēģija

jaukta stratēģija

72. Pieņemsim, ka a ir nulles summas dubultspēļu zemā cena un b augstā cena. Ja a = b, tad spēli sauc ...

seglu punktu spēle

neatrisināms konflikts

spēle bez noteikumiem

73. Vektoru, kura katra sastāvdaļa parāda relatīvo biežumu, kādā spēlētājs izmanto atbilstošo tīro stratēģiju, sauc par ...

jaukta stratēģija

virziena vektors

normāls vektors

gradients

74. Matricas spēles zemākā cena, ko dod maksājumu matrica, ir vienāda ar ...

Vairāk apakšējās cenas

vienāda ar zemāko cenu

neeksistē

81. Matricas spēle, ko dod izmaksu matrica, ...

ir seglu punkts

nav seglu gala

nav savienots pārī

82. Spēles cena, kas norādīta ar izmaksu matricu, ir ...

83. Matricas spēle, ko dod izmaksu matrica ...

ir savienots pārī

ir seglu punkts

nav savienots pārī

84. Nulles summas dubultspēli, ko nosaka tās izmaksas matrica, var samazināt līdz ...

Lineārās programmēšanas problēma

nelineārās programmēšanas problēma

veselu skaitļu lineārās programmēšanas problēma

klasiskā optimizācijas problēma

85. Maksājumu matricas dotā matricas spēles zemākā cena ir...

Vairāk apakšējās cenas

vienāda ar zemāko cenu

neeksistē

92. Matricas spēle, ko dod izmaksu matrica ...

nav seglu gala

ir seglu punkts

nav savienots pārī

93. Spēles cena, ko uzrāda maksājumu matrica, ir ...

94. Ja notikumu plūsmā notikumi seko cits citam iepriekš noteiktos un stingri noteiktos laika intervālos, tad šādu straumi sauc ...

regulāri

organizēts

95. Ja iespējamība, ka uz kādu laika intervālu iekrīt jebkurš notikumu skaits, ir atkarīga tikai no šī intervāla garuma un nav atkarīga no tā, cik tālu šis intervāls atrodas no laika sākuma, tad atbilstošo notikumu plūsmu sauc:

stacionārs

plūsma bez sekām

visvienkāršākā

Puasona

96. Ja notikumu skaits, kas iekrīt vienā no patvaļīgi izvēlētajiem laika intervāliem, nav atkarīgs no notikumu skaita, kas iekrīt citā, arī patvaļīgi izvēlētā laika intervālā, ar nosacījumu, ka šie intervāli nekrustojas, tad atbilstošo notikumu plūsmu sauc. ...

plūsma bez sekām

regulāri

indikatīvs

normāli

97. Ja varbūtība, ka divi vai vairāki notikumi uzreiz trāpīs ļoti īsā laika intervālā, ir niecīga salīdzinājumā ar varbūtību trāpīt tikai vienam notikumam, tad atbilstošo notikumu plūsmu sauc...

parasts

ārkārtējs

normāli

Puasona

98. Ja notikumu plūsmai vienlaikus piemīt stacionaritātes, parastības un seku neesamības īpašības, tad to sauc:

vienkāršākais (Puasons)

normāli

99. Vienkanāla sistēma ar atteicēm ir ikdienas automazgātavas serviss. Pieteikums - automašīna, kas atbraukusi brīdī, kad amats ir aizņemts - saņem dienesta atteikumu. Automašīnas plūsmas ātrums λ = 1,0 (auto stundā). Vidējais apkalpošanas laiks ir 1,8 stundas. Auto plūsma un servisa plūsma ir visvienkāršākā. Tad līdzsvara stāvoklī relatīvā caurlaidspēja q vienāds...

100. Vienkanāla sistēma ar kļūmēm ir ikdienas automazgātavas serviss. Pieteikums - automašīna, kas atbraukusi brīdī, kad amats ir aizņemts - saņem dienesta atteikumu. Automašīnas plūsmas ātrums λ = 1,0 (auto stundā). Vidējais apkalpošanas laiks ir 1,8 stundas. Auto plūsma un servisa plūsma ir visvienkāršākā. Tad līdzsvara stāvoklī to automašīnu procentuālais daudzums, kurām tiek atteikts pakalpojums, ir ...

Lineārās programmēšanas problēmas (LPP) vispārīgs formulējums. LPP piemēri

Lineārā programmēšana ir matemātikas nozare, kas pēta ekstrēmu problēmu risināšanas metodes, kuras raksturo lineāra sakarība starp mainīgajiem un lineārs optimitātes kritērijs. Daži vārdi par pašu terminu lineārā programmēšana. Tam nepieciešama pareiza izpratne. Šajā gadījumā programmēšana, protams, nav datorprogrammu rakstīšana. Programmēšana šeit ir jāinterpretē kā plānošana, plānu veidošana, rīcības programmas izstrāde. Lineārās programmēšanas matemātiskās problēmas ietver konkrētu ražošanas un ekonomisko situāciju izpēti, kuras vienā vai otrā veidā tiek interpretētas kā ierobežotu resursu optimālas izmantošanas problēmas. Uzdevumu loks, ko var atrisināt, izmantojot lineārās programmēšanas metodes, ir diezgan plašs. Tas ir, piemēram:

• - optimālas resursu izmantošanas problēma ražošanas plānošanā;
• - maisījumu problēma (produktu sastāva plānošana);
• - problēma, kā atrast dažādu veidu produktu optimālo kombināciju uzglabāšanai noliktavās (krājumu vadība vai "mugursomas problēma");
• - transporta uzdevumi (uzņēmuma atrašanās vietas analīze, preču kustība). Lineārā programmēšana ir visattīstītākā un visplašāk izmantotā matemātiskās programmēšanas nozare (turklāt tā ietver: veselo skaitļu, dinamisko, nelineāro, parametrisko programmēšanu). Tas ir saistīts ar sekojošo:
• - daudzu ekonomisko problēmu matemātiskie modeļi ir lineāri attiecībā pret meklētajiem mainīgajiem;
• - šāda veida problēma šobrīd ir visvairāk pētīta. Viņam ir izstrādātas speciālas metodes, ar kuru palīdzību tiek risināti šie uzdevumi, un atbilstošās datorprogrammas;
• - daudzas lineārās programmēšanas problēmas, atrisinātas, ir atradušas plašu pielietojumu;
• - dažas problēmas, kuras sākotnējā formulējumā nav lineāras, pēc vairākiem papildu ierobežojumiem un pieņēmumiem var kļūt lineāras vai reducētas līdz tādai formai, ka tās var atrisināt ar lineārās programmēšanas metodēm. Jebkuras lineārās programmēšanas problēmas ekonomiskais un matemātiskais modelis ietver: mērķa funkciju, kuras optimālā vērtība (maksimums vai minimums) jāatrod; ierobežojumi lineāru vienādojumu vai nevienādību sistēmas veidā; prasība pēc mainīgo lielumu nenegatīvisma. Kopumā modelis ir uzrakstīts šādi:
• - mērķa funkcija:

C1x1 + c2x2 + ... + cnxn> max (min); - ierobežojumi:

a11x1 + a12x2 + ... + a1nxn (? =?) b1,

a21x1 + a22x2 + ... + a2nxn (? =?) b2

am1x1 + am2x2 + ... + amnxn (? =?) bm;

Prasība bez negatīvisma:

Šajā gadījumā aij, bi, cj () tiek dotas konstantes. Problēma ir atrast funkcijas (2.1) optimālo vērtību, ievērojot ierobežojumus (2.2) un (2.3). Ierobežojumu sistēmu (2.2) sauc par problēmas funkcionālajiem ierobežojumiem, bet ierobežojumus (2.3) par tiešiem. Vektoru, kas atbilst (2.2) un (2.3) ierobežojumiem, sauc par iespējamu lineārās programmēšanas problēmas risinājumu (plānu). Konstrukciju, kurā funkcija (2.1) sasniedz savu maksimālo (minimālo) vērtību, sauc par optimālo.

Tālāk ir sniegti dažu tipisku problēmu piemēri, kas atrisinātas, izmantojot lineārās programmēšanas metodes. Šādiem uzdevumiem ir reāls ekonomisks saturs. Tagad mēs tos formulēsim tikai LPP izteiksmē, un turpmāk mēs apsvērsim metodes šādu problēmu risināšanai.

1. Problēma par optimālu resursu izmantošanu ražošanas plānošanā. Šīs klases uzdevumu vispārīgā nozīme ir šāda. Uzņēmums ražo n dažādus produktus. To ražošanai nepieciešami m dažāda veida resursi (izejvielas, materiāli, darba laiks utt.). Resursi ir ierobežoti, to rezerves plānošanas periodā ir attiecīgi b1, b2, ..., bm konvencionālās vienības. Ir zināmi arī tehnoloģiskie koeficienti aij, kas parāda, cik i-tā resursa vienību nepieciešams, lai saražotu j-tā veida produkta vienību (). Peļņa, ko uzņēmums saņem no j-tā veida preces pārdošanas, ir vienāda ar cj. Plānošanas periodā aij, bi un cj vērtības paliek nemainīgas. Nepieciešams sastādīt tādu ražošanas plānu, kuru īstenojot uzņēmuma peļņa būtu vislielākā. Tālāk ir sniegts vienkāršs šīs klases uzdevuma piemērs.

Uzņēmums specializējas hokeja nūju un šaha komplektu ražošanā. Katrs klubs uzņēmumam gūst 2 USD peļņu un 4 USD par katru šaha komplektu. Viena nūja izgatavošana objektā A aizņem četras stundas, bet vietā B - divas stundas. Šaha komplekts tiek izgatavots ar sešām stundām objektā A, sešām stundām objektā B un vienu stundu objektā C. Pieejamā ražošanas jauda objektā A ir 120 Nm - stundas diennaktī, sekcija B - 72 n-stundas un C sekcija - 10 n-stundas. Cik nūju un šaha komplektu uzņēmumam vajadzētu ražot katru dienu, lai palielinātu peļņu?

Šīs klases uzdevumu nosacījumi bieži tiek sniegti tabulas veidā (sk. 2.1. tabulu).

Saskaņā ar šo nosacījumu mēs formulējam lineārās programmēšanas problēmu. Apzīmēsim: x1 - katru dienu saražoto hokeja nūju skaitu, x2 - katru dienu saražoto šaha komplektu skaitu. ZLP formulējums:

4x1 + 6x2? 120,

Uzsvērsim, ka katra funkcionālo ierobežojumu sistēmas nevienādība šajā gadījumā atbilst vienai vai otrai ražotnei, proti: pirmā vietai A, otrā vietai B un trešā vietai C.

Mainīgo lielumu sistēma sējumu struktūras optimizācijas problēmā, ņemot vērā augsekas