Description

MS&E 211 Midterm Survey 2007-2008. LP Models. Know how to perceive a LP in verbose or lattice structure; standard or something else; max or min Know how to set up a LP See how to make different transformations between various sorts of LPs (max/min; < , > , =; > , free; |abs. value|; and so forth.).

Transcripts

MS&E 211 Midterm Review 2007-2008

LP Models Know how to perceive a LP in verbose or framework structure; standard or generally; max or min Know how to set up a LP Understand how to make different transformations between distinctive sorts of LPs (max/min; < , > , =; > , free; |abs. value|; and so forth.)

LP Modeling Process Understand the issue Collect data and information Identify and characterize the choice variables plan the target capacity Isolate and figure the requirements

Max-Flow on a Capacitated Network ( Thousands of Gallons Per Hour )

World Cup Portfolio Management Portfolio Management for World Cup Assets Five securities in a business opportunity for open exchanging at altered costs and pay-offs, offer farthest point on venture and short is not permitted Weâd like to choose what number of shares to buy to boost the pay-off when the diversion is figured it out.

Portfolio Optimization Model

Portfolio Optimization Model

The Geometry of LPs Understand the geometrical elucidation of LPs and related instinct Plot an attainable locale in 2D Plot the ideal iso-benefit lines Relate how the Simplex Method moves from corner point to neighboring corner point in enhancing bearing Understand the land translation of the different LP terms â (e.g. dynamic imperatives, essential variables, different optima, infeasibility, unbounded-ness,, and so on.)

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 advancing heading. Issue is attainable and limited : then there exists an ideal point; an ideal point is on the limit of the possible locale; and there is dependably no less than one ideal corner point (if the achievable district has a corner point). At the point when the issue is plausible and limited, There may be an one of a kind ideal point or different optima (elective optima). In the event that a corner point is not âworseâ than all its neighbor corners, then it is ideal.

Algebraic Interpretation of LPs Understand why we accentuate fundamental arrangements and essential achievable arrangements (corner focuses). Comprehend the equal (accepted) type of the LP and where it originated from Understand what the diverse components of this structure mean: decreased expense coefficient, shadow costs, diminished limitation network, RHS Know when to end Know its connection with double

The Canonical Form of the LP Recall the authoritative type of the LP: all lessened expense coefficients for fundamental variables are zero, and lessened requirement lattice for essential variable shape a character grid Why do we speak to the issue along these lines? By taking a gander at the target capacity as far as the non-fundamental variables no one but we can get knowledge into regardless of whether changing any of them may enhance the target capacity By taking a gander at the imperatives along these lines, we can see on the RHS what estimations of the essential variables yield the possible arrangement, and in the requirement coefficients, how changing any non-essential variables will require that we must change essential variables accordingly

Initial Tableau: x slack RHS Basis - c 0 0 A I b (>0) Intermediate Tableau: Basis - c +y*A y* c B - 1 B - 1 A B - 1 B - 1 b ( ï³ 0) Where y*= c B - 1 , the double answer for the creation issue, B is the present premise chose from [ An I ] The Production Problem in Canonical Form

Sensitivity Analysis Recall AGAIN the Simplex scene and the sanctioned structure and what everything means with respect to affectability Changing the expense vector and RHS Know how far every component can be changed before we change to ideal premise How would we discover the consequences for the ideal quality and ideal arrangement while the premise stays ideal? Donât simply remember equations! Comprehend where they originate from and why they work Understand the significance of decreased expenses and shadow costs for affectability

Reduced Cost and Objective Coefficient Range All fundamental variables have zero diminished expense when all is said in done, the lessened expense of any non-essential variable is the sum the target coefficient of that variable would need to change, with all other information held altered, with the end goal it should have a positive quality in the ideal. The target coefficient reaches give the target\'s scopes capacity over which no adjustment in the OS will happen. One of the âallowable increment and decreaseâ for a non-fundamental variable is interminable and the other is the diminished expense. On the off chance that a non-fundamental variable has zero lessened expense, then there exist elective desired states.

