Operations Research Fall 2012

Introduction to Operations Research

Chapter 8: Assignment Problems and

Chapter 9: Network Optimization

Zhou, Jian

School of Management, Shanghai University

zhou_jian@shu.edu.cn

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 1 / 56

Operations Research Fall 2012

Contents

Review of Transportation Problem

The Assignment Problem

Network Optimization Problem

Review of Linear Programming Problems

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 2 / 56

Operations Research Fall 2012

Review: Transportation Problem of The P & T Co.

One of the main products of the P & T COMPANY is canned peas.

The peas are prepared at three canneries (near Bellingham, Washington;

Eugene, Oregon; and Albert Lea, Minnesota).

Then the peas are shipped by truck to four distributing warehouses in the
western United States (Sacramento, California; Salt Lake City, Utah; Rapid
City, South Dakota; and Albuquerque, New Mexico).

Because the shipping costs are a major expense, management is initiating a

study to reduce them as much as possible.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 3 / 56

Operations Research Fall 2012

Review: Transportation Problem of The P & T Co.

Location of canneries and warehouses for the P & T Co. problem

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 4 / 56

Operations Research Fall 2012

Review: Transportation Problem of The P & T Co.

In order to do that, an estimate has been made of the output from each
cannery, and each warehouse has been allocated a certain amount from the
total supply of peas (in units of truckloads), along with the shipping cost
per truckload for each cannery-warehouse combination.

Please determine which plan for assigning these shipments to the various
cannery-warehouse combinations would minimize the total shipping cost.
Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 5 / 56
Operations Research Fall 2012

Review: Transportation Problem of The P & T Co.

How to solve the problem?

Step 1: List four basic elements

X Decision variables:
xij (i = 1, 2, 3; j = 1, 2, 3, 4) the number of truckloads to be shipped
from cannery i to warehouse j
X Objective function:
Z total shipping cost
X Constraints:
Cannery constraints and warehouse constraints, nonnegative
constraints
X Parameters:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 6 / 56
Operations Research Fall 2012

Step 2: Give the mathematical model

min Z = 464x11 + 513x12 + 654x13 + 867x14 + 352x21 + 416x22




+690x23 + 791x24 + 995x31 + 682x32 + 388x33 + 685x34

subject to:






x11 + x12 + x13 + x14 = 75









x21 + x22 + x23 + x24 = 125
x31 + x32 + x33 + x34 = 100





x11 + x21 + x31 = 80

x12 + x22 + x32 = 65









x13 + x23 + x33 = 70

x14 + x24 + x34 = 85





xij 0, i = 1, 2, 3; j = 1, 2, 3, 4

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 7 / 56

Operations Research Fall 2012

Step 3: Solve the model by software (Matlab, LINDO/LINGO or Excel)

For Matlab and LINDO/LINGO, write the code in the paper.
For Excel, provide the screenshot.

C = [464, 513, 654, 867, 352, 416, 690, 791, 995, 682, 388, 685];
A = [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1;
1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0;
0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0;
0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0;
0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1];
B = [75, 125, 100, 80, 65, 70, 85];
L = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
[X , fval ] = linprog (C , [ ], [ ], A, B, L)
Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 8 / 56
Operations Research Fall 2012

Step 4: Smarter Matlab code for linear programming model:

C = [464 352 995; 513 416 682; 654 690 388; 867 791 685];
[m, n] = size(C );
ae = zeros(m + n, m n);
for k =1:1:n
for h = (k 1) m + 1 : 1 : m k
ae(k, h) = 1;
end
end

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 9 / 56

Operations Research Fall 2012

for i =n+1:n+m
for h = (i n) : m : m n
ae(i, h) = 1;
end
end
A = ae;
B = [75 125 100 80 65 70 85];
L = zeors(m, n);
[X , fval ] = linprog(C , [ ], [ ], A, B, L)

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 10 / 56

Operations Research Fall 2012

Step 5:Results by Matlab:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 11 / 56

Operations Research Fall 2012

Matlab Code for General Linear Programming

Linear programming model:

max Z = CX


subject to:





AX B


Aeq X = Beq






LB X UB

Matlab code: [X , fval ] = linprog (C , A, B, Aeq , Beq , LB, UB)

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 12 / 56

Operations Research Fall 2012

Solve the Problem by Excel

N3 = B3B14 + C 3C14 + D3D14 + E 3E14 + F 3F14 + G 3G14

+H3H14 + I 3I14 + J3J14 + K 3K14 + L3L14 + M3M14
orSUMPRODUCT

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 13 / 56
Operations Research Fall 2012

Solve the Problem by Lindo

Lindo Code:

min Z 464x11 + 513x12 + 654x13 + 867x14 + 352x21 + 416x22

