《運籌學(xué)》 課件 第3章-線性規(guī)劃的擴展

7/16/2024第3章線性規(guī)劃的擴展1CONTENTS目錄3.1

運輸問題3.2

目標規(guī)劃3.3

數(shù)包絡(luò)分析7/16/202423.1運輸問題例3.1

某個公司從三個產(chǎn)地A1,A2,A3將物品運往四個銷地B1，B2，B3，B4。各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地的每件物品的運費如下表所示。應(yīng)如何調(diào)運，使得總運輸費用最?。?.1.1運輸問題的建模（1）問題的提出7/16/20244其中，

cij為從產(chǎn)地Ai運到銷地Bj的線路的運輸價格;

a1,a2,a3分別為16,10,22；b1,b2,b3,b4分別為8,14,12,14。解：設(shè)xij為從產(chǎn)地Ai運到銷地Bj的運量，（i=1,2,3;j=1,2,3,4）。

3.1.1運輸問題的建模7/16/20245運輸問題（TransportationProblem，簡記為TP）：在每個產(chǎn)地的供應(yīng)量與每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，把某種產(chǎn)品從多個產(chǎn)地調(diào)運到多個銷地，如何確定每條運輸線路上的運量使得總的運輸費用最小的問題。02運輸問題的一般模型（2）運輸問題的一般模型3.1.1運輸問題的建模7/16/20246圖3.1運輸問題的示意圖02運輸問題的一般模型3.1.2運輸問題的一般模型3.1.1運輸問題的建模7/16/20247所有產(chǎn)地的總供給量所有銷地的總銷售量設(shè)為從產(chǎn)地Ai運到銷地Bj的運量。根據(jù)供需關(guān)系可以將運輸問題分為三種類型：1）供需平衡的物資調(diào)運問題，S=D總供給等于總需求。當(dāng)供需平衡時，每個產(chǎn)地的物資可全部運出，每個銷地的需求都可以得到滿足，因此供需平衡的物資調(diào)運問題的數(shù)學(xué)模型為：02運輸問題的一般模型3.1.1運輸問題的建模7/16/20248這是一個具有mn個決策變量，m+n個約束條件的線性規(guī)劃問題。在一些實際的問題中還要求為整數(shù)，如調(diào)運的物資為電腦、家電或其它包裝成箱的物資，從而形成一個整數(shù)規(guī)劃問題。02運輸問題的一般模型3.1.1運輸問題的建模7/16/202492）供大于求的物資調(diào)運問題，S>D總供給大于總需求時，有些產(chǎn)地的物資不能全部運出，數(shù)學(xué)模型改為：3.1.1運輸問題的建模7/16/2024103）供不應(yīng)求的物資調(diào)運問題，S<D總供給小于總需求時時，數(shù)學(xué)模型為：3.1.1運輸問題的建模7/16/202411將不平衡的供需關(guān)系配平注：缺啥補啥，來配平。3.1.1運輸問題的建模7/16/202412例3.2

某公司在不同地區(qū)有三個工廠，產(chǎn)品將運往四個地區(qū)銷售。已知各線路的單位運輸成本和供需關(guān)系見下表，請寫出物資調(diào)運問題的數(shù)學(xué)模型，并轉(zhuǎn)化為供需平衡的表格形式。解：（略）3.1.1運輸問題的建模7/16/202413以上討論說明運輸問題是一類具有特殊結(jié)構(gòu)的線性規(guī)劃。供需平衡的物資調(diào)運問題是運輸問題的基本問題，因為可以將供過于求/供不應(yīng)求的運輸問題通過增加虛擬的銷地/產(chǎn)地轉(zhuǎn)化為供求平衡的運輸問題。運輸問題的特征體現(xiàn)在它的技術(shù)系數(shù)矩陣A中各元素僅可取值為1或0，且對應(yīng)于決策變量的系數(shù)列向量，只有第i個和第m+j個分量取值為1，其余分量的取值均為0，即這里，表示僅在第k個分量取值為1的m+n維單位列向量。3.1.1運輸問題的建模7/16/202414m行n行系數(shù)矩陣的特殊結(jié)構(gòu)決定了平衡運輸問題具有以下三個性質(zhì)。3.1.1運輸問題的建模7/16/2024151、運輸問題中任意m+n個決策變量的系數(shù)列向量都是線性相關(guān)的?？梢赃M一步證明，運輸問題的基變量的個數(shù)為m+n-1。如果我們能得到?jīng)Q策變量的m+n-1個線性無關(guān)的系數(shù)列向量，就得到一個相應(yīng)的基可行解。2、運輸問題必存在最優(yōu)解。（課后思考，為什么？）3、如果運輸問題中的所有供給量和需求量都為整數(shù)，則該問題的任意基可行解均為整數(shù)解。這時不必考慮整數(shù)約束運輸問題的主要特征：3.1.1運輸問題的建模7/16/202416定義3.1

凡是能排列成（其中互不相同，互不相同）形式的變量集合，稱為一個閉回路，其中諸變量稱為這個閉回路的頂點。圖3.3閉回路辨析圖（3）運輸問題的基本定理3.1.1運輸問題的建模7/16/202417閉回路的幾何特征：1、每一個頂點格子都是90°轉(zhuǎn)角點；2、每一行（或列）若有閉回路的頂點，則有兩個頂點；3、每兩個頂點格子的連線都是水平的或垂直的；4、閉回路中頂點的個數(shù)必為偶數(shù)。閉回路的代數(shù)性質(zhì)：性質(zhì)3.1

構(gòu)成閉回路的變量組對應(yīng)的列向量組必線性相關(guān)。3.1.1運輸問題的建模7/16/202418性質(zhì)3.2

若變量組中有一個部分組構(gòu)成閉回路，則該變量組對應(yīng)的列向量組是線性相關(guān)的。推論：若變量組對應(yīng)的列向量組線性無關(guān)，則該變量組一定不包含閉回路。該推論可以用反證法和性質(zhì)3.2得到。定義3.2在變量組中，若有某一個變量xij

是它所在的行（第i

行）或列（第j

列）組的一個孤立點。3.1.1運輸問題的建模7/16/202419性質(zhì)3.3若一變量組中不包含任何閉回路，則該變量組必有定理3.1變量組孤立點。對應(yīng)的列向量組線性無關(guān)的充要條件是該變量組中不包含任何閉回路。3.1.1運輸問題的建模7/16/202420既然運輸問題是線性規(guī)劃問題，當(dāng)然可以直接用單純形法求解。但運輸問題變量較多（如有20個產(chǎn)地50個銷地的運輸問題就有20×50＝1000個變量，直接求解效率不高。是一種根據(jù)運輸問題的特殊結(jié)構(gòu)進行優(yōu)化的單純形法，可以顯著而表上作業(yè)法就提高解題效率。其求解步驟也分為確定初始基可行解、最優(yōu)性判別和改善基可行解這三個主要步驟。3.1.2運輸問題的表上作業(yè)法7/16/202421產(chǎn)銷平衡的運輸問題有m+n-1個基變量，基變量非負，而其余為零?？捎脛澗€法（包括西北角法、最小元素法、沃格爾法）來確定初始基可行解中各基變量的位置和數(shù)值。每確定一個基變量的值，將供需平衡表中滿足需求的銷地所在列或搬運一空的產(chǎn)地所在行劃去。共m+n-1次線。確定下來的基變量的數(shù)值取該基變量對應(yīng)線路上現(xiàn)有的產(chǎn)地余量和銷地余量的最小值。01確定初始基可行解（1）

確定初始基本可行解7/16/2024221）西北角法西北角法（NorthwestCornerMethod）優(yōu)先滿足表中未劃去部分的左上角（西北角）空格的供銷需求。其目的只是找初始基可行解，不考慮優(yōu)化。為了在供求平衡表的基礎(chǔ)上，同時標注求解過程中所需的其他信息，將Ai和Bj的交叉格（Ai，Bj）中的運價cij放在該格的右上角，在該格子的左下角標注從Ai到Bj的線路的其他信息。01確定初始基可行解（1）

確定初始基本可行解7/16/202423例3.3試運用西北角法給出例3.1的初始可行方案。解：該運輸方案的總成本z=512（1）

確定初始基本可行解7/16/202424

Step1.找出目前未劃去的最小運價，設(shè)為cst①若產(chǎn)地余量>銷地余量，則銷地上運滿，填xst=銷地的余量，劃去第t列；②若產(chǎn)地余量<銷地余量，則產(chǎn)地全運出，填xst=產(chǎn)地的余量，劃去第s行；③若產(chǎn)地余量=銷地余量，填xst=產(chǎn)地/銷地的余量；因為同時滿足了產(chǎn)地和銷地的要求，同時劃去第s行和第t列。還要在同時劃去的第s行、第t列的任一其他空格添加一個0。Step2.重復(fù)step1直至，所有運價都劃去。

2）最小元素法基本步驟：（1）

確定初始基本可行解7/16/202425例3.4試運用最小元素法給出例3.1的初始可行方案。解：其計算結(jié)果如表3.7。表3.7最小元素法的供求平衡表（1）

確定初始基本可行解7/16/202426最小運價法的不足圖3.4一個簡單的運輸模型最小元素法可得:x11=1，x12=1，x22=2，總成本25；可是令x21=1，x12=2，x22=1，總成本20?？梢姡?dāng)只考慮最小運價線路的充分利用，而導(dǎo)致運價較小的線路（如該例中A2與B1，A1與B2之間線路）不能合理利用。（1）

確定初始基本可行解7/16/2024273）伏格爾（Vogel）法伏格爾法優(yōu)先滿足未劃去部分各產(chǎn)地（銷地）運出（運入）次小運價與最小運價的差值最大者的最小運價線路的物資調(diào)運。這種方法能一定程度地減少只顧使用最小運價線路，而導(dǎo)致某產(chǎn)地或銷地的最大次小運價線路上運輸量的增加導(dǎo)致的成本增加。例如，對圖3.4模型可以列出供求平衡表，如表3.8。（1）

確定初始基本可行解7/16/202428表3.8圖3.4模型的伏格爾法供求平衡表（1）

確定初始基本可行解7/16/202429例3.5

試運用伏格爾法給出例3.1的初始可行方案。（1）

