Unit-II

Mathematical formulations of LP Models for Product- Mix Problems:

Maximization Case:

Let's understand the maximization case with the help of a problem. Suppose a firm produces two products A and B. For
producing the each unit of product A, 4 Kg of Raw material and 6 labor hours are required. While, for the production of each
unit of product B, 4 kg of raw material and 5 labor hours is required. The total availability of raw material and labor hours is 60
Kg and 90 Hours respectively (per week). The unit price of Product A is Rs 35 and of product, B is Rs 40.

This problem can be converted into linear programming problem to determine how many units of each product should be
produced per week to have the maximum profit. Firstly, the objective function is to be formulated. Suppose X1 and X, are
units produced per week of product

A and B respectively. The sale of product A and product B yields Rs 35 and Rs 40 respectively. The total profit will be equal to

Z=35x₁+ 40x2 (objective function)

Since the raw material and labor is in limited supply the mathematical relationship that explains called inequality. Therefore,
the inequality equations will be as follows:

Product A requires 4 kg of raw material and product B also requires 4 Kg of Raw material; thus, total consumption is 4X1+4X2,
which cannot exceed the total availability of 60 kg. Thus, this constraint can be expressed as:

4X1+ 4X2≤ 60

Similarly, the second constraint equation will be:

6x1+5x2≤ 90

Where 6 hours and 5hours of labor is required for the production of each unit of product A and B respectively, but cannot
exceed the total availability of 90 hours.

Thus, the linear programming problem will be:

Maximize Z = 35x1+ 40x2 (profit)

Subject to:

4X1 + 4x2≤ 60 (raw material constraint)

6x1+5x2≤ 90 (labor hours constraint)

X1, X2 ≥ 0 (Non-negativity restriction)

Note: It is to be noted that "<" (less than equal to) sign is used as the profit maximizing output may not fully utilize all the
resources, and some may be left unused. And the non-negativity condition is used since the x and x2 are a number of units
produced and cannot have negative values.
Minimization Case:

The minimization case can be well understood through a problem. Let's say; the agricultural research institute recommended a
farmer to spread out at least 5000 kg of phosphate fertilizer and not less than 7000 kg of nitrogen fertilizer to raise the
productivity of his crops on the farm. There are two mixtures A and B, weighs 100 kg each, from which these fertilizers can be
obtained.

The cost of each Mixture A and B is Rs 40 and 25 respectively. Mixture A contains 40 kg of phosphate and 60 kg of nitrogen
while the Mixture B contains 60 kg of phosphate and 40 kg of nitrogen. This problem can be represented as a linear
programming problem to find out how many bags of each type a farmer should buy to get the desired amount of fertilizers at
the minimum cost.

Firstly, the objective function is to be formulated. Suppose, x₁ and x2are the number of bags of mixture A and mixture B. The
cost of both the mixture is 40x1 + 25x2 and thus, the objective function will be:

Minimize

Z=40x1+25x2

In this problem, there are two constraints, minimum 5000 kg of phosphate and minimum 7000 kg of nitrogen is required. The
Bag A contains 40 kg of phosphate while Bag B contains 60 kg of phosphate. Thus, the phosphate constraint can be expressed
as:

40x1+60x2≥5000

Similarly, the second constraint equation can be expressed as:

60x1 +40x2≥ 7000

Where, Bag A contains 60 kg of nitrogen and Bag B contains 40 kg of nitrogen, and the minimum requirement of nitrogen is
7000 kg.

Thus, the linear programming problem is:

Minimize Z = 40x₁+25x2 (cost)

Subject to:

40x1+60x2≥5000 (Phosphate Constraint)

60x₁+40x2≥7000 (Nitrogen Constraint)

X1, X2 ≥ 0 (Non-negativity Restriction)

Note: It is to be noted that, "2" (greater than equal to) sign shows the full utilization of resources at the minimum cost. The
non- negativity condition is used, since x₁ and X2 represent the number of bags of both the mixture and hence cannot have the
negative values.
Graphical and Simplex Method of Solving LP problems:
The Graphical Method (graphic solving) is an excellent alternative for the representation and solving of Linear Programming
models that have two decision variables.

Exercise #1: A workshop has three (3) types of machines A, B and C; it can manufacture two (2) products 1 and 2, and all
products have to go to each machine and each one goes in the same order; First to the machine A, then to B and then to C.
The following table shows:

 The hours needed at each machine, per product unit

 The total available hours for each machine, per week
 The profit of each product per unit sold
 Product 1 Units to be produced weekly
 Product 2 Units to be produced weekly

