運(yùn)籌學(xué)-第1章

1、運(yùn)籌學(xué)運(yùn)籌學(xué)主講人：朱建明主講人：朱建明 2014 年 9 月應(yīng)用數(shù)學(xué)系應(yīng)用數(shù)學(xué)系第第 1章章 線性規(guī)劃線性規(guī)劃線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型 1線性規(guī)劃問(wèn)題的解和單純形法2單純形的基本理論（自學(xué)） 3對(duì)偶問(wèn)題和對(duì)偶單純形法4靈敏度分析 5第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型一、線性規(guī)劃應(yīng)用舉例 (Liner Programming)（生產(chǎn)計(jì)劃問(wèn)題）某企業(yè)利用A、B、C三種資源，在計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品資源的消耗、單位產(chǎn)品利潤(rùn)等數(shù)據(jù)如下表，問(wèn)如何安排生產(chǎn)計(jì)劃使企業(yè)利潤(rùn)最大？ 產(chǎn)產(chǎn) 品品資資 源源甲甲乙乙資源限制資源限制A AB BC C1

2、12 20 01 11 11 1300300400400250250單位利潤(rùn)單位利潤(rùn)5050100100第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型例例1 1的線性規(guī)劃模型：的線性規(guī)劃模型：決策變量：x1、x2分別代表甲、乙兩種產(chǎn)品的生產(chǎn) 數(shù)量目標(biāo)函數(shù)： max z=50 x1+100 x2約束條件： s.t. x1 + x2300 2x1 + x2400 不等式約束 x2 250 x1 ，x20 非負(fù)約束一、線性規(guī)劃應(yīng)用舉例第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型一、線性規(guī)劃應(yīng)用舉例 (Liner Programming)例2（營(yíng)養(yǎng)搭配

3、問(wèn)題）如果有甲、乙、丙、丁四種食品，單價(jià)各不相同，都含有不同成份的維生素，其含量和單價(jià)如下表所示：若要保證每人每天維生素的最低需要量，則應(yīng)如何搭配各種食品，使花的錢(qián)最少？維生素維生素甲甲乙乙丙丙丁丁每人每天需要量每人每天需要量一一二二三三100010000.60.617.517.5150015000.270.277.57.5175017500.680.680 0325032500.30.33030400040001 13030單價(jià)單價(jià)0.80.80.50.50.90.91.51.5第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型一、線性規(guī)劃應(yīng)用舉例例3 靠近某河流有兩個(gè)化

4、工廠，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)m3，在兩個(gè)工廠之間有一條流量為200萬(wàn)m3的支流。兩化工廠每天排放某種有害物質(zhì)的工業(yè)污水分別為2萬(wàn)m3和1.4m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于0.2%。兩化工廠處理工業(yè)污水的成本分別為1000元/萬(wàn)m3和800元/萬(wàn)m3?，F(xiàn)在要問(wèn)在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工廠處理工業(yè)污水的費(fèi)用最小。第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型一、線性規(guī)劃應(yīng)用舉例解：解：決策變量決策變量：x x1 1、x x2 2分別代表工廠分別代表

5、工廠1 1和工廠和工廠2 2處理污水處理污水 的數(shù)量的數(shù)量( (萬(wàn)萬(wàn)m m3 3) )目標(biāo)函數(shù)：目標(biāo)函數(shù)：min min z z=1000=1000 x x1 1+800+800 x x2 2約束條件：約束條件： 第一段河流 （工廠1工廠2之間）： (2x1)/500 0.002第二段河流：0.8(2x1) +(1.4-x2)/7000.002此外有： x12 x21.4第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型一、線性規(guī)劃應(yīng)用舉例例例2 2的線性規(guī)劃模型：的線性規(guī)劃模型： min z=1000 x1+800 x2 s.t. x1 1 0.8x1 + x2 1.6

