Linear Programming

The route

1. 01

   Module 1: Setting up a linear program

   What a linear program is, when one is the right model, and the standard form every algorithm assumes.

   • 1
     Formulating a Linear Program

     • Given a described resource-allocation or planning problem in prose, the learner can define decision variables with explicit units, write a linear objective, and write one linear constraint per stated restriction.
     • Given a described planning or allocation situation, the learner can decide whether a linear program models it as stated, name the specific feature that disqualifies it when one is present, and identify the class of model the situation calls for instead.
   • 2
     Recurring Shapes of Linear Programs

     • Given a decision problem described in words, the learner can name its shape as covering, packing, allocation or a stated hybrid, justify the classification from the language of the description, state the direction of the objective and of the constraints that follow, and name the terminal outcome the shape makes most likely.
   • 3
     The Feasible Region of a Linear Program

     • Given a small linear program in two variables, the learner can determine whether its feasible region is empty, bounded, or unbounded, and justify the classification from the constraints rather than from the objective function.
   • 4
     Converting Linear Programs to Standard Form

     • Given a linear program stated with any mix of maximization or minimization, inequality or equality constraints, and sign-restricted or free variables, the learner can produce an equivalent standard-form program with a minimization objective, equality constraints, and all variables nonnegative, without a conversion checklist in view.
   • 5
     The Matrix Form of a Linear Program

     • Given a linear program written in scalars, the learner can assemble $A$, $b$ and $c$ with correct shapes and write the program as $min{c}^{\mathsf{T}}x$ subject to $Ax\le b$, $x\ge 0$; and given a program in matrix form, can recover a named constraint by its row and state what a named column contributes.
   • 6
     Transforming the Variables

     • Given a linear program whose variables carry sign restrictions other than simple nonnegativity, the learner can select and apply the appropriate substitution for each, carry it through the objective and every constraint, account for any constant it produces, and state how an original solution is recovered from the converted one.
   • 7
     The Transportation Model

     • Given a situation describing supply points, demand points and unit shipping costs, the learner can write the transportation model, test the balance condition and restore balance with a dummy row or column when it fails, read a plan in both the cost-table and network forms, and say what total unimodularity does and does not guarantee about the answer.
2. 02

   Module 2: Graphical solution of linear programs

   Solving in two variables by drawing: plotting the constraints, locating the direction of improvement, and pushing the objective until it leaves the region.

   • 1
     Plotting Linear Inequalities

     • Given one or more linear inequalities in two variables, the learner can draw each boundary line, determine which side the inequality allows by testing a point, and shade the set satisfying all of them together, including sign restrictions.
   • 2
     Contour Lines and the Direction of Improvement

     • Given a linear objective and a direction of optimisation, the learner can draw or describe the contour family, identify the coefficient vector as the direction of increase, decide whether a proposed direction improves the objective, and state which way a contour must be pushed.
   • 3
     Solving a Two-Variable Linear Program Graphically

     • Given a linear program in two variables, the learner can identify the feasible region from its constraints, determine which vertex or edge the objective contour last touches, compute the exact optimal solution by solving the tight constraints, and state whether the optimum is unique.
3. 03

   Module 3: Linear-program outcome classification

   The four terminal outcomes of a linear program, and deciding which one holds from the constraints, the geometry, or a solver report.

   • 1
     The Four Terminal Outcomes

     • Given a linear program in any representation, its constraints and objective, a plotted region, a simplex tableau, or a solver report, the learner can determine which of the four terminal outcomes holds, name the evidence that decides it, and distinguish it from the outcome it is most often confused with.
4. 04

   Module 4: Extreme points and basic feasible solutions

   Active constraints and the rank condition that makes a point a vertex, the basic solution a basis determines, and the correspondence between extreme points and basic feasible solutions.

   • 1
     Active Constraints

     • Given a feasible region described by inequality, equality and nonnegativity constraints together with a feasible point, the learner can determine which constraints are active there, count the independent ones among them, and state what that count implies about the point's position in the region.
   • 2
     Basic Solutions

     • Given a standard-form constraint system and a proposed set of columns, the learner can decide whether the set is a basis, construct the corresponding basic solution by setting nonbasic variables to zero and solving the square system, and state separately whether the result is feasible.
   • 3
     Canonical Form for a Basis

     • Given a standard-form program and a basis, the learner can partition the columns, solve for the basic variables, express the objective in the nonbasic variables alone, and read the basic solution, the objective value and the reduced costs off the result, stating whether the basis is optimal and why.
   • 4
     Extreme Points and Basic Feasible Solutions

     • Given a linear program in standard form and a candidate point, the learner can determine whether the point is a basic feasible solution and justify the determination by reference to feasibility and to the linear independence of the columns associated with its positive components.
     • Given the characterization of extreme points as basic feasible solutions, the learner can bound the number of extreme points of a standard-form program in terms of its dimensions, justify that bound from the characterization, and evaluate whether finiteness alone makes enumeration a practical solution method.
   • 5
     Degenerate Basic Feasible Solutions

     • Given a basic feasible solution, the learner can decide whether it is degenerate, explain the condition both as a count of positive components and as a surplus of active constraints, identify how many bases may describe the point, and state what degeneracy implies for a simplex iteration.
   • 6
     Adjacent Basic Solutions

     • Given a standard-form system and two bases, the learner can decide whether they are adjacent, compute the edge direction generated by an entering variable, determine how far the step can go before feasibility fails, and explain why moving between adjacent corners changes exactly one basis column.
5. 05

   Module 5: The simplex method

   The simplex method: pricing nonbasic columns by reduced cost to choose an entering variable, the ratio test for the leaving variable and step length, and the optimality test.

   • 1
     Reduced Costs and the Optimality Test

     • Given a minimization program in standard form and a specified basis, the learner can compute the reduced cost of each nonbasic variable and determine whether the corresponding basic feasible solution is optimal, without a formula sheet.
   • 2
     One Iteration of the Simplex Method

     • Given a standard-form minimization program and a basic feasible solution, the learner can select an entering variable from the reduced costs, apply the minimum ratio test to find the leaving variable and the step length, and report the resulting basis and basic feasible solution, without a tableau template.
   • 3
     The Full Tableau Simplex Method

     • Given a standard-form minimisation and a starting basis, the learner can build the initial tableau, carry out successive pivots correctly, decide at each iteration whether to continue, and on stopping state which terminal condition fired and read the answer the tableau reports.
   • 4
     The Revised Simplex Method

     • Given a standard-form minimisation and a basis, the learner can compute the basis inverse and basic values, form the multipliers, price nonbasic columns to find an entering variable, compute the direction and step, report the updated basis, and account for which quantities the method stores against those a full tableau would carry.
6. 06

   Module 6: Verifying solver results

   Checking a reported solution against the model as written: primal feasibility, objective consistency, and the credibility of the reported status.

   • 1
     Verifying a Reported Solution

     • Given a model and a reported solution, a status, a point and an objective value, the learner can test primal feasibility against the original constraints, recompute the objective, judge whether the status is credible, and identify which class of fault a discrepancy indicates.
   • 2
     Driving a Linear Programming SolverOptional

     • Given a formulated linear program and a named solver, the learner can convert it into that tool's expected argument form, state what each array position means, invoke it, and translate the reported status, point and objective value back into the terms of the original model.

What finishing means

Finishing this course means you have demonstrated the required skills with the level of support this course currently assesses.

25 required skills. If you reach a lesson without the background it assumes, you are pointed at the prerequisite first, and returned here afterwards.