Learning Outcomes

1.

Define what a linear program is

2.

Understand how to model a linear program

3.

View many examples and get a sense of what types of problems can be modeled as linear programs.

Resources

Example 2.1: Screen Printing Shop

Learning Outcomes

1.

Address key assumptions when choosing to model a problem with linear programming.

Variables:
The decision variables represent the quantities we want to determine. For example:

• $x_i$: Continuous variables ($x_i\in ℝ$, i.e., a real number), $\forall i=1,\dots ,n$.

These variables could represent amounts of products to produce, resources to allocate, or investments to make. We can use any letters to represent these variables. Typically we use $x_i$, but frequently will use $y_i$ or other letters depending on the context and what makes reading the problem most convenient.

Parameters:
Parameters are the given data in the problem, which are assumed to be known in advance:

• $c_i$: Cost coefficients for each decision variable, $\forall i=1,\dots ,n$. These values represent the contribution of each variable to the objective function.

• $a_{ij}$: Constraint coefficients, $\forall i=1,\dots ,n$ and $j=1,\dots ,m$. These define the relationships between decision variables and the constraints.

• $b_j$: Right-hand side values of the constraints, $\forall j=1,\dots ,m$. These represent limits or requirements for each constraint.

The general form of a linear program can be written as follows:

• Objective Function: The linear function $z=c_1{x}_1+\cdots +c_n{x}_n$ represents the goal to optimize. This could involve maximizing profit, minimizing cost, or achieving some other measurable outcome.

• Constraints: The system of inequalities (or equalities) restricts the values of the decision variables. Each constraint reflects a real-world limitation, such as resource availability or capacity limits.

• Feasibility: The set of all possible solutions that satisfy the constraints is called the feasible region. The optimal solution must lie within this region.

• Linear Relationships: Both the objective function and constraints are linear, meaning the relationships between variables are additive and proportional.

• Sets: For specific optimization problems, it can be useful to define sets of variables or parameters to help write down the problem in a generic formulation.

Example 2.2: Example of a Linear Program

To illustrate, consider a specific example with three decision variables and four constraints, including a mix of constraint types ($\le$, $\ge$, and $=$):

Variables:
$x_i$: Continuous variables ($x_i\in ℝ$, i.e., a real number), $\forall i=1,\dots ,3$.

Parameters:

• $c_i$: Cost coefficients, $\forall i=1,\dots ,3$.

• $a_{ij}$: Constraint coefficients, $\forall i=1,\dots ,3$ and $j=1,\dots ,4$.

• $b_j$: Right-hand side values for each constraint, $\forall j=1,\dots ,4$.

Model:

Definition 2.3: Linear Function

A function $z:{ℝ}^n\to ℝ$ is linear if there are constants $c_1,\dots ,c_n\in ℝ$ such that:

Linear functions are characterized by their simplicity and additivity, making them well-suited for optimization problems where proportionality is assumed. This simplicity allows linear programs to be solved efficiently, even for large-scale problems.

Learning Checkpoint 2.2.1

Learning Outcomes

1.

Identify decision variables and parameters

2.

Learn how to format a linear optimization problem.

3.

Identify and understand common classes of linear optimization problems.

Example 2.4: Production Planning

Solution

Sets:

• Days of production $=\{1,2\}$.

Parameters:

• $c_{p1}$: Per unit production cost on Day 1 ($10).

• $c_{p2}$: Per unit production cost on Day 2 ($16).

• $c_{inv}$: Per unit inventory cost ($5).

• $d_1$: Demand on Day 1 (10 units).

• $d_2$: Demand on Day 2 (4 units).

• $s_0$: Inventory at the start of Day 1.

Variables:

• $x_1$: Number of units produced on Day 1.

• $x_2$: Number of units produced on Day 2.

• $s_1$: Inventory at the end of Day 1.

• $s_2$: Inventory at the end of Day 2.

Model:

Definition 2.5: Optimization model components

