Prezentācijas lineārā programmēšana. Lineārās programmēšanas uzdevumu risināšana ar grafisko metodi, prezentācija algebras nodarbībai par tēmu Gatavu prezentāciju portāls lineārā programmēšana

10.01.2022

Lēmumu pieņemšana nenoteiktības apstākļos Ja pirmajam subjektam ir m stratēģijas, bet otrajam ir n stratēģijas, tad tiek uzskatīts, ka mums ir darīšana ar m x n spēli. Apsveriet spēli m x n. Ļaujiet dot stratēģiju kopu: pirmajam spēlētājam (Ai), otrajam spēlētājam (Bj), maksājumu matrica, kur aij ir pirmā spēlētāja ieguvums vai otrā spēlētāja zaudējums, izvēloties stratēģijas Ai un Bj, attiecīgi. Katrs spēlētājs unikāli ar varbūtību I izvēlas kādu stratēģiju, t.i. izvēloties risinājumu, izmanto tīru stratēģiju. Šajā gadījumā spēles risinājums būs tīrās stratēģijās. Tā kā spēlētāju intereses ir pretējas, pirmais spēlētājs cenšas palielināt savus laimestus, bet otrais spēlētājs, gluži pretēji, samazina savus zaudējumus. Spēles risinājums ir noteikt labāko stratēģiju katram spēlētājam. Viena spēlētāja labākās stratēģijas izvēle tiek veikta, ja nav informācijas par otrā spēlētāja pieņemto lēmumu.

2. slaids

Lineārā programmēšana

Lineārās programmēšanas metodes tiek izmantotas prognožu aprēķinos, ražošanas procesu plānošanā un organizēšanā.

Lineārā programmēšana ir matemātikas nozare, kas pēta metodes, kā izpētīt un atrast tādas lineāras funkcijas ekstremālās vērtības, kuru argumenti ir pakļauti lineāriem ierobežojumiem.

3. slaids

Šādu lineāru funkciju sauc par mērķa funkciju, un kvantitatīvo attiecību kopumu starp mainīgajiem, kas vienādojumu vai nevienādību veidā izsaka noteiktas ekonomiskās problēmas prasības, sauc par ierobežojumu sistēmu. Vārds programmēšana tika ieviests tāpēc, ka nezināmi mainīgie parasti nosaka kāda priekšmeta programmu vai darba plānu.

4. slaids Attiecību kopu, kas satur mērķa funkciju un ierobežojumus tās argumentiem, sauc par optimizācijas problēmas matemātisko modeli. PAP ir ierakstīts vispārējs skats

kā šis: ar ierobežojumiem

5. slaids

Šeit nav zināmi konstanti lielumi. Ierobežojumus var norādīt ar vienādojumiem.

Šajā gadījumā mērķfunkcijas ekstrēmu meklē uz pieļaujamo risinājumu kopu, ko nosaka ierobežojumu sistēma, un visas vai dažas ierobežojumu sistēmas nevienādības var ierakstīt vienādojumu veidā.

7. slaids

IN īsa piezīme ZLP ir forma: ar ierobežojumiem

8. slaids

Lai sastādītu ZLP matemātisko modeli, nepieciešams: 1) apzīmēt mainīgos;

2) izveidot mērķa funkciju;

3) pierakstīt ierobežojumu sistēmu atbilstoši problēmas mērķim;

4) pierakstīt ierobežojumu sistēmu, ņemot vērā problēmas izklāstā pieejamos rādītājus.

Ja visi uzdevuma ierobežojumi ir doti ar vienādojumiem, tad šāda veida modeli sauc par kanonisko. Ja vismaz viens no ierobežojumiem ir dots ar nevienlīdzību, tad modelis nav kanonisks.

9. slaids

Uzdevumu piemēri, kurus var reducēt līdz PPL. optimālas resursu sadales problēma, plānojot ražošanu uzņēmumā (sortimenta problēma); uzdevums maksimāli palielināt produkcijas izlaidi konkrētam sortimentam; problēma par maisījumiem (barība, diēta utt.); transporta problēma; esošo jaudu racionālas izmantošanas uzdevums; uzdevuma problēma. 10. slaids

1. Optimālas resursu sadales problēma.

Pieņemsim, ka uzņēmums ražo dažādus produktus. To ražošanai ir nepieciešams

dažādi veidi

resursi (izejvielas, darba un mašīnu laiks, palīgmateriāli). Šie resursi ir ierobežoti un plānošanas periodā atbilst parastajām vienībām. Ir zināmi arī tehnoloģiskie koeficienti, kas norāda, cik i-tā resursa vienības nepieciešams, lai ražotu j-tā tipa produktu. Lai peļņa, ko uzņēmums saņem, pārdodot j-tā tipa produkta vienību, ir vienāda. Plānošanas periodā tiek pieņemts, ka visi rādītāji ir nemainīgi.

11. slaids

Nepieciešams sastādīt ražošanas plānu, kurā uzņēmuma peļņa būtu vislielākā.

Problēmas ekonomiskais un matemātiskais modelis

12. slaids Mērķa funkcija atspoguļo kopējo peļņu no visu veidu saražotās produkcijas pārdošanas. Šajā problēmas modelī ir iespējama optimizācija, izvēloties ienesīgākos produktu veidus. Ierobežojumi nozīmē, ka jebkura resursa kopējais patēriņš visu veidu produktu ražošanai nepārsniedz tā rezerves. nevar pārsniegt 120, tad nevienlīdzība ir jāapmierina

15. slaids

Izmantojot līdzīgu argumentāciju, mēs varam izveidot ierobežojumu sistēmu

16. slaids

Tagad izveidosim mērķa funkciju. Peļņa no A tipa produkcijas realizācijas būs 10, no B tipa produkcijas realizācijas -14 un no C-12 tipa produkcijas realizācijas Kopējā peļņa no visas produkcijas realizācijas būs

17. slaids

Tādējādi mēs nonākam pie šāda ZLP: No visiem nevienādību sistēmas nenegatīvajiem risinājumiem ir jāatrod tāds, pie kura mērķa funkcija iegūst maksimālo vērtību.

18. slaids

2. piemērs

Pilsētas piena kombināta produkcija ir piens, kefīrs un skābais krējums, fasēts traukos. Lai saražotu 1 tonnu piena, kefīra un skābā krējuma, nepieciešami attiecīgi 1010, 1010 un 9450 kg piena. Tajā pašā laikā 1 tonnas piena un kefīra iepildīšanai pudelēs nepieciešamais darba laiks ir 0,18 un 0,19 mašīnas stundas. Speciālās mašīnas ir aizņemtas, iepakojot 1 tonnu skābā krējuma 3,25 stundas.

19. slaids

Kopumā pilnpiena produktu ražošanai rūpnīca var izmantot 136 000 kg piena. Galvenās iekārtas var aizņemt 21,4 mašīnas stundas, bet saldā krējuma iepakošanas iekārtas - 16,25 stundas. Peļņa no 1 tonnas piena, kefīra un skābā krējuma pārdošanas ir attiecīgi 30, 22 un 136 rubļi. Rūpnīcai katru dienu jāsaražo vismaz 100 tonnas pudelēs pildīta piena. Citu produktu ražošanai nav ierobežojumu.

20. slaids

Ir jānosaka, kādus produktus un kādos daudzumos ražotnei vajadzētu ražot katru dienu, lai peļņa no tās pārdošanas būtu maksimāla. Rakstīt matemātiskais modelis uzdevumus.

21. slaids

Risinājums

Lai rūpnīca ražo tonnas piena, tonnas kefīra un tonnas skābā krējuma.

Tad viņam vajag kg piena.

Tā kā rūpnīca var izmantot ne vairāk kā 136 000 kg piena dienā, nevienlīdzība ir jāapmierina

22. slaids

Laika ierobežojumi piena un kefīra un skābā krējuma iepakojumam.

Tā kā dienā būtu jāsaražo vismaz 100 tonnas piena, tad.

No ekonomiskā viedokļa

23. slaids

Kopējā peļņa no visu produktu pārdošanas ir vienāda ar RUB. Tādējādi mēs nonākam pie šādas problēmas: ar ierobežojumiem Tā kā mērķa funkcija ir lineāra un ierobežojumus nosaka nevienlīdzību sistēma, šī problēma ir ZLP.

24. slaids

Problēma ar maisījumiem.

Risinājums

Ir divu veidu produkti, kas satur barības vielas (taukus, olbaltumvielas utt.)

25. slaids

Problēmas matemātiskais formulējums: izveidojiet ikdienas uzturu, kas apmierina ierobežojumu sistēmu un samazina mērķa funkciju.

Kopumā problēmu grupā par maisījumiem ir problēmas atrast lētāko noteiktu izejmateriālu komplektu, kas nodrošina maisījuma ar noteiktām īpašībām ražošanu. Iegūtajos maisījumos noteiktos daudzumos jāsatur n dažādas sastāvdaļas, un paši komponenti ir m izejvielu sastāvdaļas.

28. slaids

Ieviesīsim šādu apzīmējumu: -maisījumā iekļautā j-tā materiāla daudzums; -j-tā tipa materiāla cena; ir minimālais nepieciešamais i-tās sastāvdaļas saturs maisījumā.

