運(yùn)籌學(xué)線性規(guī)劃.ppt

1、Operations Research 運(yùn)籌學(xué)（OR）,主講：邢延銘,管理科學(xué)與工程學(xué)院信息管理及信息系統(tǒng),第一章 線性規(guī)劃,1,一、線性規(guī)劃（Linear Programming),1947年由美國(guó)人丹齊克（Dantzing）提出,線性,x,y,O,x+y=1,1,1,x=2,y=3,2,3,規(guī)劃,LP(linear programming)的基本概念 LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟(jì)效益的優(yōu)化方法。 LP有三個(gè)要素: 決策變量、目標(biāo)函數(shù)、約束條件,二、 LP的數(shù)學(xué)模型難點(diǎn),例題1生產(chǎn)計(jì)劃問題,美佳公司計(jì)劃制造I、II兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用設(shè)備

2、A、B的臺(tái)時(shí)、調(diào)試時(shí)間、調(diào)試工序每天可用于這種家電的能力、各售出一件時(shí)的獲利情況，如表1-1所示。問該公司應(yīng)制造兩種家電各多少件，使其獲取的利潤(rùn)最大。,該計(jì)劃的數(shù)學(xué)模型,目標(biāo)函數(shù) Max Z = 2x1 + 1x2 約束條件 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1、 x2 0,x1,x2,例2 營(yíng)養(yǎng)配餐問題,假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場(chǎng)上只有四種食品可供選擇(當(dāng)然可以擴(kuò)充到n種食品），它們每千克所含的熱量和營(yíng)養(yǎng)成分和市場(chǎng)價(jià)格見下表。問如何選擇才能在滿足營(yíng)養(yǎng)的前提下使購買食品的費(fèi)用最??？,各種食物的營(yíng)養(yǎng)成分

3、表,解：設(shè)xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型為： min Z=14x1+6x2 +3x3+2x4 s.t. 1000 x1+800 x2 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1，x2 ， x3 ， x4 0,例3. 運(yùn)輸問題,某名牌飲料在國(guó)內(nèi)有三個(gè)生產(chǎn)廠，分布在城市A1、A2, A3,其一級(jí)承銷商有4個(gè)，分布在城市B1、B2、B3、B4，已知各廠的產(chǎn)量、各承銷商的銷售量及從Ai到Bj的每噸飲料運(yùn)費(fèi)為Cij，為發(fā)揮集團(tuán)優(yōu)勢(shì)，公司要統(tǒng)一籌劃運(yùn)銷問

4、題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。,(1)決策變量。設(shè)從Ai到Bj的運(yùn)輸量為xij， (2)目標(biāo)函數(shù)。則運(yùn)費(fèi)最小的目標(biāo)函數(shù)為 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)約束條件。產(chǎn)量之和等于銷量之和,故要滿足： 供應(yīng)平衡條件,x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3,銷售平衡條件,x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=1,非負(fù)性約束 xij0 (i=1,2,3；j=1,2,

5、3,4),例4.倉庫租用問題 捷運(yùn)公司擬在下一年度的1-4月的4個(gè)月內(nèi)需租用倉庫堆放物資.已知各月份所需倉庫面積數(shù)列于表1.倉庫租借費(fèi)用隨合同期而定,期限越長(zhǎng),折扣越大,具體數(shù)字見表2.租借倉庫的合同每月初都可辦理,每份合同具體規(guī)定租用面積數(shù)和期限.因此該廠可根據(jù)需要,在任何一個(gè)月初辦理租借合同.每次辦理時(shí)可簽一份,也可簽若干份租用面積和租借期限不同的合同,試確定該公司簽訂租借合同的最優(yōu)決策,目的是使所付租借費(fèi)用最小.,表1,表2,解:1)設(shè)決策變量xij表示捷運(yùn)公司在第i(i=1,2,3,4)個(gè)月初簽訂的租借期為j(j=1,2,3,4)個(gè)月的倉庫面積的合同(單位為100m2). 因5月份起該

6、公司不需要租借倉庫,故x24,x33,x34,x42,x43,x44均為零,2)目標(biāo)函數(shù):使總的租借費(fèi)用最小,3)約束條件:每個(gè)月份所需倉庫面積的限制,s.t.,例5.合理下料問題,合理下料問題（Reasonably Cutting Problem）某型號(hào)的圓鋼8米長(zhǎng)，需截取長(zhǎng)2.5米、長(zhǎng)2.0米、長(zhǎng)1.3米的毛坯分別為100根、150根、200根。 問： 如何下料，才能既滿足需求，又使總用料最少 如何下料，才能既滿足需求，又使總余料最少,此型號(hào)的圓鋼8米長(zhǎng)，截取的方案有：,四、線性規(guī)劃的一般形,線性規(guī)劃問題的數(shù)學(xué)模型有各種不同的形式，如 目標(biāo)函數(shù)有極大化和極小化； 約束條件有“”、“”和“”

7、三種情況； 決策變量一般有非負(fù)性要求，有的則沒有。,為了求解方便，特規(guī)定一種線性規(guī)劃的標(biāo)準(zhǔn)形式，非標(biāo)準(zhǔn)型可以轉(zhuǎn)化為標(biāo)準(zhǔn)型。 標(biāo)準(zhǔn)形式為： 目標(biāo)函數(shù)極大化， 約束條件為等式， 右端常數(shù)項(xiàng)bi0， 決策變量非負(fù)。,五、線性規(guī)劃問題的標(biāo)準(zhǔn)形式,標(biāo)準(zhǔn)形式為:,目標(biāo)函數(shù)最大 約束條件等式 決策變量非負(fù) 右端常數(shù)非負(fù),目標(biāo)函數(shù)極小化問題 minZ=CX，只需將等式兩端乘以 -1 即變?yōu)闃O大化問題。 右端常數(shù)項(xiàng)非正 兩端同乘以 -1 約束條件為不等式 -當(dāng)約束方程為“”時(shí)，左端加入一個(gè)非負(fù)的松弛變量； -當(dāng)約束條件為“”時(shí)，左端減去一個(gè)非負(fù)的剩余變量。 決策變量xk無約束 令xk=xk-x k，xk，x k