When defining an optimization model, it is essential to identify and clearly articulate the following five components:

• Sets: What lists of data do you need to write down? These could include indices, categories, or groups relevant to the problem.

• Parameters (Data): What is the actual data for the problem? These are the fixed numerical values such as costs, capacities, or resource availabilities.

• Decision Variables: What decisions need to be made to provide a solution? These variables represent the quantities that can be controlled or adjusted, such as production levels or resource allocations.

• Objective Function: The expression that we want to maximize or minimize. This is the goal of the optimization, such as minimizing cost or maximizing profit.

• Constraints: Certain rules that those decision variables should satisfy. These include limitations or requirements, such as resource capacities or demand fulfillment.

Each of these components plays a key role in formulating a well-structured optimization model that accurately represents the problem and provides actionable solutions. The role of Sets will become more important as we get into more complicated optimization models.

Example 2.6: Bakery Production

Example 2.7: Production with welding robot

Example 2.8: The Diet Problem

Solution

Sets:

• Set of tablets $\{1,2,3,4\}$

Parameters:

• Iron in each tablet

• Vitamin B in each tablet

• Vitamin C in each tablet

• Vitamin D in each tablet

• Cost of each tablet

Variables:
$x_i$ : number of tablets of type $i$ to include in the diet, $\forall i\in \{1,2,3,4\}$.

Model:

Example 2.9: The Next Diet Problem

Solution

Sets:

• Set of chemicals $\{1,2,3,4\}$

Parameters:

• Iron in each chemical

• Vitamin B in each chemical

• Vitamin C in each chemical

• Vitamin D in each chemical

• Cost of each chemical

Variables:
$x_i$ : grams of chemical $i$ to include in the purple tablet, $\forall i=1,2,3,4$.
Model:

The diet problem might feel like a toy. It is not.

Case Study: Feeding Millions: The World Food Programme’s Optimization Engine

The United Nations World Food Programme (WFP) is the world’s largest humanitarian organization, assisting roughly 100 million people a year in places like Iraq, Yemen, and South Sudan. Every operation must answer the same questions: what food basket to provide, where to buy it, and how to move it. WFP built an optimization tool, Optimus, that answers all three at once, and the team won the 2021 INFORMS Franz Edelman Award for it.

A food basket must meet nutritional requirements (energy, protein, fat, micronutrients) for a beneficiary, using commodities that can actually be procured and delivered through a network of suppliers, ports, warehouses, and distribution points, each with costs and capacities. Cheaper baskets can be less nutritious; more nutritious baskets can be undeliverable. Before Optimus, these decisions were made separately by different teams.

Model type: mixed-integer linear program. The core is the classical diet LP joined to a min-cost flow model; integer variables handle choices such as transfer modality (food vs. cash). No machine learning inside the optimization; demand and price inputs come from WFP assessments.

A simplified version with the two key ingredients:

Variables:

• Let $x_k\ge 0$ be the amount of commodity $k$ (grams per person per day) in the food basket.

• Let $f_{ka}\ge 0$ be the flow of commodity $k$ on arc $a$ of the supply network.

Model:

where $n_{jk}$ is the amount of nutrient $j$ per gram of commodity $k$ and $R_j$ is the daily requirement. The published model adds palatability rules (e.g., the basket cannot be all lentils), sourcing decisions, multi-period planning, and the food-vs.-cash modality choice, which is where the integer variables enter.

• Nutritional needs are modeled per “average beneficiary”; the paper discusses requirements by demographic profile.

• Prices and lead times are taken as data; the paper describes how WFP updates them per operation.

In Iraq, the tool cut operating costs by 17 percent, and the resulting food baskets met 98 percent of the nutrition requirements; WFP has since applied it across its major operations. The full MILP is printed in the paper, which is open access, so students can read exactly what was modeled and what was assumed.

Example 2.10: Work Scheduling Problem

Solution