Koeficienti parāda i-tā komponenta īpatnējo svaru j-tā materiāla vienībā

29. slaids

Problēmas ekonomiskais un matemātiskais modelis.

Mērķa funkcija atspoguļo maisījuma kopējās izmaksas, un funkcionālie ierobežojumi ir komponentu satura ierobežojumi maisījumā: maisījumam jāsatur sastāvdaļas ne mazākā apjomā par norādītajiem.

30. slaids Griešanas problēma Apģērbu rūpnīcā audumu var griezt vairākos veidos, lai izgatavotu vēlamās apģērba daļas. Lai ar j-to griešanas iespēju ražo i-tā tipa detaļas, bet atkritumu daudzumu ar

šo iespēju

griešana ir vienāda ar Zinot, ka i-tā tipa daļas jātaisa gabalos, nepieciešams audums sagriezt tā, lai ar minimālu kopējo atkritumu daudzumu tiktu iegūts nepieciešamais katra veida detaļu skaits. Izveidojiet problēmas matemātisko modeli.

31. slaids

Risinājums. Pieņemsim, ka, izmantojot j-to iespēju, tiek sagriezti simtiem audumu. Tā kā, griežot audumu pēc j-tā varianta, tiek iegūtas i-tā tipa daļas, tad visiem griešanas variantiem no izmantotajiem audumiem kopējais atkritumu daudzums visiem griešanas variantiem būs

35. slaids

LP galvenais uzdevums

Def.4. Galvenais jeb kanoniskais ZLP ir uzdevums, kas sastāv no mērķa funkcijas vērtības noteikšanas ar nosacījumu, ka ierobežojumu sistēma ir parādīta vienādojumu sistēmas veidā:

36. slaids

Atbalsta plānu sauc par nedeģenerētu, ja tajā ir m pozitīvas sastāvdaļas. Citādi to sauc par deģenerētu.

Plānu, kurā ZLP mērķa funkcija iegūst maksimālo (minimālo) vērtību, sauc par optimālo.

Skatīt visus slaidus
Noklikšķinot uz pogas "Lejupielādēt arhīvu", jūs pilnībā bez maksas lejupielādēsit nepieciešamo failu. Pirms lejupielādesšo failu atcerieties šīs labās esejas, kontroldarbus, kursa darbus, tēzes
, raksti un citi dokumenti, kas atrodas jūsu datorā nepieprasīti. Tas ir jūsu darbs, tam vajadzētu piedalīties sabiedrības attīstībā un dot labumu cilvēkiem. Atrodiet šos darbus un iesniedziet tos zināšanu bāzei.

Mēs un visi studenti, maģistranti, jaunie zinātnieki, kuri izmanto zināšanu bāzi savās studijās un darbā, būsim jums ļoti pateicīgi.

Lai lejupielādētu arhīvu ar dokumentu, ievadiet piecciparu skaitli zemāk esošajā laukā un noklikšķiniet uz pogas "Lejupielādēt arhīvu"

Līdzīgi dokumenti

Optimizācijas problēmas. Pieļaujamā komplekta ierobežojumi. Klasiskā optimizācijas problēma. Lagranža funkcija. Lineārā programmēšana: uzdevumu formulēšana un to grafiskais risinājums. Algebriskā metode uzdevumu risināšanai. Simplex metode, simpleksa tabula.

anotācija, pievienota 29.09.2008 Matemātiskās programmēšanas uzdevumu klasifikācija. Grafiskās metodes būtība lineārās programmēšanas uzdevumu risināšanai, tabulu vienkāršās metodes algoritms. Apraksts loģiskā struktūra

un programmas teksts uzdevuma risināšanai, izmantojot grafisko metodi.

kursa darbs, pievienots 27.03.2011 Vispārīgi uzdevumi

lineārā programmēšana. Simpleksās metodes algoritma apraksts, rakstīts kanoniskā formā ar vienpusējiem ierobežojumiem. Algoritms sākotnējā atsauces plāna sastādīšanai problēmas risināšanai. Paplašināts mākslīgās bāzes algoritms.

kursa darbs, pievienots 24.10.2012

Optimizācijas matemātiskie pamati. Optimizācijas problēmas izklāsts. Optimizācijas metodes. Problēmas risināšana, izmantojot klasisko simpleksa metodi. Grafiskā metode. Problēmu risināšana, izmantojot Excel. Objektīvo funkciju koeficienti. Lineārā programmēšana, metode, problēmas.

abstrakts, pievienots 21.08.2008

Lineārās programmēšanas problēmas izklāsts. Vienādojumu sistēmas atrisināšana, izmantojot simplekso metodi. Programmas izstrāde simpleksās metodes izmantošanai. Galveno algoritmu blokshēmas. Interfeisa izveide, lietotāja instrukcijas programmas lietošanai.

Lineārās programmēšanas būtība. LP uzdevuma matemātiskā formulēšana un algoritms tās risināšanai, izmantojot simplekso metodi. Programmas izstrāde ražošanas plānošanai maksimālas peļņas nodrošināšanai: blokshēma, uzskaitījums, rezultāti.

kursa darbs, pievienots 11.02.2011

Ekonomisko problēmu optimizācijas teorijas jēdziens. Simpleksās metodes būtība, dualitāte lineārajā programmēšanā. Spēles teorijas un lēmumu pieņemšanas elementi, transporta problēmas risināšana. Tīkla plānošanas iezīmes un grafiku matricu piešķiršana.

Lai izmantotu prezentāciju priekšskatījumus, izveidojiet sev kontu ( kontu) Google un piesakieties: https://accounts.google.com

Slaidu paraksti:

Vienkāršāko lineārās programmēšanas uzdevumu risināšana ar grafisko metodi 17.04.2012.

Ja lineārās programmēšanas uzdevuma ierobežojumu sistēmu attēlo kā lineāru nevienādību sistēmu ar diviem mainīgajiem, tad šādu uzdevumu var atrisināt ģeometriski.

Uzdevums. Ir 14 radioreleja sakaru (RRC) kanāli un 9 troposfēras kanāli. Uz tiem nepieciešams pārsūtīt 3 veidu informāciju: A, B, C. Turklāt informācija A ir vienāda ar 600 USD, B – 3000 USD, C – 5500 USD. (informāciju var saprast kā skaitli telefona sarunas, datu pārsūtīšana utt.). Kanālu iespējas un katra kanāla apkalpošanas izmaksas ir norādītas tabulā. Ir jāatrod abu veidu iesaistīto kanālu skaits, kas nepieciešams vajadzīgās informācijas pārraidīšanai, lai ekspluatācijas izmaksas būtu minimālas.

Informācijas veidi Sakaru kanāli Nepieciešamais informācijas apjoms, vienības Troposfēras RRS A 80 40 600 B - 1000 3000 C 300 800 5500 Viena kanāla apkalpošanas izmaksas, rub. 3000 2000

ZLP risināšanas posmi: izveidojiet SDR. Konstruēt mērķa funkcijas gradienta vektoru kādā ODR piederošā punktā X 0 – (c 1 ;c 2) . Izveidojiet taisni c 1 x 1 + c 2 x 2 = h, kur h ir jebkura pozitīvs skaitlis, vēlams, lai novilktā taisne iet cauri risinājuma daudzstūrim.

Pārvietojiet atrasto taisni paralēli sev gradienta vektora virzienā, līdz taisne atstāj ODR (meklējot maksimumu) vai pretējā virzienā (meklējot minimumu). Robežpunktā mērķa funkcija sasniedz maksimumu (minimumu) vai tiek konstatēta funkcijas neierobežotība risinājumu kopai. Nosakiet funkcijas maksimālā (minimālā) punkta koordinātas un aprēķiniet funkcijas vērtību šajā punktā.

Par tēmu: metodiskā attīstība, prezentācijas un piezīmes

Šo izstrādi var izmantot kā vispārīgu nodarbību par tēmu “Nevienādību sistēmas ar diviem mainīgajiem” 9. klasē (9. algebra rediģēja Teļakovskis) un kā pārskata stundu par šo tēmu 10. klasē. ...

Materiāls paredzēts augstākā līmeņa studentiem. Programma apspriež pamata un atsauces diagrammu sastādīšanas algoritmu dažādas metodes un atrast optimālo risinājumu...

Es izstrādāju darba burtnīcu matemātikas stundai par tēmu “Lineārās programmēšanas problēmas” tāda paša nosaukuma matemātikas stundai ( paaugstināts līmenis). var izmantot nodarbībās, semināros...

Lineārā programmēšana▪ Lineārās programmēšanas problēma – 3. slaids.
▪ Ģeometriskā metode PLP risināšanai – 26. slaids.
▪ Lineārās programmēšanas uzdevums standarta formā – 32. slaids.
▪ Simpleksā metode ZLP risināšanai – 42. slaids.
▪ Gausa metode – 48 slaidi.
▪ Vienkāršā metode – 58 slaidi.
▪ Mākslīgās bāzes metode – 76 slaidi.
▪ Lineārās programmēšanas problēmu dualitāte – 87. slaids.