In Chapter 2 we wrote a system of linear equations using matrix notation. Similarly, we can use matrix notation to write a system of linear inequalities.

1. (a) Find matrices A, B, C, and X such that the maximization problem in Example 1 of Section 4.1 can be written as

    Maximize   C X     subject   to:   A X ≤ B with X ≥ O .

(Hint: Let B and X be column matrices, and C a row matrix.)

1. (b) Show that the dual of the problem in part (a) can be written as

Minimize Y B subject   to: Y A ≥ C with Y ≥ O ,

  where Y is a row matrix.

1. (c) Show that for any feasible solutions X and Y to the original and dual problems, respectively, CX ≤ YB. (Hint: Multiply both sides of AX ≤ B by Y on the left. Then substitute for YA.)

EXAMPLE 1 Slack Variables

Restate the following linear programming problem by introducing slack variables.

Maximize z = 3 x 1 + 2 x 2 + x 3 subject   to: 2 x 1 +       x 2 +     x 3 ≤ 150 2 x 1 + 2 x 2 + 8 x 3 ≤ 200 2 x 1 + 3 x 2 +       x 3 ≤ 320 with x 1 ≥ 0 ,   x 2 ≥ 0 ,   x 3 ≥ 0.