O. Braun
1Linear Programming
Linear
Programming
20 40 60 80
20
40
60
80
100
x = #ducks
y = #trains
O. Braun
2Linear Programming
Introduction
Linear = linear functions
Programming = planning (it doesn‘t refer to computer programming)
• Linear Programming (LP) has extraordinary impact since the 1950‘s.
LP is a standard tool that has saved millions of dollars for many companies.
• The most common type of application involves the following general problem:
Allocate competing activities to limited resources in an optimal way
(How much of each resource will be consumed by each activity?)
• Examples:
• allocate products to machines
• allocate domestic needs to national resources
• allocate money to investments (portfolio selection)
• allocate products to land (agricultural planning)
• allocate doctors to patients
Hillier, F.S., Lieberman, G.J., Introduction to Operations Research, McGraw Hill, 2015, pp.25-26.
O. Braun
3Linear Programming
Outline
• You will gain insight into this topic as you work through two miniature prototypes of
linear programming problems (small enough to be solved graphically and that you
can see how the Simplex algorithm works) and a Case Study.
• Interpretation of the optimal Simplex tableau:
• How does the production program and the profit change if we would have one
more unit of a certain resource?
• What are lower bounds on the price for an additional product of a certain type?
• How does the production program and the profit change if we would outsource
a production step?
O. Braun
4Linear Programming
Problem 1
A company produces wooden ducks and trains.
Profits are $3 for each duck and $2 for each train.
Varnishing and assembling need the following amounts of time:
Varnishing Assembling
per duck 2 hours 1 hour
per train 1 hour 1 hour
Time restriction for varnishing is 100 hrs per week, for assembling it is 80 hrs per week.
The demand for ducks is limited to 40 ducks per week.
How many ducks (x) and how many trains (y) does the company has to produce per week
such that the profit is maximized?
a) Formulate the linear program.
b) Solve the problem graphically.
c) Solve the problem with the Simplex algorithm.
d) Give an interpretation of the shadow prices.
O. Braun
5Linear Programming
Problem 1: Linear Program
x = # ducks
y = # trains
max 3x + 2 y
s.t. 2x + 1 y < 100 (Varnishing)
1x + 1 y < 80 (Assembling)
x < 40 (Sales)
x, y > 0
O. Braun
6Linear Programming
20 40 60 80
20
40
60
80
100
1. Time restriction for varnishing is 100 hrs per week
and for assembling 80 hrs per week.
Varnishing Assembling
per duck 2 hours 1 hour
per train 1 hour 1 hour
2. The demand for ducks is limited to 40 ducks per
week.
3. The profit is $3 for each duck and $2 for each train.
x = #ducks
y = #trains
Problem 1: Graphical Solution
O. Braun
7Linear Programming
20 40 60 80
20
40
60
80
100
1. Time restriction for varnishing is 100 hrs per week
and for assembling 80 hrs per week.
Varnishing Assembling
per duck 2 hours 1 hour
per train 1 hour 1 hour
2. The demand for ducks is limited to 40 ducks per
week.
3. The profit is $3 for each duck and $2 for each train.
x = #ducks
y = #trains
Problem 1
O. Braun
8Linear Programming
20 40 60 80
20
40
60
80
100
1. Time restriction for varnishing is 100 hrs per week
and for assembling 80 hrs per week.
Varnishing Assembling
per duck 2 hours 1 hour
per train 1 hour 1 hour
2. The demand for ducks is limited to 40 ducks per
week.
3. The profit is $3 for each duck and $2 for each train.
x = #ducks
y = #trains
Problem 1
O. Braun
9Linear Programming
20 40 60 80
20
40
60
80
100
1. Time restriction for varnishing is 100 hrs per week
and for assembling 80 hrs per week.
Varnishing Assembling
per duck 2 hours 1 hour
per train 1 hour 1 hour
2. The demand for ducks is limited to 40 ducks per
week.
3. The profit is $3 for each duck and $2 for each train.
x = #ducks
y = #trains
Problem 1
O. Braun
10Linear Programming
20 40 60 80
20
40
60
80
100
1. Time restriction for varnishing is 100 hrs per week
and for assembling 80 hrs per week.
Varnishing Assembling
per duck 2 hours 1 hour
per train 1 hour 1 hour
2. The demand for ducks is limited to 40 ducks per
week.
3. The profit is $3 for each duck and $2 for each train.
x = #ducks
y = #trains
Problem 1
O. Braun
11Linear Programming
20 40 60 80
20
40
60
80
100
1. Time restriction for varnishing is 100 hrs per week
and for assembling 80 hrs per week.
Varnishing Assembling
per duck 2 hours 1 hour
per train 1 hour 1 hour
2. The demand for ducks is limited to 40 ducks per
week.
3. The profit is $3 for each duck and $2 for each train.
z(0,0) = 0
z(40,0) =$120
z(40,20)=$160
z(20,60)=$180
z(0,80) =$160
x = #ducks
y = #trains
Problem 1
O. Braun
12Linear Programming
20 40 60 80
20
40
60
80
100
1. Time restriction for varnishing is 100 hrs per week
and for assembling 80 hrs per week.
Varnishing Assembling
per duck 2 hours 1 hour
per train 1 hour 1 hour
2. The demand for ducks is limited to 40 ducks per
week.
3. The profit is $3 for each duck and $2 for each train.
x = #ducks
y = #trains
Problem 1
O. Braun
13Linear Programming
Simplex algorithm
x = # ducks, y = # trains
max 3x + 2 y
s.t. 2x + 1 y < 100 (Varnishing)
1x + 1 y < 80 (Assembling)
x < 40 (Sales)
x, y > 0
max 3x + 2 y
s.t. 2x + 1 y + s1 = 100
1x + 1 y + s2 = 80
1x + s3 = 40
x, y > 0
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
Initial Tableau:
objective
value z
O. Braun
14Linear Programming
Slack variables
x = # ducks, y = # trains
max 3x + 2 y
s.t. 2x + 1 y < 100 (Varnishing)
1x + 1 y < 80 (Assembling)
x < 40 (Sales)
x, y > 0
max 3x + 2 y
s.t. 2x + 1 y + s1 = 100
1x + 1 y + s2 = 80
1x + s3 = 40
x, y > 0
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
Initial Tableau:
objective
value z
s1, s2, s3 are the slack variables.
Interpretation:
s1 = unused capacity in the varnishing department
s2 = unused capacity in the assembling department
s3 = unused sales capacity
O. Braun
15Linear Programming
Interpretation of the Tables
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
objective
value z
Initial Solution:
x=0, y=0
s1=100, s2=80, s3=40
z=0
This line is from the goal function
max 3x+2y. But why the negtive values
-3 and -2? The answer is:
If we would decrease x by 1 unit, the
profit would go down by $3, therefore -3.
If we would decrease y by 1 unit, the
profit would go down by $2, therefore -2.
s1, s2, s3 are the base variables.
All other variables, i.e. x and y
in this case, are = 0.
O. Braun
16Linear Programming
Performing a Simplex step
20 40 60 80
20
40
60
80
100
x = #ducks
y = #trains
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
Initial Solution:
x=0, y=0
s1=100, s2=80, s3=40
z=0
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
O. Braun
17Linear Programming
Pivot-Column
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
100/2=50
80/1=80
40/1=40
Initial Solution:
x=0, y=0
s1=100, s2=80, s3=40
z=0
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
O. Braun
18Linear Programming
Pivot-Row
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
100/2=50
80/1=80
40/1=40
choose that row
with the smallest
non-negative
value as
Pivot-Row
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
Initial Solution:
x=0, y=0
s1=100, s2=80, s3=40
z=0
O. Braun
19Linear Programming
Pivot-Element
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
100/2=50
80/1=80
40/1=40
Pivot-Element
choose that row
with the smallest
non-negative
value as
Pivot-Row
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
Initial Solution:
x=0, y=0
s1=100, s2=80, s3=40
z=0
O. Braun
20Linear Programming
Simplex algorithm
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
100/2=50
80/1=80
40/1=40
Pivot-Element
choose that row
with the smallest
non-negative
value as
Pivot-Row
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
2.3=
1.3
x 1 0 0 0 1 40
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
Initial Solution:
x=0, y=0
s1=100, s2=80, s3=40
z=0
This entry
(Pivot-Element
from the
previous table)
must be = 1
O. Braun
21Linear Programming
Simplex algorithm
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
100/2=50
80/1=80
40/1=40
Pivot-Element
choose that row
with the smallest
non-negative
value as
Pivot-Row
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
2.2=
1.2-1.3
s2 0 1 0 1 -1 40
2.3=
1.3
x 1 0 0 0 1 40
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
Goal: Achieve
a 0 in the
pivot column
by the
addition or
subtraction
of a multiple
of the pivot
element.
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
Initial Solution:
x=0, y=0
s1=100, s2=80, s3=40
z=0
O. Braun
22Linear Programming
Simplex algorithm
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
100/2=50
80/1=80
40/1=40
Pivot-Element
choose that row
with the smallest
non-negative
value as
Pivot-Row
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
2.1=
1.1-2*1.3
s1 0 1 1 0 -2 20
2.2=
1.2-1.3
s2 0 1 0 1 -1 40
2.3=
1.3
x 1 0 0 0 1 40
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
Initial Solution:
x=0, y=0
s1=100, s2=80, s3=40
z=0
Goal: Achieve
a 0 in the
pivot column
by the
addition or
subtraction
of a multiple
of the pivot
element.
O. Braun
23Linear Programming
Simplex algorithm
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
100/2=50
80/1=80
40/1=40
Pivot-Element
choose that row
with the smallest
non-negative
value as
Pivot-Row
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
2.1=
1.1-2*1.3
s1 0 1 1 0 -2 20
2.2=
1.2-1.3
s2 0 1 0 1 -1 40
2.3=
1.3
x 1 0 0 0 1 40
2.4=
1.4+3*1.3
0 -2 0 0 3 120
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
Initial Solution:
x=0, y=0
s1=100, s2=80, s3=40
z=0
Goal: Achieve
a 0 in the
pivot column
by the
addition or
subtraction
of a multiple
of the pivot
element.
O. Braun
24Linear Programming
Simplex algorithm
x y s1 s2 s3
1.1 s1 2 1 1 0 0 100
1.2 s2 1 1 0 1 0 80
1.3 s3 1 0 0 0 1 40
1.4 -3 -2 0 0 0 0
100/2=50
80/1=80
40/1=40
Pivot-Element
choose that row
with the smallest
non-negative
value as
Pivot-Row
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
2.1=
1.1-2*1.3
s1 0 1 1 0 -2 20
2.2=
1.2-1.3
s2 0 1 0 1 -1 40
2.3=
1.3
x 1 0 0 0 1 40
2.4=
1.4+3*1.3
0 -2 0 0 3 120
New Solution:
x=40, y=0
s1=20, s2=40, s3=0
z=120
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
New solution!
Base variables
x=40, s1=20,
s2=40,
other var.
y=0, s3=0.
Why is s1=20?
Unused capac.
in the
varnish. dpmt.
is = 20, 20
hours are left
O. Braun
25Linear Programming
x y s1 s2 s3
2.1 s1 0 1 1 0 -2 20
2.2 s2 0 1 0 1 -1 40
2.3 x 1 0 0 0 1 40
2.4 0 -2 0 0 3 120
Simplex algorithm
20/1=20
40/1=40
40/0 n.def.
choose that row
with the smallest
non-negative
value as
Pivot-Row
20 40 60 80
20
40
60
80
100
Pivot-Element
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
Solution:
x=40, y=0
s1=20, s2=40, s3=0
z=120
O. Braun
26Linear Programming
x y s1 s2 s3
2.1 s1 0 1 1 0 -2 20
2.2 s2 0 1 0 1 -1 40
2.3 x 1 0 0 0 1 40
2.4 0 -2 0 0 3 120
Simplex algorithm
20/1=20
40/1=40
40/0 n.def.
choose that row
with the smallest
non-negative
value as
Pivot-Row
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
3.1=
2.1
y 0 1 1 0 -2 20
3.2=
2.2-2.1
s2 0 0 -1 1 1 20
3.3=
2.3
x 1 0 0 0 1 40
3.4=
2.4+2*2.1
0 0 2 0 -1 160
New Solution:
x=40, y=20
s1=0, s2=20, s3=0
z=160
Pivot-Element
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
O. Braun
27Linear Programming
x y s1 s2 s3
3.1 y 0 1 1 0 -2 20
3.2 s2 0 0 -1 1 1 20
3.3 x 1 0 0 0 1 40
3.4 0 0 2 0 -1 160
Simplex algorithm
20/(-2)=-10
20/1=20
40/1=40
choose that row
with the smallest
non-negative
value as
Pivot-Row
20 40 60 80
20
40
60
80
100
Pivot-Element
Solution:
x=40, y=20
s1=0, s2=20, s3=0
z=160
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
O. Braun
28Linear Programming
x y s1 s2 s3
3.1 y 0 1 1 0 -2 20
3.2 s2 0 0 -1 1 1 20
3.3 x 1 0 0 0 1 40
3.4 0 0 2 0 -1 160
Simplex algorithm
20/(-2)=-10
20/1=20
40/1=40
choose that row
with the smallest
non-negative
value as
Pivot-Row
20 40 60 80
20
40
60
80
100
x y s1 s2 s3
4.1=
3.1+2*3.2
y 0 1 -1 2 0 60
4.2=
3.2
s3 0 0 -1 1 1 20
4.3=
3.3-3.2
x 1 0 1 -1 0 20
4.4=
3.4+3.2
0 0 1 1 0 180
New Solution:
x=20, y=60
s1=0, s2=0, s3=20
z=180
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
O. Braun
29Linear Programming
x y s1 s2 s3
4.1 y 0 1 -1 2 0 60
4.2 s3 0 0 -1 1 1 20
4.3 x 1 0 1 -1 0 20
4.4 0 0 1 1 0 180
Simplex algorithm
20 40 60 80
20
40
60
80
100
Optimal Solution:
x=20, y=60
s1=0, s2=0, s3=20
z=180
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
O. Braun
30Linear Programming
Shadow Prices
In the following, you will see why Linear Programming / the Simplex
algorithm can be so interesting for companies.
We are going to answer the following questions:
How does the production program and the profit change,
• if the company would have one more hour in the varnishing department,
• if the company would have one more hour in the varnishing department.
O. Braun
31Linear Programming
x y s1 s2 s3
4.1 y 0 1 -1 2 0 60
4.2 s3 0 0 -1 1 1 20
4.3 x 1 0 1 -1 0 20
4.4 0 0 1 1 0 180
Simplex algorithm
20 40 60 80
20
40
60
80
100
Give an interpretation of the shadow prices:
• If the company would have one hour more for varnishing the
products, how would the production program and the profit
change?
• If the company would have one hour more for assembling the
products, how would the production program and the profit
change? Optimal Solution:
x=20, y=60
s1=0, s2=0, s3=20
z=180
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
O. Braun
32Linear Programming
x y s1 s2 s3
4.1 y 0 1 -1 2 0 60
4.2 s3 0 0 -1 1 1 20
4.3 x 1 0 1 -1 0 20
4.4 0 0 1 1 0 180
Simplex algorithm
20 40 60 80
20
40
60
80
100
Give an interpretation of the shadow prices:
• If the company would have one hour more for varnishing the
products, how would the production program and the profit
change? Profit: Varnish: Assembl:
x:+1 duck +$3 +2 hrs +1 hrs
y: -1 train -$2 -1 hrs -1 hrs
+$1 +1 hrs 0 hrs
• If the company would have one hour more for assembling the
products, how would the production program and the profit
change? Optimal Solution:
x=20, y=60
s1=0, s2=0, s3=20
z=180
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
see the
following
slide
O. Braun
33Linear Programming
Simplex algorithm
20 40 60 80
20
40
60
80
100
If the company would have 1 hour more for varnishing the
products, how would the production program and the profit
change? Profit: Varnish: Assembl:
x:+1 duck +$3 +2 hrs +1 hrs
y: -1 train -$2 -1 hrs -1 hrs
+$1 +1 hrs 0 hrs
Optimal Solution:
x=20, y=60
s1=0, s2=0, s3=20
z=180
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
The company gets one more hour in the varnishing
department.
How does the production program change?
1 more duck, 1 less train
How does the profit change?
+ $1
The change in the production program actually changes
only that the company uses one more hour in the
varnishing department. In the assembling department are
still 80 hours used. That‘s why the Simplex algorithm is
so useful: you can change something in one bottleneck
department (like varnishing) and the other (fully used!)
botlleneck departments (here the assembling department)
remain unchanged.
O. Braun
34Linear Programming
x y s1 s2 s3
4.1 y 0 1 -1 2 0 60
4.2 s3 0 0 -1 1 1 20
4.3 x 1 0 1 -1 0 20
4.4 0 0 1 1 0 180
Simplex algorithm
20 40 60 80
20
40
60
80
100
Optimal Solution:
x=20, y=60
s1=0, s2=0, s3=20
z=180
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
x = #ducks
y = #trains
Give an interpretation of the shadow prices:
• If the company would have one hour more for varnishing the
products, how would the production program and the profit
change? Profit: Varnish: Assembl:
x:+1 duck +$3 +2 hrs +1 hrs
y: -1 train -$2 -1 hrs -1 hrs
+$1 +1 hrs 0 hrs
• If the company would have one hour more for assembling the
products, how would the production program and the profit
change? Profit: Varnish: Assembl:
x: -1 duck -$3 -2 hrs -1 hrs
y: +2 trains+$4 +2 hrs +2 hrs
+$1 0 hrs +1 hrs
see the
following
slide
O. Braun
35Linear Programming
Simplex algorithm
If the company would have one hour more for assembling the
products, how would the production program and the profit
change? Profit: Varnish: Assembl:
x: -1 duck -$3 -2 hrs -1 hrs
y: +2 trains +$4 +2 hrs +2 hrs
+$1 0 hrs +1 hrs
Optimal Solution:
x=20, y=60
s1=0, s2=0, s3=20
z=180
x = # ducks, y = # trains
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 100 (Varnishing)
1 x + 1 y + s2 = 80 (Assembling)
1 x + s3 = 40 (Sales)
x, y > 0
20 40 60 80
20
40
60
80
100
x = #ducks
y = #trains
The company gets one more hour in the assembling
department.
How does the production program change?
1 less duck, 2 more trains
How does the profit change?
+ $1
The change in the production program actually changes
only that the company uses one more hour in the
assembling department. In the varnishing department are
still 100 hours used. That‘s why the Simplex algorithm is
so useful: you can change something in one bottleneck
department (like assembling) and the other (fully used!)
botlleneck departments (here the varnishing department)
remain unchanged.
O. Braun
36Linear Programming
Problem 2
• A company produces two products A and B. Profit is $3 for each piece of A and $2 for
each piece of B.
• The primary products P and Q are necessary to produce A and B, and there are only 8
parts of P and 6 parts of Q accessible.
• Each piece of product A needs 2 parts of P and 1 part of Q.
• Each piece of product B needs 1 part of P and 1 part of Q.
How many products A and B does the company have to produce when the objective
function is to maximize the profit?
a) Formulate the linear program.
b) Solve the problem graphically.
c) Solve the problem with the Simplex algorithm.
d) Give an interpretation of the shadow prices.
O. Braun
37Linear Programming
Solution
a) Linear Program:
x = # pieces of type A, y = # pieces of type B
max 3x + 2 y
s.t. 2x + 1 y < 8 (8 parts of P)
1x + 1 y < 6 (6 parts of Q)
x, y > 0
b) Graphical Solution:
2 4 6 8
2
4
6
8
x = #A
y = #B
O. Braun
38Linear Programming
Solution
x = # pieces of type A, y= # pieces of type B
max 3x + 2 y
s.t. 2x + 1 y < 8 (P)
1x + 1 y < 6 (Q)
x, y > 0
x y s1 s2
1.1 s1 2 1 1 0 8
1.2 s2 1 1 0 1 6
1.3 -3 -2 0 0 0
Initial Tableau:
objective
value z
Initial Solution:
x=0, y=0
s1=8, s2=6
z=0
O. Braun
39Linear Programming
Solution
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
2 4 6 8
2
4
6
8
x = #A
y = #B
Initial Solution:
x=0, y=0
s1=8, s2=6
z=0
x y s1 s2
1.1 s1 2 1 1 0 8
1.2 s2 1 1 0 1 6
1.3 -3 -2 0 0 0
O. Braun
40Linear Programming
Solution
2 4 6 8
2
4
6
8
x = #A
y = #B
Solution:
x=0, y=0
s1=8, s2=6
z=0
x y s1 s2
1.1 s1 2 1 1 0 8
1.2 s2 1 1 0 1 6
1.3 -3 -2 0 0 0
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
8/2=4
6/1=6
choose that row
with the smallest
non-negative
value as
Pivot-Row
Pivot-Element
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
O. Braun
41Linear Programming
Solution
2 4 6 8
2
4
6
8
x = #A
y = #B
x y s1 s2
2.1=
1.1 / 2
x
2.2=
1.2 – ½*1.1
s2
2.3=
1.3+3/2*1.1
x y s1 s2
1.1 s1 2 1 1 0 8
1.2 s2 1 1 0 1 6
1.3 -3 -2 0 0 0
8/2=4
6/1=6
Pivot-Element
choose that row
with the smallest
non-negative
value as
Pivot-Row
Solution:
x=0, y=0
s1=8, s2=6
z=0
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
O. Braun
42Linear Programming
Solution
2 4 6 8
2
4
6
8
x = #A
y = #B
New Solution:
x=4, y=0
s1=0, s2=2
z=12
x y s1 s2
2.1=
1.1 / 2
x 1 0.5 0.5 0 4
2.2=
1.2 – ½*1.1
s2 0 0.5 -0.5 1 2
2.3=
1.3+3/2*1.1
0 -0.5 1.5 0 12
x y s1 s2
1.1 s1 2 1 1 0 8
1.2 s2 1 1 0 1 6
1.3 -3 -2 0 0 0
8/2=4
6/1=6
Pivot-Element
choose that row
with the smallest
non-negative
value as
Pivot-Row• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
O. Braun
43Linear Programming
Solution
x y s1 s2
2.1 x 1 0.5 0.5 0 4
2.2 s2 0 0.5 -0.5 1 2
2.3 0 -0.5 1.5 0 12
4/0,5=8
2/0,5=4
Pivot-Element
choose that row
with the smallest
non-negative
value as
Pivot-Row
New Solution:
x=2, y=4
s1=0, s2=2
z=14
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x y s1 s2
3.1=
2.1-2.2
x 1 0 1 -1 2
3.2=
2.2*2
y 0 1 -1 2 4
3.3=
2.3+2.2
0 0 1 1 14
2 4 6 8
2
4
6
8
x = #A
y = #B
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
O. Braun
44Linear Programming
Solution
2 4 6 8
2
4
6
8
x = #A
y = #B
Optimal Solution:
x1=2, x2=4
s1=0, s2=0
z=14
x y s1 s2
2.1 x 1 0 1 -1 2
2.2 y 0 1 -1 2 4
2.3 0 0 1 1 14
• choose that column with the smallest
negative number as Pivot-Column
• if there are only non-negative numbers
left, then the algorithm terminates
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
O. Braun
45Linear Programming
Solution
x y s1 s2
2.1 x 1 0 1 -1 2
2.2 y 0 1 -1 2 4
2.3 0 0 1 1 14
Give an interpretation of the shadow prices:
• If the company could have access to one more piece of P,
how would the production program and the profit change?
Profit Pieces of P Pieces of Q
x +1 piece of A=+$3 +2 pieces +1 piece
y -1 piece of B=-$2 -1 piece -1 piece
+$1 +1 piece 0 pieces
• If the company could have access to one more piece of Q,
how would the production program and the profit change?
2 4 6 8
2
4
6
8
x = #A
y = #B
Optimal Solution:
x1=2, x2=4
s1=0, s2=0
z=14
see the
following
slide
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
O. Braun
46Linear Programming
Simplex algorithm
If the company could have access to one more piece of P, how
would the production program and the profit change?
Profit Pieces of P Pieces of Q
x +1 piece of A=+$3 +2 pieces +1 piece
y -1 piece of B=-$2 -1 piece -1 piece
+$1 +1 piece 0 pieces
The company gets access one more piece of P.
How does the production program change?
1 more piece of A, 1 less piece of B
How does the profit change?
+ $1
The change in the production program actually changes
only that the company uses one more piece of P, the total
number of pieces of Q that are used remains unchanged.
2 4 6 8
2
4
6
8
x = #A
y = #B
Optimal Solution:
x1=2, x2=4
s1=0, s2=0
z=14
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
O. Braun
47Linear Programming
Solution
x y s1 s2
2.1 x 1 0 1 -1 2
2.2 y 0 1 -1 2 4
2.3 0 0 1 1 14
Give an interpretation of the shadow prices:
• If the company could have access to one more piece of P,
how would the production program and the profit change?
Profit Pieces of P Pieces of Q
x +1 piece of A=+$3 +2 piece +1 piece
y -1 piece of B=-$2 -1 piece -1 piece
+$1 +1 piece 0 pieces
• If the company could have access to one more piece of Q,
how would the production program and the profit change?
Profit Pieces of P Pieces of Q
x -1 piece of A=-$3 -1 piece -2 pieces
y +2 pieces of B=+$4 +2 pieces +2 pieces
+$1 +1 piece 0 pieces
2 4 6 8
2
4
6
8
x = #A
y = #B
Optimal Solution:
x1=2, x2=4
s1=0, s2=0
z=14
see the
following
slide
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
O. Braun
48Linear Programming
Simplex algorithm
• If the company could have access to one more piece of Q,
how would the production program and the profit change?
Profit Pieces of P Pieces of Q
x -1 piece of A=-$3 -2 pieces -1 pieces
y +2 pieces of B=+$4 +2 pieces +2 pieces
+$1 0 pieces +1 piece
The company gets access one more piece of Q.
How does the production program change?
1 less piece of A, 2 more pieces of B
How does the profit change?
+ $1
The change in the production program actually changes
only that the company uses one more piece of Q, the total
number of pieces of P that are used remains unchanged.
2 4 6 8
2
4
6
8
x = #A
y = #B
Optimal Solution:
x1=2, x2=4
s1=0, s2=0
z=14
x = # A, y = # B
max 3 x + 2 y
s.t. 2 x + 1 y + s1 = 8 (P)
1 x + 1 y + s2 = 6 (Q)
x, y > 0
O. Braun
49Linear Programming
Case Study
Case Study
Sunshine Corp.
O. Braun
50Linear Programming
Case Study
In what follows, you will see how Sunshine Corp. can answer the following
questions with the help of the optimal Simplex tableau:
1. More resources (Casting, Liquering, Mounting Department)
2. More umbrellas
3. Maximum gain in profit
4. Outsourcing
O. Braun
51Linear Programming
Case Study
Sunshine Corp. produces and sells umbrellas of five different types (all prices are per umbrella):
Arturo ($199), Bernie ($142), Caesar ($99), Donald ($189), Emily ($219).
Each umbrella is produced in three steps:
1. In the Casting step (C), liquid aluminium is pressed in a steel shape to build the aluminum stands for the umbrellas.
2. The aluminum stands are varnished in the Liquering step (L).
3. In the Mounting step (M), the aluminum stands and the umbrella tissues are assembled to the final umbrellas.
Fix costs: The distribution department (fix costs $55.000 per year) is responsible for the sales. Administrative fix costs
are $20.000 per year. Fix costs in the three production departments are $75.000 (C), $32.000 (L), $13.000 (M).
Variable costs: Distribution costs (per umbrella) are $6 (Arturo), $4 (Bernie), $2 (Caesar), $2 (Donald), $4 (Emily).
Material costs (in $ per umbrealla) are
Arturo Bernie Caesar Donald Emily
Casting (C) 43 29 16 44 37
Liquering (L) 22 24 16 33 48
Mounting (M) 55 20 20 48 64
Production restrictions: Casting costs $5 per minute, Liquering $4 per minute, Mounting $6 per minute.
Production coefficients are (in minutes per umbrella):
Arturo Bernie Caesar Donald Emily maximum capacity (minutes)
Casting (C) 5 2 3 4 2 96.000
Liquering (L) 4 3 2 4 4 96.000
Mounting (M) 2 5 2 3 4 76.000
Sales restrictions: Maximum numbers of umbrellas that can be sold (no more are allowed to be produced) are:
12.000 Arturo, 16.000 Bernie, 8.000 Caesar, 10.000 Donald, 16.000 Emily.
O. Braun
52Linear Programming
Objective function:
max 20 xA + 13 xB + 10 xC + 8 xD + 16 xE – 195.000
Production restrictions:
5 xA + 2 xB + 3 xC + 4 xD + 2 xE < 96.000 (Casting)
4 xA + 3 xB + 2 xC + 4 xD + 4 xE < 96.000 (Liquering)
2 xA + 5 xB + 2 xC + 3 xD + 4 xE < 76.000 (Mounting)
Sales restrictions:
xA < 12.000
xB < 16.000
xC < 8.000
xD < 10.000
xE < 16.000
Non-Negativity restrictions:
xA, xB, xC, xD, xE > 0
Mathematical program
Contribution margin „Arturo“:
$199
– $6 Distribution costs
– $43 (C) Material costs
– $22 (L)
– $55 (M)
– $5/min*5min (C) Production
– $4/min*4min (L) restrictions
– $6/min*2min (M)
= $20
Fix costs:
$55.000
+$20.000
+$75.000+$32.000+$13.000
=$195.000
O. Braun
53Linear Programming
Optimal Simplex Table
5. Lösung xA xB xC xD xE scasting sliquering smounting sA sB sC sD sE
P 250.000 0 0 0 9,75 0 1 3,25 0,25 1,5 0 0 0 0
xE 7.750 0 0 0 0,8125 1 -0,25 0,6875 -0,3125 -0,875 0 0 0 0
xC 5.500 0 0 1 1,125 0 0,5 -0,125 -0,125 -1,75 0 0 0 0
xB 2.000 0 1 0 -0,5 0 0 -0,5 0,5 1 0 0 0 0
xA 12.000 1 0 0 0 0 0 0 0 1 0 0 0 0
sB 14.000 0 0 0 0,5 0 0 0,5 -0,5 -1 1 0 0 0
sC 2.500 0 0 0 -1,125 0 -0,5 0,125 0,125 1,75 0 1 0 0
sD 10.000 0 0 0 1 0 0 0 0 0 0 0 1 0
sE 8.250 0 0 0 -0,8125 0 0,25 -0,6875 0,3125 0,875 0 0 0 1
O. Braun
54Linear Programming
Interpretation of the optimal Simplex tableau
MORE RESOURCES
O. Braun
55Linear Programming
Important Data
contribution optimal prod. sales
margin program restrictions
$20 xA = 12.000 12.000
$13 xB = 2.000 16.000
$10 xC = 5.500 8.000
$8 xD = 0 10.000
$16 xE = 7.750 16.000
Production costs:
Casting $5 / min
Liquering $4 / min
Mounting $6 / min
Production restrictions:
A B C D E max. capacity
(in minutes)
Casting 5 2 3 4 2 96.000
Liquering 4 3 2 4 4 96.000
Mounting 2 5 2 3 4 76.000
P
O. Braun
56Linear Programming
Interpretation of the optimal Simplex tableau
If the company could have 1 more minute in the Casting department:
How would the production program and the profit change?
Prod.prg. Profit Changes in the departments:
Casting Liquering Mounting
xE -0.25 p. * $16 = -$ 4.00 *2= -0.5 min. *4= -1.0 min. *4= -1.0 min.
xC +0.5 p. * $10 = +$ 5.00 *3= +1.5 min. *2= +1.0 min. *2= +1.0 min.
+$ 1.00 +1 min. 0 min. 0 min.
The company gets one more minute in the casting department.
How does the production program change?
Emily -0.25 p.
Caesar +0.5 p.
How does the profit change? + $1.00
Note that there is no change in the (still) fully used bottleneck production resources (liquering, mounting).
A B C D E max. capacity
(in minutes)
Casting 5 2 3 4 2 96.000
Liquering 4 3 2 4 4 96.000
Mounting 2 5 2 3 4 76.000
P
O. Braun
57Linear Programming
Interpretation of the optimal Simplex tableau
If the company could have 1 more minute in the Liquering department:
How would the production program and the profit change?
Prod.prg. Profit Changes in the departments:
Casting Liquering Mounting
xE +0.6875p. * $16 = +$11.00 *2=+1.375 min. *4=+2.75 min. *4=+2.75 min.
xC -0.125 p. * $10 = -$ 1.25 *3=-0.375 min. *2=-0.25 min. *2=-0.25 min.
xB -0.5 p. * $13 = -$ 6.50 *2=-1 min. *3=-1.5 min. *5=-2.5 min.
+$ 3.25 0 min. +1 min. 0 min.
The company gets one more minute in the liquering department.
How does the production program change?
Emily +0.6875 p.
Caesar -0.125 p.
Bernie -0.5 p.
How does the profit change? + $3.25
Note that there is no change in the (still) fully used bottleneck production resources (casting, mounting).
A B C D E max. capacity
(in minutes)
Casting 5 2 3 4 2 96.000
Liquering 4 3 2 4 4 96.000
Mounting 2 5 2 3 4 76.000
P
O. Braun
58Linear Programming
Interpretation of the optimal Simplex tableau
If the company could have 1 more minute in the Mounting department:
How would the production program and the profit change?
Prod.prg. Profit Changes in the departments:
Casting Liquering Mounting
xE -0.3125p. * $16 = -$ 5.00 *2=-0.625 min. *4=-1.25 min. *4=+1.25 min.
xC -0.125 p. * $10 = -$ 1.25 *3=-0.375 min. *2=-0.25 min. *2=-0.25 min.
xB +0.5 p. * $13 = +$ 6.50 *2=+1 min. *3=+1.5 min. *5=+2.5 min.
+$ 0.25 0 min. 0 min. +1 min.
The company gets one more minute in the mounting department.
How does the production program change?
Emily -0.3125 p.
Caesar -0.125 p.
Bernie +0.5 p.
How does the profit change? + $0.25.
Note that there is no change in the (still) fully used bottleneck production ressources (casting, liquering).
A B C D E max. capacity
(in minutes)
Casting 5 2 3 4 2 96.000
Liquering 4 3 2 4 4 96.000
Mounting 2 5 2 3 4 76.000
P
O. Braun
59Linear Programming
Interpretation of the optimal Simplex tableau
MORE UMBRELLAS
O. Braun
60Linear Programming
Interpretation of the optimal Simplex table
All 12.000 Arturo umbrellas that can be sold (sales restriction) are
produced. If the company could sell 1 more Arturo umbrella:
How would the production program and the profit change?
Prod.prg. Profit Changes in the departments:
Casting Liquering Mounting
xE -0.875p. * $16 = -$14.00 *2=-1.75 min. *4=-3.5 min. *4=-3.5 min.
xC -1.75 p. * $10 = -$17.50 *3=-5.25 min. *2=-3.5 min. *2=-3.5 min.
xB +1 p. * $13 = +$13.00 *2=+2 min. *3=+3 min. *5=+5 min.
xA +1 p. * $20 = +$20.00 *5=+5 min. *4=+4 min. *2=+2 min.
+$ 1.50 0 min. 0 min. 0 min.
The company can sell one more Arturo umbrella.
How does the production program change?
Emily -0.875 p.
Caesar -1.75 p.
Bernie +1 p.
Arturo +1 p.
How does the profit change? + $1.50.
Note that there is no change in the (still) fully used bottleneck production resources (casting, liquering, mounting).
A B C D E max. capacity
(in minutes)
Casting 5 2 3 4 2 96.000
Liquering 4 3 2 4 4 96.000
Mounting 2 5 2 3 4 76.000
P
O. Braun
61Linear Programming
Lower bound for the price of additional Arturo umbrellas
What is the lower bound for the price of one Arturo for these additional orders?
$199-$1.50 =$197.50.
Material: $43+$22+$55=$120
Distribution: $6
Production: 5min x $5/min (C) +
4min x $4/min (L) +
2min x $6/min (M) = $53
In total $179.
Opportunity costs:
a) 5min x $1.00/min (C)
+ 4min x $3.25/min (L)
+ 2min x $0.25/min (M)
= $18.50
b) $16/p x 0.875 p (xE)
+ $10/p x 1.75 p (xC)
– $13/p x 1 p (xB)
= $18.50
In total $197.50.
Production restrictions:
A B C D E
Casting 5 2 3 4 2
Liquering 4 3 2 4 4
Mounting 2 5 2 3 4
Time
Pieces
P
O. Braun
62Linear Programming
What if the company MUST produce Donald umbrellas?
If the company would have to produce 1 more piece of the Donald
umbrellas: How would the production program and the profit change?
Prod.prg. Profit Changes in the departments:
Casting Liquering Mounting
xE -0.8125p. * $16 = -$13.00 *2=-1.625 min. *4=-3.25 min. *4=-3.25 min.
xC -1.125 p. * $10 = -$11.25 *3=-3.375 min. *2=-2.25 min. *2=-2.25 min.
xB +0.5 p. * $13 = +$ 6.50 *2=+1 min. *3=+1.5 min. *5=+2.5 min.
xD +1 p. * $8 = +$ 8.00 *4=+4 min. *4=+4 min. *3=+3 min.
-$ 9.75 0 min. 0 min. 0 min.
The company HAS to produce umbrellas of type D.
How does the production program change?
Emily -0.8125 p.
Caesar -1.125 p.
Bernie +0.5 p.
Donald +1 p.
How does the profit change? – $9.75.
Note that there is no change in the (still) fully used bottleneck production ressources (casting, liquering, mounting).
A B C D E max. capacity
(in minutes)
Casting 5 2 3 4 2 96.000
Liquering 4 3 2 4 4 96.000
Mounting 2 5 2 3 4 76.000
P
O. Braun
63Linear Programming
Lower bound for the price of one Donald umbrella
What is the lower bound for the price of one Donald umbrella?
$189+$9.75 =$198.75.
Material: $44+$33+$48=$125
Distribution: $2
Production: 4min x $5/min (C) +
4min x $4/min (L) +
3min x $6/min (M) = $54
In total $181.
Opportunity costs:
a) 4min x $1.00/min (C)
+ 4min x $3.25/min (L)
+ 3min x $0.25/min (M)
= $17.75
b) $16/p x 0.8125 p (xE)
+ $10/p x 1.125 p (xC)
– $13/p x 0.5 p (xB)
= $17.75
In total $197.50.
Production restrictions:
A B C D E
Casting 5 2 3 4 2
Liquering 4 3 2 4 4
Mounting 2 5 2 3 4
Time
Pieces
P
xD
9,75
0,8125
1,125
-0,5
0
O. Braun
64Linear Programming
Lower bound for the price of additional Caesar umbrellas
Caesar umbrellas are in the optimal production program, but not all Caesars that could be sold are
actually produced. What would be the largest lower bound for the price for 1 Caesar such that Sunshine
Corp would not lose money (in comparison to the current optimal production program)?
Arturo:
+ 1 A -1.75 C
+ 1.75 C -1 A
+ 1 C -1/1.75 A = – 0.57 A
+ 1 C -0.57 A x $1.50 / A = -$0.86
Liquering:
+ 1 L -0.125 C
+ 0.125 C -1 L
+ 1 C -1/0.125 L = – 8 L
+ 1 C -8 L x $3.25 / L = -$26
Mounting:
+ 1 M -0.125 C
+ 0.125 C -1 M
+ 1 C -1/0.125 M = – 8 M
+ 1 C -8 M x $0.25 / M = -$2
Casting:
+1 min. Casting +0.5 C
+1 C +2 minutes Casting
(but this is not possible as the
96.000 minutes for casting
would have to be enlarged)
The price of 1 additional Caesar umbrella
would have to be at least
$99 + $.86 = $99.86.
P
Easy „Algorithm“:
Negative values xC-row /
corresponding slack variables
-0.125 / 3.25 = -$26
-0.125 / 0.25 = -$2
-1.75 / 1.5 = -$0.86
$99 + $0.86 = $99.86
O. Braun
65Linear Programming
Lower bound for the price of additional Caesar umbrellas
+1 A -1.75 C
+1 C -1/1.75 A, x $1,50 / A = – $0,86
Let‘s say, we want to sell 500 more Caesar umbrellas:
+500 C -(500/1.75) A = -285,7142857 A, x $1.50 / A = – $428,57142857
500 C cost currently $5.000.
In ordner not to loose money in comparison to the currently optimal situation,
we would have to do the following:
The price for the additional 500 C would have to be increased to $5.428,58.
How would the production program change (if we want to produce 500 more C)?
A: 12.000 – (500/1.75) = 11.714,2857 A, x $20 = 234.285,71
B: 2.000 – (500/1.75) = 1.714,2857 B, x $13 = 22.285,71
C: 5.500 + 500 = 5.500 C, x $10 = 55.000
+ 500 C, x $10,86 = 5.428,58
E: 7.750 + 250 = 8.000 E, x $16 = 128.000
-> 445.000,00
– 195.000,00 (fix costs)
= 250.000,00
O. Braun
66Linear Programming
Interpretation of the optimal Simplex tableau
MAXIMUM GAIN IN PROFIT
O. Braun
67Linear Programming
Important Data
contribution optimal prod. sales
margin program restrictions
$20 xA = 12.000 12.000
$13 xB = 2.000 16.000
$10 xC = 5.500 8.000
$8 xD = 0 10.000
$16 xE = 7.750 16.000
Production costs:
Casting $5 / min
Liquering $4 / min
Mounting $6 / min
Production restrictions:
A B C D E max. capacity
(in minutes)
Casting 5 2 3 4 2 96.000
Liquering 4 3 2 4 4 96.000
Mounting 2 5 2 3 4 76.000
P
O. Braun
68Linear Programming
Arturo umbrellas
What is the maximum total gain in profit for producing more Arturo umbrellas?
(1) +1 Arturo = +1 Bernie, upper bound for Bernie umbrellas=16.000
max. +14.000 more Bernie umbrellas max. +14.000 more Arturo umbrellas
(2) +1 Arturo = -0.875 Emily, lower bound for Emily umbrellas=0
max. 7.750 less Emily umbrellas max. 7.750 / 0.875 = 8857.14 more Arturo umbrellas
(3) + 1 Arturo = -1.75 Caesar, lower bound for Caesar umbrellas=0
max. 5.500 less Caesar umbrellas max. 3.142,857 more Arturo umbrellas
Max. gain in profit: 3.142 x $1.50 = $4.713
P
O. Braun
69Linear Programming
Casting department
What is the maximum total gain in profit for more minutes in the Casting department?
(1) +1 more min. in the Casting dept. = -0.25 Emily, lower bound for Emily umrellas = 0
max. 7.750 less Emily umbrellas max. 7.750 / 0.25 = 29.000 more min. in the Casting dept.
(2) + 1 more min. in the Casting dept. = +0.5 Caesar, upper bound for Caesar umbrellas=8.000
max. 2.500 more Caesar umbrellas max. 2.500 / 0.5 = 5.000 more min. in the Casting dept.
Max. gain in profit: 5.000 x $1.00 = $5.000
P
O. Braun
70Linear Programming
Liquering department
What is the maximum total gain in profit for more minutes in the Liquering department?
(1) + 1 more min. in the Liquering dept. = +0.6875 Emily, upper bound for Emily umbrellas=16.000
max. 8.250 more Emily umbrellas max. 8.250 / 0.6875 = 12.000 more min. in the Liqu. dept.
(2) +1 more min. in the Liquering dept. = -0.125 Caesar, lower bound for Caesar umrellas = 0
max. 5.500 less Caesar umbrellas max. 5.500 / 0.125 = 44.000 more min. in the Casting dept.
(3) +1 more min. in the Liquering dept. = -0.5 Bernie, lower bound for Bernie umrellas = 0
max. 2.000 less Bernie umbrellas max. 2.000 / 0.5 = 4.000 more min. in the Casting dept.
Max. gain in profit: 4.000 x $3.25 = $13.000
P
O. Braun
71Linear Programming
Mounting department
What is the maximum total gain in profit for more minutes in the Mounting department?
(1) +1 more min. in the Mounting dept. = -0.3125 Emily, lower bound for Emily umrellas = 0
max. 7.750 less Emily umbrellas max. 7.750 / 0.3125 = 24.800 more min. in the Mount. dept.
(2) +1 more min. in the Mounting dept. = -0.125 Caesar, lower bound for Caesar umrellas = 0
max. 5.500 less Caesar umbrellas max. 5.500 / 0.125 = 44.000 more min. in the Mount. dept.
(3) + 1 more min. in the Mounting dept. = +0.5 Bernie, upper bound for Bernie umbrellas=16.000
max. 14.000 more Bernie umbrellas max. 14.000 / 0.5 = 28.000 more min. in the Mount.dept.
Max. gain in profit: 24.800 x $0.25 = $6.200
P
O. Braun
72Linear Programming
Interpretation of the optimal Simplex tableau
OUTSOURCING
O. Braun
73Linear Programming
Outsourcing
In the optimal production program, 2.000 umbrellas of type B are produced. Sunshine Corp. gets an
offer to buy 500 umbrella stands (Type Bernie) for $39.50 per umbrella stand.
Should Sunshine Corp accept that offer?
Solution:
Own costs: $29 (material) + 2 min/B x 5 $/min = $39
First (wrong) answer:
No, why should we buy the 500 stands for $39.50 when we can produce it for only $39 per piece?
We would loose in that way 500 x $0,50 = $250.
Second (correct) answer:
We save time in the Casting department (because we do not have to produce 500 umbrella stands of
type Bernie) and can use that time as follows.
• How many minutes do we save? 500 umbrella stands of type Bernie x 2 minutes = 1.000 minutes.
• Now look at the final Simplex tableau: 1.000 more minute in the Casting department would change
the production program (250 umbrellas of type E less, 500 umbrellas of type C more) and the profit
(-250 E x $16/E + 500 C x $10/C = +$1.000).
In total, we enhance the profit through Outsourcing by +$1.000 – $250 = +$750.
Outsourcing can enhance the profit without negative impact on the utilization/workload of the
bottlenecks. We just use the saved time in another (more effcient) way.
O. Braun
74Linear Programming
Outsourcing
C L M
A 12.000 *5=60.000 *4=48.000 *2=24.000
B 1.500/2.000 1.500*2=3.000 2.000*3=6.000 2.000*5=10.000
C +500 6.000 *3=18.000 *2=12.000 *2=12.000
E -250 7.500 *2=15.000 *4=30.000 *4=30.000
96.000 96.000 76.000
Note that there is no change in the (still) fully used bottleneck production ressources (casting, liquering, mounting).
Foliennummer 1
Introduction
Outline
Problem 1
Problem 1: Linear Program
Problem 1: Graphical Solution
Problem 1
Problem 1
Problem 1
Problem 1
Problem 1
Problem 1
Simplex algorithm
Slack variables
Interpretation of the Tables
Performing a Simplex step
Pivot-Column
Pivot-Row
Pivot-Element
Simplex algorithm
Simplex algorithm
Simplex algorithm
Simplex algorithm
Simplex algorithm
Simplex algorithm
Simplex algorithm
Simplex algorithm
Simplex algorithm
Simplex algorithm
Shadow Prices
Simplex algorithm
Simplex algorithm
Simplex algorithm
Simplex algorithm
Simplex algorithm
Problem 2
Solution
Solution
Solution
Solution
Solution
Solution
Solution
Solution
Solution
Simplex algorithm
Solution
Simplex algorithm
Case Study
Case Study
Case Study
Mathematical program
Optimal Simplex Table
Interpretation of the optimal Simplex tableau
Important Data
Interpretation of the optimal Simplex tableau
Interpretation of the optimal Simplex tableau
Interpretation of the optimal Simplex tableau
Interpretation of the optimal Simplex tableau
Interpretation of the optimal Simplex table
Lower bound for the price of additional Arturo umbrellas
What if the company MUST produce Donald umbrellas?
Lower bound for the price of one Donald umbrella
Lower bound for the price of additional Caesar umbrellas
Lower bound for the price of additional Caesar umbrellas
Interpretation of the optimal Simplex tableau
Important Data
Arturo umbrellas
Casting department
Liquering department
Mounting department
Interpretation of the optimal Simplex tableau
Outsourcing
Outsourcing