Geometry and Theory of LP

Presentation Transcript

Geometry and Theory of LP Standard (Inequality) Primal Problem: Dual Problem:

Geometry of the Prototype Example P2 Max 3 P1 + 5 P2 s.t. P1 + < 4 (Plant 1) 2 P2 < 12 (Plant 2) 3 P1 + 2 P2 < 18 (Plant 3) P1, P2 > 0 (nonnegativity) Every point in this nonnegative quadrant is related with a particular generation elective. ( point = choice = arrangement ) P1 0

Geometry of the Prototype Example P2 Max 3 P1 + 5 P2 s.t. P1 + < 4 (Plant 1) 2 P2 < 12 (Plant 2) 3 P1 + 2 P2 < 18 (Plant 3) P1, P2 > 0 (nonnegativity) P1 (4,0) (0,0)

Geometry of the Prototype Example P2 Max 3 P1 + 5 P2 s.t. P1 + < 4 (Plant 1) 2 P2 < 12 (Plant 2) 3 P1 + 2 P2 < 18 (Plant 3) P1, P2 > 0 (nonnegativity) (0,6) P1 (4,0) (0,0)

Geometry of the Prototype Example P2 Max 3 P1 + 5 P2 s.t. P1 + < 4 (Plant 1) 2 P2 < 12 (Plant 2) 3 P1 + 2 P2 < 18 (Plant 3) P1, P2 > 0 (nonnegativity) (0,6) (2,6) (4,3) (9,0) P1 (4,0) (0,0)

Geometry of the Prototype Example P2 Max 3 P1 + 5 P2 s.t. P1 + < 4 (Plant 1) 2 P2 < 12 (Plant 2) 3 P1 + 2 P2 < 18 (Plant 3) P1, P2 > 0 (nonnegativity) (0,6) (2,6) (4,3) (9,0) P1 (4,0) (0,0)

P2 Max 3 P1 + 5 P2 In Feasible Region (0,6) (2,6) Feasible locale is the arrangement of focuses (arrangements) that at the same time fulfill every one of the limitations. There are vastly numerous doable focuses (arrangements). (4,3) (9,0) P1 (4,0) (0,0)

Geometry of the Prototype Example P2 Max 3 P1 + 5 P2 (0,6) (2,6) Objective capacity shape (iso-benefit line) (4,3) (9,0) P1 (4,0) 3 P1 + 5 P2 = 12 (0,0)

Geometry of the Prototype Example 3 P1 + 5 P2 = 36 P2 Max 3 P1 + 5 P2 s.t. P1 + < 4 (Plant 1) 2 P2 < 12 (Plant 2) 3 P1 + 2 P2 < 18 (Plant 3) P1, P2 > 0 (nonnegativity) (0,6) (2,6) Optimal Solution: the answer for the concurrent limit conditions of two dynamic requirements (4,3) (9,0) P1 (4,0) (0,0)

Degeneracy P2 Max 3 P1 + 5 P2 s.t. P1 + < 4 (Plant 1) 2 P2 < 12 (Plant 2) 3 P1 + 2 P2 < 24 (Plant 3) P1, P2 > 0 (nonnegativity) (0,6) (2,6) The quantity of dynamic requirements is more than the quantity of factors. (9,0) P1 (4,0) (0,0)

LP Terminology arrangement (choice, point): any detail of qualities for all choice factors, paying little respect to whether it is an attractive or even suitable decision possible arrangement: an answer for which every one of the requirements are fulfilled. doable district (requirement set, plausible set): the accumulation of all attainable arrangement target work form (iso-benefit, iso-cost line) ideal arrangement (ideal): an achievable arrangement that has the most good estimation of the target work ideal (goal) esteem: the estimation of the target work assessed at an ideal arrangement dynamic limitation (restricting imperative) idle limitation excess requirement inside, limit extraordinary point (corner)

Unbounded or Infeasible Case On the left, the target capacity is unbounded On the privilege, the possible set is void

Graphical Solution Seeking Plot the practical area. In the event that the area is void, stop: the issue is infeasible; there must clash requirements in the model. Plot the target work form and pick the streamlining bearing. Figure out if the target esteem is limited or not. If not, stop: the issue is unbounded; there must be errors in model definition. Decide an ideal corner point. Distinguish dynamic requirements at this corner. Fathom synchronous direct conditions for the ideal arrangement. Assess the target work at the ideal answer for get the ideal estimation of the issue.

