第四五七章习题

1、1判断下列说法是否正确（1）在动态规划模型中，问题的阶段数等于问题中子问题的数目。（2）动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性。（3）对一个动态规划问题，应用顺推或逆推求解可能会得出不同的最优解。（4）动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段 的决策问题。（5）一个线性规划问题若转化为动态规划方法求解时，应严格按变量的下标顺序来划分阶段，如将决定x1值作为第一阶段，决定x2的值作为第二阶段。（6）整数规划解的目标函数值一般优于其相应的线性规划问题解的目标函数值。（7）用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是

2、该问题目标函数值的下界。（8）用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。（9）指派问题可用表上作业法求解。（10）求解0-1规划的隐枚举法是分枝定界法的特例。2. 用标号法计算下图从A到E的最短路线及其长度。A1B1B2B3C1C2D1D2D3E32144333153253412315315547688最短路为：A1 B2 C1 D1 E 最短路长为：83. 写出下面问题的动态规划的状态集合、允许决策集合、状态转移方程、基本方程。nicxbxastxgziiniiiniii, 2 , 10.)(max11状态集合：允许决策集合：状态转移方程：基本方程：kkkkx

3、ass1bsbssSkkk10|),min(0|)(kkkkkkkascxxsD0)(1 , 1,)()(max)(1111nnkkkkkDkxkksfnnksfxgsf4. 写出下面数学规划问题的动态规划模型，并用连续变量离散化方法求解。3 , 2 , 106.max32123221ixxxxstxxxzi解：其动态规划模型的基本方程为：1)(1 , 2 , 3)()()(44110maxsfksfxgsfkkkksxkkkk其中：kkkxsssxxgxxgxxg11211122223336)()()(3625169416543213s3f*3x3s第一步：k=32323,0(33max3)

4、(sxsfs第二步：k=2)()(332,0(22max2xfxsfs12345611 21 2 3 1 2 3 41 2 3 4 5 1 2 3 4 5 601 04 1 0 9 4 1 016 9 4 1 0 2516 9 4 1 001 04 2 0 9 8 3 016181240 253227165 00149 18 321111 2 22s2x3f32fg2f*2x第三步：k=1)()(22216,0(11maxxfxsf612345618363616003636231s1x21fg1f*1x结论：5. 某一求极大值的整数规划问题其松驰问题的最终单纯形表如下，写出割平面方程并将割平面

5、方程用x1,x2表示，并继续求解。79000c基bx1x2x3x4x59x23010017x132/71001/7-1/70 x311/70011/7-22/7检验数000-1-879000c基bx1x2x3x4x59x23010017x132/71001/7-1/70 x311/70011/7-22/7检验数000-1-80 x6-4/7000-1/7-6/70 x60001-1/774767154xx割平面约束为：790000c基bx1x2x3x4x5x69x230100107x141000-110 x310010-410 x4400016-7检验数0000-2-774767154xx割平面约束为：6. 建立下列整数规划的数学模型有8个分别由3个英文字符组成的字串：DBE DEG ADI FFD GHI BCD FDF BAI 称每个字符在英文字母表中的排列顺序数为该字符的位值（如A的位值为1，D的位值为4，G的位值为7等），问如何从中选取4个字串，使其中第1个字符的位值和不小于第2个字符的位值和，并使第3个字符的位值和达到最大。设否则的字串选编号为01jxj则问题的数学模型为：)8 , 2 , 1(1043864522