Standardní tvar úlohy lineárního programování

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 { c^T 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 x^d_i 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 x^d_r je doplňková proměnná příslušná k r-té podmínce.

Nezápornost proměnných se zajistí vhodnou substitucí:

• Nekladná proměnná se nahradí nezápornou proměnnou s opačným znaménkem. Podmínka x_j ≤ 0…