Chapter 3 Linear Programming

Linear Programming (LP) is a tool for solving optimization (minimization or

maximization) problems. LP is applied in various areas such as industries, banking,
education, forestry etc.
Programming problems are generally concerned with the allocation of scarce resources.
These resources include labour, capital, machines, material, etc. The resources are to be
allocated in such a way as to minimize costs or maximize profits.
We illustrate the ideas of linear programming with the help of an example below.

Example 3.1
A furniture company makes and sells tables and chairs. Each table requires board-feet
of oak, board-feet of pine, and labour-hours. Each chair requires 2 board-feet of
oak, 3 board-feet of pine and 3 labour hours. There are 122 board feet of oak, 100 board
feet of pine and 120 labour hours available for the upcoming week. How many tables and
chairs should the company make during the next week so as to maximize its profit given
that each table makes a profit of and each chair makes a profit of ?

Solution 3.1
There are many combinations of table and chair production. The problem is which
combination to choose in order to make maximum profit.

Table 3.1: Resources required per product unit

Oak board- feet Pine board -feet Labour hours Profit per unit
Tables 5 2 4 12
Chairs 2 3 3 8
Available 122 100 120
resources

This problem can be solved by formulating equations and inequalities using the data
available.
Let be the number of tables to produce next week and let be the number of chairs to
produce next week.
Using these variables, the profit function to be formed is as follows:
(3.1)
and in (3.1) are called decision variables. In order to solve our problem we have to
take decisions on these variables to determine the values they take. Equation (3.1) is
called the objective function because it describes our objective in solving the problem.
In order to maximize the profit we have to maximize , subject to the
restrictions on and . These restrictions are called constraints.

We need to use board-feet of oak for each table and 2 board-feet of oak for each chair.
The available oak board-feet is 122. Thus, if we are producing tables and chairs then
the total oak board-feet needed is and this should not exceed 122. Or
mathematically, .

1
Similarly, the available restrictions on pine board-feet and labour hours results in
and respectively. Thus, the three constraints in producing
tables and chairs are

, , .

The coefficients of the decision variables in the constraints are called technological
coefficients.

In addition to these, we have to put non negativity constraints on the variables

themselves, as they are number of tables and chairs. That is .
These are called non-negativity constraints.
In summary the linear programming model is:

Maximize

Subject to

and .

Definition 3.1: A linear programming problem is a mathematical problem that is

concerned with optimizing (maximizing or minimizing) a linear function of the decision
variables subject to a system of linear constraints (equalities or inequalities).
A general minimization linear programming problem may be algebraically stated as
below:

Minimize
Subject to

. . . .
. . . .
. . . .

, ,… .

Note: We may represent the problem in matrix notation also.

Suppose we try to represent the constraints of Example 7.1 graphically. Each less than or
equal to resource constraint and each non negativity restriction establishes a boundary

2
constraint for the objective function. When all boundaries are considered together, the
resulting area consisting of points corresponding to possible solution values for the
problem. This region is referred to as the region of feasible solutions.
It may be noted that the non negativity constraint restricts to first quadrant.

60

50

40

30

20

10
0
10 20 30 40 50 60 70 80

The shaded region satisfies the constraints of the given problem. Therefore, the solution
to the problem lies in the shaded region.
It may be proved mathematically (using the theory of convex sets) that the solution
lies on one of the vertices of the shaded region (proof is avoided at this stage).
Let us look into the vertices of this shaded region. There are 5 vertices altogether. The
coordinates and the corresponding value of the objective function are given below.
Vertex Coordinates P

It can be seen that the optimum solution is reached at and . In other words
the maximum profit is achieved at the said quantities above.

Example 3.2: Diet Mix problem

A dog food seller decided that his diet mix must contain at least 10 units of proteins, 5
units of carbohydrates, and 12 units of vitamins. There are two ingredients that he can use
to obtain the desired mix. Each pound of ingredient contains 2 units of proteins, 2
units of carbohydrates and 2 units of vitamins. Each pound of ingredient contains 3

3
units of proteins, 1 unit of carbohydrates and 4 units of vitamins. Ingredient costs
per pound and costs per pound. How would the mix be made so that it
has sufficient proteins, carbohydrates and vitamins and its cost is as low as possible?

