Domov › Internet › Řešení úlohy lineárního programování pomocí simplexní metody. Duální simplexová metoda

Řešení úlohy lineárního programování pomocí simplexní metody. Duální simplexová metoda

Chcete-li povolit spuštění apletu na vašem počítači, musíte provést následující – klepněte na Start>Ovládací panely>Programy>Java. V okně Java Control Panel vyberte záložku Security, klikněte na tlačítko Edit Site List, tlačítko Add a do volného pole vložte cestu k této stránce z adresního řádku prohlížeče. Dále klikněte na OK a restartujte počítač.

Pro spuštění apletu klikněte na tlačítko "Simplex". Pokud nad tímto řádkem není vidět tlačítko „Simplex“, není na vašem počítači nainstalována Java.

Po kliknutí na tlačítko „Simplex“ se objeví první okno pro zadání počtu proměnných a počtu omezení problému na simplexní metodě.

Po kliknutí na tlačítko „ok“ se zobrazí okno pro zadání zbývajících dat problému pomocí simplexní metody: režim zobrazení (desetinné zlomky nebo obyčejné), typ kritéria úlohy min nebo max, zadání koeficientů účelové funkce a koeficienty systému omezení se znaménky „≤“, „ ≥ „nebo „=", omezení tvaru x i ≥ 0 není třeba zavádět, bere je v úvahu ve svém algoritmu.

Po kliknutí na tlačítko „Vyřešit“ se zobrazí okno s výsledky řešení problému .Okno se skládá ze dvou částí, v horní části je textové pole obsahující popis redukce původního problému do kanonické podoby, která slouží k sestavení první simplexní tabulky. Ve spodní části okna v panelu se záložkami jsou simplexní tabulky každé iterace s malým textovým polem ve spodní části označujícím sloupec rozlišení, řádek rozlišení a další informace, díky nimž se program trénuje. V záložce s optimální (poslední) tabulkou je v textovém poli zobrazeno výsledné optimální řešení úlohy.

Veškeré chyby, kterých si všimnete, a komentáře k apletu zasílejte na: [e-mail chráněný] nebo volejte 8 962 700 77 06, za což Vám budeme velmi vděčni.

Program M-metody

Program pro řešení dopravního problému

Zde je ruční (nikoli appletové) řešení dvou problémů pomocí simplexní metody (obdoba appletového řešení) s podrobným vysvětlením pro pochopení algoritmu pro řešení problémů. První úloha obsahuje znaménka nerovnosti pouze „≤“ (problém s počátečním základem), druhá může obsahovat znaménka „≥“, „≤“ nebo „=“ (problém s umělým základem), řeší se různě.

Simplexní metoda, řešení problému s výchozím základem

1)Simplexní metoda pro problém s počáteční bází (všechny znaky omezení nerovností " ≤ ").

Zapišme si problém kanonický formě, tzn. přepisujeme omezení nerovnosti ve formě rovnosti a přidáváme rozvaha proměnné:

Tato soustava je soustava s bází (báze s 1, s 2, s 3, každá z nich je obsažena pouze v jedné rovnici soustavy s koeficientem 1), x 1 a x 2 jsou volné proměnné. Problémy, které mají být řešeny simplexovou metodou, musí mít následující dvě vlastnosti:
-systém omezení musí být soustavou rovnic se základem;
-volné členy všech rovnic v systému musí být nezáporné.

Výsledná soustava je soustava s bází a její volné členy jsou nezáporné, lze tedy použít simplexovou metodu. Vytvořme první simplexovou tabulku (Iterace 0), tzn. tabulka koeficientů účelové funkce a soustava rovnic pro odpovídající proměnné. Zde „BP“ znamená sloupec základních proměnných, „Solution“ znamená sloupec pravých stran systémových rovnic. Řešení není optimální, protože v řádku z jsou záporné koeficienty.

iterace 0

BP	Řešení	přístup

Pro zlepšení řešení přejdeme k další iteraci a získáme následující simplexní tabulku. Chcete-li to provést, musíte vybrat povolit sloupec, tj. proměnná, která bude zahrnuta do základu při další iteraci. Vybírá se největším absolutním záporným koeficientem v řádku z (v maximální úloze) - v počáteční iteraci je to sloupec x 2 (koeficient -6).

