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).

All problems have equal weight. Some are easy. Others, not so much.

Good luck!

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.

(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

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.

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).

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.

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

Riverside            Des Monies

Grand Cruiser Traveler          Weekends

$53,000

$29,000

$18,000

$50,000

$27,000

$17,000

Maximum Monthly Production

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

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 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.