The general linear programming problem has the following form:
Minimize z = c1x1 + c2x2 + . . . + cnxn (1)
Subject to:
a11x1 + a12x2 + . . . + alnxn ≥ b1 ... (2)
am1x1 + am2x2 + . . . + amnx ≥ bm
xi ≥ 0 (i = 1, 2, . . ., n).
The linear function (1) is called the objective function while the inequalities (2)
represent the constraints.
To cast the above problem into this form, first find the objective function. Since
cases are being bought, it is desired to minimize:
z = 9S + 12M + 15L. (3)
To obtain the constraints, at least 10 units of manganese are required.
Each small case contains 2 units, each medium case contains 2 units and
each large case contains 1 unit. Thus, the manganese constraint is
2S + 2M + L ≥ 10.
Similarly, the constraints on chromium and molybdenum are obtained:
2S + 3M + L ≥ 12
S + M + 5L ≥ 14.
Thus the problem is:
Minimize z = 9S + 12M + 15L (3)
Subject to:
2S + 2M + L ≥ 10 (4)
2S + 3M + L ≥ 12 (5)
S + M + 5L ≥ 14 (6)
S ≥ 0, M ≥ 0, L ≥ 0. (7)
The region common to the constraints (4) – (7) is called the feasible region.
From the theory of linear programming it is known that a point at which the
objective function is optimized must be on the boundary. Hence, convert the
inequalities in (4) – (7) to equations. A fundamental theorem of
linear programming is that if a solution exists it must be at a point
of intersection of three equations. There are 6 constraints and
three unknowns; hence the number of possible solutions is (6 3) or 20.
For example, the point (0, 0, 0), corresponding to the solution set of S = M = L
= 0, is a possible solution. But since it fails to satisfy the constraints (4) – (6) it
is not a feasible solution. On the other hand, the solution to S = 0, 2S + 2M +
L = 10 and 2S + 3M + L = 12 is (0, 2, 6) which is a feasible point. Substituting
into the objective function (3):
z = 9(0) + 12(2) + 15(6) = $114.
Proceeding in this way for every triplet of equations it is found that
the solution to (4) – (6) is (2, 2, 2). This point satisfies all the contraints,
i.e. , it is feasible. Substituting S = 2, M = 2 and L = 2 in (3):
z = 9(2) + 12(2) + 15(2) = $72.
This is the minimum cost and is the solution to the problem. Two small cases,
2 medium cases and 2 large cases should be bought to obtain
this minimum cost.
