Oliver Braun
CSE 101 (Summer Session 2021)
Homework 6: Linear Programming
Instructions
Homework questions will be similar to your future exam questions. The homework will not be graded,
however, you are highly recommended to practice using these questions for better preparations of the
exams.
Key Concepts Modeling problems, linear programming models, graphical solution, feasible solutions,
Simplex algorithm, Gaussian elimination, shadow prices, interpreting the final simplex tableau.
Linear programming describes a broad class of optimization problems in which both the optimization goal
and the constraints are linear functions. Linear programming has extraordinary impact since the 1950’s.
It is a standard tool that has saved millions of dollars for many companies [Hillier/Lieberman, pp. 25–
26]. 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
We consider only one optimization goal for each problem. In order to keep things simple, it will always
be a maximization goal. In the real world there are obviously often more than one optimization goal that
have to be fulfilled as good as possible at the same time. As an example, in logistics, one often wants
to minimize the costs and time needed to transport goods and maximize the quality. In these cases one
often sets hard constraints on some goals and optimizes the remaining goal under these constraints.
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. The simplex algorithm is nice, but more important is the interpretation of the final
simplex tableau. You will see that with the help of this final tableau a company can answer such questions
as:
� How does the production program and the profit change if we would have one more unit (e.g.
minute) of a certain resource?
� Given an optimal production program. Imagine you can, want to, or have to produce one more unit
of a certain product. What would be the lower bounds on the price for that additional product?
� One production step can be outsourced. What is the lower bound on the price you can pay for
that outsourcing?
Consider this section as a first step into the world of combining computer science, math, and business
tools that you might want or have to apply when you will work for a company in the real-world. You
will moreover refine your skills to model and solve problems. Have fun. With the following questions
you can practice the following:
(a) Formulate a linear program,
(b) solve the problem graphically,
1
(c) solve the problem with the simplex algorithm,
(d) give an interpretation of the shadow prices.
In a case study that is about the optimal production program for umbrella production, you will see why
the simplex algorithm is so interesting for companies. We are going to answer the following questions:
� How does the production program and the profit change, if the company could get access to more
resources (Casting, Liquering, Mounting Department)?
� How does the production program and the profit change, if the company could / wants / has to
produce more umbrellas of a certain type?
� What will be the maximum gain in profit that can be achieved by using more resources or producing
more umbrellas?
� What is the lower bound on the price the company can pay for outsourcing certain production
steps (like casting step)?
The question if the company would change the production coefficients (e.g. speedup in the casting
department) can be answered by playing with the coefficients in a Simplex solver, e.g. in Excel.
Sources: [1] Hillier, Frederick S. / Lieberman, Gerald J. (2015), Introduction to Operations Research,
10th ed., McGrawHill. We recommend to read Chapters 3 and 4 for an introduction to linear programming
with a lot of examples, additional problems and real-world applications.
2
Problem 1. A company produces two products, A and B, out of the three raw materials R1, R2, R3. The raw
material requirements of both products (to produce one unit) and the (for both products together)
totally available raw material quantities can be found in the following table.
A B available quantities
R1 0.2 1.0 13
R2 1.0 0.1 16
R3 0.0 1.0 12
The profit is $1 for every unit of product A and $1 for every unit of product B. At least 2 units of
product A have to be produced. How many units do both companies need to produce to maximize
the profit? Formulate a linear programming model for this problem (ignore integral constraints).
Solution:
x1 = Number of units of A
x2 = Number of units of B
max x1 + x2
subject to 0.2 x1 + x2 ≤ 13 (1)
x1 + 0.1 x2 ≤ 16 (2)
x2 ≤ 12 (3)
x1 ≥ 2 (4)
x1, x2 ≥ 0
3
Problem 2. [Hillier/Lieberman, Problem 3.2.3, p. 83] This is your lucky day. You have just won a $20 000 prize.
You are setting aside $8 000 for taxes and partying expenses, but you have decided to invest the
other $12 000. Upon hearing this news, two different friends have offered you an opportunity to
become a partner in two different entrepreneurial ventures, one planned by each friend. In both
cases, this investment would involve expending some of your time next summer as well as putting
up cash.
Becoming a full partner in the first friend’s venture would require an investment of $10 000 and
400 hours, and your estimated profit (ignoring the value of your time) would be $9 000. The
corresponding figures for the second friend’s venture are $8 000 and 500 hours, and your estimated
profit is $9 000.
However, both friends are flexible and would allow you to come in at any fraction of a full partner-
ship you would like. If you choose a fraction of a full partnership, all the above figures given for a
full partnership (money investment, time investment, and your profit) would be multiplied by this
same fraction.
Because you were looking for an interesting summer job anyway (maximum of 600 hours), you have
decided to participate in one or both friend’s ventures in whichever combination would maximize
your total estimated profit. You need to solve the problem of finding the best combination.
(a) Formulate a linear programming model for this problem.
(b) Solve the problem graphically.
Solution:
(a) x1 = Percentage of a full partnership in your first friend’s venture
x2 = Percentage of a full partnership in your second friend’s venture
max 9 000 x1+9 000 x2
subject to 10 000 x1+8 000 x2 ≤ 12 000 (1)
400 x1+ 500 x2 ≤ 600 (2)
x1 ≤ 1 (3)
x2 ≤ 1 (4)
x1, x2 ≥ 0
(b) (1)x2 ≤ 32 −
5
4
x1 (money)
(2)x2 ≤ 65 −
4
5
x1 (time)
4
x
y
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
1.1
1.2
1.3
1.4
1.5
Corners Estimated profit
(0, 0) 0
(1, 0) 9 000(
1, 1
4
)
11 250(
2
3
, 2
3
)
12 000(
1
4
, 1
)
11 250
(0, 1) 9 000
Maximum in (x1, x2) =
(
2
3
, 2
3
)
.
Estimated profit:
2
3
· 9 000 + 2
3
· 9 000 = 12 000.
5
Problem 3. Given the following linear program:
max 2×1 + 3×2
s.t.
2 11 1
1 3
[x1
x2
]
≤
200120
240
x1, x2 ≥ 0
Are the following values Qi =
[
x1
x2
]
, i = 1, . . . , 4 for x1 and x2 feasible solutions of the linear
programming problem?
(a) Q1 =
[
60
60
]
(b) Q2 =
[
60
80
]
(c) Q3 =
[
80
40
]
(d) Q4 =
[
50
50
]
Solution:
(a)
2 11 1
1 3
[60
60
]
=
180120
240
≤
200120
240
=⇒ Q1 is a feasible solution.
(b)
2 11 1
1 3
[60
80
]
=
200140
300
6≤
200120
240
=⇒ Q2 is NOT a feasible solution.
(c)
2 11 1
1 3
[80
40
]
=
200120
200
≤
200120
240
=⇒ Q3 is a feasible solution.
(d)
2 11 1
1 3
[50
50
]
=
150100
200
≤
200120
240
=⇒ Q4 is a feasible solution.
6
Problem 4. Which of the following statements are correct?
(a) The idea of the simplex method is to traverse the corners of the feasible region.
(b) The simplex method terminates in a corner.
(c) The simplex method can provide a wrong solution.
(d) For a maximization problem, we know we have reached the optimal solution when the last
row has no nonzero numbers in it.
Solution: (a) right, (b) right, (c) wrong, (d) wrong (. . . has no negative numbers in it)
7
Problem 5. Solve the following linear equation system using Gaussian elimination:
x1 + 2×2 +2×3 = 3
2×1 + 3×2 +1×3 = 7
3×1 − 2×2 + x3 = −2
Solution:
1 2 2 32 3 1 7
3 −2 1 −2
1 2 2 30 −1 −3 1
0 −8 −5 −11
1 2 2 30 1 3 −1
0 0 19 −19
1 2 2 30 1 3 −1
0 0 1 −1
x1 + 2×2 + 2×3 = 3 =⇒ x1 + 4− 2 = 3 =⇒ x1 = 1
x2 + 3×3 = −1 =⇒ x2 − 3 = −1 =⇒ x2 = 2
x3 = −1
8
Problem 6. 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: If there would be one more hour available in the
varnishing department, how would the production program and the profit change? If there
would be one more hour available in the assembling department, how would the production
program and the profit change? Prove that the total usage of the other (fully used) resource
(here: total number of hours in the varnishing or assembling department) remains unchanged
in both cases.
Solution: Please see lecture slides and videos.
9
Problem 7. A company manufactures two products A and B. The company earns $3 for each piece of A and
$2 for each piece of B. Raw materials V1 and V2 are necessary to build these products. But there
are only 8 parts of V1 and 6 parts of V2 available. To manufacture single piece of product A, 2
parts of V1 and 1 part of V2 is required. To manufacture single piece of product B, 1 part of V1
and 1 part of V2 is required.
How many pieces of A and B does the company have to manufacture when the objective function
is to maximize the profit?
(a) Formulate the mathematical program.
(b) Solve the problem graphically.
(c) Solve the problem with the Simplex algorithm.
(d) Give an interpretation of the shadow prices: If the company could have access to one more
piece of V1, how would the production program and the profit change? If the company could
have access to one more piece of V2, how would the production program and the profit change?
Prove that the total usage of the other (fully used) resource (here: pieces of P or Q) remains
unchanged in both cases.
Solution: Please see lecture slides and videos.
10
Problem 8. A fertilizer factory manufactures two types of fertilizer, A and B, from three raw materials C, D
and E. There are 1 500 tons of raw material C, 1 200 tons of raw material D, and 500 tons of raw
material E available. For the production of one ton of A, there are 2 tons C, and 1 ton of each, D
and E, needed. 1 ton of C and 1 ton of D is needed for the production of 1 ton of B. The profit
for A is $30 per ton, and the profit for B is $20 per ton.
(a) Formulate a linear programming model for this problem. Use x = amount of fertilizer A (in
tons) and y = amount of fertilizer B (in tons).
(b) Use the graphical method to solve this model.
(c) Solve the optimization problem using the simplex algorithm.
(d) Interpret the final tableau: profit, optimal production program, utilization of the resources.
Solution:
(a) x = amount of fertilizer A (in tons)
y = amount of fertilizer B (in tons)
max 30 x+20 y
subject to 2 x+ y ≤ 1 500 (1)raw material C
x+ y ≤ 1 200 (2)raw material D
x ≤ 500 (3)raw material E
x, y ≥ 0 (4)non-negativity
(b) Use the graphical method to solve this model.
y
x300 500 750 1200
900
1200
1500
11
(c) Solve the optimization problem using the simplex algorithm.
1. x y s1 s2 s3
s1 2 1 1 0 0 1 500
s2 1 1 0 1 0 1 200
s3 1 0 0 0 1 500
z −30 −20 0 0 0 0
2. x y s1 s2 s3
s1 0 1 1 0 −2 500
s2 0 1 0 1 −1 700
x 1 0 0 0 1 500
z 0 −20 0 0 30 15 000
3. x y s1 s2 s3
y 0 1 1 0 −2 500
s2 0 0 −1 1 1 200
x 1 0 0 0 1 500
z 0 0 20 0 −10 25 000
4. x y s1 s2 s3
y 0 1 −1 2 0 900
s3 0 0 −1 1 1 200
x 1 0 1 −1 0 300
z 0 0 10 10 0 27 000
(d) Profit:$27 000, optimal production program: x = 300, y = 900. s3 = 200 means that there are
200 tons of raw material E left (constraint (3) is x ≤ 500, but only x = 300 tons for A are
used). Production linkage:
C (1 500) D (1 200) E (500)
A(300) B(900)
600
900
300 900
300
12
Problem 9. In a factory there are three machines needed for the production of two different products. Each of
the two products requires different processing times (in minutes) on the machines according to the
following table:
machine 1 machine 2 machine 3
product A 40 24 0
product B 24 48 60
In addition, it is logistically impossible to produce more than 6 units of product A. The daily
machine running time is 8 hours. The profit for product A is $10 per unit and for product B it is
$40 per unit.
(a) Formulate a linear programming model for this problem.
(b) Look at the final simplex tableau of a slightly different problem (without the last constraint):
x y s1 s2 s3
s1 0 0 1 − 4024
56
60
128
x 0 1 0 1
24
− 1
30
4
y 1 0 0 0, 1
60
8
0 0 0 10
24
1
3
360
The machine runtime of machine 1 (s1) is increased from 480 minutes to 580 minutes. How
do the production program and the profit change?
Solution:
(a) x1: amount of product A
x2: amount of product B
max 10×1 + 40×2
subject to
40×1 + 24×2 ≤ 480
24×1 + 48×2 ≤ 480
60×2 ≤ 480
x1 ≤ 6
x1, x2 ≥ 0
(b) Machine 1 is not used until its full capacity of 480 minutes. The slack is 128 minutes and
therefore it is only used for 352 minutes. The extra capacity does not change the production
program.
13
Problem 10. Given the following final simplex tableau. There are two products (variables x1, x2 with profits of
$3 and $5 per unit) and three resource constraints (s1, s2 and s3).
BV x1 x2 s1 s2 s3
1. ? 0 0 1 1
3
− 1
3
2
2. ? 0 1 0 1
2
0 6
3. ? 1 0 0 − 1
3
1
3
2
0 0 0 3
2
1 36
(a) Complete the column BV with the base variables.
(b) Interpret the tableau: profit, optimal production program, utilization of the resources.
(c) How would the production program and the profit change if the capacity of resource 2 would
be increased by 3 units?
Solution:
(a) The base variables are 1.s1, 2.×2, 3.×1.
(b) profit: $36, production program: 2 units of product 1, 6 units of product 2. Resources 2 and
3 are used to full capacity (because s2, s3 are not in the base and therefore = 0), resource 1
has a remaining capacity of 2 units.
(c) If the capacity of resource 2 would be increased by 1 unit, we would produce 1/2 more units
of product 2 and 1/3 less units of product 1. The profit would increase by $1.50 (shadow price
3/2). Therefore, the production program would change to 6 + 3 · 1/2 = 7.5 units of product
2 and 2− 3 · 1/3 = 1 unit of product 1 with a total profit of 36 + 3 · 3/2 = $40.50.
14
Problem 11. 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 aluminum 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 umbrella) 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.
(a) Formulate the mathematical program.
(b) Solve the problem with the simplex algorithm.
(c) More resources.
i. If the company could have 1 more minute in the Casting department: How would the
production program and the profit change?
ii. If the company could have 1 more minute in the Liquering department: How would the
production program and the profit change?
iii. If the company could have 1 more minute in the Mounting department: How would the
production program and the profit change?
(d) More umbrellas.
i. 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? What is the lower bound for the price of one Arturo for these additional
orders?
ii. If the company would have to produce 1 more piece of the Donald umbrellas: How would
the production program and the profit change? What is the lower bound for the price of
one Donald umbrella?
iii. 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)?
(e) Maximum gain in profit.
i. What is the maximum total gain in profit for producing more Arturo umbrellas?
ii. What is the maximum total gain in profit for more minutes in the Casting department?
iii. What is the maximum total gain in profit for more minutes in the Liquering department?
iv. What is the maximum total gain in profit for more minutes in the Mounting department?
(f) 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: Please see lecture slides and videos.
15
Problem 12. A company manufactures four different models A, B, C, D of wooden doors. Each door passes
through three production areas: The delivered wood is sawn in the sawmill (S) painted in the
paint shop (P) and then assembled in the mounting department (M). Fix costs in the distribution
department are $20 000. The company management causes costs of $30 000. The following data
for the different door models are given:
door model A B C D
revenue per unit (in $) 95 124 133 142
material costs (in $ per door)
– sawmill 30 35 35 35
– paint shop 15 20 20 30
– mounting 10 10 15 15
maximum sales quantity(in pieces) 2 000 6 000 4 000 8 000
selling expenses (in $ per unit) 2 3 3 5
The following data for the different resource constraints (sawmill S, paint shop P, mounting de-
partment M) are given:
departments S P M
fix costs (in $) 20 000 20 000 10 000
costs (in $) per production minute 5 3 3
capacity (in minutes) 44 000 60 000 34 000
production time (in minutes/piece)
A 3 5 1
B 3 5 2
C 4 5 3
D 4 5 4
(a) Formulate a linear programming model for this problem (without integrality constraints).
(b) Give an interpretation of the final simplex tableau in terms of profit, optimal production
program, slack variables.
xA xB xC xD sS sP sM sA sB sC sD
sA 1 0 0 0 0 0 0 1 0 0 0 2 000
xB 0 1 0 0 0 0 0 0 1 0 0 6 000
xC 0 0 1 0 0 0 0 0 0 1 0 4 000
xD 1 0 0 1 0 1/5 0 0 −1 −1 0 2 000
sD −1 0 0 0 0 −1/5 0 0 1 1 1 6 000
sS −1 0 0 0 1 −4/5 0 0 1 0 0 2 000
sM −3 0 0 0 0 −4/5 1 0 2 1 0 2 000
5 0 0 0 0 2 0 0 10 6 0 104 000
(c) How would the production program and the profit change,
i. if the capacity of the sawmill would be increased by 100 minutes,
ii. if the paint shop capacity would be increased by 2 000 minutes,
iii. if the capacity of the mounting department would be increased by 1 000 minutes,
iv. if the maximum sales quantity of C would be 10 000?
Show that the other capacity restrictions of the resources that are used up to their full capacity
remain unchanged in every of the above cases.
(d) Determine the lower bounds for the price of an additional model of door types A,B,C,D.
(e) The company gets an offer to buy 500 sawn and painted, but unmounted doors for model D
for the price of $40 000. Should the offer be accepted?
Solution:
(a) Contribution margins:
Linear program: xA, xB , xC , xD = pieces of model A,B,C,D.
16
door model A B C D
revenue per unit 95 124 133 142
material costs per unit
sawmill 30 35 35 35
paint shop 15 20 20 30
mounting 10 10 15 15
production costs per unit
sawmill 15 15 20 20
paint shop 15 15 15 15
mounting 3 6 9 12
selling expenses 2 3 3 5
contribution margins 5 20 16 10
max 5xA + 20xB + 16xC + 10xD − 100 000
s.t.
3xA + 3xB + 4xC + 4xD ≤ 44 000 (capacity sawmill)
5xA + 5xB + 5xC + 5xD ≤ 60 000 (capacity paint shop)
xA + 2xB + 3xC + 4xD ≤ 34 000 (capacity mounting)
xA ≤ 2 000 (maximum sales A)
xB ≤ 6 000 (maximum sales B)
xC ≤ 4 000 (maximum sales C)
xD ≤ 8 000 (maximum sales D)
xA, xB , xC , xD ≥ 0 (non-negativity constraint)
(b) Interpretation of the final simplex tableau.
xA xB xC xD sS sP sM sA sB sC sD
sA 1 0 0 0 0 0 0 1 0 0 0 2 000
xB 0 1 0 0 0 0 0 0 1 0 0 6 000
xC 0 0 1 0 0 0 0 0 0 1 0 4 000
xD 1 0 0 1 0 1/5 0 0 −1 −1 0 2 000
sD −1 0 0 0 0 −1/5 0 0 1 1 1 6 000
sS −1 0 0 0 1 −4/5 0 0 1 0 0 2 000
sM −3 0 0 0 0 −4/5 1 0 2 1 0 2 000
5 0 0 0 0 2 0 0 10 6 0 104 000
Relevant data are:
xA sB sC sP
xB 0 1 0 0 6 000
xC 0 0 1 0 4 000
xD 1 −1 −1 1/5 2 000
sA 1 0 0 0 2 000
sD −1 1 1 −1/5 6 000
sS −1 1 0 −4/5 2 000
sM −3 2 1 −4/5 2 000
5 10 6 2 104 000
Total profit is 104 000.
Production program: 0 doors (out of possible 2 000 doors) of model A, 6 000 doors (out of
possible 6 000 doors) of model B, 4 000 doors (out of possible 4 000 doors) of model C, 2 000
doors (out of possible 8 000 doors) of model D .
Variables xA, sB , sC , sP are NOT in the base ans therefore = 0.
Slack variables: Unused capacity on sales of A (sA): 2 000 doors. Unused capacity on sales of
B (sB): 0 doors. Unused capacity on sales of C (sC): 0 doors. Unused capacity on sales of
D (sD): 6 000 doors. Unused capacity in the sawmill (sS): 2 000 minutes. Unused capacity
in the paint shop (sP ): 0 minutes. Unused capacity in the mounting department (sM ): 2 000
minutes.
(c) Interpretation of the shadow prices.
i. The capacity of the sawmill could be increased by 100 minutes. Since sS = 2 000, there
are 2 000 minutes left in the sawmill in the optimal production program. That means
17
that neither the profit nor the numbers of produced doors would change when we would
further increase the capacity of the sawmill.
ii. The paint shop capacity is increased by 2 000 minutes. sP is not in the base and therefore
sP = 0: all of the available 60 000 minutes in the paint shop are used in the optimal
production program. Therefore, we can increase the profit when we have more minutes
in the paint shop. The production program would change as follows: We would increase
the number of doors of type D by 2 000 · 1/5 = 400 (the number of produced doors of
type A, B and C remain unchanged). The profit would increase by $2 000 · 2 = $4 000
(which makes sense, because we the contribution margin for D-doors is $10 per door).
Note that not only the capacity in the paint shop would change by producing more doors
of type D. We would also have a change in the sawmill and in the mounting department
(+4/5 · 2 000 = 1 600 minutes in each department). This makes again sense since we need
4 minutes for each D-door in the sawmill and in the mounting department.
iii. The capacity of the mounting could be increased by 1 000 minutes. Again, nothing changes
in the production program since there are sM = 2 000 minutes left in the mounting
department in the optimal production program.
iv. The maximum sales quantity of C-doors could be increased from 4 000 doors up to 10 000
doors. As sC is not in the base and therefore sC = 0, we could increase the profit when we
increase the number of doors of type C that can be sold. From the final simplex tableau we
see that with each C-door that we would produce more, we would produce one less D-door
and use one less minute (!) in the mounting department. As we currently produce only
2 000 D-doors, we could therefore produce only 2 000 more C-doors in order to remain
feasible. Therefore the new production program would be: xA = 0, xB = 6 000, xC =
6 000, xD = 0. The profit would increase by $2.000 · 6 = $12 000. Note that the usage
of the sawmill and paint shop remains the same, and that we even save 2 000 minutes in
the mounting department. Sawmill: 6 000 · 3 + 6 000 · 4 = 42 000 minutes. Paint shop:
6 000 · 5 + 6 000 · 5 = 60 000 minutes. Mounting department: 6 000 · 2 + 6 000 · 3 = 30 000
minutes.
(d) i. Model A (in the optimal program) is not produced: list price + shadow price = $95+$5 =
$100.
ii. Model B (in the optimal program) is already produced up to the maximum sales possi-
bility. The total profit for each additional door increases by $10. For an additional order
could thus be reduced by at most $10 per door. The minimum price per door should
therefore be $124− $10 = $114.
iii. Model C (in the optimal program) is already produced up to the maximum sales possi-
bility, therefore we have again $133− $6 = $127.
iv. Model D (in the optimal program) is produced, but not until its capacity limit, therefore
we have:
list price + min
{
shadow price
coefficient in structure variable row
}
(Consider only negative values in the xD-row)
142 + min
{
10
1
; 6
1
}
= 142 + 6 = $148
(e) Outsourcing (500 sawn and painted D-doors for $40 000).
Material and production costs for 500 sawn and painted D-doors:
sawmill paint shop
material costs per door $30 $15
production costs per door $5 · 3 = $15 $3 · 5 = $15
−→ 500 · ($30 + 15 + 15 + 15) = $37 500.
Opportunity costs (Time savings per door):
sawmill paint shop
time saving per door 3 minutes 5 minutes
We would save 3 minutes per door in the sawmill which gives 3 · 500 = 1 500 minutes for 500
doors. We would save 5 minutes per door in the paint shop which gives 5 ·500 = 2 500 minutes
for 500 doors.
Because (in the optimal production program) we even have 2 000 minutes left in the sawmill,
extra minutes wouldn’t change the production program and the profit and we would therefore
not have any opportunity costs.
18
The situation is different in the paint shop: Here we could invest the saved time, change
the production program and gain more profit. If we would outsource 500 doors of type D
so that the sawmill and the paint shop would get some additional capacity we would have
the following situation: Per additional minute in the paint shop we would produce 1/5 more
D-doors and the profit would increase by $2. Therefore: Per additional 2 500 minutes in the
paint shop we would produce 500 more D-doors, and the profit would increase by $5, 000.
Therefore we could pay up to $37 500 + $5 000 = $42 500 for the outsourced D-doors. Because
we would only have to pay $40 000 for the 500 outsourced D-doors, the profit will therefore
increase by $2 500 and the offer could be accepted.
sawmill paint shop mounting
xA = 0 0 0 0
xB = 6 000 18 000 30 000 12 000
xC = 4 000 16 000 20 000 12 000
xD = 2 500 10 000
x1D = 2 000 8 000 10 000
x2D = 500 − −
42 000 60 000 34 000
19