Popis prezentácie na jednotlivých snímkach:
1 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 Lineárne programovanie Do tejto triedy lineárne programovanie(75% problémov riešených Američanmi) zahŕňajú úlohy, v ktorých účelová funkcia Wm(x), m=1,2,...,M, obmedzenia vo forme rovnosti hk(x)=0, k=1, 2... K, a nerovnosti gj(x)>0, j=1,2,...J, sú lineárne a matematické riešenie. Možné témy úloh LP: racionálne využívanie surovín a materiálov; úlohy optimalizácie rezania; optimalizácia výrobného programu podnikov; optimálne umiestnenie a koncentrácia výroby; zostaviť optimálny plán dopravy, dopravnej prevádzky; riadenie zásob; a mnohé ďalšie patriace do oblasti optimálneho plánovania. Stanovenie problému LP (definovanie ukazovateľa výkonu, premenných úloh, nastavenie lineárnej cieľovej funkcie W(x), ktorá sa má minimalizovať alebo maximalizovať, funkčné hk(x), gj(x) a regionálne xli 2 snímka
Popis snímky:
Teória rozhodovania PetrSU, A. P. Moshchevikin, 2004 Príklad problému LP Príklad - Optimalizácia umiestnenia vedľajšej produkcie lesného hospodárstva Lesné hospodárstvo má 24 hektárov voľnej pôdy ležiacej úhorom a má záujem získať z nej príjem. Môže pestovať sadenice rýchlo rastúceho hybridného vianočného stromčeka, ktorý dosiahne zrelosť za jeden rok, alebo gobies, ktoré odvádzajú časť pôdy na pastvu. Stromy sa pestujú a predávajú v nákladoch 1 000 kusov. Na pestovanie jednej partie stromov je potrebných 1,5 ha a na kŕmenie jedného býka 4 ha. Lesný obvod môže venovať svojej vedľajšej výrobe len 200 hodín ročne. Prax ukazuje, že kultivácia, výrub, výrub a zväzovanie jednej dávky stromov trvá 20 hodín. Starostlivosť o jedného býka trvá aj 20 hodín.Lesníctvo má možnosť minúť na tento účel 6 tisíc rubľov. Ročné náklady na jednu dávku stromov majú za následok 150 rubľov. a 1,2 tisíc rubľov. pre jedného býka. Už je podpísaná zmluva na dodávku 2 býkov. Pri bežných cenách jeden vianočný stromček prinesie zisk 2,5 rubľov, jeden býk - 5 tisíc rubľov. 3 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 Vyjadrenie problému 1. Ako ukazovateľ efektívnosti je vhodné brať zisk na operáciu (ročný zisk z pôdy v rubľoch). 2. Za riadené premenné problému treba brať nasledovné: x1 - počet vykŕmených býkov za rok; x2 - počet vypestovaných šarží rýchlorastúcich vianočných stromčekov, 1000 ks. každý za rok. 3. Cieľová funkcia: 5000 x1 + 2500 x2 max, kde 5000 je čistý príjem z jedného býka, rub.; 2500 - čistý príjem z jednej dávky stromov (1 000 kusov za 2,5 rubľov). 4. Obmedzenia: 4.1. Podľa využitia územia ha: 4 x 1 + 1,5 x 2 24 4,2. Podľa rozpočtu, rubľov: 1200 x1 + 150 x2 6000 4.3. Podľa pracovných zdrojov h: 20 x1 + 20 x2 200 4.4. Záväzky zo zmluvy, ks: x1 2 4.5. Hranice oblasti: x1 0, x2 0 4 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 Grafické riešenie úlohy LP Zobrazenie na grafe čiar zodpovedajúcich nasledujúcim rovniciam, 4 x1 + 1,5 x2 = 24 1200 x1 + 150 x2 = 6000 20 x1 + 20 x2 = 200 x1 2 x 2 = 0 zatienime oblasť, v ktorej body sú splnené všetky obmedzenia. Každý takýto bod sa nazýva prípustné riešenie a množina všetkých prípustných riešení sa nazýva prípustná oblasť. Je zrejmé, že riešenie problému LP spočíva v nájdení najlepšieho riešenia v prípustnej oblasti, ktorá sa zase nazýva optimálna. V tomto príklade je optimálnym riešením realizovateľné riešenie, ktoré maximalizuje funkciu W=5000 x1 + 2500 x2. Hodnota účelovej funkcie zodpovedajúca optimálnemu riešeniu sa nazýva optimálna hodnota úlohy LP. 5 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P.Moshchevikin, 2004 Grafické riešenie úlohy LP 6 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 Grafické riešenie problému LP Vyčíslenie všetkých rohových bodov oblasti realizovateľných riešení vedie k zisteniu maximálneho príjmu vo výške 34 000 rubľov. (Š=5000x1+2500x2), ktoré môže lesníctvo vyťažiť pestovaním 3,6 býkov a 6,4 dávok vianočných stromčekov. Celočíselné metódy (napríklad enumerácia) dávajú x1=3 a x2=6, čo vedie k príjmu 30 tisíc rubľov, x1=4 a x2=5 vedie k optimálnejšiemu výsledku 32,5 tisíc rubľov, bod x1 = 3 a x2=7 vedie k podobnému výsledku. Vzhľadom na veľký rozmer skutočných praktických úloh LP sa grafická metóda používa zriedka, ale umožňuje jasne pochopiť jednu z hlavných vlastností LP - ak existuje optimálne riešenie v úlohe LP, potom aspoň jedna z vrcholov prípustnej oblasti je optimálnym riešením. Napriek tomu, že prípustná oblasť problému LP pozostáva z nekonečného počtu bodov, optimálne riešenie možno vždy nájsť cieleným vymenovaním konečného počtu jeho vrcholov. Na tejto základnej vlastnosti je založená simplexná metóda na riešenie nižšie uvažovaného problému LP. 7 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P.Moshchevikin, 2004 Riešenie problému LP v MS Excel Jednou zo vstavaných funkcií tabuľkového editora MS Excel (je potrebné zaškrtnúť políčko pri inštalácii MS Office) je "Hľadať riešenie" . Tento balík vám umožňuje rýchlo riešiť problémy lineárneho a nelineárneho programovania. 8 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 Problém LP v štandardnej forme Problém LP v štandardnom tvare s m obmedzeniami a n premennými má nasledujúci tvar: W = c1x1 + c2x2 + ... + cnxn min (max) pod obmedzenia a11x1 + a12x2 + ... + a1nxn = b1; a21x1 + a22x2 + ... + a2nxn = b2; ... am1x1 + am2x2 + ... + amnxn = bm; x10; x20;...; xn0 b10; b20;...; bm0 V maticovom tvare W = cx min (max) pri obmedzeniach Ax = b; x0; b0, kde A je matica dimenzie m*n, x je stĺpcový vektor premenných dimenzie n*1, b je stĺpcový vektor zdrojov dimenzie m*1, с je riadkový vektor odhadov Problém LP 1*n. 9 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P.Moshchevikin, 2004 Transformácia nerovností Obmedzenia nerovností možno transformovať na rovnosti zavedením takzvaných reziduálnych alebo redundantných premenných. Rovnicu z predchádzajúceho príkladu 4x1 + 1,5x2 24 je možné previesť na rovnosť pomocou nezápornej reziduálnej premennej 4x1 + 1,5x2 + x3 = 24. Premenná x3 je nezáporná a zodpovedá rozdielu pravej a ľavej strany strany nerovnosti. Podobne x1 2 možno transformovať zavedením redundantnej premennej x4: x1 - x4 = 2. 10 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 znamienkom premenných Transformácia premenných neohraničených znamienkom Premenné, ktoré nadobúdajú kladné aj záporné hodnoty, by sa mali nahradiť rozdielom dvoch nezáporných hodnôt: x = x+ - x-; x+0; x- 0. Príklad. 3x1+4x2+5x3+4x4 max 2x1+x2+3x3+5x4 5 5x1+3x2+x3+2x4 20 4x1+2x2+3x3+x4 = 15 x10; x20; x3 0; x4 = znamienko -3x1-4x2+5x3-4x4 min 2x1+x2-3x3+5x4-x5 = 5 5x1+3x2-x3+2x4+x6 = 20 4x1+2x2-3x3+x4 = 15 x10; x20; x30; x4 = znamienko; x4 = x8-x7 -3x1-4x2+5x3-4x8+4x7 min 2x1+x2-3x3+5x8-5x7-x5 = 5 5x1+3x2-x3+2x8-2x7+x6 = 20 4x1+2x8-3x3+ -x7= 15 x1,x2,x3,x5,x6,x7,x80; x4=x8 -3x1-4x2+5x3-4x4+4x7 min 2x1+x2-3x3+5x4-5x7-x5 = 5 5x1+3x2-x3+2x4-2x7+x6 = 20 4x1+2x2-3x3+x4- = 15 x1,x2,x3,x4,x5,x6,x70; x8 nahradené x4 11 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 Simplexová metóda LP Simplexová metóda je iteratívny postup riešenia úloh LP napísaný v štandardnej forme, systém rovníc, v ktorých a pomocou elementárnych operácií na maticách je redukovaný na kanonický tvar: x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. Premenné x1, x2,...,xm, ktoré vstupujú s jednotkovými koeficientmi len do jednej rovnice sústavy a s nulovými koeficientmi vo zvyšku, sa nazývajú základné. V kanonickom systéme každá rovnica zodpovedá presne jednej základnej premennej. Zvyšných n-m premenných (xm+1, ...,xn) sa nazývajú nezákladné premenné. Na uvedenie systému do kanonickej podoby možno použiť dva typy základných operácií s reťazcami: Násobenie ľubovoľnej rovnice systému kladným alebo záporným číslom. Pridanie do ľubovoľnej rovnice inej rovnice systému, vynásobené kladným alebo záporným číslom. 12 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 Simplexová metóda LP Zaznamenanie problému vo forme rovníc x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. sa zhodne zapisuje v tvare matíc 1 0 .. 0 a1,m+1 .. a1s .. a1n x1 b1 0 1 .. 0 a2,m+1 .. a2s .. a2n x2 = b2 . . ... . ... ... .. .. 0 0 .. 1 dopoludnia, m+1 .. dopoludnia .. amn xn bm 13 snímka
Popis snímky:
Teória rozhodovania PetrSU, A. P. Moshchevikin, 2004 Algoritmus simplexnej metódy 1. Vyberte počiatočné prípustné základné riešenie. Základné riešenie je riešenie získané s nulovými hodnotami nebázických premenných, t.j. xi=0, i=m+1,...,n. Bázické riešenie sa nazýva prípustné zásadité riešenie, ak hodnoty základných premenných v ňom obsiahnuté sú nezáporné, t.j. xj = bj 0, j=1,2,...,m. V tomto prípade bude mať účelová funkcia nasledujúci tvar: W=cbxb=c1b1+c2b2+...+cmbm. Vyplníme úvodnú tabuľku simplexnej metódy: 14 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P.Moshchevikin, 2004 Algoritmus simplexnej metódy 2. Vypočítajte vektor relatívnych odhadov c pomocou pravidla bodového súčinu cj = cj - cbSj, kde cb je vektor odhadov základných premenných; Sj je j-tý stĺpec koeficientov aij v kanonickom systéme zodpovedajúci uvažovanej báze. Počiatočnú tabuľku dopĺňame c - riadkom. 15 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 Algoritmus Simplexovej metódy). Riešenie sa našlo. 4. V opačnom prípade je potrebné namiesto jednej zo základných premenných zaviesť do základu nebázickú premennú xr s najväčšou hodnotou cj (pozri tabuľku). 16 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P. Moshchevikin, 2004 Algoritmus simplexnej metódy 5. Pomocou pravidla minimálneho pomeru min(bi/vzduch) určíme premennú xp, odvodenú zo základu. Ak je koeficient vzduch záporný, potom bi/vzduch=. Výsledkom je, že priesečník stĺpca obsahujúceho vstupnú nebázickú premennú xr a riadka obsahujúceho výstupnú základnú premennú xp určí pozíciu vedúceho prvku tabuľky. 6. Aplikujeme elementárne transformácie na získanie nového prijateľného základného riešenia a novej tabuľky. Výsledkom je, že otočný prvok by sa mal rovnať 1 a zvyšné prvky otočného stĺpca by mali byť nastavené na nulu. 7. Vypočítajte nové relatívne skóre pomocou pravidla skalárnej transformácie a pokračujte krokom 4. 17 snímka
Popis snímky:
Teória rozhodovania PetrSU, A.P.Moshchevikin, 2004 Príklad riešenia simplexnou metódou Príklad - Optimalizácia umiestnenia vedľajšej produkcie lesného hospodárstva 3. Cieľová funkcia: 5000 x1 + 2500 x2 max, 4. Obmedzenia: 4.1. Podľa využitia územia ha: 4 x 1 + 1,5 x 2 24 4,2. Podľa rozpočtu, rubľov: 1200 x1 + 150 x2 6000 4.3. Podľa pracovných zdrojov h: 20 x1 + 20 x2 200 4.4. Záväzky zo zmluvy, ks: x1 2 4.5. Regionálne obmedzenia: x1 0, x2 0 Zredukujme problém na štandardný tvar: 4 x1 + 1,5 x2 +x3= 24 1200 x1 + 150 x2 +x4= 6000 20 x1 + 20 x2 +x5= 200 x1 – x6= 2 x1 ... x6 0 Prvé tri rovnice majú v základnej premennej v uvedenom poradí x3, x4, x5, ale vo štvrtej chýba, pretože premenná x6 má záporný jednotkový koeficient. Na redukciu systému do kanonickej podoby používame metódu umelých premenných. x1 – x6+x7= 2, zaviedol umelú premennú x7. snímka 2 Metódy lineárneho programovania sa využívajú pri prediktívnych výpočtoch, pri plánovaní a organizovaní výrobných procesov. Lineárne programovanie je oblasť matematiky, ktorá študuje metódy na výskum a nájdenie extrémnych hodnôt niektorých lineárnych funkcií, ktorých argumenty podliehajú lineárnym obmedzeniam. snímka 3 Takáto lineárna funkcia sa nazýva cieľová funkcia a súbor kvantitatívnych vzťahov medzi premennými, ktoré vyjadrujú určité požiadavky ekonomického problému vo forme rovníc alebo nerovností, sa nazýva systém obmedzení. Slovo programovanie sa zaviedlo preto, lebo neznáme premenné zvyčajne určujú program alebo plán práce nejakého predmetu. snímka 4 Súbor vzťahov obsahujúcich účelovú funkciu a obmedzenia jej argumentov sa nazýva matematický model optimalizačného problému. ZLP sa píše vo všeobecnej forme takto: pod obmedzeniami snímka 5 Tu - neznáme, - dané konštanty Obmedzenia môžu byť dané rovnicami. Najčastejšie úlohy sú vo forme: zdroje sú obmedzené. Je potrebné určiť objemy týchto zdrojov, pri ktorých cieľová funkcia dosiahne maximum (minimum), t.j. nájsť optimálne rozloženie obmedzených zdrojov. V tomto prípade existujú prirodzené obmedzenia >0. snímka 6 V tomto prípade sa extrém cieľovej funkcie hľadá na prípustnej množine riešení určenej systémom obmedzení a všetky alebo niektoré nerovnosti v systéme obmedzení možno zapísať vo forme rovníc. Snímka 7 Stručne povedané, LLP má formu: pod obmedzeniami Snímka 8 Na zostavenie matematického modelu ZLP je potrebné: 1) označiť premenné; 2) zostaviť účelovú funkciu; 3) zapísať systém obmedzení v súlade s účelom úlohy; 4) napíšte systém obmedzení, berúc do úvahy ukazovatele dostupné v stave problému. Ak sú všetky obmedzenia problému dané rovnicami, potom sa model tohto typu nazýva kanonický. Ak je aspoň jedno z obmedzení dané nerovnosťou, potom je model nekanonický. Snímka 9 problém optimálnej distribúcie zdrojov pri plánovaní produkcie v podniku (problém sortimentu); úloha maximalizácie výkonu pre daný sortiment; problém zmesí (dávka, strava atď.); dopravná úloha; úloha racionálneho využívania dostupných kapacít; menovacia úloha. Snímka 10 Predpokladajme, že podnik vyrába rôzne produkty. Ich výroba si vyžaduje rôzne druhy zdrojov (suroviny, pracovná sila a strojový čas, pomocné materiály). Tieto zdroje sú obmedzené a v plánovacom období predstavujú konvenčné jednotky. Známe sú aj technologické koeficienty, ktoré udávajú, koľko jednotiek i-tého zdroja je potrebných na výrobu produktu j-tého typu. Nech sa zisk, ktorý podnik dostane pri predaji jednotky produktu j-tého typu, rovná. V plánovacom období sa predpokladá, že všetky ukazovatele sú konštantné. snímka 11 Je potrebné vypracovať taký plán výroby výrobkov, pri realizácii ktorého by bol zisk podniku najväčší. Ekonomický a matematický model problému snímka 12 Cieľovou funkciou je celkový zisk z predaja vyrobených produktov všetkých druhov. V tomto modeli problému je možná optimalizácia výberom najziskovejších typov produktov. Obmedzenia znamenajú, že pri žiadnom zo zdrojov jeho celková spotreba na výrobu všetkých druhov produktov nepresahuje jeho zásoby. snímka 13 Snímka 14 Predpokladajme, že sa budú vyrábať výrobky typu A, - výrobky typu B a - výrobky typu C. Potom na výrobu takého množstva výrobkov bude potrebné vynaložiť strojové hodiny frézovacieho zariadenia. Keďže celkový fond pracovného času strojov tohto typu nemôže presiahnuť 120, musí byť splnená nerovnosť snímka 15 Argumentujúc podobne, môžeme zostaviť systém obmedzení snímka 16 Teraz vytvoríme účelovú funkciu. Zisk z predaja výrobkov typu A bude 10, z predaja výrobkov typu B -14 a z predaja výrobkov typu C-12 Celkový zisk z predaja všetkých výrobkov bude Snímka 17 Dostávame sa teda k nasledujúcemu LLP: Medzi všetkými nezápornými riešeniami systému nerovností je potrebné nájsť také, pre ktoré má účelová funkcia maximálnu hodnotu. Snímka 18 Produkty mliekarenského závodu sú mlieko, kefír a kyslá smotana balené v nádobách. Na výrobu 1 tony mlieka je potrebných 1010,1010, kefíru a kyslej smotany 9450 kg mlieka. Zároveň náklady na pracovný čas pri rozliatí 1 tony mlieka a kefíru sú 0,18 a 0,19 strojových hodín. Na obale 1 tony kyslej smotany sú špeciálne stroje obsadené 3,25 hodiny. Snímka 19 Celkovo môže závod použiť na výrobu plnotučných mliečnych výrobkov 136 000 kg mlieka. Hlavné zariadenie môže byť obsadené na 21,4 strojových hodín a stroje na balenie kyslej smotany na 16,25 hodiny. Zisk z predaja 1 tony mlieka, kefíru a kyslej smotany je 30, 22 a 136 rubľov. Závod musí denne vyprodukovať minimálne 100 ton mlieka vo fľašiach. Neexistujú žiadne obmedzenia na výrobu iných produktov. Snímka 20 Je potrebné určiť, aké produkty a v akom množstve má závod denne vyrábať, aby bol zisk z jeho predaja maximalizovaný. Vytvorte matematický model problému. snímka 21 Nechajte rastlinu vyrábať tony mlieka, tony kefíru a tony kyslej smotany. Potom potrebuje kg mlieka. Keďže závod nemôže spotrebovať viac ako 136 000 kg mlieka denne, musí sa uspokojiť nerovnosť snímka 22 Lehoty na balenie mlieka a kefíru a na balenie kyslej smotany. Keďže denne sa musí vyprodukovať aspoň 100 ton mlieka. Z hľadiska ekonomiky snímka 23 Celkový zisk z predaja všetkých produktov sa rovná rubľom. Dostávame sa teda k nasledujúcemu problému: pod obmedzeniami Keďže cieľová funkcia je lineárna a obmedzenia sú dané systémom nerovností, tento problém je LLP. snímka 24 Existujú dva typy produktov obsahujúcich živiny (tuky, bielkoviny atď.) Snímka 25 snímka 26 Celkové náklady na diétu v rámci obmedzení, berúc do úvahy požadované minimum živín Snímka 27 Matematické vyjadrenie problému: zostavte každodennú stravu, ktorá vyhovuje systému obmedzení a minimalizuje cieľovú funkciu. Vo všeobecnosti skupina problémov o zmesiach zahŕňa problémy nájsť najlacnejšiu sadu určitých východiskových materiálov, ktoré poskytujú zmes s požadovanými vlastnosťami. Výsledné zmesi musia obsahovať n rôznych zložiek v určitých množstvách a samotné zložky sú zložkami m východiskových materiálov. Snímka 28 Zavedme si zápis: -množstvo j-tej látky obsiahnutej v zmesi; -cena materiálu typu j; je minimálny požadovaný obsah i-tej zložky v zmesi. Koeficienty ukazujú špecifickú hmotnosť i-tej zložky v jednotke j-tého materiálu Snímka 29 Cieľovou funkciou sú celkové náklady na zmes a funkčné obmedzenia sú obmedzenia obsahu zložiek v zmesi: zmes musí obsahovať zložky v objemoch, ktoré nie sú menšie, ako je špecifikované. snímka 30 V odevnej továrni sa látka môže strihať niekoľkými spôsobmi, aby sa vyrobili požadované kusy odevov. Nechajte si vyrobiť i-tý typ dielov s j-tým variantom rezania a množstvo odpadu pri tomto variante rezania je odpad. Vytvorte matematický model problému. Snímka 31 Riešenie. Predpokladajme, že podľa j-tého variantu sa strihajú stovky látok. Keďže pri strihaní látky podľa j-tej možnosti sa získavajú diely i-tého typu, pre všetky možnosti strihu z použitých látok bude celkové množstvo odpadu za všetky možnosti strihu Snímka 35 Def.4. Hlavná alebo kanonická LLP je úloha, ktorá spočíva v určení hodnoty cieľovej funkcie za predpokladu, že systém obmedzení je prezentovaný ako systém rovníc: snímka 36 Ak je pre pohodlie alebo zmysel úlohy potrebné prepnúť z jednej formy záznamu na inú, postupujte nasledovne. Ak potrebujete nájsť minimum funkcie, potom môžete prejsť k nájdeniu maxima vynásobením cieľovej funkcie číslom (-1). Obmedzenie typu nerovnosti možno previesť na rovnosť pridaním nezápornej dodatočnej premennej na jej ľavú stranu a obmedzenie typu nerovnosti možno previesť na obmedzenie rovnosti odčítaním ďalšej nezápornej premennej od jej ľavej strany. Snímka 41 Návrh podpory sa nazýva nedegenerovaný, ak obsahuje m kladných komponentov. V opačnom prípade sa nazýva degenerovaný. Plán, v ktorom má cieľová funkcia LLP svoju maximálnu (minimálnu) hodnotu, sa nazýva optimálny.
Zobraziť všetky snímky Úvod Lineárne programovanie ako odvetvie operačného výskumu má takmer štyridsaťročnú históriu. Zavedenie výpočtovej techniky dalo významný impulz výskumu v tejto oblasti matematiky. Bolo vyvinutých množstvo algoritmov na riešenie problémov lineárneho programovania a v nasledujúcich rokoch boli vytvorené programy a softvérové balíky najmä pre veľké počítače. Prevažná časť literatúry o lineárne programovanie u nás vyšlo v 60. - 70. rokoch. Výskum v tejto oblasti (tak teoretický, ako aj aplikovaný) v súčasnosti pokračuje. Metódy lineárneho programovania sa ukázali ako veľmi účinné pri riešení niektorých problémov z oblasti operačného výskumu. Slovo „programovanie“ chápeme ako plánovanie, a to určuje charakter uvažovaných aplikácií. Hlavné myšlienky lineárneho programovania vznikli počas druhej svetovej vojny v súvislosti s hľadaním optimálnych stratégií pri vedení vojenských operácií. Odvtedy našli široké uplatnenie v priemysle, obchode a administratíve – lokálne aj celoštátne. Tieto metódy môžu vyriešiť mnohé (aj keď nie všetky) problémy súvisiace s efektívnym využívaním obmedzených zdrojov. Matematické metódy a modely sú známe, rozšírené a používané pod rôznymi názvami - matematické metódy v rozhodovaní; metódy operačného výskumu; ekonomické a matematické metódy; metódy ekonomickej kybernetiky; metódy optimálneho riadenia, aplikovaná matematika v ekonomike a organizácii výroby a pod. Operačný výskum je vedná disciplína, ktorá sa zaoberá vývojom a praktickou aplikáciou metód pre čo najefektívnejšie riadenie rôznych organizačných systémov. Riadenie akéhokoľvek systému je implementované ako proces, ktorý sa riadi určitými zákonmi. Ich znalosť pomáha určiť podmienky potrebné a postačujúce na realizáciu tohto procesu. Na to je potrebné kvantifikovať a zmerať všetky parametre charakterizujúce proces a vonkajšie podmienky. Účelom operačného výskumu je preto kvantitatívne zdôvodnenie rozhodnutí o organizácii riadenia. Účelom každého modelovania je študovať objekt najskôr kvalitatívne a potom, ako sa informácie hromadia a model sa vyvíja, na čoraz presnejších kvantitatívnych úrovniach. Tieto úvahy možno ilustrovať na jednoduchom príklade. Existovala (a stále existuje) metóda „teórie pravdepodobnosti“ ako široká trieda matematických modelov pracujúcich s pojmami „pravdepodobnosť“, „náhodná udalosť“, „náhodná premenná“, „matematické očakávanie (stredná hodnota) náhodnej premennej. ", "rozptyl (rozptyl)" a pod. Na hranici XIX a XX storočia. objavuje sa nový objekt - komutovaný telefónny komunikačný systém, s ktorým sú spojené pojmy "žiadosť o pripojenie", "odmietnutie", "čakacia doba na spojenie", "prepnutie" a ďalšie charakteristiky systému. V 20. rokoch. A. K. Erlang spojil túto metódu a objekt; v dôsledku toho bol vytvorený matematický pravdepodobnostný model procesov v komutovaných telefónnych sieťach, ktorý pracuje s pojmami "tok objednávky", "priemerná doba čakania", "priemerná dĺžka fronty na obsluhu", "rozptyl čakacej doby", "porucha" pravdepodobnosti“ atď. Ďalší vývoj tohto vedeckého smeru ukázal plodnosť koncepčného základu tohto modelu, jeho široké konštrukčné možnosti. Z modelu sa vyvinula metóda na štúdium zložitých systémov – „teória radenia“, ktorej terminológia a konceptuálny základ boli abstrahované z asociácií s telefónnymi sieťami a nadobudli všeobecný teoretický charakter. A teraz je možné vytvoriť nové modely aplikáciou teórie radenia na iné objekty (výrobné procesy, počítačové operačné systémy, dopravné toky atď.). Na jednej strane je teda metóda definovaná, ak sa vytvorí homogénna množina modelov, t. j. spôsoby uvažovania rôznych objektov v jednom aspekte, a na druhej strane je objekt známy tým hlbšie, čím viac modelov objektov sa vyvíja. . Duálna povaha modelu zároveň vedie k dualizmu konceptuálnej bázy modelovania, ktorá zahŕňa všeobecné (z „metódy“) a špecifické (z „objektu“) koncepty. Operačný výskum je súbor aplikovaných matematických metód používaných na riešenie praktických organizačných (aj ekonomických) problémov. Ide o komplexnú vednú disciplínu. Rozsah problémov, ktoré skúma, nie je dostatočne definovaný. Niekedy je operačný výskum chápaný veľmi široko, vrátane množstva čisto matematických metód, inokedy, naopak, veľmi úzko – ako praktická technika na riešenie striktne definovaného zoznamu problémov pomocou ekonomických a matematických modelov. Hlavnou metódou operačného výskumu je systematická analýza účelových akcií (operácií) a objektívne (najmä kvantitatívne) porovnávacie hodnotenie možných výsledkov týchto akcií. Medzi najdôležitejšie triedy problémov v operačnom výskume patria problémy riadenia zásob, prideľovania a prideľovania zdrojov (problémy s distribúciou), problémy s radením, problémy s výmenou zariadení, objednávaním a koordináciou (vrátane teórie plánovania), kontradiktórne (napríklad hry), vyhľadávacie problémy a pod. Medzi používané metódy patrí matematické programovanie (lineárne, nelineárne atď.), diferenciálne a diferenčné rovnice, teória grafov, Markovove procesy, teória hier, teória (štatistických) riešení, teória rozpoznávania vzorov a množstvo ďalších. Predpokladá sa, že operačný výskum vznikol v predvečer druhej svetovej vojny, keď sa v Anglicku na radarovej stanici vytvorila skupina špecialistov na riešenie technických problémov pomocou matematiky. Zamerali sa na porovnávanie efektívnosti spôsobov riešenia problémov, hľadanie optimálneho riešenia. Účasť v tejto skupine predstaviteľov rôznych odborností predurčila komplexný, alebo, ako sa dnes hovorí, systematický prístup. V súčasnosti týmto smerom pracujú stovky výskumných inštitúcií a skupín v desiatkach krajín. Spoločnosti pre operačný výskum organizuje Medzinárodná federácia (IFORS). Ruskí vedci L.V. Kantorovič, N.P. Buslenko, E.S. Wentzel, N.N. Vorobyov, N.N. Moiseev, D.B. Yudin a mnohí ďalší. K formovaniu a rozvoju operačného výskumu významne prispeli zahraniční vedci R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman a ďalší. Metódy operačného výskumu, ako každá matematická metóda, vždy do určitej miery zjednodušujú problém, odrážajú nelineárne procesy s lineárnymi modelmi, stochastické systémy s deterministickými atď. Preto by sa hodnota kvantitatívnych metód operačného výskumu nemala preháňať, ani to nepodceňovať. , odvolávajúc sa na príklady neúspešných rozhodnutí. Známa je paradoxná definícia, ktorú podal významný americký špecialista v tejto oblasti T. A. Saaty: „Operačný výskum je umenie dávať slabé odpovede na praktické otázky, na ktoré sa inými spôsobmi odpovedá ešte horšie.“ CENTRÁLNA MEDZIREGIONÁLNA VYSOKÁ ŠKOLA PRIEMYSELNÝCH TECHNOLÓGIÍ A PODNIKANIA Súhlasím námestník riaditeľ pre vzdelávanie « » 200 G . CVIČENIE pre návrh kurzu v predmete "Matematické metódy" Študent: Sergeev Evgeny Anatolyevich. Téma projektu: "Lineárne programovanie, riešenie úloh simplexovou metódou". VYSVETLIVKA Úlohy a ich riešenie: Úloha jedna: Vyriešte simplexnú úlohu metódou: F = 2X1 +3X2 → max 3.1.2 Druhá úloha: Spoločnosť vyrába dva druhy produktov. Druhy surovín, ich zásoby, miery spotreby surovín za r. e. každý typ výrobku, zisk z výroby z predaja výrobkov je uvedený v tabuľke: 3.1.3. Úloha tri: Spoločnosť vyrába 3 druhy produktov, pričom používa 3 druhy surovín. Zásoby surovín, miery ich spotreby a zisk z predaja každého produktu sú uvedené v tabuľke: Ako by sa mala plánovať výroba, aby sa maximalizoval zisk? 3.1.4. Úloha štvrtá: Na výrobu 4 druhov výrobkov sa používajú 3 druhy surovín. Zásoby surovín, miery ich spotreby a zisk z predaja každého produktu sú uvedené v tabuľke: Ako by sa mala plánovať výroba, aby sa maximalizoval zisk? 3.
Záver 4.
Bibliografia predseda cyklokomisie/ Baranov V.A. Projektový manažér kurzu/ Karpushkin A.G. Dátum vydania úlohy: Dátum ukončenia: « » 2007 « » 2007 JEDNODUCHÁ METÓDA Simplexovú metódu prvýkrát navrhol americký vedec J. Danzig v roku 1949, avšak už v roku 1939 myšlienky metódy vyvinul ruský vedec L V. Kantorovič. Simplexová metóda, ktorá umožňuje riešiť akýkoľvek problém lineárneho programovania, je univerzálna. V súčasnosti sa používa na počítačové výpočty, ale jednoduché príklady pomocou simplexovej metódy je možné riešiť aj ručne. Na implementáciu simplexovej metódy - postupného zlepšovania riešenia - je potrebné zvládnuť tri hlavné element: Spôsob, ako určiť akékoľvek počiatočné prípustné základné riešenie problému; Pravidlo prechodu na najlepšie (presnejšie nie najhoršie) riešenie; Kritérium kontroly optimálnosti nájdeného riešenia. Pre použitie simplexnej metódy je potrebné problém lineárneho programovania zredukovať na kanonickú formu, t.j. systém obmedzení musí byť prezentovaný vo forme rovníc. Bežné jordánske výnimky Uvažujme sústavu m lineárnych rovníc s n neznámymi a11 x1 + a12 x2 + … + a1n xn = b1, am1 x1 + am2 x2 + … + amn xn = bm. Tento systém zapisujeme vo forme tabuľky a11 … a1j … a1n ……………….. ai1 … aij … ain ……………….. am1 … amj … amn Krok obyčajnej eliminácie Jordánska (OJI) vykonaný na danej tabuľke s rozlišovacím prvkom aij ≠ 0 s rozlišovacím riadkom I a s rozlišovacím stĺpcom j je operácia riešenia rovnice. bi = ai1 x1 + ai2 x2 + … + aij xj + … + ain xn vzhľadom na xj, dosadenie tohto riešenia do pôvodného systému a zápis novozískaného systému vo forme novej tabuľky. Je ľahké skontrolovať, ako bude nový stôl vyzerať b11 b12 … a1j … b1n b21 b22 … a2j … b2n ……………….. Ai1 –ai2 … 1… -ain ……………….. bm1 bm2 … amj … bmn kde brs = ars aij - arj ais (i ≠ r, j ≠ s), a všetky prvky tabuľky musia byť rozdelené aij . Jeden krok Jordan Elimination (JJI) teda transformuje pôvodnú tabuľku na novú tabuľku podľa schémy pozostávajúcej z nasledujúcich 5 pravidiel: 1) aktivačný prvok sa nahradí jedným 2) zostávajúce prvky rozlišovacieho stĺpca j zostávajú nezmenené. 3) zvyšné prvky rozlišovacieho reťazca i menia iba ich znamienka. 4) zostávajúce prvky brs sa vypočítajú podľa vzorca brs = ars aij - arj ais 5) všetky prvky novej tabuľky sú rozdelené rozlišovacím prvkom aij. Príklad 1. Pre tabuľku Jordanove výnimky umožňujú prejsť z náhodne vybratého karteziánskeho systému súradnicových rovín k novému systému, v ktorom súradnice bodov predstavujú ich odchýlky od zaujímavejšieho systému rovín pre konkrétny problém. Upravené jordánske výnimky Ak je pôvodný systém rovníc ai1 x1 + ai2 x2 + … + ain xn = bi, kde i = 1,m, napíšte ako -ai1 (-x1) - ai2 (-x2) - ... - ain (-xn) = bi a urob si stôl ktorý sa získava podľa pravidiel 1 - 5 GOG s jedinou zmenou, že pravidlá 2 a 3 menia roly: 1) zostávajúce prvky permisívneho reťazca zostávajú nezmenené 2) zostávajúce prvky rozlišovacieho stĺpca menia iba svoje znamienka Zvážte systém 2X1 + 3X2 - 5X3 = 16 = b1, 3X1 – 2X2 + 4X3 = 36 = b2, 5X1 + 7X2 - 11X3 = 44 = b3. Zapíšme si to vo forme tabuľky Extrémy lineárnej funkcie Zoberme si všeobecný problém lineárneho programovania. Výpočtové metódy LP sú založené na nasledujúcej základnej vete. Veta. Ak má problém lineárneho programovania optimálne riešenie (vždy v ohraničenej oblasti a v neohraničenej oblasti v závislosti od ohraničenosti funkcie Z), potom sa zhoduje aspoň s jedným z riešení podpory sústavy reštriktívnych rovníc. Podľa tejto vety namiesto štúdia nekonečnej množiny realizovateľných riešení, aby sa medzi nimi našlo požadované optimálne riešenie, je potrebné študovať len konečný počet podporných riešení. Táto veta hovorí, že existuje aspoň jedno optimálne riešenie podpory, avšak v problémoch môže byť niekoľko optimálnych riešení podpory (alternatívne optimum). Preto je schematický diagram na riešenie problémov lineárneho programovania nasledujúci: 1. Pomocou ZhI nájdeme všetky podporné riešenia systému. a11 x1 + a12 x2 + … + a1n xn = b1 , ……................... ak1 x1 + ak2 x2 + … + akn xn = bk , ak+1,1 x1 + ak+1,2 x2 + … + ak+1n xn ≤ bk+1 , ……................... am1 x1 + am2 x2 + … + amn xn ≤ bm . 2. Vypočítajte pre každý z nich hodnotu funkcie Z určenú pomerom. Z = c1 x1 + c2 x2 + … + cn xn. 3. Vyberieme z nich extrém Z. Je potrebné poznamenať, že môže existovať veľmi veľký počet referenčných roztokov, takže je potrebné vykonať usporiadaný zoznam referenčných roztokov, čím sa dosiahne každý krok monotónnej zmeny funkcie Z. Takáto myšlienka postupného zlepšovania riešenia je zakotvená v hlavnej výpočtovej metóde na riešenie problémov lineárneho programovania, nazývanej simplexná metóda. Simplexná metóda založená na úplných tabuľkách Vyjadrenie problému určenia optimálneho sortimentu produktov Podnik môže vyrábať dva druhy výrobkov A a B, ktoré majú obmedzené zdroje železného a oceľového materiálu na ich výrobu v množstve 350 a 392 kg a zariadenia v množstve 408 strojných hodín. Údaje prezentované vo forme tabuľky charakterizujú náklady každého z troch typov zdrojov uvedených na výrobu jedného produktu A a B. Je potrebné určiť, koľko produktov A a B by mal podnik vyrobiť, aby dosiahol čo najväčší zisk. Zavádzame požadované neznáme X1 a X2, ktoré označujú počet produktov A a B, ktoré by mal podnik vyrobiť. Potom môže byť problém matematicky formulovaný nasledovne. Medzi množinou nezáporných riešení sústavy nerovníc 14X1 + 5X2 ≤ 350, (1.1) 14X1 + 8X2 ≤ 392, 6X1 + 12X2 ≤ 408, nájsť riešenie, pre ktoré je funkcia Z = 10 x 1 + 5 x 2 dosiahne svoju najvyššiu hodnotu. Geometrické riešenie úlohy Najprv zostrojme doménu realizovateľných riešení zodpovedajúcich sústave nerovností. Aby ste to dosiahli, nahraďte každú z nerovností rovnosťou 14X1 + 5X2 = 350, (1. priamka), 14X1 + 8X2 = 392, (2. riadok), 6X1 + 12X2 = 408, (3. priamka), budovanie hraničnej čiary. Ak vezmeme do úvahy, že X1 ≥ 0 a X2 ≥ 0, dostaneme zatienenú časť roviny, ktorá tvorí mnohouholník riešení OABCD (obr. 1). Potom zostrojíme úrovňovú čiaru 10X1 + 5X2 = 0 a vektor (10; 5), ktoré sú navzájom kolmé. Je ľahké ukázať, že vektor udáva smer najväčšieho nárastu lineárnej funkcie. Naozaj Z0 \u003d 10X10 + 5X20 \u003d 10 * 0 + 5 * 0 \u003d 0, ZA \u003d 10X1A + 5X2A \u003d 10 * 0 + 5 * 34 \u003d 170, ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 atď. Zo všetkých čiar úrovne vyberieme dve, z ktorých jedna prechádza bodom 0 a dáva minimálnu hodnotu funkcie Z a druhá prechádza bodom C a funkcia Z pre ňu nadobúda maximálnu hodnotu. Tieto čiary úrovne sa nazývajú referenčné čiary. Ryža. 1 Bod C je tvorený prvou a druhou čiarou. Preto riešenie sústavy rovníc 14Xl + 5X2 = 350, 14X1 + 8X2 = 392, nájsť súradnice bodu C X1 = 20, X2 = 14, zatiaľ čo Zmax \u003d 10 * 20 + 5 * 14 \u003d 270 rubľov. Maximálny zisk je teda 270 rubľov. dostane, ak podnik vyrobí 20 výrobkov typu A a 14 výrobkov typu B. Nájdenie maxima lineárnej funkcie Simplexová metóda na riešenie problémov lineárneho programovania je s určitými doplnkami založená na predtým analyzovanej metóde postupných eliminácií, čo je súbor vhodných výpočtových algoritmov založených na sekvenčnej aplikácii identických (simplexných) transformácií sústavy rovníc. Pridanie na ľavú stranu nerovností 14X1 + 5X2 ≤ 350, 14X1 + 8X2 ≤ 392, 6X1 + 12X2 ≤ 408, nejaká nezáporná hodnota Yj ≥ 0 (i = 1, 2, 3), (1,2) nazývané vyrovnávacia alebo základná premenná, premieňame ich na rovnice: X1 + 5X2 + Y1 Navyše je možné ukázať, že každé riešenie sústavy nerovníc (1.1) zodpovedá jedinečnému riešeniu sústavy rovníc (1.3) a nerovníc (1.2) a naopak. Každá z premenných Y1, Y2, Y3 je zahrnutá len v jednej rovnici a závisí od premenných X1 a X2, ktoré nazývame voľné. Sústava (1.3) zodpovedá počiatočnému prípustnému zásaditému riešeniu X1 = X2 = 0; Y1 = 350; Y2 = 392; Y3 = 408 a Z = 0. Vykonáme prvú identickú transformáciu sústavy rovníc (1.3). Vyberáme rozlišovací stĺpec zodpovedajúci najmenšiemu zápornému prvku v riadku Z, pretože sa teoreticky zistilo, že za inak rovnakých podmienok možno očakávať väčší nárast funkcie Z. . Na priesečníku vybraného stĺpca a riadku je číslo rozlíšenia. Prvú rovnicu vydelíme číslom rozlíšenia a výslednú rovnicu zapíšeme. Vynásobením tejto rovnice 14, 6 a -10 a odčítaním od 2., 3. a 4. rovnice sústavy (1.3), v tomto poradí, dostaneme nasledujúcu sústavu (1.4): X2 + 1/4 Y1 = 25, X2 - 6/14 Y1 + Y3 Takáto identická transformácia, pri ktorej sa výber rozlišovacieho čísla uskutoční podľa uvedeného pravidla, sa bude nazývať simplexná transformácia. Simplexná transformácia sa teda vykonáva podľa nasledujúceho pravidla: 1. Vyberte aktivačný stĺpec zodpovedajúci najmenšiemu zápornému prvku v Z - riadku. 2. Vyberie sa rozlišovací riadok, ktorý zodpovedá najmenšiemu kladnému pomeru prvkov pravej strany rovníc k príslušným prvkom rozlišovacieho stĺpca. Na priesečníku rozlišovacieho stĺpca a rozlišovacieho riadku je rozlišovacie číslo. 3. Prvky permisívneho reťazca sú delené permisívnym číslom. 4. Prvky všetkých ostatných riadkov sa vypočítajú podľa vzorca: Zo sústavy (1.4) nájdeme druhé prípustné zásadité riešenie Х2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, čo zodpovedá novej zvýšenej hodnote funkcie Z = 250. Proces postupných simplexných transformácií je teda procesom postupného zlepšovania riešenia. kde: 1. Ak je v Z - línii aspoň jeden negatívny prvok a a) v rozlišovacej kolóne je aspoň jeden kladný prvok, potom je možné riešenie zlepšiť; b) ak rozlišovací stĺpec neobsahuje kladné prvky, potom funkcia Z rastie donekonečna. 2. Ak sú všetky prvky v Z - riadku nezáporné, tak bolo dosiahnuté optimálne riešenie. Toto sú dostatočné podmienky pre existenciu optimálneho plánu riešenia. V systéme (1.4) je koeficient na X2 v Z - riadku záporný, takže druhý stĺpec bude riešiť. Zistili sme, že druhý riadok bude permisívny. Ďalej vykonáme simplexnú transformáciu systému (1.4) podľa uvedeného pravidla: X1 + 8/42 Y1 - 5/42 Y2 = 20, X2 - 1/3 Y1 + 1/3 Y2 = 14, 20/7 Y1 – 23/7 Y2 + Y3 = 120, 10/42 Y1 + 20/42 Y2 + Z = 270, (1,5) Keďže všetky prvky v Z-riadku sú nezáporné, tento plán je optimálny. V tomto prípade Yl = Y2 = 0; X1 = 20; X2 = 14 a Zmax = 270. Vykonávanie simplexných transformácií je spojené s namáhavými a často dosť ťažkopádnymi výpočtami. Tieto výpočty je možné výrazne zjednodušiť použitím takzvaných simplexných tabuliek na riešenie problémov. Každá simplexná transformácia systému je redukovaná na prechod z jedného simplexného tabla do druhého. Podľa pôvodnej sústavy rovníc (1.3) zostavíme prvú simplexnú tabuľku (tab. 1.1). Tabuľka 1.1 Prvý stĺpec je stĺpec základných premenných, druhý stĺpec obsahuje voľné koeficienty pravej strany rovníc (1.3), prvý riadok obsahuje všetky premenné, posledný stĺpec je riadiaci stĺpec a koeficienty v ňom sa rovnajú súčet všetkých koeficientov v riadku. Z tabuľky. 1.1 máme prvé prípustné riešenie sústavy (1.3) X1 = X2 = 0, Y1 = 350, Y2 = 392, Y3 = 408, Z = 0, čo zodpovedá vrcholu O (0,0) mnohouholníka realizovateľných riešení OABCD (obr. 1). Prechod do druhej simplexnej tabuľky (tabuľka 1.2) sa vykonáva podľa pravidla uvedeného v tomto odseku pre simplexné transformácie sústav rovníc, pričom rozlišovacia premenná X1 ide do bázy namiesto rozlišovacej premennej Y1. 1.2. Tabuľka 1.2 Po dokončení tabuľky 1.2 je potrebné skontrolovať správnosť jeho vyplnenia, na čo zosumarizujeme koeficient po riadkoch a tento súčet sa musí rovnať koeficientom v príslušných bunkách kontrolného stĺpca. Z tabuľky. 1.2 druhé platné riešenie by bolo X1 = 25, X2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 a Z = 250. Je ľahké vidieť, že táto tabuľka zodpovedá systému (1.4) a referenčnému roztoku X1 = 25, X2 = 0 zodpovedá vrcholu D(25,0) mnohouholníka riešenia. Keďže v Z-riadku je negatívny prvok, vylepšujeme riešenie, pre ktoré zostavíme simplexnú tabuľku. 1.3. Stôl 1. 3
* Poznámka. Pre jednoduchosť výpočtov treba pamätať na to, že v novej tabuľke sú na mieste prvkov povoľujúceho stĺpca (okrem povoľujúceho prvku) nuly. Ak sú v rozlišovacom riadku nuly, príslušné stĺpce sa prenesú do novej tabuľky bez zmeny: Keďže v línii Z nie sú žiadne negatívne prvky, toto riešenie bude optimálne. Tab. 1.3 zodpovedá sústave rovníc (1.5) a optimálnemu riešeniu Х1 = 20, X2 = 14 a Zmax = 270 a vrchol C (20,14) mnohouholníka prípustných riešení OABCD. Takéto podlhovasté tabuľky obsahujúce všetky premenné v prvom riadku vám vďaka prítomnosti kontrolného stĺpca umožňujú kontrolovať správnosť vypĺňania tabuliek a vyhnúť sa aritmetickým chybám. Simplexná metóda založená na skrátených tabuľkách Zvážte sústavu rovníc (1.3) a zapíšte ju do tvaru tabuľky 1.4 Tabuľka 1.4 Do prvého stĺpca napíšeme základné premenné (BP), do prvého riadku voľné premenné (SP). Ďalej sa prechod na novú tabuľku 1.5 vykoná podľa pravidla: 1) vymeňte SP a BP 2) namiesto rozlišovacieho prvku je k nemu recipročná hodnota 3) prvky rozlišovacej čiary delíme rozlišovacím číslom 4) prvky rozlišovacieho stĺpca rozdelíme rozlišovacím stĺpcom a zmeníme znamienko 5) zostávajúce prvky sa nachádzajú ako v kapitole „Hľadanie maxima lineárnej funkcie“, pravidlo 4 (pravidlo obdĺžnikov pre OGI). Dostaneme tabuľku 1.5. Tabuľka 1.6 Dostali sme optimálny plán Zmax = 270 s X1 = 20, X2 = 14 a ukázalo sa, že zdroje zariadení presahujú 120 strojových hodín. Riešenie úlohy lineárneho programovania Nájdite maximálnu cieľovú funkciu pod obmedzeniami 14x + 5r ≤ 350 Riešenie problému pomocou programu Microsoft Excel. Hodnotám premenných x a y priraďme A3 a B3. Do bunky C4 zadajte cieľovú funkciu V bunkách A7:A9 uvádzame ľavé časti obmedzení a v bunkách B7:B9 - správne časti obmedzení. Potom vyberte príkaz servis, Hľadanie riešenia(Nástroje, Riešiteľ) a vyplňte dialógové okno, ktoré sa otvorí Hľadanie riešenia ( Riešiteľ), ako je znázornené na obr. 2. Po stlačení tlačidla Bežať Otvorí sa okno (Riešiť). Výsledky hľadania riešenia(Solver Results), ktorý hlási, že sa našlo riešenie (obr. 3). Ryža. 2. Hľadanie riešenia Ryža. 3. Výsledky hľadania riešenia Geometrické riešenie úlohy pomocou programu MATHCAD 2000. 14x + 5r = 350 (-14/5)x + 70 y1(x):= (-14/5)x + 70 7x + 4y = 196 (-7/4)x + 49 y2(x):= (-7/4)x + 49 x + 2y = 68 (-1/2)x + 34 y3(x):= (-1/2)x + 34 10x + 5y = C -2x + (1/5)C y4(x):= -2x + (1/5)C Ryža. 4. Nájsť (x, y) → (20, 14) f(x, y): = 10x + 5y fmin := f(20; 14) Analytické riešenie problému pomocou programu MATHCAD 2000. Analytické riešenie problému v MathCAD je oveľa jednoduchšie. Z(x, y): = 10x + 5y 14x + 5x ≤ 360 M:=Maximalizovať(z,x,y) M=(20,14)Z(M0,M1)=270 Problém maximalizácie lineárnej funkcie v prítomnosti záporných voľných koeficientov Nájdite maximum lineárnej funkcie pod obmedzeniami X1 – X2 ≤ 3, 2X1 – 3X2 ≤ 6, X1 ≥ 0, X2 ≥ 0. Systém zapíšeme do formulára Y1 = -X1 + X2 + 3 ≥ 0 Y2 = X1 + X2 - 5 ≥ 0 Y3 = -2X1 + 3X2 + 6 ≥ 0 Y4 = -X2 + 6 > 0 Urobme si stôl. Pokračujeme v práci s druhým riadkom, pretože negatívny prvok nezmizol. Vyrábame SHMZhI s rozlišovacím prvkom -2. Dostávame stôl. Problém minimalizácie lineárnej funkcie Redukcia minimalizačného problému na problém maximalizácie lineárnej funkcie Uvažovali sme o riešení úlohy hľadania maxima lineárnej funkcie simplexnou metódou W = c1 x1 + c2 x2 + … + cn xn. V mnohých ekonomických problémoch je však potrebné nájsť minimum lineárnej funkcie. Na to stačí dať W = -Z = -c1 x1 - c2 x2 - ... - cn xn a vyriešiť problém maximalizácie výslednej funkcie W pri vhodných obmedzeniach. Keďže je jasné, že Minimalizovať lineárnu funkciu pri plnení obmedzení 7X1 + 2X2 ≥ 14, 5X1 + 6X2 ≤ 30, 3X1 + 8X2 ≥ 24, X1 ≥ 0, X2 ≥ 0. Geometrické riešenie úlohy na (obr. 5) a zodpovedá optimálnemu riešeniu v bode C (48/11, 15/11) a zároveň Zmin = -21/11. Obr 5. Geometrické riešenie úlohy Zavedením nivelačných premenných Yi ≥ 0 a funkcie W = -Z = 2X1 - 5X2 → max zapíšeme úlohu do tvaru. Y1 = 7X1 + 2X2 - 14, Y2 = -5X1 - 6X2 + 30, Y3 = 3X1 + 8X2 - 24, Tento systém zapisujeme vo forme tabuľky. Zbavíme sa záporného voľného člena v riadku Y1, čím SHMZhI s rozlišovacím prvkom „-50/8“, dostaneme tabuľku. Keďže v riadku W a v stĺpci 1 nie sú žiadne záporné prvky, dostali sme optimálne riešenie X1 = 48/11, X2 = 15/11, Wmax - 21/11 alebo Zmin = -Wmax = -21/11 , Praktická časť 1.
Vyriešte problém pomocou simplexnej metódy. X1 + 3X2 ≤ 300 F = 2X1 + 3X2 → max. Riešenie X1 + 3X2 + X3 = 300 F - 2X1 - 3X2 = 0 X1 + X2 + X4 = 150 Odpoveď: X1 = 75; X2 = 75; X3 = 0; X4 = 0. Úloha číslo 1. Spoločnosť vyrába dva druhy produktov. Druhy surovín, ich zásoby, miery spotreby surovín na kub. každý druh výrobku, zisk výroby z predaja výrobkov sú uvedené v tabuľke. Riešenie 2X1 + 2X2 ≤ 17 X1 + 3X2 + X3 = 20 F - 2X1 - X2 = 0 2X1 + X2 + X4 = 10 2X1 + 2X2 + X5 = 17 Odpoveď: X1 = 5; X2 = 0; X3 = 15; X4 = 0; X5 = 7. Úloha číslo 2. Spoločnosť vyrába tri druhy výrobkov, pričom využíva tri druhy surovín. Zásoby surovín, ich spotreba a zisk z predaja každého produktu sú uvedené v tabuľke. Ako plánovať výrobu, aby zisk podniku bol čo najväčší? Riešenie 2X1 + 3X2 + 7X3 ≤ 1250 F = 41X1 + 35X2 + 96X3 → max. 5X1 + 3X2 ≤ 900 2X1 + 3X2 + 7X3 + X4 = 1250 F - 41X1 - 35X2 - 96X3 = 0 X1 + X2 + X5 = 250 5X1 + 3X2 + X6 = 900 X1 + 3X2 ≤ 20 F = 2X1 + X2 → max 2X1 + 2X2 ≤ 17 (-1/3)(-1/3)(2/3) Odpoveď: X1 = 0; X2 = 29/5; X3 = 0; X4 = 13/5; X5 = 0; X6 = 0; X7 = 54/5. Záver Zastavme sa pri najjednoduchších interpretáciách simplexovej metódy. Algebraický význam simplexnej metódy spočíva v tom, že vykonávaním identických algebraických transformácií prechádzame od jedného možného riešenia k systému algebraických rovníc k inému vylepšenému, čím sa dosiahne optimálne riešenie problému. Z geometrického hľadiska sú identické transformácie podľa simplexovej metódy postupné pohyby z jedného vrcholu konvexného mnohouholníka riešenia do susedného, z neho do ďalšieho a tak ďalej do optimálneho vrcholu po stranách tohto mnohouholníka. . Ekonomická podstata simplexovej metódy spočíva v tom, že ide o metódu postupného zlepšovania riešení. Táto metóda umožňuje po zvolení východiskového bodu - základného akčného plánu postupne napredovať a nakoniec dosiahnuť optimálny plán, ak, samozrejme, existuje. Simplex je konvexný mnohouholník v n-rozmernom priestore s n + 1 vrcholmi, ktoré neležia na tej istej nadrovine. Simplexy sú rozdelené do samostatnej triedy, pretože simplex je najjednoduchší mnohouholník obsahujúci určitý objem n-rozmerného priestoru. Je dokázané, že ak existuje optimálne riešenie, potom sa nevyhnutne nájde po konečnom počte krokov (s výnimkou takzvaného „degenerovaného problému“, v ktorom sa javí fenomén „cyklovania“, t.j. do rovnakej polohy, je to možné). Lineárne programovanie je oblasť matematického programovania venovaná teórii a metódam riešenia extrémnych problémov charakterizovaných lineárnym vzťahom medzi premennými. Matematické programovanie (optimálne programovanie) je odvetvie matematiky, ktoré kombinuje rôzne matematické metódy a disciplíny: lineárne programovanie, dynamické programovanie, konvexné programovanie atď. Všeobecnou úlohou matematického programovania je nájsť optimálnu (maximálnu alebo minimálnu) hodnotu cieľa. funkcie a hodnoty premenných musia patriť do určitého rozsahu prijateľných hodnôt. Zoznam použitej literatúry 1) A. S. Shapkin, N. P. Mazaeva; Matematické metódy a modely výskumu operácií, 2005. 2) N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Friedman; Operačný výskum v hospodárstva. - UNITI, 2002. Ak chcete použiť ukážku prezentácií, vytvorte si Google účet (účet) a prihláste sa: https://accounts.google.com Riešenie najjednoduchších úloh lineárneho programovania grafickou metódou 17.04.2012. Ak je systém obmedzení úlohy lineárneho programovania reprezentovaný ako systém lineárnych nerovností s dvoma premennými, potom je možné takýto problém vyriešiť geometricky. Úloha. Existuje 14 rádioreléových kanálov (RRC) a 9 troposférických kanálov. Je potrebné na nich prenášať informácie 3 typov: A, B, C. Navyše, informácie A sa rovnajú 600 USD, B - 3000 USD, C - 5500 USD. (Informáciou možno chápať počet telefonických rozhovorov, prenos dát a pod.). Možnosti kanála a náklady na údržbu pre každý kanál sú uvedené v tabuľke. Je potrebné nájsť príslušný počet kanálov oboch typov potrebných na prenos požadovaných informácií tak, aby náklady na prevádzku boli minimálne. Typy informácií Komunikačné kanály Požadované množstvo informácií, c.u. Troposférický RRS A 80 40 600 V - 1000 3000 C 300 800 5500 Náklady na údržbu jedného kanála, rub. 3000 2000 Etapy riešenia LLP: Zostavte ODR. Zostavte gradientový vektor cieľovej funkcie v určitom bode X 0 patriacom do ODR - (c 1 ;c 2) . Zostrojte priamku c 1 x 1 + c 2 x 2 = h, kde h je ľubovoľné kladné číslo, najlepšie také, aby nakreslená priamka prechádzala mnohouholníkom riešenia. Posuňte nájdenú čiaru rovnobežne so sebou v smere vektora gradientu, kým čiara neopustí ODR (pri hľadaní maxima) alebo v opačnom smere (pri hľadaní minima). V limitnom bode dosiahne účelová funkcia maximum (minimum), alebo sa na množine riešení stanoví neohraničenosť funkcie. Určte súradnice maximálneho (minimálneho) bodu funkcie a vypočítajte hodnotu funkcie v tomto bode. Tento vývoj je možné využiť ako zovšeobecňujúcu hodinu na tému „Systémy nerovníc s dvoma premennými“ v 9. ročníku (algebra 9, úprava Telyakovsky) a ako opakovaciu hodinu na túto tému v 10. ročníku. ... Materiál je určený pre pokročilých. program zvažuje algoritmus na zostavenie základných a referenčných grafov rôznymi metódami a nájdenie optimálneho riešenia ... Pracovný zošit na hodinu matematiky na tému „Problematika lineárneho programovania“ som vypracoval na rovnomennú hodinu matematiky (pokročilá úroveň). možno použiť ako v triede, tak na seminári... Rozhodovanie za neistoty Ak má prvý subjekt m stratégií a druhý má n stratégií, potom hovoríme, že máme do činenia s hrou m x n. Zvážte hru m x n. Nech je daný súbor stratégií: pre prvého hráča (Аi), pre druhého hráča (Bj) výplatná matica, kde aij je zisk prvého hráča alebo strata druhého hráča, keď si zvolí stratégie Аi a Bj, resp. Každý z hráčov jedinečne volí s pravdepodobnosťou I nejakú stratégiu, t.j. pri výbere riešenia používa čistú stratégiu. V tomto prípade bude riešenie hry v čistých stratégiách. Keďže záujmy hráčov sú opačné, prvý hráč sa snaží maximalizovať svoj zisk a druhý hráč, naopak, minimalizovať svoju stratu. Rozhodnutím hry je určiť najlepšiu stratégiu pre každého hráča. Výber najlepšej stratégie jedným hráčom sa vykonáva pri úplnej absencii informácií o rozhodnutí druhého hráča.
Lineárne programovanie
Príklady úloh, ktoré sú zredukované na PAP.
1. Úloha optimálnej alokácie zdrojov.
Príklady
Príklad 2
Riešenie
Problém so zmesou.
Tabuľka
Riešenie
Ekonomicko-matematický model problému.
Rezacia úloha
Hlavnou úlohou LP
Popisy snímok:
K téme: metodologický vývoj, prezentácie a poznámky
Načítava...