8第二章8-10,144-160改

§2.8 层次分析法模型

层次分析法（Anolytic Hierarchy Process---AHP）70年代, 由美国运筹学家T. L. Saaty首先提出。

1、问题的提出

例如考虑购物模型：某一顾客选购电冰箱时，对市场出售的四种电冰箱考虑了六项准则（信誉T1，型式T2，价格T3，容量T4，致冷级别T5，耗电量T6），市场上有4种冰箱可供选择(A,B,C,D)。图2-74表示了目标层（选购电冰箱），准则层及方案层之间的关系。

目标层 选购电冰箱

准则层 信誉T1 型式T2 价格T3 容量T4 致冷级别T5 耗电量T6

方案层 A B C D 图2-74

我们希望得到一个公式 y=T1W1+┅+T6W6 （其中W1 ，┅，W6称为准则层的权系数），使得我们可以通过计算方案层不同的选择的y值，来最终确定我们该选择何种冰箱。如已知某种冰箱的Ti值（这容易知道），即可得到一个y值，分别对A,B,C,D计算y值，即可确定购买何种冰箱。

问题是：Wi如何选定？层次分析法将解决这个问题。 2、层次分析法简介

层次分析法是对复杂问题作出决策的一种简单易行的方法。它适用于那些错综复杂且难于定量分析的问题（仅有定性关系），从而，决策者难于作出最佳决策。诸如：上例购物；研究单位合理选择科研课题；面队竞争对手如何作出最佳经营策略；以及对社会团体，研究机构，期刊杂志进行排名等问题。层次分析方法提供了一个有力且有效的工具。这个由Saaty首创的方法，目前已广泛应用于：决策分析，技术评价，政策分析，规划，预测估计，关联分析，资源分配，评价和选拔人才，冲突解决及其他方面。

3、基本思想：通过准则层各因素对目标层的重要程度比较的量化，经过适当的数学推导，得出前述的各权系数。

4、步骤：

１４４

1）将问题所包含的因素适当分层，每一层不要超过9个因素(心理学家认为：人们在比较若干对象时，能够区分差异的心理极限是7±2 ,也即在对多于9个对象进行排序时，将不能严格区别)，否则可将该层次再划分为若干子层；

2）确定正互反矩阵（逆称矩阵，满足aij?0,aij?1） aji对每一层，考虑各因素相对于目标Z的重要性为?1,?2,?,?n(相当于将一石头Z分成n块y1,y2,?,yn, 各石块重量?1,?2,?,?n), 显然?i表示了yi在Z中的“份量”（或权系数）。

现设aij??i, 即得yi与yj相对于Z的 “比重” 。显然 ?j??1?????2????1?1A=?aij?=????1 且记????1??n? ??n?????????n???则

即?为A的特征向量（相对于特征值n）。

由此思想延伸到一般问题，我们考虑各因素x1,┉,xn相对于目标y的重要性。用下表数值表示：

???1????1?1A??????1??n????n?????1???1??????????n????n? ???????n??n?xi/xj aij 相等 1 较强 3 强 5 很强 7 绝对强 9

若介于上述二者之间，则取2，4，6，8，由此得出，

１４５

A=aij??n?n=??xi??= xj??n?n?a1n???a2n? ?????ann???a11??a21=????a?n1称为正互反矩阵（逆称矩阵）。

3）确定权系数ωi

a12a22?an2一致正互反矩阵：对任意i,j,k，（如前例aij·aaijajk?aikjk=

wiwj， 即?aik）

wjwk对各项目的比较是一致的。

可以证明：

（1） 一致正互反矩陣的最大特征根λmax=n , 其余特征根为0。（验略）

?（2） A的最大特征根n对应的特征向量 ?=（ω1,?,ω2）′的标准化向量，即为准则层对目标层的权系数。

由此即可得到单层各因素对目标层重要性的排序权值。

若有多层次则分别求出各层权系数，分别相乘即可。 如：某学校对学生的评价可用下图表示：

