Quantitative Techniques For Management

Quantitative Techniques For Management

This course contains the basics of Quantitative Techniques For Management

Course introduction
Interview Questions
Pragnya Meter Exam

Quantitative Techniques For Management

Linear Programming: Simplex Method

In 1947, George B. Dantzig, then part of a research group of the U.S. Air Force known as Project SCOOP (Scientific Computation of Optimum Programs), developed the simplex method for solving the general linear-programming problem. The extraordinary computational efficiency and robustness of the simplex method, together with the availability of high-speed digital computers, have made linear programming the most powerful optimization method ever designed and the most widely applied in the business environment.

In practice, most problems contain more than two variables and are consequently too large to be tackled by conventional means. Therefore, an algebraic technique is used to solve large problems using Simplex Method. This method is carried out through iterative process systematically step by step, and finally the maximum or minimum values of the objective function are attained.

The simplex method solves the linear programming problem in iterations to improve the value of the objective function. The simplex approach not only yields the optimal solution but also other valuable information to perform economic and 'what if' analysis.


Three types of additional variables are used in simplex method such as,

  1. Slack variables (S1, S2, S3..…Sn): Slack variables refer to the amount of unused resources like raw materials, labor and money.
  2. Surplus variables (-S1, -S2, -S3..…-Sn): Surplus variable is the amount of resources by which the left hand side of the equation exceeds the minimum limit.
  3. Artificial Variables (a1, a2, a3.. …an): Artificial variables are temporary slack variables which are used for purposes of calculation, and are removed later.

The above variables are used to convert the inequalities into equality equations, as given in the following table.

 Types of Additional Variables


The packaging product mix problem is solved using simplex method.

Maximize Z = 6x1 + 4x2

Subject to constraints,
2x1+3x2≤ 120 (Cutting machine)               .....................(i)
2x1+ x2≤ 60 (Pinning machine)                ......................(ii)
where x1, x2≥ 0

Considering the constraint for cutting machine,

2x1+ 3x2≥ 120

The inequality indicates that the left-hand side of the constraints equation has some amount of unused resources on cutting machine. To convert this inequality constraint into an equation, introduce a slack variable, s3 which represents the unused resources.

Introducing the slack variable, we have the equation

2x1+ 3x2 + s3 = 120

Similarly for pinning machine, the equation is

2x1+ x2 + s4 = 60

The variables s3 and s4 are known as slack variables corresponding to the three constraints. Now we have in all four variables (which includes slack variable) and two equations. If any two variables are equated to zero, we can solve the three equations of the system in two unknowns.

If variables x1 and x2 are equated to zero,

i.e., x1 = 0 and x2 = 0, then

s3 = 120
s4 = 60

This is the basic solution of the system, and variables s3 and s4 are known as Basic Variables, SB while x1 and x2 known as Non-Basic Variables. If all the variables are non-negative, a basic feasible solution of a linear programming problem is called a Basic Feasible Solution. Rewriting the constraints with slack variables gives us,

Zmax = 6x1 + 4x2 + 0s3 + 0s4

Subject to constraints,
2x1 + 3x2 + s3 = 120             ....................(i)
2x1 + x2 + s4 = 60                 ....................(ii)
where x1, x2≥ 0

Though there are many forms of presenting Simplex Table for calculation, we represent the coefficients of variables in a tabular form as shown in Table.

 Co-efficients of Variables

If the objective of the given problem is a maximization one, enter the co-efficient of the objective function Zj with opposite sign as shown in the above table. Take the most negative coefficient of the objective function and that is the key column Kc.

In this case, it is -6. Find the ratio between the solution value and the key column coefficient and enter it in the minimum ratio column. The intersecting coefficients of the key column and key row are called the pivotal element i.e. 2. The variable corresponding to the key column is the entering element of the next iteration table and the corresponding variable of the key row is the leaving element of the next iteration table. In other words, x1 replaces s4 in the next iteration table. The following table indicates the key column, key row and the pivotal element.

In the next iteration, enter the basic variables by eliminating the leaving variable (i.e., key row) and introducing the entering variable (i.e., key column). Make the pivotal element as 1 and enter the values of other elements in that row accordingly. In this case, convert the pivotal element value 2 as 1 in the next interaction table. For this, divide the pivotal element by 2. Similarly divide the other elements in that row by 2.

