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] 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
1Contents
1IntroductiontoLinearProgramming3
2ExamplesfromBazaraaet.al.andWinston11
3TheTheoryBehindLinearProgramming17
4AnOutlineoftheProof20
et.al.226ToolsforSolvingLinearPrograms23
7TheSimplexMethodInPractice25
9Cycling33
10SensitivityAnalysis39
111CaseStudy:BusingChildrentoSchool41
12Conclusion57
21IntroductiontoLinearProgramming
exploreditsapplications[1]. fewexamplesrelatedtotheGRT. studyinSection11.1.1Whatisalinearprogram?
3Minimizec1x1+c2x2++cnxn=z
Subjecttoa11x1+a12x2++a1nxn=b1
a21x1+a22x2++a2nxn=b2
a m1x1+am2x2++amnxn=bm x1;x2;:::;xn0:
Minimize4x1+x2=z
Subjectto3x1+x210
x 1+x25 x 13 x1;x20:
programmustliewithintheshadedregion. 4 x1+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
a21x1+a22x2++a2nxn=b2
a m1x1+am2x2++amnxn=bm x1;x2;:::;xn0:
Minimize
Pn j=1cjxj=zSubjecttoPn
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 82(0;1):
dene oftheset. 9 feasibleregion. 102ExamplesfromBazaraaet.al.andWinston
linearprogram.2.1Examples
11 gram,recallthat: jxj=maxfx;xg:SubjecttoP1(x13)
P 1x13 P 2(x2) P 2x2 P3(x11)
P 3x11 P4(x24)
P 4x24 P5(x1+2)
P 5x1+2 P6(x21)
P 6x21 P 7(x1) P 7x1 P8(x2+3)
P 8x2+3 allvariables0: machine.Theobjectivefunctionre ectsthedesiretominimizetotaldis- 12 theendofquarter4. dened.Ifwelet P W I theobjectivefunctionistherefore 13 P1600 I1=P1600
I2=I1+P2300
I3=I2+P3800
I4=I3+P4100=0:
expression: I n=In1+PnDn ustheconstraints P150W1+50W3+50W4
P250W2+50W4+50W1
P350W3+50W1+50W2
P450W4+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 ikwikSubjecttoP
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. 21thenewboundedset). resultoftheGRT. polyhedralset.Itisfrom[2].
5ExamplesWithConvexSetsandExtremePoints
FromBazaaraet.al.
respectively.PointA,73;23,isfoundbysolvingx1x2=3and2x1+x2=4
simultaneously. necessarytosolvefor1and2suchthat3132+7
3(112)=1
61+1022
3(112)=0:
222
7A1156B2956C=(1;0)
Minimizecx=z
SubjecttoAx=b
x0 thatAw=b:Aw=A(y+(1)z)
=Ay+AzAz =b+bb =b:6ToolsforSolvingLinearPrograms
6.1ImportantPrecursorstotheSimplexMethod
forunderstandingtheSimplexalgorithm. 23x B x N# thenxisadegeneratebasicsolution[2].
Minimizecx
SubjecttoAx=b
x0: isnotempty[2]. exists[2]. referstothesetofbasicvariables. anassociatedbasisareidenticallyzero[2]. 24n m! programs.
7TheSimplexMethodInPractice
whenthesystemisatoptimality.Maximizecx
SubjecttoAxb
x0 theinitialtableauwouldlooklike: 25zc0 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+2x2122x1+3x26
x 1;x20 ourlinearprogramto minz=3x1+8x2 s.t.4x1+2x2+s1=122x1+3x2+s2=6
x1;x2;s1;s20
wegivetheratiosusedintheratiotest. 27zcolumn)arenonpositive.