Assignment - transportation assignment and transshipment

Question

Assignment - Transportation, Assignment, and Transshipment Problems

Part A - Formulating Transportation Problems

Q1. A company supplies goods to three customers, who each require 30 units. The company has two warehouses. Warehouse 1 has 40 units available, and warehouse 2 has 30 units available. The costs of shipping 1 unit from warehouse to customer are shown in Table 7. There is a penalty for each unmet customer unit of demand: With customer 1, a penalty cost of $90 is incurred; with customer 2, $80; and with customer 3, $110. Formulate a balanced transportation problem to minimize the sum of shortage and shipping costs.

Q2. Referring to Problem 1, suppose that extra units could be purchased and shipped to either warehouse for a total cost of $100 per unit and that all customer demand must be met. Formulate a balanced transportation problem to minimize the sum of purchasing and shipping costs.

Q3. A shoe company forecasts the following demands during the next six months: month 1-200; month 2-260; month 3-240; month 4-340; month 5-190; month 6-150. It costs $7 to produce a pair of shoes with regular-time labor (RT) and $11 with overtime labor (OT). During each month, regular production is limited to 200 pairs of shoes, and overtime production is limited to 100 pairs. It costs $1 per month to hold a pair of shoes in inventory. Formulate a balanced transportation problem to minimize the total cost of meeting the next six months of demand on time.

Q4. Steelco manufactures three types of steel at different plants. The time required to manufacture 1 ton of steel (regardless of type) and the costs at each plant are shown in Table 8. Each week, 100 tons of each type of steel (1, 2, and 3) must be produced. Each plant is open 40 hours per week.

a. Formulate a balanced transportation problem to minimize the cost of meeting Steelco's weekly requirements.

b. Suppose the time required to produce 1 ton of steel depends on the type of steel as well as on the plant at which it is produced (see Table 9,). Could a transportation problem still be formulated?

Q5. A hospital needs to purchase 3 gallons of a perishable medicine for use during the current month and 4 gallons for use during the next month. Because the medicine is perishable, it can only be used during the month of purchase.

Two companies (Daisy and Laroach) sell the medicine. The medicine is in short supply. Thus, during the next two months, the hospital is limited to buying at most 5 gallons from each company. The companies charge the prices shown in Table 10. Formulate a balanced transportation model to minimize the cost of purchasing the needed medicine.

Q6. A bank has two sites at which checks are processed. Site 1 can process 10,000 checks per day, and site 2 can process 6,000 checks per day. The bank processes three types of checks: vendor, salary, and personal. The processing cost per check depends on the site (see Table 11). Each day, 5,000 checks of each type must be processed. Formulate a balanced transportation problem to minimize the daily cost of processing checks.

Q7. The U.S. government is auctioning off oil leases at two sites: 1 and 2. At each site, 100,000 acres of land are to be auctioned. Cliff Ewing, Blake Barnes, and Alexis Pickens are bidding for the oil. Government rules state that no bidder can receive more than 40% of the land being auctioned. Cliff has bid $1,000/acre for site 1 land and $2,000/acre for site 2 land. Blake has bid $900/acre for site 1 land and $2,200/acre for site 2 land. Alexis has bid $1,100/acre for site 1 land and $1,900/acre for site 2 land. Formulate a balanced transportation model to maximize the government's revenue.

Q8. The Ayatola Oil Company controls two oil fields. Field 1 can produce up to 40 million barrels of oil per day, and field 2 can produce up to 50 million barrels of oil per day. At field 1, it costs $3 to extract and refine a barrel of oil; at field 2, the cost is $2. Ayatola sells oil to two countries: England and Japan. The shipping cost per barrel is shown in Table 12. Each day, England is willing to buy up to 40 million barrels (at $6 per barrel), and Japan is willing to buy up to 30 million barrels (at $6.50 per barrel). Formulate a balanced transportation problem to maximize Ayatola's profits.

Q9. For the examples and problems of this section, discuss whether it is reasonable to assume that the proportionality assumption holds for the objective function.

