第02章 線性規(guī)劃與單純形法

畢德春遼東學(xué)院信息技術(shù)學(xué)院運(yùn)籌學(xué)第二章

線性規(guī)劃與單純形法第一節(jié)線性規(guī)劃的數(shù)學(xué)模型一類是已有一定數(shù)量的資源（人力、物質(zhì)、時(shí)間等），研究如何合理地使用它們，才能使完成的任務(wù)量為最大。另一類是當(dāng)一項(xiàng)任務(wù)確定以后，研究如何統(tǒng)籌安排，才能使完成任務(wù)所耗費(fèi)的資源量為最少?！獙?shí)際上，上述兩類問題是一個(gè)問題的兩個(gè)不同的方面，都是求問題的最優(yōu)解（max或min）。

例：用一塊邊長(zhǎng)為a的正方形鐵皮做一個(gè)容器，應(yīng)如何裁剪，使做成的容器的容積為最大。axV=（a-2x）2x第一節(jié)線性規(guī)劃的數(shù)學(xué)模型例:常山機(jī)械廠生產(chǎn)Ⅰ和Ⅱ兩種產(chǎn)品。生產(chǎn)中需使用A、B、C三種設(shè)備進(jìn)行加工，加工每件Ⅰ產(chǎn)品或Ⅱ產(chǎn)品所需的設(shè)備機(jī)時(shí)數(shù)、利潤(rùn)值及每種設(shè)備可利用機(jī)時(shí)數(shù)列于下表，請(qǐng)問：充分利用設(shè)備機(jī)臺(tái)時(shí)，工廠應(yīng)生產(chǎn)Ⅰ和Ⅱ產(chǎn)品各多少件才能獲得最大利潤(rùn)？試列出相應(yīng)的線性規(guī)劃數(shù)學(xué)模型。ABC產(chǎn)品利潤(rùn)／（元／件）Ⅰ2402Ⅱ2053設(shè)備可用機(jī)時(shí)數(shù)（工時(shí)）121615第一節(jié)線性規(guī)劃的數(shù)學(xué)模型解：設(shè)Ⅰ、Ⅱ產(chǎn)品的生產(chǎn)數(shù)量分別為x1和x2，建立問題數(shù)學(xué)模型如下：maxz=2x1+3x22x1+2x2≤124x1≤165x2≤15xj≥0，j=1，2第一節(jié)線性規(guī)劃的數(shù)學(xué)模型max（或min）z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤（＝，≥）b1a21x1+a22x2+…+a2nxn≤（＝，≥）b2：am1x1+am2x2+…+amnxn≤（＝，≥）bmx1,x2,…xn≥0s.t.目標(biāo)函數(shù)約束條件模型一般形式第一節(jié)線性規(guī)劃的數(shù)學(xué)模型模型特點(diǎn)1.都用一組決策變量X=(x1,x2,…,xn)T表示某一方案，且決策變量取值非負(fù)。2.都有一個(gè)要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成決策變量的線性函數(shù)。3.都有一組約束條件，可以用決策變量的線性等式或線性不等式來表示?！獫M足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃第一節(jié)線性規(guī)劃的數(shù)學(xué)模型其它形式①求和形式②矩陣形式?jīng)Q策變量常數(shù)項(xiàng)系數(shù)矩陣價(jià)值系數(shù)其中：第一節(jié)線性規(guī)劃的數(shù)學(xué)模型建模步驟1.確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目問什么就設(shè)什么為決策變量。2.找出所有限定條件：即決策變量受到的所有的約束；3.寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確是max還是min。第一節(jié)線性規(guī)劃的數(shù)學(xué)模型例：某工廠生產(chǎn)A、B兩種產(chǎn)品，有關(guān)資料如下表所示：解：設(shè)總成本為z，A、B產(chǎn)品銷量為x1、x2，產(chǎn)品C的銷售量為x3，報(bào)廢量為x4，則：

maxz=4x1+10x2+3x3－2x4

2x1+3x2≤123x1+4x2≤24

－2x2+x3+x4=0x3≤5

x1、x2

、x3

