06_Special Cases LP

Question 1

Which special cases can occur during Simplex?

6 items

Answer 1

• No feasible solution
• unbounded solution
• redundant constraints
• primal degeneracy
• dual degeneracy
• multiple optimal solutions

Question 2

How to detect Primal Degeneracy?

Answer 2

• RHS = 0 of BV
• Simplex might get stuck at a corner point and won’t return optimal solution [cycling]
• corner point is overdetermined
• can also include dual degerenacy if NBV has coefficient 0 in objective function
• NBV with +1 in constraint and all other 0 could be added into basis without changing objective function

Question 3

How to detect Dual Degeneracy

Answer 3

• NBV has coefficient of 0 in the optimal objective function
• when there is primal degeneracy -> RHS = 0 of basic variable in one constraint

Question 4

What are special cases in context of Simplex?

Answer 4

• Primal / Dual Degeneracy
• Unbounded Solution
• No Feasible Solution
• Redundant Constraint
• Multiple Optimal Solutions

Question 5

Multiple Solutions

Answer 5

• objective functions and constraint share same slope
• simplex will return NBV with c(j) = 0 in objective function -> Dual Degeneracy

Question 6

Unbounded Solution

Answer 6

• objective function can increase indefinitely
• maximizing objective function
• all constraint >= 0

Question 7

Redundant constraint

Answer 7

• simplex will return **slack variable **of redundant constraint that is always > 0 **and thus in the basis **

Question 8

How to detect No feasible solution?

Answer 8

• Big - M Method will return optimal solution
• but: artificial variable is still in basis

Question 9

What causes Dual Degeneracy

Answer 9

• multiple optimal solustions
• when objective function and constraint have the same slope

Question 10

What causes Redundant Constraints?

Answer 10

• constraint doesn’t add new information
• Slack variable associated with redundant constraint will always be > 0

Question 11

How to detect unbounded solution in tableau?

Answer 11

• all coefficients in the pivot column will possess a value of smaller or equal 0

Question 12

How to detect
Redundant constraints in tableau?

Answer 12

• Any tableau has 2 „non-basic rows“ that are multiples of each other

Question 13

How to detect Primal Degeneracy

with primal simplex

Answer 13

Any tableau has a basis variable with RHS = 0

Question 14

How to detect Dual Degeneracy

with Primal Simplex

Answer 14

• Optimal Tableau has a non-basic variable with last row-coefficient 0

Question 15

How to detect non-feasible solution

Answer 15

Big M-Method:
- artificial variable in the basis of the optimal tableau

Two-Phase Method:
- Phase 1 finished with objective function value > 0

Question 16

Effect of Primal Degeneracyon Simplex Algorithm

Answer 16

• pivot step without changing the objective function value is conducted.
• simplex might get stuck at overdetermined corner point (cycling) and might won’t return optimal solution

Question 17

Effect of Multiple optimal solutions on Simplex Algorithm

Answer 17

• NBV has coefficient of 0 in objective function
• Simplex will stop at one possible optimal solution

Question 18

Effect of Unboundness on Simplex Algorithm

Answer 18

• as all column entries in pivot column are negative
• simplex will stop and won’t return result

Question 19

Effect of non-feasible solution on Simplex Algorithm

Answer 19

• Canonical start form is technically optimal (i.e. all coefficients in objective function row ≤ 0)
• **simplex terminates as artifical variable is still in basis **