水資源系統(tǒng)分析-多目標(biāo)規(guī)劃

1、第五章第五章 多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃1 1問題的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型問題的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型 2目標(biāo)規(guī)劃的圖解分析法目標(biāo)規(guī)劃的圖解分析法 3用單純形法求解目標(biāo)規(guī)劃用單純形法求解目標(biāo)規(guī)劃 4求解目標(biāo)規(guī)劃的層次算法求解目標(biāo)規(guī)劃的層次算法 5應(yīng)用舉例應(yīng)用舉例1 1問題的提出與問題的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型 線性規(guī)劃、整數(shù)規(guī)劃和后面將要學(xué)習(xí)的動(dòng)態(tài)規(guī)劃都是線性規(guī)劃、整數(shù)規(guī)劃和后面將要學(xué)習(xí)的動(dòng)態(tài)規(guī)劃都是解決單個(gè)目標(biāo)函數(shù)在一組約束條件下的極值問題。但在許解決單個(gè)目標(biāo)函數(shù)在一組約束條件下的極值問題。但在許多實(shí)際問題中，在一組約束條件下，往往要求實(shí)現(xiàn)多個(gè)目多實(shí)際問題中，在一組約束條件下

2、，往往要求實(shí)現(xiàn)多個(gè)目標(biāo)。例如，在企業(yè)安排生產(chǎn)問題中，既要利潤高，又要消標(biāo)。例如，在企業(yè)安排生產(chǎn)問題中，既要利潤高，又要消耗低，還要考慮市場需求，等等。這些目標(biāo)的重要性各不耗低，還要考慮市場需求，等等。這些目標(biāo)的重要性各不相同，目標(biāo)規(guī)劃正是為了解決這類多目標(biāo)規(guī)劃問題而產(chǎn)生相同，目標(biāo)規(guī)劃正是為了解決這類多目標(biāo)規(guī)劃問題而產(chǎn)生的，它能把決策者的意愿反映到數(shù)學(xué)模型中去。的，它能把決策者的意愿反映到數(shù)學(xué)模型中去。 線性規(guī)劃問題的局限性：線性規(guī)劃問題的局限性： 1. 要求問題的解必須滿足全部約束條件，但實(shí)際問要求問題的解必須滿足全部約束條件，但實(shí)際問題中并非所有約束都需嚴(yán)格滿足；題中并非所有約束都需嚴(yán)格滿足

3、； 2. 只能處理單目標(biāo)的優(yōu)化問題，因此線性規(guī)劃模型只能處理單目標(biāo)的優(yōu)化問題，因此線性規(guī)劃模型認(rèn)為地將一些次要目標(biāo)轉(zhuǎn)為約束。而實(shí)際問題中，目標(biāo)和認(rèn)為地將一些次要目標(biāo)轉(zhuǎn)為約束。而實(shí)際問題中，目標(biāo)和約束可以互相轉(zhuǎn)化，處理時(shí)不一定嚴(yán)格區(qū)分；約束可以互相轉(zhuǎn)化，處理時(shí)不一定嚴(yán)格區(qū)分； 3. 線性規(guī)劃中各個(gè)約束條件都處于同等重要的地位，線性規(guī)劃中各個(gè)約束條件都處于同等重要的地位，但實(shí)際問題中，各目標(biāo)的重要性是有差別的；但實(shí)際問題中，各目標(biāo)的重要性是有差別的； 4. 線性規(guī)劃尋求最優(yōu)解，但很多實(shí)際問題中只需找線性規(guī)劃尋求最優(yōu)解，但很多實(shí)際問題中只需找出滿意解就可以了。出滿意解就可以了。 最佳生產(chǎn)計(jì)劃問題最佳

4、生產(chǎn)計(jì)劃問題 某工廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品的有關(guān)某工廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品的有關(guān)數(shù)據(jù)如下表所示。數(shù)據(jù)如下表所示。 工廠在作決策時(shí)，要實(shí)現(xiàn)如下的目標(biāo)：工廠在作決策時(shí)，要實(shí)現(xiàn)如下的目標(biāo)： 目標(biāo)目標(biāo)1 ：根據(jù)市場信息，產(chǎn)品甲的銷售量有下降的趨：根據(jù)市場信息，產(chǎn)品甲的銷售量有下降的趨勢，故考慮產(chǎn)品甲的產(chǎn)量不大于產(chǎn)品乙；勢，故考慮產(chǎn)品甲的產(chǎn)量不大于產(chǎn)品乙； 一、問題的提出 目標(biāo)目標(biāo)2 ：超過計(jì)劃供應(yīng)的原料時(shí)，需要高價(jià)采購，使：超過計(jì)劃供應(yīng)的原料時(shí)，需要高價(jià)采購，使成本增加，因而只采購計(jì)劃供應(yīng)的原料；成本增加，因而只采購計(jì)劃供應(yīng)的原料； 目標(biāo)目標(biāo)3 ：應(yīng)盡可能利用現(xiàn)有設(shè)備，但不希

5、望加班；：應(yīng)盡可能利用現(xiàn)有設(shè)備，但不希望加班； 目標(biāo)目標(biāo)4 ：應(yīng)盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)：應(yīng)盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)(56元元)。 這樣，在考慮產(chǎn)品生產(chǎn)決策時(shí)，不再是單純追求利潤這樣，在考慮產(chǎn)品生產(chǎn)決策時(shí)，不再是單純追求利潤最大，而是同時(shí)要考慮多個(gè)目標(biāo)，這樣的問題一般的線性最大，而是同時(shí)要考慮多個(gè)目標(biāo)，這樣的問題一般的線性規(guī)劃方法已無法解決，需引入一種新的數(shù)學(xué)模型規(guī)劃方法已無法解決，需引入一種新的數(shù)學(xué)模型目目標(biāo)規(guī)劃標(biāo)規(guī)劃。 二、目標(biāo)規(guī)劃模型的建立 1. 偏差變量偏差變量 用來表示實(shí)際值與目標(biāo)值之間的差異。用來表示實(shí)際值與目標(biāo)值之間的差異。 d + 超出目標(biāo)的差值，稱為超出目標(biāo)的差值，稱

6、為正偏差變量正偏差變量。 d - 未達(dá)到目標(biāo)的差值，稱為未達(dá)到目標(biāo)的差值，稱為負(fù)偏差變量負(fù)偏差變量。 因?qū)嶋H決策值不可能既超過目標(biāo)值又低于目標(biāo)值，故因?qū)嶋H決策值不可能既超過目標(biāo)值又低于目標(biāo)值，故最終結(jié)果中恒有最終結(jié)果中恒有 d + d - =0 (即兩者至少有一個(gè)為即兩者至少有一個(gè)為0)。 目標(biāo)規(guī)劃中，一般有多個(gè)目標(biāo)值，每個(gè)目標(biāo)值都相應(yīng)目標(biāo)規(guī)劃中，一般有多個(gè)目標(biāo)值，每個(gè)目標(biāo)值都相應(yīng)有一對偏差變量有一對偏差變量 。 2. 絕對約束和目標(biāo)約束絕對約束和目標(biāo)約束 絕對約束絕對約束是指必須嚴(yán)格滿足的等式約束或不等式是指必須嚴(yán)格滿足的等式約束或不等式約束；如線性規(guī)劃問題的所有約束條件，不能滿足這些條約束

7、；如線性規(guī)劃問題的所有約束條件，不能滿足這些條件的解稱為非可行解，所以絕對約束是件的解稱為非可行解，所以絕對約束是硬約束硬約束。 目標(biāo)約束目標(biāo)約束是目標(biāo)規(guī)劃所特有的一種約束，它把要是目標(biāo)規(guī)劃所特有的一種約束，它把要追求的目標(biāo)值作為右端常數(shù)項(xiàng)，在追求此目標(biāo)值時(shí)允許發(fā)追求的目標(biāo)值作為右端常數(shù)項(xiàng)，在追求此目標(biāo)值時(shí)允許發(fā)生正偏差和負(fù)偏差。因此，目標(biāo)約束是由決策變量，正、生正偏差和負(fù)偏差。因此，目標(biāo)約束是由決策變量，正、負(fù)偏差變量和要追求的目標(biāo)值組成的負(fù)偏差變量和要追求的目標(biāo)值組成的軟約束軟約束。 目標(biāo)約束不會(huì)不滿足，但可能偏差過大目標(biāo)約束不會(huì)不滿足，但可能偏差過大。 絕對約束絕對約束：問題中的目標(biāo)：問

8、題中的目標(biāo) 2，在原料供應(yīng)受嚴(yán)格限制，在原料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮，可寫成絕對約束為的基礎(chǔ)上考慮，可寫成絕對約束為11221 xx 假設(shè)問題中甲、乙兩產(chǎn)品的產(chǎn)量分別為假設(shè)問題中甲、乙兩產(chǎn)品的產(chǎn)量分別為 x1 和和 x2 。 目標(biāo)約束目標(biāo)約束：問題中的目標(biāo)：問題中的目標(biāo) 4 可寫成目標(biāo)約束為可寫成目標(biāo)約束為 112156108ddxx化為標(biāo)準(zhǔn)形式是：化為標(biāo)準(zhǔn)形式是： 561081121ddxx線性目標(biāo)約束的一般形式是：線性目標(biāo)約束的一般形式是： iiiibddXf nijijiTnxCXfxxxX121,其中：其中： 3. 優(yōu)先因子和權(quán)系數(shù)優(yōu)先因子和權(quán)系數(shù) 目標(biāo)規(guī)劃中，當(dāng)決策者要求實(shí)現(xiàn)多個(gè)目

9、標(biāo)時(shí)，這些目目標(biāo)規(guī)劃中，當(dāng)決策者要求實(shí)現(xiàn)多個(gè)目標(biāo)時(shí)，這些目標(biāo)之間是有主次區(qū)別的。標(biāo)之間是有主次區(qū)別的。 凡要求第一位達(dá)到的目標(biāo)，賦于凡要求第一位達(dá)到的目標(biāo)，賦于優(yōu)先因子優(yōu)先因子 p1，要求第，要求第二位達(dá)到的目標(biāo)，賦于優(yōu)先因子二位達(dá)到的目標(biāo)，賦于優(yōu)先因子 p2 并規(guī)定并規(guī)定 pk+1pk，表，表示示 pk 比比 pk+1 有絕對優(yōu)先權(quán)。因此，不同的優(yōu)先因子代表有絕對優(yōu)先權(quán)。因此，不同的優(yōu)先因子代表著不同的優(yōu)先等級(jí)。著不同的優(yōu)先等級(jí)。 若要區(qū)別具有相同優(yōu)先因子的多個(gè)目標(biāo)，可分別賦予若要區(qū)別具有相同優(yōu)先因子的多個(gè)目標(biāo)，可分別賦予它們不同的它們不同的權(quán)系數(shù)權(quán)系數(shù) k 。越重要的目標(biāo)，其權(quán)系數(shù)的值越。

10、越重要的目標(biāo)，其權(quán)系數(shù)的值越大。大。 在實(shí)現(xiàn)多個(gè)目標(biāo)時(shí)，首先保證在實(shí)現(xiàn)多個(gè)目標(biāo)時(shí)，首先保證 p1 級(jí)目標(biāo)的實(shí)現(xiàn)，這級(jí)目標(biāo)的實(shí)現(xiàn)，這時(shí)可不考慮其它級(jí)目標(biāo)，而時(shí)可不考慮其它級(jí)目標(biāo)，而 p2 級(jí)目標(biāo)是在保證級(jí)目標(biāo)是在保證 p1 級(jí)目標(biāo)級(jí)目標(biāo)值不變的前提下考慮的，以此類推。值不變的前提下考慮的，以此類推。 4. 目標(biāo)函數(shù)目標(biāo)函數(shù) 目標(biāo)規(guī)劃的目標(biāo)函數(shù)是由各目標(biāo)約束的正、負(fù)偏差變目標(biāo)規(guī)劃的目標(biāo)函數(shù)是由各目標(biāo)約束的正、負(fù)偏差變量及相應(yīng)的優(yōu)先因子、權(quán)系數(shù)構(gòu)成的，其中不含決策變量。量及相應(yīng)的優(yōu)先因子、權(quán)系數(shù)構(gòu)成的，其中不含決策變量。因?yàn)闆Q策者的愿望總是盡可能縮小偏差，實(shí)現(xiàn)目標(biāo)。故總因?yàn)闆Q策者的愿望總是盡可能縮小