Dual (Shadow) Price and Constraint RHS Ranges All inert imperatives have zero double cost by and large, the double cost on a given dynamic requirement is the rate of expansion in the ideal quality (OV) as the RHS of the limitation increments with all other information held altered. On the off chance that the RHS is diminished, it is the rate at which the OV is diminished. The imperative RHS extents give the requirement\'s scopes RHS over which no adjustment in the double cost will happen. One of the âallowable increment and decreaseâ for an inert requirement is vast and alternate equivalents the slack or overflow. As a rule, when the RHS of a dynamic limitation changes, both the OV and OS will change.

Duality Know how to develop the double Understand the monetary translation of y (=c B - 1 ) as shadow costs Using this y, comprehend why the double possibility condition is the primal optimality condition Know the duality hypotheses Know the primal-double optimality conditions and corresponding slackness

General Rules for Constructing Dual 1. The quantity of variables in the double issue is equivalent to the quantity of requirements in the first (primal) issue. The quantity of requirements in the double issue is equivalent to the quantity of variables in the first issue. 2. Coefficient of the target capacity 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 model; if the first issue is a min model, the double issue is the maximum issue. 4. The main\'s coefficient requirement capacity for the double issue are the first\'s coefficients variable in the limitations for the first issue, and the correspondingly for different imperatives. 5. The right-hand sides of the double limitations originate from the target capacity coefficients in the first issue.

General Rules for Constructing Dual ( Continued) 6. The i\'s feeling th imperative in the double is = if and if the i th variable in the first issue is unlimited in sign. 7. In the event that the first issue is man (min ) model, then in the wake of applying Rule 6, appoint to the remaining requirements in the double a sense the same as (inverse to ) the relating variables in the first issue. 8. The i th variable in the double is unlimited in murmur if and if the ith imperative in the first issue is an equity. 9. On the off chance that the first issue is max (min) model, then subsequent to applying Rule 8, allocate to the remaining variables in the double a sense inverse to (the same as) the relating limitations in the first issue. Max model Min model x j ï³ 0 jth requirement ï³ x j â¤ 0 jth imperative â¤ x j free jth limitation = ith const â¤ y i ï³ 0 ith const ï³ y i â¤ 0 ith const = y i free

Dual Pair Standard Primal Production Form: Dual Form (pivot primal 90 o clockwise):

Primal-Dual in Matrix Form Standard Primal Production Form: Dual Form:

Primal-Dual in Matrix Form: Equality Standard (Equality) Primal Form: Dual Form:

Relations Between 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 if alternate does; if one issue is achievable however unbounded, then the other is infeasible; if one is infeasible, then the other is either infeasible or attainable/unbounded. 3. Feeble Duality Theorem: The target capacity estimation of the primal (double) to be minimized assessed at any primal (double) possible arrangement can\'t be not exactly the double (primal) target capacity quality assessed at a double (primal) doable arrangement. c T x >= b T y (in the standard correspondence structure)

Relations in the middle of Primal and Dual (proceeded with) 4. Solid Duality Theorem: When there is an ideal arrangement, the ideal target estimation of the primal is the same as the ideal target estimation of the double. c T x* = b T y* 5. Reciprocal Slackness Theorem: Consider an imbalance imperative (nonnegative variable) in any LP issue. On the off chance that that limitation is latent (nonnegative variable is certain) for an ideal answer for the issue, the comparing double variable (disparity imperative) will be zero (dynamic) in any ideal answer for the double of that issue. y * j (b-Ax*) j = 0 , j=1,â¦,n; x * i (c-A T y*) i = 0 , i=1,â¦,m;

States of the LP Problems

World Cup Portfolio Management Portfolio Management for World Cup Assets Five securities in a business opportunity for open exchanging at settled costs and pay-offs, and short is permitted Weâd like to choose what number of shares to buy or auction to expand the pay when the diversion is figured it out.

Portfolio Optimization Model No offer utmost, and short is permitted: .:tslides