Simplexová metoda je jednoduchý příklad řešení. Simplexní metoda, příklady řešení problémů

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

Ú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;

Myšlenkou simplexové metody je přejít z jedné báze na druhou a získat funkční hodnotu, která není alespoň menší než ta stávající (každá báze odpovídá jedné funkční hodnotě).
Je zřejmé, že počet možných základen pro jakýkoli problém je konečný (a nepříliš velký).
Proto se dříve nebo později odpověď dočká.

Jak probíhá přechod z jednoho základu na druhý?
Výhodnější je zaznamenat řešení ve formě tabulek. Každý řádek je ekvivalentní rovnici systému. Vybraný řádek se skládá z koeficientů funkce (porovnejte sami). To vám umožní nepřepisovat proměnné pokaždé, což ušetří spoustu času.
Ve vybraném řádku vyberte největší kladný koeficient. To je nezbytné pro získání hodnoty funkce, alespoň ne menší než ta stávající.
Vybrán sloupec.
Pro kladné koeficienty zvoleného sloupce spočítáme poměr Θ a zvolíme nejmenší hodnotu. To je nutné, aby po transformaci zůstal sloupec volných členů kladný.
Vybrán řádek.
Proto je definován prvek, který bude základem. Dále počítáme.

Jedna z metod řešení optimalizačních problémů ( obvykle spojené s nalezením minima nebo maxima) lineárního 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í počáteční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ý poskytuje maximální zisk.

Počáteční data úlohy pro simplexovou metodu

Podnik vyrábí 4 druhy výrobků, zpracovává je na 3 strojích.

Časové limity (min./ks) pro zpracování výrobků na strojích jsou dány maticí A:

Fond doby chodu stroje (min.) je uveden v matici B:

Zisk z prodeje každé jednotky produktu (rublů/kus) je dán maticí C:

Účel výrobního úkolu

Vypracujte plán výroby, ve kterém bude maximalizován 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:

To znamená, že zisk z realizace plánu výroby by měl být maximální.

(4) Abychom vyřešili výsledný problém pro podmíněný extrém, nahradíme systém nerovností systémem lineární rovnice vložením dalších nezáporných proměnných do něj ( X5, X6, X7).

(5) Přijímá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 si v poslední řádek největší (modulo) záporné číslo.

Vypočítat b = N / Elements_of_chosen_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í povolujícímu prvku ( X5 až X1).

• Samotný prvek povolení se stane 1.
• Pro prvky permisivní linie - a ij (*) = a ij / RE ( to znamená, že každý prvek vydělíme hodnotou aktivačního prvku a získáme nová data).
• U prvků rozlišovacího sloupce se jednoduše vynulují.
• Zbývající prvky tabulky se přepočítají podle 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 prvkem enable. Tvoří protilehlé rohy obdélníku. Dále vynásobíme hodnoty z buněk 2 dalších rohů tohoto obdélníku. Tato práce ( A * B) vydělte rozlišovacím prvkem ( RE). A odečíst od aktuální přepočítané buňky ( aij) co se stalo. Dostáváme novou hodnotu - a ij (*).

(9) Znovu zkontrolujte poslední řádek ( C) na přítomnost záporných čísel. Pokud žádné nejsou, byl nalezen optimální plán, postupujeme 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 máme opět v posledním řádku záporná čísla, zahájíme 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! Totiž: 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 produkce výrobků 1 a 2 se ziskem na 1 kus, dostaneme konečný ( maximum! ) zisk podle daného plánu výroby.

ODPOVĚDĚT:

X1=32ks, X2=20ks, X3=0ks, X4=0ks

P \u003d 48 * 32 + 33 * 20 \u003d 2 196 rublů.

Galyautdinov R.R.

© Kopírování materiálu je povoleno pouze v případě, že zadáte přímý hypertextový odkaz na

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.

Pro toto v levá strana V prvním omezení nerovnosti zavedeme další proměnnou x 6 s koeficientem +1. 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í. Na správné umístění koeficienty účelové funkce ve sloupci "C b" odhady jednotkových vektorů zahrnutých v bázi, vždy rovné 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 jsou analyzované ekonomické jevy spojeny 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ě, tato metoda nachází široké uplatnění 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 použití různé druhy zdrojů, jakož i v procesu plánování a prognózování činnosti organizací.

Dosud matematického programování lze aplikovat i na ty ekonomické jevy, mezi nimiž 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 k nalezení nejlepší možnosti organizace, nyní 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.

Přednáška 3 Simplexní stoly. Algoritmus simplexové metody.

