Linear Programming basics

Learn how to solve linear programs, starting with two-variable cases and progressing to higher-dimensional problems with simplifying assumptions, then generalize, and analyze the revised simplex method and its complexity.

Learn solving linear programs with two variables by graphing the feasible region and moving the objective function to find the optimal vertex, such as x=4, y=2 giving value 16.

Explore simplex intuition for linear programs with variables by converting to standard equality form, introducing surplus variables, and performing entering and exiting variable steps to reach optimality or detect unboundedness.

Explore the simplex method by formalizing basic and nonbasic variables, building a dictionary, and performing pivot operations to achieve a feasible, optimal solution.

Explore the two-faced simplex method for linear programs, building an auxiliary problem to test feasibility, and use degeneracy and cycling avoidance with the blind rule and practical heuristics.

Discover the revised simplex method, including basic and non basic variable decomposition, reduced costs, entering and exiting variable rules, device simplex for efficient computation, and a ratio test example.

Analyze simplex complexity, possible dictionaries, and cycling avoidance rules; note practical behavior with about M times logging dictionaries on average, plus interior point methods and incremental reuse of solutions.

Explore linear programming duality by introducing duality, computing the dual from the primal, and examining strong duality, complementary slackness, and Fargas Lemma.

Derive the dual from a primal linear program by combining constraints to obtain lower bounds, and show the dual optimum equals the primal optimum.

Examine the duality theorem and the relationship between primal and dual problems. Using the weak duality theorem, the lecture shows that a feasible and unbounded primal implies an infeasible dual.

Explore strong duality in linear programming by linking primal and dual solutions through the simplex method, reduced costs, and optimal dictionaries.

Explore primal and dual feasibility, including feasible and bounded, infeasible and unbounded cases, and the special situation where both are invisible, with duality linking their infinite objectives.

Explore complementary slackness in linear programming, linking primal and dual solutions through zero reduced costs and zero slacks, and use it to prove optimality and detect degeneracy.

Explore Farkas' lemma and a sharp infeasibility proof for a linear program by constructing the dual, a hyperplane separation, and the dual ray.

Explore sensitivity analysis in linear programming, covering changes to right-hand side, objective coefficients, and variables, using revised and dual simplex methods to assess feasibility and optimality.

This lecture explains how changing the right-hand side of constraints affects feasibility and optimal value in linear programming, using dual values and dual simplex to adjust solutions.

This lecture demonstrates how changing X2's objective coefficient affects feasibility and optimality, computes the reduced cost using B and N, and pivots to restore optimality.

Add a new variable and evaluate its impact on feasibility and optimality by computing reduced costs from dual costs and applying primal simplex to restore optimality.

Generalize linear programming techniques to handle any change by assessing feasibility and optimality, applying dual simplex to fix issues, and extending analysis to new constraints and columns.

Review the basics of convex optimization and linear programming, including the simplex method, dual programs, Fargas Lemma, and sensitivity analysis, then explore modeling, mixed integer linear programming, and column generation.