3133 Final Exam Studying

How do you know if an LP is infeasible?

If the optimal solution of the Phase I simplex is not equal to 0

What us Phase I simplex used for?

To find a starting basis and to check infeasibility

LB and UB for a maximization branch and bound tree

LB: Best integer feasible solution

UB: Best we can hope to get

LB and UB for a minimization branch and bound tree

LB: Best we can hope to get

UB: Best integer feasible solution

Cutting planes algorithm

1). Write the LP Relaxation in standard form and solve using simples

2). Take one of the non integer constraints and move all the variables to one side

3). Floor all the variables and use less than equal to and floor the right side

4). Substitute all the non-basis variables

5). Add to IP

Max min

z <=

Min Max

z>=

Absolute value in objective

change to max

max in constraints:

max{12,12+5x}<=500

12 <= 500

12+5x <= 500

Absolute value in constraints

turn into max and do same

|x-2y|>=2

(x-2y>=2) OR (-x+2y>=2)

Primal is optimal

Dual is optimal

Primal is unbounded

Dual is infeasible

Primal is infeasible

Dual is unbounded or infeasible

Fixed cost constraint

#of units variable <= M (if fixed cost is accrued constraint)

x<=0 in standard form

x’=-x and replace x accordingy

x is free

replace x with (x’-x”)