Optimisation and Operations Research

1 Optimisation and Operations ResearchLecture 3: Linear ProgrammingMatthew of Mathematical Sciences,University of AdelaideJuly 12, 2017 Section 1 Linear ProgrammingMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20172 / 36 Linear equations and inequalitiesWe will need some tools to understand the shape of a region defined bylinear inequalitiesWe havenvariablesxi, sox RnWe haveminequalities defining the shape of thefeasibleregionAx b,whereIAis anm nmatrixIbis a lengthmcolumn vectorAlso we havennon-negativity constraintsx 0 Let s see what we can say/do about this that when we use or for vectors in this course, we mean, foreach element of the Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20173 / 36 The Feasible RegionThere are four possibilities.

2 The feasible region could beequal toRnIonly if there are no constraintsemptyIif the constraints leave no feasible pointsa subset ofRnIboundedIunboundedWe ll need to think about this a little more, but there is a problem we doknow something about: solving Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20174 / 36 Converting to standard formWe will always want to put problems into the standard form above, whichhasAx bIf you have any , then convert them to by multiplying the inequalityby 1 ExampleReplace2x 4y 3with 2x+ 4y 3 Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20175 / 36 Converting to standard formWe will always want to put problems into the standard form above, whichhasx 0If anyxiare free, replace by two new variablesx+i 0 andx i 0 suchthatxi=x+i x iMatthew Roughan (School of Mathematical Sciences, University of Adelaide)

3 OORIIJuly 12, 20176 / 36 Converting to standard formExamplemaxz=3x1+2x2subject to2x1+x2 5x1+3x2 7x1 0,x2freeand replace it withmaxz=3x1+2x+2 2x 2subject to2x1+x+2 x 2 5x1+3x+2 3x 2 7x1 0,x+2 0,x 2 0and when you finally obtain a solution, go back tox2=x+2 x 2 Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20177 / 36 Converting Inequalities to EquationsWe want to use 1st year maths in particular your experience with linearequations so we need to convert the inequalities into standard process is to introduce slack ,a11x1+a12x2+ +a1nxn b1becomesa11x1+a12x2+ +a1nxn+s1=b1wheres1is aslack constructions1 Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20178 / 36 Inequalities and EquationsIn matrix formA x bbecomesAx=bwhereA=[A I],x= x n sn + +m So now there aremequations andn=n + Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20179 / 36 InterpretationA x bmconstraints (inequalities)n variablesA is anm n matrixdefines a convexpolytopeofRn vertices are a feasibleintersection point ofmof theboundary planesnon-negativity restricts topositive quadrant Ax=bmconstraints (equalities)n=n +mvariablesAis anm nmatrixdefines ann dimensionalhyperplane inRn vertices are points wherethe hyperplane intersects axesIn =n mof the variablesare 0non-negativity restricts topositive quadrantMatthew Roughan (School of Mathematical Sciences, University of Adelaide)

4 OORIIJuly 12, 201710 / 36 Inequalities and Equationsn' = 2m = 1n = 3m = 12d hyperplanex1 + x2 1x1 + x2 + s3 = 1convexregionx1x2x1x2s3x1, x2 0x1, x2, s3 0 Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201711 / 36 Inequalities and EquationsWe need to become expert at converting back and forth betweenequalities and inequalities, and their you are on a boundary, it meansFeither a slack variable corresponding to an inequality is zeroExampleoriginal inequalityx+y 10slack variable equality formx+y+s=10on the boundarys= 0x+y=10 For one of thexi= 0 Ivertices are intersections of boundaries, so several variables must bezero, one for each boundary that s intersectingWe also need to see how to convert a LP back and forth betweenequality and inequality Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201712 / 36 Converting from equality to inequalityImagine we want to convert the equalityx+y= 10 Into an inequality form.

5 We can replace the equality withx+y 10x+y 10Or, in standard formx+y 10 x y 10 Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201713 / 36 Standard equality form of a LPThere are several alternatives we could end up with in all of theseconversions, so we choose one standard, that we will always aim (Standard equality form)An LP of the formmaxz=cTxsubject toAx=bx 0is said to be instandard equality Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201714 / 36 Standard equality form of a LPConverting to standard form1 Convert into standardinequalityformIthis isn t strictly necessary, but makes everything more consistent2 Convert inequalities into equalitiesIintroduce slack variablesIcoefficients ofccorresponding to slack variables are 03 Convert to amax1 Ieasy to convert by taking minz= max( z)Examplemaxz= 2x1+ 4x2is equivalent tominw= 2x1 4x21 Matlab slinprogworks withminproblems, so you need to know how to convert,backwards and Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201715 / 36 Converting a LPExampleLet us consider the LP.