確定初始基本可行解7/16/2024解：30如同一般目標函數(shù)最小化的線性規(guī)劃一樣，最小運輸成本問題的基可行解是否最優(yōu)可以根據(jù)非基變量檢驗數(shù)是否全部非負來判斷?；居虚]回路法和對偶變量法這兩種方法。1）閉回路法對每一個空格（非基變量）找從其出發(fā)，其余點為數(shù)字格（基變量）的閉合回路。具體操作為：從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進，只有碰到代表基變量的填入數(shù)字的格子才能向左或向右轉(zhuǎn)90°（當(dāng)然也可不改變方向）繼續(xù)前進，這樣繼續(xù)下去，直至回到出發(fā)的那個空格。02最優(yōu)性檢驗（2）

最優(yōu)性檢驗7/16/202431由此形成的封閉的折線構(gòu)成的閉回路。一個非基變量存在惟一的閉回路。令該非基變量變?yōu)?，相應(yīng)調(diào)整閉合回路上各個格子的運量，求出的總運輸費用的增量就是該非基變量的檢驗數(shù)。當(dāng)一個原非基變量xij變?yōu)?，其余基變量不變，（2）

最優(yōu)性檢驗7/16/202432例3.6試對例3.1用最小元素法求出的初始可行解進行最優(yōu)性檢驗解：因為非基變量x24的檢驗數(shù)為負數(shù)，所以該方案不是最優(yōu)方案。

（2）

最優(yōu)性檢驗7/16/2024332）對偶變量法（位勢法）有m個產(chǎn)地和n個銷地的產(chǎn)銷平衡的調(diào)運問題的對偶問題如下：對于一個基B，令（2）

最優(yōu)性檢驗7/16/202434由于基變量的檢驗數(shù)為零，對于m+n-1個基變量xij有：為求出m+n的變量，可任意令（相當(dāng)于劃去第行），解出其余這樣就可以用對偶變量來求所有非基變量的檢驗數(shù)是否非負。若都滿足，則最優(yōu)，否則還不是最優(yōu)，還要改善可行方案。（2）

最優(yōu)性檢驗7/16/202435表3.11對偶變量法檢驗數(shù)表由于，所有非基變量的檢驗數(shù)非負，所以該方案是一個最優(yōu)解。例3.7試檢驗例3.1中伏格爾法的解得到的運輸方案的最優(yōu)性。（2）

最優(yōu)性檢驗7/16/202436在所有為負值的檢驗數(shù)中，選其中最小的負檢驗數(shù)，以它對應(yīng)的非基變量為入基變量，然后以該非基變量所在格為出發(fā)點作一個閉回路。該原非基變量的運量的調(diào)整值等于閉回路頂點的序號中，所有偶數(shù)序號的頂點的調(diào)運量的最小值。同時，對閉回路中偶數(shù)/奇數(shù)序號頂點減/加該調(diào)整量，以保證產(chǎn)銷平衡。

（3）

改進的運輸方案7/16/202437例3.8試用閉回路法調(diào)整例3.1中最小元素法得到的可行方案。可以進一步驗證調(diào)整后的方案是最優(yōu)方案。（3）

改進的運輸方案7/16/2024381）無窮多最優(yōu)解當(dāng)某個非基變量的檢驗數(shù)為0時，該問題有無窮多最優(yōu)解。如表3.10中x11的檢驗數(shù)為0，表示該例有無窮多最優(yōu)解。只要把檢驗數(shù)為0的非基變量x11作為入基變量，調(diào)整運輸方案，就可得到另一個最優(yōu)方案。從出發(fā)，找到閉合路（4）

特殊情況的處理7/16/202439為了產(chǎn)銷平衡調(diào)整閉回路中其他變量的值，;其余變量不變。詳見表3.13。表3.13另一最優(yōu)解（4）

特殊情況的處理7/16/2024402）退化有兩種情況會出現(xiàn)某個基變量為零的退化情況。在用劃線法確定初始基可行解時，若某選擇的基變量所在格對應(yīng)的產(chǎn)地余量和銷地余量恰好相等。這時該基變量=產(chǎn)地余量，對應(yīng)產(chǎn)地和銷地都已平衡。但為了保證劃線法每確定一個基變量劃一線的原則，應(yīng)先劃去對應(yīng)產(chǎn)地所在行/銷地所在列，再在銷地所在列/產(chǎn)地所在行的其它格中任選一個填0作為退化的基變量，最后再劃去其所在的列/行。（4）

特殊情況的處理7/16/202441當(dāng)用閉回路法調(diào)整時，出現(xiàn)回路中偶數(shù)節(jié)點格中有多于1個等于最小值。這時入基變量取該最小值，導(dǎo)致有多個原基變量變?yōu)?。這時，只能選其中任一個為0的原基變量出基，而其余的作為退化的基變量必須在其所在格中填0，以保證基變量的個數(shù)不變。03改進運輸方案（4）