Poté vyberte povolit řetězec, tj. proměnná, která opustí základ při další iteraci. Vybírá se nejmenším poměrem sloupce „Rozhodnutí“ k odpovídajícím kladným prvkům sloupce rozlišení (sloupec „Poměr“) - v počáteční iteraci je to řádek s 3 (koeficient 20).

Permisivní prvek je na průsečíku rozlišovacího sloupce a rozlišovacího řádku, jeho buňka je barevně zvýrazněna, je rovna 1. Při další iteraci tedy proměnná x 2 nahradí s 3 v základu. Všimněte si, že vztah se nehledá v řetězci z; je tam umístěna pomlčka „-“. Pokud existují shodné minimální vztahy, vybere se kterýkoli z nich. Pokud jsou všechny koeficienty ve sloupci rozlišení menší nebo rovné 0, pak je řešení problému nekonečné.

Vyplňte následující tabulku „Iterace 1“. Získáme to z tabulky „Iterace 0“. Cílem dalších transformací je přeměnit sloupec rozlišení x2 na sloupec jednotek (s jednotkou místo prvku rozlišení a nulami místo zbývajících prvků).

1) Vypočítejte řádek x 2 tabulky „Iterace 1“. Nejprve vydělíme všechny členy rozlišovacího řádku s 3 tabulky „Iterace 0“ rozlišovacím prvkem (v tomto případě je roven 1) této tabulky, dostaneme řádek x 2 v tabulce „Iterace 1“ . Protože rozlišovací prvek je v tomto případě roven 1, pak se řádek s 3 tabulky „Iterace 0“ bude shodovat s řádkem x 2 tabulky „Iterace 1“. Řádek x 2 tabulky Iterace 1 máme 0 1 0 0 1 20, zbývající řádky tabulky Iterace 1 získáme z tohoto řádku a řádků tabulky Iterace 0 takto:

2) Výpočet z-řádku tabulky „Iterace 1“. Místo -6 v prvním řádku (řádek z) ve sloupci x2 tabulky Iterace 0 by měla být 0 v prvním řádku tabulky Iterace 1. Chcete-li to provést, vynásobte všechny prvky řádku x 2 tabulky "Iterace 1" 0 1 0 0 1 20 6, dostaneme 0 6 0 0 6 120 a tento řádek sečteme s prvním řádkem (z - řádek) tabulky "Iterace 0" -4 -6 0 0 0 0, dostaneme -4 0 0 0 6 120. Ve sloupci x 2 se objeví nula 0, cíl je dosažen. Prvky sloupce rozlišení x 2 jsou zvýrazněny červeně.

3) Výpočet řádku s 1 tabulky „Iterace 1“. Místo 1 na 1 řádek tabulky „Iterace 0“ by měla být v tabulce „Iterace 1“ 0. Chcete-li to provést, vynásobte všechny prvky řádku x 2 tabulky "Iterace 1" 0 1 0 0 1 20 -1, získejte 0 -1 0 0 -1 -20 a přidejte tento řádek s 1 - řádek tabulky "Iterace 0" 2 1 1 0 0 64, dostaneme řádek 2 0 1 0 -1 44. Ve sloupci x 2 dostaneme požadovanou 0.

4) Vypočítejte řádek s 2 tabulky „Iterace 1“. Na místě 3 v s 2 řádku tabulky "Iterace 0" by měla být 0 v tabulce "Iterace 1". Chcete-li to provést, vynásobte všechny prvky řádku x 2 tabulky „Iterace 1“ 0 1 0 0 1 20 -3, získejte 0 -3 0 0 -3 -60 a přidejte tento řádek s s 2 - řádek tabulky „Iterace 0“ 1 3 0 1 0 72, dostaneme řádek 1 0 0 1 -3 12. Ve sloupci x 2 je získána požadovaná 0 Sloupec x 2 v tabulce „Iterace 1“ se stal jednotkou , obsahuje jednu 1 a zbytek 0.