11、偏差，實(shí)現(xiàn)目標(biāo)。故總是將目標(biāo)函數(shù)極小化，其基本形式有三種。是將目標(biāo)函數(shù)極小化，其基本形式有三種。 對于第對于第 i 個(gè)目標(biāo)個(gè)目標(biāo): iiiibddXf (1) 若要求若要求決策值超過目標(biāo)值決策值超過目標(biāo)值，則相應(yīng)的負(fù)偏差變量，則相應(yīng)的負(fù)偏差變量要盡可能地小，而對正偏差變量不加限制，目標(biāo)函數(shù)的形要盡可能地小，而對正偏差變量不加限制，目標(biāo)函數(shù)的形式為式為 ：idmin (2) 允許允許達(dá)不到目標(biāo)值達(dá)不到目標(biāo)值，就是相應(yīng)的正偏差變量要盡，就是相應(yīng)的正偏差變量要盡可能地小，可能地小， 目標(biāo)函數(shù)的形式為目標(biāo)函數(shù)的形式為 ：idmin (3) 恰好達(dá)到目標(biāo)恰好達(dá)到目標(biāo)，則相應(yīng)的正、負(fù)偏差變量都要盡，則相應(yīng)

12、的正、負(fù)偏差變量都要盡可能地小，可能地小， 目標(biāo)函數(shù)的形式為目標(biāo)函數(shù)的形式為 ：iiddmin 加入優(yōu)先因子和權(quán)系數(shù)后，建立目標(biāo)函數(shù)，其一般形加入優(yōu)先因子和權(quán)系數(shù)后，建立目標(biāo)函數(shù)，其一般形式為：式為：LllkllklKkkddpz11min 前述問題的目標(biāo)規(guī)劃模型可以寫為：前述問題的目標(biāo)規(guī)劃模型可以寫為：3322211mindpddpdpz。，3,2, 1,0,561081020112s.t.2133212221112121iddxxddxxddxxddxxxxii目標(biāo)規(guī)劃的一般數(shù)學(xué)模型，見教材目標(biāo)規(guī)劃的一般數(shù)學(xué)模型，見教材 135136頁。頁。2 2目標(biāo)規(guī)劃的圖解分析法目標(biāo)規(guī)劃的圖解分析法

13、對于只有兩個(gè)決策變量的線性目標(biāo)規(guī)劃的數(shù)學(xué)模型，對于只有兩個(gè)決策變量的線性目標(biāo)規(guī)劃的數(shù)學(xué)模型，可以用圖解法來分析求解。傳統(tǒng)的線性規(guī)劃一般只是尋求可以用圖解法來分析求解。傳統(tǒng)的線性規(guī)劃一般只是尋求一個(gè)點(diǎn)，在這個(gè)點(diǎn)上得到單目標(biāo)的最優(yōu)值，目標(biāo)規(guī)劃一般一個(gè)點(diǎn)，在這個(gè)點(diǎn)上得到單目標(biāo)的最優(yōu)值，目標(biāo)規(guī)劃一般是尋求一個(gè)區(qū)域，這個(gè)區(qū)域提供了相互矛盾的目標(biāo)集的折是尋求一個(gè)區(qū)域，這個(gè)區(qū)域提供了相互矛盾的目標(biāo)集的折衷方案。衷方案。 步驟步驟1 建立直角坐標(biāo)建立直角坐標(biāo)系，令各偏差變量為系，令各偏差變量為0，作，作出所有的約束直線出所有的約束直線 。滿足。滿足所有絕對約束條件的區(qū)域，所有絕對約束條件的區(qū)域，用陰影標(biāo)出。用