特殊情況的處理7/16/202442例3.9北方的某汽車制造集團企業(yè)有三個組裝廠，即A工廠、B工廠、C工廠，每年分別需要生活用煤和取暖用煤2000t，1000t，3000t，由山西省大同、陽泉兩處煤礦負責(zé)供應(yīng)。這兩處煤礦的價格和質(zhì)量都基本相同。兩處煤礦能供應(yīng)該化工企業(yè)的煤的數(shù)量，山西陽泉為4000t，山西大同為1500t，由煤礦至該化工企業(yè)的單位運價（百元／t）如表3.14所示。由于供不應(yīng)求，經(jīng)企業(yè)領(lǐng)導(dǎo)研究平衡決定A工廠供應(yīng)量不少于1500t，B工廠需要量應(yīng)全部滿足，C工廠供應(yīng)量可減少300t。試求：總運費為最低的調(diào)運方案。01需求可變的運輸問題3.1.3幾種特殊的運輸問題（1）需求可變的運輸問題7/16/202443解：主要步驟（1）判斷供需關(guān)系（2）分析各銷地的剛性、柔性需求（3）列出供需平衡表3.1.3幾種特殊的運輸問題7/16/202444拓展思考：（1）若C工廠為了能爭取到更多的煤，聲稱有多少煤都愿意買下，則如何寫出這種情況下的供需平衡及運價表。（2）若大同到C工廠的運輸線路因泥石流被破壞，則需要如何調(diào)整供需平衡及運價表。3.1.3幾種特殊的運輸問題7/16/202445其中，cij

為從i點運到j(luò)點的單位運價，si為發(fā)點i的供應(yīng)量，dj為收點j的需求量。

圖3.5轉(zhuǎn)運問題的網(wǎng)絡(luò)圖（2）轉(zhuǎn)運問題3.1.3幾種特殊的運輸問題7/16/202446轉(zhuǎn)運問題（TransshipmentProblem）將節(jié)點分為產(chǎn)地（發(fā)點）、銷地（收點）和轉(zhuǎn)運點。其中，任何節(jié)點都可以承擔(dān)轉(zhuǎn)運功能。轉(zhuǎn)運點的運出量等于運入量。發(fā)點的運出量大于運入量。收點的運入量大于運出量。因此，轉(zhuǎn)運問題關(guān)于運輸節(jié)點的約束也相應(yīng)分為發(fā)點約束、收點約束以及轉(zhuǎn)運點約束。（2）轉(zhuǎn)運問題3.1.3幾種特殊的運輸問題7/16/202447運輸問題模型是在經(jīng)濟管理中有著廣泛應(yīng)用的重要模型。因為與一般的線性規(guī)劃相比運輸問題模型在變量個數(shù)相同的條件下，表上作業(yè)法較單純形法簡單有效，所以，常常盡可能地將一些線性規(guī)劃問題化為運輸問題的模型。一些管理問題直接可體現(xiàn)為供給和需求的形式，如按合3.1.4運輸問題的應(yīng)用舉例7/16/2024同生產(chǎn)的生產(chǎn)計劃問題等。48例3.11某集團公司為降低設(shè)備采購的成本，對生產(chǎn)設(shè)備實行集中采購。采購部門計劃通過招標采購某種生產(chǎn)設(shè)備。共邀請了m家工廠來參加投標。假設(shè)各廠家提供的是同質(zhì)產(chǎn)品。每個廠家都提供了一份標書，在標書中注明了該廠單位產(chǎn)品的價格和按此價格所能提供的數(shù)量，設(shè)為ai。該采購部門將這些產(chǎn)品運往不同的n個地區(qū)的子公司，第j個地區(qū)的設(shè)備需求量為bj，運輸費用由該采購部門支付。根據(jù)這些標書，該部門應(yīng)該向哪些廠家訂貨，訂貨量各為多少？（1）

投標裁決問題7/16/202449從第i個廠家訂貨并往到第j個地區(qū)時的單位產(chǎn)品成本，cij。設(shè)決策變量xij為從第i個廠家訂貨后運至第j個地區(qū)的訂貨量，（i=1，…，m；j=1，…，n）。

解：（1）

投標裁決問題7/16/202450例3.12某數(shù)碼產(chǎn)品制造公司有3個分廠，生產(chǎn)A、B兩種數(shù)碼產(chǎn)品。生產(chǎn)方式分為正常生產(chǎn)和加班生產(chǎn)兩種，加班生產(chǎn)成本大于正常生產(chǎn)成本。現(xiàn)要制定兩個月的工作計劃：第一月A、B產(chǎn)品的需求量分別為200和600件，第二月A、B產(chǎn)品的需求量分別為400和700件。各廠生產(chǎn)A和B產(chǎn)品所需時間、可用時間數(shù)據(jù)由表3.1.20的數(shù)據(jù)給出。設(shè)兩種產(chǎn)品的單位產(chǎn)品制造時間都為1小時。如果在第一月生產(chǎn)第二月的產(chǎn)品，則需存放一個月，3個工廠的保管費分別為10，15和20元。試擬定生產(chǎn)計劃，使總成本最低。