、x4≥0第一節(jié)線性規(guī)劃的數(shù)學(xué)模型ABC工時(shí)限制銷售報(bào)廢工序12312工序23424單位利潤(rùn)（百元）4103-2注：每生產(chǎn)單位產(chǎn)品B可得到2單位副產(chǎn)品C，據(jù)預(yù)測(cè)，市場(chǎng)上產(chǎn)品C的最大銷量為5單位，若產(chǎn)品C銷售不出去，則報(bào)廢。船只種類船只數(shù)拖輪30A型駁船34B型駁船52航線號(hào)合同貨運(yùn)量12002400航線號(hào)船隊(duì)類型編隊(duì)形式貨運(yùn)成本（千元／隊(duì)）貨運(yùn)量（千噸）拖輪A型駁船B型駁船1112—362521—4362023224724041—42720例：某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示，問應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最?。康谝还?jié)線性規(guī)劃的數(shù)學(xué)模型解：設(shè)xj為第j號(hào)類型船隊(duì)的隊(duì)數(shù)（j=1，2，3，4），z為總貨運(yùn)成本minz=36x1+36x2+72x3+27x4

x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2

＝20040x3+20x4＝400xj≥0j=1,2,3,4第一節(jié)線性規(guī)劃的數(shù)學(xué)模型例：合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來做，圓鋼長(zhǎng)度為4m?，F(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？解：這是個(gè)條材下料問題，設(shè)切口寬度為零啊，有10種下料方式，如下表所示。方案規(guī)格12345678910需求量A22111000001000B10210432101000C

01023012451000余料（m）00.30.50.10.400.30.60.20.5第一節(jié)線性規(guī)劃的數(shù)學(xué)模型解：設(shè)xj(j=1,2…,10)為第j種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學(xué)模型為:

方案規(guī)格12345678910需求量A22111000001000B10210432101000C01023012451000余料（m）00.30.50.1o.400.30.60.20.5第一節(jié)線性規(guī)劃的數(shù)學(xué)模型例:配料問題。某鋼鐵公司生產(chǎn)一種合金，要求的成分規(guī)格是：錫不少于28%，鋅不多于15%，鉛恰好10%，鎳要界于35%~55%之間，不允許有其他成分。鋼鐵公司擬從五種不同級(jí)別的礦石中進(jìn)行冶煉，每種礦物的成分含量和價(jià)格如下表所示。礦石雜質(zhì)在治煉過程中廢棄，現(xiàn)要求每噸合金成本最低的礦物數(shù)量。假設(shè)礦石在冶煉過程中合金含量沒有發(fā)生變化。

合金礦石錫%鋅%鉛%鎳%雜質(zhì)費(fèi)用（元/t）125101025303402400030302603015520601804202004020230585151755190第一節(jié)線性規(guī)劃的數(shù)學(xué)模型解:設(shè)xj（j=1,2，…，5）是第j種礦石數(shù)量，得到下列線性規(guī)劃模型礦石錫%鋅%鉛%鎳%雜質(zhì)%費(fèi)用（元/t）125101025303402400030302603015520601804202004020230585151755190第一節(jié)線性規(guī)劃的數(shù)學(xué)模型第五年：(x7/2+x9)=x8+2x5第一年：x1+x2=200(萬元)第二年：(x1/2+x3)+x4=x2第三年(x3/2+x5)+x6=x4+2x1第四年：(x5/2+x7)+x8=x6+2x3到第六年實(shí)有資金總額為x9+2x7，整理后得到下列線性規(guī)劃模型解：x1：第一年的投資；x2：第一年的保留資金

x3：第二年新的投資；x4：第二年的保留資金

x5：第三年新的投資；x6：第三年的保留資金

x7：第四年新的投資x8：第四年的保留資金

x9：第五年的保留資金例：投資問題。某投資公司在第一年有200萬元資金，每年都有如下的投資方案可供考慮采納：“假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的一倍金額”。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多。第一節(jié)線性規(guī)劃的數(shù)學(xué)模型x1：第一年的投資；x2：第一年的保留資金x3：第二年新的投資；x4：第二年的保留資金x5：第三年新的投資；x6：第三年的保留資金x7：第四年新的投資x8：第四年的保留資金x9：第五年的保留資金第一節(jié)線性規(guī)劃的數(shù)學(xué)模型例:均衡配套生產(chǎn)問題。某產(chǎn)品由2件甲、3件乙零件組裝而成。兩種零件必須經(jīng)過設(shè)備A、B上加工，每件甲零件在A、B上的加工時(shí)間分別為5分鐘和9分鐘，每件乙零件在A、B上的加工時(shí)間分別為4分鐘和10分鐘?，F(xiàn)有2臺(tái)設(shè)備A和3臺(tái)設(shè)備B，每天可供加工時(shí)間為8小時(shí)。為了保持兩種設(shè)備均衡負(fù)荷生產(chǎn)，要求一種設(shè)備每天的加工總時(shí)間不超過另一種設(shè)備總時(shí)間1小時(shí)。怎樣安排設(shè)備的加工時(shí)間使每天產(chǎn)品的產(chǎn)量最大。設(shè)備A、B每天加工工時(shí)的約束為要求一種設(shè)備每臺(tái)每天的加工時(shí)間不超過另一種設(shè)備1小時(shí)的約束為解：設(shè)x1、x2為每天加工甲、乙兩種零件的件數(shù)，則產(chǎn)品的產(chǎn)量是第一節(jié)線性規(guī)劃的數(shù)學(xué)模型目標(biāo)函數(shù)線性化。產(chǎn)品的產(chǎn)量y等價(jià)于整理得到線性規(guī)劃模型約束線性化。將絕對(duì)值約束寫成兩個(gè)不等式第一節(jié)線性規(guī)劃的數(shù)學(xué)模型例：運(yùn)輸問題?？偣臼盏缴虾1，青島B2

，西安B3三家商場(chǎng)的電機(jī)訂單，需求分別為100臺(tái)，80臺(tái)，90-120臺(tái)，現(xiàn)有北京A1，武漢A2二個(gè)倉庫，庫存分別為200臺(tái)，150臺(tái)，所需運(yùn)費(fèi)如下表，問如何調(diào)運(yùn)電機(jī)，可使總運(yùn)費(fèi)最少？第一節(jié)線性規(guī)劃的數(shù)學(xué)模型B1B2B3庫存A1152118200A2202516150需求1008090-120庫存約束需求約束非負(fù)約束問題的數(shù)學(xué)模型第一節(jié)線性規(guī)劃的數(shù)學(xué)模型解：設(shè)xij為從倉庫Ai調(diào)到商場(chǎng)Bj的電機(jī)數(shù)量（i=1,2,j=1,2,3），則目標(biāo)函數(shù)是例:一個(gè)木材儲(chǔ)運(yùn)公司有很大的倉庫用以儲(chǔ)運(yùn)出售木材。由于木材季度價(jià)格的變化，該公司于每季度初購進(jìn)木材，一部分于本季度內(nèi)出售，一部分儲(chǔ)存起來以后出售。已知該公司倉庫的最大儲(chǔ)存量為2000萬米3，儲(chǔ)存費(fèi)用為（70+100u）千元/萬米3，u為存儲(chǔ)時(shí)間（季度數(shù)）。已知每季度的買進(jìn)賣出價(jià)及預(yù)計(jì)的銷售量如下表所示。由于木材不宜久貯，所有庫存木材應(yīng)于每年秋末售完。為使售后利潤(rùn)最大，試建立這個(gè)問題的線性規(guī)劃模型。季度買進(jìn)價(jià)（萬元/萬米3）賣出價(jià)（萬元/萬米3）預(yù)計(jì)銷售量（萬米3）冬4104251000春4304401400夏4604652000秋4504551600第一節(jié)線性規(guī)劃的數(shù)學(xué)模型解：設(shè)yi分別表示冬、春、夏、秋四個(gè)季度采購的木材數(shù)，xij代表第i季度采購的用于第j季度銷售的木材數(shù)。季度買進(jìn)價(jià)（萬元/萬米3）賣出價(jià)（萬元/萬米3）預(yù)計(jì)銷售量（萬米3）冬4104251000春4304401400夏4604652000秋4504551600第一節(jié)線性規(guī)劃的數(shù)學(xué)模型例:有一艘貨輪，分前、中、后三個(gè)艙位，容積與最大允許載重量如表所示。現(xiàn)有三種貨物待運(yùn)，已知有關(guān)數(shù)據(jù)列于表。為了航運(yùn)安全，要求前、中、后艙在實(shí)際載重量上大體保持各艙最大允許載重量的比例關(guān)系，具體要求前、后艙分別與中艙之間載重量比例上偏差不超過15%，前、后艙之間不超過10%。問該貨輪應(yīng)裝載A，B，C各多少件，運(yùn)費(fèi)收入為最大？試建立這個(gè)問題的線性規(guī)劃模型。前艙中艙后艙最大允許載重量（噸）200030001500容積（立方米）400054001500商品數(shù)量（件）每件體積（立方米/件）每件重量（噸/件）運(yùn)價(jià)（元/件）A6001081000B100056700C80075600第一節(jié)線性規(guī)劃的數(shù)學(xué)模型解：設(shè)表示xij裝于第j(j=1,2,3)艙位的第i(i=1,2,3)種商品的數(shù)量艙位載重限制艙位體積限制商品數(shù)量限制平衡條件前艙中艙后艙重量200030001500容積400054001500商品數(shù)量體積重量運(yùn)價(jià)A6001081000B100056700C80075600第一節(jié)線性規(guī)劃的數(shù)學(xué)模型Maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2：am1x1+am2x2+…+amnxn＝bmx1,x2,…xn≥0s.t.目標(biāo)函數(shù)：約束條件：第二節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式1、目標(biāo)函數(shù)極小值轉(zhuǎn)化為極大值，即為：

因?yàn)榍髆inz等價(jià)于求max(-z)，令z’=-z，即化為：第二節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式2、約束條件為不等式轉(zhuǎn)化為等式xn+1≥0松弛變量如何處理？第二節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式3、右端項(xiàng)bi<0時(shí)，只需將等式兩端同乘（-1）則右端項(xiàng)必大于零第二節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式4、決策變量無非負(fù)約束轉(zhuǎn)化為非負(fù)