8、 0，用xk、x k 取代模型中xk 決策變量xk0 令xk=-xk,顯然xk 0,非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化,例：目標(biāo)函數(shù) Max Z = 2x1 + 1x2 約束條件 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1、 x2 0,化為標(biāo)準(zhǔn)型：目標(biāo)函數(shù) Max Z = 2x1 + 1x2 約束條件 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 =5 x1、 x2、x3、x4、x5 0,+0 x3+0 x4+0 x5,Max,例 2：,解 ：化為標(biāo)準(zhǔn)形為,作業(yè)：習(xí)題1.2中的（1）（2）,簡(jiǎn)寫為,用矩陣表示,C價(jià)值向量 b資源向量 X決

9、策變量向量 A技術(shù)矩陣 P 技術(shù)向量,用向量表示,六、線性規(guī)劃的圖解法,由中學(xué)知識(shí)可知：y=ax+b是一條直線，同理：Z=2x1+x2x2=Z-2x1也是一條直線，以Z為參數(shù)的一族等值線。 5x2 15 x2 3 是直線 x2=3 下方的半平面。 所有約束的半平面的交集稱之為可行域，可行域內(nèi)的任意一點(diǎn)，就是滿足所有約束條件的解，稱之為可行解。,例：目標(biāo)函數(shù) Max Z = 2x1 + 1x2 約束條件 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1、 x2 0,目標(biāo)函數(shù) Max Z = 2x1 + 1x2,可以先假設(shè) 2x1 + 1x2=4,再假設(shè) 2x1 + 1x2=6,2

10、x1 + 1x2=8,由圖中可知目標(biāo)函數(shù)相交于Q2這一點(diǎn)上，由6x1 + 2x2 = 24 x1 + x2 = 5 聯(lián)合求解得到為（x1,x2)=(3.5,1.5),則目標(biāo)函數(shù)為z=8.5,圖解法求解步驟,由全部約束條件作圖求出可行域； 作目標(biāo)函數(shù)等值線，確定使目標(biāo)函數(shù)最優(yōu)的移動(dòng)方向； 平移目標(biāo)函數(shù)的等值線，平行線移出可行域之前的最后一個(gè)交點(diǎn)，就是最優(yōu)點(diǎn)，算出最優(yōu)值。,七、線性規(guī)劃問題求解的 幾種可能結(jié)果,1、唯一最優(yōu)解（見上頁） 2、多重最優(yōu)解：無窮多個(gè)最優(yōu)解。若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線上的每一點(diǎn)都是最優(yōu)解。,3、無界解：線性規(guī)劃問題的可行域無界，使目標(biāo)函數(shù)無限增大而無界。（缺乏

11、必要的約束條件）,4、無解（或無可行解）：若約束條件相互矛盾，則可行域?yàn)榭占?圖解法的幾點(diǎn)結(jié)論:（由圖解法得到的啟示）,可行域是有界或無界的凸多邊形。 若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點(diǎn)得到。 若兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則其連線上的所有點(diǎn)都是最優(yōu)解。 解題思路：找出凸集的頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值，比較即得。,練習(xí)：用圖解法求解LP問題,圖解法 （練習(xí)）,圖解法 （練習(xí)）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,可行域,A,B,C,D,E,圖解法 （

12、練習(xí)）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),34x1 + 40 x2 = 272,圖解法 （練習(xí)）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),圖解法 （練習(xí)）,x2,18 16 14 12 10 8 6 4 2 0,| 246810121

13、41618,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,(0,6.8),最優(yōu)解 (3,6),4x1+ 6x2=48 2x1+ 2x2 =18,1.3線性規(guī)劃解的概念及基本定理,可行解：滿足約束條件AX=b,X0的解。 最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。,基 mn，且m個(gè)方程線性無關(guān)，即矩陣A的秩為m；根據(jù)線性代數(shù)定理可知，nm，則方程組有多個(gè)解，這也正是線性規(guī)劃尋求最優(yōu)解的余地所在。 若B是矩陣A中mm階非奇異子矩陣（B0），則B是線性規(guī)劃問題的一個(gè)基。不妨設(shè)：, j=1，2，,m 基向量。 ，j=1，2，,m 基變量。 , j=

14、m+1,n 非基變量。,線性方程組的增廣矩陣,例LP的標(biāo)準(zhǔn)型 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0,基矩陣： 系數(shù)矩陣A中任意m列所組成的m階非奇異子矩陣，稱為該線性規(guī)劃問題的一個(gè)基矩陣。 或稱為一個(gè)基，用B表示。 稱基矩陣的列為基向量，用Pj表示(j=1,2,m) 。,的基矩陣B，如下：,基變量： 與基向量Pj相對(duì)應(yīng)的m個(gè)變量xj稱為基變量， 其余的n-m個(gè)變量為非基變量。 基解： 令所有非基變量等于零，對(duì)m個(gè)基變量所求的解， 對(duì)應(yīng)一個(gè)

15、特定的基矩陣能求得一組唯一解，這個(gè)對(duì)應(yīng)于基的解稱為基解。,基變量是x3, x4, x5 非基變量是x1, x2 令非基變量x1=x2=0，得到一個(gè)基解 x3=8，x4=12， x5=36,基可行解：滿足非負(fù)性約束的基解稱為基可行解。 可行基：對(duì)應(yīng)于基可行解的基，稱為可行基。 最優(yōu)基：最優(yōu)解對(duì)應(yīng)的基矩陣，稱為最優(yōu)基。,非 可 行 解,可 行 解,基 解,例：求基解、基可行解、最優(yōu)解。,最優(yōu)解,解：,二、凸集及其頂點(diǎn),凸集概念： 設(shè)D是n維線性空間Rn的一個(gè)點(diǎn)集，若D中的任意兩點(diǎn)x(1),x(2)的連線上的一切點(diǎn)x仍在D中，則稱D為凸集。 即：若D中的任意兩點(diǎn)x(1),x(2) D，存在01 使得

