Math 482 old topic (questions on these topics may be asked on test 2)

• General form, canonical form and standard form of an LP and converting between forms
• drawing the feasible region LP in the plane
• basic feasible solutions and their associated basis
• simplex tableaus
• lex positive, lex negative, lex zero, lexicographic ordering
• lexicographic simplex
• two phase simplex
• simplex method as a series of pre-multiplications by special matrices (any necessary formulas will be provided)
• Bland's algorithm

Math 482 Test 2 Topics

• definitions related to convexity: convex combination, convex set, hyperplane, halfspace, polyhedron, extreme point, facets and vertex.
• relationship between extreme points of a polyhedron, vertices of a polyhedron and the set of feasible solutions of a LP in standard form
• Duality, dual of an LP in canonical form, dual to an LP in standard form, dual of an LP in general form
• weak duality, strong duality
• dual simplex method
• Farkas Lemma (Theorem 3.5)
• Matrix games, pure strategy, mixed strategy, minimax theorem
• complementary slackness (section 3.4)
• shortest path problem as an LP (Section 3.4),
• revised simplex method (section 4.1),
• revised simplex method for max-flow (section 4.3)