6、x1 2 x21.4 x1 ，x20 第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型 線性規(guī)劃的數(shù)學(xué)模型的一般形式：max(min) z=c1x1+c2x2+cnxn 目標(biāo)函數(shù)a11x1+a12x2+a1nxn= (,) b1a21x1+a22x2+a2nxn= (,) b2 約束條件am1x1+am2x2+amnxn= (,) bm x1，x2，xn0 模型特點(diǎn)：目標(biāo)函數(shù)(Objective function)與約束條件(Constraint)均為線性的；目標(biāo)函數(shù)實(shí)現(xiàn)極大化或極小化。第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型二、線性規(guī)劃的標(biāo)

7、準(zhǔn)型 LP標(biāo)準(zhǔn)型： max z=c1x1+c2x2+cnxn 目標(biāo)函數(shù) a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 約束條件 am1x1+am2x2+amnxn= bm x1，x2，xn0 特點(diǎn)： 1. Zmax 2. 約束條件為等號(hào) 3. 變量非負(fù) 4. 右端常數(shù)項(xiàng)大于等于零第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型二、線性規(guī)劃的標(biāo)準(zhǔn)型. . max z = CXs tAX = bX0111212122212.nnmmmnaaaaaaAaaa1(,.,)nCcc12.mbbbb12.nxxXxLP標(biāo)準(zhǔn)型的矩陣形式：第一節(jié)

8、第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型三、化非標(biāo)準(zhǔn)型為標(biāo)準(zhǔn)型1、若 min z=CTX此時(shí)可令：z =f，則 min z max -f 這樣處理所得最優(yōu)解不變舉例： min z =x1x2 s.t. 2x1 + x2=2 x1 + x2=1 x1 ，x20、第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型三、化非標(biāo)準(zhǔn)型為標(biāo)準(zhǔn)型2、若約束條件為“”時(shí)， aijxjbi aijxj + xn+i = bi xn+i 松弛變量(slack variable)3、若約束條件為“”時(shí)， aijxj bi aijxj xn+i = bi xn+i 剩余變量(

9、surplus variable）舉例： max z =x1+10 x2 s.t. x1 + 2x2100 x1 + x250 x1 ，x20第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型三、化非標(biāo)準(zhǔn)型為標(biāo)準(zhǔn)型4 4、若xk為無(wú)限制，則令xk=x+kx-k，其中x+kx-k05、若 bi 0舉例: 化下列線性規(guī)劃為標(biāo)準(zhǔn)型 min z=2x1+2x24x s.t. x1 + 3x23x3-3 x1 + 2x24x380 x1、x20，x3無(wú)限制第一節(jié)第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)型 本節(jié)作業(yè) 1-4 1-10（1） 第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)

10、題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法一、線性規(guī)劃圖解法（兩個(gè)決策變量）例例1 1的線性規(guī)劃模型：的線性規(guī)劃模型：決策變量：x1、x2分別代表甲、乙兩種產(chǎn)品的生產(chǎn) 數(shù)量目標(biāo)函數(shù)： max z=50 x1+100 x2約束條件： s.t. x1 + x2300 2x1 + x2400 x2 250 x1 ，x20 第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法一、線性規(guī)劃圖解法（兩個(gè)決策變量）1、基本概念 可行解(Feasible Solution)任一滿足約束條件的一組決策變量的數(shù)值； 可行域(Feasible Region)所有可行解組成的集合，也稱(chēng)為可行解集； 目標(biāo)

11、函數(shù)等值線(Objective functionline)位于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值；2、圖解法步驟(Procedure)（1）畫(huà)出線性規(guī)劃問(wèn)題的可行域；（2）畫(huà)出兩條目標(biāo)函數(shù)等值線；（3）平行移動(dòng)目標(biāo)函數(shù)等值線，使目標(biāo)函數(shù)在可 行域范圍內(nèi)達(dá)到最優(yōu)。第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法一、線性規(guī)劃圖解法（兩個(gè)決策變量）例1 max Z=50 x1+100 x2 s.t. x1 + x2300 2x1 + x2400 x2250 x1、x20 x2x1z* =27500BOACDz2=14000 x1 + x23002x1 + x2400 x2250該

12、問(wèn)題有唯一最優(yōu)解該問(wèn)題有唯一最優(yōu)解x x1 1=50=50；x x2 2=250=250z1=50 x1+100 x2=0第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法一、線性規(guī)劃圖解法（兩個(gè)決策變量）例2 max Z=50 x1+50 x2 s.t. x1 + x2300 2x1 + x2400 x2250 x1、x20 x2x1z1=50 x1+50 x2=0BOACDx1 + x23002x1 + x2400 x2250z* =27500z2=15000B B點(diǎn)和點(diǎn)和C C點(diǎn)所代表的坐標(biāo)點(diǎn)所代表的坐標(biāo)同時(shí)為最優(yōu)解，即該問(wèn)同時(shí)為最優(yōu)解，即該問(wèn)題有題有無(wú)窮多最優(yōu)解無(wú)窮多最

13、優(yōu)解第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法一、線性規(guī)劃圖解法（兩個(gè)決策變量）例3 max z =x1+x2 s.t. x1x2 1 x1 + 2x20 x1、x20 問(wèn)題有無(wú)界解 例4 min z =x1+x2 s.t. x1x2 1 x1 + 2x20 x1、x20 有唯一最優(yōu)解111z=32z=5OA2x1xx1x2 1x1 + 2x20第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法一、線性規(guī)劃圖解法（兩個(gè)決策變量）例5 max z =x1+x2 s.t. x1 + 2x21 x1 + x22 x1、x20 問(wèn)題無(wú)可行解 第二節(jié)第二節(jié) 線性規(guī)

14、劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法一、線性規(guī)劃圖解法（兩個(gè)決策變量）LP解的情況1、無(wú)可行解（LP不可行）可行域?yàn)榭占?、問(wèn)題有無(wú)界解（LP無(wú)界）3、唯一最優(yōu)解4、無(wú)窮多最優(yōu)解第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法一、線性規(guī)劃圖解法（兩個(gè)決策變量）直觀結(jié)論1、可行域可以是個(gè)凸多邊形，可能無(wú)界，也可能為空。2、若線性規(guī)劃問(wèn)題的最優(yōu)解存在，則它一定可以在可行域的某一個(gè)頂點(diǎn)上得到。3、若在兩個(gè)頂點(diǎn)上同時(shí)得到最優(yōu)解，則該兩點(diǎn)連線上的所有點(diǎn)都是最優(yōu)解，即LP有無(wú)窮多最優(yōu)解。4、若可行域非空有界，則一定有最優(yōu)解。第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的

15、解和單純形法二、單純形法例6 （切割損失問(wèn)題）假定某個(gè)造紙廠接到三份訂購(gòu)卷紙的定單，其長(zhǎng)和寬的要求如下表所示：該廠生產(chǎn)1米和2米兩種標(biāo)準(zhǔn)寬度的卷紙。假定紙的長(zhǎng)度無(wú)限制，即可以連接起來(lái)達(dá)到所需要的長(zhǎng)度。問(wèn)：應(yīng)如何切割才能使切割損失的面積最??？定單號(hào)碼寬（米）長(zhǎng)（米）一二三0.50.70.9100030002000第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法解：設(shè)xij是第i種標(biāo)準(zhǔn)紙按照第j種方式的切割長(zhǎng)度。如下表:設(shè)s1, s2, s3分別是把標(biāo)準(zhǔn)紙切成0.5米，0.7米，0.9米后的剩余長(zhǎng)度。 寬度1米寬卷紙X11 X12 X13 2米寬卷紙X21 X22 X

16、23 X24 X25 X26 需求0.50.70.9 2 0 0 0 1 0 0 0 12 2 1 0 00 1 0 2 1 00 0 1 0 1 2100030002000剩余寬度 0 0.3 0.10 0.3 0.1 0.1 0.4 0.2第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法 LP模型： Min z=0.3 X12 +0.1X13+0.3X22+0.1X23+0.1X24+0.4X25+0.2X26+0.5s1+0.7s2 +0.9 s3 S.t. 2 X11 +4 X21 +2 X22 +2 X23 + X24- s1 =1000 X12+X12