This problem has multiple optimal solutions for which days workers begin working on, all of which result in 8 total workers hired.

Variables:
$x_i$ : the number of workers that start 5 consecutive days of work on day $i$, $i=1,\dots ,7$
Model:

One solution is as follows. The LP relaxation gives $z_{LP}=7.333$ with fractional values $(x_1,\dots ,x_7)=(0,0.333,1,2.333,0,3.333,0.333)$. Rounding to an integer solution yields $z_{IP}=8$ with $(x_1,\dots ,x_7)=(0,0,0,3,0,4,1)$.

Example 2.11: LP Burger - extended

Example 2.12: Camping Trip

Solution

Variables:
$x_i$ : whether to include item $i$ in the backpack, where $i\in \{A,B,C,D,E,F,G,H\}$, $x_i=1$ if item $i$ is included, and $x_i=0$ otherwise.

Model:

Example 2.13: Capital Allocation Problem

Solution

Sets:

• Projects: $P=\{A,B,C,D,E\}$

Parameters:

• ${\text{inv}}_i$: investment required for project $i$

• ${\text{ret}}_i$: projected return from project $i$

• $B=100,000$: total available capital

Variables:
$x_i\in \{0,1\}$: 1 if project $i$ is selected, 0 otherwise

Model:

Compact Form:

Example 2.14: Solar Panel Shipping

Warehouse Demands:

Solution

Sets:

• Factories: $F=\{R,B,T\}$

• Warehouses: $W=\{1,2,3,4,5\}$

Parameters:

• $C_f$: production cost per panel at factory $f$

• $S_f$: supply capacity of factory $f$

• $D_w$: demand at warehouse $w$

• $T_{f,w}$: shipping cost per panel from factory $f$ to warehouse $w$

• $M=2000$: max panels shipped from any factory to any warehouse

Variables:
$x_{f,w}$: number of solar panels shipped from factory $f$ to warehouse $w$

Model:

Example 2.15: Hiring for tasks

Given the specific costs of assigning three people to three tasks, we can write out the mathematical model explicitly using the given numbers.

Solution

Sets:

• Persons: $\{1,2,3\}$

• Tasks: $\{1,2,3\}$

Parameters:

• $c_{ij}$: cost for person $i$ to complete task $j$

Variables:
$x_{ij}=1$ if person $i$ is assigned to task $j$, and $0$ otherwise.

Model:

Exercise 2.16: Identify Linear Functions

$\star$  Which ones are linear functions?

1.

$x^2+3y+2z$

2.

$\sqrt{x_1{x}_2{x}_3}$

3.

${\sum }_{i=1}^n{a}_i{2}^{x_i},\text{where }{a}_1,a_2,\dots ,a_n\text{ are constant}$

4.

${\sum }_{i=1}^n{a}_i{x}_i,\text{where }{a}_1,a_2,\dots ,a_n\text{ are constant}$

Exercise 2.17: Identify Linear Function

$\star$  Which one is a linear function?

1.

$2x_1+x_2{x}_3-7x_3$

2.

$\sqrt{2}{x}_1+x_2+3^{1.6}{x}_3$

Exercise 2.18: Hoodies and Posters

Exercise 2.19: Smoothie Powders

Exercise 2.20: Chemical Manufacturing

$\star \star$  A specialty coatings plant makes three additives, labeled A, B, and C, as joint outputs of two continuous production lines. Each hour that Line 1 runs costs $5 in energy and labor and outputs 2 drums of A, 3 drums of B, and 1 drum of C. Each hour that Line 2 runs costs $2 and outputs 1 drum of A and 2 drums of C (Line 2 cannot make B). Contracts require the plant to deliver at least 8 drums of A, 6 drums of B, and 5 drums of C each day. The plant manager wants a daily operating schedule for the two lines that meets the contracts at the lowest cost.

Formulate a linear program for the manager’s problem. State your decision variables clearly, including their units.