設(shè)xj

沒有非負(fù)約束，若xj≤0，可令xj=-xj’

，則xj’≥0；

又若xj

為自由變量，即xj

可為任意實(shí)數(shù)，可令xj=xj’-xj’’，且xj’,xj’’≥0第二節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式例：試將下面線性規(guī)劃問題minz=-x1+2x2-3x3

s.t.x1+x2+x3≤7x1-x2+x3≥2

-3x1+x2+2x3=-5

x1,x2

≥0化為標(biāo)準(zhǔn)形式。解：令x3=x4-x5其中x4、x5≥0；對(duì)第一個(gè)約束條件加上松弛變量x6

；對(duì)第二個(gè)約束條件減去松弛變量x7

；對(duì)第三個(gè)約束條件兩邊乘以“-1”；令z’=-z把求minz改為求maxz’maxz’=x1-2x2+3x4-3x5

s.t.

x1+x2+x4-x5+x6=7

x1-x2+x4-x5-x7=2

3x1-x2-2x4+2x5=5

x1,x2,x4,x5,x6,x7≥0

第二節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式例：將下列數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)型maxz=4x1+5x2+2x3x1+x2≤45x1+x2+2x3≤80x1+x2-4x3≥-40x1,x2≥0,x3無約束maxz=4x1+5x2+2x’3+2x’’3x1+x2+x4﹦45x1+x2+2（x”3+x”3)+x5﹦80-x1-x2+4（x”3+x”3)++x6﹦40x1,x2,x’3,x’’3,x4,x5,x6≥0第二節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式例：將下列線性規(guī)劃化為標(biāo)準(zhǔn)形第二節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式max