16、 x= x(1)+(1- )x(2) D,則稱D為凸集,頂點(diǎn):若K是凸集，XK；若X不能用不同的兩點(diǎn)的線性組合表示為： 則X為頂點(diǎn).,凸集,三、幾個(gè)基本定理的證明,證明:,定理1: 若線性規(guī)劃問題存在可行域, 則其可行域: 是凸集.,只要驗(yàn)證X在D中即可,引理：可行解X為基可行解 X的正分量對(duì)應(yīng)的列向量線性無關(guān),定理3：若可行域有界，線性規(guī)劃 問題的目標(biāo)函數(shù)一定可以在 其可行域的頂點(diǎn)上達(dá)到最優(yōu)。,定理2：線性規(guī)劃問題的基可性解X 對(duì)應(yīng)于可行域D的頂點(diǎn)。,幾點(diǎn)結(jié)論：,線性規(guī)劃問題的可行域是凸集。 基可行解與可行域的頂點(diǎn)一一對(duì)應(yīng)，可行域有有限多個(gè)頂點(diǎn)。 最優(yōu)解必在頂點(diǎn)上得到。,1.4單純形法的基本

17、原理,單純形法(Simplex Method)是美國(guó)人丹捷格 (G.Dantzig)1947年創(chuàng)建的 這種方法簡(jiǎn)捷、規(guī)范，是舉世公認(rèn)的解決線性規(guī)劃問題行之有效的方法。,例1的標(biāo)準(zhǔn)型 ： 目標(biāo)函數(shù) Max Z = 2x1 + 1x2+0 x3+0 x4+0 x5 約束條件 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 =5 x1、 x2、x3、x4、x5 0,LP的代數(shù)方法,定理1.線性規(guī)劃問題如果存在可行域，則其 可行域一定是一個(gè)凸集。 定理2.線性規(guī)劃問題的基可行解與凸集頂點(diǎn)是一一對(duì)應(yīng)的。 定理3.線性規(guī)劃問題如果存在最優(yōu)解，則一定存在一個(gè)基可

18、行解是最優(yōu)解。（或者說最優(yōu)解如果存在，一定出現(xiàn)在凸集的頂點(diǎn)上）。,線性規(guī)劃問題求最優(yōu)解思路,step1.找到一個(gè)初始的基可行解。 step2.判斷是否最優(yōu)。 如果最優(yōu)，則結(jié)束。否則轉(zhuǎn)step3。 Step3.轉(zhuǎn)到與初始基可行解相鄰的下一個(gè)基可行解，轉(zhuǎn)化時(shí)應(yīng)遵循目標(biāo)函數(shù)值增大的原則。,1.確定初始基可行解,對(duì)標(biāo)準(zhǔn)型線性規(guī)劃問題 在約束中總存在一個(gè)單位矩陣 我們以這個(gè)單位矩陣為基矩陣，令非基變量都=0，得到一個(gè)初始基解 因?yàn)閎=0，所以這個(gè)基解是一個(gè)基可行解。,標(biāo)準(zhǔn)形式為:,2.從一個(gè)基可行解轉(zhuǎn)換為相鄰的基可行解,定義：如果兩個(gè)基可行解之間的變換只需要變換一個(gè)基變量，則稱這兩個(gè)基可行解相鄰。,3.

19、最優(yōu)性檢驗(yàn),將兩個(gè)基可行解分別帶入目標(biāo)函數(shù)中得：,代入目標(biāo)消去基變量，得到非基變量xj的檢驗(yàn)數(shù) j。,判斷最優(yōu)（即規(guī)則） 會(huì)出現(xiàn)以下四種情況： （1）若對(duì)于一 切非基變量的解指數(shù)j均有j 0 則當(dāng)前基本 可行解為最優(yōu)解。 （2）若所有非基變量的檢測(cè)驗(yàn)數(shù) j 0，其中某個(gè)基變量的檢驗(yàn)數(shù) k=0，而該變量的系數(shù)列向量Pk中存在正分量，則說明該問題在兩個(gè)頂點(diǎn)上同時(shí)達(dá)到最優(yōu)，該問題有無窮多最優(yōu)解。,（3）若某個(gè)非基變量XK的檢驗(yàn)數(shù)k 0，但其對(duì)應(yīng)的列向量PK中，每一個(gè)元素aik(I=1,2,3m)均為非正數(shù)，這時(shí)該線性規(guī)劃問題無解。 （4）若存在非基變量檢驗(yàn)數(shù)k 0，其對(duì)應(yīng)的系數(shù)列向量Pk中，至少有一

20、個(gè)aik0,則問題還沒有得到最優(yōu)解，應(yīng)進(jìn)行下步。,基變換,（1）換入變量的確定 以k對(duì)應(yīng)的非基變量xk做為換入變量，當(dāng)然任選也可以，或選取腳標(biāo)最小的一個(gè) （2）換出變量的確定 改進(jìn)目標(biāo) 換入變量xk原是非基變量，取值為0，現(xiàn)在將其作為基變量，取值為正。要保持除xk以外的原非基變量繼續(xù)為0，迫使某個(gè)原基變量為0，當(dāng)xk取值超過任一bi/aik時(shí)，將使第i個(gè)基變量xBi0，就破壞了非負(fù)性約束條件。所以，比值i=bi/aik表示用xk去替換xBi時(shí)的取值限度，為保持解的可行性，取,即原其變量xl出基，為了表示清楚用Xbl表示換出變量，即規(guī)則 若不存在, 則Z，沒有有限最優(yōu)解。,主元變換（迭代或旋轉(zhuǎn)變

21、換） xk進(jìn)基， xl出基，其相應(yīng)的系數(shù)列向量分別是,為了使Xk和XBl進(jìn)行對(duì)換，須把Pk變?yōu)閱挝涣邢蛄?，這可以通過系數(shù)矩陣的初等變換變來完成,1,alk,將上式中的第L行除以alk,得到,用第I行減去aik與上式的乘積，各行元素的變換關(guān)系式為,變換后新的增廣矩陣為：,這樣就進(jìn)行了一次新的變換。另非基變量都為0，就會(huì)得到新的一組其可行解。,LP的表格法,表格單純形法，是對(duì)上節(jié)討論的方法步驟進(jìn)行具體化、規(guī)范化、表格化的結(jié)果。,一、單純形法表,將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。 找出或構(gòu)造一個(gè)m階單位矩陣作為初始可行基，建立初始單純形表。 計(jì)算各非基變量xj的檢驗(yàn)數(shù)j=Cj-CBB-1Pj ，若所有j0，

