XK上海交大運(yùn)籌學(xué)期末考試考研復(fù)習(xí)珍貴資料適合全國高?？佳?和期末【策劃稿】

1、 第五章 目標(biāo)規(guī)劃第一節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型具 體 案 例例1 某工廠生產(chǎn)，兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)見下表。試求獲利最大的生產(chǎn)方案。解： 這是求獲利最大的單目標(biāo)的規(guī)劃問題，用x1，x2分別表示，產(chǎn)品的產(chǎn)量，其線性規(guī)劃模型表述為： 用圖解法求得最優(yōu)決策方案為：x1*=4, x2*=3, z*=62(元)。 (4,3)實際上工廠在作決策時，要考慮市場等一系列其他條件 （1) 根據(jù)市場信息，產(chǎn)品的銷售量有下降的趨勢，故考慮產(chǎn)品的產(chǎn)量不大于產(chǎn)品。(2) 超過計劃供應(yīng)的原材料時，需用高價采購，會使成本大幅度增加。(3) 應(yīng)盡可能充分利用設(shè)備臺時，但不希望加班。 (4) 應(yīng)盡可能達(dá)到并超過計劃利潤指標(biāo)56元

2、。 這樣在考慮產(chǎn)品決策時，便為多目標(biāo)決策問題。目標(biāo)規(guī)劃方法是解這類決策問題的方法之一。下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念。 1.設(shè)x1，x2為決策變量，此外，引進(jìn)正、負(fù)偏差變量d+，d- 。正偏差變量d表示決策值超過目標(biāo)值的部分；負(fù)偏差變量d-表示決策值未達(dá)到目標(biāo)值的部分。因決策值不可能既超過目標(biāo)值同時又未達(dá)到目標(biāo)值，即恒有d+d-=0。2.絕對約束和目標(biāo)約束絕對約束是指必須嚴(yán)格滿足的等式約束和不等式約束；如線性規(guī)劃問題的所有約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。目標(biāo)約束是目標(biāo)規(guī)劃特有的，可把約束右端項看作要追求的目標(biāo)值。在達(dá)到此目標(biāo)值時允許發(fā)生正或負(fù)偏差，因

3、此在這些約束中加入正、負(fù)偏差變量，它們是軟約束。線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可變換為目標(biāo)約束。也可根據(jù)問題的需要將絕對約束變換為目標(biāo)約束。如：例1的目標(biāo)函數(shù)z=8x1+10 x2可變換為目標(biāo)約束8x1+10 x2+d1-d1+=56。約束條件2x1+x211可變換為目標(biāo)約束2x1+x2+d2-d2+=11。3.優(yōu)先因子(優(yōu)先等級)與權(quán)系數(shù)一個規(guī)劃問題常常有若干目標(biāo)。但決策者在要求達(dá)到這些目標(biāo)時，是有主次或輕重緩急的不同。要求第一位達(dá)到的目標(biāo)賦予優(yōu)先因子P1，次位的目標(biāo)賦予優(yōu)先因子P2，并規(guī)定PkPk+1,k=1,2,，K。表示Pk比Pk+1有更大的優(yōu)先權(quán)。即首先保

4、證P1級目標(biāo)的實現(xiàn)，這時可不考慮次級目標(biāo)；而P2級目標(biāo)是在實現(xiàn)P1級目標(biāo)的基礎(chǔ)上考慮的；依此類推。若要區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，這時可分別賦予它們不同的權(quán)系數(shù)j,這些都由決策者按具體情況而定。 4.目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)(準(zhǔn)則函數(shù))是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是min z=f(d+,d-)。其基本形式有三種： (1) 要求恰好達(dá)到目標(biāo)值，即正、負(fù)偏差變量都要盡可能地小，這時 min z=f(d+d-)(2) 要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，就

5、是正偏差變量要盡可能地小。這時min z=f(d+)(3) 要求超過目標(biāo)值，即超過量不限，但必須是負(fù)偏差變量要盡可能地小，這時min z=f(d-)對每一個具體目標(biāo)規(guī)劃問題，可根據(jù)決策者的要求和賦予各目標(biāo)的優(yōu)先因子來構(gòu)造目標(biāo)函數(shù)，以下用例子說明。 例2 ： 例1的決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮：首先：產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量；其次：充分利用設(shè)備有效臺時，不加班；再次：利潤額不小于56元。求決策方案 。解 按決策者所要求的，分別賦予這三個目標(biāo)P1，P2，P3優(yōu)先因子。這問題的數(shù)學(xué)模型是： 目標(biāo)規(guī)劃的一般數(shù)學(xué)模型為 為權(quán)系數(shù)。 第二節(jié) 目標(biāo)規(guī)劃的圖解法例 某電視機(jī)廠裝配黑白和彩色兩種電

