Chapter 9 Linear programming

1 Chapter 9 Linear programmingThe nature of the programmes a computer scientist has to conceive often requires some knowl-edge in a specific domain of application, for example corporate management, network proto-cols, sound and video for multimedia streaming,.. Linear programming is one of the necessaryknowledges to handle optimization problems. These problems come from varied domains asproduction management, economics, transportation network planning, .. For example, one canmention the composition of train wagons, the electricity production, or the flight planning byairplane of these optimization problems do not admit an optimal solution that can be computedin a reasonable time, that is in polynomial time (See Chapter 3). However, we know how to ef-ficiently solve some particular problems and to provide an optimal solution (or at least quantifythe difference between the provided solution and the optimal value) by using techniques fromlinear fact, in 1947, Dantzig conceived the Simplex Method to solve military planningproblems asked by the US Air Force that were written as a Linear programme, that is a systemof Linear equations.

2 In this course, we introduce the basic concepts of Linear programming . Wethen present the Simplex Method, following the book of V. Chv atal [2]. If you want to readmore about Linear programming , some good references are [6, 1].The objective is to show the reader how to model a problem with a Linear programme whenit is possible, to present him different methods used to solve it or at least provide a good ap-proximation of the solution. To this end, we present thetheory of dualitywhich provide waysof finding good bounds on specific also discuss the practical side of Linear programming : there exist very efficient toolsto solve Linear programmes, CPLEX [3] and GLPK [4]. We present the different stepsleading to the solution of a practical problem expressed as a Linear IntroductionAlinear programmeis a problem consisting in maximizing or minimizing a Linear functionwhile satisfying a finite set of Linear 9.

3 Linear PROGRAMMINGL inear programmes can be written under thestandard form:Maximize nj=1cjxjSubject to: nj=1aijxj bifor all 1 i mxj 0 for all 1 j n.( )All constraints are inequalities (and not equations) and all variables are non-negative. Thevariablesxjare referred to asdecision variables. The function that has to be maximized iscalled the problemobjective that a constraint of the form nj=1aijxj bimay be rewritten as nj=1( aij)xj bi. Similarly, a minimization problem may be transformed into a maximization problem:minimizing nj=1cjxjis equivalent to maximizing nj=1( cj)xj. Hence, every maximizationor minimization problem subject to Linear constraints can be reformulated in the standard form(See Exercices and ).An-tuple(x1,..,xn)satisfying the constraints of a Linear programme is afeasible solutionof this problem. A solution that maximizes the objective function of the problem is called anoptimal solution.

4 Beware that a Linear programme does not necessarily admits a unique optimalsolution. Some problems have several optimal solutions while others have none. The later casemay occur for two opposite reasons: either there exist no feasible solutions, or, in a sense, thereare too many. The first case is illustrated by the following 3x1 x2 Subject to:x1+x2 2 2x1 2x2 10x1,x2 0( )which has no feasible solution (See Exercise ). Problems of this kind are referred to asunfeasible. At the opposite, the problemMaximizex1 x2 Subject to: 2x1+x2 1 x1 2x2 2x1,x2 0( )has feasible solutions. But none of them is optimal (See Exercise ). As a matter of fact, forevery numberM, there exists a feasible solutionx1,x2such thatx1 x2>M. The problemsverifying this property are referred to asunbounded. Every Linear programme satisfies exactlyone the following assertions: either it admits an optimal solution, or it is unfeasible, or it set of points in IRnat which any single constraint holds with equality is a hyperplane inIRn.

5 Thus each constraint is satisfied by the points of a closed half-space of IRn, and the set offeasible solutions is the intersection of all these half-spaces, a convex the objective function is Linear , its level sets are hyperplanes. Thus, if the maximumvalue ofcxoverPisz , the hyperplanecx=z is a supporting hyperplane ofP. Hencecx=z contains an extreme point (a corner) ofP. It follows that the objective function attains itsmaximum at one of the extreme points THE SIMPLEX The Simplex MethodThe authors advise you, in a humanist elan, to skip this section if you are not ready to suffer. Inthis section, we present the principle of the Simplex Method. We consider here only the mostgeneral case and voluntarily omit here the degenerate cases to focus only on the basic more complete presentation can be found for example in [2]. A first exampleWe illustrate the Simplex Method on the following example:Maximize 5x1+4x2+3x3 Subject to:2x1+3x2+x3 54x1+x2+2x3 113x1+4x2+2x3 8x1,x2,x3 0.