Objective Function:

Maximize Z

Constraints:

The constraints represent the number of hours available weekly for machines A, B and C, respectively, and also incorporate
the non- negativity conditions.

For the graphical solution of this model we will the Graphic Linear Optimizer (GLP) software. The green colored area
corresponds to the set of feasible solutions and the level curve of the objective function that passes by the optimal vertex is
shown with a red dotted line.

The optimal solution is and with an optimal value that represents the workshop's profit.
 Simplex Method:
The Simplex Method or Simplex Algorithm is used for calculating the optimal solution to the linear programming problem. In
other words, the simplex algorithm is an iterative procedure carried systematically to determine the optimal solution from the
set of feasible solutions.

Firstly, to apply the simplex method, appropriate variables are introduced in the linear programming problem, and the primary
or the decision variables are equated to zero. The iterative process begins by assigning values to these defined variables. The
value of decision variables is taken as zero since the evaluation in terms of the graphical approach begins with the origin.
Therefore, x₁ and x2 is equal to zero.

The decision maker will enter appropriate values of the variables in the problem and find out the variable value that
contributes maximum to the objective function and removes those values which give undesirable results. Thus, the value of
the objective function gets improved through this method. This procedure of substitution of variable value continues until any
further improvement in the value of the objective function is possible.

Following two conditions need to be met before applying the simplex method:

1. The right-hand side of each constraint inequality should be non-negative. In case, any linear programming problem has a
negative resource value, then it should be converted into positive value by multiplying both the sides of constraint inequality
by "-1".

2. The decision variables in the linear programming problem should be non- negative.

Thus, the simplex algorithm is efficient since it considers few feasible solutions, provided by the corner points, to determine
the optimal solution to the linear programming problem.

Duality:
The Duality in Linear Programming states that every linear programming problem has another linear programming problem
related to it and thus can be derived from it. The original linear programming problem is called "Primal," while the derived
linear problem is called "Dual."

Before solving for the duality, the original linear programming problem is to be formulated in its standard form. Standard form
means, all the variables in the problem should be non-negative and "," "<" sign is used in the minimization case and the
maximization case respectively.

The concept of Duality can be well understood through a problem given below:

Maximize Z=50x₁+30X2

Subject to: 4X1+3X2≤100

3x1 +5x2≤150

X1, X2 ≥0

The duality can be applied to the above original linear programming problem as:
Minimize G = 100y₁+150у2

Subject to: 4y₁ + 3y2≥50

3y1 +5у2≥30

Y1, y2≥0

The following observations were made while forming the dual linear programming problem:

1. The primal original linear programming problem is of the maximization type while the dual problem is of minimization type.

2. The constraint values 100 and 150 of the primal problem have become the coefficient of dual variables y₁and y₂in the
objective function of a dual problem and while the coefficient of the variables in the objective function of a primal problem
has become the constraint value in the dual problem.

3. The first column in the constraint inequality of primal problem has become the first row in a dual problem and similarly the
second column of constraint has become the second row in the dual problem.

4. The directions of inequalities have also changed, i.e. in the dual problem, the sign is the reverse of a primal problem. Such
that in the primal problem. Such that in the primal problem, the inequality sign was “≤” but in the Dual Problem, the sign of
inequality becomes “≥”.

Transportation Problem
1.North West Corner Method:
The North-West Corner Rule is a method adopted to compute the initial feasible solution of the transportation problem. The
name North- west corner is given to this method because the basic variables are selected from the extreme left corner.

The concept of North-West Corner can be well understood through a transportation problem given below:

In the table, three sources A, B and C with the production capacity of 50 units, 40 units, 60 units of product respectively is
given. Every day the demand of three retailers D, E, F is to be furnished with at least 20 units, 95 units and 35 units of product
respectively. The transportation costs are also given in the matrix.

The prerequisite condition for solving the transportation problem is that demand should be equal to the supply. In case the
demand is more than supply, then dummy origin is added to the table. The supply of dummy origin will be equal to the
difference between the total supply and total demand. The cost associated with the dummy origin will be zero.
Similarly, in case the supply is more than the demand, then dummy source is created whose demand will be equivalent to the
difference between supply and demand. Again the cost associated with the dummy source will be zero.

Once the demand and supply are equal, the following procedure is followed:

1. Select the north-west or extreme left corner of the matrix, assign as many units as possible to cell AD, within the supply and
demand constraints. Such as 20 units are assigned to the first cell, that satisfies the demand of destination D while the supply
is in surplus.

