Dr.
Ron Lembke
SOLVING LINEAR PROGRAMS
USING EXCEL
Formulating in Excel
1.
2.
3.
4.
Write the LP out on paper, with all
constraints and the objective function.
Decide on cells to represent variables.
Enter coefficients of each variable in
each constraint in a block of cells.
Compute amount of each constraint
being used by current solution.
Formulating in Excel
5. Place inequalities in sheet, so you
remember <=, >=
6. Enter amount of each constraint
7. Enter objective coefficients
8. Calculate value of objective function
9. Make sure you have plenty of labels.
10. Widen columns for readability.
Standard Form
Max7x1 + 5x2
s.t. 4x1 + 3x2 <=
2x1 + 1x2 <=
x1
>=
x2 >=
240 electronics
100 assembly
Formulating in Excel
Current
value of
variables
Constraint
coefficients
Formulating in Excel
Amount of
each
constraint
used
by current
solution
Formulating in Excel
Objective
Function
Value
Objective Function
Coefficients
RHS of constraints,
Inequality signs.
Fancy What If Tool
Trial and error
Simplifies the math
Cant solve it for us
Solving in Excel
All we have so far is a big what if tool. We
need to tell the LP Solver that this is an
LP that it can solve.
Choose Solver from Tools menu
Click Data then Solver
If No Solver, Office2010
If No Solver, Office 2007
Solving in Excel
1.
2.
3.
Choose Solver from Data tab
Tell Solver what is the objective function,
and which are variables.
Tell Solver to minimize or maximize
Solver Dialog Box
Set the Target Sell
Tell to minimize or maximize
Where the variables are
Solving in Excel
1.
2.
3.
4.
Choose Solver from Tools menu
Tell Solver what is the objective function, and
which are variables.
Tell Solver to minimize or maximize
Add constraints:
5.
Click Add, enter LHS, RHS, choose inequality
Click Add if you need to do more, or click Ok if this
is the last one.
Add rest of constraints
Add Constraint Dialog Box
Constraints Added
Assuming Linear
6.
You have to tell Solver that the model is
Linear. Click options, and make sure
the Assume Linear Model box is
checked.
Assume Linear
Assuming Linear
6.
7.
You have to tell Solver that the model is Linear.
Click options, and make sure the Assume
Linear Model box is checked.
On this box, checking assume non-negative
means you dont need to actually add the nonnegativity constraints manually.
Solve the LP: Click Solve. Look at Results.
Office 2010
Office 2010 Options
Set maximum time
to look for a solution
OR maximum # of
iterations
Our
problems
should solve quickly
Solution is Found
When a solution has been found, this box comes up.
You can choose between keeping the solution and going
back to your original solution.
Highlight the reports that you want to look at.
Successful Solution
Optimality Conditions?
200
Dead Profits
4000
160
T
2000
0
120
T-shirts
2
Solution #
80
Each time we go to another solution,
Objective value gets better
40
0
50
100
S Sweatshirts
150
200
Optimality Conditions
Simplex method
creates dual
Max
has a min dual,
min has a max dual
Dual and primal
converge to same
value
Solution must be
optimal
Dead Profits
7000
6000
5000
4000
3000
2000
1000
0
Solution #
Answer Report
Gives optimal and initial values of
objective function
Gives optimal and initial values of
variables
Tells amount of slack between LHS and
RHS of each constraint, tells whether
constraint is binding.
Answer Report
Sensitivity Report
Variables:
Final value of each variable
Reduced cost: how much objective
changes if current solution is changed
Objective coefficient (from problem)
Sensitivity Report
Variables:
Allowable increase:
How much the objective coefficient can go up before the optimal
solution changes.
Allowable decrease:
How much the objective coefficient can go down before optimal
solution changes.
Both of these only are accurate for changes made to one
variable at a time. If you change more than one variable,
need to re-solve the LP.
Suppose t-shirts had increase of $5 decrease $10
Solution is optimal if t-shirt profits are between $15-$30
Sensitivity Report
Constraints
Final Value (LHS)
Shadow price: how much objective would
change if RHS increased by 1.0
Allowable
increase, decrease: how wide a range of
values of RHS shadow price is good for.
Also only accurate for changes made to one
constraint at a time
To see the impact of changing more than one
constraint, we just have to re-run the problem
Sensitivity Report
Limits Report
Tells ranges of values over which the
maximum and minimum objective values
can be found.
Rarely useful
Limits Report
Summary
Entered the LP into Excel
Opened Solver, told it how we wanted to
solve the LP
Interpreting results of Solver Reports
Answer
report basic results
Sensitivity how much the situation would
change with different profits per unit, or
amounts of constraints
