Řešení produkčního problému tabulkovou simplexovou metodou. Příklad řešení problému. Simplexní metoda řešení LLP

Tato metoda je metodou účelového výčtu referenčních řešení úlohy lineárního programování. Umožňuje konečný počet kroků buď k nalezení optimálního řešení, nebo ke zjištění, že žádné optimální řešení neexistuje.

1. Specifikujte metodu pro nalezení optimálního referenčního řešení
2. Upřesněte způsob přechodu z jednoho referenčního řešení do druhého, na kterém se hodnota účelové funkce bude blížit optimální, tzn. uveďte způsob, jak zlepšit referenční řešení
3. Nastavte kritéria, která vám umožní včas zastavit výčet podpůrných řešení na optimální řešení nebo se řídit závěrem, že optimální řešení neexistuje.

Algoritmus simplexové metody pro řešení úloh lineárního programování

1. Převeďte problém do kanonické podoby
2. Najděte počáteční referenční řešení s „jednotkovým základem“ (pokud neexistuje žádné referenční řešení, pak problém nemá řešení kvůli nekompatibilitě systému omezení)
3. Vypočítejte odhady rozšíření vektorů z hlediska báze referenčního řešení a vyplňte tabulku simplexové metody
4. Pokud je splněno kritérium jednoznačnosti optimálního řešení, řešení problému končí
5. Pokud je splněna podmínka pro existenci množiny optimálních řešení, pak jsou jednoduchým výčtem nalezena všechna optimální řešení

Příklad řešení úlohy simplexovou metodou

Vyřešte problém pomocí simplexní metody:

Řešení:

Dovedeme problém do kanonické podoby.

K tomu zavedeme další proměnnou x 6 s koeficientem +1 na levou stranu prvního omezení nerovnosti. Proměnná x 6 je zahrnuta v účelové funkci s koeficientem nula (tj. není zahrnuta).

Dostaneme:

Najdeme výchozí referenční řešení. Abychom to udělali, srovnáme volné (nevyřešené) proměnné s nulou x1 = x2 = x3 = 0.

Dostaneme referenční roztok X1 = (0,0,0,24,30,6) s jednotkovou bází B1 = (A4, A5, A6).

Vypočítat odhady vektorového rozkladu podmínky na základě referenčního roztoku podle vzorce:

Δ k \u003d C b X k - c k

• C b = (с 1 , с 2 , ... , с m) je vektor koeficientů účelové funkce se základními proměnnými
• X k = (x 1k , x 2k , ... , x mk) je expanzní vektor odpovídajícího vektoru A k z hlediska báze referenčního řešení.
• C k - koeficient účelové funkce pro proměnnou x k.

Odhady vektorů zahrnutých do základu jsou vždy rovny nule. Referenční řešení, koeficienty expanzí a odhady expanzí stavových vektorů z hlediska báze referenčního řešení jsou zapsány v simplexní stůl:

Nad tabulkou jsou pro usnadnění výpočtu odhadů zapsány koeficienty účelové funkce. První sloupec "B" obsahuje vektory zahrnuté v základu referenčního roztoku. Pořadí zápisu těchto vektorů odpovídá počtu povolených neznámých v omezujících rovnicích. Ve druhém sloupci tabulky "S b" jsou zapsány koeficienty účelové funkce se základními proměnnými ve stejném pořadí. Při správném uspořádání koeficientů účelové funkce ve sloupci "C b" jsou odhady jednotkových vektorů zahrnutých do báze vždy rovny nule.

V posledním řádku tabulky s odhady Δ k ve sloupci "A 0" jsou hodnoty účelové funkce zapsány na referenčním řešení Z(X 1).

Počáteční referenční řešení není optimální, protože v úloze maxima jsou odhady Δ 1 = -2, Δ 3 = -9 pro vektory A 1 a A 3 záporné.

Podle věty o zlepšení referenčního řešení, pokud má alespoň jeden vektor v maximální úloze negativní odhad, pak je možné najít nové referenční řešení, na kterém bude hodnota účelové funkce větší.

Určeme, který z těchto dvou vektorů povede k většímu přírůstku účelové funkce.

Přírůstek účelové funkce se zjistí podle vzorce: .

Hodnoty parametru θ 01 pro první a třetí sloupec vypočítáme pomocí vzorce:

Dostaneme θ 01 = 6 pro l = 1, θ 03 = 3 pro l = 1 (tabulka 26.1).

Přírůstek účelové funkce najdeme, když se do báze zavede první vektor ΔZ 1 = - 6 * (- 2) = 12 a třetí vektor ΔZ 3 = - 3 * (- 9) = 27.

Pro rychlejší přiblížení se k optimálnímu řešení je tedy nutné zavést do báze referenčního řešení místo prvního vektoru báze A6 vektor A3, neboť minima parametru θ 03 je dosaženo v prvním řádku. (l = 1).

Jordanovu transformaci provedeme s prvkem X13 = 2, získáme druhé referenční řešení X2 = (0.0.3.21.42.0) se základem B2 = (A3, A4, A5). (tabulka 26.2)

Toto řešení není optimální, protože vektor A2 má negativní odhad Δ2 = - 6. Pro zlepšení řešení je nutné zavést vektor A2 do báze referenčního řešení.

Určíme číslo vektoru odvozené z báze. K tomu vypočítáme parametr θ 02 pro druhý sloupec, ten je roven 7 pro l = 2. Z báze tedy odvodíme druhý bázový vektor A4. Jordanovu transformaci provedeme prvkem x 22 = 3, získáme třetí referenční řešení X3 = (0.7.10.0.63.0) B2 = (A3, A2, A5) (tabulka 26.3).

Toto řešení je jediné optimální, protože pro všechny vektory, které nejsou zahrnuty v základu, jsou odhady kladné

Δ 1 \u003d 7/2, Δ 4 \u003d 2, Δ 6 \u003d 7/2.

Odpovědět: max Z(X) = 201 při X = (0,7, 10, 0,63).

Metoda lineárního programování v ekonomické analýze

Metoda lineárního programování umožňuje zdůvodnit nejoptimálnější ekonomické řešení při přísných omezeních souvisejících se zdroji používanými ve výrobě (fixní aktiva, materiály, pracovní zdroje). Aplikace této metody v ekonomické analýze nám umožňuje řešit problémy související zejména s plánováním činnosti organizace. Tato metoda pomáhá určit optimální hodnoty výstupu a také směry pro co nejefektivnější využití výrobních zdrojů, které má organizace k dispozici.

Pomocí této metody se provádí řešení tzv. extremálních problémů, které spočívá v nalezení extrémních hodnot, tedy maxima a minima funkcí proměnných.

Toto období je založeno na řešení soustavy lineárních rovnic v případech, kdy analyzované ekonomické jevy spojuje lineární, přísně funkční závislost. Metoda lineárního programování se používá k analýze proměnných za přítomnosti určitých omezujících faktorů.

Zcela běžné je řešení tzv. transportního problému metodou lineárního programování. Obsahem tohoto úkolu je minimalizace nákladů vzniklých v souvislosti s provozem vozidel za stávajících omezení týkajících se počtu vozidel, jejich nosnosti, délky jejich práce, pokud je potřeba obsloužit maximální počet zákazníků .

Kromě toho je tato metoda široce používána při řešení problému plánování. Tento úkol spočívá v takovém rozložení času fungování personálu této organizace, které by bylo nejpřijatelnější jak pro členy tohoto personálu, tak pro klienty organizace.

Cílem je maximalizovat počet obsluhovaných klientů a zároveň omezit počet dostupných zaměstnanců a pracovní dobu.

Metoda lineárního programování je tedy velmi běžná při analýze umístění a využití různých typů zdrojů, stejně jako v procesu plánování a prognózování činnosti organizací.

Přesto lze matematické programování aplikovat i na ty ekonomické jevy, jejichž vztah není lineární. K tomuto účelu lze využít metody nelineárního, dynamického a konvexního programování.

Nelineární programování se opírá o nelineární povahu cílové funkce nebo omezení nebo obojího. Formy cílových funkcí a omezujících nerovností za těchto podmínek mohou být různé.

Nelineární programování se využívá v ekonomické analýze zejména při stanovení vztahu mezi ukazateli vyjadřujícími efektivitu činnosti organizace a objemem této činnosti, strukturou výrobních nákladů, tržními podmínkami atd.