（2）生產(chǎn)排程問題7/16/202451解：（2）生產(chǎn)排程問題7/16/202452例3.13某航空公司使用上海作為中轉(zhuǎn)樞紐，以最少的航班數(shù)滿足國內(nèi)北方城市和南方城市之間的航空出行需求。從上午10點到11點有四架分別來自哈爾濱、長春、吉林、沈陽的波音747客機將在上海虹橋機場降落。這些飛機上的乘客將分別去往福州、廣州、深圳、廈門。飛機的離場時間為11點30分到12點30分。表3.1.26列出了各個航班的乘客去往各目的地的情況表，即轉(zhuǎn)機情況表。例如，來自哈爾濱的飛機，若飛往廈門則有38人不轉(zhuǎn)機，剩下的去福州、廣州和深圳等城市的都需要轉(zhuǎn)機。此外，表中航班的出發(fā)地和目的地都是按時間的先后順序排列的。例如，福州在廣州之前表示去往福州的飛機將先于去往廣州的飛機起飛。表格中標記為“-”的兩個格子表示，由于來自沈陽的飛機到中轉(zhuǎn)站（上海）的時間最遲，已經(jīng)來不及在去福州和廣州的城市的飛機起飛前完成到這兩地的轉(zhuǎn)機流程。請問應(yīng)如何安排各航班離開虹口機場后的目的地，以使得在虹橋機場轉(zhuǎn)機的乘客數(shù)最少？（3）

機場航班轉(zhuǎn)機問題7/16/202453設(shè)xij是從北方城市i到南方城市j的線路上的“運量”，xij是取值為0或1的二值選擇變量。設(shè)cij為從北方城市i到南方城市j的線路上不轉(zhuǎn)機的人數(shù)。（3）

機場航班轉(zhuǎn)機問題7/16/2024解：54案例1新美電器公司是新進在中國南方崛起的智能家用電器公司。從一家小型科技創(chuàng)業(yè)企業(yè)起家，憑借其研發(fā)的家用智能機器人技術(shù)，首先在深圳建立了第一個制造基地。隨著業(yè)務(wù)的發(fā)展又在順德建立了第二個制造基地。為了覆蓋全國的市場，公司在北京、上海和廣州建立分銷中心，向9個目標客戶區(qū)銷售產(chǎn)品。這九個地區(qū)的編號分別為T1，...，T9。兩個生產(chǎn)基地的生產(chǎn)成本不同。深圳基地的單位生產(chǎn)成本為1050元，而順德基地由于有更熟練的工人和改進的新一代設(shè)備，單位生產(chǎn)成本比深圳少50元。公司的快速發(fā)展，曾一度使得公司高層無暇顧及分銷系統(tǒng)的效率。然后，隨著新的競爭對手的涌入，技術(shù)壁壘的突破，市場競爭日趨激烈。公司高層意識到需要將提高分銷系統(tǒng)的效率放在當(dāng)前日程中了。目前，深圳的一個季度的生產(chǎn)能力為30000臺，而順德的生產(chǎn)能力是20000臺。表3.22為公司統(tǒng)計的從各生產(chǎn)基地到3個分銷中心的單位產(chǎn)品的運輸價格。

北京上海廣州深圳基地423215順德基地-3512表3.22

從生產(chǎn)基地到分銷中心的運輸價格（單位：元/臺）3.1.5運輸問題的管理案例7/16/202455公司的市場部向高層提供了下個季度的各客戶地區(qū)的需求預(yù)測，詳見表3.23客戶地區(qū)需求客戶地區(qū)需求客戶地區(qū)需求T16300T41210T72750T24880T56120T88580T32130T64830T94460表3.23下季度需求預(yù)測表（單位：臺）從各分銷中心向各客戶地區(qū)的單位產(chǎn)品的運輸成本如表3.24所示。

T1T2T3T4T5T6T7T8T9北京321314460----上海525445602747343327廣州----5433242125表3.24分銷中心到各客戶區(qū)的運輸價格（單位：元）現(xiàn)有的分銷系統(tǒng)中北京負責(zé)T1，T2，T3，T4，上海負責(zé)T5，T6，T7，廣州負責(zé)T8，T9地區(qū)。每個客戶區(qū)都由唯一指定的分銷中心負責(zé)。3.1.5運輸問題的管理案例7/16/202456請根據(jù)已知的資料，幫助該公司高管做以下分析：（1）根據(jù)目前的分銷策略，為使得總的運輸成本最小，下個季度的制造和運輸方案是什么？（2）有些高管建議放棄客戶區(qū)必須由唯一指定的分銷中心負責(zé)的原則，認為可以讓客戶從任意可行的分銷中心拿貨。請給出按該意見實施前后在總成本上的差異。（3）公司想知道如果允許從生產(chǎn)基地到客戶區(qū)的直接供貨是否有利于提升效率。假設(shè)深圳到T2，順德到T8，T9的單位運輸成本分別為3.5，0.3，0.7元?？紤]這三條直供線路后，分銷的總成本能否減少。3.1.5運輸問題的管理案例7/16/2024573.2目標規(guī)劃(1)問題提出例3.15某公司分廠用一條生產(chǎn)線生產(chǎn)兩種產(chǎn)品A和B，每周生產(chǎn)線運行時間為60小時，生產(chǎn)一臺A產(chǎn)品需要4小時，生產(chǎn)一臺B產(chǎn)品需要6小時．根據(jù)市場預(yù)測，A、B產(chǎn)品平均銷售量分別為每周9、8臺，它們銷售利潤分別為12、18萬元。在制定生產(chǎn)計劃時，經(jīng)理考慮下述4項目標：3.2.1多目標規(guī)劃模型7/16/202459首先，產(chǎn)量不能超過市場預(yù)測的銷售量；其次，工人加班時間最少；第三，希望總利潤最大；最后，要盡可能滿足市場需求,當(dāng)不能滿足時,市場認為B產(chǎn)品的重要性是A產(chǎn)品的2倍．試建立這個問題的數(shù)學(xué)模型．3.2.1多目標規(guī)劃模型7/16/202460設(shè)決策變量x1，x2

