線性規(guī)劃模型（課堂PPT）

1、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1第第1節(jié)節(jié) 線性規(guī)劃問(wèn)題與模型線性規(guī)劃問(wèn)題與模型 一、線性規(guī)劃模型一、線性規(guī)劃模型 從招聘總經(jīng)理談起從招聘總經(jīng)理談起 v 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2泰山工廠生產(chǎn)狀況 泰山工廠可以生產(chǎn)兩種產(chǎn)品出售，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表： 目前生產(chǎn)現(xiàn)狀： 不生產(chǎn)產(chǎn)品A ，生產(chǎn)產(chǎn)品B每天30 ， 獲利3600 產(chǎn)品A產(chǎn)品B資源限量設(shè) 備勞動(dòng)力原材料9434510360200300利潤(rùn)元/kg70120管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3招聘總經(jīng)理！ 約翰： 我應(yīng)聘！ 在現(xiàn)有資源狀況下，我可以使利潤(rùn)達(dá)到4280 ！ 方案是： 生產(chǎn)A 產(chǎn)品

2、20 ， 生產(chǎn) B 產(chǎn)品 24 可行性：9*20+4*24=276360 4*20+5*24=200 3*20+10*24=300管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4怎么達(dá)到的？ 約翰使用了運(yùn)籌學(xué)中的線性規(guī)劃模型 問(wèn)題：如何安排生產(chǎn)計(jì)劃，使得獲利最多？ 步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg,B產(chǎn)品x2kg2、確定目標(biāo)函數(shù)：maxZ=70X1+120X23、確定約束條件：設(shè)備約束 9X1+4X2360 人力約束4X1+5X2 200 原材料約束3X1+10X2 300 非負(fù)性約束X10 X20管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)5線性規(guī)劃圖解法 由數(shù)學(xué)知識(shí)可知：y=ax+b是一條直線，同理：Z=70

3、x1+120 x2x2=70/120 x1-Z/120也是一條直線，以Z為參數(shù)的一族等值線。 9x1+4x2 360 x1 360/9-4/9x2 是直線 x1=360/9-4/9x2 下方的半平面。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點(diǎn)，就是滿足所有約束條件的解，稱之為可行解。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)6例1圖示. 90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300ABCDEFGHIZ=70 x1+120 x2管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)7 最優(yōu)解： X1=20 , x2=24 對(duì)應(yīng)

4、的生產(chǎn)方案： 生產(chǎn)A 產(chǎn)品20 生產(chǎn) B 產(chǎn)品 24 獲利：70*20+120*24=4280管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)8約翰就任泰山工廠總經(jīng)理！管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)9二、線性規(guī)劃圖解法二、線性規(guī)劃圖解法例例2. 某工廠在計(jì)劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、資源的限制，如下表：?jiǎn)栴}：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？線性規(guī)劃模型：線性規(guī)劃模型： 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0管管 理理 運(yùn)運(yùn)

5、 籌籌 學(xué)學(xué)10例例1.目標(biāo)函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標(biāo)值 z = 27500圖圖 解解 法法 對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問(wèn)題的有關(guān)概念，并求解。 下面通過(guò)例1詳細(xì)講解其方法：管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)11線性規(guī)劃圖解法（續(xù)）線性規(guī)劃圖解法（續(xù)） (1)分別取決策變量X1 , X2 為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)

6、系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1的每個(gè)約束條件都代表一個(gè)半平面。x2x1X20X2=0 x2x1X10X1=0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)12線性規(guī)劃圖解法（續(xù)）線性規(guī)劃圖解法（續(xù)）（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)13線性規(guī)劃圖解法（續(xù)）線性規(guī)劃圖解法（續(xù)）（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-1所示。100100

7、x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-1管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)14線性規(guī)劃圖解法（續(xù)）線性規(guī)劃圖解法（續(xù)）（4）目標(biāo)函數(shù)z=50 x1+100 x2，當(dāng)z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100

8、 x2z=10000=50 x1+100 x2CBADE管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)15線性規(guī)劃圖解法（續(xù)）線性規(guī)劃圖解法（續(xù)） 重要結(jié)論： 如果線性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解； 無(wú)窮多個(gè)最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙ax z=50 x1+50 x2，則線段BC上的所有點(diǎn)都代表了最優(yōu)解； 無(wú)界解。即可行域的范圍延伸到無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú)窮小。一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件； 無(wú)可行解。若在例1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x21200，則可行域?yàn)榭沼?，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。管管 理理 運(yùn)運(yùn) 籌籌

9、學(xué)學(xué)16線性規(guī)劃圖解法（續(xù)）線性規(guī)劃圖解法（續(xù)） 例例2 2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購(gòu)進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)格為2萬(wàn)元，每噸B原料的價(jià)格為3萬(wàn)元，試問(wèn)在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買A，B兩種原料，使得購(gòu)進(jìn)成本最低？管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)17線性規(guī)劃圖解法（續(xù)）線性規(guī)劃圖解法（續(xù)）解：目標(biāo)函數(shù)： Min f = 2x1 + 3 x2 約

