# MB0048 : Given a general linear programming problem, explain how you would test whether a basic feasible solution is an optimal solution or not. How would you proceed to change the basic feasible solution in case it is not optimal?

Posted October 20, 2011

on:**MB0048 : Given a general linear programming problem, explain how you would test whether a basic feasible solution is an optimal solution or not. How would you proceed to change the basic feasible solution in case it is not optimal? **

**Answer :- Initial basic feasible solution of a LPP**

Consider a system of m equations in n unknowns x1, x_{2} – – a_{n},

a_{11} x_{1} + a_{12} x_{2} + – – + a_{1n} x_{n} = b_{1}

a_{21} x_{1} + a_{22} x_{2} + – – + a_{2n} x_{n} = b_{2}

_{………………………………………………………}

a_{m1} x_{1} + a_{m2} x_{2} + – – + a_{mn} x_{n} = b_{n}

Where mn

To solve this system of equations, you must first assign any of n – m variables with value zero. The variables assigned the value zero are called **non-basic** variables, while the remaining variables are called **basic variables.** Then, solve the equation to obtain the values of the basic variables. If one or more values of the basic variables are valued at zero, then solution is said to **degenerate, **whereas if all basic variable have **non-zero** values, then the solution is called a **non-degenerate** solution. A basic solution satisfying all constraints is said to be **feasible.**

*Following are the steps to test whether a basic feasible solution is an optimal solution or not as follows: *

- Introduce stack variables (S
_{i}’s) for “” type of constraint. - Introduce surplus variables (S
_{i}’s) and artificial variables (A_{i}) for “” type of constraint. - Introduce only Artificial variable for “=” type of constraint.
- Cost (C
_{j}) of slack and surplus variables will be zero and that of artificial variable will be “M” - Find Z
_{j}– C_{j}for each variable. - Slack and artificial variables will form basic variable for the first simplex table. Surplus variable will never become basic variable for the first simplex table.
- Z
_{j}= sum of [cost of variable x its coefficients in the constraints – Profit or cost coefficient of the variable]. - Select the most negative value of Z
_{j}– C_{j}. That column is called key column. The variable corresponding to the column will become basic variable for the next table. - Divide the quantities by the corresponding values of the key column to get ratios; select the minimum ratio. This becomes the key row. The basic variable corresponding to this row will be replaced by the variable found in step 6.
- The element that lies both on key column and key row is called Pivotal element.
- Ratios with negative andvalue are not considered for determining key row.
- Once an artificial variable is removed as basic variable, its column will be deleted from next iteration.
- For maximisation problems, decision variables coefficient will be same as in the objective function. For minimisation problems, decision variables coefficients will have opposite signs as compared to objective function.
- Values of artificial variables will always is – M for both maximisation and minimisation problems.
- The process is continued till all Z
_{j}– C_{j}0.

To test for optimality of the current basic feasible solution of the LPP, use the following algorithm called simplex algorithm. Let’s also assume that there are no artificial variables existing in the program.

*Perform the following steps to solve the simplex algorithm to change the basic feasible solution in case it is not optimal*

1) Locate the negative number in the last row of the simplex table. Do not include the last column. The column that has negative number is called the **work column. **

2) Next, form ratios by dividing each positive number in the work column, excluding the last row into the element in the same row and last column. Assign that element to the work column to yield the smallest ratio as the **pivot element.** If more than one element yields the same smallest ratio, choose the elements randomly. The program has no solution, if none of the element in the work column is non-negative.

3) To convert the pivot element to unity (1) and then reduce all other elements in the work column to zero, use elementary row operations.

4) Replace the x -variable in the pivot row and first column by x-variable in the first row pivot column. The variable to be replaced is called the outgoing variable and the variable that replaces it is called the incoming variable. This new first column is the current set of basic variables.

5) Repeat steps 1 through 4 until all the negative numbers in the last row excluding the last column are exhausted.

6) You can obtain the optimal solution by assigning the value to each variable in the first column corresponding to the row and last column. All other variables are considered as non-basic and have assigned value zero. The associated optimal value of the objective function is the number in the last row and last column for a maximisation program, but the negative of this number for a minimisation problem.

## Leave a Reply