[PDF] [PDF] Linear Programming: Theory and Applications

[PDF] Linear Programming: Theory and Applications

11 mai 2008 · For instance, several assumptions are implicit in linear programing The example of a canonical linear programming problem from the 

[PDF] LINEAR PROGRAMMING MODELS

A Linear programming problem can be expressed in the following standard form: max z= c1x1+ Assumptions of Linear Programming 1 Examples of LP

[PDF] BASIC LINEAR PROGRAMMING CONCEPTS - Faculty Washington

11 mai 1998 · Linear programming is a mathematical technique for finding optimal solutions to problems cases, where, for example, the variables might represent the levels of a set The Fundamental Assumptions of Linear Programming

[PDF] Linear Programming

tion Models B5 Assumptions of Linear Programming Models B6 The following example shows how an operational problem can be represented and analyzed 

[PDF] LINEAR PROGRAMMING - ResearchGate

We now present examples of four general linear programming problems Under this assumption, the inequalities in constraints (2) and (3) must be satisfied

[PDF] LINEAR PROGRAMMING - NPTEL

example, let us assume that the revenue per table is 120 and revenue per chair is 70 define a Linear Programming problem, state the assumptions, introduce  

[PDF] Introduction to Linear Programming

For example, the objective function coefficient for x1 is 3, and the objec- Does the Dorian model meet the four assumptions of linear programming outlined in

[PDF] 101 Types of Constraints and Variables in Linear Programming

10 2 "Violations" of the Algorithmic Assumptions as well as LP assumptions 10 1 Types of Constraints and For example, a LP formulation of an automobile

[PDF] I Developing Linear and Integer Programming models

too many wild assumptions, in the form of an LP then you know you can get a The presentation below is given in terms of the following constraint types:

[PDF] Présentation PowerPoint

4 sept 2018 · Resolution based on Linear Programming – use case o Assumptions: 4 tramways, 1 sub-system per tramway for predictive maintenance

[PDF] assumptions of linear programming problem

[PDF] assumptions of linear programming slideshare

[PDF] assumptions of linear programming with examples

[PDF] assurance accident de travail france

[PDF] assurance étudiant étranger

[PDF] assurance qualité pharmaceutique et biotechnologique emploi

[PDF] ast manulife

[PDF] ast shares

[PDF] ast transfer shares

[PDF] ast2 apple

[PDF] astfinancial com ca en login

[PDF] astm a890

[PDF] astm a995 gr 5a

[PDF] astm e112

[PDF] astm e3 11(2017) pdf

LinearProgramming:TheoryandApplications

CatherineLewis

May11,2008

1

Contents

1IntroductiontoLinearProgramming3

2ExamplesfromBazaraaet.al.andWinston11

3TheTheoryBehindLinearProgramming17

4AnOutlineoftheProof20

et.al.22

6ToolsforSolvingLinearPrograms23

7TheSimplexMethodInPractice25

9Cycling33

10SensitivityAnalysis39

1

11CaseStudy:BusingChildrentoSchool41

12Conclusion57

2

1IntroductiontoLinearProgramming

exploreditsapplications[1]. fewexamplesrelatedtotheGRT. studyinSection11.

1.1Whatisalinearprogram?

3

Minimizec1x1+c2x2++cnxn=z

Subjecttoa11x1+a12x2++a1nxn=b1

a

21x1+a22x2++a2nxn=b2

a m1x1+am2x2++amnxn=bm x

1;x2;:::;xn0:

Minimize4x1+x2=z

Subjectto3x1+x210

x 1+x25 x 13 x

1;x20:

programmustliewithintheshadedregion. 4 x

1+x2=5,wherex1=3andx2=2.

1.2Assumptions

problems.Theseassumptionsare: 5 valueof4x1,nomoreorless.

1.3ManipulatingaLinearProgrammingProblem

desiredform. 6 replacingthisvariablexjwithx0 jx00 jwherex0 j;x00 j0;theproblemtsthe canonicalform. functionforamaximizationproblem maxz=min(z):

1.4TheLinearAlgebraofLinearProgramming

acanonicalproblemis:

Minimizec1x1+c2x2++cnxn=z

Subjecttoa11x1+a12x2++a1nxn=b1

a