22、則問題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步。 在大于0的檢驗(yàn)數(shù)中，若某個(gè)k所對(duì)應(yīng)的系數(shù)列向量Pk0，則此問題是無解，停止計(jì)算，否則轉(zhuǎn)入下步。 根據(jù)maxjj0=k原則，確定xk為換入變量(進(jìn)基變量)，再按規(guī)則計(jì)算：=minbi/aik| aik0=bl/ alk 確定xBl為換出變量。建立新的單純形表，此時(shí)基變量中xk取代了xBl的位置。 以alk為主元素進(jìn)行迭代，把xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄浚碼lk變?yōu)?，同列中其它元素為0，轉(zhuǎn)第 步。,二、單純形法的計(jì)算步驟,三、單純形法計(jì)算舉例,例：目標(biāo)函數(shù) Max Z = 2x1 + 1x2 約束條件 5x2 15 6x1 + 2x2 24 x

23、1 + x2 5 x1、 x2 0,化為標(biāo)準(zhǔn)型：目標(biāo)函數(shù) Max Z = 2x1 + 1x2+0 x3+0 x4+0 x5 約束條件 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 =5 x1、 x2、x3、x4、x5 0,填入初始單純形表,最優(yōu)解 :X*=(3.5,1.5,7.5,0,0)T，Z*=8.5,表準(zhǔn)化 maxZ= 3x1 +2 x2 -2x1 + x2 + x3 =2 x1 -3 x2 + x4 =3 x1 , x2 , x3, x4 0,此時(shí)，檢驗(yàn)數(shù)2=11 0，還沒有得到最優(yōu)解。 確定x2進(jìn)基，但x2所在列的系數(shù)向量元素非正，無界

24、 值不存在，有進(jìn)基變量但無離基變量。,1.5人工變量問題,一、人工變量,用單純形法解題時(shí)，需要有一個(gè)單位陣作為初始基。 當(dāng)約束條件都是“”時(shí)，加入松弛變量就形成了初始基。 但實(shí)際存在“”或“”型的約束，沒有現(xiàn)成的單位矩陣。,問題：線性規(guī)劃問題 化為標(biāo)準(zhǔn)形時(shí)，若約束 條件的系數(shù)矩陣中不存 在單位矩陣，如何構(gòu)造 初始可行基？,采用人造基的辦法：人工構(gòu)造單位矩陣 在沒有單位列向量的等式約束中加入人工變量，構(gòu)成原線性規(guī)劃問題的伴隨問題，從而得到一個(gè)初始基。 人工變量是在等式中人為加進(jìn)的，只有它等于0時(shí)，約束條件才是它本來的意義。,加入 人工變量,設(shè)線性規(guī)劃問題的標(biāo)準(zhǔn)型為：,系數(shù)矩陣為 單位矩陣， 可構(gòu)

25、成初始 可行基。,約束條件已改變， 目標(biāo)函數(shù)如何調(diào)整？,“懲罰” 人工變量！,（1）大M法 （2）兩階段法,一、大 M 法,人工變量在最大化的目標(biāo)函數(shù)中的系數(shù)為 M（最小化的為+M）, 其中，M 為任意大的正數(shù)。,目標(biāo)函數(shù)中添加“罰因子” 最大化-M（M是任意大的正數(shù)） 為人工變量系數(shù)，只要人 工變量0，則目標(biāo)函數(shù) 不可能實(shí)現(xiàn)最優(yōu)。,例: 求解線性規(guī)劃問題,加入松弛變量和剩余變量,化成標(biāo)準(zhǔn)型,加入人工變量構(gòu)造初始可行基.,求解結(jié)果出現(xiàn)檢驗(yàn)數(shù)非正 若基變量中含非零的人工變量， 則無可行解； 否則，有最優(yōu)解。,用單純形法求解（見下頁）。,目標(biāo)函數(shù)中添加“罰因子” -M為人工變量系數(shù)，只要人 工變量

26、0，則目標(biāo)函數(shù) 不可能實(shí)現(xiàn)最優(yōu)。,表1（初始單純形表）,主元,表2,主元,表3,主元,表4,最優(yōu)解為 目標(biāo)函數(shù) 值 z=2,檢驗(yàn)數(shù)均非正，此為最終單純形表,M在計(jì)算機(jī)上處理困難。 分階段處理 先求初始基，再求解。,二、兩階段法,第一階段: 構(gòu)造如下的線性規(guī)劃問題,加入人工變量 后的系數(shù)矩陣 為單位矩陣， 可構(gòu)成初始 可行基。,目標(biāo)函數(shù)僅含人工變量，并要求實(shí)現(xiàn)最小化。 若其最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，則原線性規(guī)劃問題無可行解。,用單純形法求解上述問題,若=0,進(jìn)入第二階段,否則,原問題無可行解。 第二階段：去掉人工變量，還原目標(biāo)函數(shù)系數(shù)，做出初始單純形表。

27、用單純形法求解即可。,下面舉例說明，仍用大M法的例。,例：,加入松弛變量和剩余變量,化成標(biāo)準(zhǔn)型,解：,構(gòu)造第一階段問題并求解,注意，此時(shí)目標(biāo)函數(shù)不滿足標(biāo)準(zhǔn)型條件，所以應(yīng)將目標(biāo)函數(shù)也化成標(biāo)準(zhǔn)型 用單純形法求解,（第一階段、求min ）,表1,主元,1 0 0 0 -1 1 0 0 0,0 -1 0,0 0 -1,x4 x5 x6,（第一階段、求min ）,表2,主元,1 -2 2 0 -1 1 0 0 0,0 0 -1,0 0 -1,x4 x5 x6,（第一階段、求min ）,表3：最終單純形表,進(jìn) 入 第 二 階 段,不含人工變量且=0,第二階段,將去掉人工變量， 還原目標(biāo)函數(shù)系數(shù)，做 出初始

