《运筹学》胡运权清华版-7-04动态规划应用举例.ppt
第四节 动态规划应用举例,离散型资源分配问题背包问题生产与存储问题加工排序问题,设pi(xi)表示分配给第i队xi个科学家后失败的概率,某科研项目有三个小组用不同的方法独立进行研究。他们失败的概率分别为0.40,0.60和0.80。为了减少三个小组都失败的可能性。现决定暂派两名科学家参加这一科研项目。把这两人分配到各组后，各小组失败的概率如下表，问应如何分派这两名科学家以使三个小组都失败的概率最小？,没有明显的函数表达式,离散型资源分配问题,建模（逆序解法）3个阶段（按小组）；状态变量sk：第k阶段初可用于分配的科学家数；决策变量xk：第k阶段分配给第k个小组的科学家数；状态转移方程：sk+1=sk-xk 允许决策集合 Dk(sk)=xk0 xksk,xk为整数阶段指标函数 pk(xk)过程指标函数,基本方程,第k阶段初拥有科学家数是sk，应如何分配给k3组，使得失败概率最小？,逆序求解 k3,k=2,逆序求解 k3,k=2,逆序求解 k3,k=2,逆序求解 k3,k=2,逆序求解 k3,k=2,k=2,逆序求解 k3,k=1,k=1,k=1,由状态转移方程顺推最优决策：x*11=s2=s1-x*11 查k2表，得x*20=s3=s2-x*21 查k3表，得x*31所以最优分配方案（1，0，1），最优值0.06,x*11，x*20，x*31所以最优分配方案（1，0，1），最优值0.06,推广1：二维（或多维）资源分配问题,推广2：非线性整数规划问题，如：,一位旅行者携带背包去登山，背包重量限度为akg，现有n种物品可供他选择装入背包，第i种重量为aikg，其价值是携带数量xi的函数ci（xi），问应如何选择携带各种物品的件数，使总价值最大？,背包问题,建模（逆序解法）n个阶段（按物品种类，一个阶段装一种）；状态变量sk：第k阶段初允许装入的剩余物品总重量；决策变量xk：装入的第k种物品件数；状态转移方程：sk+1=sk-akxk 允许决策集合 Dk(sk)=xk0 xksk/ak,xk为整数过程指标函数,基本方程,第k阶段初允许载重量为sk，应如何装入第kn种物品，使剩余物品总价值最大？,例7 有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量以及单位价值如下表，问应如何选择携带各种物品的件数，使总价值最大？,状态转移方程：sk+1=sk-akxk s2=s1-3x1 0 x1s1/3,x1为整数 s3=s2-4x2 0 x2s2/4,x2为整数 s4=s3-5x3 0 x3s3/5,x3为整数阶段指标函数 c1(x1)=4x1,c2(x2)=5x2,c3(x3)=6x3,基本方程,逆序求解(初始条件已知s110),s110,s2s1-3x1,s3s2-4x2,s4 s3-5x3,k3（装5t重的物品）能装多少装多少,k3（装5t重的物品）能装多少装多少,k2（装4t重的物品）,k2（装4t重的物品）,k2（装4t重的物品）,k2（装4t重的物品）,k2（装4t重的物品）,k=1,装3t物品，最多装3件,由状态转移方程顺推最优决策 x*12=s2 s1-3x1=10-6=4=x*21=s3 s2-4x2=0=x*30 最优值13,最优决策 x*12，x*21，x*30 最优值13,生产与存贮问题,例8 某厂为新一年制定前四个月的生产计划，生产费用为每月库存费用 E(j)=0.5j同时年初和4月底皆无库存，每月产品的需求量分别为2、3、2、4单位，该厂库存容量为3单位，最大生产能力为6单位，试确定费用最小的生产计划。,解：按4个月的顺序分为4个阶段。sk：第k阶段初的库存量；uk：第k阶段的生产量；gk：第k阶段的需求量（已知）。状态转移方程：sk1 sk+uk-gk 阶段指标 vk(sk,uk)=C(uk)+E(sk),基本方程：,逆序求解：,k=4 因要求4月底的库存量为0，即s5=0,有 s5 s4+u4 4 0=u4 4-s4,k=3 允许决策分析 s3 只能是0，1，2，3单位；现考虑产量 u3 限制:（1）变量非负 u3 0（2）满足需求限制（本月需求 g32）=s3+u3 2 或 u3 2-s3（3）生产能力限制 u3 6（4）保证期末库存量为0=s3+u3 g3g4 或 u3 g3g4-s36-s3（5）下月初库存量限制=s4s3+u3-g3 3 或 u3 3g3-s3 5-s3,max(0,2-s3)u3 min(6,6-s3,5-s3),需求：2，3，2，4,max(0,2-s3)u3 min(6,6-s3,5-s3),K=3,k=2 允许决策分析 s2 只能是0，1，2，3单位；现考虑产量 u2 限制:（1）变量非负 u2 0（2）满足需求限制（本月需求 g23）=s2+u2 3 或 u2 3-s2（3）生产能力限制 u2 6（4）保证期末库存量为0=s2+u2 g2 g3g4 或 u2 g2 g3g4 s29-s2（5）下月初库存量限制=s3 s2+u2 g2 3 或 u2 3g2-s2 6-s2,max(0,3-s2)u2min(6,6-s2,9-s2),需求：2，3，2，4,k=2,max(0,3-s2)u2min(6,6-s2,9-s2),k=1 允许决策分析 由已知s1 只能是0；现考虑产量 u1 限制:（1）变量非负 u1 0（2）满足需求限制（本月需求 g12）=s1+u1 2 或 u1 2（3）生产能力限制 u1 6（4）保证期末库存量为0=s1+u1 g1 g2 g3g4 或 u1 11（5）下月初库存量限制=s2 s1+u1 g1 3 或 u1 3g1-s1 5,max(0,2)u1min(6,11,5)或2 u15,需求：2，3，2，4,k=1,从上述计算可知，最优生产计划为：1月份生产2单位，2月份生产5单位，3月份不生产，4月份生产4单位，总费用为21单位。,2 u15,设有n个工件需要在机床A、B上加工,每个工件都必须经过先A后B的两道加工工序，我们用一号码i(1=i=n)表示第i个工件，以ai，bi分别表示工件i在A、B上的加工时间，由于工序的不同，所用的时间也是不同的，因此，加工完这n个工件的总时间是排列顺序的函数。现在的问题是怎样安排加工顺序才使总时间最少?,加工排序问题,用(X,t)来描述状态,X表示在机床A上等待加工的工件集合,就是说,这是A已经把X以外的工件全加工完了,准备选择X中某个工件加工,t表示B还需时刻t才能把X以外的工件加工完.,在状态(X,t),决策集合是工件集合X,选定决策i属于X,就转入新的状态(Xi,zi(t),并获得效益.用最优化原理得到 这是一个递推公式,有X=0开始,直到X=n.,最优排序法,1:找出a1,a2,an,b1,b2,bn中的最小数.2:若最小者为ai,则将工件i排在第一位,并从工件集合中去掉这个工件.3:若最小者为bj,则将工件j排在最后一位,并从工件集合中去掉这个工件.4:对剩下的工件重复上述手续,直到工件集合为空集合时停止.,例：给定5个工件,在A,B上的加工时间如下表所示.用上述方法,很容易得到最优化顺序是1 3 5 4 2,第四节 结束,
