29.1 Standard and slack forms

29.1-1

If we express the linear program in $\text{(29.24)}$–$\text{(29.28)}$ in the compact notation of $\text{(29.19)}$–$\text{(29.21)}$, what are $n$, $m$, $A$, $b$, and $c$?

$$ \begin{aligned} n = m & = 3, \\ A & = \begin{pmatrix} 1 & 1 & -1 \\ -1 & -1 & 1 \\ 1 & -2 & 2 \end{pmatrix} , \\ b & = \begin{pmatrix} 7 \\ -7 \\ 4 \end{pmatrix} , \\ c & = \begin{pmatrix} 2 \\ -3 \\ 3 \end{pmatrix} . \end{aligned} $$

29.1-2

Give three feasible solutions to the linear program in $\text{(29.24)}$–$\text{(29.28)}$. What is the objective value of each one?

1. $(x_1, x_2, x_3) = (6, 1, 0)$ with objective value $9$.
2. $(x_1, x_2, x_3) = (5, 2, 0)$ with objective value $4$.
3. $(x_1, x_2, x_3) = (4, 3, 0)$ with objective value $-1$.

29.1-3

For the slack form in $\text{(29.38)}$–$\text{(29.41)}$, what are $N$, $B$, $A$, $b$, $c$, and $v$?

$$ \begin{aligned} N & = \{1, 2, 3\}, \\ B & = \{4, 5, 6\}, \\ A & = \begin{pmatrix} 1 & 1 & -1 \\ -1 & -1 & 1 \\ 1 & -2 & 2 \end{pmatrix} , \\ b & = \begin{pmatrix} 7 \\ -7 \\ 4 \end{pmatrix} , \\ c & = \begin{pmatrix} 2 \\ -3 \\ 3 \end{pmatrix} , \\ v & = 0. \end{aligned} $$

29.1-4

Convert the following linear program into standard form:

$$ \begin{array}{lrcrcrcrl} \text{minimize} & 2x_1 & + & 7x_2 & + & x_3 & & \\ \text{subject to} & \\ & x_1 & & & - & x_3 & = & 7 \\ & 3x_1 & + & x_2 & & & \ge & 24 \\ & & & x_2 & & & \ge & 0 \\ & & & & & x_3 & \le & 0 & . \end{array} $$

$$ \begin{array}{lrcrcrcrcrl} \text{maximize} & -2x_1 & + & 2x_2 & - & 7x_3 & + & x_4 & & \\ \text{subject to} & \\ & -x_1 & + & x_2 & & & - & x_4 & \le & -7 \\ & x_1 & - & x_2 & & & + & x_4 & \le & 7 \\ & -3x_1 & + & 3x_2 & - & x_3 & & & \le & -24 \\ & & x_1, x_2, x_3, x_4 & & & & & & \ge & 0 & . \end{array} $$

29.1-5

Convert the following linear program into slack form:

$$ \begin{array}{lrcrcrcrl} \text{maximize} & 2x_1 & & & - & 6x_3 \\ \text{subject to} & \\ & x_1 & + & x_2 & - & x_3 & \le & 7 \\ & 3x_1 & - & x_2 & & & \ge & 8 \\ & -x_1 & + & 2x_2 & + & 2x_3 & \ge & 0 \\ & & x_1, x_2, x_3 & & & & \ge & 0 & . \end{array} $$

What are the basic and nonbasic variables?

First, we will multiply the second and third inequalities by minus one to make it so that they are all $\le$ inequalities. We will introduce the three new variables $x_4$, $x_5$, $x_6$, and perform the usual procedure for rewriting in slack form

$$ \begin{array}{rcrcrcrcr} x_4 & = & 7 & - & x_1 & - & x_2 & + & x_3 \\ x_5 & = & -8 & + & 3x_1 & - & x_2 \\ x_6 & = & & - & x_1 & + & 2x_2 & + & 2x_3 \\ x_1, x_2, x_3, x_4, x_5, x_6 & \ge & 0 & , \end{array} $$

where we are still trying to maximize $2x_1 - 6x_3$. The basic variables are $x_4$, $x_5$, $x_6$ and the nonbasic variables are $x_1$, $x_2$, $x_3$.

29.1-6

Show that the following linear program is infeasible:

$$ \begin{array}{lrcrcrl} \text{minimize} & 3x_1 & - & 2x_2 \\ \text{subject to} & \\ & x_1 & + & x_2 & \le & 2 \\ & -2x_1 & - & 2x_2 & \le & -10 \\ & & x_1, x_2 & & \ge & 0 & . \end{array} $$

By dividing the second constraint by $2$ and adding to the first, we have $0 \le −3$, which is impossible. Therefore there linear program is unfeasible.

29.1-7

Show that the following linear program is unbounded:

$$ \begin{array}{lrcrcrl} \text{minimize} & x_1 & - & x_2 \\ \text{subject to} & \\ & -2x_1 & + & x_2 & \le & -1 \\ & -x_1 & - & 2x_2 & \le & -2 \\ & & x_1, x_2 & & \ge & 0 & . \end{array} $$

For any number $r > 1$, we can set $x_1 = 2r$ and $x_2 = r$. Then, the restaints become

$$ \begin{array}{rcrcrl} -2(2r) & + & r = -3r & \le & -1 \\ -2r & - & 2r = -4r & \le & -2 \\ & 2r, r & & \ge & 0 & . \end{array} $$

All of these inequalities are clearly satisfied because of our initial restriction in selecting $r$. Now, we look to the objective function, it is $2r - r = r$. So, since we can select $r$ to be arbitrarily large, and still satisfy all of the constraints, we can achieve an arbitrarily large value of the objective function.

29.1-8

Suppose that we have a general linear program with $n$ variables and $m$ constraints, and suppose that we convert it into standard form. Give an upper bound on the number of variables and constraints in the resulting linear program.

In the worst case, we have to introduce 2 variables for every variable to ensure that we have nonnegativity constraints, so the resulting program will have $2n$ variables. If each constraint is an equality, we would have to double the number of constraints to create inequalities, resulting in $2m$ constraints. Changing minimization to maximization and greater-than signs to less-than signs don't affect the number of variables or constraints, so the upper bound is $2n$ on variables and $2m$ on constraints.

29.1-9

Give an example of a linear program for which the feasible region is not bounded, but the optimal objective value is finite.

Consider the linear program where we want to maximize $x_1 − x_2$ subject to the constraints $x_1 − x_2 \le 1$ and $x_1$, $x_2 \ge 0$. clearly the objective value can never be greater than one, and it is easy to achieve the optimal value of $1$, by setting $x_1 = 1$ and $x_2 = 0$. Then, this feasible region is unbounded because for any number $r$, we could set $x_1 = x_2 = r$, and that would be feasible because the difference of the two would be zero which is $\le 1$.

If we further wanted it so that there was a single solution that achieved the finite optimal value, we could add the requirements that $x_1 \le 1$.