The development of all LP models can be examined in a four-step process:
(1) identification of the problem as solvable by LP
(2) formulation of the mathematical model.
The formulation of the mathematical problem involves translation of a problem scenario to a simple L.P framework containing a set of mathematical relationships. For the formulation we identify the components of L.P:
- mathematical symbols representing levels of activity of an operation
- these variables are continuous which means that they can have any value within a restricted range provided in the prompt.
The objective function
- a linear relationship reflecting the objective of an operation
- it is the sum of terms made by variable coefficient ratio.
- a most frequent objective of business firms is to maximize profit
- a most frequent objective of individual operational units (such as a production or packaging department) is to minimize cost
Max/min z = c1x1 + c2x2 + … + cnxnwhich is a linear function.
A linear relationship representing a restriction on decision making subject to:
a11x1 + a12x2 + … + a1nxn (≤, =, ≥) b1
a21x1 + a22x2 + … + a2nxn (≤, =, ≥) b2
am1x1 + am2x2 + … + amnxn (≤, =, ≥) bm
xj = decision variables
bi = constraint levels
cj= objective function coefficients
aij = constraint coefficients
It is simpler to express each constraint in words to present them in mathematical form. The formulation process is iterative, and at times more variables need to be defined or existing variables redefined to validate the problem
Example: International Wool Company operates a large farm on which sheep are raised. The farm manager determined that for the sheep to grow, at least minimum amounts of four nutrients present in grains are required. As long as a sheep receives the minimum daily amount of each nutrient as shown in the table below, it will be healthy to produce a standard amount of wool. The manager wants to optimize his problem and raise the sheep at a minimum cost for optimum amount of wool.
Decision variable: xj= number of pounds of grain j to feed each sheep daily
The daily feed cost per sheep is
(cost per lb of grain j) X (lb. of grain j fed to each sheep daily)
The objective function is to
Minimize z 41x1+ 36x2+ 96x3
The values of the variables is obtained so that the number of units of nutrient a consumed daily by each sheep is equal or more than 110.
20x1+ 30x2+ 70x3≥ 110
The constraints for the other nutrients are
10x1+ 10x2 ≥ 18
50x1+ 30x2≥ 90
6x1 + 2.5x2+ 10x3≥ 110
xj s≥ 0
This is a mathematical formulation of the LP problem given.