Solution 3.2
Table 3.2
units/pound units/pound Minimum requirements

Proteins 2 3 10
Carbohydrates 2 1 5
Vitamins 2 4 12
Cost per pound

Here the problem is to determine the amount of each ingredient ( and ) so that the
resulting mix has sufficient proteins, carbohydrates and vitamins and its cost is as low as
possible.
Let be the number of pounds of ingredient to use and be the number of pounds of
ingredient to use.
The objective function is and
the constraints are: , , , , .

So the linear programming model is:

Minimize
Subject to

The graphical solution may be obtained as below.

4
 7

0
1 2 3 4 5 6 7

Vertex Coordinates C

The optimum solution is attained at and . That is, the cost function is

minimum at and .
Note: In our discussion, we have considered LP problems with two decision variables. In
a practical situation, there can be several variables. However, graphical representation is
possible only in the case of a 2-dimensional problem. One has to employ other methods
to solve the LP problems of higher dimensions. One such important method is
SIMPLEX ALGORITHM.

5
Exercises
1. Solve the following linear programming problem.
Maximize subject to .
2. Maximize subject to
.
3. Minimize subject to .
4. Minimize subject to .
5. An ice cream manufacturer blends ingredients A, B and C in varying proportions to
make two types of ice cream: Regular (R) and Extra rich (E). Each litre of R contains 0.1
litre of A, 0.2 litre of B, and 0.4 litre of C. Each litre of E contains 0.5 litre of A, 0.2 litre
of B, and 0.1 litre of C. The profits on ice cream R and E are P40 and P20 per litre
respectively. If the manufacturer has 50 litres of A, 80 litres of B, and 100 litres of C
available, how many litres of each type of ice cream should be made to maximize the
profit?
6. Joe Armstrong has 250 acres of land on which to plant corn and soybeans. Each acre of
corn requires 4 units of storage space and 2 hours of labour. Each acre of soybeans
requires 5 units of storage space and 9 hours of labour. Corn returns P140 profit per acre
and soybeans return P150 per acre. Given that there are 1500 labour hours and 600 units
of storage space, how many acres should be devoted to each crop?
7. Maximize subject to
8. Maximize subject to .
9. Determine the minimum value of the objective function subject to
constraints:
10. Maximize subject to .
11. A furniture manufacturer makes two types of chairs – one that reclines and other one
that does not. The recliner chair requires 2 hours assembly time and 1 hour of packing
time. The non-recliner chair requires 1 hour of assembly and 1 hour of packing time.
Each month, the manufacturer has 420 work-hours available for assembly and 300 work-
hours for packing. The profit on each recliner chair is P140 and that on each non-recliner
chair is P100. How many chairs of each type should be produced per month in order to
maximize profit?
12. A farmer has at most 500 acres on which to plant two crops-tomatoes and cotton.
Producing tomatoes requires 2 hours of labour per acre and cotton requires 3 hours of
labour per acre. The farmer has 1200 hours of labour available. If the profit per acre is
P80 for tomatoes and P100 for cotton, how many acres of each crop should be planted to
maximize profit?
13. A rancher has 1500 acres of grazing pasture to raise sheep and cattle. The rancher has
the resources to raise no more than 4800 animals. Each acre of pasture sustains 2 cows or
6 sheep. The profit on each acre of gazing cow is P80 and that on sheep is P90. How
many acres should be allotted for cattle and sheep in order to maximize the profit?
14. A pet-store owner has decided to make and sell dog food. He has decided that the mix
must contain at least 10 units of protein, 5 units of carbohydrates and 12 units of
vitamins. There are two ingredients that he can use to obtain the desired mix. Each
kilogram of ingredient A contains 2 units of protein, 2 units of carbohydrates and 2 units
of vitamins. Each kilogram of ingredient B contains 3 units of protein, 1 unit of

6
carbohydrates and 4 units of vitamins. Ingredient A costs P0.25 per kilogram and
ingredient B costs P0.30 per kilogram. How should the mix be made so that it has
sufficient protein, carbohydrates and vitamins, and its cost is as low as possible?