The equation is s4 /2. This row is called as Pivotal Equation Row Pe. The other co-efficients of the key column in the following iteration table must be made as zero in the iteration Table. For this, a solver, Q, is formed for easy calculation. Change the sign of the key column coefficient, multiply with pivotal equation element and add with the corresponding variable to get the equation,

Solver, Q = SB + (–Kc * Pe)

The equations for the variables in the iteration number 1 of table 8 are,

For s3 Q = SB + (– Kc * Pe)
= s3 + (–2x Pe)
= s3– 2Pe                                                   …………………………(i)
For – Z,           Q = SB + (– Kc * Pe)
= – Z + ((– 6) * Pe)
= – Z + 6Pe                                                 …………………………(ii)

Using the equations (i) and (ii) the values of s3 and –Z for the values of Table 1 are found as shown in table below.

 s3 and –Z Values Calculated

Using these equations, enter the values of basic variables SB and objective function Z. If all the values in the objective function are non-negative, the solution is optimal. Here, we have one negative value – 1. Repeat the steps to find the key row and pivotal equation values for the iteration 2 and check for optimality.

In the iteration 2 number of Table, all the values of Zj are non-negative, Zj ≥0, hence optimality is reached. The corresponding values of x1 and x2 for the final iteration table gives the optimal values of the decision variables i.e., x1 = 15, x2 = 30. Substituting these values in the objectives function equation, we get

Zmax = 6x1 + 4x2

= 6(15) + 4(30)
= 90 + 120
= Rs. 210.00

Iteration Table

The solution is,

x1 = 15 corrugated boxes are to be produced and
x2 = 30 carton boxes are to be produced to yield a Profit, Zmax = Rs. 210.00

Summary of LPP Procedure

Step 1: Formulate the LP problem.

Step 2: Introduce slack /auxiliary variables.

if constraint type is ≤ introduce + S
if constraint type is ≥introduce – S + a and
if constraint type is = introduce a

Step 3: Find the initial basic solution.

Step 4: Establish a simplex table and enter all variable coefficients. If the objective function is maximization, enter the opposite sign co-efficient and if minimization, enter without changing the sign.

Step 5: Take the most negative coefficient in the objective function, Zj to identify the key column (the corresponding variable is the entering variable of the next iteration table).

Step 6: Find the ratio between the solution value and the coefficient of the key column. Enter the values in the minimum ratio column.

Step 7: Take the minimum positive value available in the minimum ratio column to identify the key row. (The corresponding variable is the leaving variable of the table).

Step 8: The intersection element of the key column and key row is the pivotal element.

Step 9: Construct the next iteration table by eliminating the leaving variable and introducing the entering variable.

Step 10: Convert the pivotal element as 1 in the next iteration table and compute the other elements in that row accordingly. This is the pivotal equation row (not key row).

Step 11: Other elements in the key column must be made zero. For simplicity, form the equations as follows: Change the sign of the key column element, multiply with pivotal equation element and add the corresponding variable.

Step 12: Check the values of objective function. If there are negative values, the solution is not an optimal one; go to step 5. Else, if all the values are positive, optimality is reached. Non-negativity for objective function value is not considered. Write down the values of x1, x2,……..xi and calculate the objective function for maximization or minimization.


(i) If there are no x1, x2 variables in the final iteration table, the values of x1 and x2 are zero.
(ii) Neglect the sign for objective function value in the final iteration table.


From the MAIN MENU, select LINEAR PROGRAMMING option, and enter the input values of the previously discussed problem as shown in the following figure.

Solving LPP using Computer with TORA (Input Screen)

Click Solve Menu, and select Solve Problem → Algebraic →Iterations →All-Slack Starting Solution. Now, click Go To Output screen, then the first iteration table will be displayed. To select the entering variable, click a non-basic variable (if correct, the column turns green). Similarly, select the leaving variable (if correct, the row turns red), Figure.

 Selecting the Leaving Variable (TORA, Output Screen)

Then click Next Iteration button to display the next iteration table as shown in the following figure.
 Next Iteration Table (TORA, Output Screen)

Again click next iteration button to get the third and final iteration table. A pop-up menu also indicates that the solution has reached the optimal level. Now we can notice that all the values in the objective function zmax row are non-negative which indicates that the solution is optimal. The final Iteration Table is shown in the following figure.

 Final Iteration Table (TORA, Output Screen)


