Kapitola 14

Lineární programování

Vraťme se k problému sestavení ideální štafety. V něm jsme měli úplný bipartitní graf, každou hranu ohodnocenou nějakým reálným číslem a hledali jsme perfektní párování s co nejmenším součtem hodnot hran. Tento problém můžeme obecně formulovat následovně.

Je dán úplný bipartitní graf G = (V, E), to znamená, že V = L ˙∪R je disjuntkní sjednocení dvou množin téže mohutnosti n a množina n^{2} neorientovaných hran E = {{v, w} : v ∈ L, w ∈ R}. Dále je dána funkce ω : E → R. Hodnotu ω(e) budeme zapisovat také jako ω_{e}. Minimální perfektní párování v grafu G je nějaká množina n hran M taková, že

• žádné dvě hrany M neobsahují společný vrchol,

• součet ∑_{e∈M} ω_{e} je minimální.

Tuto úlohu přeformulujeme pomocí charakteristických vektorů. Každou podmnožinu F ⊆ E můžme popsat pomocí reálného vektoru x_{F} = (x_{e})_{e∈E} dimenze n^{2} se všemi souřadnicemi x_{e} ∈ {0, 1}, pro které platí

x_{e} = 1 právě když e ∈ F.

Množina F ⊆ E je perfektní párování v grafu G právě když pro vektor x_{F} = (x_{e})_{e∈E} platí

∑_{v∈e} x_{e} = 1 pro každý vrchol v ∈ V.

Jinak řečeno, každý vrchol v ∈ V je obsažen v právě jedné hraně e ∈ F. Součet hodnot hran v množině F se rovná

∑_{e∈E} ω_{e}x_{e}.

Úlohu nalezení perfektního párování s minimálním součtem hodnot tak může být formulován následovně jako úloha na nalezení n^{2} reálných čísel x_{e} splňujících podmínky součet

• součet ∑_{e∈E} ω_{e}x_{e} je minimální,

• ∑_{v∈e} x_{e} = 1 pro každý vrchol v ∈ V,

• x_{e} ∈ {0, 1} pro každou hranu e ∈ E.

Lineární funkce ∑_{e∈E} ω_{e}x_{e} se nazývá účelová funkce, dalším podmínkám říkáme omezující podmínky nebo jenom omezení. Protože omezující podmínky říkají, že každá proměnná x_{e} musí nabývat celočíselných hodnot, říkáme že jde o úlohu celočíselného lineárního programování.

Tímto přeformulováním získáme dolní odhad pro naši úlohu. Získáme jej tak, že oslabíme třetí podmínku x_{e} ∈ {0, 1} pro každou hranu e ∈ E na 0 ≤ x_{e} ≤ 1 pro každou hranu e ∈ E. Dostaneme tak úlohu lineárního programování

• součet ∑_{e∈E} ω_{e}x_{e} je minimální,

• ∑_{v∈e} x_{e} = 1 pro každý vrchol v ∈ V,

• 0 ≤ x_{e} ≤ 1 pro každou hranu e ∈ E.

Protože každý vektor (x_{e})_{e∈E} splňující omezení úlohy celočíselného lineárního programování rovněž splňuje všechny podmínky příslušné úlohy lineárního programování, platí, že minimální hodnota účelové funkce u úlohy lineárního programování je menší nebo rovná minimální hodnotě vytvořující funkce odpovídající úlohy celočíselného lineárního programování.

Věta 14.1 Pro úlohu nalezení minimálního perfektního paárování v bipartitním grafu G = (V, E) existuje optimální řešení (x_{e})_{e∈E} příslušné úlohy lineárního programování, jehož všechny souřadnice x_{e} jsou celočíselné.

Důkaz. Na přednášce. □

Předcházející tvrzení je spíš výjimečné. V naprosté většině případů je optimální řešení úlohy celočíselného lineárního programování různé od optimálního řešení odpovídající úlohy lineárního programování.

Úloha 14.1 Nalezení maximální nezávislé množiny vrcholů v neorientovaném grafu.

Řešení. Na přednášce. □

Simplexová metoda

