1、多目標規(guī)劃講解人：陳修素時 間：2010年8月1 在許多實際問題中，衡量一個方案的好壞標準往往不止一個，例如設計一個導彈，既要射程最遠，又要燃料最省，還要精度最高. 這一類問題統(tǒng)稱為多目標最優(yōu)化問題或多目標規(guī)劃問題. 我們先來看一個生產(chǎn)計劃的例子.2DVD在線租賃第二個問題的求解問題二的分析 經(jīng)營成本和會員的滿意度是被考慮的兩個相互制約的重要因素. 在忽略郵寄成本的前提下，經(jīng)營成本主要體現(xiàn)為DVD的數(shù)量. 我們主要考慮在會員向網(wǎng)站提供需求信息，且滿足一定要求的前提下，對給定數(shù)量DVD進行分配決策，使得DVD的數(shù)量盡量小，會員滿意度最大. 3 假設按照公歷月份進行的租賃業(yè)務，即會員無論兩次租賃還

2、是一次租賃，必須在當月內完成DVD的租與還. 同時假設網(wǎng)站對其會員進行一次租賃業(yè)務時，只能向其提供3張該會員已經(jīng)預定的DVD，否則不進行租賃. 經(jīng)觀察，可以認為在線訂單中每個會員的預定DVD的表示偏好程度的數(shù)字反映了會員對所預定不同DVD的滿意程度，且當會員租到其預定排序為1，2，3的三張DVD時，滿意度達到100% .會員沒有預定的DVD對其滿意度的貢獻為0 . 4 利用層次分析法，對此滿意指數(shù)的合理性進行了簡單分析. 該問題要求根據(jù)現(xiàn)有的100種DVD的數(shù)量和當前需要處理的1000位會員的在線訂單，制定分配策略，使得會員達到最大的滿意度. 因而我們認為只需對這些DVD進行一次性分配，使得會

3、員的總體滿意度達到最大. 為此考慮建立優(yōu)化模型，進行求解. 5問題二的模型及求解 經(jīng)營成本和會員的滿意度是被考慮的兩個相互制約的重要因素. 在忽略郵寄成本的前提下，經(jīng)營成本主要體現(xiàn)為DVD的數(shù)量. 我們主要考慮在會員向網(wǎng)站提供需求信息，且滿足一定要求的前提下，對給定數(shù)量DVD進行分配決策，使得DVD的數(shù)量盡量小，會員滿意度最大. 6由此，可得問題二的0-1整數(shù)線性規(guī)劃模型如下： 7 根據(jù)所得的0-1整數(shù)線性規(guī)劃模型，利用LINGO軟件進行求解，我們得到了一組最優(yōu)分配方案（見表3） . 該組最優(yōu)解其目標函數(shù)會員總體最大滿意度為91.56%，只有6人未成功租賃（如：前30名會員中C0008被分配到

4、DVD），其余994個會員全都得到了3張預定的DVD . 8我們希望購買DVD的總數(shù)量最小，即 :由此，可以得到問題三的雙目標整數(shù)線性規(guī)劃模型如下： 9表 當 時最小購買量的 值DVD編號D01D02D03D04D05D06D07D08D09D10最少購買量14211724121719212214DVD編號D11D12D13D14D15D16D17D18D19D20最少購買量18181717172418161823DVD編號D21D22D23D24D25D26D27D28D29D30最少購買量20182214181715121624DVD編號D31D32D33D34D35D36D37D38D3

5、9D40最少購買量19222019222213171717DVD編號D41D42D43D44D45D46D47D48D49D50最少購買量32201621221620152020續(xù)上表DVD編號D51D52D53D54D55D56D57D58D59D60最少購買量24171917191819172021DVD編號D61D62D63D64D65D66D67D68D69D70最少購買量16191920171917212019DVD編號D71D72D73D74D75D76D77D78D79D80最少購買量21221520151412171917DVD編號D81D82D83D84D85D86D87D8