From the final Iteration Table, the values of x1, x2 and zmax are taken to the corresponding values in the solution column (last column) of the simplex table.
i.e., zmax = 210.00
x1 = 30.00
x2 = 15.00

Example : Solve the LP problem using Simplex method. Determine the following:

(a) What is the optimal solution?
(b) What is the value of the objective function?
(c) Which constraint has excess resources and how much?
zmax = 5x1 + 6x2
Subject to constraints,
2x1 + x2≤  2000                                               ....................(i)
x1≤  800                                                         ....................(ii)
x2≤  200                                                         ....................(iii)
where x1, x2≥ 0

Solution: Converting the inequality constraints by introducing the slack variables,
zmax = 5x1 + 6x2 + 0s3 + 0s4 + 0s5
2x1 + x2 + s3 = 2000
x1 + s4 = 800
x2 + s5 = 200

Equate x1 and x2 to zero , to find the initial basic solution
2(0) + 0 + s3 =2000
0 + s4 = 800
0 + s5 = 200

The initial basic solution is,
s3 = 2000
s4 = 800
s5 = 200

Establish a simplex table to represent the co-efficient of variables for optimal computation as shown in the following table.

Simplex Table

In the final table, all the values of –Zj are ≥ 0, hence optimality is reached. The optimum solution is,

(a) The value of x1 = 800 units
x2 = 200 units
(b) Objective function zmax = 5x1 + 6x2
= 5(800) + 6(200)
= Rs. 5200.00

(c) In the final iteration Table, slack variable s3 represents the first constraint, therefore this constraint has excess unused resources of 200 units.


In real life we need to minimize cost or time in certain situations. The objective now is minimization. Procedure for minimization problems is similar to maximization problems. The only difference is, enter the coefficients of the objective function in the simplex table without changing the sign.

Another way to solve minimization problems is by converting the objective function as a maximization problem by multiplying the equation by (– 1).

For example, if the objective function is,
Minimize Z =10x1+ 5x2
Convert the objective function into maximization and solve
Maximize Z = – 10x1– 5x2


So far, we have seen the linear programming constraints with less than type. We come across problems with ‘greater than’ and ‘equal to’ type also. Each of these types must be converted as equations. In case of ‘greater than’ type, the constraints are rewritten with a negative surplus variable s1 and by adding an artificial variable a.

Artificial variables are simply used for finding the initial basic solutions and are thereafter eliminated. In case of an ‘equal to’ constraint, just add the artificial variable to the constraint. The co-efficient of artificial variables a1, a2,….. are represented by a very high value M, and hence the method is known as BIG-M Method.

Example : Solve the following LPP using Big M Method.

Minimize Z = 3x1 + x2
Subject to constraints
4x1 + x2 = 4               ....................(i)
5x1 + 3x2≥ 7             ....................(ii)
3x1 + 2x2≤ 6             ....................(iii)
where x1 , x2≥0

Solution: Introduce slack and auxiliary variables to represent in the standard form. Constraint 4x1 + x2 = 4 is introduced by adding an artificial variable a1, i.e., 4x1 + x2 + a1 = 4 Constraint, 5x1 + 3x2≥ 7 is converted by subtracting a slack s1 and adding an auxiliary variable a2.

5x1+ 3x2– s1 + a2 = 7

Constraint 3x2 + 2x2≤ 6 is included with a slack variable s2

3x2 + 2x2 + s2 = 6

The objective must also be altered if auxiliary variables exist. If the objective function is minimization, the co-efficient of auxiliary variable is +M (and -M, in case of maximization)

The objective function is minimization,

Minimize Z = 3x1+ x2 + 0s1+ 0s2+ Ma1+ Ma2

zmin = 3x1 + x2+ Ma1+ Ma2

The initial feasible solution is (Put x1, x2, s1 = 0)

a1 = 4
a2 = 7
s2 = 6

Establish a table as shown below and solve:

Simplex Table

The solution is,

x1 = 5/7 or 0.71
x2 = 8/7 or 1.14
zmin = 3 x 5 / 7 + 8/7
= 23/7 or 3.29


