Skip to main content

Linear Optimization Modeling and Solving Linear problems with Julia and WebCAS

Peter Staab

Section 2.1 Introduction to Linear Optimization

This section goes into a number of applied problems that have linear constraints and a linear objective function. Consider the following:
🔗

Problem 2.1.1. The toy car problem.

Luis is a toymaker who builds toy cars with wood. His most popular toys are a car, an SUV and a truck. The car is made with 6 units of pine, 3 units of birch and take a total of 45 minutes to make. The SUV is made with 5 units of pine, 6 units of birch and takes a total of 75 minutes to make. The truck takes 4 units of pine, 7 units of birch and takes a total of 90 minutes to make. For each car he makes $10 in profit, for each SUV is $15 in profit and for each truck is $12 in profit.
🔗
Luis has 183 units of pine, 204 units of birch. For the week, he has a total of 2655 minutes of time the shop can spend building toys. How many of each toy should he make to maximize his profit?
🔗
🔗
Example of Linear Optimization Problems (LOPs) occur in many fields. This section introduces a few more examples.
🔗

Problem 2.1.2. Shipping Coffee Problem.

A coffee supplier has warehouses in Seattle and San José. The coffee supplier receives orders from coffee retailers in Salt Lake City and Reno.
🔗
The retailer in Salt Lake City needs 400 pounds of coffee and the the retailer in Reno needs 350 pounds of coffee. The Seattle warehouse has 700 pounds available and the San José warehouse has 500 pounds available.
🔗
The cost of shipping from Seattle to Salt Lake City is $2.50 per pound, from Seattle to Reno $3 per pound, from San José to Salt Lake is $4 per pound and from San José to Reno is $2 per pound.
🔗
Find the number of pounds to be shipped from each warehouse to each retailer to minimize the cost.
🔗
🔗

Problem 2.1.3. Scheduling Librarians.

The FSU library needs to make sure that there is at least one reference librarian on duty during open hours. If there are 3 reference librarians, how do you schedule them to work such that a) each one works at least 30 hours per week. b) No one work longer than 10 hours in a given day. How would you schedule them such that the total number of hours worked by all reference librarians is minimized.
🔗
🔗

Problem 2.1.4. A Diet Problem.

Consider the problem: Gary goes on a diet eating only a salad, turkey sandwich or a bagel with cream cheese for a week. (Yes. It’s the worst!). The following table shows important information for each
🔗
calories protein carbs fat
salad 600 5 7 4
sandwich 750 18 10 8
bagel 500 10 24 12
Gary is trying to minimize the total calories ensuring that he eats at least 54 grams of protein, 45 grams of fat and 60 grams of carbs. Write down the objective function and the set of linear constraints?
🔗
🔗

Problem 2.1.5. Blending Problem.

Becky’s Bakery has the following amounts of ingredients on hand: 32 cups flour, 2 dozen eggs and 20 cups of sugar. They would like to make some number of batches of Chocolate Chip Cookies, Brownies and Sugar Cookies. The recipes for these call for the following amounts of flour, eggs and sugar:
🔗
Recipe Flour Eggs Sugar
Choc. Chip Cookies 3 2 1
Brownies 2 1 2
Sugar Cookies 1 2 2
If the profit made for each recipe is 20, 24, and 16 dollars respectively, find the number of batches of each baked good that the bakery should make to maximize the profit.
🔗
🔗

Problem 2.1.6. Allocation Problem.

Jane has four courses this given semester. Let’s call them Mathematics (M), History (H), Writing (W) and Psychology (Psy). We want to determine a number of constraints on the amount of studying she does in these classes.
🔗
  1. The total number of hours for studying is 360.
    🔗
    🔗
  2. Jane is on a scholarship and needs to keep a 3.0.
    🔗
    🔗
  3. Jane needs to pass every class to stay on the scholarship.
    🔗
    🔗
  4. From past experience, the following table lists the amount of time Jane needs to earn 1 grade point in each course:
    🔗
    Course hour/grade point
    Mathematics 30
    Psychology 20
    History 25
    Writing 20
    🔗
🔗
What is the minimum number of hours that Jane should study in each class?
🔗
🔗

Problem 2.1.7. Urban Farming Project.

A non-profit organization, GreenHarvest, aims to establish a sustainable urban farm within a limited city space.
 1 
This problem was created in part using Google Gemini.
They want to maximize their total profit from selling produce to local restaurants and farmers’ markets while adhering to various constraints. They have identified four key crops to cultivate:
🔗
  1. Heirloom Tomatoes (T): High-profit, but require significant space and water.
    🔗
    🔗
  2. Organic Lettuce (L): Moderate profit, quick growing, but sensitive to sun exposure.
    🔗
    🔗
  3. Specialty Herbs (H): Low profit per plant, but very space-efficient and high demand.
    🔗
    🔗
  4. Root Vegetables (R): Moderate profit, require deep soil beds and longer growth cycles.
    🔗
    🔗
🔗
The project has 50 growing beds for all crops. Due to city regulations and sustainable practices, there’s a limit on daily water consumption. Each crop type has different water requirements per bed. The total water usage cannot exceed 1500 liters per day.
🔗
  • Heirloom Tomatoes: 40 liters/bed
    🔗
    🔗
  • Organic Lettuce: 25 liters/bed
    🔗
    🔗
  • Specialty Herbs: 15 liters/bed
    🔗
    🔗
  • Root Vegetables: 30 liters/bed
    🔗
    🔗
🔗
To meet the demand from local restaurants that rely heavily on fresh herbs, GreenHarvest wants to ensure at least 5 beds are dedicated to Specialty Herbs.
🔗
To maintain crop diversity and manage pest control effectively, the number of Heirloom Tomato beds should be no more than twice the number of Organic Lettuce beds.
🔗
Profit per bed (estimated per growing season):
🔗
  1. Heirloom Tomatoes: $300
    🔗
    🔗
  2. Organic Lettuce: $180
    🔗
    🔗
  3. Specialty Herbs: $100
    🔗
    🔗
  4. Root Vegetables: $220
    🔗
    🔗
🔗
The goal of this problem is to determine the number of beds to devote to each of the different types of crops in order to maximize the profit.
🔗
🔗

Subsection 2.1.1 Creating Linear Models

We have seen a number of problems in this chapter that will fit into a linear model. Let’s look at Problem 2.1.1 as a example of how to approach creating a linear model. We’ll write the common steps and fill in those steps for this problem.
🔗
  1. What are the variables? Clearly list each one or perhaps if they are indexed, write down what each indexed variable represents.
    🔗
    Solution: There are 3 types of toys for this problem:
    🔗
    \begin{align*} x_1 \amp = \text{number of cars to be produced},\\ x_2 \amp = \text{number of SUVs to be produced},\\ x_3 \amp = \text{number of trucks to be produced}. \end{align*}
    🔗
    🔗
  2. What is the objective? Is it to be minimized or maximized.
    🔗
    Solution: In this case, the profit is to be maximized and can be written
    🔗
    \begin{equation*} z = 10 x_1 + 15 x_2 + 12 x_3. \end{equation*}
    🔗
    🔗
  3. What are the constraints? Note: one way to think about this is the case of something being maximized, why can’t the objective be increased without bound.
    🔗
    Solution: The profit cannot be increased with bound because there is a limit on the amount of wood and labor that can be used. For each of these, we build a constraint.
    🔗
    • For the amount of pine: \(6x_1 + 5x_2 + 4x_3 \leq 183.\)
      🔗
      🔗
    • For the amount of birch: \(3x_1 + 6x_2 + 7x_3 \leq 204.\)
      🔗
      🔗
    • For the amount of labor: \(45x_1 + 75x_2 + 90x_3 \leq 2655.\)
      🔗
      🔗
    🔗
    🔗
  4. Check if the nonnegative constraints on the variables are needed assumptions.
    🔗
    Solution: Yes. Since the variables represent the numbers of things (in this case toys) to make, the nonnegative assumptions on each variable makes sense.
    🔗
    \begin{equation*} x_1, x_2, x_3 \geq 0 \end{equation*}
    🔗
    🔗
  5. Check if either integer or binary constraints are reasonable.
    🔗
    Solution: Since the variables are numbers of toys to make, they must be integers,
     2 
    There are a few different ways to denote the set of nonnegative integers, however, in this text, we will use \(\mathbb{N}_0\) to represent \(\{0,1,2,3, \ldots \}\text{.}\)
    but not binary.
    🔗
    \begin{equation*} x_1, x_2, x_3 \in \mathbb{N}_0 \end{equation*}
    🔗
    🔗
🔗
The next problem shows how to attack another linear problem.
🔗

Problem 2.1.8.

Use the steps above to write the LOP for Problem 2.1.2.
🔗
Solution.
  1. What are the variables?
    🔗
    Solution: In this case, first note that we need to know the amount of coffee shipped between warehouses and retail outlets. The following graph is helpful for this:
    🔗
    Figure 2.1.9.
    🔗
    Specifically we have the following:
    🔗
    \begin{align*} x_1 \amp = \text{number of pounds of coffee to ship from Seattle to Reno},\\ x_2 \amp = \text{number of pounds of coffee to ship from Seattle to Salt Lake City},\\ x_3 \amp = \text{number of pounds of coffee to ship from San José to Reno},\\ x_4 \amp = \text{number of pounds of coffee to ship from San José to Salt Lake. City} \end{align*}
    🔗
    🔗
  2. What is the objective?
    🔗
    The objective is the total cost and it is to be minimized or
    🔗
    \begin{equation*} z = 3 x_1 + 2.50 x_2 + 4 x_3 + 2 x_4. \end{equation*}
    🔗
    🔗
  3. What are the constraints?
    🔗
    The variables are going to be the total amount of coffee to be shipped from the two warehouses to the two retail locations. If we look first at the amount of coffee that the Salt Lake City and Reno locations need then we need to ship at least this amount or
    🔗
    \begin{align*} x_2 + x_3 \amp \geq 400, \\ x_1 + x_4 \amp \geq 350. \end{align*}
    🔗
    Since the warehouses have a limited supply, they can only ship what they have so there are two additional constraints, one for each warehouse
    🔗
    \begin{align*} x_1 + x_2 \amp \leq 700,\\ x_3 + x_4 \amp \leq 500. \end{align*}
    🔗
    🔗
  4. Check if the nonnegative constraints on the variables are needed assumptions.
    🔗
    Solution: Each amount of coffee shipped should be nonnegative, so \(x_1, x_2, x_3, x_4 \geq 0\text{.}\)
    🔗
    🔗
  5. Check if either integer or binary constraint are needed.
    🔗
    In this case, because coffee does not need to be shipped in integer amounts of pounds, this is not needed.
    🔗
    🔗
🔗
We can combine all of these into the following LOP:
🔗
\begin{equation*} \begin{aligned} \text{Minimize} \amp \amp z = 2.5 x_1 + 3 x_2 + 4 x_3 + 2 x_4,\amp \\ \text{subject to} \amp \amp x_2 + x_3 \amp \geq 400.\\ \amp \amp x_1 + x_4 \amp \geq 350,\\ \amp \amp x_1 + x_2 \amp \leq 700,\\ \amp \amp x_3 + x_4 \amp \leq 500,\\ \text{and}\amp \amp x_1, x_2, x_3, x_4 \amp \geq 0. \end{aligned} \end{equation*}
🔗
🔗
🔗
🔗

Subsection 2.1.2 Non-Obvious Linear Optimization Problems

Perhaps as you have read through the problems at the top of this section and then the mathematical formulation of each in Subsection 2.1.1 and notice that there are some similarities between the problems. Each clearly has an objective that is to optimized and has a number of constraints. However, there are other problems that with some creativity can be written as an LOP. Consider the following:
🔗

Problem 2.1.10. \(n\)-queens problem.

A chessboard is a grid of spaces in which pieces move around the board according to various rules. A queen is a piece that can move left, right, up, down or diagonal any number of squares. Figure 2.1.11 shows the standard 8 by 8 chessboard and one queen.
🔗
The \(n\)-queens problem asks if \(n\) queens can appear on an \(n\) by \(n\) chessboard, so that no queen can attacker another queen.
🔗
🔗
Figure 2.1.11. An 8 by 8 chessboard with a queen on a square. The arrows indicate the other squares that can attack with this piece.
🔗
It’s not clear what the objective function is for this problem (although there is one). The constraints for the problem might be the constraints on a queen. Also, what are the variables? We’ll see how to approach this later.
🔗

Problem 2.1.12. Room Scheduling.

The registrar at State University needs to schedule rooms for a set of classes in a time block. For simplification, the classes will be A, B, C, ..., H and they will be put in rooms 1,2,3, ..., 8. Not every class can be scheduled in every room. Some classes need to be in a computer class, some classes need to be on the first floor of the building, some faculty prefer whiteboards, some faculty prefer to use a project. Here’s all of these constraints:
🔗
  • Classes A, B and C need to be scheduled in a computer lab (rooms 1, 4, 6, 8).
    🔗
    🔗
  • Classes D and E need to be on the first floor the building (rooms 1, 2, 3).
    🔗
    🔗
  • Classes B, E, F, G, H need a whiteboard and cannot be in rooms 1, 2 or 7.
    🔗
    🔗
  • Classes C, D, F and H need a projector and cannot be in room 2, 5, or 8.
    🔗
    🔗
🔗
What is a reasonable scheduling of the rooms if possible?
🔗
🔗
This problem seems to have similarities with the previous problem, and similar questions arise. What are the variables for the problem? There are clearly some constraints in that certain classes need to be in a some rooms, but not others. It’s unclear what the objective is.
🔗

Problem 2.1.13. Mars Rover.

You are the lead mission planner for NASA’s new Mars rover, “Curiosity II.” The rocket launching the rover has a strict weight limit for its scientific payload. Exceeding this limit is not an option. A team of scientists has reviewed all possible instruments and assigned each a “scientific value” score based on the mission’s objectives (like finding signs of past life or analyzing atmospheric composition). Your job is to select the combination of instruments that will maximize the total scientific value of the mission without exceeding the weight limit.
 3 
This was generated with help from Gemini AI.
🔗
Table 2.1.14. Mars Rover Instrument Options
🔗
Instrument Name Weight (kg) Scientific Value Score
Alpha Particle X-ray Spectrometer 35 30
High-Resolution Panoramic Camera 30 25
Subsurface Drilling Unit 60 55
Weather & Radiation Monitor 45 35
Laser-Induced Breakdown Spectrometer 40 40
Robotic Scoop & Soil Analyzer 55 50
🔗
This problem falls into a class of problems called knapsack problems. The idea is that you have a knapsack (backpack) with limited capacity and you want to include as much as possible, whether that is volume, weight or some other measure (like scientific value).
🔗
The next problem is interesting in that it asks about where to place items (in this case in a city). At first glance this doesn’t seem to be a linear optimization problem.
🔗

Problem 2.1.15. The Mailbox Problem.

Gridburg is 4 blocks by 6 blocks in a grid as shown below:
🔗
Figure 2.1.16.
🔗
The postal chief wants to arrange mailboxes such that anywhere in the city, one does not need to walk any more than two blocks to reach a mailbox. If it is required that mailboxes be placed at intersections, where should the mailboxes be placed to minimize the number of mailboxes.
 4 
This problem is a nod to Glenn Hurlbert, whose book Linear Optimization: a Handbook motivated this work. The book had a number of problems in Gridburg a town on a grid like above.
🔗
🔗

Subsubsection 2.1.2.1 LOP Formulation of \(n\)-queens Problem

Perhaps looking at Problem 2.1.10, it would not seem like it is a linear optimization problem. You might think that there are constraints—no queen can attack another one, but what is the objective function?
🔗
First, to formulate the problem, we need to know the variables. A common situation is to place objects in a grid or other arrangement and then use a variable to denote whether or not to place the object at the grid point. In this case, we are going to use \(x_{i,j}\) to be a binary variable that is 1 if there is a queen at row \(i\) and column \(j\) and 0 otherwise.
🔗
The constraints will be that there is at most one queen in any row, column or diagonal of the chessboard. At most a single queen in any row or column can be written as
🔗
\begin{align} \sum_{j=1}^n x_{i,j} \amp \leq 1 \qquad \text{for $i=1, 2, \ldots n$} \tag{2.1.1}\\ \sum_{i=1}^n x_{i,j} \amp \leq 1 \qquad \text{for $j=1, 2, \ldots n$} \tag{2.1.2} \end{align}
🔗
Note that in (2.1.1), the sum is across row \(i\) and the inequality with \(\leq 1\) means that at most there is 1 queen in each row. Similarly in (2.1.2), the sum in for a given column, so there is at most one queen in a column.
🔗
The diagonals are trickier. In the diagonal from the lower left to upper right then summing \(\sum_{i=1}^n x_{i,i} \leq 1 \text{,}\) but this is also true for every diagonal that parallels this one. The inequality for this is in the problem below.
🔗
There is also a diagonal from the upper left to lower right with the inequality \(\sum_{i=1}^n x_{i,n+1-i} \leq 1\text{,}\) but also with every other diagonal parallel to these, which are listed below.
🔗
Finally, we will use the objective that the total number of queens on the board to be minimized. The total number can be calculated with
🔗
\begin{equation*} z = \sum_{i=1}^n \sum_{j=1}^n x_{i,j} \end{equation*}
🔗
Here’s a summary of the \(n\)-queens problems:
🔗
\begin{equation*} \begin{aligned} \text{Minimize} \amp \amp z \amp = \sum_{i=1}^n \sum_{j=1}^n x_{i,j}, \\ \text{subject to} \amp \amp \sum_{i=1}^n x_{i,j} \amp \leq 1 \qquad \text{for $j=1, 2, \ldots n$} \\ \amp \amp \sum_{j=1}^n x_{i,j} \amp \leq 1 \qquad \text{for $i=1, 2, \ldots n$} \\ \amp \amp \sum_{i=1}^{n-k} x_{i,i+k} \amp \leq 1 \qquad \text{for $k=0, 1, \ldots n-1$} \\ \amp \amp \sum_{i=k-1}^{n-1} x_{i,i-k} \amp \leq 1 \qquad \text{for $k=1,2, \ldots n-1$} \\ \amp \amp \sum_{i=1}^{n-k} x_{i,n-k} \amp \leq 1 \qquad \text{for $k=0, 1, \ldots n-1$} \\ \amp \amp \sum_{i=k-1}^{n-1} x_{n-i,k} \amp \leq 1 \qquad \text{for $k=1,2, \ldots n-1$} \\ \text{and} \amp \amp x_{i,j} \amp \in \{0,1\} \qquad \text{for $i=1,\ldots, n, j = 1, \ldots n$} \end{aligned} \end{equation*}
🔗
The first inequality is the column sum for every \(j\text{,}\) the second is the row sum for every \(i\text{.}\) The third and fourth are the diagonals that run from bottom left to upper right on the chessboard and the fifth and sixth are the upper left to lower right.
🔗
The Mailbox Problem in Problem 2.1.15 can be set up in a similar manner to that of the \(n\)-queens problem because we can write the variables as a binary variables of each intersection. A one would indicate the presence of a mailbox and zero would not. The constraints would be that the total number of mailboxes within two blocks of every intersection is at least 2.
🔗
🔗
🔗
🔗
PrevTopNext