Simple alogrithm

7 important questions on Simple alogrithm

When using the simplex algorithm when is a solution considered optimal?

  • All NBV have a nonnegative value in row 0 (NBV >= 0)
  • Right hand side >= 0

What if there is a NBV (Non Basic Variable) with a 0 coëfficient in row 0?

You can enter this variable into the basis (into BV's) which results in an alternative solution.

Considering the simplex algorithm when is an LP unbounded?

The entering variable is negative in all constraints.
  • Higher grades + faster learning
  • Never study anything twice
  • 100% sure, 100% understanding
Discover Study Smart

When is an LP considered non-degenerate?

When BV >= 0, bound to find the optimal solution;

What does an degenerate LP result in?

Cycling;

In applying the 2 phase simplex method (minimization problem) what are the steps of phase I?

  1. Modify the constraints such that the right hand side of each constraint is non negative (multiplication by -1) ;
  2. Convert each inequality constraint to the standard/canonical form;
  3. Add a artificial variable a for all constraints that were bigger >= or in step 2;
  4. Solve the phase I LP through min w' = [all artificial variables] and force them into the basis;
  5. Solve the rest of the simplex;

In application of the 2 phase simplex method and the transition to phase II what are the 3 cases differentiated

Case 1
w' > 0, no feasible solution for the original tableau;

Case 2
w'= 0 and no artificial variables in the BV, drop all columns corresponding to artificial variables and combine the original objective function with the constraints from the optimal phase I tableau;    

Case 3
w'= 0 and at least 1 artificial variable is in the BV, drop all nonbasic artificial variables and any variable that has a negative coefficient in row 0 of the optimal phase I tableau;

The question on the page originate from the summary of the following study material:

  • A unique study and practice tool
  • Never study anything twice again
  • Get the grades you hope for
  • 100% sure, 100% understanding
Remember faster, study better. Scientifically proven.
Trustpilot Logo