運(yùn)籌學(xué)概論課件

科學(xué)性

（1）它是在科學(xué)方法論的指導(dǎo)下通過(guò)一系列規(guī)范化步驟進(jìn)行的；（2）它是廣泛利用多種學(xué)科的科學(xué)技術(shù)知識(shí)進(jìn)行的研究。運(yùn)籌學(xué)研究不僅僅涉及數(shù)學(xué)，還要涉及經(jīng)濟(jì)科學(xué)、系統(tǒng)科學(xué)、工程物理科學(xué)等其他學(xué)科。運(yùn)籌學(xué)研究的特點(diǎn)實(shí)踐性

運(yùn)籌學(xué)以實(shí)際問(wèn)題為分析對(duì)象，通過(guò)鑒別問(wèn)題的性質(zhì)、系統(tǒng)的目標(biāo)以及系統(tǒng)內(nèi)主要變量之間的關(guān)系，利用數(shù)學(xué)方法達(dá)到對(duì)系統(tǒng)進(jìn)行最優(yōu)化的目的。更為重要的是分析獲得的結(jié)果要能被實(shí)踐檢驗(yàn)，并被用來(lái)指導(dǎo)實(shí)際系統(tǒng)的運(yùn)行。系統(tǒng)性

運(yùn)籌學(xué)用系統(tǒng)的觀點(diǎn)來(lái)分析一個(gè)組織（或系統(tǒng)），它著眼于整個(gè)系統(tǒng)而不是一個(gè)局部，通過(guò)協(xié)調(diào)各組成部分之間的關(guān)系和利害沖突，使整個(gè)系統(tǒng)達(dá)到最優(yōu)狀態(tài)。

綜合性

運(yùn)籌學(xué)研究是一種綜合性的研究，它涉及問(wèn)題的方方面面，應(yīng)用多學(xué)科的知識(shí)，因此，要由各方面的專家組成的小組來(lái)完成。運(yùn)籌學(xué)模型

運(yùn)籌學(xué)研究的模型主要是抽象模型——數(shù)學(xué)模型。數(shù)學(xué)模型的基本特點(diǎn)是用一些數(shù)學(xué)關(guān)系（數(shù)學(xué)方程、邏輯關(guān)系等）來(lái)描述被研究對(duì)象的實(shí)際關(guān)系（技術(shù)關(guān)系、物理定律、外部環(huán)境等）。

運(yùn)籌學(xué)模型的一個(gè)顯著特點(diǎn)是它們大部分為最優(yōu)化模型。一般來(lái)說(shuō)，運(yùn)籌學(xué)模型都有一個(gè)目標(biāo)函數(shù)和一系列的約束條件，模型的目標(biāo)是在滿足約束條件的前提下使目標(biāo)函數(shù)最大化或最小化。運(yùn)籌學(xué)分析的主要步驟

運(yùn)籌學(xué)分析的主要步驟包括：發(fā)現(xiàn)和定義待研究的問(wèn)題；構(gòu)造數(shù)學(xué)模型；尋找經(jīng)過(guò)模型優(yōu)化的結(jié)果，并通過(guò)應(yīng)用這些結(jié)果來(lái)改善系統(tǒng)的運(yùn)行效率。

真實(shí)系統(tǒng)系統(tǒng)分析問(wèn)題描述模型建立與修改模型求解與檢驗(yàn)結(jié)果分析與實(shí)施數(shù)據(jù)準(zhǔn)備

運(yùn)籌學(xué)分析的步驟1.3.1極小化LP問(wèn)題的解法方法一：將最小化問(wèn)題化為最大化問(wèn)題，再對(duì)該最大化問(wèn)題進(jìn)行求解。方法二：最小化問(wèn)題直接求解：檢驗(yàn)數(shù)的判別由所有σj(cj-zj)≤0即為最優(yōu)，變?yōu)樗笑襧≥0則為最優(yōu)。(選擇最小的負(fù)的σj所對(duì)應(yīng)的變量為進(jìn)基變量。其余同最大化求解方法。)

應(yīng)用舉例例1配料問(wèn)題某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格要求，產(chǎn)品單價(jià)，每天能供應(yīng)的原材料數(shù)量及原材料單價(jià)見下表。該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？產(chǎn)品名稱規(guī)格要求單價(jià)（元/kg)

A原材料C不少于50﹪，原材料P不超過(guò)25﹪

50

B原材料C不少于25﹪，原材料P不超過(guò)50﹪

35

D不限

25解：數(shù)學(xué)模型為：產(chǎn)品名稱規(guī)格要求單價(jià)（元/kg)

A原材料C不少于50﹪，原材料P不超過(guò)25﹪

50

B原材料C不少于25﹪，原材料P不超過(guò)50﹪

35

D不限

25原材料產(chǎn)品

C

P

H

A

x11

x12

x13

B

x21

x22

x23

D

x31

x32

x33解：設(shè)xiA,xiB,xiC,xiD,分別表示第i年年初給項(xiàng)目A、B、C、D的投資額。列表如下：

年份項(xiàng)目

12345

ABCD

x1Ax2Ax3Ax4A

x3B

x2Cx1Dx2Dx3Dx4Dx5D數(shù)學(xué)模型為：人力資源分配的問(wèn)題

解：設(shè)

xi

表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：MinZ=x1+x2+x3+x4+x5+x6

s.t.x1+x6

≥60

x1+x2

≥70

x2+x3

≥60

x3+x4

≥50

x4+x5

≥20

x5+x6

≥30

x1,x2,x3,x4,x5,x6

≥0

班次：1，2，3，4，5，6

x6+x1,x1+x2,x2+x3,x3+x4,x4+x5,x5+x6班次：1，2，3，4，5，6

x6+x1,x1+x2,x2+x3,x3+x4,x4+x5,x5+x6人力資源分配的問(wèn)題

解：設(shè)

xi

表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：

MinZ=x1+x2+x3+x4+x5+x6s.t.x6+x1

=60

x1+x2

=70

x2+x3

=60x1-x3

=10

x3+x4=50x1+x4

=60

x4+x5=20x1-x5

=40

x5+x6=30x1+x6=70

x1,x2,x3,x4,x5,x6

≥0

第2章對(duì)偶理論和靈敏度分析第1節(jié)單純形法的矩陣描述單純形法的矩陣描述考慮線性規(guī)劃問(wèn)題：