z=x1+3x2 s.t.x1+x2≤6-x1+2x2≤8 x1≥0,x2≥0可行域目標(biāo)函數(shù)等值線最優(yōu)解Z（4/3,14/3）=46/364-860x1x2第三節(jié)圖解法x1x2O10204010203040(3,4)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=85第三節(jié)圖解法246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)minZ=x1+2x2(1,2)第三節(jié)圖解法246x1x2246X（2）＝（3,1）X（1）＝（1,3）(5,5)minZ=5x1+5x2有無窮多個(gè)最優(yōu)解，即具有多重解,通解為0≤α≤1當(dāng)α=0.5時(shí)，Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)第三節(jié)圖解法246x1x2246(1,2)無界解(無最優(yōu)解)maxZ=x1+2x2第三節(jié)圖解法x1x2O10203040102030405050無可行解，即無最優(yōu)解maxZ=10x1+4x2第三節(jié)圖解法圖解法的重要結(jié)論:

1.線性規(guī)劃的解通常會(huì)有四種情況，即唯一解、無窮多解、無界解和無可行解。

2.線性規(guī)劃問題的可行域是凸集（即凸多邊形）；

3.若線性規(guī)劃存在最優(yōu)解，一定在可行域的某個(gè)頂點(diǎn)上得到；

