1.  Formulate the following problems as an LP (a)  Minimise ∥Ax − b∥1 + ∥x∥∞

(b)  Minimise ∥x∥1     subject to     ∥Ax − b∥∞  ≤ 1

2.  (10 points)  Fantastic Homeware produces three sizes of quilts  (single, queen, and king size) that it markets to major retail establishments throughout the country.   Due to contracts with these establishments, Fantastic Homeware must produce at least 120 of each size quilt daily. It pays $0 .50 per pound for stuffing and $0.20 per square foot for quilt fabric used in the production of the quilts. 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 Fantastic Homeware.  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 quilt.

Table 1: Fantastic Homeware data.

(a)  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 quilts that Fantastic Homeware could charge

while maintaining the optimal production schedule recommended in part (a)?

(c)  Suppose Fantastic Homeware could obtain additional stuffing or quilted fabric from supplemen- tary suppliers. What is the most it should be willing to pay for:

1.  An extra pound of stuffing? Within what limits is this valid?

2.  An extra square foot of quilt fabric? Within what limits is this valid?

3.  An extra minute of cutting time? Within what limits is this valid?

4.  An extra minute of sewing time? Within what limits is this valid?

(d)  Suppose the requirement to produce at least 120 king size quilts were relaxed. How would this affect the optimal daily profit?

3.  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 a binary model that will determine the minimum number of units required to implement the chief ’s policy.

4.  The Scrivenshaft’s Quill Shop produces rolls of parchment 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 parchment 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, Scrivenshaft’s Quill Shop 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 model to help Scrivenshaft’s Quill Shop 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 parchment).

5. It is anticipated that steel production at a new plant in Indianapolis, Indiana, will generate approx- imately 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. Will the existing system of pipes between pumping stations be sufficient to support this operation, or will additional piping capacity be re- quired?  (The numbers give the maximum number of thousands of gallons per hour possible through each pipe.) Sewage can flow in either direction between Stations 1 and 2 and Stations 4 and 5.

6.  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 (2). 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 (3).  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 2: Maximum and minimum quantity produced by each boiler

Table 3: Maximum and minimum quantity processed by each turbine

7.  Lux MobileHome has two plants, one in Riverside, Melbourne, and the other in Carlisle, Perth. Each plant can produce three different models:  the Grand Lux, the Compact Lux, and the Light Lux. Labor time at the Riverside plant limits production to 600 models per month, while the Carlisle 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 summarized in the following table.

Manufacturing Costs and Maximum Monthly Production Levels

Table 4: Manufactoring Cost

Table 5: Maximum Monthly Production

Once the units are manufactured, they are shipped to central distribution locations in Sydney, Perth, and Melbourne, where they are ultimately purchased by retailers.  The demand for MobileHome at the distribution locations for this month’s production is as follows.

  Sydney    Perth    Melbourne

Grand Lux

Compact Lux

Light Lux

100

200

225

50

100

175

150

300

250