Mathematical formulation of LP Problems

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.

(3) solution.

(4) interpretation.

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:

Decision variables

• 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 = c₁x₁ + c₂x₂ + … + c_nx_nwhich is a linear function.

Constraint

A linear relationship representing a restriction on decision making subject to:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n (≤, =, ≥) b₁

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n (≤, =, ≥) b₂

:

a_m1x1 + a_m2x₂ + … + a_mnx_n (≤, =, ≥) b_m

x_j = decision variables

b_i = constraint levels

c_j= objective function coefficients

a_ij = 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 41x₁+ 36x₂+ 96x₃

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.

20x₁+ 30x₂+ 70x₃≥ 110

The constraints for the other nutrients are

10x₁+ 10x₂ ≥ 18

50x₁+ 30x₂≥ 90

6x₁ + 2.5x₂+ 10x₃≥ 110

x_j s≥ 0

This is a mathematical formulation of the LP problem given.