Příklad řešení simplexní metody online. Řešení úloh lineárního programování simplexovou metodou

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

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

Pro výrobu tří typů košil se používají nitě, knoflíky a látky. Zásoby nití, knoflíků a látek, jejich spotřeba na ušití jedné košile jsou uvedeny v tabulce. Najděte maximální zisk a optimální plán vydání produktu, který to zajišťuje (najděte ).

Ř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í.

Potom budou limity zdrojů vypadat takto:

Navíc podle smyslu úkolu

Cílová funkce vyjadřující obdržený zisk:

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

Redukce úlohy lineárního programování na kanonickou formu

Přenesme problém do kanonické podoby. Zavedeme další proměnné. Všechny další proměnné zavedeme do účelové funkce s koeficientem rovným nule. Do levých částí omezení přidáme další proměnné, které nemají preferovaný tvar, a dostaneme rovnosti.

Řešení úlohy simplexovou metodou

Vyplňte simplexní tabulku:

Protože problém řešíme pro maximum, přítomnost záporných čísel v indexovém řádku při řešení úlohy pro maximum naznačuje, že jsme neobdrželi optimální řešení a že je nutné přejít z tabulky 0. iterace na další.

Přechod na další iteraci se provádí následovně:

zápasy vedoucích sloupců

Klíčová řada je určena minimálními poměry volných členů a členů vedoucího sloupce (simplexní poměry):

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

Nyní začneme sestavovat 1. iteraci: Místo jednotkového vektoru zavedeme vektor .

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

Klíčový sloupec pro shodu 1. iterace

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.