17、+2 X24 + X25 - s2 =3000 X13+ X23 + X25+2X26- s3 =2000 Xij0, si 0, 對(duì)一切i和j第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法例7 （產(chǎn)品配套問(wèn)題）假定一個(gè)工廠的甲、乙、丙三個(gè)車(chē)間生產(chǎn)同一產(chǎn)品，每件產(chǎn)品包括4個(gè)A零件和3個(gè)B零件。這兩種零件由兩種不同的原材料制成，而這兩種原材料的現(xiàn)有數(shù)額分別是100千克和200千克。每個(gè)生產(chǎn)班的原材料需要量和零件產(chǎn)量見(jiàn)下表：?jiǎn)枺哼@三個(gè)車(chē)間各應(yīng)開(kāi)多少班，才能使這種產(chǎn)品的配套數(shù)達(dá)到最大？車(chē)間每班進(jìn)料數(shù)（千克）每班產(chǎn)量（個(gè)數(shù)）原料1原料2 零件A零件B甲乙丙8536987

18、68594第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法 LP的一般形式：max(min) z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= (,) b1a21x1+a22x2+a2nxn= (,) b2 am1x1+am2x2+amnxn= (,) bm x1，x2，xn0 第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法 max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，x

19、n0 特點(diǎn)： 1. Zmax 2. 約束條件為等號(hào) 3. 變量非負(fù) 4. 右端常數(shù)項(xiàng)大于等于零將LP的一般形式變成LP的標(biāo)準(zhǔn)型第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法 單純形法求解LP的整體思路無(wú)窮多可行解無(wú)窮多可行解有限多可行解有限多可行解一個(gè)最優(yōu)解一個(gè)最優(yōu)解基本定理基本定理迭代迭代第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法 基本定理以下我們總假設(shè)LP有最優(yōu)解。定理 1 LP的可行域是一個(gè)凸集（凸多面體）凸集（凸多面體）。定理 2 LP的可行域的一個(gè)點(diǎn)是極點(diǎn)極點(diǎn)當(dāng)且僅當(dāng)是它是一個(gè) 基本可行解基本可行解。定理 3 LP的

20、最優(yōu)解可在一個(gè)基本可行解（極點(diǎn)）上取到。定理 4 LP的基本可行解的個(gè)數(shù)是有限的。第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法 舉例：找出下列LP所有的基及其對(duì)應(yīng)的基本解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化為標(biāo)準(zhǔn)型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法 基基基本解基本解可行否可行否 目標(biāo)值目標(biāo)值對(duì)應(yīng)圖對(duì)應(yīng)圖中的點(diǎn)中的點(diǎn)

21、B1=(P1，P2)B2=(P1，P3)B3=(P1，P4)B4=(P2，P3)B5=(P2，P4)B6=(P3，P4)X1=(20，20，0，0)TX2=(30，0，40，0)TX3=(50，0，0，80)TX4=(0，60，80，0)TX5=(0，100/3，0，160/3)TX6=(0，0，100，120)T 200180400/30BCDEAOABCDEOx1x22x1+3x2 =1004x1 + 2x2 =120第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法 單純形法求LP的一般步驟步驟1：將LP化為標(biāo)準(zhǔn)型步驟2：選定一個(gè)初始基本可行解（人工變量法）步

22、驟3：迭代到另外一個(gè)基本可行解，使得目標(biāo) 函數(shù)值有所改進(jìn)（檢驗(yàn)數(shù)計(jì)算）步驟4：重復(fù)步驟3，直到目標(biāo)函數(shù)值不再改進(jìn)時(shí) 算法停止（所有檢驗(yàn)數(shù)大于等于零）第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法解下列線性規(guī)劃問(wèn)題: 12231241251252515. .62245,0Max zxxxxs txxxxxxxxx基基解解345xxxz12345xxxxx例8第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法 例8(續(xù)）24231242451252183351521. .46641166,0M axzxxxxs txxxxxxxxx基基解解12345

23、xxxxxz315xxx02 / 301 / 300510012 / 601 / 6004 / 601 / 61第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法 例8（續(xù)）45345145245125111824251515422117. .422133422,0M axzxxxxxs txxxxxxxxx基基解解12345xxxxxz312xxx0001 / 41 / 20015 / 415 / 21001/ 41/ 20101/ 43 / 218215/27/23/2第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法 單純形表格求LP的一般步驟基基解解11

24、mmnxxxxz1mnxx100mcc11111001mmmmaaaa01mbb2 2、最優(yōu)性檢驗(yàn) 若表中所有 ,則已得最優(yōu)解,算法停止。若存在檢驗(yàn)數(shù) ,則若 ,則原問(wèn)題無(wú)解,算法停;否則轉(zhuǎn)3。0jz 0jz 0jp 1、初始表格第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法 單純形表格求LP的一般步驟 (1) 確定進(jìn)基變量 在所有負(fù)的檢驗(yàn)數(shù)中,找出負(fù)的最大的一個(gè),對(duì)應(yīng)的變量即為進(jìn) 基變量,記為 。 (2) 確定出基變量令 則 為出基變量, 為旋轉(zhuǎn)元 (3) 在“基”這一列中,用進(jìn)基變量替換出基變量.(4) 用初等行變換,將旋轉(zhuǎn)元變成1,旋轉(zhuǎn)元所在列其余元素?fù)Q成0。 同樣用