4.若線性規(guī)劃存在多重最優(yōu)解，則有兩個(gè)頂點(diǎn)及其連線上的一切點(diǎn)均取得最優(yōu)解。第三節(jié)圖解法凸集凸集不是凸集極點(diǎn)預(yù)備知識(shí)：凸集和頂點(diǎn)第四節(jié)單純形法線性規(guī)劃的基矩陣、基變量、非基變量==目標(biāo)函數(shù)約束條件行列式≠0基矩陣右邊常數(shù)在本例中，最多可以有基矩陣第四節(jié)單純形法例：線性規(guī)劃

求所有基矩陣解:約束方程的系數(shù)矩陣為2×5矩陣容易看出r(A)=2，2階子矩陣有C52=10個(gè)，其中第1列與第3列構(gòu)成的2階矩陣不是一個(gè)基，基矩陣只有9個(gè)，即第四節(jié)單純形法例:求下列約束方程所對(duì)應(yīng)的線性規(guī)劃的所有基本解，基本可行解。解：化為標(biāo)準(zhǔn)形式為2×4階矩陣。且R(A)=2,所以該線性規(guī)劃基的個(gè)數(shù)≤=6個(gè)

取,為基變量，

若令非基變量，約束方程組為

可得對(duì)應(yīng)的基本解是一個(gè)基本可行解。第四節(jié)單純形法按相同步驟，可求得線性規(guī)劃其他4個(gè)基：對(duì)應(yīng)基本解是一個(gè)基本可行解。對(duì)應(yīng)基本解是一個(gè)基本可行解。對(duì)應(yīng)基本解不是一個(gè)基本可行解。對(duì)應(yīng)基本解是一個(gè)基本可行解。第四節(jié)單純形法若利用圖解法畫出線性規(guī)劃的可行域，如圖，CDOBA448第四節(jié)單純形法得到最優(yōu)解或證明最優(yōu)解不存在標(biāo)準(zhǔn)型從可行域某個(gè)頂點(diǎn)開始檢查該點(diǎn)是否最優(yōu)解不是取一個(gè)“相鄰”、“更好”的頂點(diǎn)單純形法計(jì)算步驟規(guī)范型第四節(jié)單純形法例:找出下列線性規(guī)劃問題的全部基本解，指出基本可行解和最優(yōu)解:第四節(jié)單純形法=目標(biāo)函數(shù)約束條件基矩陣右邊常數(shù)進(jìn)基變量、離基變量、基變換=基變量第四節(jié)單純形法=進(jìn)基變量離基變量目標(biāo)函數(shù)約束條件右邊常數(shù)=第四節(jié)單純形法=目標(biāo)函數(shù)約束條件新的基矩陣右邊常數(shù)=第四節(jié)單純形法=進(jìn)基變量離基變量目標(biāo)函數(shù)約束條件基矩陣=第四節(jié)單純形法右邊常數(shù)=目標(biāo)函數(shù)約束條件新的基矩陣右邊常數(shù)=第四節(jié)單純形法55第四節(jié)單純形法頂點(diǎn)4，最優(yōu)解初始頂點(diǎn)1頂點(diǎn)2頂點(diǎn)3目標(biāo)函數(shù)改善目標(biāo)函數(shù)改善目標(biāo)函數(shù)改善單純形法原理示意圖從一個(gè)頂點(diǎn)出發(fā)，沿著使目標(biāo)函數(shù)改善的方向，到達(dá)下一個(gè)相鄰的頂。如果相鄰的所有頂點(diǎn)都不能改善目標(biāo)函數(shù)，這個(gè)頂點(diǎn)就是最優(yōu)頂點(diǎn)。用這樣的搜索策略，可以大大減少搜索頂點(diǎn)的個(gè)數(shù)。按照這樣的搜索策略建立的算法，叫做單純形法。單純形法的思路找出一個(gè)初始可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)基本可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束第四節(jié)單純形法例：用單純形法求下列線性規(guī)劃的最優(yōu)解第四節(jié)單純形法解:化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為系數(shù)矩陣A及可行基B1r(B1)=2，B1是一個(gè)初始基,