14、陰影標(biāo)出。 步驟步驟2 作圖表示差變量增減對約束直線的影響作圖表示差變量增減對約束直線的影響 在所有目標(biāo)約束直線旁標(biāo)上在所有目標(biāo)約束直線旁標(biāo)上 d +， d - ，如圖所示。這，如圖所示。這表明目標(biāo)約束直線可以沿表明目標(biāo)約束直線可以沿d +， d - ，所示的方向平移。，所示的方向平移。 步驟步驟3 根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。解。 根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，首先考慮具有優(yōu)先根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，首先考慮具有優(yōu)先因子因子 p1 的目標(biāo)的實(shí)現(xiàn)。目標(biāo)函數(shù)要求實(shí)現(xiàn)的目標(biāo)的實(shí)現(xiàn)。目標(biāo)函數(shù)要求實(shí)現(xiàn) min d1+，從圖，從圖中可見，可以

15、滿足中可見，可以滿足d1+=0 ，這時(shí)，只能在三角形，這時(shí)，只能在三角形 OBC的區(qū)的區(qū)域上取值；域上取值； 考察具有優(yōu)先因子考察具有優(yōu)先因子 p2的的目標(biāo)，此時(shí)可在線段目標(biāo)，此時(shí)可在線段ED 上上取值；取值； 考察優(yōu)先因子考察優(yōu)先因子 p3 的目標(biāo)，的目標(biāo)，這就使取值范圍縮小到線段這就使取值范圍縮小到線段 GD 上，該線段上所有點(diǎn)的上，該線段上所有點(diǎn)的坐標(biāo)，都是問題的解。坐標(biāo)，都是問題的解。 多目標(biāo)規(guī)劃問題的另一類表示方法 買糖問題買糖問題 設(shè)商店有甲、乙、丙三種糖果，單價(jià)分別為設(shè)商店有甲、乙、丙三種糖果，單價(jià)分別為4元元/kg ，2.80元元/kg 和和 2.40元元/kg。今要籌辦一次節(jié)

16、日茶話會(huì)，要求。今要籌辦一次節(jié)日茶話會(huì)，要求用于買糖的錢數(shù)不超過用于買糖的錢數(shù)不超過20元，糖的總量不少于元，糖的總量不少于6kg ，甲、，甲、乙兩種糖的總和不少于乙兩種糖的總和不少于3kg ，問應(yīng)如何確定最好的買糖方，問應(yīng)如何確定最好的買糖方案。案。 解解：設(shè)購買甲：設(shè)購買甲,乙乙,丙三種糖果的斤數(shù)分別為丙三種糖果的斤數(shù)分別為x1,x2,x3 用于買糖所花的錢數(shù)為用于買糖所花的錢數(shù)為 y1 ，所買糖的總斤數(shù)為，所買糖的總斤數(shù)為 y2 。 我們希望我們希望 y1 取最小值，取最小值，y2 取最大值。取最大值。maxmin4 . 28 . 2432123211xxxyxxxy 約束條件可以寫為：