目标层 对学生评价 0.3 0.55 0.15 第二层 德 智 体 0.5 0.5 0.2 0.25 0.15 0.15 0.1 第三层 思想 道德 语文 数学 ? 计算机 眼 ? 肺

这里把问题分成三个层次。也可以直接讨论第三层对目标层的权系数，但可能超过9项，从而无法求出准确的正互反矩阵。

求出各层对象对目标的权系数，将相应系数相乘即可得第三层对目标层的权系数。如语文对目标层权系数为0.2×0.55=0.11。

4）一致性判别 一般情况下，矩阵A未必为一致性矩阵，但为了得到较准确的结论，通常要求矩阵具有较高的一致性。 通常用CI=

?max?nn?1 来恒量一致性，若CI越小，

则一致性越好。若A为一致阵，CI=0 由于CI与n有关，可能随n增大，CI增大。于

１４６

是，Saaty又提出了平均随机一致性指标RI的概念, 用 CR=CI/RI 来衡量矩阵的一致性, 其中RI用如下方法产生：对固定n, 随机产生正互反矩阵，其中aij从

1111,2,?,9,,,?,中随机抽出。求出充分大样本（如500个）A的最大特征根的平均

239值λ

'max,

定义RI=

?'max?nn?1。一般情况下，通常用Saaty给出的值为标准：

n 1 2 3 4 5 6 7 8 9 RI 0 0 0.58 0.9 1.12 1.24 1.32 1.41 1.45

当CR<0.1时, 认为矩阵有较满意的一致性。（否则须对矩阵A的元素调整）

?5）?的计算 可以证明：

?

??Ake?定理： 设A为矩阵（aij>0），x=e=(1,1,?,1)?， 则lim?k?=? 。

e?Ae

???0?求出?的单位向量 ??=?（归一化），即为A的属于最大特征根的单位向量。

e???n(A?)i且 ?max＝??。

i?1n?i?e11 （2） 求x0????(?)?；

e?enn具体步骤：（1） 取e=(1,1,?,1)；

???A2xn?2Ax0Ax （3）求x1????? ，xn??2???eAeeAx0e?Axn?2由定理知，xn收敛于A的最大特征根的特征向量?。

?Axn?2A??e?Axn?2Axn?1???? ?Axn?2?eAxn?1e?A?e?Axn?2?在具体问题中，取小数点后三位有效数字即可。于是，在一般情况下，xk?xk?1对某k≤7成立。

6）对多个专家情况，可用aij?

n?ai?1nkij 作为A的元素。

１４７

如某问题的正互反矩阵为

A????15?11?5?12?3??3?1?2??1?计算：

??CR?CIRI? 0.0<0.1， 其中 CI??max?nn?1,?max=3.00369为A的最大特征值，给出。

从而可以认为矩阵A的一致性较好。 用Mathematica软件，计算出权系数?

? = 0.648329,0.12202,0.229 Mathematica程序：

?a={{1,5,3},{1/5,1,1/2},{1/3,2,1}}; e={{1,0,0},{0,1,0},{0,0,1}}; x e-a; n=3;

NSolve[Det[%%]?0,x] Abs[%[[3,1,2]]-n]/.58

\?{0,0,0},{x,y,z}]\ e1={1,1,1}; x=e1/n;

x=N[a.x/e1.a.x,3] x=N[a.x/e1.a.x,3] x=N[a.x/e1.a.x,3]

１４８

RI?0.58由saaty

§2.9 统筹建模

作为一门科学，统筹学是从毛主席“统筹兼顾，合理安排”的思想发展起来的。50年代，华罗庚大力提倡“二法”：优选法，统筹法。使得数学这一高深莫测的理论为广大人民群众所应用，极大得推动了我国国民经济的发展。

优选法 以0.618(黄金分割数)为基数，对实验合理安排。方法简单，容易掌握。如：管线检查，化学试剂量得调配等。