Lineární programování (LP) ve své nejobecnější podobě je úloha jak maximalizovat nějakou lineární funkci v n proměnných x_{1}, …, x_{n}, které musí splňovat m lineárních nerovností. Pokud navíc požadujeme, aby x_{i} ≥ 0, říkáme, že úloha LP je ve standardním tvaru. Ten můžeme zapsat následovně:

• maximalizujte funkci ∑_{j=1}^{n} c_{j}x_{j}

• za předpokladů ∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{j} pro i = 1, 2, …, m

• a dále x_{j} ≥ 0 pro j = 1, 2, …, n,

kde c_{j}, b_{i} a a_{ij} jsou reálná čísla.

Označíme-li

x = (x_{1}, …, x_{n})^{T} ,
c = (c_{1}, …, c_{n})^{T} ,
b = (b_{1}, …, b_{m})^{T} ,

A = ( \begin{matrix}a_{11} & a_{12} & ⋯ & a_{1n} \\ a_{21} & a_{22} & ⋯ & a_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{m1} & a_{m2} & ⋯ & a_{mn} \end{matrix} ) ,

můžeme úlohu lineárního programování zapsat kompaktněji v podobě

• maximalizujte funkci c^{T} x

• vzhledem k omezením Ax ≤ b

• a x ≥ 0.

Nerovnost x ≤ y mezi dvěma vektory téže délky platí právě když platí pro každou souřadnici obou vektorů.

Vektor c se nazývá cenový vektor, funkce x ↦ c^{T} x se nazývá účelová funkce, nerovnosti Ax ≤ b a x ≥ 0 se nazývají omezující podmínky nebo také omezení. Vektor b se nazývá pravá strana úlohy. Úloha LP se nazývá přípustná, pokud existuje nezáporný vektor x vyhovující omezujícím podmínkám Ax ≤ b. Takovému vektoru x pak říkáme přípustné řešení. Pokud žádné přípustné řešení úlohy LP neexistuje, pak říkáme, že taková úloha je nepřípustná. Úloha je neomezená, pokud existuji přípustná řešení, pro která účelová funkce nabývá libovolně velkých hodnot. V opačném případě se nazývá omezená. Pro úlohu LP, která je současně přípustná a omezená, existuje jednoznačně určené maximum účelové funkce c_{T} x. Ta jej dosahuje v nějakém vektoru x, kterému říkáme optimální řešení. Optimální řešení nemusí být určené jednoznačně.

Tabulky

Zavedení nových proměnných

x_{n+i} = b_{i} − ∑_{j=1}^{n}a_{ij}x_{j}

spolu s omezeními x_{n+i} ≥ 0 pro i = 1, …, m.

Původní úlohu LP upravíme tímto do tvaru

• maximalizujte funkci ∑_{j=1}^{n} c_{j}x_{j}

• vzhledem k omezením x_{n+i} = b_{i} − ∑_{j=1}^{n} a_{ij}x_{j} pro i = 1, …, m

• a dále x_{j} ≥ 0 pro j = 1, 2, …, m + n.

V kompaktním tvaru tutéž úlohu zapíšeme ve tvaru

• maximalizujte funkci d^{T} x

• vzhledem k omezením Bx = b

• a dále x ≥ 0.

Zde platí

B = (A|I_{m}),

dále d je vektor dimenze n + m tvaru (c|0)^{T} a x je sloupcový vektor m + n neznámých

x = (x_{O}|x_{S})^{T} ,

kde x_{O} = (x_{1}, …, x_{n}) a x_{S} = (x_{n+1} , …, x_{n+m} ).

Vyjádření nových proměnných x_{n+i} = b_{i} − ∑_{j=1}^{n} a_{ij}x_{j} pro i = 1, …, m spolu s účelovou funkcí obsahuje všechny informace o úloze. Tradičně se tyto informace zapisují do tabulky.

Úloha 14.2 Maximalizujte funkci x_{1}+x_{2} vzhledem k omezením −x_{1}+x_{2} ≤ 1, x_{1} ≤ 3, x_{2} ≤ 2, x_{1}, x_{2} ≥ 0.

Řešení. Úvodní tabulka k této úloze je

x_{3} = 1 + x_{1} − x_{2}
x_{4} = 3 − x_{1}
x_{5} = 1  − x_{2}
z =  x_{1} + x_{2}

