Class Notes (835,882)
CO 250 (44)
Lecture

# CO327W13_a3_soln.pdf

5 Pages
99 Views

School
Department
Combinatorics and Optimization
Course
CO 250
Professor
Christine Dupont
Semester
Winter

Description
Assignment 3 Due: Wednesday February 27 at the BEGINNING of class T Consider the given LP of the form maxfc xjAx ▯ b;x ▯ 0g: maximize 200x1+ 100x2+ 500x3 subject to 10x + 20x + 40x ▯ 10000 1 2 3 25x1+ 30x2+ 50x3 ▯ 25000 50x1+ 40x2+ 100x3 ▯ 40000 x ▯ 0 For the following questions, show ALL work and refer to part (a) as required. (Hint: You can double check your work using AMPL!) (a) Find the optimal solution of the LP in Standard Equality Form and the corresponding tableau. Solution: Converting the LP into SEF, the tableau is 2 3 1 ▯200 ▯100 ▯500 0 0 0 0 6 0 10 20 40 1 0 0 10000 7 6 7 4 0 25 30 50 0 1 0 25000 5 0 50 40 100 0 0 1 40000 We have canonical form for basis B = f4;5;6g. Let 1 enter the basis. ▯ ▯ 10000 25000 40000 40000 t = min ; ; = = 800 10 25 50 50 6 leaves the basis. Pivot on (3,1). New basis B = f1;4;5g. 2 3 1 0 60 ▯100 0 0 4 160000 6 7 6 0 0 12 20 1 0 ▯1=5 2000 7 4 0 0 10 0 0 1 ▯1=2 5000 5 0 1 4=5 2 0 0 1=50 800 Let 4 enter the basis. ▯ ▯ 2000 800 2000 t = min 20 ;▯; 2 = 20 = 100 4 leaves the basis. Pivot on (1,3). New basis B = f1;3;5g. 2 3 1 0 120 0 5 0 3 170000 6 7 6 0 0 3=5 1 1=20 0 ▯1=100 100 7 4 0 0 10 0 0 1 ▯1=2 5000 5 9 1 ▯2=5 0 ▯1=10 0 1=25 600 We have an optimal solution 1f x = 602, x =30, x = 140, x 5 0, x = 5600, x = 0. (b) What is the optimal dual solution of the LP without determining the dual LP? Solution: Since our LP was given in Standard Inequality Form, we can read the value of the optimal dual variables using the tableau. By reading the values in row zero for the slack variables, the optimal dual solution is y1= 5, y2= 0, y3= 3. (c) Find the shadow prices for the constraints. Solution: Since our LP was given in Standard Inequality Form, the shadow prices are equal to the corresponding dual solution. The shadow prices are 5 for the 1st constraint, 0 for the 2nd constraint, and 3 for the 3rd constraint. (d) Assume we do not know how to ▯nd shadow prices for this LP but we do know how to solve the LP. Give an argument to show why you know that the shadow price of the 2nd constraint should be zero. (Hint: Use the interpretation of the LP as deter- mining production of products to maximize revenue where the constraints are based on resource limitations.) Solution: Our optimal solution in part (a) has x = 5000. If we interpret the LP as suggested 5 in the hint, this means in an optimal production scheme we have 5000 units of the 2nd resource leftover. As such we are unwilling to pay for more of the 2nd resource to increase revenue. Thus, the shadow price for the 2nd constraint should be zero. (e) For each coe▯cient cjin the objective function of the original LP, determine what values c can be changed to and the optimal solution will NOT change. j Solution: For j = 1, it is in the optimal basis. Assuming we chang1 c b1 ▯ , then we have the equivalent tableau: 2 3 1 ▯▯1 120 0 5 0 3 170000 6 0 0 3=5 1 1=20 0 ▯1=100 100 7 4 5 0 0 10 0 0 1 ▯1=2 5000 9 1 ▯2=5 0 ▯1=10 0 1=25 600 Performing row operations we get the canonical form for basis B = f1;3;5g: 2 3 1 0 120 ▯ 0:4▯ 1 0 5 ▯ 0:1▯1 0 3 + 0:04▯1 170000 + 600▯1 6 0 0 3=5 1 1=20 0 ▯1=100 100 7 4 5 0 0 10 0 0 1 ▯1=2 5000 9 1 ▯2=5 0 ▯1=10 0 1=25 600 To have B remaining an optimal basis, we require 120 ▯ 0:41 ▯ 0 ) ▯ ▯1300 5 ▯ 0:11 ▯ 0 ) ▯ ▯150 3 + 0:041 ▯ 0 ) ▯ ▯1▯75 Thus ▯75 ▯ ▯ 1 50 so c1can stay in the range 200 ▯ 75 = 125 ▯ c1▯= 250 = 200 + 50 For j = 2, it is not in the optimal basis. Since the optimal tableau in part (a) has 120 in (0,2), We can change2c by2▯ ▯ 120 so2c can stay in the range
More Less

Related notes for CO 250
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.