For our example, suppose that the Wireless Widget (WW) Company has six warehouses supplying eight vendors with their widgets. Each warehouse has a supply of widgets that cannot be exceeded, and each vendor has a demand for widgets that must be satisfied. WW wants to determine how many widgets to ship from each warehouse to each vendor so as to minimize the total shipping cost. This is a classic optimization problem referred to as the transportation problem.

The following diagram illustrates the problem:

 

 

Wireless Widget's Shipping Network

Since each warehouse can ship to each vendor, there are a total of 48 possible shipping paths, or arcs. We will need a variable for each of these arcs to represent the amount shipped on the arc.