Concepts & Steps of Operations Research April 2014 Exam Linear Programming Problems

LINEAR PROGRAMMING PROBLEMS

{GRAPHICAL METHOD}

TERMINOLOGY OF LP –

1. Decision Variables: The unknowns to be determined.
2. Constraints: Mathematical equations of the limitations imposed by the situation or problem characteristics. Constraints define limits within which the solution of the Problem has to be found.
3. Objective Function: The mathematical equation of the major goal of the Problem.
4. Linear Relationship: Each Variable appears in only one term & only the first power.
5. Feasible Solution: A set of values of Decision Variables which satisfy all the constraints.
6. Optimal Solution: A Feasible Solution which optimizes the Objective Function.

LINEAR PROGRAMMING PROBLEMS

{SIMPLEX METHOD}

The LPP involving two or more than two variables can be solved by using Simplex method. Simplex is an iterative procedure which follows certain rules. Each iteration gives either the same or better (closer to Optimal) solution than the previous iteration. The process continues till optimal solution is reached.

TERMINOLOGY –

1. Standard Form:       A LPP in which all constraints are written in equalities.

2. Slack Variable:        A variable added to the LHS of “less than or equal to” constraint to convert the convert the constraint into an equality. Value of slack variable indicates unused resources.

3. Surplus Variable:     A variable subtracted from the LHS of “more than or equal to” constraint to convert the convert the constraint into an equality. Value of surplus variable indicates consumption over & above minimum requirements.

4. Simplex Tableau:     A table used to keep record of the calculation made at each iteration.

5. Basis:           The set of variables which are not restricted to equal zero in the current basic solution. The variables which make up the basis are called Basic variables. The remaining are called non-basic variables.

6. Iteration:     The steps performed in simplex method to progress form one feasible solution to another.

7. Cj Row:       A row in the simplex table which contains the coefficients (unit profit) of the variables in the Objective function.

8. Zj Row:       A row in the simplex tables whose elements represent the increase / decrease in the value of objective function; if one unit of that variable is brought into the solution.

9. Zj – Cj Row (Index Row): A row in the simplex table whose elements represent net contribution / loss per unit if one unit of that variable is brought into the solution.

10. Key column:          The column with the largest positive / negative index number. It indicates the Entering variable in the Basis.

11. Key row:   The row with the smallest positive ratio found by dividing Quantity column values by Key column values for each row. It indicates the Exiting variable from the Basis.

12. Key element:         The element at the intersection of Key row & Key column.

Linear Programming : It is a method of selecting an appropriate optimum combination of factors from a series of alternative which are interrelated and each subject to some constraints or restrictions. It involves the development of linear equation to obtain the best solution for the allocation problem. An allocation problem arise whenever there are number of activities to perform, but limitation on either the amount of resources or the way they can be spent prevent us from performing each separate activity in the most effective way conceivable. In such situation we wish to allot the available resource to the activities in a way that they will optimize the total effectiveness.

“Linear Programming is a mathematical technique for determining the optimum allocation of resources and obtaining a particular objective when there are alternative uses of the resources: money, manpower, material, machine and other facilities. The objective in resources allocation may be cost minimization or inversely profit maximization. The technique of linear programming is applicable to problems in which the total effectiveness can be expressed as a linear function of individual allocations and the limitations on resources give rise to linear equalities or inequalities of the individual allocations.”

Some more areas where Linear Programming : Can be used are as follows :

• In structural design for maximum product.
• In structural design for maximum product.
• In determining which parts to make and which to buy to obtain maximum profit margin.
• In selecting equipment and evaluating method improvements that maximize profit margin.
• In planning most profitable match of sales requirements to plant capacity that obtains a fair share of the market.
• In design of optimal purchasing policies.
• Choice of investment from a variety of shares and debentures so as to maximize return on investment.
• Allocation of a limited publicity budget on various heads in order to maximise its effectiveness.

Formulation as a Linear Programming Problem :

The formulation as a LPP model involves the following basic steps :

1.      Find the key decision to be made from the study of the problem, i.e. look for variables.

2.      Identify the variables and assign them symbols as X₁, X₂, X₃ ……… etc.

3.         State the feasible alternative which generally in a given situation is non negativity condition.

4.      Identify the constraints or restrictions in the problem and express them as linear equations or inequalities which are linear functions of the unknown variables.

5.      Identify the Objective function which is to be optimized (maximized or minimized) and represent it as a linear function in terms of unknown variables.

Graphical Method :

The graphic method of solving linear programming problems consists of the following steps :

Step 1 : Plot the Constraints :  To plot the constraints, treat each constraint as equalities so as it represents a straight line. Because of Non-negativity constraints the graph will be in the first quadrant. Depending upon inequalities mark the regions either below or above the line.

Step 2 : Identify the feasible region : The feasible region is the region in which all the constraints are satisfied. In other words, it is the common portion of all the regions represented by all the constraints of the problem.

Step 3 : Locate the solution points :  The feasible region contains an infinite number of points.  In this step, search those points which will make objective function optimum. Note that such points will be only from corner points of the solution space. This is because of extreme point theorem. “Let the solution space of an L.P.P. be a complex region bounded by lines in the plane. Then the objective function of L.P.P. attends its maximum                (or minimum) at the vertices (corners of the feasible space region).”

Step 4 : Select any of the following two methods :

(a)     ISO – Profit (or ISO – Cost) Method :

(i)      Choose a convenient profit (or cost) and draw as iso – profit (or iso – cost) line so that it falls within shaded region.

(ii)     Move this iso – profit (or iso – cost) line parallel to itself further (closer) from (to) the origin.

(iii)    Identify the optimum solution as the co – ordinate of that point on the feasible region touched by the highest possible iso – profit line (or lower possible iso – cost) line.

(iv)    Read the co – ordinates of optimum point either directly from the graph or by simultaneous solution two lines intersecting at that point.

(v)     Compute the optimum profit (or cost) values.

(b)     Corner Point Method :

(i)      Identifying each of the corner or extreme points of the feasible regions either directly from the graph or by method of simultaneous equation.

(ii)     Evaluate the objective function at each of the corner points of the feasible region.

(iii)       Identify the optimum solution which corresponds to that corner points which gives the optimum values of the objective function.

Simplex Method :

When the number of variables and/or the number of constraints increases, it becomes difficult to visualize the feasible region and construct graph. In such cases an efficient competition procedure is needed to solve for the class of L.P.P’s. One such procedure is Simplex method. The Simplex method is developed by George B. Datzing in 1947. IT is an iterative and an efficient method to solve L.P.P.

The Simplex method is an algebraic procedure that starts at a feasible extreme point of simplex, normally the origin, and systematically moves from one feasible extreme point to another until an optimum extreme point is located at each iteration. The procedure tests one extreme point for optimality and if not optimum chooses another extreme point of the convex set that is formed by the constraint and non negativity conditions of the L.P.P. Since the number of extreme points of the convex set of all feasible solutions is finite, the method leads to the optimum extreme points in a finite number of steps or indicates that there exists an unbounded solution.

Feasible Solution :

If all m variables in the solutions satisfies non – negativity constraints then it is said that solution is feasible solution.

Basic Feasible Solution :

It is a solution which is feasible and has at most m positive valued variables i.e. remaining (n – m) variables are zero.

Degenerate Basic Feasible Solution :

It is basic feasible solution with less than m variables are positive valued.

Simplex Algorithm (Manimization Case) :

Steps :

1.      Formulate the linear programming model.

2.      Convert the inequalities in the constraints into equalities by introducing slack, surplus and artificial variables. Whenever surplus variable is introduced, add artificial variable. Also in case of equality in the constraints split it into two constraints one with (£) and other with (³). Then introduce slack, surplus and artificial variables as required.

3.      Express the Objective function in terms of slack, surplus and artificial variables by assigning a 0 (zero) to slack, surplus and M as coefficient to artificial variables. Here M is considered a vary large number so as to finally drive out the artificial variables of basic solutions.

4.      Set up the initial simplex tableau as discussed in above procedure.

5.      Obtain Z_j, and C_j – Z_­j rows.

6.      Test for optimality : Test the current solution for optimality. If all the entries in the index row above are positive, then the current solution is optimum. If there exists any negative or zero number, the current solution can be improved by removing one basic variable from the basic and replacing it by non basic variable.

