运筹学课件 Duality and Post-Optimal Analysis.pdf

Operations ResearchCh4 Duality and Post Optimal Analysis1 4 1 Defi nition of The Dual Problem A dual variable is defi ned for each primal constraint A dual constraint is defi ned for each primal variable A constraint coeffi cients of a primal variable defi ne the LHS coeffi cients of the dual constraint and its objective coeffi cient defi ne the RHS The objective coeffi cients of the dual equal the RHS of the primal constraints Operations ResearchCh4 Duality and Post Optimal Analysis2 The sense of optimization in the dual is always opposite to that of the primal Assume that the problem is in standard form If the dual objective is minimization then the constraints are all type The opposite is true when the dual objective is max Example 4 1 1 Write down the dual of the following max 5x1 12x2 4x3 x1 2x2 x3 10 2x1 x2 3x3 8 x1 x2 x3 0 Operations ResearchCh4 Duality and Post Optimal Analysis3 maxx0 5x1 12x2 4x3miny0 10y1 8y2 x1 2x2 x3 x4 10y1 2y2 5 2x1 x2 3x3 0 x4 8 2y1 y2 12 x1 x2 x3 x4 0y1 3y2 4 y1 0 y1 y2free Example 4 1 3 maxx0 5x1 6x2 x1 2x2 5 x1 5x2 3 4x1 7x2 8 x1unrestricted x2 0 Operations ResearchCh4 Duality and Post Optimal Analysis4 maxx0 5x 1 5x 1 6x2 x 1 x 1 2x2 5 x 1 x 1 5x2 x3 3 4x 1 4x 1 7x2 x4 8 x 1 x2 x3 x4 0 One can get that the dual problem is miny0 5y1 3y2 8y3 y1 y2 4y3 5 2y1 5y2 7y3 6 y1unrestricted y2 0 y3 0 Operations ResearchCh4 Duality and Post Optimal Analysis5 we summarize the formulation in the following table MinimizationMaximization 0 variable 0 constraint unrestricted 0 constraint 0variable unrestricted Operations ResearchCh4 Duality and Post Optimal Analysis6 4 3 1 Economic Interpretation of Dual Example 4 3 1 Consider the Reddy Mikks model The primal problem represents a resource allocation problem The dual variableyj 0represents the worth per unit of the resource Suppose that the company wants to estimate the least min value of its resources This will induce the problemminy0 24y1 6y2 y3 2y4 Notice that the worth of the resources cannot be less than producing the paints thus 6y1 y2 y3 5 4y1 2y2 y3 y4 4 This is the dual problem Operations ResearchCh4 Duality and Post Optimal Analysis7 4 4 1 Dual Simplex Algorithm To start the algorithm two requirements must be met 1 The objective function must satisfy the optimality condition of the regular simplex method 2 All the constraints must be of the type Dual feasibility condition The leaving variable xr is the basic variable having the most negative value If all the basic variables are nonnegative the algorithm ends Dual optimality condition The entering variable is the nonbasic variable that corresponds to min fl fl fl fl cj arj fl fl fl fl arj 0 Operations ResearchCh4 Duality and Post Optimal Analysis8 Example 4 4 1 minx0 3x1 2x2 x3 3x1 x2 x3 3 3x1 3x2 x3 6 x1 x2 x3 3 x1 x2 x3 0 x1x2x3x4x5x6 3 2 10000 x4 3 1 1100 3 x53 3 1010 6 x61110013 ratio 2 31 1 Operations ResearchCh4 Duality and Post Optimal Analysis9 x1x2x3x4x5x6 50 1 3 0 2 3 04 x4 40 2 3 1 1 3 0 1 x2 11 1 3 0 1 3 02 x620 2 3 0 1 3 11 ratio5 4 1 2 2 x1x2x3x4x5x6 300 1 2 1 2 0 9 2 x4 401 3 2 1 2 0 3 2 x2 110 1 2 1 2 0 3 2 x62001010 Operations ResearchCh4 Duality and Post Optimal Analysis10 4 5 Post Optimal Analysis Consider the problem maxx0 3x1 2x2 5x3 x1 2x2 x3 430 3x1 2x3 460 x1 4x2 420 x1 x2 x3 0 The optimal tableau for the problem is Operations ResearchCh4 Duality and Post Optimal Analysis11 x1x2x3x4x5x6 4001201350 x2 1 4 10 1 2 1 4 0100 x3 3 2 010 1 2 0230 x6200 21120 Change in the RHS Ifb 602 644 588 T then x2 x3 x6 1 2 1 4 0 0 1 2 0 211 602 644 588 140 322 28 x0 1890 Operations ResearchCh4 Duality and Post Optimal Analysis12 If we shift the slack of operation 3 i e b 450 460 400 T one can check that the RHS becomes 110 230 40 T x1x2x3x4x5x6 4001201370 x2 1 4 10 1 2 1 4 0110 x3 3 2 010 1 2 0230 x6200 2 11 40 x1x2x3x4x5x6 5000 5 2 1 2 1350 x2 1 4 1000 1 4 100 x3 3 2 010 1 2 0230 x4 1001 1 2 1 2 20 Operations ResearchCh4 Duality and Post Optimal Analysis13 Addition of New constraints Suppose now a constraint for a new operation 4 is added as 3x1 x2 x3 500 This constraint is satisfi ed by the current optimum solution Hence the current optimum remains unchanged If the new constraint is3x1 3x2 x3 500 we have x1x2x3x4x5x6x7 40012001350 x2 1 4 10 1 2 1 4 00100 x3 3 2 010 1 2 00230 x6200 211020 x73310001500 Operations ResearchCh4 Duality and Post Optimal Analysis14 x1x2x3x4x5x6x7 40012001350 x2 1 4 10 1 2 1 4 00100 x3 3 2 010 1 2 00230 x6200 211020 x7 9 4 00 3 2 1 4 01 30 Dual simplex method can then be applied to yield a new optimalx1 0 x2 90 x3 230 andx0 1330 Changes in the Objective Function Suppose nowx0 2x1 3x2 4x3 We have cT BB 1N cT N 2 3 5 4 0 a1a4a5 2 0 0 13 4 3 2 5 4 Remains optimal withx0 1220 Operations ResearchCh4 Duality and Post Optimal Analysis15 Suppose nowx0 6x1 3x2 4x3 We have cT BB 1N cT N 3 2 5 4 0 a1a4a5 6 0 0 3 4 3 2 5 4 one can get the tableau as x1x2x3x4x5x6 3 4 00 3 2 5 4 01220 x2 1 4 10 1 2 1 4 0100 x3 3 2 010 1 2 0230 x6200 21120 One can then check that the optimal solution isx1 10 x2 102 5 x3 215 andx0 1227 5 Operations ResearchCh4 Duality and Post Optimal Analysis16 Addition of a New Activity Suppose we getx7withaT 7 1 1 2 andc7