Oba tvary vyžadjí maximalizaci, účelovou funkci tedy otočíme vynásobením \(-1\) na \(\max 2x_1- x_3\)
Nejprve tvar \(A\mathbf x\le\mathbf b\). První rovnost je třeba rozložit na dvě nerovnosti (se omezeními \(\le\) a \(\ge\)) a poté otočit všecny nerovnosti vynásobením \(-1\) na \(\le\). Dostaneme nerovnosti:
\[\begin{eqnarray*} 5 x_1 + 3x_2 & \le & 6 \\ -5 x_1 - 3x_2 & \le& -6 \\ - x_2 - 2x_3 & \le & -4 \\ -3 x_1 - 2x_2 + 6x_3 & \le & -6 \\ 2 x_1 + x_2 - 3x_3 & \le & 5 \\ x_2 & \le & 0 \\ -x_1 & \le & 3 \end{eqnarray*}\]
Pro tvar \(A\mathbf x=\mathbf b, \mathbf x\ge0\) zavedeme do 2., 3., 4. a 6. podmínky pomocné proměnné \(z_1,…,z_4\). Poté provedeme následující substituce:
– jakmile původní proměnná \(x_i\) může nabývat kladných i záporných hodnot \(x_i=x_i'-x_i''\) (týká se \(x_1\) a \(x_3\), ale \(x_1\) lze ošetřit i jinak, viz dále)
– je li proměnná zároveň i omezená, můžeme ustřit jednu pomocnou proměnnou, u \(x_1\) substitucí \(x_1=x_i'-3\)
– má-li proměnná jen záporné hodnoty, položíme \(x_2=-x_2''\)
Zapíšeme rovnou maticově:
\[ \begin{pmatrix} 5 & -3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & -2 & 2 & 1 & 0 & 0 & 0 \\ 3 & -2 & -6 & 6 & 0 & -1 & 0 & 0 \\ -2 & 1 & 3 & -3 & 0 & 0 & -1 & 0 \\ \end{pmatrix} \begin{pmatrix} x_1' \\ x_2'' \\ x_3' \\ x_3'' \\ z_1 \\ z_2 \\ z_3 \\ z_4 \end{pmatrix} = \begin{pmatrix} 21 \\ -4 \\ 15 \\ -11 \end{pmatrix} \]
kde \(\mathbf x'=(x_1', x_1'' ,x_2'', x_3', x_3'', z_1, z_2, z_3, z_4)\ge 0\).
Na cílovou funkci provedeme stejné substituce a získáme \(z'=\max{\mathbf c'}^T\mathbf x'=z+6\), kde \(c'=(2, 0, -1, 1, 0, 0, 0, 0)^T\).
Z řešení transformované úlohy získáme substitucemi řešení původní úlohy.