Dynamické programování je založeno na budování rozhodovacího stromu. Každá vrstva tohoto stromu slouží jako fáze pro stanovení důsledků předchozího rozhodnutí a pro eliminaci neefektivních variant tohoto rozhodnutí. Dynamické programování má tedy vícekrokový, vícestupňový charakter. Tento typ programování se používá v ekonomické analýze s cílem nalézt nejlepší možnosti rozvoje organizace jak nyní, tak i v budoucnu.

Konvexní programování je druh nelineárního programování. Tento typ programování vyjadřuje nelineární charakter vztahu mezi výsledky činnosti organizace a jí vynaloženými náklady. Konvexní (jinak konkávní) programování analyzuje konvexní účelové funkce a konvexní omezující systémy (vlastní body). Konvexní programování se používá při analýze ekonomické aktivity za účelem minimalizace nákladů a konkávní programování za účelem maximalizace příjmu v podmínkách existujících omezení působení faktorů, které ovlivňují analyzované ukazatele opačně. V důsledku toho jsou u uvažovaných typů programování konvexní objektivní funkce minimalizovány a konkávní maximalizovány.

Krok 0. Přípravná fáze.

Problém LP redukujeme na speciální formu (15).

Krok 1. Kompilace simplexní stůl odpovídající zvláštnímu formuláři:

Všimněte si, že tato tabulka odpovídá přípustnému základnímu řešení
problém (15). Hodnota účelové funkce na tomto řešení

Krok 2 Kontrola optimálnosti

Pokud mezi prvky řádku indexu simplex je tabulka
není tam žádný pozitivní prvek
, je nalezeno optimální řešení úlohy LP:. Algoritmus se ukončí.

Krok 3 Zkontrolujte neřešitelnost

Pokud mezi
existuje pozitivní prvek
a v odpovídajícím sloupci
není tam žádný pozitivní prvek
, pak účelová funkce L je zespodu neomezená na přípustné množině. V tomto případě neexistuje optimální řešení. Algoritmus se ukončí.

Krok 4 Výběr úvodního sloupce q

Mezi prvky
vyberte maximální pozitivní prvek
.Tento sloupec je deklarován jako hlavní (povolující).

Krok 5 Výběr hlavní čáry p

Mezi pozitivní prvky sloupu
najít prvek
, pro které je rovnost

.

tětiva p prohlásit vedení (povolující). Živel
prohlásit pána (povolující).

Krok 6 Simplexní transformace tabulky

Sestavujeme novou simplexní tabulku, ve které:

a) místo základní proměnné zapsat , místo nezákladní proměnné zapsat ;

b) je vedoucí prvek nahrazen recipročním
;

c) všechny prvky vedoucího sloupce (kromě
) vynásobte
;

d) všechny prvky vodicí čáry (kromě
) vynásobte ;

e) zbývající prvky simplexové tabulky jsou transformovány podle následujícího schématu "obdélník".

Od prvku se odečte součin tří faktorů:

první je odpovídající prvek vedoucího sloupce;

druhý je odpovídající prvek náběžné čáry;

třetí je reciproční prvek vedoucího
.

Transformovaný prvek a tři faktory jemu odpovídající jsou přesně vrcholy "obdélníku".

Krok 7 Přechod na další iteraci se provede návratem ke kroku 2.

2.3. Simplexní metoda Algoritmus pro problém maxima

Algoritmus simplexové metody pro maximální úlohu se liší od algoritmu pro minimální úlohu pouze znaménky indexové řady koeficientů v účelové funkci.
, jmenovitě:

V kroku 2:
:

V kroku 3
. Účelová funkce je shora neomezená na přípustné množině.

V kroku 4:
.

2.4. Příklad řešení úlohy simplexovou metodou

Vyřešte úlohu zapsanou ve formuláři (15).

Vytvoříme simplexní tabulku:

Protože koeficienty řádku účelové funkce jsou nezáporné, není počáteční základní řešení optimální. Hodnota účelové funkce pro tento základ L=0.

Vyberte úvodní sloupec - jedná se o sloupec odpovídající proměnné .

Vyberte úvodní čáru. K tomu najdeme
. Úvodní čára tedy odpovídá proměnné .

Transformaci simplexové tabulky provedeme zavedením proměnné na základ a výstup proměnné od základu. Dáme si tabulku:

Jedna iterace metody je dokončena. Pojďme k nové iteraci. Výsledná tabulka není optimální. Základní řešení odpovídající tabulce má tvar . Hodnota účelové funkce na tomto základě L= -2.

Vedoucím sloupcem je zde sloupec odpovídající proměnné . Úvodní čára - čára odpovídající proměnné . Po provedení transformací získáme simplexní tabulku:

Další iterace dokončena. Pojďme k nové iteraci.

Řádek účelové funkce neobsahuje kladné hodnoty, což znamená, že odpovídající základní řešení je optimální a algoritmus končí.

Je uvažován příklad řešení úlohy simplexovou metodou a také příklad řešení duální úlohy.

Úkol

Pro realizaci tří skupin zboží má obchodní podnik tři druhy omezených hmotných a peněžních zdrojů ve výši b 1 = 240, b 2 = 200, b 3 = 160 jednotek. Současně za prodej 1 skupiny zboží za 1 tisíc rublů. obrat, zdroj prvního typu je spotřebován ve výši a 11 = 2 jednotky, zdroj druhého typu ve výši a 21 = 4 jednotky, zdroj třetího typu ve výši 31 = 4 Jednotky. Pro prodej 2 a 3 skupin zboží za 1 tisíc rublů. obrat se vynakládá, resp. zdroj prvního typu ve výši a 12 = 3, a 13 = 6 jednotek, zdroj druhého typu ve výši a 22 = 2, a 23 = 4 jednotky, zdroj třetího typu v množství a 32 = 6, a 33 = 8 jednotek . Zisk z prodeje tří skupin zboží za 1 tisíc rublů. obrat je c 1 \u003d 4, c 2 \u003d 5, c 3 \u003d 4 (tisíc rublů). Stanovte plánovaný objem a strukturu obchodního obratu tak, aby byl maximalizován zisk obchodního podniku.

K přímému problému plánování oběhu zboží, řešitelná simplexová metoda, skládat duální problém lineární programování.
Nainstalujte konjugované páry proměnných přímé a duální problémy.
Podle konjugovaných dvojic proměnných, z řešení přímé úlohy, získat duální řešení problému, ve kterém odhad zdrojů vynaložené na prodej zboží.

Řešení simplexní úlohy metodou

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