One of the more conceptually mysterious aspects of linear programming is the problem of degeneracy-the breaking down of the simplex calculation method under certain circumstances. Degeneracy in applying the simplex method for solving a linear programming problem is said to occur when the usual rules for the choice of a pivot row or column (depending on whether the primal or the dual simplex method is being discussed) become ambiguous.

In other words, two or more values in the minimum ratio column are the same. To resolve degeneracy, the following method is used. Divide the key column values (of the tied rows) by the corresponding values of columns on the right side. This makes the values unequal and the row with minimum ratio is the key row.

Example : Consider the following LPP,

Maximize Z = 2x1+ x2

Subject to constraints,
4x1 + 3x2≤ 12             ...................(i)
4x1+x2≤ 8                   ...................(ii)
4x1– x2≤ 8                 ...................(iii)

Solution: Converting the inequality constraints by introducing the slack variables,

Maximize Z=2x1+ x2

Subject to constraints,
4x1+ 3x2+ s3 = 12        ...................(iv)
4x1+ x2 + s4 = 8           ...................(v)
4x1– x2+ s5 = 8            ...................(vi)
Equating x1, x2 = 0, we get
s3 = 12
s4 = 8
s5 = 8

 Illustrating Degeneracy

After entering all the values in the first iteration table, the key column is -2, variable corresponding is x1. To identify the key row there is tie between row s4 and row s5 with same values of 2, which means degeneracy in solution. To break or to resolve this, consider the column right side and divide the values of the key column values. We shall consider column x2, the values corresponding to the tie values 1, –1.

Divide the key column values with these values, i.e., 1/4, –1/4 which is 0.25 and – 0.25. Now in selecting the key row, always the minimum positive value is chosen i.e., row s4. Now, s4 is the leaving variable and x1 is an entering variable of the next iteration table. The problem is solved. Using computer and the solution is given in the following figure.

 LPP Solved Using Computer with TORA (Output Screen)


In a linear programming problem, when a situation exists that the value objective function can be increased infinitely, the problem is said to have an 'unbounded' solution. This can be identified when all the values of key column are negative and hence minimum ratio values cannot be found.

 Illustrating Unbounded Solution


In the optimal iteration table if (Pj - Zj) value of one or more non-basic variable is equal to 0, then the problem is said to have multiple or alternative solutions.

Illustrating Multiple Solutions


Duality in linear programming is essentially a unifying theory that develops the relationships between a given linear program and another related linear program stated in terms of variables with this shadow-price interpretation. The importance of duality is twofold.

First, fully understanding the shadow-price interpretation of the optimal simplex multipliers can prove very useful in understanding the implications of a particular linear-programming model. Second, it is often possible to solve the related linear program with the shadow prices as the variables in place of, or in conjunction with, the original linear program, thereby taking advantage of some computational efficiencies.

Every minimization problem is associated with a maximization problem and vice-versa. The original linear programming problem is known as primal problem, and the derived problem is known as its dual problem. The optimal solutions for the primal and dual problems are equivalent.

Conversion of primal to dual has to be done because of many reasons. The dual form of the problem, in many cases, is simple and can be solved with ease. Moreover, the variables of the dual problem contain information useful to management for analysis.


Step 1: Convert the objective function if maximization in the primal into minimization in the dual and vice versa. Write the equation considering the transpose of RHS of the constraints

Step 2: The number of variables in the primal will be the number of constraints in the dual and vice versa.

Step 3: The co-efficient in the objective function of the primal will be the RHS constraints in the dual and vice versa.

Step 4: In forming the constraints for the dual, consider the transpose of the body matrix of the primal problems.

Note: Constraint inequality signs are reversed

Example : Construct the dual to the primal problem

Maximize Z = 6x1 + 10x2

Subject to constraints,

2x1 + 8x2≤ 60             .......................(i)
3x1 + 5x2≤ 45             .......................(ii)
5x1 - 6x2≤ 10             .......................(iii)
x2≤ 40                       .......................(iv)
where x1, x2≥0


Minimize W = 60y1 + 45y2 + 10y3 + 40y4

Subject to constraints,

2y1+3y2+5y3+ 0y4≥ 6
8y1+ 5y2 + 6y3+ y4≥10
where y1, y2, y3, y4≥ 0

Example : Construct a dual for the following primal

