Things to blindly memorize

Question 1

What should you do when there is a tie for entering basic variable

Answer 1

Break the tie arbitrarily

Question 2

What should you do when there is a tie for leaving variable

Answer 2

Break the tie arbitrarily, may lead to degeneracy

Question 3

What is the result when there is no valid leaving variable?

Answer 3

Z is unbounded?

Question 4

What is the result when a non-basic variable has a zero at optimality in simplex?

Answer 4

There are multiple optimal solutions, we can increase the value of the non-basic variable without affecting Z

Question 5

What does a zero basic variable at optimality imply

Answer 5

The simplex tableau is degenerate (will cycle)

Question 6

What is degeneracy?

Answer 6

The simplex will cycle, without modifying the value of Z

Question 7

When do we include artificial variables?

Answer 7

When we have >= or = constraints (origin is not a feasible solution)

Question 8

When is a simplex tableau infeasible?

Answer 8

artificial variables != 0 at optimality

Question 9

What do the coefficients of the non-basic variables in simplex objective row correspond to

Answer 9

value of the dual variables

Question 10

What if the dual is unbounded what can we say about the primal

Answer 10

primal is infeasible

Question 11

If the primal is infeasible what can w e say about the dual

Answer 11

dual is infeasible or unbounded

Question 12

what is a CPF solution

Answer 12

Corner point feasible. 2+ binding constraints

Question 13

What is standard for of an LP

Answer 13

1) All constraints equality
2) All RHS non negative
3) All variables >=0
4) Objective Fnc is max (optional)

Question 14

How do we implement Big M

Answer 14

for a max problem, subtract Mai

Question 15

What are the range of optimality of the objective coefficiants

Answer 15

range for each objective function coefficient for which the current CPF solution is optimal

Question 16

When we change the objective function coefficients within the range of optimality, how is Z affected?

Answer 16

Z changes, basis does not

Question 17

What is the 100% rule?

Answer 17

calculate percentage of the change for each coefficient for each variable. If sum of changes < 100 -> remains optimal

Question 18

What is reduced cost

Answer 18

amount by which the objective function coefficient can change before that value is included in the basis

Question 19

What is the reduced cost for a basic variable

Answer 19

0

Question 20

What is an analogy for reduced cost

Answer 20

Estimate of how much will Z change if we force a variable to be non zero

Question 21

What happens when we change the RHS of a non-binding constraint

Answer 21

optimal basis doesn’t change

optimal solution doesn’t change

Question 22

What happens when we change the rhs of a binding constraint

Answer 22

Optimal basis doesnt change

Optimal solution does change

Question 23

What is shadow price

Answer 23

The amount by which the optimal value will increase or decrease when the RHS of the constraint is increased or decreased by 1

Question 24

How is shadow price related to dual problem

Answer 24

Shadow price = value of the dual variable

Question 25

What happens when shadow price is negative

Answer 25

Optimal solution gets worse when we increase RHS by one unit

Question 26

What is an analogy for shadow price?

Answer 26

How much would we pay for one additional unit of the resource

Question 27

how do we constrain that at most k out of n variables can be 1?

Answer 27

Sum(x_i) <= k

Question 28

how do we constrain that x and y are mutually exclusive

Answer 28

x+y <= 1

Question 29

how to we make y a prereq of x?

Answer 29

x <= y

Question 30

how do we make x a corequisite of y

Answer 30

x = y