則A=(B,N)，X＝(XB,XN)T，C＝(CB,CN)目標(biāo)函數(shù)約束條件單純形法的矩陣描述線性規(guī)劃問(wèn)題B是A的一個(gè)基則線性規(guī)劃問(wèn)題可寫成以下形式：由上述模型可看出，當(dāng)XB=B-1b,XN=0,滿足AX=b條件當(dāng)XB=B-1b≥0XN=0時(shí)，B是可行基，X是基本可行解再當(dāng)CN－CBB-1N

0時(shí)，B是最優(yōu)基，X是最優(yōu)解單純形法的矩陣描述則線性規(guī)劃也可表示成：定理(最優(yōu)解判別準(zhǔn)則）對(duì)于可行基B,若

C-CBB-1A≤0

則對(duì)應(yīng)于基B的基礎(chǔ)可行解x就是基礎(chǔ)最優(yōu)解，此時(shí)的可行基就是最優(yōu)基。

σ=C-CBB-1A為檢驗(yàn)數(shù)。基變量的檢驗(yàn)數(shù)：CB-CBB-1B

=0C-CBB-1A=（0，CN-CBB-1N）檢驗(yàn)數(shù)σ=C-CBB-1A=（0，CN-CBB-1N）非基變量檢驗(yàn)數(shù)σ=CN-CBB-1N時(shí),達(dá)到最優(yōu)。單純形法的矩陣描述（2）項(xiàng)目非基變量XBXN基變量

XS0XSb

BN

I

Cj-zjCBCN

0項(xiàng)目基變量

XB非基變量

XNXSCBXBB-1b

I=B-1BB-1NB-1I

Cj-zj

0CN-CBB-1N-CBB-1初始單純形表例1生產(chǎn)計(jì)劃問(wèn)題（資源利用問(wèn)題）某家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元/個(gè)，椅子銷售價(jià)格30元/個(gè)，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工1小時(shí)。該廠每個(gè)月可用木工工時(shí)為120小時(shí)，油漆工工時(shí)為50小時(shí)。問(wèn)該廠如何組織生產(chǎn)才能使每月的銷售收入最大？桌子椅子總工時(shí)（小時(shí)）木工（小時(shí)）43120油漆工2150價(jià)格（元/個(gè)）5030解：將此問(wèn)題列成圖表如下：數(shù)學(xué)模型

maxZ=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20線性規(guī)劃數(shù)學(xué)模型三要素：

決策變量、約束條件、目標(biāo)函數(shù)例3營(yíng)養(yǎng)配餐問(wèn)題假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場(chǎng)上只有四種食品可供選擇，它們每千克所含的熱量和營(yíng)養(yǎng)成分和市場(chǎng)價(jià)格見下表。問(wèn)如何選擇才能在滿足營(yíng)養(yǎng)的前提下使購(gòu)買食品的費(fèi)用最?。扛鞣N食物的營(yíng)養(yǎng)成分表每天需要300055800X1X2x3x4解：設(shè)xj為第j種食品每天的購(gòu)入量，則配餐問(wèn)題的線性規(guī)劃模型為：

minZ=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，

x3，x40

例4合理下料問(wèn)題

現(xiàn)做100套鋼架，每套用長(zhǎng)為2.9m,2.1m和1.5m的原鋼各一根。已知原料長(zhǎng)為7.4m，問(wèn)應(yīng)如何下料，使用的原料最省。解：最簡(jiǎn)單的方法是在每根原料上截取2.9m,2.1m,1.5m的元鋼各一根組成一套，需100根，每根省下料頭0.9m，就浪費(fèi)了。若改為套裁，可以節(jié)約原料。幾種套裁方案如下表：下料方案

數(shù)（根）長(zhǎng)度

Ⅰ

Ⅱ

Ⅲ

Ⅳ

Ⅴ

2.92.11.5

120

103

201

013

022合計(jì)（m)

料頭(m)

7.10.3

7.407.30.1

6.60.87.20.2

設(shè)各種方案下料的根數(shù)為xi,i=1,2,3,4,5其數(shù)學(xué)模型為：minZ=0.3x1+0x2+0.1x3+0.8x4+0.2x5(orminS=x1+x2+x3+x4+x5)s.t.x1+2x2+2x3=1002x1+x4+2x5=1003x1+x3+3x4+2x5=100x1，x2，

x3，x4，

x50例5運(yùn)輸問(wèn)題

設(shè)有兩磚廠A1、A2分別供應(yīng)三個(gè)工地B1、B2、B3，運(yùn)價(jià)表如下，問(wèn)如何調(diào)運(yùn)使總運(yùn)費(fèi)最??？列出數(shù)學(xué)模型。

工地運(yùn)價(jià)（元/萬(wàn)塊）磚廠B1

B2

B3產(chǎn)量（萬(wàn)塊）

A1

50

60

70

23

A260

110160

