试确定上述各目标的最优调运方案。 7．已知目标规划问题
???minz?P1d1??P2d2?P35d3?3d4?P4d1?
??（1）分别用图解法和单纯形法求解；
?x1?2x2?d1??d1??6???x?2x?d?d?01222??st.?x1?2x2?d3??d3??4???x2?d4?d4?2?????x1?0,x2?0,di,di?0;i?1,2,3,4
（2）分析目标函数分别变为①，②两种情况时（②中分析?1,?2的比例变动）解的变
化。
①minz?P1d1?P2d2?P3d1?P45d3?3d4，
②minz?P1d1?P2d2?P3?1d3??2d4?P4d1。
1．设某厂有同种机器100台，用这种机器可以做甲、乙两种工作。根据以往的经验可知，用该种机器做甲种工作一季度将损坏机器的1/3，所得利润为每台10000元，做乙种工作一季度将损坏机器的1/10，所得利润为每台7000元。问如何分配这100台机器做甲乙两种工作使工作一年后所获得的总利润最大。 解：根据季度将该动态规划问题划分为四个阶段
设Sk为第k季度开始时拥有的完好的机器数量（k=1,2,3,4）,决策变量uk表示第k季度做甲种工作的机器数量，则（Sk-uk）表示第k季度做乙种工作的机器数量
??????????????状态转移方程：
Sk?1?（1?1/3）uk?(1?1/10)(Sk?uk)?97Sk?uk1030
uk?7000(Sk?uk)?7000Sk?3000uk 第k阶段的利润为 10000设k子过程指标最优值函数为fk(Sk) 则 f(Sk)=0?uk?Sk??k?max(7000Sk?3000uk?fk*?1(Sk?1)) k=4,3,2,1
?k=4时，由于f5(S5)?0，则f4(S4)=0?u4?S4max(7000S4?3000u4)?*u?S10000S,uf(S)4时取到最大值，444?S4 4= 当4k=3时， 当
f3*(S3)?max(7000S3?3000u3?f4*(S4))?max(18000S3?0?u3?S3a?u3?S32000u3)3
f2*(S2)?max(7000S2?3000u2?f3*(S3))?max(16800S2?(1200?0?u2?S2a?u2?S21400)u3)9时取
到最大值，
f3?(S3)?(18000?2000)S33
k=2时
f2*(S2)?max(7000S2?3000u2?f3*(S3))?max(16800S2?(1200?0?u2?S2a?u2?S21400)u2)9
当u?0时有最大值，k=1时
*2f2?(S2)?(15600?1400)S29
f1*(S1)?max(7000S1?3000u1?f2*(S2))?max(21800S1?(0?u1?S1a?u1?S1980?640)u1)27
当u?0时有最大值，
***1f1?(S1)?(20540?**980)S127
,u4?54 故最优策略集为u1?u2?0,u3?81
2．某工厂生产三种产品，运送各种产品的重量与利润关系如下表所示。现将三种产品运往市场销售。运输能力总量不超过10吨，问如何安排运输使得总利润最大？
表10-12 运送各种产品的重量与利润关系
种类 1 2 3 重量（吨/件） 2 3 4 利润（元/件） 100 140 180 解：将该问题以产品种类数为依据划分为三个阶段 设Sk为第k阶段至第3阶段运送的产品重量，是第k阶段的状态变量，fk(Sk)为第k阶段至第3阶段运送产品的总利润，是k子过程指标函数
设第k种产品质量为mk，利润为ck，则uk为在第k阶段运送的产品数，则ckuk为阶段指标函数。建立如下数学模型：
?fk*(Sk)?max(ckuk?fk*?1(Sk?1))?k?1,2,3uk??Sk?1?Sk?mkuk?10/mk],Jk)?0?uk?min([??f4(S4)?0,S4?0,S1?10
Jk为阶段k中的产品总数
k=3时，S3?0,1,,?,10,u3?[S3/4],u3?0,1,2
u3 S3 f3(S3)?c3u3 0 1 2 *u3 f3*(S3) 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 180 180 180 180 360 360 360 0 0 0 0 180 180 180 180 360 360 360 0 0 0 0 1 1 1 1 2 2 2 3 k=2时，S2?0,1,,?,10,u2?[S2/3],u2?0,1,2， u3 S2 f2(S2)?c2u2?f3*(S3) 0 1 2 3 *u2 f2*(S2) 0 1 2 3 4 5 6 7 8 9 0+0 0+0 0+0 0+0 0+180 0+180 0+180 0+180 0+360 0+360 140+0 140+0 140+0 140+180 140+180 140+180 280+0 280+0 280+0 280+0 420+0 0 0 0 140 180 180 280 320 360 420 0 0 0 1 0 0 2 1 0 3 10 0+360 140+180 280+180 420+0 460 2 k=1时，S1=10，u1=0，1，2，3，4，5 S1 u1 0 0+460 1 f1(S1)?c1u1?f2*(S2) 2 3 4 5 500+0 *f1*(S1) u1 10 100+360 200+280 300+180 400+0 500 5 ***u?5,u?u23?0，收益为500 该问题的最优方案为1
3．某公司打算在城东、城南、城西、新设4个连锁经营超市，根据前期的市场调查，在不同地区设置不同数量的超市，每月的营业利润不同，具体如下表。问连锁经营超市如何分布，才能使总利润最大？
表10-13 不同地区不同数量的超市月利润
城东 城南 城西 1 16 12 10 2 20 15 13 3 30 20 16 4 32 24 17 解：将问题按地区分为三个阶段，分别编号为1，2，3，设Sk表示在第k地区至第三地区设置超市的数量，过程指标函数记为fk(sk)；Xk表示在第k地区设置超市的数量，。阶段指标函数记为fk(sk,xk)。
当k=3时 s3 0 1 2 3 x3 0 0 1 10 f3(s3,x3) 2 13 3 16 4 17 *f3(s3) *x3 0 10 13 16 17 *f2(s2) 0 1 2 3 4 *x2 4 当k=2时 0 2 s1 sx2 0 0+0 0+10 0+13 1 12+0 12+10 *f2(s2,x2)?f3(s3) 2 15+0 3 4 0 12 22 0 1 1 3 0+16 12+13 12+16 15+10 15+13 20+0 20+10 24+0 25 30 1，2 3 *x1 4 0+17 当k=1时 4 0+30 16+25 s 可知最优方案有两个：
*sx1 0 1 *f1(s1,x1)?f2(s2) f1*(s1) 4 32+0 42 2 20+22 3 30+12 2，3 ****（1）x1=2，x2=1，x3=1；（2）x1=3，x2=1，x3=0
*这两种方案都可以得到最高的利润42.
4．如下图所示为一给定的网络图。图中两点之间连线上的数字表示距离，用动态规划方法求解从A到E的最短路线。
3AB1413335C24C121B2253142D13D215EB33D3
图10-2 网络图
***f(D)?3,f(D)?1,f(D3)?5. 41424解：当k=4时，
当k=3时
*?d(C1,D1)?f4(D1)?2?3?5?????**f3(C1)?min?d(C1,D2)?f4(D2)?5?1?6???*d(C,D)?f(D)?3?5?81343????=5
*?d(C2,D1)?f4(D1)?1?3?4?????**f3(C2)?min?d(C2,D2)?f4(D2)?4?1?5??4??*d(C,D)?f(D)?2?5?72343???? *?d(B1,D1)?f4(D1)?4?3?7?????**f2(B1)?min?d(B1,C1)?f3(C1)?4?5?9??7??*d(B,C)?f(C)?2?5?7??1232??
*?d(B,C)?f(C1)?1?5?6???213*f2(B2)?min???6*??d(B2,C2)?f3(C2)?3?4?7??
当k=2时