第8章动态规划
8.1 在设备负荷分配问题中，n =10，a =0.7，b =0.85，g =15，h =10，期初有设备1000台。试利用公式(8.7)确定10期的设备最优负荷方案。 【解】
由公式
1
0()n t n t
i
i i i g h a a g b a ---==-≤≤-∑
∑得
(g -h )/g (b -a )＝0.2222，a 0＋a 1＋a 2＝1+0.7＋0.49＝2.19＜2.222＜a 0+a 1＋a 2＋a 3＝2.533，n －t －1＝2，t =7，则1~6年低负荷运行，7~10年为高负荷运行。各年年初投入设备数如下表。
年份
1 2 3 4 5 6 7 8 9 10 设备台数 1000 850 723 614 522 444 377 264 184.8 129 8.2如图8－4，求A 到F 的最短路线及最短距离。 【解】A 到F 的最短距离为13；最短路线 A→ B2→ C3 → D2 → E2 → F 及A→C2 → D2 → E2 → F
8.3求解下列非线性规划
(1) 123123max 0,1,2,3j Z x x x x x x C x j =++=???≥=?? (2) 22
123
123123min ,,0Z x x x x x x C
x x x =++++=??
≥?（3）2
123
123123max 2310
,,0
Z x x x x x x x x x =++++=??
≥?
(4)123123max 42100,1,2,3
j Z x x x x x x x j =++=???≥=?? (5) 123
123max 24100,1,2,3
j Z x x x x x x x j =++≤???
≥=??（6）22
1123123123max 228
,,0
Z x x x x x x x x x x =+++++=??
≥?
【解】（1）设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=C
则有 x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=C 用逆推法，从后向前依次有
k ＝3，33
3333()max()x s f s x s ===及最优解 x 3*=s 3
k ＝2，22
22
22
22233222222000()max [()max [()]max (,)x s x s x s f s x f x x s x h s x ≤≤≤≤≤≤==-=
由
2222221
20,2
h s x x s x ?=-=?则＝
22
2
2
2<0,h x ??＝－故2212x s =为极大值点。 所以222
22222111()244
f s s s s =-=及最优解x 2*=s 2
k =1时，1111112
111221*********()max[()]max ()max (,)4
x s x s x s f s x f s x s x h s x ≤≤≤≤≤≤==-=，
由221111111(43)04
h s s x x x ?=-+=?，得*
1113x s =
故23
111111111()()12327
f s s s s s =-= 已知知x 1 + x 2+ x 3 = C ，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下
*
113x C =，311()27
f C c =
由s 2=s 1－x 1*=2C/3，*
222211,()39x C f s C ==
由s 3=s 2－x 2*=C/3，*
33311,()33
x C f s C ==
最优解为：
3
1111(,,);33327
T X C C C z C ==
【解】（2）设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=C
则有x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=C 用逆推法，从后向前依次有
k ＝3，2
333333
()min()x s f s x s ===及最优解 x 3*=s 3
k ＝2，22
22
222
22233222222022
00()min [()min [()]min (,)x s x s x s f s x f x x s x h s x ≤≤≤≤≤≤=+=+-=
由2222221
420,2
h s x x s x ?=-=?则＝
2
2
22x h ??=4>0,故x 2=221
s 为极小值点。 因而有2*2222211
(),22
f s s x s ==
k ＝1时，11112
11111111001()min [()min (,)2
x s x s f s x s x h s x ≤≤≤≤=+-=
由1111
10h s x x ?=-+=?知*
1111111,()2x s f s s =-=-
得到最优解
1
(1,1/2,1/2);2
T X C z C =-=-
【解】(3) 设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=10 则有 x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=10 用逆推法，从后向前依次有
k ＝3时，33
2
3333()max()x s f s x s ===及最优解 x 3=s 3
k ＝2时，22
22
2
2222222200()max [3()]max (,)x s x s f s x s x h s x ≤≤≤≤=+-=
2222223
32202
h s x x s x ?=-+==-+?时 而22222
2320,2
h x s x ?=>=-+?故不是一个极大值点。 讨论端点：当x 2=0时2
222()f s s ＝, x 2= s 2时222()3f s s =
如果s 2>3时, 2
222()f s s =
k ＝1时，11
11
2
1111111100()max[2()]max (,)x s x s f s x s x h s x ≤≤≤≤=+-=
1
11111
22201h s x x s x ?=-+==-+?时 21
122
1
20,1h x s x ?=>=-+?故不是一个极大值点 同理有, x 1=0, f 1（s 1）= s 12= 100，x 1= s 1, f 1（s 1）= 2s 1= 20 (舍去) 得到最优解
(0,0,10);100X z ==
【解】(4)设s 3=x 3 ,2s 3+4x 2=s 2，s 2+x 1=s 1=10 则有x 3= s 3 ，0≤x 2≤s 2/4，0≤x 1≤s 1=10 用逆推法，从后向前依次有 k ＝1，
33
3333()max()x s f s x s ===及最优解x 3*=s 3
k ＝2，2222222222220404
1
()max [(2)max (,)2
x s x s f s x s x h s x ≤≤≤≤=-=
由22x h ??=2
1s 2-4x 2=0,则 x 2=81s 2
22
2
2
40h x ?=-
2
22()32
s f s =及最优解x 2*=s 2/8
k ＝1，1111
211111111001
()max[
()]max (,)32x s x s f s x s x h s x ≤≤≤≤=-= 22*
1111111111(43)0,323
h s s x x x s x ?=-+==?，故31111()216f s s = 得到最优解
(10/3,5/6,5/3);125/27T X z ==
【解】(5)按问题中变量的个数分为三个阶段s 1，s 2，s 3 ，且s 3≤10，x 1，x 2，x 3为各阶段的决
策变量，各阶段指标函数相乘。
设s 1=2x 1 , s 1+4x 2=s 2，s 2+x 3=s 3≤10，则有x 1= s 1/2，0≤x 2≤s 2/4，0≤x 3≤s 3=10 用顺推法，从前向后依次有 k ＝1，111
111/2
()max ()2
x s s f s x ===
及最优化解x 1*=s 1/2 k ＝2，2222222222220/4
0/4
1()max [(4)max (,)2
x s x s f s x s x h s x ≤≤≤≤=-=
由
22221402
h s x x ?=-=?,则*
2
218x s = 22
2
2
40h x ?=-
233333333001
()max [
()]max (,)32x s x s f s x s x h s x ≤≤≤≤=-= 由22*3333333311(43)0,323
h s s x x x s x ?=-+==? 故3
3331()216
f s s =，由于s 3≤10，则s 3=10时取最大值，x 3＝10/3，s 2=s 3－x 3＝20/3，x 2＝5/6，s 1=s 2－4x 2＝10/3，x 1＝5/3
得到最优解
(5/3,5/6,10/3);125/27T X z ==
【解】（6）设s 1=x 1, s 1+x 2=s 2，s 2+x 3=s 3=8
k ＝1，11
2
2
111111()max(2)2x s f s x x s s ==+=+及最优化解x 1*=s 1
k ＝2，22
22
2
2
222222222200()max [2()2()]max (,)x s x s f s x s x s x h s x ≤≤≤≤=+-+-=
2
222622,h x s x ?=--?222
2
60h x ?=>? x 2*=0时，f 2（s 2）=s 22+2s 2, x 2*= s 2时，f 2（s 2）=2s 22 故22
22222()max{2,2}f s s s s =+ k ＝3，
①当x 2*=0时，2
3333333333033
033
()max [()2()]max (,)x s x s f s x s x s x h s x ≤≤≤≤=+-+-= 同样得x 3*=0
时，f 3（s 3）=s 32+2s 3
x 3*=s 3时，f 3（s 3）=s 3 所以， f 3（s 3）= s 32+2s 3=80
②当x 2*= s 2时，f 3（s 3）=3
30max s x ≤≤[x 3+2（s 3-x 3）2]
同样得x 3*=0时，f 3（s 3）=2s 32 =128 x 3*=s 3时，f 3（s 3）=s 3 =8 所以， f 3（s 3）= 2s 32=128 最优解为
(0,8,0);128X z ==
8.4用动态规划求解下列线性规划问题。
12121212max 242624,0
Z x x x x x x x x =++≤??≤??
≤??≥?
【解】设s 2=x 2 ,s 2+2x 1=s 1≤6
则有 0≤x 2=s 2≤4，0≤x 1≤s 1/2 用逆推法，从后向前依次有 222()4f s s =及最优解x 2*=s 2
111111122110/2
0/2
()max [2()]max [46]x s x s f s x f s s x ≤≤≤≤=+=-
由 s 2=s 1－2x 1≤4， s 1≤6，取s 1＝6，
111110/2
()max [246]x s f s x ≤≤=-
又1≤x 1≤2，取x 1＝1，11()18f s =
最优解
(1,4);18T X z ==
8.5 10吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表8.24所示。应该如何装载货物使总价值最大。
i 123
123123max 3452349
,,0z x x x x x x x x x =++++≤??
≥?且为整数
利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求解。当R=1时，
1210/2
()max (3)x s f s x ≤≤=。计算结果如下：
当R=2时，f 2（s 3）=4
/210s x ≤≤[4x 2+f 1（s 3-3x 2）]
当R=3时，f 3（9）=2
30max ≤≤x [5x 3+f 2（9-4x 3）] （x 3为整数）=2
20max ≤≤x [f 2（9），5+f 2（5），
10+f 2（1）]=max[13，12，10]=13
8.6有一辆货车载重量为10吨，用来装载货物A 、B 时成本分别为5元/吨和4元/吨。现在已知每吨货物的运价与该货物的重量有如下线性关系：
A ：P 1=10-2x 1，
B ：P 2=12-3x 2
其中x 1 、x 2 分别为货物A 、B 的重量。如果要求货物满载，A 和B 各装载多少，才能使总利润最大
【解】A ：P 1=15-x 1，B ：P 2=18-2x 2 由题意可得各种货物利润函数为
21111112222222
()(155)10()(1824)142g x x x x x g x x x x x
=--=-=--=-
原问题的数学模型归结为
22
11221212max (10)(142)
10,0
z x x x x x x x x =-+-+=??
≥?
最优解：x 1 =6，x 2 =4；z ＝48
8.7 现有一面粉加工厂，每星期上五天班。生产成本和需求量见表8-25。
表8-25
面粉加工没有生产准备成本，每袋面粉的存储费为h k ＝0.5元/袋，按天交货，分别比较下列两种方案的最优性，求成本最小的方案。
（1）星期一早上和星期五晚的存储量为零，不允许缺货，仓库容量为S=40袋； （2）其它条件不变，星期一初存量为8。 【解】动态规划求解过程如下： 阶段k ：日期，k =1,2,…,6
状态变量s k ：第k 天早上（发货以前）的冷库存量 决策变量x k ：第k 天的生产量 状态转移方程：s k +1=s k +x k －d k ；
决策允许集合：{}
400,0)(≤-+≤≥=k k k k k k k d x s x x s D 阶段指标：v k (s k ，x k )=c k x k +0.5s k 终端条件：f 6(s 6)=0, s 6=0； 递推方程：
{}
{}
)(),(min
)(),(min )(1)
(11)
(k k k k k k k k s k D k x k k k k k k s k D k x k k d x s f x s v s f x s v x f -++=+=+∈++∈
当k =5时，因为s 6=0，有6555550,15,s s x d x s =+-==-
由于s 5≤15，
{}
55
555515*55
5
()min 100.51509.5, 15x s f s x s s x s ∈-=+ =-=-
k =4时，5440153015,s s x ≤≤≤+-≤，0有44445s x s -≤≤-30，
{{444444444455()
44()
*444
4*
444()min 120.5()}
min
2.59435}
11.551030,3094354030,0
x D s x D s f s x s f s x s s s x s s s x ∈∈=++=-+?-+≤=-=?-+≤≤=?
k =3时，当0≤s 4≤30时，332530s +x ≤-≤0，得
3332555s x s -≤≤-
有{}
333333()max[0.25]55D s x s x s =-≤≤-
{{{3333
3
3
3
3
3
333344()
334()
33()
*
333
()min
90.5()}
min 90.511.5510}min 2.511797.5}8.5660
55x D s x D s x D s f s x s f s x s s x s s x s ∈∈∈=++=+-+=--+=-+=-取上界：
当30≤s 4≤40时，4330,302540x s +x =≤-≤，有
{}333333()5565D s x s x s =-≤≤-
{{{3333333
3
3
(1)333344()
334()
*
33()
()min
90.5()}
min
90.59435}min 8.5210},x D s x D s x D s f s x s f s x s s x x ∈∈∈=++=+-+=-+ 取任意值
显然此决策不可行。
当k =2时，由4322030,0252025,s s s x ≤≤≤≤≤+-≤，0x 2的决策允许集合为
{}222222()max[0,20]45D s x s x s =-≤≤-
{{2222
2
2
22222()
22()
*
222
()min
60.56608.5}
min 2.58830}5.5717.5
45x D s x D s f s x s s x s s x s ∈∈=++-=--+=-+=-取上界：
当k =1时，由21102001020s s x ≤≤≤+-≤，，则x 1的决策允许集合为
{}111111()max[0,10]30D s x s x s =-≤≤- {}
{}11111111112()
11()
()min 80.5717.5 5.5min 2.55772.5797.5
x D s x D s f s x s s x s ∈∈=++-=-+=
因为110, 10,s x ==
222322334334454455 10100, 4545, 2025, 5530, 2530, 300, 300, 1515.
s x s s s x x s s s x x s s s x x s =-==-==+-==-==+-==-==+-==-=-
(2)期初存储量s 1=8, 与前面计算相似，x 1=2. Min Z=772.5+2.5x 1-5s 1=737.5 则总成本最小的方案是第二种。
8.8 某企业计划委派10个推销员到4个地区推销产品，每个地区分配1~4个推销员。各地区月收益（单位：10万元）与推销员人数的关系如表8－26所示。
表8-26
企业如何分配4个地区的推销人员使月总收益最大。
【解】设x k 为第k 种货物的运载重量，该问题的静态规划模型为
112233441234max ()()()()80,2,4,6,8
j Z v x v x v x v x x x x x x =++++++=???=??
利用图表法：
故最优解为12340,0,4x x x x ====
则 max Z=44
8.9有一个车队总共有车辆100辆，分别送两批货物去A 、B 两地，运到A 地去的利润与车辆数目满足关系100x ，x 为车辆数，车辆抛锚率为30%，运到B 地的利润与车辆数y 关系为80y ，车辆抛锚率为20%，总共往返3轮。请设计使总利润最高的车辆分配方案。 【解】动态规划求解过程如下。
阶段k ：共往数k=1,2,3,4，k=1表示第一趟初，k =4表示第三趟末（即第六年初）； 状态变量s k ：第k 趟初完好的车辆数（k =1,2,3,4），也是第k －1趟末完好的车辆数，其中s 4表示第三趟末的完好车辆数。
决策变量x k ：第k 年初投入高负荷运行的机器数； 状态转移方程：s k +1=0.7x k +0.8(s k －x k ) 决策允许集合：D k (s k )={x k |0≤x k ≤s k } 阶段指标：v k (s k ，x k )=100x k +80(s k －x k ) 终端条件：f 4(s 4)=0 递推方程：
{}
[]{}
11()
10()max
(,)()max 10080()0.70.8()k k k k k
k k k k k k k x D s k k k k k k k x s f s v s x f s x s x f x s x ++∈+≤≤=+=+-++-
f k (x k )表示第k 趟初分配x k 辆车到A 地，到第3趟末的最大总运价为
{}
33
33
33333440*333
3
30()max 10080()()max{2080}100x s x s f s x s x f s x s s x s ≤≤≤≤=+-+ =+==最优
{}
22
22
22222330*222
2
20()max 10080()()max {10160}170x s x s f s x s x f s x s s x s ≤≤≤≤=+-+=+==最优
{}
11
11
11111220*111
110()max 10080()()max{3216}219x s x s f s x s x f s x s s x s ≤≤≤≤=+-+=+==最优
因为s 1=100，最大总运价f 1(s 1)=21900元
8.10 系统可靠性问题。一个工作系统由n 个部件串联组成，见图8-5。只要有一个部件失灵，整个系统就不能工作。为提高系统的可靠性，可以增加部件的备用件。例如，用5个部件1并联起来作为一个部件与部件2串联，如果其中一个部件失灵其它4个部件仍能正常工作。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。
图8-5
假设部件(1,2,,)i i n = 上装有i x 个备用件，该部件正常工作的概率为()i i p x 。设装一个部件i 的备用件的成本为i c ，要求备件的总费用为C 。那么该问题模型为：
1
1
max ()
01,2,,n
i i i n i i i j
P p x c x C x i n ===?≤???≥=?∏∑ 并且为整数，（8.8）
同理，如果一个复杂的工作系统由n 个部件并联组成的，只有当n 个部件都失灵，整个系统就不能工作，见图8-6。
图8-6
部件1
部件2
……
部件n
假设()i i p x 为第i 个部件失灵的概率，为提高系统的可靠性，可以增加部件的备用件。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。系统的可靠性为1
1()n
i
i
i p x =-
∏，则该问题的数学模型归结为
1
1
min ()
01,2,,n
i i i n i i i j
P p x c x C x i n ===?≤???≥=?∏∑ 并且为整数，（8.9）
利用式(8－8)或（8－9）求解下列问题。
（1）工厂设计的一种电子设备，其中有一系统由三个电子元件串联组成。已知这三个元件的价格和可靠性如表8-27所示，要求在设计中所使用元件的费用不超过200元，试问应如何设计使设备的可靠性达到最大。
表8-27
（2）公司计划在5周内必须采购一批原料，而估计在未来的5周内价格有波动，其浮动价格和概率根据市场调查和预测得出，如表8-28所示，试求在哪一周以什么价格购入，使其采购价格的期望最小，并求出期望值。
表8-28
【解】（1）设123x x x 、、分别为元件1、2、3的备件数，则数学模型为
312123123max (10.05)(10.2)(10.4)403520200,,0x x x Z x x x x x x =---++≤??
≥?并且为整数
最优解X=(1，2，4)；可靠性Z=0.888653，总费用190。即元件1使用一个，元件2使用2个并联，元件3使用4个并联。
（2）
设阶段k ，可按采购期限分为5段，k ＝l ，2，3，4，5 决策变量为x k ，第k 周采购则x k ＝l ，若不采购则x k ＝0 状态变量s k 表示第k 周原料实际价格
用Q k 表示当第k 周决定等待，而在以后采购时的采购价格期望值，即
11110.1(550)0.25(650)0.3(800)0.35(900)k k k k k Q f f f f ++++=+++
最优指标函数f k (s k )表示第k 周实际价格为s k 时，从第k 周到第5周采取最优决策所花费的
最低期望价格，递推公式为
{}}
{55555()min ,,4,3,2,1()550,650,00k k k k k k k f s s Q s D k f s s s D D ?=∈=?
=∈?
，，为状态集合800,9 则k ＝5时，因为若前四周尚未购买，则无论本周价格如何，该企业都必须购入原料 所以
*
55*
5555*
55*
55550, 5501650, 6501()800, 8001900,8001s x s x f s s x s x ?==?==?=?==??==?
当，当，当，当，
当k ＝4时，
455550.1(550)0.25(650)0.3(800)0.35(900)0.15500.256500.38000.35900772.5
Q f f f f =+++=?+?+?+?=
}{}
{44
44444*
44*44*
44()min ,min ,772.5550, 5501650 6501 8009000s D f s s Q s s x s x s x ∈==?==?===??==?当，，当，772.5，当
或， 当k ＝3时，
344440.1(550)0.25(650)0.3(800)0.35(900)0.15500.25650(0.30.35)772.5719.625Q f f f f =+++=?+?++?=
}{}
{33
33333*
33*33*33()min ,min ,719.625550, 5501650 6501719.625 8009000s D f s s Q s s x s x s x ∈==?==?===??==?
当，，当，，当或， 当k ＝2时，
233330.1(550)0.25(650)0.3(800)0.35(900)0.15500.256500.30.30.35719.625685.256
Q f f f f =+++=?+?+?+?=（）
}{}
{22
22222*22*22*
22()min ,min ,685.256550, 5501650 6501685.256 8009000s D f s s Q s s x s x s x ∈==?==?===??==?当，，当，，
当或， 当k ＝1时，
112220.1(550)0.25(650)0.3(800)0.35(900)0.15500.256500.30.30.35685.256662.92
Q f f f f =+++=?+?+?+?=（）
}{}
{11
11111*
11*11*
11()min ,min ,662.92550, 5501650 6501662.92 8009000s D f s s Q s s x s x s x ∈==?==?===??==?当，，当，，
当或， 最优采购策略：
若前面四周原料价格为550或650时，则立即采购，否则在以后的几周内再采购。第五周无论当时的价格为多少都必须采购。期望价格为11()0.15500.25650(0.30.35)662.92648.4f s =?+?++?=（元）
8.11 思考与简答题
（1）简述动态规划模型的特点。
（2）动态规划数学模型由哪些要素构成。 （3）动态规划求解的基本步骤是什么。 （4）简述动态规划的基本原理。
（5）为什么说动态规划是解决多阶段决策问题的一种思路。
（6）名词解释：阶段、状态、决策、策略、状态转移方程、指标函数、最优指标函数。 （7）什么是顺序法和逆序法。 （8）什么是无后效性。
（9）指标函数的连和形式与连乘形式各是怎样的函数。 （10）状态转移方程是哪些变量的函数。
返回顶部
第四章动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20 世纪50 年代初R. E. Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 图1 是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A 到G距离最短（或费用最省）的路线。 图1 最短路线问题 例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3 （千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类根据过程的时间变量是离散的还是连续的，分为离散时间 决策过程（discrete-time -56-
第四章 数学规划模型 【教学目的】：深刻理解线性规划，非线性规划，动态规划方法建模的基本特点，并能熟练建立一些实际问题的数学规划模型；熟练掌握用数学软件（Matlab ，Lindo ，Lingo 等）求解优化问题的方法。 【教学重点难点】： 教学重点：线性规划和非线性规划的基本概念和算法，解决数学规划问题的一般思路和 方法，线性规划模型、整数规划模型、非线性规划模型的构建及其Matlab 与Lingo 实现。 教学难点：区分线性规划模型和非线性模型适用的实际问题，以及何时采用线性模型， 何时采用非线性模型，线性模型与非线性模型的转化。 【课时安排】：10学时 【教学方法】：采用多媒体教学手段，配合实例教学法，通过对典型例题的讲解启发学生思维，并给与学生适当的课后思考讨论的时间，加深知识掌握的程度。安排一定课时的上机操作。 【教学内容】： 在众多实际问题中，常常要求决策（确定）一些可控制量的值，使得相关的量（目标）达到最佳（最大或最小）。这些问题就叫优化问题，通常需要建立规划模型进行求解。称这些可控制量为决策变量，相关的目标量为目标函数；一般情况下，决策变量x 的取值是受限制的，不妨记为x ∈Ω，Ω称为可行域，优化问题的数学模型可表示为 Max(或Min)f(x), x ∈Ω 一般情况下，x 是一个多元变量，f(x)为多元函数，可行域比较复杂，一般可用一组不等式组来表示，这样规划问题的一般形式为 () x Min f x . ()0,1,2,,i st g x i m ≤= 虽然，该问题属于多元函数极值问题，但变量个数和约束条件比较多，一般不能用微分法进行解决，而通过规划方法来求解；这里讨论的不是规划问题的具体算法，主要是讨论如何将一个实际问题建立优化模型，并利用优化软件包进行求解。 根据目标函数和约束函数是否为线性，将规划模型分为线性规划和非线性规划。 4.1线性规划 线性规划(LP)研究的实际问题多种多样的，它在工农业生产、经济管理、优化设计与控
动态规划 关健字：阶段状态决策函数递推式 摘要： 动态规划是解决多阶段决策最优化问题的一种思想方法。所谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。动态规划思想近来在各类型信息学竞赛中频繁出现，它的应用也越来越受人重视。本文就是讨论如何运用动态规划的思想设计出有效的数学模型来解决问题。 一动态规划问题的数学描述 我们先来看一个简单的多阶段决策问题。 [例1]现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试找出从结点1到结点10的最短路径。 第一阶段第二阶段第三阶段第四阶段第五阶段 图1 本问题的解决可采用一般的穷举法，即把从结点1至结点10的所有道路列举出来，计算其长度，再进行比较，找出最小的一条。虽然问题能解决，但采用这种方法，当结点数增加，其运算量将成指数级增长，故而效率是很低的。 分析图1可知，各结点的排列特征： (1) 可将各结点分为5个阶段； (2) 每个阶段上的结点只跟相邻阶段的结点相连，不会出现跨阶段或同阶段
结点相连的情况，如不会出现结点1与结点4连、结点4与结点5连的情况。 (3) 除起点1和终点10外，其它各阶段的结点既是上一阶段的终点，又是下一阶段的起点。例如第三阶段的结点4、5、6，它即是上一阶段结点2、3中某结点的终点，又是下一阶段结点7、8、9中某结点的起点。 根据如上特征，若对于第三阶段的结点5，选择1-2-5和1-3-5这两条路径，后者的费用要小于前者。那么考虑一下，假设在所求的结点1到结点10最短路径中要经过结点5，那我们在结点1到结点5之间会取那条路径呢？显然，无论从结点5出发以后的走法如何，前面选择1-3-5这条路都总是会优于1-2-5的。也就是说，当某阶段结点一定时，后面各阶段路线的发展不受这点以前各阶段的影响。反之，到该点的最优决策也不受该点以后的发展影响。 由此，我们可以把原题所求分割成几个小问题，从阶段1开始，往后依次求出结点1到阶段2、3、4、5各结点的最短距离，最终得出答案。在计算过程中，到某阶段上一结点的决策，只依赖于上一阶段的计算结果，与其它无关。例如，已求得从结点1到结点5的最优值是6，到结点6的最优值是5，那么要求到下一阶段的结点8的最优值，只须比较min{6+5,5+5}即可。这样，运用动态规划思想大大节省了计算量。可以看出，动态规划是解决此类多阶段决策问题的一种有效方法。 二动态规划中的主要概念，名词术语 1阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。 2 状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。如图1中，阶段3就有三个状态结点4、5、6。 3 决策：从某阶段的一个状态演变到下一个阶段某状态的选择。 4策略：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。 5 状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。 6 目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。 三运用动态规划需符合的条件 任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同理，动态规划也并不是万能的。那么使用动态规划必须符合什么条件呢？必须满足最优化原理和无后效性。 1 最优化原理 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状
第七章动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 §7.1 动态规划的基本理论 1.1多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。
第8章动态规划 8.1 在设备负荷分配问题中，n =10，a =0.7，b =0.85，g =15，h =10，期初有设备1000台。试利用公式(8.7)确定10期的设备最优负荷方案。 【解】 由公式 1 0()n t n t i i i i g h a a g b a ---==-≤≤-∑ ∑得 (g -h )/g (b -a )＝0.2222，a 0＋a 1＋a 2＝1+0.7＋0.49＝2.19＜2.222＜a 0+a 1＋a 2＋a 3＝2.533，n －t －1＝2，t =7，则1~6年低负荷运行，7~10年为高负荷运行。各年年初投入设备数如下表。 年份 1 2 3 4 5 6 7 8 9 10 设备台数 1000 850 723 614 522 444 377 264 184.8 129 8.2如图8－4，求A 到F 的最短路线及最短距离。 【解】A 到F 的最短距离为13；最短路线 A→ B2→ C3 → D2 → E2 → F 及A→C2 → D2 → E2 → F 8.3求解下列非线性规划 (1) 123123max 0,1,2,3j Z x x x x x x C x j =++=???≥=?? (2) 22 123 123123min ,,0Z x x x x x x C x x x =++++=?? ≥?（3）2 123 123123max 2310 ,,0 Z x x x x x x x x x =++++=?? ≥? (4)123123max 42100,1,2,3 j Z x x x x x x x j =++=???≥=?? (5) 123 123max 24100,1,2,3 j Z x x x x x x x j =++≤??? ≥=??（6）22 1123123123max 228 ,,0 Z x x x x x x x x x x =+++++=?? ≥? 【解】（1）设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=C 则有 x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=C 用逆推法，从后向前依次有 k ＝3，33 3333()max()x s f s x s ===及最优解 x 3*=s 3 k ＝2，22 22 22 22233222222000()max [()max [()]max (,)x s x s x s f s x f x x s x h s x ≤≤≤≤≤≤==-= 由 2222221 20,2 h s x x s x ?=-=?则＝
精心整理 第四章决策 一、单项选择题 1、有一种说法认为"管理就是决策"，这实际上意味着：（C ） A.对于管理者来说只要善于决策就一定能够获得成功 B.管理的复杂性和挑战性都是由于决策的复杂性而导致的 C.决策能力对于管理的成功具有特别重要的作用 D.管理首先需要的就是面对复杂的环境作出决策 2 A.3、根据"A.B.C.D.4(1)5 A.B.C.D.620A.B.C.D.这不是真正意义上的授权而只是一种工作落实 7、某企业原先重大战略决策的基本过程是由各部门(如财务部、销售部、生产部、人事部等)独立把各自部门的情况写成报告送给总经理，再由总经理综合完成有关的战略方案。后来，对此过程作了些调整，这就是：总经理收到各部门呈上的报告后，有选择地找些管理人员来磋商，最后由自己形成决策。再后来，总经理在收到报告后，就把这些报告交给一个有各部门人员共同参与组成的委员会，通过委员会全体成员的面对面讨论，最终形成有关决策。对此你的看法是：（Ｃ） A.这种处理方式的改变对企业战略决策以及其它方面的工作没什么影响 B.这种处理方式的改变可以大大提高企业决策的效率 C.这种处理方式的改变增加了信息沟通的范围，可带来更多的成员满意感 D.这种处理方式的改变提高了企业上下信息沟通的效率 8、现在社会上销售彩票的很多。一家三口在抽奖时，常常喜欢让孩子来抽，请问这是遵循了什么决策原则?（A ）
A.乐观原则 B.悲观原则 C.折衷原则 D.最小最大后悔值原则 9、某企业集团拟投资开发新产品，现有两个方案，假定其开发费用相同。开发甲产品，估计投产后，市场竞争不激烈时每年可获利150万元，市场竞争激烈时每年亏损50万元。开发乙产品，估计投产后无论市场竞争激烈与否，每年均可获利70万元。根据预测，这两种拟开发的产品投产后，出现市场竞争不激烈情况的概率为0.6，出现市场竞争激烈情况的概率为0.4。如果只能在这两个方案中选一个，你的评价是什么?（B） A.开发甲产品比开发乙产品好。 B.开发乙产品比开发甲产品好。 C.开发甲产品与开发乙产品没什么差别。 D.根据以上资料尚无法下结论。 10、在以下X、Y和Z三种方案中，哪一个方案最好？（B） A.X 11 A. B. C. D. 12 A. 13、 A. 13 A. C. 14 A.关于公司各部门办公电脑的分配方案 D.对一位客户投诉的例行处理 C.对一家主要竞争对手突然大幅削价作出反应 D.对一位公司内部违纪职工按规章进行处理 15、在制定计划时，为了有效地确定前提条件，应当：（A） A.找出并着重研究那些关键性的、战略性的的提条件， B.要准备不止一套的备选前提条件，以供出现偶发事件时应急使用。 C.所选择的各前提条件相互间必须协调一致。 D.对以上3条作综合考虑。 16、有一个大家熟悉的商务趣闻：甲乙两家鞋业公司的经理各派了一位市场调查员去某岛调查，发现岛上的居民从来不穿鞋。结果甲公司的调查员向公司报告称自己发现厂一个新市场，进而开拓了市场；而乙公司的调查员则
第八章动态规划 动态规划模型和求解方法 (1)阶段． (2)状态．描述过程在第k阶段状态的变量，称为状态变量，用s k表示．s k取值的全体记作S k，称作第k阶段的状态集合． 状态的定义在动态规划中往往是最重要的概念．它必须具备3个特性： ①描述性．各阶段状态的演变能描述决策过程． ②无后效性．如果第k阶段的状态给定，则在这阶段以后过程的发展不受这阶段以前各个阶段状态的影响．也就是说，过程未来的发展，只与过程的现在状态有关，而与过程的过去状态无关． ③阶段状态变量的取值，直接或间接是可知的，也就是说，第k阶段的状态集合S k是给定的． (3)决策．当第k阶段的状态s k给定后，从该状态演变为第k+1阶段状态时所作的选择称
为决策． 描述决策的变量称为决策变量，用x k(s k)表示，简记为x k． x k(s k)取值的全体记为D k(s k)，称为第k阶段的决策集合，s k取值不同，相应的决策集合也可能不同． (4)策略．{ x1(s1)，x2(s2)…，x N(s N)}称为策略． (5)状态转移方程．第k+1阶段的状态s k+l 与第k阶段的状态s k、决策x k之间有函数关系s k+l =T k (s k，x k)， 并称其为状态转移方程． (6)权函数．在第k阶段，当状态取定s k、决策取定x k时，该阶段所实现的效益指标(例如距离、时耗、利润、成本等)称为权函数， (7)指标函数．若第k阶段的状态为s k，当采用了最优子策略{ x*k，x*k+1，…，x*N}后，从阶段k到阶段N可获得的效益，称为指标函数，记为f k (s k)．实现f k (s k) 值的x k记为x*k． (8)递归方程．称下列方程为递归方程： f N+1 (s N+1) =0或1，
第八章自动规划 教学内容：介绍自动规划的基本概念和各种规划系统。 教学重点：机器人规划的作用与任务、积木世界的规划系统、具有学习能力的规划系统、基于专家系统的规划机理。 教学难点：具有学习能力的规划系统。 教学方法：课堂教学为主，注意结合例子来说明抽象概念。 教学要求：本章为选修内容，掌握机器人规划的作用与任务，并一般了解有哪几种规划方法。 8.1机器人规划的作用与任务 教学内容：引入规划的概念，说明问题分解途径，然后讨论自动规划系统的任务。 教学重点：机器人规划的作用。 教学方法：课堂教学。 教学要求：掌握机器人规划的作用与任务。 8.1.1规划的作用与问题分解途径 1、规划的概念及作用 规划的概念：规划是一种重要的问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。 规划的作用：规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。 2、问题分解途径及方法 把某些较复杂的问题分解为一些较小的子问题。有两条实现这种分解的重要途径。 第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。
第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。 3、域的预测和规划的修正 举例：以工作日计划来形象地说明规划的作用。 8.1.2机器人规划系统的任务与方法 在规划系统中，必须具有执行下列各项任务的方法： (1) 根据最有效的启发信息，选择应用于下一步的最好规则。 (2) 应用所选取的规则来计算由于应用该规则而生成的新状态。 (3) 对所求得的解答进行检验。 (4) 检验空端，以便舍弃它们，使系统的求解工作向着更有效的方向进行。 (5) 检验殆正确的解答，并应用具体的技术使之完全正确。 下面讨论能够执行上述5项任务的方法。 1、选择和应用规则 在选择合适的应用规则时最广泛采用的技术是：首先要查出期望目标状态与现有状态之间的差别集合，然后辨别出那些与减少这些差别有关的规则。 2、检验解答与空端 当规划系统找到一个能够把初始问题状态变换为目标状态的操作符序列时，此系统就成功地求得问题的一个解答。 如果搜索过程是从初始状态正向推理的，那么可以删去任何导致某种状态的路径，从这种状态出发是无法达到目标状态的。 如果搜索过程是从目标状态逆向推理的，那么当确信无法达到初始状态，或者搜索过程进展甚微时，可以终止该路径的搜索。 3、修正殆正确解 一个求解殆可分解问题的办法是：当执行与所提出的解答相对应的操作符序列时，检查求得的状态，并把它与期望目标加以比较。
第四章 动态规划初步 第一节 问题概览 一、问题的表述 与变分法和最优控制相比，动态规划处理离散时间与不确定性问题更有优势。在本章中，我们将简介在确定性下的动态规划的初步知识。我们从下面的问题开始： {}0 (1)((0))((),(1))max t t x t V x U x t x t β∞=∞* +=+∑ （P1） .. (1)(())s t x t G x t +∈， 对所有的时间t (0)x 给定。 约束说明在()x t 时(1)x t +的值。()x t 是状态变量，(1)x t +可以看作是t 时的控制变量。所以该约束说明给定状态变量如何确定控制变量。U 是瞬时回报（实值函数），U 不独立依赖于时间。 我们是要得到最优值序列{}0 (1)t x t ∞ *=+以使得((0))V x *最大，{}0 (1)t x t ∞ *=+被称 为最优计划（plan ），((0))V x *是值函数。我们把问题P1的形式称为序贯（sequence problem ）问题。显而易见，((0))V x *与初始的(0)x 相关，即不同的(0)x 会导致不同的最优值。下面是一个该问题形式的具体例子： 例1：{} (),() max (())t c t k t t U c t β∞ =∑ .. (1)(())()(1)()s t k t f k t c t k t δ+=-+- ()0k t ≥，(0)k 给定。 该例子实际上就是代表性主体（或计划者）的Ramsey 问题。该问题不是标准的P1问题的形式，但是我们可以将它转化成P1的形式： {}0 (1)((0))((())(1)(1)())max t t k t V k U f k t k t k t βδ∞=*+=-++-∑ .. (1)[0,(())(1)()]s t k t f k t k t δ+∈+- 其中，()(())(1)(1)c t f k t k t k t δ=- ++-。对应P1式中：()()x t k t =，
（决策管理）参考试题第四章决策
第四章决策 壹、单项选择题 1、有壹种说法认为"管理就是决策"，这实际上意味着：（C） A.对于管理者来说只要善于决策就壹定能够获得成功 B.管理的复杂性和挑战性均是由于决策的复杂性而导致的 C.决策能力对于管理的成功具有特别重要的作用 D.管理首先需要的就是面对复杂的环境作出决策 2、有关活动尚未进行，从而环境未受到影响的情况下作出的决策是（C） A.长期决策 B.战术决策 C.初始决策 D.程序化决策 3、根据"企业运营单位组合分析图"，下列哪壹项命题是不正确的？（C） A.幼童和瘦狗均可能被放弃 B.金牛能给企业带来最大的现金流 C.对幼童和明星均应该投入巨资以扩大其市场占有率 D.应用该方法决策要以"企业的目标是追求增长和利润"为前提 4、对某复杂问题进行系统分析,从而得到最满意的行动方案,可能需要做这样壹些工作：(1)对方案进行分析、比较、评价；(2)选择满意方案；(3)阐明问题现状；(4)提出可行备选方案；(5)明确决策目标。你认为正确的分析思路和程序应该是：（A） A.(5)(3)(4)(1)(2) B.(3)(4)(1)(2)(5) C.(5)(4)(3)(1)(2) D.(3)(5)(4)(1)(2) 5、政策指导矩阵是根据（D）将运营单位进行分类的。 A.业务增长率和相对竞争地位
B.业务增长率和行业市场前景 C.运营单位的竞争能力和相对竞争地位 D.运营单位的竞争能力和行业市场前景 6、某XX公司总裁决定进壹步采取授权行动，于XX公司内部推行民主管理。最近XX公司发文规定，于文件所列举的20种紧急情况下，壹线经理有权自主采取行动，但需将进展情况和结果及时方案上级经理。对于这壹安排，你认为下述描述中哪壹条最贴切?（D） A.这表明XX公司显著增加了壹线经理的决策权 B.XX公司有限度地扩大了壹线经理的自主决策权 C.如果无须方案上级经理，这种做法就是授权 D.这不是真正意义上的授权而只是壹种工作落实 7、某企业原先重大战略决策的基本过程是由各部门(如财务部、销售部、生产部、人事部等)独立把各自部门的情况写成方案送给总经理，再由总经理综合完成有关的战略方案。后来，对此过程作了些调整，这就是：总经理收到各部门呈上的方案后，有选择地找些管理人员来磋商，最后由自己形成决策。再后来，总经理于收到方案后，就把这些方案交给壹个有各部门人员共同参和组成的委员会，通过委员会全体成员的面对面讨论，最终形成有关决策。对此你的见法是：（Ｃ） A.这种处理方式的改变对企业战略决策以及其它方面的工作没什么影响 B.这种处理方式的改变能够大大提高企业决策的效率 C.这种处理方式的改变增加了信息沟通的范围，可带来更多的成员满意感 D.这种处理方式的改变提高了企业上下信息沟通的效率 8、当下社会上销售彩票的很多。壹家三口于抽奖时，常常喜欢让孩子来抽，请问这是遵循
１８９ 习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?
7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解） １９０
第四章决策 一、单项选择题 1、有一种说法认为"管理就是决策"，这实际上意味着：（ C ） A.对于管理者来说只要善于决策就一定能够获得成功 B.管理的复杂性和挑战性都是由于决策的复杂性而导致的 C.决策能力对于管理的成功具有特别重要的作用 D.管理首先需要的就是面对复杂的环境作出决策 2、有关活动尚未进行，从而环境未受到影响的情况下作出的决策是（ C ） A.长期决策 B.战术决策 C.初始决策 D.程序化决策 3、根据"企业经营单位组合分析图"，下列哪一项命题是不正确的？（ C ） A.幼童和瘦狗都可能被放弃 B.金牛能给企业带来最大的现金流 C.对幼童和明星都应该投入巨资以扩大其市场占有率 D.应用该方法决策要以"企业的目标是追求增长和利润"为前提 4、对某复杂问题进行系统分析,从而得到最满意的行动方案,可能需要做这样一些工作： (1) 对方案进行分析、比较、评价；(2) 选择满意方案；(3) 阐明问题现状；(4) 提出可行备选方案；(5)明确决策目标。你认为正确的分析思路与程序应该是：（ A ） A.(5) (3) (4) (1) (2) B.(3) (4) (1) (2) (5) C.(5) (4) (3) (1) (2) D.(3) (5) (4) (1) (2) 5 、政策指导矩阵是根据（ D ）将经营单位进行分类的。 A.业务增长率和相对竞争地位 B.业务增长率和行业市场前景 C.经营单位的竞争能力与相对竞争地位 D.经营单位的竞争能力与行业市场前景 6、某公司总裁决定进一步采取授权行动，在公司内部推行民主管理。最近公司发文规定，在文件所列举的20 种紧急情况下，一线经理有权自主采取行动，但需将进展情况和结果及时报告上级经理。对于这一安排，你认为下述描述中哪一条最贴切? （ D ） A.这表明公司显著增加了一线经理的决策权 B.公司有限度地扩大了一线经理的自主决策权 C.如果无须报告上级经理，这种做法就是授权 D.这不是真正意义上的授权而只是一种工作落实 7、某企业原先重大战略决策的基本过程是由各部门(如财务部、销售部、生产部、人事部等)独立把各自部门的情况写成报告送给总经理，再由总经理综合完成有关的战略方案。后来，对此过程作了些调整，这就是：总经理收到各部门呈上的报告后，有选择地找些管理人员来磋商，最后由自己形成决策。再后来，总经理在收到报告后，就把这些报告交给一个有各部门人员共同参与组成的委员会，通过委员会全体成员的面对面讨论，最终形成有关决策。对此你的看法是：（Ｃ） A.这种处理方式的改变对企业战略决策以及其它方面的工作没什么影响 B.这种处理方式的改变可以大大提高企业决策的效率 C.这种处理方式的改变增加了信息沟通的范围，可带来更多的成员满意感 D.这种处理方式的改变提高了企业上下信息沟通的效率 8、现在社会上销售彩票的很多。一家三口在抽奖时，常常喜欢让孩子来抽，请问这是遵循了什么决策原则?（ A ） A. 乐观原则 B.悲观原则 C.折衷原则 D.最小最大后悔值原则 9、某企业集团拟投资开发新产品，现有两个方案，假定其开发费用相同。开发甲产品，估计投产后，市场竞争不激烈时每年可获利150万元，市场竞争激烈时每年亏损50万元。开发乙产品，估计投产后无论市场竞争激烈与否，每年均可获利70万元。根据预测，这两种拟开发的产品投产后，出现市场竞争不激烈情况的概率为0.6，出现市场竞争激烈情况的概率为0.4。如果只能在这两个方案中选一个，你的评价是什么?（ B ）
第四章决策 一、名词解释： 1、决策 2、例行问题和例外问题 3、程序化决策和非程序化决策 4、战略决策、战术决策和业务决策 5、确定型决策、风险型决策、不确定型决策 6、决策树法 二、选择题 1、决策是工作和日常生活中经常要进行的活动，但人们对其含义的理解不尽相同，你认为以下哪种理解较为完整？（） A、出主意 B、拿主意 C、既出主意又拿主意 D、评价各种主意 2、企业经营方案决策最终所选出的方案一般为（） A、成本最低的方案 B、较为满意的方案 C、各个目标都最佳的方案 D、实现理论最大的方案 3、企业管理中的高层管理者一般主要负责制定（） A、局部程序性决策 B、短期操作性决策 C、日常事务性决策 D、长远战略性决策 4、（）是日常工作中为提高生产效率、工作效率而做出的决策，牵涉范围较窄，只对组织产生局部影响。 A、战略决策 B、战术决策 C、个人决策 D、业务决策 5、下列选项中属于企业的短期决策的是（） A、投资方向的选择 B、人力资源的开发 C、组织规模的确定 D、企业日常营销 6、在经营单位组合分析法中，具有较高业务增长率和较低市场占有率的经营单位是（） A、金牛 B、明星 C、幼童 D、瘦狗 7、有一种说法认为“管理就是决策”，这实际上意味着（） A、对于管理者来说只要善于决策就一定能获得成功 B、管理的复杂性和挑战性都是由于决策的复杂性导致的 C、决策能力对于管理的成功具有特别重要的作用 D、管理首先需要的就是面对复杂的环境做出决策 8、决策树适合于下列哪种类型的决策（） A、确定型决策 B、非确定型决策 C、风险型决策 D、A、B和C 9、在决策要素中，决策者无法控制但又对决策后果起重大影响的要素是（） A、决策方案 B、决策环境 C、决策变量 D、决策评价 10、企业面临的境况正日益变得复杂多变，企业的决策越来越难以依靠个人的智力经验来应付了，因此，现代决策应该更多地依靠（） A、多目标协调 B、集体智慧 C、动态规划 D、下级意见 11、应根据所作决策的具体情况，采用相应的决策方式，以下几种情况，哪一种通常不采用群体决策方式（） A、确定长期投资于哪一种股票 B、决定一个重要副手的工作安排
骆吉洲作业： 1. 设有n种不同面值的硬币，个个硬币的面值存于数组T[1:n]中。现在用这些硬币来找钱。各种硬币使用的各数不限。 （1）当只用面值为T[1]、T[2],…,T[i]来找出钱j时，所用的硬币的最小个数记为C(i,j),写出C(i,j)的递推式。 （2）设计一个动态规划算法以计算C(n,j)，1≤j≤L，并且只使用一个规模为L的数组，并分析该算法的复杂度。 （3）设C(n,j)，1≤j≤L已经计算出来，对任意钱数m（小于等于L），确定用最少硬币数找出钱m的策略。证明该问题有贪心选择性，设计解该问题的贪心算法，并分析其复杂度。 答： （1）递推式： C(i,j)={ 0 j=0 j/T[1] j>0且i=1 min 1≤k≤j/T[i] {k+C(i?1,j?k×T[i])} j>0且i≠1 （2）算法设计：根据（1）中的递推公式，计算C(i,j)时只可能会用到C(i-1,x)，其中x的取值区间为[1,j-1]。不会使用x>j的元素数值。假设一个n×L阶矩阵，只需要从左往右计算，每列从上往下计算C(i,j)，并使用一个规模为L的数组即可。 算法伪代码： Input：硬币面值数组T[1:n]，待找钱数L Output：使用硬币的最小个数x的数组 GET-CHANGE(T,L)
1 n←length(T) 2 create array x[1:L] 3 for j←1 to L 4 d o x[j]←j/T[1] 5 for i←2 to n 6 do for j←L to 1 7 do for k←1 to j/T[i] 8 do if x[j-k*x]+k
相关主题
文本预览