0)))(~)" title="delim(lbrace)(matice(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Simplex řešíme metodou.

Zavádíme další proměnné x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, abychom převedli nerovnosti na rovnosti.

Jako základ bereme x 4 \u003d 240; x5 = 200; x6 = 160.

Data se zadávají simplexní stůl

Simplexní stůl číslo 1

Cílová funkce:

0 240 + 0 200 + 0 160 = 0

Skóre vypočítáme podle vzorce:

Δ 1 \u003d 0 2 + 0 4 + 0 4 - 4 \u003d - 4
Δ 2 \u003d 0 3 + 0 2 + 0 6 - 5 \u003d - 5
Δ 3 \u003d 0 6 + 0 4 + 0 8 - 4 \u003d - 4
Δ 4 \u003d 0 1 + 0 0 + 0 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 0 0 - 0 \u003d 0
Δ 6 \u003d 0 0 + 0 0 + 0 1 - 0 \u003d 0

Protože existují negativní odhady, plán není optimální. Nejnižší hodnocení:

Do základu zavedeme proměnnou x 2.

Definujeme proměnnou opouštějící základ. K tomu najdeme nejmenší nezáporný poměr pro sloupec x 2 .

= 26.667

Nejmenší nezáporné: Q 3 = 26,667. Proměnnou x 6 odvodíme ze základu

Rozdělte řádek 3 na 6.
Od prvního řádku odečtěte 3. řádek vynásobený 3
Od 2. řádku odečtěte 3. řádek vynásobený 2

Vypočítáme:

Dostáváme novou tabulku:

Simplexní stůl číslo 2

Cílová funkce:

0 160 + 0 440/3 + 5 80/3 = 400/3

Skóre vypočítáme podle vzorce:

Δ 1 \u003d 0 0 + 0 8/3 + 5 2/3 - 4 \u003d - 2/3
Δ 2 \u003d 0 0 + 0 0 + 5 1 - 5 \u003d 0
Δ 3 \u003d 0 2 + 0 4/3 + 5 4/3 - 4 \u003d 8/3
Δ 4 \u003d 0 1 + 0 0 + 5 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 5 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 \u003d 5/6

Protože existuje negativní odhad Δ 1 = - 2/3, plán není optimální.

Do základu zavedeme proměnnou x 1.

Definujeme proměnnou opouštějící základ. K tomu najdeme nejmenší nezáporný poměr pro sloupec x 1 .

Nejmenší nezáporné: Q 3 \u003d 40. Proměnnou x 2 odvodíme ze základu

Vydělte 3. řadu 2/3.
Od 2. řady odečtěte 3. řadu vynásobenou 8/3

Vypočítáme:

Dostáváme novou tabulku:

Simplexní stůl číslo 3

Cílová funkce:

0 160 + 0 40 + 4 40 = 160

Skóre vypočítáme podle vzorce:

Δ 1 \u003d 0 0 + 0 0 + 4 1 - 4 \u003d 0
Δ 2 \u003d 0 0 + 0 (-4) + 4 3/2 - 5 \u003d 1
Δ 3 \u003d 0 2 + 0 (-4) + 4 2 - 4 \u003d 4
Δ 4 \u003d 0 1 + 0 0 + 4 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 4 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 \u003d 1

Protože neexistují žádné negativní odhady, plán je optimální.

Řešení problému:

Odpovědět

To znamená, že je nutné prodat zboží prvního typu ve výši 40 tisíc rublů. Zboží 2. a 3. druhu není nutné prodávat. V tomto případě bude maximální zisk F max = 160 tisíc rublů.

Řešení duálního problému

Dvojitý problém vypadá takto:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->min

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Zavádíme další proměnné y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, abychom převedli nerovnosti na rovnosti.

Konjugované dvojice proměnných přímých a duálních problémů mají tvar:

Z poslední simplexové tabulky č. 3 přímé úlohy najdeme řešení duální úlohy:

Zmin = Fmax = 160;
y 1 \u003d Δ 4 \u003d 0; y 2 \u003d Δ 5 \u003d 0; y 3 \u003d Δ 6 \u003d 1; y 4 \u003d Δ 1 \u003d 0; y 5 \u003d Δ 2 \u003d 1; y 6 \u003d Δ 3 \u003d 4;

Zvážit simplexní metoda pro řešení úloh lineárního programování (LP). Je založen na přechodu z jednoho referenčního plánu do druhého, ve kterém se zvyšuje hodnota účelové funkce.

Algoritmus simplexové metody je následující:

1. Původní problém převedeme do kanonické podoby zavedením dalších proměnných. Pro nerovnost tvaru ≤ se další proměnné zavádějí 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 účelová funkce by neměla měnit svůj ekonomický význam.
2. Vydávají se vektory Pi 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í.
3. Poté jsou počáteční 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ých funkcí se zapisují s opačným znaménkem.
4. Kritérium optimality pro problém LP je, že řešení je optimální, pokud je v F– řádek všechny koeficienty jsou kladné. Pravidlo hledání sloupce oprávnění – Zobrazeno F je řetězec a mezi jeho negativními prvky je vybrán ten nejmenší. Vektor Pi 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 stane rozlišovacím prvkem, vzhledem k němuž bude simplexní tabulka přepočítána. Řetězec obsahující tento prvek se nazývá povolený řetězec. Pokud ve sloupci rozlišení nejsou žádné kladné prvky, problém nemá řešení. Po určení rozlišovacího prvku přistoupí k přepočtu nové simplexní tabulky.
5. Pravidla pro vyplňování nové simplexní tabulky. Místo rozlišovacího prvku je jeden položen a ostatní prvky jsou považovány 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ěny. Prvky permisivní linie jsou rozděleny permisivním prvkem a zbývající prvky jsou přepočítány podle pravidla obdélníků.
6. To se provádí až do F– všechny prvky řetězce se nestanou pozitivními.

Zvažte ř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:

:
Přepočítejte 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– řetězec obsahuje jeden záporný prvek – ​​(-5/3), vektory P1. Obsahuje ve svém sloupci jediný kladný prvek, který bude rozlišovacím prvkem. Přepočítejme tabulku s ohledem na tento prvek:

Absence negativních prvků v F- řetězec 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,
• Wentzel 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: Vyšší škola, 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