Baker K.R. Optimization Modeling with Spreadsheets

Подождите немного. Документ загружается.

The optimal solution, shown in Figure 3.2, achieves the minimum cost of

$13,830. All demand constraints in this solution are binding, even though we per-

mitted the model to send more than the requirement to each warehouse. This result

makes intuitive sense because shipping more than is required to any warehouse

would merely incur excess cost. Once we understand why there is no incentive to

exceed demand, we can anticipate that there will be some excess capacity in the sol-

ution. This follows from the fact that total capacity comes to 40,000 cartons, while

total shipment volume comes to only 39,000, as conﬁrmed in cell G15. In particular,

capacity constraints are binding at Pittsburgh and Minneapolis, but an excess capacity

of 1000 cartons remains at Tucson.

The solution, shown on the original network in Figure 3.4, may be surprising to

someone who has not previously seen the transportation model. Although there are 12

possible shipment routes in the model, the optimal solution uses onlysix. The ﬂexibility

in having three possible sources for meeting each demand is not fully utilized. After

a little further thought, this pattern makes sense because many of the unused routes

are expensive. Nonetheless, the solution uses the TA route, on which the unit cost is

$0.65, and avoids the PC route, where the unit cost is $0.28. Such choices might be

unexpected, but they reﬂect the systems view that an optimization model can take.

As in other linear programming solutions, the transportation model provides both

tactical and strategic information. If Goodwin Manufacturing had to implement a

distribution plan immediately, then the plan shown in Figure 3.2 would be the cost-

minimizing plan that its management seeks, representing the tactical interpretation of

the model. However, if there is time to explore some changes in the given information,

as strategic initiatives, then to reduce total transportation cost, we should explore ways

of lowering one of the demand requirements or ways of adding capacity to Minneapolis

Figure 3.4. Optimal ﬂows for Example 3.1.

76 Chapter 3 Linear Programming: Network Models

or Pittsburgh because these actions loosen the binding constraints. At the margin,

adding capacity at Tucson will not help in reducing total cost. Thus, by using linear

programming to solve its transportation problem, Goodwin Manufacturing can deter-

mine the cheapest way to meet customer demands in the short run. It can identify some

economically attractive strategic initiatives as well.

Example 3.1, which contains three sources and four destinations, shows how to

build a suitable spreadsheet for the transportation problem. It is straightforward to

adapt the spreadsheet design to any number of sources and any number of destinations.

Again, the key formulation step is to display cost parameters and shipment quantities

as separate arrays.

3.2. THE ASSIGNMENT MODEL

An important special case of the transportation problem has all capacities and all

requirements equal to one. Moreover, the number of sources and the number of

destinations are the same. This special case is known as the assignment problem.

The one-to-one matching structure of an assignment is a practical problem. In

addition, it arises as a portion of a more complicated model, as we shall see later.

For the most part, we can set up and solve this special case in the same way that we

dealt with the transportation problem. Consider the example of the Europa Auto

Company.

EXAMPLE 3.2

Europa Auto Company

Europa Auto Company is an automaker with six manufacturing plants and six vehicles to pro-

duce this year. The ﬁrm has learned that it makes sense to produce each vehicle at a unique plant,

even though some of the plants are older and less efﬁcient than others. For each possible assign-

ment of a vehicle to a plant, the ﬁrm has estimated the annual cost (in millions of dollars) of

implementing the assignment. The cost data take the form shown in the following table,

which identiﬁes the products by number. The automaker’s objective is to minimize the total

cost of the assignment.

Product

Compact Coupe Sedan SUV Truck Van

Plant 1 2 3 4 5 6

Akron 80 56 43 62 46 58

Buffalo 94 50 88 64 63 52

Columbus 94 46 50 40 55 73

Detroit 98 79 71 65 91 59

Evansville 61 59 89 98 45 52

Flint 77 49 65 95 72 91

3.2. The Assignment Model 77

We can think of an assignment as a selection of six numbers from the cost table,

one from each row and one from each column. (Because the number of products is the

same as the number of plants, we can think of either assigning plants to products or

assigning products to plants.) The total cost associated with such an assignment is

the sum of the numbers selected. This is merely another way of saying that the problem

is a special transportation problem in which the row “capacities” are each one and the

column “requirements” are also one. As such, we can construct a ﬂow diagram to

represent the decision problem in much the same way as in the transportation model

of Figure 3.1. The diagram for the automaker example is shown in Figure 3.5,

where each of the 36 arcs in the diagram represents part of a potential assignment.

To construct the assignment model algebraically, we deﬁne our decision variables

as the possible plant–product combinations, A1, A2, ..., F6. Our objective function

(denoted z) is the total cost of an assignment, which can be expressed as the sum

of 36 products. Each term in this sum is an assignment cost multiplied by a decision

variable.

Total cost ¼ z ¼ 80A1 þ 56A2 þ 43A3 þþ72F5 þ 91F6

There are 12 constraints, 6 for the plants and 6 for the products. The row (plant) con-

straints are as follows.

A1 þ A2 þ A3 þ A4 þ A5 þ A6  1

B1 þ B2 þ B3 þ B4 þ B5 þ B6  1

C1 þ C2 þ C3 þ C4 þ C5

þ C6  1

Figure 3.5. Flow diagram for Example 3.2.

78 Chapter 3 Linear Programming: Network Models

D1 þ D2 þ D3 þ D4 þ D5 þ D6  1

E1 þ E2 þ E3 þ E4 þ E5 þ E6  1

F1 þ F2 þ F3 þ F4 þ F5 þ F6  1

These constraints could also be written as equations. Meanwhile, the column (product)

constraints are as follows.

A1 þ B1 þ C1 þ D1 þ E1 þ F1  1

A2 þ B2 þ C2 þ D2 þ E2 þ F2  1

A3 þ B

3 þ C3 þ D3 þ E3 þ F3  1

A4 þ B4 þ C4 þ D4 þ E4 þ F4  1

A5 þ B5 þ C5 þ D5 þ E5 þ F5  1

A6 þ B6 þ C6 þ D6 þ E6 þ F6  1

Again, these constraints could be written as equations without affecting the problem’s

solution.

Alternatively, for a more compact algebraic representation, we can use x

to rep-

resent the assignment decisions. Speciﬁcally, x

¼ 1 if vehicle j is made at plant i.

In addition, we let c

denote the cost of assigning plant i to vehicle j. The index i

corresponds to a row number and the index j corresponds to a column number. Then,

we can express the objective function—the system-wide cost of the assignment—as

the following sum

z ¼

The constraints become

 1, for each plant i

 1, for each vehicle j

Because the assignment model is a special case of the transportation model with total

capacity equal to total demand, we can be sure that the capacity and demand con-

straints will be binding. (This compact form of the problem statement will be useful

to us in later chapters.)

The assignment problem is to minimize z subject to the 12 constraints on the

variables. In neither of these formulations are there explicit considerations that would

help us avoid fractional values for the decision variables. Although our problem state-

ments allow the decision variables to be fractional, their optimal values will always be

either zero or one, as we shall discuss later.

Figure 3.6 shows a spreadsheet model for the assignment problem. It resembles

the spreadsheet for the transportation model introduced in Figure 3.2. The upper

table contains a 6  6 array of assignment costs. The decisions are shown in the

lower 6  6 table and highlighted. To the right of each row is the row sum and below

3.2. The Assignment Model 79

each of the columns is the column sum. As in the transportation model (Figure 3.2),

these cells use the SUM formula. Finally, in cell B24, we highlight the value of the

objective function, or total cost, which is computed as the SUMPRODUCT of the

cost array and the decision array.

Conceptually, there are capacities of one for each plant and requirements of one

for each product, in analogy to the transportation model. Rather than include these

parameters on the spreadsheet itself, they are entered as RHS constants in the con-

straints. Normally, it is not good practice to enter RHS constants in the task pane,

because we prefer to show parameters of the model on the spreadsheet itself, where

we might want to explore some what-if questions. However, we make an exception

here because the right-hand sides will not change: values of one represent the essence

of the assignment problem. The speciﬁcation of the model is as follows.

Figure 3.6. Spreadsheet model for Example 3.2.

80 Chapter 3 Linear Programming: Network Models

Objective: B24 (minimize)

Variables: C15:H20

Constraints: I15:I20  1

C21:H21  1

The LT constraints assure that at most one product is assigned to each plant, and the

GT constraints assure that each plant has at least one product assigned to it. (As

mentioned earlier, we could also express all of the constraints as equations.)

Figure 3.6 displays the optimal solution, which achieves a minimum total cost of

$314 million. This optimum is achieved by assigning the Sedan to Plant A, the Coupe

to B, the SUV to C, the Van to D, the Truck to E, and the Compact to F. By solving this

linear programming problem, Europa can ﬁnd an economic assignment of vehicle

models to plants, thus potentially saving millions of dollars over ad hoc assignment

methods.

The assignment problem often arises when people must be assigned to tasks. The

model assumes that quantitative scores apply to each person– task combination and

the objective is to ﬁnd a minimum (or maximum) total score. One classic application

isthe assignment of four swimmers to laps in a medley relay,where eachlap corresponds

to a different stroke, and each swimmer has a lap time for each stroke. The assignment

model has also been used to assign workers to shifts, courses to time slots, airline crews

to ﬂights, and purchase contracts to supplier bids. For our purposes in modeling, the

assignment problem is simply a practical special case of the transportation problem.

3.3. THE TRANSSHIPMENT MODEL

The assignment problem turned out to be a simpliﬁed version of the transportation pro-

blem, specialized to unit demands and unit supplies. By contrast, the transshipment

problem is a complicated version of the transportation problem, containing two

stages of ﬂow instead of just one. In Figure 3.1—our diagram for the transportation

problem—the system contains two levels (plants and warehouses), and all the ﬂow

takes place in one stage, from plants to warehouses. In many logistics systems, how-

ever, there are three major levels: plants, distribution centers (DCs), and warehouses;

in such systems, the ﬂow often takes place in two stages. Consider the example of

DeMont Chemical Company.

EXAMPLE 3.3

DeMont Chemical Company

DeMont Chemical Company manufactures fertilizer in three plants, referred to as P1, P2, and

P3. The company ships its products from plants to two central DCs, designated D1 and D2,

and then from the DCs to ﬁve regional warehouses, W1 –W5. At the DCs, no demand occurs

and no capacity limits exist. Demand is associated with the warehouses, and capacities exist at

the plants. The system is described in the following two tables, one for each stage. The units

for capacity and demand are pounds of fertilizer, and the unit costs are given per pound.

3.3. The Transshipment Model

(To) DC

(From) plant D1 D2 Capacity

P1 $1.36 $1.28 2400

P2 1.28 1.35 2750

P3 1.68 1.55 2500

(To) warehouse

(From) DC W1 W2 W3 W4 W5

D1 $0.60 $0.36 $0.32 $0.44 $0.72

D2 $0.80 $0.56 $0.42 $0.40 $0.55

Requirement 1250 1000 1600 1750 1500

Figure 3.7 provides a ﬂow diagram for the system, showing the plants on the left-

hand side of the diagram, the warehouses on the right, and the DCs in the center. We

can think of this system as composed of two side-by-side transportation problems, one

involving the plants and DCs and the other involving the DCs and warehouses. All

material ﬂow occurs in two stages; that is, material ﬂows ﬁrst from a plant to a DC

and then from a DC to a warehouse. The DCs are called transshipment points, referring

to the fact that material arrives at those locations and is then subject to further ship-

ment. The essence of the transshipment structure is the coordination of the two trans-

portation stages.

Figure 3.7. Flow diagram for Example 3.3.

82 Chapter 3 Linear Programming: Network Models

The ﬂow diagram reinforces the fact that the problem involves two side-by-side

transportation problems, and we could build a spreadsheet layout showing two

stages horizontally on a worksheet, each resembling Figure 3.2 for the transportation

model. However, a vertical layout is shown in the worksheet of Figure 3.8. In this

layout, the upper portion of the worksheet corresponds to the ﬁrst stage of plant –

DC ﬂow, with costs in the left-hand array and decisions (highlighted) in the right-

hand array. Plant capacities appear, just as in the transportation problem, in this portion

of the model. Although no requirements appear, Cell F9 contains a SUMPRODUCT

formula that accounts for the total transportation cost in the ﬁrst stage. The lower

portion of the sheet corresponds to the second stage of DC –warehouse ﬂow, again

with costs in the left-hand array and decisions (highlighted) in the right-hand array.

Requirements appear in this segment of the model, and another SUMPRODUCT

formula accounts for the total cost of the second stage in cell F18. The total cost

for the entire system is the sum of the ﬁrst stage cost and the second stage cost, as

captured in cell C20.

In the upper portion of the model, the sources are represented in rows and the des-

tinations are represented in columns. In the lower portion, this convention is reversed:

the sources are represented in columns, and the destinations are represented in rows.

Under this “ﬂip ﬂopping” convention, the same columns (in this worksheet, columns

C and D for costs, or columns G and H for decisions) correspond to the DCs in both

portions of the model. The identiﬁcation of DCs with unique columns helps to

reinforce the need for coordinating the ﬂows in to and out of the DCs. This structure

also makes it relatively easy to accommodate an additional DC in the model (by

inserting a column in the spreadsheet).

Figure 3.8. Spreadsheet model for Example 3.3.

3.3. The Transshipment Model 83

The model speciﬁcation is as follows

Objective: C20 (minimize)

Variables: G6:H8, G13:H17

Constraints: I6:I8  E6:E8

I13:I17  E13:E17

G9:H9 ¼ G12:H12

The formulation contains three LT constraints (one per plant), ﬁve GT constraints (one

per warehouse), and two EQ constraints (one per DC). The optimal solution in this

example is shown in Figure 3.8 with a total cost of $12,849.50. Thus, DeMont

Chemical can take a systems view—and recognize both stages of its supply chain—

when it optimizes its distribution costs.

To repeat, the total cost in cell C20 is the sum of the ﬁrst-stage total cost and the

second-stage total cost, and the decision variables appear in two arrays. Three types of

constraints are needed in the model: a set of LT constraints for the plant capacities, a

set of GT constraints for the warehouse requirements, and a set of EQ constraints bal-

ancing the inﬂows and outﬂows at the DC locations. Although this last set of con-

straints could also be expressed in the form of inequalities, the use of equations

helps to identify the various constraints by associating a different constraint type

(LT, GT, EQ) with each of the three different roles (capacities at the plants, require-

ments at the warehouses, and transshipment at the DCs). We can also view the EQ con-

straints as expressing the key conservation law of ﬂows in networks: the total quantity

ﬂowing out of a node must always be equal to the total quantity ﬂowing in.

To describe the conservation law algebraically, we introduce some notation for

the decision variables. Let P2D1 represent the quantity shipped from plant P2 to

distribution center D1, and so on. With this notation, we can write the conservation

relationship for D1 as follows

ðFlow OutÞ¼ðFlow InÞ

ðFlow OutÞðFlow InÞ¼0

ðD1W1 þ D1W2 þ D1W3 þ D1W4 þ D1W5ÞðP1D1 þ P2D1 þ P3D1Þ¼0

Similarly, for D2, we have

(D2W1 þ D2W2 þ D2W3 þ D2W4 þ D2W5)  (P1D2 þ P2D2 þ P3D2) ¼ 0

Thus, the conservation law takes the form of an equality constraint for particular nodes

in the network. This equality constraint is sometimes called a balance equation,

because it ensures perfect balance between inputs and outputs.

In this approach, we employed the conservation law to help build constraints for

the DCs. We did not use the conservation law for the supply and demand nodes. At

ﬁrst glance, it may appear that the conservation law does not necessarily hold at

those nodes. For example, if we interpret the input to node P1 as its capacity, we

cannot be sure, before solving the optimization problem, whether all of that capacity

will be used. Thus, we can’t tell whether the total ﬂow out of the node will be equal to

Chapter 3 Linear Programming: Network Models

the ﬂow in to the node. A similar fact applies to the demand nodes, although as we

noted earlier, we can expect the total ﬂow into those nodes to equal the demands

when there is an adequate supply in the network as a whole and when minimum

cost is the objective. In other words, there is no economic incentive to violate the con-

servation law at the demand nodes, even though the constraints of the model might

permit it. Nevertheless, there is a sense in which the conservation law holds even

for the supply and demand nodes. We explore this interpretation in a later section.

3.4. FEATURES OF SPECIAL NETWORK MODELS

The transportation, assignment, and transshipment problems constitute a set of special

network models in linear programming. They are special in the sense that they all lend

themselves easily to the use of a ﬂow diagram, and they all contain a From/To ﬂow

structure that suggests a convenient row-and-column layout in a spreadsheet. In par-

ticular, we can conveniently display the decision variables as an array in the spread-

sheet. When we specify the variables for Solver, we do not enter a row of adjacent

cells, which is the standard format. Instead, we enter an array, or in the case of the

transshipment model, a pair of arrays. (This feature could obviously be generalized

to cases in which we have three or more stages in the model.) With the array format

at the heart of the model, the constraints involve limitations on totals across a row

or down a column. As a result, the constraints use the SUM formula, rather than the

BOX 3.1

Characteristics of Special Network Models

Modules

Data module: capacities, demands, and unit costs.

Decision module: variables, row sums, and column sums.

Objective function: total cost of distribution, transportation, or assignment.

Decision variables

Use array layout reﬂecting the problem’s From/To structure.

Use an array the same size as the corresponding unit cost array.

Objective function

Calculate as the SUMPRODUCT(s) of array pairs.

Minimize total distribution, transportation, or assignment cost.

Constraints

Sum decision variables along row or column to compute capacity allocated.

Sum decision variables along row or column to compute demand covered.

Use LT for capacity, GT for demands to express the most ﬂexible form.

3.4. Features of Special Network Models