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

• 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
• 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)

Math 482 Test 3 Topics

• Primal dual algorithm (section 5.1 and section 5.2)
• Primal dual applied to shortest path (section 5.4)
• Primal dual applied to max flow - Ford-Fulkerson, (section 5.6 and section 6.1), Ford Fulkerson algorithm, Theorem 6.2 (min-cut,max-flow), Theorem 6.3 (Ford Fulkerson terminates)
• Definitions: the value of a flow, augmenting path, s,t-cuts, the capacity of a cut,...
• Application of the Ford-Fulkerson (maximum matching in bipartite graphs, edge verison of Menger's Theorem)
• Floyd-Warshall algorithm
• Introduction to Integer Linear Programming (ILP), representing problems as ILPs (examples:TSP and satisfiablity)