2. Now move horizontally and assign 30 units to the cell AE. Since 30 units are available with the source A, the supply gets fully
saturated.

3. Now move vertically in the matrix and assign 40 units to Cell BE. The supply of source B also gets fully saturated.

4. Again move vertically, and assign 25 units to cell CE, the demand of destination E is fulfilled.

5. Move horizontally in the matrix and assign 35 units to cell CF, both the demand and supply of origin and destination gets
saturated. Now the total cost can be computed.

The Total cost can be computed by multiplying the units assigned to each cell with the concerned transportation cost.
Therefore,

Total Cost = 20*5+ 30*8+ 40*6+ 25*9+ 35*6 = Rs 1015

2.Least Cost Method:

The Least Cost Method is another method used to obtain the initial feasible solution for the transportation problem. Here, the
allocation begins with the cell which has the minimum cost. The lower cost cells are chosen over the higher-cost cell with the
objective to have the least cost of transportation.

The Least Cost Method is considered to produce more optimal results than the North-west Corner because it considers the
shipping cost while making the allocation, whereas the North- West corner method only considers the availability and supply
requirement and allocation begin with the extreme left corner, irrespective of the shipping cost.
In the given matrix, the supply of each source A, B, C is given Viz. 50units, 40 units, and 60 units respectively. The weekly
demand for three retailers D, E, F i.e. 20 units, 95 units and 35 units is given respectively. The shipping cost is given for all the
routes.

The minimum transportation cost can obtained by following the steps given below:

1.The minimum cost in the matrix is Rs 3, but there is a tie in the cell BF, and CD, now the question arises in which cell we shall
allocate. Generally, the cost where maximum quantity can be assigned should be chosen to obtain the better initial solution.
Therefore, 35 units shall be assigned to the cell BF. With this, the demand for retailer F gets fulfilled, and only 5 units are left
with the source B.

2. Again the minimum cost in the matrix is Rs 3. Therefore, 20 units shall be assigned to the cell CD. With this, the demand of
retailer D gets fulfilled. Only 40 units are left with the source C.

3. The next minimum cost is Rs 4, but however, the demand for F is completed, we will move to the next minimum cost which
is 5. Again, the demand of D is completed. The next minimum cost is 6, and there is a tie between three cells. But however, no
units can be assigned to the cells BD and CF as the demand for both the retailers D and F are saturated. So, we shall assign 5
units to Cell BE. With this, the supply of source B gets saturated.

4. The next minimum cost is 8, assign 50 units to the cell AE. The supply of source A gets saturated.

5. The next minimum cost is Rs. 9; we shall assign 40 units to the cell CE. With his both the demand and the supply of all the
sources and origins gets saturated.

The total cost can be calculated by multiplying the assigned quantity with the concerned cost of the cell. Therefore,
Total Cost = 50*8 + 5*6 + 35*3 +20*3 +40*9 =Rs 955.

Note: The supply and demand should be equal and in case supply are more, the dummy source is added in the table with
demand being equal to the difference between supply and demand, and the cost remains zero. Similarly, in case the demand
is more than supply, then dummy destination or origin is added to the table with the supply equal to the difference in quantity
demanded and supplied and the cost being zero.

3.Vogel's Approximation Method:

The Vogel's Approximation Method or VAM is an iterative procedure calculated to find out the initial feasible solution of the
transportation problem. Like Least cost Method, here also the shipping cost is taken into consideration, but in a relative sense.

The following is the flow chart showing the steps involved in solving the transportation problem using the Vogel's
Approximation Method:

The concept of Vogel's Approximation Method can be well understood through an illustration given below:

1. First of all the difference between two least cost cells are calculated for each row and column, which can be seen in the
iteration given for each row and column. Then the largest difference is selected, which is 4 in this case. So, allocate 20 units to
cell BD, since the minimum cost is to be chosen for the allocation. Now, only 20 units are left with the source B.
2. Column D is deleted, again the difference between the least cost cells is calculated for each row and column, as seen in the
iteration below. The largest difference value comes to be 3, so allocate 35 units to cell AF and 15 units to the cell AE. With this,
the Supply and demand of source A and origin F gets saturated, so delete both the row A and Column F.

3. Now, single column E is left, since no difference can be found out, so allocate 60 units to the cell CE and 20 units to cell BE,
as only 20 units are left with source B. Hence the demand and supply are completely met.

Now the total cost can be computed, by multiplying the units assigned to each cell with the cost concerned. Therefore,

