Example 8

EXAMPLE 8 Delivering Bread

Imagine that we have three bakeries and three stores, though the ideas we develop will also solve problems where the number of stores and bakeries are not the same. The three stores require 3 dozen, 7 dozen, and 1 dozen loaves of bread, respectively, while the three bakeries can supply 8 dozen, 1 dozen, and 2 dozen loaves, respectively. The information given so far can be displayed in Figure 4.18, where the “suppliers” are represented by the rows of the table (labeled with Roman numerals) and the “demanders” are represented by the columns (labeled with Hindu-Arabic numerals).

Figure 4.18: Figure 4.18 A representation of a specific problem involving meeting the demands of three stores for breads from the supplies available at three bakeries. Shipping costs between bakeries and stores are also shown.

The numbers of breads available and the numbers being required are shown on the right side and bottom of the table and will be referred to as rim conditions. Each entry of the table shown in Figure 4.18 is known as a cell. it is convenient to have a name for each of these cells. For example, the cell in the third row and second column will be denoted (III, 2). The first number always corresponds to a row, the second to a column. Thus cell (I, 2) refers to Bakery I and Store 2.

In deciding which bakeries should ship to which stores, it seems natural to take into account the costs of shipping a dozen breads from a particular bakery to a particular store. if Bakery I is farther from Store 2 than is Bakery II, it seems reasonable that the shipping cost for I will be higher than for II when shipping to that particular store.

150

However, the costs of shipping may also involve time considerations. (The distance to a store may be shorter, but it may be that this route is a very slow one.) Also, it may take extra time for a truck coming from I to park when making the next delivery.

The numbers we use in our diagrams are “aggregate” costs. The nice thing about what we are doing is that the solution method works independently of the way the costs are arrived at or computed. These costs (see Figure 4.18) are shown in the upper- right-hand corner of a cell. Thus the number 9 shown in cell (I, 2) means that it costs nine units to ship a bread from Bakery I to Store 2. Our goal will be to supply the stores with the breads they require from the supplies available at the bakeries so that the total cost of providing the breads to the stores is as small as possible (a minimum).