V řádku indexu jsou všechny členy nezáporné, takže získáme následující řešení úlohy lineárního programování (vypíšeme 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ů v tomto předmětu můžete najít odesláním zprávy na VKontakte, na Viberu nebo vyplněním formuláře. Náklady na řešení domácí práce začíná od 7 BYN. za úkol (200 ruských rublů), ale ne méně než 10 běloruských rublů. (300 ruských rublů) za celou objednávku. Detailní provedení. Náklady na asistenci při online zkoušce (v tomto případě je vyžadována 100% platba předem) - od 30 BYR. (1000 ruských rublů) pro rozhodnutí o jízdence.

Příklad 5.1. Vyřešte následující problém lineárního programování pomocí simplexní metody:

Řešení:

já opakování:

x3, x4, x5, x6 x1,x2. Základní proměnné vyjadřujeme pomocí volných:

Objektivní funkci převedeme do následujícího tvaru:

Na základě získané úlohy vytvoříme počáteční simplexní tabulku:

Tabulka 5.3

Počáteční simplexní tabulka

Podle definice základního řešení se volné proměnné rovnají nule a hodnoty základních proměnných se rovnají odpovídajícím hodnotám volných čísel, tj.:

Fáze 3: kontrola kompatibility systému omezení LLP.

Při této iteraci (v tabulce 5.3) nebylo odhaleno znaménko nekonzistence omezovacího systému (funkce 1) (tj. neexistuje žádná čára se záporným volným číslem (s výjimkou čáry účelové funkce), která by neobsahovala alespoň jeden záporný prvek (tj. záporný koeficient pro volnou proměnnou)).

Při této iteraci (v tabulce 5.3) nebylo odhaleno znaménko neohraničenosti účelové funkce (znaménko 2) (tj. v řádku účelové funkce není žádný sloupec se záporným prvkem (kromě sloupce volných čísel) ve kterém by byl alespoň jeden kladný prvek) .

Protože nalezené základní řešení neobsahuje negativní složky, je přípustné.

Fáze 6: kontrola optimálnosti.

Nalezené základní řešení není optimální, protože podle kritéria optimality (znaménko 4) by v řádku účelové funkce neměly být žádné záporné prvky (volné číslo tohoto řádku se při uvažování tohoto znaménka nebere v úvahu ). Proto podle algoritmu simplexové metody přistoupíme k 8. etapě.

Protože nalezené základní řešení je přípustné, budeme hledat rozlišovací sloupec podle následujícího schématu: určíme sloupce se zápornými prvky v řádku účelové funkce (kromě sloupce volných čísel). Podle tabulky 5.3 existují dva takové sloupce: sloupec " x1"a sloupec" x2". Z takových sloupců se vybere ten, který obsahuje nejmenší prvek v řádku účelové funkce. Bude řešit. sloupec" x2' obsahuje nejmenší prvek (-3) ve srovnání se sloupcem ' x1

Pro určení permisivního řetězce najdeme kladné odhadované poměry volných čísel k prvkům permisivního sloupce, řetězec, který odpovídá nejmenšímu kladnému odhadovanému poměru, je považován za povolený.

Tabulka 5.4

Počáteční simplexní tabulka

V tabulce 5.4 nejmenší kladný poměr hodnocení odpovídá řádku " x5“, proto se to vyřeší.

Prvek umístěný na průsečíku povolovacího sloupce a povolovací čáry je akceptován jako povolovací. V našem příkladu se jedná o prvek, který se nachází na průsečíku čáry " x5» a sloupce « x2».

Rozlišovací prvek zobrazuje jednu základní a jednu volnou proměnnou, které je třeba prohodit v simplexní tabulce, aby bylo možné přejít na nové „vylepšené“ základní řešení. V tento případ to jsou proměnné x5 A x2, v nové simplexní tabulce (tabulka 5.5) je prohodíme.

9.1. Povolit transformaci prvku.

Permisivní prvek tabulky 5.4 je transformován následovně:

Získaný výsledek zapíšeme do podobné buňky v tabulce 5.5.

9.2. Povolit převod řetězce.

Prvky permisivního řádku tabulky 5.4 jsou rozděleny permisivním prvkem této simplexové tabulky, výsledky se vejdou do podobných buněk nové simplexové tabulky (tabulka 5.5). Transformace prvků povolovacího řetězce jsou uvedeny v tabulce 5.5.

9.3. Permisivní transformace sloupců.

Prvky rozlišovacího sloupce tabulky 5.4 jsou rozděleny rozlišovacím prvkem této simplexní tabulky a výsledek se bere s opačným znaménkem. Získané výsledky zapadají do podobných buněk nové simplexové tabulky (tabulky 5.5). Transformace prvků rozlišovací kolony jsou uvedeny v tabulce 5.5.

9.4. Transformace zbývajících prvků simplexové tabulky.

Transformace ostatních prvků simplexní tabulky (tj. prvků nenacházejících se v rozlišovacím řádku a rozlišovacím sloupci) se provádí podle pravidla "obdélník".

Zvažte například transformaci prvku umístěného na průsečíku řetězce " x3“ a sloupce „“, podmíněně jej označují jako „ x3". V tabulce 5.4 mentálně nakreslíme obdélník, jehož jeden vrchol se nachází v buňce, jejíž hodnota se transformuje (tj. v buňce " x3“) a druhý (diagonální vrchol) je v buňce s rozlišovacím prvkem. Další dva vrcholy (druhé diagonály) jsou jednoznačně určeny. Potom transformovaná hodnota buňky " x3"se bude rovnat předchozí hodnotě této buňky mínus zlomek, v jehož jmenovateli je rozlišovací prvek (z tabulky 5.4), a v čitateli součin dvou dalších nepoužitých vrcholů, tj.:

« x3»: .

Hodnoty ostatních buněk se převedou podobně:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

V důsledku těchto transformací byla získána nová simplexní tabulka (tabulka 5.5).

II opakování:

Fáze 1: sestavení simplexní tabulky.

Tabulka 5.5

Simplexní stůlII iterací

Fáze 2: stanovení základního řešení.

V důsledku simplexních transformací bylo získáno nové základní řešení (tabulka 5.5):

Jak vidíte, u tohoto základního řešení je hodnota účelové funkce =15, což je více než u předchozího základního řešení.

Nejednotnost systému omezení podle znaku 1 v tabulce 5.5 nebyla zjištěna.

Fáze 4: kontrola ohraničenosti účelové funkce.

Neohraničenost účelové funkce podle znaménka 2 v tabulce 5.5 nebyla odhalena.

5. etapa: kontrola přípustnosti nalezeného základního řešení.

Nalezené základní řešení podle znaku 4 není optimální, protože řádek účelové funkce simplexové tabulky (tabulka 5.5) obsahuje záporný prvek: -2 (volné číslo tohoto řádku se při uvažování nebere v úvahu Vlastnosti). Pojďme tedy ke kroku 8.

Fáze 8: definice aktivačního prvku.

8.1. Definice sloupce rozlišení.

Nalezené základní řešení je přípustné, v řádku účelové funkce určíme sloupce se zápornými prvky (kromě sloupce volných čísel). Podle tabulky 5.5 existuje pouze jeden takový sloupec: " x1". Proto to přijímáme jako povolené.

8.2. Definice permisivního řetězce.

Podle získaných hodnot kladných odhadovaných poměrů v tabulce 5.6 je minimem poměr odpovídající řádku " x3". Proto to přijímáme jako povolené.

Tabulka 5.6

Simplexní stůlII iterací

Fáze 9: transformace simplexové tabulky.

Transformace simplexové tabulky (tabulka 5.6) se provádějí stejným způsobem jako v předchozí iteraci. Výsledky transformací prvků simplexové tabulky jsou uvedeny v tabulce 5.7.

III opakování

Na základě výsledků simplexních transformací předchozí iterace sestavíme novou simplexní tabulku:

Tabulka 5.7

Simplexní stůlIII iterací

Fáze 2: stanovení základního řešení.

V důsledku simplexních transformací bylo získáno nové základní řešení (tabulka 5.7):

Fáze 3: kontrola slučitelnosti systému omezení.

Nejednotnost systému omezení podle znaku 1 v tabulce 5.7 nebyla zjištěna.

Fáze 4: kontrola ohraničenosti účelové funkce.

Neohraničenost účelové funkce podle znaménka 2 v tabulce 5.7 nebyla odhalena.

5. etapa: kontrola přípustnosti nalezeného základního řešení.

Nalezené základní řešení podle kritéria 3 je přípustné, protože neobsahuje negativní složky.

6. fáze: kontrola optimálnosti nalezeného základního řešení.

Nalezené základní řešení podle znaku 4 není optimální, protože řádek účelové funkce simplexové tabulky (tabulka 5.7) obsahuje záporný prvek: -3 (volné číslo tohoto řádku se při uvažování nebere v úvahu Vlastnosti). Pojďme tedy ke kroku 8.

Fáze 8: definice aktivačního prvku.

8.1. Definice sloupce rozlišení.

Nalezené základní řešení je přípustné, v řádku účelové funkce určíme sloupce se zápornými prvky (kromě sloupce volných čísel). Podle tabulky 5.7 existuje pouze jeden takový sloupec: " x5". Proto to přijímáme jako povolené.

8.2. Definice permisivního řetězce.

Podle získaných hodnot kladných odhadovaných poměrů v tabulce 5.8 je minimem poměr odpovídající řádku " x4". Proto to přijímáme jako povolené.

Tabulka 5.8

Simplexní stůlIII iterací

Fáze 9: transformace simplexové tabulky.

Transformace simplexní tabulky (tabulka 5.8) se provádějí stejným způsobem jako v předchozí iteraci. Výsledky transformací prvků simplexové tabulky jsou uvedeny v tabulce 5.9.

IV opakování

Fáze 1: stavba nového simplexního stolu.

Na základě výsledků simplexních transformací předchozí iterace sestavíme novou simplexní tabulku:

Tabulka 5.9

Simplexní stůlIV iterací

Fáze 2: stanovení základního řešení.

V důsledku simplexních transformací bylo získáno nové základní řešení, podle tabulky 5.9, řešení je následující:

Fáze 3: kontrola slučitelnosti systému omezení.

Nejednotnost systému omezení podle znaku 1 v tabulce 5.9 nebyla odhalena.

Fáze 4: kontrola ohraničenosti účelové funkce.

Neohraničenost účelové funkce podle znaménka 2 v tabulce 5.9 nebyla odhalena.

5. etapa: kontrola přípustnosti nalezeného základního řešení.

Nalezené základní řešení podle kritéria 3 je přípustné, protože neobsahuje negativní složky.

6. fáze: kontrola optimálnosti nalezeného základního řešení.

Základní řešení nalezené podle znaku 4 je optimální, protože v řádku účelové funkce simplexní tabulky (tabulka 5.9) nejsou žádné záporné prvky (volné číslo tohoto řádku se při posuzování tohoto znaku nebere v úvahu) .

Fáze 7: kontrola alternativního řešení.

Nalezené řešení je jediné, protože v řádku účelové funkce (tabulka 5.9) nejsou žádné nulové prvky (volné číslo tohoto řádku se při zvažování této vlastnosti nebere v úvahu).

Odpovědět: optimální hodnota účelové funkce uvažovaného problému =24, které je dosaženo při.

Příklad 5.2. Vyřešte výše uvedený problém lineárního programování za předpokladu, že účelová funkce je minimalizována:

Řešení:

já opakování:

Fáze 1: vytvoření počáteční simplexní tabulky.

Původní úloha lineárního programování je uvedena ve standardní formě. Uveďme to do kanonické podoby zavedením další nezáporné proměnné do každého z omezení nerovnosti, tzn.

Ve výsledné soustavě rovnic bereme jako povolené (základní) proměnné x3, x4, x5, x6, pak jsou volné proměnné x1,x2. Základní proměnné vyjadřujeme pomocí volných.

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 v posledním řádku máme opět 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

Pokud potřebujete vyřešit problém lineárního programování pomocí simplexních tabulek, pak naše služba online bude vám velkou pomocí. Simplexová metoda znamená sekvenční výčet 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 zlepšuje v každém následujícím kroku. Takové řešení se nazývá základní. Zde je sekvence 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 obsahuje negativní prvky, pak je nutné přistoupit ke druhému kroku, pokud ne, tak k pátému.

Druhý krok. Ve druhém kroku je nutné rozhodnout, kterou proměnnou vyjmout ze základu a kterou zahrnout, abychom mohli přepočítat simplexovou tabulku. K tomu se podíváme na sloupec s volnými členy a najdeme v něm záporný prvek. Řádek se záporným prvkem se bude nazývat vedoucí. V něm najdeme maximální záporný prvek v absolutní hodnotě, jemu odpovídající sloupec je následovník. Pokud jsou mezi volnými členy 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, která je ve sloupci volných členů, je vyloučena ze základu a proměnná odpovídající úvodnímu sloupci je zahrnuta do základu.

Stůl 1.

Třetí krok. Ve třetím kroku přepočítáme celou simplexovou tabulku pomocí speciálních vzorců, tyto vzorce lze zobrazit pomocí .

Čtvrtý krok. Pokud po přepočtu zůstanou ve sloupci volných členů záporné prvky, přejděte k prvnímu kroku, pokud žádné nejsou, přejděte 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 řadě F kladné. Pokud tomu tak není, je nutné řešení vylepšit, u kterého najdeme úvodní řádek a sloupec pro další přepočet podle následujícího algoritmu. Nejprve najdeme minimální záporné číslo v řádku F, vyjma 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 vedoucího sloupce, pokud jsou kladné. Minimální poměr určí vedoucí čáru. Tabulku přepočítáme podle vzorců, tzn. přejděte ke kroku 3.