27銷量(萬(wàn)塊）

17

1815

50解設(shè)Ai調(diào)運(yùn)給Bj的調(diào)運(yùn)量為xij,i=1,2;j=1,2,3其數(shù)學(xué)模型為：minZ=50x11+60x12+70x13+60x21+110x22+160x23

s.t.x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+x23=15xij≥0,i=1,2;j=1,2,3

工地運(yùn)價(jià)磚廠B1

B2

B3產(chǎn)量（萬(wàn)塊）

A1

50

60

70

23

A260

110160

27銷量

17

1815

504線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式：(其中bi≥0(i=1,2,...,m)例6將下列問(wèn)題化成標(biāo)準(zhǔn)型:MinZ=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20x3無(wú)非負(fù)限制例6將下列問(wèn)題化成標(biāo)準(zhǔn)型:MinZ=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20x3無(wú)非負(fù)限制（二維）線性規(guī)劃問(wèn)題圖解法：（1）滿足約束條件的變量的值，稱為可行解。（2）使目標(biāo)函數(shù)取得最優(yōu)值的可行解，稱為最優(yōu)解。例1的數(shù)學(xué)模型

maxZ=50x1+30x2s.t.4x1+3x21202x1+x2

50x1,x2

0二個(gè)重要結(jié)論：滿足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實(shí)可以推廣到更多變量的場(chǎng)合。最優(yōu)解必定能在凸多邊形的某一個(gè)頂點(diǎn)上取得，這一事實(shí)也可以推廣到更多變量的場(chǎng)合。解的討論：最優(yōu)解是唯一解；無(wú)窮多組最優(yōu)解：例1的目標(biāo)函數(shù)由

maxZ=50x1+30x2變成：

maxZ=40x1+30x2s.t.4x1+3x21202x1+x250x1,x20例1maxZ=50x1+30x2

s.t.4x1+3x2

1202x1+x2

50x1,x2

0解的討論：無(wú)界解：例：maxZ=x1+x2s.t.-2x1+x240x1-x220x1,x20x2504030201010203040x1該可行域無(wú)界，目標(biāo)函數(shù)值可增加到無(wú)窮大，稱這種情況為無(wú)界解或無(wú)最優(yōu)解。

-2x1+x240x1-x220解的討論：無(wú)可行解：例：maxZ=2x1+3x2s.t.x1+2x28x14x23-2x1+x24x1,x20該問(wèn)題可行域?yàn)榭占?，即無(wú)可行解，也不存在最優(yōu)解。解的情況：有可行解⊙有唯一最優(yōu)解⊙有無(wú)窮最優(yōu)解⊙無(wú)界解(無(wú)最優(yōu)解）無(wú)可行解線性規(guī)劃問(wèn)題解的概念線性規(guī)劃標(biāo)準(zhǔn)型的矩陣形式：Max

Z=CX（1-9）

s.t.

AX=b（1-10）

X0（1-11）解、可行解、最優(yōu)解⊙滿足約束條件（1-10）的X，稱為線性規(guī)劃問(wèn)題的解。⊙滿足約束條件（1-10）與（1-11）的X，稱為線性規(guī)劃的問(wèn)題可行解?！褲M足目標(biāo)函數(shù)（1-9）的可行解X，稱為線性規(guī)劃的問(wèn)題最優(yōu)解。秩：mn矩陣A的所有不為零的子式的最高階數(shù)稱為矩陣A的秩。記作R(A)。線性無(wú)關(guān)向量組：對(duì)于向量組a1,a2,…,an，如果存在一組不全為零的實(shí)數(shù)k1,k2,…,kn,使

k1a1+k2a2+…+knan=0,則稱向量組a1,a2,…,an線性相關(guān)，否則稱它們線性無(wú)關(guān)?；?、基向量、基變量⊙設(shè)r(A)=m,并且B是A的m階非奇異的子矩陣（det(B)<>0),則稱矩陣

B為線性規(guī)劃問(wèn)題的一個(gè)基?！丫仃嘊=（P1，P2….Pm)，其列向量

Pj稱為對(duì)應(yīng)基B的基向量?！雅c基向量Pj

相對(duì)應(yīng)的變量xj就稱為基變量，其余的就稱為非基變量。基解.基可行解.可行基⊙對(duì)于某一特定的基B，非基變量取

0值的解，稱為基解?！褲M足非負(fù)約束條件的基解，稱為基可行解。⊙與基可行解對(duì)應(yīng)的基，稱為可行基。不失一般性，設(shè)B是A的前m列,即B=(p1,p2,…,pm）,其相對(duì)應(yīng)的變量XB=(x1,x2,…,xm)T稱為基變量；其余變量XN=(xm+1,…,xn)T稱為非基變量。令所有非基變量等于零時(shí)得出的解,即X=（x1,x2,…xm,0,…,0)T稱為基解?；尚薪猓夯饪烧韶?fù)，負(fù)則不可行（違背非負(fù)性約束條件），滿足非負(fù)約束條件的基解為基可行解。對(duì)應(yīng)于基可行解的基稱為可行基。退化的基可行解：若某個(gè)基變量取值為零，則稱之為退化的基可行解。基解的數(shù)目：最多Cmn=n!/m!(n-m)!矩陣A=（P1，P2….,Pn),B=（P1，P2….Pm)

，基的個(gè)數(shù)≤，基可行解的個(gè)數(shù)≤。

a11a12….a1mb1B=a21a22….a2mb

=

b2………am1am2….ammbn

a11a12a1mb1a1m+1a1na21x1+a22x2+….+a2mxm=b2-

a2m+1xm+1-….-a2nxn

………am1am2ammbnamm+1amn或標(biāo)準(zhǔn)型為：

x1+2x2≤84x1≤16

4x2≤12

x1，x2≥0

maxz=2x1+3x2+0x3+0x4+0x5

x1+2x2+x3=84x1

x4=16

4x2+x5=12

x1,x2,x3,x4,x5≥0例

maxz=2x1+3x2基基為：基變量為：x3

，x4

，x5，非基變量為x1

，x2

。令非基變量x1=0，x2=0

，基變量x3=8，x4=16，x5=12X=(0,0,8,16,12)T為基解，且為基可行解解的集合：可行解基解基最優(yōu)解基可行解

練習(xí)題已知線性規(guī)劃問(wèn)題：求其所有基解，基可行解及最優(yōu)解。第一章線性規(guī)劃與單純形方法第二節(jié)：線性規(guī)劃解的性質(zhì)（幾何意義）概念：1、可行解：滿足所有約束條件的解。2、可行域：即可行解的集合。所有約束條件的交集，也就是各半平面的公共部分。滿足所有約束條件的解的集合，稱為可行域。幾種解之間的關(guān)系部分基解是非可行解。凸集（Convexset）概念：

設(shè)K是n維歐氏空間的一個(gè)點(diǎn)集，若K中的任意兩點(diǎn)x(1),x(2)的連線上的一切點(diǎn)x仍在K中，則稱K為凸集。即：若K中的任意兩點(diǎn)x(1),x(2)

∈K，存在0<<1使得x=x(1)+(1-)x(2)∈K,則稱K為凸集例1.6（凸集）例（非凸集）兩個(gè)基本概念：凸組合(Convexcombination)：

設(shè)x(1),x(2)…..x(k)是n維歐氏空間中的k個(gè)點(diǎn)，若存在數(shù)u1,u2,….uk且0≤ui≤1(i=1,2,…k),ui=1,使得x=u1x(1)+u2x(2)+…..+

uk

x(k)成立，則稱x為x(1),x(2)…..x(k)的凸組合。線性規(guī)劃的基本定理定理1

若線性規(guī)劃問(wèn)題存在可行域，則其可行域是凸集。（即連接線性規(guī)劃問(wèn)題任意兩個(gè)可行解的線段上的點(diǎn)仍然是可行解。)引理1

線性規(guī)劃問(wèn)題的可行解x=（x1,x2,…,xn)T為基可行解的充分必要條件是：x的正分量所對(duì)應(yīng)的系數(shù)矩陣A的列向量是線性無(wú)關(guān)的。線性規(guī)劃的基本定理定理2

線性規(guī)劃問(wèn)題的基可行解x對(duì)應(yīng)于可行域D中的頂點(diǎn)。頂點(diǎn)與基可行解相對(duì)應(yīng)推論1：可行解集D中的頂點(diǎn)個(gè)數(shù)是有限的。推論2：若可行解集D是有界的凸集，則D中任意一點(diǎn)x，都可表示成D的頂點(diǎn)的凸組合。證明反證法：若X*不為頂點(diǎn)且是LP的最優(yōu)解，由推論2，因此，令則由此得到即目標(biāo)函數(shù)在頂點(diǎn)處也達(dá)到最優(yōu)值。定理3

若可行域D有界，則線性規(guī)劃問(wèn)題的最優(yōu)解，必定在D的頂點(diǎn)上達(dá)到。說(shuō)明1：若可行解集D無(wú)界，則線性規(guī)劃問(wèn)題可能有最優(yōu)解，也可能無(wú)最優(yōu)解。若有最優(yōu)解，也必在頂點(diǎn)上達(dá)到。說(shuō)明2：有時(shí)目標(biāo)函數(shù)也可能在多個(gè)頂點(diǎn)上達(dá)到最優(yōu)值。這些頂點(diǎn)的凸組合也是最優(yōu)值。（有無(wú)窮多最優(yōu)解）事實(shí)上，若是目標(biāo)函數(shù)達(dá)到最大值的頂點(diǎn)，，，于是，小結(jié)基本定理定理1：若線性規(guī)劃問(wèn)題存在可行域，則其可行域D＝是凸集。

引理1：LP問(wèn)題的可行解X＝(x1,x2,…,xn)T

為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。定理2：LP問(wèn)題的基可行解X對(duì)應(yīng)于可行域的頂點(diǎn)。引理2：若K是有界凸集。則任何一點(diǎn)X屬于K可表示為K的頂點(diǎn)的凸組合。定理3若可行域有界，LP問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。另外，若可行域?yàn)闊o(wú)界，則可能無(wú)最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點(diǎn)上得到。有時(shí)目標(biāo)函數(shù)也可能在多個(gè)頂點(diǎn)上達(dá)到最優(yōu)值。這些頂點(diǎn)的凸組合也是最優(yōu)值。（有無(wú)窮多最優(yōu)解）第1章線性規(guī)劃與單純形法第1節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第2節(jié)線性規(guī)劃問(wèn)題的幾何意義第3節(jié)單純形法第4節(jié)單純形法的計(jì)算步驟第5節(jié)單純形法的進(jìn)一步討論第6節(jié)應(yīng)用舉例線性規(guī)劃問(wèn)題解的關(guān)系圖AX=b的解基解若非基變量為0基可行解基最優(yōu)解B是A的M階子矩陣基B若|B|0可行基B當(dāng)B-1b0最優(yōu)基B若基變量取非負(fù)若對(duì)應(yīng)目標(biāo)函數(shù)值最優(yōu)非可行解線性規(guī)劃問(wèn)題解的關(guān)系圖（2）可行解基可行解基解基可行基最優(yōu)基二.幾個(gè)基本定理定理1若線性規(guī)劃問(wèn)題存在可行解,則問(wèn)題的可行域是凸集.定理2線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域(凸集)的頂點(diǎn).定理3若可行域有界,線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域頂點(diǎn)上達(dá)到最優(yōu).引理2若K是有界凸集，則任何一點(diǎn)X∈K可表示為K的頂點(diǎn)的凸組合。引理1線性規(guī)劃的可行解X＝(x1,x2,…,xn)T為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。第2章對(duì)偶理論和靈敏度分析第1節(jié)單純形法的矩陣描述單純形法的矩陣描述考慮線性規(guī)劃問(wèn)題：

則A=(B,N)，X＝(XB,XN)T，C＝(CB,CN)目標(biāo)函數(shù)約束條件單純形法的矩陣描述線性規(guī)劃問(wèn)題B是A的一個(gè)基則線性規(guī)劃問(wèn)題可寫成以下形式：由上述模型可看出，當(dāng)XB=B-1b,XN=0,滿足AX=b條件當(dāng)XB=B-1b≥0XN=0時(shí)，B是可行基，X是基本可行解再當(dāng)CN－CBB-1N

0時(shí)，B是最優(yōu)基，X是最優(yōu)解單純形法的矩陣描述最優(yōu)基判別定理

設(shè)B是(LP)的一個(gè)基,若基B滿足:

(1)B-1b0(2)CN－CBB-1N

0

則B是(LP)的最優(yōu)基.可證明：CN－CBB-1N

0等價(jià)于C－CBB-1A

