Question

For the following linear programming problem:

   Maximize z = 2x₁+ x₂

   Such that

     x₁+ 2x_{2 ≤} 12

         x₂ ≥ 3

      x₁,x₂ ≥ 0

(a) Write the first two constraints in equation form by adding slack or subtracting excess (surplus) variables.

(b)Find all basic solutions for this LP

(c) Which of these solutions are feasible?

(d)Which of these feasible solutions is optimal? Find the optimal value of z

Answer 1

(a)

Constraints with slacks and surplus:

x1 + 2x2 + s1 = 12

x2 - s2 = 3

(b)

There are four variables: x1, x2, s1, and s2

Make one pair of variables equal to zero and compute the other two from the two equations of part-a as found in the following table.

Example: make x1=0, x2=0 gives s1=12 from the first equation and s2=-3 from the second equation.

These are all basic solutions.

x1	x2	s1	s2
0	0	12	-3
6	3	0	0
0	6	0	3
0	3	6	0
12	0	0	-3

Note that we have excluded the pair (x2=0, s2=0) because that's simply impossible considering the second equation x2 - s2 = 3

(c)

The feasible are only having non-negative values for all the variables i.e. the following only.

x1	x2	s1	s2
6	3	0	0
0	6	0	3
0	3	6	0

(d)

Compute the value of 'z' for the above four solutions. Note the values of x1 and x2 only because 'z' does not contain slacks or surplus.

x1	x2	z = 2x1 + x2
6	3	2*6 + 3 = 15
0	6	2*0 + 6 = 6
0	3	2*0 + 3 = 3

It is clear that 'z' is maximized when x1=6 and x2=3 so, this is the optimal solution and max. z = 15