Presentation Transcript

Linear Programming :
Linear Programming is a practical use for solving systems of inequalities. Linear Programming

Slide 2:
Linear programming is a situation that requires you to find maximum or minimum values. You are given constraints represented by linear inequalities. When graphed they will give you a region which represents solutions (ordered pairs that satisfy all the constraints). The maximum or minimum values will be found at the vertices of the region. You will substitute the coordinated of the vertices into an objective function to determine which yield the maximum or minimum values.

Slide 3:
Example 1: On June 24, 1948, the former Soviet Union blocked all land and water routes through East Germany to Berlin. A gigantic airlift was organized using American and British planes to supply food, clothing and other supplies to more than 2 million people in West Berlin. The cargo capacity was 30,000 cubic feet for an American plane and 20,000 cubic feet for a British plane. To break the Soviet blockade, the Western Allies had to maximize cargo capacity, but were subject to the following restrictions: No more than 44 planes could be used. The larger American planes required 16 personnel per flight, double that of the requirement for the British planes. The total number of personnel available could not exceed 512. The cost of an American flight was $9000 and the cost of a British flight was $5000. The total weekly costs could note exceed $300,000.   Find the number of American and British planes that were used to maximize cargo capacity.

Slide 4:
A. Define your variables. Let x = # of American planes Let y = # of British planes. B. Writing an objective function. (We are trying to maximize cargo capacity so…) Z = 30,000x + 20,000y (This equation will not be used until the end to determine the maximum values)

Slide 5:
C. Writing the constraints. There can be no more than 44 planes so… American planes require 16 people while British require half that (8) and the number of people cannot exceed 512 so… American planes cost $9000 while British cost $5000 and there is only $300,000 to spend so… AND there cannot be a negative number of planes so… These are the constraints that must be graphed.

Slide 6:
Get each equation ready to graph: (I will use intercepts for each) x-int: x + 0 = 44 x = 44 y-int: 0 + y = 44 y = 44 x-int: 16x + 8(0) = 512 16x = 512 x = 32 Y-int: 16(0) + 8y = 512 8y = 512 Y = 64 X-int: 9000x + 5000(0) = 300000 9000x = 300000 X = 33.3 y-int: 9000(0) + 5000y + 300000 5000y = 300000 y = 60 These constraints restrict us to the first quadrant where everything is positive

Slide 7:
Now we graph: you will need to set up your axes to reflect the numbers you will need to use. The shading is all below the lines so the “region” is the quadrilateral at the bottom.

Slide 8:
We will need to find the vertices of the region: The y-int of the blue line is (0,44) The x-int of the green line is (33.3,0) The last point is the intersection of any two of the line (they all meet). To find solve the system: x + y = 44 16x + 8y = 512 Multiply the 1st eq by -8 -8x – 8y = -352 16x + 8y = 512 Add the eq and solve: 8x = 160 X = 20 Then y = 24 so (20,24)

Slide 9:
Finally, test the vertices in the objective function: Z = 30,000x + 20,000y (0,44): z = 30,000(0) + 20,000(44) = 880,000 (33.3,0): z = 30,000(33.3) + 20,000(0) = 999,000 (20,24): z = 30,000(20) + 20,000(24) = 1,080,000 We were trying to MAXIMIZE cargo capacity so… The maximum is (20,24) so 20 American planes, 24 British planes for a maximum cargo capacity of 1,080,000 cubic feet.