Top Brass Trophy problem (Ex. 5.1 in Rardin'98)

Top Brass Trophy Company makes large championship trophies for youth athletic leagues. At the moment, they are planning production for fall sports: football and soccer. Each football trophy has a wood base, an engraved plaque, a large brass football on top, and returns \$12 in profit. Soccer trophies are similar except that a brass soccer ball is on top, and the unit profit is only \$9. Since the football has an asymmetric shape, its base requires 4 board feet of wood; the soccer base requires only 2 board feet. At the moment there are 1000 brass footballs in stock, 1500 soccer balls, 1750 plaques, and 4800 board feet of wood. What trophies should be produced from these supplies to maximize total profit assuming that all that are made can be sold?

Minimal solution

In [8]:
using JuMP, Clp

m = Model(solver=ClpSolver())
@variable(m, f >= 0)                        # football trophies
@variable(m, s >= 0)                        # soccer trophies
@constraint(m, Cwood,   4f + 2s <= 4800)    # total board feet of wood
@constraint(m, Cplaques,  f + s <= 1750)    # total number of plaques
@constraint(m, Cfballs,       f <= 1000)    # total number of brass footballs
@constraint(m, Csballs,       s <= 1500)    # total number of brass soccer balls
@objective(m, Max, 12f + 9s)                # maximize profit

status = solve(m)

display(m)

println(status)
println("Build ", getvalue(f), " football trophies.")
println("Build ", getvalue(s), " soccer trophies.")
println("Total profit will be \$", getobjectivevalue(m))
$$ \begin{alignat*}{1}\max\quad & 12 f + 9 s\\ \text{Subject to} \quad & 4 f + 2 s \leq 4800\\ & f + s \leq 1750\\ & f \leq 1000\\ & s \leq 1500\\ & f \geq 0\\ & s \geq 0\\ \end{alignat*} $$
Optimal
Build 650.0 football trophies.
Build 1100.0 soccer trophies.
Total profit will be $17700.0

Dual variables

In [2]:
println("Dual variable for wood: ", getdual(Cwood))
println("Dual variable for plaques: ", getdual(Cplaques))
println("Dual variable for brass footballs: ", getdual(Cfballs))
println("Dual variable for brass soccer balls: ", getdual(Csballs))
Dual variable for wood: 1.5
Dual variable for plaques: 6.0
Dual variable for brass footballs: -0.0
Dual variable for brass soccer balls: -0.0

Dual problem

In [7]:
using JuMP, Clp

m = Model(solver=ClpSolver())
@variable(m, λ[1:4] >= 0)
@constraint(m, 4λ[1] + λ[2] + λ[3] >= 12)
@constraint(m, 2λ[1] + λ[2] + λ[4] >= 9)
@objective(m, Min, 4800λ[1] + 1750λ[2] + 1000λ[3] + 1500λ[4])

status = solve(m)

display(m)

println(status)
println("dual variables are: ", getvalue(λ))
println("Optimal objective is: ", getobjectivevalue(m))
$$ \begin{alignat*}{1}\min\quad & 4800 λ_{1} + 1750 λ_{2} + 1000 λ_{3} + 1500 λ_{4}\\ \text{Subject to} \quad & 4 λ_{1} + λ_{2} + λ_{3} \geq 12\\ & 2 λ_{1} + λ_{2} + λ_{4} \geq 9\\ & λ_{i} \geq 0 \quad\forall i \in \{1,2,3,4\}\\ \end{alignat*} $$
Optimal
dual variables are: [1.5, 6.0, 0.0, 0.0]
Optimal objective is: 17700.0
In [ ]: