false

Class Notes
(835,882)

Canada
(509,468)

University of Waterloo
(18,569)

CO 250
(44)

Christine Dupont
(9)

Lecture

Unlock Document

Combinatorics and Optimization

CO 250

Christine Dupont

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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.