Problem 3.1, p 43 (setf *A* `((2 2 -1) (3 -2 1) (1 -3 1))) ; define matrix A (setf *b* `(10 10 10)) ; define b (setf *c* `(1 3 -1)) ; define c (make-tableau) --------------------------------------- X1 X2 X3 B --------------------------------------- 2 2 -1 10 | Y1 3 -2 1 10 | Y2 1 -3 1 10 | Y3 --------------------------------------- -1 -3 1 0 | F --------------------------------------- T (pivot 1 2) --------------------------------------- X1 Y1 X3 B --------------------------------------- 1 1/2 -1/2 5 | X2 5 1 0 20 | Y2 4 3/2 -1/2 25 | Y3 --------------------------------------- 2 3/2 -1/2 15 | F --------------------------------------- T ;;; cannot pivot anymore. Problem is unbounded Problem 3.2 (setf *a* `((-2 -9 1 9) (1/3 1 -1/3 -2))) (setf *b* `(0 0)) (setf *c* `(2 3 -1 -12)) (make-tableau) --------------------------------------- X1 X2 X3 X4 B --------------------------------------- -2 -9 1 9 0 | Y1 1/3 1 -1/3 -2 0 | Y2 --------------------------------------- -2 -3 1 12 0 | F --------------------------------------- T (pivot 2 2) --------------------------------------- X1 Y2 X3 X4 B --------------------------------------- 1 9 -2 -9 0 | Y1 1/3 1 -1/3 -2 0 | X2 --------------------------------------- -1 3 0 6 0 | F --------------------------------------- T (pivot 1 1) --------------------------------------- Y1 Y2 X3 X4 B --------------------------------------- 1 9 -2 -9 0 | X1 -1/3 -2 1/3 1 0 | X2 --------------------------------------- 1 12 -2 -3 0 | F --------------------------------------- T (pivot 2 4) --------------------------------------- Y1 Y2 X3 X2 B --------------------------------------- -2 -9 1 9 0 | X1 -1/3 -2 1/3 1 0 | X4 --------------------------------------- 0 6 -1 3 0 | F --------------------------------------- T (pivot 1 3) --------------------------------------- Y1 Y2 X1 X2 B --------------------------------------- -2 -9 1 9 0 | X3 1/3 1 -1/3 -2 0 | X4 --------------------------------------- -2 -3 1 12 0 | F --------------------------------------- T ;;; Which is numerically same as the original tableau, ;;; hence we have cycling using the first row rule. ; Problem 3.3 ;;; Solving prob 3.2 by the perturbation technique. (make-tableau) --------------------------------------- X1 X2 X3 X4 B --------------------------------------- -2 -9 1 9 0 | Y1 1/3 1 -1/3 -2 0 | Y2 --------------------------------------- -2 -3 1 12 0 | F --------------------------------------- T (setf *b* `(0.0001 0.00000001)) (make-tableau) ; with perturbation. --------------------------------------- X1 X2 X3 X4 B --------------------------------------- -2 -9 1 9 9.9999994e-5 | Y1 1/3 1 -1/3 -2 1.0e-8 | Y2 --------------------------------------- -2 -3 1 12 0 | F --------------------------------------- T (pivot 2 2) --------------------------------------- X1 Y2 X3 X4 B --------------------------------------- 1 9 -2 -9 1.00090005e-4 | Y1 1/3 1 -1/3 -2 1.0e-8 | X2 --------------------------------------- -1 3 0 6 2.9999998e-8 | F --------------------------------------- T (pivot 2 1) --------------------------------------- X2 Y2 X3 X4 B --------------------------------------- -3 6 -1 -3 1.0006001e-4 | Y1 3 3 -1 -6 2.9999998e-8 | X1 --------------------------------------- 3 6 -1 0 5.9999996e-8 | F --------------------------------------- T ;;; all coeffecients in the negative col are negative. Problem 3.9 NIL (setf *a* `((1 -1) (-1 -1) (2 1))) ((1 -1) (-1 -1) (2 1)) (setf *b* `(-1 -3 4)) (-1 -3 4) (setf *c* `(3 1)) (3 1) (make-exp-tableau) --------------------------------------- X1 X2 X3 B --------------------------------------- 1 -1 1 0 | Y1 -1 -1 3 0 | Y2 2 1 -4 0 | Y3 0 0 1 1 | Y4 -3 -1 0 0 | Phase II --------------------------------------- 0 0 -1 0 | Phase I --------------------------------------- NIL (pivot 1 3) --------------------------------------- X1 X2 Y1 B --------------------------------------- 1 -1 1 0 | X3 -4 2 -3 0 | Y2 6 -3 4 0 | Y3 -1 1 -1 1 | Y4 -3 -1 0 0 | Phase II --------------------------------------- 1 -1 1 0 | Phase I --------------------------------------- T (pivot 2 2) --------------------------------------- X1 Y2 Y1 B --------------------------------------- -1 1/2 -1/2 0 | X3 -2 1/2 -3/2 0 | X2 0 3/2 -1/2 0 | Y3 1 -1/2 1/2 1 | Y4 -5 1/2 -3/2 0 | Phase II --------------------------------------- -1 1/2 -1/2 0 | Phase I --------------------------------------- T (pivot 4 1) --------------------------------------- Y4 Y2 Y1 B --------------------------------------- 1 0 0 1 | X3 2 -1/2 -1/2 2 | X2 0 3/2 -1/2 0 | Y3 1 -1/2 1/2 1 | X1 5 -2 1 5 | Phase II --------------------------------------- 1 0 0 1 | Phase I --------------------------------------- T ; Feasible solution found, reduce tableau and solve Phase II. (reduce-tableau) --------------------------------------- Y2 Y1 B --------------------------------------- -1/2 -1/2 2 | X2 3/2 -1/2 0 | Y3 -1/2 1/2 1 | X1 --------------------------------------- -2 1 5 | F --------------------------------------- NIL (pivot 2 1) --------------------------------------- Y3 Y1 B --------------------------------------- 1/3 -2/3 2 | X2 2/3 -1/3 0 | Y2 1/3 1/3 1 | X1 --------------------------------------- 4/3 1/3 5 | F --------------------------------------- T ; Optimal solution found, X = (1, 2), F = 5. ; Part B (setf *b* `(-1 -3 2)) (-1 -3 2) (make-exp-tableau) --------------------------------------- X1 X2 X3 B --------------------------------------- 1 -1 1 0 | Y1 -1 -1 3 0 | Y2 2 1 -2 0 | Y3 0 0 1 1 | Y4 -3 -1 0 0 | Phase II --------------------------------------- 0 0 -1 0 | Phase I --------------------------------------- NIL (pivot 1 3) --------------------------------------- X1 X2 Y1 B --------------------------------------- 1 -1 1 0 | X3 -4 2 -3 0 | Y2 4 -1 2 0 | Y3 -1 1 -1 1 | Y4 -3 -1 0 0 | Phase II --------------------------------------- 1 -1 1 0 | Phase I --------------------------------------- T (pivot 2 2) --------------------------------------- X1 Y2 Y1 B --------------------------------------- -1 1/2 -1/2 0 | X3 -2 1/2 -3/2 0 | X2 2 1/2 1/2 0 | Y3 1 -1/2 1/2 1 | Y4 -5 1/2 -3/2 0 | Phase II --------------------------------------- -1 1/2 -1/2 0 | Phase I --------------------------------------- T (pivot 3 1) --------------------------------------- Y3 Y2 Y1 B --------------------------------------- 1/2 3/4 -1/4 0 | X3 1 1 -1 0 | X2 1/2 1/4 1/4 0 | X1 -1/2 -3/4 1/4 1 | Y4 5/2 7/4 -1/4 0 | Phase II --------------------------------------- 1/2 3/4 -1/4 0 | Phase I --------------------------------------- T (pivot 3 3) --------------------------------------- Y3 Y2 X1 B --------------------------------------- 1 1 1 0 | X3 3 2 4 0 | X2 2 1 4 0 | Y1 -1 -1 -1 1 | Y4 3 2 1 0 | Phase II --------------------------------------- 1 1 1 0 | Phase I --------------------------------------- T ; Phase I optimal solution, X3 = 0, => No feasible solution, halt. ; Part C (setf *a* `((1 -1) (-1 -1) (2 -1))) ((1 -1) (-1 -1) (2 -1)) (make-exp-tableau) --------------------------------------- X1 X2 X3 B --------------------------------------- 1 -1 1 0 | Y1 -1 -1 3 0 | Y2 2 -1 -2 0 | Y3 0 0 1 1 | Y4 -3 -1 0 0 | Phase II --------------------------------------- 0 0 -1 0 | Phase I --------------------------------------- NIL (pivot 1 3) --------------------------------------- X1 X2 Y1 B --------------------------------------- 1 -1 1 0 | X3 -4 2 -3 0 | Y2 4 -3 2 0 | Y3 -1 1 -1 1 | Y4 -3 -1 0 0 | Phase II --------------------------------------- 1 -1 1 0 | Phase I --------------------------------------- T (pivot 2 2) --------------------------------------- X1 Y2 Y1 B --------------------------------------- -1 1/2 -1/2 0 | X3 -2 1/2 -3/2 0 | X2 -2 3/2 -5/2 0 | Y3 1 -1/2 1/2 1 | Y4 -5 1/2 -3/2 0 | Phase II --------------------------------------- -1 1/2 -1/2 0 | Phase I --------------------------------------- T (pivot 4 1) --------------------------------------- Y4 Y2 Y1 B --------------------------------------- 1 0 0 1 | X3 2 -1/2 -1/2 2 | X2 2 1/2 -3/2 2 | Y3 1 -1/2 1/2 1 | X1 5 -2 1 5 | Phase II --------------------------------------- 1 0 0 1 | Phase I --------------------------------------- T (reduce-tableau) --------------------------------------- Y2 Y1 B --------------------------------------- -1/2 -1/2 2 | X2 1/2 -3/2 2 | Y3 -1/2 1/2 1 | X1 --------------------------------------- -2 1 5 | F --------------------------------------- NIL (pivot 2 1) --------------------------------------- Y3 Y1 B --------------------------------------- 1 -2 4 | X2 2 -3 4 | Y2 1 -1 3 | X1 --------------------------------------- 4 -5 13 | F --------------------------------------- T ;;; No non-negative pivot => Solution unbounded. (dribble)