### Create a StudySoup account

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

Already have a StudySoup account? Login here

# LINEAR OPTIMIZATION MATH 407

UW

GPA 3.76

### View Full Document

## 25

## 0

## Popular in Course

## Popular in Mathematics (M)

This 6 page Class Notes was uploaded by Addison Beer on Wednesday September 9, 2015. The Class Notes belongs to MATH 407 at University of Washington taught by Staff in Fall. Since its upload, it has received 25 views. For similar materials see /class/192100/math-407-university-of-washington in Mathematics (M) at University of Washington.

## Reviews for LINEAR OPTIMIZATION

### 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: 09/09/15

Problem 1 This problem uses the de nitions in Professor Burke7s notes on Duality 1 Write down the standard form for an arbitrary primal linear programming problem the form used by the simplex algorithm Write down the corresponding dual problem 2 State the Weak Duality Theorem for this pair of primal and dual problems 3 State the Strong Duality Theorem for this pair of primal and dual problems Solution 1 We are given a matrix A E Rmm7 a vector b E Rm7 and a vector 0 E R 1 The corresponding primal problem is P maximize cTz wrt xERZ subject to Ax Sb The corresponding dual problem is D minimize bTy wrt yER f subject to ATy 20 2 Weak Duality Theorem If x is feasible for problem P and y is feasible for problem D then cTz S yTAx S yTb In particular7 if P is unbounded7 then D is infeasible7 and if D is unbounded7 then P is infeasible 3 Strong Duality Theorem If either P or D has nite optimal value the objective supre mum for P or the objective in mum for D is nite7 then both P and D have nite optimal values that are equal In addition7 there are optimal solutions for both P and Problem 2 maximize 7z1 7 x2 7 x3 wrt z E R1 subject to 2x1 7 2x2 x3 3 75 712723 S 1 1 Write down the Phase I feasibility problem in standard form for this linear program 2 Write down the initial tableau for this Phase 1 problem and perform a simplex pivot that results in a tableau corresponding to a basic feasible solution 3 Write down the tableau for the original linear program as stated in this problem Note that is is not primal feasible7 but it is dual feasible Perform one pivot of the dual simplex algorithm on this tableau Solution 2 1 maximize 7 wrt 0717273T E Ri subject to 7z0 2x1 7 2m 3 3 75 70712723 2 The initial tableau for the corresponding Phase 1 problem is X0 X1 X2 X3 sl 52 b 1 2 2 1 1 O 5 1 1 1 2 O 1 1 O 1 1 1 O O O 1 O O O O O O The third row contains the original objective which makes it easier to go on to Phase 117 but it is not necessary for the Phase 1 problem Pivoting on row 1 and column 1 we have X0 X1 X2 X3 sl 52 b 1 2 2 1 1 O 5 O 3 3 3 1 1 4 O 1 1 1 O O O O 2 2 1 1 O 5 for which the basic solution is feasible Note third row corresponds to original objective and fourth row to the Phase I objective7 so the corresponding value of b need not be positive for the basic solution to be feasible 3 The initial tableau corresponding to the linear program in the problem statement is X1 X2 X3 sl 52 b 2 2 1 1 O 5 1 1 2 O 1 1 1 1 1 O O 0 Using the dual simplex algorithm7 we pivot on row 1 and column 2 to obtain D X1 X2 X3 sl 52 b 1 1 12 12 0 52 0 O 32 12 1 72 2 O 32 12 0 52 also could pivot on row 2 and column 3 to obtain X1 X2 X3 sl 52 b 32 32 0 1 12 112 12 12 1 O 12 12 12 32 0 O 12 12 Problem 3 The Three Mines Company owns three di erent mines that produce an ore which after being crushed is graded into three classes high medium and low grade The company has a contract to provide a smelting plant with 20 tons of high grade 20 tons of medium grade and 20 tons of low grade ore per week The three mines have di erent operating characteristics as detailed below Mine Cost High Medium Low 6 One 2 Two 18 4 4 4 Three 16 2 4 6 where Cost is in thousands of dollars per day to operate the corresponding mine High Medium and Low are the number of tons per day produces by the corresponding mine The company is not allowed to operate on Saturday or Sunday Use 1 2 and 3 to denote the decision variables for this problem State what the meaning of the decision variables and nd a matrix A E R6 a vector b E R6 and a vector 0 E R3 such that the optimal solution for maximize cTz wrt z E R1 subject to Ax S b ful lls the contract with the minimal cost Solution 3 We use 1 2 and 3 to denote the number number of days per week that the company operates mine number one two and three respectively 1 0 0 5 0 1 0 5 720 0 0 1 5 A 76 i4 72 7b 720 70 j 74 i4 i4 720 i2 i4 76 720 Problem 4 Prove or disprove the hypothesis that 1 07 2 7 and x3 0 is optimal for the problem maximize 3x1 2x2 4 wrt z E R1 subject to izl 7 x2 7 2x3 lt 74 2x1 3 lt 5 2 2 3 S 7 Solution 4 1 The vector x is feasible because 7z17z272x3 77 lt74 2x1 3 0 lt 5 21233 7 7 2 If x is optimal then there must be a y E R1 that is optimal for the dual and that satis es complementary slackness with respect to x ie 27 0 791y32 7z17x272377lt74 y10 21330lt5 gty20 Thus7 if z is optimal7 then the solution of the dual must be yl 07 yg 07 yg 2 3 The vector y is dual feasible because yi22293 4gt3 791y3 2gt2 72913yz3y3 624 In summary7 z is feasible for the primal7 y is feasible for the dual7 and the pair satis es the complementary slackness condition Thus7 by the complementary slackness theorem7 z is optimal for the primal and y is optimal for the dual 7 As a check7 we note that the primal and dual objectives are equal because 31 22 43 491 592 723 14 9 As an alternative solution One could apply the two phase simplex method to solve the optimization problem As it turns Problem 5 Write the dual of the following linear program directly without converting to the standard form used by the simplex algorithm maximize 1 subject to 2 3 1 7 Sig 103 1 Sig 7 103 Solution 5 minimize yl subject to 12 ya 11 7 512 512 yl 10y2 710y3 wrt 1 6 R7 273T E R1 0 0 wrt yl E R 112793011 6 R2 l 2 0 2 0

### 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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.