6、視機(jī)，每裝配一臺電視機(jī)需占用裝配線1小時，裝配線每周計劃開動40小時。預(yù)計市場每周彩色電視機(jī)的銷量是24臺，每臺可獲利80元；黑白電視機(jī)的銷量是30臺，每臺可獲利40元。該廠確定的目標(biāo)為：第一優(yōu)先級：充分利用裝配線每周計劃開動40小時；第二優(yōu)先級：允許裝配線加班；但加班時間每周盡量不超過10小時；第三優(yōu)先級：裝配電視機(jī)的數(shù)量盡量滿足市場需要。因彩色電視機(jī)的利潤高，取其權(quán)系數(shù)為2。試建立這問題的目標(biāo)規(guī)劃模型，并求解黑白和彩色電視機(jī)的產(chǎn)量。 解 設(shè)x1，x2分別表示黑白和彩色電視機(jī)的產(chǎn)量。這個問題的目標(biāo)規(guī)劃模型為(d)0102030405060102030405060(a)(b)(c)(24, 2

7、6)滿足P1, P2的可行域滿足P1, P2, P3(c)的可行域目標(biāo)規(guī)劃的最優(yōu)解d1+d2+d4+資源甲乙資源限制設(shè)備臺時2412材料3312利潤（萬元/單位）43.2消耗定額產(chǎn)品443363.75212340 x1x2硬約束圍成區(qū)域內(nèi)，滿足第一等級目標(biāo)的區(qū)域。5滿足第一、二等級目標(biāo)的區(qū)域內(nèi)，能盡可能地滿足第三等級目標(biāo)的區(qū)域。這個區(qū)域僅包含點(2.4, 1.6 ).滿足第一等級目標(biāo)的區(qū)域內(nèi)，還滿足第二等級目標(biāo)的區(qū)域。這個區(qū)域是一條線段。例：前面的例2：滿意解為線段DG第3節(jié) 解目標(biāo)規(guī)劃的單純形法 目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要考

8、慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點，作以下規(guī)定：(1) 因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以以cj-zj0，j=1,2,，n為最優(yōu)準(zhǔn)則。(2) 因非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，即因P1P2PK；從每個檢驗數(shù)的整體來看：檢驗數(shù)的正、負(fù)首先決定于P1的系數(shù)1j的正、負(fù)。若1j=0，這時此檢驗數(shù)的正、負(fù)就決定于P2的系數(shù)2j的正、負(fù)，下面可依此類推。 解目標(biāo)規(guī)劃問題的單純形法的計算步驟：(1) 建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行，置k=1。(2) 檢查該行中是否存在負(fù)數(shù)，且對應(yīng)的前k-1行的系數(shù)是零。若有負(fù)數(shù)取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)(3)。若無負(fù)數(shù)，

9、則轉(zhuǎn)(5)。(3) 按最小比值規(guī)則確定換出變量，當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。(4) 按單純形法進(jìn)行基變換運(yùn)算，建立新的計算表，返回(2)。(5) 當(dāng)k=K時，計算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回到(2)。例:試用單純形法來求解例2。將例2的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型： 取xs，d1-，d2-，d3-為初始基變量，列初始單純形表，見表。 取k=1，檢查P1行的檢驗數(shù)，因該行無負(fù)檢驗數(shù)， 故轉(zhuǎn)(5)。 因k(=1)K(=3)，置k=k+1=2，返回到(2)。 當(dāng)k=2時,查出P2行檢驗數(shù)中有-1、-2； 取min(-1,-2)=-2。 它對應(yīng)

10、的變量x2為換入變量，轉(zhuǎn)入(3)。 在表上計算最小比值它對應(yīng)的變量d2-為換出變量，轉(zhuǎn)入(4) 即進(jìn)行基變換運(yùn)算，計算結(jié)果見表 返回到(2)，得到最終表最終表所示的解x1*=2，x2*=4為例1的滿意解。此解相當(dāng)于圖解中的G點。檢查最終表的檢驗數(shù)行，發(fā)現(xiàn)非基變量d3+的檢驗數(shù)為0，這表示存在多重解。以非基變量d3+為換入變量，d1-為換出變量，經(jīng)迭代得到下表。由上表得到解x1*=10/3，x2*=10/3，此解相當(dāng)于圖解中的D點，G、D兩點的凸線性組合都是例2的滿意解初始單純形表x1x2x3d1d1+d2d2+d3d3+檢驗數(shù)P11P210122P35681010000基變量x31121100