例39 某段地下管线AB之间出现了断点。较简单的方法是将管线挖开，检查出断点的位置进行修复，这要耗去大量的人力物力。

为了节省劳力，我们可以在AB的0.618处挖开，检查断点在AC还是在BC，从而，可以将搜索范围缩小，然后在AC或BC上重复这一过程即

AB0.618可达到缩短工期，加快进程的目的。可以证明：用

这种办法能够最快的找到断点。 C这种方法也可以用到上述提到的化学试剂量得调配等。

图2-74 这种方法称为：0.618法。实践中也可以用“二

分法”，菲波那奇数列作为选取中间点的依据。但收敛速度略有差别。

统筹法则与50年代国际上刚刚出现的网络技术相呼应，是对大系统（包括不太大系统）的各个部门合理安排，统筹兼顾，使之尽可能缩短工期。华罗庚（70年代）认为“贯彻毛主席统筹兼顾，合理安排的思想，统筹方法仅提供了一个辅助工具”“初步看来，潜力不小”“初步设想可以概括为十二个字：大统筹，理数据，建系统，策发展。使之形成了一门由中国人创建的科学――统筹学。

其中“理数据，建系统”则包含了一般的系统论内容，以网络为基本工具，是我们要掌握的内容。而“大统筹”，“策发展”则含有更深层次的意义，华罗庚从时间和空间的统一，对宇宙万物进行筹划出发，体现大中之繁，更应做统筹安排，充分考虑到系统涉及的此时此地人群的业务系统结构状况等综合因素。“对系统进行处理”（理数据，建系统）建立一个现实系统的同时，要想到把它转化到一个更新，更高，更切实际的系统阶段中去，使统一体不仅是成功，优化的，而且是良性循环（策发展）。

在现实问题中，从生活琐事，如做饭：好的厨师在做饭过程中能统筹安排则可以忙而不乱，作出美味佳肴；盖房：合理安排各个工序则可以提高速度，不误工期。大的方面，我国“二弹一星”的科技成就若没有统筹学的参与是不可想象的。美国阿波罗载人登月工程（60年代）历时11年，二万多家公司、120所大学参与，使用700多万个零件，平均每年动用42万人，最高时达60万人，动用当时的计算机630台，耗资300亿

１４９

美元。可以想象，若采取传统的管理办法，那是很难如期完成的，即使如期完成其耗资经费也很难控制在预算之内。但工程总指挥韦伯说：“阿波罗飞船技术其中没有一项是新的突破，都是现成的技术，关键是能否把他们精确无误的组织好，实施系统管理”。可以说，阿波罗载人登月计划的成功，是系统工程这种现代管理理论和技术走向成熟的标志，也使系统工程由此名扬四海。

现以建房为例说明统筹法的思想。现要建一座房。已知各工序需要的时间及其前面的活动如表，请合理安排使

编号 活动 前面的活动 延 续时（天）

之能尽可能早的完工。

1 地基 无 4．0 将这些活动用图2-75

2 挖沟 无 1．7 表示。下面以解决这一问题

3 2 管线 2．0 为例，介绍统筹学的基本内

4 砌砖 1，2，3 15．0 容。

5 4 喷涂 4．8 1、 关键轨道

4 木工 8．4 上述问题称为一个规6 6 屋顶 10．0 划审计技术（Program 7 Evalnative and Review Technique）（或计划评审技术）代号：PERT。

PERT图，指一有向图

1G(V,E)满足：

1) V(G)中存在起始顶s

524（start）与终止顶t(terminal)；s02) G中无有向回路（如工程中

t6378此种情况相当于拆了砌，砌了又拆）；3）?v?V(G)－{s,t},

图2-75

v在某条从s到t的有向轨上。

约定：

1） PERT图的每一边代表一过程

2）α(v)表示入顶v的过程，β(v)表示出顶v的过程，β(s)可以马上开始 3）v∈V(G), v≠s, 当α(v)全部结束时，β(v)才能开始 关键轨道问题：设PERT图每边e之权l(e)表示该过程所需时间，问由β(s)到α(t)最短需多长时间？

如图2-57可采用如下算法： PERT最短时间算法

1) 标志s为0，其余顶不标志

2) 找一个v∈V(G), v未标志,且α(v)的一切尾已标志，标记v为max{λ

e?uv １５０

(u)+l(e)}

3) 若v=t 则止，否则转2）

从上述路径返回即得s→①→④→⑥→⑦→t为关键路线。

问题：1）上述工程工期要缩短，必须缩短关键路径；2）若缩的过多，则关键路线可能变化，如：1—4变为3.5，则可以看出关键路线改为1－4?1－2－3－4。

由此可见上述PERT关键路径问题存在缺点，下面进一步探讨解决办法。 2、工序的最早开工，最晚开工时间与总工期

将事项编号（如上例），s→0，t→8 设k事项最早发生日期 tes(k), 最晚发生日期

tls(k), 最早完工日期 tef(k), 最晚完工日期tlf(k)(如图2-76) ，记

Gk为指向k的结点集，tj表示j的延续时间，Qk为由k出发的弧直接指向的结点集，则显然 tes(k)?max{tef(j)}，

j?Gktes (k)tef(k)tls (k)tlf(k)图2-76

tef(j)?tes(j)?tj tlf(k)?min{tls(j)} ，tls(j)?tlf(j)?tj，

j?Qk10 4 0 4 4444 19 4 19 66151519 27.4 19 27.4 78.427.4 37.4 27.4 37.4 s0 1.7 0.3 2 1.71.721.7 3.7 2 4 19 23.8 32.6 37.4 104.837.4 37.4 37.4 37.4 223图2-77

58 tlf(8)?tef(8)?TE(总工期）如图2-77,经简单计算,可得建房问题的总工期TE?37.4.

几点说明：1）tes(4)=max 意味着1，2，3全部结束，4才能开始 ， tlf（2） =min 意味着比0.3再晚将影响3或4的进度；

１５１

2）Tef(8) =TE即为关键轨道之长；

3）在关键轨道上(s→①→④→⑥→⑦→⑧)最早，最晚开工日期相同，

这不是偶然的，正是被称为关键轨道的原因。因此，也可以用这种方式直接求出关键轨道；

4）浮动时间 tls(j)?tes(j)?tf(j)；

5）②和③的浮动时间均为0.3,但有区别：③推迟了0.3对其它活动无

任何影响，②推迟0.3对③有影响。

6）当各活动延续时间变化时，关键轨道可能将改变，从而在抢进度时

要注意。

7）在填图2-77时，最早开始、结束时间从前到后标记；最晚开始、结

束时间从后到前标记,且要先标注最晚开始、结束时间。

3、 网络流的最大流与最小截问题

把商品从产地运往市场，交通网上每个路段的运输能力有限（如火车），当给定运输能力条件下，怎样使运输最快（即运输总量最大）？

设G为有向图（加权），s源，t汇，边e的权c(e)为e的容量，求满足下列条件的F的最大值。

称f:：E(G)→R为一个流函数,如果满足C1: ?e∈E(G),0≤f(e)≤c(e)；C2: ?v∈V(G)－{s,t},0=

e?(v)deff(e)－?f(e)。 ???e?(v)显然,流函数必存在.如对任意e,f(e)=0。 又称F=

e?(t)f(e) 为f的流量。 ??若有流函数f使F=max,则称f为PERT的一个最大流。

约定：1）若e=uv,u已标志，v无标志，C(e)>f(e)(未达容量)，则通过边e可向前标志顶v,记?(e)=C(e)－f(e)且标志e； 2)若e=uv，v已标志，u未标志，且f(e)>0则称通过边e可向后标志顶u,记?(e)=f(e),且得到标志边（注：向后，向前标志?(e)意义不同）。

下边介绍求最大流的双F算法 Ford—Fulkerson算法 1）对?e?E(G),f(e)=0； 2) 标志顶s,其他顶未标志； 3） 选可向前标志或可向后标志的顶v(对s仅可能有向前标志顶，对t仅有向后标志顶)。若无，则现流函数即为最大流；若有此种顶，则得新的标志顶v和标志边e；若v=t则转4），否则转3）；

１５２

4) 设已得标志轨为（无向）se1v1e2v2┄elt,从t沿此轨道逆行，令?=min?(ei)，

1?i?t则当ei为前进边，f(ei)+?→f(ei)；ei为后退边，则f(ei)－?→f(ei) 5) 转2）

注：双F算法为多项是算法。

例40 求如图2-78，图中边上方左数字为容量，右边为流量（初始流量为0） a 12，0 b 15，0 3，0 7，0 s t 4，0 5，0 10，0 c 10，0 d 图2-78

按F-F方法：第一步，可得标志轨道s→a→b→t ，?=min{15,12,7} 得流量图。 a 12，7 b 15，7 3，0 7，7 s t 4，0 5，0 10，0 c 10，0 d 图2-79

第二步，可得 s→a→b→c→d→t ?=min{8,5,3,10,10}=3 得流量图 a 12，10 b 15，10 3，3 7，7 s t 4，0 5，0 10，7 c 10，3 d 图2-80

第三步，得 s→c→d→t ，?=min{4,7,7}=4，即为最大流量图

a 12.10 b 15.10 3.3 7.7 s t 4.4 5.0 10.7 c 10.7 d 图2-81

１５３

F=

e?(t)f(e)－?f(e)=14 ???e?(t)截：S?V(G) (S,S) (S=V(G)－S)称为G的一个截集。如：S={s,a,c,d}则(S,S)={ab,dt} ( 头在S中，尾在S中的边)

截量： C(S)=

e?(S,S)?_?_?c(e) ( 即截集的容量) ，如对上述问题

C(S)=c(ab)+c(dt)=12+10=22.

最小截：在标志过程的最后一次不能标志到t, 从s到最后一个标志顶集记为S, 则S为最小截（未证）.

如：{s,a,b}=S, 则（S,S）={sc,bt,bc} C(S)=4+7+3=14=Fmax

定理： 最大流＝最小截

以上我们讨论了容量下界为零的情形,下面讨论容量下界非零情形。

设有网络记为N(G(V,E),b(e),c(e))，若容量下界非0，记为b(e)，则流函数f应满足 C1: b(e)≤ f(e)≤ c(e)；C2:

2,30,1???e?(v) f(e)－?f(e)=0，对任意 v?{s,t}。???e?(v)此时未必存在流函数. 如：a?b?c，因此，含有容量下界的最大流不能用2F法求得（2F法前提:有初始流函数）。

此时,我们可以通过引入辅助网络的办法,得到原网络的一个流函数.

构造辅助网络N

1） 增加二个点 s，t 得 V=V?{s,t} ；

2）对每个v?V(G)－{t} (汇无流出), 加新边e=vt , c(e)=(出边下界之和)；

3）对每一个v?V(G)－{s}(源不流进), 加新边e=sv,c(e)=(进边下界之和) ；

4）e?E(G)保留，c(e)=c(e)－b(e),b(e)=0；

１５４

____________e?(v)b(e),b(e)=0 ??_e?(v)b(e),b(e)=0 ??_5) 加边 e=st，e′=st，c(e)=c(e′)=?，b(e)=b(e′)=0。

定理: N(G,b(e),c(e))有流量函数的充分必要条件是：N的最大流，使流出s(始______点)的一切边皆满载，即

?f(e?)=?c(e)_ （对s）

。 例41 求下图的最大流

w 1,3 x 1，3 1，3 3，5 s t 0，10 2，4 2，6 y 2，8 z 图2-82 构造辅助网络N:

图2-83

N__求得的一个最大流，从而可得N的一个流函数：f=f+b(e)

w 5，7，5 x 1，3，3 2，4，2 1，3，1 3，5，4

s t 0，10，3 2，6，2 y 2，8，4 z 图2-84

再按前述方法可进一步调整得N的最大流。

１５５

§2．10 动态规划模型

1、动态规划的基本思想和最短路线问题

动态规划是解决多阶段决策过程的最优化问题的一种方法。

多阶段决策：决策问题按时间，空间可以分成很多阶段，每一阶段都需要作出决策使整个过程达到最优,称为多阶段决策。

例42（最短路问题）从A到D要铺设一条煤气管道，中间要经过二级中转站，第一级中转站分别为3C1B1,B2，第二级中转站分别为

2AB1C1,C2,C3，如图2-85，有连线的是

43123B211C234D可以铺设管道的路线，连线上的数C3字表示二地之间的距离，问如何铺

图2-85 设管道可以使总造价最小？

方法1. 穷举法 对本问题用穷

举法，共有6条路线，对本题也不难，但对阶段多时则不可行,穷举法的计算量非多项式算法。

分析：若B1, B2到D均求出了最短路，不妨设B1到D的最短路的距离小, 则A只要沿B1到D即为A到D的最短路。由此思路即得方法2)。为介绍方法2，先介绍几个名词：

1）某点到D的阶段数用整数n表示； 2）状态s表示当前所处位置；

3）决策变量xn(s)――集合：还有n个阶段到D,下一步可选取地点，x2(B2)?{C1,C2,C3}。

4) fn(s)表示状态s, 还有n个阶段到D, 采取最优策略时的最短管道长度。显然本问题即求f3(s)。

5）d(s,xn(s))表示由s到下一个地点xn(s)的管道长度。

方法2的计算依据是

最优化原理: 每阶段决策的一个策略(路径)是最优化策略?对该策略(路径)中的任

１５６

一点, 从该点到终点的最优策略(路径)必含在该策略(路径)内.

计算过程：从后向前依次计算fn(s)。

1） 计算f1(C1), f1(C2), f1(C3)：f1(C1)=1, f1(C2)=3, f1(C3)=4； 2) 计算f2(B1), f2(B2)：

a) 对B1：d(B1,C1)+f1(C1)=3+1=4, d(B1,C2)+f1(C2)=3+3=6 , d(B1,C3)+f1(C3)=1+4=5, f2(B1)=min{4,6,5}=5，

b) 对B2：d(B2,C1)+f1(C1)=2+1=3, d(B2,C2)+f1(C2)=3+3=6, d(B2,C3)+f1(C3)=1+4=5, f2(B2)=min{3,6,5}=3；

3) 计算f3(A)： d(A,B1)+f2(B1)=2+4=6， d(A1,B2)+f2(B2)=4+3=7， f3(A)=min{6,7}=6 。

上述计算依据了最优化原理.

如：本例中最优策略为 A→B1→C1→D, B1属于上述路径．从而B1到D1的最优策略必是B1→C1→D．否则,若从B1到D有另外更优策略B1→Ci0→D, 则A→B1→Ci0→D比策略A→B1→C1→D更优．

由此可见，该原理虽然简单, 但意义重大. 2、投资分配问题 投资分配问题：若考虑数量为a(万元)的资金计划分配给n个工厂, 用于扩大再生产， xi=分配给i工厂的资金数(万元)， gi(xi)表示i工厂得到xi(万元)后产生的利润值(此量为已知量)问如何分配可使总利润最大?

即求 max

?g(x)

iii?1nnst

?xi?1i?a, xi≥0

这是一个非线性规划问题， 无一般方法求解。

考虑化为动态规划问题： 为此， 将n个工厂排序为1，2，┅，n。 前k个工厂分配x(万元)，产生最大的总利润，记为fk(x) 显然，目标为求fn(a)。当k=1时显然f1(x)=g1(x). 设1