Položíme-li proměnné na pravých stranách rovné 0, hodnoty proměnných na levé straně nabývají hodnot x_{3} = 1, x_{4} = 3, x_{5} = 2. Vektor (0, 0, 1, 3, 2) je proto přípustné řešení. Tomuto řešení říkáme základní přípustné řešení a jeho tabulka je přípustná tabulka. Účelová funkce z nabývá hodnoty z = 0. Proměnným na levé straně říkáme bázové proměnné, proměnné na pravé straně jsou nebázové proměnné.

Nyní budeme postupně tabulku upravovat tak, abychom dostali nové baázové přípustné řešení s vyšší hodnotou účelové funkce z nebo abychom dokázali, že neexistuje žádné přípustné řešení s vyšší hodnotou z.

V první tabulce si všimneme, že zvětšení hodnoty x_{1} nebo x_{2} zvýší hodnotu účelové funkce z. Obě proměnné mají kladné znaménko ve formulce pro účelovou funkci. Jak moc ale můžeme zvětšit např. x_{2} ? Chceme-li zachovat přípustnost řešení, můžeme kvůli první rovnici zvětšit x_{2} nejvýše na hodnotu 1. Druhá rovnice nijak hodnotu x_{2} neomezuje. Třetí rovnice omezuje x_{2} nejvýše na hodnotu 2. Největší omezení tak pochází z první rovnice. Z ní tedy vypočítáme hodnotu

x_{2} = 1 + x_{1} − x_{3}

a dosadíme ji do ostatních rovnic a do účelové funkce. Dostaneme tak následující tabulku

x_{2} = 1 + x_{1} − x_{3}
x_{4} = 3 − x_{1}
x_{5} = 1 − x_{1} + x_{3}
z = 1 + 2x_{1} − x_{3}

Je zřejmé, že oba systémy rovnic mají stejné množiny řešení. Původně nebázová proměnná x_{2} byla přesunuta do báze, ze které naopak byla odsunuta proměnná x_{3}. Položíme-li opět hodnoty nebázových proměnných x_{1}, x_{3} rovné nule, dostaneme x_{2} = 1, x_{4} = 3, x_{5} = 2. Dostáváme tak nové bázové přípustné řešení (0, 1, 0, 3, 1) a účelová funkce z nyní nabývá hodnoty z = 1.

V nové tabulce můžeme stále ještě zvýšit hodnotu x_{1}. Z první rovnice žádné omezení pro hodnotu x_{1} nevyplývá, z druhé rovnice dostáváme x_{1} ≤ 3 a ze tgřetí rovnice vyplývá omezení x_{1} ≤ 1. Největší omezení tak vyplývá ze třetí rovnice, ze které vyjádříme x_{1} a dosadíme je do zbývajících rovnic. Dostaneme tak další tabulku

x_{2} = 2  − x_{5}
x_{4} = 2 − x_{3} + x_{5}
x_{1} = 1 + x_{3} − x_{5}
z = 3 + x_{3} − 2x_{5}

s odpovídajícím bázovým přípustným řešením (1, 2, 0, 2, 0) a hodnotou z = 3. Provedeme další úpravu tabulky, při které se proměnná x_{3} přesune mezi bázové proměnné a x_{4} naopak bázi opustí. Dostaneme tak tabulku

x_{2} = 2  − x_{5}
x_{3} = 2 − x_{4} + x_{5}
x_{1} = 3 − x_{4}
z = 5 − x_{4} − x_{5}

s odpovídajícím bázovým přípustným řešením (3, 2, 2, 0, 0) hodnotou účelové funkce z = 5. V této tabulce nemůžeme žádnou nebázovou proměnnou zvětšit aniž bychom nesnížili hodnotu účelové funkce z. Žádnou další analogickou úpravu tabulky proto nemůžeme udělat. Naštěstí to znamená, že už jsme našli optimální řešení. To si můžeme snadno ověřit. Je-li (x′_{1}x′_{2}x′_{3}x′_{4}x′_{5}) libovolné přípustné řešení první tabulky s hodnotou účelové funkce z′, pak je rovněž přípustným řešením poslední tabulky, ze které vyplývá

