Fuzzy Multiple Objective Decision Making

65

6

Multi-Stage Programming

Multi-stage programming can be considered a special network problem that nds the

shortest path joining two points in a given network. However, unlike other shortest

path problems that focus on nding the shortest path from the source node to any

other node in a network, multi-stage programming seeks the shortest path from the

source to each sequential stage. In this chapter, we will introduce dynamic program-

ming, which is widely used for multi-stage network problems and the related applica-

tion of this programming technique.

6.1 DYNAMIC PROGRAMMING

The concept of dynamic programming comes from the principle of optimality

(Bellman, 1952, 1953) as a solution for sequential optimization problems. That is, an

optimal solution has the property that whatever the initial state and the initial deci-

sions are, the remaining decisions must constitute an optimal solution with regard

to the state resulting from the rst decision. The network problems of multi-stage

programming are shown in Figure6.1.

To model the illustrated problem, we rst dene the notations. Let the distance

between node i and node j be

c

ij

and

fj()

t

be the node j in stage t. If we want to nd

the shortest distance from node 0 to node 9, we can begin by nding

f (6)

4

,

f (6)

4

,

f (6)

4

, and

f (6)

4

, i.e., nding min{

c

69

,

c

79

,

c

89

}.

Next, we can nd

f (4)

3

and

f (5)

3

. Using

f (4)

3

for an example, we apply the

following equation:

=+ ∀=fcfj j(4)min{()}

,6

,7,8.

j

j34,4

(6.1)

Then, we can use the procedure until

f (0)

0

results to obtain the shortest distance

from node 0 to node 9. This method is called dynamic programming with backward

recursion. However, if we start from node 0 to nd the shortest distance, the process

is called forward recursion. We can generalize a k-stage problem as the following

dynamic programming equation:

=+ ∀=fj cf

jt

k() min{()}

,1

,..., ,

t

j

ij t

(6.2)

where c

ij

denotes the distance between node i and node j and

fj()

t

is the node j in

stage t.

66 Fuzzy Multiple Objective Decision Making

It is easy to understand that if a multi-stage problem is too complicated, dynamic

programming is far superior for achieving explicit enumeration. We can summarize

the characteristics of a multi-stage problem as follows (Winston, 1994):

1. A multi-stage problem can be divided into stages with a decision required

at each stage.

2. Each stage has a number of associated stages.

3. The decision chosen at any stage describes how the current stage is trans-

formed into the next stage.

4. Given the current stage, the optimal decision for each of the remaining

stages must not depend on previously reached stages or previously chosen

decisions (principle of optimality).

Example 6.1

We can reconsider the above five-stage programming problem as the following

shortest route problem. Assume you live in Taipei and plan to see a friend in

Shanghai and want to take this opportunity to travel in China. If your funds are

limited, you must determine the most economical way to enjoy each day of your

trip. Figure6.2 displays the possible cities to visit and the corresponding costs for

each day.

We will employ backward recursion to determine the optimal path of the trip.

We can use dynamic programming to deal with this five-stage programming prob-

lem. First, we calculate the trip costs from Day 3 to Day 4 separately, as shown

in Table6.1. Next, we consider the trip costs from Day 2 to Day 4 as shown in

Table6.2. The solution of Table6.2 can be explained as follows. The trip cost

from Jinjiang to Ningbo is equal to 7. Hence, if we decide to arrive at Jinjiang in

Day 2 and at Ningbo in Day 3, we should cost 12 units to Shanghai after Day 1.

0

1

2

8

3

7

6

5

4

9

Stage1 Stage2 Stage3 Stage4 Stage5

01

c

14

c

03

c

01

c

24

c

25

c

34

c

35

c

15

c

46

c

47

c

48

c

56

c

57

c

58

c

69

c

79

c

89

c

02

c

FIGURE 6.1 Example of a multi-stage programming problem.