11、0000d10110110000d210120001100d3568100000011解:最終單純形表x1x2x3d1d1+d2d2+d3d3+P11P2111P31100000 x3300100221/21/2d1200011331/21/2x24010004/34/31/61/6x12100005/35/31/31/3第4節(jié) 靈敏度分析 目標(biāo)規(guī)劃的靈敏度分析方法與線性規(guī)劃相似，只是除分析各項系數(shù)的變化外，還有優(yōu)先因子的變化問題，下面舉例說明。 改變目標(biāo)優(yōu)先等級的分析。例 已知目標(biāo)規(guī)劃問題得到最終表表1。目標(biāo)函數(shù)的優(yōu)先等級變化為：(1) min z=P1(2d1+3d2+)+P2d4+P3d

12、3-(2) min z= P1d3-+P2(2d1+3d3+)+P3d4+試分析原解有什么變化。表1解 分析(1)，實際是將原目標(biāo)函數(shù)中d4+，d3-的優(yōu)先因子對換了一下。這時將表1的檢驗數(shù)中的P2、P3和cj行的P2、P3對換即可。這時可見原解仍滿足最優(yōu)解條件 (見表2)。表2分析(2)，將變化了的優(yōu)先等級直接反映到表1上。再計算檢驗數(shù)，得表3。然后進(jìn)行迭代（表4，5），直到求得新的滿意解（表6）x1*=4，x2*=12為止。表3表4表5表6第5節(jié) 應(yīng) 用 舉 例例 某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時，依次遵守以下規(guī)定：(1) 不超過年工資總額60000元；(2) 每級的人數(shù)不超過定

13、編規(guī)定的人數(shù)；(3) ，級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%，且無越級提升；(4) 級不足編制的人數(shù)可錄用新職工，又級的職工中有10%要退休。有關(guān)資料匯總于表中，問該領(lǐng)導(dǎo)應(yīng)如何擬訂一個滿意的方案。表解 設(shè)x1、x2、x3分別表示提升到、級和錄用到級的新職工人數(shù)。對各目標(biāo)確定的優(yōu)先因子為：P1不超過年工資總額60000元；P2每級的人數(shù)不超過定編規(guī)定的人數(shù)；P3、級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%。先分別建立各目標(biāo)約束。P1:年工資總額不超過60000元 2000(10-100.1+x1)+ 1500(12-x1+x2)+1000(15-x2+x3)+ d1-d1+ =60000P2：每級的人

14、數(shù)不超過定編規(guī)定的人數(shù)：對級有 10(1-0.1)+x1+d2-d2+=12對級有 12-x1+x2+d3-d3+=15對級有 15-x2+x3+d4-d4+=15P3：，級的升級面不大于現(xiàn)有人數(shù)的20%，但盡可能多提；對級有 x1+d5-d5+對級有 x2+d6-d6+目標(biāo)函數(shù)：min z=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-)以上目標(biāo)規(guī)劃模型可用單純形法求解，得到多重解。現(xiàn)將這些解匯總于表，這單位的領(lǐng)導(dǎo)再按具體情況，從表中選一個執(zhí)行方案 表例 已知三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間的供需量和單位運(yùn)價見表。有關(guān)部門在研究調(diào)運(yùn)方案時依次考慮以下七項目標(biāo)，規(guī)定其相應(yīng)

15、的優(yōu)先等級：P1B4是重點保證單位，必須全部滿足其需要；P2A3向B1提供的產(chǎn)量不少于100；P3每個銷地的供應(yīng)量不小于其需要量的80%；P4所定調(diào)運(yùn)方案的總運(yùn)費(fèi)不超過最小運(yùn)費(fèi)調(diào)運(yùn)方案的10%；P5因路段的問題，盡量避免安排將A2的產(chǎn)品往B4；P6給B1和B3的供應(yīng)率要相同；P7力求總運(yùn)費(fèi)最省。試求滿意的調(diào)運(yùn)方案。表解 表上作業(yè)法求得最小運(yùn)費(fèi)的調(diào)運(yùn)方案見表。這時得最小運(yùn)費(fèi)為2950元，再根據(jù)提出的各項目標(biāo)的要求建立目標(biāo)規(guī)劃的模型。表供應(yīng)約束（硬約束） x11+x12+x13+x14300 x21+x22+x23+x24200 x31+x32+x33+x34400需求約束：x11+x21+x31+d1-d1+=200 x12+x22+x32+d2-d2+=100 x13+x23+x33+d3-d3+=450P1：x14+x24+x34+d4-d4+=250P2：A3向B1提供的產(chǎn)品量不少于100 x31+d5-d5+=100P3：每個銷地的供應(yīng)量不小于其需要量的80%