### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for AEDECON 702 with Professor Thraen at OSU

### View Full Document

## 14

## 0

## Popular in Course

## Popular in Department

This 20 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Ohio State University taught by a professor in Fall. Since its upload, it has received 14 views.

## Popular in Subject

## Reviews for Class Note for AEDECON 702 with Professor Thraen at OSU

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

43 The Simplex Algorithm max LPs Consider the simplex algorithm applied to the maximization below The Dakota Furniture company manufactures desk tables and chairs The manufacturer of each type of furniture requires lumber and two types of skilled labor finishing and carpentry The amount of each resource needed to make each type of furniture is given in the table below Resource Desk Table Chair Lumber 8 board ft 6 board ft 1 board ft Finishing hours 4 hours 2 hours 15 hours Carpentry hours 2 hours 15 hours 05 hours At present 48 board feet of lumber 20 finishing hours 8 carpentry hours are available A desk sells for 60 a table for 30 and a chair for 20 Dakota believes that demand for desks and chairs is unlimited but at most 5 tables can be sold Since the available resources have already been purchased Dakota wants to maximize total revenue Define x1 number of desks produced x2 number of tables produced x3 number of chairs produced The LP is max 2 60x1 30x 20x3 st 8x1 6xZ X3 S 48 4x1 2xZ 15X3 S 20 2x1 15x 05X3 S 8 xZ S 5 X1 X2 X3 2 0 lumber constraint finishing constraint carpentry constraint table demand constraint 43 The Simplex Algorithm max LPs Step 1 Convert the LP to Standard Form Canonical Form Basic Variable Row 0 z 60x1 30x2 20x3 0 z 0 Row 1 8x1 6x2 x3 51 48 51 48 Row 2 4x1 2x2 15x3 52 20 52 20 Row 3 2x1 15x2 05x3 53 8 53 8 Row 4 x2 54 5 s4 5 If we set X1 X2 X3 0 we can solve for the values s1 52 s3 s4 Thus BV 1 52 S3 s4 and NBV X1 X2 X3 Since each constraint is then in canonical form BVs have a coefficient 1 in one row and zeros in all other rows with a nonnegative rhs a bfs can be obtained by inspection 43 The Simplex Algorithm max LPs Step 2 Obtain a Basic Feasible Solution To perform the simplex algorithm we need a basic although not necessarily nonnegative variable for row 0 Since 2 appears in row 0 with a coefficient of 1 and 2 does not appear in any other row we use 2 as the basic variable With this convention the basic feasible solution for our initial canonical form has BV 2 S1 82 S3 S4 and NV x1 X2 X3 For this initial bfs z 0 s1 48 2 20 s3 854 5 X1 X2 X3 0 As this example indicates a slack variable can be used as a basic variable if the rhs of the constraint is nonnegative 43 The Simplex Algorithm max LPs Step 3 Determine if the Current BFS is Optimal Once we have obtained a bfs we need to determine whether it is optimal To do this we try to determine if there is any way 2 can be increased by increasing some nonbasic variable from its current value of zero while holding all other nonbasic variables at their current values of zero Solving for z in row 0 yields 2 60X1 30 X2 20x3 For each nonbasic variable we can use the equation above to determine if increasing a nonbasic variable while holding all other nonbasic variables to zero will increase 2 Increasing any of the nonbasic variables will cause an increase in 2 However increasing x1 causes the greatest rate of increase in z If x1 increases from its current value of zero it will have to become a basic variable For this reason x1 is called the entering variable Observe x1 has the most negative coefficient in row 0 43 The Simplex Algorithm max LPs The Ratio Test When entering a variable into the basis compute the ratio rhs of row I coefficient of entering variable in row for every constraint in which the entering variable has a positive coefficient The constraint with the smallest ratio is called the winner of the ratio test The smallest ratio is the largest value of the entering variable that will keep all the current basic variables nonnegative 43 The Simplex Algorithm max LPs Step 4 We choose the entering variable in a max problem to be the nonbasic variable with the most negative coefficient in row 0 ties broken arbitrarily We desire to make x1 as large as possible but as we do the current basic variables s1 s2 s3 s4 will change value Thus increasing x1 may cause a basic variable to become negative RAT0 From row 1 we see that s1 48 8x1 Since s1 2 0 x1 S 48 8 6 From row 2 we see that s2 20 4x1 Since s2 2 0 x1 S 204 5 From row 3 we see that s3 8 2x1 Since s3 2 0 x1 S 8 2 4 From row 4 we see that s4 5 For any x1 s4 will always be 2 0 This means to keep all the basic variables nonnegative the largest we can make x1 is min 6 5 4 4 43 The Simplex Algorithm max LPs To make X1 a basic variable in row 3 we use elementary row operations ero s to make X1 have a coefficient of 1 in row 3 and a coefficient of 0 in all other rows This procedure is called pivoting on row 3 and row 3 is called the pivot row The final result is that X1 replaces S3 as the basic variable for row 3 The term in the pivot row that involves the entering basic variable is called the pivot term The GaussJordan method using ero s and simplex tableaus shown on the next slide makes X1 a basic variable For review see Chapter 2 l39 ro 1 2 x1 x2 x3 51 52 s3 s4 rhs em 0 1 60 30 20 1 8 6 1 1 48 2 4 2 15 1 20 V 3 Q 075 025 05 4 row 3 divided by 12 i 4 1 1 5 era 2 2 x1 x2 x3 51 52 s3 s4 rhs 0 1 15 5 30 240 60 times row 3 added to row 0 1 8 6 1 1 48 2 4 2 15 1 20 3 1 075 025 05 4 4 1 1 5 era 3 2 x1 x2 x3 51 52 s3 s4 rhs i 0 1 15 5 30 240 1 1 1 4 16 8 times row 3 added to row 1 2 4 2 15 1 20 3 1 075 025 05 4 4 1 1 5 V era 4 2 x1 x2 x3 s1 s2 s3 s4 rhs 0 1 15 5 30 240 1 1 1 4 16 2 1 05 1 2 4 4 times row 3 added to row 2 3 1 075 025 05 4 4 1 1 5 43 The Simplex Algorithm max LPs The result is Canonical Form 1 Row 0 z 15x2 5x3 3083 240 Row 1 x3 51 453 16 Row2 x205x3 s2 253 4 Row3 x1 075x2 02 5x3 0533 4 Row 4 x2 34 5 Basic Variable z240 In canonical form 1 BV 2 s1 52 x1 54 and NBV 53 xz X3 yielding the bfs z 240 S1 16 2 4 x1 4 s4 5 s3 x2 x3 0 The procedure of going to one bfs to a better adjacent bfs is called an iteration or a pivot of the simplex algorithm 43 The Simplex Algorithm max LPs Returning to Step 3 we attempt to determine if the current bfs is optimal A a L il Rlydl jf mgimg o from lt Z 240 15X2 5X3 30 S3 The current bfs is NOT optimal because increasing X3 to 1 while holding the other nonbasic variable to zero will increase the value of 2 Making either x or 3 basic will caused the value of z to decrease Step 4 Recall the rule for determining the entering variable is the row 0 coefficient with the greatest negative value Since x3 is the only variable with a negative coefficient x3 should be entered into the basis w 1 net i Begin iteration pivot 2 Performing the ratio test using X3 as the entering variable yields the following results holding other NBVs to zero From row 1 s1 2 0 for all values of X3 since 81 16 X3 From row2sZ20 ifxslt4I058 From row3x12 0 ifxs lt 4025 16 From row 4 s4 2 0 for all values of x3 since s4 5 This means to keep all the basic variables nonnegative the largest we can make X1 is min 816 8 So row 2 becomes the pivot row Step 5 Now use ero s to make x3 a basic variable in row 2 Erin 1 x1 x2 x3 s1 52 s3 rhs 0 15 5 30 240 1 1 1 4 16 2 2 Q 2 4 8 multiplied row 2 by 2 3 1 075 0 5 05 4 4 1 5 era 2 x1 x2 x3 51 52 3 rhs 0 5 10 10 280 add 5 times row 2 to row 0 1 1 1 4 16 2 2 1 2 4 8 3 1 075 025 05 4 4 1 5 era 3 x1 x2 x3 51 52 3 rhs 0 5 10 10 280 1 2 1 2 8 24 add row 2 to row 1 2 2 1 2 4 8 3 1 075 025 05 4 4 1 5 era 4 x1 x2 x3 51 52 3 rhs 0 5 10 10 280 1 2 1 2 8 24 2 2 1 2 4 8 3 1 125 05 15 2 add 14 times row 2 to row 3 4 1 5 43 The Simplex Algorithm max LPs The result is Canonical Form 2 Basic Variable Row 0 z 5x2 1052 1053 280 z 280 Row 1 2X2 51 252 853 24 s1 24 Row 2 2x2 x3 252 453 8 x3 8 Row 3 x1 125x2 05 52 1553 2 x1 2 Row 4 x2 54 5 s4 5 In Canonical Form 2 BV 2 51 x3 x1 54 and NBV 53 82 x2 yielding the bfs z 280 s1 24 X3 8 X1 2 s4 582 3 xa 0 43 The Simplex Algorithm max LPs Solving for z in row 0 yields Z 280 5X2 10s2 10s3 We can see that increasing X2 s2 or s3 while holding the other NBVs to zero will not cause the value of z to increase The solution at the end of iteration 2 is therefore the optimal basic feasible solution The following rule can be applied to determine whether a canonical form s bfs is optimal A canonical form is optimal for a max problem if each nonbasic variable has a nonnegative coefficient in the canonical form s row 0 ROW 0 Z 5X2 1052 1053 280 Z 280 44 The Simplex Algorithm min LPs Consider the LP minimization m39quot z 2x1quot 3x2 model shown to the right St X1 X2 5 4 X1 X2 5 6 Method 1 X1 x2 2 0 The optimal solution is the point X1X2 that makes 2 2X1 3X2 the smallest Equivalently this point st X1 x2 5 4 makes max z 2x1 3x the largest This means we can find the optimal solution to the LP by X1 XZ a o solving the LP shown to the right max z 2x1 3xa X1X256 The optimal solution to the max problem is z 12 x2 4 s2 10 x1 s1 0 Then the optimal solution to the min problem is z 12 x24 s2 10 x1 s2 0 The min LP objective function confirms this 2 2x1 3X2 20 3 4 12 46 Unbounded LPs For some LPs there exist points in the feasible region for which 2 assumes arbitrarily large in max problems or arbitrarily small in min problems values When this occurs we say the LP is unbounded An unbounded LP occurs in a max problem if there is a nonbasic variable with a negative coefficient in row 0 and there is no constraint that limits how large we can make this NBV

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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