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

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* 200)+(X_3-200)15+(10 * 200)+(X_4-200 )* 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.