0檢驗(yàn)數(shù)單純形法的矩陣描述則線性規(guī)劃也可表示成：定理(最優(yōu)解判別準(zhǔn)則）對(duì)于可行基B,若

C-CBB-1A≤0

則對(duì)應(yīng)于基B的基礎(chǔ)可行解x就是基礎(chǔ)最優(yōu)解，此時(shí)的可行基就是最優(yōu)基。

σ=C-CBB-1A為檢驗(yàn)數(shù)?；兞康臋z驗(yàn)數(shù)：CB-CBB-1B

=0C-CBB-1A=（0，CN-CBB-1N）檢驗(yàn)數(shù)σ=C-CBB-1A=（0，CN-CBB-1N）非基變量檢驗(yàn)數(shù)σ=CN-CBB-1N時(shí),達(dá)到最優(yōu)。項(xiàng)目基變量

XB非基變量

XN

CBXBb

B

N

Cj-zj

CB

CN項(xiàng)目基變量

XB非基變量

XN

CBXBB-1b

B-1B

B-1N

Cj-zj

CB-CBB-1B

CN-CBB-1N

初始單純形表迭代單純形表單純形法的矩陣描述（2）項(xiàng)目非基變量XBXN基變量

XS0XSb

BN

I

Cj-zjCBCN

0項(xiàng)目基變量

XB非基變量

XNXSCBXBB-1b

I=B-1BB-1NB-1I

Cj-zj

0CN-CBB-1N-CBB-1初始單純形表例：某工廠在計(jì)劃內(nèi)要安排生產(chǎn)P1、P2兩種產(chǎn)品,

已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及原材料A、

B的消耗如下表所示.線性規(guī)劃的對(duì)偶理論問(wèn)工廠應(yīng)如何安排生產(chǎn)計(jì)劃使該工廠獲利最多?現(xiàn)從另一角度來(lái)討論這個(gè)問(wèn)題.引例（1）假如該工廠的決策者決定不生產(chǎn)產(chǎn)品P1和P2,而將其所有資源出租或外售.這時(shí)工廠的決策者要考慮給每種資源如何定價(jià)的問(wèn)題,或者,對(duì)要購(gòu)買這些資源的人來(lái)說(shuō),該如何提出購(gòu)買的價(jià)格可使工廠接受。下面建立該問(wèn)題的數(shù)學(xué)模型:設(shè)三種資源的單位出售的價(jià)格分別為對(duì)購(gòu)買者來(lái)講,購(gòu)入所有資源的支出越少越好因此目標(biāo)函數(shù)為對(duì)工廠來(lái)講,應(yīng)作如下比較：對(duì)工廠來(lái)講,應(yīng)作如下比較：引例（2）用一個(gè)單位設(shè)備臺(tái)時(shí)和4個(gè)單位原材料可以生產(chǎn)一件產(chǎn)品P1,可獲利2元,那么把生產(chǎn)一件產(chǎn)品P1的資源出售的收入應(yīng)不低于生產(chǎn)一件產(chǎn)品P1的利潤(rùn),否則不如自己生產(chǎn)獲利多.因此有對(duì)生產(chǎn)一件產(chǎn)品P2的資源出售的收入應(yīng)不低于生產(chǎn)一件產(chǎn)品P2的因此則數(shù)學(xué)模型二.對(duì)偶線性規(guī)劃的定義稱線性規(guī)劃(DLP)為線性規(guī)劃(LP)的對(duì)偶線性規(guī)劃2.1.2對(duì)偶規(guī)則原問(wèn)題一般模型：對(duì)偶問(wèn)題一般模型：maxZ=CXminω=YbAX

≤bYA≥CX≥0Y≥0當(dāng)CN－CBB-1N

0,－CBB-1

0時(shí)，表示線性規(guī)劃問(wèn)題已得到最優(yōu)。(2.1)(1)由（2.1）得Y0。Y=CBB-1——它稱為單純形算子(2)由CN－CBB-1N

0等價(jià)于C－CBB-1A0，可得

YA

C(3)由(2.1)得－Y=－

CBB-1

，兩邊右乘b,可得－Yb=－

CBB-1b,Yb=CBB-1b=z(4)minω=Yb(因?yàn)閅的上界為無(wú)限大,所以只存在最小值）

YA≥CY≥0原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)MaxZ目標(biāo)函數(shù)MinW決策變量數(shù)：n個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量約束條件數(shù)：n第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“=”約束條件數(shù)：m個(gè)第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“=”對(duì)偶變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量對(duì)偶規(guī)則P56例題2：寫出下列原問(wèn)題的對(duì)偶問(wèn)題由max

min對(duì)偶約束與原問(wèn)題變量一致,變量與原問(wèn)題約束相反；minZ=3x1+2x2-6x3+x52x1+x2-4x3+x4+3x5

≥7x1+2x3-x4≤

4-x1+3x2-x4+x5=-2x1，x2，x3

≥0;x4≤

0;x5無(wú)限制例題3maxω=7y1+4y2-2y32y1+y2-y3≤3y1+3y3≤2-4y1+2y2≤-6y1-y2-y3≥

03y1+y3=1y1≥0,y2≤0；y3無(wú)約束

由maxmin對(duì)偶約束與原問(wèn)題變量一致，變量與約束相反；由minmax對(duì)偶約束與原問(wèn)題變量相反，變量與約束一致；例題4：寫出以下模型的對(duì)偶問(wèn)題2.4對(duì)偶問(wèn)題的基本性質(zhì)對(duì)稱性：對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題證明：原問(wèn)題為:maxZ=CXAX≤bX≥0對(duì)偶問(wèn)題為:minω=YbYA≥CY≥0則上述對(duì)偶問(wèn)題為：min(ω*)=CXAX≤

b,X≥0即：maxZ=CXAX≤bX≥02弱對(duì)偶性：極大化原問(wèn)題的任一可行解的目標(biāo)函數(shù)值不大于其對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值。即：C≤b

證明：設(shè)原問(wèn)題為maxZ=CX,AX

≤b，X≥0.

為原問(wèn)題的可行解，有A

≤b，為對(duì)偶問(wèn)題的可行解，則A

≤b.對(duì)偶問(wèn)題為：minω=Yb，

YA≥C，Y≥0.

為對(duì)偶問(wèn)題的可行解，所以，

A≥C，有

A≥C

.于是

C≤A

≤b.

證明:若對(duì)偶問(wèn)題有可行解Y1，則CX1≤Y1b

，

與原問(wèn)題有無(wú)界解矛盾。逆不成立。

即：一個(gè)為無(wú)可行解，則另一個(gè)必為無(wú)界解或無(wú)可行解。3無(wú)界性:原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解,對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解.

4可行解是最優(yōu)解的性質(zhì)：設(shè)X*是原問(wèn)題的可行解，Y*是對(duì)偶問(wèn)題的可行解，當(dāng)CX*=Y*b時(shí)，X*,Y*是最優(yōu)解。證明：若CX*=Y*b，由性質(zhì)2，對(duì)偶問(wèn)題的所有可行解Y1，因CX*=Y*b，存在Y*b=CX*≤Y1b，故Y*是對(duì)偶問(wèn)題的最優(yōu)解；對(duì)原問(wèn)題的可行解X1，有CX1≤Y*b=CX*,故X*是原問(wèn)題的最優(yōu)解。5對(duì)偶定理：若一個(gè)問(wèn)題有最優(yōu)解，則另一問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。若原問(wèn)題最優(yōu)基為B，則其對(duì)偶問(wèn)題最優(yōu)解Y*=CBB-1證明：設(shè)X*是原問(wèn)題的最優(yōu)解，則其對(duì)應(yīng)的基為B，有C-CBB-1A≤0，設(shè)Y*=CBB-1

，則Y*A≥C.又對(duì)偶問(wèn)題目標(biāo)函數(shù)值w=Y*b=CBB-1

b；原問(wèn)題目標(biāo)函數(shù)值z(mì)=CX*=CBB-1