Řádky tabulky „Iterace 1“ se získají podle následujícího pravidla:

Nový řádek = starý řádek – (koeficient sloupce rozlišení starého řádku)* (nový řádek rozlišení).

Například pro z-řetězec máme:

Starý z-řetězec (-4 -6 0 0 0 0)
-(-6)*Nový řádek rozlišení -(0-6 0 0 -6 -120)
=Nový z-řetězec(-4 0 0 0 6 120) .

U následujících tabulek je přepočet prvků tabulky proveden obdobným způsobem, proto jej vynecháme.

iterace 1

						Řešení	přístup

Vyřešení sloupce x 1, vyřešení řádku s 2, s 2 opustí základ, x 1 vstoupí do základu. Úplně stejným způsobem získáme zbývající simplexní tabulky, dokud nezískáme tabulku se všemi kladnými koeficienty v řádku z. To je známka optimálního stolu.

Iterace 2

						Řešení	přístup

Vyřešení sloupce s 3, vyřešení řádku s 1, s 1 opustí základ, s 3 vstoupí do základu.

Iterace 3

						Řešení	přístup

V řádku z jsou všechny koeficienty nezáporné, proto dostaneme optimální řešení x 1 = 24, x 2 = 16, z max = 192.

Simplexová metoda, řešení problému s umělým základem

2) Vyřešme problém s umělým základem (alespoň jeden omezující znak nerovnosti „≥“ nebo „=“).

Zapišme úlohu v kanonickém tvaru (ve formě soustavy rovnic, která vyžaduje simplexovou metodu), k tomu zavedeme dvě proměnné x 3 ≥ 0 a x 4 ≥ 0, dostaneme:

Systém omezení nabízí pouze jednu přípustnou základní proměnnou x 4, pouze je zahrnuta pouze v jedné rovnici ve třetí s koeficientem 1, takže do první a druhé rovnice přidáme umělé proměnné R 1 ≥ 0 a R 2 ≥ 0 aby mohla být aplikována simplexová metoda, musí být omezovací rovnice systému systémem s bází, tzn. v každé rovnici musí být proměnná s koeficientem 1, která je obsažena pouze v jedné rovnici systému, v našem případě jsou to R 1, R 2 a x 4. Dostali jsme takzvaný M-úkol:

Tento systém je systémem s bází, ve kterém R 1, R 2 a x 4 jsou základní proměnné a x 1, x 2 a x 3 jsou volné proměnné, volné členy všech rovnic jsou nezáporné. Proto lze k řešení problému použít simplexovou metodu. Zapišme si počáteční simplexní tabulku:

iterace 0

	Řešení	přístup
-16

Pro problémy s umělým základem byl do tabulky přidán řádek „Hodnocení“. Získá se sečtením odpovídajících koeficientů řádků s umělými proměnnými (R) s opačným znaménkem. V tabulce bude přítomna tak dlouho, dokud bude v základu alespoň jedna z umělých proměnných. Na základě největšího modulo záporného koeficientu řádku „Vyhodnocení“ se určí rozlišovací sloupec, dokud je v tabulce. Když řádek "Evaluation" opustí tabulku (v základu nejsou žádné umělé proměnné), bude rozlišovací sloupec určen řádkem z, jako v problému s počátečním základem. V této tabulce je rozlišovací sloupec x 2, je vybrán na základě největšího absolutního negativního skóre (-7).Řešicí řádek R 2 je vybrán na základě nejmenšího poměru sloupce „Řešení“ k odpovídajícím kladným prvkům rozlišovacího sloupce, jako v úloze bez umělých proměnných. To znamená, že při další iteraci proměnná x2 přejde z volné na základní a proměnná R2 ze základní na volnou. Zapišme si následující simplexní tabulku:

Vyřešení sloupce x 1, vyřešení řádku R 1, R 1 opustí základ, x 1 vstoupí do základu. Poté v základu nezůstanou žádné umělé proměnné, takže v následující tabulce není žádný řádek „Vyhodnocení“:

iterace 2

							Řešení	přístup