x3、x4為基變量，x1、x2為非基變量，令x1=0、x2=0由約束方程知x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T

第四節(jié)單純形法以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。目標(biāo)函數(shù)Z=3x1+4x2中x1的系數(shù)大于零，如果x1為一正數(shù)，則Z的值就會(huì)增大，同樣若x2不為零為一正數(shù)，也能使Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒有達(dá)到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗(yàn)數(shù)，記作λj,j=1,2…,n。檢驗(yàn)數(shù)：目標(biāo)函數(shù)用非基變量表達(dá)時(shí)的變量系數(shù)。本例中λ1=3,λ2=4,λ3=0,λ4=0。參看下表。最優(yōu)解判斷標(biāo)準(zhǔn)：當(dāng)所有檢驗(yàn)數(shù)λj≤0（j=1，…，n）時(shí)，基本可行解為最優(yōu)解。當(dāng)目標(biāo)函數(shù)中有基變量xi時(shí)，利用約束條件將目標(biāo)函數(shù)中的xi消去即可求出檢驗(yàn)數(shù)。第四節(jié)單純形法進(jìn)基列出基行bi/ai2，ai2>0θi(1)XBx1x2x3x4bx3211040x4130130λj3400

(2)x3x2λj

(3)x1

x2

λj

基變量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/52/5400-1-1將3化為1乘以1/3后得到3018第四節(jié)單純形法最優(yōu)解X=(18，4，0，0)T，最優(yōu)值Z=70O20301040(3,4)X(3)=(18,4)最優(yōu)解X=(18,4)最優(yōu)值Z=70X(1)=(0,0)2010x2x130X(2)=(0,10)第四節(jié)單純形法例：用單純形法求解【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，單純法計(jì)算結(jié)果如表所示。第四節(jié)單純形法Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

1/3150120301713751/30－90－2M2025601017/31/31250128/9－1/92/335/300－98/9－1/9－7/3最優(yōu)解X=(25，35/3，0，0，0)T，最優(yōu)值Z=145/3第四節(jié)單純形法例：用單純形法求解

解:這是極小化線性規(guī)劃問題,可以將其化為極大化問題求解,也可以直接求解,這時(shí)判斷標(biāo)準(zhǔn)是：λj≥0(j=1，…，n)時(shí)得到最優(yōu)解。容易觀察到,系數(shù)矩陣中有一個(gè)3階單位矩陣,x3、x4、x5為基變量。目標(biāo)函數(shù)中含有基變量x4,由第二個(gè)約束得到x4=6+x1－x2，并代入目標(biāo)函數(shù)消去x4得第四節(jié)單純形法XBx1x2x3x4x5bθx3x4x51-16[1]121000100015→6215621/2λj1-1↑000

x2x4x51-241001-1-20100015111

λj20100

表中λj≥0,j=1,2,…,5所以最優(yōu)解為X=(0,5,0,1,11,)最優(yōu)值Z=2x1－2x2－x4=－2×5－1=－11極小值問題,注意判斷標(biāo)準(zhǔn),選進(jìn)基變量時(shí),應(yīng)選λj<0的變量xj進(jìn)基。第四節(jié)單純形法例：求解線性規(guī)劃解:化為標(biāo)準(zhǔn)型第四節(jié)單純形法初始單純形表為XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2進(jìn)基，而a12<0，a22<0，沒有比值，從而線性規(guī)劃的最優(yōu)解無界。由模型可以看出，當(dāng)固定x1使x2→+∞且滿足約束條件，還可以用圖解法看出具有無界解。第四節(jié)單純形法例：求解線性規(guī)劃解:化為標(biāo)準(zhǔn)型后用單純形法計(jì)算如下表所示第四節(jié)單純形法XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000第四節(jié)單純形法XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200第四節(jié)單純形法XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200(3)x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑－20第四節(jié)單純形法XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200(3)x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑－20(4)x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000－20第四節(jié)單純形法

表(3)中λj全部非正,則最優(yōu)解為:表(3)表明,非基變量x3的檢驗(yàn)數(shù)λ3=0,x3若增加,目標(biāo)函數(shù)值不變,即當(dāng)x3進(jìn)基時(shí)Z仍等于20。使x3進(jìn)基

x5出基繼續(xù)迭代,得到表(4)的另一基本最優(yōu)解X(1),X(2)是線性規(guī)劃的兩個(gè)最優(yōu)解，它的凸組合