25、初等行變換將檢驗(yàn)數(shù)中相應(yīng)的元素變?yōu)?。 kxmin|0ilikiklkbbaaalxlka 4、重復(fù)2,3,直到計(jì)算結(jié)束。3、列出新單純形表第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法 例9（練習(xí)） 解下列線性規(guī)劃問(wèn)題：12312313121233252430. .324604420,0Max zxxxxxxs txxxxxxx第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法（人工變量法） 例10 解下列線性規(guī)劃問(wèn)題（大M法）：1212121212433. .43623,0Min zxxxxs txxxxxx12121231241

26、234433. .43623,0Max zxxxxstxxxxxxx xx x 標(biāo)準(zhǔn)化：第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法 加入人工變量:基基 4 1 0 0 M M 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3123456xxxxxxz564xxx12561251236124123456433. .43623,0Max zxxMxMxxxxs txxxxxxxxxxxxx 例10（續(xù)）第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法例10（續(xù)） 0 -(1+5M)/3 M (4-7M)/3 0 0 -4

27、-2M 1 1/3 00 1/3 0 05/3 -1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 2z164xxx基基解解4-7M 1-4M M 0 0 0-9M 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3123456xxxxxx564xxxz第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法例10（續(xù)） 0 0 0 1/5 -7/5+M M -18/5 1 0 0-1/5 2/5 0 0 1 0 3/5 -1/5 0 0 0 1 1 1 -1 3/5 6/5 0z123xxx基基解解 0 0 -1/5 0 -8/5+M

28、 1/5+M -18/5 1 0 1/5 03/5 -1/5 0 1 -3/5 0 -4/5 3/5 0 0 1 1 1 -1 3/5 6/5 0123456xxxxxx124xxxz*(3/5,6/5)TX *18/5z 最優(yōu)解：最優(yōu)值：第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法（人工變量法） 兩階段法兩階段法 第一階段第一階段: : 添加人工變量后添加人工變量后, ,引入一個(gè)輔助問(wèn)題引入一個(gè)輔助問(wèn)題. .保留原約束條件保留原約束條件, ,目標(biāo)函目標(biāo)函數(shù)改為數(shù)改為 , ,這里這里 為人工變量為人工變量. .求這個(gè)輔助求這個(gè)輔助問(wèn)題的解問(wèn)題的解. .考察下列

29、情況考察下列情況: : (i) (i) 輔助問(wèn)題有最優(yōu)解輔助問(wèn)題有最優(yōu)解 , ,表明原問(wèn)題有可行解表明原問(wèn)題有可行解, ,輔助問(wèn)輔助問(wèn)題的最優(yōu)解即為原問(wèn)題的一個(gè)可行解。題的最優(yōu)解即為原問(wèn)題的一個(gè)可行解。 (ii) (ii) 輔助問(wèn)題有最優(yōu)解輔助問(wèn)題有最優(yōu)解 , , 表明原問(wèn)題無(wú)可行解表明原問(wèn)題無(wú)可行解, ,即可即可行域?yàn)榭占?。行域?yàn)榭占?第二階段第二階段: : 去除人工變量去除人工變量, ,還原目標(biāo)函數(shù)還原目標(biāo)函數(shù), ,繼續(xù)求解。繼續(xù)求解。 12minhwrrr*0w ir*0w 第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法二、單純形法（人工變量法） 例10 解下列線性