分別為產(chǎn)品A，B的產(chǎn)量

MaxZ=12x1+18x2

s.t.4x1+6x2

60

x1

9x2

8

x1,x2

0容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T

到(3,8)T

所在線段上的點,最優(yōu)目標值為Z*=180,即可選方案有多種.在實際上,這個結(jié)果并非完全符合決策者的要求,它只實現(xiàn)了經(jīng)理的第一、二、三條目標，而沒有達到最后的一個目標。進一步分析可知，要實現(xiàn)全體目標是不可能的。3.2.1多目標規(guī)劃模型7/16/202461(2)目標規(guī)劃模型的基本概念

把例3.15的4個目標表示為不等式.仍設(shè)決策變量x1，x2

分別為產(chǎn)品A，B的產(chǎn)量.那么,

第一個目標為:x1

9，x2

8

；第二個目標為:4x1+6x2

60

；第三個目標為:希望總利潤最大，要表示成不等式需要找到一個目標上界，這里可以估計為252（=12

9+18

8），于是有

12x1+18x2

252；第四個目標為:x1

9，x2

8；3.2.1多目標規(guī)劃模型7/16/202462下面引入與建立目標規(guī)劃數(shù)學(xué)模型有關(guān)的概念．（1）正、負偏差變量d

+，d-

我們用正偏差變量d

+表示決策值超過目標值的部分；負偏差變量d-表示決策值不足目標值的部分。因決策值不可能既超過目標值同時又末達到目標值，故恒有d

+

d-＝0．（2）絕對約束和目標約束我們把所有等式、不等式約束分為兩部分：絕對約束和目標約束。3.2.1多目標規(guī)劃模型7/16/202463絕對約束指必須嚴格滿足的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。設(shè)例1中生產(chǎn)A，B產(chǎn)品所需原材料數(shù)量有限制，并且無法從其它渠道予以補充，則構(gòu)成絕對約束。目標約束目標規(guī)劃特有的，我們可以把約束右端項看作要努力追求的目標值，但允許發(fā)生正式負偏差，用在約束中加入正、負偏差變量來表示，于是稱它們是軟約束。3.2.1多目標規(guī)劃模型7/16/202464對于例3,15,我們有如下目標約束

x1

+d1--d1+=9(1)

x2+d2--d2+=8(2)

4x1+6x2

+d3--d3+=60(3)12x1+18x2+d4--d4+=252(4)3.2.1多目標規(guī)劃模型7/16/202465(3)優(yōu)先因子與權(quán)系數(shù)

對于多目標問題，設(shè)有L個目標函數(shù)f1,f2,

,fL,決策者在要求達到這些目標時，一般有主次之分。為此，我們引入優(yōu)先因子Pi

，i=1,2,

,L.無妨設(shè)預(yù)期的目標函數(shù)優(yōu)先順序為f1,f2,

,fL,我們把要求第一位達到的目標賦于優(yōu)先因子P1，次位的目標賦于優(yōu)先因子P2、…，并規(guī)定Pi>>Pi+1，i=1,2,

,L-1.

即在計算過程中,首先保證P1級目標的實現(xiàn)，這時可不考慮次級目標；而P2級目標是在實現(xiàn)P1級目標的基礎(chǔ)上考慮的，以此類推。當(dāng)需要區(qū)別具有相同優(yōu)先因子的若干個目標的差別時，可分別賦于它們不同的權(quán)系數(shù)wj

。優(yōu)先因子及權(quán)系數(shù)的值，均由決策者按具體情況來確定．3.2.1多目標規(guī)劃模型7/16/202466（4）目標規(guī)劃的目標函效．目標規(guī)劃的目標函數(shù)是通過各目標約束的正、負偏差變量和賦于相應(yīng)的優(yōu)先等級來構(gòu)造的．決策者的要求是盡可能從某個方向縮小偏離目標的數(shù)值。于是，目標規(guī)劃的目標函數(shù)應(yīng)該是求極?。篗inf＝f（d+，d-)

其基本形式有三種：3.2.1多目標規(guī)劃模型7/16/202467①要求恰好達到目標值，即使相應(yīng)目標約束的正、負偏差變量都要盡可能地小。這時取

Min（d++d-)；②要求不超過目標值，即使相應(yīng)目標約束的正偏差變量要盡可能地小。

這時取

Min（d+)；③要求不低于目標值，即使相應(yīng)目標約束的負偏差變量要盡可能地小。

這時取

Min（d-)；3.2.1多目標規(guī)劃模型7/16/202468

對于例3.15,我們根據(jù)決策者的考慮知第一優(yōu)先級要求Min（d1++d2+

)；第二優(yōu)先級要求Min（d3+

)；第三優(yōu)先級要求Min（d4-)；第四優(yōu)先級要求Min（d1-+2d2-)，這里,當(dāng)不能滿足市場需求時,市場認為B產(chǎn)品的重要性是A產(chǎn)品的2倍．即減少B產(chǎn)品的影響是A產(chǎn)品的2倍，因此我們引入了2:1的權(quán)系數(shù)。3.2.1多目標規(guī)劃模型7/16/202469綜合上述分析，可得到下列目標規(guī)劃模型

