= Solution
Use the <standard maximum form of a linear program> convention $\max c^Tu$ subject to $Mu\leq b$ and $u\geq0$. Split the unrestricted variables as $x=x^+-x^-$ and $y=y^+-y^-$, with all four new variables nonnegative. The resulting <linear program> is
$$
\begin{aligned}
\max\quad&2x^+-2x^-+3y^+-3y^-+4z+7w\\
\text{subject to}\quad&2x^+-2x^--y^++y^-+5w\leq1,\\
&y^+-y^-+z+w\leq3,\\
&x^+,x^-,y^+,y^-,z,w\geq0.
\end{aligned}
$$
If equality-constraint standard form is preferred, add a nonnegative <slack variable> to each inequality.
Give the two inequalities nonnegative <dual variables> $\alpha,\beta$. The <dual linear program> is
$$
\begin{aligned}
\min\quad&\alpha+3\beta\\
\text{subject to}\quad&2\alpha\geq2,\qquad -2\alpha\geq-2,\\
&-\alpha+\beta\geq3,\qquad \alpha-\beta\geq-3,\\
&\beta\geq4,\qquad5\alpha+\beta\geq7,\\
&\alpha,\beta\geq0.
\end{aligned}
$$
The paired inequalities encode equalities for the two original unrestricted variables. Equivalently, the <dual linear program> has $2\alpha=2$, $-\alpha+\beta=3$, $\beta\geq4$, $5\alpha+\beta\geq7$ and $\alpha,\beta\geq0$. Thus \b[its only <feasible point> is $(\alpha,\beta)=(1,4)$, of <objective function> value $13$].
Back to article page
