The chilling adventures of Sabrina¶

Problem definition¶

Spellman´s Ltd is a company that manufactures chilling soft drinks. They want to manufacture two types of drinks A, and B. Both beverages use a semi-elaborate C, another expensive ingredient D and other ingredients that are not relevant for production planning. Sabrina is a young student of engineering and management doing an internship at Spellman´s. She needs to formulate a Continuous Linear Program to configure the optimal daily production plan for the company.

The selling price of drink A is 3€/liter and the selling price of drink B is 2€/liter.

1 liter of drink A uses 3 grams of ingredient D. A liter of drink B uses 1 gram of ingredient D. There are only 3 grams of ingredient D available per day.

The factory only has one mixer to elaborate both drink types and the semi-elaborate. It takes 1 hour to process a liter of drink A, 1 hour to process 1 liter of drink B, and 1 hour to process 1cl of semi-elaborate C. The mixer is available 6 hours per day.

Drink A uses 2cl of semi-elaborate C and drink B uses 1cl of semi-elaborate C. The company has 3cl of semi-elaborate C plus the amount they decide to produce available per day.

1. Write a Continuous Linear Problem to help Sabrina design the optimal production plan that maximises revenues for the company.

Decision variables:

$x_A$: Production of drink A in liters
$x_B$: Production of drink B in liters
$x_C$: Production of semi-elaborate C in centiliters

$x_A, x_C, x_B \in \mathbb{R}$

Objective function

$\max z = 3*x_A + 2*x_B$

z is the profit in euros.

Constraints s.t.

Availability of ingredient D in grams:

$3*x_A + x_B \leq 3$

Availability of mixer in hours:

$x_A + x_B + x_C \leq 6$

Availability of semi-elaborate C in centiliters:

$2*x_A + x_B -x_C \leq 3$

Logical constraint

$ x_A, x_C, x_B :nbsphinx-math:`geq 0`$

2. Write the dual problem The dual is:

$\min z = 3*u_1 + 6*u_2 + 3*u_3$

s.t.

$3*u_1 + u_2 + 2*u_3 \geq 3$

$u_1 + u_2 + u_3 \geq 2$

$u_2 - u_3 \geq 0$

3. Given the following solution:

0 Liters of drink A
3 Liters of drink B
3 cl of semi-elaborate C

Verify the solution. Is the solution feasible? What are the values of the slack variables?

We plug in the values of the solution in our constraints:

Availability of ingredient D in grams:

$3*x_A + x_B \leq 3$

$3*0 + 3 \leq 3$

$3 + s_1 = 3$

$s_1 = 0$

Availability of mixer in hours:

$x_A + x_B + x_C \leq 6$

$0 + 3 + 3 \leq 6$

$6 + s_2 = 6$

$s_2 = 0$

Availability of semi-elaborate C in centiliters:

$2*x_A + x_B -x_C \leq 3$

$2*0 + 3 - 3 \leq 3$

$0 + s_3 = 3$

$s_3 = 3$

Logical constraint

$ s_1, s_2, s_3 :nbsphinx-math:`geq 0`$

The solution is feasible because it meets all constraints and slack variables are non-negative.

4. Use complementary slackness to find the dual solution corresponding to this vertex. Is the dual solution feasible? Is the solution optimal? Motivate your response.

By complementary slackness, since $s_3=3$, we know that $u_3 = 0$, and also, since $x_C$ is greater than zero, we know that the third constraint of the dual is binding. By plugging this information into the third constraint we obtain:

$u_2 - u_3 = 0$

$u_2 = 0$

We can plug this value into the second constraint of the dual, which is also binding since $x_B$ is non-zero, to obtain:

$u_1 + u_2 + u_3 = 2$

$u_1 = 2$

All values are non-negative, so the solution is feasible and since both primal and dual are feasible, the solution is optimal.

Gurobi provides the following solution:

Optimal

Total profit is 6.00 €

The following table shows the decision variables:

j	Variables	Solution (GRB)	Reduced cost (GRB)	Objective Coefficient (GRB)	Objective Lower bound (GRB)	Objective Upper bound (GRB)
A	units_A	0	-3	3	-inf	6
B	units_B	3	0	2	1	inf
C	units_C	3	0	0	-0	1.5

The following table shows the constraints:

j	Constraint	Slack	Shadow Price	Right Hand Side	Min RHS	Max RHS
0	Availability_of_ingredient_A	0	2	3	0	4.5
1	Availability_of_mixer_hours	0	0	6	3	inf
2	Availability_of_semi_elaborate	3	0	3	0	inf