z′ = 5 − x′_{4} − x′_{5}.

Protože navíc musí platit x′_{4} ≥ 0 a x′_{5} ≥ 0, dostáváme tak z′ ≤ 5. □

Geometrická interpretace

Omezující podmínky úlohy 14.2 můžeme znázornit geometricky. Každá podmínka (včetně podmínek x_{i} ≥ 0 pro i = 1, 2) určuje uzavřenou polorovinu v rovině. Jejich průnik je uzavřený konvexní mnohoúhelník P všech přípustných řešení. Kvůli podmínkám x_{i} ≥ 0 pro i = 1, 2 je tento mnohoúhelník obsažený v prvním kvadrantu. Maximalizovat účelovou funkci z = x_{1} + x_{2} znamená najít ten bod (x_{1}, x_{2}) mnohoúhelníku přípustných řešení, pro který má fukce z = x_{1} + x_{2} maximální možnou hodnotu.

Obecná úloha lineárního programování je ve tvaru

• maximalizujte funkci ∑_{j=1}^{n} c_{j}x_{j}

• za předpokladů ∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{j} pro i = 1, 2, …, m

• a dále x_{j} ≥ 0 pro j = 1, 2, …, n,

kde c_{j}, b_{i} a a_{ij} jsou reálná čísla.

Každá nerovnost

∑_{j=1}^{n}a_{ij}x_{j} ≤ b_{j} pro i = 1, 2, …, m

popisuje uzavřený poloprostor v n-dimezionálním aritmetickém prostoru R^{n}. Množina P všech přípustných řešení je tak průnikem m + n uzavřených poloprostorů. Průnik konečně mnoha uzavřených poloprostorů v R^{n} nazýváme konvexní polytop.

Co s výjimkami?

Neomezenost Při jednom kroku simplexového algoritmu hledáne nebázovou proměnnou, kterou můžeme zvětšit tak, abychom nějakou bázovou proměnnou zmenšili na 0. Může se ale stát, že žádná taková bázová proměnná neexistuje. Uvažujme úlohu maximalizovat účelovou funkci z = x_{1} za podmínek x_{1} − x_{2} ≤ 1 a −x_{1} + x_{2} ≤ 2 (a samozřejmě x_{1}, x_{2} ≥ 0). Počáteční tabulka této úlohy je

x_{3} = 1 − x_{1} + x_{2}
x_{4} = 2 + x_{1} − x_{2}
z =  x_{1}

V prvním kroku simplexového algoritmu přesuneme do báze proměnnou x_{1}. Dostaneme tak tabulku

x_{1} = 1 + x_{2} − x_{3}
x_{4} = 3  − x_{3}
z = 1 + x_{2} − x_{3}

Pokusíme-li se nyní přesunout do báze proměnnou x_{2} tak zjistíme, že že žádná z rovnic nedává žádné omezení na její velikost. Jak x_{2} tak i účelová funkce z mohou nabývat libovolně velkých hodnot, úloha je neomezenná. Podud zvětšujeme x_{2} do nekonečna, dostaneme celou polopřímku přípustných řešení s počátkem v současném bázovém přípustném řešení (1, 0, 0, 3). Je to množina

{(1, 0, 0, 3) + x_{2}(1, 1, 0, 0) : x_{2} ≥ 0}.

Příčinnou je neomezenost polytopu přípustných řešení P.

Degenerovanost V degenerovaném případě nastává opačný extrémní případ – některé rovnice tabulky způsobují, že nemůžeme žádnou nebázovou proměnnou zvětšit a žádný nárůst účelové funkce tak není možný. Ukážeme si to opět na příkladu. Tentokrát se budeme snažit maximalizovat účelovou funkci z = x_{2} za podmínek −x_{1} + x_{2} ≤ 0 a x_{1} ≤ 2 a x_{1}, x_{2} ≥ 2. Počáteční tabulka je

x_{3} =  x_{1} − x_{2}
x_{4} = 2 − x_{1}
z =  x_{2}

Bázové přípustné řešení se rovná (0, 0, 0, 2). Jediným kandidátem na přesunutí do báze je proměnná x_{2}. První rovnice ale říká, že ji nemůžeme zvětšit aniž bychom učinili proměnnou x_{3} zápornou. Tato situace nastane vždy kdy v bázovém přípustném řešení se některá z bázových proměnných rovná 0. Takový případ nazýváme degenerovaný. Nemožnost zvýšení hodnoty účelové funkce ale neznamená optimalitu bázového přípustného řešení. V našem případě přesunutím proměnné x_{2} do báze dostaneme další degenerovanou tabulku se stejným bázovým přípustným řešením:

\begin{aligned}x_{2} & = & & & x_{1} & − & x_{3} \\ x_{4} & = & 2 & − & x_{1} \\ z & = & & & x_{1} & − & x_{3} \end{aligned}

Situace se přesto zlepšila. Nebázovou proměnnou x_{1} llze nyní zvětšit a jejím přesunutím do báze dostaneme závěrečnou tabulku

x_{1} = 2  − x_{4}
x_{2} = 2 − x_{3} − x_{4}
z = 2 − x_{3} − x_{4}

s optimálním bázovým přípustným řešením (2, 2, 0, 0).

V tomto případě bylo možné po jednom kroku, kdy zůstala hodnota účelové funkce nezměněná, udělat další úpravu tabulky, která již hodnotu účelové funkce zvětšila. V obecnosti takových degenerovaných kroků může být více, může dokonce nastat i případ, kdy se celý postup zacyklí a po několika degenerovaných krocích dostaneme opět původní tabulku. Jak ukazuje následující lemma, zacyklení je jediná možnost, při které algoritmus neskončí. Nemůže se stát, že bychom dostali nekonečnou posloupnost různých tabulek k dané úloze.

Lemma 14.2 Úloha lineárního programování

• maximalizujte funkci ∑_{j=1}^{n} c_{j}x_{j}

• za předpokladů ∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{j} pro i = 1, 2, …, m

• a dále x_{j} ≥ 0 pro j = 1, 2, …, n,

kde c_{j}, b_{i} a a_{ij} jsou reálná čísla, má nejvýše \binom{m+n}{m} různých tabulek.

Důkaz. Na přednášce, vychází z toho, že výběr m bázových proměnných určuje tabulku jednoznačně. □

Perturbace

Standardní metoda jak vyloučit zacyklení spočívá v použití mocnin symbolické proměnné ϵ, o které předpokládáme, že je kladná a nekonečně malá. S její pomocí upravíme původní úlohu do tvaru

• maximalizujte funkci ∑_{j=1}^{n} c_{j}x_{j}

• za předpokladů ∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{j} + ϵ^{j} pro i = 1, 2, …, m

• a dále x_{j} ≥ 0 pro j = 1, 2, …, n,

kde c_{j}, b_{i} a a_{ij} jsou reálná čísla. Má-li původní úloha přípustné řešení, má je i nová úloha. A naopak, z libovolného řešení nové úlohy dostaneme řešení původní úlohy tak, že položíme ϵ = 0.

S pomocnou symbolickou proměnnou ϵ vypadá počáteční tabulka poslední úlohy následovně.

x_{3} =  ϵ + x_{1} − x_{2}
x_{4} = 2 + ϵ^{2} − x_{1}
z =  x_{2}

Po přesunutí proměnné x_{2} do báze dostaneme

\begin{aligned}x_{2} & = & & & ϵ & + & x_{1} & − & x_{3} \\ x_{4} & = & 2 & + & ϵ^{2} & − & x_{1} \\ z & = & & & ϵ & + & x_{1} & − & x_{3} \end{aligned}

přičemž hodnota účelové funkce se zvýší na ϵ. A po přesunutí x_{1} do báze dostaneme tabulku

\begin{aligned}x_{2} & = & 2 + ϵ^{2} & + & x_{1} & − & x_{3} \\ x_{4} & = & 2 + ϵ + ϵ^{2} & − & x_{3} & − & x_{4} \\ z & = & 2 + ϵ + ϵ^{2} & − & x_{3} & − & x_{4} \end{aligned}

s optimálním bázovým přípustným řešením (2+ϵ^{2}, 2+ϵ+ϵ^{2}, 0, 0). Po dosazení ϵ = 0 dostaneme optimální řešení původní úlohy.

