Class Notes (808,147)
CO 250 (44)
Lecture

# CO327W13_a4_soln.pdf

8 Pages
57 Views

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

Description
Assignment 4 Due: Wednesday March 20 at the BEGINNING of class 1. Consider the following LP: maximize 2x1+ x2▯ x 3 3x 4 x 5 x 6 subject to x1+ 2x 2 x 4 x 5 2x 6 = 3 ▯x1+ x 2 2x 3 2x 5 x 6 = 2 x ▯ x + x + x ▯ x + x = 1 1 2 3 4 5 6 x 1x2;x3;x4;x5;x6 ▯ 0 (a) Give the canonical form of the LP for the basis B = f1;2;3g using tableau. Solution: The LP as a tableau is: 2 3 1 ▯2 ▯1 1 ▯3 ▯1 1 0 6 0 1 2 0 1 1 ▯2 3 7 4 5 0 ▯1 1 ▯2 0 2 1 2 0 1 ▯1 1 1 ▯1 1 1 Perform pivots on (1,1), (2,2), and (3,3) to get the canonical form for the basis B = f1;2;3g: 2 3 1 0 0 0 1 1 4 10 6 0 1 0 0 5=3 1=3 4=3 11=3 7 6 7 4 0 0 1 0 ▯1=3 1=3 ▯5=3 ▯1=3 5 0 0 0 1 ▯1 ▯1 ▯2 ▯3 (b) Using the tableau from part (a), perform the Dual Simplex Method to solve the LP. Give the optimal basis, the optimal solution and the optimal value. Solution: From part (a) we see that2x 3 x < 0. We can remove either 2 or 3 from the basis. Let’s remove 2. ▯ ▯ ▯1 ▯4 ▯4 = min ▯1=3; ;▯5=3 = ▯5=3 = 2:4 Thus, 6 enters the basis.Pivot on (2,6) for the canonical form of the basis B = f1;3;6g: 2 3 1 0 12=5 0 1=5 9=5 0 46=5 6 7 6 0 1 4=5 0 7=5 3=5 0 17=5 7 4 0 0 ▯3=5 0 1=5 ▯1=5 1 1=5 5 0 0 ▯6=5 1 ▯3=5 ▯7=5 0 ▯13=5 We see that 3 = ▯13=5 < 0 so we can remove 3 from the basis. ▯ ▯ ▯12=5 ▯1=5 ▯9=5 ▯1=5 1 = min ▯6=5 ▯3=5 ▯7=5 = ▯3=5 = 3 Thus, 4 enters the basis. Pivot on (3,4) for the canonical form for the basis B = f1;4;6g: 2 3 1 0 2 1=3 0 4=3 0 25=3 6 0 1 ▯2 7=3 0 ▯8=3 0 ▯8=3 7 6 7 4 0 0 ▯1 1=3 0 ▯2=3 1 ▯2=3 5 0 0 2 ▯5=3 1 7=3 0 13=3 Since 1 ;6 < 0, we can remove 1 or 6 from the basis. Let’s remove 1. ▯ ▯ ▯2 ▯4=3 ▯4=3 1 = min ; ; = = ▯2 ▯8=3 ▯8=3 2 Thus, 5 enters the basis. Pivot on (1,5) for the canonical form for the basis B = f4;5;6g: 2 3 1 1=2 1 3=2 0 0 0 7 6 0 ▯3=8 3=4 ▯7=8 0 1 0 1 7 4 0 ▯1=4 ▯1=2 ▯1=4 0 0 1 0 5 0 ▯7=8 1=4 3=8 1 0 0 2 We have an optimal tableau for the basis B = f4;5;6g. The optimal solution is x4= 2, x5= 1 and all other variables are zero. The optimal value is 7. 2. Consider the following LP: maximize 200x 1 100x 2 500x 3 subject to 10x 1 20x 2 40x 3 ▯ 10000 25x + 30x + 50x ▯ 25000 1 2 3 50x 1 40x 2 100x 3 ▯ 40000 x ▯ 0 After converting to SEF by adding slack varia4le5 6 ;x ;x , the optimal tableau is: 2 3 1 0 120 0 5 0 3 170000 6 0 1 ▯2=5 0 ▯1=10 0 1=25 600 7 6 7 4 0 0 3=5 1 1=20 0 ▯1=100 100 5 0 0 10 0 0 1 ▯1=2 5000 for the basis B = f1;3;5g. (a) Solve the following modi▯ed LP for the di▯erent values of ▯: maximize 200x 1 100x 2 500x 3 subject to 10x 1 20x 2 40x 3 ▯ 10000 + ▯ 25x 1 30x 2 50x 3 ▯ 25000 ▯ 2▯ 50x 1 40x 2 100x 3 ▯ 40000 + ▯ x ▯ 0 by using the optimal tableau from the original LP. Give the optimal basis for the di▯erent optimal values based on ▯. Solution: We need to calculate the new RHS of the tableau. If the original constraints in SEF were Ax = b, then the new constraints are Ax = b + ▯e ▯ 2▯e + ▯e 1 2 3 Thus, the basic variables for the basis B = f1;3;5g are x = A ▯b + ▯A▯1e ▯ 2▯A▯1e + ▯A▯1e B B B 1 B 2 B 3 = A Bb + ▯AB1A4▯ 2▯A BA 5 ▯A B1A 6 2 3 2 3 2 3 2 3 2 3 x1 600 ▯1=10 0 1=25 4 x35 = 4 100 5 + ▯4 1=20 5 ▯ 2▯4 0 5+ ▯ 4 ▯1=100 5 x5 2 5000 3 0 1 ▯1=2 600 ▯ 3▯=50 4 5 = 100 + ▯=25 5000 ▯ 5▯=2 We can plug these values into the objective function to get a value of 200(600 ▯ 3▯=50) + 100(0) + 500(100 + ▯=25) = 170000 + 8▯ The tableau for the canonical form of the new LP for the basis B = f1;3;5g is 2 3 1 0 120 0 5 0 3 170000 + 8▯ 6 7 6 0 1 ▯2=5 0 ▯1=10 0 1=25 600 ▯ 3▯=507 4 0 0 3=5 1 1=20 0 ▯1=100 100 + ▯=25 5 0 0 10 0 0 1 ▯1=2 5000 ▯ 5▯=2 By forcing the variables to be non-negative: 600 ▯ 3▯=50 ▯ 0 ) ▯ ▯ 10000 100 + ▯=25 ▯ 0 ) ▯ ▯ ▯2500 5000 ▯ 5▯=2 ▯ 0 ) ▯ ▯ 2000 If ▯2500 ▯ ▯ ▯ 2000, then B = f1;3;5g is the optimal basis with optimal value 170000 + 8▯. If ▯ < ▯2500, then 3 leaves the basis. ▯ ▯ = min ; ; ▯3 = ▯3 = 300 ▯1=100 ▯1=100 Thus, 6 enters the basis. Pivot on (2,6) for the basis B = f1;5;6g: 2 3 1 0 300 300 20 0 0 200000 + 20▯ 6 0 1 2 4 1=10 0 0 1000 + ▯=107 6 7 4 0 0 ▯60 ▯100 ▯5 0 1 ▯10000 ▯ 4▯5 0 0 ▯20 ▯50 ▯2:5 1 0 ▯9▯=2 By forcing the variables to be non-negative: 1000 + ▯=10 ▯ 0 ) ▯ ▯ ▯10000 ▯10000 ▯ 4▯ ▯ 0 ) ▯ ▯ ▯2500 ▯9▯=2 ▯ 0 ) ▯ ▯ 0 If ▯10000 ▯ ▯ ▯ ▯2500, then B = f1;5;6g is the optimal basis with optimal value 200000 + 20▯. If ▯ < ▯10000, then 1 leaves the basis. In row 1 of the tableau, all the coe▯cients are non-negative. Thus we cannot perform the Dual Simplex Method any further. The LP is infea
More Less

Related notes for CO 250

OR

Don't have an account?

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.