1、 1、设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线？
把a看作终点，该问题可分为4个阶段。
fk(sk)表示从第k阶段点sk到终点a的最短距离。
f4(b1)=20，f4(b2)=40，f4(b3)=30
f3(c1)=min[d3(c1, b1)+ f4(b1), d3(c1, b2)+ f4(b2), d3(c1, b3)+ f4(b3) ]70，u3(c1)= b2 或b3
f3(c2)=40 ，u3(c2)= b3
f3(c3)=80 ，u3(c3)= b1或 b2 或b3
f2(d1)=80 ，u2(d1)= c1
f2(d2)=70 ，u2(d2)= c2
f1(e)=110 ，u1(e)= d1或d2
所以可以得到以下最短路线，e→d1→c1→b2 / b3→a
e→d2→c2→b3→a
2、 习题4－2
解：1)将问题按地区分为三个阶段，三个地区的编号分别为；
2)设sk表示为分配给第k个地区到第n个地区的销售点数，xk表示为分配给第k个地区的销售点数，sk＋1＝sk－xk
pk(xk)表示为xk个销售点分到第k个地区所得的利润值。
fk(sk)表示为sk个销售点分配给第k个地区到第n个地区的最大利润值。
3)递推关系式：
fk(sk)＝max[ pk(xk)+ fk+1(sk－xk) ]k=3,2,1
f4(s4)＝0
4）从最后一个阶段开始向前逆推计算。
第三阶段：设将s3个销售点（s3＝0,1,2,3,4）全部分配给第三个地区时，最大利润值为：
f3(s3)＝max[p3(x3)] 其中x3＝s3＝0,1,2,3,4
表1第二阶段：
设将s2个销售点（s2＝0,1,2,3,4）分配给乙丙两个地区时，对每一个s2值，都有一种最优分配方案，使得最大盈利值为：
f2(s2)＝max[ p2(x2)+ f3(s2－x2) ]
其中，x2＝0,1,2,3,4
表2第一阶段：
设将s1个销售点（s1＝4）分配给三个地区时，则最大利润值为：
f1(s1)＝max[ p1(x1)+ f2(4－x1) ]
其中，x1＝0,1,2,3,4
表3然后按计算**的顺序反推，可知最优分配方案有两个：最大总利润为53
1）由x1*＝2，x2*＝1，x3*＝1。即得第一个地区分得2个销售点，第二个地区分得1个销售点，第三个地区分得1个销售点。
2）由x1*＝3，x2*＝1，x3*＝0。即得第一个地区分得3个销售点，第二个地区分得1个销售点，第三个地区分得0个销售点。
3、 某施工单位有500台挖掘设备，在超负荷施工情况下，年产值为20万元/台，但其完好率仅为0.4，在正常负荷下，年产值为15万元/台，完好率为0.8。
在四年内合理安排两种不同负荷下施工的挖掘设备数量，使第四年年末仍有160台设备保持完好，并使产值最高。试求出四年内使得产值最高的施工方案和产值数。
解：1）该问题分成四个阶段，k表示年度，k＝1,2,3,4
2）设sk表示为分配给第k年初拥有的完好挖掘设备数量，uk表示为第k年初分配在超负荷下施工的挖掘设备数量，dk (sk)=
sk－uk表示为第k年初分配在正常负荷下施工的挖掘设备数量。
状态转移方程：sk＋1＝0.4uk +0.8(sk－uk)， s1＝500台
3）设vk(sk,uk)为第k年度的产量，则。
vk＝20uk +15(sk－uk)
故指标函数为v1,4=
fk(sk)表示由资源量sk出发，从第k年开始到第4年结束时所生产的产量最大。
4）递推关系式：fk(sk)＝max k=1,2,3,4
5）从第4阶段开始，向前逆推计算。
当k＝4时，s5=160, 0.4u4 +0.8(s4－u4)=160 2s4-u4=400 u4=2s4-400
f4(s4)＝max
＝max=25s4-2000
当k＝3时，f3(s3)＝max
= max＝max
故得最大解u3*＝0
所以f3(s3)＝35 s3-2000
依次类推，可求得：
u2*＝0，f2(s2)＝43s2-2000
u1*＝0，f1(s1)＝49.4s1-2000
因为s1＝500台，故f1(s1)＝22700台
最优策略为u1*＝0，u2*＝0，u3*＝0，u4*＝112
已知s1＝500，s2＝0.4u1 *+0.8(s1－u1*)＝0.8s1＝400
s3＝0.4u2 *+0.8(s2－u2*)＝0.8s2＝320
s4＝0.4u3 *+0.8(s3－u3*)＝0.8s3＝256
u4=2s4-400=112 s4-u4=256-112=144
即前三年应把年初全部完好的挖掘设备投入正常负荷下施工，第四年应把年初112台全部完好的挖掘设备投入超负荷下施工，144台投入正常负荷下施工。这样最高产量为22700台。
4、 某电视机厂为生产电视机而需生产喇叭，生产以万只为单位。根据以往记录，一年的四个季度需要喇叭分别是3万、2万、3万、2万只。设每万只存放在仓库内一个季度的存储费为0.
2万元，每生产一批的装配费为2万元，每万只的生产成本费为1万元。问应该怎样安排四个季度的生产，才能使总的费用最小？
再生产点性质，c(1,1)=c(3)+h(0)=5 c(1,2)=c(5)+h(2)=7.4
c(1,3)=c(8)+h(5)+h(3)=11.6
c(1,4)=c(10)+h(7)+h(5)+h(2)=14.8
c(2,2)=c(2)+h(0)=4 c(2,3)=c(5)+h(3)=7.6
c(2,4)=c(7)+h(5)+h(2)=10.4
c(3,3)=c(3)+h(0)=5 c(3,4)=c(5)+h(2)=7.4
c(4,4)=c(2)+h(0)=4
f0=0 f1=f0+ c(1,1)=5 j(1)=1
f2=min=min=7.4 j(2)=1
f3= min
min=11.6 j(3)=1
f4= min
min=14.8 j(4)=1,3
当j(4)=1，x1=d1+d2+d3+d4=10,x2=0,x3=0,x4=0
当j(4)=3,x3=d3+d4=5,x4=0,x1=d1+d2=5,x2=0。
5、 某工厂生产三种产品，各产品重量与利润关系如下表所示，现将此三种产品运往市场**，运输能力总重量不超过6吨。问如何安排运输使总利润最大。
解：6、某工厂在一年进行了a、b、c三种新产品试制，由于资金不足，估计在年内这三种新产品研制不成功的概率分别为.80，因而都研制不成功的概率为0.
4×0.6×0.8=为了促进三种新产品的研制，决定增援2万元的研制费，并要资金集中使用，以万元为单位进行分配。
其增援研制费与新产品不成功的概率如下表所示。试问如何分配费用，使这三秤新产品都研制不成功的概率为最小。
解：1) （1分）将问题按产品a、b、c分为三个阶段，k；
2) （6分）设sk表示第k阶段可分配给第k个产品到第n个产品的研制费，s1＝2
xk设为决策变量，表示第k阶段分配给第k个产品的研制费。
状态转移方程为sk＋1＝sk－xk
允许决策集合：dk(sk)＝
pk(xk)表示为第k个产品失败的概率。
fk(sk)表示为sk万元研制费分配给第k个产品到第n个产品的最小的失败概率。
3)（4分）递推关系式：
fk(sk)＝min[ pk(xk)×fk+1(sk－xk) ]k=3,2,1
边界条件： f4(s4)＝1
4）（11分）从最后一个阶段开始向前逆推计算。
第三阶段：设将s3万元研制费（s3＝0,1,2）全部分配给c产品时，最小的失败概率为：
f3(s3)＝min[p3(x3)] 其中x3＝s3＝0,1,2
x3*表示使得f3(s3)为最大值时的最优决策。
第二阶段：设将s2万元研制费（s2＝0,1,2）分配给b、c产品时，最小的失败概率为：
f2(s2)＝min[ p2(x2)×f3(s2－x2) ]
其中，x2＝0,1,2
第一阶段：设将s1万元研制费（s1＝2）分配给三个产品时，最小的失败概率为：
f1(s1)＝min[ p1(x1)×f2(s1－x1) ]
其中，x1＝0,1,2
5）即分配给a产品1万元，b产品0万元，c产品1万元，可使三个小组都失败的概率减小到0.060。
动态规划经典教程
引言 本人在做过一些题目后对dp有些感想，就写了这个总结 第一节动态规划基本概念。一，动态规划三要素 阶段，状态，决策。他们的概念到处都是，我就不多说了，我只说说我对他们的理解 如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操...
数学建模8 动态规划和目标规划
一 动态规划。1.动态规划是求解决策过程最优化的数学方法，主要用于求解以时间划分阶段的动态过程的优化问题。但是一些与时间无关的静态规划 如线性规划 非线性规划 只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。2.基本概念 基本方程 1 阶段。2 状态。3 决策。4 策...
运筹学实验动态规划
实验二用matlab解决动态规划问题。问题 有一部货车每天沿着公路给四个售货店卸下6箱货物，如果各零售店 该货物所得利润如下表所示，试求在各零售店卸下几箱货物，能使获得总利润最大？其值为多少？解 1 将问题按售货店分为四个阶段。2 设sk表示为分配给第k个售货店到第n个工厂的货物数，xk设为决策变量...