Simplexní metoda, příklady řešení problémů. Simplexní metoda řešení problémů
Jedna z metod řešení optimalizačních problémů ( obvykle spojené s nalezením minima nebo maxima) lineární programování se nazývá . Simplexní metoda zahrnuje celou skupinu algoritmů a metod pro řešení problémů lineárního programování. Jedna z těchto metod, která zahrnuje zaznamenání zdrojových dat a jejich přepočet do speciální tabulky, se nazývá tabulková simplexová metoda.
Uvažujme algoritmus tabulkové simplexové metody na příkladu řešení výrobní úkol, která se scvrkává na nalezení výrobního plánu, který zajistí maximální zisk.
Vstupní data pro úlohu simplexní metody
Společnost vyrábí 4 druhy výrobků, zpracovává je na 3 strojích.
Časové normy (min./kus) pro zpracování výrobků na strojích jsou specifikovány maticí A:
Fond provozní doby stroje (min.) je uveden v matici B:
Zisk z prodeje každé jednotky produktu (RUB/kus) je dán maticí C:
Účel výrobního úkolu
Vypracujte plán výroby, který maximalizuje zisk podniku.
Řešení úlohy tabulkovou simplexovou metodou
(1) Označme X1, X2, X3, X4 plánovaný počet výrobků každého typu. Pak požadovaný plán: ( X1, X2, X3, X4)
(2) Zapišme si omezení plánu ve formě soustavy rovnic:
(3) Pak je cílový zisk:
Čili zisk z plnění plánu výroby by měl být maximální.
(4) Abychom vyřešili výsledný podmíněný extrém, nahradíme systém nerovnic systémem lineárních rovnic tím, že do něj vložíme další nezáporné proměnné ( X5, X6, X7).
(5) Přijměme následující referenční plán:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Zadáme data do simplexní stůl:
V posledním řádku zadáme koeficienty účelové funkce a její hodnotu samotnou s opačným znaménkem;
(7) Vyberte v posledním řádku největší (modulo) záporné číslo.
Pojďme počítat b = N / Items_of_the_selected_column
Mezi vypočtenými hodnotami b vybereme nejméně.
Průsečík vybraného sloupce a řádku nám dá rozlišovací prvek. Změníme základ na proměnnou odpovídající rozlišovacímu prvku ( X5 až X1).
- Samotný rozlišovací prvek se změní na 1.
- Pro prvky rozlišovací čáry – a ij (*) = a ij / RE ( to znamená, že každý prvek vydělíme hodnotou rozlišovacího prvku a získáme nová data).
- U prvků sloupce rozlišení se jednoduše vynulují.
- Zbývající prvky tabulky přepočítáme pomocí pravidla obdélníku.
a ij (*) = a ij – (A * B / RE)
Jak vidíte, vezmeme aktuální buňku, která se přepočítává, a buňku s rozlišovacím prvkem. Tvoří protilehlé rohy obdélníku. Dále vynásobíme hodnoty z buněk dalších 2 rohů tohoto obdélníku. Tato práce ( A * B) vydělte rozlišovacím prvkem ( RE). A odečíst od aktuální buňky, která se přepočítává ( a ij) co se stalo. Dostáváme novou hodnotu - a ij (*).
(9) Znovu zkontrolujte poslední řádek ( C) na přítomnost záporných čísel. Pokud tam nejsou, byl nalezen optimální plán, přecházíme do poslední fáze řešení problému. Pokud ano, plán ještě není optimální a simplexovou tabulku je třeba znovu přepočítat.
Protože v posledním řádku máme opět záporná čísla, začneme novou iteraci výpočtů.
(10) Protože v posledním řádku nejsou žádné negativní prvky, znamená to, že jsme našli optimální plán výroby! Konkrétně: vyrobíme ty produkty, které se přesunuly do sloupce „Základ“ - X1 a X2. Známe zisk z výroby každé jednotky výstupu ( matice C). Zbývá vynásobit zjištěné objemy výroby výrobků 1 a 2 ziskem na 1 kus, dostaneme konečný ( maximum! ) zisk pro daný výrobní plán.
ODPOVĚDĚT:
X1 = 32 ks, X2 = 20 ks, X3 = 0 ks, X4 = 0 ks.
P = 48 * 32 + 33 * 20 = 2 196 rub.
Galyautdinov R.R.
© Kopírování materiálu je přípustné pouze v případě přímého hypertextového odkazu na
Pokud potřebujete vyřešit problém lineárního programování pomocí simplexních tabulek, pak vám naše online služba velmi pomůže. Simplexová metoda zahrnuje postupné prohledávání všech vrcholů rozsahu přijatelných hodnot, aby se našel vrchol, kde funkce nabývá extrémní hodnoty. V první fázi je nalezeno nějaké řešení, které se v každém následujícím kroku zlepšuje. Toto řešení se nazývá základní. Zde je posloupnost akcí při řešení problému lineárního programování pomocí simplexní metody:
První krok. V sestavené tabulce se nejprve musíte podívat na sloupec s volnými členy. Pokud jsou v něm negativní prvky, pak je nutné přejít na druhý krok, pokud ne, tak na pátý.
Druhý krok.
Ve druhém kroku je nutné rozhodnout, kterou proměnnou vyloučit ze základu a kterou zahrnout pro přepočet simplexní tabulky. Za tímto účelem prohlédneme sloupec s volnými termíny a najdeme v něm negativní prvek. Čára se záporným prvkem se bude nazývat proklad. V něm najdeme maximální záporný prvek v modulu, odpovídající sloupec je podřízený. Pokud jsou mezi volnými výrazy záporné hodnoty, ale ne v odpovídajícím řádku, pak taková tabulka nebude mít řešení. Proměnná v úvodním řádku umístěná ve sloupci volných termínů je vyloučena ze základu a proměnná odpovídající úvodnímu sloupci je zahrnuta do základu.
| Stůl 1. | základní proměnné | Volní členové pod omezením | |||||
| Nezákladní proměnné | x 1 | ... | x 2 | ... | x l | ||
| x n | x n+1 | b 1 | 11 | ... | 12 | ... | 1l |
| a 1n | x n+2 | b 2 | 21 | ... | 22 | ... | 2l |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| a 2n | x n+r | b2 | a r1 | ... | a r2 | ... | a rl |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| arn | x n+m | b m | m1 | ... | m2 | ... | ml |
| a mn | F(x)max | F 0 | -c 1 | ... | F 0 | ... | -c 2 |
-c n
Třetí krok. Ve třetím kroku přepočítáme celou simplexovou tabulku pomocí speciálních vzorců;
Čtvrtý krok. Pokud po přepočtu zbývají ve sloupci volných členů záporné prvky, přejděte k prvnímu kroku, pokud žádné nejsou, pak k pátému.
Pátý krok. Pokud jste dosáhli pátého kroku, pak jste našli řešení, které je přijatelné. To však neznamená, že je optimální. Optimální bude pouze tehdy, pokud budou všechny prvky v F-struně kladné. Pokud tomu tak není, pak je nutné řešení vylepšit, u kterého najdeme úvodní řádek a sloupec pro další přepočet pomocí následujícího algoritmu. Zpočátku najdeme minimální záporné číslo v řetězci F, kromě hodnoty funkce. Sloupec s tímto číslem bude vedoucí. Abychom našli úvodní řádek, najdeme poměr odpovídajícího volného členu a prvku z úvodního sloupce, pokud jsou kladné. Minimální poměr vám umožní určit vedoucí čáru. Tabulku opět přepočítáme pomocí vzorců, tzn. přejděte ke kroku 3. Uvažujme simplexní metoda
pro řešení problémů lineárního programování (LP). Je založen na přechodu z jednoho referenčního plánu do druhého, při kterém se zvyšuje hodnota účelové funkce.
- Původní problém transformujeme do kanonické podoby zavedením dalších proměnných. Pro nerovnice tvaru ≤ se uvádějí další proměnné se znaménkem (+), ale pokud jsou ve tvaru ≥, pak se znaménkem (-). Do účelové funkce jsou zavedeny další proměnné s odpovídajícími znaménky s koeficientem rovným 0 , protože cílová funkce by neměla měnit svůj ekonomický význam.
- Vektory jsou vypsány P i z koeficientů proměnných a sloupce volných členů. Tato akce určuje počet jednotkových vektorů. Platí pravidlo, že jednotkových vektorů by mělo být tolik, kolik je nerovností v systému omezení.
- Poté jsou zdrojová data vložena do simplexní tabulky. Do základu se zavedou jednotkové vektory a jejich vyloučením ze základu se najde optimální řešení. Koeficienty účelové funkce se zapisují s opačným znaménkem.
- Znakem optimality pro problém LP je, že řešení je optimální, pokud je v F– v řádku jsou všechny koeficienty kladné. Pravidlo pro vyhledání aktivačního sloupce - prohlíženo F– řetězec a mezi jeho negativními prvky je vybrán ten nejmenší. Vektor P i jeho obsah se stává permisivním. Pravidlo pro výběr rozlišovacího prvku - sestaví se poměry kladných prvků rozlišovacího sloupce k prvkům vektoru P 0 a číslo, které dává nejmenší poměr, se stává rozlišovacím prvkem, podle kterého se bude simplexní tabulka přepočítávat. Řádek obsahující tento prvek se nazývá povolený řádek. Pokud ve sloupci rozlišení nejsou žádné kladné prvky, pak problém nemá řešení. Po určení rozlišovacího prvku přistoupí k přepočtu nové simplexní tabulky.
- Pravidla pro vyplňování nové simplexní tabulky. Jednotka se umístí na místo rozlišovacího prvku a ostatní prvky se považují za stejné 0 . Rozlišovací vektor je přidán k bázi, ze které je vyloučen odpovídající nulový vektor, a zbývající základní vektory jsou zapsány beze změn. Prvky rozlišovací čáry jsou rozděleny prvkem rozlišení a zbývající prvky jsou přepočítány podle pravidla obdélníku.
- To se provádí do F– všechny prvky řetězce se nestanou pozitivními.
Zvažme řešení problému pomocí výše uvedeného algoritmu.
Vzhledem k tomu:
Převedeme problém do kanonické podoby:
Skládáme vektory:
Vyplňte simplexní tabulku:
:
Pojďme přepočítat první prvek vektoru P 0, pro který uděláme obdélník čísel: a dostaneme: 
.
Podobné výpočty provádíme pro všechny ostatní prvky simplexní tabulky:
V přijatém plánu F– řádek obsahuje jeden záporný prvek – (-5/3), vektor P 1. Obsahuje ve svém sloupci jeden kladný prvek, který bude povolovacím prvkem. Přepočítejme tabulku týkající se tohoto prvku:
Žádné negativní prvky F– řádek znamená nalezený optimální plán:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Lineární programování, M: Nauka, 1998,
- Ventzel E.S. Operační výzkum, M: Sovětský rozhlas, 2001,
- Kuzněcov Yu.N., Kuzubov V.I., Voloshenko A.B. Matematické programování, M: Higher School, 1986.
Vlastní řešení lineárního programování
Jakékoliv zadání v této disciplíně si můžete objednat na našem webu. Můžete připojit soubory a určit termíny na
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S1 = 0 S2 = 15 S3 = 4 R1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | Svatý. člen | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Svatý. člen | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| Si = 0 S2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Lineární programování je technika matematického modelování určená k optimalizaci využití omezených zdrojů. LP se úspěšně používá ve vojenské oblasti, průmyslu, zemědělství, dopravním průmyslu, ekonomice, zdravotnictví a dokonce i ve společenských vědách. Široké využití této metody podporují také vysoce účinné počítačové algoritmy, které tuto metodu implementují. Optimalizační algoritmy pro další, složitější typy modelů a problémů operačního výzkumu (OR), včetně celočíselného, nelineárního a stochastického programování, jsou založeny na algoritmech lineárního programování.
Problém s optimalizací je ekonomický a matematický problém, který spočívá v nalezení optimální (maximální nebo minimální) hodnoty účelové funkce, přičemž hodnoty proměnných musí patřit do určitého rozsahu přijatelných hodnot.
Ve své nejobecnější podobě je problém lineárního programování zapsán matematicky takto:
Kde X = (x 1 , X 2 , ... , X n ) ; W– rozsah přípustných hodnot proměnných X 1 , X 2 , ... , X n ;f(X)- Objektivní funkce.
K vyřešení optimalizačního problému stačí najít jeho optimální řešení, tzn. naznačit to 
v každém případě.
Optimalizační problém je neřešitelný, pokud nemá optimální řešení. Zejména problém maximalizace bude neřešitelný, pokud bude účelová funkce f(X) není shora omezena na přípustnou množinu W.
Metody řešení optimalizačních úloh závisí jak na typu účelové funkce f(X) a ze struktury přípustné množiny W. Pokud je cílová funkce v problému funkcí n proměnné, pak se metody řešení nazývají metody matematického programování.
Charakteristické rysy problémů lineárního programování jsou následující:
index optimality f(X) je lineární funkcí prvků řešení X = (x 1 , X 2 , ... , X n ) ;
omezující podmínky kladené na možná řešení mají podobu lineárních rovností nebo nerovností.
Problém lineárního programování se nazývá problém operačního výzkumu, jehož matematický model má tvar:
(2)
(3)
(4)(5)
V tomto případě systém lineárních rovnic (3) a nerovnic (4), (5), který určuje přípustnou množinu řešení úlohy W, volal systém omezení problémy lineárního programování a lineární funkce f(X) volal cílová funkce nebo kritérium optimality .
Platné řešení je sbírka čísel ( plán ) X = (X 1 , X 2 , ... , X n ) , splňující omezení problému. Optimální řešení – jedná se o plán, ve kterém účelová funkce nabývá své maximální (minimální) hodnoty.
Pokud má matematický model úlohy lineárního programování tvar:
pak říkají, že problém je prezentován v kanonická forma .
Jakýkoli problém lineárního programování lze redukovat na problém lineárního programování v kanonické formě. K tomu v obecném případě musíte být schopni redukovat problém maximalizace na problém minimalizace; přejít od omezení nerovností k omezením rovnosti a nahradit proměnné, které nepodléhají podmínce nezápornosti. Maximalizace určité funkce je ekvivalentní minimalizaci stejné funkce s opačným znaménkem a naopak.
Pravidlo pro převedení problému lineárního programování do kanonické formy je následující:
pokud je v původním problému nutné určit maximum lineární funkce, pak byste měli změnit znaménko a hledat minimum této funkce;
pokud je pravá strana omezení záporná, pak by toto omezení mělo být vynásobeno -1;
pokud jsou mezi omezeními nerovnosti, pak se zavedením dalších nezáporných proměnných přemění na rovnosti;
pokud nějaká proměnná X j nemá žádná omezení znaménka, pak je nahrazen (v objektivní funkci a ve všech omezeních) rozdílem mezi dvěma novými nezápornými proměnnými: X 3 = x 3 + -X 3 - , Kde X 3 + , X 3 - ≥ 0 .
Příklad 1. Redukce problému lineárního programování na kanonickou formu:
min L = 2x 1 +x 2 -X 3 ; 2x 2 -X 3 < 5; X 1 +x 2 -X 3 > -1; 2x 1 -X 2 < -3; X 1 < 0; X 2 > 0; X 3 ≥ 0.
Zaveďme nivelační proměnné do každé rovnice systému omezení X 4 , X 5 , X 6 . Systém bude zapsán ve formě rovnosti a v první a třetí rovnici systému omezení budou proměnné X 4 , X 6 se zadávají do levé strany se znaménkem „+“ a do druhé rovnice proměnná X 5 se zadává se znaménkem "-".
2x 2 -X 3 +x 4 = 5; X 1 +x 2 -X 3 -X 5 = -1; 2x 1 -X 2 +x 6 = -3; X 4 > 0; X 5 > 0; X 6 ≥ 0.
Volné členy v kanonickém tvaru musí být kladné, vynásobte poslední dvě rovnice číslem -1:
2x 2 -X 3 +x 4 = 5; -X 1 -X 2 +x 3 +x 5 = 1; -2x 1 +x 2 -X 6 = 3.
Simplexní metoda pro řešení úloh lineárního programování.
Algoritmus simplexové metody najde optimální řešení zvážením omezeného počtu proveditelných základních řešení. Algoritmus simplexové metody vždy začíná nějakým proveditelným bázovým řešením a poté se snaží najít jiné proveditelné bázové řešení, které „vylepší“ hodnotu účelové funkce. To je možné pouze v případě, že zvýšení jakékoli nulové (nezákladní) proměnné vede ke zlepšení hodnoty účelové funkce. Ale aby se nebázická proměnná stala kladnou, musí být jedna ze současných základních proměnných nastavena na nulu, tzn. převést na nezákladní. To je nutné, aby nové řešení obsahovalo přesně m základní proměnné. V souladu s terminologií simplexové metody se volá vybraná nulová proměnná vstup (k základně) a základní proměnná, která má být odstraněna, je vyloučeno (od základu).
Zavolejte dvě pravidla pro výběr vstupních a vylučovacích proměnných v simplexní metodě stav optimality A podmínka přípustnosti . Pojďme formulovat tato pravidla a také zvážit posloupnost akcí prováděných při implementaci simplexové metody.
Optimální stav. Vstupní proměnná v problému maximalizace (minimalizace) je nebázická proměnná, která má největší záporný (kladný) koeficient v cílová-čára. Pokud v cílová- takových koeficientů je v řádku více, pak se výběr zadané proměnné provádí libovolně. Optimálního řešení je dosaženo, když cílová-line, všechny koeficienty pro nezákladní proměnné budou nezáporné (nekladné).
Podmínka přípustnosti. V úlohách maximalizace i minimalizace se jako vyloučená vybere základní proměnná, pro kterou je poměr hodnoty pravé strany omezení ke kladnému koeficientu vedoucího sloupce minimální. Pokud existuje více základních proměnných s touto vlastností, pak je výběr vyloučené proměnné libovolný.
Uveďme si algoritmus pro řešení úlohy lineárního programování hledání maxima pomocí simplexních tabulek.
F = с 1 x 1 +с 2 x 2 +…+с n x n max
x 1 0, x 2 0,…, x n 0.
1. krok. Zavedeme další proměnné a zapíšeme výslednou soustavu rovnic a lineární funkci ve formě rozšířené soustavy.
F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c str.
2. krok. Složíme počáteční simplexovou tabulku.
|
Proměnné |
Základní a doplňkové proměnné |
volných členů (řešení) |
Odhadovaný přístup |
|||||||
3. krok. Kontrolujeme splnění kritéria optimality - přítomnost záporných koeficientů v posledním řádku. Nejsou-li žádné, pak je řešení optimální a F * =c o, základní proměnné se rovnají odpovídajícím koeficientům b j, nebázické proměnné jsou rovny nule, tj. X * =(b 1,b 2,…, b m, 0,…, 0).
4. krok. Pokud není kritérium optimality splněno, pak největší absolutní záporný koeficient v posledním (odhadovaném) řádku určuje rozlišovací sloupec s.
Pro určení rozlišovací čáry vypočítáme vyhodnocovací poměry 
a vyplňte poslední sloupec tabulky.
Odhadovaný poměr i-té řady je
jestliže b i a a mají různá znaménka;
jestliže b i =0 a a je<0;
jestliže a je =0;
0, pokud b i = 0 a a je > 0;
Ve sloupci hodnotících vztahů najdeme minimální prvek min 
který definuje povolovací řetězec.
Pokud není žádné minimum, pak problém nemá konečné optimum I a je neřešitelný.
V průsečíku rozlišovacího řádku a sloupce je rozlišovací prvek a gs.
5. krok. Sestavme si následující tabulku. Pro tohle
Přejděme ke třetímu kroku.
M-metoda Někdy při řešení ZLP matice koeficientů pro neznámá systémová omezení nemá jednotkové sloupce, ze kterých by se dala poskládat jednotková matice, tzn. nastává problém při výběru základních proměnných nebo je počáteční řešení nepřijatelné. V takových případech použijte metoda umělé báze (M - metoda). Ve všech omezeních, kde neexistují žádné základní proměnné, umělé proměnné. Umělé proměnné jsou do účelové funkce zavedeny s koeficientem (- M) pro úlohy s max a s koeficientem (+ M) pro úlohy s min, kde M je dostatečně velké kladné číslo.. Poté je rozšířený problém řešen pomocí pravidel simplexové metody. Pokud jsou všechny umělé proměnné rovny nule, tzn. jsou vyloučeny ze základu, pak se buď získá optimální řešení původního problému, nebo se původní problém dále řeší a najde se jeho optimální řešení nebo se zjistí jeho neřešitelnost. Pokud se ukáže, že alespoň jedna z umělých proměnných je jiná než nula, pak původní problém nemá řešení
