Linear Programming NotesCarl W. LeeDepartment of MathematicsUniversity of KentuckyLexington, KY [email protected] 3, 1996Latest Revision: Summer 20021Contents1 References 52 Exercises: Linear Algebra 63 Introduction 93.1 Example...................................... 93.2 Definitions..................................... 103.3 BacktotheExample............................... 114 Exercises: Linear Programs 135 Theorems of the Alternatives 175.1 SystemsofEquations............................... 175.2 Fourier-Motzkin Elimination — A Starting Example . . . . . . . . . . . . . . 195.3 ShowingourExampleisFeasible ........................ 225.4 AnExampleofanInfeasibleSystem ...................... 235.5 Fourier-MotzkinEliminationinGeneral..................... 255.6 MoreAlternatives................................. 276 Exercises: Systems of Linear Inequalities 297 Duality 327.1 EconomicMotivation............................... 327.2 TheDualLinearProgram ............................ 337.3 TheDualityTheorems .............................. 357.4 CommentsonGoodCharacterization...................... 407.5 ComplementarySlackness ............................ 407.6 DualsofGeneralLP’s .............................. 417.7 GeometricMotivationofDuality ........................ 468 Exercises: Duality 489 The Simplex Method 549.1 BasesandTableaux................................ 549.2 Pivoting ...................................... 619.3 The(Primal)SimplexMethod.......................... 66210 Exercises: The Simplex Method 7811 The Simplex Method—Further Considerations 8211.1Uniqueness .................................... 8211.2RevisedSimplexMethod............................. 8211.3DualSimplexMethod .............................. 8511.4RevisedDualSimplexMethod.......................... 8711.5SensitivityAnalysis................................ 8911.5.1 RightHandSides............................. 9011.5.2 ObjectiveFunctionCoefficients ..................... 9211.5.3 NewVariable ............................... 9511.5.4 NewConstraint.............................. 9611.6LP’sWithEquations............................... 9711.7LP’sWithUnrestrictedVariables ........................ 10011.8 LP’s With Bounded Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 10011.9MinimizationProblems.............................. 10412 Exercises: More On the Simplex Method 10513 More On Linear Systems and Geometry 10713.1StructureTheorems................................ 10713.2ExtremePointsandFacets............................ 11014 Exercises: Linear Systems and Geometry 11815 Exercises: Some Formulations 12016 Networks 12317 Exercises: Networks 12918 Total Unimodularity 13319 Exercises: Total Unimodularity 13720 Knapsack and Cutting Stock Problems 13921 Dantzig-Wolfe Decomposition 144322 Subgradient Optimization 14722.1 Subgradients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14722.2LinearProgramswithTwoTypesofConstraints................ 14822.3FindingFeasiblePoints.............................. 15023 The Ellipsoid Method 15324 Appendix: Some More Linear Algebra 16541 ReferencesFour good references for linear programming are1. Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization,Athena Scientific.2. Vaˇsek Chv´atal, Linear Programming, W.H. Freeman.3. George L. Nemhauser and Laurence A. Wolsey, Integer and Combinatorial Optimiza-tion, Wiley.4. Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algo-rithms and Complexity, Prentice Hall.I used some material from these sources in writing these notes. Also, some of the exerciseswere provided by Jon Lee and Francois Margot. Thanks in particular to Francois Margotfor many useful suggestions for improving these notes.Exercise 1.1 Find as many errors in these notes as you can and report them to me. ✷52 Exercises: Linear AlgebraIt is important to have a good understanding of the content of a typical one-semester un-dergraduate matrix algebra course. Here are some exercises to try. Note: Unless otherwisespecified, all of my vectors are column vectors. If I want a row vector, I will transpose acolumn vector.Exercise 2.1 Consider the product C = AB of two matrices A and B. What is the formulafor cij, the entry of C in row i,columnj? Explain why we can regard the ith row of C asa linear combination of the rows of B. Explain why we can regard the jth column of C asa linear combination of the columns of A. Explain why we can regard the ith row of C as asequence of inner products of the columns of B with a common vector. Explain why we canregard the jth column of C as a sequence of inner products of the rows of A with a commonvector. Consider the block matricesA BC DandE FG H.Assume that the number of columns of A and C equals the number of rows of E and F ,andthat the number of columns of B and D equals the number of rows of G and H. Describethe product of these two matrices. ✷Exercise 2.2 Associated with a matrix A are four vector spaces. What are they, how canyou find a basis for each, and how are their dimensions related? Give a “natural” basis forthe nullspace of the matrix [A|I], where A is an m × n matrix and I is an m × m identitymatrix concatenated onto A. ✷Exercise 2.3 Suppose V is a set of the form {Ax : x ∈ Rk},whereA is an n × k matrix.Prove that V is also a set of the form {y ∈ Rn: By = O} where B is an  × n matrix, andexplain how to find an appropriate matrix B. Conversely, suppose V is a set of the form{y ∈ Rn: By = O},whereB is an  × n matrix. Prove that V is also a set of the form{Ax : x ∈ Rk},whereA is an n × k matrix, and explain how to find an appropriate matrixA. ✷Exercise 2.4 Consider a linear system of equations, Ax = b. What are the various elemen-tary row operations that can be used to obtain an equivalent system? What does it meanfor two systems to be equivalent? ✷Exercise 2.5 Consider a linear system of equations, Ax = b. Describe the set of all solutionsto this system. Explain how to use Gaussian elimination to determine this set. Prove thatthe system has no solution if and only if there is a vector y such that yTA = OTand yTb =0.✷6Exercise 2.6 If x ∈ Rn, what is the definition of x1?Ofx2?Ofx∞?Forfixedmatrix A (not necessarily square) and vector b, explain how to minimize Ax − b2.Note:From now on in these notes, if no subscript appears in the notation x, then