Programming Question

160CHAPTER 4
SOLVING LINEAR PROGRAMMING PROBLEMS: THE SIMPLEX METHOD
(resource 1)
(resource 2)
this information to identify the shadow price for each resource, the allowable range for each objective function
coefficient, and the allowable range for each right-hand
side.
subject to
3×1  2×2  3×3  x4  24
3×1  3×2  x3  3×4  36
and
x1  0,
x2  0,
x3  0,
x4  0.
D,I (a) Work through the simplex method step by step to solve the
problem.
(b) Identify the shadow prices for the two resources and describe
their significance.
C (c) Use a software package based on the simplex method to solve
the problem and then to generate sensitivity information. Use
4.9.1. Use the interior-point algorithm in your IOR Tutorial
to solve the model in Prob. 4.1-4. Choose   0.5 from the Option menu, use (x1, x2)  (0.1, 0.4) as the initial trial solution, and
run 15 iterations. Draw a graph of the feasible region, and then
plot the trajectory of the trial solutions through this feasible region.
4.9-2. Repeat Prob. 4.9-1 for the model in Prob. 4.1-5.
■ CASES
CASE 4.1 Fabrics and Fall Fashions
From the tenth floor of her office building, Katherine Rally
watches the swarms of New Yorkers fight their way through
the streets infested with yellow cabs and the sidewalks littered with hot dog stands. On this sweltering July day, she
pays particular attention to the fashions worn by the various
women and wonders what they will choose to wear in the
fall. Her thoughts are not simply random musings; they are
critical to her work since she owns and manages TrendLines,
an elite women’s clothing company.
Today is an especially important day because she must
meet with Ted Lawson, the production manager, to decide
upon next month’s production plan for the fall line. Specifically, she must determine the quantity of each clothing
item she should produce given the plant’s production capacity, limited resources, and demand forecasts. Accurate
planning for next month’s production is critical to fall
sales since the items produced next month will appear in
stores during September, and women generally buy the
majority of the fall fashions when they first appear in
September.
She turns back to her sprawling glass desk and looks at
the numerous papers covering it. Her eyes roam across the
clothing patterns designed almost six months ago, the lists
of materials requirements for each pattern, and the lists of
demand forecasts for each pattern determined by customer
surveys at fashion shows. She remembers the hectic and
sometimes nightmarish days of designing the fall line and
presenting it at fashion shows in New York, Milan, and Paris.
Ultimately, she paid her team of six designers a total of
$860,000 for their work on her fall line. With the cost of hiring runway models, hair stylists, and makeup artists, sewing
and fitting clothes, building the set, choreographing and rehearsing the show, and renting the conference hall, each of
the three fashion shows cost her an additional $2,700,000.
She studies the clothing patterns and material requirements. Her fall line consists of both professional and casual
fashions. She determined the prices for each clothing item
by taking into account the quality and cost of material, the
cost of labor and machining, the demand for the item, and
the prestige of the TrendLines brand name.
The fall professional fashions include:
Clothing Item
Materials Requirements
Price
Labor and
Machine Cost
Tailored wool slacks
3 yards of wool
2 yards of acetate for lining
1.5 yards of cashmere
1.5 yards of silk
0.5 yard of silk
2 yards of rayon
1.5 yards of acetate for lining
2.5 yards of wool
1.5 yards of acetate for lining
$300
$160
$450
$180
$120
$270
$150
$100
$ 60
$120
$320
$140
Cashmere sweater
Silk blouse
Silk camisole
Tailored skirt
Wool blazer
161
CASES
The fall casual fashions include:
Clothing Item
Materials Requirements
Price
Labor and
Machine Cost
Velvet pants
3 yards of velvet
2 yards of acetate for lining
1.5 yards of cotton
0.5 yard of cotton
1.5 yards of velvet
1.5 yards of rayon
$350
$175
$130
$ 75
$200
$120
$ 60
$ 40
$160
$ 90
Cotton sweater
Cotton miniskirt
Velvet shirt
Button-down blouse
She knows that for the next month, she has ordered
45,000 yards of wool, 28,000 yards of acetate, 9,000 yards
of cashmere, 18,000 yards of silk, 30,000 yards of rayon,
20,000 yards of velvet, and 30,000 yards of cotton for production. The prices of the materials are as follows:
Material
Price per yard
Wool
Acetate
Cashmere
Silk
Rayon
Velvet
Cotton
$ 9.00
$ 1.50
$60.00
$13.00
$ 2.25
$12.00
$ 2.50
Any material that is not used in production can be sent back
to the textile wholesaler for a full refund, although scrap material cannot be sent back to the wholesaler.
She knows that the production of both the silk blouse
and cotton sweater leaves leftover scraps of material. Specifically, for the production of one silk blouse or one cotton
sweater, 2 yards of silk and cotton, respectively, are needed.
From these 2 yards, 1.5 yards are used for the silk blouse
or the cotton sweater and 0.5 yard is left as scrap material.
She does not want to waste the material, so she plans to use
the rectangular scrap of silk or cotton to produce a silk
camisole or cotton miniskirt, respectively. Therefore, whenever a silk blouse is produced, a silk camisole is also produced. Likewise, whenever a cotton sweater is produced, a
cotton miniskirt is also produced. Note that it is possible to
produce a silk camisole without producing a silk blouse and
a cotton miniskirt without producing a cotton sweater.
The demand forecasts indicate that some items have
limited demand. Specifically, because the velvet pants and
velvet shirts are fashion fads, TrendLines has forecasted that
it can sell only 5,500 pairs of velvet pants and 6,000 velvet
shirts. TrendLines does not want to produce more than the
forecasted demand because once the pants and shirts go out
of style, the company cannot sell them. TrendLines can produce less than the forecasted demand, however, since the
company is not required to meet the demand. The cashmere
sweater also has limited demand because it is quite expensive, and TrendLines knows it can sell at most 4,000 cashmere sweaters. The silk blouses and camisoles have limited
demand because many women think silk is too hard to care
for, and TrendLines projects that it can sell at most 12,000
silk blouses and 15,000 silk camisoles.
The demand forecasts also indicate that the wool
slacks, tailored skirts, and wool blazers have a great demand
because they are basic items needed in every professional
wardrobe. Specifically, the demand for wool slacks is 7,000
pairs of slacks, and the demand for wool blazers is 5,000
blazers. Katherine wants to meet at least 60 percent of the
demand for these two items in order to maintain her loyal
customer base and not lose business in the future. Although
the demand for tailored skirts could not be estimated,
Katherine feels she should make at least 2,800 of them.
(a) Ted is trying to convince Katherine not to produce any velvet
shirts since the demand for this fashion fad is quite low. He
argues that this fashion fad alone accounts for $500,000 of the
fixed design and other costs. The net contribution (price of
clothing item  materials cost  labor cost) from selling the
fashion fad should cover these fixed costs. Each velvet shirt
generates a net contribution of $22. He argues that given the
net contribution, even satisfying the maximum demand will not
yield a profit. What do you think of Ted’s argument?
(b) Formulate and solve a linear programming problem to maximize
profit given the production, resource, and demand constraints.
Before she makes her final decision, Katherine plans to explore the following questions independently except where
otherwise indicated.
(c) The textile wholesaler informs Katherine that the velvet cannot be sent back because the demand forecasts show that the
162
CHAPTER 4
SOLVING LINEAR PROGRAMMING PROBLEMS: THE SIMPLEX METHOD
demand for velvet will decrease in the future. Katherine can
therefore get no refund for the velvet. How does this fact change
the production plan?
(d) What is an intuitive economic explanation for the difference between the solutions found in parts (b) and (c)?
(e) The sewing staff encounters difficulties sewing the arms and
lining into the wool blazers since the blazer pattern has an awkward shape and the heavy wool material is difficult to cut and
sew. The increased labor time to sew a wool blazer increases
the labor and machine cost for each blazer by $80. Given this
new cost, how many of each clothing item should TrendLines
produce to maximize profit?
(f) The textile wholesaler informs Katherine that since another textile customer canceled his order, she can obtain an extra 10,000
yards of acetate. How many of each clothing item should TrendLines now produce to maximize profit?
(g) TrendLines assumes that it can sell every item that was not sold
during September and October in a big sale in November at 60
percent of the original price. Therefore, it can sell all items in
unlimited quantity during the November sale. (The previously
mentioned upper limits on demand concern only the sales during September and October.) What should the new production
plan be to maximize profit?
■ PREVIEWS OF ADDED CASES ON OUR WEBSITE (www.mhhe.com/hillier)
CASE 4.2 New Frontiers
AmeriBank will soon begin offering Web banking to its customers. To guide its planning for the services to provide over
the Internet, a survey will be conducted with four different
age groups in three types of communities. AmeriBank is imposing a number of constraints on how extensively each age
group and each community should be surveyed. Linear programming is needed to develop a plan for the survey that
will minimize its total cost while meeting all the survey constraints under several different scenarios.
CASE 4.3 Assigning Students to Schools
After deciding to close one of its middle schools, the Springfield school board needs to reassign all of next year’s middle
school students to the three remaining middle schools. Many
of the students will be bused, so minimizing the total busing
cost is one objective. Another is to minimize the inconvenience and safety concerns for the students who will walk
or bicycle to school. Given the capacities of the three
schools, as well as the need to roughly balance the number
of students in the three grades at each school, how can linear programming be used to determine how many students
from each of the city’s six residential areas should be assigned to each school? What would happen if each entire
residential area must be assigned to the same school? (This
case will be continued in Cases 7.3 and 12.4.)
HOMEWORK SUBMISSION GUIDE
You can form a team upto 3 people and submit you homework as a group study.
You have to write your names under your group number in BB. You have to submit
only one homework for each group . Don’t forget to write your names on the
report. You will submit both your report and cplex project files. Copying from other
groups is not allowed. In that case both groups will get zero.
You will submit you report and codes in the following detail:
1) HW_REPORT_GroupNumber.pdf (PDF FORMAT)
In this report:
1) Construct and show the mathematical model for part b. Identify decision
variables clearly. Construct and solve the model in CPLEX. Put a screenshot of your
CPLEX model. Show profit, amount of each product type that has been produced.
2) For e, f, g parts explain the changes you made in the model clearly, put
screenshots of new models, show new profit, show amount of each product that
has been produced.
3) For a, c, d explain in detail using proper English. Justify your answers with
necessary mathematical operations.
2) CPLEX FILES
CPLEX files must be named same as the corresponding parts. b.mod, b.dat, e.mod,
e.dat, f.mod, f.dat, g.mod, g.dat. If you haven’t used .dat file don’t upload it.
Compress all files including your report, into a
ZIP FOLDER (preferably .7zip or .rar) named
HW_GroupNumber