0?y?x（x－y）+gk(y)}= max {gk(y)+fk－1（x－y）}。

若取y=0，1，?，x， 递推可得fn(a)。

例43 国家拨款60（万元）的投资供4个工厂扩建用，投资给各工厂后产生的利润如下

１５７

表：

投资x 0 利润 g1(x) g2(x) g3(x) g4(x) 1） f1(x)=g1(x)

x f1(x) 最优策略 0 0 0 10 20 10 20 50 20 30 65 30 40 80 40 50 85 50 60 85 60 0 0 0 0 10 20 20 25 25 20 50 40 60 40 30 65 50 85 50 40 80 55 100 60 50 85 60 110 65 60 85 65 115 70 2）f2(x)=max {g2(y)+f1(x－y)}，其中 y=0，10，┅x。 目标：求f4(60)：f4(60)=max{g4(y)+f3(60－y)} 其中y=0，10，┅，60 ，于是须求出 f3(60)，f3(50)，?，f3(0)，进而要求出 f2(60)，f2(50)，?，f2(0)。

计算：

f2(60)=max{g2(0)+f1(60)， g2(10)+f1(50)， g2(20)+f1(40)， g2(30)+f1(30)，

g2(40)+f1(20)， g2(50)+f1(10)， g2(60)+f1(0)}

=max{0+85， 20+85， 40+80，50+65，55+20，60+20，65+0} =max{85，105，120，115，75，80，65}=120 最优策略 （40，20）