10、束條件：s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用圖解法。如下圖：得Q點(diǎn)坐標(biāo)（250，100）為最優(yōu)解。100200300 400 500 600100200300400600500 x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200 x1 x2 Q管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)18三、線性規(guī)劃一般形式 企業(yè)管理的重點(diǎn)內(nèi)容之一就是在各種生產(chǎn)因素和產(chǎn)品的調(diào)配問(wèn)題上。 一方面， 在一固定階段， 企業(yè)管理者所能“投入”的生產(chǎn)因素：原料、人力、設(shè)備時(shí)間是由一定限量的。

11、 在一固定期間，任何一工廠的廠房、工場(chǎng)、機(jī)器、一切固定資本是不會(huì)變動(dòng)的， 再雄厚的資本， 也還是有它的限度。再?gòu)牧鲃?dòng)資本來(lái)看，原料的來(lái)源和存量， 各種技工的人數(shù)和時(shí)間，在一相當(dāng)?shù)亩唐谥幸彩怯幸欢ǖ南薅取?管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)19線性規(guī)劃一般形式 另一方面，企業(yè)管理者“投入”生產(chǎn)因素時(shí)，一定有一完整的目標(biāo)。在商言商， 企業(yè)管理者的目標(biāo)當(dāng)然是求最高的利潤(rùn)和最低的成本。如何將受時(shí)間、空間、數(shù)量限制的“投入”生產(chǎn)因素調(diào)配“得當(dāng)”，達(dá)到最佳的境界而獲得最佳的“產(chǎn)出”量，因而獲得最大的收益。 以上就是企業(yè)管理者須面對(duì)的一個(gè)問(wèn)題的兩個(gè)方面。企業(yè)管理者不僅要知道如何調(diào)配手頭上有限的生產(chǎn)因素，同時(shí)要從不

12、同的調(diào)配中， 找出最佳的調(diào)配，來(lái)達(dá)到他的企業(yè)經(jīng)營(yíng)目標(biāo)最低成本、最高利潤(rùn)。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)20線性規(guī)劃一般形式 事實(shí)上，用最低的代價(jià)去追求最高的收獲， 原是一種理性的要求，因此在任何理性活動(dòng)中，都有一求“最佳”問(wèn)題的存在。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)21例題3配方問(wèn)題 養(yǎng)海貍鼠 飼料中營(yíng)養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表：飼料VaVbVc價(jià)格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495營(yíng)養(yǎng)要求70030200管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)22例題3建模 設(shè)抓取飼料

13、I x1kg;飼料II x2kg;飼料III x3kg 目標(biāo)函數(shù)：最省錢 minZ=2x1+7x2+4x3+9x4+5x5 約束條件：3x2+2x2+x3+6x4+18x5 700營(yíng)養(yǎng)要求： x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5 =200用量要求： x1 50,x2 60,x3 50,x4 70,x5 40非負(fù)性要求：x1 0,x2 0,x3 0,x4 0,x5 0 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)23例題4：人員安排問(wèn)題 醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí)。不同時(shí)段需要的護(hù)士人數(shù)不等。據(jù)統(tǒng)計(jì)： 序號(hào)時(shí)段最少人數(shù)安排人數(shù)1061

14、060X12101470X23141860X34182250X45220220X56020630 x6管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)24例題4建模 目標(biāo)函數(shù)：min Z=x1+x2+x3+x4+x5+x6 約束條件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30非負(fù)性約束：xj 0,j=1,2,6管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)25歸納：線性規(guī)劃的一般模式 目標(biāo)函數(shù)：max(min)Z=c1x1+c2x2+c3x3+cnxn 約束條件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2

15、 am1x1+am2x2+am3x3+amnxn (= )bn非負(fù)性約束：x1 0,x2 0,xn 0 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)26四、線性規(guī)劃的標(biāo)準(zhǔn)型四、線性規(guī)劃的標(biāo)準(zhǔn)型 一般形式一般形式目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式目標(biāo)函數(shù)： Max z = c1

16、x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)27線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型 可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項(xiàng)非負(fù)。 對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)28線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型

17、1.極小化目標(biāo)函數(shù)的問(wèn)題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 則該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即 Max z = - c1x1 - c2x2 - - cnxn 但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即 Min f - Max z管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)29線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型2、約束條件不是等式的問(wèn)題： 設(shè)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進(jìn)一個(gè)新的變量s ，使它等于約束右邊與左邊之差 s=bi(ai1 x1 + ai2

18、 x2 + + ain xn )顯然，s 也具有非負(fù)約束，即s0， 這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ +ain xn+s = bi管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)30線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型 當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時(shí)， 類似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 顯然，s 也具有非負(fù)約束，即s0，這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)31線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型 為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于

19、”時(shí)稱為“松弛變量”；當(dāng)不等式為“大于等于”時(shí)稱為“剩余變量”。如果原問(wèn)題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。 3.右端項(xiàng)有負(fù)值的問(wèn)題： 在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如 bi 40 選選X2從從0，X1 =0X3 =30-2X2 0 0 X2 30/2 X4 =60-2X2 0 0 X2 60/2 X5 =24-2X2 0 0 X2 24/2 X2=min(30/2 , 60/2 , 24/2 ) =12X2進(jìn)基變量，進(jìn)基變量， X5出基變量。出基變量。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)44B B2 2=(P3 P

20、4 P2)Z=0+40X1+50X2 X3 +2X2 =30-X1 X4+2X2 =60-3X1 2X2=24-X5 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)45 1/2 ，代入式，代入式， ，Z=600 +40X1 -25X5X3 =6 -X1 +X5 X4 = 36-3X1 +X5 X2=12 -1/2X5令令X1 =X5 =0 X(2) =(0, 12, 6, 36, 0)T Z(2) =600管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)46(2)(2) 判斷判斷 400 X(2)不是不是。(3)(3) 選選X1從從0， X5 =0 X3= 6- X1 0 0 X4= 36-3X1 0 0 X2=12 0 0 X1

21、=min( 6/1 , 36/3 , 1 ) =6X1進(jìn)基，進(jìn)基， X3出基。出基。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)47B3 =(P1 P4 P2 )Z=840-40X3+15X5X1=6 - X3 + X5 X4= 18+3X3 - 2X5X2=12 -1/2X5令令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)TZ(3) =840管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)48(2)(2) 150 X(3)不是不是(3)(3) 選選X5從從0， X3 =0 X1=6 +X5 0 0 X4= 18 -2X5 0 0 X2=12-1/2 X5 0 0 X5=min( 18/2 , 12/1/2

22、 ) =9X5進(jìn)基，進(jìn)基， X4出基。出基。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)49B4=(P1 P5 P2 )Z=975- 35/2X3 - 15/2X4X1= 15 + 1/2X3 - 1/2X4X5= 9 + 3/2X3 - 1/2X4X2= 15/2 -3/4X3 + 1/4X4令令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)500(0,0)X X2 2X X1 1A A D DC CB B(0,12)(6,12)(15,7.5)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)51 maxZ=CX當(dāng)當(dāng)LP的數(shù)學(xué)模型為矩陣型的數(shù)學(xué)模型為

23、矩陣型 AX=b 時(shí)，時(shí)， X 0 0兩個(gè)重要公式：兩個(gè)重要公式：XB =B-1 b-B-1 NXNZ=CB B-1 b+(CN -CB B-1 N)XN當(dāng)當(dāng)XN =0時(shí)，時(shí)， B-1 b 0X=Z= CB B-1 b管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)52當(dāng)當(dāng)LPLP的數(shù)學(xué)模型為一般型時(shí)的數(shù)學(xué)模型為一般型時(shí)njjjXCZ1max), 2 , 1(0), 2 , 1(1njXmibXajnjijij兩個(gè)重要公式形如：兩個(gè)重要公式形如：nmjjmiijijmiiinmjjijiiXaCCbCZmiXabX1111)(), 2 , 1(管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)531 00 a1m+1 a1n0 10

24、a2m+1 a2n0 01 amm+1 amn設(shè)設(shè)A=A=B=(P1 P2 Pm )=InmjijijimibXaX1), 1(), 2 , 1(1miXabXnmjjijii管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)54nmjjmiijijimiinmjiinmjjijimiiminmjiiiiXaCCbCXCXabCXCXCZ11111111)()(miiiTmbCZbbX11)0,0,(當(dāng)當(dāng)Xj =0 (j=m+1,n)時(shí)時(shí),管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)551.5.2 單純形法原理單純形法原理njjjXCZ1max), 2 , 1(0), 2 , 1(1njXmibXajnjijijnmjjmiiji

25、jmiiinmjjijiiXaCCbCZmiXabX1111)(), 2 , 1(管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)56此時(shí)，此時(shí)，B=(P1 P2 Pm )對(duì)應(yīng)的基本可行解為對(duì)應(yīng)的基本可行解為miiiTmbCZbbX11)0,0,(nmjjijiinmjjjmiXabXXZZ110), 2 , 1(1)(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)57定理定理1 1：對(duì)解：對(duì)解X(1) ，若檢驗(yàn)數(shù)，若檢驗(yàn)數(shù) j ( j=m+1,n)全全部部 0，則則X(1)為最優(yōu)解。為最優(yōu)解。定理定理2 2：對(duì)：對(duì)X(1)，若有某個(gè)非基變量，若有某個(gè)非基變量Xm+k m+k00且相應(yīng)的且相應(yīng)的Pm+k =(a1m+k , ,

26、amm+k )T 0，則原問(wèn)題則原問(wèn)題無(wú)有限最優(yōu)解。無(wú)有限最優(yōu)解。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)58定理定理2證明證明Xi =bi - aij xjJ=m+1n令非基變量令非基變量Xm+k = ( 0)X(2) =(b1 - a1m+k , ,bm - amm+k ,0, , , ,0)TAX(2) =b X(2) 0Z=Z0+ m+k 當(dāng)當(dāng) 時(shí)時(shí) Z 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)59例：例： Z=30X1+20X2 -X1+3X2 +X3 =10-3X1+2X2 +X4 =15初始基初始基B1 =(P3 P4 )X(1) =(0, 0, 10, 15 )T Z(1) =0Z=030X1+20X

27、2X3=10-(-X1 +3X2 )X4 =15-(-3X1 +2X2 )管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)60選中選中X1從從0，X2 =0 X3=10-(-X1 ) 0 0 X4=15-(-3X1 ) 0 0 求求X1， X1+ , ,Z Z+ 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)61換基迭代公式：換基迭代公式：(1)、決定換入變量：決定換入變量：maxmax j = m+k ，則則Xm+k 為換入變量為換入變量 j00(2)、決定換出變量：決定換出變量：bi -aim+kXm+k 0 0 ( i=1 ,2 , m)Xm+k biaim+k(aim+k 0 0 )管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)62= =

28、min aim+k 0 =0 =biaim+kbrarm+k則則X Xr為換出變量為換出變量。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)63定理定理3：經(jīng)單純形法得到的：經(jīng)單純形法得到的X(2) =(b1 - a1m+k , ,bm - amm+k ,0, , , ,0)T是基本可行解，且是基本可行解，且Z(2) Z(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)64證明：設(shè)證明：設(shè)Xr = Xm , Xm =0, Xm+k = =bmAmm+k(0)X(1)中中P1 , Pm線性無(wú)關(guān)，下證線性無(wú)關(guān)，下證P1 , Pm -1 , Pm +k線性無(wú)關(guān)。線性無(wú)關(guān)。若否，因?yàn)槿舴瘢驗(yàn)镻1 , Pm線性無(wú)關(guān)線性無(wú)關(guān)則則Pm

29、+k = a1m +k P1+ + amm +k Pm 而而Pm +k = l1 P1+ lm -1 Pm -1 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)65 - (a1m +k - l1 )P1 + +(am -1m +k - lm -1 ) Pm -1+ am m+k Pm =0P1 , ,Pm線性相關(guān)，矛盾。線性相關(guān)，矛盾。X(2)是基本解，且是可行解是基本解，且是可行解 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)66單純形法基本步驟單純形法基本步驟(1)、定初始基，初始基本可行解、定初始基，初始基本可行解(3)、若有若有 k 0 0，Pk全全 0，停，停， 沒(méi)有有限最優(yōu)解；沒(méi)有有限最優(yōu)解； 否則轉(zhuǎn)否則轉(zhuǎn)(4)(

30、2)、對(duì)應(yīng)于非基變量檢驗(yàn)數(shù)、對(duì)應(yīng)于非基變量檢驗(yàn)數(shù) j全全 0。 若是，停，得到最優(yōu)解；若是，停，得到最優(yōu)解； 若否，轉(zhuǎn)若否，轉(zhuǎn)(3)。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)67= = min aim+k 0 =0 =biaim+kbrarm+k定定X Xr為換出變量，為換出變量，a arm+k為為主元。主元。由最小由最小比值法求：比值法求：maxmax j = m+kXm+k 換入變量換入變量 j00(4)、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)68轉(zhuǎn)轉(zhuǎn)(2) (2) m+k 0 a1m+k 0arm+k 1amm+k 0初等行變換初等行變換Pm+k = =(5)、以、以a arm+k為中心，換基迭代為中心，換基

31、迭代管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)69證明可用歸納法（略）證明可用歸納法（略）X(1)X(2)X(3)X XX在邊界上在邊界上X在內(nèi)部在內(nèi)部X X +(1- ) X(2) (0 1)X X(1) +(1- ) X(3) X(1) (1- ) X(2) (1- )X(3) X=+(0 1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)70證明：證明： 設(shè)設(shè)X(1) , ,X(k) 為可行域頂點(diǎn)，若為可行域頂點(diǎn)，若X*不是不是頂點(diǎn)，但頂點(diǎn)，但 max Z = C X* X*=定理定理2：可行域有界，最優(yōu)值必可在頂點(diǎn)得到：可行域有界，最優(yōu)值必可在頂點(diǎn)得到 i X(i)ki=1 i =1ki=10 i 1 1CX*= i

32、C X(i)ki=1 i CX(m)ki=1= CX(m) 設(shè)設(shè) CX(m) Max (C X(i) 1 1 i k k管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)71Z(1) = Ci bii=1mZ(2) = Ci (bi - aim+k)+ Cm+k i=1m = Ci bi - + Cm+k i=1m Ci aim+ki=1m = Ci bi +Cm+k - Ci aim+k i=1m i=1mZ(2) - Z(1) =(Cm+k -Zm+k ) = m+k 0 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)721.5.3 單純形表單純形表 C1 C2 Cm Cm+1 Cm+k Cn X1 X2 Xm Xm+1 Xm+

33、k XnCB XB Z0 0 0 0 m+1 m+k nC1 X1 b1 1 0 0 a1m+1 a1m+k a1nC2 X2 b2 0 1 0 a2m+1 a2m+k a2nCr Xr br 0 0 0 arm+1 arm+k arnCm Xm bm 0 0 1 amm+1 amm+k annmiiibCZ10miijijjaCC1管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)73 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 40 50 0 0 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 X

34、4 6060 3 3 2 0 1 0 302 0 1 0 300 0 X5 24 0 (2) 0 0 1 12 24 0 (2) 0 0 1 12 XB 600 40 0 0 0 -25 600 40 0 0 0 -250 0 X3 6 (1) 0 1 0 -1 66 (1) 0 1 0 -1 60 0 X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 840 0 0 -40 0 15 840 0 0 -40 0 1540 40 X1 6 1 0 1 0 -16 1 0 1 0 -10 0 X4

35、18 0 0 -3 1 2 18 0 0 -3 1 250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)74 XB 975 0 0 -35/2 -15/2 0 975 0 0 -35/2 -15/2 040 40 X1 15 1 0 -1/2 1/2 0 15 1 0 -1/2 1/2 0 0 0 X5 9 0 0 -3/2 1/2 1 9 0 0 -3/2 1/2 1 50 50 X2 15/2 0 1 3/4 -1/4 0 15/2 0 1 3/4 -1/4 0本問(wèn)題的最優(yōu)解本問(wèn)題的最優(yōu)解 X=(15, 15/2, 0, 0, 9)T

36、Z=975管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)75幾點(diǎn)說(shuō)明：幾點(diǎn)說(shuō)明：(1)(1)、例、例 maxZ=maxZ=X1 +2X2X1 4X2 3X1+2X2 8 X1 , X2 0 0 X1+X3 = = 4X2+X4 = = 3X1+2X2+X5= = 8 X1 X5 0 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)76 1 2 0 0 0 1 2 0 0 0 X1 X2 X3 X4 X5CB XB 0 1 2 0 0 00 1 2 0 0 00 0 X3 4 1 0 1 0 0 4 1 0 1 0 00 0 X4 3 0 (1) 0 1 03 0 (1) 0 1 00 0 X5 8 1 2 0 0 1 8 1 2

37、 0 0 1CB XB 6 1 0 0 -2 0 6 1 0 0 -2 00 0 X3 4 1 0 1 0 0 4 1 0 1 0 0 2 2 X2 3 0 1 0 1 0 3 0 1 0 1 0 0 0 X5 2 2 (1) 0 0 -2 1 (1) 0 0 -2 1 ( (接下表接下表) )管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)77 1 2 0 0 0 1 2 0 0 0 X1 X2 X3 X4 X5 CB XB 8 0 0 0 0 -18 0 0 0 0 -10 0 X3 2 0 0 1 (2) -1 2 0 0 1 (2) -12 2 X2 3 0 1 0 1 03 0 1 0 1 01 1 X

38、1 2 1 0 0 -2 1 2 1 0 0 -2 1CB XB 8 0 0 0 0 -1 8 0 0 0 0 -10 0 X4 1 0 0 1/2 1 -1/2 1 0 0 1/2 1 -1/2 2 2 X2 2 0 1 -1/2 0 1/2 2 0 1 -1/2 0 1/2 1 1 X1 4 4 1 0 1 0 0 1 0 1 0 0 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)78X X(1)(1)= = (2,3) Z Z(1)(1)=8 =8 X X(2)(2)= = (4,2) Z Z(2)(2)=8=8無(wú)窮多解無(wú)窮多解全部解：全部解：X X= + (1-) (0 1)2 4 3 2管管 理理 運(yùn)

39、運(yùn) 籌籌 學(xué)學(xué)79(2)(2)、例：、例： 求求 minZ=minZ=X1 -X2+X3 -3X5X2+X3 -X4+2X5 = = 6X1+2X2 -2X4 = = 52X2 +X4+3X5 +X6 = = 8X1 X6 0 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)80 1 -1 1 0 -3 0 1 -1 1 0 -3 0 X1 X2 X3 X4 X5 X6CB XB 11 0 -4 0 3 -5 011 0 -4 0 3 -5 01 1 X3 6 0 1 1 -1 2 0 6 0 1 1 -1 2 01 1 X1 5 1 2 0 -2 0 05 1 2 0 -2 0 00 0 X6 8 0 2 0

40、 1 3 1 8 0 2 0 1 3 1CB XB -7/3 0 -2/3 0 14/3 0 5/3 -7/3 0 -2/3 0 14/3 0 5/31 1 X3 2/3 0 -1/3 1 -5/3 0 -2/3 2/3 0 -1/3 1 -5/3 0 -2/3 1 1 X1 5 1 2 0 -2 0 05 1 2 0 -2 0 0-3 -3 X5 8/38/3 0 2/3 0 1/3 1 1/30 2/3 0 1/3 1 1/3CB XB -4 1/3 0 0 4 0 5/3-4 1/3 0 0 4 0 5/31 1 X3 3/2 1/6 0 1 -2 0 -2/33/2 1/6 0 1 -