Pro výběr proměnné, kterou přesuneme do báze, potřebujeme umět porovnávat hodnoty polynomů v proměnné ϵ. To uděláme pomocí lexikografického uspořádání.

Definice 14.3 Předpokládáme, že (a_{0}, a_{1}, …, a_{n}) a (b_{0}, b_{1}, …, b_{n}) jsou dvě posloupnosti reálných čísel. Říkáme, že posloupnost (a_{0}, a_{1}, …, a_{n}) je lexikograficky menší než posloupnost (b_{0}, b_{1}, …, b_{n}) jestliže existuje přirozené číslo j ∈ {0, 1, …, n − 1} takové, že a_{i} = b_{i} pro všechna i = 0, …, j a a_{j+1} < b_{j+1} .

Při výběru proměnné pro přesunutí do báze pak používáme nerovnost

∑_{k=0}^{n} a_{k}ϵ^{k} < ∑_{k=0}^{n} b_{k}ϵ^{k}

právě když posloupnost (a_{0}, a_{1}, …, a_{n}) je lexikograficky menší než posloupnost (b_{0}, b_{1}, …, b_{n}).

Nepřípustnost

Aby mohl simplexový algoritmus začít, potřebuje nějakou tabulku, ze které po dosazení x_{i} = 0 za libovolnou nebázovou proměnnou x_{i} dostaneme přípustné řešení. Říkáme, že tabulka má přípustný počátek. Počáteční tabulka úlohy lineárního programování ale přípsutný počátek mít nemusí, jak ukazuje následující úloha.

Maximalizujte funkci z = −x_{2} vzhledem k podmínkám −x_{1} − x_{2} ≤ −2 a x_{1} − x_{2} ≤ −1 a x_{1}, x_{2} ≥ 0. Počáteční tabulka této úlohy je

x_{3} = −2 + x_{1} + x_{2}
x_{4} = −1 − x_{1} + x_{2}
z =  − x_{2}

a po dosazení x_{1} = x_{2} = 0 dostáváme x_{3} = −2 a x_{4} = −1, což není přípustné řešení. Počáteční tabulka nemá přípustný počátek.

Tento problém vyřešíme zavedením nové pomocné proměnné x_{0} a budeme maximalizovat novou účelovou funkci w = −x_{0} vzhledem k podmínkám −x_{1}−x_{2}−x_{0} ≤ −2 a x_{1}−x_{2}−x_{0} ≤ −1 a x_{0}, x_{1}, x_{2} ≥ 0. Tato úloha má přípustné řešení pro dostatečně velké x_{0}. Modifikovaná úloha má počáteční tabulku

x_{3} = −2 + x_{1} + x_{2} + x_{0}
x_{4} = −1 − x_{1} + x_{2} + x_{0}
w =  − x_{0}

Tato tabulka rovněž nemá přípustný počátek, můžeme z ní ale dostat tabulku s přípustným počátkem tak, že zvětšíme dostatečně hodnotu pomocné proměnné x_{0}. Cílem zvětšování proměnné x_{0} tentokrát není zvýšení hodnoty účelové funkce, ale nalezení tabulky s přípustným počátkem. Abychom dostali x_{3} ≥ 0, musí být x_{0} ≥ 2. V tom případě je rovněž x_{4} ≥ 1. Přesuneme pomocnou proměnnou x_{0} do báze místo proměnné x_{3} a dostaneme novou tabulku pro pomocnou úlohu, tentokrát ale již s přípustným počátkem.

x_{0} = 2 − x_{1} − x_{2} + x_{3}
x_{4} = 1 − 2x_{1}  + x_{3}
w = -2 + x_{1} + x_{2} − x_{3}

Nyní lze již simplexový algoritmus použít, do báze přesuneme proměnnou x_{2} a dostaneme závěrečnou tabulku

x_{2} = 2 − x_{1} + x_{3} − x_{0}
x_{4} = 1 − 2x_{1} + x_{3}
w =  − x_{0}

