### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# OPERATIONSRESEARCH IE1081

Pitt

GPA 3.51

### View Full Document

## 66

## 0

## Popular in Course

###### Class Notes

##### HIST 1200 (History, Steven Watts, Survey of American History Since 1865)

###### Elizabeth Ronecker

verified elite notetaker

## Popular in Industrial Engineering

This 80 page Class Notes was uploaded by Dr. Jamel Schultz on Monday October 26, 2015. The Class Notes belongs to IE1081 at University of Pittsburgh taught by Staff in Fall. Since its upload, it has received 66 views. For similar materials see /class/229408/ie1081-university-of-pittsburgh in Industrial Engineering at University of Pittsburgh.

## Similar to IE1081 at Pitt

## Reviews for OPERATIONSRESEARCH

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

The SIMPLEX Method Development Every LP is in exactly of the following states 1 Feasible with a unique optimum solution 2 Feasible with infinitely many optima 3 Feasible with no optimum solution because the objective is unbounded 4 lnfeasible and hence with no optimum solution Assume we are in States 1 or 2 Then the following are true A The LP has at least one optimal corner point or extreme point 1 If in State 1 exactly one extreme point is optimal 2 If in State 2 at least two adjacent neighboring extreme points are optimal BThe number of extreme points is finite C If the objective function at some extreme point is as good as or better than at all of its adjacent extreme point then this extreme point is optimal for the LP It follows then that we can use the following iterative algorithmic procedure STEP 0 Initialization Find an initial extreme point and make it the current candidate if one cannot be found the LP is in state 4 Le it is infeasible so STOP STEP 1 Stopping Criterion Check Is the objective at the current extreme point at least as good or better than it is at all of its adjacent neighboring extreme points If so this must be the optimal extreme point via C so STOP If not go to Step 2 STEP 2 Iterative Step At least one of the adjacent extreme points is better so make it the current candidate and go to Step 1 QUESTIONS 1 How to find an initial extreme point 2 What is the algebraic characterization of an extreme point 3 What is the algebraic characterization of adjacent extreme points ie how to move from an extreme point to one of its neighbors in Step 2 Standard Form of a Linear Program Three conditions must be met 1 All constraints must be stated as equalities of the form gkxbk where gkx is a linear function of x 2 The RHS for each constraint must be nonnegative ie all bkzo 3 All variables must be nonnegative ie X20 for all i Thus the LP with m constraints and n variables looks like Min or Max c1x1 02X2 0an St a11X1 a12X2 a1an b1 821X1 822X2 82an b2 am1X1 am2X2 anan bm X1 X2 Xn 2 0 where b1 b2 b7 2 0 More compactly let cc1 02 on and all 0112 am x1 1 a a a x 21 22 2n 2 2 A X and X a a a x b m1 m2 m Then the LP may be restated as Min or Max cx st Axb x20 where b20 This final system of constraint equations of the LP in standard form is called the AUGMENTED SYSTEM Consider such an augmented system of n variables in m equations where msn Note that the augmented system does not include the nonnegativity conditions Also note that this system has three possible states 1 no solution 2 exactly one solution or 3 infinitely many solutions Feasible solution Any solution to the augmented system that also satisfies nonnegativity is called a feasible solution Eg Consider the following constraints and the corresponding augmented system x12x2 120 x12x2S1 120 x1 x23 90 x1x2 82 90 X1 S 70 X1 83 70 x23 50 x2 S450 Note that n6 and m4 1 An infeasible solution is x170 x250 S150 Sz30 830 840 2 A feasible solution is x120 x220 8160 8250 8350 8430 Basic Solution Suppose we fix nm out of the n variables at zero and try to solve the system of m equations in the remaining m variables If a solution to this exists then it is called a basic solution Solution 1 on the previous page is an example of a basic solution Basic Feasible Solution A basic solution that also satisfies nonnegativity is called a basic feasible solution BFS An example of a BFS is x120 xz50 S10 8220 8350 S40 Note that 1 is not a BFS even though it is a basic solution Augmented System 4 One No Solution In nitely many solutions Original LP has exactly Original LP is infeasible one feasible solution it F easible Infeasible must also be the optimal 7 one IBasic I Nonbasic Basic HNonbasic FACT Each BFS corresponds to an extreme point of the feasible region In a basic solution the nm variables that are chosen to be xed at zero are called the nonbasic variables and the remaining m variables are called basic variables Note that we can choose nm out of the n variables in l n n Ldifferent ways Thus we can get a n m m n m 171 maximum of this many different basic solutions some of which will also be basic feasible solutions in practice all of these may not exist since in some cases the resulting m x 171 system may not have a solution 3915 m 6 44 The 15 combinations of nonbasic variables are n I In our example 146 and m4 so that j 6 n 1 X1 X2 2 X1 SI 6 X2 SI 3 X1 82 X2 82 81 82 4 X1 S3 X2 S3 81 S3 Sz 82 5 X1 S4 X2 S4 81 S4 82 S4 S3 S4 Try to locate each of these on the graphical representation S30 X170 sz0 X1Xz90 50 53540 Max 20X110Xz st X12Xz S 120 X1Xz S 90 X1 S 70 X2 S 50 X1 X2 2 0 Constr 1 S1 Constr 2 Sz Constr 3 S3 Constr 4 S4 s0 Xz50 x l Us BASIC SOLUTIONS 13 ofthem Note that there should be 15 of these but only 13 exist because X170 is parallel to the XZaxis and X250 is parallel to the Xlaxis 2 III IV V VI BASIC FEASIBLE SOLUTION 6 of the above 13 numbered I II 3 Contour of the objective function corresponding to a value of 1600 4 Set of all Feasible solutions to the LP A TYPICAL TRANSPORTATION PROBLEM The Industrial Engineering Department at a large corporation has been assigned the task of planning the distribution of the monthly production at its three main plants to its four major warehouses around the country The following demand supply and cost data are available Warehouse j Plant i j1 j2 j3 j4 Supply Si i1 12 13 4 6 i2 6 4 10 1 1 700 i3 10 9 12 14 800 Demand Dj 4 00 900 200 500 2000 QUESTION What is the minimum cost distribution plan so that all demand is satis ed ANSWER Solve the following LP M111 12X1113X124X136X14 6X214X2210X2311X24 10X319X3212X3314X34 st X11X12X13X14 500 X21 X22 X23 X24 g 700 X31X32X33 X34 g 800 X11 X21 X31 2400 X12 X22 X32 2900 Xi3 X23 X33 2200 X14 X24 X34 2 500 all Kg 2 0 Northwest C orner Rule 12 13 4 6 6 4 10 11 10 9 12 4 400 900 200 500 Least Unit Cost Rule 12 13 4 6 6 4 10 11 10 9 12 4 400 900 200 500 Vogel 39s Approximation Method 12 13 4 6 6 4 10 11 10 9 12 4 400 900 200 500 FINDING REDUCED COSTS De ne a variable ui for each row i De ne a variable vJ for each column j FACT For a basic variable cij ui vJ Arbitrarily set u10 and find all other ui and vi using the above fact for basic variables For a nonbasic variable the reduced cost ui vJ cij Thus find reduced cost for all nonbasic variables THE TRANSPORTATION SIMPLEX ALGORITHM r Do all variables have nonpositive reduced costs If so STOP N If not pick a variable usually the nonbasic variable with the largest reduced cost to enter the basis 4 Find the unique loop using this variable and some of the basic variables 4 Start with the entering cell and label it Then proceed by alternately designating consecutive cells in the loop and U Pick the cell with smallest Xlj ijn say This becomes the leaving variable Reduce values in all cells in the loop by Xmin and increase values in all cells in the loop by Xmin Return to l with the new basic feasible solution 16 16 13 22 17 40 10 50 14 14 13 19 15 6O 30 30 19 19 20 23 M 50 0 20 30 M 0 M 0 0 50 50 3O 20 7O 3O 60 V1 ui ui The HUNGARIAN ALGORITHM for the Assignment Problem Consider the n x n assignment cost matrix A De ne Row Reduction Operation Subtract the smallest entry in a row from every entry in that row Column Reduction Operation Subtract the smallest entry in a column om every entry in that column Fully Reduced Matrix One Where the minimum number of horizontal andor vertical lines required to cover all zero entries is equal to the order of the matrix 1 STEP 0 First Row Reduce A then Column Reduce the resulting matrix STEP 1 Is the current matrix fully reduced If yes go to Step 3 else go to Step 2 STEP 2 Identify the smallest unlined cell value m Subtract m from every entry that is unlined and add m to every entry With two lines through it Go to Step 1 With the new matrix STEP 3 Extract the optimal assignment A Transshipment Problem Consider an automobile company with two plants located at nodes 1 and 2 with supply amounts of 1000 and 1200 respectively Cars are shipped to dealers denoted by nodes 5 6 and 7 through distribution centers denoted by 4 and 5 The demands at the three dealers are 800 900 and 500 respectively The number above each arc represents the per unit shipping cost What is the best way of ful lling demand at the dealers Formulating the Transshipment Problem as a Transportation Problem 2200 vi 1000 1200 2200 2200 2200 2200 3 4 B4 B4 B4 1 1000 2 5 B4 B4 B4 2 1200 0 7 8 6 B4 3 2200 B4 0 B4 4 9 4 2200 B4 B4 0 5 B4 5 2200 B4 B4 B4 0 3 6 2200 2200 2200 3000 3100 500 V J VEIHFT THMJ ZHISLS171EPTYAIUEIIHIHJL4LO ui A Q b 4 U1 0 Chapter 5 Sensitivity Analysis Using an Applied Approach Learning Objectives Understand what sensitivity analysis is and be able to de ne it eXplain why we use it and justify its importance Understand how to conduct sensitivity analysis for o the objective function coeff1cients considering the range of the objective function coeff1cients the reduced cost 0 the right hand side values of the constraints considering the range of the right hand side values the shadow or dual prices of the constraints Be able to conduct sensitivity analysis using the graphical method Be able to conduct sensitivity analysis using LINDO You should be able to interpret the entire LINDO output for a problem Understand the concept of complementary slackness and what it means Understand parametric analysis and its application Chap 5 l Sensitivity Analysis Sensitivity analysis is concerned with examining the effect that changes in the LP parameters have on the LP39s optimal solution These include changes to the objective function coefficients and right hand side values Why would this be a concern For example let39s suppose that in the original formulation and solution to an LP problem it was thought that variable xi would generate 10 of pro t Well suppose now that it only generates 9 of pro t Is the same solution valid Does the LP problem need to be solved again In another example suppose that we thought that there were 1000 hours of machine time Unexpectedly a machine breaks down reducing the number of hours to 800 hours Is the same solution valid as in the original formulation Does the LP problem need to be solved again Chap 5 2 Additionally sensitivity analysis can be useful in deciding how much one should pay for additional units of resources such as pieces of equipment or labor hours In summary sensitivity is important due to l Uncertainty of parameters 2 Changing parameters We will begin our discussion of sensitivity analysis by looking at the two variable case and using a graphical method to perform sensitivity analysis Next we will examine how to perform sensitivity analysis by utilizing the output from LINDO Chapter 6 discusses duality which provides many insights into the nature of linear programming and helps us to understand sensitivity analysis It forms a solid foundation for study of advanced topics in linear and nonlinear programming We will begin in Chapter 5 Chap 5 3 Overview of Sensitivitv Analysis Chap 5 4 Example Section 51 pg 201 Problem 5 max z 3x1 2x2 st 1 x1 2x2 S 40 2 2x1 x2 S 50 x1x2 2 O This could be solved using the graphical solution technique or the simplex method Let39s solve it graphically a For what values of the price of a type 1 radio would the current basis remain optimal This analyzes the effect of a change in an objective function coefficient The slope of any isoprof1t line z 32 For any isoprof1t line the value of the objective function is constant and equals 3x1 2x2 Replace the 39339 with a 39c139 The slope now becomes c12 Chap 5 5 Chap 5 6 If the slope of z becomes steeper point C will no longer be optimal but point B will become optimal This occurs where c12 lt 2 c1 gt 4 If the slope of z becomes atter point C will no longer be optimal but point D will become optimal This occurs where c12 gt l2 c1 ltl So in order for the basis to remain optimal c1 the pro t of a type 1 radio must be l c1 4 c1 price5l25 price 22 l 3 price 22 g 4 23 3 price 3 26 b For what values of the price of a type 2 radio would the current basis remain optimal Chap 5 7 This also analyzes the effect of a change in an objective function coefficient The slope ofz 32 For any isoprof1t line the value of the objective function is constant and equals 3X1 2X2 Replace the 39239 with a 39c239 The slope now becomes 3c2 If the slope of z becomes steeper point C will no longer be optimal but point B will become optimal This occurs where 3c2 lt 2 c2 lt 15 If the slope of z becomes atter point C will no longer be optimal but point D will become optimal This occurs where 3c2 gt 12 c2 gt 6 So in order for the basis to remain optimal c2 the profit of a type 2 radio must be Chap 5 8 15 3 c2 3 6 c2 pricelO64 price 20 15 3 price 20 g 6 215 3 price 3 26 c If laborer l were willing to work only 30 hours per week would the current basis remain optimal Find the new optimal solution to the LP This analyzes the effect of a change in a RHS on the LP39s optimal solution Currently laborer 1 works 40 hours If he only works 30 hours the feasible region will change The optimal solution will still occur at the intersection of the two constraints x1 703 x2 103 z 2303 The current basis is optimal But the values of X1 X2 and z have changed Chap 5 9 d If laborer 2 were willing to work up to 60 hours per week would the current basis remain optimal Find the new optimal solution to the LP This analyzes the effect of a change in a RHS on the LP39s optimal solution e Find the shadow price of each constraint What is a shadow price Each constraint has a shadow price It is the amount by which the optimal zvalue is improved increased for a max or decreased for a min if the RHS of the constraint is increased by 1 Assuming the change in the constraint leaves the current basis optimal For a two variable problem it is easy to determine the shadow price Chap 5 lO For this problem we know that the optimal solution is occurring at the intersection of the two constraints So for constraint 1 the shadow price is X 2X2 40 A 2X1 X2 50 solve simultaneously yielding x1 20 A3 X2 10 2A3 plug into z 3X1 2X2 yields z 80 A3 so the shadow price for constraint 1 l3 In other words for each additional unit of labor 1 the pro t will increase by l3 ChapSll For constraint 2 the shadow price is X 2X2 40 2X1 X2 50 A solve simultaneously yielding x1 20 A3 X2 10 A3 plug into z 3X1 2X2 yields z 80 4A3 so the shadow price for constraint 2 43 In other words for each additional unit of labor 2 the pro t will increase by 43 Chap 5 l2 LINDO and Sensitivity Analysis LINDO produces information which is helpful for sensitivity analysis In LINDO type Yes when queried after using the GO command Let39s follow along in our book on pg 2123 problem 4 Gepbab Manufacturing Objective Function Coeff1cient Ranges LINDO allowable increase and allowable decrease This is the increasedecrease with the current basis remaining optimal It also assumes that only one variable is changing Note the value of the decision variables remains unchanged however the value of the objective function will change Chap 5 l3 Example Chap 5 14 Reduced Cost The reduced cost tells us about how changing the objective function coef cient for a NBV will change the LP39s optimal solution For any NBV xk the reduced cost for xk is the amount by which the objective function coef cient of Xk must be improved before the LP will have an optimal solution in which xk is a BV If the objective function coef cient of a NBV Xk is improved by its reduced cost then the LP will have alternate optimal solutions at least one with Xk as a BV and at least one in which xk is not a BV If the objective function coef cient of a NBV is improved by more than its reduced cost then barring degeneracy any optimal solution to the LP will have this variable xk as a BV and Xk gt 0 Chap 5 15 Example Chap 5 16 RHS Ranges LINDO allowable increase and allowable decrease This is the increasedecrease with the current basis remaining optimal It also assumes that only one variable is changing Note the value of the decision variables may change and the value of the objective function will change Chap 5 l7 Shadow Prices also called Dual Prices Suppose that the current basis remains optimal as we increase the RHS of the ith constraint by Abi Abi lt 0 means that we are decreasing the RHS of the ith constraint Note Abi bnew bold Then for a maximization problem New optimal zvalue old optimal zvalue constraint i39s shadow priceAbi for a minimization problem New optimal zvalue old optimal zvalue constraint i39s shadow priceAbi 2 constraint shadow price will be nonpositive constraint shadow price will be nonnegative constraint shadow price could be positive negative or zero ChapS 18 Use of Shadow Prices The shadow prices can help a manager to answer the question What is the maximum amount that I would be willing to pay for an additional unit of a resource Note if the shadow price is 0 this indicates that the resource is in excess and we would not be willing to pay any additional amount for the resource Chap 5 l9 Example Problem 4 Section 53 pg 218 What is the most that Gepbab would be willing to pay for another unit of capacity at plant 1 Chap 5 20 Example Problem 1 Section 53 pg 218 What is the most that Carco should be willing to pay for an extra ton of steel Chap 5 21 Example Problem 2 Section 53 pg 218 What is the most that Carco should be willing to pay to rent an additional type 1 machine for one day Chap 5 22 Slack and Surplus Variables and Complementary Slackness The product of the values of the constraint39s slacksurplus variable and the constraints shadow price must equal 0 This is known as the complementary slackness condition In other words any constraint whose slacksurplus variable gt 0 will have a zero shadow price Which also means that any constraint with a nonzero shadow price must be a binding constraint the slacksurplus variable must equal 0 Chap 5 23 Oddities of the LINDO output if the optimal solution is degenerate a Q U For at least one constraint either the allowable increase or the allowable decrease for the RANGE IN WHICH THE BASIS IS UNCHANGED will equal 0 For a NBV to become positive a NBV s objective coeff1cient may have to increase more than its REDUCED COST This is because the basis may change but the variable may still have a value of O and the LP optimal solution may be unchanged Increasingdecreasing a variable s objective function coeff1cient by more that its allowable increasedecrease leaves the optimal solution unchanged As in 2 there may be a basis change but no change in the variable values and the LP optimal solution Chap 5 24 Parametric Analysis examines the way in which the optimal solution the set of BVs and the objective function value varies as a function of one of the parameters LINDO can perform parametric analysis for the RHS values LINDO use the 39PARA39 command Consider Example 1 p202 in Chapter 5 The amount of raw material is 4600 This current basis remains optimal for the range 4450 4850 To see what happens outside of this range we can run LINDO We obtain the output in Figure 12 Note that we must rerun the GO command prior to each time we use the PARA command Chap 5 25 From this data we can draw the graph shown in Figure 13 of Chapter 5 Remarks a The graph is piecewise linear 2 For a maximization problem the graph for a constraint is nondecreasing Note that the slopes of the individual segments are nonincreasing diminishing returns 3 For a 2 constraint the graph is nonincreasing and the slopes of the indiVidual segments are nonincreasing Chap 5 26 We can perform a similar analysis to measure the effect of changing the objective function coef cient on the optimal zValue Example Problem 4 Section 54 pg 222 min z 50X1100X2 From the graph on page 63 we found that point E 36 14 was the optimal z 320 Construct an isocost line Pick 120 z 5012 1000 600 Plug the value 600 in for z 600 50x1 100x2 X2 l2x1 6 slope l2 Chap 5 27 If the line is steeper point B 0 14 would be optimal and z 1400 z c1x1100x2 slope is now c1100 c1 100 gt 72 where 72 is the slope of constraint 1 c1 lt 350 otherwise point B becomes optimal If the slope were atter point C 120 would be optimal and z 600 c1100 lt 16 where 16 is the slope of constraint 2 c1 gt 503 1667 otherwise point C becomes optimal In summary Point Range on c1 z c1x1 100X2 slope C 120 0 1667 12c1 12 E 3614 1667 350 36c1 140 36 B 014 350 in nity 1400 0 This data can now be graphed Chap 5 28 The 100 Rule Section 64 Chap 5 29 Chap 5 30 Chap 5 31 Duality Chap 5 32 Chap 5 33 Chap 5 34 POSTOPTIMALITY ANALYSIS aka SENITIVITY ANALYSIS Objective To analyze the optimum solution to see how sensitive this solution is wrt the cost coe cienls and the righthand side values Consider our example Maximize z 5000x1 4000x2 St 10x1 15x2 g 150 20x1 10x2 g 160 30x1 le 2135 all xiZO Theop nunnsohnunlmmsxf45xf7z50500 A Sensitivity to Cost Coef cients Suppose we wish to examine changes in C the coef cient for x1 from its current value of 5000 Let us say the new value is c139c1Ac15000ch say Wecanwrite c39 z zc39x4000x z x 1x 1 1 2 2 4000 1 4000 The slope of the above line is c1394000 and 50004000 l25 currently If C increases the slope becomes more negative and conversely if c 139 decreases the slope becomes less negative In other words the isocost line representing the objective rotates in a clockwise or a counterclockwise direction If this rotation is small the optimum solution might be unchanged but for a sufficiently large tilt the optimum could shift to a neighboring comer point A 20x110x2160 slope 2 30x110x2l35 slopel3 In the above picture the current value for c1 c15000 so that the current slope is 50004000 l25 The extreme point that is currently optimal A is unchanged as long as the new slope after c1 changes lies between 2 and 23 2S01 4000 23 gt 8000 c1 S80003 gt 80003 S 0138000 ie 2667 S 01 38000 So for the basis to not change ie for optimum to remain at point A the max allowable increase is 800050003000 and the max allowable decrease is 5000 2667 2333 ie 2333 S Acl S 3000 When the increase exceeds 3000 the optimum shifts to D and when the decrease exceed 2333 the optimum shifts to B B Sensitivi to RightHandSide Values Now suppose we wish to examine changes in b1 the RHS for constraint 1 from its current value of 150 Let us say the new value is b139b1AbJ150Ab1 say Consider the line 10x1 15x bf As the value of 9139 changes the slope is unchanged but the line moves parallel to itself either quotupwardquot if it increases in value or quotdownwardquot if it decreases in value In general for the case where the RHS value changes one of several different things could happen 0 The current optimum point might be unaffected and remain optimum o The current optimum point might not be an extreme point any longer and thus we would have a new optimum point which has a either the same basic variables b or different basic variables 0 The entire problem might become infeasible for a suf ciently large increase or decrease In our example as 9139 changes the feasible region either expands and admits more points or shrinks and admits fewer points in all cases the optimum solution changes as does the optimal objective value Consider the picture The current feasible region is ABCD i 10X115X2120 10X115X280 Note that if c b1 120 the new feasible region is MLCD and the optimum is at M same basis 0 b1 80 the new feasible region is N CD and the optimum is at D different basis Similarly if c b1 200 the new feasible region is JPKCD and the optimum is at J same basis 0 b1 240 the new feasible region is QKCD and the optimum is at Q different basis Note that the current optimal basis is unchanged as long the new RHS satis es 8031913240 That is since b139150Ab1 70 S Abls 90 Also note that the value of 2 changes in all cases even if the basis is unchanged and that as 1 becomes smaller and smaller at some point the problem could become infeasible In summary 0 Changes in cf do not affect feasibility in any way However the optimum solution may shift to another extreme point with a different BFS for a suf ciently large change In either case 2 will change too Changes in b affect the shape of the feasible region and big changes could make the feasible region vanish If the problem is still feasible after the change the optimum may or may not change If it does change the value of zwill change too and the new optimum may or may not have a different set of basic variables ie may be at a point of intersection of a different set of lines than before LINDO and the Excel Solver provide the range of values for each cf and for each I in which the basis is unchanged They do not provide the new values of the objective though RANGES IN WHICH THE BASIS IS UNCHANGED OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 5000000000 3000000000 2333333252 X2 4000000000 3500000000 1500000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 150000000 90000000 70000000 3 160000000 140000000 40000000 4 135000000 70000000 INFINITY SHADOW PRICES aka DUAL PRICES De nition The shadow price for constraint 139 is the amount by which the optimum objective 2 improves ie increases for a max problem or decreases for a min problem when the RHS for that constraint bi increases by 1 unit provided that the basis does not change In our example consider b1 Suppose it becomes 1 39b1 Ab1 Suppose the basis does not change so that the optimum is still at the intersection of the line 10x1 15x2 3 150Ab1 and the line 20x1 10x2 3 160 This point is given by x1 45Ab120 and x2 7Ab110 So the optimal objective is 2 SOOOxf 4000x2 500045Ab120 40007Ab110 50500150Ab1 Thus the shadow price for the rst constraint is 150 Similarly the shadow price for the second constraint is 175 LINDO and Excel Solver provide these as well ROW SLACK OR SURPLUS DUAL PRICES 2 0000000 150000000 3 0000000 175000000 4 70000000 0000000 IIVIPORTANT NOTE The signs of the Shadow Prices should be carefully noted and can always be predicted suppose we let 7 represent the shadow price for constraint 1 Assuming that the basis is unchanged for a 1 unit increase in 1 Then we have 0 New 2 Old 2 71 for a max problem 0 New 2 Old 2 7 for a min problem Case 1 Constraint 1 is a constraint In this case a 1 unit increase in the RHS loosens the constraint ie makes it easier to satisfy ie expands the feasible region Thus the objective new cannot get any worse and thus New 2 2 Old 2 for a max problem New 2 Old 2 for a min problem Thus 71 must be nonnegative 20 Case 2 Constraint 1 is a 2 constraint In this case a 1 unit increase in the RHS tightens the constraint ie makes it harder to satisfy ie shrinks the feasible region Thus the objective new cannot get any better and thus New 2 3 Old 2 for a max problem New 2 2 Old 2 for a min problem Thus 71 must be nonpositive S0 Case 3 Constraint 1 is an constraint In this case 7 could take on any sign REDUCED COSTS Recall that the optimum reduced cost for a variable is its entry in Equation 0 in the optimum tableau thus the optimum reduced cost value 0 for a basic variable is always equal to 0 o for a nonbasic variable is 20 if we are maximizing SO if we are minimizing Also recall that the reduced cost for a nonbasic variable was de ned as the decrease in z for a 1 unit increase in that variable An alternative interpretation of the reduced cost for a nonbasic variable xj is the following o For a max problem it is the required increase in the value of its pro t coef cient cj before it can be entered into the basis and made positive 0 For a min problem it is the required decrease in the value of its cost coef cient cj before it can be entered into the basis and made positive LINDO and Excel Solver provide these as well VARIABLE VALUE REDUCED COST Xl 4500000 0000000 X2 7000000 0000000 COMPLEMENTARY SLACKNESS This is an important concept that applies only to g or 2 constraints and it may be stated as follows At the optimum o If a particular inequality constraint is nonbinding ie loose or inactive so that the corresponding slack excess variable is positive then the shadow price for that constraint must be equal to zero If the shadow price for some constraint is nonzero then that constraint must be binding ie tight or active so that the corresponding slackexcess variable is equal to zero Thus slack or excess variable for constraint im 0 Note that it is possible for both the slackexcess as well as the shadow price to be equal to zero however it is impossible for both to be nonzero DUALITY l PRIMAL has n variables 2 DUAL has n constraints 2 PRIMAL has In constraints 2 DUAL has In variables 3 Coe icient matrix for the PRIMAL is A 2 Coef cient matrix for the DUAL is the transposm A 4 RHS vector for the PRIMAL becomes the objective coef cient vector for the DUAL and the objective coef cient vector for the PRIMAL becomes the RHS vector for the DUAL 5 IF the PRIMAL is a MAXIMIZATION problem THEN a First convert any 2 constraints to g by multiplying through by l b DUAL is a MINIMIZATION problem c Dual variable corresponding to a primal constraint is UNRESTRICTED d Dual variable corresponding to a primal 5 constraint is NONNEGATIVE 20 e Dual constraint corresponding to a nonnegative primal variable is 2 1 Dual constraint corresponding to an UNRESTRICTED primal variable is 6 IF the PRIMAL is a MINIMIZATION problem THEN a First convert any g constraints to 2 by multiplying through by l b DUAL is a MAXIMIZATTON problem c Dual variable corresponding to a primal constraint is UNRESTRICTED d Dual variable corresponding to a primal 2 constraint is NONNEGATIVE 20 e Dual constraint corresponding to a nonnegative primal variable is g 1 Dual constraint corresponding to an UNRESTRICTED primal variable is NOTE For a MAX problem a g constraint is considered quotnorma quot For a MIN problem a 2 constraint is considered quotnormalquot A nonnegative variable is considered quotnormalquot A quotnormalquot constraint in one problem will give rise to a normal nonnegative variable in the other Equality constraints always give rise to unrestricted variables Similarly a quotnormalquot nonnegative variable in one problem will always give rise to a quotnormalquot constraint in the other While an unrestricted variable in one will give rise to an equality constraint in the other The main duality result states that 1 if one problem is feasible and has a nite optimum solution then so does the other and the optimal objective values are equal to each other 2 if one problem is unbounded the other is infeasible and 3 if one problem is infeasible the other is either unbounded or infeasible Network Flow Problems A Proto pical Example A new amusement park is being constructed by a large corporation Cars are not allowed into the park but there is a system of narrow winding pathways for automated people movers and pedestrians The road system is shown in the gure below where 0 represents the entrance to the park and AF represent sites of various popular amusements The numbers above the arcs give the distances of the arcs The designers face three questions 1 Electrical lines must be laid under the pathways to establish communication between all nodes in the network Since this is an expensive process the question to be answered is how this can be accomplished with a minimum total distance Location F is extremely popular with visitors and it is planned that a small number of people movers will run directly from the entrance 0 to site F The question is which path will provide the smallest total distance from O to F During the peak season the number of people wanting to go from O to F is very large Thus during this time various routes may be followed from O to F irrespective of distance so as to accommodate the increased demand through additional trips However due to the terrain and the quality of the construction there are limits on the number of people mover trips that can run on any given path per day these are different for different paths The question is how to route various trips to maximize the number of trips that can be made per day without violating the limits on any individual path Question 1 may be answered by solving a minimum spanning tree problem Question 2 may be answered by solving a shartestpath problem Question 1 may be answered by solving a maximum ow problem DIJKSTRA 39S SHORTEST PA THALGORITHM Let us represent the origin by 0 and suppose that there are n additional nodes in the network Obiective at Iteration i To nd the ith closest node from 0 along with the corresponding path and distance Ingut at Iteration i The closest the 2nd closestiIth closest nodes to 0 along with their paths and distances These are designated as permanent nodes P while the remaining nodes are designated as temporary nodes T Initially P0 and Tall other nodes At Iteration i Determine all nodes in T that are directly linked to at least one node inP call this subset of T as 9 For each jeQ compute D Minimumdistance of direct link from j to a permanent node shortest distance from 0 to that permanent node Determine the j 69 that has the minimum value for D Remove j from T and add it to P along with the shortest path and distance At the end of iterationi the shortest path to each node is available Example Iterationl Q IL O TABCDEF o A B C DAMinLOA02 DBMinLOB05 DCMinLOC04 Closest node A Iteration 2 Iteration 3 Iteration 4 ER ET 3 TB3C3D3E3F 9 3 C D DBZMII ILOB0 LAB24 DCMinLOCO4 DDMinLAD29 2m1 closest node C 9 3 D E DB MinLOBO LAB2 Loc44 DDMinLAD29 DEMinLCE48 3rd closest node B P0ACB T DEF 9 D E DD MlnLAD2 LBD48 DE Mll lLCE4 LBE4 7 4th closest node E Iteration 5 1E0ACBE T DF MinLAD2 LBD4 LED78 DE MinLCE4 LBE4 7 5th closest node D Iteration 6 9 IL 0ACBED TF 9 F DF MinLED7 LDF513 6th closest node F THE FORDF ULKERSON ALGORITHM FOR THE MAXIMUM FLOW PROBLEM STEP 0 Start with some feasible ow if one isn39t obvious let ow in each arc be equal to zero from the source node to the sink node STEP 1 If ow in arc ij is less than capacity of arc ij assign it to set I set of arcs along which amount of ow can be Increased If ow in arc ij is greater than zero assign it to set R set of arcs along which amount of ow can be Reduced NOTE An arc can belong to both I and R STEP 2 LABELING PROCEDURE Label the source node If the ow along an arc ij is from a labeled node to an unlabeled node and the arc belongs to I then label the unlabeled node call the arc a forward arc and let ij Capacityij Flowij If the ow along an arc is from an unlabeled node to a labeled node and the arc belongs to R then label the unlabeled node and call the arc a backward arc and let Rij Flowij Continue the labeling procedure until a the sink has been labeled or b no more nodes can be labeled STEP 4 If the sink has not been labeled STOP this is the optimum ow If the sink has been labeled go to Step 5 STEP 5 There is a chain C from source to sink If C has only forward arcs increase the ow in each arc by an amount AfZ Mini CIi J If C has forward and backward arcs increase the ow in each forward and decrease the ow in each backward arc by an amount Af Mm k1 2 M i jeInC1i J k2 Mina peRnCRU 1 Return to Step 2 X1 X2 51 S2 53 S4 0 0 120 90 7O 50 0 50 20 4O 7O 0 20 50 0 20 50 0 6O 3O 0 0 10 20 7O 20 10 0 0 3O 7O 0 50 20 0 50 slt2a ALGEBRAIC SPECIFICATION OF THE SIMPLEX METHOD PHASE I STEP 0 INITIALIZATION Find an initial basic feasible solution BFS ie an extreme point of the feasible region If one cannot be found the problem is infeasible STOP PHASE II STEP 1 STOPPING CRITERIA CHECK Is unboundedness detected If so there is no optimum solution STOP If not is there an adjacent extreme point where the objective function is better than at the current one ie can the objective be improved by exchanging one of the currently basic variables for one of the currently nonbasic variables If not the current BF S is optimal STOP If not proceed to Step 2 STEP 2 ITERATIVE STEP Move to the better adjacent extreme point identified above by exchanging a basic variable for a nonbasic one and got to Step 1 LP Tableau Reduced Costs or Relative Pro ts Row Z X1 X2 S1 S2 S3 S4 RHS Basic 0 1 0 0 0 0 0 Z 1 0 1 0 0 0 120 S1 2 0 0 1 0 0 90 S2 3 0 0 0 1 0 70 S3 4 0 0 0 0 1 50 S4 substitution rates The system of equations represented above is said to be in CAN ONICAL F ORM Each basic variable appears in exactly one constraint and has a coef cient of 1 The RHS for each constraint is a nonnegative constant NOTE that the system has essentially been quotsolvedquot for Z S1 S2 S3 and S4 in terms of X1 and X2 2 020X110X2 S1 120 X1 2X2 X1 and X2 are parameters S2 90 X1 X2 or NONBASIC variables S3 70 X1 S4 50 X2 S1 S2 S3 and S4 are BASIC variables Letting the nonbasic variables equal 0 we obtain the Basic Feasible Solution X1X20 Sl120 8290 8370 and 5450 Obviously this BFS is not optimal from Z 0 20X1 10X2 it is clear that increasing either X1 or X2 will increase Z Let us arbitrarily select X1 for increase while maintaining the other basic variables X2 in this case at 0 Each unit increase in X1 increases Z by 20 units However as X1 is increased the values of the current basic variables Sl 2 83 and S4 change 1 unit decrease in 81 1 unit decrease in Sz ONE unit increase in X1 gt 1 unit decrease in 83 substitution rates 0 unit change in S4 Question HOW MUCH MAY X1 INCREASE Answer A further increase in X1 is quotblockedquot when one of the basic variables reaches its lower bound zero To continue increasing X1 would cause the nonnegativity restriction on this basic variable to be violated Here we thus have 81 reaches 0 when X1 reaches 1201 120 Sz reaches 0 when X1 reaches 901 90 83 reaches 0 when X1 reaches 701 70 S4 is unaffected by increases in X1 As we increase X1 the rst quotblockquot occurs at Minimum 120 90 70 00 70 when 83 goes to 0 That is we select the MINIMUM RATIO of the form current basic variable value positive substitution rate Next we would like to quotresolvequot the system so that we obtain a canonical form with X1 being a basic variable and 83 being nonbasic and hence equal to zero PIVOT OPERATION A sequence of elementary row operations which reduce the tableau to canonical form Consider the current tableau piyot column ROW Z X1 X2 81 2 53 S4 RHS Basic 0 l 20 10 0 0 0 0 0 Z 1 0 1 2 1 0 0 0 120 s1 2 0 1 1 0 1 0 0 90 2 3 0 0 0 0 1 0 70 s3 4 0 0 l 0 0 0 l 50 S4 We will pivot on the element in pivot row the row corresponding to the variable leaving the basis and the column corresponding to the variable entering the basis Add 20Row 3 to Row 0 Add lRow 3 to Row 1 Add lRow 3 to Row 2 Resulting Tableau ROW Z X1 X2 81 2 53 S4 RHS Basic 0 l 0 10 0 0 20 0 1400 Z l 0 0 2 l 0 l 0 50 81 2 0 0 1 0 l l 0 20 2 3 0 l 0 0 0 l 0 70 X1 4 0 0 l 0 0 0 l 50 S4 which represent the BFS 83X20 8150 8220 X170 and 8450 with Z1400 ARE WE DONE Again rewriting Z in terms of the basic variables Z1400 10X2 2083 Z can be increased from its current value 1400 by increasing X2 Consider the column of substitution rates for X2 A unit increase in X2 will force us to in order to maintain feasibility decrease 81 by 2 units decrease 82 by 1 unit decrease S4 by 1 unit Conducting the minimum ratio test the maximum increase possible in X2 is given by minimum of 502 20 1 00 501 20 at which point S2 goes to zero and leaves the basis Thus the new basis will have X2 replacing S2 in the basis Now pivot again Current Tableau L Row Z X1 X2 S1 S2 S3 S4 RHS Basic 0 1 0 10 0 0 20 0 1400 Z 1 0 0 2 1 0 1 0 50 S1 2 0 0 D 0 1 1 0 20 2 3 0 1 0 0 0 1 0 70 X1 4 0 0 1 0 0 0 1 50 S4 Row 0 lt Row 0 10Row 2 Row 1 lt Row 1 2Row 2 Row 4 lt Row 4 1Row 2 New Tableau Row Z X1 X2 S1 S2 S3 S4 RHS Basic 0 1 0 0 0 10 10 0 1600 Z 1 0 0 0 1 2 1 0 10 S1 2 0 0 1 0 1 1 0 20 X2 3 0 1 0 0 0 1 0 70 X1 4 0 0 0 0 1 1 1 30 S4 The SIMPLEX method in Tabular Form Maximize z 40x1 60X2 50x3 St 10X14X22X3Sg50 2X1 2X2 S 0 X1 2X3 S 610 X1 X2 X3 2 INITIAL TABLEAU Iteration 0 Row Basic Z x1 x2 x3 S1 S2 S3 RHS 0 Z 1 40 60 50 0 0 0 0 1 S1 0 10 4 2 1 0 0 950 2 S2 0 2 2 0 0 1 0 410 3 S3 0 1 0 2 0 0 1 610 Eq 0 Eq 0 30Eq 2 Eq 1 Eq 1 2Eq 2 Eq 2 12Eq 2 Iteration 1 Row Basic Z x1 x2 x3 S1 S2 S3 RHS 0 Z 1 20 0 50 0 30 0 12300 1 S1 0 6 0 2 1 2 0 130 2 x2 0 1 1 0 0 12 0 205 3 S3 0 1 0 2 0 0 1 610 Eq 0 Eq 0 25Eq 1 Eq 3 Eq 3 1Eq 1 Eq 1 12Eq 1 Iteration 2 ROW Basic Z x1 x2 X3 S1 S2 S3 RHS 0 Z 1 170 0 0 25 20 0 15550 1 x3 0 3 0 1 12 1 0 65 2 x2 0 1 1 0 0 12 0 205 3 S3 0 5 0 0 1 2 1 480 Eq 0 Eq 0 10Eq 3 Eq 1 Eq 1 12Eq 3 Eq 2 Eq 2 14Eq 3 Eq 3 12Eq 3 Iteration 3 ROW Basic Z x1 x2 X3 S1 S2 S3 RHS 0 Z 1 120 0 0 15 0 10 20350 1 x3 0 12 0 1 0 0 12 305 2 x2 0 94 1 0 14 0 14 85 3 S2 0 52 0 0 12 1 12 240 All nonbasic variables have coefficients in Eq 0 that are nonnegative Therefore no neighboring adjacent extreme point could be any better Therefore the optimal value is 2220350 and the optimal solution is x0 85 305 0 240 0T Degeneracy Consider the following LP Max Z 2X1 3X2 St X1 X2 S 3 X1 2X2 S 4 4X1 3X2 S 12 X1 X2 2 0 Iteration 0 ROW Z X1 X2 S1 S2 S3 RHS Basic 0 1 2 3 0 0 0 0 Z 1 0 1 1 0 0 3 S1 2 0 1 2 0 1 0 4 S2 3 0 4 0 0 1 12 S3 Iteration 1 ROW Z X1 X2 S1 S2 S3 RHS Basic 0 1 05 0 0 15 0 6 Z 1 0 0 5 0 1 0 5 0 1 S1 2 0 05 1 0 05 0 2 X2 3 0 25 0 0 15 1 6 S3 Iteration 2 ROW Z X1 X2 S1 S2 S3 RHS Basic 0 1 0 0 1 1 0 7 Z 1 0 1 0 2 1 0 2 X1 2 0 0 1 1 1 0 1 X2 3 0 0 0 5 1 1 1 S3 31 42 23 105 205 625 OPTIMAL SOLUTION All reduced costs are nonnegative so no further increase is possible in the objective Z Suppose instead that we had started by bringing Xlinto the basis at the first iteration rather than X2 Iteration 0 ROW Z X1 X2 1 52 S3 RHS Basic 0 1 2 3 0 0 0 0 Z 1 0 1 1 1 0 0 3 81 2 0 2 0 1 0 4 82 3 0 3 0 0 1 12 83 Iteration 1 Row Z X1 X2 81 2 3 RHS Basic 0 1 0 1 2 0 0 6 Z 1 0 1 1 1 0 0 3 X1 2 0 0 1 1 1 0 1 82 3 0 0 1 4 0 1 0 83 Iteration 2 Row Z X1 X2 81 2 3 RHS Basic 0 1 0 0 1 1 0 7 Z 1 0 1 0 2 1 0 2 X1 2 0 0 1 1 1 0 1 X2 3 0 0 0 5 1 1 1 83 Same optimal solution as before but different route Recall that at Iteration 1 we had a tie for the leaving variable between 81 and 83 and we picked 81 to leave Consider what happens if we had broken the tie in favor of 83 31 42 23 31 11 Iteration 0 ROW Z X1 X2 81 2 3 RHS Basic 0 1 2 3 0 0 0 0 Z 1 0 1 1 1 0 0 3 81 2 0 1 2 0 1 0 4 82 3 0 3 0 0 1 12 83 Iteration 1 ROW Z X1 X2 1 52 S3 RHS Basic 0 1 0 15 0 0 05 6 Z 1 0 0 025 1 0 25 0 81 2 0 0 125 0 1 25 1 82 3 0 1 075 0 0 25 3 X1 Iteration 2 ROW Z X1 X2 81 2 3 RHS Basic 0 1 0 0 6 0 1 6 Z 1 0 0 1 4 0 1 0 X2 2 0 0 0 5 1 1 1 82 3 0 1 0 3 0 1 3 X1 Iteration 3 ROW Z X1 X2 81 2 3 RHS Basic 0 1 0 0 1 1 0 7 Z 1 0 0 1 1 1 0 1 X2 2 0 0 0 5 1 1 1 83 3 0 1 0 2 1 0 2 X1 31 42 23 025 1125 3 75 11 3 Once again we got to the same optimal solution BUT we took one extra iteration note that we got temporarily quotstuckquot at the second iteration there was no improvement in Z Consider the feasible region below for our problem 4 Optimum X12X24 S2 0 A X1 1 392 3 394 39 Extr Pt BFS No Basic Variables Nonbasic Variables A 1 813 824 8312 X1 X2 0 B 2 SllX2 836 X1Sz0 C 3 X12 X2l 831 1 2 0 D 4 X13 821 83 0 1 X2 0 D 5 X13 821 81 0 S3 X2 0 D 6 X13 821 X2 0 81 S3 0 Note that there are three BFS39s corresponding to extreme point D To get to the optimum at C BFS No 3 we took different routes 1 A gtB gtC BFSl gtBFSZ gtBFS3 2 A gtD gtC BFSl gtBFS4 gtBFS3 3 A gtD gtD gtC BFSl gtBFSS gtBFS6 gtBFS3

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.