+690x23 + 791x24 + 995x31 + 682x32 + 388x33 + 685x34
subjectto
x11 + x12 + x13 + x14 = 75
x21 + x22 + x23 + x24 = 125
x31 + x32 + x33 + x34 = 100
x11 + x21 + x31 = 80
x12 + x22 + x32 = 65
x13 + x23 + x33 = 70
x14 + x24 + x34 = 85
Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 14 / 56
Operations Research Fall 2012

Solve the problem by Lindo

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 15 / 56

Operations Research Fall 2012

Assignment Problem

The JOB SHOP COMPANY has purchased four new machines of different
types.

There are four available locations in the shop where a machine could be
installed.

Some of these locations are more desirable than others for particular
machines because of their proximity to work centers that will have a heavy
work flow to and from these machines.

Therefore, the objective is to assign the new machines to the available

locations to minimize the total cost of materials handling.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 16 / 56

Operations Research Fall 2012

Assignment Problem

The estimated cost in dollars per hour of materials handling involving each
of the machines is given in the table for the respective locations.

Step 1: How to formulate the problem?

X Decision variables:
X Objective function:
X Constraints:
X Parameters:
Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 17 / 56
Operations Research Fall 2012

Assignment Problem

Step 1: List four basic elements

X Decision variables: (binary variables)


1 if assignee i performs task j,
xij =
0 if not,

for i = 1, 2, ..., n and j = 1, 2, ..., n.

X Objective function:
Z = the total cost
X Constraints:
Assignee constraints and task constraints, nonnegative constraints
X Parameters:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 18 / 56

Operations Research Fall 2012

Step 2: Give the mathematical model

min Z = 58x11 + 69x12 + 180x13 + 260x14 + 75x21 + 50x22 + 150x23




+230x24 + 65x31 + 70x32 + 170x33 + 250x34 + 82x41 + 55x42 + 200x43 + 2




subject to:


x11 + x12 + x13 + x14 = 1





x21 + x22 + x23 + x24 = 1





x31 + x32 + x33 + x34 = 1



x41 + x42 + x43 + x44 = 1

x11 + x21 + x31 + x41 = 1





x12 + x22 + x32 + x42 = 1





x13 + x23 + x33 + x43 = 1





x14 + x24 + x34 + x44 = 1





xij 0, i = 1, 2, 3, 4; j = 1, 2, 3, 4

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 19 / 56

Operations Research Fall 2012

Step 3: Solve the model by software (Matlab, LINDO/LINGO or Excel)

Code by Matlab:

C = [58, 69, 180, 260, 75, 50, 150, 230, 65, 70, 170, 250, 82, 55, 200, 280];
A = [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1;
1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0;
0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0;
0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0;
0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1];
B = [1, 1, 1, 1, 1, 1, 1, 1];
L = zeros(1, 16);
[X , fval ] = bintprog (C , [ ], [ ], A, B, L)
Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 20 / 56
Operations Research Fall 2012

Step 4: Smarter Matlab code for assignment problem:

C = [58, 75, 65, 82; 69, 50, 70, 55; 180, 150, 170, 200; 260, 230, 250, 280];
[m, n] = size(C );
ae = zeros(m + n, m n);
for k =1:1:n
for h = (k 1) m + 1 : 1 : m k
ae(k, h) = 1;
end
end

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 21 / 56

Operations Research Fall 2012

Step 5: Results by Matlab:

for i =m+1:m+n
for h = (i n) : m : m n
ae(i, h) = 1;
end
end
A = ae;
B = [1, 1, 1, 1, 1, 1, 1, 1];
L = zeors(n, n);
[X , fval ] = bintprog (C , [ ], [ ], A, B, L)

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 22 / 56

Operations Research Fall 2012

Solve the Problem by EXCEL

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 23 / 56

Operations Research Fall 2012

Solve the Problem by Lindo

Lindo Code:

min Z 58x11 + 69x12 + 180x13 + 260x14 + 75x21 + 50x22

+150x23 + 230x24 + 65x31 + 70x32 + 170x33 + 250x34
+82x41 + 55x42 + 200x43 + 280x44
subject to
x11 + x12 + x13 + x14 = 1
x21 + x22 + x23 + x24 = 1
x31 + x32 + x33 + x34 = 1
x41 + x42 + x43 + x44 = 1
x11 + x21 + x31 + x41 = 1
x12 + x22 + x32 + x42 = 1
x13 + x23 + x33 + x43 = 1
x14 + x24 + x34 + x44 = 1
Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 24 / 56
Operations Research Fall 2012

Solve the problem by Lindo

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 25 / 56

Operations Research Fall 2012

Solve the Problem by Lindo

Results by Lindo:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 26 / 56

Operations Research Fall 2012

Network Optimization Problem

SEERVADA PARK has recently been set aside for a limited amount of
sightseeing and backpack hiking.