Dále je pomocí z-řádku vybrán sloupec rozlišení. V řádku z jsou všechny koeficienty nezáporné s výjimkou koeficientu pro umělou proměnnou R 1, který neovlivňuje optimalitu, když umělé proměnné opustí bázi. V důsledku toho je získáno optimální řešení x 1 = 6/5; x 2 = 3/5; z max = 72/5.

Speciální případy použití simplexové metody

1) Když je přímka (pokud je uvažován problém dvourozměrného lineárního programování a v obecném případě nadrovina) reprezentující účelovou funkci rovnoběžná s přímkou (nadrovinou) odpovídající jednomu z omezení nerovnosti (která na optimální bod je splněn jako přesná rovnost), účelová funkce nabývá jedničky a je také optimální hodnotou v určité množině bodů na hranici oblasti proveditelných řešení. Tato řešení se nazývají alternativní optimální řešení. Přítomnost alternativních řešení lze určit pomocí optimální simplexové tabulky. Pokud z-řádek optimální tabulky obsahuje nulové koeficienty nezákladních proměnných, pak existují alternativní řešení.

2) Pokud jsou v rozlišovacím sloupci simplexové tabulky všechny koeficienty menší nebo rovné nule, pak nelze vybrat rozlišovací řádek, v tomto případě je řešení neomezené.

3) Pokud jsou omezení problému lineárního programování nekonzistentní (to znamená, že nemohou být splněna současně), pak problém nemá žádná proveditelná řešení. Tato situace nemůže nastat, pokud všechny nerovnosti, které tvoří systém omezení, jsou typu „≤“ s nezápornými pravými stranami, protože v tomto případě mohou další proměnné představovat proveditelné řešení. Pro jiné typy omezení se používají umělé proměnné. Pokud má úloha řešení, pak v optimální tabulce nejsou v základu žádné umělé proměnné (R i). Pokud tam jsou, pak problém nemá řešení.

Nitě, knoflíky a látka se používají k výrobě tří druhů košil. Zásoby nití, knoflíků a látek, normy jejich spotřeby na ušití jedné košile jsou uvedeny v tabulce. Najděte maximální zisk a optimální plán výroby produktu, který jej zajišťuje (najděte).

košile 1

košile 2

košile 3

Rezervy

vlákna (m.)

tlačítka (ks)

640

