Linear Optimization Modeling

Abstract

The chapter introduces linear programming, arguably the most used optimization method applicable when all the model terms are linear. Graphical solution approaches to solve two-variable linear models are used to illustrate how linear programming algorithms solve models containing many more variables as are typical of most real-world problems.

8.1 Introduction

Undoubtedly the most commonly used of all the mathematical programming (constrained optimization) methods is linear programming. Developing and solving linear optimization models is often the first topic addressed in courses in systems analysis. This is not because the world is linear, but because the algorithms (solution methods) used to solve linear models are so efficient and are able to solve problems with many—even thousands—of variables and constraints, as long as they are linear. Thus, many tricks exist for making non-linear functions linear. They are often employed just because of the efficiency and widespread availability of the solution methods for linear models. Linear programming has found many applications in the military, in government agencies, industry and in agriculture, ecology, economics, engineering, public health, and urban planning to mention only a few subject areas.

Hence, it seems reasonable to show how linear problems are solved, at least graphically, and when necessary, how some non-linear components of a model may be made linear to take advantage of linear optimization solution methods.

If a model is linear and has only two variables such as

$$ \begin{gathered} {\text{maximize}}\;X + Y \hfill \\ {\text{subject to}}:\;{2}X + Y \le {4}, \hfill \\ \quad \quad \quad \quad \;X \ge 0, \;Y \ge 0 \hfill \\ \end{gathered} $$

a method for solving linear programming models can be illustrated graphically. The first step is to find the region of values of X and Y that satisfy all the constraints. This region is called the feasible region. The combinations of X and Y values in this region meet all the constraints. They are called feasible solutions. This region of feasible solutions can be shown by a plot of each constraint on a graph whose axes are the two variables. In this case, there are three constraints (Fig. 8.1)

$$ {2}X + Y \le {4},\quad X \ge 0,\quad Y \ge 0. $$

Fig. 8.1

A plot of the three constraints of the linear model defines the region of feasible solutions for X and Y

All the X Y pairs of values in the shaded region and its boundaries, called the feasible region, satisfy all the constraints. Optimization problems that do not have feasible regions have no feasible solutions, meaning that not all constraints can be satisfied. Unbounded feasible regions result from one or more variables going to infinity as would be the case if there were no constraint 2X + Y ≤ 4 or if the constraint had to be greater or equal to 4 or any other number.

To find the best combination of X and Y values in this feasible region, set the objective function equal to some value, such as X + Y = 2, and then plot that equation. This is shown as a dashed line in Fig. 8.2. Since that function is to be maximized, our goal is to find the maximum value of its right-hand side while some part of that function is in the feasible region or on its boundary. Changing the right-hand side moves the objective function, the dashed line, up and down but doesn’t change its slope. If we change the 2 to a 4, we get the dash-dot line shown in that same figure. This is as high as the line can be raised, i.e., as large a value as the right-hand side of that objective function can be, while some part of that function is in or on the boundary of the feasible region.

Fig. 8.2

Finding the optimal solution to the linear model by moving the objective function that is to be maximized to its highest value position while it still is in or on the boundary of the feasible region

This plot shows that the optimal values of X and Y are 0 and 4, respectively. For all continuous variable linear optimization problems, the optimal solution will be one of the corner points of the feasible region. Thus, computer programs solving such linear optimization models need only to compute and compare the objective function values at the corner points (intersections of constraints) of the feasible region, rather than searching among the infinity of feasible solutions within the feasible region. Furthermore, once a corner point produces an objective value greater than that of all immediately adjacent corner points, the search for the best solution can end. No more corner points need to be considered. Some of you may be interested in thinking about why this is true.

Even though computer programs (e.g., Solver in Excel) will always produce corner point solutions it is possible that there are multiple optimal solutions, other than corner point ones, when the objective function has the same slope as one of the binding constraints. In this example, if we were maximizing 2X + Y, any combination of non-negative X and Y values in which 2X + Y = 4 would maximize that function.

Before leaving this problem, it should be obvious that if this objective were to be minimized, the optimal solution would result when the objective line in the plot would be lowered until it went through the origin of the plot where X = Y = 0.

8.2 Dual Variables

Of interest to many using optimization models involving constraints is the sensitivity of the objective function value to changes in bounds of those constraints. In this model, the upper bound on the constraint 2X + Y is 4. With 4 as an upper bound on that constraint, the maximum value of the objective function X + Y is 4. If the upper bound were 5 instead of 4, the maximum value of the objective function would be 5, an increase of 1. Similarly, if 4 were decreased to 3, the objective function value would decrease by 1. This change in the objective function per unit change in the bound on the constraint is called the shadow price or dual variable or Lagrange multiplier associated with that constraint. It signifies the change in the objective function value associated with a unit change in the upper or lower bound of the constraint.

For any linear or non-linear model containing a vector of decision variables X and m constraints of the form

$$ \begin{gathered} {\text{Maximize}}\;{\text{or}}\;{\text{Minimize}}\; {\text{F}}\left( {\varvec{X}} \right) \hfill \\ {\text{Subject}}\;{\text{to}}: \;{\text{g}}_{{\text{i}}} \left( {\varvec{X}} \right) \le \;{\text{or}}\; \ge {\text{b}}_{{\text{i}}} \quad {\text{for}}\;{\text{i}}\; = \;{1},\;{2},\; \ldots ,\;{\text{m}}. \hfill \\ \end{gathered} $$

each dual variable of each constraint i signifies the change in the optimal value of the objective function, F(X), given a unit change in the value of b_i. It is the slope of the objective function at the optimal values of the decision variables when the constraint equals b_i. For non-linear models, the shadow price of any binding constraint i changes as b_i changes. Hence, the shadow price applies for only small changes in b_i relative to the value of b_i. For linear models, the range of change in b_i for which the value of the shadow price applies can be larger and will depend on the particular model.

Computer programs, such as Solver in Excel, used to solve optimization models not only provide the optimal values of the decision variables X, assuming they exist, but also the values of the shadow prices, also called dual variables or dual prices or Lagrange multipliers) associated with each constraint i. Again, these values are based on a unit change in the value of each b_i. For linear models, the output of Solver also specifies the range of each b_i value over which its dual variable value applies (See Chap. 6).

8.3 A Production Model

Suppose for a community fundraising project, two products are to be produced, Product A and Product B. Each product is offered for sale for $60 and $80, respectively. Each product takes one unit of wood and the total amount of wood available is 80. Making each Product B requires 2 h of labor, half of what product A requires to make, and the total amount of labor hours available is 280. Desired are the amounts of Product A, denoted as A and Product B, denoted as B, that maximize the total income (Fig. 8.3).

Fig. 8.3

Putting things together after determining how much wood and labor are available. (Public domain. Bureau of Labor Statistics (BLS)) www.bls.gov/ooh/production/woodworkers.htm

This optimization problem can be expressed as

$$ \begin{gathered} {\text{Maximize}}\;{\text{income}} = {6}0A + {8}0B \hfill \\ \quad {\text{Subject}}\;{\text{to}}: \hfill \\ \quad {\text{Material}}\;{\text{Constraint}}: \;A + B \le {8}0 \hfill \\ \quad {\text{Labor}}\;{\text{Constraint}}: \;{4}A + {2}B \le {28}0 \hfill \\ \quad {\text{Non - negativity}}\;{\text{Constraints}}: \;A \ge 0,\; B \ge 0 \hfill \\ \end{gathered} $$

Since this is another two-variable problem, we can solve it graphically (Fig. 8.4).

As one can see from this plot, only two constraints of the four are binding, namely A + B ≤ 80 and A ≥ 0 meaning that instead of inequalities they are equalities. Thus, the dual variable value of the labor constraint is 0. Having more labor doesn’t increase income. But having another unit of wood, in this case, would increase income by $80. As seen from this plot, this rate of change of $80 per unit of wood would apply from 0 up to a supply of wood of 140. After that labor would be limiting the total obtainable income. If we were forced to produce a unit of A, we would have to produce one less B and the maximum total income would decrease by 80–60 = 20. This is called the ‘reduced cost’ of A. Reduced costs only apply to variables whose optimal values are 0.

Also, evident from Fig. 8.4 is that if the coefficient of A, 60, in the objective function, 60A + 80B, increased by 20, or if the coefficient of B decreased by 20, then any non-negative values of A and B that summed to 80 would be optimal. Any additional changes until the coefficient of A is twice that of B would result in an optimal solution where the two constraints intersect. At this point, A is 60 and B is 20. Beyond that, the optimal solution would be at A = 70 and B = 0.