30、規(guī)劃問(wèn)題（兩階段法法）：1212121212433. .43623,0Min zxxxxs txxxxxx第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法例10 （兩階段法續(xù)）第一階段： 基基 0 0 0 0 1 1 0 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3123456xxxxxxw564xxx56125123612412345633. .43623,0Min wxxxxxs txxxxxxxxxxxxx第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法例10 （兩階段法續(xù)）第一階段： 0 -5/3 1 07/3

31、 0 -2 1 1/3 00 1/3 0 05/3 -1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 2w164xxx基基解解 -7 -4 1 0 0 0 -9 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3123456xxxxxx564xxxw第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法例10 （兩階段法續(xù)）第一階段：基基解解 0 0 0 0 1 1 0 1 01/5 03/5 -1/5 0 1-3/50-4/5 3/5 0 0 1 1 1 -1 3/5 6/5 0123456xxxxxx124xxxw基基 解解 4

32、 1 0 0 0 1 01/5 0 0 1-3/50 0 0 1 1 3/5 6/5 01234xxxxz124xxx 第二階段,換上原目標(biāo)函數(shù),并刪去人工變量：第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法例10 （兩階段法續(xù)）第二階段：基基 解解 0 0 0 1/5 -18/5 1 0 0-1/5 0 1 0 3/5 0 0 1 0 3/5 6/5 01234xxxxz123xxx基基 解解 0 0 -1/5 0 -18/5 1 01/5 0 0 1-3/50 0 0 1 1 3/5 6/5 01234xxxxz124xxx第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)

33、劃問(wèn)題的解和單純形法 幾種特殊情況1、退化解當(dāng)最優(yōu)解中有基變量取值為0時(shí), 就稱(chēng)為退化解。2、無(wú)界解 當(dāng)進(jìn)基變量所對(duì)應(yīng)的列向量小于等于0時(shí),則有無(wú)界解。3、多重解(無(wú)窮多個(gè)解) 在最優(yōu)表中,有非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)為0,則有多重解(無(wú)窮多個(gè)最優(yōu)解)。4、無(wú)解(無(wú)可行解) 線性規(guī)劃添加人工變量后,若人工變量仍留在最優(yōu)基中,則原規(guī)劃問(wèn)題無(wú)可行解。 本節(jié)作業(yè) 1-15 1-19（2） 1-22（1） 1-26 第二節(jié)第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法線性規(guī)劃問(wèn)題的解和單純形法第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法一、對(duì)偶問(wèn)題的提出（生產(chǎn)計(jì)劃問(wèn)題）某企業(yè)利用A、B、C三種資源，在計(jì)劃

34、期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品資源的消耗、單位產(chǎn)品利潤(rùn)等數(shù)據(jù)如下表，問(wèn)如何安排生產(chǎn)計(jì)劃使企業(yè)利潤(rùn)最大？ 產(chǎn)產(chǎn) 品品資資 源源甲甲乙乙資源限制資源限制A AB BC C1 12 20 01 11 11 1300300400400250250單位利潤(rùn)單位利潤(rùn)5050100100第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法一、對(duì)偶問(wèn)題的提出 例例1 1的的LPLP模型：模型： 設(shè) x1、x2分別代表甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量 max z=50 x1+100 x2 s.t. x1 + x2300 2x1 + x2400 x2 25 x1 ，x20 同樣是上述問(wèn)題，提問(wèn)同樣是上述問(wèn)

35、題，提問(wèn)：企業(yè)不安排生產(chǎn)，而轉(zhuǎn)讓 三種資源，應(yīng)如何給三種資源定價(jià)？第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法一、對(duì)偶問(wèn)題的提出設(shè) y1、y2、y3分別代表A、B、C三種資源的價(jià)格（最低轉(zhuǎn)讓凈收入），則LP模型為： min w=300y1 +400y2 +250y3 s.t. y1+ 2y2 50 y1+ y2+ y3 100 y1、y2、y3 0例1（續(xù)）第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法一、對(duì)偶問(wèn)題的提出 問(wèn)題B: min w=300y1 +400y2 +250y3 s.t. y1+ 2y2 50 y1+ y2+ y3 100 y1、y2、y3 0 稱(chēng)