b=w.由性質(zhì)4，Y*是對(duì)偶問(wèn)題的最優(yōu)解。6互補(bǔ)松弛性：若X*，Y*是原問(wèn)題和對(duì)偶問(wèn)題的可行解，那么Y*Xs=YsX*=0,當(dāng)且僅當(dāng)X*，Y*是最優(yōu)解。證明：原問(wèn)題對(duì)偶問(wèn)題

maxZ=CXminω=YbAX+Xs=bYA-Ys=CX，Xs

≥0

Y，Ys≥0則：z=(YA-Ys

)X=YAX-YsXw=Y(AX+Xs)=YAX+YXs

必要性:若Y*Xs=YsX*=0，則z=YAX=w,由性質(zhì)4，X*，Y*是最優(yōu)解。充分性：若X*，Y*分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解，因CX*≤Y*AX*≤Y*b，CX*=Y*b，故Y*Xs=YsX*=0。證明:因?yàn)閅*=CBB-1,σs=0-CBB-1Is=-Y*.-σs=Y*.σ=C-CBB-1A=C-YA,YA+σ=C,YA-(-σ)=C,故-σ=Ys

7對(duì)偶松弛性2：若原問(wèn)題有最優(yōu)解，則最終表中松弛變量檢驗(yàn)數(shù)的相反數(shù)為對(duì)偶問(wèn)題的最優(yōu)解；其它變量檢驗(yàn)數(shù)的相反數(shù)為對(duì)偶剩余變量的值。XBXNXS0CN-CBB-1N-CBB-1YS1-YS2-Y對(duì)偶問(wèn)題的基本性質(zhì)1.對(duì)稱性：對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題。2.弱對(duì)偶性：若是最大化原問(wèn)題的可行解，是對(duì)偶問(wèn)題的可行解，則存。3.無(wú)界性：若原問(wèn)題為無(wú)界解，則對(duì)偶問(wèn)題無(wú)可行解。（注：該性質(zhì)的逆不存在。當(dāng)原問(wèn)題無(wú)可行解時(shí)，其對(duì)偶問(wèn)題可能為無(wú)界解，也可能無(wú)可行解。）4.最優(yōu)解定理：若兩互為對(duì)偶的問(wèn)題均有可行解，且可行解對(duì)應(yīng)的目標(biāo)函數(shù)值相等，則該可行解分別為他們的最優(yōu)解。5.對(duì)偶定理：若原問(wèn)題有最優(yōu)解，則對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。若原問(wèn)題最優(yōu)基為B，則其對(duì)偶問(wèn)題最優(yōu)解Y*=CBB-1。6.互補(bǔ)松弛性：在LP的最優(yōu)解中，若對(duì)應(yīng)某一約束條件的對(duì)偶變量值不為零，則該約束條件取嚴(yán)格等式；反之，若約束條件取嚴(yán)格等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。（另一解釋：在互為對(duì)偶的兩個(gè)問(wèn)題中，①若原問(wèn)題的某個(gè)變量取正數(shù)，則對(duì)偶問(wèn)題相應(yīng)的約束條件必取“＝”式；②若原問(wèn)題的某個(gè)約束條件取不等式，則對(duì)偶問(wèn)題相應(yīng)的變量為零。）7.設(shè)原問(wèn)題是maxz=CX,AX+Xs=b;X,Xs≥0,其對(duì)偶問(wèn)題是minω=Yb,YA-Ys=C,Y,Ys≥0,則原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問(wèn)題的一個(gè)基解CBB-1

（符號(hào)相反），其對(duì)應(yīng)關(guān)系如下：XBXNXS0CN-CBB-1N-CBB-1YS1-YS2-Y由弱對(duì)偶性,可得出以下結(jié)論1、原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界反之,

對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題的目標(biāo)函數(shù)值的上界.2、若原問(wèn)題為無(wú)界解,則其對(duì)偶問(wèn)題無(wú)可行解.反之,若對(duì)偶問(wèn)題為無(wú)界解,則其原問(wèn)題無(wú)可行解3、若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解,

則原問(wèn)題無(wú)最優(yōu)解.注:原問(wèn)題無(wú)可行解,則對(duì)偶問(wèn)題無(wú)可行解或具有無(wú)界若對(duì)偶問(wèn)題無(wú)可行解,則原問(wèn)題無(wú)可行解或具有無(wú)界解.反之,若對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解,則對(duì)偶問(wèn)題無(wú)最優(yōu)解.性質(zhì)3的應(yīng)用P59已知LP問(wèn)題：試用對(duì)偶理論證明上述LP問(wèn)題無(wú)最優(yōu)解。解：對(duì)偶問(wèn)題為：因?yàn)椋?，0，0）為線性規(guī)劃問(wèn)題的可行解。而對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題為無(wú)界解或無(wú)可行解，故原問(wèn)題無(wú)最優(yōu)解。性質(zhì)6的應(yīng)用P60已知線性規(guī)劃問(wèn)題：已知其對(duì)偶問(wèn)題的最優(yōu)解為：試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解。解：標(biāo)準(zhǔn)型為：對(duì)偶問(wèn)題為：標(biāo)準(zhǔn)型為：代入原問(wèn)題標(biāo)準(zhǔn)型有：例：某工廠在計(jì)劃內(nèi)要安排生產(chǎn)P1、P2兩種產(chǎn)品,

已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及原材料A、

B的消耗如下表所示.線性規(guī)劃的對(duì)偶理論問(wèn)工廠應(yīng)如何安排生產(chǎn)計(jì)劃使該工廠獲利最多?

203

X1X4

X2

283

1010-1/200-41201001/4---8/23/(1/4)

-Z

-13

00-201/4

203

X1X5

X2

442

1001/4000-21/21011/2-1/80

-Z

-14

00-3/2-1/80

CB

XB

Cj

b

23000

x1x2x3x4x5

j

000

X3X4

X5

81612

1210040010040018/2---12/4

-Z

0

23000

y1y2y3y4y5互為對(duì)偶問(wèn)題在單純形表間關(guān)系：1、原問(wèn)題的基解對(duì)應(yīng)于對(duì)偶問(wèn)題的檢驗(yàn)數(shù)。2、原問(wèn)題的松弛變量對(duì)應(yīng)對(duì)偶問(wèn)題的變量；3、原問(wèn)題的變量對(duì)應(yīng)對(duì)偶問(wèn)題的剩余變量；4、原問(wèn)題的基變量對(duì)應(yīng)對(duì)偶問(wèn)題的非基變量。例：某工廠在計(jì)劃內(nèi)要安排生產(chǎn)P1、P2兩種產(chǎn)品,