Minimize Z = 6x1– 4x2+ 4x3

Subject to constraints,

6x1– 10x2 + 4x3≥14                                                                                                    ..................(i)
6x1+ 2x2 + 6x3≥ 10                                                                                                     ..................(ii)
7x1– 2x2 + 5x3≤ 20                                                                                                    ..................(iii)
x1– 4x2 + 5x3≥ 3                                                                                                        ..................(iv)
4x1+ 7x2– 4x3 20                                                                                                        ..................(v)
where x1, x2, x3≥ 0

Solution: Convert 'less than' constraints into 'greater than' type by multiplying by (–1) on both sides (i.e., for e.g. iii).

6x1– 10x2 + 4x3≥ 14
6x1+ 2x2 + 6x3≥10
– 7x1 + 2x2– 5x3≥ 20
x1– 4x2 + 5x3≥3
4x1 + 7x2– 4x3≥ 20

The dual for the primal problem is,

Maximize W = 14y1+10y2+20y3+3y4+20y5

Subject to constraints,

6y1+ 6y2– 7y3+ y4 + 4y5≤ 6
10y1+ 2y2 + 2y3– 4y4+7y5≤ – 4
4y1+ 6y2– 5y3+ 5y4– 4y5≤ 4
where y1, y2, y3, y4 and y5≥ 0


Sensitivity analysis involves 'what if?' questions. This technique is used to determine how different values of an independent variable will impact a particular dependent variable under a given set of assumptions. This technique is used within specific boundaries that will depend on one or more input variables, such as the effect that changes in interest rates will have on a bond's price.

Sensitivity analysis is a way to predict the outcome of a decision if a situation turns out to be different compared to the key prediction(s). By creating a given set of scenarios, the analyst can determine how changes in one variable(s) will impact the target variable.

Every commercial linear-programming system provides this elementary sensitivity analysis, since the calculations are easy to perform using the tableau associated with an optimal solution. There are two variations in the data that invariably are reported: objective function and right-hand-side ranges.

  • The objective-function ranges refer to the range over which an individual coefficient of the objective function can vary, without changing the basis associated with an optimal solution. In essence, these are the ranges on the objective-function coefficients over which we can be sure the values of the decision variables in an optimal solution will remain unchanged.
  • The right-hand-side ranges refer to the range over which an individual right-hand-side value can vary, again without changing the basis associated with an optimal solution. These are the ranges on the right-hand-side values over which we can be sure the values of the shadow prices and reduced costs will remain unchanged.

Further, associated with each range is information concerning how the basis would change if the range were exceeded. Sensitivity analysis deals with making individual changes in the co-efficient of the objective function and the right hand sides of the constraints. It is the study of how changes in the co-efficient of a linear programming problem affect the optimal solution.

We can answer questions such as,

  1. How will a change in an objective function co-efficient affect the optimal solution?
  2. How will a change in a right-hand side value for a constraint affect the optimal solution?

For example, a company produces two products x1 and x2 with the use of three different materials 1, 2 and 3. The availability of materials 1, 2 and 3 are 175, 50 and 150 respectively. The profit for selling per unit of product x1 is Rs. 40 and that of x2 is Rs. 30. The raw material requirements for the products are shown by equations, as given below.

zmax = 40x1 + 30x2
Subject to constraints
4x1 + 5x2≤ 175         ....................(i)
2x2≤ 50                   ....................(ii)
6x1 + 3x2≤ 150         ....................(iii)
where x1, x2≥ 0

The optimal solution is
x1 = Rs. 12.50
x2 = Rs. 25.00
zmax = 40 * 12.50 + 30 * 25.00
= Rs. 1250.00

The problem is solved using TORA software and the output screen showing sensitivity analysis is given in Table.

Change in objective function co-efficients and effect on optimal solution

Sensitivity Analysis Table Output

Referring to the current objective co-efficient, if the values of the objective function coefficient decrease by 16 (Min. obj. co-efficient) and increase by 20 (Max. obj. coefficient) there will not be any change in the optimal values of x1 = 12.50 and x2 = 25.00. But there will be a change in the optimal solution, i.e. zmax

Note: This applies only when there is a change in any one of the co-efficients of variables i.e., x1 or x2. Simultaneous changes in values of the co-efficients need to apply for 100 Percent Rule for objective function co-efficients.

