;; Problem 8-1 (setf *a* `((-5 -2) (-3 3))) (setf *b* `(-1 -2)) (setf *c* `(-21 -6)) (make-tableau) ----------------------------------- X1 X2 B ----------------------------------- -5 -2 -1 | Y1 -3 3 -2 | Y2 ----------------------------------- 21 6 0 | F ----------------------------------- NIL (pivot 2 1) ----------------------------------- Y2 X2 B ----------------------------------- -5/3 -7 7/3 | Y1 -1/3 -1 2/3 | X1 ----------------------------------- 7 27 -14 | F ----------------------------------- T ;; No negative indicator, hence solution found. ;; Problem 8-2 ;; Part A (setf *a* `((1 1) (1 2) (-1 -2))) (setf *b* `(20 30 -30)) (setf *c* `(-1 -3)) (make-tableau) ----------------------------------- X1 X2 B ----------------------------------- 1 1 20 | Y1 1 2 30 | Y2 -1 -2 -30 | Y3 ----------------------------------- 1 3 0 | F ----------------------------------- NIL (pivot 3 1) ----------------------------------- Y3 X2 B ----------------------------------- 1 -1 -10 | Y1 1 0 0 | Y2 -1 2 30 | X1 ----------------------------------- 1 1 -30 | F ----------------------------------- T (pivot 1 2) ----------------------------------- Y3 Y1 B ----------------------------------- -1 -1 10 | X2 1 0 0 | Y2 1 2 10 | X1 ----------------------------------- 2 1 -40 | F ----------------------------------- T ;; No negative dual indicator, hence optimal solution found ;; Optimal Y* = (1 0 2), X* = (10 10), F* = G* = -40. ;; Part B (setf *a* `((1 1) (2 1) (-2 -1))) (setf *b* `(5 6 -6)) (setf *c* `(-2 -1)) (make-tableau) ----------------------------------- X1 X2 B ----------------------------------- 1 1 5 | Y1 2 1 6 | Y2 -2 -1 -6 | Y3 ----------------------------------- 2 1 0 | F ----------------------------------- NIL (pivot 3 1) ----------------------------------- Y3 X2 B ----------------------------------- 1/2 1/2 2 | Y1 1 0 0 | Y2 -1/2 1/2 3 | X1 ----------------------------------- 1 0 -6 | F ----------------------------------- T ;; No neg. dual indicators, Optimal found. ;; X* = (3 0), Y* = (0 0 1), F* = G* = -6. Problem 8-7 (setf *a* `((1 0) (0 1) (1 -1) (-1 1) (2 -1) (-1 2))) (setf *b* `(4 4 4 4 8 8)) (setf *c* `(1 1)) (make-tableau) ----------------------------------- X1 X2 B ----------------------------------- 1 0 4 | Y1 0 1 4 | Y2 1 -1 4 | Y3 -1 1 4 | Y4 2 -1 8 | Y5 -1 2 8 | Y6 ----------------------------------- -1 -1 0 | F ----------------------------------- NIL ; Solve using primal simplex. (do-simplex) Pivoting on Row 1 and Column 1 . ----------------------------------- Y1 X2 B ----------------------------------- 1 0 4 | X1 0 1 4 | Y2 -1 -1 0 | Y3 1 1 8 | Y4 -2 -1 0 | Y5 1 2 12 | Y6 ----------------------------------- 1 -1 4 | F ----------------------------------- Pivoting on Row 2 and Column 2 . ----------------------------------- Y1 Y2 B ----------------------------------- 1 0 4 | X1 0 1 4 | X2 -1 1 4 | Y3 1 -1 4 | Y4 -2 1 4 | Y5 1 -2 4 | Y6 ----------------------------------- 1 1 8 | F ----------------------------------- No negative indicator, Terminated successfully NIL ;; Optimal solution, X* = (4 4), F* = G* = 8, ;; The problem is degenerate since 0`s appear in the ;; tableau's b-area after first pivoting.