Linear Programming NotesCarl W. LeeDepartment of MathematicsUniversity of KentuckyLexington, KY [email protected] 3, 1996Latest Revision: Fall 2003iContents1 References 12 Exercises: Linear Algebra 23 Introduction 53.1 Example...................................... 53.2 Definitions..................................... 63.3 BacktotheExample............................... 74 Exercises: Linear Programs 95 Theorems of the Alternatives 135.1 SystemsofEquations............................... 135.2 Fourier-Motzkin Elimination — A Starting Example . . . . . . . . . . . . . . 155.3 ShowingourExampleisFeasible ........................ 185.4 AnExampleofanInfeasibleSystem ...................... 195.5 Fourier-MotzkinEliminationinGeneral..................... 215.6 MoreAlternatives................................. 236 Exercises: Systems of Linear Inequalities 257 Duality 287.1 EconomicMotivation............................... 287.2 TheDualLinearProgram ............................ 297.3 TheDualityTheorems .............................. 317.4 CommentsonGoodCharacterization...................... 367.5 ComplementarySlackness ............................ 367.6 DualsofGeneralLP’s .............................. 377.7 GeometricMotivationofDuality ........................ 428 Exercises: Duality 449 The Simplex Method 509.1 BasesandTableaux................................ 509.2 Pivoting ...................................... 579.3 The(Primal)SimplexMethod.......................... 62ii10 Exercises: The Simplex Method 7411 The Simplex Method—Further Considerations 7811.1Uniqueness .................................... 7811.2RevisedSimplexMethod............................. 7811.3DualSimplexMethod .............................. 8111.4RevisedDualSimplexMethod.......................... 8311.5SensitivityAnalysis................................ 8511.5.1 RightHandSides............................. 8611.5.2 ObjectiveFunctionCoefficients ..................... 8811.5.3 NewVariable ............................... 9111.5.4 NewConstraint.............................. 9211.6LP’sWithEquations............................... 9311.7LP’sWithUnrestrictedVariables ........................ 9611.8 LP’s With Bounded Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 9611.9MinimizationProblems.............................. 10012 Exercises: More On the Simplex Method 10113 More On Linear Systems and Geometry 10313.1StructureTheorems................................ 10313.2ExtremePointsandFacets............................ 10614 Exercises: Linear Systems and Geometry 11415 Exercises: Some Formulations 12216 Networks 12517 Exercises: Networks 13118 Total Unimodularity 13519 Exercises: Total Unimodularity 139iii1 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. 212 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. 2Exercise 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. 2Exercise 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. 2Exercise 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? 2Exercise 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.22Exercise 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 the norm x 2is meant. 2Exercise 2.7 Consider a square n × n matrix A. What is the determinant of A?Howcan it be expressed as a sum with n! terms? How can it be expressed as an expansion bycofactors along an arbitrary row or column? How is it affected by the application of variouselementary row operations? How can it be determined by Gaussian elimination? What doesit mean for A to be singular?