Úloha optimalizácie v matematike sa problém nájdenia extrému reálnej funkcie v určitom regióne nazýva. Spravidla považujeme oblasti, ktoré patria a sú vymedzené súborom rovnosti a nerovností.
3.1. Popis
Úloha lineárne programovanie spočíva v tom, že je potrebné maximalizovať alebo minimalizovať nejaký lineárny funkcionál na viacrozmernom priestore za daných lineárnych obmedzení.
Každý z lineárne nerovnosti do premenných ohraničuje polpriestor v zodpovedajúcom lineárnom priestore. Výsledkom je, že všetky nerovnosti viažu určitý polytop (možno nekonečný), nazývaný aj mnohostenný kužeľ.
Rovnica W (x) = c, kde W (x) je maximalizovaný (alebo minimalizovaný) lineárny funkcionál, generuje nadrovinu L (c). Zo závislosti na c vzniká rodina paralelných nadrovín. V tomto prípade má extrémny problém nasledujúcu formuláciu: je potrebné nájsť najväčšie c také, aby nadrovina L (c) pretínala polytop aspoň v jednom bode. Všimnite si, že priesečník optimálnej nadroviny a mnohostenu bude obsahovať aspoň jeden vrchol a bude ich viac, ak priesečník obsahuje hranu alebo k-rozmernú plochu. Preto maximum funkcionálu možno hľadať vo vrcholoch mnohostenu. Princíp simplexovej metódy spočíva v tom, že sa vyberie jeden z vrcholov mnohostenu, po ktorom sa začne pohybovať po svojich okrajoch od vrcholu k vrcholu v smere zvyšovania hodnoty funkcionálu. Pri prechode hrany z aktuálneho vrcholu do iného vrcholu s viac vysoká hodnota funkčné nie je možné, má sa za to optimálna hodnota c nájdené.
Podstatou simplexovej metódy je, že ak je počet neznámych väčší ako počet rovníc, tak tento systém neurčitý s nespočetnými riešeniami. Na vyriešenie systému sú všetky neznáme ľubovoľne rozdelené na základné a voľné. Počet základných premenných je určený počtom lineárne nezávislých rovníc. Zvyšok neznámych je voľný. Sú im dané ľubovoľné hodnoty a potom dosadené do systému. Akejkoľvek množine voľných neznámych môže byť pridelený nekonečný počet ľubovoľných hodnôt, ktoré poskytnú nekonečný počet riešení. Ak sa všetky voľné neznáme rovnajú nule, riešenie bude pozostávať z hodnôt základných neznámych. Toto riešenie sa nazýva základné.
V teórii lineárneho programovania existuje teorém, ktorý hovorí, že medzi základnými riešeniami systému možno nájsť optimálne a v niektorých prípadoch niekoľko optimálnych riešení, z ktorých všetky poskytnú extrém. objektívna funkcia... Ak teda nájdete základný plán a následne ho vylepšíte, získate optimálne riešenie. Na tomto princípe je postavená simplexná metóda.
Postupnosť výpočtov simplexovou metódou možno rozdeliť do dvoch hlavných fáz:
1. nájdenie pôvodného vrcholu množiny realizovateľných riešení;
2. sekvenčný prechod zhora nahor, vedúci k optimalizácii hodnoty cieľovej funkcie.
V niektorých prípadoch je počiatočné riešenie zrejmé alebo jeho definícia nevyžaduje zložité výpočty, napríklad keď sú všetky obmedzenia reprezentované nerovnosťami v tvare „menšie alebo rovné“ (vtedy je nulový vektor určite realizovateľným riešením, aj keď, s najväčšou pravdepodobnosťou to nie je ani zďaleka optimálne). Pri takýchto problémoch sa prvá fáza simplexovej metódy nemusí vôbec vykonávať. Simplexová metóda sa podľa toho delí na jednofázový a
dvojfázový.
3.2. Algoritmus simplexnej metódy
Rozšírené vyhlásenie o probléme
Zvážte nasledujúci problém lineárneho programovania:
Tento problém teraz predstavujeme v ekvivalentnej posilnenej forme. Je potrebné maximalizovať Z, kde:
Tu x sú premenné z pôvodného lineárneho funkcionálu; x s - nové premenné, ktoré dopĺňajú staré tak, že sa nerovnosť mení na rovnosť; c - koeficienty pôvodného lineárneho funkcionálu; Z je premenná, ktorá sa má maximalizovať. Polpriestory a priesečník tvoria mnohosten predstavujúci množinu realizovateľných riešení. Rozdiel medzi počtom premenných a rovníc udáva počet stupňov voľnosti. Jednoducho povedané, ak vezmeme do úvahy vrchol mnohostenu, je to počet hrán, po ktorých sa môžete ďalej pohybovať.
Potom môžete takémuto počtu premenných priradiť hodnotu 0 a zavolať
Zvážte metódu riešenia problému CPU pomocou myšlienok simplexnej metódy. Hlavná črta úloh CPU spočíva v návrhu cieľovej funkcie a v premenných, ktoré vykazujú odchýlky od požadovanej úrovne dosiahnutia cieľov. Ak vezmeme do úvahy tieto vlastnosti, potom obvyklé simplexná metóda... Ukážme si to na príklade, ktorý sme uvažovali vyššie. Algoritmus je trochu zjednodušený, pretože tu je zrejmé pôvodné základné riešenie. Úlohu základných premenných pre prvotný návrh tu zohrávajú negatívne odchýlky „d“, ktoré sú do modelu zahrnuté s koeficientmi +1. Ťažšie je to s reťazcom pre koeficienty účelovej funkcie, t.j. s deliacou čiarou. Ako vieme, koeficienty rozptylu v cieľovej funkcii úlohy CPU sú váhy, ktoré zoraďujú ciele podľa priority. Ich číselné hodnoty zvyčajne nie sú definované. Je dôležité, aby faktor odchýlky pre cieľové obmedzenie s vyššou prioritou bol výrazne väčší ako faktor odchýlky pre cieľ s nižšou prioritou. Preto je pre pohodlie výpočtov odhadovaný riadok rozdelený do niekoľkých riadkov (podľa počtu priorít) a výpočty sa vykonávajú na každom riadku samostatne.
Nech je teda úloha vyriešená min Z = P 1 d 1 - + P 2 d 2 - + P 3 d 3 + + P 4 d 4 -,
za predpokladu, že
7x 1 + 6x 2 + d1 - - d1 + = 30;
2x 1 + 3x 2 + d2 - - d2 + = 12;
6x 1 + 5x 2 + d3 - - d3 + = 30;
x2 + d4 - - d4 + = 7;
x 1, x 2, d i -, d i + ³ 0 (i =).
Zostavme si úvodnú simplexnú tabuľku (tabuľka 5.1.)
Tabuľka 5.1 - Pôvodná simplexná tabuľka
| C j C B | Základ | Riešenie | 0 x 1 | 0 x 2 | P 1 d 1 - | P 2 d 2 - | d 3 - | P 4 d 4 - | d1+ | d2+ | P3d3+ | d4+ | q |
| P 1 P 2 P 4 | d 1 - d 2 - d 3 - d 4 - | 7 | -1 | -1 | -1 | -1 | 30/7 30/6 - | ||||||
| Z j - С j | P 4 P 3 P 2 P 1 | -1 | -1 | -1 | -1 |
Ako viete, prvky odhadovaného riadku (Z j - C j) sa vypočítajú podľa pravidla: "zo súčtu súčinov prvkov stĺpca" C v "prvkami zodpovedajúceho stĺpca sa element horný riadok". Napríklad pre stĺpec „riešenie“ sa prvok „Z j - C j“ rovná: Р 1 * 30 + Р 2 * 12 + 0 * 30 + р 4 * 7 - 0 = 30Р 1 + 12Р 2 + 7Р 4 a koeficienty pre príslušné P i (i =) sú vypísané v tomto stĺpci v bloku "Z j - C j" (čítaj zdola nahor). Pre stĺpec "x 1": Р 1 * 7 + Р 2 * 2 + 0 * 6 + Р 4 * 0 - 0 = 7Р 1 + 2Р 2, a to sú koeficienty pre Р 1 a Р 2 v bloku " Z j - C j " atď.
Keďže problém s CPU je vždy vyriešený na minimum, potom bude riešenie optimálne, ak všetky prvky hodnotiacej línie nebudú pozitívne. V našom prípade sú dva odhady (v stĺpcoch „x 1“ a „x 2“) kladné, preto plán nie je optimálny. Na určenie premennej zahrnutej do základu pri prvej iterácii určíme najvyšší kladný odhad. Určuje sa znamienkom koeficientu pri P 1, od r P 1 >> P 2 >> P 3 >> P 4. Pri rovnakých koeficientoch na P 1 "stúpte" o jeden riadok vyššie a tam vyberte najvyšší koeficient. V prípade úplnej rovnosti pre všetky riadky sa vyberie ktorýkoľvek z nich. V našom prípade bude rozlišovacím stĺpcom stĺpec "x 1" (od 7> 6). Rozlišovací riadok sa vyberá rovnakým spôsobom ako pri simplexnej metóde - najmenším simplexným vzťahom q (prvky stĺpca „riešenie“ sú rozdelené kladnými prvkami rozlišovacieho stĺpca). V tabuľke 5.1 je najmenší pomer q v prvom riadku. Takže pri ďalšej iterácii sa do základu zavedie premenná "x 1" a na výstup sa dostane "d 1 -". Tabuľku prepočítame ako pri bežnej simplexnej metóde (tabuľka 5.2.)
Tabuľka 5.2 - Druhá simplexná tabuľka
| C j C B | Základ | Riešenie | x 1 | x 2 | P 1 d 1 - | P 2 d 2 - | d 3 - | P 4 d 4 - | d1+ | d2+ | P3d3+ | d4+ | q |
| P 2 P 4 | x 1 d 2 - d 3 - d 4 - | 30/7 24/7 30/7 | 6/7 9/7 1/7 | 1/7 2/7 6/7 | 1/7 2/7 6/7 | -1 | -1 | -1 | 30/6 24/9 - | ||||
| Z j - C j | P 4 P 3 P 2 P 1 | 24/7 | 9/7 | 2/7 -1 | 2/7 | -1 | -1 | -1 |
Ako vidíte, pri druhej iterácii sa zo základu odvodí d 2, do základu sa vloží x 2. A tak ďalej, kým nedosiahneme optimálne riešenie. Po 4. iterácii dostaneme tabuľku 5.3.
Tabuľka 5.3 - Súhrnná simplexná tabuľka
| C j C B | Základ | Riešenie | x 1 | x 2 | P 1 d 1 - | P 2 d 2 - | d 3 - | P 4 d 4 - | d1+ | d2+ | P3d3+ | d4+ |
| P 4 | d 2 + x 2 d 1 + d 4 - | 1,6 1,2 0,2 -1,2 | -1 | -1 | 0,6 0,2 1,2 -0,2 | -0,6 -0,2 -1,2 0,2 | -1 | |||||
| Z j - C j | P 4 P 3 P 2 P 1 | -1,2 | -1 | -1 | -0,2 | 0,2 -1 | -1 |
Skutočnosť, že v riadku pre P 4 je kladný prvok (v stĺpci d 3 +), znamená, že štvrtý cieľ nie je úplne splnený. V tomto prípade sa účelová funkcia rovná P 4, to je jej minimálna možná hodnota. Vo všeobecnosti sa odhad premennej d 3 + rovná (0,2 Р 4 - Р 3), a keďže Р 3 >> Р 4, je nakoniec záporný. Všetky ostatné odhady sú nepozitívne, preto je návrh z pohľadu simplexovej metódy optimálny.
Riešenie tohto problému možno komentovať nasledujúcim spôsobom... Na splnenie tejto úlohy je potrebné vydať druhý produkt v množstve 6 jednotiek. (x 2 = 6). Nie vydať prvé produkty. Zároveň bol prvý a druhý cieľ prekročený o 6 jednotiek. (d 1 + = d 2 + = 6) a štvrtý má nižšiu výkonnosť o 1 jednotku. (d4- = 1). Získali sme teda 6 jednotiek zisku. viac ako požadovaná úroveň, prvý zdroj bol použitý nad normálny limit o 6 jednotiek a výroba 2. typu v požadovanom objeme nevyšla - namiesto 7 jednotiek. uvoľnený 6 (2. zdroj nestačil, jeho „ekonomika“ je cieľom vyššej priority).
Na záver, ako príklad, ako modelovať úlohu CPU, namodelujme inú úlohu.
Príklad 5.2... Vedenie mesta plánuje rozšírenie športovej základne. Na tieto účely bolo z rozpočtu mesta vyčlenených 5,4 milióna rubľov. Dodatočne sa plánovalo vybudovať štyri druhy športovísk: tenisové kurty, plavárne, mikroštadióny (atletiská) a telocvične. Údaje o týchto projektoch sú nasledovné (tabuľka 5.4).
Tabuľka 5.4 - Informácie o zariadeniach vo výstavbe
Riešenie. Mesto na tieto účely vyčlenilo 20 hektárov voľnej plochy, no v prípade potreby je možné túto plochu zväčšiť. Pri realizácii tohto projektu administratíva stanovuje nasledujúce ciele v poradí dôležitosti:
1) splniť sumu pridelenú v rozpočte;
2) vybudované športové zariadenia musia poskytovať minimálne 14 000 návštev týždenne;
3) ak je to možné, uspokojiť očakávaný dopyt po športových zariadeniach. Pri formulovaní cieľovej funkcie pre tieto objektívne obmedzenia použite váhy úmerné očakávanému použitiu;
4) počas realizácie projektu, ak je to možné, neberte viac ako je pridelené voľné miesto na 20 hektároch.
Pri zostavovaní modelu tejto úlohy budeme mať na pamäti, že obmedzenia pri formulovaní cieľov nie sú kategorické a môžu byť preplnené alebo nedostatočne naplnené.
Variabilné úlohy: x 1, x 2, x 3, x 4 - respektíve počet vybudovaných stavieb: tenisové kurty, bazény, atletické ihriská a telocvične.
Všetky obmedzenia budú cielené, neexistujú žiadne systémové obmedzenia.
Prvým cieľom je splniť pridelené množstvo:
120x 1 + 600x 2 + 480x 3 + 1 200 x 4 + d 1 - - d 1 + = 5 400.
Minimalizujeme "prekročenie": min Z = P 1 d 1 +.
Druhým cieľom je aspoň 14 000 návštev za týždeň:
500 x 1 + 1 000 x 2 + 2 000 x 3 + 1 500 x 4 + d 2 - - d 2 + = 14 000
Minimalizujeme „nedostatočnú dochádzku“. Ak vezmeme do úvahy prvý cieľ, máme:
min Z = P1d1 + + P2d2-.
Realizácia tretieho cieľa si bude vyžadovať splnenie 4 obmedzení pre každý typ štruktúry:
x1 + d3 - - d3 + = 8;
x2 + d4 - - d4 + = 3;
x3 + d5 - - d5 + = 3;
x 4 + d6 - - d6 + = 2.
Minimalizujeme „nedostatočný výkon“. Toto je tretí najdôležitejší cieľ, preto v účelovej funkcii budú mať všetky 4 členy koeficient P 3, ale s rôzne hmotnosti:
min Z = P 1 d 1 + + P 2 d 2 - + 0,5 P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5 P 3 d 6 -.
Štvrtý gól: 0,8 x 1 + 5 x 2 + 3,2 x 3 + 1,6 x 4 + d 7 - - d 7 + = 20.
Objektívna funkcia so zreteľom na všetky ciele:
min Z = P 1 d 1 + + P 2 d 2 - + 0,5 P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5 P 3 d 6 - + P 4 d 7 +.
Takže model problému bude mať formu:
Nájdite min Z = P 1 d 1 + + P 2 d 2 - + 0,5 P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5 P 3 d 6 - + P 4 d 7 +
za predpokladu, že
120x 1 + 600x 2 + 480x 3 + 1200x 4 + d 1 - - d 1 + = 5 400,
500x 1 + 1 000 x 2 + 2 000 x 3 + 1 500 x 4 + d 2 - - d 2 + = 14 000,
x 1 + d 3 - - d 3 + = 8,
x 2 + d 4 - - d 4 + = 3,
x 3 + d 5 - - d 5 + = 3,
x 4 + d6 - - d6 + = 2,
0,8 x 1 + 2 x 2 + 3,2 x 3 + 1,6 x 4 + d 7 - - d 7 + = 20.
xj30 (j=); dj-, dj + 30 (i=).
Ak je tento problém vyriešený obvyklou simplexnou metódou, potom by sa váhám P i mali priradiť konkrétne hodnoty, ale berte do úvahy, že P 1 >> P 2 >>… >> P 7. Vyvinutý špeciálne programy riešiť takéto problémy. Implementáciou jedného z nich (program QM for Window) dostaneme nasledovné optimálne riešenie (tabuľka 5.5):
Tabuľka 5.5 - Riešenie úlohy z príkladu 5.2.
(Cieľové programovanie)
x 1 = 8, x 2 = 3, x 3 = 3, x 4 = 1, d2 + = 500, d6 - = 1, d7 + = 3,6. (d 7 + = –653 994 je kódované číslo 3.6 - je uvedené v riadku Priorita 4). Uvedené nesplnenie (Nedosiahnutie) v riadku Priorita 3 rovné 1,5 zohľadňuje váhový faktor v cieľovej funkcii at).
Z vyčlenených prostriedkov je teda možné postaviť 8 tenisových kurtov, 3 bazény, 3 miništadióny a jednu telocvičňu. Ako vidíte, štvrtý cieľ je nesplnený o 1 (d = 1), t.j. namiesto dvoch plánovaných sa postaví jedna telocvičňa. Druhý cieľ je preplnený (d 2 + = 500), t.j. namiesto 14 000 návštev je možných 14 500. Cieľ 4 bol tiež prekročený (d 7 + = 3,6), t.j. namiesto vyčlenených 20 hektárov pre tieto športoviská bude potrebných 23,6 hektárov.
Kapitola 6. Techniky plánovania a riadenia siete
Metódy plánovania siete umožňujú analyzovať súbor prác, ktorý zahŕňa veľké číslo vzájomne súvisiacich operácií. Môžete určiť pravdepodobnú dobu trvania všetkých prác, ich cenu, možnú veľkosť časovej úspory resp Peniaze, ako aj to, aké operácie nemožno odložiť bez toho, aby sa oneskorila lehota pre projekt ako celok. Dôležitý je aj problém poskytovania zdrojov. Metódy sieťová analýza možno použiť na skladanie kalendárny plán vykonávanie operácií uspokojujúce existujúce obmedzenia poskytnúť zdroje.
Analýza každého projektu sa vykonáva v troch fázach:
1. Rozdelenie projektu do série jednotlivé práce(alebo operácie), ktoré sú potom zložené z logického diagramu.
2. odhad trvania každej operácie; zostavenie kalendárneho plánu realizácie projektu a pridelenie prác, ktoré určujú dokončenie projektu ako celku.
3. Hodnotenie požiadaviek na zdroje každej operácie; prepracovanie plánu operácií s prihliadnutím na zabezpečenie zdrojov, príp
prerozdelenie hotovosti alebo iných zdrojov, ktoré plán zlepšia.
Po zostavení zoznamu možno logický tok operácií znázorniť pomocou grafu. existuje Rôzne druhy grafy, no najpoužívanejšie sú takzvané vrcholové a šípkové grafy.
Federálna agentúra pre vzdelávanie
Štát vzdelávacia inštitúcia vyššie odborné vzdelanie
Štátna technická univerzita v Perme
Pobočka Lysva
Katedra EN
Práca na kurze
v odbore "Systémová analýza a operačný výskum"
na tému: "Simplexná metóda formou prezentácie"
Vyplnil študent skupiny VIVT-06-1:
Startseva N.S.
Skontrolované učiteľom:
Mukhametyanov I.T.
Lysva 2010
Úvod. 3
Matematické programovanie. 5
Grafická metóda. 6
Tabulárny simplex je metóda. 6
Metóda umelý základ. 7
Modifikovaná simplexná metóda. 7
Duálny simplex je metóda. 7
Všeobecný pohľad na problém lineárneho programovania. deväť
Riešenie úlohy lineárneho programovania simplexnou metódou. jedenásť
Výpočtové postupy simplexovej metódy. jedenásť
Veta 1: 13
Veta 2: 14
Veta 3: 15
Veta 4: 15
Veta 5: 15
Prechod na nový základný plán. 15
Dvojitá úloha. 17
Veta 1 (prvá veta o dualite) 18
Veta 2 (druhá veta o dualite) 18
Záver. dvadsať
Optimálne riešenie problému lineárneho programovania patrí medzi podporné riešenia. Myšlienka simplexovej metódy spočíva v tom, že pre určité pravidlo sa podporné riešenia vytriedia pred nájdením optimálneho medzi nimi, vytriedime podporné riešenia, v podstate iterujeme cez rôzne základné premenné, to znamená pri ďalšom kroku sa zo základných prenesie nejaká premenná a namiesto nej nejaká premenná z počtu voľných do počtu základných.
7x 1 + 5x 2 → max
x 3 = 19-2x 1-3x2 (0; 0; 19; 13; 15; 18)
x 4 = 13-2x 1 -x 2 počiatočná základná línia
x 6 = 18-3x 1 F (x 1, x 2) = 7 * 0 + 5 * 0 = 0
x i ≥ 0, (i = 1,… n)
Na intuitívnej úrovni je jasné, že nárast x 1 bude prirodzený, pretože koeficient s ním je väčší ako s x 2. Ak ponecháme x 2 = 0, môžeme zvyšovať, pokiaľ x 3, x 4, x 5, x 6 sú nezáporné.
x 1 = min (19/2; 13/2; ∞; 18/3) = 6
To znamená, že keď x 1 = 6, x 6 = 0, teda x 1-ide do počtu základných a x 6-do počtu voľných.
x 3 = 19-2 (6-1 / 3 x 6) -3 x 2 = 19-12 + 2/3 x 6 -3 x 2 = 7 + 2/3 x 6 -3 x 2
x 4 = 13-2 (6-1 / 3 x 6) - x 2 = 1 + 2/3 x 6 - x 2
F (x 2; x 6) = 42-7 / 3 x 6 + 5 x 2
Pre daný referenčný plán (6; 0; 7; 1; 15; 0) sa x 2 prenesie z voľnej na základné premenné:
x 2 = min (∞; 7/3; 1/11; 15/3) = 1
Express x 2 v zmysle x 4
x 2 = 1 + 2/3 x 6 - x 4
Neznáme premenné a účelovú funkciu vyjadrujeme pomocou voľných premenných:
x 3 = 7 + 2/3 x 6 -3 (1 + 2 / 3x 6 -x 4) = 7 + 2/3 x 6 -3-2x 6 + 3x 4 = 4-4 / 3x 6 +3 x 4
x 5 = 12-2x 6 + 3x 4 -
F = 42-7 / 3 x 6 +5 (1 + 2 / 3x 2 - x 4) = 47-7 / 3x 6 + 10 / 3x 6 -5x 4 = 47 + x 6 -5x 4
x 6 je kladné, preto ho môžete zvýšiť
x 6 = min (18; ∞; 3; 6) = 1
x 4 = 4 / 3-4 / 9 x 6 - 1 / 3 x 3
F = 47 + x 6 -5 (4 / 3-4 / 9-1 / 3x 3)
V účelovej funkcii sú všetky koeficienty pre premenné záporné, hodnotu funkcie nemožno zvýšiť, podobne transformujeme ostatné premenné, nájdeme referenčný plán, z ktorého určíme x 1, x 2.
1. Priesečník uzavretých množín, súbor netriviálnych obmedzení.
2. Množina riešení sústavy nestriktných lineárnych nerovníc a rovníc je uzavretá.
αX = (αx 1, x 2, ..., αx n)
X + Y = (x 1 + y 1, x 2 + y 2,... x n + y n)
Lineárne súradnice X 1, X 2,… X n sa nazývajú bod P = λ 1 x 1 + λ 2 x 2 +… + λ k x k
Množina P = (λ 1 x 1 + λ 2 x 2 +… + λ kxk) 0≤ hi ≤1 pre i = 1,… kn åR i = 1, 1≤ i ≤k je konvexná lineárna kombinácia bodov x 1, x 2,… Xn. Ak k = 2, potom sa táto množina nazýva segment. X 1, X 2 - konce segmentu. Rohový bod uzavretej množiny je bod, ktorý nie je netriviálnou lineárnou kombináciou bodov množiny (rohový bod).
Netriviálnosť znamená, že aspoň jeden z λ sa líši od 0 alebo 1.
 |
