Linear Programming
– the simple Wyndor Glass example
Thomas Stidsen
tks@imm.dtu.dk
Informatics and Mathematical Modeling Technical University of Denmark
LP parts:
Decision variables Objective function Constraints
Wyndor glass
Wyndor model in Excel
LP: Linear Programming
ILP: Integer Linear Programming
Solver: An algorithm/a program which finds the optimal solution to LP/ILP problems
Decision variables: An un-decided decision which is left to the solver
Objective function: A function specifying the
cost of a certain setting of the decision variables Constraint set: A set of equations limiting the
possible values of the decision variables
elements:
(Decision) Variables
(Linear) Objective function A set of (linear) constraints
M AX 300x + 500y
M AX 300x + 500y ST :
x ≤ 4 2y ≤ 12 3x + 2y ≤ 18
M AX 300x + 500y ST :
x ≤ 4 2y ≤ 12 3x + 2y ≤ 18
x ≥ 0 y ≥ 0
x 8
6
4
2
2 4 6 8
Only positive
y
x 8
6
4
2
2 6 8
y <= 6
4
2y ≤ 12
y <= 6
x 8
6
4
2
2 8
x <= 4
6 4
x ≤ 4
4 6 8 2
2 4 6 8
x y
y <= 6 x <= 4
3x + 2y <= 18
3x + 2y ≤ 18
4 6 8 2
2 4 6 8
x y <= 6 x <= 4
3x + 2y <= 18
f(x)=300x+500y
f(x) = 300x + 500y
4 6 8 2
2 4 6 8
x y
y <= 6 x <= 4
3x + 2y <= 18
Maximisation
f(x)=300x+500y
Maximal point: x = 2 and y = 6
LP models are extremely usefull
Modelling is the proces of formulating a mahtematical model for the problem.
Lets look at a simple problem, the Wyndor glass problem, from the book “Introduction to Operations Research”, by Hillier & Liberman.
Wyndor glass is a compagny producing different kinds of windows and (window) doors. They are considering two new types of products, a new alu- minium door and wooden window. The question is now: Which mix of products should be produced, limited by the capacity of the production lines such that the profit is maximized ?
A production line for aluminium frames, (4 production hours available)
A production line for wood frames, (12 production hours available)
An assembly line, (18 production hours available)
Each batch of doors requires:
1 hour of work on the aluminium framing line 3 hours of work on the assembling line
Each batch of doors can be sold for 300 $’s.
2 hours of work on the wood framing line 2 hours of work on the assembling line
Each batch of windows can be sold for 500 $’s.
Informatics and Mathematical Modelling / Operations Research
Modelling: How ?
Given a problem we should ask the following questions:
What should we decide ? What are the limits on the produktion plans ?
Do not overuse the production capacity and only allow positive production.
What is the goal ?
Maximize the profit: 300D + 500W
Informatics and Mathematical Modelling / Operations Research
Modelling: How ?
Given a problem we should ask the following questions:
What should we decide ?
The ammount of production of Doors and Windows
What is the goal ?
Maximize the profit: 300D + 500W
Informatics and Mathematical Modelling / Operations Research
Modelling: How ?
Given a problem we should ask the following questions:
What should we decide ?
The ammount of production of Doors and Windows
What are the limits on the produktion plans ? What is the goal ?
Maximize the profit: 300D + 500W
Informatics and Mathematical Modelling / Operations Research
Modelling: How ?
Given a problem we should ask the following questions:
What should we decide ?
The ammount of production of Doors and Windows
What are the limits on the produktion plans ? Do not overuse the production capacity and only allow positive production.
Informatics and Mathematical Modelling / Operations Research
Modelling: How ?
Given a problem we should ask the following questions:
What should we decide ?
The ammount of production of Doors and Windows
What are the limits on the produktion plans ? Do not overuse the production capacity and only allow positive production.
What is the goal ?
questions:
What should we decide ?
The ammount of production of Doors and Windows
What are the limits on the produktion plans ? Do not overuse the production capacity and only allow positive production.
What is the goal ?
Maximize the profit: 300D + 500W
We decide:
The production (in batches) is defined by two decision variables: D (Doors) and W
(Windows)
The profit is calculated as a linear function:
prof it = 300 · D + 500 · W
The limited capacity of each line is modelled as a constraint.
M AX 300D + 500W ST :
D ≤ 4 2W ≤ 12 3D + 2W ≤ 18
D ≥ 0 W ≥ 0 Hmmm, this looks familiar ....
4 6 8 2
2 4 6 8
x y
y <= 6 x <= 4
3x + 2y <= 18
Maximisation
f(x)=300x+500y
earn us any money !
Finding optimal solutions is not trivial in more than 2 dimensions ...
... and we would like the computer do do the work for us ...
This is where Excel comes in: We can translate our above model into a linear model in Excel and the built in solver will find the optimal solution (but of course we already know it: D = 2 and W = 6).
Hence: Switch to Excel
following way:
Login to the databar
Start windows: win desk
Log into Excel again (same login name and password)
Choose Excel from the start button
Add solver login (unfortunately this is necessary after every Excel start up ...)
Tools drop down menu Choose add in’s
Choose solver add in Select ok
Load your favorite Excel model ....
Establish the “constraint result cells”, using sumproduct for each constraint
Establish the result cell (again sumproduct) Enter the solver
Select the cell
Add the constraints
Set options (assume linear annd non-negative)
Say ok
