Selected topics in finite mathematics/Transportation problems

Objectives

edit

To minimize the total cost of meeting the required demands based solely upon the supplies available.

Details

edit

Optimization Problem: A problem that seeks to discover either the minimum or maximum value possible

Constraint: An equation in an optimizing problem that must be satisfied.

Linear Program: an optimization problem in which the constraints and objectives are linear.

Transportation Problem: A linear program that can be thought of in terms of suppliers producing goods and demanders receiving the goods.

Northwest Corner Rule: To find a feasible solution "read the chart like a book," start in the top left hand corner.

Examples

edit
1. Consider the situation where two mills A and B are supplied by two farms M and N. Mill A demands 4 trucks of grain while mill B demands 6 trucks of grain. Farm M can produce 5 trucks of grain and farm N can produce 6 trucks of grain. Due to the location of the farms and mills, the transportation costs also vary: farm M can ship to mills A and B with costs 2 and 3 respectively, while farm N can ship to mills A and B with costs 1 and 4 respectively.


Caution: The following example may appear formidable because of its length. Consider that it is really four examples in one, because we push goods through a cycle four times: each time we are rearranging the transportation routes to reduce the total cost.

2. Consider the scenario where there are now three stores A, B, C trying to sell goods supplied by M, N, and L. The stores can sell 2, 3, and 7 goods respectively. The suppliers can supply 3, 4, and 5 goods respectively. The transportation cost for M to ship to the stores are 1, 5, and 2 respectively. For N the transportation costs are 2, 1, and 5 respectively. And lastly for L these costs are 4, 4, and 6 respectively.



3. In the example above, how were the cycles for the indicators found?

Nonexamples

edit

Homework

edit

Homework Solutions

edit