最優(yōu)化多目標(biāo)規(guī)劃動(dòng)態(tài)規(guī)劃chr5~6

1、 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 令hi(xi=hi(xi, = maxgi(xi,yi yi yi0 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 這是一個(gè)一維分配問題，可用對(duì)一維的方 法求解，這里由于是參數(shù)，因此，最優(yōu) 解xi*是參數(shù)的函數(shù)，相應(yīng)的yi*也是的 函數(shù)，即xi=xi*(, yi=yi*(為其解。如 y (l =b 為原問題的最 果 ，則可證明xi*, y åi* 優(yōu)解；如果 ，可調(diào)整的值(利用插 值法逐漸確定 ，直到滿足 為止。 å y (l ¹ b n i =1 * i ( 為了使此式有意義 , 可設(shè) lim 于是問題變?yōu)?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 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 (2逐次逼近法 這是另一種降維方法，先保持一個(gè)變量不 變，對(duì)另一個(gè)變量實(shí)現(xiàn)最優(yōu)化，然后交替 地固定變量，以迭代的形式反復(fù)進(jìn)行，直 到獲得某種要求為止。 逐次逼近法 先設(shè)x(0=x1(0, x2(0,xn(0為滿足 x1(0+x2(0+xn(0=a的一個(gè)可行解，固定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 的解，設(shè)這個(gè)解為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 的解，設(shè)其解為x(1=x1(1, x2(1,xn(1， 逐次逼近法 再固定x為x(1,對(duì)y求解，這樣依次輪換下去 得到一系列的解x(k,y(k，(k=0,1,2, 顯然，函數(shù)值g1(x1(k,y1(k +g2(x2(k,y2(k +gn(xn(k,yn(k是單調(diào)上升的，通常它收 斂到一個(gè)局部最優(yōu)解，因此，在實(shí)際計(jì)算 中，可選擇

4、幾個(gè)初始點(diǎn)x(0進(jìn)行計(jì)算，從中 選出一個(gè)最好的解作為近似最優(yōu)解。 21 5.3排序問題 設(shè)有n個(gè)工件需要在機(jī)床A、B上加工，每個(gè) 工件都必須經(jīng)過先A而后B的兩道加工工 序，工件i(1in在A、B上的加工時(shí)間分 別設(shè)為ai, bi, 問應(yīng)如何在兩機(jī)床上安排各工 件的加工順序，使在機(jī)床A上加工第一個(gè)工 件開始到在機(jī)床B上將最后一個(gè)工件加工完 為止，所用的加工時(shí)間最少？ 排序問題 當(dāng)機(jī)床B上的加工順序與機(jī)床A不同時(shí)，意 味著在A上加工完畢的某些工件不能在B上 立即加工，而需等到另一個(gè)或一些工件加 工完畢之后才能加工，這樣使機(jī)床B的等待 加工時(shí)間加長，從而使總的加工時(shí)間加長 了?？梢宰C明：最優(yōu)加工順序

5、可以在A、B 上加工順序相同時(shí)實(shí)現(xiàn)。因此，只考慮在A、 B上具有相同的加工順序。 排序問題 當(dāng)加工順序取定之后，工件在A上加工時(shí)沒 有等待時(shí)間，而在B上常常等待，且第i個(gè)工 件在A上加工完畢以后，在B上要經(jīng)過若干 時(shí)間才能加工完，因此對(duì)同一個(gè)工件來 說，在A、B上總是出現(xiàn)加工完畢的時(shí)間差。 排序問題 X：表示在A上等待加工的按取定順序排列的工件 集合； x：以x表示不屬于X的在A上最后加工完的工件； t：表示在A上加工完x的時(shí)刻到B上加工完x所延 續(xù)的時(shí)間； 在A上加工完一個(gè)工件之后就有(X, t與之對(duì)應(yīng)， 以(X, t作為描述A、B在加工過程中的狀態(tài)變量。 排序問題 令f(X, t為由狀態(tài)(

6、X, t出發(fā)，對(duì)未加工的工件采 取最優(yōu)加工順序后，將X中所有工件加工完所需 時(shí)間。 f(X, t, i為由狀態(tài)(X, t出發(fā)，在A上加工工件i，然 后再對(duì)以后的加工工件采取最優(yōu)加工順序后，把 X中所有工件加工完所需時(shí)間。 f(X, t, i, j為由狀態(tài)(X, t出發(fā)，在A上相繼加工工 件i與j后，對(duì)以后的加工工件采取最優(yōu)加工順序 后，把X中所有工件加工完所需時(shí)間。 排序問題 針對(duì)t與ai之間的關(guān)系，有下圖 A 當(dāng) tai時(shí) B 當(dāng) t>ai時(shí) 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 當(dāng)t > a i 當(dāng)t £ a i 排序問題 由定義，進(jìn)一步可得 f(X,t,i,j=ai +aj + fX/i, j, Zij(t 這里是在機(jī)床A上從X出發(fā)相繼加工工件i, j, 并從它將j加工完的時(shí)刻算起至在上相繼 加工工件i, j并將工件j加工完所延續(xù)的時(shí) 間，故(X/i, j, Zij(t是在加工i, j后所形 成的新狀態(tài)。 記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對(duì)調(diào)，可得 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、的單調(diào)增函數(shù)，故當(dāng)Zij(tZji(t 時(shí)，有f(X, t, i, jf(X,t,j,i，因此不管t為何值， 當(dāng)Zij(tZji(t時(shí)，工件i放在工件j之前加工可以 縮短總的加工時(shí)間。由Zij(t的表達(dá)式可知，當(dāng) max (bi+ bj-aj , bjmax (bi+ bj-ai, bi 成立時(shí)，有 Zij(tZji(t 將上式兩邊同時(shí)減去bi與bj，得 排序問題 max (-aj , -bimax (-ai, -bj 即等價(jià)于 min (ai, bjmin (aj , bi 這個(gè)條件就是工件i應(yīng)該排在工件j之前的條 件，即對(duì)于從頭到尾的最優(yōu)排序而言，它 有所有前后相鄰的兩個(gè)工件所組成的對(duì)，

10、都必須滿足上述條件，由此，得到下面的 最優(yōu)排序規(guī)則： 排序問題 最優(yōu)排序規(guī)則： (1寫出工件加工時(shí)間的工時(shí)矩陣 æ a1 a 2 L a n ö M =ç çb b L b ÷ ÷ 2 nø è 1 (2在M中找最小者，若它在上行，則將相應(yīng)的 工件排在最前位置；若它在下行，則將相應(yīng)的 工件排在最后位置。 (3將排定位置的工件所對(duì)應(yīng)的列從M中劃掉， 然后對(duì)余下的工件重復(fù)(2直至所有的工件被安 排完為止。 以上最優(yōu)排序規(guī)則是Johnson在1954年提出的。 23 排序問題 例 有6個(gè)工全需要在設(shè)備A和B上加工，先 在A上加工，再在B上加工，加工時(shí)間如下 表： 設(shè)備 零件 1 2 3 4 5 6 A 3 12 5 2 9 11 B 8 10 9 6 3 1 求其最優(yōu)加工順序，使總的加工時(shí)間最短。 排序問題 解工件的加工工時(shí)矩陣為 æ 3 12 5 2 9 11 ö M =ç ç 8 10 9 6 3 1 ÷ ÷ è