textil (

zisk (r.)

Řešení problému

Vytváření modelu

Průchozí a počet košil 1., 2. a 3. typu určených k vydání.

Omezení zdrojů pak bude vypadat takto:

Navíc podle smyslu úkolu

Objektivní funkce vyjadřující získaný zisk:

Dostaneme následující problém lineárního programování:

Redukce problému lineárního programování na kanonickou formu

Redukujme problém na kanonickou formu. Zavedeme další proměnné. Všechny další proměnné zavedeme do účelové funkce s koeficientem rovným nule. Na levé strany omezení přidáme další proměnné, které nemají preferovaný tvar, a získáme rovnosti.

Řešení úlohy simplexovou metodou

Vyplňte simplexní tabulku:

Vzhledem k tomu, že problém řešíme na maximum, přítomnost záporných čísel v indexovém řádku při řešení problému na maximum naznačuje, že jsme nezískali optimální řešení a že je nutné přejít z tabulky 0. iterace na další.

Pokračujeme k další iteraci takto:

přední sloupec odpovídá

Klíčový řádek je určen minimálním poměrem volných členů a členů vedoucího sloupce (simplexní vztahy):

Na průsečíku klíčového sloupce a klíčové řady najdeme povolovací prvek, tzn. 9.

Nyní přistoupíme ke kompilaci 1. iterace: Místo jednotkového vektoru zavedeme vektor .

V nové tabulce místo povolovacího prvku napíšeme 1, všechny ostatní prvky klíčového sloupce jsou nuly. Prvky řetězce klíčů jsou rozděleny na prvek enable. Všechny ostatní prvky tabulky se vypočítají pomocí pravidla obdélníku.

Klíčový sloupec pro 1. iteraci odpovídá

Rozlišovacím prvkem je číslo 4/3. Vektor odvodíme ze základu a místo něj zavedeme vektor. Dostaneme tabulku 2. iterace.

Klíčový sloupec pro 2. iteraci odpovídá

Najdeme klíčový řádek, pro něj definujeme:

Rozlišovacím prvkem je číslo 10/3. Vektor odvodíme ze základu a místo něj zavedeme vektor. Dostaneme tabulku 3. iterace.

№

c B

A o

x 1

x 2

x 3

x 4

x 5

x 6

Simplexní

vztah

x 4

32/3

x 5

640

x 6

F j - c j

-2

-5

-4

x 2

32/3

1/9

1/3

1/9

x 5

1600/3

170/9

80/3

-10/9

x 6

68/3

7/9

4/3

-2/9

F j - c j

160/3

-13/9

-7/3

5/9

x 2

-1/12

1/6

-1/4

x 5

10/3

-20

x 3

7/12

-1/6

3/4

204/7

F j - c j

-1/12

1/6

7/4

x 2

1/4

1/40

-3/4

x 1

3/10

-6

x 3

-3/4

-7/40

17/4

F j - c j

1/4

1/40

5/4

V řádku indexu jsou všechny členy nezáporné, takže získáme následující řešení problému lineárního programování (vypíšeme ho ze sloupce volných členů):

Je potřeba ušít 24 košil 1. druhu, 7 košil 2. typu a 3 košile 3. typu. V tomto případě bude získaný zisk maximální a bude činit 95 rublů.

Pomoc při řešení vašich problémů na toto téma můžete najít zasláním zprávy na VKontakte, Viber nebo vyplněním formuláře. Náklady na řešení domácích úkolů začínají od 7 BYR. za úkol (200 ruských rublů), ale ne méně než 10 běloruských rublů. (300 RUB) za celou objednávku. Detailní provedení. Náklady na online asistenci při zkoušce (v tomto případě je vyžadována 100% platba předem) jsou od 30 BYR. (1000 ruských rublů) za vyřešení tiketu.

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ě. Chcete-li to provést, 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ákladu) 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á-line obsahuje několik takových koeficientů, 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í simplexní tabulku.

Proměnné	Základní a doplňkové proměnné	volných členů (řešení)	Odhadovaný přístup
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í

Simplexní metoda je iterativní proces řízeného řešení soustavy rovnic v krocích, který začíná referenčním řešením a při hledání nejlepší možnosti se pohybuje podél rohových bodů oblasti proveditelného řešení a zlepšuje hodnotu cílové funkce, dokud se objektivní funkce dosáhne optimální hodnoty.

Účel služby. Služba je určena pro online řešení problémů lineárního programování (LPP) pomocí simplexní metody v následujících formách zápisu:

ve formě simplexní tabulky (jordánská transformační metoda); základní záznamový formulář;
modifikovaná simplexová metoda; ve sloupcovém tvaru; v řádkové podobě.

Instrukce. Vyberte počet proměnných a počet řádků (počet omezení). Výsledné řešení se uloží do souboru Word a Excel.

V tomto případě neberte v úvahu omezení jako x i ≥ 0. Pokud pro některé x i nejsou v úloze žádná omezení, tak je třeba ZLP převést na KZLP, případně využít tuto službu. Při řešení se automaticky určí použití M-metoda(jednoduchá metoda s umělým základem) a dvoustupňová simplexová metoda.

S touto kalkulačkou se také používají následující:
Grafická metoda řešení ZLP
Řešení dopravního problému
Řešení maticové hry
Pomocí online služby můžete určit cenu maticové hry (dolní a horní hranice), zkontrolovat přítomnost sedlového bodu, najít řešení smíšené strategie pomocí následujících metod: minimax, simplexová metoda, grafická (geometrická ) metoda, Brownova metoda.
Extrém funkce dvou proměnných
Problémy dynamického programování
Rozdělte 5 homogenních partií zboží mezi tři trhy tak, abyste z jejich prodeje získali maximální příjem. Příjem z prodeje na každém trhu G(X) závisí na počtu prodaných šarží produktu X a je uveden v tabulce.

Objem produktu X (v šaržích)	Příjem G(X)
Objem produktu X (v šaržích)	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Algoritmus simplexní metody zahrnuje následující kroky:

Sestavení prvního základního plánu. Přechod ke kanonické podobě problému lineárního programování zavedením nezáporných dodatečných bilančních proměnných.
Kontrola optimálnosti plánu. Pokud je alespoň jeden koeficient indexové čáry menší než nula, pak plán není optimální a je třeba jej zlepšit.
Určení úvodního sloupce a řádku. Ze záporných koeficientů indexové čáry se vybere největší v absolutní hodnotě. Poté se prvky sloupce volného členu simplexní tabulky rozdělí na prvky stejného znaménka vedoucího sloupce.
Vytvoření nového referenčního plánu. Přechod na nový plán je proveden jako výsledek přepočtu simplexní tabulky pomocí Jordan-Gaussovy metody.

Pokud je potřeba najít extrém účelové funkce, pak mluvíme o nalezení minimální hodnoty (F(x) → min, viz příklad řešení minimalizace funkce) a maximální hodnoty ((F(x ) → max, viz příklad řešení maximalizace funkce)

Krajního řešení je dosaženo na hranici oblasti proveditelných řešení na jednom z vrcholů rohových bodů polygonu, nebo na segmentu mezi dvěma sousedními rohovými body.

Základní věta lineárního programování. Dosáhne-li účelová funkce ZLP v nějakém bodě v oblasti možných řešení extrémní hodnoty, nabývá této hodnoty v rohovém bodě. Pokud účelová funkce ZLP dosáhne extrémní hodnoty ve více než jednom rohovém bodě, pak nabývá stejné hodnoty v kterékoli z konvexních lineárních kombinací těchto bodů.

Podstata simplexové metody. Pohyb k optimálnímu bodu se provádí pohybem z jednoho rohového bodu do sousedního, čímž se přibližuje a zrychluje X opt. Takové schéma pro výčet bodů, tzv. simplexní metoda, navrhl R. Danzig.
Rohové body jsou charakterizovány m základními proměnnými, takže přechod z jednoho rohového bodu do sousedního lze provést změnou pouze jedné základní proměnné v bázi na proměnnou z nepodložené.
Implementace simplexové metody má vzhledem k různým vlastnostem a formulacím úloh LP různé modifikace.

Konstrukce simplexových stolů pokračuje, dokud není dosaženo optimálního řešení. Jak můžete pomocí simplexní tabulky určit, že řešení problému lineárního programování je optimální?
Pokud poslední řádek (hodnoty účelové funkce) neobsahuje záporné prvky, najde optimální plán.

Poznámka 1. Je-li jedna ze základních proměnných rovna nule, pak krajní bod odpovídající takovému základnímu řešení je degenerovaný. Degenerace nastává, když existuje nejednoznačnost ve výběru vodící linie. Degenerace problému si nemusíte vůbec všimnout, pokud si jako vodítko zvolíte jinou linii. V případě nejednoznačnosti by měl být vybrán řádek s nejnižším indexem, aby se zabránilo zacyklení.

Poznámka 2. Nechť jsou v nějakém extrémním bodě všechny simplexní rozdíly nezáporné D k ³ 0 (k = 1..n+m), tzn. získá se optimální řešení a existuje A k - bezbázový vektor, pro který D k = 0. Pak je dosaženo maxima alespoň ve dvou bodech, tzn. existuje alternativní optimum. Pokud tuto proměnnou x k zavedeme do báze, hodnota účelové funkce se nezmění.

Poznámka 3. Řešení duální úlohy je v poslední simplexní tabulce. Posledních m složek vektoru simplexních rozdílů (ve sloupcích bilančních proměnných) je optimálním řešením duální úlohy. Hodnoty objektivních funkcí přímého a duálního problému v optimálních bodech se shodují.

Poznámka 4. Při řešení minimalizační úlohy se do báze zavede vektor s největším kladným simplexním rozdílem. Dále se použije stejný algoritmus jako pro problém maximalizace.

Pokud je uvedena podmínka „Je nutné, aby suroviny typu III byly zcela spotřebovány“, pak je odpovídající podmínkou rovnost.

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.

Oblíbené v kategorii: