QBUS2310 Semester 2 2022
Assignment 2
This assignment consists of eleven problems that require you to submit a written response and a
coding component.
(1) When a problem asks you to formulate you need to provide your mathematical formulation
of the LP or IP with clear justification of variables, constraints and objective. You should
submit your written response as a PDF to GradeScope and match the page number with
the questions that you answered. You can find the detailed instructions on how to scan and
submit your assignments on Canvas. If you fail to match the page to the corresponding
question, the marker will not be able to view your response and thus you will be awarded 0
mark for the question.
(2) When a problem involves computation you must give the Python source code that produces
the result, the final numerical results and your interpretation of the numerical results. The
Python code and numerical results go into the space provided below. You should submit
your code as a Jupyter notebook file via Canvas. In addition, the final numerical results and
your interpretation of the results should appear in your written response, described in (1).
The assignment is due by Friday, the 4th of November, 5pm. Late assignments will not be ac-
cepted unless a special consideration was granted.
All problems have equal weight. Some are easy. Others, not so much.
Good luck!
1
Problem 1: Minnesota Fabrics
Minnesota Fabrics produces three sizes of comforters (single, queen, and king size) that it markets
to major retail establishments throughout the country. Due to contracts with these establishments,
Minnesota Fabrics must produce at least 120 of each size comforter daily. It pays $0.50 per pound
for stuffing and $0.20 per square foot for quilted fabric used in the production of the comforters. It
can obtain up to 2,700 pounds of stuffing and 48,000 square feet of quilted fabric from its suppliers.
Labor is considered a fixed cost for Minnesota Fabrics. It has enough labor to provide 50 hours of
cutting time and 200 hours of sewing time daily. The following table gives the unit material and
labor required as well as the selling price to the retail stores for each size comforter.
Stuffing (lb) Quilted Fabric (sq.ft.) Cutting Time (min) Sewing Time (min) Selling Price ($)
Single 3 55 3 5 19
Queen 4 75 5 6 26
King 6 95 6 8 32
(a) Formulate and solve an LP to determine the daily production schedule that maximizes total
daily gross profit (= selling price - material costs). How much of the available daily material
and labor resources would be used by this production schedule?
(b) What is the lowest selling price for queen size comforters that Minnesota Fabrics could
charge while maintaining the optimal production schedule recommended in part (a)?
(c) Suppose Minnesota Fabrics could obtain additional stuffing or quilted fabric from supple-
mentary suppliers. What is the most it should be willing to pay for:
An extra pound of stuffing? Within what limits is this valid?
An extra square foot of quilted fabric? Within what limits is this valid?
An extra minute of cutting time? Within what limits is this valid?
An extra minute of sewing time? Within what limits is this valid?
(d) Suppose the requirement to produce at least 120 king size comforters were relaxed. How
would this affect the optimal daily profit?
Question 2: Restaurant crew assignment
Burger Boy Restaurant is open from 8:00 A.M. to 10:00 P.M. daily. In addition to the hours of
business, a crew of workers must arrive one hour early to help set up the restaurant for the day’s
operations, and another crew of workers must stay one hour after 10:00 P.M. to clean up after
closing. Burger Boy operates with nine different shifts:
Shift Type Daily Salary ($)
1. 7AM-9AM Part-time 15
2. 7AM-11AM Part-time 25
3. 7AM-3PM Full-time 52
4. 11AM-3PM Part-time 22
5. 11AM-7PM Full-time 54
6. 3PM-7PM Part-time 24
2
Shift Type Daily Salary ($)
7. 3PM-11PM Full-time 55
8. 7PM-11PM Part-time 23
9. 9PM-11PM Part-time 16
A needs assessment study has been completed, which divided the workday at Burger Boy into
eight 2-hour blocks. The number of employees needed for each block is as follows:
Time Block Employees Needed
7AM–9AM 8
9AM–11AM 10
11AM–1PM 22
1PM–3PM 15
3PM–5PM 10
5PM–7PM 20
7PM–9PM 16
9PM–11PM 8
Burger Boy wants at least 40% of all employees at the peak time periods of 11:00 A.M. to 1:00 P.M.
and 5:00 P.M. to 7:00 P.M. to be full-time employees. At least two full-time employees must be on
duty when the restaurant opens at 7:00 A.M. and when it closes at 11:00 P.M.
Formulate and solve an IP that Burger Boy can use to determine how many employees it should
hire for each of its nine shifts to minimize its overall daily employee costs.
Problem 3: Law enforcement
The police department of the city of Flint, Michigan, has divided the city into 15 patrol sectors,
such that the response time of a patrol unit (squad car) will be less than three minutes between
any two points within the sector.
Until recently, 15 units, one located in each sector, patrolled the streets of Flint from 7:00 P.M. to
3:00 A.M. However, severe budget cuts have forced the city to eliminate some patrols. The chief
of police has mandated that each sector be covered by at least one unit located either within the
sector or in an adjacent sector.
The accompanying figure depicts the 15 patrol sectors of Flint, Michigan. Formulate and solve an
IP that will determine the minimum number of units required to implement the chief’s policy.
3
Problem 4: Paper rolls
The Gem City Paper Company produces rolls of paper of various types for its customers. One
type is produced in standard rolls that are 50 inches wide and 100 yards long. Customers of this
type of paper order rolls that are 100 yards long but can have any of the widths 12, 15, 25, 30, and
40 inches. In a given week, Gem City Paper waits for all orders and then decides how to cut its
50-inch rolls to satisfy the orders. The weekly number of orders for each roll width is provided in
the table below. Each week this company must decide how to cut its rolls in the most economical
way to meet its orders. Specifically, it wants to produce and cut as few rolls as possible. Formulate
and solve an IP to help Gem City Paper find the best way to meet all weekly customer demands.
(Hint: list all the feasible patterns that can be used to cut a 50-inch roll of paper).
Width 12 15 25 30 40
Requirement 40 30 20 20 20
Problem 5: Piping
It is anticipated that steel production at a new plant in Bethlehem, Pennsylvania, will generate
approximately 50,000 gallons of raw sewage per hour that must be treated at a local treatment
facility. The plant plans to use excess capacity on existing pipes. Formulate a LP to determine
the capacity of the current system and hence determine if the existing system of pipes between
pumping stations be sufficient to support this operation, or will additional piping capacity be
required? The numbers on arcs give the maximum throughput for each pipe in thousands of
gallons per hour. Sewage can flow in either direction between Stations 1 and 2 and Stations 4 and
5.
4
Problem 6: Boilers
A power plant has three boilers. If a given boiler is operated, it can be used to produce a quantity
of steam (in tons) between the minimum and maximum given in Table 1. The cost of producing
a ton of steam on each boiler is also given. Steam from the boilers is used to produce power on
three turbines. If operated, each turbine can process an amount of steam (in tons) between the
minimum and maximum given in Table 2. The cost of processing a ton of steam and the power
produced by each turbine is also given. Formulate an IP that can be used to minimize the cost of
producing 8,000 kwh of power.
Table 1:
Boiler Number Min Steam Max Steam Cost/Ton ($)
1 500 1,000 10
2 300 900 8
3 400 800 6
Table 2:
Turbine Number Minimum Maximum Kwh per Ton of Steam ($) Processing Cost per Ton ($)
1 300 600 4 2
2 500 800 5 3
3 600 900 6 4
Problem 7: Motorhomes
Luxor Motorhomes has two plants, one in Riverside, California, and the other in Des Moines,
Iowa. Each plant can produce three different models: the Grand Cruiser, the Traveler, and the
Weekender. Labor time at the Riverside plant limits production to 600 models per month, while
the Des Moines plant can produce up to 1000 models per month. The manufacturing costs and
monthly production capacities for each model vary, depending on the plant. These costs are sum-
marized in the following table.
Manufacturing Cost
5
Riverside Des Monies
Grand Cruiser $53,000 $50,000
Traveler $29,000 $27,000
Weekends $18,000 $17,000
Maximum Monthly Production
Riverside Des Monies
Grand Cruiser 200 400
Traveler 500 500
Weekends 600 900
Once the units are manufactured, they are shipped to central distribution locations in Florida,
Texas, and California, where they are ultimately purchased by retailers. The demand for mo-
torhomes at the distribution locations for this month’s production is as follows.
Demand for Motorhomes
Florida Texas California
Grand Cruiser 100 50 150
Traveler 200 100 300
Weekends 225 175 250
The transportation costs for shipping a motorhome from a plant to a distribution center are inde-
pendent of the model. These are given in the following table.
Motorhome Shipping Costs
Florida Texas California
Riverside $2000 $700 $300
Des Monies $1000 $800 $1200
Formulate this problem as a capacitated transshipment problem and solve for the optimal produc-
tion and distribution of motorhomes during this month.
(Hint: Define a set of nodes for the plants, a set for the models, and a set for the models at the
distribution locations.)
Problem 8: Project scheduling 1
This problem deals with the creation of a project schedule; specifically, the project of building a
house. The project has been divided into a set of jobs. The problem is to schedule the time at
which each of these jobs should start and also to predict how long the project will take. Naturally,
the objective is to complete the project as quickly as possible (time is money!). Over the duration
6
of the project, some of the jobs can be done concurrently. But, as the following table shows, certain
jobs definitely can’t start until others are completed.
Job Duration (weeks) Must be preceded by
0. Sign contract with buyer 0 -
1. Framing 2 0
2. Roofing 1 1
3. Siding 3 1
4. Windows 2.5 3
5. Plumbing 1.5 3
6. Electrical 2 2, 4
7. Inside finishing 4 5, 6
8. Outside painting 3 2, 4
9. Complete the sale to buyer 0 7, 8
One possible schedule is the following:
Job Start time
0. Sign contract with buyer 0
1. Framing 1
2. Roofing 4
3. Siding 6
4. Windows 10
5. Plumbing 9
6. Electrical 13
7. Inside finishing 16
8. Outside painting 14
9. Complete the sale to buyer 21
With this schedule, the project duration is 21 weeks (the difference between the start times of jobs
9 and 0).
To model the problem as a linear program, introduce the following decision variables: tj - the start
time of job j.
(a) Write an expression for the objective function, which is to minimize the project duration.
(b) For each job j, write a constraint for each job i that must precede j; the constraint should
ensure that job j doesn’t start until job i is finished. These are called precedence constraints.
(c) Write down a complete LP formulation.
Problem 9 : Project scheduling 2
This problem generalizes the specific example of Problem 8. A project consists of a set of jobs J.
For each job j ∈ J there is a certain set Pj of other jobs that must be completed before job j can be
started. (This is called the set of predecessors of job j.) One of the jobs, say s, is the starting job; it
7
has no predecessors. Another job, say t, is the final (or terminal) job; it is not the predecessor of
any other job. The time it will take to do job j is denoted dj (the duration of the job).
The problem is to decide what time each job should begin so that no job begins before its pre-
decessors are finished, and the duration of the entire project is minimized. Using the notation
introduced above, write out a complete linear programming formulation of this problem.
Problem 10: Project scheduling 3
Let xij denote the dual variable corresponding to the precedence constraint that ensures job j
doesn’t start until job i finishes.
(a) Write out the dual to the specific linear program you formulated in Problem 8.
(b) Write out the dual to the general linear program you formulated in Problem 9.
(c) Describe how the optimal value of the dual variable xij can be interpreted.
Problem 11: Project scheduling 4
Here is an algorithm for computing optimal start times tj:
1. List the jobs so that the predecessors of each job come before it in the list.
2. Put t0 = 0.
3. Go down the list of jobs and for job j put tj = max{ti + di : i is a predecessor of j}.
(a) Apply this algorithm to the specific instance from Problem 8. What are the start times of
each of the jobs? What is the project duration?
(b) Prove that the solution found in Part (a) is optimal by solving the LP you formulated in
Problem 8 and comparing the solutions.