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

11 mai 2008 · For instance, several assumptions are implicit in linear programing problems These assumptions are: 1 Proportionality The contribution of any 



Previous PDF Next PDF





[PDF] LINEAR PROGRAMMING MODELS

INDR 262 Optimization Models and Mathematical Programming Assumptions of Linear Programming 1 Proportionality: - contribution of each activity to the 



[PDF] Linear Programming

Assumptions of Linear Programming Models B6 Formulating Linear Linear programs make the following implicit assumptions 1 Slide along edge Y = 0 Y



[PDF] Linear Programming: Theory and Applications

11 mai 2008 · For instance, several assumptions are implicit in linear programing problems These assumptions are: 1 Proportionality The contribution of any 



[PDF] BASIC LINEAR PROGRAMMING CONCEPTS - Faculty Washington

11 mai 1998 · A problem can be realistically represented as a linear program if the following assumptions hold: 1 The constraints and objective function are 



[PDF] Linear Programming with Fuzzy Coefficients in Constraints - CORE

This paper studies a linear programming problem with fuzzy coefficients in are optimal solutions to (LSIP) and (DLSIP), respectively, then by the assumption



[PDF] Linear Programming Lecture Notes - Personal Psu

Simple Linear Programming Problems 13 1 Modeling Assumptions in Linear Programming 14 2 Graphically Solving Linear Programs Problems with Two 



A1 LINEAR PROGRAMMING AND OPTIMAL SOLUTIONS A2

1 The basic solution corresponding to an optimal basis is the optimal solution of linear programming (P) Proof It is easy to see that is a feasible solution to (P)



[PDF] 3 Introduction to Linear Programming

The following two sections present the general linear programming model and its basic assumptions Sections 3 4 and 3 5 give some additional examples of 



[PDF] Linear Programming - Savvas Learning Company

LP problems seek to maximize or minimize some quantity (usually profit or cost) We refer to this property as the objective function of an LP problem The major 



[PDF] Mathematical Programming - MIT

Since then, many additional techniques have been developed, which relax the assumptions of the linear- programming model and broaden the applications of 

[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

[PDF] astm e3 pdf download

[PDF] astm e3 pdf español

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

quotesdbs_dbs14.pdfusesText_20