Skip to content

29.1 Standard and slack forms

29.1-1

If we express the linear program in (29.24)\text{(29.24)}–(29.28)\text{(29.28)} in the compact notation of (29.19)\text{(29.19)}–(29.21)\text{(29.21)}, what are nn, mm, AA, bb, and cc?

n=m=3,A=(11−1−1−111−22),b=(7−74),c=(2−33). \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 (29.24)\text{(29.24)}–(29.28)\text{(29.28)}. What is the objective value of each one?

  1. (x1,x2,x3)=(6,1,0)(x_1, x_2, x_3) = (6, 1, 0) with objective value 99.
  2. (x1,x2,x3)=(5,2,0)(x_1, x_2, x_3) = (5, 2, 0) with objective value 44.
  3. (x1,x2,x3)=(4,3,0)(x_1, x_2, x_3) = (4, 3, 0) with objective value −1-1.

29.1-3

For the slack form in (29.38)\text{(29.38)}–(29.41)\text{(29.41)}, what are NN, BB, AA, bb, cc, and vv?

N={1,2,3},B={4,5,6},A=(11−1−1−111−22),b=(7−74),c=(2−33),v=0. \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:

minimize2x1+7x2+x3subject tox1−x3=73x1+x2≥24x2≥0x3≤0. \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}

maximize−2x1−2x2−7x3+x4subject to−x1+x2−x4≤−7x1−x2+x4≤7−3x1+3x2−x3≤−24x1,x2,x3,x4≤0. \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 & & & & & & \le & 0 & . \end{array}

29.1-5

Convert the following linear program into slack form:

maximize2x1−6x3subject tox1+x2−x3≤73x1−x2≥8−x1+2x2+2x3≥0x1,x2,x3≥0. \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 x4x_4, x5x_5, x6x_6, and perform the usual procedure for rewriting in slack form

x4=7−x1−x2+x3x5=−8+3x1−x2x6=−x1+2x2+2x3x1,x2,x3,x4,x5,x6≥0, \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 2x1−6x32x_1 - 6x_3. The basic variables are x4x_4, x5x_5, x6x_6 and the nonbasic variables are x1x_1, x2x_2, x3x_3.

29.1-6

Show that the following linear program is infeasible:

minimize3x1−2x2subject tox1+x2≤2−2x1−2x2≤−10x1,x2≥0. \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 22 and adding to the first, we have 0≤−30 \le −3, which is impossible. Therefore there linear program is unfeasible.

29.1-7

Show that the following linear program is unbounded:

minimizex1−x2subject to−2x1+x2≤−1−x1−2x2≤−2x1,x2≥0. \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>1r > 1, we can set x1=2rx_1 = 2r and x2=rx_2 = r. Then, the restaints become

−2(2r)+r=−3r≤−1−2r−2r=−4r≤−22r,r≥0. \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 rr. Now, we look to the objective function, it is 2r−r=r2r - r = r. So, since we can select rr 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 nn variables and mm 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 2n2n variables. If each constraint is an equality, we would have to double the number of constraints to create inequalities, resulting in 2m2m 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 2n2n on variables and 2m2m 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 x1−x2x_1 − x_2 subject to the constraints x1−x2≤1x_1 − x_2 \le 1 and x1x_1, x2≥0x_2 \ge 0. clearly the objective value can never be greater than one, and it is easy to achieve the optimal value of 11, by setting x1=1x_1 = 1 and x2=0x_2 = 0. Then, this feasible region is unbounded because for any number rr, we could set x1=x2=rx_1 = x_2 = r, and that would be feasible because the difference of the two would be zero which is ≤1\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 x1≤1x_1 \le 1.