Things to blindly memorize Flashcards
What should you do when there is a tie for entering basic variable
Break the tie arbitrarily
What should you do when there is a tie for leaving variable
Break the tie arbitrarily, may lead to degeneracy
What is the result when there is no valid leaving variable?
Z is unbounded?
What is the result when a non-basic variable has a zero at optimality in simplex?
There are multiple optimal solutions, we can increase the value of the non-basic variable without affecting Z
What does a zero basic variable at optimality imply
The simplex tableau is degenerate (will cycle)
What is degeneracy?
The simplex will cycle, without modifying the value of Z
When do we include artificial variables?
When we have >= or = constraints (origin is not a feasible solution)
When is a simplex tableau infeasible?
artificial variables != 0 at optimality
What do the coefficients of the non-basic variables in simplex objective row correspond to
value of the dual variables
What if the dual is unbounded what can we say about the primal
primal is infeasible
If the primal is infeasible what can w e say about the dual
dual is infeasible or unbounded
what is a CPF solution
Corner point feasible. 2+ binding constraints
What is standard for of an LP
1) All constraints equality
2) All RHS non negative
3) All variables >=0
4) Objective Fnc is max (optional)
How do we implement Big M
for a max problem, subtract Mai
What are the range of optimality of the objective coefficiants
range for each objective function coefficient for which the current CPF solution is optimal
When we change the objective function coefficients within the range of optimality, how is Z affected?
Z changes, basis does not
What is the 100% rule?
calculate percentage of the change for each coefficient for each variable. If sum of changes < 100 -> remains optimal
What is reduced cost
amount by which the objective function coefficient can change before that value is included in the basis
What is the reduced cost for a basic variable
0
What is an analogy for reduced cost
Estimate of how much will Z change if we force a variable to be non zero
What happens when we change the RHS of a non-binding constraint
optimal basis doesn’t change
optimal solution doesn’t change
What happens when we change the rhs of a binding constraint
Optimal basis doesnt change
Optimal solution does change
What is shadow price
The amount by which the optimal value will increase or decrease when the RHS of the constraint is increased or decreased by 1
How is shadow price related to dual problem
Shadow price = value of the dual variable
What happens when shadow price is negative
Optimal solution gets worse when we increase RHS by one unit
What is an analogy for shadow price?
How much would we pay for one additional unit of the resource
how do we constrain that at most k out of n variables can be 1?
Sum(x_i) <= k
how do we constrain that x and y are mutually exclusive
x+y <= 1
how to we make y a prereq of x?
x <= y
how do we make x a corequisite of y
x = y
