1.
2. návod na použitie mat. modely v ekonomike.
Matematické modely umožňujú určiť optimálne hodnoty neznámych parametrov ekonomických systémov, čo je dôležité v procese rozhodovania. Matematické programovanie poskytuje len prístroj, ktorý vám umožňuje optimalizovať proces výberu najlepšie možnosti plánov v procese riadenia v ekonomických systémoch.
Používa sa v matematickej štatistike, optimalizačné metódy, ekonomické metódy. kybernetika, experimentálne problémy.
Pri štúdiu zložitých procesov a javov v ekonomike sa často používa modelovanie - presne definované konkrétne zobrazenie uvažovaných charakteristík skúmaného objektu. Jeho podstata spočíva v tom, že skúmaný jav je reprodukovaný v experimentálnych podmienkach pomocou modelu v inej časovej a priestorovej mierke. Model je špeciálne vytvorený objekt, pomocou ktorého sa reprodukujú určité charakteristiky skúmaného systému, aby ho bolo možné študovať. Matematické modelovanie je najdokonalejšia a zároveň najefektívnejšia metóda získavania informácií o skúmanom objekte. Je to silný nástroj na analýzu v ekonómii. Výsledky výskumu pomocou modelov budú praktické vtedy, keď bude skonštruovaný model dostatočne adekvátny uvažovanému javu, t.j. dostatočne na to, aby odrážal skutočnú situáciu.
2. matematické programovanie ako veda, jeho štruktúra. Problémy s optimalizáciou. Ťažkosti pri aplikácii klasických optimalizačných metód pri riešení ekonomických problémov.
Matematické programovanie je odvetvie aplikovanej matematiky, ktoré sa rozvíja teoretický základ a metódy riešenia extrémnych problémov.
Matematické programovanie obsahuje niekoľko sekcií, z ktorých hlavné sú tieto:
1. Lineárne programovanie. Táto časť obsahuje úlohy, v ktorých sú neznáme premenné zahrnuté do matematických vzťahov na prvom stupni.
2. Nelineárne programovanie. Táto časť obsahuje problémy, v ktorých môže byť účelová funkcia a (alebo) obmedzenia nelineárne.
3. Dynamické programovanie. Táto časť obsahuje úlohy, v ktorých je možné proces riešenia rozdeliť do samostatných etáp.
4. Celočíselné programovanie. Táto časť obsahuje úlohy, v ktorých môžu neznáme premenné nadobúdať iba celočíselné hodnoty.
5. Stochastické programovanie. Táto časť obsahuje úlohy, ktoré obsahujú náhodné premenné v cieľovej funkcii alebo obmedzeniach.
6. Parametrické programovanie. Táto časť obsahuje problémy, v ktorých koeficienty neznámych premenných v cieľovej funkcii alebo obmedzenia závisia od niektorých parametrov.
Na riešenie problémov matematického programovania je ťažké použiť klasické metódy na nájdenie extrému, pretože v problémoch matematického programovania cieľová funkcia dosahuje svoju extrémnu hodnotu na hranici oblasti prijateľných hodnôt neznámych premenných a deriváty neexistujú. v hraničných bodoch. Úplné vymenovanie prípustných bodov je nemožné z dôvodu ich značného počtu.
3. Pojem matematického modelu, druhy mat. modelov
Matematický model je abstrakcia skutočného javu alebo procesu zapísaná v matematických symboloch a výrazoch. Matematické modely ekonomických procesov a javov sa nazývajú ekonomické a matematické modely
Modely sa delia na:
1. lineárne, v ktorom sú všetky závislosti opísané lineárnymi vzťahmi,
2. nelineárne, v ktorých existujú nelineárne vzťahy;
3. stochastické, ktoré zohľadňujú náhodný charakter skúmaných procesov,
4. deterministický, ktoré zohľadňujú priemerné hodnoty všetkých parametrov.
5. dynamický modely, v ktorých sa skúmané systémy zvažujú vo vývoji počas niekoľkých období,
6. statické, v ktorom sa nezohľadňuje časový faktor.
7. optimalizácia modely, v ktorých sa výber uskutočňuje v závislosti od extrémizácia nejaké kritérium,
8. neoptimalizácia, v ktorom neexistuje žiadne kritérium optimality.
9. makromodely(pre celú domácnosť)
10. mikromodely(jednotlivé väzby alebo procesy ekonomiky).
Typy matematických modelov: lineárne, nelineárne, kvadratické, celočíselné, diskrétne, parametrické, lineárne zlomkové, dynamické, stochastické
4. Všeobecný prehľad problémov matematického programovania.
Zvážte všeobecné vyhlásenie o probléme matematického programovania.
Všeobecným problémom matematického programovania je určiť optimálnu hodnotu cieľovej funkcie a hodnoty premenných musia patriť do určitého rozsahu prípustných hodnôt. Matematická definícia optimálne riešenie vyjadrené nájdením extrému (max alebo min) funkcie mnohých premenných
Z = f(x1, x2, …, xn)
v danom rozsahu zmeny týchto premenných
gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),
kde Ri je jedno zo znakov ≥, =, ≤.
5. Problém optimalizácie výrobného plánu. Ekonomická formulácia a konštrukcia matematického modelu problémov.
Ekonomické nastavenie:
Spoločnosť vyrába n typy používaných produktov m druhy surovín. Na výrobu výrobnej jednotky sa používa presne definované množstvo surovín jedného alebo druhého druhu. Suroviny každého druhu v podniku sú obmedzené. Spoločnosť získa určitý zisk z predaja jednotky produkcie. Je potrebné nájsť taký výrobný plán, v ktorom podnik získa maximálny celkový zisk.
Matematické nastavenie:
Nech j je index typu produktu j = 1, n
i - index typu zdroja i = 1, m
a ij sú náklady na suroviny i-tý typ na výrobu výrobnej jednotky j-tý typ;
Аi je daný limit disponibilného objemu zdrojov i-tého typu;
Pj - zisk získaný z predaja výrobnej jednotky j-tého typu;
xj je objem výstupu j-tého typu.
z \u003d P1x 1 + P2x 2 + ... + Pnx n → max
a11x 1 + a12x 2 +…+ a1nx n ≤ A1
a21x 1 + a22x 2 +…+ a2nx n ≤ A2
…………………………….
a m1x1 + a m2x2 +…+ a m n x n ≤ Am
xj ≥ 0, j = 1, n
6. Úloha diéty. Ekonomická formulácia a konštrukcia matematického modelu problému.
Ekonomické nastavenie
Niektoré farmy kŕmia zvieratá. Používa sa na výkrm n druhy krmiva. Obsah živín (vápnik, fosfor atď.) je známy na kŕmnu jednotku každého druhu. Pre správnu výživu zvierat je potrebné konzumovať živiny nie menej ako stanovené množstvá. Jednotkové náklady každého krmiva sú známe. Je potrebné určiť stravu kŕmenia zvierat, pri ktorej budú celkové náklady na výkrm minimálne.
Matematické nastavenie:
j je index typu krmiva, j = 1, n
i – index nutričného typu, i = 1, m
Ái je požadovaný denný príjem i-tého typu živín;
Сj sú náklady na jednotku krmiva j-tého typu.
Predstavme si neznáme premenné:
хj - denný objem krmiva pre zvieratá j-tý pohľad prísny.
V zmysle zavedenej notácie zadanú úlohu bude napísané ďalej
a11x1 + a12x2 +…+ a1nxn ≥ A1
a21x1 + a22x2 +…+ a2nxn ≥ A2
…………………………….
am1x1 + am2x2 +…+ a mnxn ≥Am
xj ≥ 0, j = 1, n
7. Dopravná úloha . Ekonomická formulácia a konštrukcia matematického modelu problému.
Ekonomické nastavenie :
Dostupné m dodávatelia homogénnych produktov a n spotrebiteľov tohto produktu. Známe jednotkové náklady na dodávku výrobnej jednotky od každého dodávateľa každému spotrebiteľovi. Zásoby dodávateľov sú obmedzené. Známe sú aj potreby produktov každého spotrebiteľa.
Je potrebné určiť taký plán prepravy výrobkov od dodávateľov k spotrebiteľom, v ktorom budú celkové náklady na prepravu minimálne.
Matematické nastavenie :
Uveďme si označenie daných parametrov:
j – spotrebiteľský index, j = 1, n
i – index dodávateľa, i = 1, m
Ái je objem produktov dostupných od i-tého dodávateľa;
Bj - objem dopytu po produktoch j-tého spotrebiteľa;
Cij sú jednotkové náklady na prepravu jednotky produktu od i-tého dodávateľa k j-tému spotrebiteľovi.
Predstavme si neznáme premenné:
хij je objem prepravy produktov od i-tého dodávateľa k j-tému spotrebiteľovi.
z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → min
Obmedzenia úloh.
I. Od každého dodávateľa môžete stiahnuť produkty nie viac, ako je dostupné množstvo:
x11 + x12 +…+ x1n ≤ A1
x21 + x22 +…+ x2n ≤ A2 (2)
…………………….
xm1 + xm2 +…+ xmn ≤ Am
II. Musí byť uspokojená potreba každého spotrebiteľa po produktoch
x11 + x21 +…+ xm1 ≥B1
x12 + x22 +…+ xm2 ≥B2
……………………. (3)
x1n + x2n +…+ xmn ≥Bn
III. Podmienka nezápornosti: xij ≥0, i = 1, m ; j = 1, n
Často je vhodné napísať matematický výrok v zloženom tvare:
i = 1, m 
j = 1, n
8. Problém výberu úloh alebo úloh. Ekonomická formulácia a konštrukcia matematického modelu problému.
Ekonomické nastavenie :
Dostupné n druhy práce a núčinkujúcich. Každý z účinkujúcich môže vykonávať akúkoľvek, no len jednu prácu. Náklady na vykonanie každého diela každým interpretom sú stanovené. Výkonných umelcov je potrebné zadávať do práce tak, aby celkové náklady na dokončenie diela boli minimálne.
Matematické nastavenie .
Uveďme si označenie daných parametrov.
i – index prác, i = 1, m
j je index výkonných umelcov, j = 1, n
Cij sú náklady na vykonávanie i-tej práce j-tým vykonávateľom.
Zavedieme neznáme premenné. V tomto probléme môžu neznáme premenné nadobúdať iba dve hodnoty, 0 alebo 1. Takéto premenné sa nazývajú nulové premenné.
1 - ak je j-tý umelec priradený k i-tej práci;
0 - inak.
V zmysle zavedenej notácie možno tento problém zapísať takto:
z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → min
I skupina obmedzení.
Ku každému dielu by mal byť priradený iba jeden interpret:
x11 + x12 +…+ x1n = 1
x21 + x22 +…+ x2n = 1
……………………..
xn1 + xn2 +...+ xnn = 1
II. reštrikčnej skupiny.
Každý vykonávateľ môže vykonávať iba jednu prácu:
x11 + x21 +...+ xn1 = 1
x12 + x22 +...+ xn2 = 1
……………………..
x1n + x2n +...+ xnn = 1
x ij = (0,1) i = 1, n; j = 1, n
9. Problém rezania materiálov. Ekonomická formulácia a konštrukcia matematického modelu problému.
Ekonomické nastavenie .
Na rezanie sa dodáva surovina rovnakej veľkosti. Je potrebné ho narezať na prírezy danej veľkosti v danom množstve, aby bol celkový odpad minimálny.
Matematické nastavenie .
Predstavme si notáciu:
i je index medzier,
Аi - požadovaný počet polotovarov i-tého typu;
j - index možností rezania,
Cj je veľkosť odpadu pri rezaní jednotky východiskového materiálu podľa možnosti j;
a ij je počet polotovarov i-tého typu pri rezaní jednotky východiskového materiálu podľa možnosti j.
Uveďme si zápis neznámych premenných.
xj je množstvo narezanej suroviny podľa možnosti j.
V zmysle zavedenej notácie možno tento problém zapísať takto:
z \u003d С1x1 + С2x2 + ... + Сnxn → min
a11x1 + a12x2 +…+ a1nxn = A1
a21x1 + a22x2 +…+ a2nxn = A2
…………………………….
am1x1 + am2x2 +…+ amnxn =Am
xj ≥ 0, j = 1, n
Použitie matematických modelov umožňuje ušetriť až 20 % surovín.
Matematický model rezania je zostavený v dvoch etapách.
V prvej fáze sa skonštruujú možnosti rezania, v dôsledku čoho sa získajú hodnoty počtu možností n, počet polotovarov každého typu rôzne možnosti rezanie (aij), ako aj hodnotu odpadu (Cj).
Konštrukcia možností na rezanie jednotky zdrojového materiálu sa vykonáva vo forme nasledujúcej tabuľky:
| číslo možnosti |
Prázdne i1 |
i2 prázdne |
prázdny im |
Polotovary sú usporiadané v nezvyšujúcom sa poradí ich veľkostí. Konštrukcia variantov sa uskutočňuje metódou úplného enumerácie.
10. Všeobecná forma modelu problému LP a jeho vlastnosti
Všeobecná forma LLP je:
z \u003d С1x1 + ... + Сnxn max (min)
a11 X1 + a12 X2 + … + a1n Xn R1 a1
a21 X1 + a22 X2 + … + a2n Xn R2 a2
………………………………………………….
am1 X1 + am2 X2 +…+ amnxn Rm am
xj ≥ 0, j = 1, k, k ≤ n
Vo všeobecnosti každý symbol R1, R2,…, Rm znamená jeden zo znakov: ≥, = alebo ≤ .
Všeobecná forma modelu problému LP má nasledujúce vlastnosti.
1. Systém obmedzení je prezentovaný vo forme rovníc (rigidné podmienky) a nerovníc (nerigidné podmienky).
2. Podmienky nezápornosti nie sú kladené na všetky premenné
3. Účelová funkcia smeruje buď k maximu, alebo k minimu.
11. Štandardná forma modelu problému LP a jeho vlastnosti
Štandardný formulár je nasledujúci.
Nájdite maximum alebo minimum cieľovej funkcie z:
z = С1x1 + … + Сnxn → max (min) (1)
S výhradou nasledujúcich obmedzení:
a11 X1 + a12 X2 + … + a1n Xn ≤ a1
a21 X1 + a22 X2 + ... + a2n Xn ≤ a2
…………………………………………..
am1 X1 + am2 X2 +… + amn Xn ≥ am
xj ≥ 0, j = 1, k, k ≤ n
Vlastnosti štandardnej formy modelu problému LP sú nasledovné:
1. systém obmedzení je prezentovaný vo forme nerovností (neprísne podmienky)
2. na všetky premenné sú kladené podmienky nezápornosti
3. účelová funkcia smeruje buď k max alebo min
12. Kanonická forma modelu problému LP a jeho vlastnosti
Kanonická forma je:
Nájdite minimum účelovej funkcie z:
z = С1x1 + … + Сnxn → min
S výhradou nasledujúcich obmedzení:
a11 X1 + a12 X2 + ... + a1n Xn = a1
a21 X1 + a22 X2 + ... + a2nxn = a2
…………………………
am1x1 + am2 X2 +… + amn Xn = am
Xj ≥0, j = 1, n
Vlastnosti kanonickej formy sú nasledovné:
1. Systém obmedzení je prezentovaný vo forme rovníc (prísne podmienky).
2. Podmienky nezápornosti platia pre všetky premenné
3. Účelová funkcia má tendenciu
V niektorých zdrojoch objektívna funkcia problému LP, prezentovaná v kanonickej forme, smeruje k maximu. Toto sa robí pre pohodlie pri riešení problému podľa algoritmu vyvinutého pre maximálnu objektívnu funkciu.
13. Možný, prípustný, optimálny plán základnej úlohy, ODZ úlohy LP
Definícia 1. Hodnoty neznámych premenných, ktoré spĺňajú všetky obmedzenia problému lineárne programovanie, sa volajú prípustné premenné hodnoty resp plány .
Definícia 2. Súbor všetkých plánov pre problém lineárneho programovania sa nazýva doména prípustných hodnôt premenných ( ODZ ).
Definícia 3. Plán úlohy lineárneho programovania, v ktorom účelová funkcia nadobúda minimálnu (alebo maximálnu) hodnotu na ODZ, sa nazýva optimálne .
14. Typy záznamov úloh LP: rozšírené, skladané, maticové, vektorové.
Modely problémov LP môžu byť napísané v rôznych formách.
1. Rozšírený pohľad na záznam modelu
Z = c1 X1 + c2 X2 + … + cn Xn → min
a11 X1 + a12 X2 + … + a1n Xn = a1,
a21 X1 + a22 X2 + … + a2n Xn = a2,
……………………………………………
a m1 X1 + am2 X2 + … + amn Xn = am,
Xj ≥ 0, j = 1, n.
2. Zbalené zobrazenie:
,
Xj ≥ 0, j = 1, n.
3. Model úlohy LP v maticovom tvare:
X ≥ 0
Kde 
a11 a12 … a1n X1 a1
A= a21 a22 … a2n, X= X2, A0 = a2
… … … … … …
dopoludnia 1 dopoludnia … dopoludnia X3 dopoludnia
4. Model úlohy LP vo vektorovej forme:
Kde
X1 a11 a12 a1n a1
X2, a21, a22, a2n, a2
… … … … …
Хn am1 am2 am2 am
15. Prechod od štandardnej a všeobecnej formy problémov LP ku kanonickej. Spojovacia veta
Na prechod od všeobecnej alebo štandardnej formy ku kanonickej sa používajú nasledujúce techniky.
1. Variabilná konverzia. Ak je nejaká premenná Xk kladná (Xk ≤ 0), potom sa zavedie nová premenná Xk ", takže Xk " = –Xk . Je zrejmé, že Xk " ≥ 0. Potom je v každom obmedzení a cieľovej funkcii premenná Xk nahradená [ – Xk "].
Ak nejaká premenná Xt môže nadobúdať ľubovoľné hodnoty, potom je nahradená rozdielom dvoch nezáporných premenných Xt' a Xt'', t.j. predpokladá sa, že xt = Xt' – Xt'', kde Xt' 0 ≥ a Xt'' ≥ 0.
2. Transformácia obmedzení. Ak má ktorákoľvek z obmedzení v modeli tvar nerovnosti, potom sa prevedie na rovnosť pridaním (ak je nerovnosť typu ≤) alebo odčítaním (ak je nerovnosť typu ≥) od jej ľavej strany. Tieto premenné sa nazývajú bilančné premenné. Bilančné premenné sú zahrnuté v účelovej funkcii s nulovými koeficientmi. Bilančná premenná nadobúda hodnotu indexu postupne po už existujúcich. Ak má napríklad systém obmedzení 5 premenných, potom prvá premenná bilancie bude X6 a druhá - X7 atď.
16. Prechod z kanonickej formy modelu ZLP na štandard
Ak chcete prejsť z kánonickej formy na štandardnú formu, každý z
rovnice, ktoré sa majú nahradiť systémom nerovností:
Ďalším spôsobom je dostať sústavu rovníc do špeciálnej formy a ďalej eliminovať niektoré premenné.
Jordan-Gaussovou metódou vyberáme základnú premennú v každej rovnici. Takýto výber sa uskutočňuje pomocou ekvivalentných (elementárnych) Gaussových transformácií. Tie obsahujú:
a) násobenie ľubovoľnej rovnice konštantou inou ako nula;
b) sčítanie akejkoľvek rovnice akejkoľvek inej rovnice vynásobené ľubovoľnou konštantou.
Pred transformáciou je vhodné napísať počiatočný systém lineárnych rovníc vo forme matice alebo tabuľky:
Úlohu napíšeme v štandardnom tvare.
17. Pojem nadrovina polroviny, nosná nadrovina.
18. Geometrické. interpretácia systému obmedzení a objektívnej funkcie v problémoch LP
19. Konvexná množina: krajné (rohové) body množiny. Konvexný mnohosten
Definícia Množina M sa nazýva konvexná, ak spolu s ľubovoľnými dvoma bodmi patriacimi do danej množiny obsahuje aj úsečku, ktorá ich spája.
 |