6、8D89D90最少購買量18101412211322151317DVD編號D91D92D93D94D95D96D97D98D99D100最少購買量24171514251522201122 我們利用規(guī)劃模型求得每種DVD的購買量后，需要對其進行可行性校驗，測試此結果是否可以滿足一個月內比例為95%的會員得到他想看的DVD，且具有盡可能大的總體滿意度.12校驗方法： （一）根據(jù)訂單和求得的DVD購買數(shù)量，利用問題二的規(guī)劃模型進行第一次分配，對分配情況：租賃的會員，DVD的分配情況，剩余的各種DVD數(shù)量作記錄；同時將已租賃的會員在滿意指數(shù)矩陣的指數(shù)全變?yōu)?，即不考慮對其進行第二次分配. （二）隨機從

7、第一次得到DVD的會員中抽取60%，將這部分人所還回的DVD與第一次分配余下的DVD合在一起，作為第二次分配時各種DVD的現(xiàn)有量.然后，利用問題二的0-1線性規(guī)劃模型對第一次未分配到DVD的會員進行第二次分配；13 （三）統(tǒng)計出經(jīng)過兩次分配后，得到DVD的會員的比例，若大于95%，則此次分配成功.利用這種算法進行多次隨機模擬，若大多數(shù)情況下可以使得到DVD的會員大于95%，則認為模型三是合理的.14校驗結果： 因為每次檢驗需時約1小時，我們只對問題三求得的結果進行了7次模擬，其中6次符合要求（觀看比例大于95%）.下面給出7次模擬得到的觀看比例（表7）： 表7 7次模擬結果每次的觀看比例列表驗

8、證次數(shù)1234567觀看比例95.896.693.495.395.996.195.715 在實際問題中，經(jīng)常是在一組約束條件下，希望同時實現(xiàn)多個目標。例如，在企業(yè)安排生產(chǎn)問題中，既希望利潤高，又要消耗低，還要考慮市場上產(chǎn)品的銷路等等。當然，這些目標之間往往是相互矛盾的，要追求利潤最大，通常消耗便不可能最低。能否構造這樣一個數(shù)學模型，其結果，即使利潤盡量地大，同時使消耗盡量地低，銷路盡量地好呢? PART II 目標規(guī)劃方法16例3 多目標生產(chǎn)計劃問題某工廠計劃用所擁有的三種資源生產(chǎn)代號為A、B的兩種產(chǎn)品，原材料資源可供量為90噸，使用專用設備臺時最多為200臺時，勞動力300個；生產(chǎn)單位產(chǎn)品A

9、需用原材料2.5噸，設備臺時4個和勞動力3個，產(chǎn)品B則需用原料1.5噸，設備臺時5個和勞動力10個。扣除成本，每單位產(chǎn)品A、B分別可獲利7(百元)和12(百元)，求一個生產(chǎn)計劃，使獲利最大。 17據(jù)題設，容易得到其線性規(guī)劃基礎模型為：18其中x1，x2依次表示產(chǎn)品A 和B的生產(chǎn)量。容易求出其絕對最優(yōu)解為x1=20，x2=24，最大利潤值為428(百元)。 19 問題分析與模型假設 上述結果并未考慮市場信息和資源的可塑性條件，僅僅根據(jù)現(xiàn)有生產(chǎn)能力和固定不變的產(chǎn)品價格求得的，因而是脫離實際的“理想化”方案。依據(jù)市場調查和生產(chǎn)能力，廠長認為上述利潤指標不易達到，決定降低為420(百元)，當然力求超過

10、。根據(jù)市場調查和預測，產(chǎn)品B開始出現(xiàn)滯銷現(xiàn)象，隨著市場需求的改變，預測兩種產(chǎn)品的需求量比例大致為1:1，而目前的產(chǎn)品比例失調，有待調整。 203根據(jù)原材料市場信息，這種原材料的市 場價格下跌，而所生產(chǎn)的產(chǎn)品價格基本 穩(wěn)定，故決策者希望盡量將原材料轉化 為產(chǎn)品，即希望原料要全部用掉。但按 原生產(chǎn)計劃看，原材料將有剩余(4噸)。 因此，盡可能將原材料全部轉化為利潤 成為一個重要的生產(chǎn)規(guī)劃指標。 21 這了敘述方便，先來考慮單利潤指標情況。 實現(xiàn)利潤420是決策者的希望，但在計劃具體實施后，由于各方面因素的制約，完全有可能達不到，也完全可能超過該指標，換句話說，可能實現(xiàn)的利潤指標和規(guī)定的利潤指標完全

11、可能不一致而產(chǎn)生某一差距。我們稱這個差距為偏差變量，記以d。規(guī)定d0。 22 從決策者的心理和要求來分析，使之絕對滿意可以做不到，但他總希望將來得到的實際利潤與規(guī)定的指標值之間偏差量愈小愈好，這就“等價地”表示了他希望利潤值達420的目標。當然，他所希望的是未達規(guī)定指標的實際值與規(guī)定值的偏差量越小越好。我們引入下述符號： d+表示超出指標的偏差變量，稱為正偏差變量。 d表示未達指標的偏差變量，稱為負偏差變量。 23 自然規(guī)定d+0，d0。顯然，偏差變量d+，d的取值有且僅有下述三種情形： i)超額完成指標時，d+0，d=0； ii)未能完成指標時，d0，d+=0； iii)恰好完成指標時，d+

12、=0，d=0。 有了偏差變量的概念，上述利潤指標就可以比較靈活地進行表示了。事實上，決策者的目標是利潤達到或超過420。因此，他所希望的自然是d+0。但實際中完全可能d0，這是決策者所不希望出現(xiàn)的，而一旦出現(xiàn)d0，也希望d盡可能地小。 24 因此，決策者最關心是d達到最小，故此時的目標函數(shù)可表示為 ： 這樣，我們把目標函數(shù)寫成了偏差變量的函數(shù)。注意，例子中原來的目標函數(shù)顯然不再成為目標規(guī)劃的目標函數(shù)。由于它在目標規(guī)劃中只是問題要達到的目標之一，因而也成了一個約束條件。 25 事實上，作為目標之一的利潤值已被限制(約束)在420百元，用偏差變量很容易將它表成為 它自然是約束條件，而且確切地表出了

13、目標利潤應為420百元這一約束。事實上，當達不到420百元時，由于這一約束條件是目標規(guī)劃的目標之一的約束要求，故又稱為目標約束，其特點是帶有偏差變量的等式約束。 26 凡非目標約束的約束條件統(tǒng)稱為系統(tǒng)約束或剛性約束。也相應地稱目標約束為柔性約束，這主要是因為這種約束較剛性約束來得靈活。 至此，我們可把上述單利潤指標的規(guī)劃問題寫成如下形式: 27 稱這種規(guī)劃模式為目標規(guī)劃模式。其特點主要兩條，其一是目標函數(shù)是各目標的偏差變量的函數(shù)，其二是約束條件中含有目標約束條件。 有了上面關于單指標目標規(guī)劃的構模原理，我們來討論具有三個指標情形的例3該如何構模。 28 模型建立 對利潤指標已有 ，及相應的目標

14、約束 ,這里將偏差變量給以下標1表示利潤指標對應的偏差變量?，F(xiàn)考慮原材料要求的指標。記 表示原材料偏差變量，則 表示未用量， 表示超用量，由于希望90噸原料全部用完，既不希望有余也不希望超支，故目標函數(shù)應為 29 相應的目標約束完全類似利潤指標情形，應為 又設d3表示產(chǎn)品比例指標偏差變量。即以d3表示產(chǎn)品A和B之產(chǎn)量差距，則由于要求兩種產(chǎn)品的產(chǎn)量盡可能達到或接近1:1，故有目標函數(shù) 其對應的約束條件可寫為 30 我們的目的是求這三個目標的統(tǒng)一體的最優(yōu)化方案，即從整體看，我們希望各個指標的偏差總和達最小，要把所涉及指標都考慮到，只能按各目標的輕重緩急分級考慮。事實上，各目標的重要程度是不同的，可

15、以因人，因地，因時而異。比如產(chǎn)品的產(chǎn)量問題，對有的企業(yè)來講是第一位的，而對別的企業(yè)來講則是第二位的；同一企業(yè)此時此地產(chǎn)量第一而彼時彼地可能產(chǎn)量就放在第二位甚至于第三位，等等。31 這就需要決策者或決策集團根據(jù)各目標的重要程度，科學地予以排隊。我們規(guī)定p1表示第一位重要，p2表示第二位重要，即滿足 ,稱pk為優(yōu)先因子。如第一位重要的目標是要求超額完成利潤指標，則賦予它優(yōu)先因子p1，其在整個問題的目標函數(shù)中表為 ，列為第一優(yōu)先級；其次目標是要求恰好用完原材料，賦予優(yōu)先因子p2，列為第二優(yōu)先級表為 ;最后是要求產(chǎn)品產(chǎn)量比例達1:1的目標，賦予優(yōu)先因子p3，列為第三優(yōu)先 32 級，在整體目標函數(shù)中表為

16、 , 于是整個問題的目標函數(shù)表為 從而三個目標的例1的目標規(guī)劃模型便 是 33例4 某工廠生產(chǎn)代號為、的兩種產(chǎn)品，這兩種產(chǎn)品都要經(jīng)甲、乙兩個車間加工，并經(jīng)檢驗與銷售兩部門處理。已知甲、乙兩車間每月可用生產(chǎn)工時分別為120小時和150小時，每小時費用分別為80元和20元，其它數(shù)據(jù)如表44。 工廠領導希望給出一個可行性生產(chǎn)方案，使生產(chǎn)銷售及檢驗等方面都能達標。34 表44 35問題分析與模型假設 與工廠總經(jīng)理交談，確定下列幾個目標： p1：檢驗和銷售費每月不超過4600元； p2：每月售出產(chǎn)品I不少于50件； p3：兩車間生產(chǎn)工時充分利用（重要性權系數(shù)按兩車間每小時費用比確定）； p4：甲車間加班

17、不超過20小時； p5：每月售出產(chǎn)品不少于80件； p6：兩車間加班總時數(shù)要有控制（對權系數(shù)分配參照第三優(yōu)先級）。36 模型建立 設x1，x2分別為產(chǎn)品和的月產(chǎn)量，依題設,有37 設d1表檢驗銷售費偏差，則希望 達最小，有 相應的目標約束為 以 表示產(chǎn)品I售量偏差，則希望 達最小，有 相應的目標約束為 以d3、d4表示兩車間生產(chǎn)工時偏差，則由于要求充分利用兩車間生產(chǎn)工時，故希望 都達最小，考慮到費用比例為80：20=4：1，有 。 38 相應的目標約束應為 以d5表甲車間加班偏差，則有 ,相應目標約束為 ,最后用d6表產(chǎn)品售量偏差，則希望 達最小，有 相應約束為于是得到該問題的目標規(guī)劃模型為

18、3940 對目標規(guī)劃的小結線性目標規(guī)劃的幾個組成部分： 1，偏差變量 2，系統(tǒng)約束和目標約束 3，目標規(guī)劃的目標函數(shù) 4，目標函數(shù)的優(yōu)先級41 一般線性目標規(guī)劃的數(shù)學模型：42 建立一個實際問題的目標規(guī)劃模型的一般步驟如下： 第一步：由實際問題建立具有m個目標的線性規(guī)劃模型； 第二步：將多目標線性規(guī)劃模型轉化為目標規(guī)劃模型： 1，由實際問題對第i個目標給以適當?shù)钠谕?2，對第i個目標引進 ，建立目標約束方程并將其列入原約束條件之中；43 3，若原約束條件中有互相矛盾的方程， 則對它們同樣的引入 ； 4，確定第k個目標的優(yōu)先級別 及權系 數(shù) ； 5，建立目標函數(shù)minz。44 線性目標規(guī)劃的求解方法 對線性目標規(guī)劃的求解以下介紹線性目標規(guī)劃的序列法； 線性目標規(guī)劃的