Editing LinearProgrammingExample
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Fri Apr 26 07:56:22 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
Example: A farmer has 90 acres on which he may raise peanuts and corn. He has accepted orders requiring at least 10 acres of peanuts and 5 acres of corn. He also must follow a regulation that the acreage for corn must be at least twice the acreage for peanuts. If the profit is $100 per acre of corn and $200 per acre of peanuts, how many acres of each will give him the greatest profit? ---- COLUMN_START^ We want to know the acreage for corn and the acreage for peanuts. Let's represent them by X and Y: * X = acres of corn * Y = acres of peanuts Shown at right is our graph to start with: COLUMN_SPLIT^ http://www.solipsys.co.uk/new/images/x3.png COLUMN_END ---- COLUMN_START^ We are told that he has 90 acres in all, so we know that X+Y <= 90. That's a constraint. COLUMN_SPLIT^ http://www.solipsys.co.uk/new/images/x4.png COLUMN_END ---- COLUMN_START^ We are told that his orders require at least 10 acres of peanuts, so Y >= 10. We are also told that his orders require 5 acres of corn, so X >= 5 (remember, X is corn) COLUMN_SPLIT^ http://www.solipsys.co.uk/new/images/x5.png COLUMN_END ---- COLUMN_START^ The next constraint is that the regulations state that the acreage for corn must be at least twice the acreage for peanuts. That means that X >= 2Y COLUMN_SPLIT^ http://www.solipsys.co.uk/new/images/x6.png COLUMN_END ---- COLUMN_START^ Now we know we are inside this area. I've marked the corners because the basic theorem, the most fundamental fact in Linear Programming is this: |>> [[[ |>> The answer is always _ at a corner of the _ permitted region. <<| ]]] <<| COLUMN_SPLIT^ http://www.solipsys.co.uk/new/images/x7.png COLUMN_END ---- COLUMN_START^ So we solve the equations to find the corners, and we get three solutions: So: * X=20, Y=10 * X=60, Y=30 * X=80, Y=10 You should check that all the constraints are met by these solutions. COLUMN_SPLIT^ http://www.solipsys.co.uk/new/images/x8.png COLUMN_END ---- The final step, get the maximum profit. COLUMN_START^ We know that the profit is 100X + 200Y. Which of these solutions gives the most profit, and how much profit does he make? One thing we can do is simply evaluate the objective function at each vertex of the region. The other thing is we can plot 100X+200Y=C for various values of C. Different values of C give parallel lines, and our objective is to get C as large as possible while still having the line intersect the area. Here we've plotted the lines for C=0, C=9000 and C=18000. See how as C increases the line moves up and to the right. C=18000 clearly has the line moved too far, so we need to work out the last place the line touches in the region as the line moves. That point is where X=60 and Y=30. If the line had a different slope then it might last touch somewhere else. COLUMN_SPLIT^ http://www.solipsys.co.uk/new/images/x9.png COLUMN_END