Learning Curve…

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 on: October 20, 2011

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, x2 – – an,

a11 x1 + a12 x2 + – – + a1n xn = b1

a21 x1 + a22 x2 + – – + a2n xn = b2

………………………………………………………

am1 x1 + am2 x2 + – – + amn xn = bn

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 (Si’s) for “” type of constraint.
  • Introduce surplus variables (Si’s) and artificial variables (Ai) for “” type of constraint.
  • Introduce only Artificial variable for “=” type of constraint.
  • Cost (Cj) of slack and surplus variables will be zero and that of artificial variable will be “M”
  • Find Zj – Cj 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.
  • Zj = sum of [cost of variable x its coefficients in the constraints – Profit or cost coefficient of the variable].
  • Select the most negative value of Zj – Cj. 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 Zj – Cj0.

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Author

Learning days (Calendar)

October 2011
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

Knowledge Bank (Archives)

I am on Twitter

Blog Stats

  • 498,419 hits

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 43 other followers

%d bloggers like this: