1、關于多目標規劃模型第一張，PPT共三十一頁，創作于2022年6月 多目標決策由于考慮的目標多,有些目標之間又彼此有矛盾,這就使多目標問題成為一個復雜而困難的問題.但由于客觀實際的需要,多目標決策問題越來越受到重視,因而出現了許多解決此決策問題的方法.一般來說,其基本途徑是,把求解多目標問題轉化為求解單目標問題.其主要步驟是,先轉化為單目標問題,然后利用單目標模型的方法,求出單目標模型的最優解,以此作為多目標問題的解. 化多目標問題為單目標問題的方法大致可分為兩類,一類是轉化為一個單目標問題,另一類是轉化為多個單目標問題,關鍵是如何轉化. 下面,我們介紹幾種主要的轉化方法:主要目標法、線性加權和

2、法、字典序法、步驟法。第二張，PPT共三十一頁，創作于2022年6月f1f21234567810.1多目標決策問題的特征 在解決單目標問題時，我們的任務是選擇一個或一組變量X，使目標函數f(X)取得最大（或最小）。對于任意兩方案所對應的解，只要比較它們相應的目標值，就可以判斷誰優誰劣。但在多目標情況下，問題卻不那么單純了。例如，有兩個目標f1(X)，f2(X),希望它們都越大越好。下圖列出在這兩個目標下共有8個解的方案。其中方案1，2，3，4稱為劣解，因為它們在兩個目標值上都比方案5差，是可以淘汰的解。而方案5，6，7，8是非劣解（或稱為有效解，滿意解），因為這些解都不能輕易被淘汰掉，它們中間

3、的一個與其余任何一個相比，總有一個指標更優越，而另一個指標卻更差。一、解的特點第三張，PPT共三十一頁，創作于2022年6月二、模型結構 多目標決策問題包含有三大要素：目標、方案和決策者。在多目標決策問題中，目標有多層次的含義。從最高層次來看，目標代表了問題要達到的總目標。如確定最滿意的投資項目、選擇最滿意的食品。從較低層次來看，目標可看成是體現總目標得以實現的各個具體的目標，如投資項目的盈利要大、成本要低、風險要小；目標也可看成衡量總目標得以實現的各個準則，如食品的味道要好，質量要好，花費要少。 多目標決策問題中的方案即為決策變量，也稱為多目標問題的解。備選方案即決策問題的可行解。在多目標決

4、策中，有些問題的方案是有限的，有些問題 的方案是無限的。方案有其特征或特性，稱之為屬性。第四張，PPT共三十一頁，創作于2022年6月1、多目標規劃問題的模型結構為決策變量如對于求極大(max)型，其各種解定義如下：絕對最優解：若對于任意的X，都有F（X*）F(X)有效解：若不存在X，使得F（X*） F(X)弱有效解：若不存在X，使得F（X*)F(X)第五張，PPT共三十一頁，創作于2022年6月第六張，PPT共三十一頁，創作于2022年6月第七張，PPT共三十一頁，創作于2022年6月10.2 多目標規劃問題的求解1、主要目標法 在有些多目標決策問題中，各種目標的重要性程度往往不一樣。其中一

5、個重要性程度最高和最為關鍵的目標，稱之為主要目標法。其余的目標則稱為非主要目標。例如，在上述多目標問題中，假定f1(X)為主要目標，其余p-1個為非主要目標。這時，希望主要目標達到極大值，并要求其余的目標滿足一定的條件，即第八張，PPT共三十一頁，創作于2022年6月例題1 某工廠在一個計劃期內生產甲、乙兩種產品，各產品都要消耗A，B，C三種不同的資源。每件產品對資源的單位消耗、各種資源的限量以及各產品的單位價格、單位利潤和所造成的單位污染如下表。假定產品能全部銷售出去，問每期怎樣安排生產，才能使利潤和產值都最大，且造成的污染最小？甲乙資源限量資源A單位消耗資源B單位消耗資源C單位消耗9434

6、510240200300單位產品的價格400600單位產品的利潤70120單位產品的污染32第九張，PPT共三十一頁，創作于2022年6月解：問題的多目標模型如下對于上述模型的三個目標，工廠確定利潤最大為主要目標。另兩個目標則通過預測預先給定的希望達到的目標值轉化為約束條件。經研究，工廠認為總產值至少應達到20000個單位，而污染控制在90個單位以下，即由主要目標法化為單目標問題用單純形法求得其最優解為第十張，PPT共三十一頁，創作于2022年6月2、線性加權和目標規劃在上述目標規劃中，假定f1(X),f2(X),fp(X)具有相同的量綱,按照一定的規則分別給fi賦予相同的權系數i，作線性加權

7、和評價函數則多目標問題化為如下的單目標問題第十一張，PPT共三十一頁，創作于2022年6月例如，某公司計劃購進一批新卡車，可供選擇的卡車有如下4種類型：A1，A2，A3，A4。現考慮6個方案屬性：維修期限f1，每100升汽油所跑的里數f2，最大載重噸數f3，價格（萬元）f4，可靠性f5，靈敏性f6。這4種型號的卡車分別關于目標屬性的指標值fij如下表所示。fijf1f2f3f4f5f6A12.01500455一般高A22.527003.665低一般A32.020004.245高很高A42.21800450很高一般首先對不同度量單位和不同數量級的指標值進行標準化處理。先將定性指標定量化：第十二張

8、，PPT共三十一頁，創作于2022年6月效益型指標很低低一般高很高13579很高高一般低很低 成本型指標可靠性和靈敏性都屬于效益型指標，其打分如下可靠性一般低高很高5379靈敏性高一般很高一般7595按以下公式作無量綱的標準化處理其中：第十三張，PPT共三十一頁，創作于2022年6月變換后的指標值矩陣為：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001設權系數向量為W=（0.2,0.1,0.1,0.1,0.2,0.3),則故最優方案為選購A3型卡車第十四張，PPT共三十一頁，

9、創作于2022年6月3、分層序列法：1.基本步驟：把(VP)中的p個目標 按其重要程度排序。依次求單目標規劃的最優解。2. 過程：無妨設其次序為 先求解 得最優值 ，記再解 得最優值 ，依次進行，直到 得最優值則 是在分層序列意義下的最優解集合。第十五張，PPT共三十一頁，創作于2022年6月3. 性質： ，即在分層序列意義下的最優解是有效解。證明：反證。設 ，但 ，則必存在 使 即至少有一個j0 ，使 , 由于 ，即 ， 矛盾。得證。4. 進一步討論： 上述方法過程中，當某個問題(Pj)的解唯一時，則問題 的求解無意義，因為解都是唯一的。 實際求解時，有較寬容意義下的分層序列法： 取 為預先

10、給定的寬容值，整個解法同原方法類似，只是取各約束集合時，分別取為：第十六張，PPT共三十一頁，創作于2022年6月 目標規劃模型 線性規劃問題都是處理單個目標的情況，但是在現實世界中有許多問題具有多個目標，這些目標的重要性各不相同，往往有不同的量綱，有的目標相互依賴，例如決策者既希望實現利潤最大，又希望實現產值最大；有的相互抵觸，如決策者既希望充分利用資源，又不希望超越資源限量。而決策者希望在某些限制條件下，依次實現這些目標。這就是目標規劃所要解決的問題。當所有的目標函數和約束條件都是線性時，我們稱其為線性目標規劃問題。在這里我們主要討論線性目標規劃問題。一、目標規劃模型的建立 第十七張，PP

11、T共三十一頁，創作于2022年6月引例1： 對于生產計劃問題： 甲 乙 資源限額 材料 2 3 24 工時 3 2 26 單位利潤 4 3 現在工廠領導要考慮市場等一系列其他因素，提出如下目標：（1）根據市場信息，甲產品的銷量有下降的趨勢，而乙產品的銷量有上升的趨勢，故考慮乙產品的產量應大于甲產品的產量。（2）盡可能充分利用工時，不希望加班。（3）應盡可能達到并超過計劃利潤30元。現在的問題是：在原材料不能超計劃使用的前提下，如何安排生產才能使上述目標依次實現？第十八張，PPT共三十一頁，創作于2022年6月解：（1）決策變量：仍設每天生產甲、乙兩種產品各為x1和x2 偏差變量：對于每一目標，

12、我們引進正、負偏差變量。 如對于目標1，設d1-表示乙產品的產量低于甲產品產量的數，d1+表示乙產品的產量高于甲產品產量的數。稱它們分別為產量比較的負偏差變量和正偏差變量。則對于目標1，可將它表示為等式約束的形式 -x1+x2+ d1- d1+ =0 (目標約束) 同樣設d2-和d2+分別表示安排生產時，低于可利用工時和高于可利用工時，即加班工時的偏差變量，則對目標2，有 3x1+2x2+ d2-d2+ =26 對于目標3，設d3-和d3+分別表示安排生產時，低于計劃利潤30元和高于計劃利潤30元的偏差變量，有： 第十九張，PPT共三十一頁，創作于2022年6月 4x1+3x2+ d3-d3+