36、問(wèn)題B為問(wèn)題A的對(duì)偶問(wèn)題對(duì)偶問(wèn)題，問(wèn)題A為原問(wèn)題原問(wèn)題。 問(wèn)題A: max z=50 x1+100 x2 s.t. x1 + x2300 2x1 + x2400 x2250 x1、x20第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶問(wèn)題的定義1 1221112111121max. .,0nnnmmmnnmnzc xc xc xaaaxbstaaaxbxx11221121111121min. .,0mmmnnmnmnmwb yb yb yaaaycstaaaycyy原問(wèn)題：原問(wèn)題：對(duì)偶問(wèn)題：對(duì)偶問(wèn)題：第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶問(wèn)題的定義

37、原問(wèn)題：原問(wèn)題：對(duì)偶問(wèn)題：對(duì)偶問(wèn)題：max.0z CXstAXbXmin. .0wYbstYACY性質(zhì)：對(duì)偶問(wèn)題的對(duì)偶問(wèn)題即為原問(wèn)題。矩陣形式：第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶問(wèn)題的定義對(duì)偶關(guān)系表原問(wèn)題原問(wèn)題（或?qū)ε紗?wèn)題）（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題對(duì)偶問(wèn)題（或原問(wèn)題）（或原問(wèn)題）目標(biāo)函數(shù)目標(biāo)函數(shù)max zmin w目標(biāo)函數(shù)目標(biāo)函數(shù)變量變量n個(gè)個(gè)00無(wú)約束無(wú)約束n個(gè)個(gè)=約束條件約束條件約束條件約束條件m個(gè)個(gè)=m個(gè)個(gè)00無(wú)約束無(wú)約束變量變量約束條件右端常數(shù)項(xiàng)約束條件右端常數(shù)項(xiàng)目標(biāo)函數(shù)變量系數(shù)目標(biāo)函數(shù)變量系數(shù)目標(biāo)函數(shù)變量系數(shù)目標(biāo)函數(shù)變量系數(shù)約束條件右端常數(shù)項(xiàng)約束條件右端

38、常數(shù)項(xiàng)第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶問(wèn)題的定義例2 寫(xiě)出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 max z=2x1+2x24x3 s.t. x1 + 3x2 + 3x3 30 4x1 + 2x2 + 4x380 x1、x2，x30解：其對(duì)偶問(wèn)題為：min w=30y1+ 80y2s.t. y1 + 4y2 2 3y1 + 2y2 2 3y1 + 4y2 4 y1、y20第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶問(wèn)題的定義例3 寫(xiě)出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 min z=2x1+8x24x3 s.t. x1 + 3x2 3x3 30 x1 + 5x

39、2 + 4x3 = 80 4x1 + 2x24x3 50 x10、x20，x3無(wú)限制max w=30y1+80 y2+50y3 s.t. y1y2 + 4y3 2 3y1+5y2 + 2y3 8 3y1 + 4y24y3=4 y10，y2無(wú)限制，y30對(duì)偶問(wèn)題為：第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶基本定理max.0z CXstAXbXmax.( , , ),0BBNNIIBNIBNIz C XC XC XXstB N IXbXX XX考慮如下線性規(guī)劃問(wèn)題：第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶基本定理單純形表的矩陣形式 基基 解解z基

40、基解解 zBXNXIXBCNCICIXBNI0bBXNXIX01BNC B N C1BIC BC1BC B bBXI1B N1B1B b初始表：迭代后表：第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶基本定理1111min.00 0BBBBNBIw C B bstC B B CC B N CC BC構(gòu)造如下線性規(guī)劃問(wèn)題：min. BNIw YbstYB CYN CYC令 （單純形乘子，對(duì)偶問(wèn)題的最優(yōu)解） 1BYC B第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶基本定理對(duì)偶關(guān)系示意圖非最優(yōu)非最優(yōu)可行可行.最優(yōu)最優(yōu)最優(yōu)最優(yōu)可行不可行不可行不可行.1BC B

