1 動態(tài)規(guī)劃的基本方法
1.1 多階段決策過程及實(shí)例
- definition of multi stage decision
- example of multi stage decision problem
- shortest path problem
- machine's work load
high level, output, the condition of a machine.
the decision variable is the number of the machine with two different work load with the goal of achieving biggest output.
1.2 the concept of dynamic program and basic formulations
- the concept of dynamic program
take shortest path as example
the former decision affects later decision, but later decision does not affect former decisions.
adopt the concept of multi stage decisions, the shortest problem can be stated as 在各個階段選取一個
恰當(dāng)?shù)臎Q策, 使由這些決策組成的一個決策序列所決定的一條路線, 其總路程最短。(at each stage, we made a decision, and for all stages, we get a decision sequence, the sequence make the shortest path) - how to solve this problem?
we can use the algorithm/method of dynamic program.
1.2.1 . the basic concept of dynamic program
- stage
a time/spatial period - status (input variable)
statistic parameters at the beginning or end of a stage.
these parameters called status variables.
the decisions made only based on the adjust up flow parameters. 這個性質(zhì)稱為無后效性( 即馬爾科夫性)扔役。
如果狀態(tài)的某種規(guī)定方式可能導(dǎo)致不滿足無后效性, 應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的規(guī)定方法, 達(dá)到能使它滿足無后效性的要求濒持。 - decisions (output variable)
make decisions and come into next stage
the decisions called decision variables
they are the functions of status variables
the decision variables have a feasible set. - strategy
decision sequence
the kth sub-process: the following stages start from kth stage
the kth sub-decision sequence
the feasible decision sequence set and optimal decision sequence - stage moving function
an action/movement.
the function determine the K+1th status
the input of the function is the Kth status variables and Kth decision variables - objective function
the objective function is separable and 滿足遞推關(guān)系
Condition of objective function in dynamic program
1.2.2 the basic thoughts and functions
- take shortest path searching as example.
- dynamic programming start searching from end to head.
- 寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件( 簡言之為基本方程)。
- 要做到這一點(diǎn), 必須先將問題的過程分成幾個相互聯(lián)系的階段, 恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù), 從而把一個大問題化成一族同類型的子問題, 然后逐個求解。
- 即從邊界條件開始, 逐段遞推尋優(yōu),** 在每一個子問題的求解中, 均利用了它前面的子問題的最優(yōu)化結(jié)果**, 依次進(jìn)行, 最后一個子問題所得的最優(yōu)解, 就是整個問題的最優(yōu)解。
- 每段決策的選取是從全局來考慮的, 與該段的最優(yōu)選擇答案一般是不同
1.2.3 動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理
how to use dynamic program to solve shortest path problem?
the dynamic approach solves general problems, like shortest path, TSP, and so on. In this sense, it is an algorithm.
the problems do not have to be time-dependent.
