Linear Programming Examples
A store has requested a manufacturer to produce pants and sports jackets.
For materials, the manufacturer has 750 m2 of cotton textile and 1,000 m2 of polyester. Every pair of pants (1 unit) needs 1 m2 of cotton and 2 m2 of polyester. Every jacket needs 1.5 m2 of cotton and 1 m2 of polyester.
The price of the pants is fixed at $50 and the jacket, $40.
What is the number of pants and jackets that the manufacturer must give to the stores so that these items obtain a maximum sale?
1Choose the unknowns.
x = number of pants
y = number of jackets
2Write the objective function.
f(x,y)= 50x + 40y
To write the constraints, use a table:
x + 1.5y ≤ 750 2x+3y ≤ 1500
2x + y ≤ 1000
As the number of pants and jackets are natural numbers, there are two more constraints:
x ≥ 0
y ≥ 0
4 Find the set of feasible solutions that graphically represent the constraints.
Represent the constraints graphically.
As x ≥ 0 and y ≥ 0, work in the first quadrant.
Represent the straight lines from their points of intersection with the axes.
Solve the inequation graphically: 2x +3y ≤ 1500, and take a point on the plane, for example (0,0).
2 · 0 + 3 · 0 ≤ 1,500
Since 0 ≤ 1,500 then the point (0,0) is in the half plane where the inequality is satisfied.
Similarly, solve 2x + y ≤ 1,000.
2 · 0 + 0 ≤ 1,000
The area of intersection of the solutions of the inequalities would be the solution to the system of inequalities, which is the set of feasible solutions.
5 Calculate the coordinates of the vertices from the compound of feasible solutions.
The optimal solution, if unique, is in a vertex. These are the solutions to the systems:
2x + 3y = 1,500; x = 0 (0, 500)
2x + y = 1,000; y = 0 (500, 0)
2x + 3y =1,500; 2x + y = 1,000 (375, 250)
6 Calculate the value of the objective function at each of the vertices to determine which of them has the maximum or minimum values. It must be taken into account the possible non-existence of a solution if the compound is not bounded.
In the objective function, place each of the vertices that were determined in the previous step.
f(x, y) = 50x + 40y
f(0, 500) = 50·0 + 40·500 = $20,000
f(500, 0) = 50·500 + 40·0 = $25,000
f(375, 250) = 50·375 + 40·250 = $28,750 Maximum
The optimum solution is to make 375 pants and 250 jackets to obtain a benefit of $28,750.
The solution is not always unique, so we can also find other solutions.
If the objective function of the previous exercise had been:
f(x,y) = 20x + 30y
f(0,500) = 20·0 + 30 · 500 = $15,000 Maximum
f(500, 0) = 20·500 + 30·0 = $10,000
f(375, 250) = 20·375 + 30·250 = $15,000 Maximum
In this case, all the pairs with integer solutions of the segment drawn in black would be the maximum.
f(300, 300)= 20·300 + 30·300 = $15,000 Maximum