Baker K.R. Optimization Modeling with Spreadsheets
Подождите немного. Документ загружается.
lease in January. In total, there are 15 possible leases it could use. It must decide which
leases to purchase, and how many square feet to purchase on each lease.
Since the space requirements differ month-to-month, it may be economical to lease
only the amount needed each month on a month-by-month basis. On the other hand, the
monthly cost for leasing space for additional months is much less than for the first month,
so it may be desirable to lease the maximum amount needed for the entire five months.
Another option is the intermediate approach of changing the total amount of space
leased (by adding a new lease and/or having an old lease expire) at least once but not
every month. Two or more leases for different terms can begin at the same time.
The space requirements (in square feet) and the leasing costs (in dollars per thousand
square feet) are given in the tables below.
Space Lease Lease
Month requirements length cost
Jan 15,000 1 month $280
Feb 10,000 2 months 450
Mar 20,000 3 months 600
April 5000 4 months 730
May 25,000 5 months 820
The task is to find a leasing schedule that provides the necessary amounts of space at the
minimum cost.
(a) Determine the optimal leasing schedule and the optimal total cost.
(b) Trace the effects of increasing the space required for January. How will the leasing
schedule change? How will the total cost change?
2.14. Production Planning The Kim Camera Company produces four different camera
models, known as C1– C4. Each model can be made by two different methods. The
manual method requires work in the Fabrication, Assembly, and Test departments,
while the automated method combines the Assembly and Test operations in one depart-
ment. The first table below describes the price and cost features of the camera models,
along with marketing information on the range of possible sales in the coming month.
Because model C1 is delivered to one large retailer under a long-term contract, a threshold
demand quantity of 1500 units must be met. For the other models, there is flexibility in
how much demand to meet, up to a ceiling that represents maximum possible sales.
C1 C2 C3 C4
Price 125 175 200 135
Manual cost 110 160 155 125
Auto cost 100 112 150 90
Manual margin 15 15 45 10
Auto margin 25 63 50 45
Sales max. 3000 2500 2000 3200
Sales min. 1500 0 0 0
66 Chapter 2 Linear Programming: Allocation, Covering, and Blending Models
The next table provides data on the various departments at the firm, consisting of the time
per camera required in each department and the number of hours available in each depart-
ment during the month.
C1 C2 C3 C4 Hours
Manual fab. 3 5 4 4 16,000
Manual asy. 8 12 10 9 30,000
Manual test 2 3 5 2 15,000
Auto fab. 5 6 7 4 24,000
Auto asy/test 4 5 8 5 20,000
(a) What production plan will maximize profit for Kim Camera?
(b) How would the solution in (a) change if there were no threshold requirement for
Camera C1?
2.15. Make/Buy Planning The CammTex Fabric Mill is in the process of deciding on a pro-
duction schedule. It wishes to know how to weave the various fabrics it will produce
during the coming quarter. The sales department has confirmed orders for each of the
15 fabrics that are produced by CammTex. These quarterly demands are given in the
table below. Also tabulated is the variable cost for each fabric. The mill operates continu-
ously during the quarter: 13 weeks, 7 days a week, and 24 hours a day.
CammTex uses two types of looms: dobbie and regular. Dobbie looms can make all
fabrics, and they are the only looms that can weave certain fabrics such as plaids. The
production rate for each fabric on each type of loom is also given in the table. (If the
production rate is zero, the fabric cannot be woven on that type of loom.) CammTex
has 90 regular looms and 15 dobbie looms.
Fabrics woven at CammTex proceed to the finishing department in the mill and are
then sold. Any fabrics not woven in the mill because of limited capacity are subcontracted
to an outside producer and sold at the selling price. The cost of purchasing from the
subcontractor is also given in the table.
Demand Dobbie Regular Mill cost Sub. cost
Fabric (yd) (yd/hr) (yd/hr) ($/yd) ($/yd)
1 16,500 4.653 0.00 0.6573 0.80
2 52,000 4.653 0.00 0.555 0.70
3 45,000 4.653 0.00 0.655 0.85
4 22,000 4.653 0.00 0.5542 0.70
5 76,500 5.194 5.313 0.6097 0.75
6 110,000 3.767 3.809 0.6153 0.75
7 122,000 4.055 4.185 0.6477 0.80
8 62,000 5.208 5.232 0.488 0.60
9 7500 5.208 5.232 0.5029 0.70
10 69,000 5.208 5.232 0.4351 0.60
11 70,000 3.652 3.733 0.6417 0.80
12 82,000 4.007 4.185 0.5675 0.75
13 10,000 4.291 4.439 0.4952 0.65
14 380,000 5.208 5.232 0.3128 0.45
15 62,000 4.004 4.185 0.5029 0.70
Exercises
67
(a) What is minimum total cost of production and purchasing for CammTex?
(b) Which fabrics should be made at the mill and which should be purchased? For those
made at the mill, which loom types should be assigned to their production?
2.16. Production Scheduling The Seaboch Tire Company produces four lines of tires: the
Economy, the Glass-belted, the Snow and the Radial tire. The problem it faces is to sche-
dule two shifts of production during the last quarter of the calendar year. The production
process primarily involves the use of vulcanization, fabrication, and plastometer equip-
ment, but the limiting resource is the availability of the vulcanization machines. The
four tires require different amounts of time at vulcanization, as tabulated below.
Tire Econ. Glass Snow Radial
Hours/tire 4.5 5.0 5.5 6.0
A sales forecast is available, breaking down predicted sales (in thousands) by tire type and
by month.
Sales Oct Nov Dec
Econ. 8 7 6
Glass 18 16 18
Snow 4 15 15
Radial 6 5 8
In addition, the number of hours of vulcanizing time (in thousands), for each shift and for
each month, is also known.
Oct Oct Nov Nov Dec Dec
Shift 1 2 1 2 1 2
Hours 110 100 130 120 120 115
The labor cost of operating the vulcanizing machines is $10 per hour during the first shift
and $12 per hour during the second shift. The other relevant cost is storage: It costs $4 per
month for storage and handling at the warehouse, regardless of tire type. This cost is
incurred if there is not enough labor capacity to meet demand in the month when it occurs.
(a) What production plan will minimize cost and meet demand at Seaboch Tire?
(b) How would the solution in (a) change if sales for each tire in December were 10 per-
cent higher?
Case: JetGreen
∗
JetGreen flies three airplanes, using a “hub and spoke” flight schedule between Houston and
three cities, Chicago, Miami, and Phoenix. These three cities are the “spokes” connected by
the Houston “hub.” Once each day, the three airplanes fly from the spoke cities to Houston.
∗
Adapted from case material written by Professor Rob Shumsky of Dartmouth College.
68 Chapter 2 Linear Programming: Allocation, Covering, and Blending Models
They arrive nearly simultaneously at Houston, then connecting passengers change aircraft
during a one-hour layover, and the three airplanes return to their starting cities. One set of six
flights (3 inbound to Houston and 3 outbound) is called a bank. A bank can serve passengers
flying on 12 different routes: three inbound direct routes (Chicago or Miami or Phoenix into
Houston), three outbound direct routes (Houston to Chicago or Miami or Phoenix), and six
routes requiring two flights each (Chicago– Miami, Chicago –Phoenix, Miami–Phoenix,
Miami– Chicago, Phoenix–Chicago, and Phoenix–Miami).
JetGreen charges a regular price for a one-way ticket on each route. Exhibit 2.1 shows the
regular prices. Following a well-established policy, JetGreen offers a discount to senior trave-
lers. The ticket price for a senior traveler is 90 percent of the regular price, rounded down to
the next smaller integer number of dollars. (For example, on the Houston-Phoenix route, the
senior ticket price is $112.) The marginal cost of flying a passenger on each route is virtually
zero.
Each of JetGreen’s three airplanes contains 260 seats. Exhibit 2.2 shows demand for the
routes in a bank at the regular price, and Exhibit 2.3 shows the demand from seniors (at the dis-
counted price). These figures apply to the times at which JetGreen flies, and they show that pas-
senger demand exceeds airplane capacity on every flight segment. For example, on the flight
from Miami to the Houston hub, the total regular demand is the sum of demands for three pas-
senger routes, (Miami to Houston or Chicago or Phoenix), totaling 72 + 105 + 68 ¼ 245 pas-
sengers (from the third row of Exhibit 2.2). For seniors, the comparable figure is 6 + 15 + 8 ¼
29, and the total is 245 + 29 ¼ 274. Because only 260 passengers can travel on the Miami–
Houston flight, at least 14 passengers represent lost demand.
When the total demand for a particular flight is larger than the available capacity, an airline
can decide whether to accept or reject an offer to buy a ticket for a particular route. Controlling
EXHIBIT 2.1 Price for Each Passenger Route
Destination
Houston Chicago Miami Phoenix
Origin
Houston – $197 $110 $125
Chicago $190 – $282 $195
Miami $108 $292 – $238
Phoenix $110 $192 $230 –
EXHIBIT 2.2 Regular Demand During One Bank
Destination
Houston Chicago Miami Phoenix
Origin
Houston – 123 80 110
Chicago 130 – 98 88
Miami 72 105 – 68
Phoenix 115 90 66 –
Case: JetGreen
69
sales in this way to maximize revenue is called revenue management. For example, JetGreen
may decide to sell large numbers of tickets for the Miami– Houston and Miami– Chicago
routes, but might severely restrict sales of the Miami–Phoenix tickets. Given the data above,
JetGreen might sell tickets to 78 Miami–Houston passengers, 120 Miami–Chicago passengers,
and only 62 Miami–Phoenix passengers, thus filling all 260 seats on the Miami–Houston flight.
All 14 lost demands would then come from the Miami–Phoenix route.
Assuming that the various demands in Exhibits 2.2 and 2.3 are known, JetGreen wants to
determine the number of tickets it should sell to regular and senior passengers on each route.
EXHIBIT 2.3 Senior Demand During One Bank
Destination
Houston Chicago Miami Phoenix
Origin
Houston – 12 7 10
Chicago 15 – 10 13
Miami 6 15 – 8
Phoenix 12 8 5 –
70 Chapter 2 Linear Programming: Allocation, Covering, and Blending Models
Chapter 3
Linear Programming:
Network Models
In the previous chapter, we examined allocation, covering, and blending models—
three basic structures frequently encountered in linear programming applications. A
fourth common structure is the network model, and we devote a separate chapter
to it because of its distinctive nature. The network model describes configurations
of flow in a connected system, where the flow might involve material, people,
funds, and so on. These configurations are conveniently described with flow diagrams,
which help in the development of valid spreadsheet models. The possibility of doing
some of the model building with a diagram makes network models a special category
of linear programs.
The flow diagram is a modeling tool in its own right, and we can use it as a visual
aid or an auditing device. Used as a visual aid, the flow diagram is an accessory,
providing a picture of the problem structure to assist us in our main task, which is
developing the spreadsheet representation of the linear program. In this role, the
flow diagram is a preliminary step; it helps us build the spreadsheet model, and
once we’ve done that, we may no longer need the diagram. Alternatively, used as
an auditing device, the flow diagram allows us to translate a network picture directly
into an algebraic formulation and vice versa. This approach integrates the flow dia-
gram with the spreadsheet model. In this role, the diagram allows us to develop a
model on two fronts simultaneously, and we can use the diagram to check for
errors and omissions as we build the spreadsheet model.
In terms of the optimization software, no new features are needed to deal with
network models. Therefore, the software features covered in the previous chapter
are sufficient for this chapter as well.
We first study three types of special network problems that illustrate the use of
flow diagrams as visual aids. The distinguishing feature of special network models
is an inherent From/To flow pattern that lends itself to the row and column format
of the spreadsheet. We then move on to general network problems involving other
flow patterns, where we illustrate how to integrate the flow diagram with the develop-
ment of a spreadsheet. As we will see, the distinguishing feature of network models is
Optimization Modeling with Spreadsheets, Second Edition. Kenneth R. Baker
# 2011 John Wiley & Sons, Inc. Published 2011 by John Wiley & Sons, Inc.
71
a basic conservation law governing patterns of flow. This feature allows us to identify
the key constraints needed for the model. In the course of this chapter, we encounter
several applications of the conservation law, and we pay particular attention to the use
of flow diagrams in modeling.
3.1. THE TRANSPORTATION MODEL
A central feature of physical supply chains is the movement of product from one or
more source locations to a set of destinations where demand occurs. The cost of
moving units of product, together with the cost of making the product, accounts for
most of the cost of getting products to market. Small wonder, then, that a great deal
of attention is paid to controlling the costs that occur in supply chains. The building
block for performing this type of analysis is the transportation model. Consider the
example of Goodwin Manufacturing.
EXAMPLE 3.1
The Goodwin Manufacturing Company
The Goodwin Manufacturing Company is planning next week’s shipments from its three man-
ufacturing plants to its four distribution warehouses and is seeking a minimum-cost shipping
schedule. Each plant has a potential capacity, expressed in cartons of product, and each ware-
house has a demand requirement for the week that must be met. There are 12 possible shipment
routes, and for every plant– warehouse combination, the unit shipping cost is known. The
following table provides the given information.
(To) Warehouse
(From) plant Atlanta Boston Chicago Denver Capacity
Minneapolis $0.60 $0.56 $0.22 $0.40 10,000
Pittsburgh 0.36 0.30 0.28 0.58 15,000
Tucson 0.65 0.68 0.55 0.42 15,000
Requirement 8000 10,000 12,000 9000
B
Figure 3.1 displays a flow diagram showing the possible routes. In the diagram,
the letters on the left designate the manufacturing plants, which supply the product.
The letters on the right stand for the warehouses, where the demands occur. In this
case, all supply– demand pairs represent potential shipping routes.
Network terminology refers to flow along arcs or arrows in the diagram. Each arc
connects two nodes or circles, and the direction of the corresponding arrow indicates
the direction of flow. This flow incurs a cost: the unit cost of flow from any plant to any
warehouse is given in Example 3.1. The flows along each of the 12 possible routes
constitute the decision variables in the model. Although the diagram does not contain
labels for the arcs, it would be natural to use the notation MA for the quantity shipped
72
Chapter 3 Linear Programming: Network Models
on the route from Minneapolis to Atlanta, MB for the quantity shipped on the route
from Minneapolis to Boston, and so on.
This is an instance of the classical transportation problem, which is described by
a set of sources and their supplies, a set of destinations and their demands, and the unit
cost associated with each source–destination pair. In Example 3.1, the supplies are
plant capacities—figures that would be provided by the production or manufacturing
function. The demands are customer orders, typically marketing forecasts of near-term
requirements, although they could be firm orders in environments where delivery
lead times are relatively long. Unit costs are actual costs incurred internally, and
they would be estimated from historical data in logistics records. If some of the
potential routes had not been in use, the cost on those routes would have to be esti-
mated by knowledgeable people in the distribution or transportation functions.
Alternatively, the unit costs could arise as prices set by third parties who take res-
ponsibility for transportation of physical goods. In such cases, unit costs would be
based on published rates for delivery by truck, rail or air.
Figure 3.2 displays a spreadsheet model for the example. Notice the distinctive
From/To structure in the table describing the parameters of the problem. This structure
lends itself readily to a row-and-column format, which is the essence of spreadsheet
layout. Here, we adopt a convention that associates sources with rows and destina-
tions with columns. In other words, flow moves conceptually in the spreadsheet
from rows to columns. Because of this structure, it is helpful to depart from the stan-
dard linear programming layout used in Chapter 2 and to adopt a special format for
this type of model. In particular, we can construct a spreadsheet model in rows and
columns to mirror the table of parameters given in Example 3.1. In the Parameters
Figure 3.1. Flow diagram for Example 3.1.
3.1. The Transportation Model 73
module of the spreadsheet, we see all of the given information, displayed in an array. In
the Decisions module, the decision variables (shaded for highlighting) appear in an
array of the same size. At the right of each row is the “Sent” quantity, which is
simply the sum of the flows along the row. Below each column of the array is the
“Received” quantity, which is the sum in the column. The objective function,
which is expressed as a SUMPRODUCT in cell C18, is the total transportation cost
for the system. It is the SUMPRODUCT of the two ranges, C5:F7 and C12:F14,
that hold the unit cost parameters and the shipment decisions. In algebraic form, the
objective function can be expressed as
Total cost ¼ z ¼ 0:60MA þ 0:56MB þ 0:22MC þþ0:55TC þ 0:42TD
The transportation model has two kinds of constraints: LT supply constraints and
GT demand constraints. For the Minneapolis plant, the amount shipped from
Minneapolis must be no greater than the Minneapolis capacity. In symbols, we can
write the capacity constraint as
MA þ MB þ MC þ MD 10,000
For Pittsburgh and Tucson, we have similar constraints:
PA þ PB þ PC þ PD 15,000
TA þ TB þ TC þ TD 15,000
Given the spreadsheet layout, these three constraints constitute a set of LT constraints
that say Sent Capacity, or G12:G14 must be less than or equal to G5:G7. The LHS
Figure 3.2. Spreadsheet model for Example 3.1.
74 Chapter 3 Linear Programming: Network Models
of these constraints simply adds the outbound shipment quantities from a given
location. For that reason, we don’t really need to use the SUMPRODUCT formula
in the worksheet; we can use the simpler SUM formula. Thus, as the display of for-
mulas in Figure 3.3 demonstrates, the spreadsheet model uses both the
SUMPRODUCT and SUM functions.
For the Atlanta warehouse, the demand constraint requires that the amount
received at Atlanta (from all sources) must be at least as large as the Atlanta
demand. As we saw in Chapter 2, it is good practice to use the inequality form of
this type of constraint, even though our intuition may tell us that there is no reason
to ship more to Atlanta than is demanded. In symbols, this constraint reads
MA þ PA þ TA 8000
Similarly, for the other three warehouses, the constraints become
MB þ PB þ TB 10,000
MC þ PC þ TC 12,000
MD þ PD þ TD 9000
In the spreadsheet, these four constraints constitute a set of GT constraints that say
Received Demand, or C15:F15 must be greater than or equal to C8:F8. Again,
the left-hand sides of these constraints can easily be expressed using the SUM formula.
In the Model tab of the task pane, we specify the model as follows.
Objective: C18 (minimize)
Variables: C12:F14
Constraints: G12:G14 G5:G7
C15:F15 C8:F8
As usual for linear programs, we select the Standard LP/Quadratic Engine from
the drop-down menu on the Engine tab and set the Assume Non-Negative option to
True. This will be standard operating procedure when we are solving linear programs,
so we won’t mention it specifically from now on, unless there is an exception.
Figure 3.3. Formulas in the spreadsheet for Example 3.1.
3.1. The Transportation Model 75