Táto metóda je metódou účelového vymenovania referenčných riešení problému lineárne programovanie. Umožňuje v konečnom počte krokov buď nájsť optimálne riešenie, alebo zistiť, že žiadne optimálne riešenie neexistuje.
Hlavný obsah simplexovej metódy je nasledujúci:- Uveďte metódu na nájdenie optimálneho referenčného riešenia
- Uveďte spôsob prechodu z jedného referenčného riešenia do druhého, pri ktorom sa hodnota účelovej funkcie bude približovať optimálnej, t.j. uveďte spôsob, ako zlepšiť referenčné riešenie
- Nastavte kritériá, ktoré vám umožnia okamžite zastaviť hľadanie riešení podpory pri optimálnom riešení alebo vyvodiť záver o absencii optimálneho riešenia.
Algoritmus simplexovej metódy na riešenie úloh lineárneho programovania
Ak chcete vyriešiť problém pomocou simplexnej metódy, musíte urobiť nasledovné:- Prineste úlohu kanonickej podobe
- 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í)
- Vypočítajte odhady rozkladov vektorov na základe referenčného roztoku a vyplňte tabuľku simplexnej metódy
- Ak je splnené kritérium jedinečnosti optimálneho riešenia, riešenie problému končí
- Ak je splnená podmienka existencie množiny optimálnych riešení, potom sa všetky optimálne riešenia nájdu jednoduchým enumeráciou
Príklad riešenia úlohy simplexnou metódou
Príklad 26.1Vyriešte problém pomocou simplexnej metódy:
Riešenie:
Prinášame problém do kanonickej podoby.
Aby sme to dosiahli, zavedieme ďalšiu premennú x 6 s koeficientom +1 na ľavú stranu prvého obmedzenia nerovnosti. Premenná x 6 je zahrnutá do účelovej funkcie s koeficientom nula (t. j. nie je zahrnutá).
Dostaneme:
Nájdeme počiatočné riešenie podpory. Aby sme to dosiahli, prirovnáme voľné (nevyriešené) premenné k nule x1 = x2 = x3 = 0.
Dostaneme referenčný roztok X1 = (0,0,0,24,30,6) s jednotkovým základom B1 = (A4, A5, A6).
Počítame odhady rozkladov vektorov podmienky na základe referenčného roztoku podľa vzorca:
A k = Cb X k - c k
- C b = (c 1, c 2, ..., c m) - vektor koeficientov účelovej funkcie pre základné premenné
- X k = (x 1k, x 2k, ..., x mk) - vektor expanzie príslušného vektora A k podľa bázy referenčného riešenia
- C k je koeficient účelovej funkcie pre premennú x k.
Odhady vektorov zahrnutých v základe sú vždy rovné nule. Je zapísané referenčné riešenie, expanzné koeficienty a odhady expanzií stavových vektorov na základe referenčného riešenia simplexný stôl:
V hornej časti tabuľky sú na uľahčenie výpočtu odhadov napísané koeficienty účelovej funkcie. V prvom stĺpci "B" sú zapísané vektory zahrnuté v základe referenčného roztoku. Poradie, v ktorom sú tieto vektory zapísané, zodpovedá počtu povolených neznámych v obmedzujúcich rovniciach. V druhom stĺpci tabuľky "C b" sú koeficienty účelovej funkcie pre základné premenné zapísané v rovnakom poradí. Pri správnom usporiadaní koeficientov účelovej funkcie v stĺpci „C b“ sa odhady jednotkových vektorov zahrnutých do bázy vždy rovnajú nule.
V poslednom riadku tabuľky s odhadmi Δ k v stĺpci „A 0“ sú zapísané hodnoty účelovej funkcie na referenčnom riešení Z(X 1).
Počiatočné riešenie podpory nie je optimálne, keďže v maximálnom probléme sú odhady Δ 1 = -2, Δ 3 = -9 pre vektory A 1 a A 3 záporné.
Podľa vety o zlepšení riešenia podpory, ak má v maximálnom probléme aspoň jeden vektor záporný odhad, potom môžete nájsť nové riešenie podpory, na ktorom bude hodnota účelovej funkcie väčšia.
Určme, ktorý z týchto dvoch vektorov povedie k väčšiemu prírastku cieľovej funkcie.
Prírastok účelovej funkcie zistíme podľa vzorca: .
Hodnoty parametra θ 01 pre prvý a tretí stĺpec vypočítame pomocou vzorca:
Získame θ 01 = 6 pre l = 1, θ 03 = 3 pre l = 1 (tabuľka 26.1).
Prírastok účelovej funkcie nájdeme, keď do bázy vložíme prvý vektor ΔZ 1 = - 6*(- 2) = 12 a tretí vektor ΔZ 3 = - 3*(- 9) = 27.
Pre rýchlejší prístup k optimálnemu riešeniu je preto potrebné namiesto prvého vektora bázy A6 zaviesť do bázy referenčného riešenia vektor A3, keďže minimum parametra θ 03 je dosiahnuté v prvom riadku ( l = 1).
Jordanovu transformáciu vykonáme s prvkom X13 = 2, získame druhé referenčné riešenie X2 = (0,0,3,21,42,0) so základom B2 = (A3, A4, A5). (Tabuľka 26.2)
Toto riešenie nie je optimálne, pretože vektor A2 má negatívny odhad Δ2 = - 6. Na zlepšenie riešenia je potrebné zaviesť vektor A2 do základu referenčného riešenia.
Určíme číslo vektora odvodené od základu. Na tento účel vypočítame parameter θ 02 pre druhý stĺpec, ktorý sa rovná 7 pre l = 2. Následne zo základu odvodíme druhý základný vektor A4. Jordanovu transformáciu vykonáme prvkom x 22 = 3, získame tretie referenčné riešenie X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (tabuľka 26.3).
Toto riešenie je jediné optimálne, keďže pre všetky vektory, ktoré nie sú zahrnuté v základe, sú odhady kladné
A 1 = 7/2, A 4 = 2, A 6 = 7/2.
odpoveď: max Z(X) = 201 pri X = (0,7, 10, 0,63).
Metóda lineárneho programovania v ekonomickej analýze
Metóda lineárneho programovania umožňuje zdôvodniť najoptimálnejšie ekonomické riešenie v podmienkach prísnych obmedzení súvisiacich so zdrojmi používanými vo výrobe (fixný majetok, materiál, pracovné zdroje). Využitie tejto metódy v ekonomickej analýze umožňuje riešiť problémy súvisiace najmä s plánovaním činnosti organizácie. Táto metóda pomáha určiť optimálne množstvá výstupov produktov, ako aj pokyny pre najefektívnejšie využitie výrobných zdrojov, ktoré má organizácia k dispozícii.
Pomocou tejto metódy sa riešia takzvané extrémne problémy, ktoré spočívajú v hľadaní extrémnych hodnôt, teda maxima a minima funkcií. premenných.
Toto obdobie je založené na riešení systému lineárne rovnice v prípadoch, keď sú analyzované ekonomické javy spojené lineárne, striktne funkčná závislosť. Metóda lineárneho programovania sa používa na analýzu premenných v prítomnosti určitých obmedzujúcich faktorov.
Je veľmi bežné riešiť takzvaný transportný problém metódou lineárneho programovania. Obsahom tejto úlohy je minimalizácia nákladov vynaložených v súvislosti s prevádzkou vozidiel pri existujúcich obmedzeniach počtu vozidiel, ich nosnosti, dĺžky ich prevádzky, ak je potrebné obslúžiť maximálny počet zákazníkov.
Okrem toho je táto metóda široko používaná pri riešení problému plánovania. Táto úloha spočíva v takom rozložení prevádzkového času personálu danej organizácie, ktoré by bolo najprijateľnejšie pre členov tohto personálu aj pre klientov organizácie.
Touto úlohou je maximalizovať počet obsluhovaných klientov za podmienok obmedzenia počtu disponibilných zamestnancov, ako aj fondu pracovného času.
Metóda lineárneho programovania je teda celkom bežná v analýze umiestnenia a použitia. rôzne druhy zdrojov, ako aj v procese plánovania a prognózovania činnosti organizácií.
Napriek tomu sa dá matematické programovanie aplikovať aj na tie ekonomické javy, vzťah medzi ktorými nie je lineárny. Na tento účel možno použiť metódy nelineárneho, dynamického a konvexného programovania.
Nelineárne programovanie sa spolieha na nelineárnu povahu cieľovej funkcie alebo obmedzení, alebo oboch. Formy objektívnej funkcie a obmedzenia nerovnosti v týchto podmienkach môžu byť rôzne.
Nelineárne programovanie sa využíva v ekonomickej analýze najmä pri zisťovaní vzťahu medzi ukazovateľmi vyjadrujúcimi efektivitu činnosti organizácie a objemom tejto činnosti, štruktúrou výrobných nákladov, trhovými podmienkami a pod.
Dynamické programovanie je založené na konštrukcii rozhodovacieho stromu. Každá vrstva tohto stromu slúži ako štádium na určenie dôsledkov predchádzajúceho rozhodnutia a na odstránenie neefektívnych možností tohto rozhodnutia. Dynamické programovanie má teda viackrokový, viacstupňový charakter. Tento typ programovania sa používa v ekonomickej analýze na nájdenie optimálnych možností rozvoja organizácie v súčasnosti aj v budúcnosti.
Konvexné programovanie je typ nelineárneho programovania. Tento typ programovania vyjadruje nelineárny charakter vzťahu medzi výsledkami činnosti organizácie a jej nákladmi. Konvexné (aka konkávne) programovanie analyzuje konvexné objektívne funkcie a konvexné obmedzujúce systémy (body uskutočniteľnosti). Konvexné programovanie sa používa pri analýze ekonomických aktivít s cieľom minimalizácie nákladov a konkávne programovanie s cieľom maximalizácie príjmu pri existujúcich obmedzeniach pôsobenia faktorov, ktoré ovplyvňujú analyzované ukazovatele opačným spôsobom. V dôsledku toho s typmi uvažovaného programovania sú konvexné objektívne funkcie minimalizované a konkávne objektívne funkcie sú maximalizované.
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
POZOR
Vymazať všetky bunky?
Zavrieť Vymazať
Pokyny na zadávanie údajov.Čísla sa zadávajú ako celé čísla (príklady: 487, 5, -7623 atď.), desatinné miesta (napr. 67., 102,54 atď.) alebo zlomky. Zlomok je potrebné zadať v tvare a/b, kde a a b (b>0) sú celé čísla alebo desatinné čísla. Príklady 45/5, 6,6/76,4, -7/6,7 atď.
Simplexná metóda
Príklady riešenia ZLP simplexovou metódou
Príklad 1. Vyriešte nasledujúci problém lineárneho programovania:
 |