17、約束條件可以寫為：0,36204 . 28 . 2432121321321xxxxxxxxxxx 這是含有兩個(gè)目標(biāo)的線性規(guī)劃問題，這里可以將求這是含有兩個(gè)目標(biāo)的線性規(guī)劃問題，這里可以將求y2的最大值轉(zhuǎn)化為求（的最大值轉(zhuǎn)化為求（- y2 ）的最小值，這時(shí)目標(biāo)函數(shù)可以）的最小值，這時(shí)目標(biāo)函數(shù)可以寫為：寫為： TxfxfV21,min其中：其中：Txxxxyxfyxf),( , )( , )(32122113 3用單純形法求解目標(biāo)規(guī)劃用單純形法求解目標(biāo)規(guī)劃 目標(biāo)規(guī)劃的數(shù)學(xué)模型與線性規(guī)劃的數(shù)學(xué)模型基本相同，目標(biāo)規(guī)劃的數(shù)學(xué)模型與線性規(guī)劃的數(shù)學(xué)模型基本相同，因此利用單純形法求解步驟也基本相同，但是需要尤其

18、注因此利用單純形法求解步驟也基本相同，但是需要尤其注意它們之間的區(qū)別。意它們之間的區(qū)別。 線性規(guī)劃的單純形法求解過程：線性規(guī)劃的單純形法求解過程： 1. 建立初始單純形表，計(jì)算出所有變量的檢驗(yàn)數(shù)。建立初始單純形表，計(jì)算出所有變量的檢驗(yàn)數(shù)。 2. 在非基變量檢驗(yàn)數(shù)中找到最大的正數(shù)在非基變量檢驗(yàn)數(shù)中找到最大的正數(shù) j，它所對，它所對應(yīng)的變量應(yīng)的變量 xj 作為換入基的變量。作為換入基的變量。 3. 對于所有對于所有 aij 0 計(jì)算計(jì)算 bi /aij ，其中最小的元素，其中最小的元素 所所對應(yīng)的基變量對應(yīng)的基變量 xi 作為換出基的變量。作為換出基的變量。 4. 建立新單純形表，重復(fù)上述步驟建立

19、新單純形表，重復(fù)上述步驟2、3，直到所有，直到所有檢驗(yàn)數(shù)都小于等于零。檢驗(yàn)數(shù)都小于等于零。 由于目標(biāo)規(guī)劃的目標(biāo)函數(shù)都是求極小化問題，而線性由于目標(biāo)規(guī)劃的目標(biāo)函數(shù)都是求極小化問題，而線性規(guī)劃問題的標(biāo)準(zhǔn)型中目標(biāo)函數(shù)都是求極大化問題，因此在規(guī)劃問題的標(biāo)準(zhǔn)型中目標(biāo)函數(shù)都是求極大化問題，因此在用單純形法求解時(shí)要注意一些重要的的差別。用單純形法求解時(shí)要注意一些重要的的差別。)3 , 2 , 1( 0,1002340 210 min213321222111132211iddxxddxxddxxddxdPddPzii 用單純形法求解下述目標(biāo)規(guī)劃問題：用單純形法求解下述目標(biāo)規(guī)劃問題： 第一步：第一步：列出初始單

20、純形表，并計(jì)算檢驗(yàn)數(shù)。列出初始單純形表，并計(jì)算檢驗(yàn)數(shù)。 將表格中最后一行檢驗(yàn)數(shù)按優(yōu)先級(jí)改寫為：將表格中最后一行檢驗(yàn)數(shù)按優(yōu)先級(jí)改寫為： （這是與線性規(guī)劃單純形法的（這是與線性規(guī)劃單純形法的第一個(gè)差別第一個(gè)差別） 對兩行檢驗(yàn)數(shù)需分別進(jìn)行處理。對兩行檢驗(yàn)數(shù)需分別進(jìn)行處理。 第二步：第二步：確定換入基的變量。確定換入基的變量。 在負(fù)檢驗(yàn)數(shù)中，選擇最小的一個(gè)在負(fù)檢驗(yàn)數(shù)中，選擇最小的一個(gè) j 所對應(yīng)的變量所對應(yīng)的變量 xj作為換入基的變量。在這個(gè)問題中第一優(yōu)先級(jí)作為換入基的變量。在這個(gè)問題中第一優(yōu)先級(jí) P1 所的檢所的檢驗(yàn)數(shù)中驗(yàn)數(shù)中 1 是最小的，因此是最小的，因此 x1 為換入基的變量。為換入基的變量。

21、 這是與線性規(guī)劃單純形法的這是與線性規(guī)劃單純形法的第二個(gè)差別第二個(gè)差別，在線性規(guī)劃，在線性規(guī)劃中是將大于零的檢驗(yàn)數(shù)中較大的一個(gè)對應(yīng)的變量換入基。中是將大于零的檢驗(yàn)數(shù)中較大的一個(gè)對應(yīng)的變量換入基。這是僅僅因?yàn)槟繕?biāo)函數(shù)取值有極大和極小的差別，對于目這是僅僅因?yàn)槟繕?biāo)函數(shù)取值有極大和極小的差別，對于目標(biāo)函數(shù)取極小的線性規(guī)劃問題也可以同樣進(jìn)行處理。標(biāo)函數(shù)取極小的線性規(guī)劃問題也可以同樣進(jìn)行處理。 第三步：第三步：確定換出基的變量。確定換出基的變量。 對于所有對于所有 aij 0 計(jì)算計(jì)算 bi /aij ，其中最小的元素，其中最小的元素 所對應(yīng)所對應(yīng)的基變量的基變量 xi 作為換出基的變量。（這與線性規(guī)劃