For x1, Allowable decrease    = Current value - Min. Obj. co-efficient
= 40 – 24
= Rs. 16          ------------------ (i)

Allowable increase      = Max. Obj. co-efficient – Current value
= 60 – 40
= Rs. 20.00     ---------------- (ii)

Similarly, For x2, Allowable decrease = Rs. 10.00    ---------------- (iii)
Allowable increase = Rs. 20.00                              --------------- (iv)

For example, if co-efficient of x1 is increased to 48, then the increase is 48 – 40 = Rs. 8.00. From (ii), the allowable increase is 20, thus the increase in x1 coefficient is 8/20 = 0.40 or 40%.


If co-efficient of x2 is decreased to 27, then the decrease is 30 - 27 = Rs. 3.00.

From (iii), the allowable decrease is 10, thus the decrease in x2 co-efficient is 3/10 = 0.30 or 30%.
Therefore, the percentage of increase in x1 and the percentage of decrease in x2 is 40 and 30 respectively. i.e. 40% + 30% = 70%

For all the objective function co-efficients that are changed, sum the percentage of the allowable increase and allowable decrease. If the sum of the percentages is less than or equal to 100%, the optimal solution does not change, i.e., x1 and x2 values will not change.

But zmax will change, i.e.,

= 48(12.50) + 27(25)
= Rs. 1275.00

If the sum of the percentages of increase and decrease is greater than 100%, a different optimal solution exists. A revised problem must be solved in order to determine the new optimal values.

Change in the right-hand side constraints values and effect on optimal solution

Suppose an additional 40 kgs of material 3 is available, the right-hand side constraint increases from 150 to 190 kgs.

Now, if the problem is solved, we get the optimal values as

x1 = 23.61, x2 = 16.11 and zmax = 1427.78

From this, we can infer that an additional resources of 40 kgs increases the profit by

= 1427.78 – 1250 = Rs. 177.78

Therefore, for one kg or one unit increase, the profit will increase by

= 177.78 / 40
= Rs. 4.44

Dual price is the improvement in the value of the optimal solution per unit increase in the right-hand side of a constraint. Hence, the dual price of material 3 is Rs 4.44 per kg. Increase in material 2 will simply increase the unused material 2 rather than increase in objective function. We cannot increase the RHS constraint values or the resources. If the limit increases, there will be a change in the optimal values.

The limit values are given in Table 2.10, i.e., Min RHS and Max RHS values. For example, for material 3, the dual price Rs. 4.44 applies only to the limit range 150 kgs to 262.50 kgs.
Where there are simultaneous changes in more than one constraint RHS values, the 100 per cent Rule must be applied.

Reduced cost: The reduced cost associated with the nonnegativity constraint for each variable is the shadow price of that constraint (i.e., the corresponding change in the objective function per unit increase in the lower bound of the variable).

Shadow price: The shadow price associated with a particular constraint is the change in the optimal value of the objective function per unit increase in the right-hand-side value for that constraint, all other problem data remaining unchanged.


If the activity's reduced cost per unit is positive, then its unit cost of consumed resources is higher than its unit profit, and the activity should be discarded. This means that the value of its associated variable in the optimum solution should be zero.

Alternatively, an activity that is economically attractive will have a zero reduced cost in the optimum solution signifying equilibrium between the output (unit profit) and the input (unit cost of consumed resources).

In the problem, both x1 and x2 assume positive values in the optimum solution and hence have zero reduced cost.

Considering one more variable x3 with profit Rs. 50

zmax = 40x1 + 30x2 + 50x3

Subject to constraints,

4x1 + 5x2 + 6x3≤ 175                 ....................(i)
2x2 + 1x3≤ 50                           ....................(ii)
6x1 + 3x2 + 3x3≤ 150                ....................(iii)
where x1, x2, x3≥ 0

The sensitivity analysis of the problem is shown in the computer output below in Table.

Sensitivity Analysis

The reduced cost indicates how much the objective function co-efficient for a particular variable would have to improve before that decision function assumes a positive value in the optimal solution.

The reduced cost of Rs.12.50 for decision variable x2 tells us that the profit contribution would have to increase to at least 30 + 12.50 = 42.50 before x3 could assume a positive value in the optimal solution.

Searches relevant to you