Cars are not allowed into the park, but there is a narrow, winding road
system for trams and for jeeps driven by the park rangers.

This road system is shown in Fig. 9.1, where location O is the entrance
into the park; other letters designate the locations of ranger stations .

The numbers give the distances of these winding roads in miles. The park
contains a scenic wonder at station T.

A small number of trams are used to transport sightseers from the park
entrance to station T and back.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 27 / 56

Operations Research Fall 2012

The Shortest-path Problem

Determine which route from the park entrance to station T has the
smallest total distance for the operation of the trams.
The road system for Seervada Park.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 28 / 56

Operations Research Fall 2012

The shortest-path problem

How to solve the problem?

Step 1: List four basic elements

X Decision variables:
xij (i = 1, 2, 3; j = 1, 2, 3, 4) The path from the origin to the
destination
X Objective function:
Z The total distance of the path
X Constraints:
Connected network constraints and nonnegative constraints
X Parameters:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 29 / 56
Operations Research Fall 2012

Algorithm for the Shortest-Path Problem

Objective of nth iteration: Find the nth nearest node to the origin.
Input for nth iteration: n 1 nearest nodes to the origin, including
their shortest path and distance from the origin. (Solved nodes;
unsolved nodes.)
Candidates for nth nearest node: Each solved node that is directly
connected by a link to one or more unsolved nodes provides one
candidate - the unsolved node with the shortest connecting link.
Calculation of nth nearest node: For each such solved node and its
candidate, add the distance between them and the distance of the
shortest path from the origin to this solved node. The candidate with
the smallest such total distance is the nth nearest node , and its
shortest path is the one generating this distance.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 30 / 56

Operations Research Fall 2012

Algorithm for the Seervada Park ShortestPath Problem

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 31 / 56

Operations Research Fall 2012

The Minimum Spanning

Telephone lines must be installed under the roads to establish telephone

communication among all the stations.

Because the installation is both expensive and disruptive to the natural

environment, lines will be installed under just enough roads to provide some
connection between every pair of stations.

The question is where the lines should be laid to accomplish this with a
minimum total number of miles of line installed.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 32 / 56

Operations Research Fall 2012

The Minimum Spanning Problem

How to solve the problem?

Step 1: List four basic elements

X Decision variables:
A network providing a path between each pair of nodes
X Objective function:
Z The total length of the links
X Constraints:
Links must provide a path between each pair of nodes and
nonnegative constraints
X Parameters:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 33 / 56
Operations Research Fall 2012

Algorithm for the Minimum Spanning Tree Problem

1 Select any node arbitrarily, and then connect it to the nearest distinct
node.
2 Identify the unconnected node that is closest to a connected node,
and then connect these two nodes . Repeat this step until all nodes
have been connected.
3 Tie breaking: Ties for the nearest distinct node (step 1) or the closest
unconnected node (step 2) may be broken arbitrarily, and the
algorithm must still yield an optimal solution.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 34 / 56

Operations Research Fall 2012

Applying This Algorithm to the Seervada Park Minimum

Spanning Tree Problem

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 35 / 56

Operations Research Fall 2012

Applying This Algorithm to the Seervada Park Minimum

Spanning Tree Problem

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 36 / 56

Operations Research Fall 2012

The Maximum Flow Problem

During the peak season, a strict ration has been placed on the number of
tram trips that can be made on each of the roads per day.

Various routes might be followed regardless of distance to increase the

number of tram trips that can be made each day.

The question pertains to how to route the various trips to maximize the
number of trips that can be made per day without violating the limits on
any individual road.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 37 / 56

Operations Research Fall 2012

The Maximum Flow Problem

How to solve the problem?

Step 1: List four basic elements

X Decision variables:
Combinations of routes
X Objective function:
Z The total number of trips
X Constraints:
Rout constraints, outgoing trip constraints and nonnegative constraints
X Parameters:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 38 / 56

Operations Research Fall 2012

Review 1 - Linear Programming

Background: The WYNDOR GLASS CO. produces high-quality glass

products, including windows and glass doors.
It has three plants. Aluminum frames and hardware are made in Plant 1,
wood frames are made in Plant 2, and Plant 3 produces the glass and
assembles the products.
Product 1: An 8-foot glass door with aluminum framing
Product 2: A 4 6 foot double-hung wood-framed window
Objectives: Determine what the production rates should be for the two
products in order to maximize their total profit, subject to the restrictions
imposed by the limited production capacities available in the three plants.
Product 1 requires some of the production capacity in Plants 1 and 3, but
none in Plant 2. Product 2 needs only Plants 2 and 3.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 39 / 56

Operations Research Fall 2012

Review 1 : Linear Programming

The WYNDOR GLASS CO.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 40 / 56

Operations Research Fall 2012

Review 1: Linear Programming Model

How to solve the problem?

Step 1: List four basic elements