Pravá strana obmedzení sústavy rovníc má tvar:
Zapíšme si aktuálny referenčný plán:
 |
Tento referenčný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší záporný prvok v module je (-3), preto je vektor zahrnutý do základu X 
pri 
. min(40:6, 28:2)=20/3 zodpovedá riadku 1. Vektor vychádza zo zákl. X 3. Urobme Gaussovu elimináciu pre stĺpec X 2, za predpokladu, že vodiaci prvok zodpovedá riadku 1. Vynulujeme všetky prvky tohto stĺpca okrem vodiaceho prvku. Ak to chcete urobiť, pridajte riadky riadku 2, 3, 4 k riadku 1, vynásobené -1/3, 1/6, 1/2. Ďalej delíme čiaru s vodiacim prvkom vodiacim prvkom.
Tento referenčný plán nie je optimálny, pretože posledný riadok obsahuje záporný prvok (-3), preto základ zahŕňa vektor X 1. Určujeme, ktorý vektor vychádza zo základu. Aby sme to dosiahli, vypočítame 
pri 
. min(44/3:11/3, 62/3:5/3)=4 zodpovedá riadku 2. Vektor vychádza zo zákl. X 4. Urobme Gaussovu elimináciu pre stĺpec X 1, za predpokladu, že vodiaci prvok zodpovedá riadku 2. Vynulujeme všetky prvky tohto stĺpca okrem vodiaceho prvku. Ak to chcete urobiť, pridajte riadky 1, 3, 4 s riadkom 2 vynásobeným 1/11, -5/11, 9/11. Ďalej delíme čiaru s vodiacim prvkom vodiacim prvkom.
Simplexná tabuľka bude mať nasledujúcu formu:
Súčasný referenčný plán je optimálny, keďže v riadkoch 4 pod premennými 
neexistujú žiadne negatívne prvky.
Riešenie možno napísať takto: 
.
Hodnota účelovej funkcie v tomto bode: F(X)=
.
Príklad 2. Nájdite maximum funkcie
Riešenie.
Bázové vektory X 4 , X 3 teda všetky prvky v stĺpcoch X 4 , X 3 pod vodorovnou čiarou by mala byť nula.
Vynulujte všetky prvky stĺpca X 4, s výnimkou vodiaceho prvku. Ak to chcete urobiť, pridajte riadok 3 k riadku 1 vynásobenému 4. Vynulujte všetky prvky stĺpca X 3, okrem vodiaceho prvku. Ak to chcete urobiť, pridajte riadok 3 k riadku 2 vynásobenému 1.
Simplexná tabuľka bude mať tvar:
Tento referenčný plán nie je optimálny, pretože posledný riadok obsahuje záporný prvok (-11), preto základ zahŕňa vektor X 2. Určujeme, ktorý vektor vychádza zo základu. Aby sme to dosiahli, vypočítame 
pri 
. Preto je účelová funkcia zhora neobmedzená. Tie. Problém lineárneho programovania je neriešiteľný.
Príklady riešenia ZLP metódou umelej bázy
Príklad 1. Nájdite maximum funkcie
Riešenie. Keďže počet bázových vektorov musí byť 3, pridáme umelú premennú a k účelovej funkcii pridáme túto premennú vynásobenú −M, kde M je veľmi veľké číslo:
 |
