This course contains the basics of Quantitative Techniques For Management

Course introductionTest Your Caliber

Interview Questions

Pragnya Meter Exam

##### List of Topics

- QUANTITATIVE TECHNIQUES – INTRODUCTION
- Measures of Central Tendency
- Mathematical Model
- Linear Programming: Graphical Method
- Linear Programming: Simplex Method
- Transportation Model
- ASSIGNMENT MODEL
- NETWORK MODEL
- WAITING MODEL (QUEUING THEORY)
- PROBABILITY
- THEORETICAL PROBABILITY DISTRIBUTIONS
- PROBABILITY DISTRIBUTION OF A RANDOM VARIABLE
- INVENTORY MODEL
- Game Theory
- Simulation

**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 (Scientiﬁc 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,

- Slack variables (S1, S2, S3..…Sn): Slack variables refer to the amount of unused resources like raw materials, labor and money.
- 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.
- 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 = 6x_{1} + 4x_{2}

Subject to constraints,

2x_{1}+3x_{2}≤ 120 (Cutting machine) .....................(i)

2x_{1}+ x_{2}≤ 60 (Pinning machine) ......................(ii)

where x_{1}, x_{2}≥ 0

Considering the constraint for cutting machine,

2x_{1}+ 3x_{2}≥ 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, s_{3} which represents the unused resources.

Introducing the slack variable, we have the equation

2x_{1}+ 3x_{2} + s_{3} = 120

Similarly for pinning machine, the equation is

2x_{1}+ x_{2} + s_{4} = 60

The variables s_{3} and s_{4} 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 x_{1} and x_{2} are equated to zero,

i.e., x_{1} = 0 and x_{2} = 0, then

s_{3} = 120

s_{4} = 60

This is the basic solution of the system, and variables s_{3} and s_{4} are known as Basic Variables, S_{B} while x_{1} and x_{2} 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,

Z_{max} = 6x_{1} + 4x_{2} + 0s_{3} + 0s_{4}

Subject to constraints,

2x_{1} + 3x_{2} + s_{3} = 120 ....................(i)

2x_{1} + x_{2} + s_{4} = 60 ....................(ii)

where x_{1}, x_{2}≥ 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 K_{c}.

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, x_{1} replaces s_{4} 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 s_{4} /2. This row is called as Pivotal Equation Row P_{e}. 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 = S_{B} + (–K_{c} * P_{e})

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

For s_{3} Q = S_{B} + (– K_{c} * P_{e})

= s_{3} + (–2x P_{e})

= s_{3}– 2P_{e} …………………………(i)

For – Z, Q = S_{B} + (– K_{c} * P_{e})

= – Z + ((– 6) * P_{e})

= – Z + 6P_{e} …………………………(ii)

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

* s _{3} and –Z Values Calculated*

Using these equations, enter the values of basic variables S_{B} 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 x_{1} and x_{2} for the final iteration table gives the optimal values of the decision variables i.e., x_{1} = 15, x_{2} = 30. Substituting these values in the objectives function equation, we get

Z_{max} = 6x_{1} + 4x_{2}

= 6(15) + 4(30)

= 90 + 120

= Rs. 210.00

*Iteration Table*

The solution is,

x_{1} = 15 corrugated boxes are to be produced and

x_{2} = 30 carton boxes are to be produced to yield a Profit, Z_{max} = 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 x

*Note:*

(i) If there are no x_{1}, x_{2} variables in the final iteration table, the values of x_{1} and x_{2} 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 z_{max} 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 x_{1}, x_{2} and z_{max} are taken to the corresponding values in the solution column (last column) of the simplex table.

i.e., z_{max} = 210.00

x_{1} = 30.00

x_{2} = 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?

z_{max} = 5x_{1} + 6x_{2}

Subject to constraints,

2x_{1} + x_{2}≤ 2000 ....................(i)

x_{1}≤ 800 ....................(ii)

x_{2}≤ 200 ....................(iii)

where x_{1}, x_{2}≥ 0

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

z

2x

x

x

Equate x_{1} and x_{2} to zero , to find the initial basic solution

2(0) + 0 + s_{3} =2000

0 + s_{4} = 800

0 + s_{5} = 200

The initial basic solution is,

s_{3} = 2000

s_{4} = 800

s_{5} = 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 x_{1} = 800 units

x_{2} = 200 units

(b) Objective function z_{max} = 5x_{1} + 6x_{2}

= 5(800) + 6(200)

= Rs. 5200.00

(c) In the final iteration Table, slack variable s_{3} 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 =10x_{1}+ 5x_{2}

Convert the objective function into maximization and solve

Maximize Z = – 10x_{1}– 5x_{2}

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 s_{1} 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 a_{1}, a_{2},….. 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 = 3x_{1} + x_{2}

Subject to constraints

4x_{1} + x_{2} = 4 ....................(i)

5x_{1} + 3x_{2}≥ 7 ....................(ii)

3x_{1} + 2x_{2}≤ 6 ....................(iii)

where x_{1} , x_{2}≥0

** Solution: **Introduce slack and auxiliary variables to represent in the standard form. Constraint 4x

5x_{1}+ 3x_{2}– s_{1} + a_{2} = 7

Constraint 3x_{2} + 2x_{2}≤ 6 is included with a slack variable s_{2}

3x_{2} + 2x_{2} + s_{2} = 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 = 3x_{1}+ x_{2} + 0s_{1}+ 0s_{2}+ Ma_{1}+ Ma_{2}

z_{min} = 3x_{1} + x_{2}+ Ma_{1}+ Ma_{2}

The initial feasible solution is (Put x_{1}, x_{2}, s_{1} = 0)

a_{1} = 4

a_{2} = 7

s_{2} = 6

Establish a table as shown below and solve:

**Simplex Table**

The solution is,

x_{1} = 5/7 or 0.71

x_{2} = 8/7 or 1.14

z_{min} = 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 = 2x_{1}+ x_{2}

Subject to constraints,

4x_{1} + 3x_{2}≤ 12 ...................(i)

4x_{1}+x_{2}≤ 8 ...................(ii)

4x_{1}– x_{2}≤ 8 ...................(iii)

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

Maximize Z=2x_{1}+ x_{2}

Subject to constraints,

4x_{1}+ 3x_{2}+ s_{3} = 12 ...................(iv)

4x_{1}+ x_{2} + s_{4} = 8 ...................(v)

4x_{1}– x_{2}+ s_{5} = 8 ...................(vi)

Equating x_{1}, x_{2} = 0, we get

s_{3} = 12

s_{4} = 8

s_{5} = 8

** Illustrating Degeneracy**

After entering all the values in the first iteration table, the key column is -2, variable corresponding is x_{1}. To identify the key row there is tie between row s_{4} and row s_{5} 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 x_{2}, 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 s_{4}. Now, s_{4} is the leaving variable and x_{1} 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 (P_{j} - Z_{j}) 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.

*Procedure*

** 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 = 6x_{1} + 10x_{2}

Subject to constraints,

2x_{1} + 8x_{2}≤ 60 .......................(i)

3x_{1} + 5x_{2}≤ 45 .......................(ii)

5x_{1} - 6x_{2}≤ 10 .......................(iii)

x_{2}≤ 40 .......................(iv)

where x_{1}, x_{2}≥0

*Solution:*

Minimize W = 60y_{1} + 45y_{2} + 10y_{3} + 40y_{4}

Subject to constraints,

2y_{1}+3y_{2}+5y_{3}+ 0y_{4}≥ 6

8y_{1}+ 5y_{2} + 6y_{3}+ y_{4}≥10

where y_{1}, y_{2}, y_{3}, y_{4}≥ 0

** Example : **Construct a dual for the following primal

Minimize Z = 6x_{1}– 4x_{2}+ 4x_{3}

Subject to constraints,

6x_{1}– 10x_{2} + 4x_{3}≥14 ..................(i)

6x_{1}+ 2x_{2} + 6x_{3}≥ 10 ..................(ii)

7x_{1}– 2x_{2} + 5x_{3}≤ 20 ..................(iii)

x_{1}– 4x_{2} + 5x_{3}≥ 3 ..................(iv)

4x_{1}+ 7x_{2}– 4x_{3} 20 ..................(v)

where x_{1}, x_{2}, x_{3}≥ 0

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

6x_{1}– 10x_{2} + 4x_{3}≥ 14

6x_{1}+ 2x_{2} + 6x_{3}≥10

– 7x_{1} + 2x_{2}– 5x_{3}≥ 20

x_{1}– 4x_{2} + 5x_{3}≥3

4x_{1} + 7x_{2}– 4x_{3}≥ 20

The dual for the primal problem is,

Maximize W = 14y_{1}+10y_{2}+20y_{3}+3y_{4}+20y_{5}

Subject to constraints,

6y_{1}+ 6y_{2}– 7y_{3}+ y_{4} + 4y_{5}≤ 6

10y_{1}+ 2y_{2} + 2y_{3}– 4y_{4}+7y_{5}≤ – 4

4y_{1}+ 6y_{2}– 5y_{3}+ 5y_{4}– 4y_{5}≤ 4

where y_{1}, y_{2}, y_{3}, y_{4} and y_{5}≥ 0

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.

*Procedure*

** 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 = 6x_{1} + 10x_{2}

Subject to constraints,

2x_{1} + 8x_{2}≤ 60 .......................(i)

3x_{1} + 5x_{2}≤ 45 .......................(ii)

5x_{1} - 6x_{2}≤ 10 .......................(iii)

x_{2}≤ 40 .......................(iv)

where x_{1}, x_{2}≥0

*Solution:*

Minimize W = 60y_{1} + 45y_{2} + 10y_{3} + 40y_{4}

Subject to constraints,

2y_{1}+3y_{2}+5y_{3}+ 0y_{4}≥ 6

8y_{1}+ 5y_{2} + 6y_{3}+ y_{4}≥10

where y_{1}, y_{2}, y_{3}, y_{4}≥ 0

** Example : **Construct a dual for the following primal

Minimize Z = 6x_{1}– 4x_{2}+ 4x_{3}

Subject to constraints,

6x_{1}– 10x_{2} + 4x_{3}≥14 ..................(i)

6x_{1}+ 2x_{2} + 6x_{3}≥ 10 ..................(ii)

7x_{1}– 2x_{2} + 5x_{3}≤ 20 ..................(iii)

x_{1}– 4x_{2} + 5x_{3}≥ 3 ..................(iv)

4x_{1}+ 7x_{2}– 4x_{3} 20 ..................(v)

where x_{1}, x_{2}, x_{3}≥ 0

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

6x_{1}– 10x_{2} + 4x_{3}≥ 14

6x_{1}+ 2x_{2} + 6x_{3}≥10

– 7x_{1} + 2x_{2}– 5x_{3}≥ 20

x_{1}– 4x_{2} + 5x_{3}≥3

4x_{1} + 7x_{2}– 4x_{3}≥ 20

The dual for the primal problem is,

Maximize W = 14y_{1}+10y_{2}+20y_{3}+3y_{4}+20y_{5}

Subject to constraints,

6y_{1}+ 6y_{2}– 7y_{3}+ y_{4} + 4y_{5}≤ 6

10y_{1}+ 2y_{2} + 2y_{3}– 4y_{4}+7y_{5}≤ – 4

4y_{1}+ 6y_{2}– 5y_{3}+ 5y_{4}– 4y_{5}≤ 4

where y_{1}, y_{2}, y_{3}, y_{4} and y_{5}≥ 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,

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

For example, a company produces two products x_{1} and x_{2} 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 x_{1} is Rs. 40 and that of x_{2} is Rs. 30. The raw material requirements for the products are shown by equations, as given below.

z_{max} = 40x_{1} + 30x_{2}

Subject to constraints

4x_{1} + 5x_{2}≤ 175 ....................(i)

2x_{2}≤ 50 ....................(ii)

6x_{1} + 3x_{2}≤ 150 ....................(iii)

where x_{1}, x_{2}≥ 0

The optimal solution is

x_{1} = Rs. 12.50

x_{2} = Rs. 25.00

z_{max} = 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 x_{1} = 12.50 and x_{2} = 25.00. But there will be a change in the optimal solution, i.e. z_{max}

** Note: **This applies only when there is a change in any one of the co-efficients of variables i.e., x

For x_{1}, 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 x_{2}, Allowable decrease = Rs. 10.00 ---------------- (iii)

Allowable increase = Rs. 20.00 --------------- (iv)

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

Similarly,

If co-efficient of x_{2} is decreased to 27, then the decrease is 30 - 27 = Rs. 3.00.

From (iii), the allowable decrease is 10, thus the decrease in x_{2} co-efficient is 3/10 = 0.30 or 30%.

Therefore, the percentage of increase in x_{1} and the percentage of decrease in x_{2} 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., x_{1} and x_{2} values will not change.

But z_{max} 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

x_{1} = 23.61, x_{2} = 16.11 and z_{max} = 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.

**Formula**

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 x_{1} and x_{2} assume positive values in the optimum solution and hence have zero reduced cost.

Considering one more variable x_{3} with profit Rs. 50

z_{max} = 40x_{1} + 30x_{2} + 50x_{3}

Subject to constraints,

4x_{1} + 5x_{2} + 6x_{3}≤ 175 ....................(i)

2x_{2} + 1x_{3}≤ 50 ....................(ii)

6x_{1} + 3x_{2} + 3x_{3}≤ 150 ....................(iii)

where x_{1}, x_{2}, x_{3}≥ 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 x_{2} tells us that the profit contribution would have to increase to at least 30 + 12.50 = 42.50 before x_{3} could assume a positive value in the optimal solution.