41、2 0 -2/3-1 -1 X2 5/2 1/2 1 0 -1 0 0 5/2 1/2 1 0 -1 0 0 -1 -1 X5 1 -2/3 0 0 1 1 1/31 -2/3 0 0 1 1 1/3管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)81判定定理判定定理1 1：基本可行解：基本可行解X X，當(dāng)全部，當(dāng)全部 j 0 0時(shí)，時(shí)，X X為為最優(yōu)解。最優(yōu)解。判定定理判定定理2 2：對(duì)可行基：對(duì)可行基B B，當(dāng)某，當(dāng)某 k00，且，且Pk=(a1k amk )T 0，則原問(wèn)題無(wú)有限最優(yōu)解。則原問(wèn)題無(wú)有限最優(yōu)解。 換入變量：換入變量：maxmax j = j = m+k Xm+k j 00, 則判定原問(wèn)題無(wú)可行

42、解。則判定原問(wèn)題無(wú)可行解。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)98兩階段法原理：兩階段法原理：(1)、輔助問(wèn)題的基本可行解、輔助問(wèn)題的基本可行解X(0) 為最優(yōu)解，對(duì)應(yīng)為最優(yōu)解，對(duì)應(yīng)最小值最小值 =0 則則X(0) 的前的前n個(gè)分量是原問(wèn)題的基本可行解。個(gè)分量是原問(wèn)題的基本可行解。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)99 設(shè)設(shè)X(0)=(X1(0) Xn(0) , y1(0) yn(0) )T 使使 aij xj(0)+ yi(0) bi ( i=1, 2, ,n )nj=1 =0, y1(0) = = yn(0) =0 aij xj(0) bi ( i=1, ,m )nj=1證明：證明：管管 理理 運(yùn)運(yùn) 籌

43、籌 學(xué)學(xué)100(2)、原問(wèn)題有可行解時(shí)，輔助問(wèn)題最優(yōu)值、原問(wèn)題有可行解時(shí)，輔助問(wèn)題最優(yōu)值 =0 。證明：若原問(wèn)題有可行解證明：若原問(wèn)題有可行解X(0)=(X1(0) , , Xn(0)T使使 aij xj(0) bi ( i=1, ,m )j=1n作作X(1)=( X1(0) Xn(0) ,0 0 )T = yi 0 =0i=1m必為輔助問(wèn)題最優(yōu)解必為輔助問(wèn)題最優(yōu)解管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)101maxZ= -X1 +2X2 X1 +X2 2-X1 +X2 1 X2 3 3X1 X2 0例例2 2：管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)102第第(1)階段：階段：minW=X6 +X7 X1 +X2

44、-X3 +X6 = =2-X1 +X2 -X4 +X7 = =1 X2 +X5 = =3X1 X7 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)103 0 0 0 0 0 1 1 0 0 0 0 0 1 1 X1 X2 X3 X4 X5 X6 X7CB XB 3 3 0 -2 1 1 0 1 1 0 0 0 0 01 1 X6 2 1 1 -1 0 0 1 0 2 1 1 -1 0 0 1 0 1 1 X7 1 -1 1 -1 (1) 0 -1 0 0 1 (1) 0 -1 0 0 1 0 X5 3 0 1 0 0 1 0 0 3 0 1 0 0 1 0 0 CB XB 1 1 -2 -2 0 1 -1 0

45、 1 -1 0 0 2 X6 1 (2) 0 -1 1 0 1 -1 1 (2) 0 -1 1 0 1 -1 X2 1 -1 1 -1 1 0 -1 0 0 1 1 0 -1 0 0 1 X5 2 1 0 0 1 1 0 -1 2 1 0 0 1 1 0 -1 XB 0 0 0 0 0 0 0 0 0 0 0 1 1 X1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 1/2 1 0 -1/2 1/2 0 1/2 -1/2 X2 3/2 0 3/2 0 1 -1/2 -1/2 0 1/2 1/21 -1/2 -1/2 0 1/2 1/2 X5 3/2 0 0 -1/2 1/2 1 -

46、1/2 -1/2 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)104 -1 2 0 0 0 X1 X2 X3 X4 X5CB XB 3/2 0 0 1/2 3/2 0 -1 X1 1/2 1 0 -1/2 (1/2) 0 2 X2 3/2 0 1 -1/2 -1/2 0 0 X5 3/2 0 0 1/2 1/2 1 XB 4 -3 0 2 0 0 X4 1 2 0 -1 1 0 X2 2 1 1 -1 0 0 X5 1 -1 0 (1) 0 1 XB 6 1 0 0 0 -2 X4 2 1 0 0 1 1 X2 3 0 1 0 0 1 X3 1 -1

47、0 1 0 1管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)105例例3：maxZ= 2X1 +X2 5X1 +10X2 82X1 +2X2 1X1 ，X2 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)106第第(1)(1)階段：階段：minW= X55X1 +10X2 -X3 +X5 =82X1 +2X2 +X4 = =1X1 X5 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)107 0 0 0 0 1 0 0 0 0 1 X1 X2 X3 X4 X5 CB XB 8 -5 -10 1 0 01 X5 8 5 10 -1 0 10 X4 1 2 (2) 0 1 0 XB 3 5 0 1 5 01 X5 3 -5 0 -1 -5 10 X

48、2 1/2 1 1 0 1/2 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)108X2X1O管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)109第第1階段階段 最優(yōu)基最優(yōu)基B* min = *(1)、 *0 (2)、 * =0 yi 0( i=1,2, ,m) B* 基變量無(wú)人工變量基變量無(wú)人工變量 B* 基變量含人工變量基變量含人工變量yr 單純形表中，單純形表中， yr+ ark yk + arj xj =0 () k Jj JJ：非基變量下標(biāo)集合：非基變量下標(biāo)集合管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1101) arj 全全 =0 () 式多余方程式多余方程2) arj 有有 0 元，設(shè)為元，設(shè)為ars 0 以以ars為主元，換

49、基迭代，最后得到為主元，換基迭代，最后得到管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)111例例4 4、求、求maxZ= -4X1 -3X3 1/2X1 +X2+1/2X3-2/3X4 = 23/2X1 +3/4X3 = =33X1 -6X2 +4X4 = 0X1 , X2 , X3 , X4 0滿足滿足管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)112 0 0 0 0 1 1 1 X1 X2 X3 X4 y1 y2 y3 CB XB 5 -5 5 -5/4 -10/3 0 0 0 1 y1 2 1/2 1 1/2 -2/3 1 0 0 1 y2 3 3/2 0 3/4 0 0 1 0 1 y3 0 3 6 0 4 0 0

50、1 CB XB 5 0 -5 -4/5 10/3 0 0 5/3 1 y1 2 0 2 1/2 -4/3 1 0 -1/6 1 y2 3 0 3 3/4 2 0 1 -1/2 0 X1 0 1 -2 0 4/3 0 0 1/3第第 一一 階階 段段 一一二二管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)113 CB XB 0 0 0 0 0 5/2 0 5/4 0 X2 1 0 1 1/4 -2/3 1/2 0 -1/2 1 y2 0 0 0 0 0 -3/2 1 -1/4 0 X1 2 1 0 1/2 0 1 0 1/6第一階段第一階段三三 -4 0 -3 0 X1 X2 X3 X4CB XB -8 0 0

51、-1 0 0 X2 1 0 1 1/4 -2/3-4 X4 2 1 0 1/2 0第二階段第二階段管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)114的特殊情況的特殊情況: :第第1 1階段結(jié)束時(shí)階段結(jié)束時(shí), ,有人工變量有人工變量在基中取在基中取0,0,但但Xi系數(shù)全為系數(shù)全為0,0,此方程為多余方此方程為多余方程。程。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)115例例5 5、求、求minZ=4X1 +3X31/2X1 +X2 +1/2X3 -2/3X4 =23/2X1 -1/2X3 = =33X1 -6X2 +4X4 =0X1 , X2 , X3 , X4 0滿足滿足管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)116 0 0 0 0

52、1 1 1 X1 X2 X3 X4 y1 y2 y3 CB XB 5 -5 5 0 -10/3 0 0 0 1 y1 2 1/2 1 1/2 -2/3 1 0 0 1 y2 3 3/2 0 -1/2 0 0 1 0 1 y3 0 3 6 0 4 0 0 1 CB XB 5 0 -5 0 10/3 0 0 5/3 y1 2 0 2 1/2 -4/3 1 0 -1/6 y2 3 0 3 -1/2 -2 0 1 -1/2 X1 -2 1 -2 0 4/3 0 0 1/3第第 一一 階階 段段 一一二二管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)117 CB XB 0 0 0 5/4 0 5/2 0 5/4 X2 1

53、 0 1 1/4 -2/3 1/2 0 -1/2 y2 0 0 0 -5/4 0 -3/2 1 -1/4 X1 2 1 0 1/2 0 1 0 1/6 CB XB 0 0 0 0 0 1 1 1 X2 1 0 1 0 -2/3 1/5 1/5 -2/15 X3 0 0 0 1 0 1/5 -4/5 1/5 X1 2 1 0 0 0 2/5 2/5 1/15第第 一一 階階 段段三三四四管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)118 -4 0 -3 0 X1 X2 X3 X4CB XB -8 0 0 0 0 0 X2 1 0 1 0 -2/3-3 X3 0 0 0 1 0 -4 X1 2 1 0 0 0第二

54、階段第二階段的特殊情況，可將人工變量換出的特殊情況，可將人工變量換出管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)119單純形法小結(jié)：?jiǎn)渭冃畏ㄐ〗Y(jié)：1)1)、標(biāo)準(zhǔn)型中有單位基。、標(biāo)準(zhǔn)型中有單位基。2)2)、標(biāo)準(zhǔn)型中沒(méi)有單位基，用大、標(biāo)準(zhǔn)型中沒(méi)有單位基，用大M M法加人工變法加人工變量，使之構(gòu)成單位基。量，使之構(gòu)成單位基。 求求maxZ時(shí)，目標(biāo)中時(shí)，目標(biāo)中M MXj 求求minZ時(shí)，目標(biāo)中時(shí)，目標(biāo)中M MXj3)3)、判定最優(yōu)解定理：、判定最優(yōu)解定理：maxZ問(wèn)題，檢驗(yàn)數(shù)問(wèn)題，檢驗(yàn)數(shù)j 0minZ問(wèn)題，檢驗(yàn)數(shù)問(wèn)題，檢驗(yàn)數(shù)j 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1204)4)、解的幾種情況：、解的幾種情況：唯一解唯一解無(wú)

