Optimization of Discrete Models
Optimization – 这是一个关于assembly的题目, 主要考察了关于Optimization 的内容,是一个比较经典的题目, 是比较有代表性的Optimization 等代写方向
250 Chapter 7 Optimization of Discrete Models
of how many cattle to sell and how many to keep. If he sells, he estimates his profit to be
piin yeari. Also, the number of cattle kept in yeariis expected to double in yeariC 1.
Although this scenario neglects many factors that an analyst might consider in the real
world (name several), we can see that the cattle rancher is faced with a trade-off decision
each year: take a profit or build for the future.
In the next several sections we focus our attention on solving linear programming
problems, first geometrically and then by the Simplex Method.
7.17.1 PROBLEMS
Use the model-building process described in Chapter 2 to analyze the following scenarios.
After identifying the problem to be solved using the process, you may find it helpful to
answer the following questions in words before formulating the optimization model.
a. Identify the decision variables: What decision is to be made?
b. Formulate the Objective function: How do these decisions affect the objective?
c. Formulate the constraint set: What constraints must be satisfied? Be sure to consider
whether negative values of the decision variables are allowed by the problem, and ensure
they are so constrained if required.
After constructing the model, check the assumptions for a linear program and compare
the form of the model to the examples in this section. Try to determine which method of
optimization may be applied to obtain a solution.
1. Resource Allocation You have just become the manager of a plant producing plastic products. Although the plant operation involves many products and supplies, you are interested in only three of the products: (1) a vinylasbestos floor covering, the output of which is measured in boxed lots, each covering a certain area; (2) a pure vinyl counter top, measured in linear yards; and (3) a vinylasbestos wall tile, measured in squares, each covering 100 ft^2. Of the many resources needed to produce these plastic products, you have identified four: vinyl, asbestos, labor, and time on a trimming machine. A recent inventory shows that on any given day you have 1500 lb of vinyl and 200 lb of asbestos available for use. Additionally, after talking to your shop foreman and to various labor leaders, you realize that you have 3 person-days of labor available for use per day and that your trimming machine is available for 1 machine-day on any given day. The following table indicates the amount of each of the four resources required to produce a unit of the three desired products, where the units are 1 box of floor cover, 1 yard of counter top, and 1 square of wall tiles. Available resources are tabulated below.
Vinyl Asbestos Labor Machine
(lb) (lb) (person-days) (machine-days) Profit
Floor cover (per box) 30 3 0.02 0.01 $0.
Countertop (per yard) 20 0 0.1 0.05 5.
Wall tile (per square) 50 5 0.2 0.05 5.
Available (per day) 1500 200 3 1
Copyright 201 3 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
7.1 An Overview of Optimization Modeling 251
Formulate a mathematical model to help determine how to allocate resources to
maximize profits.
2. Nutritional Requirements A rancher has determined that the minimum weekly nutri- tional requirements for an average-sized horse include 40 lb of protein, 20 lb of carbohy- drates, and 45 lb of roughage. These are obtained from the following sources in varying amounts at the prices indicated:
Protein Carbohydrates Roughage
(lb) (lb) (lb) Cost
Hay 0.5 2.0 5.0 $1.
(per bale)
Oats 1.0 4.0 2.0 3.
(per sack)
Feeding blocks 2.0 0.5 1.0 0.
(per block)
High-protein 6.0 1.0 2.5 1.
concentrate
(per sack)
Requirements 40.0 20.0 45.
per horse
(per week)
Formulate a mathematical model to determine how to meet the minimum nutritional
requirements at minimum cost.
3. Scheduling Production A manufacturer of an industrial product has to meet the fol- lowing shipping schedule:
Month Required shipment (units)
January 10,
February 40,
March 20,
The monthly production capacity is 30,000 units and the production cost per unit is $ 10.
Because the company does not warehouse, the service of a storage company is utilized
whenever needed. The storage company determines its monthly bill by multiplying
the number of units in storage on the last day of the month by $3. On the first day
of January the company does not have any beginning inventory, and it does not want
to have any ending inventory at the end of March. Formulate a mathematical model
to assist in minimizing the sum of the production and storage costs for the 3-month
period.
How does the formulation change if the production cost is10xC 10 dollars, where
xis the number of items produced?
Copyright 201 3 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
252 Chapter 7 Optimization of Discrete Models
4. Mixing Nuts A candy store sells three different assortments of mixed nuts, each as- sortment containing varying amounts of almonds, pecans, cashews, and walnuts. To preserve the stores reputation for quality, certain maximum and minimum percentages of the various nuts are required for each type of assortment, as shown in the following table:
Selling price
Nut assortment Requirements per pound
Regular Not more than 20% cashews $0.
Not less than 40% walnuts
Not more than 25% pecans
No restriction on almonds
Deluxe Not more than 35% cashews 1.
Not less than 25% almonds
No restriction on walnuts
and pecans
Blue Ribbon Between 30% and 50% cashews 1.
Not less than 30% almonds
No restriction on walnuts
and pecans
The following table gives the cost per pound and the maximum quantity of each type of
nut available from the stores supplier each week.
Cost Maximum quantity
Nut type per pound available per week (lb)
Almonds $0.45 2000
Pecans 0.55 4000
Cashews 0.70 5000
Walnuts 0.50 3000
The store would like to determine the exact amounts of almonds, pecans, cashews,
and walnuts that should go into each weekly assortment to maximize its weekly profit.
Formulate a mathematical model that will assist the store management in solving the
mixing problem. Hint: How many decisions need to be made? For example, do you need
to distinguish between the cashews in the regular mix and the cashews in the deluxe
mix?
5. Producing Electronic Equipment An electronics firm is producing three lines of prod- ucts for sale to the government: transistors, micromodules, and circuit assemblies. The firm has four physical processing areas designated as follows: transistor production, cir- cuit printing and assembly, transistor and module quality control, and circuit assembly test and packing.
Copyright 201 3 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
7.1 An Overview of Optimization Modeling 253
The various production requirements are as follows: Production of one transistor
requires 0.1 standard hour of transistor production area capacity, 0.5 standard hour of
transistor quality control area capacity, and $0.70 in direct costs. Production of micro-
modules requires 0.4 standard hour of the quality control area capacity, three transis-
tors, and $0.50 in direct costs. Production of one circuit assembly requires 0.1 stan-
dard hour of the capacity of the circuit printing area, 0.5 standard hour of the capacity
of the test and packing area, one transistor, three micromodules, and $2.00 in direct
costs.
Suppose that the three products (transistors, micromodules, and circuit assemblies)
may be sold in unlimited quantities at prices of $2, $8, and $25 each, respectively. There
are 200 hours of production time open in each of the four process areas in the com-
ing month. Formulate a mathematical model to help determine the production that will
produce the highest revenue for the firm.
6. Purchasing Various Trucks A truck company has allocated $800,000 for the purchase of new vehicles and is considering three types. Vehicle A has a 10-ton payload capacity and is expected to average 45 mph; it costs $26,000. Vehicle B has a 20-ton payload capacity and is expected to average 40 mph; it costs $36,000. Vehicle C is a modified form of B and carries sleeping quarters for one driver. This modification reduces the capacity to an 18-ton payload and raises the cost to $42,000, but its operating speed is still expected to average 40 mph. Vehicle A requires a crew of one driver and, if driven on three shifts per day, could be operated for an average of 18 hr per day. Vehicles B and C must have crews of two drivers each to meet local legal requirements. Vehicle B could be driven an average of 18 hr per day with three shifts, and vehicle C could average 21 hr per day with three shifts. The company has 150 drivers available each day to make up crews and will not be able to hire additional trained crews in the near future. The local labor union prohibits any driver from working more than one shift per day. Also, maintenance facilities are such that the total number of vehicles must not exceed 30. Formulate a mathematical model to help determine the number of each type of vehicle the company should purchase to maximize its shipping capacity in ton-miles per day. 7. A Farming Problem A f arm family owns 100 acres of land and has $25,000 in funds available for investment. Its members can produce a total of 3500 work-hours worth of labor during the winter months (mid-September to mid-May) and 4000 work-hours during the summer. If any of these work-hours are not needed, younger members of the family will use them to work on a neighboring farm for $4.80 per hour during the winter and $5.10 per hour during the summer. Cash income may be obtained from three crops (soybeans, corn, and oats) and two types of livestock (dairy cows and laying hens). No investment funds are needed for the crops. However, each cow requires an initial investment outlay of $400, and each hen requires $3. Each cow requires 1.5 acres of land and 100 work-hours of work during the winter months and another 50 work-hours during the summer. Each cow produces a net annual cash income of $450 for the family. The corresponding figures for the hen are as follows: no acreage, 0.6 work-hour during the winter, 0.3 more work-hour in the summer, and an annual net cash income of $3.50. The chicken house accommodates a maximum of 3000 hens, and the size of the barn limits the cow herd to a maximum of 32 head.
Copyright 201 3 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
254 Chapter 7 Optimization of Discrete Models
Estimated work-hours and income per acre planted in each of the three crops are as
shown in the following table:
Winter Summer Net annual cash
Crop work-hours work-hours income (per acre)
Soybean 20 30 $175.
Corn 35 75 300.
Oats 10 40 120.
Formulate a mathematical model to assist in deter mining how much acreage should
be planted in each of the crops and how many cows and hens should be kept to maximize
net cash income.
7.17.1 PROJECTS
For Projects 15, complete the requirements in the referenced UMAP module or monograph.
(See enclosed CD for UMAP modules.)
1. Unconstrained Optimization, by Joan R. Hundhausen and Robert A. Walsh, UMAP 522. This unit introduces gradient search procedures with examples and applications. Acquaintance with elementary partial differentiation, chain rules, Taylor series, gradi- ents, and vector dot products is required. 2. Calculus of Variations with Applications in Mechanics, by Carroll O. Wilde, UMAP 468. This module provides a brief introduction to finding functions that yield the maxi- mum or minimum value of certain definite integral forms, with applications in mechanics. Students learn Eulers equations for some definite integral forms and learn Hamiltons principle and its application to conservative dynamical systems. The basic physics of kinetic and potential energy, the multivariate chain rules, and ordinary differential equa- tions are required. 3. The High Cost of Clean Water: Models for Water Quality Management , by Edward Beltrami, UMAP Expository Monograph. To cope with the severe wastewater disposal problems caused by increases in the nations population and industrial activity, the U.S. Environmental Protection Agency (EPA) has fostered the development of regional wastewater management plans. This monograph discusses the EPA plan developed for Long Island and formulates a model that allows for the articulation of the trade-offs between cost and water quality. The mathematics involves partial differential equations and mixed-integer linear programming. 4. Geometric Programming, by Robert E. D. Woolsey, UMAP 737. This unit provides some alternative optimization formulations, including geometric programming. Famil- iarity with basic differential calculus is required. 5. Municipal Recycling: Location and Optimality, by Jannett Highfill and Michael McAsey, UMAP Journal Vol. 15(1), 1994. This article considers optimization in mu- nicipal recycling. Read the article and prepare a 10-min classroom presentation.
Copyright 201 3 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).