Principles of Mathematics in Operations Research

8.5 Problems 115

Either P4 is feasible, or D4 is unbounded. For D4 to be unbounded, we

must have bTy < 0. Thus, either Ax > b,x > 8 has a solution, or else

3y 3 ATy > 6, yTb < 0, y < 9.

Problems

8.1. (P):

Max z =xi + 2x2 + 2x3

s.t.

2xi + x 2 < 8

x 3 < 10

x 2 >2

xi,x 2 ,x 3 > 0.

Let the slack/surplus variables be «i, S2, S3.

a)Draw the polytope defined by the constraints in R^3 , identify its extreme

points and the minimum set of supporting hyperplanes.

b) Solve (P) using

1. matrix form,


2. simplex tableau,


3. revised simplex with product form of the inverse,


4. revised simplex with B = LU decomposition,


5. revised simplex with B = QR decomposition.
   c) Write the dual problem, draw its polytope.

8.2. Let P = {(xi,x 2 ,x 3 ) > 0 and

2xi — x 2 — X3 > 3

xi - x 2 + x 3 > 2
xi -2x 2 + 2x 3 > 4}.
Let «i,S2,S3 be the corresponding slack/surplus variables.
a) Find all the extreme points of P.
b) Find the extreme rays of P (if any).
c) Considering the extreme rays of P (if any) check whether we have a finite
solution x G P if we maximize

1. xi +x 2 + x 3 ,


2. -2xi — X2 - 3x 3 ,


3. —xi — 2x 2 + 2x3.

d) Let xi = 6, x 2 = 1, X3 = |. Express this solution with the convex