Al Akhawayn University Decision Making
School of Business Administration Dr. Yassine Benrqya
Assignment #1 –Basic Network Flow Models
P.1 (Transportation Problem)
A compressor company has plants in three locations: Cleveland, Chicago, and Boston. During the past week the total
production of a special compressor unit out of each plant has been 35, 50, and 40 units respectively. The company wants to
ship 45 units to a distribution center in Dallas, 20 to Atlanta, 30 to San Francisco, and 30 to Philadelphia. The unit
production and distribution costs from each plant to each distribution center are given in Table below.
What is the best shipping strategy?
a) Give the Linear program corresponding
b) Solve the problem using Excel
P.2 (Transportation Problem)
A company supplies goods to three customers, who each require 30 units. The company has two warehouses. Warehouse 1
has 40 units available, and warehouse 2 has 30 units available. The costs of shipping 1 unit from warehouse to customer
are shown in Table below. There is a penalty for each unmet customer unit of demand: With customer 1, a penalty cost of
$90 is incurred; with customer 2, $80; and with customer 3, $110.
a) Formulate the problem as a transportation problem to minimize the sum of shortage.
b) Solve the problem using Excel
P.3 (Transshipment Problem)
Widgetco manufactures widgets at two factories, one in Memphis and one in Denver. The Memphis factory can produce as
many as 150 widgets per day, and the Denver factory can produce as many as 200 widgets per day. Widgets are shipped
by air to customers in Los Angeles and Boston. The customers in each city require 130 widgets per day. Because of the
deregulation of airfares, Widgetco believes that it may be cheaper to first fly some widgets to New York or Chicago and
then fly them to their final destinations. The costs of flying a widget are shown in Table below. Widgetco wants to
minimize the total cost of shipping the required widgets to its customers.
a) Formulate as a transshipment problem to minimize the total cost.
b) Solve the problem using Excel
P.4 (The Shortest Path Problem)
A mail service company operates on network of postal hubs, represented in the figure below. We assume that hubs are
identified by nodes and that fixed delivery costs are associated with links between select hubs. These fixed costs are paid
once the company decides to move one mail order issued by a customer on a given link. Assume a customer issues a
delivery order from Hub #1 to Hub #7. Notice that the mail company always tries to answer orders at the lowest total
delivery cost.
4
3
4
5
1
3 5
1
3
4
4 8
7
3
2 3
6
a) Formulate this problem as a linear (possibly binary) programming problem.
b) Solve the problem using Excel Solver.
c) Use Dijkstra’s algorithm to solve the problem. Show clearly all the steps of the algorithm in action.
P.6 (The Maximum Flow Problem)
Consider the following flow network:
a) Solve the maximum flow problem on the above network by using the Ford Fulkerson algorithm
P.7 (Minimum Cost Flow Problem)
Each hour, an average of 900 cars enter the network in Figure below at node 1 and seek to travel to node 6. The time it
takes a car to traverse each arc is shown in Table below. In the Figure, the number above each arc is the maximum number
of cars that can pass by any point on the arc during a one-hour period. Formulate an MCNFP that minimizes the total time
required for all cars to travel from node 1 to node 6.
Representation of Traffic
Travel Times for Traffic
a) Formulate this problem as a linear programming problem. Indicate clearly the problem’s decision variables,
objective, and constraints.
b) Solve the problem using Excel Solver.
