Lab 2 - Mathematical Programming Examples
1. Introduction
This lab introduces additional mathematical programming examples and demonstrates how optimization models can be formulated in both open form (explicit equations) and closed form (set-based notation).
Topics covered include:
- Cake Production Problem
- Diet Problem
- Dorian Auto Advertising Problem
- Indexed decision variables in PuLP
- Summation notation using
lpSum
2. Cake Production Problem
A bakery produces two types of cakes:
- Plain cake:
- 200g flour
- 25g fat
- Chocolate cake:
- 100g flour
- 50g fat
Available resources:
- 5 kg flour (5000g)
- 1 kg fat (1000g)
The objective is to determine the production quantities that maximize the total number of cakes produced.
| Resource | Available |
|---|---|
| Flour | 5000 g |
| Fat | 1000 g |
| Cake Type | Flour (g) | Fat (g) |
|---|---|---|
| Plain | 200 | 25 |
| Chocolate | 100 | 50 |
Mathematical Model
Let:
- \(x_1\) = number of plain cakes
- \(x_2\) = number of chocolate cakes
Objective
Maximize total cakes produced:
\[ \max Z = x_1 + x_2 \]
Subject to
\[ 200x_1 + 100x_2 \le 5000 \]
\[ 25x_1 + 50x_2 \le 1000 \]
\[ x_1, x_2 \ge 0 \]
\[ x_1, x_2 \in \mathbb{Z}_{\ge 0} \]
3. Diet Problem
A diet must satisfy minimum daily nutritional requirements at the lowest possible cost.
Available foods:
| Food Item | Cost |
|---|---|
| Brownie | $0.50 |
| Chocolate Ice Cream | $0.20 |
| Juice | $0.30 |
| Pineapple Cheesecake | $0.80 |
Daily requirements:
- At least 500 calories
- At least 6 oz chocolate
- At least 10 oz sugar
- At least 8 oz fat
Nutritional Data
| Item | Calories | Chocolate (oz) | Sugar (oz) | Fat (oz) |
|---|---|---|---|---|
| Brownie | 400 | 3 | 2 | 2 |
| Chocolate Ice Cream | 200 | 2 | 2 | 4 |
| Juice | 250 | 0 | 4 | 1 |
| Pineapple Cheesecake | 500 | 0 | 4 | 5 |
Closed Form Model
Sets
\[ J = \{1,2,3,4\} \]
Food items
\[ I = \{1,2,3,4\} \]
Nutritional requirements
Decision Variables
\[ x_j = \text{amount of food item } j \]
\[ x_j \ge 0 \quad \forall j \in J \]
Parameters
- \(c_j\) = cost of food item \(j\)
- \(a_{ij}\) = contribution of food \(j\) to requirement \(i\)
- \(b_i\) = minimum required amount of requirement \(i\)
Objective Function
\[ \min Z = \sum_{j \in J} c_j x_j \]
Constraints
\[ \sum_{j \in J} a_{ij}x_j \ge b_i \quad \forall i \in I \]
\[ x_j \ge 0 \quad \forall j \in J \]
Matrix Representation
Cost vector:
\[ \mathbf{c}= \begin{bmatrix} 0.50 & 0.20 & 0.30 & 0.80 \end{bmatrix} \]
Requirement vector:
\[ \mathbf{b}= \begin{bmatrix} 500\\ 6\\ 10\\ 8 \end{bmatrix} \]
Coefficient matrix:
\[ \mathbf{A}= \begin{bmatrix} 400 & 200 & 250 & 500\\ 3 & 2 & 0 & 0\\ 2 & 2 & 4 & 4\\ 2 & 4 & 1 & 5 \end{bmatrix} \]
4. PuLP Indexed Variables
When models contain sets of variables, PuLP allows variables to be created using LpVariable.dicts().
Example
import pulp
foods = [1, 2, 3, 4]
x = pulp.LpVariable.dicts(
"x",
foods,
lowBound=0,
cat="Continuous"
)This creates:
\[ x_1,\;x_2,\;x_3,\;x_4 \ge 0 \]
Variables can then be referenced using indexing:
x[j]5. PuLP Summations with lpSum
Optimization models frequently use summation notation.
Mathematically:
\[ \min Z = \sum_{j \in J} c_jx_j \]
In PuLP:
model += pulp.lpSum(
c[j] * x[j]
for j in foods
)Benefits of lpSum:
- Efficient construction of linear expressions
- Cleaner code
- Preferred over Python’s built-in
sum()
6. Dorian Auto Advertising Problem
Dorian Auto is planning a television advertising campaign.
Advertising options:
| Commercial Type | Women Reached (millions) | Men Reached (millions) | Cost |
|---|---|---|---|
| Comedy Show | 7 | 2 | $50,000 |
| Football Game | 2 | 12 | $100,000 |
Requirements:
- Reach at least 28 million high-income women
- Reach at least 24 million high-income men
Objective:
Minimize advertising cost.
Open Form Model
Let:
- \(x_1\) = comedy commercials purchased
- \(x_2\) = football commercials purchased
Objective
\[ \min Z = 50,000x_1 + 100,000x_2 \]
Subject to
\[ 7x_1 + 2x_2 \ge 28 \]
\[ 2x_1 + 12x_2 \ge 24 \]
\[ x_1,x_2 \ge 0 \]
Closed Form Model
Sets
\[ J = \{1,2\} \]
Advertising options
\[ I = \{1,2\} \]
Audience groups
Decision Variables
\[ x_j = \text{number of advertisements of type } j \]
\[ x_j \ge 0 \quad \forall j \in J \]
Parameters
- \(c_j\) = cost of advertisement type \(j\)
- \(a_{ij}\) = audience reach generated by advertisement \(j\)
- \(b_i\) = minimum required audience reach
Mathematical Formulation
\[ \min Z = \sum_{j \in J} c_j x_j \]
\[ \sum_{j \in J} a_{ij}x_j \ge b_i \quad \forall i \in I \]
\[ x_j \ge 0 \quad \forall j \in J \]
Matrix Representation
Cost vector:
\[ \mathbf{c}= \begin{bmatrix} 50,000 & 100,000 \end{bmatrix} \]
Requirement vector:
\[ \mathbf{b}= \begin{bmatrix} 28\\ 24 \end{bmatrix} \]
Coefficient matrix:
\[ \mathbf{A}= \begin{bmatrix} 7 & 2\\ 2 & 12 \end{bmatrix} \]
View Slides
Materials
- Excel File
- Follow Along
- Completed
- Google Colab
- Follow Along
- Completed
- GAMS Code
References
Winston, W. L. (2004). Operations Research: Applications and Algorithms (4th ed.). Thomson Brooks/Cole.
PuLP Documentation. https://coin-or.github.io/pulp/