28、單純形表。,1 0 0 0 -1,1/3 -2/3 0 -1 2/3 -4/3,0 0,x4 x5,第二階段,0 0 0 -1/3 -1/3,最優(yōu)解為 目標(biāo)函數(shù) 值 z=2,最優(yōu)基,x3,x1,x2,最優(yōu)基的逆,LP補(bǔ)遺,進(jìn)基變量相持： 單純形法運(yùn)算過程中，同時(shí)出現(xiàn)多個(gè)相同的j最大。 在符合要求的j(目標(biāo)為max：j0，min：j0)中，選取下標(biāo)最小的非基變量為換入變量；,離基變量相持： 單純形法運(yùn)算過程中，同時(shí)出現(xiàn)多個(gè)相同的最小值。 繼續(xù)迭代，便有基變量為0，稱這種情況為退化解。 選取其中下標(biāo)最大的基變量做為換出變量。,多重最優(yōu)解： 最優(yōu)單純形表中，存在非基變量的檢驗(yàn)數(shù)j=0。 讓這個(gè)非基變

29、量進(jìn)基，繼續(xù)迭代，得另一個(gè)最優(yōu)解。,無界解： 在大于0的檢驗(yàn)數(shù)中，若某個(gè)k所對(duì)應(yīng)的系數(shù)列向量Pk0，則此問題是無界解。,無可行解： 最終表中存在人工變量是基變量。,1.6單純形法矩陣描述,為進(jìn)一步加深對(duì)單純形法的理解以及為對(duì)偶理論和靈敏度分析打基礎(chǔ)，現(xiàn)在用矩陣形式描述單純形法的求解過程。前面講過線規(guī)劃標(biāo)準(zhǔn)型的矩陣表達(dá)式為,對(duì)于上式移項(xiàng)得,再左乘以B-1,代入目標(biāo)函數(shù)得,單純形表的矩陣形式,例：,(1)、, 1 =C1 - CB B-1P1 =40 -(0 0 50) = 40 -(0,0,25) =40, A= C - CB B-1A=(40, 50, 0, 0, 0)- (0, 0, 50)

30、 =(40, 50, 0, 0, 0) -(0 0 25) = (40, 50, 0, 0, 0) -(0, 50, 0, 0, 25) = (40, 0, 0, 0, -25),1 2 1 0 0 3 2 0 1 0 0 2 0 0 1,1 2 1 0 0 3 2 0 1 0 0 2 0 0 1,B1-1,B2-1,B3-1,(1)、只須存貯原始數(shù)據(jù)A、B、C，每步需知B-1 。,(2)、每步必須計(jì)算的數(shù)據(jù), 當(dāng)某個(gè) m+k 0時(shí)，需關(guān)鍵列：,1.6單純形法小結(jié),基本概念,線性規(guī)劃模型 三個(gè)要素： 決策變量、目標(biāo)函數(shù)、約束條件 線性性 線性規(guī)劃解的性質(zhì) 線性規(guī)劃問題的可行域是凸集。,最優(yōu)解必

31、在頂點(diǎn)上得到。 線性規(guī)劃求解方法 圖解法 單純形法,本次習(xí)題課內(nèi)容,單純形法小結(jié),一般線性規(guī)劃問題的標(biāo)準(zhǔn)化及初始單純形法表.,變量, 約束條件,目標(biāo)函數(shù),單純形法計(jì)算步驟框圖（下頁）,單純形法小結(jié),LP的習(xí)題課,極小化線性規(guī)劃求解方法,極小化問題與極大化問題的解法，主要有一點(diǎn)區(qū)別，那就是進(jìn)基變量的選取。由式 可知，若以極大化為目標(biāo)，則當(dāng)所有非基變量的檢驗(yàn)數(shù)j0時(shí)，Z值達(dá)到最大。反之，若以極小化為目標(biāo)，則當(dāng)某個(gè)非基變量檢驗(yàn)數(shù)j0時(shí)，若取xj0，將使Z值進(jìn)一步變小，即使目標(biāo)進(jìn)一步優(yōu)化；,當(dāng)所有非基變量檢驗(yàn)數(shù)j0時(shí)，若使任意非基變量xj0都會(huì)導(dǎo)致目標(biāo)函數(shù)的增加從而偏離了極小化目標(biāo)，于是可以認(rèn)定此時(shí)的

32、解為最優(yōu)解。 總而言之，極小化問題的判別準(zhǔn)則是：j0 (j=1，2，n)時(shí)為最優(yōu)，進(jìn)基變量的選取是在負(fù)檢驗(yàn)數(shù)中選取最小的一個(gè)k，它所對(duì)應(yīng)的變量xk為換入變量。,舉例：,填入初始單純形表,所有的檢驗(yàn)數(shù)大于0,得到最優(yōu)解 X1=2/5 X2=38/5 Z=-30,一、已知某LP的初始單純形表和單純形法 迭代的表，求未知數(shù)al的值。,b=2,1 0,2,c/2=2 c=4,4,d/2=-1 d=-2,-2,-2a-1=-7 a=3,3,3,5,0,g=1 h=0,1=-1+e e=2,2,5,-3/2,解：,二、考慮LP問題 模型中 為參數(shù)，要求： （a）組成兩個(gè)新的約束(1)=(1)+(2), (

33、2)= (2)- 2(1) , 根據(jù) (1),(2) ，以 為 基變量，列出初始單純形表；,（b）在表中，假定 ，則 為何值時(shí)， 為問題的最優(yōu)基； （c）在表中，假定 ，則 為何值時(shí)， 為問題的最優(yōu)基；,解：（a）兩個(gè)新的約束,以 為基變量，初始單純形表如下：,（b） 時(shí)， 最優(yōu)基不變,（c） 時(shí)， 最優(yōu)基不變,三、設(shè)線性規(guī)劃問題 （1）分別用圖解法和單純形法求解； （2）對(duì)照指出單純形表中的各基本可行 解對(duì)應(yīng)圖解法中可行域的哪一頂點(diǎn)。,續(xù),（3）若目標(biāo)函數(shù)變?yōu)?討論c、d的值如何變化，使每個(gè)頂 點(diǎn)依次使目標(biāo)函數(shù)達(dá)到最優(yōu)。,解：化為標(biāo)準(zhǔn)型,1,2,2,1,最優(yōu)解,10 5 0 0 0 9 3

