QBUS2310代写、代写Python编程设计

日期：2022-11-04 08:44

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.