With precisely 2700 sq. cm. of cardboard, you wish to construct a box (width: \(x\), depth: \(y\), height: \(z\)) containing a volume \(V\). You require the width to double its depth. You would like to maximise the volume of the box. Which values of \(x, y, z\) will maximise the volume?
From this, KKT’s dual feasibility and complementary slackness conditions are satisfied, so we can proceed to the stationarity and primal feasibility conditions.
KKT’s stationarity
Solve for partial derivatives and set them equal to 0:
import sympy as sp# Variablesx, y, z = sp.symbols("x y z", positive=True)lambda1, lambda2 = sp.symbols("lambda1 lambda2")# Objective and constraintsV = x * y * zg1 =2* (x*y + x*z + y*z) -2700g2 = x -2*y# LagrangianL = V - lambda1 * g1 - lambda2 * g2# First-order conditionsequations = [ sp.diff(L, x), sp.diff(L, y), sp.diff(L, z), g1, g2,]solution = sp.solve( equations, [x, y, z, lambda1, lambda2],dict=True)print("Solutions:")for sol in solution:print(sol)# Keep positive real solutionpositive_solutions = [ sol for sol in solutionif sol[x].is_real and sol[y].is_real and sol[z].is_realand sol[x] >0and sol[y] >0and sol[z] >0]best =max(positive_solutions, key=lambda sol: V.subs(sol))print("\nOptimal dimensions:")print(f"x = {sp.simplify(best[x])} = {float(best[x]):.4f} cm")print(f"y = {sp.simplify(best[y])} = {float(best[y]):.4f} cm")print(f"z = {sp.simplify(best[z])} = {float(best[z]):.4f} cm")print("\nMaximum volume:")print(f"V = {sp.simplify(V.subs(best))} = {float(V.subs(best)):.4f} cubic cm")
Solutions:
{lambda1: 5, lambda2: -50, x: 30, y: 15, z: 20}
Optimal dimensions:
x = 30 = 30.0000 cm
y = 15 = 15.0000 cm
z = 20 = 20.0000 cm
Maximum volume:
V = 9000 = 9000.0000 cubic cm
Question 2
A manufacturing facility produces four types of wood panelling: Tahoe, Pacific, Savannah, and Aspen. Each product is manufactured using pine chips and oak chips and requires both gluing and pressing processes.
The profit earned per pallet is as follows:
$450 for Tahoe,
$1140 for Pacific,
$800 for Savannah, and
$400 for Aspen.
The factory operates under limited resource availability. During the planning period, there are 5,800 quarts of glue available, 730 pressing machine hours, and 29,200 pounds of pine chips. In addition, the supply of oak chips is limited to a fixed total amount.
Tahoe
Pacific
Savannah
Aspen
Capacity
Glueing (quarts)
50
50
100
50
5800 quarts
Pressing (hours)
5
15
10
5
730 hours
Pine chips (pounds)
500
400
300
200
29200 pounds
Oak chips (pounds)
500
750
250
500
60500 pounds
Profit per pallet ($)
450
1150
800
400
-
Let decision variables be \(X_1,X_2,X_3,X_4\) (pallets of Tahoe, Pacific, Savannah, Aspen). Write down the optimisation model to maximise profit, and solve for the optimal production plan. What is the maximum profit?
This can be solved using KKT. However, it is usually not the preferred manual method for solving linear programming problems, especially with 4 variables. Instead, we can use the Simplex method or an LP solver.
Consider the problem of diet optimisation. There are four different types of food: Brownies, Ice Cream, Cola, and Cheese Cake. The nutrition values and cost per unit are as follows:
Brownies
Ice Cream
Cola
Cheese Cake
Calories
400
200
150
500
Chocolate
3
2
0
0
Sugar
2
2
4
4
Fat
2
4
1
5
Cost ($)
$0.50
$0.20
$0.30
$0.80
The objective is to minimise the cost of the diet while satisfying the following nutritional requirements:
At least 500 calories,
At least 6 units of chocolate,
At least 10 units of sugar, and
At least 8 units of fat.
Formulate the optimisation model and solve for the optimal diet plan.
TowAlong makes trailers at Kansas City, Denver, and Raleigh plants and ships these units to Birmingham, Milwaukee, Los Angeles, and Seattle distribution centres. In planning production for the next year, TowAlong estimates Kansas City, Denver, and Raleigh plant’s unit shipping cost between any plant and distribution centre, plant capacities, and distribution centre demands. These numbers are given in the table.
Plant/DC
Birmingham
Milwaukee
LA
Seattle
Capacity
Kansas City
$35
$40
$60
$120
12,000
Denver
$30
$30
$45
$130
8,000
Raleigh
$60
$65
$50
$100
5,000
Demand
9,000
3,000
9,500
1,500
-
Formulate the optimisation model to minimise the total shipping cost, and solve for the optimal shipping plan. What is the minimum total cost?
Sunchem, a manufacturer of printing inks, has five manufacturing plants worldwide. Their locations and capacities are shown in Table 4 along with the cost of producing 1 ton of ink at each facility. The production costs are in the local currency of the country where the plant is located. The major markets for the inks are North America, South America, Europe, Japan, and the rest of Asia. Demand at each market is shown in Table 4. Transportation costs from each plant to each market in U.S. dollars are shown in Table 4. Management must come up with a production plan for the next year.
If exchange rates are expected as in Table 2, and no plant can run below 50 percent of capacity, how much should each plant produce and which markets should each plant supply?
If there are no limits on the amount produced in a plant, how much should each plant produce?
Can adding 10 percent of capacity in any plant reduce costs?
How should Sunchem account for the fact that exchange rates fluctuate over time?
Table 1. Transportation costs, production capacity, and cost by region