(a) Consider the following statements about linear programming and the simplex method. Label each statement as true or false:
(1) Given that an optimal solution to a linear programming problem exists, it must occur at a vertex of the feasible set. ( )
(2) If the optimal solution occurs at two adjacent vertices of the feasible set, then the linear programming problem has infinitely many solutions. Any point on the line segment joining the two vertices is also a solution. ( )
(b) Outline the steps of the graphical method for solving linear programming problems.
Step 1: Graph the system of constraints. This will give the feasible set.
(a) Explain the following criteria:
(1) Optimality Criterion. Suppose that, in a maximization problem, every nonbasic variable has a nonpositive coefficient in the objective function of a canonical form. Then the basic feasible solution given by the canonical form maximizes the objective function over the feasible region.
(2) Improvement Criterion. Suppose that, in a maximization problem, some nonbasic variable has a positive coefficient in the objective function of a canonical form. If that variable has a positive coefficient in some constraint, then a new basic feasible solution may be obtained by pivoting.
(b) The simplex method is an iterative algorithm with the following structure, please explain them in detail, including how to determine the entering and leaving basic variables.
Initialization: Set up to start iterations, including finding an initial CPF solution.
Optimality test: Is the current CPF solution optimal?