34、4 1 0 0 8 5 2 0 1 10 5 0 0 0 21/5 0 14/5 1 -3/5 10 8/5 1 2/5 0 1/5 0 1 0 -2 5 3/2 0 1 5/14 -3/14 10 1 1 0 -1/7 2/7 0 0 -5/14 -25/14,O（0，0）,1,2,2,1,o,c d c/d 最優(yōu)解的頂點(diǎn) c/d5/2 Q1 c/d=5/2 Q1,Q2 0 0 3/40 不限 Q3 0 =0 - Q1 0 0 不限 Q1 0 0 不限 O,線性規(guī)劃的對(duì)偶理論與靈敏度分析,1.7線性規(guī)劃的對(duì)偶問題,一、對(duì)偶問題的提出 二、原問題與對(duì)偶問題的數(shù)學(xué)模型 三、原問題與對(duì)偶問題的對(duì)應(yīng)

35、關(guān)系,對(duì)偶問題概念 任何一個(gè)線性規(guī)劃問題都有一個(gè)伴生的線性規(guī)劃問題，稱為其“對(duì)偶”問題。 對(duì)偶問題是對(duì)原問題從另一角度進(jìn)行的描述，其最優(yōu)解與原問題的最優(yōu)解有著密切的聯(lián)系，在求得一個(gè)線性規(guī)劃最優(yōu)解的同時(shí)也就得到對(duì)偶線性規(guī)劃的最優(yōu)解，反之亦然。 對(duì)偶理論就是研究線性規(guī)劃及其對(duì)偶問題的理論，是線性規(guī)劃理論的重要內(nèi)容之一。,一、對(duì)偶問題的提出,實(shí)例：某家電廠家利用現(xiàn)有資源生產(chǎn)兩種 產(chǎn)品， 有關(guān)數(shù)據(jù)如下表：,(1)如何組織生產(chǎn),獲利最大 （2）如果外公司收購其資源，收購價(jià)格最低,如何安排生產(chǎn)， 使獲利最多？,設(shè) 產(chǎn)量 產(chǎn)量,設(shè)：設(shè)備A 元時(shí) 設(shè)備B 元時(shí) 調(diào)試工序 元時(shí),付出的代價(jià)最小， 且對(duì)方能接受。

36、,出讓代價(jià)應(yīng)不低于 用同等數(shù)量的資源 自己生產(chǎn)的利潤(rùn)。,美佳能接受的條件： 收購方的意愿：,對(duì) 偶 問 題,原 問 題,廠 家,改寫成向量式,例2,例2,假設(shè)有客戶提出要求，購買工廠所擁有的工時(shí)和材料，為客戶加工別的產(chǎn)品，由客戶支付工時(shí)費(fèi)和材料費(fèi)。那么工廠給工時(shí)和材料制訂的最低價(jià)格應(yīng)是多少，才值得出賣工時(shí)和材料 ?,出賣資源獲利應(yīng)不少于生產(chǎn)產(chǎn)品的獲利; 約束 價(jià)格應(yīng)該盡量低，這樣，才能有競(jìng)爭(zhēng)力; 目標(biāo) 價(jià)格應(yīng)該是非負(fù)的,用y1和y2分別表示工時(shí)和材料的出售價(jià)格,總利潤(rùn)最小 min W=3y1+9y2 保證A產(chǎn)品利潤(rùn) y1+y22 保證B產(chǎn)品利潤(rùn) y1+4y23 保證C產(chǎn)品利潤(rùn) y1+7y23

37、售價(jià)非負(fù) y10 y20,min,max,3個(gè)約束 2個(gè)變量,2個(gè)約束 3個(gè)變量,一般規(guī)律,對(duì)偶問題對(duì)應(yīng)表,例:,對(duì)偶問題為,寫出下面的線性規(guī)劃問題的對(duì)偶問題,對(duì)偶問題為：,對(duì)稱形式的對(duì)偶問題,對(duì)稱形式的對(duì)偶問題,對(duì)偶問題的特點(diǎn) 若原問題目標(biāo)是求極大化，則對(duì)偶問題的目標(biāo)是極小化，反之亦然 原問題的約束系數(shù)矩陣與對(duì)偶問題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣 極大化問題的每個(gè)約束對(duì)應(yīng)于極小化問題的一個(gè)變量，其每個(gè)變量對(duì)應(yīng)于對(duì)偶問題的一個(gè)約束。,一般線性規(guī)劃問題的對(duì)偶問題,1.8對(duì)偶問題的基本性質(zhì),對(duì) 偶 問 題,原 問 題,收 購,廠 家,引例,（ ）,原問題，最終單純形表：,對(duì)偶問題用兩階段法求解的最終的

38、單純形表,（ ）,（x1,x2）原問題 最優(yōu)解,對(duì)偶問題 最優(yōu)解,原問題與對(duì)偶問題對(duì)比，最終單純形表：,相反數(shù)！,兩個(gè)問題作一比較: 1.兩者的最優(yōu)值相同 2.變量的解在兩個(gè)單純形表中互相包含 原問題最優(yōu)解（決策變量） 對(duì)偶問題最優(yōu)解（決策變量）,從引例中可見： 原問題與對(duì)偶問題在某種意義上來說，實(shí)質(zhì)上是一樣的，因?yàn)榈诙€(gè)問題僅僅在第一個(gè)問題的另一種表達(dá)而已。,理論證明： 原問題與對(duì)偶問題解的關(guān)系,二、對(duì)偶問題的基本性質(zhì),（1）對(duì)稱定理： 定理： 對(duì)偶問題的對(duì)偶是原問題。,設(shè)原問題（1） 對(duì)偶問題（2）,（2）弱對(duì)偶性定理： 若 和 分別是原問題（1）及對(duì)偶問題（2）的可行解，則有,從弱對(duì)偶性

