21-257 Past-Due Homework, Fall 1999

21-257 Past-Due Homework
Fall 1999

All homework assignments are from Introduction to Mathematical Programming by Russell C. Walker, Prentice Hall, 1999, unless otherwise noted.

Homework 1: Due on Monday, August 30, 1999. Write up solutions to the following problems

4, 10 in Section 1.3
4, 6, 7, 11, 12, 14, 16 in Section 1.4 (In problem 14 the objective function is 4y_1 + 2y_2 instead of 4y_1 + 2y_1.)
What is a major disadvantage of the graphical method for solving linear programs? Give an application of linear programming that would be difficult to attack with the graphical method.

Homework 2: Due on Wednesday, September 8, 1999. Write up solutions to the following problems.

Exercises 2, 3, 5 from Section 2.6 (in #5 use Gaussian elimination)
Exercises 2, 5 in Section 3.2 (you might want to wait until we talk about the Simplex Algorithm before doing #5)
Exercises 2, 4, 6, 11 from Section 3.3
Give an example of a linear program that has a degenerate basic solution. Identify the degenerate basic solution. Explain the significance of degenerate solutions in the context of the simplex algorithm.

Homework 3: Due on Wednesday, September 15, 1999 in lecture.

Read the article, "Raw Material Management at Welch's, Inc." by Edmund W. Schuster and Stuart J. Allen, and answer the following questions. The article appears in Interfaces, vol. 28 No. 5, September-October 1998 (pp. 13-24). It can be downloaded from the Interfaces Webpage (login as Guest) and it is located on reserve in Hunt Library (ask for a copy at the circulation desk on the first floor) and in the Bounded Journal section of Hunt Library (3rd Floor).
1. The Juice-Availability Committee (JAC) was formed to decide how to use the grape crop. What two features of the industry, listed in the article, make this decision complex?
2. The MRP and cost-accounting systems that Welch's employed did not always determine a feasible and optimal plan of raw material movement and choices for recipes used in production. This was primarily due to 2 assumptions that the designers of the MRP and the cost-accounting systems made. What were the 2 assumptions?
3. Originally the LP which modelled the raw materials distribution had 8000 variables. The authors managed to cut this number down to 324. What assumptions did they make in order to decrease the number of variables? What impact might this assumption have on the results of the LP?
4. Describe what the objective function and the Material Balance constraint (listed as constraint (2) in the paper) model.
5. How did Welch's Inc benefit from the implementation of the LP proposed by the authors?
Exercises 8, 11, 15 from Section 3.5 (In these exercise, you are only required to formulate the LP; you don't have to solve it)
Formulate the LP for the situation described in Example 3.5.6.

Homework 4: Due on Tuesday, September 21, 1999 by 5:00 in your TA's mailbox.

Exercise 5 in Section 3.5 (you are encouraged to use LINDO to do this problem)
Exercises 2, 4 from Section 3.6 (do not use any computer package to solve Exercise 2).
Explain what the following situation indicates about a LP:
- When the artifical objective function is maximized, the artificial objective function has a negative value.
Exercise 11 from Section 3.7.

Homework 5: Due on Monday, September 27, 1999 in lecture.

Do not use any computer package to solve the problems for this assignment.
Exercises 2, 4, 15 from Section 3.7
Exercises 4, 8, 9 from Section 3.8

Homework 6: Due on Wednesday, October 13, 1999 in lecture.

Exercises 2, 3, 10, 11 from section 4.2

Formulate an integer program to solve the following problem.

Determine the minimum cost menu for a day using the foods listed below such that the total protein content of the food is at least 25 grams. We also require that the total number of calories not exceed 2000. The menu should consist of 3 meals: a breakfast, lunch and dinner. We require that each meal contain an entree and a side dish and that no meal contain two items which are "high" in carbohydrates. Below is the relevant information:

Entrees Side Dishes

Pizza Tuna Sub Oatmeal Hard-boiled
Egg Hamburger Yogurt Green Beans Baked Potato Ice Cream Apple

Protein Content (g) 13 30 4 6.3 12 13 2 3 2 0.4

Calories Content(kcal) 184 584 106 78 272 127 38 145 117 125

Is the food "high"
in carbohydrates? Yes Yes No No Yes No No Yes No Yes

Cost (dollars) $2.00 $3.50 $0.75 $0.30 $1.50 $0.60 $0.20 $0.40 $1.00 $0.20

	Entrees	Side Dishes
	Pizza	Tuna Sub	Oatmeal	Hard-boiled Egg	Hamburger	Yogurt	Green Beans	Baked Potato	Ice Cream	Apple
Protein Content (g)	13	30	4	6.3	12	13	2	3	2	0.4
Calories Content(kcal)	184	584	106	78	272	127	38	145	117	125
Is the food "high" in carbohydrates?	Yes	Yes	No	No	Yes	No	No	Yes	No	Yes
Cost (dollars)	$2.00	$3.50	$0.75	$0.30	$1.50	$0.60	$0.20	$0.40	$1.00	$0.20

Reminder: You only need to formulate the integer program; you are not asked to solve it.

Homework 7: Due on Monday, October 18, 1999 in lecture.

Read the article, "A Truck Scheduling System Improves Efficiency in the Forest Industries," by Weintraub et.al. and answer the following questions. The article appears in Interfaces vol. 26 no. 4, July-August 1996, pp 1-12. A copy of the article is located on Reserve in Hunt Library, behind the circulation desk on the first floor and the journal is located in the Bounded Journals section of Hunt Library on the third floor.
1. The article describes an elaborate transportation problem. In the article what are the destinations; origins; and the 3 products being shipped from origins to destinations.
2. In this particular transportation problem, the demand constraints were generally flexible. Give an example of a situation which would cause a certain demand constraint to become more rigid.
3. Aside from the demand constraints, list three other constraints and give some justification why each constraint is warranted.
4. Due to the combinatorial complexity of the integer program that models this particular transportation problem, the authors developed a heuristic algorithm to come up with an acceptable shipping schedule. Using the rules discussed in the article, consider the Scenario from lecture and answer the question:
  Which delivery will Truck 3 most likely be assigned at 1:00pm? (Justify your answer).
5. Describe how the forest firms in Chile implement the new system for solving the transportation problem.
6. Describe one of the benefits that the forest firms experienced from implementing the new system.
Note: This article will be discussed in lecture on Wednesday, October 13, 1999.

Homework 8: Due on Monday, October 25, 1999 in lecture.

Exercises 2, 6, and 8 from Section 4.3 (Only 3 problems!)

Homework 9: Due on Monday, November 1, 1999 in lecture.
Notice the change in the assignment. Do problem 6 from 7.3 instead of 7 from 7.3 (as #7 does not exist).

Exercise 3 from Section 7.2
Exercises 1, 4, 6 from Section 7.3

Homework 10: Due on Monday, November 8, 1999 in lecture.

Exercises 1, 2, 5 from section 7.4
Exercises 4, 6 from Section 7.5 (solve number 4 graphically or include a graph which illustrates the steps of the branch and bound algorithm)
Reminder: The project consultations are this week. You will need to set up an appointment with me (by signing the sheet on my office door, 7213 Wean). You must have made some progress on your projects before consulting with me.

Homework 11: Due on Monday, November 15, 1999 in lecture.

Exercise 4 from Sec 7.6 (You will need to use LINDO to solve this problem)
Formulate the Integer Program for Exercises 2 and 10 from Sec 7.6

Formulate an Integer Program for the following problems:

Consider the problem faced by a track coach of entering four of his sprinters in a quarter-mile relay. Not only are the sprinters' base running times factors, but also the time-losses associated with baton handoffs play an important role in determining the order of the sprinters in the relay. Below are the base times for the four different sprinters on the 4 different legs of the race:

	Running times				Extra time needed if Sprinter i hands off to Sprinter j where i corresponds to row i and j corresponds to column j
	Leg 1	Leg 2	Leg 3	Leg 4	Sprinter 1	Sprinter 2	Sprinter 3	Sprinter 4
Sprinter 1	10.8	10.6	10.6	10.5	0	0.5	0.3	0.5
Sprinter 2	10.6	10.1	10.2	10.1	0.3	0	0.2	0.6
Sprinter 3	10.5	10.1	10.1	10.2	0.3	0.2	0	0.7
Sprinter 4	10.7	10.5	10.6	10.4	0.2	0.5	0.3	0

Determine the assignment of the sprinters to the legs of the race so that no sprinter runs more than one leg and the total time of the race is minimized. (This problem was taken from Optimal Sports Strategies by S. Ladany and R. Machol, 1977.)

Terminology to those unfamilar with relay races: A quarter-mile relay is a race involving 4 sprinters. The first sprinter runs a quarter of a mile and then hands off a baton to the next runner, who then runs a quarter-mile before handing off the baton to the third runner, etc. The part of the race that the first sprinter runs is called the first leg. The second runner runs the second leg, etc.

(Cut and Trim Problem) Assume that 2 machines A and B are available; machine A is capable of cutting a standard roll of 100 in and machine B is capable of cutting a standard roll of 80 in. The following orders of various widths must be cut:

Width
(in.) Demand
(rolls)

45 862

36 341

31 87

14 216

We assume that as many standard rolls as necessary are available and that, excluding the unavoidable trim loss, only the widths 45 in., 36 in., 31 in. and 14 in. are cut. Determine the cutting plan to minimize trim loss. (This problem was taken from Linear Programming by S. Gass, 1975.)

Width (in.)	Demand (rolls)
45	862
36	341
31	87
14	216

Access the Current Homework List.
Return to the Optimization Page.
Return to the Syllabus.