Linear programming

Linear programming problems

Most management decisions are decisions about how to allocate resources so as to optimize something. One may need to decide how to allocate money so as to maximize the return on an investment or how to allocate people and materials so as to minimize the cost. Often problems of this nature can be solved using linear programming.

Definition A linear programming problem consists of a linear function to be maximized or minimized subject to constraints in the form of linear inequalities.

Example: A cat food company manufactures two products A and B.
Product A sells for $10 per bag and product B sells for $12 per bag. Both products are made of chicken and fish and the only difference between them is the relative amounts of chicken and fish as shown in the table below

compound	amount in 1 bag of A	amount in 1 bag of B	total amount available
chicken	1	2	12
fish	3	2	24

How many bags of each product should be produced to maximize profit ?

Let x = # of bags of product A
and y = # of bags of product B
Then the total profit is P = 10x + 12y.

From the table the total amount of chicken used is x + 2y. Since there are only 12 lbs available we obtain the constraint x + 2y <= 12. Similarly, with the fish we obtain the constraint 3x + 2y <= 24. Summarizing, we obtain the following linear programming problem


Maximize P = 10x + 12y 
subject to the constraints
æ  x + 2y  £  12 ö
ç 3x + 2y  £  24 ÷
ç       x  ³  0  ÷
è       y  ³  0  ø

Exercise

(1) Set up the following linear programming problem.
A company manufactures two products A and B on 
two machines I and II.  The company makes a profit
of $3 per item on each unit of product A and a profit
of $4 per item on each item of product B.  The time
constraints for dthe machines are summarized in the 
following table.  Determine the number of units of
each product that should be produced to maximize 
profit.

machine	time to produce 1 unit of product A	time to produce 1 unit of product B	total time available
I	6 min	9 min	5 hrs
II	5 min	4 min	3 hrs


 Little hint
 Big hint
 Answer