Akékoľvek referenčné riešenie problému lineárneho programovania je rohovým bodom oblasti realizovateľných riešení.
Ak má problém lineárneho programovania jedinečné riešenie, potom leží medzi rohovými bodmi ODR. A ak existuje viac riešení, potom medzi riešeniami existuje niekoľko rohových riešení, takže množina všetkých riešení je ich konvexnou lineárnou kombináciou.
Simplexová metóda spočíva v tom, že sa najprv nájde nejaké základné riešenie problému (počiatočný základný plán), a potom sa cielene prechádza od jedného základného plánu k druhému a hľadá sa optimálny plán. Ak je ich niekoľko, nájdu sa všetky rohové riešenia a množina riešení je reprezentovaná ako ich lineárna kombinácia.
Prechod na nový základný plán
F1 = F (x 1); F 2 = F (x 2) F 2 -F 1 = -υ k Δ k = F 2 možno dokázať, kde υ k je minimum uvažované vyššie, ktoré sa určí zavedením k-tej premennej do základu a Δ k = ес jxj ( 1) -С k, kde n ≤ j ≤ 1, X 1 = (x 1 (1); x 2 (1); ... xn (1)) je odhad k-tej premennej, preto , ak je vyriešený maximálny problém, potom hodnota ΔF 2 musí byť kladná, Δk - záporná. Pri riešení úloh za minimum je ΔF 2 záporné, Δ k kladné. Tieto hodnoty sú vypočítané a ak medzi ΔF 2 nie sú všetky hodnoty kladné, potom pri riešení problémov s minimom je opak pravdou. Ak pri riešení pre maximum medzi ΔF 2 existuje niekoľko kladných, potom do základu zavedieme vektor, pri ktorom táto hodnota dosiahne maximum, a ak sa problém vyrieši minimálne a medzi ΔF 2 je niekoľko záporných jedničky, potom vektor s najmenšia hodnotaΔF 2, teda s najväčšou absolútnou hodnotou. Pri splnení týchto podmienok je zaručená najväčšia možná zmena hodnoty funkcie.
Riešenie problému bude jedinečné, ak pre všetky vektory xk, ktoré nie sú zahrnuté v základe, odhadne Δ k ≠ 0, ak aspoň jeden z takýchto Δ k = 0, riešenie nie je jedinečné; aby sme našli iné riešenie, prejdite na iný základný plán vrátane základu xk, kde Δ k = 0. Výpočet všetkých takýchto podporné riešenia zostavte ich v lineárnej kombinácii, ktorá bude riešením problému.
Ak pre niektoré Δ k, ktoré sú v rozpore s podmienkou optimality, sú koeficienty pre premennú x k ≤ 0, potom systém obmedzení nie je obmedzený, to znamená, že neexistuje optimálny návrh.
Dvojitá úloha
Duálny problém (DZ) je pomocný problém lineárneho programovania formulovaný pomocou určitých pravidiel priamo z podmienok priameho problému. Záujem o definovanie optimálne riešenie priamej úlohy riešením duálnej úlohy k nej je spôsobené tým, že výpočty pri riešení DZ môžu byť menej komplikované ako pri priamej úlohe (DZ). Zložitosť výpočtov pri riešení LPP závisí vo väčšej miere od počtu obmedzení, a nie od počtu premenných. Pre prechod na DZ je potrebné, aby DZ bola zaznamenaná v norme kanonická forma... Keď je PP prezentovaný v štandardnej forme, premenné x j zahŕňajú aj nadbytočné a reziduálne premenné.
Dvojitý problém má:
1. m premenných zodpovedajúcich počtu obmedzení priameho problému;
2. n obmedzení zodpovedajúcich počtu premenných priameho problému.
Duálny problém sa získa symetrickou štruktúrnou transformáciou podmienok priameho problému podľa nasledujúcich pravidiel:
· Každé obmedzenie b i PZ zodpovedá premennej y i DZ;
· Každá premenná x j PP zodpovedá obmedzeniu C j DZ;
· Koeficienty pri x j v obmedzeniach DZ sa stanú koeficientmi ľavej strany zodpovedajúceho obmedzenia DZ;
· Koeficienty C j pre x j v cieľovej funkcii DZ sa stanú konštantnými na pravej strane obmedzenia DZ;
· Konštantné obmedzenia b i PZ sa stávajú koeficientmi objektívnej funkcie DZ.
Zvážte nasledujúce dve úlohy:
F = C 1 x 1 + C 2 x 2 + ... + C n x n → max
|
a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m
x j ≥ 0 j = 1,…, n
Z = b 1 x 1 + b 2 x 2 + ... + b n x n → min
|
a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤ C 2
. . . . . . . . . . . . . . . . . . . . . . .
a 1 n y n + a 2 m y n + ... + a nm y n ≤ C n
V tomto ročníková práca boli položené základy matematické metódy riešenie problémov lineárneho programovania. Preto viac pozornosti bol zaradený do nasledujúcich sekcií:
1. Základy matematických metód a ich aplikácia;
2. Riešenie úloh simplexnou metódou.
1.5.1. Výpočtový obvod založený na transformácii inverzné matice. Pri analýze výpočtového postupu simplexovej metódy z hľadiska hodnotenia zložitosti je ľahké vidieť, že v tomto smere je najkritickejšia fáza prepočtu hodnôt. A a b pri prechode z jedného základného plánu na druhý (položka 3 algoritmu). Avšak v prípade, keď počet obmedzení úloh m jednoznačne menej premenných n, môžete dosiahnuť značné "úspory" vykonaním v ďalšej iterácii q Jordan-Gaussova transformácia nie cez matricu A(β ( q)) a nad maticou Δ -1 (β ( q)). V tomto prípade sa tiež berie do úvahy, že ak je to potrebné, použitím vzorca (1.26) je vždy možné získať A(β ( q)) vzhľadom na Δ -1 (β ( q)). Navyše, aby sme mohli vykonávať akcie simplexného postupu opísaného vyššie, maticu sme v skutočnosti nepotrebovali A(β ( q)) úplne. V skutočnosti použila iba ratingovú čiaru. a 0 (β ( q)) a vedúci stĺpec a l(β ( q)). Tieto úvahy sú základom výpočtovej schémy simplexovej metódy založenej na transformácii inverzných matíc, ktorá je tiež tzv. modifikovaná simplexná metóda... najprv tento algoritmus bol navrhnutý v roku 1951 v dielach L. V. Kantoroviča.
Výpočtový obvod modifikovaná simplexová metóda zodpovedá sústave tabuliek T 1 a T 2 (q). tabuľky T 1 (ryža. 1.7) je spoločný pre všetky iterácie a používa sa na získanie radu odhadov pre aktuálny základný plán a 0 (β ( q)). Ak označíme δ i(β ( q)) (iÎ 0: m) riadky matice Δ -1 (β ( q)), potom najmä z (1,26) vyplýva, že
Ako je vidieť z ryža. 1.7, T 1 pozostáva z troch blokov:
Ø Ø stred obsahuje maticu А;
Ø Ø v ľavom bloku tabuľky sa pri každej iterácii pridá nula riadkov maticeΔ -1 (β ( q))pre súčasný základ;
Ø Ø spodný blok umiestnený pod matricou A, pri každej iterácii je doplnený o rad odhadov aktuálneho plánu vypočítaný podľa vzorca (1.42).
Simplexný stôl T 2 (q) zobrazené v ryža. 1.8, zodpovedá prípustnému základu KZLP β ( q) získané dňa q iteráciu. Stĺpec N(β ( q)) obsahuje čísla základných stĺpcov (v poradí výskytu v základe); stĺpec b(β ( q)) sú komponenty vektora obmedzenia vzhľadom na aktuálnu bázu β ( q); Δ -1 (β ( q)) je inverzná matica vzhľadom na maticu rozšírených stĺpcov aktuálnej bázy β ( q); počítať a l obsahuje rozšírený vektor podmienok zadaných do základu v aktuálnej iterácii a nasledujúci graf obsahuje súradnice a l(β ( q)) rovnakého stĺpca v aktuálnom základe β ( q) .
Analogicky s časťou 1.4.1 popíšeme formálnu schému algoritmu modifikovanej simplexovej metódy.
0-stupňový. Nájdenie platného základného plánu.
1. Na hľadanie prípustného základu je možné použiť metódu minimalizácie zvyškov, o ktorej sa uvažuje v časti 1.4.5. V tomto prípade sa na vyriešenie pomocnej úlohy používa postup modifikovanej simplexovej metódy. V dôsledku nulovej fázy získame platný základný plán X(β (1)) a zodpovedajúca matica Δ -1 (β (1)) a vektor b(p (1)).
2. Vyplníme strednú časť tabuľky T 1 obsahujúci matricu A.
3. Obsah matice Δ -1 (β (1)) a vektora b(β (1)), získaný vo fáze hľadania prípustného základného plánu, sa prenesie do tabuľky T 2 (1) .
4. Nastavíme číslo aktuálnej iterácie q rovná 1 a prejdite do I-fázy.
1. fáza Štandardná iterácia algoritmu- vykonaná pre ďalší základný plán X(β ( q)).
1 °. Kontrola optimálnosti aktuálneho základného plánu... Obsah nultého riadku tabuľky T 2 (q) - δ 0 (β ( q)) sa prepíše do príslušného stĺpca tabuľky T 1. Pomocou vzorca (1.42) vypočítame a vyplníme riadok a 0 (β ( q)). Zobrazenie riadku hodnotenia a 0 (β ( q)). Sú dve možnosti:
1. a 0 (β ( q)) ≥0 -plán zodpovedajúci aktuálnemu základu problému, optimálne. Proces výpočtu hotový. Podľa vzorcov (1.33) a (1.32) sa napíše optimálny plán úlohy NS* = X(β ( q)) a optimálnu hodnotu účelovej funkcie f(NS*) = f(X(β ( q))).
1 ". V riadku hodnotenia a 0 (β ( q)) je tam aspoň jeden prvok a 0, j(β ( q))<0, т. е. имеющий отрицательную оценку. Следовательно, план X(β ( q)) - suboptimálne... Vybraté číslo l zodpovedajúce prvku, ktorý má minimálne (maximálne v absolútnej hodnote) negatívne hodnotenie:
l stĺpec matice A sa stáva vedenie a musí sa zadať do ďalšieho základu. Prejdeme k bodu 2° algoritmu.
2 °. Definovanie stĺpca na odvodenie zo základu... Prepísanie vedúceho stĺpca a l od stola T 1 k aktuálnej tabuľke T 2 (q). Podľa vzorca a l(β ( q)) = Δ -1 (β ( q))a l vyplňte príslušný stĺpec v tabuľke T 2 (q). Sú dve možnosti:
2 ". Pre každého iÎ 1: m a i, l(β ( q)) ≤0. Dospelo sa k záveru, že neobmedzená objektívna funkcia a výpočtový proces končí.
2.". Existuje aspoň jeden index iÎ 1: m pre ktoré a i, l(β ( q))> 0. Podľa pravidla (1.27) je miesto r a číslo N r(β ( q)) pre stĺpec odvodený od základu. Prejdeme k bodu 3° algoritmu.
3 °. Prepočet vzhľadom na nový základ prvkov stĺpca b a matice A-1. Prechod na nový základ β ( q+1), ktorý sa získa zavedením do základu β ( q) stĺpec a l a výstupom z neho stĺpec a r, sa uskutočňuje vzorcami podobnými vzorcom (1.28) - (1.31). Vyzerajú takto:
Nastavíme číslo aktuálnej iterácie q: =q+ l a prejdite na prvý krok algoritmu.
Na záver zdôrazňujeme, že vzhľadom na vyššie uvedené výhody áno modifikovaná simplexná metóda skutočne aplikovaný v softvér navrhnutý na riešenie problémov kanonického lineárneho programovania.
1.5.2. Príklad LPP riešenia modifikovaná simplexná metóda. Uveďme riešenie predtým uvažovanej úlohy (1.34) - (1.35), založené na použití postupu modifikovanej simplexovej metódy. Analogicky s oddielom 1.4.3 sa začína výberom jasného počiatočného základu tvoreného stĺpcami (5,2,3). Pre to platí Δ -1 (β ( q)) a b(β ( q)), takže vyplňte počiatočné tabuľky T 1 a T 2 (1) nie je ťažké.
V prvej iterácii prepíšeme nulový reťazec
od T 2 (1) palcov T 1 a vynásobením maticou A, dostaneme líniu odhadov
Pretože a 0 (β (1)) obsahuje záporné prvky, potom dospejeme k záveru, že plán zodpovedajúci základu β (1) nie je optimálny a po výbere najmenej záporného odhadu (-88) dostaneme číslo zadaného stĺpca do základu, l= 4.
Prepisovanie stĺpca
od stola T 1 palec T 2 (1) a prepočítajte jeho súradnice vzhľadom na aktuálny základ, t.j. vynásobte maticu Δ -1 (β ( q)), ktorý sa nachádza v tabuľke T 2 (1) vľavo, na a 4 .
Po vyplnení tabuľky T 2 (1) údaje o stĺpci zapísané do nového základu, môžete pristúpiť k určeniu čísla zobrazeného stĺpca. Tento postup sa vykonáva úplne analogicky s konvenčnou simplexovou metódou. Vzhľadom na vzťah prvkov b i(p (1)) a a i, l(β (1)) pre ( iÎ1: m | a i, l(β (1))> 0) a určením ich minima zistíme, že r= 2. Preto je stĺpec očíslovaný N 2 (β ( q)) = 2 treba odpočítať od základu. Takto získame ďalší prípustný základ problému s N(p (2)) = (5, 4, 3). Element a 2,3 (β (1)) je prvý (zakrúžkovaný). Použitím vzorcov (1.43) - (1.46) prejdeme do simplexnej tabuľky zodpovedajúcej druhej iterácii T 2 (2) a nastavte index aktuálnej iterácie q = 2.
Opakovaním rovnakých akcií (môžete ich jednoducho nasledovať podľa tu uvedených tabuliek T 2 (2) a T 2 (3), pri tretej iterácii dostaneme optimálny plán problému a optimálnu hodnotu účelovej funkcie, ktoré sú extrahované z druhého stĺpca tabuľky. T 2 (3). Je ľahké vidieť, že v procese riešenia sme „kráčali“ po rovnakej postupnosti prípustných základných plánov, s ktorou sme sa stretli v časti 1.4.3.
Odoslanie dobrej práce do databázy znalostí je jednoduché. Použite nižšie uvedený formulár
Študenti, postgraduálni študenti, mladí vedci, ktorí pri štúdiu a práci využívajú vedomostnú základňu, vám budú veľmi vďační.
Podobné dokumenty
Geometrickým spôsobom riešenia štandardné úlohy lineárne programovanie s dvoma premennými. Univerzálna metóda riešenia kanonická úloha... Základná myšlienka simplexovej metódy, implementácia príkladom. Tabuľková implementácia jednoduchej simplexovej metódy.
abstrakt, pridaný 15.06.2010
Typy problémov lineárneho programovania a formulácia problémov. Podstata optimalizácie ako odvetvia matematiky a charakteristika hlavných metód riešenia problémov. Koncept simplexnej metódy, skutočný aplikované úlohy... Algoritmus a etapy riešenia dopravného problému.
ročníková práca, pridaná 17.02.2010
Riešenie úlohy lineárneho programovania grafickou a simplexnou metódou. Riešenie problému, ktorý je duálny oproti pôvodnému. Stanovenie optimálneho plánu pripojenia spotrebiteľov k dodávateľom homogénneho nákladu za predpokladu, že sa minimalizuje celkový počet najazdených kilometrov.
test, pridané 15.08.2012
Použitie simplexnej metódy na riešenie úloh lineárneho programovania na výpočet denného objemu produkcie. Kontrola optimálneho plánu. Prepočet simplexný stôl Jordan-Gaussovou metódou. Zostavenie modelu dopravného problému.
test, pridané 18.02.2014
Ekonomický a matematický model pre dosiahnutie maximálneho zisku, jeho riešenie graficky... Algoritmus na riešenie úlohy lineárneho programovania simplexnou metódou. Navrhovanie duálne úlohy a jej grafické riešenie... Riešenie platobnej matice.
test, pridaný 05.11.2014
Základy matematického modelovania ekonomické procesy. všeobecné charakteristiky grafické a simplexné metódy riešenia priamych a duálnych úloh lineárneho programovania. Vlastnosti formulácie a metodiky riešenia dopravného problému.
ročníková práca, pridaná 12.11.2010
Zostavenie matematického modelu problému. Výpočet optimálneho plánu prepravy s minimálnymi nákladmi pomocou metódy potenciálu. Najlepšia možnosťšpeciálne mobilné vybavenie pre technická podpora produkčný manažment.
test, pridané 01.06.2014
Hodnota avatarov v psychológii
Hodnota avatarov v psychológii
Ako zdôrazniť písmeno v MS Word
Čo to znamená, ak je avatar osoby
Ako si vytvoriť svoj vlastný Twitter moment