Further iterate towards an optimum solution : To improve the current solution decide outgoing variable or departing variable and incoming variable or entering variables as follows :

(i)      Identify the column with highest negative value in C_j – Z row.  This column is known as key column or pivot column. Indicate this column with (­). The non basic variable at the top of the key column is the entering variable in the next iteration.

(ii)     Work out the ratios in the last column of the simplex tableau as by dividing each number in X_B column by the corresponding number the key column selected in above step. Identify the raw corresponding to minimum ratio.

This row is called key row or Pivot row. Indicate the row by (¬)

The corresponding variable in the kay row in known as departing variable or leaving variable.

(iii)    Identify the key element or pivot element as the number in the cell corresponding to key row and key column.

8.      Evaluate the new solution by constructing second simplex table.

Update the simplex table I as follows :

(a)     Divide all the entries in the key row by key element.

(b)     The entries in the rows are obtained by performing elementary row operations on all rows so that all elements except the key elements in the key column are zero. In other words for each row other than the key row use the formula :

New row elements = (Element in old rows)

{[Corresponding element above or below key element] x [Corresponding element above or below key element in the row replaced in (a)]}

New entries in the C_B column and X_B column are entered in the new table of the current solution.

(f)      Compute Z_j and C_j – Z_j rows. If all the entires in C_j – Z_j row are either negative or zero, an optimum solution has been obtained.

9.      If any of the numbers in C_j – Z_j row is negative or zero, repeat the iterations until an optimal / optimum solution has been obtained.

Big M Method :

1.      If any constraint have negative constant on RHS, multiply both sides by – 1 to obtain non negative constant. In this situation inequality will be reversed.

2.      Convert the inequalities into equalities by introducing slack, surplus, or artificial variables as per sign of inequality.

3.      Assign – M to an artificial variable in objective function in case of Maximization and + M to an artificial variable in objective function in case of minimization.

UNIVERSITY THEORY QUESTIONS

1. Meaning of Degeneracy and Infeasibility in LPP.(Apr 2002)

Degeneracy:   Degeneracy occurs in two cases.

1] When one or more of basic variables has ZERO value. Quantity value for a Basic variable is equal to zero in the simplex table.

2] There is a tie in replacement ratios for two rows (Basic variables). Hence, for one incoming variable, there are two outgoing variables.

Infeasibility:   The solution is called feasible if it satisfies all the constraints and non-negativity. The solution is infeasible. The constraints are of contradictory nature. Hence, it is not possible to find the feasible region of solution in graphical method.

In simplex method infeasibility can be detected when one or more artificial variables have positive value & the simplex algorithm has ended.

2. Shadow prices in LPP.(Apr 2002) (Apr 2005) (Apr 2006)

Shadow prices are the index row (Cj – Zj row) values for resources i. e. Slack variables. Shadow prices indicate the value of 1 extra unit of resource. When a resource is scarce resource, if we want to acquire 1 extra unit of that scarce resource how much maximum price should we pay for it is determined by shadow price.

3. Basic variables in simplex method of LPP. (Apr 2003)

Basic variables in simplex are the variables which are present in the Basis. They are the variables present in the solution. In the 1^st simplex table, the basic variables are slack variables. The “Z” value (profit or cost) can be calculated from basic variables. (Contribution multiplied by Quantity). Variables not present in the Basis are called Non-Basic variables.

The index row values (Cj – Zj) for basic variables in simplex table is always zero.

In the 1^st simplex table, basic variables are slack variables.

4. Post optimality test in Linear programming.  (Apr 2003) (Oct 2003) Sensitivity analysis in LPP. (Oct. 2004) Sensitivity analysis. (Oct 2005) 

The solution is optimal when all “C – Z” values are either zero or negative.

Post optimality test or Sensitivity analysis is done to test the sensitivity of the optimal solution. We can find following details in post optimality test –

1. Range of profit for each decision variable within which solution remains optimal.
2. Range of availability of each resource within which solution remains optimal.
3. Range of resource availability for validity of shadow price of each resource.

What will be the effect on solution or output if resources are increased or decreased?

5. Major differences between Simple and Dual method of solving LPP (Apr 2004)

The Simple method is used for solving maximization problem.  We convert all constraints into equalities by adding a slack variable in each resource (S1, S2, etc.) Then we prepare the simplex table. Basic variables in 1^st table are slack variables.