41、 b原問(wèn)題對(duì)偶問(wèn)題第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法二、對(duì)偶基本定理基本定理XYCXYbXYCXYbXY定理1 （弱對(duì)偶性）若 是原問(wèn)題的可行解， 是對(duì)偶問(wèn)題的可行解，則有 。 定理2 （最優(yōu)性）設(shè) 、 分別為原問(wèn)題和對(duì)偶問(wèn)題的可行解。若 ，則 、 分別為原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。定理3 （強(qiáng)對(duì)偶性）若原問(wèn)題和對(duì)偶問(wèn)題均有可行解，則兩者都有最優(yōu)解，且最優(yōu)值相等。 第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法三、對(duì)偶單純形法1212121212min2.3 3436 23 ,0zxxstxxxxxxx x例4 用對(duì)偶單純形法求如下線性規(guī)劃：*123/5,6/

42、5xx最優(yōu)解：最優(yōu)值：*12/5z 第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法三、對(duì)偶單純形法 對(duì)偶單純形法的基本步驟 1、將約束條件化成小于等于約束，列出初始單純形表。 2、 確定出基變量。選右端向量 中，負(fù)的最大的基變量（若 ，則已得最優(yōu)解）記為 。 3、 確定進(jìn)基變量。若第 行系數(shù) ，則原問(wèn)題無(wú)解。 反之，令 即為進(jìn)基變量， 為旋轉(zhuǎn)元。 4、用初等行變換，得到一個(gè)新的基，重復(fù)以上步驟直到最優(yōu)。sXrXmax|0jsrjjrjrszzaaarsab0br0rja 第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法四、對(duì)偶問(wèn)題的經(jīng)濟(jì)意義 max z=50 x1+100

43、 x2 min w=300y1+400y2+250y3 s.t. x1 + x2300 s.t. y1+ 2y2 50 2x1 + x2400 y1 + y2 + y3100 x2250 y1、y2、y3 0 x1、x20例1（續(xù)）最優(yōu)解：*1250,250 xx最優(yōu)解：*12350,0,50yyy影子價(jià)格：約束條件右端項(xiàng)增加一個(gè)單位，目標(biāo)函數(shù)值的增加量（即為對(duì)偶問(wèn)題的最優(yōu)解） 本節(jié)作業(yè) 1-38（2）（3） 1-48 1-42 第四節(jié)第四節(jié) 對(duì)偶問(wèn)題和對(duì)偶單純形法對(duì)偶問(wèn)題和對(duì)偶單純形法第第 五節(jié)五節(jié) 靈敏度分析靈敏度分析一、引例某企業(yè)利用甲、乙兩種原料，生產(chǎn)A、B、C三種產(chǎn)品，每種的產(chǎn)品單位

44、利潤(rùn)及原材料消耗定額等數(shù)據(jù)如下表，問(wèn)如何安排生產(chǎn)計(jì)劃使企業(yè)利潤(rùn)最大？ 產(chǎn)產(chǎn) 品品原料原料ABC供應(yīng)量供應(yīng)量甲甲乙乙1 12 20 02 21 11 130308080單位利潤(rùn)單位利潤(rùn)4 43 32 2第第 五節(jié)五節(jié) 靈敏度分析靈敏度分析一、引例例例1 1的的LPLP模型：模型：設(shè)x1、x2、x3分別代表A、B、C三種產(chǎn)品的生產(chǎn)數(shù)量，則max z=4x1+3x2+2x3 max z=4x1+3x2+2x3s.t. x1+ x330 s.t. x1+ x3+s1=30 2x1+2x2+x380 2x1+2x2+x3 +s2=80 x1 ，x20 x1 ，x2 , s1 ，s20第第 五節(jié)五節(jié) 靈敏度分析靈敏度分析一、引例初始單純形表：初始單純形表：基基解解12312xxxssz12ss4320 01 0 1 1 02 2 1 0 1030