[PDF] [PDF] Chapter 9 Linear programming

[PDF] Finding feasible solutions to a LP

basic feasible solution: put the slack variables on the left hand side How- ever, this is not always the case, especially for minimization problems, or problems 

[PDF] Finding feasible solutions to a LP In all the examples we have seen

Forget for a minute that the solution is obvious If we try to use simplex, we will first convert it to a max problem and negate the objective function maximize −x

A1 LINEAR PROGRAMMING AND OPTIMAL SOLUTIONS A2

A nonnegative vector of variables that satisfies the constraints of (P) is called a feasible solution to the linear programming problem A feasible solution that minimizes the objective function is called an optimal solution

[PDF] Solving Linear Programs - MIT

simplex method, proceeds by moving from one feasible solution to another, at each step how the optimal solution varies as a function of the problem data ( cost 

[PDF] Lecture 11 1 Example of the Simplex Method

30 sept 2014 · Given a basic feasible solution x with corresponding basis B, we first To apply the simplex method, convert it to a standard form problem by 

[PDF] LECTURE NOTES ON LINEAR PROGRAMMING Pre-requisites

The set of all feasible solutions of an L P P is a convex set The objective Transportation and Assignment problem and their optimal solutions Inventory 

[PDF] Glossary of terms Basic feasible solutions - USNA

The decision variables are the n-dimensional vector x Note that the objective can be minimization or maximization Combinatorial Optimization Problem: A 

[PDF] Chapter 9 Linear programming

Reciprocally, any feasible solution of the primal provides a lower bound on the optimal value of the dual problem Actually, if one of both problems admits an 

[PDF] The Graphical Simplex Method: An Example

Feasible to augmented problem is feasible to original Consider the feasible solution (x1,x2,s1,s2,s3,s4) = (0,0,6,3,5,4) to the augmented problem 2 · 0 +3 · 0 +6

[PDF] a feasible solution to linear programming problem should

[PDF] a final class can be abstract

[PDF] a final class can be extended

[PDF] a final class can be extended. true false

[PDF] a final class can have subclass i.s. it can be extended

[PDF] a final method can be inherited

[PDF] a first course in graph theory pdf

[PDF] a fois b au carré

[PDF] a for apple to z for

[PDF] a for apple to z for zebra chart

[PDF] a for apple to z for zebra images

[PDF] a for apple to z for zebra pictures

[PDF] a for apple to z for zebra spelling

[PDF] a for apple to z tak

[PDF] a friendly introduction to numerical analysis pdf

Chapter9

Linearprogramming

Thenatureof theprogrammesa computerscientisthas toconceiv eoften requiressomekno wl- edgeina specificdomainof application,fore xamplecorporatemanagement, networkproto- cols,soundand videofor multimediastreaming,.. .Linearprogrammi ngisone ofthenecessary knowledgestohandleoptimizationproblems. Theseproblems comefromv arieddomainsas productionmanagement,economics ,transportationnetw orkplanning,...F ore xample,onecan mentionthecomposition oftrainw agons,theelectricity production,orthe flightplanning by airplanecompanies. Mostofthese optimizationproblemsdo notadmitan optimalsolution thatcan becomputed inareasonable time,thatis inpolynomial time(SeeChapter 3).Howe ver, weknow howto ef- ficientlysolve someparticularproblemsandtopro videanoptimal solution(or atleastquantify thedifference betweentheprovidedsolutionand theoptimalv alue)byusing techniquesfrom linearprogramming. Infact, in1947,G.B.Dantzigconcei vedth eSimplex Methodtosolv emilitaryplanning problemsasked bytheUSAirF orcethatwere writtenasa linearprogramme,that isasystem oflinear equations.Inthiscourse,we introducethebasic conceptsoflinear programming.We thenpresentthe SimplexMethod, followingthe bookofV.Chv´atal[2].If youwant toread moreaboutlinear programming,somegood referencesare [6,1]. Theobjectiv eistoshowthereaderhow tomodela problemwitha linearprogrammewhen itispossible, topresenthim differentmet hodsusedto solveit orat leastprovideagoodap- proximationofthe solution.T othisend, wepresentthe theoryofduality whichprovide ways offindinggood boundsonspecific solutions. Wealsodiscussthepractical sideoflinear programming:theree xistvery efficient tools tosolve linearprogrammes,e.g.CPL EX[3] andGL PK [4].Wepresentthedifferentsteps leadingtothe solutionofa practicalproblem expressedas alinearprogramme.

9.1Introduction

Alinearpro grammeisaproblem consistinginmaximizing orminimizing alinearfunction whilesatisfyinga finiteset oflinearconstraints. 129

130CHAPTER9.LINEAR PROGRAMMING

Linearprogrammescan bewrittenunder thestandardform:

Maximize∑

n j=1 c j x j

Subjectto:∑

n j=1 a ij x j i x j (9.1) Allconstraintsare inequalities(andnot equations)andall variablesare non-neg ative. The variablesx j arereferred toasdecisionvariables .Thefunction thathasto bemaximizedis calledtheproblem objectivefunction.

Observethataconstraintof theform ∑

n j=1 a ij x j ≥b i maybere writtenas ∑ n j=1 (-a ij )x j -b i .Similarly, aminimizationproblemmaybetransformed intoamaximization problem: minimizing∑ n j=1 c j x j isequiv alenttomaximizing∑ n j=1 (-c j )x j .Hence,e verymaximizati on orminimization problemsubjecttolinearconstraintscan bereformulatedin thestandard form (SeeExercices 9.1and9.2.).

An-tuple(x

1 ,...,x n )satisfyingthec onstraintsofa linearprogrammeisafeasiblesolution ofthisproblem. Asolutionthat maximizestheobjecti vefunction ofthe problemiscalled an optimalsolution.Bew arethatalinearprogrammedoesnot necessarilyadmitsa uniqueoptimal solution.Someproblems have several optimalsolutionswhileothershavenone. Thelatercase mayoccurfor twoopposite reasons:eitherthere existnofeasiblesolutions,or ,in asense,there aretooman y.The firstcaseisillustratedbythefollowingproblem.

Maximize3x

1 -x 2

Subjectto:x

1 +x 2 -2x 1 -2x 2 x 1 ,x 2 ≥0 (9.2) whichhasno feasiblesolution(See Exercise 9.3).Problemsof thiskindare referredtoas unfeasible.Atthe opposite,theproblem

Maximizex

1 -x 2

Subjectto:-2x

1 +x 2 -x 1 -2x 2 x 1 ,x 2 ≥0 (9.3) hasfeasiblesoluti ons.Butnone ofthemisoptimal(SeeEx ercise9.3).As amatter offact, for everynumberM,theree xistsafeasible solutionx 1 ,x 2 suchthatx 1 -x 2 >M.Theproblems verifyingthispropertyarereferred toasunbounded.Every linearprogrammesatisfiesexactly onethefollo wingassertions:either itadmitsanoptimalsolution, oritis unfeasible,orit is unbounded.

Geometricinterpr etation.

Thesetof pointsin IR

n atwhichan ysingle constraintholdswithequalityisa hyperplanein IR n .Thuseach constraintissatisfied bythepoints ofaclosed half-spaceofI R n ,andthe setof feasiblesolutionsis theintersection ofallthese half-spaces,acon vex polyhedronP. Becausetheobjecti vefunction islinear,itslevelsetsare hyperplanes. Thus,ifthe maximum valueofcxoverPisz ,theh yperplanecx=z isasupporting hyperplaneof P.Hencecx=z containsane xtremepoint(a corner)ofP.Itfollo wsthatthe objectivefunctionattains its maximumatone ofthee xtremepoints ofP.

9.2.THESIMPLEX METHOD131

9.2TheSimplex Method

Theauthorsadvise you,ina humanist´elan,toskip thissection ifyouare notreadyto suffer. In thissection,we presenttheprinciple oftheSimple xMethod.W econsider hereonlythe most generalcaseand voluntarilyomit herethede generatecasestofocusonly onthebasic principle. Amorecomplete presentationcanbe foundfore xamplein[2].

9.2.1Afirst example

WeillustratetheSimplex Methodon thefollowing example:

Maximize5x

1 +4x 2 +3x 3

Subjectto:

2x 1 +3x 2 +x 3 4x 1 +x 2 +2x 3 3x 1 +4x 2 +2x 3 x 1 ,x 2 ,x 3 ≥0. (9.4) Thefirststep oftheSimple xMethodis tointroducene wvariables calledslackvariables. Tojustifythisapproach,let uslookat thefirstconstraint, 2x 1 +3x 2 +x 3

Forallfeasiblesolutionx

1 ,x 2 ,x 3 ,thev alueofthe leftmemberof(9.5)is atmostthe value oftheright member.But, thereoftenis agapbetweenthesetw ov alues.We notethisg apx 4 .In otherwords, wedefinex 4 =5-2x 1 -3x 2 -x 3 .With thisnotation,Equation(9.5)canno wbe writtenasx 4 ≥0.Similarly, weintroducethevariablesx 5 andx 6 forthetw oother constraintsof Problem(9.4).Finally ,we usetheclassicnotationzfortheobjecti vefunction 5x 1 +4x 2 +3x 3

Tosummarize,forallchoices ofx

1 ,x 2 ,x 3 wedefinex 4 ,x 5 ,x 6 andzbytheformulas x 4 =5-2x 1 -3x 2 -x 3 x 5 =11-4x 1 -x 2 -2x 3 x 6 =8-3x 1 -4x 2 -2x 3 z=5x 1 +4x 2 +3x 3 (9.6)

Withthesenotations,theproblem canbe writtenas:

Maximizezsubjecttox

1 ,x 2 ,x 3 ,x 4 ,x 5 ,x 6 ≥0.(9.7) Thenew variablesthatwereintroduced arereferredasslackvariables,whenthe initial variablesareusuallycalledthe decisionvariables.Itis importanttonote thatEquation(9.6) defineanequi valencebetween (9.4)and(9.7).Moreprecisely: •Anyfeasiblesolution(x 1 ,x 2 ,x 3 )of(9.4)can beuniquely extendedby (9.6)into afeasible solution(x 1 ,x 2 ,x 3 ,x 4 ,x 5 ,x 6 )of(9.7).

132CHAPTER9.LINEAR PROGRAMMING

•Anyfeasiblesolution(x 1 ,x 2 ,x 3 ,x 4 ,x 5 ,x 6 )of(9.7)can bereduced byasimple removal of theslackv ariablesinto afeasiblesolution(x 1 ,x 2 ,x 3 )of(9.4). •Thisrelationshipbetween thefeasible solutionsof(9.4) andthefeasible solutionsof(9.7) allowstoproducetheoptimal solutionof(9.4) fromtheoptimal solutionsof (9.7)and vice versa. TheSimplex strategyconsistsinfindingthe optimalsolution(ifitexists )by successive improvements.Ifwehavefound afeasiblesolution (x 1 ,x 2 ,x 3 )of(9.7),then wetryto finda newsolution(¯x 1 ,¯x 2 ,¯x 3 )whichisbetter inthesense oftheobjecti vefunction:

5¯x

1 +4¯x 2 +3¯x 3 ≥5x 1 +4x 2 +3x 3 Byrepeatingthis process,weobtain attheend anoptimalsolution. Tostart,wefirstneed afeasiblesolution. Tofind oneinour example, itisenough toset thedecisionv ariablesx 1 ,x 2 ,x 3 tozeroand toe valuatethe slackvariables x 4 ,x 5 ,x 6 using(9.6).

Hence,ourinitial solution,

x 1 =0,x 2 =0,x 3 =0,x 4 =5,x 5 =11,x 6 =8(9.8) givestheresultz=0. Wenowhav etolookfora newfeasiblesolutionwhichgivesa largerv alueforz.Finding suchasolution isnothard. For example,if wek eepx 2 =x 3 =0andincrease thevalue ofx 1 thenweobtain z=5x 1 ≥0.Hence,if wekeep x 2 =x 3 =0andif wesetx 1 =1,thenwe obtain z=5(andx 4 =3,x 5 =7,x 6 =5).Abetter solutionisto keepx 2 =x 3 =0andto setx 1 =2; wethenobtain z=10(andx 4 =1,x 5 =3,x 6 =2).Howe ver,ifwekeepx 2 =x 3 =0andif wesetx 1 =3,thenz=15andx 4 =x 5 =x 6 =-1,breakingthe constraintx i ≥0forall i.The conclusionisthatonecannotincreasex 1 canx 1 beraised(when keeping x 2 =x 3 =0)whilesatisfying theconstraints (x 4 ,x 5 ,x 6 ≥0)?

Theconditionx

4 =5-2x 1 -3x 2 -x 3 ≥0impliesx 1 5 2 .Similarly, x 5 ≥0impliesx 1 11 4quotesdbs_dbs20.pdfusesText_26