konvexná sada
Definícia Bod x množiny M sa nazýva rohový alebo krajný bod, ak nie je vnútorným žiadnemu segmentu, ktorý úplne patrí do danej množiny.
Veta 1. Akýkoľvek bod segmentu môže byť reprezentovaný ako konvexná kombinácia jeho rohových bodov.
x \u003d λ 1 A + λ 2 B
λ 1 , λ 2 ≥ 0 konvexná kombinácia bodov rohových bodov A a B
λ1 + λ2 = 1
Veta 2. Akýkoľvek bod konvexnej uzavretej množiny môže byť reprezentovaný ako konvexná kombinácia jej rohových bodov.
20. Algoritmus grafickej metódy riešenia úloh LP
1. Skontroluje sa, či je pôvodný LPP v štandardnom formulári, ak nie, potom treba úlohu previesť do štandardného formulára.
2. Kontroluje sa počet neznámych premenných. Ak je toto číslo viac ako tri, potom sa problém nedá vyriešiť grafickou metódou (existujú aj iné efektívne metódy riešenia takýchto problémov).
3. Oblasť prípustných hodnôt premenných pre ZLP je vo výstavbe.
4. Vytvára sa vodiaci vektor c .
5. Počiatočná izocel je nakreslená cez ODZ (kolmo na smerový vektor).
6. Uskutoční sa mentálny pohyb počiatočnej izocoelu v smere vektora c, ak je určená maximálna hodnota účelovej funkcie, alebo v opačnom smere, ak je určená jej minimálna hodnota, kým sa izocieľ nestane odkazom na ODZ. Priesečníky referenčnej izocoel a ODZ budú optimálnymi bodmi problému.
7. Na určenie súradníc optimálneho bodu je potrebné vyriešiť sústavu zodpovedajúcich lineárnych rovníc.
8. Na nájdenie optimálnej hodnoty cieľovej funkcie je potrebné dosadiť optimálne hodnoty premenných do cieľovej funkcie a vypočítať jej hodnotu.
20. grafický algoritmus. LP metóda riešenia problémov
Algoritmus grafickej metódy.
1. Postupnou výstavbou každej z podmienok systému obmedzení problému sa realizuje výstavba ODZ.
2. Smerovací vektor C je zostrojený koeficientmi pre premenné účelovej funkcie.
3. Počiatočná izocoel je nakreslená kolmo na smerový vektor cez počiatok.
4. Počiatočný izogól sa mentálne posúva v smere rastúcich hodnôt vektora C, ak je určená maximálna hodnota cieľovej funkcie, alebo v opačnom smere, ak je určená jej minimálna hodnota, až kým sa izogól nestane odkaz na ODZ. Priesečníky referenčnej izocoel a ODZ budú optimálnymi bodmi problému.
5. Na určenie súradníc optimálneho bodu je potrebné vyriešiť sústavu zodpovedajúcich lineárnych rovníc tých podmienok, v ktorých priesečníku sa optimálny bod nachádza.
6. Na nájdenie optimálnej hodnoty účelovej funkcie je potrebné dosadiť súradnice optimálneho bodu do účelovej funkcie a vypočítať jej hodnotu.
23. vety o rozsahu prípustných hodnôt úlohy LP a o účelovej funkcii
Veta ODZ. Oblasťou prípustných riešení úlohy LP je konvexná množina (uzavretá a ohraničená v n-rozmernom priestore)
Veta 2. O účelovej funkcii úlohy lineárneho programovania.
Cieľová funkcia LLP nadobúda svoju optimálnu hodnotu v jednom z rohových bodov oblasti prijateľných hodnôt premenných. Ak má účelová funkcia svoju optimálnu hodnotu v niekoľkých rohových bodoch, potom nadobudne rovnakú hodnotu v akomkoľvek bode, ktorý je konvexnou kombináciou týchto rohových bodov.
24. Veta o rohovom bode. Dostatočné a nevyhnutná podmienka
25. Dôsledky z vety o vlastnostiach riešení úloh a záverov LP. Koncept základnej línie.
Dôsledky z viet.
Definícia. Plán = (х1,х2,…,хn), ktorých kladné súradnice zodpovedajú lineárne nezávislým vektorom, sa nazýva základný plán PLP .
Dôsledok 1. Referenčný plán nemá viac ako m kladných súradníc.
Ak má presne m kladných súradníc, potom sa takýto návrh podpory nazýva nedegenerovaný, inak degenerovaný.
Dôsledok 2. Každý rohový bod ODZ je referenčným plánom.
27. Algoritmus simplexovej metódy.
Pri riešení úloh LP simplexovou metódou je potrebné vykonať nasledujúcu postupnosť akcií.
1. Skontroluje sa, či je problém LP v kanonickej forme. Ak nie, potom je potrebné previesť pôvodný model do kánonickej podoby.
2. Pre tento referenčný plán sa vyberie počiatočný referenčný plán a hodnota cieľovej funkcie.
3. Vytvorí sa počiatočná simplexná tabuľka.
4. Kontrolujú sa hodnoty odhadov optimality v indexovom riadku. Ak neexistujú žiadne kladné odhady, vypíše sa optimálne riešenie a algoritmus ukončí svoju prácu. V opačnom prípade je bod 5 splnený.
5. V základe je zavedený vektor, ktorý zodpovedá najväčšiemu kladnému odhadu. Tento stĺpec sa nazýva stĺpec povolenia.
6. Zo základu je odvodený vektor, ktorý zodpovedá simplexnému pomeru vypočítanému vzorcom 0< Ө ≤ . Данная строка называется разрешающей строкой.
7. Postaví sa nový simplexný stôl. Príslušne sa zmenia aj stĺpce B a C B. Zvyšok tabuľky sa vyplní z predchádzajúcej pomocou Gaussových transformácií, pričom za indexový riadok sa považuje m+1 riadkov a tiež sa transformuje pomocou Gaussových transformácií. Pokračujeme v implementácii odseku 4 tohto algoritmu.
Po zostavení každej tabuľky môžete skontrolovať správnosť výpočtov pomocou vzorcov na výpočet odhadov uvedených v predchádzajúcom odseku.
28. Voľba podkladu a konštrukcia východiskového referenčného plánu riešenia úloh simplexovou metódou.
29. Simplexné stoly, ich plnenie. Vzorce na výpočet koeficientov riadkov indexu.
30 . Veta o optimalite pre plán úlohy lineárneho programovania je dôsledkom vety o odhade optimality pre riešenie úloh simplexovou metódou.
Veta 1: Ak pre nejaký vektor Ā j v sústave
X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1
X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2
…………………………………………………..
X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m
Vzťah Z j – c j > 0 je splnený, potom plán X B0 nie je optimálny a je možné prejsť na plán X B1 tak, že Z (X B1) ≤ Z (X B0).
Tu je Z j = (С, Ā j) skalárny súčin vektorov.
C je vektor pozostávajúci z koeficientov pri základných premenných účelovej funkcie Z
Ā j je vektor pozostávajúci z expanzných koeficientov zodpovedajúceho vektora z hľadiska bázových vektorov.
c j je koeficient účelovej funkcie Z s premennou X j
Dôsledok od teorémy: Ak pre všetky vektory Ā 1 , Ā 2 , …, Ā n nejakého referenčného plánu Х platí vzťah Z j – c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.
Veta a dôsledok nám teda umožňujú určiť, či je ďalší plán podpory optimálny, a ak nie, potom je potrebné prejsť na iný plán podpory, v ktorom bude hodnota cieľovej funkcie menšia.
Komentujte. Veta a dôsledok predpokladajú, že problém je v kanonickej forme s minimálnou účelovou funkciou. Pri riešení úloh s maximálnou objektívnou funkciou však možno použiť aj simplexnú metódu. V tomto prípade sa pri analýze hodnôt odhadov používa ich opačný význam, to znamená, že plán bude optimálny, ak všetky odhady optimality nie sú negatívne (pozitívne alebo negatívne).
31. Voľba vektora vstupujúceho do bázy a odvodenie od bázy. Simplexný vzťah.
Na prechod na nový referenčný plán je potrebný jeden z voľných vektorov 
vstúpiť do základu a vydať niektoré zo základných vektorov. Na zavedenie do základu zvolíme vektor, ktorý má aspoň jednu kladnú súradnicu. Nech je takýmto vektorom vektor A m+1.
rozklad -
Resp. vektor, kat. bude referenčným plánom, ak jeho súradnice nie sú záporné a počet kladných súradníc sa bude rovnať m.
Súradnice vektora X1 musia byť nezáporné, t.j. .
Ak 
, potom táto súradnica bude nezáporná.
Nech dostaneme minimum vo vzťahu (5) pri i =1, potom ak vezmeme
potom prvá súradnica vektora 1 X sa stane nulou.
Vzťah (6) sa nazýva simplexný vzťah. Posunuli sme sa teda z pôvodnej základnej línie 0 X(základné vektory A1, A2, ... Am) k referenčnému plánu 1 X(základné vektory А2,А3,…,Аm, Am+1).
32. permisívny prvok tabuľky, jej výber. Úplné Jordanovo eliminačné pravidlo na prepočet simplexnej tabuľky.
33. Štvoruholníkové pravidlo na prepočet simplexnej tabuľky
34. Znak jedinečnosti optimálneho plánu, súboru optimálnych plánov a absencie optimálneho plánu pri riešení úlohy LP simplexovou metódou.
Pri riešení problémov simplexnou metódou sú možné tieto typy optimálnych riešení:
1. Jedinečnosť . Ak sú odhady všetkých voľných vektorov striktne negatívne, potom je získaný návrh podpory optimálny a jedinečný. (pozri príklad v predchádzajúcom odseku).
2. Alternatívne optimum (množina optimálnych riešení).
Ak medzi nepozitívnymi odhadmi voľných vektorov existuje aspoň jeden nulový odhad, potom získaný návrh podpory bude optimálny, ale nie jediný. V tomto prípade môžete prejsť na iné plány podpory (do základu sa zavedú vektory, ktoré zodpovedajú nulovým odhadom) a potom napísať všeobecné optimálne riešenie ako konvexnú kombináciu získaných optimálnych plánov podpory.
3. LLP nemá optimálne riešenie, keďže účelová funkcia nie je zdola ohraničená . Ak má simplexová tabuľka kladné skóre, a všetky prvky daný stĺpec sú záporné a nulové, potom je možné tento vektor zaviesť do základu. Žiadny zo základných vektorov však nemožno odvodiť zo základu. Z toho vyplýva, že pri prechode na nepodporný plán je možný ďalší pokles účelovej funkcie.
4. Program celoživotného vzdelávania nemá optimálne riešenie, pretože systém obmedzení je nekonzistentný. Keďže pri riešení CŽV by mala byť východiskovým referenčným plánom obvyklá simplexová metóda, systém lineárnych rovníc určite nie je nejednotný. Pri riešení obvyklou simplexovou metódou teda takýto prípad nemôže nastať.
5. Ak ODZ pozostáva z jedného bodu, potom je riešenie takéhoto problému triviálne a možno ho získať bez použitia simplexnej metódy.
35. Kedy sa používa metóda umelej bázy?
umelé.
36. Konštrukcia M-problému v metóde umelých báz
Ak je problém lineárneho programovania v kanonickej forme, nie všetky rovnice obsahujú základné premenné, t. j. neexistuje žiadna pôvodná základná línia. V tomto prípade v tých rovniciach, v ktorých nie sú žiadne základné premenné, je potrebné pridať nejakú nezápornú premennú s koeficientom +1. Takáto premenná sa nazýva umelé.
K účelovej funkcii sa musí pridať umelá premenná s veľmi veľkým kladným číslom (keďže účelovou funkciou je nájsť minimum). Toto číslo sa označuje latinským písmenom M. Možno ho považovať za rovné +∞. V tomto ohľade sa niekedy metóda umelej bázy nazýva M-metóda. Takáto transformácia pôvodného problému sa nazýva konštrukcia rozšíreného problému. Ak riešite problém s účelovou funkciou na nájdenie umelej premennej, musíte k účelovej funkcii pridať veľmi veľké kladné číslo (keďže účelová funkcia je nájsť minimum). Toto číslo sa označuje latinským písmenom M. Možno ho považovať za rovné +∞. V tomto ohľade sa niekedy metóda umelej bázy nazýva M-metóda. Takáto transformácia pôvodného problému sa nazýva konštrukcia rozšíreného problému. Ak sa problém rieši pomocou účelovej funkcie na nájdenie maxima, potom umelé premenné vstupujú do účelovej funkcie s koeficientom -M.
V rozšírenom probléme teda máme základnú líniu (hoci niektoré základné premenné sú umelé).
Vytvorí sa počiatočná simplexná tabuľka.
37. vybudovanie indexovej čiary metódou umelej bázy
Vytvorí sa počiatočná simplexná tabuľka, v ktorej je riadok indexu rozdelený na dva riadky, pretože odhady pozostávajú z dvoch výrazov. Horný riadok obsahuje člen odhadu bez M, spodný riadok zobrazuje koeficienty pri M. Znamienko odhadu je určené znamienkom koeficientu pri M bez ohľadu na hodnotu a znamienko člena bez M, keďže M je veľmi veľké kladné číslo.
Preto na určenie vektora, ktorý je zavedený do základu, je potrebné analyzovať spodnú indexovú čiaru. Ak je zo základu odvodený umelý vektor, potom je možné príslušný stĺpec v nasledujúcich simplexných tabuľkách vynechať, ak nie je potrebné získať riešenie duálneho problému (pozri nasledujúcu tému).
Po odstránení všetkých umelých vektorov zo základu bude mať spodný riadok všetky nulové prvky, okrem odhadov zodpovedajúcich umelým vektorom. Budú sa rovnať -1. Takáto línia môže byť vyňatá z úvahy a ďalšie riešenie môže byť uskutočnené obvyklou simplexovou metódou, ak nie je potrebné získať riešenie duálneho problému (pozri nasledujúcu tému).
38. Kritérium optimálnosti v metóde umelej bázy. Znakom je konštrukcia počiatočného základného plánu pôvodnej úlohy.
39. Algoritmus duálnej simplexovej metódy
Algoritmus duálnej simplexovej metódy:
1. obvyklým spôsobom vyplňte prvé simplexné tablo, ignorujte znaky voľných výrazov. Predpokladá sa, že takýto problém by mal mať základnú jednotku.
2. Vyberte vodiacu čiaru podľa najväčšieho absolútneho záporného prvku stĺpca voľných členov A0
3. Vodiaci stĺpec sa volí podľa najmenšej absolútnej hodnoty pomeru prvkov indexovej čiary k negatívnym prvkom vodiacej čiary.
4. Prepočítajte simplexnú tabuľku podľa pravidla úplných Jordanových eliminácií
5. skontrolujte prípustnosť prijatého plánu. Znakom získania prijateľného referenčného plánu je absencia negatívnych prvkov v stĺpci A0. Ak sú v stĺpci A0 záporné prvky, prejdite na druhý odsek. Ak neexistujú žiadne, pokračujú v riešení problému obvyklým spôsobom.
6. Znakom získania optimálneho riešenia duálnou simplexovou metódou je kritérium optimálnosti pre obyčajnú simplexovú metódu.
41. Otvorené a uzavreté dopravné modely. Prechod z otvoreného dopravného modelu na uzavretý.
Druhy prepravných úloh.
Dostupné m dodávatelia homogénnych výrobkov so známymi zásobami výrobkov a n spotrebiteľov týchto produktov s daným objemom potrieb. Známe sú aj jednotkové náklady na dopravu.
Ak sa súčet objemov zásob výrobkov rovná objemu potrieb všetkých spotrebiteľov, potom sa takýto problém nazýva tzv. uzavretá dopravná úloha
(t. j. ak ∑ Ai = ∑ Bj), inak sa nazýva dopravný problém OTVORENÉ. Na vyriešenie dopravného problému je potrebné, aby bola uzavretá.
Otvorenú prepravnú úlohu možno previesť na uzavretú nasledujúcim spôsobom.
Nech ∑Ai > ∑Bj. V tomto prípade je potrebné zaviesť fiktívneho n + 1 spotrebiteľa s objemom potrieb ∑Ai – ∑Bj.Jednotkové náklady na prepravu od dodávateľov k fiktívnemu spotrebiteľovi sa predpokladajú 0, keďže v skutočnosti takáto preprava nebude a časť produktov zostane dodávateľom.
Ak ∑Bj > ∑Ai . V tomto prípade je potrebné zaviesť fiktívneho m + 1 dodávateľa s objemom zásob ∑Bj – ∑Ai . Predpokladá sa, že jednotkové náklady na prepravu od fiktívneho dodávateľa k spotrebiteľom sa rovnajú 0, pretože v skutočnosti sa takáto preprava neuskutoční a spotrebitelia nedostanú niektoré produkty.
42. Metódy konštrukcie počiatočného rozdelenia v dopravnom probléme: metóda severozápadného rohu a metóda najmenšieho prvku v matici.
Severozápadná technika na zostavenie referenčného plánu. Podľa tejto techniky sa tvorba hodnôt návštevnosti začína s.-z. roh stola, t.j. z bunky x11. Podľa tohto spôsobu sa najskôr distribuuje tovar prvého dodávateľa. Navyše, prvý dodávateľ najskôr maximálne uspokojí prvého spotrebiteľa. Potom, ak dodávateľ stále má tovar,
Metóda najmenšieho prvku v matici.
Podstata metódy spočíva v tom, že do bunky je vždy vložená maximálna možná zásoba, ktorá zodpovedá najnižšej tarife matice.
Najprv urobíme značky (napríklad znakom ▼) v tých bunkách riadkov, v ktorých je pozorovaná najnižšia cena za riadok. Potom obchádzame tabuľku po stĺpcoch a robíme si rovnaké poznámky do buniek, v ktorých je najmenšia cena podľa stĺpcov.
Ďalšia distribúcia sa najskôr uskutoční pokiaľ možno nad bunkami s dvoma značkami, potom - s jednou a potom sa problém vyváži na (m + n - 1) výplne. Náplne organizujeme pri prechode stola zľava doprava a zhora nadol.
43. Vlastnosti dopravných úloh
Transportný problém má niektoré vlastnosti, ktoré sa môžu prejaviť v nasledujúcich vetách.
Veta 1. Uzavretý dopravný problém má vždy riešenie.
Veta 2. Ak objem zásob produktov a objem potrieb sú celé čísla, potom riešenie problému dopravy bude tiež celé číslo.
Veta 3. systém obmedzení uzavretého dopravného problému je vždy lineárne závislý.
Z tejto vety vyplýva, že rozdelenie uzavretého dopravného problému má vždy m + n – 1 základných premenných a (m – 1) (n – 1) premenných voľného času.
44. Degenerovaná distribúcia v dopravných problémoch, zbavenie sa degenerácie. Prečiarknutá kombinácia.
Distribúcia sa nazýva degenerovaná, ak je počet buniek menší ako m + n - 1.
45. Vety o optimálnosti pre dopravný problém.
Veta. Ak pre nejaké rozdelenie prepravnej úlohy si
sú splnené podmienky:
A). ui+vj = cij pre obsadené bunky
b) ui+vj ≤ сij, pre voľné bunky,
potom je toto rozdelenie optimálne.
Hodnoty ui sa nazývajú riadkové potenciály a hodnoty vj sa nazývajú stĺpcové potenciály.
46. Potenciály a spôsoby ich výpočtu.
Na nájdenie potenciálov riadkov a stĺpcov sa používa nasledujúca úvaha na základe podmienky a) vety o optimálnosti.
Počet rovníc založených na tejto podmienke je m + n – 1 a počet neznámych ui a vj je m + n. To. počet premenných je väčší ako počet rovníc a všetky rovnice sú lineárne nezávislé. Riešenie takéhoto systému lineárnych rovníc je neurčité, preto je potrebné jednému z potenciálov priradiť ľubovoľnú hodnotu. V praxi ui = 0. získa sa sústava m + n – 1 rovníc s m + n – 1 neznámymi premennými. Tento systém je možné vyriešiť akýmkoľvek spôsobom. V praxi sa na výpočet potenciálov berú do úvahy obsadené bunky, pre ktoré je známy jeden z ich potenciálov a na základe podmienky a) vety sa vypočítajú hodnoty zostávajúcich neznámych potenciálov.
47. Výpočet odhadov optimality rozloženia dopravných úloh a kritéria optimality.
Na základe vzťahu b) vety môžeme napísať nasledujúci vzorec na výpočet odhadov: δ ij= ui + vj – сij. Aby nedošlo k zámene odhadov s objemami dopravy, sú (odhady) ohraničené krúžkami.
Odhady optimality vo voľných TK bunkách sú kritériom optimality, ktoré kontroluje distribúciu z hľadiska optimality. Ak sú odhady všetkých voľných buniek menšie alebo rovné nule, potom je toto rozdelenie optimálne.
48. prerozdelenie zásob v dopravnom probléme
Ak distribúcia nie je optimálna, potom je potrebné zásoby prerozdeliť.
Na prerozdelenie je zostavený cyklus prepočtu. Ako bunka sa vyberie bunka s najvyšším pozitívnym skóre. Táto bunka je označená znakom „+“, to znamená, že je potrebné do nej zaznamenať určité množstvo dodávky. Potom sa však zostatok v tomto stĺpci naruší, preto musí byť jedna z obsadených buniek tohto stĺpca označená znakom „-“, to znamená, že objem dodávky by sa mal znížiť o rovnakú sumu. Potom sa však zostatok na tomto riadku zmení, preto musí byť niektorá obsadená bunka tohto riadku označená znamienkom „+“. Tento proces pokračuje, kým sa v riadku, kde sa nachádzala pôvodná bunka, neumiestni znak „-“.
Pre každú voľnú bunku existuje cyklus prepočtu a navyše jediný.
49. redistribučné reťazce, ich typy.
Uvažovaný dopravný plán nech nie je optimálny, t.j. existujú pozitívne relatívne odhady. Potom sa vezme nepriaznivá bunka (jedna z nevýhodných) a zostaví sa pre ňu cyklus prepočtu, podľa ktorého sa potom prerozdelí plánovaná preprava. Cyklus je postavený vo forme prerušovanej uzavretej čiary, ktorej segmenty prebiehajú buď pozdĺž stĺpca alebo pozdĺž čiary. V jednom z rohov prerušovanej čiary je nepriaznivá bunka nárokujúca si výrobok a v ostatných rohoch sú bunky vyplnené, t.j. pri konštrukcii cyklu začíname od kandidátskej bunky a vraciame sa k nej po prerušovanej čiare, ale obraty môžeme robiť len vo vyplnených bunkách (zodpovedajúcich základným premenným). Nepriaznivá bunka nech si uplatňuje nárok na produkt Q. Aby sa predišlo nerovnováhe v tabuľke, je potrebné
pridať a odčítať Q k dostupnej premávke. Pretože existuje párny počet rohov, Q sa pridá do polovice buniek a odčíta sa do druhej polovice. Cyklus sa spustí v smere alebo proti smeru hodinových ručičiek od kandidátskej bunky, umiestni sa tam dobré Q, potom sa Q odčíta od susednej bunky, potom sa pridá atď. Samotná hodnota Q je zvolená tak, aby sa jedna z buniek vyprázdnila, ale žiadna zo zásob by nebola záporná.
Aby sa to dosiahlo, musí sa Q zvoliť rovné najmenšej redukovateľnej z buniek, v ktorých sa Q odpočítava. Na nasledujúcom obr. 7.1 a 7.2 si ukážeme príklady cyklov a výpočtového pravidla.
V tomto prípade sa vyprázdnia dve bunky. Je však potrebné, aby sa iba jedna bunka stala vzájomne prázdnou. Robia to takto: jedna z vyprázdňovacích buniek sa v novej tabuľke vyprázdni a do druhej vyprázdňovacej bunky sa vloží nula. Táto bunka sa v novej tabuľke považuje za základnú (vyplnenú).
50. Voľba objemu prerozdeľovania.
Stanovenie objemu prepravovaných produktov. Pri určovaní objemu produktov presunutých cez cyklus počítania musíme vychádzať z nasledujúcich dvoch úvah:
a) po transformácii v bunkách tabuľky by sa nemali získať záporné čísla;
b) jedna z obsadených ciel sa musí uvoľniť.
Aby boli tieto podmienky splnené, je potrebné zvoliť objem prepravovaných produktov nasledovne: θ=min (хij) -, kde (хij) je objem prepravy z buniek prepočítavacieho cyklu označeného „ -“ znamenie.
6 = min(20;30)=20
K hodnotám buniek označených znamienkom „+“ sa pridá θ. θ sa odpočíta od hodnôt buniek označených znamienkom „-“. Dodávaná hodnota zostávajúcich buniek sa prepíše bez zmien. V dôsledku toho dostaneme nasledujúcu tabuľku.
53. Algoritmus metódy potenciálov.
Algoritmus:
1. Skontrolujte, či je rovnica pre danú úlohu splnená 
ak nie, do úlohy sa zapojí fiktívny dodávateľ alebo spotrebiteľ
2. Podmienka úlohy je zapísaná vo forme transportnej tabuľky
3. Vytvára sa počiatočná základná línia
4. Určujú sa potenciály dodávateľov a spotrebiteľov
5. Vypočítajú sa skóre voľných buniek. Ak nie sú všetky negatívne, plán je optimálny a odpoveď si musíte zapísať. Prepravnú maticu X a určiť výšku prepravných nákladov. Ak plán nie je optimálny, t.j. medzi odhadmi sú negatívne, vyberte sľubnú bunku s najväčšou zápornou hodnotou. odhadnúť a prejsť vo veľkosti na ďalšiu.
6. Načítajte perspektívnu bunku. Pripravte si nový základný plán vo forme prepravnej tabuľky. Prejdite na bod 4.
54. Účtovanie nákladov na výrobu a prepravu výrobkov. Prepravná úloha so zákazom zásobovania.
Pri riešení niektorých problémov je potrebné počítať s nákladmi nielen na prepravu tovaru, ale aj na výrobu prepravovaných produktov. K tomu sa v matici transp. úlohy
Kde Cij ' sú znížené náklady na výrobu jednej jednotky výstupu.
Cij “- náklady na prepravu jednej jednotky produkcie.
Úlohy so zákazom dodávok.
V niektorých situáciách nie je možné prepravovať produkty na žiadnej trase.
Za týmto účelom sa v matici prepravnej úlohy, cez ktorú je preprava zakázaná, zadá prohibitívna tarifa M. Ďalej sa úloha rieši obvyklým spôsobom, táto bunka však bude vždy zodpovedať zápornému skóre bunky.
55. berúc do úvahy obmedzenia priepustnosti trás, berúc do úvahy povinný charakter určitých dodávok v dopravnom probléme.
zohľadnenie obmedzení priepustnosti trás.
V niektorých dopravných úlohách, na niektorých trasách, menšie priepustnosť než je potrebné na uspokojenie dopytu odberného miesta.
berúc do úvahy obligatórny charakter určitých dodávok v dopravnom probléme.
V niektorých prípadoch úloha vyžaduje, aby sa napríklad na trase Ak Bs vykonala dodávka v jednotkách objemu A. V tomto prípade sa povinná dodávka odpočíta od objemu výroby bodu A a objemu S Bs a problém je vyriešený s ohľadom na voliteľnú dodávku. Po získaní optimálneho riešenia sa zásoba nevyhnutne pripočíta k objemu stojacemu v článku Ak Bs.
56. Možné závery s ekonomickým. interpretácia optimálneho rozdelenia pre otvorené dopravné problémy.
Po prijatí optimálnej distribúcie je potrebné vrátiť sa k pôvodnému problému a patrične hospodáriť. závery. Sú to nasledovné:
1. Ak je zavedené odberné miesto, znamená to, že v analyzovanom systéme sú nadmerné objemy výroby a je možné, bez toho, aby bol dotknutý uvažovaný systém, znížiť kapacity týchto výrobných miest o množstvo záväzných ktoré sú viazané na fiktívne miesto spotreby.
2. Ak sa zavedie fiktívne miesto výroby, znamená to, že kapacity skutočných výrobných miest nestačia a je potrebné ich zvýšiť. Zvyšuje sa kapacita tých výrobných miest, ktoré sú najbližšie k odberným miestam naviazaným na fiktívne výrobné miesto. Kapacita výrobcu sa zvyšuje o záväznú hodnotu. Za týmto účelom zvážte stĺpec odberného miesta, ktorý je viazaný na fiktívne miesto výroby, a nájdite v ňom najnižšiu tarifu. Najúčinnejšie je zvýšiť kapacitu výrobného miesta zodpovedajúcu tejto tarife o výšku viazanosti.
57. Pojem duality. Ekonomická formulácia duálnych problémov na príklade problému optimalizácie výrobného plánu.
Duálny problém je pomocný problém lineárneho programovania formulovaný pomocou určitých pravidiel priamo z podmienok pôvodného, alebo priameho problému.
Nech je úlohou optimalizovať plán výroby. Vyzerá to takto:
Počiatočná úloha:
a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1
a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | o 2
……………….. |.. (1)
A T 1 x 1 + a T 2 x 2 + ... + a T n x n ≤v 1 | pri T
x j ≥ 0, j = 1, n(2)
z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)
X \u003d (x 1, x 2, ..., x n)
a ij - počet surovín i-tého typu, vynaložených na výrobu j-tého typu produktu
Dvojitý problém
Nech podnik z akéhokoľvek dôvodu nemôže vyrábať produkty. Aby sa znížili náklady na prestoje, spoločnosť môže predávať suroviny, ktoré má. Za akú cenu by sa mali suroviny predávať?
i - cena i-tého druhu suroviny dostupnej v podniku.
a 11 r 1 + a 21 r 2 + ... + a T 1 r T≥s 1
a 12 x 1 + a 22 y 2 + ... + a T 2 x n ≥ s 2
……………….. (1’)
A 1p y 1 + a 2p y 2 +…+ a tp pri T≥s P
i ≥0, j = 1,m(2’)
F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)
58. Korešpondencia medzi štrukturálnymi prvkami priameho a duálneho problému
Každý problém lineárneho programovania môže byť spojený
dvojitá úloha podľa nasledujúcich pravidiel:
1. Vo všetkých obmedzeniach pôvodného problému musia byť voľné podmienky
byť na pravej strane a podmienky s neznámymi na ľavej strane.
2. Obmedzenia – nerovnosti pôvodného problému musia mať znaky,
nasmerované jedným smerom.
3. Ak je cieľová funkcia v pôvodnom probléme minimalizovaná, obmedzenia nerovností by sa mali zapísať so znamienkom "≤", potom v duálnom probléme bude cieľová funkcia minimalizovaná a znamienka obmedzení nerovnosti budú "≥".
4. Každé obmedzenie pôvodného problému zodpovedá premennej in
dvojitá úloha. Ak premenná zodpovedá nerovnosti, je nezáporná, ak zodpovedá rovnosti, potom je premenná bez obmedzenia znamienka („ľubovoľná“).
5. Koeficienty premenných v obmedzeniach duálneho problému sa získajú transpozíciou matice zloženej z
koeficienty pre premenné pôvodného problému.
6. Voľné členy pôvodnej úlohy sú koeficienty at
premenné v cieľovej funkcii duálneho problému a voľné
termíny v duálnom probléme sú koeficienty premenných v
funkcie pôvodného problému.Poznamenávame tiež, že vzťah duality je vzájomný, t.j. úloha duálna vzhľadom na duálnu sa zhoduje s pôvodnou Duálne dvojice úloh sa delia na symetrické a asymetrické. V symetrickom páre sú obmedzeniami primárneho a duálneho problému neprísne nerovnosti, a preto môžu premenné oboch problémov nadobúdať iba nezáporné hodnoty.
59. Konštrukcia duálnych problémov k pôvodným problémom napísaným v štandardnej, kanonickej a všeobecnej forme modelu (konštrukcia symetrických a asymetrických duálnych problémov)
Štandardný formulár (originál)
Σ a ij x j ≤ b i, i=1,n(1)
x j ≥0, j=1,n(2)
z = Σ c j x j ->max(3)
Dvojitý štandard
Σ a ij y i ≤ c j, j=1,n(1)
yi ≥0, j=1,m(2)
F = Σ b i y i -> min(3)
Pôvodný problém v kanonickej forme:
Σ a ij x j = b i, i=1,m(1)
x j ≥0, j=1,n(2)
z = Σ c j x j -> min(3)
Dvojitý kanonický
Σ a ij y i ≤ c j, j=1,n(1)
y i - ľubovoľné (2)
F = Σ b i y i ->max(3)
Uveďme ekonomickú interpretáciu dvojice duálnych problémov. Zvážte problém racionálneho využívania zdrojov. Nech má podnik zdroje b1,b2,...bm, ktoré možno použiť na výrobu n-typov produktov. Nech sú známe aj náklady na jednotku j-typu produktu cj (j=1,n) a miera spotreby i-tého zdroja (i=1,m) na výrobu jednotky j-tá produkcia– aij. Je potrebné určiť objem výroby každého typu xj (j=1,n), maximalizovať celkové náklady
f= c1x1+…+cnxn (1)
Zároveň by spotreba zdrojov nemala prekročiť ich dostupnosť:
a11x1+…+a1nxn<=b1 }
…………………….. } (2)
am1x1+…+amnxn<=bm }
Všetky známe v ich ekonomickom zmysle nie sú negatívne:
Xj>=0 (j=l,n). (3)
Všimnite si, že tento problém tvorí symetrický duálny problém.
Asymetrické duálne problémy.
Zoberme si ZLP na maximum v kanonickej podobe:
Max Z=(n;j=1)Σcj*xj
(n;j=1)Σaij*xj=bi (i=1,m)
Xj>=0 (j=l,n).
60. Hlavná a druhá veta o dualite (uveďte vetu a vysvetlite)
Prvá veta o dualite.
Veta: ak má jeden z duálnych problémov optimálny plán, potom je druhý riešiteľný, t.j. má voliteľný plán. V tomto prípade sa extrémne hodnoty účelových funkcií zhodujú (j=od 1 do n) Σcjxj*= (i=od 1 do m)Σbiyi*, ak sú v origináli. problém je účelová funkcia neobmedzená na množine plánov, potom v duálnom probléme je systém obmedzení nekonzistentný.
Druhá veta duality a jej ekonomická interpretácia.
Za účelom platné riešenia dvojice duálnych úloh boli optimálne, je potrebné a postačujúce na splnenie podmienky: xj*(∑aij yi*-cj)=0, j od 1 do n, yi*(∑aij xj*-bi)=0, I od 1 do m. Toto sú podmienky komplementárnej nevoľnosti. Z nich vyplýva: ak akékoľvek obmedzenie duálneho problému premení optimálny plán na prísnu rovnosť, potom zodpovedajúca zložka opt. plán duálneho problému by sa mal rovnať nule.Ak nejaký komponent opt. plán sa rovná nule, potom zodpovedajúce obmedzenie duálneho problému prevedie opt.plán na striktnú rovnosť xj*>0, teda (i= od 1 do m)Σaij yi*=cj opt.plán, potom ak náklady>ceny, objem výroby=0 Σaij yi* >cj teda xj*=0
yi*>0 teda (j=od 1 do n) Σaij xj*=bi (rasy zdrojov = zásoba zdrojov).
(j=1 až n) Σaij xj* Význam vety je nasledujúci: Ak je odhad nákladov na spotrebu zdrojov na výrobu jednotky prod-ii \u003d cena, potom je tento typ prod-ii zahrnutý do optimálneho plánu; Ak náklady prevyšujú cenu, potom by sa produkt prod-yu nemal vyrábať; Ak spotreba zdrojov = zásoby, potom je odhad nákladov na tento zdroj kladný. Takýto zdroj sa nazýva vzácny. Najviac deficitné.res-s má najvyššie skóre; Ak zdroj nie je úplne vyčerpaný, potom jeho odhad nákladov = 0. 61. Konštrukcia optimálneho plánu podpory pre duálny problém z simplexnej tabuľky pôvodného problému Informácie zo stĺpcov inverznej matice lineárnych transformácií, ktoré viedli k optimálnemu výsledku. Stĺpce matice D-1 poskytujú veľmi užitočné informácie. Stĺpec A3: "tieňová" cena zdroja S2 je y01=0, stĺpec zostáva single a z prvého riadku sa dá vyčítať, že x3=9, t.j. pri realizácii nájdeného optimálneho plánu bude 1. zdroj prebytok a tento prebytok (nedostatočné využitie) bude predstavovať len 9 konvenčných jednotiek. Stĺpec A4: "tieňová" cena zdroja S2 sa rovná y02=1, zdroj bude plne využitý a jeho prípadné zvýšenie povedie k zvýšeniu účelovej funkcie (tj príjmu). A preto y02=1, potom zvýšenie zdroja S2 o 1 c.u. poskytne prírastok z hľadiska príjmu o.Z = y02· .w2 = = 1,1 = 1 (tisíc UAH) (tu.w2 je prírastok zdroja S2 a .Z je zodpovedajúci prírastok príjmu). Pri takomto prírastku zdroja S2 už bude maximálny príjem Zmax=58 tisíc UAH. + 1 tisíc UAH = 59 tisíc UAH. Na obr. 6.2 ilustruje túto situáciu, ktorej komentár bude uvedený nižšie. Zo stĺpca A4 tiež vyplýva, že pri zvýšení zdroja S2 o 1 c.u. pre nový optimálny bod sa výkon tovaru T1 zníži o ½ tony (na priesečníku riadku základnej premennej x1 a stĺpca A4 je "-1/2") a výkon tovaru T2 sa zvýši o 3 /2 tony (pretože v riadku so základnou premennou x2 v stĺpci A4 máme "3/2". To, čo bolo povedané o stĺpci A4, bude komentované nižšie pomocou grafických konštrukcií (obr. 6.2). Stĺpec A5: "tieň" "cena zdroja S3 sa rovná y03=2. To znamená, že zvýšenie zdroja S3 o 1 c.u. prinesie sčítanie v Z to.Z = y03 · .v3 = 2,1 =2 (tisíc hrivien) a bude Zmax=58 tisíc hrivien. + 2 tisíc UAH = 60 tisíc UAH. Súčasne, ako vyplýva zo stĺpca A5 tabuľky. 3 sa výkon T1 zvýši o ½ tony a T2 sa zníži o ½ tony. Zásoba surovín S1 (pozri riadok 1) sa zvýši o 3/2 k.ú. 62. Myšlienka metódy dynamického programovania a jej geometrická interpretácia. Bellmanov princíp optimality. Optimálne riešenie úlohy metódou dynamického programovania sa nájde na základe funkcionálnej rovnice Na jeho definovanie potrebujete: 1. zapíšte si funkčnú rovnicu pre posledný stav procesu (zodpovedá l \u003d n-1) fn-1(Sl-1)=optimálne(Rn(Sn-1,Un)+f0(Sn)) 2. nájdite Rn(Sn-1,Un) z diskrétnej množiny jeho hodnôt pre niektoré pevné Sn-1 a Un zo zodpovedajúcich prípustných oblastí (keďže f0(Sn)=0, potom f1(Sn-1)= optimum(Rn(Sn-1,Un) Výsledkom je, že po prvom kroku je známe riešenie Un a zodpovedajúca hodnota funkcie f1(Sn-1). 3. Znížte hodnotu l o jeden a zapíšte príslušnú funkčnú rovnicu. Pre l=n-k (k= 2,n) to vyzerá takto fk(Sn-k)=optimálne(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2) 4. nájsť podmienene optimálne riešenie na základe výrazu (2) 5. skontrolujte, aká je hodnota l. Ak l=0, výpočet podmienene optimálnych riešení je ukončený a nájde sa optimálne riešenie úlohy pre prvý stav procesu. Ak sa l nerovná 0, prejdite na krok 3. 6. Vypočítajte optimálne riešenie úlohy pre každý nasledujúci krok procesu od konca výpočtov na začiatok. Metóda dynamiky programov umožňuje nahradiť jeden problém s mnohými premennými množstvom postupne riešených problémov s menším počtom premenných. Rozhodnutie sa robí krok za krokom. Hlavným princípom, na ktorom je založená optimalizácia viackrokového procesu, ako aj vlastnosti výpočtovej metódy, je Bellmanov princíp optimality. Optimálne správanie má tú vlastnosť, že bez ohľadu na počiatočný stav a počiatočné rozhodnutie, následné rozhodnutia musia byť optimálne vzhľadom na stav vyplývajúci z počiatočného rozhodnutia. Matematicky sa to píše ako vyjadrenie tvaru: fn-1(Sl)=optimálne(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1) (l=0,n-1)Optimum vo výraze znamená maximum alebo minimum v závislosti od stavu problému. 63. Požiadavky na úlohy riešené metódou DP Dynamické programovanie je matematická metóda na hľadanie optimálnych riešení viackrokových problémov. Viacstupňový proces je proces, ktorý sa vyvíja v priebehu času a rozkladá sa na niekoľko krokov alebo etáp. Jednou z vlastností metódy dynamického programovania je, že rozhodnutia prijaté vo vzťahu k viackrokovým procesom sa nepovažujú za jeden akt, ale za celý komplex vzájomne súvisiacich rozhodnutí. Táto postupnosť vzájomne súvisiacich rozhodnutí sa nazýva stratégia Cieľom optimálneho plánovania je vybrať stratégiu, ktorá poskytuje najlepší výsledok v zmysle vopred zvoleného kritéria. Takáto stratégia sa nazýva optimálna. Ďalšou dôležitou vlastnosťou metódy je nezávislosť optimálneho rozhodnutia prijatého v ďalšom kroku od praveku, t.j. o tom, ako proces, ktorý sa optimalizuje, dosiahol súčasný stav. Optimálne riešenie sa vyberá len s prihliadnutím na faktory charakterizujúce daný proces v súčasnosti. Metóda dynamických programov sa vyznačuje aj tým, že výber optimálneho riešenia v každom kroku by sa mal robiť s prihliadnutím na jeho dôsledky v budúcnosti. To znamená, že pri optimalizácii procesu v každom jednotlivom kroku by ste v žiadnom prípade nemali zabúdať na všetky nasledujúce kroky. 64.Ekonomická formulácia a konštrukcia matematického modelu úlohy riešenej metódou DP (na príklade úlohy rozloženia kapitálových investícií). Bellmanov vzťah recidívy. Predbežne si vysvetlíme, že metóda dynamického programovania sa aplikuje predovšetkým na tie problémy, v ktorých je optimalizovaný proces (alebo situácia) nasadený v priestore alebo čase, prípadne oboje. Nech je samotný proces (situácia) taký komplikovaný, že neexistuje spôsob, ako ho optimalizovať pomocou známych metód. Potom sa podľa metódy dynamického programovania KOMPLEXNÝ proces (operácia, situácia) rozdelí (rozdelí) do niekoľkých etáp (krokov). Toto rozdelenie je v mnohých prípadoch prirodzené, ale vo všeobecnosti je zavedené umelo. .
Napríklad, keď uvažujeme o akejkoľvek šachovej hre, každý ťah každého z hráčov len slúži rozdelenie celej dávky do samostatných krokov (stupňov). A vo vojenskej operácii na prenasledovanie jednej rakety proti druhej musí byť celý nepretržitý proces umelo rozdelený na etapy, napríklad každá sekunda pozorovania. Metóda dynamického programovania umožňuje nahradiť optimalizáciu celého komplexného procesu podmienenou optimalizáciou pre každú z fáz (kroky), po ktorých nasleduje syntéza optimálneho riadenia celého procesu. Metóda zároveň zabezpečuje, že podmienená optimalizácia v samostatnom kroku (fáze) sa vykonáva v prvom rade v záujme celej operácie. Všetky výpočty, ktoré umožňujú nájsť optimálnu hodnotu dosiahnutého účinku v n krokoch, fn(S0), sa vykonávajú podľa vzorca (1), ktorý sa nazýva základná funkcionálna Bellmanova rovnica alebo rekurentný vzťah. Pri výpočte ďalšej hodnoty funkcie fn-1 sa použije hodnota funkcie fn-(l+1) získaná v predchádzajúcom kroku a priama hodnota efektu Rl+1(Sl,Ul+1), dosiahnuté ako výsledok voľby riešenia Ul+1 pre daný stav Sl sústavy. Proces výpočtu hodnoty funkcie fn-1(l=0,n-1) Uskutočňuje sa za prirodzenej počiatočnej podmienky f0(Sn)=0, čo znamená, že mimo konečného stavu systému je účinok nulový. 65. Problém rozloženia kapitálových investícií (príklad). Na vyriešenie problému optimálneho rozloženia kapitálových investícií použijeme funkčnú Bellmanovu rovnicu. Najprv si pomocou najjednoduchšej situácie znázorníme odvodenie Bellmanovej funkcionálnej rovnice a potom na príklade ukážeme, ako túto rovnicu použiť na riešenie problému, ktorý nás zaujíma. Začnime optimálnym rozložením alokovaných kapitálových investícií vo výške K medzi dva podniky. Plánovacie oddelenia podnikov na základe svojich výpočtov vytvorili dôchodkové funkcie q(x) pre podnik P1 a h(x) pre podnik P2. Tieto funkcie znamenajú, že ak prvý alebo druhý podnik dostane investíciu vo výške x, potom prvý podnik bude prijatý príjem q(x) a druhý h(x) a hodnota x môže nadobudnúť spojité alebo známe diskrétne hodnoty od 0 do K. Ak teda spoločnosť P1 pridelí kapitálové investície vo výške x, potom spoločnosti P2 pridelí sumu K - x. V tomto prípade bude príjem q(x) prijatý od prvého podniku a h(K - x) od druhého. Ak boli investície K alokované na jedno plánovacie obdobie, potom celkový príjem z dvoch podnikov bude R(K, x) = q(x) + h(K - x). Je zrejmé, že x a podľa toho aj K - x musíme zvoliť tak, aby R(K, x) nadobudlo svoju maximálnu hodnotu, ktorú označíme F(K): Tento záznam je ako kostra pre úplnejšie záznamy. funkčná Bellmanova rovnica. KOMPLIKOVAŤ našu úlohu rozdelením kapitálových investícií do dvoch plánovacích období (dve etapy) .
Nech sa najprv rozhodne prideliť sumu x prvému podniku P1 a x druhému podniku P1. Vo všeobecnosti by sa príjem rovnal R(K, x) = q(x) + h(K - x). Ak si uvedomíme, že investície sú rozdelené na 2 obdobia (2 etapy), potom v prvom podniku bude zostatok investícií x, kde , a v druhom - .(K - x), kde príjem za druhá perióda bude q( .x) - podľa prvého zariadenia a h[.(K - x)] - podľa druhého. Dynamická optimalizácia programovania sa spravidla začína v konečnej fáze. Preto začneme od druhej fázy, pričom F1 označujeme maximálny možný príjem z dvoch podnikov v druhej etapa. Získajte Potom k uvažovanej poslednej (v našom prípade druhej) fáze tak trochu pridáme predchádzajúcu (v našom prípade prvú) fázu a nájdeme maximálny príjem z dvoch fáz spolu: Podobne pre n etáp získame kde Fn-1 je účelová funkcia, ktorá dáva najlepší výsledok pre posledných (n - 1) štádií. Výsledná funkčná Bellmanova rovnica je rekurentná, t.j. spája hodnotu Fn s hodnotou Fn-1. Vo všeobecnosti má Bellmanova rovnica tvar kde , Fn-1 - maximálny príjem pre (n - 1) posledných fáz, Fn - maximálny príjem pre všetkých n etáp. 66. Koncepcia riešenia problémov nelineárneho programovania Nech je problém nelineárneho programovania položený v tejto všeobecnej forme: nájdite také hodnoty premenných x1, x2, ..., xn, ktoré spĺňajú podmienky: a priniesť požadovaný extrém (maximum alebo minimum) cieľovej funkcie f = f(x1, x2,…, xn), (13,2) kde f(х1, …, хn) a qi(х1, …, хn) (m , 1 i =) sú skutočné nelineárne, regulárne funkcie n reálnych premenných. Podľa ich všeobecných vlastností môžu problémy nelineárneho programovania výrazne odlišné od lineárnych. Napríklad doména uskutočniteľných riešení už môže byť nekonvexná a extrém účelovej funkcie možno pozorovať v ktoromkoľvek bode uskutočniteľnej oblasti. Metódy riešenia nelineárnych problémov sa tiež výrazne líšia. Uvažujme len o niektorých prístupoch k riešeniu týchto problémov. V prvom rade je grafický prístup platný aj pri riešení najjednoduchších problémov nelineárneho programovania. Ak sú teda premenné x1 a x2 argumentmi problému, potom sa najprv na rovine týchto premenných postaví oblasť realizovateľných riešení a potom sa pomocou úrovní cieľovej funkcie určí optimálny bod v oblasti. f(x1,x2). V nelineárnom programovaní sa na riešenie mnohých problémov používa gradientný prístup. Existuje množstvo gradientových metód, ktorých podstatou je nájsť optimálny výsledok pomocou gradientu účelovej funkcie – vektora, ktorý udáva smer maximálneho nárastu cieľa pre uvažovaný bod. Vo všeobecnom prípade sa postup vyhľadávania vykonáva v iteratívnom režime od pôvodne zvoleného bodu k bodom s najlepším indikátorom. Nech je napr. -
oblasť prípustných riešení považovaný za problém a iteračný proces výpočtov začína od bodu Ďalej sa najprv uskutoční prechod pozdĺž gradientu cieľovej funkcie a potom sa vráti do oblasti. pozdĺž gradientu k narušenej hranici oblasti O2O3. 13.3 je znázornené, že Ai s nepárnymi indexmi patrí do oblasti., a body Ai s párnymi indexmi nie. Keď sa blížime k optimálnemu bodu Q, smery pracovných gradientov sa zbiehajú. Preto ideálnym kritériom na zastavenie procesu bude kolinearita cieľového gradientu a gradientu prerušenej hranice. 67. Pojem parametrického a celočíselného programovania
. Výrok a matematický model ZCLP. Pri problémoch s nedeliteľnými objektmi sú na premenné kladené celočíselné podmienky. Niekedy sa tieto podmienky vzťahujú na všetky premenné, niekedy na niektoré z premenných. Uvažujme o úplne celočíselnom probléme f=(n,j=1)∑CjXi max (n,j=1)∑AijXj=bi, i=1,m xi-celé číslo,j=1,n Teraz, na rozdiel od všeobecného problému lineárneho programovania, optimálny plán nemusí byť nevyhnutne vo vrchole mnohostenu plánu. Existujú nasledujúce metódy riešenia celočíselných problémov: 1. Metódy orezávania 2.Kombinatorické 3.Približné metódy.. Parametrické programovanie je odvetvie matematického programovania venované štúdiu optimalizačných problémov, v ktorých podmienky prípustnosti a účelová funkcia závisia od niektorých deterministických parametrov.
Definícia. Lineárne programovanie (LP) - veda o metódach výskumu a nájdení extrémnych (maximálnych a minimálnych) hodnôt lineárnej funkcie, na neznáme ktorých sú uložené lineárne obmedzenia.
Táto lineárna funkcia sa nazýva cieľ, a nazývajú sa obmedzenia, ktoré sú matematicky zapísané ako rovnice alebo nerovnice systém obmedzení.
Definícia. Matematické vyjadrenie účelovej funkcie a jej obmedzení sa nazýva matematický model ekonomického problému.
Vo všeobecnosti je matematický model úlohy lineárneho programovania (LP) napísaný ako
s obmedzeniami:
Kde x j- neznámy; aij, b i, cj sú dané konštanty.
Všetky alebo niektoré rovnice systému obmedzení možno zapísať ako nerovnice.
Matematický model v kratšom zápise má podobu
s obmedzeniami:
Definícia. Uskutočniteľné riešenie (plán) úlohy lineárneho programovania je vektor = ( X 1 , X 2 ,..., x p), splnenie systému obmedzení.
Množina prípustných riešení tvorí oblasť prípustných riešení (ODD).
Definícia. Uskutočniteľné riešenie, pri ktorom účelová funkcia dosiahne svoju extrémnu hodnotu, sa nazýva optimálne riešenie úlohy lineárneho programovania a označuje sa ako opt.
Základné prípustné riešenie (X 1 , X 2 ,...,X r , 0, …, 0) je referenčný roztok, kde r- poradie obmedzovacieho systému.
Matematický model problému LP môže byť kanonický a nekanonický.
7. Riešenie úloh lineárneho programovania grafickou metódou. Grafy obmedzujúcich funkcií. Úrovňové čiary.
Grafická metóda na riešenie problémov lineárneho programovania
Najjednoduchšia a najnázornejšia metóda lineárneho programovania je grafická metóda. Používa sa na riešenie úloh LP s dvoma premennými uvedenými v nekanonickej forme a mnohými premennými v kanonickej forme za predpokladu, že neobsahujú viac ako dve voľné premenné.
Z geometrického hľadiska sa v úlohe lineárneho programovania hľadá taký rohový bod alebo množina bodov z prípustnej množiny riešení, pri ktorej sa dosiahne najvyššia (nižšia) čiara, ktorá sa nachádza ďalej (bližšie) ako ostatné v smere najrýchlejšieho rastu.
Na nájdenie krajnej hodnoty účelovej funkcie pri grafickom riešení úloh LP sa používa vektor L() na povrchu X 1 OH 2 , ktoré označujeme . Tento vektor ukazuje smer najrýchlejšej zmeny v cieľovej funkcii. Inými slovami, vektor je normála čiary hladiny L()
Kde e 1 a e 2 - jednotkové vektory pozdĺž osí VÔL 1 a VÔL 2 v tomto poradí; teda = (∂L/∂x 1 , ∂L/∂х 2 ).
Vektorové súradnice sú koeficienty cieľovej funkcie L(). Konštrukcia nivelety bude podrobne zvážená pri riešení praktických problémov.
Algoritmus riešenia problémov
1. Nájdeme oblasť realizovateľných riešení pre systém obmedzení problému.
2. Budovanie vektora .
3. Nakreslite čiaru úrovne L 0 , ktorá je kolmá .
4. Hladinovú čiaru posúvame v smere vektora pre úlohy na maximum a v opačnom smere , pre minimálne úlohy.
Hladinová čiara sa posúva, kým nebude mať iba jeden spoločný bod s oblasťou realizovateľných riešení. Tento bod, ktorý určuje jedinečné riešenie problému LP, bude extrémnym bodom.
Ak sa ukáže, že čiara úrovne je rovnobežná s jednou zo strán ODT, potom sa v tomto prípade dosiahne extrém vo všetkých bodoch zodpovedajúcej strany a problém LP bude mať nekonečný počet riešení. Hovorí sa, že takýto LP problém má alternatívne optimum a jeho riešenie je dané vzorcom:
Kde 0 ≤ t≤ 1, 1 a 2 - optimálne riešenia v rohových bodoch ODS.
Problém LP môže byť neriešiteľný, keď sa obmedzenia, ktoré ho definujú, ukážu ako protichodné.
5.
Nájdeme súradnice extrémneho bodu a v ňom hodnotu účelovej funkcie.
Príklad 3 Výber najlepšej možnosti uvoľnenia produktu
Spoločnosť vyrába 2 druhy zmrzliny: smotanovú a čokoládovú. Na výrobu zmrzliny sa používajú dva počiatočné produkty: mlieko a plnivá, ktorých náklady na 1 kg zmrzliny a denné zásoby sú uvedené v tabuľke.
Prieskum trhu ukázal, že denný dopyt po maslovej zmrzline prevyšuje dopyt po čokoládovej, ale nie o viac ako 100 kg.
Okrem toho sa zistilo, že dopyt po čokoládovej zmrzline nepresahuje 350 kg za deň. Maloobchodná cena 1 kg krémovej zmrzliny je 16 rubľov, čokoláda - 14 rubľov.
Koľko z každého druhu zmrzliny by mala firma vyrobiť, aby maximalizovala svoje tržby?
Riešenie. Označiť: X 1 - denný objem výroby krémovej zmrzliny, kg; X 2 - denná produkcia čokoládovej zmrzliny, kg.
Urobme matematický model problému.
Ceny za zmrzlinu sú známe: 16 rubľov a 14 rubľov, takže objektívna funkcia bude vyzerať takto:
Stanovte limity na mlieko pre zmrzlinu. Jeho spotreba na smotanovú zmrzlinu je 0,8 kg, na čokoládovú zmrzlinu - 0,5 kg. Zásoba mlieka 400 kg. Preto bude prvá nerovnosť vyzerať takto:
0,8x 1 + 0,5x 2 ≤400 - prvá nerovnosť je obmedzenie. Ostatné nerovnosti sú skonštruované podobným spôsobom.
Výsledkom je systém nerovností. aká je oblasť riešenia každej nerovnosti. To sa dá dosiahnuť dosadením súradníc bodu O(0:0) do každej z nerovností. V dôsledku toho dostaneme:
Obrázok OABDEF- oblasť prípustných riešení. Zostavíme vektor (16; 14). nivelačná čiara L 0 je daná rovnicou 16x 1 +14x 2 =Konšt. Zvolíme ľubovoľné číslo, napríklad číslo 0, potom 16x 1 +14x 2 =0. Na obrázku je pre čiaru L 0 vybrané kladné číslo, ktoré sa nerovná nule. Všetky čiary úrovne sú navzájom rovnobežné. Normálny vektor čiary hladiny.
Posuňte čiaru úrovne v smere vektora. výstupný bod L 0 z oblasti realizovateľných riešení je bod D, jeho súradnice sú definované ako priesečník priamok daných rovnicami:
Vyriešením systému získame súradnice bodu D(312,5; 300), v ktorom bude optimálne riešenie, t.j.
Spoločnosť tak musí denne vyrobiť 312,5 kg maslovej zmrzliny a 300 kg čokoládovej zmrzliny, pričom príjem z predaja bude 9 200 rubľov.
8. Redukcia ľubovoľného problému lineárneho programovania na hlavný problém. Prevod obmedzení daných nerovnicami do zodpovedajúcich rovníc.
9. Simplexná metóda. Charakteristika a algoritmus metódy, jej použiteľnosť.
Na vyriešenie problému simplexnou metódou je potrebné:
1. Uveďte metódu na nájdenie optimálneho referenčného riešenia
2. Špecifikujte spôsob prechodu z jedného referenčného riešenia do druhého, na ktorom bude hodnota účelovej funkcie bližšie k optimálnemu, t.j. uveďte spôsob, ako zlepšiť referenčné riešenie
3. Stanovte kritériá, ktoré vám umožnia včas zastaviť enumeráciu referenčných riešení na optimálnom riešení alebo dospieť k záveru o absencii optimálneho riešenia.
Algoritmus simplexovej metódy na riešenie úloh lineárneho programovania
1. Preneste problém do kanonickej podoby
2. Nájdite počiatočné podporné riešenie s „jednotkovým základom“ (ak neexistuje podporné riešenie, potom problém nemá riešenie, kvôli nekompatibilite systému obmedzení)
3. Vypočítajte odhady expanzií vektorov z hľadiska bázy referenčného riešenia a vyplňte tabuľku simplexovej metódy.
4. Ak je splnené kritérium jedinečnosti optimálneho riešenia, riešenie problému končí
5. Ak je splnená podmienka existencie množiny optimálnych riešení, jednoduchým výpočtom sa nájdu všetky optimálne riešenia
10. Dopravná úloha. Definícia, typy, metódy hľadania počiatočného riešenia dopravného problému.
Problém dopravy je jedným z najbežnejších problémov lineárneho programovania. Jeho cieľom je vyvinúť čo najracionálnejšie spôsoby a prostriedky prepravy tovaru, eliminovať nadmerne diaľkovú, protismernú, opakovanú prepravu.
1. Nájdenie počiatočného referenčného riešenia;
2. Kontrola optimálnosti tohto riešenia;
3. Prechod od jedného základného riešenia k druhému.
T10. Vyhlásenie problému lineárneho programovania
matematický model Ekonomický problém je súbor matematických vzťahov, ktoré popisujú ekonomický proces.
Na zostavenie matematického modelu je potrebné:
1. vybrať premenné úlohy;
2. vypracovať systém obmedzení;
3. nastaviť účelovú funkciu.
Premenné úlohy sa nazývajú veličiny x 1 , x 2 ,…, x n, ktoré plne charakterizujú ekonomický proces. Zvyčajne sa píšu ako vektor X \u003d (x 1, x 2, ..., x n).
Systém obmedzenia úloh je súbor rovníc a nerovníc, ktoré sú splnené premennými problému a ktoré vyplývajú z obmedzených zdrojov a iných ekonomických podmienok, napríklad z pozitivity premenných. Vo všeobecnosti vyzerajú takto:
Cieľová funkcia sa nazýva funkcia F(X) = f(x 1 , x 2 ,…, x n) premenných úlohy, ktorá charakterizuje kvalitu úlohy a ktorej extrém je potrebné nájsť.
Všeobecný problém matematického programovania je formulovaný takto: nájdite premenné úlohy x 1 , x 2 ,…, x n, ktoré poskytujú extrém účelovej funkcie
F (X) \u003d f (x 1, x 2, ..., x n) ® max (min) (2)
a spĺňať systém obmedzení (1).
Ak sú cieľová funkcia (2) a systém obmedzení (1) lineárne, potom sa problém matematického programovania nazýva problém lineárneho programovania (LPP).
Volá sa vektor X (súbor úlohových premenných). prijateľné riešenie alebo plán PLP, ak spĺňa systém obmedzení (1). Uskutočniteľný plán X, ktorý poskytuje extrém účelovej funkcie, sa nazýva optimálne riešenie ZLP.
2. Príklady zostavovania matematických modelov ekonomických problémov
Štúdium konkrétnych výrobných situácií vedie k ZLP, ktoré sú interpretované ako problémy optimálneho využitia obmedzených zdrojov.
1.Problém optimálneho výrobného plánu
Na výrobu dvoch druhov výrobkov T 1 a T 2 sa používajú tri druhy zdrojov S 1, S 2, S 3. Zásoby zdrojov, počet jednotiek zdrojov vynaložených na výrobu výrobnej jednotky, ako aj zisk z predaja výrobnej jednotky sú uvedené v tabuľke:
Je potrebné nájsť taký plán výroby produktov, pri ktorom bude zisk z jeho predaja maximálny.
Riešenie.
Označme x 1, x 2 - počet jednotiek výroby, respektíve T 1 a T 2, plánovaných na výrobu. Na ich výrobu budú potrebné (x 1 + x 2) jednotky zdroja S 1, (x 1 + 4x 2) jednotky zdroja S 2, (x 1) jednotky zdroja S 3. Spotreba zdrojov S 1 , S 2 , S 3 by nemala presiahnuť ich zásoby, resp. 8, 20 a 5 jednotiek.
Potom možno ekonomicko-matematický model problému sformulovať takto:
Nájdite plán výroby X \u003d (x 1, x 2), ktorý vyhovuje systému obmedzení: 
a stav
pod ktorou je funkcia nadobúda maximálnu hodnotu.
Problém možno ľahko zovšeobecniť na prípad výroby n druhov výrobkov s použitím m druhov zdrojov.
2.Problém optimálnej stravy
Existujú dva druhy potravín K 1 a K 2 obsahujúce živiny S 1 , S 2 a S 3 . Obsah počtu živných jednotiek v 1 kg každého druhu krmiva, požadované minimum živín, ako aj náklady na 1 kg krmiva sú uvedené v tabuľke:
Je potrebné zostaviť dennú dávku, ktorá má minimálne náklady, v ktorej by obsah každého druhu živín nebol nižší ako stanovený limit.
Riešenie.
Označme x 1, x 2 - množstvo krmiva K 1 a K 2 zahrnuté v dennej strave. Potom bude táto strava obsahovať (3x 1 + x 2) jednotky živiny S 1, (x 1 + 2x 2) jednotky látky S 2, (x 1 + 6x 2) jednotky živiny S 3. Keďže obsah živín S 1 , S 2 a S 3 v strave by mal byť 9, 8 a 12 jednotiek, možno ekonomicko-matematický model úlohy formulovať nasledovne:
Zostavte dennú stravu X \u003d (x 1, x 2), ktorá spĺňa systém obmedzení:
a stav
pod ktorou je funkcia nadobúda minimálnu hodnotu.
Záznamové formuláre PLP
V LLP je potrebné nájsť extrém lineárnej cieľovej funkcie:
s obmedzeniami:
a podmienka nezápornosti
kde a ij , b i , c j ( , ) sú dané konštanty.
Takto je zapísaný ZLP všeobecný formulár. Ak systém obmedzení obsahuje iba nerovnosti, potom je LLP reprezentovaný v štandardné formulár. Kanonický (hlavný) forma zápisu ZLP je zápis, keď systém obmedzení obsahuje iba rovnosti. Takže vyššie uvedené LLP sú napísané v štandardnej forme.
Všeobecné, štandardné a kanonické formy LLP sú ekvivalentné v tom zmysle, že každú z nich možno pomocou jednoduchých transformácií prepísať do inej formy. To znamená, že ak existuje spôsob, ako vyriešiť jeden z týchto problémov, potom je možné určiť optimálny plán pre ktorýkoľvek z problémov.
Aby sme mohli prejsť z jednej formy zápisu LLP do druhej, musíme byť schopní prejsť od obmedzení nerovnosti k obmedzeniam rovnosti a naopak.
Obmedzenie nerovnosti (£) možno previesť na obmedzenie rovnosti pridaním ďalšej nezápornej premennej na jej ľavú stranu a obmedzenie nerovnosti (³) možno previesť na obmedzenie rovnosti odčítaním ďalšej nezápornej premennej od jej ľavá strana. Počet zavedených dodatočných nezáporných premenných sa rovná počtu transformovaných obmedzení nerovností.
Predstavený dodatočné premenné majú určitý ekonomický zmysel. Ak teda obmedzenia pôvodnej PLP odrážajú spotrebu a dostupnosť zdrojov, potom sa hodnota dodatočnej premennej PLP v kanonickej forme rovná objemu nevyužitého zodpovedajúceho zdroja.
Príklad 1. Napíšte v kánonickom tvare ZLP:
s obmedzeniami:
Riešenie.
Účelová funkcia zostáva nezmenená:
Systém nerovností sa transformuje na systém rovnosti:
Pri riešení CŽV grafickou metódou je potrebný prechod z kanonickej formy na štandardnú.
Ak chcete dostať LLP do štandardnej formy, použite Jordan-Gaussova metóda riešenia SLAU. Na rozdiel od Gaussovej metódy, v ktorej je rozšírená matica systému redukovaná na stupňovitú formu, v Jordan-Gaussovej metóde sa tvorí matica identity ako súčasť rozšírenej matice. Preto tu nie je potrebný spätný pohyb.
Ak chcete previesť pôvodný kanonický LLP na ekvivalentný štandard LLP:
a) v rozšírenej matici systému obmedzení je zvolený nenulový prvok a qp. Tento prvok sa nazýva povoľný a q - i riadok a p-tý stĺpec nazývaný aktivačný riadok a povoliť stĺpec.
b) rozlišovací reťazec sa prepíše bez zmeny a všetky prvky rozlišovacieho stĺpca okrem rozlišovacieho stĺpca sa nahradia nulami. Zvyšné prvky rozšírenej matice sa určujú pomocou „pravidla obdĺžnika“:
Uvažujme štyri prvky rozšírenej matice: prvok a ij, ktorý sa má transformovať, rozlišovací prvok a qp a prvky a i p a a qj . Na nájdenie prvku a ij je potrebné od prvku a ij odčítať súčin prvkov a i p a a qj umiestnených v opačných vrcholoch obdĺžnika, delený rozlišovacím prvkom a qp:
c) povolené neznáme sú súčasne vylúčené z účelovej funkcie. Na tento účel sa koeficienty účelovej funkcie zapíšu do rozšírenej matice v poslednom riadku. Výpočty berú do úvahy, že aktivačný prvok v poslednom riadku nie je možné vybrať.
Príklad 2. Zmena na štandardný formulár:
Riešenie.
Pomocou Jordan-Gaussovej metódy prinášame systém obmedzujúcich rovníc LLP na ekvivalentný systém nerovností. Vyberme si tretí prvok prvého riadku ako rozlišovací prvok:
Číslo -9 získané v poslednom stĺpci posledného riadku je potrebné zapísať do účelovej funkcie s opačným znamienkom. V dôsledku transformácií má LLP podobu:
Pretože premenné x 2 a x 3 sú nezáporné, potom ich vyradíme, môžeme ZLP zapísať v symetrickom tvare:
V kanonickej forme LLP možno objektívnu funkciu minimalizovať aj maximalizovať. Prejsť od hľadania maxima k hľadaniu minima alebo naopak, stačí zmeniť znamienka koeficientov cieľovej funkcie: F 1 = - F. Výsledný problém a pôvodný LLP majú rovnaké optimálne riešenie a hodnoty účelových funkcií na tomto riešení sa líšia len v znamenie.
vlastnosti ZLP
1. Množina všetkých prípustných riešení sústavy obmedzení úlohy lineárneho programovania je konvexná.
Súbor bodov sa nazýva konvexné, ak obsahuje celý segment spájajúci ľubovoľné dva body tejto množiny.
Podľa tejto definície je mnohouholník na obr. 1a konvexná množina, zatiaľ čo mnohouholník na obr. 1b nie je, pretože segment MN medzi jeho dvoma bodmi M a N nepatrí úplne do tohto mnohouholníka.
Konvexné množiny môžu byť nielen polygóny. Príklady konvexných množín sú kruh, sektor, segment, kocka, pyramída atď.
2. Ak má LLP optimálne riešenie, potom lineárna funkcia nadobudne maximálnu (minimálnu) hodnotu v jednom z rohových bodov rozhodovacieho mnohostenu. Ak lineárna funkcia nadobudne maximálnu (minimálnu) hodnotu vo viac ako jednom rohovom bode, potom ju získa v akomkoľvek bode, ktorý je konvexnou lineárnou kombináciou týchto bodov.
Bod X sa nazýva konvexná lineárna kombinácia body X 1 , X 2 ,…, X n, ak sú splnené tieto podmienky:
X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,
αj ≥ 0, Σαj = 1.
Je zrejmé, že v špeciálnom prípade pre n = 2 je konvexná lineárna kombinácia dvoch bodov úsečkou, ktorá ich spája.
3. Každé prípustné základné riešenie kanonického systému obmedzení LLP zodpovedá rohovému bodu mnohostenu riešenia a naopak každému rohovému bodu mnohostenu riešenia zodpovedá prípustné základné riešenie.
Z posledných dvoch vlastností vyplýva, že ak má LLP optimálne riešenie, potom sa zhoduje aspoň s jedným z jeho prípustných základných riešení.
Extrém lineárnej funkcie LLP teda treba hľadať medzi konečným počtom jej prípustných základných riešení.
Prednáška 2
IN kanonická forma
prípustné riešenie PLP(prijateľný plán).
optimálne riešenie LLP.
Nevyhnutnosť
Príklad. 
Napíšme problém kanonická forma
Špeciálne situácie grafického riešenia ZLP
Okrem prípadov, keď je úloha jediné optimálne riešenie pre a , môže byť špeciálne situácie:
1. úloha má nekonečné množstvo optimálnych riešení – extrém funkcie sa dosiahne na segmente ( alternatívne optimum)- obrázok 2;
2. úloha neriešiteľné z dôvodu neobmedzenosti RSO, alebo - Obrázok 3;
3. RSO - jediný bod Ach, potom;
4. úloha neriešiteľné ak má RSO prázdnu oblasť.
A
Obrázok 2 Obrázok 3
Ak je čiara úrovne rovnobežná so stranou oblasti realizovateľných riešení, potom sa extrém dosiahne vo všetkých bodoch strany. Problém má nekonečné množstvo optimálnych riešení - alternatívne optimum . Optimálne riešenie sa nájde podľa vzorca
kde je parameter. Pre akúkoľvek hodnotu od 0 do 1 môžete získať všetky body segmentu, pre každý z nich má funkcia rovnakú hodnotu. Odtiaľ pochádza názov – alternatívne optimum.
Príklad. Vyriešte graficky problém lineárneho programovania ( alternatívne optimum):
Otázky na sebaovládanie
1. Napíšte úlohu lineárneho programovania vo všeobecnej forme.
2. Napíšte úlohu lineárneho programovania v kanonických a štandardných formách.
3. Aké transformácie možno použiť na prechod od všeobecnej alebo štandardnej formy problému lineárneho programovania ku kanonickej?
4. Definujte uskutočniteľné a optimálne riešenia problému lineárneho programovania.
5. Ktoré z riešení je „najlepšie“ pre úlohu minimalizácie funkcie ak 
?
6. Ktoré z riešení je „najlepšie“ pre problém maximalizácie funkcie ak ?
7. Napíšte štandardný tvar matematického modelu úlohy lineárneho programovania s dvoma premennými.
8. Ako zostrojiť polrovinu danú lineárnou nerovnicou s dvomi premennými 
?
9. Ako sa nazýva riešenie sústavy lineárnych nerovníc s dvoma premennými? Zostrojte v rovine doménu realizovateľných riešení takého systému lineárnych nerovností, ktoré:
1) má jedinečné riešenie;
2) má nekonečnú množinu riešení;
3) nemá riešenie.
10. Napíšte pre lineárnu funkciu 
vektorový gradient, pomenujte typ čiar úrovne. Ako sú čiary gradientu a úrovne umiestnené voči sebe navzájom?
11. Formulujte algoritmus pre grafickú metódu riešenia štandardného LLP s dvoma premennými.
12. Ako nájsť súradnice a hodnoty riešenia?
13. Zostrojte oblasť uskutočniteľných riešení, gradientové a úrovňové čiary pre problémy lineárneho programovania, v ktorých:
1) sa dosiahne v jednom bode a - na segmente ODR;
2) sa dosiahne v jedinom bode ODS a .
14. Uveďte geometrickú ilustráciu LLP, ak:
1) má jedinečné optimálne riešenia pre a ;
2) má súbor optimálnych riešení pre .
Prednáška 2
grafická metóda na nájdenie optimálneho riešenia
1. Formy lineárnych matematických modelov a ich transformácia
2. Grafická metóda riešenia úlohy lineárneho programovania
3. OSOBITNÉ SITUÁCIE GRAFICKÉHO RIEŠENIA LLP
4. Grafické riešenie ekonomických problémov lineárneho programovania
Formy lineárnych matematických modelov a ich transformácia
Matematický model úlohy lineárneho programovania (LPP) možno napísať v jednej z troch foriem.
IN všeobecná forma matematického modelu je potrebné nájsť maximum alebo minimum účelovej funkcie; systém obmedzení obsahuje nerovnosti a rovnice; nie všetky premenné môžu byť nezáporné.
IN kanonická forma matematický model potrebuje nájsť maximum účelovej funkcie; systém obmedzení pozostáva len z rovníc; všetky premenné sú nezáporné.
V štandardnej forme matematického modelu je potrebné nájsť maximum alebo minimum funkcie; všetky obmedzenia sú nerovnosti; všetky premenné sú nezáporné.
Riešenie systému obmedzení, ktoré spĺňa podmienky nezápornosti premenných sa nazýva tzv. prípustné riešenie PLP(prijateľný plán).
Súbor realizovateľných riešení je tzv oblasť realizovateľných riešení LLP.
Uskutočniteľné riešenie, pri ktorom účelová funkcia dosiahne extrémnu hodnotu, sa nazýva optimálne riešenie LLP.
Tieto tri formy celoživotného vzdelávania sú ekvivalentné v tom zmysle, že každú z nich možno pomocou matematických transformácií zredukovať na inú formu.
Nevyhnutnosť prechod od jednej formy matematického modelu k druhej spojené s metódami riešenia problémov: napríklad simplexová metóda, široko používaná v lineárnom programovaní, sa aplikuje na problém napísaný v kanonickej forme a grafická metóda sa aplikuje na štandardnú formu matematického modelu.
Prechod na kanonickú notáciu ZLP.
Príklad.
Napíšme problém kanonická forma, čím sa do ľavej strany prvej nerovnosti systému obmedzení zavedie dodatočná premenná (zostatok) so znamienkom „+“ a do ľavej strany druhej nerovnosti sa zavedie ďalšia premenná so znamienkom „mínus“.
Ekonomický význam rôznych dodatočných premenných nemusí byť rovnaký: závisí od ekonomického významu obmedzení, v ktorých sú tieto premenné zahrnuté.
Takže v probléme použitia surovín ukazujú zvyšok surovín a v probléme výberu optimálnych technológií ukazujú nevyužitý čas podniku pomocou určitej technológie; v probléme rezania - uvoľnenie polotovarov danej dĺžky presahujúcej plán atď.
Základom riešenia ekonomických problémov sú matematické modely.
Zostavenie matematického modelu zahŕňa:matematický model problém je súbor matematických vzťahov, ktoré popisujú podstatu problému.
- výber premennej úlohy
- vytvorenie systému obmedzení
- výber objektívnej funkcie
Premenné úlohy sa nazývajú veličiny X1, X2, Xn, ktoré plne charakterizujú ekonomický proces. Zvyčajne sa zapisujú ako vektor: X=(X 1 , X 2 ,...,X n).
Systém obmedzeníúlohy sú súbor rovníc a nerovníc, ktoré opisujú obmedzené zdroje v uvažovanom probléme.
cieľová funkciaúloha sa nazýva funkcia premenných úlohy, ktorá charakterizuje kvalitu úlohy a ktorej extrém je potrebné nájsť.
Vo všeobecnosti možno problém lineárneho programovania napísať takto:
Tento záznam znamená nasledovné: nájdite extrém účelovej funkcie (1) a zodpovedajúce premenné X=(X 1 , X 2 ,...,X n) za predpokladu, že tieto premenné spĺňajú systém obmedzení (2) a nie -podmienky negativity (3) .
Prijateľné riešenie(plán) úlohy lineárneho programovania je ľubovoľný n-rozmerný vektor X=(X 1 , X 2 ,...,X n), ktorý vyhovuje systému obmedzení a podmienok nezápornosti.
Súbor realizovateľných riešení (plánov) problému tvorí rozsah realizovateľných riešení(RSO).
Optimálne riešenie(plán) úlohy lineárneho programovania je také realizovateľné riešenie (plán) úlohy, pri ktorej účelová funkcia dosahuje extrém.
Príklad zostavenia matematického modelu
Úloha využívať zdroje (suroviny)
podmienka: Na výrobu n druhov výrobkov sa používa m druhov zdrojov. Vytvorte matematický model.
Známe:
- b i (i = 1,2,3,...,m) sú zásoby každého i-tého typu zdroja;
- a ij (i = 1,2,3,...,m; j=1,2,3,...,n) sú náklady každého i-tého typu zdroja na produkciu jednotkového objemu j-tý typ produktu;
- c j (j = 1,2,3,...,n) je zisk z predaja jednotkového objemu j-tého druhu produktu.
Je potrebné vypracovať plán výroby produktov, ktorý poskytuje maximálny zisk pri daných obmedzeniach zdrojov (surovín).
Riešenie:
Zavedieme vektor premenných X=(X 1 , X 2 ,...,X n), kde x j (j = 1,2,...,n) je objem produkcie j-tého typu produkt.
Náklady i-tého typu zdroja na výrobu daného objemu x j výrobkov sa rovnajú a ij x j , preto obmedzenie použitia zdrojov na výrobu všetkých druhov výrobkov má podobu:
Zisk z predaja j-tého typu produktu sa rovná c j x j , teda účelová funkcia sa rovná:
Odpoveď- Matematický model vyzerá takto:
Kanonická forma problému lineárneho programovania
Vo všeobecnom prípade je problém lineárneho programovania napísaný tak, že rovnice aj nerovnice sú obmedzeniami a premenné môžu byť nezáporné alebo ľubovoľne sa meniace.
V prípade, že všetky obmedzenia sú rovnice a všetky premenné spĺňajú podmienku nezápornosti, problém lineárneho programovania sa nazýva kanonický.
Môže byť reprezentovaný súradnicovým, vektorovým a maticovým zápisom.
Kanonický problém lineárneho programovania v súradnicovom zápise má tvar:
Kanonický problém lineárneho programovania v maticovom zápise má tvar:
- A je matica koeficientov sústavy rovníc
- X je stĺpcová matica premenných úlohy
- Ao je maticový stĺpec pravých častí systému obmedzení
Často sa používajú problémy lineárneho programovania, nazývané symetrické, ktoré v maticovom zápise majú tvar:
Redukcia všeobecného problému lineárneho programovania na kanonickú formu
Vo väčšine metód riešenia problémov lineárneho programovania sa predpokladá, že systém obmedzení pozostáva z rovníc a prirodzených podmienok pre nezápornosť premenných. Pri zostavovaní modelov ekonomických problémov sa však obmedzenia tvoria najmä v podobe sústavy nerovností, preto je potrebné vedieť prejsť od sústavy nerovností k sústave rovníc.
Dá sa to urobiť takto:Vezmite lineárnu nerovnosť a 1 x 1 +a 2 x 2 +...+a n x n ≤b a pridajte k jej ľavej strane nejakú hodnotu x n+1 tak, aby sa z nerovnosti stala rovnosť a 1 x 1 +a 2 x 2 + ...+a n x n +x n+1 =b. Navyše táto hodnota x n+1 nie je záporná.
Uvažujme všetko na príklade.
Príklad 26.1Redukujte problém lineárneho programovania na kanonickú formu:
Riešenie:
Prejdime k problému hľadania maxima účelovej funkcie.
Za týmto účelom zmeníme znamienka koeficientov účelovej funkcie.
Na prevod druhej a tretej nerovnice systému obmedzení do rovníc zavedieme nezáporné dodatočné premenné x 4 x 5 (táto operácia je na matematickom modeli označená písmenom D).
Premenná x 4 sa zadáva naľavo od druhej nerovnosti so znamienkom „+“, keďže nerovnosť má tvar „≤“.
Premenná x 5 sa zadáva na ľavej strane tretej nerovnosti so znamienkom „-“, keďže nerovnosť má tvar „≥“.
Premenné x 4 x 5 sa zadávajú do účelovej funkcie s koeficientom. rovná nule.
Úlohu zapisujeme v kanonickom tvare.
Načítava...