In Dual method, we convert minimization problem into maximization problem. Decision variables are represented by Y1, Y2, etc. Objective function of Primal becomes constraint RHS in Dual. Constraint RHS in Primal become objective function in Dual. All ≥ constraints get converted in ≤ constraints. Then we add a slack variable in each constraint. Slack variables are represented by r1, r2, etc.

In the optimal table, shadow prices of slack variables (r1, r2 etc.) of Dual represent quantity of decision variables (X1, X2 etc.) of Primal.

6. Major steps in formulation of LPP.  (Oct 2004) 

Formulation of LPP involves basically three steps-

1. Identification of decision variables. (X1, X2, etc.) Decision variables are equal to total number of profit or cost centres in the problem. If there are two products giving profit, there will be two decision variables.
2. Identification of objective function. (Max. Z or Min. Z) Objective function is maximization if it is a profit problem and it is minimization if it is a cost problem. E.g. Max. Z = 3X1 + 5X2.
3. Formulation of constraints. Constraints are restrictions imposed on the problem Constraints can be of three types- 1. Less than or equal to 2. Greater than or equal to 3. Equal to.

7. Artificial variables in LPP.  (Oct 2003)

Artificial variable is used to convert a Greater than or equal to (≤) constraint into Equality for writing the standard form. Coefficient of Artificial variable in the Objective function is “M” (infinity).

If artificial variable is present in the optimal solution, it indicates infeasibility.

8. Uses of Slack, Surplus and Artificial variables in LPP. (Apr 2004)

Slack variable: It is used o convert a Less than or equal to (≤) constraint into equality to write standard form. It is ADDED to ≤ constraint.

E. g. 2×1 + 4×2 ≤ 40 will become 2×1 + 4×2 + S1 = 40. Where, S1 is slack variable.

Surplus & Artificial variables: They are used to convert Greater than or equal to (≥) constraint into equality to write standard form. Surplus variable is SUBTRACTED from ≥ constraint and Artificial variable is ADDED to the ≥ constraint.

E. g. 2×1 + 4×2 ≥ 40 will become 2×1 + 4×2 – s1 + A1 = 40. s2 is surplus variable and A1 is artificial variable.

9. Distinguish between degeneracy and cycling in LPP. (Apr 2005) 

Degeneracy: Degeneracy exists when for one incoming variable there are two outgoing variables. This happens when there is tie in minimum positive ratios. Another form of degeneracy is quantity value of a basic variable becomes zero.

Cycling: Cycling occurs when a variable goes out of solution and then re-enters solution. So it forms a cycle by going out and re-entering. Or vice versa, i. e. entering the solution and going out in next tables.

10. Distinguish between Basic feasible solution and Optimal solution in LPP. (Apr 2005)

Basic feasible solution means the 1^st simplex table. In basic feasible solution, the basic variables are slack variables. The Z value, i. e. profit value of that table is zero.

Optimal solution means the last table of simplex. In this table, all “C – Z (delta)” values, i. e. opportunity costs are either zero or negative. Hence, no further improvement in the solution is possible. The profit of this table is maximum. No further increase in profit is possible.

11. Iso-profit line in graphical solution in LPP. (Oct 2006)

Iso-profit line is the line which represents the optimal solution point in graphical solution. The slope of the line is calculated from the Objective function.

If the objective function is Z = 20×1 + 30×2, slope will be calculate as below.

Convert the equation such that x2 is on one side and all remaining values are on the other side.

Z = 20×1 + 30×2

30×2 = Z – 20×1

x2 = Z/30 – (20/30) x1

The co-efficient of x1 is the slope of the line.

Hence, slope is – 20/30 = – 2/3.

The negative sign indicates that the line slopes from left to right downwards. 2/3 indicates for every 2 cm on Y axis, it has 3 cm on X axis.

12. Multiple optimal solutions in LPP. (Oct 2006)

In LPP multiple solutions can be detected in the following way –

In simplex method, in the optimal table if the (C – Z) value for any Non-basic variable is zero, then there is an alternate optimal (multiple optimal) solution.

The non-basic variable for which the (C- Z) value is zero can enter the solution. The basis will change. But the total profit or cost will remain same.