GATE Mechanical Short Notes - IMPORTANT POINTS TO BE REMEMBERED WHILE SOLVING LINEAR PROGRAMMING PROBLEMS BY SIMPLEX METHOD

  1. In the given inequalities, there should not be any negative element on right hand side (bi≥ 0). If any bi is negative, multiply the inequality by – 1 and change the inequality sign.
  2. Sometimes the objective function may be maximization type and the inequalities may be ≥ In such cases, multiply the objective function by – 1 and convert it into minimization type and vice – versa.
  3. While selecting, the incoming variable, i.e., key column, in maximization case, we have to select the highest positive opportunities cost and in minimization case, select the highest element with negative sign. While doing so, sometimes you may find the highest positive element in maximization case or lowest element in minimization case falls under the slack variable in maximization case or under surplus variable in minimization case. Do, not worry. As per rule, select that element and take the column containing that element as key column.
  4. Some times the column of non – basis variables (decision variables) may have their net evaluation elements same. That is the net evaluation elementsare equal. This is known as a TIE in linear Programming Problems. To break the time, first select any one column of your choice as the key column. In the next table, everything will go right.
  5. While selecting the out going variable i.e., key row, we have to select limiting ratio in net evaluation row. In case any element of key column is negative, the replacement ratio will be negative. In case it is negative, do not consider it for operation. Negative that and consider other rows to select out going variable.
  6. Sometimes all the replacement ratios for all the rows may be equal and that element may be limiting ratio. This situation in linear Programming Problem is known as DEGENRACY. We say that the problem is degenerating, when the problem degenerate, the following precautions are taken to get rid of degeneracy.

(a) Take any one ratio of your choice to select key row or out going variables. If you do this, there is a possibility that the problem may cycle. Cycling means, after doing many iterations, you will get the first table once again. But it may not be the case all times.

(b) Select the variable, whose subscript is small. Say S1 is smaller than S2 and S2 is smaller than S3 or X1 is smaller than X2 an so on or x is smaller than y or ‘a’ is smaller than ‘b’ and so on.

(c) If we do above two courses of action, we may encounter with one problem. That one of the remaining variable in the next table will be reduced to a magnitude of zero. This causes trouble in selecting key column in the next table.

(d) Identity the tied variable or rows. For each of the columns in the identity, compute a ratio by dividing the entry in each tied row by the key column number in that row.

(e) If the ratio in the identity do not braek the tie, form similar ratios in the columns of the main body and select the key row as described in (d) above. The application of the above we shall see when deal with degeneracy problems.

(f) While solving the linear programming problems, we may come across a situation that the opportunity cost of more than one non – basic variables are zero, then we can say that the problem has got ALTERNATE SOLUTIONS.

(g) If in a simplex table only one unfavourable Cj – Zj identifying the only incoming variable and if all the elements of the column are either negative elements or Zeros, showing that no change in the basis can be made and no current basic variable can be reduce to zero.

(h) In a problem where, the set of constraints is inconsistent i.e., mutually exclusive, is the case of NO FEASIBLE SOLUTION. In simplex algorithm, this case will occur if the solution is optimal but some artificial variable remains in the optimal solution with a non zero value.  

The degeneracy in linear programming problems and the methods of solving degeneracy, if it exists, are discussed earlier in the chapter. To recollect the same a brief discussion is given below:

While improving the basic feasible solution to achieve optimal solution, we have to find the key column and key row. While doing so, we may come across two situations. One is tie and the other is Degenracy.

The tie occurs when two or more net evaluation row elements of variables are equal. In maximization problem, we select the highest positive element to indicate incoming variable and in minimization we select lowest element to indicate incoming variable. When two or more net evaluation row elements are same, to break the tie, we select nay one of them to indicate incoming variable and next iteration the problem of tie will be solved.

To select the out going variable, we have to select the lowest ratio or limiting ratio in the replacement ratio column. Here also, some times during the phases of solution, the ratio may be equal. This situation in linear programming problem is called degeneracy. To solve degeneracy, the following methods are used:

  • Select any one row as you please. If you are lucky, you may get optimal solution, otherwise the problem cycles.
  • Identify the row, which are having same ratios. Say for example, S1 and S3 rows having equal ratio. In such case select the row, which contains the variable with smaller subscript. That is select row containing S1 as the key row. Suppose the rows of variable x and z are having same ratio, then select the row – containing x as the key row.
  • (a) Divide the elements of unit matrix by corresponding elements of key column. Verify the ratios column – wise in unit matrix starting from left to right. Once the ratios are unequal, the degeneracy is solved. Select the minimum ratio and the row containing that element is the key row.
  • If the degeneracy is not solved by 3 (a), then divide the elements of the main matrix by the corresponding element in the key column, and verify the ratios. Once the ratios are unequal, select the lowest ratios. (This should be done only to rows that are in tie).

In linear programming problem, we come across certain problem, where feasible region is unbounded i.e., the value of objective function can be increased indefinitely. Then we say that solution is UNBOUNDED. But it is not necessary, however, that an unbounded feasible region should yield an unbounded value of the objective function.

Note:

  1. If in the primal, objective function is to be maximized, then in the dual it is to be minimized. Conversely, if in the primal the objective function is to be minimized, then in the dual it is to be maximized.
  2. The objective function coefficients of the prima appear as right – hand side numbers in the dual and vice – versa.
  3. The right hand side elements of the primal appear as objective function coefficients in the dual and vice – versa.
  4. The input – output coefficient matrix of the dual is the transpose of the input – output coefficient matrix of the primal and vice – versa.
  5. If the inequalities in the primal are of the “less than or equal to” type then in the dual they are of the “greater than or equal to” type; then in the dual they are of the “less than or equal to” type.
  6. The necessary and sufficient condition for any linear programming problem and dual to have optium solution is that both have feasible solution. Moreover if one of them has a finite optium solution, the other also has a finite optium solution. The solution of the other can be read from the net evaluation row. Then the values of dual variables are called shadow prices.
  7. If the primal problem has an unbounded solution, then the dual has no solution.
  8. If the i th dual constraints are multiplied by – 1, then i th primal variable computed from net evaluation row of the dual problem must be multiplied by – 1.
  9. If the dual has no feasible solution, then the primal also admits no feasible solution.
  10. If k th constraint of the primal is equality, then the k th dual variable in unrestricted in sign.
  11. If p th variable of the primal is unrestricted in sign, then the p th constraint of the dual is a strict equality.

Summary:

Primal

Dual

Maximize

Minimize

Objective Function

Right hand side

Right hand side

Objective Function

i th row of input – output coefficients

i th column of input output coefficients

j th row of input – output coefficients

j th row of input output coefficients

i th relation of inequality

i th variable non - negative

i th relation is an equality

i thevariable is unrestricted in sign.

j th variable non - negative

j relation an inequality

j th variable unrestricted in sign

j th relation an equality  

Note:

  • Primal of a prima is primal
  • Dual of dual is primal
  • Primal of a dual is primal
  • Dual of a primal is dual
  • Dual of a dual of a dual is Primal.