已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及原材料A、

B的消耗如下表所示.線性規(guī)劃的對(duì)偶理論問(wèn)工廠應(yīng)如何安排生產(chǎn)計(jì)劃使該工廠獲利最多?

203

X1X4

X2

283

1010-1/200-41201001/4---8/23/(1/4)

-Z

-13

00-201/4

203

X1X5

X2

442

1001/4000-21/21011/2-1/80

-Z

-14

00-3/2-1/80

CB

XB

Cj

b

23000

x1x2x3x4x5

j

000

X3X4

X5

81612

1210040010040018/2---12/4

-Z

0

23000

y1y2y3y4y5互為對(duì)偶問(wèn)題在單純形表間關(guān)系：1、原問(wèn)題的基解對(duì)應(yīng)于對(duì)偶問(wèn)題的檢驗(yàn)數(shù)。2、原問(wèn)題的松弛變量對(duì)應(yīng)對(duì)偶問(wèn)題的變量；3、原問(wèn)題的變量對(duì)應(yīng)對(duì)偶問(wèn)題的剩余變量；4、原問(wèn)題的基變量對(duì)應(yīng)對(duì)偶問(wèn)題的非基變量。2.5對(duì)偶最優(yōu)解的經(jīng)濟(jì)解釋—影子價(jià)格Z*=CBB-1b=Y*b=b1y1*+b2y2*

+…+bmym*

(*)Z=Z(b)b為資源求偏導(dǎo)：Z*b=CBB-1=Y*=(y1*

,y2*,

…ym*

)

對(duì)偶解yi*

的經(jīng)濟(jì)意義：其它條件不變的情況下，第i種資源改變一個(gè)單位所引起的目標(biāo)函數(shù)最優(yōu)解的變化。W=yb=(y1…ym)b1bm…=b1y1+b2y2+…+bmymbi：

第i種資源的數(shù)量yi：對(duì)偶解bi增加bi,其它資源數(shù)量不變時(shí),目標(biāo)函數(shù)的增量Z=biyiyi：反映bi的邊際效益(邊際成本)對(duì)偶最優(yōu)解的經(jīng)濟(jì)解釋—影子價(jià)格對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋--影子價(jià)格(2)在前面的例1中的最優(yōu)單純形表為如下

由該表可知,松馳變量X3=0,X4=0,X5=4這表明資源1(設(shè)備臺(tái)時(shí)),資源2(原材料A)已充分利用,而資源3(原材料B)還有4kg剩余因此,只要適當(dāng)增加設(shè)備臺(tái)時(shí)和原材料A,可使企業(yè)總利潤(rùn)有所增加.另外,從表中也可知,單純形乘子這說(shuō)明當(dāng)其它條件不變的情況下,若設(shè)備增加一臺(tái)時(shí),該廠按最優(yōu)計(jì)劃生產(chǎn)可多獲利潤(rùn)1.5元;原材料A增加1kg,可多獲利0.125元;原材料B增加1kg,對(duì)獲利無(wú)影響。對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋--影子價(jià)格(3)上式中bi是原問(wèn)題中第i種資源的擁有量,對(duì)偶變量y*代表對(duì)單位第i種資源的估價(jià).這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊價(jià)格.這種估價(jià)不是資源市場(chǎng)的價(jià)格,而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作出的估價(jià),故稱之為影子價(jià)格.

如例1在該廠現(xiàn)有資源和現(xiàn)有生產(chǎn)方案的條件下，設(shè)備的每小時(shí)租費(fèi)為1.5元，1kg原材料A的出讓費(fèi)為除成本外再附加0.125元，1kg原材料B可按原成本出讓，這時(shí)收入與生產(chǎn)獲利相等。影子價(jià)格的應(yīng)用情況①某資源對(duì)偶解>0，該資源有利可圖，可增加此種資源量；某資源對(duì)偶解為0，則不增加此種資源量。情況②直接用影子價(jià)格與市場(chǎng)價(jià)格相比較，進(jìn)行決策，決定是否買入該資源。影子價(jià)格所含有的信息：1、資源緊缺狀況；2、確定資源轉(zhuǎn)讓基價(jià)；3、取得緊缺資源的代價(jià)。當(dāng)資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，應(yīng)買進(jìn)資源用于擴(kuò)大生產(chǎn)；當(dāng)資源的市場(chǎng)價(jià)高于影子價(jià)格時(shí)，應(yīng)把已有資源賣掉。資源影子價(jià)格的性質(zhì)影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0(因?yàn)閅*XS=0)影子價(jià)格代表對(duì)這種資源的一個(gè)估價(jià)。當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，應(yīng)買進(jìn)這種資源；否則，應(yīng)賣出這種資源。對(duì)偶單純形法設(shè)有問(wèn)題maxZ=CX，

AX

＝b，

