This page presents several corrected exercises about automated planning and scheduling problems, more especially about transportation problems and the related algorithms: the stepping stone.

Exercise 1

A company has to transport supplies from plants to the construction sites. The three plants have 300, 300, 100 supply capacity respectively. And the three construction sites demand 200, 200, 300 respectively.

The transporting costs are shown in the following graph:

corrected exercises automated planning and scheduling problems transportation problems

Find how to allocate the supplies.

Exercise 2

Wheat is harvested in the Midwest and stored in grain elevators in three different cities — Kansas City, Omaha, and Des Moines. These grain elevators supply three flour mills, located in Chicago, St. Louis, and Cincinnati. Grain is shipped to the mills in railroad cars, each car capable of holding one ton of wheat. Each grain elevator is able to supply the following number of tons (ie, railroad cars) of wheat to the mills on a monthly basis.

corrected exercises automated planning and scheduling problems transportation problems

Each mill demands the following number of tons of wheat per month.

corrected exercises automated planning and scheduling problems transportation problems

The cost of transporting one ton of wheat from each grain elevator (source) to each mill (destination) differs according to the distance and rail system. These costs are shown in the following table. For example, the cost of shipping one ton of wheat from the grain elevator at Omaha to the mill at Chicago is $7.

corrected exercises automated planning and scheduling problems transportation problems

The problem is to determine how many tons of wheat to transport from each grain elevator to each mill on a monthly basis in order to minimize the total cost of transportation. Is there any alternative solution? If yes, which one?

Exercise 3

From the linear program below, formulate the transportation problem and solve it.

corrected exercises automated planning and scheduling problems transportation problems

Is there any alternative solution? If yes, which one?

Same as exercise 2.

Exercise 4

Take the same problem as exercise 2. Change the demand at Cincinnati to 350 tons. Solve it.

Exercise 5

Resolve the following LP problem:

corrected exercises automated planning and scheduling problems transportation problems

We introduce a dummy for j because supply (45 + 60 + 35) -demand (50 + 60) = 30:

corrected exercises automated planning and scheduling problems transportation problems

corrected exercises automated planning and scheduling problems transportation problems

Exercise 6

The Atlantic Coast Conference has four basketball games on a particular night. The conference office wants to assign four teams of officials to the four games in a way that will minimize the total distance traveled by the officials. The distances in miles for each team of officials to each game location are shown in Table below:

corrected exercises automated planning and scheduling problems transportation problems

Each supply and each demand are equal to 1. Solve it as a transportation problem.