仍是最優(yōu)解，從而原線性規(guī)劃有多重最優(yōu)解。第四節(jié)單純形法唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解

。多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。無界解的判斷:

某個(gè)λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。第四節(jié)單純形法在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。第四節(jié)單純形法例：用大工變量法解下列線性規(guī)劃第四節(jié)單純形法解:首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式式中x4，x5為松弛變量，x5可作為一個(gè)基變量，第一、三約束中分別加入人工變量x6、x7，目標(biāo)函數(shù)中加入―Mx6―Mx7一項(xiàng)，得到人工變量單純形法數(shù)學(xué)模型用前面介紹的單純形法求解，見下表。第四節(jié)單純形法Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000第四節(jié)單純形法Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M00第四節(jié)單純形法Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑0000第四節(jié)單純形法Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319/3λj000－5-25/3第四節(jié)單純形法最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/3例：用單純形法（大M法）求解

Max

z=3x1－2x2－x3x1－2x2+x3≤11

－4x1+x2+2x3≥3

－2x1x3=1x1、x2、x3≥0解：化為標(biāo)準(zhǔn)形式，并引入人工變量，構(gòu)造如下模型：

Maxz=3x1－2x2－x3－Mx6－Mx7x1－2x2+x3+x4=11

－4x1+x2+2x3

－x5+x6=3

－2x1

+x3

+x7=1

x1，x2，x3

，x4，x5，

x6，

x7≥0第四節(jié)單純形法Cj3-1-100-M-MbCBXBx1↓x2↓x3x4x5x6x70x41-21100011-Mx6-4120-1103-Mx7-20[1]00011

z3-6M-1+M-1+3M0-M00

0x43-20100-110-Mx60[1]00-11-21-1x3-20100011

Z1-1+M00-M0-3M+1

0x4[3]001-22-512-1x20100-11-21-1x3-20100011

z1000-1-M+1-M-1

3x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39

Z000-1/3-1/3-M+1/3-M+2/32第四節(jié)單純形法例：求解線性規(guī)劃解:加入松馳變量x3、x4化為標(biāo)準(zhǔn)型在第二個(gè)方程中加入人工變量x5，目標(biāo)函數(shù)中加上Mx5一項(xiàng)，得到第四節(jié)單純形法用單純形法計(jì)算如下表所示。第四節(jié)單純形法Cj5-800MbCBXBx1x2x3x4x50x3311006Mx51-20-114λj5-M2M-80M0第四節(jié)單純形法Cj5-800MbCBXBx1x2x3x4x50x3[3]11006→Mx51-20-114λj5-M↑2M-80M0第四節(jié)單純形法Cj5-800MbCBXBx1x2x3x4x50x3[3]11006→Mx51-20-114λj5-M↑2M-80M05x111/31/3002Mx50-7/3-1/3-112λj0－29/3+7/3M－5/3+1/3MM0表中λj≥0，j=1，2，…，5，從而得到最優(yōu)解X=（2，0，0，0，2），Z=10+2M。但最優(yōu)解中含有人工變量x5≠0說明這個(gè)解是偽最優(yōu)解，是不可行的，因此原問題無可行解。兩階段單純形法與大M單純形法的目的類似，將人工變量從基變量中換出，以求出原問題的初始基本可行解。將問題分成兩個(gè)階段求解，第一階段的目標(biāo)函數(shù)是約束條件是加入人工變量后的約束方程，當(dāng)?shù)谝浑A段的最優(yōu)解中沒有人工變量作基變量時(shí)，得到原線性規(guī)劃的一個(gè)基本可行解，第二階段就以此為基礎(chǔ)對(duì)原目標(biāo)函數(shù)求最優(yōu)解。當(dāng)?shù)谝浑A段的最優(yōu)解w≠0時(shí)，說明還有不為零的人工變量是基變量，則原問題無可行解。第四節(jié)單純形法例：用兩階段單純形法求解?！窘狻繕?biāo)準(zhǔn)型為在第一、三約束方程中加入人工變量x6、x7后，第一階段問題為用單純形法求解，得到第一階段問題的計(jì)算表如下：第四節(jié)單純形法Cj0000011bCBXBx1x2x3x4x5x6x7101x6x5x7－4123－1－212[