13、 =30 （2）約束條件：有資源約束和目標約束 資源約束：2x1+3x224 目標約束：為上述各目標中得出的約束 （3）目標函數：三個目標依次為： minZ1=d1- ，minZ2=d2+d2- ，minZ3=d3- 因而該問題的數學模型可表述如下： minZ1=d1- ，minZ2=d2+d2-，minZ3=d3- 2x1+3x224 st -x1+x2+ d1- d1+ =0 3x1+2x2+ d2-d2+ =26 4x1+3x2+ d3-d3+ =30 第二十張，PPT共三十一頁，創作于2022年6月 案例2（提級加新問題） 某公司的員工工資有四級，根據公司的業務發展情況，準備招收部分新

14、員工，并將部分員工的工資提升一級。該公司的員工工資及提級前后的編制表如下，其中提級后編制是計劃編制，允許有變化，其中1級員工中有8%要退休。公司領導的目標如下：（1）提級后在職員工的工資總額不超過550千元；（2）各級員工不要超過定編人數；（3）為調動積極性，各級員工的升級面不少于現有人數的18%；（4）總提級面不大于20%，但盡可能多提；（5）4級不足編制人數可錄用新工人。 第二十一張，PPT共三十一頁，創作于2022年6月問：應如何擬定一具滿意的方案，才能接近上述目標？ 級別1234工資（千元）8643現有員工數10204030編制員工數10225230解：（1）決策變量：設x1,x2,x

15、3,x4分別表示提升到1，2，3級和新錄用的員工數。 偏差變量：為各目標的正、負偏差變量。 （2）約束條件：1） 提級后在職員工的工資總額不超過550千元；8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1-d1+=550 第二十二張，PPT共三十一頁，創作于2022年6月 2）各級員工不要超過定編人數1級有： 10-10 8%+x1+d2-d2+=10 2級有： 20-x1+ x2+d3-d3+=22 3級有： 40-x2+ x3+d4-d4+=52 4級有： 30-x3+ x4+d5-d5+=303）各級員工的升級面不少于現有人數的18

16、%對2級有： x1+d6-d6+=22 18%對3級有： x2+d7-d7+=40 18% 對4級有： x3+d8-d8+=30 18% 4）總提級面人數不大于20%，但盡可能多提 x1+ x2+ x3+d9-d9+=100 20% 第二十三張，PPT共三十一頁，創作于2022年6月（3）目標函數：minZ1=d1+minZ2=d2+d3+ d4+ d5+minZ3=d6-+ d7-+ d8-minZ4=d9+ d9-案例3 有三個產地向四個銷地供應物資。產地Ai(i=1,2,3)的供應量ai、銷地Bj(j=1,2,3,4)的需要量bj、各產銷地之間的單位物資運費Cij如表2所示。表中，ai和

17、bj的單位為噸，Cij的單位為元/噸。編制調運方案時要求按照相應的優先級依次考慮下列七個目標：P1：B4是重點保證單位，其需要量應盡可能全部滿足；P2：A3向B1提供的物資不少于100噸；P3：每個銷地得到的物資數量不少于其需要量的80%； 第二十四張，PPT共三十一頁，創作于2022年6月P4：實際的總運費不超過最小總運費a的110%，這里的最小總費用利用第三大題中第2小題求出的結果；P5：因路況原因，盡量避免安排A2的物資運往B4；P6：對B1和B3的供應率要盡可能相同；P7：力求使總運費最省。試建立該問題的運籌學模型。 Cij BjAiB1B2B3B4aiA15267300A235462

18、00A34523400bj200100450250解：用表上作業法可求得不考慮P1至P6各目標時的最小運費調運方案，相應的最小運費為2950元第二十五張，PPT共三十一頁，創作于2022年6月（1）決策變量：設Ai運往Bj的物資為xij噸（2）約束條件：產量約束B4銷量要滿足銷量80%的限制供應率盡可能相同第二十六張，PPT共三十一頁，創作于2022年6月二、目標規劃的解法 由于目標規劃有多個目標，各個目標又有相對不同的重要性，求解時是首先滿足重要性權數大的目標，再滿足重要性權數次大的目標，所以并不能保證所有的目標都能達到，所求的解也不一定是最優解，而只能求出滿意解。 （3）目標函數第二十七張，PPT共三十一頁，創作于2022年6月 求解目標規劃的仍用單純形法，但是與線性規劃的單純形法不同的是，此時檢驗數行不再是一行，而是變化為一個檢驗數矩陣。 例4 用單純形法求解如下線性目標規劃模型 minZ1=d1-，minZ2=d2+d2-，minZ3=d3- 2x1+3x224 加入松馳變量化