§ 3 JEDNODUCHÁ METODA

3.1. Obecná myšlenka simplexové metody. Geometrická interpretace

Grafická metoda je použitelná pro velmi úzkou třídu problémů lineárního programování: dokáže efektivně řešit problémy obsahující ne více než dvě proměnné. Byly uvažovány hlavní věty lineárního programování, z nichž vyplývá, že má-li úloha lineárního programování optimální řešení, pak odpovídá alespoň jednomu rohovému bodu mnohostěnu řešení a shoduje se s alespoň jedním z přípustných základních řešení řešení. omezovací systém. Byl naznačen způsob, jak vyřešit jakýkoli problém lineárního programování: vyjmenovat konečný počet proveditelných základních řešení systému omezení a vybrat z nich to, o kterém cílová funkce činí optimální rozhodnutí. Geometricky to odpovídá výčtu všech rohových bodů polyedru řešení. Takový výčet nakonec povede k optimálnímu řešení (pokud existuje), ale jeho praktická realizace je spojena s obrovskými obtížemi, protože pro skutečné problémy může být počet proveditelných základních řešení, byť konečných, extrémně velký.

Počet přípustných základních řešení k výčtu lze snížit, pokud výčet není proveden náhodně, ale s přihlédnutím ke změnám lineární funkce, tzn. snažit se zajistit, aby každé další řešení bylo „lepší“ (nebo alespoň „ne horší“) než to předchozí z hlediska hodnot lineární funkce (při hledání maxima je zvyšujte, při hledání minima snižujte
). Takový výčet umožňuje snížit počet kroků při hledání optima. Pojďme si to vysvětlit na grafickém příkladu.

Nechť oblast proveditelných řešení představuje mnohoúhelník ABCDE. Předpokládejme jeho rohový bod A odpovídá původnímu přípustnému základnímu řešení. Náhodný výčet by musel vyzkoušet pět proveditelných základních řešení odpovídajících pěti rohovým bodům polygonu. Kresba však ukazuje, že po vrchol A výhodné jít na další vrchol V, a pak do optimálního bodu S. Místo pěti byly procházeny pouze tři vrcholy, což konzistentně zlepšovalo lineární funkci.

Myšlenka postupného zlepšování řešení tvořila základ univerzální metody pro řešení problémů lineárního programování - simplexová metoda nebo metoda postupného zlepšování plánu.

Geometrický význam simplexové metody spočívá v sekvenčním přechodu z jednoho vrcholu omezujícího mnohostěnu (tzv. počátečního) do sousedního, ve kterém lineární funkce nabývá nejlepší (alespoň ne nejhorší) hodnotu ve vztahu k cíl problému; dokud není nalezeno optimální řešení - vrchol, kde je dosaženo optimální hodnoty cílové funkce (pokud má úloha konečné optimum).

Simplexovou metodu poprvé navrhl americký vědec J. Danzig v roce 1949, ale již v roce 1939 myšlenky metody rozvinul ruský vědec L.V. Kantorovič.

Simplexní metoda, který umožňuje řešit jakýkoli problém lineárního programování, je univerzální. V současnosti se používá pro počítačové výpočty, ale jednoduché příklady pomocí simplexové metody lze řešit i ručně.

Pro implementaci simplexové metody - postupného zlepšování řešení - je nutné zvládnout tři hlavní prvky:

metoda pro stanovení nějakého počátečního proveditelného základního řešení problému;

pravidlo přechodu k nejlepšímu (přesněji ne nejhoršímu) řešení;

kritérium pro kontrolu optimálnosti nalezeného řešení.

Pro použití simplexové metody je třeba problém lineárního programování zredukovat na kanonickou formu, tzn. systém omezení musí být prezentován ve formě rovnic.

Literatura dostatečně podrobně popisuje: nalezení výchozího referenčního plánu (počáteční proveditelné základní řešení), také pomocí metody umělé báze, nalezení optimálního referenčního plánu, řešení úloh pomocí simplexních tabulek.

3.2. Algoritmus simplexové metody.

Uvažujme řešení LLP simplexovou metodou a uveďme jej ve vztahu k maximalizačnímu problému.

1. Podle stavu úlohy se sestaví její matematický model.

2. Vytvořený model se převede na kanonická forma. V tomto případě může vyniknout základ s počátečním referenčním plánem.

3. Kanonický model úlohy je zapsán ve formě simplexní tabulky tak, aby všechny volné členy byly nezáporné. Pokud je vybrán počáteční referenční plán, přejděte ke kroku 5.

