Question

Problem 1. Network-Flow Programming (25pt) A given merchandise must be transported at a minimum total cost between two origins (supply) and two destinations (demand). Destination 1 and 2 demand 500 and 700 units of merchandise, respectively. At the origins, the available amounts of merchandise are 600 and 800 units. USPS charges $5 per unit from origin 1 to demand 1, and $7 per unit from origin 1 to demand 2. From origin 2 to demand 1 and 2, USPS charges the same unit cost, $10 per unit, however, after 200 units, the unit cost of transportation increases by 50% (only from origin 2 to demand 1 and 2).
a) Formulate this as a network-flow problem in terms of objective function and constraint(s) and solve using Excel Solver.
b) How many units of merchandise should be shipped on each route and what is total cost?

Answer 1

Solution :

Cost

Destination           Destination         Destination                     Maximum supply

Origin 1                       5                          7                                           600

Origin 2                     10                         10                                          800

                         15, for > 200            15, for > 200

         Demand          500                       700

Variables

Destination       1          2

Origin 1             $X_1$        $X_2$

Origin 2            $X_3$        $X_4$

Constraints   :   $X_1$, $X_2$, $X_3$, $X_4$  ≥ 0

Supply : $X_1$ + $X_2$  ≤ 600

              $X_3$ + $X_4$ ≤ 800

Demand : $X_1$ + $X_3$  ≥ 500

              $X_2$ + $X_4$ ≥ 700

Objective function :

Min z = $5X_1+7X_2+10X_3+10X_4, \ (if \ X_3, X_4 \leq 200)$

$=5X_1+7X_2+(10\times 200)+(X_3-200)15+(10 \times 200)+(X_4-200 )\times 15 , \ \ (\text{else})$

Costs :

                  Destination 1       Destination  2

Origin 1         5                             7

Origin 2        10                           10

                     15                            15

Variables :

$X_1$        $X_2$

300    300  

200   400

$X_3$      $X_4$

Objective function : Min z = 10600

Constraints:

Supply    600 ≤ 600

                600 ≤ 800

Demand   500 ≥ 500

                 700 ≥ 500

Therefore, the total cost is 10,600.