6 ( )The first step of the Simplex Method is to introduce new variables calledslack justify this approach, let us look at the first constraint,2x1+3x2+x3 5.( )For all feasible solutionx1,x2,x3, the value of the left member of ( ) is at most the valueof the right member. But, there often is a gap between these two values. We note this gapx4. Inother words, we definex4=5 2x1 3x2 x3. With this notation, Equation ( ) can now bewritten asx4 0. Similarly, we introduce the variablesx5andx6for the two other constraints ofProblem ( ). Finally, we use the classic notationzfor the objective function 5x1+4x2+ summarize, for all choices ofx1,x2,x3we definex4,x5,x6andzby the formulasx4=5 2x1 3x2 x3x5=11 4x1 x2 2x3x6=8 3x1 4x2 2x3z=5x1+4x2+3x3.( )With these notations, the problem can be written as:Maximizezsubject tox1,x2,x3,x4,x5,x6 0.( )The new variables that were introduced are referred asslack variables, when the initialvariables are usually called thedecision variables.

7 It is important to note that Equation ( )define an equivalence between ( ) and ( ). More precisely: Any feasible solution(x1,x2,x3)of ( ) can be uniquely extended by ( ) into a feasiblesolution(x1,x2,x3,x4,x5,x6)of ( ).132 Chapter 9. Linear programming Any feasible solution(x1,x2,x3,x4,x5,x6)of ( ) can be reduced by a simple removal ofthe slack variables into a feasible solution(x1,x2,x3)of ( ). This relationship between the feasible solutions of ( ) and the feasible solutions of ( )allows to produce the optimal solution of ( ) from the optimal solutions of ( ) Simplex strategy consists in finding the optimal solution (if it exists) by successiveimprovements. If we have found a feasible solution(x1,x2,x3)of ( ), then we try to find anew solution( x1, x2, x3)which is better in the sense of the objective function:5 x1+4 x2+3 x3 5x1+4x2+ repeating this process, we obtain at the end an optimal start, we first need a feasible solution.

8 To find one in our example, it is enough to setthe decision variablesx1,x2,x3to zero and to evaluate the slack variablesx4,x5,x6using ( ).Hence, our initial solution,x1=0,x2=0,x3=0,x4=5,x5=11,x6=8( )gives the resultz= now have to look for a new feasible solution which gives a larger value forz. Findingsuch a solution is not hard. For example, if we keepx2=x3=0 and increase the value ofx1,then we obtainz=5x1 0. Hence, if we keepx2=x3=0 and if we setx1=1, then we obtainz=5 (andx4=3,x5=7,x6=5). A better solution is to keepx2=x3=0 and to setx1=2;we then obtainz=10 (andx4=1,x5=3,x6=2). However, if we keepx2=x3=0 and ifwe setx1=3, thenz=15 andx4=x5=x6= 1, breaking the constraintxi 0 for alli. Theconclusion is that one can not increasex1as much as one wants. The question then is: how muchcanx1be raised (when keepingx2=x3=0) while satisfying the constraints (x4,x5,x6 0)?The conditionx4=5 2x1 3x2 x3 0 impliesx1 52.

9 Similarly,x5 0 impliesx1 114andx6 0 impliesx1 83. The first bound is the strongest one. Increasingx1to this boundgives the solution of the next step:x1=52,x2=0,x3=0,x4=0,x5=1,x6=12( )which gives a resultz=252improving the last valuez=0 of ( ).Now, we have to find a new feasible solution that is better than ( ). However, this taskis not as simple as before. Why? As a matter of fact, we had at disposal the feasible solutionof ( ), but also the system of Linear equations ( ) which led us to a better feasible , we should build a new system of Linear equations related to ( ) in the same way as ( )is related to ( ).Which properties should have this new system? Note first that ( ) express the strictlypositive variables of ( ) in function of the null variables. Similarly, the new system has toexpress the strictly positive variables of ( ) in function of the null variables of ( ):x1,x5,x6(andz) in function ofx2,x3andx4.

10 In particular, the variablex1, whose value just THE SIMPLEX METHOD133from zero to a strictly positive value, has to go to the left side of the new system. The variablex4, which is now null, has to take the opposite build this new system, we start by puttingx1on the left side. Using the first equation of( ), we writex1in function ofx2,x3,x4:x1=52 32x2 12x3 12x4( )Then, we expressx5,x6andzin function ofx2,x3,x4by substituting the expression ofx1given by ( ) in the corresponding lines of ( ).x5=11 4 52 32x2 12x3 12x4 x2 2x3=1+5x2+2x4,x6=8 3 52 32x2 12x3 12x4 4x2 2x3=12+12x2 12x3+32x4,z=5 52 32x2 12x3 12x4 +4x2+3x3=252 72x2+12x3 the new system isx1=52 32x2 12x3 12x4x5=1+5x2+2x4x6=12+12x2 12x3+32x4z=252 72x2+12x3 52x4.( )As done at the first iteration, we now try to increase the value ofzby increasing a rightvariable of the new system, while keeping the other right variables at zero.