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

3Write the constraints as a system of inequalities.

To write the constraints, use a table:

pants jackets available
cotton 1 1,5 750
polyester 2 1 1,000

x + 1.5y ≤ 750 flecha 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.

Linear Programming Graph

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.

Intersection of the 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)

Optimal Solution Graph

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.

Example

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.

Optimal Solution Graph

f(300, 300)= 20·300 + 30·300 = $15,000     Maximum




  • Steps to solve a linear programming problem
  •  
  •