[Hint: the decisions are how long to run each line, not how much of each chemical to make. Once you choose those variables, both the cost and the output of each chemical are linear expressions in them.]

Exercise 2.21: E-Bike Showroom

$\star \star$  A showroom sells three e-bike models: commuter, cargo, and mountain. Each commuter, cargo, and mountain bike on display requires, respectively, 2, 4, and 3 square meters of floor space; the showroom has 60 square meters available. Selling one bike takes 2, 3, and 2 hours of staff time respectively, and 120 staff hours are available per month. Each sold bike also needs 1, 3, and 2 hours respectively in the assembly bay, which has 75 hours available per month.

If the profit (in dollars) per commuter, cargo, and mountain bike is 150, 300, and 240 respectively, how many of each model should the showroom plan to sell each month to maximize profit, and what is the maximum profit?

Exercise 2.22: Manufacturing Profit Problem

$\star \star$  A furniture workshop builds bookcases, desks, and cabinets. Every piece passes through two workstations: a CNC router and a finishing station. The router is available 200 hours per month and the finishing station 240 hours per month. The table below shows the time requirements (in hours per unit) and profit per unit for each product.

Exercise 2.23: Juice Bottling Plants

$\star \star$  A beverage company bottles three juices (apple, orange, and grape) at two plants. The number of cases each plant bottles per day of operation is listed below:

Exercise 2.24: Quiz Grading Minimization

$\star \star$  Professor Wright gives three types of quizzes (objective, recall, and recall-plus) and decides to give at least 20 quizzes next quarter. Each type of quiz requires the students to spend extra preparation time:

He wants students to spend at least 12 hours (720 minutes) in total preparation for these quizzes (beyond normal study time).

Average quiz scores are:

He wants the total of all quiz scores to be at least 130 points.

It takes the professor:

How many of each type should he give in order to minimize his own grading time?

Exercise 2.25: Campus Café Scheduling

$\star \star$  A campus café is open seven days a week. Each barista works four consecutive days and then has three days off. The minimum number of baristas needed each day is:

1.

Let $x_i$ be the number of baristas who start their four-day stretch on day $i$ (with the week wrapping around). Formulate an LP that minimizes the total number of baristas hired.

2.

Solve the LP relaxation with software and verify that its optimal value is $28∕3\approx 9.33$.

3.

Explain why part (b) implies that every feasible whole-number staffing plan uses at least 10 baristas, and find a plan that uses exactly 10.

Exercise 2.26: Identify Linear Inequalities

$\star \star$  Which ones are linear inequalities? Can any be made into linear inequalities?

1.

$\frac{x_1}{x_1+x_2+x_3}\ge 0.5$

2.

$\sin x_1+x_2+x_3=0.5$

3.

${\sum }_{i=1}^n{a}_i{2}^{x_i}\ge b,\text{where }{a}_1,a_2,\dots ,a_n,b\text{ are constant}$

4.

${\sum }_{i=1}^n{a}_i{x}_i=b,\text{where }{a}_1,a_2,\dots ,a_n,b\text{ are constant}$

5.

${\sum }_{i=1}^n{a}_i{x}_i\ge b,\text{where }{a}_1,a_2,\dots ,a_n,b\text{ are constant}$

Exercise 2.27: Random Costs in the Objective

$\star \star \star$  In every model so far, the objective coefficients were fixed numbers. Now suppose each cost coefficient $c_i$ is not known exactly; instead, you know its probability distribution. Propose a single deterministic linear program whose solution is a sensible plan under this uncertainty, and explain what your objective function represents.

[Hint: if a lottery ticket pays some amount between $1 and $2 with all values equally likely, what single number summarizes its worth to you? Apply the same summary to each $c_i$.]

Exercise 2.28: Which Assumption Breaks?

$\star \star$  For each scenario below, name the linear programming assumption (proportionality, additivity, divisibility, or certainty) that is most clearly violated, and explain your choice in one sentence.