CSC 445/545: Midterm Study Aid Fall 2012

Coverage for the first test:

Chapters 1-5 from the text.

Chapter 1:

1. Be able to express a problem explained in words as a linear programming problem.
2. Definitions: optimal solution, feasible solution, infeasible, unbounded.
3. Know that our standard form is:
   Max c^T x
   subject to Ax <= b
   x >= 0
4. Be able to put an arbitrary LP into an equivalent one which is in standard form.

Chapter 2:

1. Know how to pivot and the Simplex rules for deciding where to pivot.
2. Understand and be able to execute pivoting using:
   • largest coefficient rule,
   • smallest subscript rule.
3. Understand dictionaries.
4. Understand the role of B^-1 with regards to finding a dictionary which corresponds to a given basis [Covered in class].
5. Understand the tableau format.

Chapter 3:

1. Understand and be able to execute the two phase Simplex method.
2. Cycling and degeneracy: the lexicographic and perturbation methods were not covered in detail yet and so no specific questions about them will be on the midterm.
3. Know that the Simplex method does not cycle as long as ties for selecting the entering and leaving variable are broken by selecting the variable with the smallest subscript. You do not need to know the details of the proof for the exam.
4. Theorem 3.4: Understand this theorem and its proof.

Chapter 4:

1. Know that there are examples for which the Simplex method can take an exponential number of iterations, and hence the algorithm does not run in polynomial time.
2. Be able to execute the Simplex method using the maximum increase rule.
3. Read and understand discussion on the difference in efficiency in theory and in practice.

Chapter 5:

1. Given a problem in standard form, be able to construct its dual.
2. Know how to read the dual solution from the final dictionary for the primal problem.
3. Undertand the relationships between primal and dual problems (summarized in Table 5.1).
4. Know that if x* is a feasible primal solution, and y* is a feasible dual solution and c^T x* (the primal objective function) is equal to b^Ty* (the dual objective function) then both x* and y* are optimal solutions.

Note: Some of the previous tests covered complementary slackness and the effect of small changes to the b_i's but these will not be on our test.