Solved Problem 9-1 Don Yale, president of Hardrock Concrete Company, has plants in three locations and is currently working on three major construction projects, located at different sites. The shipping cost per truckload of concrete, plant capacities, and project requirements are provided in the accompanying table.

Formulate Hardrock’s transportation problem as a linear program and solve using software.

Solution

Define the variables as

$$X_{ij}=\text{number of units shipped from Plant }i\text{ to Project }j$$

where

$$\begin{array}{l}i\text{ = 1, 2, 3 with 1 = Plant 1, 2 = Plant 2, and 3 = Plant 3}\\ j\text{ = 1, 2, 3 with 1 = Project A, 2 = Project B, and 3 = Project C}\end{array}$$

The linear program formulation is

$$\text{Minimize total cost}=10X_{11}+4X_{12}+11X_{13}+12X_{21}+5X_{22}+8X_{23}+9X_{31}+7X_{32}+6X_{33}$$

subject to

$$\begin{array}{l}{X}_{\text{11}}\text{ + }{X}_{\text{21}}\text{ + }{X}_{\text{31}}\text{ = }\text{40}\left(\text{Project A requirements}\right)\\ X_{\text{12}}\text{ + }{X}_{\text{22}}\text{ + }{X}_{\text{32}}\text{ = }\text{50}\left(\text{Project B requirements}\right)\\ X_{\text{13}}\text{ + }{X}_{\text{23}}\text{ + }{X}_{\text{33}}\text{ = }\text{60}\left(\text{Project C requirements}\right)\\ X_{\text{11}}\text{ + }{X}_{\text{12}}\text{ + }{X}_{\text{13}}\le \text{ 70}\left(\text{Plant 1 capacity}\right)\\ X_{\text{21}}\text{ + }{X}_{\text{22}}\text{ + }{X}_{\text{23}}\le \text{ 50}\left(\text{Plant 2 capacity}\right)\\ X_{\text{31}}\text{ + }{X}_{\text{32}}\text{ + }{X}_{\text{33}}\le \text{ 30}\left(\text{Plant 3 capacity}\right)\\ \begin{array}{lll}\hfill & \text{ All variables} \ge \text{ 0}\hfill & \hfill \end{array}\end{array}$$

The computer output found using Excel QM gives the optimal solution. From Plant 1, ship 20 units to Project A and 50 units to Project B. From Plant 2, ship 50 units to Project C. From Plant 3, ship 20 units to Project A and 10 units to Project B. The total cost of this solution is $1,040. While not shown in the computer output, there are alternate optimal solutions to this problem.

9.3-6 Full Alternative Text

Solved Problem 9-2 Prentice Hall, Inc., a publisher headquartered in New Jersey, wants to assign three recently hired college graduates—Jones, Smith, and Wilson—to regional sales districts in Omaha, Dallas, and Miami. But the firm also has an opening in New York and would send one of the three there if it were more economical than a move to Omaha, Dallas, or Miami. It will cost $1,000 to relocate Jones to New York, $800 to relocate Smith there, and $1,500 to move Wilson. What is the optimal assignment of personnel to offices?

Because there are three new hires and four offices when New York is included, the problem is not balanced. It is impossible for all four cities to have a person assigned (i.e., there is no feasible solution). Therefore, a dummy source (new hire) is added, and the costs are zero for this dummy. Thus, the variables could be omitted from the objective function, but they are included for the sake of completeness.

Define the variables as

where

The linear program formulation is

subject to

The solution found using Excel QM is shown below, and it provides the optimal solution: Jones is assigned to Miami $\left(X_{12}=1\right),$ Smith is assigned to New York $\left(X_{24}=1\right),$ Wilson is assigned to Omaha $\left(X_{31}=1\right),$ and no one (the dummy) is assigned to Dallas $\left(X_{43}=1\right).$ The total cost is $2,400.