1、Management Science:Operations Research(OR)Chapter 2.3 2.41/10/20231LectureChapter 2.3:Graphical Representation and Solution TechniquelVariables are represented as dimensions,lconstraints are represented as lines(hyperplanes)for equations&halflines(halfspaces)for inequalities1/10/20232LectureExample:
2、3x1+2x2 6lNote:It is not true that“”define halfspaces below the hyperplane&“”constraints define halfspaces above the hyperplane.1/10/20233LectureExample:3x1+2x2 6lNote:If x1=0 and x2=0 Satisfies 6 ThenMark the halfspaces where(0,0)located as our desired halfspaces.Otherwise,Mark the other halfspaces
3、 as our desired halfspaces.1/10/20234LectureTesting with(0,0)x1=0 and x2=0 The feasible setlThe intersection of the halfspaces&hyperplanes of all constraints in the problemlExample:Max z =2x1+3x2 s.t.x1+4x2 12(I)2x1 x2 2(II)5x1+3x2 15(III)4x1+6x2 6(IV)x1 0(V)x2 0(VI)1/10/20235LectureThe shaded area
4、is the feasible set1/10/20236LectureSome observationslThe area is a polytope:a bounded polyhedronlExtreme points A,B,C,D,E,F.lAt each extreme point,some constraints are satisfied as equations.For instance;at C,constraints I&II are satisfied as equations;at F,constraint IV&x2 0.lExact coordinates of
5、extreme points are determined by a system of simultaneous linear equations.1/10/20237LecturelFor instance,at point A:Constraints IV and V are satisfied as equations,i.e.,4x1+6x2=6 x1 =0.lThe system has a solution(x1,x2)=(0,1).l At point C,the constraints I and II are binding,so that the system isx1+
6、4x2=12I2x1 x2=2.IIlThe system has a solution(x1,x2)=(4/9,26/9).1/10/20238LectureIn summaryPointBinding Constraints Coordinates(x1,x2)z-valueAIV,V(0,1)3BII,V(0,2)6CI,II (.4444,2.8889)9.5556DI,III (1.4118,2.6471)10.7649EIII,VI(3,0)6FIV,VI(1,0)3)2,(9894)2,1(17111771/10/20239LecturelNow the objective fu
7、nction:Max z=2x1+x2.The parameter z is called the value of the objective function(or simply objective value)lFor now,ignore“Max.”Then z=2x1+x2 is a constraint with unknown right-hand side value.1/10/202310LectureIso-profit(or iso-cost)lines,contour linesThe gradient(or direction)of the objective fun
8、ction is perpendicular to the iso-profit lines.1/10/202311LectureHow to find the gradient?Examples:(a)Max z1=4x1 3x2(b)Max z2=x1+3x2(c)Min z3=2x1 x2(d)Min z4=2x1+3x2 1/10/202312LectureGraphical solution procedurel(1)Graph the constraints and determine the set of feasible solutions.l(2)Plot the gradi
9、ent of the objective function.l(3)Apply the graphical solution technique that pushes iso-profit lines into the direction of the gradient until the last feasible point is reached.This is the optimal solution.l(4)Determine which constraints are satisfied as equations at =.Write them as equations and s
10、olve the resulting system of simultaneous linear equations for the exact coordinates of the optimal solution.l(5)Use the coordinates of the optimal point in the objective functions and compute the value of the objective function.1/10/202313LectureAn Example:1/10/202314LectureSolutionlThe last feasib
11、le point towards higher objective values is D.Binding constraints:I&III.Hence,the system of simultaneous linear equations is x1+4x2=125x1+3x2=15.lThe optimal solution is (1.4118,2.6471);the associated value of the objective function is =10.7647.1/10/202315LectureCorner point theoremlTheorem(Corner p
12、oint theorem,Dantzig):At least one optimal solution is located at an extreme point of the feasible set.lDantzigs simplex method:an incremental technique.Feasible(&improving)directions.lSimplex path in our example:either A,B,C,D,or A,F(same value of the objective function),E,D.lIn practice:millions o
13、f possible paths.Which is best,is known only after the fact.lAverage simplex performance:very good;worst-case performance:very poor(Klee-Minty example).Computational complexity.Other techniques,e.g.,interior point methods.1/10/202316LectureNo feasible solutionlReason:incompatibility of the constrain
14、tsModeling error,constraints are too tightExample:2x1+3x2 7(I)x1+x2 3(II)x1 0(III)x2 0.(IV)1/10/202317LecturelHere,the constraints I,II,&III are incompatible.1/10/202318LecturePossible way-outl“Loosen”the constraints by increasing the RHS values of constraints or decreasing the constraints.lHere:eit
15、her decrease b2 by 22%to 2(or lower),or increase b1 to at least 28%to 9,or similar.lAlternatively,simultaneously increase b1 by 14%to 8 and reduce b2 by 11%to 2.67.Such simultaneous changes may be easier to implement.1/10/202319LectureUnbounded“optimal”solutionslConstraints are“too loose.”Often,cons
16、traints have been forgotten.This is an error message.lExample:P:Max z=2x1+x2 s.t.x1 x2 2(I)2x1+x2 1(II)x1,x2 0.1/10/202320LecturelUnbounded“optimal”solutions exist,if the feasible set is unbounded and the gradient of the objective function points into the direction of the opening.1/10/202321LectureD
17、ual degeneracylA“technical”occurrence.Adjacent extreme points have the same objective values.(We normally do not care).lImportant special case:Dual degeneracy at optimum=alternative optimal solutions.1/10/202322LecturelAt extreme points A&D dual degeneracy exists(but neither solution is optimal),whi
18、le dual degeneracy exists at the optimal solutions B&C,so that all points(not only extreme points)between B&C are optimal(alternative optimal solutions).1/10/202323LectureRedundancy.lA constraint is redundant,if it can be deleted without changing the feasible set.lExampleP:3x1+x2 8(I)x1 2(II)x1 x2 3
19、(III)x1+2x2 6(IV)x1,x2 0.1/10/202324LecturelConstraint III is(strongly)redundant,while constraint I is weakly redundant(it has at least one point in common with the feasible set).lIdentification of redundant constraints is usually as difficult as solving the original problem,hence it is typically no
20、t worth determining whether or not a constraint is redundant.1/10/202325LectureChpter.2.4:Postoptimality AnalyseslOnce an optimal solution has been obtained,the natural question is“what(happens),if one(or more of the given)parameter(s)change(s)?”l Two types of changes:l(1)Structural changes(addition
21、 or deletion of variables or constraints)l(2)Parameter changes.1/10/202326LectureStructural changeslAddition/deletion of a variable=addition/deletion of an economic opportunity.lExample:diet problem.Add a variable=add a type of food the solution may get better(here:cheaper).Delete a variable(here:de
22、lete some foodstuff):the solution either stays the same(if the food was not used anyway),or it gets more expensive(the food was used&cannot be used anymore).1/10/202327LectureAddition/deletion of a variablelAddition of a variable lSame or better Optimal result lOptimal result stay same or increase f
23、or max problems,lOptimal result stay same or decrease for min problems.lDeletion of variableslSame or Worse Optimal result lOptimal result stay same or increase for max problems,lOptimal result stay same or decrease for min problems.1/10/2023Lecture28Addition/deletion of ConstrainslAddition of a con
24、straint:The new problem is more restricted.Same or Worse Optimal result Optimal result stay same or increase for max problems,Optimal result stay same or decrease for min problems.lDeletion of a constraint:The new problem is less restricted.lSame or better Optimal result Optimal result stay same or
25、increase for max problems,Optimal result stay same or decrease for min problems.1/10/2023Lecture29Parameter changes:lChanges of the objective function coefficientslChanges of LHS coefficients(technological coefficients)lChanges of the RHS value1/10/2023Lecture30ExampleConsider the problem:P:Max z=5x
26、1+6x2 s.t.x1 2x2 2 3x1+4x2 12 x1,x2 0.cj:Objective function coefficients(here 5&6)bi:RHS values(here 2,12,0,0)aij:LHS coefficients(technological coefficients).1/10/2023Lecture31Changes of the objective function coefficientslMax z=3x1+2x21/10/2023Lecture32The angle of the gradient of the objective fu
27、nction changes.Example:P:Max z=1x1+2x2 s.t.x2 3 3x1+2x2 11 x1 x2 2 x1,x2 0.The original optimal solution isat Point B (1.67,3).1/10/2023Lecture33Sensitivity analysis on c2.1/10/2023Lecture34Increasing c2 tilts the objective function in a counterclockwise direction.Regardless of the magnitude of the
28、increase,the optimal solution stays at point B.However,the objective function will increase,as X2=3,as c2 increases(i.e.,becomes more valuable),Optimal result increases.Sensitivity analysis on c2.1/10/2023Lecture35decrease c2 the gradient of the objective function moves in a clockwise direction.For
29、small changes,the optimal solution stays at point B.As c2=,B is still optimal.Sensitivity analysis on c2.1/10/2023Lecture36As c2 decreases further,point C(x1,x2)=(3,1)is now the unique optimal solution.Sensitivity analysis on c2.1/10/2023Lecture37For c2 below,point C is the unique optimum until c2=1
30、.At this point,C&D are both optimal.For c2 below 1,point D remains optimal.Summary:1/10/2023Lecture38Range of c2,1 1 1,+Optimal solution pointDD&CCC&BBOptimal coordinates()(2,0)(2,0)&(3,1)(3,1)(3,1)&(1,3)(1,3)Optimal objective value 223+c231+3c2Sensitivity analysis on c1.1/10/2023Lecture39Range of c
31、1,000,333,Optimal solution pointAA&BBB&CCOptimal coordinatesSolution(0,3)(0,3)&(1,3)(1,3)(1,3)&(3,1)(3,1)Optimal objective value 666+1c1 112+3c1 LINDO Output RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 1.000000 2.000000
32、 1.000000 X2 2.000000 INFINITY 1.3333331/10/2023Lecture40simultaneous changesl100%rule:As long as the sum of the absolute values of the increases or decreases of the objective function coefficients is no more than 100%,the optimal solution point remains optimal.1/10/2023Lecture41Our example:lthe opt
33、imal solution for the original objective function Max z=1x1+2x2 was(1,3).lThis solution remains optimal as long as c1(whose original value is c1=1)does not increase by more than =2 to the upper limit of the range at c1=3.Similarly,the solution remains optimal as long as c1 does not decrease by more
34、than =1 to the lower end of the range at c1=0.Similarly,we obtain the values =+and =1.1/10/2023Lecture42100%Rule1/10/2023Lecture431 1|2|31212211cccccc 11C FOR CHANGE ALLOWABLE:c22C FOR CHANGE ALLOWABLE:cLINDO Output RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOW
35、ABLE ALLOWABLE COEF INCREASE DECREASE X1 1.000000 2.000000 1.000000 X2 2.000000 INFINITY 1.3333331/10/2023Lecture441 1|2|31212211cccccc100%RulelFor instance,if c1 increases by and c2 decreases by,we obtain =+=1,so that the optimal solution would change.1/10/2023Lecture45Changes of the right-hand sid
36、e value lConsider the constraint 2x1+3x2 6.Changes of the right-hand side value shift the corresponding hyperplane in parallel fashion.Example:P:Max z=1x1+2x2 s.t.x2 3(I)3x1+2x2 11 (II)x1 x2 2 (III)x1,x2 0.The feasible set(shaded)has extreme points 0,A,B,C,and D.Optimal solution:point B with coordin
37、ates:(1,3),Value of the objective function is =7.Increasing b2(RHS for constrain II)lIncreasing b2 shifts the hyperplane in parallel fashion to the right.lPresently,the constraint is essential(shaping the feasible set),at b2=21 it is weakly redundant(primal degeneracy),and for b2 21,it is strongly r
38、edundant.lOriginal problem:Point B.As b2 increases,the optimal solution moves to points B1,B2,and B3=C.As b2 increases further,the optimal point remains at B3=C.Decreasing b2(RHS for constrain II)lreducing the value of b2 shifts the hyperplane in parallel fashion to the right.lThe feasible set shrin
39、ks,it degenerates to a single point for b2=0(primal degeneracy),and if b2 decreases further,there is no feasible solution.lIf b2 decreases from its original value,the optimal solution moves from B to B4 to B5=A.Further decreases of b2 force the optimal point down to A6&A7=0.Any further decrease leav
40、es no feasible solution.LINDO OUTPUTRIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 3.000000 2.500000 3.000000 3 11.000000 INFINITY 5.000000 4 0.000000 1.666667 INFINITY 5 0.000000 3.000000 INFINITY1/10/2023Lecture50100%Rule1/10/2023Lecture511|2211bbbb 11b FOR CHANGE AL
41、LOWABLE:b22b FOR CHANGE ALLOWABLE:blSuppose now that b1 changes to 4,b2 to 7,and b3 remains unchanged at 2.b1=1,b2=4,and b3=0.lso that the basis will change.1575421|2211bbbblSame problem,different example:Let b1=2(b1=),b2=13(b2=2),&b3=1(b3=1).14311022|310332211bbbbbbthe solution may(and most likely will)change.