Minf=P1（d1++d2+

)+P2d3++P3d4-+P4（d1-+2d2-

)s.t.x1

+d1--d1+=9x2+d2--d2+=84x1+6x2

+d3--d3+=6012x1+18x2

+d4--d4+=252x1,x2

,di-,di+

0,i=1,2,3,4.

3.2.1多目標規(guī)劃模型7/16/202470(3)目標規(guī)劃模型的一般形式式中的第二行是L個目標約束，第三行是m個絕對約束，clj

和gl

是目標參數(shù)。3.2.1多目標規(guī)劃模型7/16/202471LP：MaxZ=100X1+

80X2

2X1+4X2

500s.t4X1+2X2

400X*=(50,100)X1,

X20Z*=13000

例3.16某工廠生產(chǎn)甲，乙兩種產(chǎn)品，受到金工和裝配有效工時限制。在單件收益已知的條件下，要求制定一個收益最大的計劃。具體數(shù)據(jù)見表3.27。

甲乙有效工時金工42400裝配24500收益10080

表3.41基本數(shù)據(jù)表3.2.1多目標規(guī)劃模型7/16/202472目標：去年總收益9000，增長要求11.1%

即：今年希望總收益不低于10000引入d+：決策超過目標值部分(正偏差變量)

d-：決策不足目標值部分(負偏差變量)目標約束：100X1+80X2-d++d-=10000

d+?d-=0d+,d-

03.2.1多目標規(guī)劃模型7/16/202473可得到目標規(guī)劃模型如下所示：3.2.1多目標規(guī)劃模型7/16/202474原材料價格上漲，超計劃要高價購買，所以要嚴格控制市場情況，產(chǎn)品Ⅰ銷售量下降，產(chǎn)品Ⅰ的產(chǎn)量不大于產(chǎn)品Ⅱ的產(chǎn)量盡可能達到并超過利潤計充分利用設(shè)備，不希望加班劃指標56千元例3.17某企業(yè)生產(chǎn)兩種產(chǎn)品，受到原材料供應(yīng)和設(shè)備限制。在單件利潤等有關(guān)數(shù)據(jù)已知的條件下，要求一個獲利最大的生產(chǎn)計劃。具體數(shù)據(jù)見表3.28。

ⅠⅡ資源擁有量原材料2111設(shè)備1210利潤810

表3.28基本數(shù)據(jù)表3.2.1多目標規(guī)劃模型7/16/202475建模：設(shè)定約束條件。(目標約束、絕對約束)規(guī)定目標約束優(yōu)先級建立模型

設(shè)X1，X2為產(chǎn)品Ⅰ，產(chǎn)品Ⅱ產(chǎn)量。3.2.1多目標規(guī)劃模型7/16/2024762X1+X2

11X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,

X2,

di-,

di+0di-?

di+=0d1-:X1產(chǎn)量不足X2部分d1+

:X1產(chǎn)量超過X2部分d2-:設(shè)備使用不足10

部分d2+

:設(shè)備使用超過10部分d3-:利潤不足56部分d3+

:利潤超過56部分或

MinZ1=d1+MinZ2=d2-+d2+

MinZ3=d3-

MinZ=p1d1++p2(d2-+d2+)+p3(d3-)3.2.1多目標規(guī)劃模型7/16/202477

對只具有兩個決策變量的目標規(guī)劃的數(shù)學(xué)模型，我們可以用圖解法來分析求解．通過圖解示例，可以看到目標規(guī)劃中優(yōu)先因子，正、負偏差變量及權(quán)系數(shù)等的幾何意義。下面用圖解法來求解例3.15我們先在平面直角坐標系的第一象限內(nèi)，作出與各約束條件對應(yīng)的直線，然后在這些直線旁分別標上G-i，i=1，2，3，4。圖中x，y分別表示問題的x1和x2；各直線移動使之函數(shù)值變大、變小的方向用+、-表示di+,di-．3.2.2幾何意義及圖解法7/16/202478圖105101520yx2015105+-G-1+-G-2+-G-3G-4+-3.2.2幾何意義及圖解法7/16/202479

下面我們根據(jù)目標函數(shù)的優(yōu)先因子來分析求解．首先考慮第一級具有P1優(yōu)先因子的目標的實現(xiàn)，在目標函數(shù)中要求實現(xiàn)Min（d1++d2+),取d1+=d2+=0.圖2中淺紅色陰影部分即表示出該最優(yōu)解集合的所有點。我們在第一級目標的最優(yōu)解集合中找滿足第二優(yōu)先級要求Min（d3+)的最優(yōu)解.取d3+=0

,可得到圖3中淺綠陰影部分即是滿足第一、第二優(yōu)先級要求的最優(yōu)解集合。3.2.2幾何意義及圖解法7/16/202480圖205101520yx2015105+-G-1+-G-2+-G-3G-4+-3.2.2幾何意義及圖解法7/16/202481圖305101520yx2015105+-G-1+-G-2+-G-3G-4+-3.2.2幾何意義及圖解法7/16/202482