Koeficientová matica sústavy rovníc má tvar:
Bázové vektory preto musia byť všetky prvky v stĺpcoch pod vodorovnou čiarou nulové.
Obnovme všetky prvky stĺpca okrem vodiaceho prvku. Ak to chcete urobiť, pridajte riadok 5 s riadkom 3 vynásobeným -1.
Simplexná tabuľka bude mať tvar:
Tento referenčný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší absolútny záporný prvok je (-5), preto je vektor zahrnutý do základu, určujeme, ktorý vektor vychádza zo základu. Aby sme to dosiahli, vypočítame 
pri 
zodpovedá riadku 3. Zo základu vznikne vektor. Urobme Gaussovu výnimku pre stĺpec, keďže vodiaci prvok zodpovedá riadku 3. Vynulujme všetky prvky tohto stĺpca okrem vodiaceho prvku. Ak to chcete urobiť, pridajte riadky riadok 5 s riadkom 3 vynásobeným 1. Ďalej rozdeľte riadok s vodiacim prvkom vodiacim prvkom.
Simplexná tabuľka bude mať nasledujúcu formu:
Tento referenčný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší absolútny záporný prvok je (-3), preto je vektor zahrnutý do základu Určujeme, ktorý vektor vychádza zo základu. Aby sme to dosiahli, vypočítame 
pri 
zodpovedá riadku 1. Vektor vychádza zo základu X 2. Urobme Gaussovu elimináciu pre stĺpec X 1 za predpokladu, že vodiaci prvok zodpovedá riadku 1. Vynulujme všetky prvky tohto stĺpca okrem vodiaceho prvku. Ak to chcete urobiť, pridajte riadky riadku 2, 3, 4 k riadku 1, vynásobené 3/2, -1/10, 3/2. Ďalej delíme čiaru s vodiacim prvkom vodiacim prvkom.
Simplexná tabuľka bude mať nasledujúcu formu:
Tento referenčný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší záporný prvok v module (-13/2), preto základ zahŕňa vektor X 3. Určujeme, ktorý vektor vychádza zo základu. Aby sme to dosiahli, vypočítame 
pri 
zodpovedá riadku 3. Vektor vychádza zo základu X 5. Urobme Gaussovu elimináciu pre stĺpec X 3, za predpokladu, že vodiaci prvok zodpovedá riadku 3. Vynulujeme všetky prvky tohto stĺpca okrem vodiaceho prvku. Ak to chcete urobiť, pridajte riadky riadku 1, 2, 4 k riadku 3, vynásobené 5/3, 25/9, 65/9. Ďalej delíme čiaru s vodiacim prvkom vodiacim prvkom.
Simplexná tabuľka bude mať nasledujúcu formu:
Súčasný referenčný plán je optimálny, keďže pod premennými v riadkoch 4–5 nie sú žiadne negatívne prvky.
Riešenie pôvodného problému možno napísať takto:
Príklad 2. Nájdite optimálny plán pre problém lineárneho programovania:
Koeficientová matica sústavy rovníc má tvar:
Bázové vektory X 4 , X 5 , X 6 teda všetky prvky v stĺpcoch X 4 , X 5 , X 6, pod vodorovnou čiarou by mala byť nula.
Vynulujte všetky prvky stĺpca X 4, s výnimkou vodiaceho prvku. Ak to chcete urobiť, pridajte riadok 4 k riadku 1 vynásobenému -1. Vynulujte všetky prvky stĺpca X 5, s výnimkou vodiaceho prvku. Ak to chcete urobiť, pridajte riadok 5 s riadkom 2 vynásobeným -1. Vynulujte všetky prvky stĺpca X 6, s výnimkou vodiaceho prvku. Ak to chcete urobiť, pridajte riadok 5 s riadkom 3 vynásobeným -1.
Simplexná tabuľka bude mať tvar:
V riadku 5 prvky zodpovedajúce premenným X 1 , X 2 , X 3 , X 4 , X 5 , X 6 sú nezáporné a číslo sa nachádza na priesečníku daného riadku a stĺpca X 0 je záporné. Potom pôvodný problém nemá referenčný plán. Preto je nerozhodnuteľné.
Simplexná metóda je metóda postupného prechodu z jedného základného riešenia (vrchol mnohostenu riešenia) sústavy obmedzení úlohy lineárneho programovania k inému základnému riešeniu, kým funkcia cieľa nenadobudne optimálnu hodnotu (maximum alebo minimum).
Simplexová metóda je univerzálna metóda, ktorý dokáže vyriešiť akýkoľvek problém lineárneho programovania, pričom grafická metóda je vhodná len pre systém obmedzení s dvoma premennými.
Simplexovú metódu navrhol americký matematik R. Danzig v roku 1947, odvtedy sa touto metódou pre potreby priemyslu často riešia problémy lineárneho programovania s tisíckami premenných a obmedzení.
Predtým, ako prejdeme k algoritmu simplexnej metódy, niekoľko definícií.
Akékoľvek nezáporné riešenie systému obmedzení sa nazýva prijateľné riešenie .
Nech existuje systém m obmedzenia od n premenné ( m n).
Prípustné základné riešenie je roztok obsahujúci m nezáporné Hlavná (základné ) premenné a n - m nejadrový . (nezákladné, príp zadarmo ) premenné. Vedľajšie premenné v základnom riešení sú rovné nule, ale hlavné premenné sú spravidla nenulové, to znamená, že sú to kladné čísla.
akýkoľvek m systémové premenné m lineárne rovnice s n premenné sa nazývajú Hlavná , ak je determinant ich koeficientov odlišný od nuly. Potom zvyšok n - m premenné sa nazývajú nejadrový (alebo zadarmo ).
Algoritmus simplexnej metódy
- Krok 1. Znížte problém lineárneho programovania na kanonickej podobe. Ak to chcete urobiť, presuňte voľné členy na pravú stranu (ak sú medzi týmito voľnými členmi záporné, vynásobte zodpovedajúcu rovnicu alebo nerovnosť číslom -1) a do každého obmedzenia vložte ďalšie premenné (so znamienkom plus, ak je v pôvodná nerovnosť je znamienko „menšie alebo rovné“ a so znamienkom mínus, ak je „väčšie alebo rovné“).
- Krok 2. Ak vo výslednom systéme m rovnice teda m vezmite premenné ako hlavné, vyjadrite hlavné premenné z hľadiska nezákladných a nájdite zodpovedajúce základné riešenie. Ak sa nájdené základné riešenie ukáže ako prípustné, prejdite na prípustné základné riešenie.
- Krok 3. Vyjadrite cieľovú funkciu z hľadiska nebázických premenných prípustného základného riešenia. Ak sa nájde maximum (minimum) lineárneho tvaru a v jeho vyjadrení nie sú žiadne nebázické premenné so zápornými (kladnými) koeficientmi, potom je kritérium optimality splnené a výsledné základné riešenie je optimálne - riešenie je hotové. Ak pri zistení maxima (minima) lineárneho tvaru obsahuje jeho vyjadrenie jednu alebo viac nebázických premenných so zápornými (kladnými) koeficientmi, pristúpime k novému základnému riešeniu.
- Krok 4. Z nebázických premenných zahrnutých v lineárnom tvare so zápornými (kladnými) koeficientmi vyberte tú, ktorá zodpovedá najväčšiemu (v absolútnej hodnote) koeficientu a preveďte ju na základné. Prejdite na krok 2.
Dôležité podmienky
Niektoré špeciálne prípady sú popísané v samostatných článkoch: kedy maximum cieľovej funkcie je nekonečno, Kedy systém nemá riešenie, a kedy optimálne riešenie nie je jediné .
Ďalej sa pozrieme na typický príklad, keď je systém obmedzení spojený a existuje konečné optimum, jedinečné. Variáciou simplexovej metódy je distribučný spôsob riešenia dopravného problému .
Simplexná metóda s simplexnými tabuľkami
Zostrojením simplexných tabuliek je riešenie úlohy lineárneho programovania oveľa jednoduchšie ako pomocou algebraických transformácií, čo je znázornené v nasledujúcom odseku. Simplexové stoly sú veľmi vizuálne. Existuje niekoľko typov pravidiel pre prácu s simplexnými tabuľkami. Pozrieme sa na pravidlo, ktoré sa najčastejšie nazýva pravidlo pre vodiaci stĺpec a vodiaci riadok.
Príručku Akcie so zlomkami by bolo užitočné otvoriť v novom okne: je ich dosť, mierne povedané, v problémoch s použitím simplexovej metódy.
Príklad.
Zavádzame ďalšie nezáporné premenné a redukujeme tento systém nerovností na jeho ekvivalentný systém rovníc
.
Urobilo sa to v súlade s nasledujúcim pravidlom: ak má pôvodné obmedzenie znamienko „menšie alebo rovné“, musí sa pridať dodatočná premenná, a ak „väčšia alebo rovnaká“, musí sa dodatočná premenná odpočítať.
Zavedené dodatočné premenné sa berú ako hlavné (základné). Potom a sú nezákladné (voľné) premenné.
Vyjadrením hlavných (základných) premenných z hľadiska nezákladných (voľných) premenných získame
Cieľovú funkciu môžeme vyjadriť aj prostredníctvom neprimárnych (voľných) premenných:
Z koeficientov (neznámych) premenných zostrojíme prvú simplexnú tabuľku.
| stôl 1 | ||||
| Základné neznáme | Voľní členovia | Voľné neznáme | Pomocné koeficienty | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| F | 0 | -1 | -2 | |
Posledný riadok tabuľky, ktorý obsahuje účelovú funkciu a koeficienty voľných premenných v nej, sa bude nazývať indexový riadok.
Výsledné riešenie nie je optimálne, keďže v indexovej línii sú koeficienty voľných premenných záporné. To znamená, že optimálne riešenie bude také, v ktorom sú koeficienty voľných premenných v indexovej línii väčšie alebo rovné nule.
Ak chcete prejsť na ďalšiu tabuľku, nájdime najväčšie (modulo) z čísel a . Toto číslo je 2. Vedúcim stĺpcom je teda stĺpec, v ktorom
Na určenie vedúceho riadku nájdeme minimálny pomer voľných členov k prvkom vedúceho stĺpca a ak je čitateľ kladné číslo a menovateľ je záporný, pomer sa považuje za rovný nekonečnu.
.
Preto je vedúcou líniou tá, v ktorej je napísaná
Vedúci prvok je teda -2.
Poskladáme druhú simplexnú tabuľku.
Do prvého riadku zadáme nový základný prvok a do stĺpca, v ktorom stál, zadáme novú voľnú premennú
Vyplňte prvý riadok. Aby sme to dosiahli, vydelíme všetky čísla v poprednom riadku tabuľky 1 vodiacim prvkom a zapíšeme ich do zodpovedajúceho stĺpca prvého riadku tabuľky 2, s výnimkou čísla v poprednom stĺpci, kde je inverzná hodnota počiatočného prvok je zapísaný (to znamená jeden delený vedúcim prvkom).
Vyplňte stĺpec pomocných koeficientov. Pre toto číslo v poprednom stĺpci tabuľky 1 zapisujeme okrem vedúceho prvku do stĺpca pomocných koeficientov tabuľky 2 aj opačnými znamienkami.
| tabuľka 2 | ||||
| Základné neznáme | Voľní členovia | Voľné neznáme | Pomocné koeficienty | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| F | 2 | -2 | -1 | 2 |
Každý, kto ešte neotvoril manuál Akcie so zlomkami v novom okne, môže tak urobiť teraz, pretože je čas.
Aby sme získali zvyšné riadky tabuľky 2, vynásobíme čísla už v prvom riadku tejto tabuľky pomocným koeficientom v riadku na vyplnenie a k výsledku pripočítame číslo z tabuľky 1, ktoré je v rovnakom riadok s príslušnou premennou.
Napríklad, aby sme získali voľný termín druhého riadku, vynásobíme číslo 1 číslom 1 a pridáme číslo -4 z tabuľky 1. Dostávame -3. V druhom riadku nájdeme aj koeficient pre: 
. Keďže predchádzajúca tabuľka nemá stĺpec s novou voľnou premennou, koeficient druhého riadku v stĺpci novej voľnej premennej bude 
(to znamená, že pridáme 0 z tabuľky 1, keďže v tabuľke 1 chýba stĺpec c).
Indexový riadok je tiež vyplnený:
Takto získané riešenie opäť nie je optimálne, keďže v indexovej línii sú koeficienty voľných premenných opäť záporné.
Na prechod na ďalšiu simplexnú tabuľku nájdeme najväčšie (modulo) z čísel a teda moduly koeficientov v indexovom riadku. Toto číslo je 2. Vedúcim stĺpcom je teda stĺpec, v ktorom je .
Aby sme našli vodiaci riadok, nájdeme minimálny pomer voľných členov k prvkom vodiaceho riadku. Dostaneme:
.
Preto je vodiaca čiara tá, v ktorej je , a vodiaci prvok je -3/2.
Zostavenie tretej simplexnej tabuľky
Novú základnú premennú zapíšeme do prvého riadku. Do stĺpca, v ktorom zadáme novú voľnú premennú.
Prvá línia:
Pomocné koeficienty:
| Tabuľka 3 | ||||
| Základné neznáme | Voľní členovia | Voľné neznáme | Pomocné koeficienty | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| F | 6 | -4/3 | -1/3 | 2 |
Výsledné riešenie opäť nie je optimálne, keďže koeficienty voľných neznámych v indexovej línii sú opäť záporné.
Ak chcete prejsť na štvrtú simplexnú tabuľku, nájdeme najväčšie z čísel a . Toto je číslo.
Preto je vedúci stĺpec ten, v ktorom je .
Minimálne moduly vzťahov voľných členov k prvkom vedúceho stĺpca:
.
Preto je vodiaca čiara tá, v ktorej je , a vodiaci prvok je 1/3.
Do štvrtej simplexnej tabuľky zapíšeme novú základnú premennú ako prvý riadok. Do stĺpca kde napíšeme novú voľnú premennú.
Prvá línia:
Pomocné koeficienty:
| Tabuľka 4 | ||||
| Základné neznáme | Voľní členovia | Voľné neznáme | Pomocné koeficienty | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| F | 14 | 4 | -3 | 4/3 |
Výpočet zostávajúcich riadkov pomocou druhého riadku ako príkladu:
Výsledné riešenie tiež nie je optimálne, ale je už lepšie ako predchádzajúce, keďže jeden z koeficientov voľných premenných v indexovom riadku je nezáporný.
Aby sme plán zlepšili, prejdime k ďalšej simplexnej tabuľke.
Nájdite najväčšie z čísel 4 a . Toto číslo je 4. Preto je vedúci stĺpec .
Aby sme našli vedúcu čiaru, nájdeme
.
Preto je vedúcou líniou tá, v ktorej . Ale už boli spolu medzi voľnými premennými. Preto, aby sme preniesli ďalšiu premennú z voľnej na základnú, vyberieme iný vedúci stĺpec - ten, v ktorom .
Aby sme našli vedúcu čiaru, nájdeme
.
Preto je kľúčový riadok ten, v ktorom je , a vedúci prvok je 1.
V piatej simplexnej tabuľke zapíšeme novú základnú premennú ako prvý riadok. Do stĺpca kde napíšeme novú voľnú premennú.
Prvá línia:
Pomocné koeficienty:
| Tabuľka 5 | ||||
| Základné neznáme | Voľní členovia | Voľné neznáme | Pomocné koeficienty | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| F | 20 | 1 | 3 | 3 |
Skúsme hneď zistiť, či je riešenie optimálne. Preto pre zostávajúce riadky vypočítame iba voľné členy (na zistenie hodnôt základných premenných, keď sa voľné premenné rovnajú nule) a koeficienty pre voľné premenné v indexovom riadku.
Voľní členovia:
V druhom riadku;
V treťom riadku;
Vo štvrtom riadku.
Indexový riadok:
Pozrime sa na simplexnú tabuľku 5. Vidíme, že sme získali optimálne riešenie, keďže koeficienty pre voľné neznáme v indexovej línii sú nezáporné.
Simplexná metóda s algebraickými transformáciami
Vyriešme rovnaký príklad ako v predchádzajúcom odseku pomocou algebraických transformácií. Treba si uvedomiť, že pri riešení tohto typu simplexovej metódy je lepšie nepísať cieľovú funkciu do formulára , keďže v znameniach sa dá ľahko zmiasť. Ale v tomto prípade bude bod algoritmu, ktorý určuje kritérium optimality, upravený nasledovne.
Ak sa nájde maximum (minimum) lineárneho tvaru a v jeho vyjadrení nie sú žiadne nebázické premenné s kladnými (zápornými) koeficientmi, potom je kritérium optimality splnené a výsledné základné riešenie je optimálne - riešenie je hotové. Ak pri zistení maxima (minima) lineárneho tvaru obsahuje jeho vyjadrenie jednu alebo viac nebázických premenných s kladnými (zápornými) koeficientmi, pristúpte k novému základnému riešeniu.
Príklad. Nájdite maximum funkcie v rámci obmedzení
Krok I. Zavádzame ďalšie nezáporné premenné a redukujeme tento systém nerovností na jeho ekvivalentný systém rovníc
.
Zavedené prídavné premenné berieme ako hlavné, keďže v tomto prípade je jednoduché nájsť základné riešenie systému. Potom a sú nezákladné premenné.
Vyjadrením hlavných premenných z hľadiska nezákladných dostaneme
Následne toto delenie premenných na základné a nebázické zodpovedá základnému riešeniu 
, ktorá je neplatná (dve premenné sú záporné), a preto nie je optimálna. Od tohto základného riešenia prejdeme k vylepšenému.
Ak chcete rozhodnúť, ktorá premenná by sa mala preniesť z vedľajšej na základnú, zvážte ktorúkoľvek z dvoch dostupných rovníc druhého systému so zápornými voľnými členmi, napríklad druhú. Ukazuje, že a možno ich premeniť na hlavné premenné, keďže v tejto rovnici majú kladné koeficienty (teda, keď sa zvýšia, a to sa stane, ak niektorú z nich prevedieme na hlavné premenné, premenná sa zvýši).
Skúsme to preložiť do hlavnej premennej. Aby sme určili, ktorá premenná by sa mala previesť zo základnej na nebázickú, nájdeme absolútnu hodnotu najmenšieho pomeru voľných členov systému ku koeficientom pri . Máme. Získava sa z tretej rovnice, ktorá ukazuje, že premennú, ktorá je v pôvodnom základnom riešení kladnú, je potrebné previesť na nebázické. Výsledné základné riešenie teda rovnako ako pôvodné obsahuje dve negatívne zložky, t.j. pri prechode na takéto základné riešenie nedôjde k zlepšeniu.
Niť, gombíky a látka sa používajú na výrobu troch druhov košieľ. Zásoby nití, gombíkov a látok, normy ich spotreby na ušitie jednej košele sú uvedené v tabuľke. Nájdite maximálny zisk a optimálny plán výroby produktu, ktorý ho zabezpečuje (nájdite).
| košeľa 1 | košeľa 2 | košeľa 3 | Rezervy | vlákna (m.) | 1 | 9 | 3 | 96 | tlačidlá (ks) | 20 | 10 | 30 | 640 | textil ( | 1 | 2 | 2 | 44 | zisk (r.) | 2 | 5 | 4 |
Riešenie problému
Stavba modelu
Cez a počet košieľ 1., 2. a 3. typu určených na uvoľnenie.
Potom budú obmedzenia zdrojov vyzerať takto:
Navyše podľa zmyslu úlohy
Objektívna funkcia vyjadrujúca získaný zisk:
Dostaneme nasledujúci problém lineárneho programovania:
Redukcia problému lineárneho programovania na kanonickú formu
Zredukujme problém na kanonickú formu. Predstavme si ďalšie premenné. Všetky dodatočné premenné zavedieme do účelovej funkcie s koeficientom rovným nule. Na ľavé strany obmedzení pridáme ďalšie premenné, ktoré nemajú preferovaný tvar, a získame rovnosti.
Riešenie úlohy simplexnou metódou
Vyplňte simplexnú tabuľku:
Keďže problém riešime na maximum - prítomnosť v indexovom riadku záporné čísla pri riešení úlohy na maximum naznačuje, že sme nezískali optimálne riešenie a je potrebné prejsť z tabuľky 0. iterácie na ďalšiu.
Pokračujeme k ďalšej iterácii takto:
vedúci stĺpec zodpovedá
Kľúčový riadok je určený minimálnym pomerom voľných výrazov a členov vedúceho stĺpca (jednoduché vzťahy):
Na priesečníku kľúčového stĺpca a kľúčového radu nájdeme povoľovací prvok, t.j. 9.
Teraz pristúpime k zostaveniu 1. iterácie: Namiesto jednotkového vektora zavedieme vektor .
V novej tabuľke namiesto povoľovacieho prvku napíšeme 1, všetky ostatné prvky kľúčového stĺpca sú nuly. Prvky reťazca kľúčov sú rozdelené na prvok enable. Všetky ostatné prvky tabuľky sa vypočítajú pomocou pravidla obdĺžnika.
Kľúčový stĺpec pre 1. iteráciu zodpovedá
Rozlišovacím prvkom je číslo 4/3. Vektor odvodíme zo základu a namiesto neho zavedieme vektor. Dostaneme tabuľku 2. iterácie.
Kľúčový stĺpec pre 2. iteráciu zodpovedá
Nájdeme kľúčový riadok, na ktorý definujeme:
Rozlišovacím prvkom je číslo 10/3. Vektor odvodíme zo základu a namiesto neho zavedieme vektor. Dostaneme tabuľku 3. iterácie.
| № | BP | c B | A o | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | Simplexné | 2 | 5 | 4 | 0 | 0 | 0 | vzťah | 0 | x 4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | x 5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | x 6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | F j - c j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | x 2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | x 5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | x 6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | F j - c j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | x 2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | x 5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | x 3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | F j - c j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | x 2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | x 1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | x 3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | F j - c j | 95 | 0 | 0 | 0 | 1/4 | 1/40 | 5/4 |
V riadku indexu sú všetky členy nezáporné, takže sa získa nasledujúce riešenie problému lineárneho programovania (vypíšeme ho zo stĺpca voľných členov):
Je potrebné ušiť 24 košieľ 1. druhu, 7 košieľ 2. typu a 3 košele 3. typu. V tomto prípade bude získaný zisk maximálny a bude predstavovať 95 rubľov.
Je potrebné vyriešiť problém lineárneho programovania.
Objektívna funkcia:
2x 1 +5x 2 +3x 3 +8x 4 →min
Obmedzujúce podmienky:
3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1
Uveďme systém obmedzení do kanonickej podoby, na to je potrebné prejsť od nerovností k rovnosti s pridaním ďalších premenných.
Keďže náš problém je problém minimalizácie, musíme ho transformovať na problém maximálneho vyhľadávania. Za týmto účelom zmeníme znamienka koeficientov účelovej funkcie na opačné. Prvky prvej nerovnosti zapíšeme nezmenené, pridáme ďalšiu premennú x 5 a zmeníme znamienko „≤“ na „=“. Keďže druhá a tretia nerovnosť majú znamienko „≥“, je potrebné zmeniť znamienka ich koeficientov na opačné a zaviesť do nich ďalšie premenné x 6 a x 7, resp. V dôsledku toho dostaneme ekvivalentný problém:
3x 1 +6x 2 -4x 3 +x 4 +x 5 = 12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 = -6
-3x 1 -7x 2 -x 3 +x 7 = -1
Pokračujeme k vytvoreniu počiatočnej simplexnej tabuľky. Koeficienty účelovej funkcie s opačným znamienkom sa zapisujú do riadku F tabuľky.
|
Voľný člen |
|||||
| F | |||||
| X5 | |||||
| X6 | |||||
| X7 |
V nami zostavenej tabuľke sú v stĺpci voľných členov záporné prvky, medzi nimi nájdeme maximum v module - to je prvok: -6, nastavuje vodiaci riadok - X6. V tomto riadku nájdeme aj maximálny záporný prvok v module: -10 nachádza sa v stĺpci X3, ktorý bude vedúcim stĺpcom. Premenná v úvodnom riadku je vylúčená zo základu a premenná zodpovedajúca prvému stĺpcu je zahrnutá do základu. Prepočítajme simplexnú tabuľku:
| X1 | X2 | X6 | X4 | Voľný člen | |
| F | 0.8 | 8.9 | 0.3 | 6.5 | -1.8 |
| X5 | 4.6 | 0.8 | -0.4 | 3 | 14.4 |
| X3 | 0.4 | -1.3 | -0.1 | 0.5 | 0.6 |
| X7 | -2.6 | -8.3 | -0.1 | 0.5 | -0.4 |
V nami zostavenej tabuľke sú v stĺpci voľných členov záporné prvky, medzi nimi nájdeme maximum v module - to je prvok: -0,4, nastavuje vodiaci riadok - X7. V tomto riadku nájdeme aj maximálny záporný prvok v module: -8,3 nachádza sa v stĺpci X2, ktorý bude vedúcim stĺpcom. Premenná v úvodnom riadku je vylúčená zo základu a premenná zodpovedajúca prvému stĺpcu je zahrnutá do základu. Prepočítajme simplexnú tabuľku:
| X1 | X7 | X6 | X4 | Voľný člen | |
| F | -1.988 | 1.072 | 0.193 | 7.036 | -2.229 |
| X5 | 4.349 | 0.096 | -0.41 | 3.048 | 14.361 |
| X3 | 0.807 | -0.157 | -0.084 | 0.422 | 0.663 |
| X2 | 0.313 | -0.12 | 0.012 | -0.06 | 0.048 |
Keďže v stĺpci voľných členov nie sú žiadne záporné prvky, našlo sa prípustné riešenie. Riadok F obsahuje záporné prvky, čo znamená, že výsledné riešenie nie je optimálne. Definujme vedúci stĺpec. Aby sme to dosiahli, nájdeme v riadku F záporný prvok s maximálnym modulom - to je -1,988 Vedúci riadok bude ten, pre ktorý je pomer voľného člena k zodpovedajúcemu prvku vedúceho stĺpca minimálny. Vodiaci riadok je X2 a vodiaci prvok je: 0,313.
| X2 | X7 | X6 | X4 | Voľný člen | |
| F | 6.351 | 0.31 | 0.269 | 6.655 | -1.924 |
| X5 | -13.895 | 1.763 | -0.577 | 3.882 | 13.694 |
| X3 | -2.578 | 0.152 | -0.115 | 0.577 | 0.539 |
| X1 | 3.195 | -0.383 | 0.038 | -0.192 | 0.153 |
Keďže v reťazci F nie sú žiadne negatívne prvky
sa našlo optimálne riešenie. Keďže pôvodnou úlohou bolo nájsť minimum, optimálnym riešením bude voľný člen reťazca F, braný s opačným znamienkom. F = 1,924
s premennými hodnotami rovnými: x 3 = 0,539, x 1 = 0,153. Premenné x 2 a x 4 nie sú zahrnuté v základe, takže x 2 = 0 x 4 = 0.
Podobné články