X≥0又設(shè)B是其一個(gè)基，當(dāng)非基變量都為0時(shí)，可以得到XB=B-1b。若在B-1b中至少有一個(gè)負(fù)分量，設(shè)第i個(gè)為負(fù)分量，并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正，這種情況就可以用對(duì)偶單純形法來(lái)進(jìn)行求解。2.6對(duì)偶單純形法的計(jì)算步驟P61（1）根據(jù)LP問(wèn)題，列出初始單純形表。檢查b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解，停止計(jì)算。若檢查b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，則進(jìn)行以下計(jì)算。（3）確定換入變量：檢查換出變量所在行（第L行）的各系數(shù)aLj。若所有的aLj≥0，則無(wú)可行解，停止計(jì)算。若存在aLj<0，則計(jì)算，將其最小值所對(duì)應(yīng)的變量作為換入變量。（2）確定換出變量：將B-1b中最小的負(fù)分量所對(duì)應(yīng)的變量確定為換出變量。（4）進(jìn)行迭代計(jì)算。重復(fù)1－4步，直至得到最優(yōu)解為止。對(duì)偶單純形法舉例利用對(duì)偶單純形法求解以下線性規(guī)劃問(wèn)題：cjCBXBbx1x2x3x4x5-1-3000-2-3-1-1-2-2100010解法001-3-4-1x3x4x5000-1-3000cj-zj1/33/2x3x1x50101/32/3-4/3100-2/3-1/3-1/3001cj-zj-1/34/31/30-7/30-1/301/20-10x4x1x5?3/21/2010-1/2?-3/2-3/2-1/2-1/21000010-10cj-zj0-5/2-1/200-3/2此時(shí)所有的B-1b均≥0，且所有的cj-zj均≤0，此時(shí)已得到最優(yōu)解為：X*=(3/2,0,0,1/2,1/2)TZ*=-3/2總結(jié)：對(duì)偶單純形法與單純形法的比較單純形法對(duì)偶單純形法保持B-1b≥0所有的cj-zj≤0最優(yōu)解時(shí)要求所有的cj-zj≤0B-1b≥0對(duì)偶單純形法的應(yīng)用時(shí)機(jī)要求最大化時(shí)，在單純形表中：如果檢驗(yàn)數(shù)均非正，而列中有負(fù)值，此時(shí)用對(duì)偶單純形法求解。若所有，中有正值，則用單純形法求解；若列中有負(fù)值，且中有正值，則必須引入人工變量，建立新的單純形表，重新計(jì)算。B-1bcj-zjB-1bcj-zjB-1b≥0對(duì)偶單純形法的優(yōu)點(diǎn)（1）初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)，就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因此可以直接計(jì)算。（2）當(dāng)變量多于約束條件，對(duì)這樣的LP問(wèn)題，用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量。因此，對(duì)變量較少，而約束條件很多的LP問(wèn)題，可以先將它變換成對(duì)偶問(wèn)題，然后用對(duì)偶單純形法求解。（3）在靈敏度分析中,有時(shí)需要用對(duì)偶單純形法這樣可使問(wèn)題的處理簡(jiǎn)化。例：用對(duì)偶單純形法求解變標(biāo)準(zhǔn)型為：對(duì)偶單純形法舉例cjCBXBbx1x2x3x4x5-2-3-400-1[-2]-21-1-310解法01-3-4x4x500-2-3-400cj-zj1x4x101-5/2-1/21/23/210-1/2-1/2cj-zj-120-4-10-120-2x2x10.42.20110-1/51.4-2/5-0.21/5-0.4-3-2cj-zj00-1.8-1.6-0.2-5.6此時(shí)所有的B-1b均≥0，且所有的cj-zj均≤0，此時(shí)已得到最優(yōu)解為：X*=(2.2,0.40,0,0)TZ*=5.64/38/5得原問(wèn)題最優(yōu)解為：得對(duì)偶問(wèn)題最優(yōu)解為：解：變標(biāo)準(zhǔn)型例：用對(duì)偶單純形法求解無(wú)最優(yōu)解。2.2靈敏度分析（考研時(shí)常考的知識(shí)點(diǎn)）靈敏度分析通常有兩類問(wèn)題：①是當(dāng)C,A,b中某一部分?jǐn)?shù)據(jù)發(fā)生給定的變化時(shí)，討論最優(yōu)解與最優(yōu)值怎么變化；②是研究C,A,b中數(shù)據(jù)在多大范圍內(nèi)波動(dòng)時(shí)，使原有最優(yōu)基仍為最優(yōu)基，同時(shí)討論此時(shí)最優(yōu)解如何變動(dòng)？靈敏度分析的兩把尺子：

σj=Cj-CBB-1pj≤0；

XB=B-1b≥02.2.1右端項(xiàng)bi變化的靈敏度分析bi變化到什么程度可以保持最優(yōu)基不變？用尺度xB=B-1b≥0。問(wèn)題：為什么不用尺度σj=Cj-CBB-1pj≤0？一.資源變化的靈敏度分析例1:

線性規(guī)劃問(wèn)題：

maxS=2x1+3x2s.t.x1+2x2<=84x1<=164x2<=12x1,x2>=0初始單純性表TAB(1)為：最終單純性表TAB(1)為：

例1中,若該廠又從別處抽出4臺(tái)時(shí)用于生產(chǎn)這兩種產(chǎn)品產(chǎn)品,求這時(shí)的最優(yōu)方案.

代入最終表得TAB(2)

最優(yōu)生產(chǎn)方案改為:x1=4,x2=3,z*=4×2+3×3=17(元).二.目標(biāo)函數(shù)中價(jià)值系數(shù)變化的靈敏度分析例：基變量x2的系數(shù)c2變化為△c2

，在最優(yōu)解不變條件下確定△c2變化范圍。從上表中知:三.技術(shù)系數(shù)變化的靈敏度分析例:分析在原計(jì)劃中是否應(yīng)該安排一種新產(chǎn)品Ⅲ,已知數(shù)據(jù)如上表,問(wèn)該廠是否應(yīng)該生產(chǎn),生產(chǎn)多少?解（1）設(shè)生產(chǎn)產(chǎn)品Ⅲ臺(tái)，其技術(shù)系數(shù)向量，的檢驗(yàn)數(shù)為說(shuō)明安排生產(chǎn)Ⅲ是有利的。（2）計(jì)算產(chǎn)品Ⅲ在最終表中對(duì)應(yīng)的列向量將（1）、（2）結(jié)果加入P31頁(yè)最終表中得：（3）換入，換出，得下表：例：原工藝發(fā)生變化時(shí)，例如：產(chǎn)品Ⅰ的工藝有了改進(jìn)，其技術(shù)系數(shù)，每件利潤(rùn)為4元，試分析對(duì)原最優(yōu)計(jì)劃有何影響。將以上結(jié)果添入最終表的列向量位置。變?yōu)檎?guī)表為：最優(yōu)解為：若遇到原問(wèn)題與對(duì)偶問(wèn)題都為非可行解時(shí)，則需要引入人工變量重新求解。

例：上例中產(chǎn)品Ⅰ的技術(shù)系數(shù)向量變?yōu)?/p>

，而每件獲利仍為4元，問(wèn)該廠應(yīng)如何安排最優(yōu)生產(chǎn)方案。解：將以上結(jié)果添入最終表的列向量位置。變?yōu)檎?guī)表為：原問(wèn)題與對(duì)偶問(wèn)題都為非可行解，引入人工變量，第三行用方程表示為：

換入，換出，得下表：=x1

換入，換出，得下表：

例：某廠生產(chǎn)A、B、C三種產(chǎn)品，其所需勞動(dòng)力、材料等有關(guān)數(shù)據(jù)見下表。

要求：

（1）

確定獲利最大的產(chǎn)品計(jì)劃；

（2）

寫出