X Decision variables:
xi (i = 1, 2) the number of batches of product i produced per week
X Objective function:
Z total profit per week from producing these two products
X Constraints:
Production capacity constraints, integer and nonnegative constraints
X Parameters:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 41 / 56

Operations Research Fall 2012

Review 1: A Linear Programming Problem

Step 2: Give the mathematical model

max Z = 3x1 + 5x2
subject to:





x1 4

2x2 12

3x1 + 2x2 18




x1 0, x2 0 integers.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 42 / 56

Operations Research Fall 2012

Step 3: Solve the model by software

C = [3 5];
A = [1 0; 0 2; 3 2; ];
B = [4 12 18];
LB = [0, 0];
Aeq = [ ];
Beq = [ ];
[x, fval ] = linprog (C , A, B, Aeq, Beq, LB)

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 43 / 56

Operations Research Fall 2012

Step 4:Results by Matlab:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 44 / 56

Operations Research Fall 2012

Solve the Problem by Excel

D3 = SUMPRODUCT (B3 : C 3 B9 : C 9)
D4 = SUMPRODUCT (B4 : C 4 B9 : C 9)

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 45 / 56
Operations Research Fall 2012

Solve the Problem by Lindo

Lindo Code:

max 3x1 + 5x2

subject to
x1 <= 4
2x2 <= 12
3x1 + 2x2 <= 18

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 46 / 56

Operations Research Fall 2012

Solve the Problem by Lindo

Results by Lindo:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 47 / 56

Operations Research Fall 2012

Review 2: Controlling Air Pollution

Background: The three main types of pollutants in this airshed are

particulate matter (sulfur oxides, and hydrocarbons).
Objectives:
The new standards require that the company reduce its annual emission of
these pollutants by the amounts 60, 150 and 125 respectively.
The steelworks has two primary sources of pollution, namely, the blast
furnaces for making pig iron and the open-hearth furnaces for changing iron
into steel.
Table 3.13 shows how much emission (in millions of pounds per year) can
be eliminated from each type of furnace by fully using any abatement
method to its technological limit.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 48 / 56

Operations Research Fall 2012

Review 2: Controlling Air Pollution

The NORI and LEETS CO.

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 49 / 56

Operations Research Fall 2012

Review 2: Controlling Air Pollution

How to solve the problem?

Step 1: List four basic elements

X Decision variables:
Fraction of the maximum feasible use of an abatement method (so xj
cannot exceed 1), xj (j = 1, 2, , 6)
X Objective function:
Z Minimum total annual cost
X Constraints:
Reduction requirements, fraction constraints and nonnegative
constraints
X Parameters:

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 50 / 56
Operations Research Fall 2012

Review 2: Controlling Air Pollution

Step 2: Give the mathematical model

minZ = 8x1 + 10x2 + 7x3 + 6x4 + 11x5 + 9x6

subject to:







12x1 + 9x2 + 25x3 + 20x4 + 17x5 + 13x6 > 60




35x1 + 42x2 + 18x3 + 31x4 + 56x5 + 49x6 > 150





37x1 + 53x2 + 28x3 + 24x4 + 29x5 + 20x6 > 125


xj 6 1, forj = 1, 2, , 6 xj > 0, forj = 1, 2, , 6

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 51 / 56

Operations Research Fall 2012
Step 4:Results by Matlab:
Step 3: Solve the model by software

c = [8, 10, 7, 6, 11, 9];

a = [12, 9, 25, 20, 17, 13;
35, 42, 18, 31, 56, 49;
37, 53, 28, 24, 29, 20];
b = [60, 150, 125];
lb = [0, 0, 0, 0, 0, 0];
ub = [1, 1, 1, 1, 1, 1];
Aeq = [ ];
Beq = [ ];
[x, fval ] = linprog (c, a, b, Aeq, Beq, lb, ub)

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 52 / 56

Operations Research Fall 2012

Solve the Problem by Excel

H3 = SUMPRODUCT (B3 : G 3 B11 : G 11)

H4 = SUMPRODUCT (B4 : G 4 B11 : G 11)

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 53 / 56

Operations Research Fall 2012

Solve the Problem by Lindo

Lindo Code:

min 8x1 + 10x2 + 7x3 + 6x4 + 11x5 + 9x6

subject to

12x1 + 9x2 + 25x3 + 20x4 + 17x5 + 13x6 <= 60

35x1 + 42x2 + 18x3 + 31x4 + 56x5 + 49x6 <= 150
37x1 + 53x2 + 28x3 + 24x4 + 29x5 + 20x6 <= 125

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 54 / 56

Operations Research Fall 2012

Results by Lindo

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 55 / 56

Operations Research Fall 2012

Zhou, Jian: zhou_jian@shu.edu.cn School of Management, Shanghai University 56 / 56