6 Maxz=x1+x2subject tox1+2x2 6x1 x2 3x1 0,x2 write this as a system of linear equations, by introducing 2 slackvariablesx3andx4, and leaving the objective unchangedmaxz=x1+x2subject tox1+ 2x2+x3= 6x1 x2+x4= 3x1 0,x2 0,x3 0,x4 we often don t use special notation for the slack Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201716 / 36 Basic feasible solutionRemember from lecture 2 Definition (Basic solution)Abasic solutiontoAx=bis a solution with at leastn mzero can add to this:Definition (Basic feasible solution)If a basic solution satisfiesx 0, then it is called abasic feasible is, the solution is feasible if it also satisfies the non-negativityrequirements (for the original variables, and the slack variables).Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201717 / 36 Extreme PointsWe already know that the feasible set for a LP (in inequality form) is aconvex set.

7 We can add to thisDefinition (Extreme points)We sayx Sis anextreme pointof convexsetSifx= y+ (1 )zfory,z Sand 0< <1 impliesx=y= this means that extreme points arenot in the interior of any line segment insidethe a convex polytope (such as defined byA x b,x 0 ) the extremepoints are the Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201718 / 36 Geometry of linear programming solutionsTheoremIf an LP has a finite optimum, it has an optimum at an extreme point ofthe feasible LP problems the feasible set will always have a finite number ofextreme points (vertices). This suggests a na ve algorithm:1 Find all the vertices of the feasible set2 Choose the Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201719 / 36 How do we find vertices?

8 TheoremThe basic feasible solutions ofAx=bare the extreme points of thefeasible setA x b,x 0 .Unfortunately, we can not typically identify which basic solutions will befeasiblea priori( ,which are vertices)New na ve algorithm1 Find all the basic solutions2 Test to see if they are feasible3 Choose the optimum of the basic feasible solutionsSomehow we also need to check for boundedness at the same Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201720 / 36 ExampleExample (cont.) (2,2), f=10(0,3), f=9(0,0), f=0(4,0), f=8(2,2), f=10maximize f = 2x + 3ysubject to 2x + 4y 12 x + y 4 x 0 y 0 Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201721 / 36 Section 2 RankMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201722 / 36 Linear equations and redundancyGivenAx=b, whereAis of sizem nnvariables (unknowns)mequations (pieces of information)Na vely we havempieces of information, andnvariables, so we mightexpect a unique solution form n.

9 However, some pieces of information(equations) might be two rows are the same, then they don t provide any extra informationIif one row is a scalar multiple of another, then it doesn t provide anyextra information, ,x1+x2= 32x1+ 2x2= 6how do we assess redundancy in general?Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201723 / 36 RankDefinition (Rank)The rank of a matrixAis the number of linearly-independent matrix is full-rank if it has the maximum rank for its size (the minimumofnandmfor anm nmatrix).aThere are actually several equivalent definitions of this is defined for any matrix: so we can use it forIrank(A) the rank of the constraint coefficient matrixIrank(M) the rank of the augmented matrixM= [A|b]they won t necessarily have the same rank, butrank(A) rank(M)because when we add a column the rank either increases by 1, orstays the Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201724 / 36 Rank exampleExampleA= 12 1 2 3 135 0 Therank(A) = 2R3=R1 R2so the 3 rows are linearly dependentany pair of two rows is linearly independentNow add columnsM= [A|b]M1= 12 12 2 3 1435 0 1 andM2= 12 12 2 3 1335 0 1 Thenrank(M1) = 3 andrank(M2) = 2 Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201725 / 36 Ranks and numbers of solutionsTheorem (Rouch e-Capelli)

10 A system of linear equationsAx=bhas a solution iff the ranks of itscoefficient matrixAand its augmented matrixM= [A|b]are there are solutions, they form an affine subspaceaofRnof dimensionn rank(A)where there this is just a linear subspace translated away from the :rank(A) =rank([A|b]) =n, there will be a unique solutionrank(A) =rank([A|b])<n, infinite solutionsrank(A)6=rank([A|b]),no solutionsMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201726 / 36 Full-rankIf the matrixAis less than full rank, and the equations are consistent(there is at least one solution) we can reduce the set of equationsdown to a new set of full rankIsome LP pre-processors do just thisWhen we go fromA x btoAx=bwe addmslack variables, andan identity matrix toA, ,A= [A |Im].