f2(50)=max{g2(0)+f1(50)，g2(10)+f`1(40)，g2(20)+f1(30)，g2(30)+f1(20)，g2(40)+f1(10)，

g2(50)+f1(0)}

=max{0+85，20+80，40+65，50+50，55+20，60+0} =max{85，100，105，100，75，60}=105 最优策略（30，20）

f2(40)=max{g2(0)+f1(40)， g2(10)+f1(30)，g2(20)+f1(20)，g2(30)+f1(10)， g2(40)+f1(0)}

=max{0+80，20+65， 40+50， 50+20， 55+0} =max{80， 85， 90， 70， 55}=90 最优策略（20，20）

f2(30)=max{g2(0)+f1(30)， g2(10)+f1(20)， g2(20)+f1(10)， g2(30)+f1(0)}

=max{0+65， 20+50， 40+20， 50} =max{65， 70， 60， 50}=70 最优策略（20，10）

f2(20)=max{g2(0)+f1(20)， g2(10)+f1(10)， g2(20)+f1(0)}

１５８

=max{0+50， 20+20， 40+0}=50 最优策略（20，0）

f2(10)=max{g2(0)+f1(10)， g2(0)+f1(0)}

=max{20， 20}=20

最优策略（0，10）或（10，0） f2(0)=max{g2(0)+f1(0)}=0

最优策略（0，0）结果如下表： x f2(x) 最优 0 0 10 20 20 50 30 70 40 90 (20,20) 50 105 (30,20) 60 120 (40,20) （0，0） （10,0） （20，0） (20,10) 3) f3=max{g3(y)+f2(x－y)}, 其中y=0，10，20，?,x .

计算：

f3(60)=max{g3(0)+f2(60)，g3(10)+f2(50)，g3(20)+f2(40)，g3(30)+f2(30)，g3(40)+f2(20)，

g3(50)+f2(10)，g3(60)+f2(0)}

=max{0+120，25+105，60+90，85+70，100+50，110+20，115} =max{120，130，150，155，150，130，115}=155 最优策略（20，10，30）

f3(50)=max{g3(0)+f2(50)，g3(10)+f2(40)，g3(20)+f2(30)，g3(30)+f2(20)，g3(40)+f2(10)，

g3(50)+f2(0)}

=max{0+105，25+90，60+70，85+50，100+20，110+0} =max{105，115，130，135，120，110}=135 最优策略（20，0，30）

f3(40)=max{g3(0)+f2(40)，g3(10)+f2(30)，g3(20)+f2(20)，g3(30)+f2(10)，g3(40)+f2(0)}

=max{0+90，25+70，60+50，85+20，100+0} =max{90，95，110，105，100}=110 最优策略（20，0，20）

f3(30)=max{g3(0)+f2(30)，g3(10)+f2(20)，g3(20)+f2(10)，g3(30)+f2(0)}

=max{0+70，25+50，60+20，85+0}=85 最优策略（0，0，30）

f3(20)=max{g3(0)+f2(20)，g3(10)+f2(10)，g3(20)+f2(0)}

=max{0+50，25+20，60+0}=60 最优策略（0，0，20）

f3(10)=max{g3(0)+f2(10)，g3(10)+f2(0)}

=max{0+20，25+0}=25 最优策略（0，0，10） f3(0)=0，最优策略（0，0，0）

１５９

x f3(x) 最优策略 0 0 (0,0,0) 10 25 (0,0,10) 20 60 (0,0,20) 30 85 (0,0,30) 40 110 (20,0,20) 50 135 (20,030) 60 155 (20,10,30) 4) f4(60)=max{g4(0)+f3(60)，g4(10)+f3(50)，g4(20)+f3(40)，g4(30)+f3(30)，g4(40)+f3(20)，

g4(50)+f3(10)，g4(60)+f3(0)}

=max{0+155，25+135，40+110，50+85，60+60，65+25，70+0} =max{155，160，150，135，120，130，170}=160 最优策略（20，0，30，10）

3、 背包问题

一徒步旅行者，有n种物品可供其选择装入背包中，已知每种物品的重量及使用价值（指该物品对旅行者本人带来的好处得数量指标）如下表：

? ? 1 2 j n 物品号 重量（公斤/件） 每件使用价值 a1 c1 a2 c2 ? ? aj cj ? ? an cn 问各件物品取多少件对旅行者使用价值最大？ 设第j种带xi件对旅行者使用价值最大，则问题转化为求下述线性规划问题

max

?cx

iii?1nst

?axii≤a, xi 为整数。

化为动态规划问题：设前k种物品只装y公斤时的最大使用价值为fk(y)，则问题转化为求fn(a)。

显然，f1(y)=[

y]c1 ，设k－1件的最大使用价值已知fk－1(x) ， 则将y公斤物品a1对前k件物品进行分配，使之使用价值最大，即求fk(y)。

设先装第k件物品 xk(件) （0≤akxk≤y），则余下重量y－akxk 即 fk(y)=max{ckxk+fk－1(y－ckxk)} ， xk为整数。

0?xk?yak例44. 求下面“背包”问题的解

设各种物品的重量及使用价值如右表，且取a=5,则问题即求下列线性规划问题最优解：

max{8x1+5x2+12x3}

１６０

物品 重量（ 每件使用价值 1 3 8 2 2 5 3 5 12 st. 3x1+2x2+5x3≤5 ，x1，x2，x3≥0，xi整数

按上述动态规划问题解法，我们的目标是求f3(5).

1） 求f1(x):

f01(0)=[

3]*8=0 , f1(1)=0, f1(2)=0 , f1(3) = f1(4)=f1(5)=8; 2) 求f2(x):

f2(0)=0, f2(1)=max{8·0+0}=0,

f2(2)=max{8·0+f2(2)，8*1+f1(0) }=5, f2(3)=max{0+8，8·1+f1(3－2)}=8, f2(4)=max{0+8，5·1+0，5·2+0}=10 ,

f2(5)=max{0+8，5·1+18，5·2+0}=13

xk?0,1,23) 求f3(5):

f3(5)=max{0+fx2(5)，12+f2(0)}=13 ,

k?0,1 最优方案：x1=1， x2=1， x3=0.

１６１

本文来源：https://www.bwwdw.com/article/itg5.html