Total Cost 20*3+ 35*1 +15*4 + 60*4 + 20*8 = Rs 555

Optimality Test
1.Stepping Stone Method:
The Stepping Stone Method is used to check the optimality of the initial feasible solution determined by using any of the
method Viz. North-West Corner, Least Cost Method or Vogel's Approximation Method. Thus, the stepping stone method is a
procedure for finding the potential of any non-basic variables (empty cells) in terms of the objective function.

Through Stepping stone method, we determine that what effect on the transportation cost would be in case one unit is
assigned to the empty cell. With the help of this method, we come to know whether the solution is optimal or not.

The series of steps are involved in checking the optimality of the initial feasible solution using the stepping stone method:

1. The prerequisite condition to solve for the optimality is to ensure that the number of occupied cells is exactly equal to
m+n-1, where 'm' is the number of rows, while 'n' is equal to the number of columns.

2. Firstly, the empty cell is selected and then the closed path is created which starts from the unoccupied cell and returns to
the same unoccupied cell, called as a "closed loop". For creating a closed loop the following conditions should be kept in mind:

 In a closed loop, cells are selected in a sequence such that one cell is unused/unoccupied, and all other cells are
used/occupied.
 A pair of Consecutive used cells lies either in the same row or the same column.
 No three consecutive occupied cells can either be in the same row or column.
 The first and last cells in the closed loop lies either in the same row or column.
 Only horizontal and movement is allowed. Vertical
 Once the loop is created, assign "+" or "-" sign alternatively on each corner cell of the loop, but begin with the "+" sign
for the unoccupied cell.
 Repeat these steps again until all the unoccupied cells get evaluated.
 Now, if all the computed changes are positive or are equal to or greater than zero, then the optimal solution has been
reached.
 But in case, if any, value comes to be negative, then there is a scope to reduce the transportation cost further. Then,
select that unoccupied cell which has the most negative change and assign as many units as possible. Subtract the unit
that added to the unoccupied cell from the other cells with a negative sign in a loop, to balance the demand and
supply requirements.

Example, suppose the following matrix shows the initial feasible solution and stepping stone method is adopted to check its
optimality:
With the new matrix so formed, again the empty cells will be evaluated through a loop formation and signs will be assigned
accordingly. The cell with the highest opportunity cost will be assigned the units, and this process will repeat until the best
optimum solution is obtained or the opportunity cost of all the unoccupied cells comes to be negative.

2. Modified Distribution Method (MODI Mothed):

The Modified Distribution Method or MODI is an efficient method of checking the optimality of the initial feasible solution.

MODI

The concept of can be further comprehended through an illustration given below:

1. Initial basic feasible solution is given below

2. Now, calculate the values of ui and vj by using the equation

ui+vj = Cij

Substituting the value of u1 as O

U1+V1 = C11, 0+V1 = 6 or V1 = 6

U1+V2 = C12, 0+V2 = 4 or V2 = 4

U2+V2 = C22, U2+4 = 8 or U2 = 4

U3+V2=C32, U3+4= 4 or U3 = 0

U3+V3 = C33, 0+V3 = 2 or V3=2

3. Next step is to calculate the opportunity cost of the unoccupied cells (AF, BD, BF, CD) by using the following formula

Cij - (ui+Vi)

AF = C13 - (U1+V3), 1- (0+2) = -1 or 1

BD = C21 - (U2+v1), 3-(4+6) = -7 or 7

BF = C23 (U2+V3), 7-(4+2) = 1 or -1

CD = C31-(U3+V1), 4-(0+6) = −2 or 2
4. Choose the largest positive opportunity cost, which is 7 and draw a closed path, as shown in the matrix below. Start from
the unoccupied cell and assign "+" or "-"sign alternatively. Therefore, The most favored cell is BD, assign as many units as
possible.

5. The matrix below shows the maximum allocation to the cell BD, and that number of units are added to the cell with a
positive sign and subtracted from the cell with a negative sign.

6. Again, repeat the steps from 1 to 4 i.e. find out the opportunity costs for each unoccupied cell and assign the maximum
possible units to the cell having the largest opportunity cost. This process will go on until the optimum solution is reached.

The Modified distribution method is an improvement over the stepping stone method since; it can be applied more efficiently
when a large number of sources and destinations are involved, which becomes quite difficult or tedious in case of stepping
stone method.

Modified distribution method reduces the number of steps involved in the evaluation of empty cells, thereby minimizes the
complexity and gives a straightforward computational scheme through which the opportunity cost of each empty cell can be
determined.

THE END