Q10. Touche Young has three auditors. Each can work as many as 160 hours during the next month, during which time three projects must be completed. Project 1 will take 130 hours; project 2, 140 hours; and project 3, 160 hours. The amount per hour that can be billed for assigning each auditor to each project is given in Table 13. Formulate a balanced transportation problem to maximize total billings during the next month.

Q11. Paperco recycles newsprint, uncoated paper, and coated paper into recycled newsprint, recycled uncoated paper, and recycled coated paper. Recycled newsprint can be produced by processing newsprint or uncoated paper. Recycled coated paper can be produced by recycling any type of paper. Recycled uncoated paper can be produced by processing uncoated paper or coated paper. The process used to produce recycled newsprint removes 20% of the input's pulp, leaving 80% of the input's pulp for recycled paper. The process used to produce recycled coated paper removes 10% of the input's pulp. The process used to produce recycled uncoated paper removes 15% of the input's pulp. The purchasing costs, processing costs, and availability of each type of paper are shown in Table 14. To meet demand, Paperco must produce at least 250 tons of recycled newsprint pulp, at least 300 tons of recycled uncoated paper pulp, and at least 150 tons of recycled coated paper pulp. Formulate a balanced transportation problem that can be used to minimize the cost of meeting Paperco's demands.

Q12. Explain how each of the following would modify the formulation of the Sailco problem as a balanced transportation problem:

a. Suppose demand could be backlogged at a cost of $30/sailboat/month. (Hint: Now it is permissible to ship from, say, month 2 production to month 1 demand.)

b. If demand for a sailboat is not met on time, the sale is lost and an opportunity cost of $450 is incurred.

c. Sailboats can be held in inventory for a maximum of two months.

d. At a cost of $440/sailboat, Sailco can purchase up to 10 sailboats/month from a subcontractor

Table 7
From	To
	Customer 1	Customer 2	Customer 3
Warehouse 1	$15	$35	$25
Warehouse 2	$10	$50	$40

 

Table 8
Plant	Cost ($)			Time (minutes)
	Steel 1	Steel 2	Steel 3
1	60	40	28	20
2	50	30	30	16
3	43	20	20	15

 

Table 9
Plant	Time (minutes)
	Steel 1	Steel 2	Steel 3
1	15	12	15
2	15	15	20
3	10	10	15

 

Table 10
Company	Current Month's Price per Gallon ($)	Next Month's Price per Gallon ($)
Daisy	800	720
Laroach	710	750

 

Table 11
Checks	Site (c)
	1	2
Vendor	5	3
Salary	4	4
Personal	2	5

 

Table 12
From ($)	To ($)
	England	Japan
Field 1	1	2
Field 2	2	1

 

 

Table 13
Auditor	Project ($)
	1	2	3
1	120	150	190
2	140	130	120
3	160	140	150

 

Table 14
	Purchase Cost per Ton of Pulp ($)	Processing Cost per Ton of Input ($)	Availability
Newsprint	10		500
Coated paper	9		300
Uncoated paper	8		200
NP used for RNP		3
NP used for RCP		4
UCP used for RNP		4
UCP used for RUP		1
UCP used for RCP		6
CP used for RUP		5
CP used for RCP		3

Part B - Assignment Problems

Q1. Five employees are available to perform four jobs. The time it takes each person to perform each job is given in Table 50. Determine the assignment of employees to jobs that minimizes the total time required to perform the four jobs.

Q2. Doc Councillman is putting together a relay team for the 400-meter relay. Each swimmer must swim 100 meters of breaststroke, backstroke, butterfly, or freestyle. Doc believes that each swimmer will attain the times given in Table 51. To minimize the team's time for the race, which swimmer should swim which stroke?

Q3. Tom Cruise, Freddy Prinze Jr., Harrison Ford, and Matt LeBlanc are marooned on a desert island with Jennifer Aniston, Courteney Cox, Gwyneth Paltrow, and Julia Roberts. The "compatibility measures" in Table 52 indicate how much happiness each couple would experience if they spent all their time together. The happiness earned by a couple is proportional to the fraction of time they spend together. For example, if Freddie and Gwyneth spend half their time together, they earn happiness of ½(9) = 4.5.

a. Let x_ij be the fraction of time that the ith man spends with the jth woman. The goal of the eight people is to maximize the total happiness of the people on the is-land. Formulate an LP whose optimal solution will yield the optimal values of the x_ij's.

b. Explain why the optimal solution in part (a) will have four x_ij = 1 and twelve x_ij = 0. The optimal solution requires that each person spend all his or her time with one person of the opposite sex, so this result is often referred to as the Marriage Theorem.

c. Determine the marriage partner for each person.

d. Do you think the Proportionality Assumption of linear programming is valid in this situation?

Q4. A company is taking bids on four construction jobs. Three people have placed bids on the jobs. Their bids (in thousands of dollars) are given in Table 53 (a * indicates that the person did not bid on the given job). Person 1 can do only one job, but persons 2 and 3 can each do as many as two jobs.

Determine the minimum cost assignment of persons to jobs.

Q5. Greydog Bus Company operates buses between Boston and Washington, D.C. A bus trip between these two cities takes 6 hours. Federal law requires that a driver rest for four or more hours between trips. A driver's workday consists of two trips: one from Boston to Washington and one from Washington to Boston. Table 54 gives the departure times for the buses. Greydog's goal is to minimize the total downtime for all drivers. How should Greydog assign crews to trips? Note: It is permissible for a driver's "day" to overlap midnight. For example, a Washington-based driver can be assigned to the Washington-Boston 3 P.M. trip and the Boston-Washington 6 A.M. trip.

Q6. Five male characters (Billie, John, Fish, Glen, and Larry) and five female characters (Ally, Georgia, Jane, Rene, and Nell) from Ally McBeal are marooned on a desert island. The problem is to determine what percentage of time each woman on the island should spend with each man. For example, Ally could spend 100% of her time with John or she could "play the ?eld" by spending 20% of her time with each man. Table 55 shows a "happiness index" for each potential pairing of a man and woman. For example, if Larry and Rene spend all their time together, they earn 8 units of happiness for the island.

a. Play matchmaker and determine an allocation of each man and woman's time that earns the maximum total happiness for the island. Assume that happiness earned by a couple is proportional to the amount of time they spend together.

b. Explain why the optimal solution to this problem will, for any matrix of "happiness indices," always involve each woman spending all her time with one man.

c. What assumption made in the problem is needed for the Marriage Theorem to hold?

Q7. Any transportation problem can be formulated as an assignment problem. To illustrate the idea, determine an assignment problem that could be used to find the optimal solution to the transportation problem in Table 56. (Hint: You will need five supply and five demand points).

Q8. The Chicago board of education is taking bids on the city's four school bus routes. Four companies have made the bids in Table 57.

a. Suppose each bidder can be assigned only one route. Use the assignment method to minimize Chicago's cost of running the four bus routes.

b. Suppose that each company can be assigned two routes. Use the assignment method to minimize Chicago's cost of running the four bus routes. (Hint: Two supply points will be needed for each company.)

Q9. Show that step 3 of the Hungarian method is equivalent to performing the following operations: (1) Add k to each cost that lies in a covered row. (2) Subtract k from each cost that lies in an uncovered column.

Q10. Suppose c_ij is the smallest cost in row i and column j of an assignment problem. Must x_ij = 1 in any optimal assignment?

Table 50
Person	Time (Hour)
	Job 1	Job 2	Job 3	Job 4
1	22	18	30	18
2	18	-	27	22
3	26	20	28	28
4	16	22	-	14
5	21	-	25	28
Note - Dashes indicate person cannot do that particular job.

 

Table 51
Swimmer	Time (seconds)
	Free	Breast	Fly	Back
Gary Hall	54	54	51	53
Mark Spitz	51	57	52	52
Jim Montgomery	50	53	54	56
Chet Jastremski	56	54	55	53

Textbook - Operations Research APPLICATIONS AND ALGORITHMS, FOURTH EDITION by Wayne L. Winston WITH CASES BY Jeffrey B. Goldberg.

Chapter 7 - Transportation, Assignment, and Transshipment Problems.