22、相同）作為換出基的變量。（這與線性規(guī)劃相同） 在這個(gè)問題中在這個(gè)問題中 minbi /aij =10，因此，因此 d1- 為換出變量。為換出變量。 換入、換出基的變量確定過程如下表：換入、換出基的變量確定過程如下表： 第四步：第四步：用換入變量替換換出變量，進(jìn)行單純形法迭用換入變量替換換出變量，進(jìn)行單純形法迭代運(yùn)算，直至優(yōu)先級(jí)代運(yùn)算，直至優(yōu)先級(jí) P1 所對應(yīng)的檢驗(yàn)數(shù)全為非負(fù)。所對應(yīng)的檢驗(yàn)數(shù)全為非負(fù)。 本例中，第一優(yōu)先級(jí)計(jì)算后得：本例中，第一優(yōu)先級(jí)計(jì)算后得： 由于優(yōu)先級(jí)由于優(yōu)先級(jí) P2 的檢驗(yàn)數(shù)仍然有負(fù)值，因此可以繼續(xù)的檢驗(yàn)數(shù)仍然有負(fù)值，因此可以繼續(xù)優(yōu)化，重復(fù)上述步驟優(yōu)化，重復(fù)上述步驟 24 。

23、 確定換入、換出變量：確定換入、換出變量： 第一點(diǎn)說明：第一點(diǎn)說明： 目標(biāo)函數(shù)按優(yōu)先級(jí)順序進(jìn)行優(yōu)化，當(dāng)目標(biāo)函數(shù)按優(yōu)先級(jí)順序進(jìn)行優(yōu)化，當(dāng) P1 行所有檢驗(yàn)行所有檢驗(yàn)數(shù)非負(fù)時(shí)，說明第一級(jí)已經(jīng)優(yōu)化，可以轉(zhuǎn)入下一級(jí)，考察數(shù)非負(fù)時(shí)，說明第一級(jí)已經(jīng)優(yōu)化，可以轉(zhuǎn)入下一級(jí)，考察 P2 行檢驗(yàn)數(shù)，依此類推。行檢驗(yàn)數(shù)，依此類推。 第二點(diǎn)說明：第二點(diǎn)說明： 從考察從考察 P2 行檢驗(yàn)數(shù)開始，注意應(yīng)包括更高級(jí)別的優(yōu)行檢驗(yàn)數(shù)開始，注意應(yīng)包括更高級(jí)別的優(yōu)先因子在內(nèi)。如上述問題的進(jìn)一步單純形表如下：先因子在內(nèi)。如上述問題的進(jìn)一步單純形表如下：對應(yīng)的檢驗(yàn)數(shù)為對應(yīng)的檢驗(yàn)數(shù)為P1 + (3/2)P2 0對應(yīng)的檢驗(yàn)數(shù)為對應(yīng)的檢驗(yàn)數(shù)

24、為P1 P2 0對應(yīng)的檢驗(yàn)數(shù)為對應(yīng)的檢驗(yàn)數(shù)為P1 2P2 0 因此上述三種情況都因此上述三種情況都不能選為換入基的變量，不能選為換入基的變量，這其實(shí)與線性規(guī)劃相同。這其實(shí)與線性規(guī)劃相同。 判別迭代計(jì)算停止的準(zhǔn)則：判別迭代計(jì)算停止的準(zhǔn)則： (1) 檢驗(yàn)數(shù)檢驗(yàn)數(shù) P1 , P2 , , Pk 行的所有值均行的所有值均為非負(fù)；為非負(fù)； (2) 若若 P1 , P2 , , Pi 行的所有檢驗(yàn)數(shù)為行的所有檢驗(yàn)數(shù)為非負(fù)，而非負(fù)，而 Pi+1 行存在負(fù)檢驗(yàn)數(shù)，但在負(fù)檢驗(yàn)行存在負(fù)檢驗(yàn)數(shù)，但在負(fù)檢驗(yàn)數(shù)所在列的上面行中有正檢驗(yàn)數(shù)（不一定是數(shù)所在列的上面行中有正檢驗(yàn)數(shù)（不一定是相鄰行，只要在起上方即可）。相鄰行，