Bázové přípustné řešení je (x_{0}, x_{1}, x_{2}, x_{3}, x_{4}) = (0, 0, 2, 0, 1) a účelová funkce nabývá maximální hodnoty w = −x_{0} = 0.

Co z toho vyplývá pro řešení původní úlohy maximalizovat funkci z = −x_{2} vzhledem k podmínkám −x_{1}−x_{2} ≤ −2 a x_{1}−x_{2} ≤ −1 a x_{1}, x_{2} ≥ 0? Protože účelová funkce pomocné úlohy w = −z_{0} nabývá maximální hodnotu 0, splňují proměnné x_{1}, x_{2}, x_{3}, x_{4} z bázového přípustného řešení pomocné úlohy podmínky (nerovnosti) úlohy původní. Ze závěrečné tabulky modifikované úlohy tak dostaneme přípustnou tabulku původní úlohy tak, že vynecháme pomocnou proměnnou x_{0} a vyjádříme původní účelovou funkci z = −x_{2} pomocí nebázových proměnných z = −x_{2} = −2 + x_{1} − x_{3}. Dostaneme tak tabulku

\begin{aligned}x_{2} & = & 2 & − & x_{1} & + & x_{3} \\ x_{4} & = & 1 & − & 2x_{1} & + & x_{3} \\ w & = & −2 & + & x_{1} & − & x_{3} \end{aligned}

s bázovým přípustným řešením (x_{1}, x_{2}, x_{3}, x_{4}) = (0, 2, 0, 1). Od této tabulky můžeme dále postupovat obvyklým způsobem. Abzchom mohli takto získat přípustnou tabulku z konečné tabulky modifikované úlohy, musí být pomocná proměnná x_{0} v této tabulce nebázová. To zajistíme tak, že kdykoliv je možné pomocnou proměnnou x_{0} nahradit v bázi nějakou jinou proměnnou, tak to uděláme.

Je-li naopak maximální hodnota účelové funkce modifikované úlohy záporná, pak původní úloha nemá žádné přípustné řešení, je neřešitelná.

Podobně se můžme vyrovnat s obecnou úlohou

• maximalizujte funkci ∑_{j=1}^{n} c_{j}x_{j}

• za předpokladů ∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{j} pro i = 1, 2, …, m

• a dále x_{j} ≥ 0 pro j = 1, 2, …, n,

kde c_{j}, b_{i} a a_{ij} jsou reálná čísla, pokud nemá přípustný počátek. Tuto úlohu modifikujeme zavedením pomocné proměnné x_{0} na úlohu

• maximalizujte funkci −x_{0}

• za předpokladů ∑_{j=1}^{n} a_{ij}x_{j} − x_{0} ≤ b_{j} pro i = 1, 2, …, m

• a dále x_{j} ≥ 0 pro j = 0, 1, 2, …, n,

kde c_{j}, b_{i} a a_{ij} jsou reálná čísla. Řešením této modifikované úlohy najdeme přípustnou tabulku původní úlohy, pokud nová účelová funkce w = −x_{0} má maximální hodnotu 0. Pokud je maximální hodnota nové účelové funkce w = −x_{0} nenulová (záporná), pak původní úloha nemá žádné přípustné řešení.

Simplexový algoritmus si uvedeme pro případ, že už máme nějakou přípustnou tabulku

Algoritmus SIMPLEX(úloha lineárního programování) sestav počáteční tabulku úlohy {x_{B} = b + Ax_{N}, z = c^{T} x_{N}} opt:=false; neom:=false; REPEAT

IF c ≤ 0 THEN opt:=true ELSE

BEGIN s:=min{j : c_{j} > 0}; IF A_{∗s} ≥ 0 THEN neom:=true ELSE

BEGIN r:=min\{k : \frac{b_{k}}{−a_{ks}} = min\{\frac{b_{j}}{−a_{js}} : a_{js} < 0\} : a_{ks} < 0\} přesuň proměnnou x_{N_{s}} do báze místo x_{B_{r}}

END

END UNTIL opt OR neom; IF opt THEN x_{B} je optimální řešení ELSE úloha je neomezená

Různá pravidla pro výběr prvku a_{rs}

Největší koeficient c_{j}, největší nárůst z, Blandovo pravidlo (použito v algoritmu), náhodně.