39、可得到以下重要結(jié)論： （1）極大化問題（原問題）的任一可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是對(duì)偶問題最優(yōu)目標(biāo)函數(shù)值的下界。極小化問題（對(duì)偶問題）的任一可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是原問題最優(yōu)目標(biāo)函數(shù)值的上界。 （2）若原問題可行，但其目標(biāo)函數(shù)值無界（無上界），則對(duì)偶問題無可行解。 （3）若對(duì)偶問題可行，但其目標(biāo)函數(shù)值無界（無下界），則原問題無可行解。 （4）若原問題有可行解而其對(duì)偶問題無可行解，則原問題目標(biāo)函數(shù)值無界。 （5）對(duì)偶問題有可行解而其原問題無可行解，則對(duì)偶問題的目標(biāo)函數(shù)值無界。,原問題,對(duì)偶問題,（3）最優(yōu)性定理： 若 和 分別是（1）和（2）的 可行解，且有 則 分別是（1）和（2）的最優(yōu)解 。

40、,則 為（1）的最優(yōu)解， 反過來可知： 也是（2）的最優(yōu)解。,證明：因?yàn)椋?）的任一可行解 均滿足,（4）強(qiáng)對(duì)偶性定理 若原問題和對(duì)偶問題都有可行解，則兩者都有最優(yōu)解，且最優(yōu)解的目標(biāo)函數(shù)值相等。,證明：設(shè)X*是原問題的最優(yōu)解，則必有所有檢驗(yàn)數(shù)0即,設(shè)Y=CBB-1，則,這表示Y*滿足對(duì)偶問題的約束條件。Y*是對(duì)偶問題的可行解，代入目標(biāo)函數(shù)得,根據(jù)最優(yōu)性，Y*是對(duì)偶問題的最優(yōu)解，兩者最優(yōu)值相等,（5）互補(bǔ)松弛性： 若 分別是原問題（1）與對(duì)偶問題（2）的可行解， 分別為（1）、（2）的松弛變量，則： 即：,為最優(yōu)解,原問題第i條約束,A的第i行,說明：即如原始變量XJ*0 ，則與之相應(yīng)的第J個(gè)對(duì)

41、偶約束方程為等式，即剩余變量YSJ=0；如果第J個(gè)對(duì)偶約束為嚴(yán)格不等式，即剩余變量YSJ0，則與之相對(duì)應(yīng)的原始變量XJ*=0,另一方面：,對(duì)偶問題的第j條約束,證明：,充分性：設(shè)原問題為,對(duì)偶問題為：,原問題的目標(biāo)函數(shù)可以變?yōu)?同理對(duì)偶目標(biāo)函數(shù)可表示為：,互補(bǔ)松弛定理應(yīng)用： （1）從已知的最優(yōu)對(duì)偶解，求原問題最優(yōu)解，反之亦然。 （2）證實(shí)原問題可行解是否為最優(yōu)解。 （3）從不同假設(shè)來進(jìn)行試算，從而研究原始、對(duì)偶問題最優(yōu)解的一般性質(zhì)。 （4）非線性的方面的應(yīng)用。,以上性質(zhì)同樣適用于非對(duì)稱形式。,例,化為標(biāo)準(zhǔn)型時(shí)：分別加上松馳變量X4，X5，X6構(gòu)成標(biāo)準(zhǔn)型,化為標(biāo)準(zhǔn)型時(shí)：分別減去剩作變量y4，y5

42、，y6構(gòu)成標(biāo)準(zhǔn)型,已知上例中對(duì)偶問題的最優(yōu)解Y1*=0,Y2 * =8,Y3 * =2,利用互補(bǔ)松馳定理求原問題的最優(yōu)解。,解： 將最優(yōu)解Y1*=0,Y2 * =8,Y3 * =2代入對(duì)偶問題的數(shù)學(xué)模型，知Y40,Y5=0,Y6=0.剩余變量Y40，根據(jù)互補(bǔ)松馳性X*YS=0，則原始變量X1=0。 對(duì)偶變量Y1=0，而XSY*=0，則松馳變量X4=0,相應(yīng)約束條件為不起作用約束。 同理，對(duì)偶變量Y2，Y30,則松馳變量X5=0，X6=0。 于是原問題約束條件為 2X1+X2=50 4X1+3X3=150 解之得X2=50，X3=50,當(dāng)線性規(guī)劃原問題求得最優(yōu)解 時(shí)，其對(duì)偶問題也得到最優(yōu)解 ，且

43、代入各自的目標(biāo)函數(shù)后有：,是線性規(guī)劃原問題約束條件的 右端項(xiàng)，它代表第 種資源的擁有量；,（3）,1.9影子價(jià)格,影子價(jià)格的定義,對(duì)偶變量 的意義代表在資源最優(yōu)利用條件下對(duì)單位第 種資源的估價(jià)，這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)，為區(qū)別起見，稱為影子價(jià)格（shadow price)。,影子價(jià)格的經(jīng)濟(jì)意義,1資源的市場(chǎng)價(jià)格是已知數(shù)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改變。,2影子價(jià)格是一種邊際價(jià)格。 在（3）式中， 。 說明 的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下， 每增

44、加一個(gè)單位時(shí)目標(biāo)函數(shù) 的增量。,（3）,幾何解釋,3資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本. 在純市場(chǎng)經(jīng)濟(jì)條件下,當(dāng)?shù)?種資源的市場(chǎng)價(jià)格低于1/4時(shí)，可以買進(jìn)這種資源；相反當(dāng)市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，就會(huì)賣出這種資源。隨著資源的買進(jìn)賣出，它的影子價(jià)格也將隨之發(fā)生變化，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。,4在對(duì)偶問題的互補(bǔ)松弛性質(zhì)中有 這表明生產(chǎn)過程中如果某種資源 未得到充分利用時(shí)，該種資源的影子價(jià)格為零；又當(dāng)資源的影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。,5從影子價(jià)格的含義上考察單純形表的 檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。,（4）,第j種產(chǎn)品的產(chǎn)值,生產(chǎn)第j中產(chǎn)品所消耗各項(xiàng)資源的

