### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Linear Programming MA 505

NCS

GPA 3.93

### View Full Document

## 74

## 0

## Popular in Course

## Popular in Mathematics (M)

This 8 page Class Notes was uploaded by Braeden Lind on Thursday October 15, 2015. The Class Notes belongs to MA 505 at North Carolina State University taught by Staff in Fall. Since its upload, it has received 74 views. For similar materials see /class/223715/ma-505-north-carolina-state-university in Mathematics (M) at North Carolina State University.

## Reviews for Linear Programming

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

MAlEOR 505 001 Linear Programming Spring 2007 Final Exam Review Instructor Dr Kartz k Sivammakm shnan INSTRUCTIONS The questions on the nal will be similar to these review problems Work out each problem in suf cient detail If you have any questions7 please send me an email I will post the solutions to selected problems on the course webpage on Friday 1 Consider the linear programming problem min chibTy st Ax 2 b iATy 2 70 z 2 0 y 2 0 where A is a m gtlt n matrix7 b 6 IR and c 6 B a What is the dual to this LP Use the dual to show that the original LP is either infeasible or optimal b Write down the complementary slackness conditions c If the LP is optimal7 then show that the optimal objective value is zero 2 Consider the following optimal dictionary 5 1 1 3 57 271405 1 1 1 1 2245 2 6 3 Z 7447257 of an LP maximization problem7 constraints are of the 3 type It is known that 4 and 5 are the slack variables in the rst and second constraints of the original problem a Write down the original LP and its dual 1 9 7 b Obtain the optimal solutions to the primal and dual LPs directly from the dic tionary c Are there alternate primal and dual optimal solutions Give reasons for your answer Consider the linear program min ch st Ax b 1 z 2 0 where A E IRWX b 6 IR and c E B Suppose we nd a vector d 6 1R satisfying Ad 0 d 2 0 and ch lt 0 Then for any feasible vector x in 1 show that z ad is also feasible for all 04 gt 0 Also show that CTx ad lt ch Deduce that if such a vector d exists then the LP 1 is unbounded Consider the following problem min W 5y1 4y2 st 4y1 3y2 2 4 291 732 2 3 2 91 222 2 1 91 12 2 2 117 12 2 0 Because this primal problem has more functional constraints than variables suppose that the simplex method has been applied directly to its dual problem If we let x5 and x6 denote the slack variables for the dual problem the nal optimal dictionary for the dual problem is 2 11356 x4 372xL 733572x6 3 Z 97317237576 a Construct the optimal dictionary for the primal problem 2 directly from the optimal dictionary 3 for the dual problem A C7 V For each of the following independent changes in the primal problem use sensitiv ity analysis to determine whether the current solution to the primal problem 2 is still feasible and whether it is still optimal Do not reoptimize the new problem Then check your answer by a direct graphical analysis of the primal problem Change the objective function to W 3y1 5y2 Change the right hand sides of the functional constraints to 3 5 2 and 3 respectively Change the rst constraint to 2y1 4y2 2 7 5 03 I 00 Solve the following problem max 74 7 6x2 7 5 st 2x1 3 2 37 3M 2 Z 67 1 2 3 2 0 by the dual simplex method Consider the LP max 1 2 st 1 2 3 3 17 2 S 1 17 2 2 a Sketch the feasible region of the LP and solve it geometrically What is the optimal solution to this LP A C7 V Solve the LP using the decomposition approach treating the rst constraint as the coupling constraint and the remaining constraints as the constraints in the sub problem Restart the decomposition approach in the usual way with the extreme point 07 0 You will need 2 iterations to solve the problem A O V What is the optimal solution generated by the decomposition scheme for the original LP ls this an extreme point solution Kartik is planning to spend the day at the races He will have b available for bet ting On the day of his proposed visit7 there is only one race planned in which horses numbered 17 27 k are competing lf Kartik bets a dollar on the 2th horse7 his gross payoff is 04 for every dollar bet if this horse comes rst in the race7 and 0 otherwise The numbers 041 70 are known positive integers Kartik is7 of course7 allowed to bet any nonnegative amount on any number of horses His problem is to determine how much to bet on each of the horses in the race so as to maximize his minimum gross payoff7 irrespective of whichever horse comes rst in the race Formu late this problem as an LP Write down the special case of this problem when b 1007 k 57 and 0410420430447045 2515713 Solve the following integer programming problem max Z 7x1 2x2 st 74 6x2 3 9 1 2 S 4 172 gt 0 172 inteiger using branch and bound You must follow these details carefully a Solve the linear programming relaxations at each node of the branch and bound tree graphically b In the 1st iteration7 you will have a choice to branch on either 1 or 2 Branch on 2 c Examine the nodes in the branch and bound tree in a breadth rst fashion7 ie7 solve all the subproblerns at one level before proceeding to the next level of the tree d You should enclose the entire branch and bound tree in your solution to get full credit on this problem MAlEOR 505 001 Linear Programming Spring 2007 Midterm Review Instructor Dr Kartz k Sivammakm shnan INSTRUCTIONS The questions on the midterm will be similar to these 10 review problems Work out each problem in suf cient detail If you have any questions7 please send me an email I will post the solutions to selected problems on the course webpage on Tuesday 1 Consider the linear programming problem max 1 x2 st szl x2 3 t 17 2 2 0 a Find some values of s and t such that this linear program has a unique optimum solution7 b multiple optimal solutions7 c no feasible solution LP is infeasible7 and d no optimal solution LP is unbounded Illustrate each case with a gure b Write down the dual LP for each of the four cases What happens to the dual linear program in each of the four cases 2 Consider the following dictionary associated with a linear program in standard form x2 Bia475737 x3 22472x57nx6z7 1 3572677 z 064735767 xm The entries 04 B y 6 77 and b in the dictionary are unknown parameters For each one of the folllowing statements7 nd some parameter values that will make the following statements true a The simplex method can be applied using this as an initial dictionary b The rst row of the dictionary indicates that the problem is infeasible c The corresponding basic solution is feasible7 but we do not have an optimal solu tion 9 7 7 9 d The corresponding basic solution is feasible7 and the rst simplex iteration indi cates that the problem is unbounded e The corresponding basic solution is feasible x6 is a candidate for entering the basis and when 6 enters the basis7 x3 leaves the basis f The corresponding basic solution is feasible x7 is a candidate for entering the basis but if it does7 the solution and the objective value remain unchanged Use a linear programming formulation to show that the following constraints 4 2 S 4 21 7 gig S 6 17 2 2 0 imply 1 2x2 3 8 Verify that z 6010100 is an optimal solution to min 72 13 3 7 2x4 5 5 10 st x17x24z47z5x6747 5 1 74 7 25 36 7 37 Z 71 523742576727 S 5 3962x3z4z5z67967 2 xi 2 07 21 7 using the supervisor principle Consider the linear programming problem min 1 7 2 st 2x1 3x2 7x3z4 S 0 31243724 Z 3 7172234 6 1 S 0 27 3 2 0 Write down the corresponding dual problem Consider the following problem min 2x1 15 5 6x4 st 1 6x2 3 x4 2 2 721 Sig 7 43 34 S 73 xi 2 07 21 74 a Give the dual linear program b Solve the dual problem geometrically c Use the dual optimal solution and the complementary slackness conditions to solve the primal problem 7 Consider the so called aum39llary problem 00 3 min 0 V L st Zaijxjiso S bi 21 7m j1 0 2 0 7 2 07 j1 771 that we encountered during initialization phase 1 of the standard simplex method a b c d What are the complementary slackness conditions for this primal dual pair of LPs Show that the auxiliary problem always possesses a feasible solution Write down the dual to the auxiliary problem Show that the dual problem always possesses a feasible solution too e sing ua 1 y eory7 w a conc usions can you reac a ou e aux1 1ary pro em U d l t th h t l h b t th 1 bl and its dual ln particular7 can the auxiliary problem be unbounded Consider the one constraint knapsack LP max ch st aTz S b x 2 0 where b is a positive scalar ea 6 1R with 07 17 gt 07 j 1 771 Suppose we also 0 c c haveillt72ltlti 01 02 an a Write the dual to this linear program b Construct the optimal solution to the dual problem A c Use complementary slackness conditions to nd the corresponding primal solution Verify that the primal and dual objective values are the same d Verify your observations by solving the following knapsack LP max 3x1 5x2 st 4x1 5x2 10 17 2 0 7 W l using the revised simplex method Let A E Rm z 6 IR and y 6 1R Derive the following theorem of the alternative Theorem 1 The system Ax lt 0 z 2 0 is solvable if and only if the system ATy 2 0 y 2 0 y 31 0 is unsolvable 0 using LP duality along the lines of the proof of Farkas7 theorem in class Note that the strict vector inequality y gt 0 implies that yi gt 0 for all 239 Proceed as follows a Show that if the 1st system is solvable then the 2nd system is unsolvable b Show that if the 1st system is unsolvable then the 2nd system is solvable Hint Rewrite the 1st system as Ax S 6 z 2 0 where e is the m dimensional vector of all ones since LPs deal with inequalities rather than strict inequalities Consider the following problem max Z 01x1 02x2 03 st 1 2x2 3 3 b 21 2 gig S 17273 Z 0 Note that we have not yet assigned values to the coef cients 01 02 and 03 in the objective function7 and the only speci cation for the right hand side of the functional constraints is that the second one 2b be twice as large as the rst Now suppose Kartik has inserted his best estimate of the values of 01 02 03 and b without informing you and then has run the simplex method The optimal dictionary is given below where M and 5 are the slack variables corresponding to the two functional constraints in the linear program7 but you are unable to read the values of Oz and t9 owing to Kartik7s bad handwriting 3 1 170wL 7 7x4 7z5 2 5 5 z 373x172z 3 7 51 54 55 2077 77 W 10951 5954 5955 Compute the following in that order a Find the value of a b Find the values of 01 02 and 03 c Find the value of b d e Calculate the optimal objective value 0 Find the optimal solution y to the dual problem

### 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 signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I 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."

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