21x1+a22x2++a2nxn=b2

a m1x1+am2x2++amnxn=bm x

1;x2;:::;xn0:

Minimize

Pn j=1cjxj=z

SubjecttoPn

j=1ajxj=b x j0j=1;2;:::;n: or,morecompactly,

Minimizecx=z

SubjecttoAx=b

x0; 7 analysis,whichwillbediscussedinSection9.

1.5ConvexSetsandDirections

program. convexset. andinvalidonanother. A B 12 8

2(0;1):

dene oftheset. 9 feasibleregion. 10

2ExamplesfromBazaraaet.al.andWinston

linearprogram.

2.1Examples

11 gram,recallthat: jxj=maxfx;xg:

SubjecttoP1(x13)

P 1x13 P 2(x2) P 2x2 P

3(x11)

P 3x11 P

4(x24)

P 4x24 P

5(x1+2)

P 5x1+2 P

6(x21)

P 6x21 P 7(x1) P 7x1 P

8(x2+3)

P 8x2+3 allvariables0: machine.Theobjectivefunctionre ectsthedesiretominimizetotaldis- 12 theendofquarter4. dened.Ifwelet P W I theobjectivefunctionistherefore 13 P1600 I

1=P1600

I

2=I1+P2300

I

3=I2+P3800

I

4=I3+P4100=0:

expression: I n=In1+PnDn ustheconstraints P

150W1+50W3+50W4

P

250W2+50W4+50W1

P

350W3+50W1+50W2

P

450W4+50W3+50W2

betheoptimalvalue,andnotvaryyeartoyear. 14 w ik=tonsofwastemovedfromitok;1im;1kK y and0otherwise,1kK x kj=tonsofwastemovedfromktoj;1kK;1jn is: minz=X iX kc ikwik+X kX jckjxkj+X kf kyk+X kX i kwik: X iw ik=X jx kj: amountmovedtoallthetransferfacilities: X kw ik=X ia i: 15 gives:X kx kjbjandX iw ikqk:

Minimizez=P

iP kcikwik+P kP jckjxkj+P kfkyk+P kP ikwik

SubjecttoP

iwik=P jxkjP kwik=P iaiP kxkjbjP iwikqk allvariables0: solvingthisproblem.

2.2Discussion

program:minimizecxsubjecttoAxb,x0: (wherexn+1=0)butitmaynowalsoincludemore. equal0atoptimality. 16 thesame. becomeslessoptimal.

3TheTheoryBehindLinearProgramming

3.1Denitions

andtheoremsarenecessary. wherepisanonzerovectorinRnandkisascalar. canbeplottedonthex1x2-plane. planetomoredimensions. orfx:pxkg. hyperplanex1=2. halfspaceiseverythingononesideofaaplane. 17 matrix(wheremandnareintegers). faceofthepuptent. 18 hyperplanesofX. inthenextsection.

3.2TheGeneralRepresentationTheorem

x x=kX j=1 jxj+lX j=1 jdj k X j=1 j=1; j0;j=1;2;:::;k j0;j=1;2;:::;l: 19 directions.

4AnOutlineoftheProof

nis nite,sothenumberofextremepointsisnite. extremepoints.

Next,thebackwardsproof:

pointxthatcanbewrittenasinEquationGRT.

WanttoProve:x2X.

20 Ax=kX j=1 jAxj+lX j=1 jAdj:

ItisclearthatPk

j=1Axjislessthanb(sinceeachxjisinX)and thereforePk j=1jAxjbsincePk j=1j=1.

ButwhataboutPl

j=1jAdj?Fromthedenitionofextremedirec- restrictionsond:

A(x+d)b

x+d0(1) havenegativecomponents).Therefored>0.

Fromthisinformation,itisclearthatPl

j=1jAdjislessthan0. allpositivenumbers,thismustbetrue. forwarddirection: X. thatset. 21
thenewboundedset). resultoftheGRT. polyhedralset.Itisfrom[2].

5ExamplesWithConvexSetsandExtremePoints

FromBazaaraet.al.

respectively.PointA,7

3;23,isfoundbysolvingx1x2=3and2x1+x2=4

simultaneously. necessarytosolvefor1and2suchthat

3132+7

3(112)=1

61+1022

3(112)=0:

22
2