Simplexní tabulka: systém omezujících rovnic zapadá do a Objektivní funkce ve formě výrazů povolených vzhledem k výchozímu základu. Řádek, do kterého se zadávají koeficienty účelové funkce
, volal
–řetězec nebo řetězec objektivní funkce.

4. Najděte počáteční plán podpory provedením simplexních transformací s pozitivními rozlišovacími prvky odpovídajícími minimálním simplexním poměrům a bez zohlednění znamének prvků
– struny. Je-li v průběhu transformací nulový řádek, jehož všechny prvky kromě volného členu jsou nulové, pak je soustava omezujících rovnic úlohy nekonzistentní. Pokud je naopak nulová řada, ve které kromě volného členu nejsou žádné další kladné prvky, pak systém omezujících rovnic nemá nezáporná řešení.

Bude vyvolána redukce systému (2.55), (2.56) na nový základ simplexní transformace . Pokud je simplexová transformace považována za formální algebraickou operaci, pak lze vidět, že v důsledku této operace jsou role přerozděleny mezi dvě proměnné zahrnuté v nějakém systému lineární funkce: jedna proměnná přechází ze závislé na nezávislou a druhá naopak - z nezávislé na závislou. Tato operace je v algebře známá jako Krok eliminace Jordan.

5. Nalezený výchozí základní plán je zkoumán z hlediska optimálnosti:

a) pokud v
-line nemá žádné negativní prvky (kromě volného termínu), pak je plán optimální. Pokud nejsou žádné nuly, pak je optimální plán jedinečný; pokud existuje alespoň jedna nula, pak existuje nekonečný počet optimálních plánů;

b) pokud
– řádek má tedy alespoň jeden záporný prvek, který odpovídá sloupci nekladných prvků
;

c) pokud v
-řádek má alespoň jeden záporný prvek a jeho sloupec má alespoň jeden kladný prvek, pak můžete přejít na nový referenční plán, který je blíže optimálnímu. K tomu musí být určený sloupec přiřazen jako rozlišovací, minimálním simplexním poměrem, najít rozlišovací řádek a provést simplexní transformaci. Získaný základní plán je znovu posouzen z hlediska optimálnosti. Popsaný proces se opakuje, dokud není získán optimální plán nebo dokud není problém neřešitelný.

Sloupec koeficientů pro proměnnou zahrnutou do základu se nazývá rozlišení. Tedy výběr proměnné zavedené do báze (nebo výběr rozlišovacího sloupce) záporným prvkem
–řetězce, zajistíme zvýšení funkce
.

Trochu obtížnější je určit proměnnou, která má být vyloučena ze základu. K tomu sestaví poměry volných členů ke kladným prvkům rozlišovacího sloupce (takové vztahy se nazývají simplexní) a najdou z nich nejmenší, který určuje řádek (rozlišovací) obsahující vyloučenou proměnnou. Volba proměnné, která má být vyloučena z báze (nebo volba rozlišovacího řetězce) podle minimálního simplexního poměru zaručuje, jak již bylo stanoveno, pozitivitu základních složek v novém referenčním návrhu.

V kroku 3 algoritmu se předpokládá, že všechny prvky sloupce volných členů jsou nezáporné. Tento požadavek není povinný, ale pokud je splněn, pak se všechny následné simplexní transformace provádějí pouze s prvky s kladným rozlišením, což je výhodné pro výpočty. Pokud jsou ve sloupci volných členů záporná čísla, pak se rozlišovací prvek zvolí takto:

1) naskenujte řetězec odpovídající například nějakému negativnímu volnému členu –řádek a vyberte v něm nějaký záporný prvek a odpovídající sloupec se považuje za rozlišovací (předpokládáme, že omezení problému jsou kompatibilní);

2) sestavit poměry prvků sloupce volných členů k odpovídajícím prvkům rozlišovacího sloupce, které mají stejná znaménka (simplexní poměry);

3) vyberte nejmenší z simplexních vztahů. Určí řetězec oprávnění. Ať je to např. R-čára;

4) v průsečíku rozlišovacích sloupců a řádků je nalezen rozlišovací prvek. Pokud je prvek povolen –řetězec, pak se po simplexní transformaci volný člen tohoto řetězce stane kladným. V opačném případě se v dalším kroku opět obracíme na -tětiva. Pokud je problém řešitelný, pak po určitém počtu kroků nebudou ve sloupci volných termínů žádné záporné prvky.

Pokud je nějaká reálná produkční situace oděna do formy LLP, pak další proměnné, které je třeba do modelu zavést v procesu jeho převodu na kanonickou formu, mají vždy určitý ekonomický význam.