Invincible Nutritional Supplements¶
Problem Definition¶
Invincible Ltd makes two types of nutritional supplements. The recip of both supplements is based on three ingredients for which the company has limited availability. The table below shows the daily availability of the three ingredients and their costs:
Table 1: daily availability and cost of ingredients
Ingredient |
Availability (grams) |
Cost (€cents/gram) |
|---|---|---|
1 |
1500 |
85 |
2 |
1300 |
90 |
3 |
2000 |
125 |
The selling prices are 3€/gram for supplement Awesome (product A) and 3.5€/gram for supplement Beast (product B).
The recip must comply with the following requirements:
Both products must contain at least 25% of ingredient 3.
Product B must have at least 10% more of ingredient 2 than product A.
The minimum quantity of any ingredient in any product is 10%
The factory has a production line that operates for 10 hours per day. The production speed of the line is 300 grams per hour for product A and 175 grams per hour for product B.
Indices¶
We can define the following indices to express the problem in a compact form:
i: Ingredient \(i \in [1, 2, 3]\)
j: Product \(j \in [A, B]\)
Decision variables¶
The decision variables are:
\(x_{ij}\): Amount of ingredient i (1, 2, 3) in product j (A, B) (ie i=[1,2,3], j=[A,B]) in grams
Objective Function¶
The objective function is:
\(\max z = \sum_{i=1}^{3}\sum_{j=A}^{B}(d_j - c_i)*x_{ij}\)
where \(d_j\) is the selling price of a gram of product j and \(c_i\) is the cost of ingredient i.
\(\max z=(3-0.85)*x_{1A}+(3-0.9)*x_{2A}+(3-1.25)*x_{3A})+(3.5-0.85)*x_{1B}+(3.5-0.9)*x_{2B}+(3.5-1.25)*x_{3B}\)
\(\max z=2.15*x_{1A}+2.1*x_{2A}+1.75*x_{3A}+2.65*x_{1B}+2.6*x_{2B}+2.25*x_{3B}\)
Constraints¶
Subject to the following constraints:
Availability constraints The availability constraints can be expressed in a compact form as:
\(\sum_jx_{ij} \leq a_i \quad \forall i\)
\(x_{1A}+x_{1B} \leq 1500\)
\(x_{2A}+x_{2B} \leq 1300\)
\(x_{3A}+x_{3B} \leq 2000\)
Both products must contain at least 25% of ingredient 3
\(x_{3A} \geq 0.25*(x_{1A}+x_{2A}+x_{3A})\)
\(x_{3B} \geq 0.25*(x_{1B}+x_{2B}+x_{3B})\)
Product B must have at least 10% more of ingredient 2 than product A:
\(x_{2B} \geq 1.1(x_{2A})\)
The minimum quantity of any ingredient in any product is 10%:
??
Production capacity constraint:
??
A solver provides the following tables with the solution of the primal and the dual:
Variables |
Solution (GRB) |
Reduced cost (GRB) |
Objective Coefficient (GRB) |
Objective Lower bound (GRB) |
Objective Upper bound (GRB) |
|---|---|---|---|---|---|
Grams of ingredient 1 in product A |
1460.65 |
0 |
2.15 |
1.75 |
132.4 |
Grams of ingredient 1 in product B |
39.35 |
0 |
2.65 |
-inf |
3.58 |
Grams of ingredient 2 in product A |
232.54 |
0 |
2.1 |
-inf |
2.63 |
Grams of ingredient 2 in product B |
255.79 |
0 |
2.6 |
-inf |
3.09 |
Grams of ingredient 3 in product A |
632.2 |
0 |
1.75 |
1.61 |
2.15 |
Grams of ingredient 3 in product B |
98.38 |
0 |
2.25 |
-inf |
3.05 |
idx |
Constraint |
Right Hand Side |
Shadow Price |
Slack |
Min RHS |
Max RHS |
|---|---|---|---|---|---|---|
0 |
Ingredient 1 availability |
1500 |
0.4 |
0 |
271.89 |
1550.85 |
1 |
Ingredient 2 availability |
1300 |
0 |
811.67 |
488.33 |
inf |
2 |
Ingredient 3 availability |
2000 |
0 |
1269.42 |
730.58 |
inf |
3 |
Ingredient 3 >=25% in product_A |
0 |
0 |
-50.85 |
-inf |
50.85 |
4 |
Ingredient 3 >=25% in product_B |
0 |
-1.04 |
0 |
-50.07 |
42.04 |
5 |
Product B >=10% of ingredient 2 than product A |
0 |
-0.69 |
0 |
-330 |
42.04 |
6 |
Quantity of ingredient 1 in product A must be at least 10% |
0 |
0 |
-1228.11 |
-inf |
1228.11 |
7 |
Quantity of ingredient 1 in product B must be at least 10% |
0 |
-1.04 |
0 |
-35.16 |
242.68 |
8 |
Quantity of ingredient 2 in product A must be at least 10% |
0 |
-0.41 |
0 |
-300 |
21.82 |
9 |
Quantity of ingredient 2 in product B must be at least 10% |
0 |
0 |
-216.44 |
-inf |
216.44 |
10 |
Quantity of ingredient 3 in product A must be at least 10% |
0 |
0 |
-399.66 |
-inf |
399.66 |
11 |
Quantity of ingredient 3 in product B must be at least 10% |
0 |
0 |
-59.03 |
-inf |
59.03 |
12 |
Production capacity |
10 |
512.58 |
0 |
9.67 |
15.69 |
a Write the expressions of the missing constraints. You may use indices to write your expressions in a compact form
b Write down the objective function of the dual problem and provide an economic interpretation of the dual variables
c What is the maximum price for ingredient 3 that the company can pay without changes in the optimal solution? Motivate your response
d The company can improve the daily capacity of the line in 1 hour for 50000€. How would this affect the profits and how long will it take for the company to make this investment profitable, considering only the increase in the daily profits
e Is the availability of ingredient 1 a binding constraint? How would you optimise the procurement of ingredients (daily amounts that are available) according to the provided solution?