25、只要在起上方即可）。4 4求解目標(biāo)規(guī)劃的層次算法求解目標(biāo)規(guī)劃的層次算法 求解目標(biāo)規(guī)劃是從高優(yōu)先級(jí)到低優(yōu)先級(jí)逐層優(yōu)化的，求解目標(biāo)規(guī)劃是從高優(yōu)先級(jí)到低優(yōu)先級(jí)逐層優(yōu)化的，求解目標(biāo)規(guī)劃的層次算法就是根據(jù)這樣的思想構(gòu)造的。求解目標(biāo)規(guī)劃的層次算法就是根據(jù)這樣的思想構(gòu)造的。 層次算法步驟：層次算法步驟： 第一步：第一步： 對目標(biāo)函數(shù)中的對目標(biāo)函數(shù)中的 P1 層次進(jìn)行優(yōu)化，建立第層次進(jìn)行優(yōu)化，建立第一層次的線性規(guī)劃模型一層次的線性規(guī)劃模型 LP1 并求解。并求解。 LP1的目標(biāo)函數(shù)為的目標(biāo)函數(shù)為Lllldwdwz111111minLP1的約束條件含原目標(biāo)規(guī)劃的所有約束。的約束條件含原目標(biāo)規(guī)劃的所有約束。 第二

26、步：第二步：對對 P2 層次進(jìn)行優(yōu)化。層次進(jìn)行優(yōu)化。 由于下一層次的優(yōu)化應(yīng)在前面各層次優(yōu)化的基礎(chǔ)上進(jìn)由于下一層次的優(yōu)化應(yīng)在前面各層次優(yōu)化的基礎(chǔ)上進(jìn)行行，若第一層次目標(biāo)函數(shù)最優(yōu)值為，若第一層次目標(biāo)函數(shù)最優(yōu)值為 z1* ，則構(gòu)建的，則構(gòu)建的P2 層次層次的線性規(guī)劃模型的線性規(guī)劃模型 LP2 ，其目標(biāo)函數(shù)為，其目標(biāo)函數(shù)為Lllldwdwz122222min 約束條件除含有原目標(biāo)規(guī)劃的所有約束條件之外，由約束條件除含有原目標(biāo)規(guī)劃的所有約束條件之外，由于這一步優(yōu)化是在前一步優(yōu)化的基礎(chǔ)上進(jìn)行的，所以前一于這一步優(yōu)化是在前一步優(yōu)化的基礎(chǔ)上進(jìn)行的，所以前一步優(yōu)化的結(jié)果應(yīng)成為一個(gè)新的約束條件，即約束條件增加步優(yōu)

27、化的結(jié)果應(yīng)成為一個(gè)新的約束條件，即約束條件增加了一個(gè)式子：了一個(gè)式子：*111111zdwdwLill 小于等于使得上一步的最優(yōu)值在計(jì)算后不會(huì)發(fā)生改變小于等于使得上一步的最優(yōu)值在計(jì)算后不會(huì)發(fā)生改變 第三步：第三步：依此類推得到第依此類推得到第Ps( s 2) 層次進(jìn)行優(yōu)化時(shí)建層次進(jìn)行優(yōu)化時(shí)建立的線性規(guī)劃模型立的線性規(guī)劃模型 LPs 為：為：Llsslsslsdwdwz1min), 1( 0, , ), 1( 0), 1( ), 1(),() 1, 1( . .11j*LlddnjxLlgddxcmi bxasrzdwdwtslljlllnjjljinjijrrrlrrl 當(dāng)進(jìn)行到當(dāng)進(jìn)行到 s=K 時(shí)，對時(shí)，對 Pk 層次建立的線性規(guī)劃模型層次建立的線性規(guī)劃模型LPk 的最優(yōu)解即為目標(biāo)規(guī)劃問題的滿意解。的最優(yōu)解即為目標(biāo)規(guī)劃問題的滿意解。 K是某一步。是某一步。 例例. 用層次算法求解下述目標(biāo)規(guī)劃。用層次算法求解下述目標(biāo)規(guī)劃。)4 , 1( 0,155 16 40 215321222. . 3min2144233122211121214333322211idd