Fig. 8.4

Graphical solution to the production model

8.4 Crop Production

Each year farmers have to decide what crops to grow, where, and how much. Assume a farmer can grow three types of grains (Fig. 8.5). The farmer wants to determine how much of each type of grain to grow taking into account the labor, land and water resource requirements, the resources available, and the incomes per hectare of each crop. The resource requirements for each crop, the available resources, and the incomes per hectare of each crop are given in Table 8.1.

Fig. 8.5

Harvesting a grain crop from farmland. CC BY-SA 3.0. https://en.wikipedia.org/wiki/Harvest#/media/File:Agriculture_in_Volgograd_Oblast_002.JPG

Table 8.1 Data required to determine how much of each grain crop to grow to maximize total income

Letting the decision variables be the number of hectares of each crop, denoted as Corn, Wheat, and Oats, an optimization model for finding the hectares of each crop that maximize total income can be written as

$$ \begin{gathered} {\text{Maximize}}\;{\text{total}}\;{\text{income}}:\; {4}00\;Corn + {2}00\;Wheat + {25}0\;Oats \hfill \\ {\text{Subject}}\;{\text{to}}: \hfill \\ \quad \quad \quad \quad Corn + Wheat + Oats \le {625} \;{\text{land}}\;{\text{constraint}}. \hfill \\ \quad \quad \quad \quad {3}\;Corn + Wheat + {1}.{5}\;Oats \le {1}000 \;{\text{water}}\;{\text{constraint}}. \hfill \\ \quad \quad \quad \quad 0.{8}\;Corn + 0.{2}\;Wheat + 0.{3}\;Oats \le {3}00 \;{\text{labor}}\;{\text{constraint}}. \hfill \\ \end{gathered} $$

The non-negativity constraints will obviously be satisfied and hence need not be included in the model.

Using a computer to solve this model, one solution is

Maximum objective value: 162500.0
Variable	Value	Reduced cost
Corn	187.5000	0.000000
Wheat	437.5000	0.000000
Oats	0.000000	0.000000

Constraint	Slack or surplus	Dual variable
Land	0.000000	100.0000
Water	0.000000	100.0000
Labor	62.50000	0.000000

This solution shows that both land and water limit how much the farmer can grow. The dual variable values show that If the farmer could add one more unit of water, or land, the income would increase by $100. In addition, the solution shows no oats being grown, yet forcing a unit of oats to be grown does not reduce the total income, as indicated by Its ‘reduced cost’ of 0. This suggests that there are multiple optimal solutions, i.e., different values of corn, wheat, and oats that give the same maximum total income.

For example, if a constraint were added forcing the hectares of oats to be 100, the solution becomes

Objective value: 162500.0
Variable	Value	Reduced cost
Corn	162.5000	0.000000
Wheat	362.5000	0.000000
Oats	100.0000	0.000000

Constraint	Slack or surplus	Dual variable
Land	0.000000	100.0000
Water	0.000000	100.0000
Labor	67.50000	0.000000
Oats required	0.000000	0.000000

The range of optimal solutions is shown in the sketch below (Fig. 8.6)

Fig. 8.6

Different combinations of each crop that produce the same maximum income

8.5 Police Scheduling

A community has minimum requirements for the number of police (Fig. 8.7) that need to be on duty during each 4-h period. These requirements are shown in Table 8.2. The actual number employed cannot be less than that. Each police person works 8 consecutive hours per day. (For simplicity assume no days off.) There are no part-time police, and union regulations prohibit split shifts. The problem is to find a daily schedule that employs the fewest number of police officers. Table 8.2 also defines the variables, xt, used to represent the number of police who begin their work at hour t.

Fig. 8.7

Police providing a public service. Creative Commons Attribution 2.0 Generic license. https://commons.wikimedia.org/wiki/File:Beijing_Police_is_helping.jpg

Table 8.2 Data required to determine how many police to hire in each 4-h period of a day

The objective is to find the minimum total number of police needed to be hired throughout the day.

$$ {\text{Minimize}}\; x0 \, + \, x4 \, + \, x8 \, + \, x12 \, + \, x16 \, + \, x20; $$

Subject to the requirements for each 4-h period during the day:

$$ \begin{gathered} {\text{Period }}0000{-}0{4}00 \quad X20 + x0 \ge {4}0 \hfill \\ {\text{Period }}0{4}00{-}0{8}00 \quad x0 + x4 \ge {1}0 \hfill \\ {\text{Period }}0{8}00{-}{12}00\quad x4 + x8 \ge {15} \hfill \\ {\text{Period 12}}00{-}{16}00 \quad x8 + x12 \ge {1}0 \hfill \\ {\text{Period 16}}00{-}{2}000 \quad x12 + x16 \ge {25} \hfill \\ {\text{Period 2}}000{-}{24}00 \quad x16 + x20 \ge {3}0 \hfill \\ \end{gathered} $$

One solution is as shown in Table 8.3.

Table 8.3 An optimal solution to the police scheduling problem, requiring 80 police

Once again zero ‘reduced costs’ for variables ×8 and ×16 whose values are 0 suggests there are many optimal solutions requiring a total police force of 80. Hence, it is possible to alter the times some police can start their shifts to better satisfy other personnel or police department objectives, if any, without requiring more police. For example, if it were desired-to minimize the maximum shift size while also minimizing the total number of police needed, one solution is given in Table 8.4.

Table 8.4 Another optimal solution to the police scheduling problem, requiring 80 police

This policy tends to reduce the variation in the number of police beginning their work in each time period.

8.6 Project Scheduling

Large infrastructure projects involving many personnel and machines and materials are commonly divided into a number of tasks. Each task needs to be completed before the entire project is completed. Of interest to project managers is when to begin each task and how to allocate the personnel, machines, and materials among tasks to minimize the total time and cost needed to complete the entire project (Fig. 8.8).

Fig. 8.8

Deciding when to schedule various project tasks to complete an entire project. iStock licence number 2075982143

A number of methods exist to estimate task start times. One is to create an optimization model that when solved will identify the task start times that minimize the total project time. Clearly, if each task had to be done one after another, the total project time would simply be the sum of all the task durations. In reality, some tasks can be worked on at the same time, or stated another way, what tasks need to be completed before others can begin depends on each particular task. The constraints of the model need to identify the sequencing of the tasks.

To illustrate, assume a particular project consists of 6 distinct tasks. One task can begin right away (task A), and all the other tasks can’t begin before some of the others are completed. These conditions along with the expected duration, in weeks, of each task, are given in Table 8.5 below. The plot also shows the necessary sequencing as specified in the table.

Table 8.5 Sequence and duration of project tasks

To find the minimum number of weeks, T, required to complete the project and the corresponding starting times of each task, designated by A, B, C, D, E, and F, the following linear model can be solved:

$$ \begin{gathered} {\text{Minimize}}\;T \hfill \\ {\text{Subject}}\;{\text{to}}: \hfill \\ \quad \quad \quad \quad B \ge A + {5} \hfill \\ \quad \quad \quad \quad C \ge A + {5} \hfill \\ \quad \quad \quad \quad D \ge B + {3} \hfill \\ \quad \quad \quad \quad D \ge C + {6} \hfill \\ \quad \quad \quad \quad E \ge C + {6} \hfill \\ \quad \quad \quad \quad F \ge D + {7} \hfill \\ \quad \quad \quad \quad F \ge E + {4} \hfill \\ \quad \quad \quad \quad T \ge F + {2} \hfill \\ \end{gathered} $$

Its solution is shown in Table 8.6.

Table 8.6 Solution of project planning problem showing start times of each task and total project time, T

The minimum total project time, T, is 20. In any project such as this one, usually, only some of the tasks determine the total project time. In this example, this sequence of tasks is A, C, D, and F. Tasks B and E could start somewhat later if they do not alter the start times of the following tasks. This may be advantageous with respect to the management of personnel, material or machines. Of course, it may be advantageous to extend the total project time if cost savings result. However, extending total project completion times could result in penalties.

Assume that a penalty of 2000 per week will apply for each week the project time is over 18. Now the question is can this project time be reduced and if so at what cost, and will that cost be less than the penalty. The objective becomes one of minimizing the total additional project cost of exceeding the target time of 18. Assume the cost of reducing the duration D_i of task i by $\Delta_{{\text{i}}}$ is a known function, C_i($\Delta_{{\text{i}}}$), of that reduction. The objective of the model now is one of finding the task reductions, $\Delta_{{\text{i}}}$, that minimize the sum of task reduction costs, $\sum_{{{\text{i}}\, = \,{\text{A,}}\,{\text{F}}}} \left( {{\text{C}}_{{\text{i}}} (\Delta_{{\text{i}}} )} \right)$, and the penalty cost, 2000 (T − 18).

$$ \begin{gathered} {\text{Minimize}} \quad {2}000\;\left( {T{-}{18}} \right) + \sum_{{{\text{i}} = {\text{A}},{\text{ F}}}} ({\text{C}}_{{\text{i}}} (\Delta_{{\text{i}}} )) \hfill \\ {\text{Subject to}}: \hfill \\ \quad \quad B \ge A + 5 - \Delta_{A} \hfill \\ \quad \quad C \ge A + 5 - \Delta_{A} \hfill \\ \quad \quad D \ge B + 3 - \Delta_{B} \hfill \\ \quad \quad D \ge C + 6 - \Delta_{C} \hfill \\ \quad \quad E \ge C + 6 - \Delta_{C} \hfill \\ \quad \quad F \ge D + 7 - \Delta_{D} \hfill \\ \quad \quad F \ge E + 4 - \Delta_{E} \hfill \\ \quad \quad T \ge F + 2 - \Delta_{{\text{F}}} \hfill \\ \end{gathered} $$

This model assumes the total project time, T, will be no less than 18. If we were not sure that T would be at least 18, then we could add the constraint defining the positive difference, P, of T − 18.

$$ T - 18 \le P\;{\text{and}}\; P \ge 0. $$

The objective function would now be to

$$ {\text{Minimize}} \;{2}000\;P + \sum_{{{\text{i}} = {\text{A}},{\text{ F}}}} ({\text{C}}_{{\text{i}}} (\Delta_{{\text{i}}} )). $$

This modification makes sure there is no negative penalty if T < 18.

8.7 Trash and Pollution

The management of trash is an issue facing every community. Assume a particular city burns a total of 3000 tons of trash per day in three incinerators. All three have antipollution devices. Their emissions differ, as shown in Table 8.5. At present, all three incinerators are operating at full capacity. The remainder of the city’s trash, another 1500 tons per day, is dumped into a sanitary landfill area. This landfill option is very expensive compared to incineration. The city is under court order to reduce the total emissions of sulfur dioxide to 400,000 units per day and particulate emissions to 50,000 per day. These maximum allowable emissions are less than what is being discharged at the present time. The city wants to know the most economical way to meet these standards (Fig. 8.9 and Table 8.7).

Fig. 8.9

Burning trash at an incineration plant. Credit Pixabay/CC0 public domain. https://phys.org/news/2021-11-life-carbon-capture.html

Table 8.7 Capacity and emission data pertaining to the incineration of trash

Let the variables A, B, C be the tons of trash burned per day in incinerator A, B, and, C, respectively. The city’s objective is to burn as much trash as possible while meeting the emission and capacity constraints.

This is an optimization problem that can be written as

$$ \begin{gathered} \begin{array}{*{20}c} {{\text{Maximize}}\;A + B + C} & {{\text{Amount of trash burned per day}}.} \\ \end{array} \hfill \\ {\text{Subject}}\;{\text{to}}: \hfill \\ \begin{array}{*{20}c} {{25}0A + {15}0B + {22}0C \le {4}00,000} & {\text{maximum sulfur dioxide emission}} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {{2}0A + { 3}0B + {24}C \le {5}0,000} & {\text{maximum particulate emission}} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {A \le {12}00 } & {\text{maximum capacity of incinerator A}} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {B \le {8}00} & {\text{maximum capacity of incinerator B}} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {C \le {1}000} & {\text{maximum capacity of incinerator C}} \\ \end{array} \hfill \\ \end{gathered} $$

The solution of this model is given in Table 8.8.

Table 8.8 Solution to incinerator problem

The solution shows that all three incinerators should be used, but only B at capacity. The dual variables of the emission constraints indicate the additional tons of trash that could be burned per unit increase in the emission standards. For example, if 100 more units of SO₂ could be released, then 0.25 more tons of trash could be burned. Depending on the cost savings that would result from reducing the amount of trash taken to the landfill, the city might wish to argue for less strict standards. Alternatively, it might offer to further reduce its emissions in the interest of improving the public’s health or reducing the adverse impacts of climate change.

8.8 Modeling Fixed Cost Problems

Minimizing costs is a common objective, among others, in optimization models. Many cost functions include fixed costs, as illustrated in Fig. 8.10. In addition, some decision problems involve finding optimal integer variable values instead of continuous values. For example, allocating fractions of trucks or workers to various construction sites in a community makes no sense. Non-negative integer variables can take on values 0, 1, 2, etc. Variables having only integer values must be specified as such as part of the input to the computer program, such as Solver in Excel, used to solve the model. Binary integer variables that can take on only values of 0 or 1 must also be designated as such in computer programs used to solve any model containing them. Non-negative integer variables constrained to be no greater than 1 can also represent binary (0, 1) variables.

Fig. 8.10

A cost function showing economies to scale and fixed initial costs that apply if X > 0

Many cost functions contain fixed costs, such as shown in the sketch below. In this sketch, the variable costs are linear with slopes C_i and the fixed costs are C_0i.

Each cost function i equals

$$ \begin{aligned} {\text{Cost}}_{{\text{i}}} & = {\text{C}}_{{0{\text{i}}}} + {\text{ C}}_{{\text{i}}} X\quad {\text{if}}\;X > 0. \\ & = 0\quad {\text{otherwise}}. \\ \end{aligned} $$

The fixed costs, C_0i, only apply if the variable X is greater than 0. If X = 0, the Cost_i = 0.

The use of binary variables makes it possible to include such cost functions in linear optimization models. For example, suppose one wants to find the minimum cost associated with a value of the variable X in Fig. 8.11. The answer is obvious just from looking at the two cost functions and picking the one having a lower value. If the value of X is to the left of the breakeven point where the two cost functions meet and have the same value, clearly Cost₂ having the lower fixed cost is cheaper. Otherwise, if the value of X is to the right of the breakeven point, Cost₁ having the higher fixed cost is cheaper.

Fig. 8.11

Two cost functions having fixed costs C_0i and linear variable costs whose marginal values (slopes) are C_i

If we entered either cost function into a computer to have it identify the cost associated with any given value of X, it would give us the correct answer unless the value of X was 0. In that case, it would give us the fixed cost. Hence, we need some way to let the computer know that if X = 0, the total cost is 0. That constraint needs to be included in the model, and ideally, that constraint should be linear.

One approach for doing this is to multiply the known fixed cost by an unknown binary variable. Let Z be that binary variable. Considering just one cost function, the objective becomes

$$ {\text{Minimize}} \; {\text{Cost}} = {\text{C}}_{0} Z + {\text{ C}}X, $$

for any value of X and where Z can be either 0 or 1.

When the binary Z variable is 1, the fixed cost, C₀, is included in the total cost. When the value of Z is 0, it is not included in the cost. Hence, if the cost is to be minimized the value of Z will be 0 no matter what the value of X is. The challenge is to create a linear constraint that will force that binary variable Z to equal 1 when X is strictly greater than 0. Otherwise, as just stated, since the cost function is to be minimized, that binary variable will want to be 0.

If we require

$$ X \le { 999}Z $$

then if the value of X is greater than 0, the binary variable Z must equal 1. This constraint also defines the upper bound on the value of X. If there is no upper bound, then any large number that will exceed any value X could assume can be used. In this example, it is 999.

This trivial example can be made more interesting by assuming the two cost functions shown in Fig. 8.11 represent the cost of buying and operating two cars that are for sale. For each car j, the fixed cost, C_0j, is the annual value of the purchase price, and the variable cost, C_jX_j is the annual operating cost of driving it X_j miles. Car 1 is more expensive to buy but cheaper to operate. Car 2 is less expensive to purchase but more expensive to operate. Whichever car is selected, it will be driven over a three-year period in which the predicted miles the car will be driven each year will differ. The question is which car will result in a lower present value of the total annual cost.

If there were no difference in fixed costs, it is obvious the car with the smaller variable operating cost (slope C_j) would be the less expensive car to buy. But a difference in fixed costs makes a difference. If the predicted miles driven include some that are less than the breakeven point and others in other years that are greater than the breakeven point, which car to buy may not be so obvious.

To model this problem, let M_y be the predicted non-zero number of miles that are expected to be driven in year y. If there were only one car to consider, then the present value of the total cost over the three years is

$$ {\text{Cost}} = {\text{C}}_{0} + {\text{CM}}_{{1}} /\left( {{1} + {\text{i}}} \right) + {\text{CM}}_{{2}} /\left( {{1} + {\text{i}}} \right)^{{2}} + {\text{CM}}_{{3}} /\left( {{1} + {\text{i}}} \right)^{{3}} {-}{\text{R}}/\left( {{1} + {\text{i}}} \right)^{{3}} $$

where i is the annual interest rate and R is the resale value at the end of 3 years. One could plug in the values of C₀, C, and R for each car and compare the results to determine which car would be less expensive. It would also make sense to vary the assumed values of these parameters, along with the M_y estimates, to see how sensitive the decision of which car to buy is to those assumed, but uncertain, values.

Alternatively, one could include both cars in the same model and have its solution indicate which car to buy. This requires allowing the use of both cars. Let the variable X_jy be the miles driven using car type j in year y. Their sum in each year y must be at least M_y. Let Z_j be a binary variable associated with car type j. Now the objective of minimizing the present value of the total costs can be written as

$$ \begin{gathered} {\text{Minimize}}\;{\text{Cost}} = \sum_{{\text{j}}} \left[ {{\text{C}}_{{0{\text{j}}}} Z_{{\text{j}}} + \sum_{{\text{y}}} \left\{ {{\text{C}}_{{\text{j}}} X_{{{\text{jy}}}} /\left( {{1} + {\text{i}}} \right)^{{\text{y}}} } \right\}{-}{\text{R}}_{{\text{j}}} /\left( {{1} + {\text{i}}} \right)^{{3}} Z_{{\text{j}}} } \right] \hfill \\ {\text{Subject}}\;{\text{to:}} \hfill \\ \begin{array}{*{20}l} \sum\limits_{{\text{y}}} {X_{{{\text{jy}}}} } \le \left( {\sum\limits_{{\text{y}}} {{\text{M}}_{{\text{y}}} } \;{\text{or}}\;{\text{more}}} \right)Z_{{\text{j}}} \,\, \forall {\text{j}}\;{\text{forcing}}\;Z_{{\text{j}}} \;{\text{to}}\;{\text{be}}\;1\;{\text{if}}\;{\text{car}}\;{\text{type}}\;{\text{j}}\;{\text{is}}\;{\text{driven}}, \hfill \\ {\text{i}}.{\text{e}}.,\;{\text{any}}\;X_{{{\text{jy}}}} > 0. \hfill \\ \\ \end{array} \hfill \\ \begin{array}{*{20}c} {\sum_{{\text{j}}} X_{{{\text{jy}}}} \ge {\text{M}}_{{\text{y}}} } & {\forall {\text{y}} \;{\text{mileage}}\;{\text{requirement}}\;{\text{in}}\;{\text{each}}\;{\text{year}}\;{\text{y}}.} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {Z_{{\text{j}}}\; {\text{is binary}}} & {\forall {\text{j}} \;{\text{associated}}\;{\text{with}}\;{\text{fixed}}\;{\text{cost}}\;{\text{and}}\;{\text{resale}}\;{\text{parameters}}} \\ \end{array} \hfill \\ \end{gathered} $$

The solution of this linear model, once the values of the fixed and unit variable costs, the interest rate, the miles to be driven in each year, and the annual resale value, are specified, will show that only one of the binary variable values, Z_j, is 1. The less expensive car j is the one whose Z_j = 1. The constraint Z₁ + Z₂ ≤ 1 insuring only one, if any, the car is to be used, can be added to the model’s constraints but it is not necessary. Selecting both cars, while feasible, would clearly increase the total cost. Just how sensitive the choice of car is to the mileage requirements will be indicated by the applicable ranges of the dual variable values of the second set of constraints.

There are many more ways of using integer and binary variables in models. Chapter 9 contains more information on how various non-linear terms and functions can be approximated by linear ones using these integer and binary variables. Again, the motivation for doing this is evident when trying to solve large non-linear optimization problems. At the same time, one should minimize the use of integer variables to the extent possible, for they too can challenge some computer programs designed to solve mixed-integer models containing both continuous and integer variables. Rounding continuous variable values to their nearest integer values does not always guarantee optimal or even feasible solutions (Fig. 8.12).

Fig. 8.12

Happiness is assuming the world is linear!

Exercises

• 1. Bake Sale

  For a community fundraising event cakes and pies are to be sold. Find how many cakes and pies should be baked to maximize total income.

  Let A and B be the number of cakes and B the number of pies produced. The following data apply:

  Product	A	B
  Income per item	$6	$8
  Pans required per item	1	1
  Labor required per item	2	4

  There are 80 pans and 280 person hours available, and because of limited cake ingredients, no more than 50 cakes (A) can be produced.

• 2. Diet model

  You manage the local SPCA (Society for the Prevention of Cruelty to Animals) that keeps stray dogs. Your dogs need to eat and there are two varieties of dog food available: foods D and C. Their unit costs are $1.10 and $0.90, respectively. Your job is to find the least cost combination of pounds of D and C for each dog that meets various nutrition constraints shown in the table below. The amounts of the ingredients shown are in each pound of D and C.

  Ingredient	D	C	Daily minimum/dog/day
  Protein	3 oz	4 oz	8 oz
  Carbohydrate	5 oz	12 oz	11 oz
  Iron	30 mg	35 mg	100 mg

• (a) First, describe your objective function and constraints in words.

• (b) Define the parameters and variables, and their units, that you can use to create a mathematical model.

• (c) Express the model mathematically.

• (d) Show the solution by plotting the constraints and objective function on a graph of D versus C.

• 3. Labor Scheduling

  A social welfare program involves three projects. Projects A, B, and C require 18, 12, and 30 person months to complete. Four qualified social workers are available to work on these projects.

  Their monthly salaries are $3000, $3500, $3200, and $3900, respectively.

  All projects must be completed in 18 months, and each social worker can be assigned only to one project in each 6-month period. Multiple workers can be assigned to the same project.

  Find the allocation of each worker to each job that minimizes the total cost of completing the projects.

• 4. A transportation problem

  Assume there are 4 warehouses containing Personal protective equipment, commonly referred to as ‘PPE,’ supplies being used at 6 hospitals. Given the supplies available at each warehouse and the demand at each hospital, and the unit costs of transporting them (all known values), construct a model to determine how much gets transported from each warehouse to each hospital that minimizes the total transportation costs.

  To do this, you need to make up your notation for all variables and parameters. Plug in values of the parameters of the model and solve it to find how much is shipped from each warehouse to each hospital.

  What condition must be satisfied for your model to be feasible?

• 5. Forest management

  A particular State Forest has four different subareas whose characteristics such as species composition, age distribution, drainage, soil characteristics, etc., are similar. The areas of these subareas are known. Recent growth studies have produced predictions of the volumes per hectare for each subarea for the next 50 years. The forest manager is responsible for defining a cutting schedule that will produce a steady supply of logs to be cut into lumber over the 50-year life span of the forest. Her goal is to find the maximum constant amount of wood (volume) that can be converted to lumber every year.

  Develop a model for determining just how much volume can be cut in each subarea in each of 5 10-year periods. Once any area is cut trees in that area cannot be cut over again for another 50 years. Cutting trees from the forest in this sustainable way increases water yields, the quality of wildlife habitat, and timber income.

  Define the variables, parameters, and constraints you need, and use them to build and solve a model for identifying the best cutting schedule—i.e., how much to cut, where, and when.

• 6. Water Quality Management Model

  Find the wastewater treatment efficiencies at sites 1 and 2 that meet stream quality standards at sites 2 and 3 at a minimum total cost. Currently, there is no treatment. All the wastewaters at sites 1 and 2 are discharged into the stream.

  

  Available Data:

  Streamflow = 1000 m³/day at all sites. 1 kg/day/1000 m³/day = 1 mg/l;

  Fraction of waste discharged into the stream at site 1 that reaches site 2: 0.25

  Fraction of waste discharged at site 1 that reaches site 3: 0.15

  Fraction of waste at and discharged into the stream at site 2 that reaches site 3: 0.60

  Limits of treatment: removal of 30 % required, but no more than 90%, for both sites. The initial concentration just upstream of site 1 is 32 mg/l.

  Can you find the least cost solution that meets the quality standards without knowing the cost functions for treatment?