55、窮多解最優(yōu)表中非基變量檢驗(yàn)數(shù)有為無(wú)窮多解最優(yōu)表中非基變量檢驗(yàn)數(shù)有為0 0者。者。無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解 max,j 0 但但Pj 0 min,j 0 但但Pj 0無(wú)可行解無(wú)可行解最優(yōu)表中人工變量在基中，且最優(yōu)表中人工變量在基中，且0 0。建模有問(wèn)題建模有問(wèn)題5)5)、退化解問(wèn)題、退化解問(wèn)題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)121管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)122第三章 運(yùn)籌學(xué)優(yōu)化模型大連海事大學(xué)劉巍管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)123第第3節(jié)節(jié) 對(duì)偶線性規(guī)劃與影子價(jià)格對(duì)偶線性規(guī)劃與影子價(jià)格 一、對(duì)偶問(wèn)題一、對(duì)偶問(wèn)題 再談?wù)衅缚偨?jīng)理再談?wù)衅缚偨?jīng)理 v 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)124泰山工廠生產(chǎn)狀況

56、 泰山工廠可以生產(chǎn)兩種產(chǎn)品出售，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表： 目前生產(chǎn)現(xiàn)狀： 不生產(chǎn)產(chǎn)品A ，生產(chǎn)產(chǎn)品B每天30 ， 獲利3600 產(chǎn)品A產(chǎn)品B資源限量設(shè) 備勞動(dòng)力原材料9434510360200300利潤(rùn)元/kg70120管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)125招聘總經(jīng)理！ 約翰： 我應(yīng)聘！ 在現(xiàn)有資源狀況下，我可以使利潤(rùn)達(dá)到4280 ！ 方案是： 生產(chǎn)A 產(chǎn)品20 ， 生產(chǎn) B 產(chǎn)品 24 可行性：9*20+4*24=276360 4*20+5*24=200 3*20+10*24=300管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)126怎么達(dá)到的？ 約翰使用了運(yùn)籌學(xué)

57、中的線性規(guī)劃模型 問(wèn)題：如何安排生產(chǎn)計(jì)劃，使得獲利最多？ 步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg,B產(chǎn)品x2kg2、確定目標(biāo)函數(shù)：maxZ=70X1+120X23、確定約束條件：設(shè)備約束 9X1+4X2360 人力約束4X1+5X2 200 原材料約束3X1+10X2 300 非負(fù)性約束X10 X20管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)127例1圖示. 90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300ABCDEFGHIZ=70 x1+120 x2管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)128 X1=20 ,

58、x2=24 對(duì)應(yīng)的生產(chǎn)方案： 生產(chǎn)A 產(chǎn)品20 生產(chǎn) B 產(chǎn)品 24 獲利：70*20+120*24=4280管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)129問(wèn)題的最優(yōu)解*最優(yōu)解如下* 目標(biāo)函數(shù)最優(yōu)值為 : 4280 變量 最優(yōu)解 相差值 - - - x1 20 0 x2 24 0 約束 松弛/剩余變量 對(duì)偶價(jià)格 - - - 1 84 0 2 0 13.6 3 0 5.2 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - x1 36 70 96 x2 87.5 120 233.333 常數(shù)項(xiàng)數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - - - 1 276 360 無(wú)上限 2 150 200 2

59、26.923 3 227.586 300 400管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)130再談?wù)衅缚偨?jīng)理 約翰作為總經(jīng)理將泰山工廠經(jīng)營(yíng)的很好了！ 湯姆來(lái)競(jìng)爭(zhēng)了！ 競(jìng)爭(zhēng)口號(hào)： 不裁員！ 不減薪！ 不加班！ 提高利潤(rùn)5 % ！管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)131可能嗎？ 目前約翰的經(jīng)營(yíng)已經(jīng)是資源的最佳利用了！ 湯姆還有什么絕招增加利潤(rùn)呢？管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)132 這個(gè)問(wèn)題涉及到： （1） 線性規(guī)劃的對(duì)偶問(wèn)題 （2） 影子價(jià)格概念 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)133原來(lái)問(wèn)題的最優(yōu)解*最優(yōu)解如下* 目標(biāo)函數(shù)最優(yōu)值為 : 4280 變量 最優(yōu)解 相差值 - - - x1 20 0 x2 24 0 約束

60、松弛/剩余變量 對(duì)偶價(jià)格 - - - 1 84 0 2 0 13.6 3 0 5.2 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - x1 36 70 96 x2 87.5 120 233.333 常數(shù)項(xiàng)數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - - - 1 276 360 無(wú)上限 2 150 200 226.923 3 227.586 300 400管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)134 對(duì)偶性是線性規(guī)劃問(wèn)題的最重要的內(nèi)容之一。每對(duì)偶性是線性規(guī)劃問(wèn)題的最重要的內(nèi)容之一。每一個(gè)線性規(guī)劃（一個(gè)線性規(guī)劃（ LP ）必然有與之相伴而生的另一個(gè)）必然有與之相伴而生的另一個(gè)線性規(guī)劃問(wèn)題，即