第三優(yōu)先級要求Min（d4-)，根據(jù)圖示可知，d4-不可能取0值，我們?nèi)∈筪4-最小的值72得到圖4中兩陰影部分的交線(紅色粗線)，其表示滿足第一、第二及第三優(yōu)先級要求的最優(yōu)解集合。

最后，考慮第四優(yōu)先級要求Min（d1-+2d2-)，即要在黑色粗線段中找出最優(yōu)解。由于d1-的權(quán)因子小于d2-，因此在這里可以考慮取d2-=0。于是解得d1-=5，最優(yōu)解為A點x=3，y=8。3.2.2幾何意義及圖解法7/16/202483圖405101520yx2015105+-G-1+-G-2+-G-3G-4+-A(3,8)3.2.2幾何意義及圖解法7/16/202484目標規(guī)劃的數(shù)學(xué)模型,特別是約束的結(jié)構(gòu)與線性規(guī)劃模型沒有本質(zhì)的區(qū)別，只是它的目標不止是一個,雖然其利用優(yōu)先因子和權(quán)系數(shù)把目標寫成一個函數(shù)的形式,但在計算中無法按單目標處理,所以可用單純形法進行適當(dāng)改進后求解。

在組織、構(gòu)造算法時，我們要考慮目標規(guī)劃的數(shù)學(xué)模型一些特點，作以下規(guī)定：因為目標規(guī)劃問題的目標函數(shù)都是求最小化，所以檢驗數(shù)的最優(yōu)準則與線性規(guī)劃是相同的；3.2.3單純形法7/16/202485因為非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，Pi>>Pi+1，i=1,2,

,L-1.于是從每個檢驗數(shù)的整體來看：Pi+1（i=1,2,

,L-1）優(yōu)先級第k個檢驗數(shù)的正、負首先決定于P1

，P2，…，Pi

優(yōu)先級第k個檢驗數(shù)的正、負。若P1

級第k個檢驗數(shù)為0，則此檢驗數(shù)的正、負取決于P2級第k個檢驗數(shù)；若P2

級第k個檢驗數(shù)仍為0，則此檢驗數(shù)的正、負取決于P3級第k個檢驗數(shù)，依次類推。換一句話說，當(dāng)某Pi級第k個檢驗數(shù)為負數(shù)時，計算中不必再考察Pj（j>I

）級第k個檢驗數(shù)的正、負情況；根據(jù)目標規(guī)劃模型特征，當(dāng)不含絕對約束時，di-

（i=1,2,…,K）構(gòu)成了一組基本可行解。在尋找單純形法初始可行點時，這個特點是很有用的。3.2.3單純形法7/16/202486解目標規(guī)劃問題的單純形法的計算步驟:1)建立初始單純形表．在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行。初始的檢驗數(shù)需根據(jù)初始可行解計算出來，方法同基本單純形法。當(dāng)不含絕對約束時，di-

（i=1,2,…,K）構(gòu)成了一組基本可行解，這時只需利用相應(yīng)單位向量把各級目標行中對應(yīng)di-

（i=1,2,…,K）的量消成0即可得到初始單純形表。置k＝1；

2)檢查當(dāng)前第k行中是否存在小于0，且對應(yīng)的前k-1行的同列檢驗數(shù)為零的檢驗數(shù)。若有取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)3)。若無這樣的檢驗數(shù)，則轉(zhuǎn)5)；3.2.3單純形法7/16/2024873)按單純形法中的最小比值規(guī)則確定換出變量，當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量，轉(zhuǎn)4）；4)按單純形法進行換基運算，建立新的單純形表，（注意：要對所有的行進行初等變換運算）返回2)；5)當(dāng)k＝K時，計算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回2）。3.2.3單純形法7/16/202488例3.18試用單純形法來求解例3.15的目標規(guī)劃模型3.2.3單純形法7/16/202489解:首先處理初始基本可行解對應(yīng)的各級檢驗數(shù)。3.2.3單純形法7/16/202490（1）k=1，在初始單純形表中基變量為（d1-,d2-,d3-,d4-)T=（9，8，60，252)T

；（2）因為P1與P2優(yōu)先級的檢驗數(shù)均已經(jīng)為非負，所以這個單純形表對P1與P2優(yōu)先級是最優(yōu)單純形表；（3）下面考慮P3優(yōu)先級，第二列的檢驗數(shù)為-18，此為進基變量，計算相應(yīng)的比值bi/aij寫在

列。通過比較，得到d2-

對應(yīng)的比值最小，于是取a22（標為*號）為主元進行矩陣行變換得到新的單純形表；（4）下面繼續(xù)考慮P3優(yōu)先級，第一列的檢驗數(shù)為-12，此為進基變量，計算相應(yīng)的比值bi/aij

，得到d3-

對應(yīng)的比值最小，于是取a31（標為*號）為轉(zhuǎn)軸元進行矩陣行變換得到新的單純形表；3.2.3單純形法7/16/2024913.2.3單純形法7/16/202492（5）當(dāng)前的單純形表各優(yōu)先級的檢驗數(shù)均滿足了上述條件,故為最優(yōu)單純形表。我們得到最