最优化多目标规划动态规划chr5~6

1、 动态规划的解法及应用举例 令hi(xi=hi(xi, = maxgi(xi,yi yi yi0 动态规划的解法及应用举例 这是一个一维分配问题，可用对一维的方 法求解，这里由于是参数，因此，最优 解xi*是参数的函数，相应的yi*也是的 函数，即xi=xi*(, yi=yi*(为其解。如 y (l =b 为原问题的最 果 ，则可证明xi*, y åi* 优解；如果 ，可调整的值(利用插 值法逐渐确定 ，直到满足 为止。 å y (l ¹ b n i =1 * i ( 为了使此式有意义 , 可设 lim 于是问题变为 maxh1(x1+h1(x1+hn(xn 满足

2、条件 x1+x2+xn=a xi0, i=1,2,n yi ® ¥ gi ( xi , yi = 0 yi n i =1 * i å y (l = b i =1 * i n 动态规划的解法及应用举例 (2逐次逼近法 这是另一种降维方法，先保持一个变量不 变，对另一个变量实现最优化，然后交替 地固定变量，以迭代的形式反复进行，直 到获得某种要求为止。 逐次逼近法 先设x(0=x1(0, x2(0,xn(0为满足 x1(0+x2(0+xn(0=a的一个可行解，固定x在x(0， 求 maxg1(x1(0,y1 +g2(x2(0,y2 +gn(xn(0,yn 满足条件 y

3、1+y2+yn=b yi0 i=1,2,n 的解，设这个解为y(0=y1(0, y2(0,yn(0 逐次逼近法 然后再固定y为y(0, 求 maxg1(x1,y1(0 +g2(x2,y2(0 +gn(xn,yn(0 满足条件 x1+x2+xn=a xi0 i=1,2,n 的解，设其解为x(1=x1(1, x2(1,xn(1， 逐次逼近法 再固定x为x(1,对y求解，这样依次轮换下去 得到一系列的解x(k,y(k，(k=0,1,2, 显然，函数值g1(x1(k,y1(k +g2(x2(k,y2(k +gn(xn(k,yn(k是单调上升的，通常它收 敛到一个局部最优解，因此，在实际计算 中，可选择

4、几个初始点x(0进行计算，从中 选出一个最好的解作为近似最优解。 21 5.3排序问题 设有n个工件需要在机床A、B上加工，每个 工件都必须经过先A而后B的两道加工工 序，工件i(1in在A、B上的加工时间分 别设为ai, bi, 问应如何在两机床上安排各工 件的加工顺序，使在机床A上加工第一个工 件开始到在机床B上将最后一个工件加工完 为止，所用的加工时间最少？ 排序问题 当机床B上的加工顺序与机床A不同时，意 味着在A上加工完毕的某些工件不能在B上 立即加工，而需等到另一个或一些工件加 工完毕之后才能加工，这样使机床B的等待 加工时间加长，从而使总的加工时间加长 了。可以证明：最优加工顺序

5、可以在A、B 上加工顺序相同时实现。因此，只考虑在A、 B上具有相同的加工顺序。 排序问题 当加工顺序取定之后，工件在A上加工时没 有等待时间，而在B上常常等待，且第i个工 件在A上加工完毕以后，在B上要经过若干 时间才能加工完，因此对同一个工件来 说，在A、B上总是出现加工完毕的时间差。 排序问题 X：表示在A上等待加工的按取定顺序排列的工件 集合； x：以x表示不属于X的在A上最后加工完的工件； t：表示在A上加工完x的时刻到B上加工完x所延 续的时间； 在A上加工完一个工件之后就有(X, t与之对应， 以(X, t作为描述A、B在加工过程中的状态变量。 排序问题 令f(X, t为由状态(

6、X, t出发，对未加工的工件采 取最优加工顺序后，将X中所有工件加工完所需 时间。 f(X, t, i为由状态(X, t出发，在A上加工工件i，然 后再对以后的加工工件采取最优加工顺序后，把 X中所有工件加工完所需时间。 f(X, t, i, j为由状态(X, t出发，在A上相继加工工 件i与j后，对以后的加工工件采取最优加工顺序 后，把X中所有工件加工完所需时间。 排序问题 针对t与ai之间的关系，有下图 A 当 tai时 B 当 t>ai时 t ai 工件i bi t 工件i-1 工件i-1 bi t-ai+bi 22 排序问题 得到 ìa i + f ( X / i ,

7、t - a i + bi f ( X , t, i = í îa i + f ( X / i , bi 当t > a i 当t £ a i 排序问题 由定义，进一步可得 f(X,t,i,j=ai +aj + fX/i, j, Zij(t 这里是在机床A上从X出发相继加工工件i, j, 并从它将j加工完的时刻算起至在上相继 加工工件i, j并将工件j加工完所延续的时 间，故(X/i, j, Zij(t是在加工i, j后所形 成的新状态。 记Zi(t=max (t-ai, 0 + bi 则上式可写为 f(X,t,i=ai + fX/i, Zi(t 排序问题 仿照

8、Zi(t的定义，以X/i, j代替X/i，以Zi(t代替t, aj代替ai，bj代替bi，则可得 Zij(t=max (Zi(t-aj, 0 + bj 于是可得 Zij(t=max (max (t-ai, 0 + bi-aj, 0 + bj =max (max (t-ai-aj+ bi, bi-aj , 0 + bj =max (t-ai-aj+ bi+ bj, bi+ bj-aj , bj 将i, j对调，可得 f(X,t,j,i=ai +aj + fX/i, j, Zji(t Zji(t=max (t-ai-aj+ bi+ bj, bi+ bj-ai, bi 排序问题 由于f(X, t为t

9、的单调增函数，故当Zij(tZji(t 时，有f(X, t, i, jf(X,t,j,i，因此不管t为何值， 当Zij(tZji(t时，工件i放在工件j之前加工可以 缩短总的加工时间。由Zij(t的表达式可知，当 max (bi+ bj-aj , bjmax (bi+ bj-ai, bi 成立时，有 Zij(tZji(t 将上式两边同时减去bi与bj，得 排序问题 max (-aj , -bimax (-ai, -bj 即等价于 min (ai, bjmin (aj , bi 这个条件就是工件i应该排在工件j之前的条 件，即对于从头到尾的最优排序而言，它 有所有前后相邻的两个工件所组成的对，

10、都必须满足上述条件，由此，得到下面的 最优排序规则： 排序问题 最优排序规则： (1写出工件加工时间的工时矩阵 æ a1 a 2 L a n ö M =ç çb b L b ÷ ÷ 2 nø è 1 (2在M中找最小者，若它在上行，则将相应的 工件排在最前位置；若它在下行，则将相应的 工件排在最后位置。 (3将排定位置的工件所对应的列从M中划掉， 然后对余下的工件重复(2直至所有的工件被安 排完为止。 以上最优排序规则是Johnson在1954年提出的。 23 排序问题 例 有6个工全需要在设备A和B上加工，先 在A上加工，再在B上加工，加工时间如下 表： 设备 零件 1 2 3 4 5 6 A 3 12 5 2 9 11 B 8 10 9 6 3 1 求其最优加工顺序，使总的加工时间最短。 排序问题 解工件的加工工时矩阵为 æ 3 12 5 2 9 11 ö M =ç ç 8 10 9 6 3 1 ÷ ÷ è