Linear Programming Theory

And

Solver Output/Sensitivity Report

1.How can a linear program terminate?

1.Unique Optimal Solution

2.Infeasible -- Solver Could not find a feasible solution

3.Unbounded – The Set Cell values do not converge

4.Alternate Optimal Solutions –

An allowable increase or decrease for an objective function coefficient = 0

2.What points can be optimal?

1.Extreme Points (An extreme point is always optimal)

2.Boundary Points (When there are alternate optimal solutions)

3.What is the meaning of a reduced cost?

For variables that are positive – reduced cost = 0

For variables that are 0, the reduced cost means

1.The amount that objective function coefficient must change before that variable can become positive.

2.The amount the objective function value would change if that variable were increased from 0 to 1.

4.What is the range of optimality for an objective function coefficient?

It is the range from (current value of the objective function coefficient) – (ALLOWABLE DECREASE) to (current value of the objective function coefficient) + (ALLOWABLE INCREASE)

  • In this range the optimal solution will not change
  • In this range the optimal profit will change if the coefficient multiplies a variable that is positive in the optimal solution

5.What is slack or surplus?

  • Slack = (RHS coefficient) – (LHS value) for “≤” constraints
  • Surplus = (LHS value) – (RHS coefficient) for “≥” constraints

6.What is a shadow price?

  • For constraints whose slack or surplus ≠ 0, the shadow price = 0.
  • For constraints whose slack or surplus = 0, the shadow price = the value the objective function value will change per unit change in the RHS coefficient (within the range of feasibility)
  • The actual interpretation depends on whether the resource for the constraint was included in calculating the original objective function coefficients (see page 70)
  • If they were not (sunk cost), shadow price = the value of an additional unit of the resource, i.e. the maximum price you would be willing to pay for additional units of this resource
  • If they were (included costs), shadow price = a premiumabove the current unit price of the item that you would be willing to pay for additional units

7.What is the range of feasibility for a RHS coefficient?

It is the range from (current value of the RHS coefficient) – (ALLOWABLE DECREASE) to (current value of the RHS coefficient) + (ALLOWABLE INCREASE)

  • In this range the shadow prices will not change
  • In this range the optimal solution will change as will the optimal profit

8.What’s special about problems in which variables are required to be integers?

  • They are more difficult and take longer to solve
  • There is no sensitivity analysis for these “integer linear programs”.

SETTING UP THE SPREADSHEET

COLUMNS

  • Leave a column to designate the meaning of each row
  • Create a column for each variable.
  • Leave a column for the total on the LHS – these cells will be programmed using the SUMPRODUCT function.
  • Include a column designating the signs of each constraint.
  • Include a column of RHS coefficients

ROWS

  • Begin with a row of labels for each column
  • Label the next row the first column (use a word like Values, Results, # per week, etc – whatever is appropriate) as a row where Excel will put the optimal solution – this is the row of CHANGING CELLS
  • Skip the next row except insert the word TOTAL in the column for the LHS
  • Label the next row as PROFIT, COST, or whatever the objective function is about and enter the objective function coefficients – temporarily skip the LHS column
  • Label the rest of the rows with what each constraint is about, enter the constraint coefficients, temporarily leave the LHS column blank, insert the sign of the constraint (<=, =, or >=) and enter the RHS coefficient

LHS Column

  • In the objective function row, enter in the LHS column (this is the Target Cell)

=SUMPRODUCT(highlight changing cells row, highlight objective function row)

  • In the formula bar, highlight the changing cells part of this equation and press the F4 function key to input $ signs to make these references absolute. Then press enter to enter the formula.
  • Drag the formula in this cell down to all entries in the LHS column

SOLVER

  • SET TARGET CELL – click on the cell for the LHS of the objective function
  • BY CHANGING CELLS –highlight the changing cells row where the output occurs
  • Put bullet in correct cell for MAX or MIN
  • Click ADD CONSTRAINTS
  • Add constraints in order – click on the LHS cell, put in the right sign, click on the RHS cell
  • When several consecutive constraints all have the same sign, you can input them collectively, highlighting all the LHS cells, entering the correct sign, then highlighting all the RHS cells
  • Click Add to add more constraints or click OK when finished
  • Back in the Solver dialogue box – Click Options
  • Check Assume Linear Model; Check Assume Non-Negative and Click OK
  • In the Solver dialogue box – Click Solve
  • Highlight the Answer and Sensitivity Reports
  • Interpret the Output in accordance with points 3-7 on previous page