Theory of Linear Programming A LP issue falls in one of three cases: Problem is infeasible : Feasible area is vacant. Issue is unbounded : Feasible area is unbounded towards the upgrading heading. Issue is achievable and limited : then there exists an ideal point; an ideal point is on the limit of the practical locale; and there is dependably no less than one ideal corner point (if the plausible district has a corner point). At the point when the issue is possible and limited, There might be a remarkable ideal point or various optima (elective optima). In the event that a corner point is not "more awful" than all its neighbor corners, then it is ideal.

Convexity of Feasible Region Convex Set Non-Convex Set F is a raised set if and if for any two focuses, x and y, of F , their curved blend,  x + (1- )y, for every single genuine esteem 0 <=  <= 1, is likewise in F.

Local Optimal => Global Optimal Convex Set Proof by disagreement: If the fact is not comprehensively ideal, then it is not locally ideal

LP Duality Standard (Inequality) Primal Problem: Dual Problem:

LP Duality (proceeded with) Standard (Equality) Primal Form: Dual Form:

General Rules for Constructing Dual 1. The quantity of factors in the double issue is equivalent to the quantity of limitations in the first (primal) issue. The quantity of imperatives in the double issue is equivalent to the quantity of factors in the first issue. 2. Coefficient of the target work in the double issue originate from the right-hand side of the first issue. 3. In the event that the first issue is a maximum model, the double is a min display; if the first issue is a min model, the double issue is the maximum issue. 4. The coefficient of the principal limitation work for the double issue are the coefficients of the primary variable in the requirements for the first issue, and the correspondingly for different imperatives. 5. The right-hand sides of the double requirements originate from the target work coefficients in the first issue.

General Rules for Constructing Dual ( Continued) 6. The feeling of the i th imperative in the double is = if and just if the i th variable in the first issue is unlimited in sign. 7. On the off chance that the first issue is man (min ) show, then in the wake of applying Rule 6, appoint to the rest of the limitations in the double a sense the same as (inverse to ) the comparing factors in the first issue. 8. The i th variable in the double is unlimited in moan if and just if the ith imperative in the first issue is an equity. 9. On the off chance that the first issue is max (min) demonstrate, then in the wake of applying Rule 8, dole out to the rest of the factors in the double a sense inverse to (the same as) the comparing requirements in the first issue. Max demonstrate Min display x i >= 0 <=> ith constraint>= x i <= 0 <=> ith imperative <= x i free <=> ith limitation = ith const <= <=> y i >= 0 ith const >= <=> y i <= 0 ith const = <=> y i free

Economic Interpretation 1. Max Model: the shadow cost for the ith limitation = the ideal estimation of the ith variable in the double. 2. Min Model: the shadow cost for the ith requirement = - the ideal estimation of the ith variable in the double. 3. Assume Factory 1's creation issue is Max 3x1 + 5x2 s.t. x1 <= 4 2x2 <= 12 3x1 + 2x2 <= 18 x1, x2 >= 0 Suppose that the administration of Factory 2 chooses to BUY the crude material in manufacturing plant 1. What are 'reasonable cost' for the three crude material? Sum Factory 2 pays = 4y1 + 12y2 + 18y3 obviously, Factory 2 needs to pay as less as could be allowed. Its will likely Min 4y1 + 12y2 + 18y3

Economic Interpretation ( proceeded with ): However , the costs must fulfill Factory 1 to such an extent that Factory 1 will offer. Processing plant 1 sees that in the event that it has 1 unit crude material 1 and 3 units of crude material 3, it could deliver on unit item 1 for a benefit $3. In this way, to fulfill Factory 1, Factory 2 will cover the loss of item 1 in Factory 1 because of the offer: y1 + 3y3 >= 3 The same is valid for Product 2 in Factory 1: 2y2 + 2y3 >=5 Finally, Factory 2 confronts the ideal evaluating issue min 4y1 + 12 y2 + 18y3 s.t. y1 + 3y3 >= 3 2y2 + 2y3 >= 5 y1, y2, y3 >= 0 It gives 'reasonable costs' in the feeling of costs that yield the base satisfactory liquidation installment.

Relations amongst Primal and Dual 1 . The double of the double issue is again the primal issue. 2 . Both of the two issues has an ideal arrangement if and just if alternate does; on the off chance that one issue is possible yet unbounded, then the other is infeasible; on the off chance that one is infeasible, then the other is either infeasible or practical/unbounded. 3. Frail Duality Theorem: The target work estimation of the primal (double) to be augmented assessed at any primal (double) possible arrangement can't surpass the double (primal) target work esteem assessed at a double (primal) achievable arrangement. c T x >= b T y (in the standard balance frame)

Relati