7A1156B2956C=(1;0)

Minimizecx=z

SubjecttoAx=b

x0 thatAw=b:

Aw=A(y+(1)z)

=Ay+AzAz =b+bb =b:

6ToolsforSolvingLinearPrograms

6.1ImportantPrecursorstotheSimplexMethod

forunderstandingtheSimplexalgorithm. 23
x B x N# thenxisadegeneratebasicsolution[2].

Minimizecx

SubjecttoAx=b

x0: isnotempty[2]. exists[2]. referstothesetofbasicvariables. anassociatedbasisareidenticallyzero[2]. 24
n m! programs.

7TheSimplexMethodInPractice

whenthesystemisatoptimality.

Maximizecx

SubjecttoAxb

x0 theinitialtableauwouldlooklike: 25
zc0 0Ab: objectivefunctioncoecient,say,columni. asthenewbasicvariableentersthebasis. thebasis. (foraminimizationproblem). 26
columnisinRow1.

Rowzx1x2s1s2RHSBVratio

013-8000z=0-

10421012s1=1212

4=32023016s2=66

2=3 followingLP: minz=3x1+8x2 s.t.4x1+2x212

2x1+3x26

x 1;x20 ourlinearprogramto minz=3x1+8x2 s.t.4x1+2x2+s1=12

2x1+3x2+s2=6

x

1;x2;s1;s20

wegivetheratiosusedintheratiotest. 27
zcolumn)arenonpositive.

Rowzx1x2s1s2RHSBVratio

010192340-9z=9-

101121403x1=3-

20021210s2=0-

Row1toRow2.

z=9: identitymatrix.

8WhatifthereisnoinitialbasisintheSimplex

tableau? right-hand-sidevariablewouldbenegative. 28

Table3:1-21-1000

021-2018

04-12002

023-1-104

Table4:100000-1-10

021-201008

04-1200102

023-1-10014

inthefollowingsections.

8.1TheTwo-PhaseMethod

Considerthefollowingproblem:

Maximize2x1x2+x3

Subjectto2x1+x22x38

4x1x2+2x3=2

2x1+3x2x34

x

1;x2;x30:

e tableaushowninTable4. 29

Table5:1621-10006

021-201008

04-1200102

023-1-10014

Table6:100.6-.30-.8-1.4.8

000-2.6.21-.25.26.4

010.3-.10.2.10.8

001-.8-.40-.2.41.2

variablesx1,x2ands1arebasic. steps: inwhichtherearenoslackvariables. arezero. 30

Table7:1-21-1000

000-2.6.216.4

010.3-.10.8

001-.8-.401.2

100.4.20.4

000-2.6.216.4

010.3-.10.8

001-.8-.401.2

jectivefunction.ThisisthestartofPhaseII. arezero.

8.2TheBig-MMethod

Considertheproblem

Minimizex12x2

Subjecttox1+x22

x1+x21 x 23
x

1;x20:

thatpossible. 31

Table8:1-120000

011-1002

0-110-101

0010013

Table9:1-12000000

011-100102

0-110-10011

001001003

1-12000-M-M0

011-100102

0-110-10011

001001003

1-12+2M-M-M0003M

011-100102

0-110-10011

001001003

11+2M0-M2+M00-2-2M-2+M

020-1101-11

0-110-10011

0100110-12

1-1000-2-M-M-6

0100110-12

001001003

0-10101-101

32
exceptwithavariableM x

2=3;x3=1;x4=2andz=6.

inwhichtherearenoslackvariables. andxaisavectorofthearticialvariables. arezero.

4.CompletetheSimplexalgorithmasusual.

objectivefunctionvalueshouldbenite.

9Cycling

33
phenomenonisaptlycalled\cycling." tableauisthesameastherst. thatpreventitsoccurrence.

9.1TheLexicographicMethod

Giventheproblem

Minimizecx

SubjecttoAx=b

x0; I 0= r:br yrk=Minimum1imbiyik:yik>0

3.FormthesetI1suchthat

I 1= r:yr1 yrk=Minimumi2I0yi1yik:yik>0 newratioisatie. 34

Table10:Anexampleofcycling.

1000.75-20.5-60

0100.25-8-190

quotesdbs_dbs20.pdfusesText_26