45、 影子價(jià)格的總和。（即隱含成本）,6一般說對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及到資源的最有效利用。,經(jīng)濟(jì)學(xué)研究如何管理 自己的稀缺資源,1.10對(duì)偶單純形法,一、對(duì)偶單純形法的基本思路 單純形法是在原問題為可行解(表格bi列0)、對(duì)偶問題為非可行解(部分檢驗(yàn)數(shù)j0）的條件下，逐步進(jìn)行變量替換，改善目標(biāo)函數(shù)值，最終達(dá)到全部檢驗(yàn)數(shù)j0，即對(duì)偶問題也是可行時(shí)，根據(jù)對(duì)偶問題性質(zhì)3，原問題和對(duì)偶問題均得到最優(yōu)解。 對(duì)偶單純形法是根據(jù)線性規(guī)劃問題的對(duì)偶性質(zhì)設(shè)計(jì)的一種解題方法。其基本思路是：原問題不是可行解，保持對(duì)偶問題為可行解，逐步進(jìn)

46、行變量替換，當(dāng)原問題變?yōu)榭尚薪鈺r(shí)，即得到問題的最優(yōu)解。,單純形法的基本思路： 原問題基可行解 最優(yōu)解判斷,對(duì)偶問題的可行解,對(duì)偶問題 最優(yōu)解判斷,對(duì)偶單純形法 基本思路,對(duì)偶單純形法的優(yōu)點(diǎn)是可以從非可行解開始迭代，而不需添加人工變量去造基，這樣對(duì)一些特殊類型的線性規(guī)劃問題求解起來更加便捷。,對(duì)偶單純形法的解題步驟,根據(jù)線性規(guī)劃問題列出初始單純形表，表中所有檢驗(yàn)數(shù)j0，b列中至少有一個(gè)分量為負(fù)。,確定換出變量，在b列的負(fù)分量中選出一個(gè)最小值（也可任選）bl，其對(duì)應(yīng)的基變量xB1為出基變量。,對(duì)應(yīng)基變量 為換出基的變量,例：用對(duì)偶單純形法求解線性規(guī)劃問題,初始可行基,初始可行基,使對(duì)偶問題基變量可

47、行,主元,主元,最優(yōu)解,例2.12 用對(duì)偶單純形方法求解：,解: （1）引入松弛變量 x3 , x4 , x5 化為標(biāo)準(zhǔn)形，并在約束等式兩側(cè)同乘-1，得到,例2.13 用對(duì)偶單純形法求解下面線性規(guī)劃,解: 構(gòu)造對(duì)偶單純形表進(jìn)行迭代，,從最后的表可以看到，B-1b列元素中有-20，并且，-2所在行各元素皆非負(fù)，因此，原規(guī)劃沒有可行解。,用對(duì)偶單純形法求解線性規(guī)劃問題：,對(duì)偶單純形法的優(yōu)點(diǎn)： 不需要人工變量； 在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法處理簡(jiǎn)化。 對(duì)偶單純形法缺點(diǎn)： 在初始單純形表中對(duì)偶問題是基可行解，這點(diǎn)對(duì)多數(shù)線性規(guī)劃問題很難做到。 因此，對(duì)偶單純形法一般不單獨(dú)使用。,1.11靈敏度

48、分析,在生產(chǎn)計(jì)劃問題的一般形式中，A代表企業(yè)的技術(shù)狀況，b代表企業(yè)的資源狀況，而C代表企業(yè)產(chǎn)品的市場(chǎng)狀況，這些因素不變時(shí)企業(yè)的最優(yōu)生產(chǎn)計(jì)劃和最大利潤(rùn)由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定。 在實(shí)際生產(chǎn)過程中，上述三類因素均是在不斷變化的，如果按照初始的狀況制訂了最佳的生產(chǎn)計(jì)劃，而在計(jì)劃實(shí)施前或?qū)嵤┲猩鲜鰻顩r發(fā)生了改變，則決策者所關(guān)心的是目前所執(zhí)行的計(jì)劃還是不是最優(yōu)，如果不是應(yīng)該如何修訂原來的最優(yōu)計(jì)劃。更進(jìn)一步，為了防止在各類狀況發(fā)生時(shí)，來不及隨時(shí)對(duì)其變化作出反應(yīng)，即所謂“計(jì)劃不如變化快”，企業(yè)應(yīng)當(dāng)預(yù)先了解，當(dāng)各項(xiàng)因素變化時(shí)，應(yīng)當(dāng)作出什么樣的反應(yīng)。,當(dāng)系數(shù)A，b，C發(fā)生改變時(shí)，目前最優(yōu)基是否還最優(yōu)？ 為

49、保持目前最優(yōu)基還是最優(yōu)，系數(shù)A，b，C的允許變化范圍是什么？ 假設(shè)每次只有一種系數(shù)變化 目標(biāo)系數(shù)C變化 基變量系數(shù)發(fā)生變化； 非基變量系數(shù)發(fā)生變化； 右端常數(shù)b變化 增加一個(gè)變量 增加一個(gè)約束 技術(shù)系數(shù)A發(fā)生變化,列出初始單純形表,列出最終單純形表,Z0= CBB-1b, A = C - CBB-1 A N = CN - CBB-1 N j = Cj- CBB-1 Pj, b= B-1b, j = Cj- CBB-1 Pj,Z0= CBB-1b, b= B-1b,靈敏度分析只要滿足以下兩把尺子： j =Cj-CBB-1pj 0； b= B-1b 0,一、價(jià)值系數(shù)CJ的變化,（一）非基變量Xj的

50、價(jià)值系數(shù)Cj的改變,只要滿足：,（二）基變量Xbi的價(jià)值系數(shù)Cbi的變化 由j=Cj-CBB-1Pj看出：某一基變量?jī)r(jià)值系數(shù)CBi的變化將引起CB變化，CB變了則所有非基變量的檢驗(yàn)數(shù)也隨之發(fā)生變化?；兞康臋z驗(yàn)數(shù)(CB+CB)-(CB+CB)B-1B0不受變動(dòng)影響。非基變量的檢驗(yàn)數(shù)變?yōu)?為確保所有 的允許變化范圍是,例：在第一章的美佳公司例子中， （1）若家電I的利潤(rùn)降至1.5元/件，而家電II的利潤(rùn)增至2元/件時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化； （2）若家電I的利潤(rùn)不變，家電II的利潤(rùn)在什么范圍內(nèi)變化時(shí)，則該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化。,6 14 -,即Z=(2,3,0,6,0),6 14 -,設(shè)家電II的利潤(rùn)為（1+),為使表中為最優(yōu)解則： -1/4+1/40, -1/2-3/2 0,解得：-1/3 1 即2/3 C2 2,二、右端資