17.4.3
Standardní tvar úlohy lineárního programování
Doc. Ing. Alois Fiala, CSc.
NahoruStandardní tvar
Jakoukoli úlohu LP lze převést do tzv. standardního tvaru, v
němž se účelová funkce maximalizuje, všechny proměnné jsou nezáporné a ostatní
omezující podmínky mají tvar rovnic. Nezápornost všech proměnných a rovnicový
tvar ostatních omezujících podmínek jsou nutné pro to, abychom mohli úlohu LP
řešit numericky. Omezení na pouze jeden typ optimalizace je vhodné pro
zjednodušení teorie a programů pro řešení úloh LP. Úloha LP ve standardním
tvaru vypadá takto:
Z úsporných důvodů se často používá maticový zápis:
max { cT x | Ax = b, x ≥ 0 },
kde matice A je typu (m, n), vektor b je
typu (m, 1), vektory c a x jsou typu (n, 1) a
symbol T označuje transpozici.
U úlohy LP ve standardním tvaru budeme nadále předpokládat, že:
b ≥ 0, m ≤ n, h(A) = m,
kde h(A) je hodnost matice A (je to maximální
počet lineárně nezávislých řádků nebo sloupců matice A). Uvedené
předpoklady nejsou na újmu obecnosti. Jestliže má nějaká rovnice zápornou
pravou stranu, můžeme tuto rovnici vynásobit (–1). Je-li m > n nebo je-li h(A) <m, jsou buď některé rovnice závislé a
pak je můžeme vypustit, nebo jsou v rozporu a pak se úlohou nemusíme zabývat,
protože nemá přípustné řešení.
Minimalizační úloha se převede na maximalizační změnou znaménka
účelové funkce. Platí:
min f(x) = – max (– f(x)).
Nerovnice typu ≤ se převede na rovnici přičtením nezáporné doplňkové proměnné k levé straně nerovnice. Podmínka
se tedy nahradí ekvivalentní dvojicí podmínek
kde xdi je doplňková proměnná příslušná
k i-té podmínce (každé nerovnici odpovídá jiná doplňková proměnná).
Nerovnice typu ≥ se převede na rovnici odečtením nezáporné doplňkové
proměnné od levé strany nerovnice. Podmínka
se tedy nahradí ekvivalentní dvojicí podmínek
kde xdr je doplňková proměnná příslušná
k r-té podmínce.
Nezápornost proměnných se zajistí vhodnou substitucí:
