Linear Programming

Any industrial organization is faced with the problem of taking right decisions or sequence of actions in a decision problem under the restriction of limited resources.  Operations research or Operational research (OS) provides methods for finding the best (optimum) solutions to these problems.

The two factors attributed to the rapid growth of OR are:-

1. The substantial progress that was made in improving the techniques like linear programming, dynamic programming, queuing theory and inventory theory available.
2. The development of the electronic digital computers, with their ability to perform arithmetic calculations millions of times faster than a human, was a tremendous boon.

Mathematical Model

The phases of an OR study includes:-

1. Formulating the problem.
2. Constructing a mathematical model to represent the system under study.
3. Deriving a solution from the model.
4. Testing the model and the solution derived from it.
5. Establishing the controls over the solution.
6. Putting the solution to work-implementation.

Model construction and development represents the crucial step in the implementation of OR. For the construction of a real system one should concentrate primarily on identifying the dominant factors (Variables, constraints, and parameters) that control the behavior of real system. Based on these factors we consider a assumed real system which provides us some relationships in the form of an objective and a set of constraints.

Linear Programming Problems

A mathematical representation of maximizing or minimizing an objective, subject to constraints on decision variables is

Maximize/Minimize Z = f(x₁,x₂,x₃,…..x_n)

Subject to  

          g₁(x₁,x₂,x₃,…..x_n) ≥ b1

          g₂(x₁,x₂,x₃,…..x_n) ≥ b2

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

              g_m(x₁,x₂,x₃,…..x_n) ≥ bm    

  

which is usually referred to as mathematical programming.

If all the functions involved above are linear in the variables x₁,x₂,x₃,…..x_{n with the additional requirement of non-negativity for} x₁,x₂,x₃,…..x_{n, we have  a linear programming problem (LP Problem).}

A LP Problem, in general, is presented in two forms:

1. Canonical form 
2. Standard form 

1. Canonical form:

Maximize Z = C₁X₁+C₂X₂+…..+C_nX_n

_{Subject to} 

                         a₁₁x₁+a₁₂x₂+…..+a_1nx_n= b₁

                                  _{…………………………………}

                         a_m1x₁+a_m2x₂+……+a_mnx_n= b_n

                         x_i ≥ 0, i = 1,2,.....,n

2. Standard form

_{Maximize Z =}  C₁X₁+C₂X₂+…..+C_nX_n

_{Subject to} 

                         a₁₁x₁+a_m2x₂+…..+a_1nx_n= b₁

                                  _{…………………………………}

                         a_m1x₁+a_m2x₂+……+a_mnx_n= b_m

                         x_i ≥ 0, i = 1,2,.....,n

where n ≥ m and  b_i ≥ 0, i = 1,2,.......,m

In both forms the objective functions are maximized.

The situations, which can be modeled through LP, have the following characteristics:

1. There are n competing activities.
2. It is desired to determine the levels of activities.
3. There are m scarce resources.
4. The unit level of each activity consumes a constant amount of every resources.
5. It is desired to maximize(minimize) some measure of effectiveness of the activities.
6. Each unit increase in any level of activity is assumed to have a proportion of increase in the over all measure of effectiveness
7. We rule out the possibility of negative activity levels.

Example:

One of the classical problems of LP is the diet problem. The objective is to determine the quantities of certain foods that should be eaten to meet certain nutritional requirements at a minimum cost. Assume that we have limited our consideration to milk, fish and eggs and to vitamin A,C and D. The following table gives the number of milligrams of each of these vitamins contained within a unit of each food.

Food	Vitamin A	Vitamin C	Vitamin D	Cost
Gallon of Milk	1	100	5	Rs. 1.50/Gallon
Pound of Fish	2	10	90	Rs. 15.00/Pound
Dozens of eggs	10	5	10	Rs.12.00/Dozen
Minimum daily Requirements	1mg	60mg	10mg

LP formulation:

Let x₁, x₂, x₃ be the number of gallons of milk, pounds of fish and dozens of eggs, respectively, in the daily diet.
The objective is to minimize the cost.
Therefore LP model for this problem is the following:

Minimize Z = 1.5x₁+15x₂+12x₃

Subject to
                      x₁+2x₂+10x₃ ≥ 1

                           100 x₁+10x₂+5x₃ ≥ 60

                      5x₁+90x₂+10x₃ ≥ 10

and x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0

The construction of a mathematical model can be initiated by answering the following three questions:

1. What are the decision variables of the problem?
2. What constraints must be imposed on the variables?
3. What is the measure of effectiveness that needs to be achieved to determine the best solution?

Assumptions of LP problem

The assumptions of LP problem that limits its applicability are:

1. Proportionality:
• The objective function and every constraint function must be linear on variables under consideration.
• The measure of effectiveness and resource usage must be proportion to the values of decision variables.
2. Additivity:
• The activities be additive with respect to the measure of effectiveness and each resource usage.
3. Divisibility:
• Require integer optimal solution to decision variables.
4. Deterministic:
• All the coefficients in the LP model are assumed to be known constants.

Graphical Procedure

The method of finding solution graphically to a LP problem involving 2 decision variables, called simplex method. For three or more number of variables this procedure is impractical.

Depict graphically the values of ( x_1, x₂) which satisfies the constraints:

 a₁₁x₁+a₁₂x₂  ≤  b₁ 
 a₂₁x₁+a₂₂x₂  ≥  b₂ 
 a₃₁x₁+a₃₂x₂  ≥  b₃ 

Since uncountable number of values( x_1, x₂) satisfy each constraint, we follow the procedure given below for each constraint.

Step 1: Treat the constraint a₁₁x₁+a₁₂x₂  ≤  b₁ as if it were an equality.

                   a₁₁x₁+a₁₂x₂  =  b₁               

rewrite this as 

                     
      x₁                           x₂ 

_{___________ + ___________}       = 1         

    b₁ / a₁₁            b₁ / a₁₂  


   

                                                                    



To determine which half space represents the inequality  a₁₁x₁+a₁₂x₂  ≤  b₁ , one should observe the sign of b_1. If b₁ is positive, the half space which contains the origin (0,0) represents the feasible region for 'less than' type inequality and the other half space represents that of 'greater than' type inequality.

Step 2: Once the feasible region for each constraint is obtained, their intersection is the feasible region for the totality of all the constraints.

Step 3: If the objective function is Z = C₁X₁+C₂X_2, draw the straight lines

C₁X₁+C₂X₂ = Z ₁ and  C₁X₁+C₂X₂ = Z ₂ for two different constants Z _{1 and} Z _2.

These two lines will be parallel and one can determine the direction in which the objective function C₁X₁+C₂X₂ increases, for increasing values of Z. If the problem is maximization of objective function Z = C₁X₁+C₂X_2, we should determine the objective function line which has the longest distance from the origin but still intersects the set of feasible solutions. One may conclude that such a line will be passing through one of corners or will be coinciding with a side of the set of feasible region. If the former is the case, we get a unique solution to our problem and in the later, an infinite number of solutions.