《運(yùn)籌學(xué)》 課件全套 周晶 第1-11章-線性規(guī)劃-存儲(chǔ)論

7/16/2024第1章線性規(guī)劃1CONTENTS目錄7/16/20241.1

線性規(guī)劃建模1.2

線性規(guī)劃的解1.3

線性規(guī)劃的圖解法1.4線性規(guī)劃的基本定理1.5

單純形法1.6

單純形法的進(jìn)一步討論1.7應(yīng)用舉例21.1線性規(guī)劃建模例1.1

生產(chǎn)計(jì)劃問(wèn)題問(wèn)產(chǎn)品A,B各生產(chǎn)多少,可獲最大利潤(rùn)?生產(chǎn)經(jīng)營(yíng)中經(jīng)常提出的一個(gè)問(wèn)題是：如何合理地利用人、財(cái)、物，以降低成本，獲取效益，這就是規(guī)劃問(wèn)題。7/16/20241.1.1線性規(guī)劃引例

AB備用資源

鋼材（噸）1230勞動(dòng)力（工時(shí)）3260特種設(shè)備（臺(tái)時(shí)）0224

利潤(rùn)（元/件）40504

x1

+2x2

303x1+2x2

60

2x2

24

x1，x2

0maxz=40x1+50x2解:設(shè)產(chǎn)品A,B的產(chǎn)量分別為變量x1,

x2s.t.7/16/20241.1.1線性規(guī)劃引例5例1.2混合配料問(wèn)題請(qǐng)?jiān)O(shè)計(jì)一個(gè)既保證維生素?cái)z入量，又最經(jīng)濟(jì)的配食方案。

飼料ABC

每單位成本

飼料14102飼料26125飼料31716飼料42538每天維生素12148的最低需求維生素/mg7/16/20241.1.1線性規(guī)劃引例6解：設(shè)每天給每頭奶牛喂食飼料i的單位用量為xi

(i=1,2,3,4)minz=2x1

+5x2+6x3+8x4

4x1

+6x2+x3+2x4

12x1

+x2+7x3+5x4

14

2x2

+x3+3x4

8

xi

0(i=1,…,4)7/16/20241.1.1線性規(guī)劃引例s.t.7線性規(guī)劃問(wèn)題的特征要解決的問(wèn)題的目標(biāo)可以用數(shù)值指標(biāo)反映對(duì)于要實(shí)現(xiàn)的目標(biāo)有多種方案可選擇有影響決策的若干約束條件線性規(guī)劃模型的要素決策變量：向量

(x1,

…,xn)T

，即決策人要考慮和控制的因素（通常非負(fù)）約束條件：線性等式或不等式目標(biāo)函數(shù)：z=f(x1,

…,xn)

線性式，求

z

極大或極小7/16/20241.1.1線性規(guī)劃引例8max(min)z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn(=,)b1a21x1+a22x2+…+a2nxn

(=,)b2………am1x1+am2x2+…+amnxn

(=,)bmxj()0,j=1,2,…,n7/16/20241.1.2線性規(guī)劃模型的一般形式9a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn

=b2…………am1x1+am2x2+…+amxn

=bmxj0(j=1,2,…,n)maxz=c1x1+c2x2+…+cnxn其中

bi

0(i=1,2,…,m)7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式10maxz=cTxs.t.Ax=bx

0

a11a12………a1n其中A=

a21a22………

a2n

…

am1am2………amn

x1

x=x2

xn…

b1

b=b2

bm…

c1

c=c2

cn…標(biāo)準(zhǔn)形式的矩陣表示：7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式11(1)目標(biāo)函數(shù)(2)約束條件(3)決策變量非標(biāo)準(zhǔn)型

標(biāo)準(zhǔn)型7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式12(1)

目標(biāo)函數(shù)xoz-z令z’=

－

z非標(biāo)準(zhǔn)型

標(biāo)準(zhǔn)型7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式13(2)

約束條件例1.

maxz=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20非標(biāo)準(zhǔn)型

標(biāo)準(zhǔn)型7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式14(2)

約束條件

x1+2x2+x3=303x1+2x2+x4=602x2+

+x5=24

x1,

…,x50

x3,x4,x5

稱為松弛變量(slackvariables)例1.

maxz=40x1+50x2+0·x3+0·x4+0·x5非標(biāo)準(zhǔn)型

標(biāo)準(zhǔn)型7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式154x1+6x2+x3+2x4

12x1+x2+7x3+5x4

142x2+x3+3x4

8

x1,

…,x4

0

例2.

minz=2x1+5x2+6x3+8x4(2)

約束條件非標(biāo)準(zhǔn)型

標(biāo)準(zhǔn)型7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式16(2)

約束條件4x1+6x2+x3+2x4-x5=12x1+x2+7x3+5x4-x6=142x2+x3+3x4-x7=8

x1,

…,x7

0

x5,x6,x7

剩余變量(surplusvariables)例2.

minz=2x1+5x2+6x3+8x4非標(biāo)準(zhǔn)型

標(biāo)準(zhǔn)型7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式17(3)

決策變量3

x1'-3x1"+2x28x1'

-x1"–4x2

14x1',x1",x203x1+2x28x1–4x2

14x20令

x1=x1'-x1"非標(biāo)準(zhǔn)型

標(biāo)準(zhǔn)型7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式18(3)

決策變量x1'

+x211x1'

16x1',x20x1+x25-6

x110x20-6+6x1+6

10+6

令

x1'

=x1+6

0

x1'

16非標(biāo)準(zhǔn)型

標(biāo)準(zhǔn)型7/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式197/16/20241.1.3線性規(guī)劃模型的標(biāo)準(zhǔn)形式變換的方法目標(biāo)函數(shù)為

min型，價(jià)值系數(shù)一律反號(hào)，即令

f

(x)=-f(x)=-

cTx第

i個(gè)約束的

bi

為負(fù)值，則該行左右兩端系數(shù)同時(shí)反號(hào)，同時(shí)不等號(hào)也要反向第

i個(gè)約束為型，在不等式左邊增加一個(gè)非負(fù)的變量

xn+i，稱為松弛變量；同時(shí)令

cn+i

=0第

i個(gè)約束為型，在不等式左邊減去一個(gè)非負(fù)的變量

xn+i，稱為剩余變量；同時(shí)令

cn+i

=0若

xj0，令

xj=-

xj

，代入非標(biāo)準(zhǔn)型，則有

xj

0若

xj正負(fù)不限，令

xj=xj

-

xj

，xj

0，xj

0，代入非標(biāo)準(zhǔn)型201.2線性規(guī)劃的解maxz=cTxs.t.Ax=b(1)x

0(2)定義1：滿足約束(1)，(2)的x=(x1,…,xn)T稱為L(zhǎng)P問(wèn)題的可行解，全部可行解的集合稱為可行域。定義2：使目標(biāo)函數(shù)達(dá)到最大值的的可行解稱為L(zhǎng)P問(wèn)題的最優(yōu)解。(LP)7/16/20241.2線性規(guī)劃的解22BN(m<n)rank(A)=m[至少有一個(gè)m階子式不為0]Am×n

滿秩m×m滿秩子矩陣a11…a1ma1m+1…a1na21…

a2ma2m+1…

a2n………am1…

ammamm+1…

amnP1…

PmPm+1…

PnAm×n=maxz=cTxs.t.Ax=bx

0x

=(x1,…,xn)T7/16/20241.2線性規(guī)劃的解23定義3：基(基陣)

—

若A

中一個(gè)m×m子矩陣B

是可逆矩陣，則稱方陣B

為L(zhǎng)P問(wèn)題的一個(gè)基。A=(P1…

PmPm+1…

Pn)=(BN)

基向量

非基向量

BN…X=(x1…

xmxm+1…

xn)T=(XBXN)T

基變量

非基變量

XB

XN…7/16/20241.2線性規(guī)劃的解24AX=b的求解A=(BN)X=(XBXN)TXBXN(BN)=bBXB+NXN=bBXB=b-NXNXB=B-1b-B-1NXN7/16/20241.2線性規(guī)劃的解25定義4：基本解

—

對(duì)應(yīng)于基B，X=為AX=b的一個(gè)解。B-1b

0定義5：基本可行解

—基B，基本解X=

B-1b

0若B-1b0，稱基

B為可行基。若其基本解是最優(yōu)解，成為最優(yōu)基本解，相應(yīng)的基為最優(yōu)基。※

基本解中最多有m個(gè)非零分量;基本解的數(shù)目7/16/20241.2線性規(guī)劃的解26約束方程的解空間基本解可行解非可行解基本可行解7/16/20241.2線性規(guī)劃的解271.3線性規(guī)劃的圖解法非負(fù)約束Thenon-negativeconstraintsx2x1最簡(jiǎn)單、直觀的方法但只適用有兩個(gè)決策變量的情況7/16/20241.3.1圖解法的步驟29012345678可行域x2非可行域x1+2x2￡843214x1￡16x1最優(yōu)解點(diǎn)x1=4，x2

=2z=

2x1+3x2即x2=

-2x1/3+z/3z取不同值時(shí)是一束斜率為-2/3平行線，z最大值出現(xiàn)在最高的一條線上。

4x2￡

127/16/20241.3.1圖解法的步驟已知某線性規(guī)劃模型歸結(jié)為：目標(biāo)函數(shù)max

z=

2x1+3x2約束條件x1+2x2

8

4

x1

16

s.t.4x2

12x1,x2

0307/16/20241.3.1圖解法的步驟max

z=x1+3x2 s.t. x1+x2≤6

-x1+2x2≤8

x1≥0,x2≥0可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860x1x231例1.1

maxz=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x207/16/20241.3.2線性規(guī)劃解的幾種可能性32DABC解：(1)確定可行域

x10x1=0(縱)x20x2=0(橫)x1+2x230(0,15)(30,0)0102030x23x1+2x2

60(0,30)(20,0)

2x2

24(0,12)203010x17/16/20241.3.2線性規(guī)劃解的幾種可能性33(2)求最優(yōu)解解：x*=(15,7.5)zmax=975z=40x1+50x20=40x1+50x2(0,0),

(10,-8)C點(diǎn)：

x1+2x2=30

3x1+2x2=60DABC0102030x2203010x17/16/20241.3.2線性規(guī)劃解的幾種可能性34例：

maxz=40x1+80x2

x1+2x2303x1+2x2602x224

x1,x207/16/20241.3.2線性規(guī)劃解的幾種可能性無(wú)窮多個(gè)最優(yōu)解35最優(yōu)解：BC線段B點(diǎn)x(1)=(6,12)C點(diǎn)x(2)=(15,7.5)x*=

x(1)+(1-

)x(2)(01)求解DABC0102030x2203010x1Z=40x1+80x2=0

1.3.2線性規(guī)劃解的幾種可能性036無(wú)界無(wú)有限最優(yōu)解例：

maxz=2x1+4x22x1+x2

8-2x1+x22x1,x20Z=02x1+x2=8-2x1+x2=28246x240x17/16/20241.3.2線性規(guī)劃解的幾種可能性無(wú)界解37例：

maxz=2x1+x2

x1+x2

22x1+2x26x1,x20無(wú)解無(wú)可行解7/16/20241.3.2線性規(guī)劃解的幾種可能性無(wú)可行解x1+x2=22x1+2x2=64123x220x13387/16/20241.3.2線性規(guī)劃解的幾種可能性

線性規(guī)劃的可行域及最優(yōu)解的可能結(jié)果圖示：

(a)可行域封閉，唯一最優(yōu)解(b)可行域封閉，多個(gè)最優(yōu)解(d)可行域開(kāi)放，多個(gè)最優(yōu)解(e)可行域開(kāi)放，目標(biāo)函數(shù)無(wú)界(f)可行域?yàn)榭占?c)可行域開(kāi)放，唯一最優(yōu)解39唯一解無(wú)窮多個(gè)最優(yōu)解無(wú)有限最優(yōu)解無(wú)可行解有解無(wú)解總結(jié):7/16/20241.3.2線性規(guī)劃解的幾種可能性40可行域?yàn)橥苟噙呅稳粲凶顑?yōu)解，一定在可行域的頂點(diǎn)達(dá)到X(1)X(2)凸多邊形凹多邊形X(1)X(2)7/16/20241.3.3圖解法的啟示41凸集及其性質(zhì)定義1：凸集—

D是n維歐氏空間上的一個(gè)集合

X(1),

X(2)∈D,對(duì)任一個(gè)滿足

X=

X(1)+(1-

)X(2)(01)

有X∈D凸集中任意兩點(diǎn)的連線仍然屬于該集合。

7/16/20241.3.3圖解法的啟示42凸集及其性質(zhì)定義2：凸組合—

X(1),X(2),…,X(k)

是n維歐氏空間中

的

k個(gè)點(diǎn),若有一組數(shù)

μ1,μ2,…

,μk

滿足

0

μi1

(i=1,…,k)

μi=1

ki=1有點(diǎn)X=μ1X(1)

+…+μkX(k)則稱點(diǎn)X為X(1),X(2),…,X(k)

的凸組合。7/16/20241.3.3圖解法的啟示437/16/20241.3.3圖解法的啟示—凸集D,點(diǎn)XD，若找不到兩個(gè)不

同的點(diǎn)

X(1),X(2)D使得

X=

X(1)

+(1-

)

X(2)

(0<<1)

則稱

X為D的頂點(diǎn)。凸集及其性質(zhì)定義3：頂點(diǎn)凸多邊形也稱為極點(diǎn)extremepoint44幾何概念代數(shù)概念約束直線滿足一個(gè)等式約束的解約束半平面滿足一個(gè)不等式約束的解約束半平面的交集：凸多邊形滿足一組不等式約束的解約束直線的交點(diǎn)基本解可行域的極點(diǎn)基本可行解目標(biāo)函數(shù)等值線：一組平行線目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解1.3.3圖解法的啟示0451.4線性規(guī)劃的基本定理若(LP)問(wèn)題有可行解，則可行解集（可行域）是凸集（可能有界，也可能無(wú)界），有有限個(gè)頂點(diǎn)。(LP)問(wèn)題的基本可行解可行域的頂點(diǎn)。若(LP)問(wèn)題有最優(yōu)解，必定可以在基本可行解（頂點(diǎn)）達(dá)到。7/16/20241.4線性規(guī)劃的基本原理47若(LP)問(wèn)題有可行解，則可行解集（可行域）是凸集（可能有界，也可能無(wú)界），有有限個(gè)頂點(diǎn)。即證滿足約束條件的所有點(diǎn)組成的圖形是凸集。or7/16/20241.4線性規(guī)劃的基本原理48

(LP)問(wèn)題的基本可行解可行域的頂點(diǎn)。引理：線性規(guī)劃問(wèn)題的可行解

X

=(x1,

…,xn)

為基本可行解的充要條件是

X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。證明：由基本可行解定義顯然成立；若向量P1,P2,…,Pk

線性獨(dú)立，則必有k≤m；（1）“k=m”

恰好構(gòu)成一個(gè)基；（2）“k<m”一定可以從其余列向量中找出(m-k)個(gè)與P1,P2,…,Pk

構(gòu)成一個(gè)基，其對(duì)應(yīng)的解恰為X。7/16/20241.4線性規(guī)劃的基本原理49

(LP)問(wèn)題的基本可行解可行域的頂點(diǎn)。反證法（1）X

不是基本可行解X

不是可行域的頂點(diǎn)假設(shè)X的前m個(gè)分量為正：由引理，P1,P2,…,Pm

線性相關(guān)，即7/16/20241.4線性規(guī)劃的基本原理50反證法（2）X

不是可行域的頂點(diǎn)X

不是基本可行解可以找到可行域內(nèi)另外兩個(gè)不同點(diǎn)Y和Z：X=aY+(1-a)Z(0<a<1)

(LP)問(wèn)題的基本可行解可行域的頂點(diǎn)。7/16/20241.4線性規(guī)劃的基本原理51

若(LP)問(wèn)題有最優(yōu)解，必定可以在基本可行解（頂點(diǎn)）達(dá)到。證明：設(shè)是線性規(guī)劃的一個(gè)最優(yōu)解。若不是基本可行解，則不是頂點(diǎn)。可以找到另兩個(gè)點(diǎn)。代入目標(biāo)函數(shù)：如果仍然都不是基本可行解，按上面的方法繼續(xù)做下去，最后一定可以找到一個(gè)基本可行解，且目標(biāo)函數(shù)值等于。7/16/20241.4線性規(guī)劃的基本原理521.5單純形法單純形法的基本思路：從一個(gè)初始的基本可行解出發(fā)，經(jīng)過(guò)判斷，如果是最優(yōu)解，則結(jié)束；否則經(jīng)過(guò)基變換得到另一個(gè)改善的基本可行解，如此一直進(jìn)行下去，直到找到最優(yōu)解。(1)

確定初始基本可行解(2)從一個(gè)基本可行解轉(zhuǎn)換到相鄰的基本可行解(3)最優(yōu)性檢驗(yàn)和解的判別7/16/20241.5.1迭代原理54(1)

確定初始基本可行解一般約束條件的變量系數(shù)矩陣中總會(huì)存在一個(gè)單位矩陣：7/16/20241.5.1迭代原理55(2)從一個(gè)基本可行解轉(zhuǎn)換到相鄰的基本可行解僅變換一個(gè)基變量P1P2…PmPm+1…Pj…Pnb7/16/20241.5.1迭代原理56P1P2…Pl-1PjPl+1…PmbPlPj進(jìn)行初等變換形成單位矩陣(2)從一個(gè)基本可行解轉(zhuǎn)換到相鄰的基本可行解7/16/20241.5.1迭代原理57(3)最優(yōu)性檢驗(yàn)和解的判別將基本可行解和分別代入目標(biāo)函數(shù)得：>0≤

0

>07/16/20241.5.1迭代原理58單純形法的基本思路：從一個(gè)初始的基本可行解出發(fā)，經(jīng)過(guò)判斷，如果是最優(yōu)解，則結(jié)束，否則經(jīng)過(guò)基變換得到另一個(gè)改善的基本可行解，如此一直進(jìn)行下去，直到找到最優(yōu)解。第1步：求初始基可行解，列出初始單純形表。第2步：最優(yōu)性檢驗(yàn)。第3步：從一個(gè)基可行解轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)值更大的基可行解，列出新的單純形表。第4步：重復(fù)第2、3步，一直到計(jì)算結(jié)束為止。7/16/20241.5.2迭代步驟59非標(biāo)準(zhǔn)形的LP問(wèn)題標(biāo)準(zhǔn)的LP問(wèn)題設(shè)法使約束方程的系數(shù)矩陣中包含一個(gè)單位陣以此作為基求出問(wèn)題的一個(gè)初始基可行解為了書寫規(guī)范和便于計(jì)算，對(duì)單純形的計(jì)算有一種專門的表格，稱為單純形表。

含初始基可行解的單純形表

——初始單純形表

含最優(yōu)解的單純形表

——最終單純形表第1步-求初始基可行解，列出初始單純形表7/16/20241.5.2迭代步驟60

cj

c1…cm…cj…cnCB

基b

x1…

xm

…

xj

…

xn

c1

x1b1

c2

x2

b2

：：：：：：

cm

xm

bm10…a1j…a1n00…a2j…a2n

：：：：

：：

：：01…amj

…amn

cj

-zj0…0……基變量基變量的取值檢驗(yàn)數(shù)σj第1步-求初始基可行解，列出初始單純形表7/16/20241.5.2迭代步驟61

cj

c1…cm…cj…cnCB

基b

x1…

xm

…

xj

…

xn

c1

x1b1

c2

x2

b2

：：：：：：

cm

xm

bm10…a1j…a1n00…a2j…a2n

：：：：

：：

：：01…amj

…amncj-zj0…0……所有檢驗(yàn)數(shù)≤0，且基變量中不含人工變量時(shí)，即為最優(yōu)解。當(dāng)表中存在

cj–zj＞0時(shí)，如有

Pj≤0，則問(wèn)題為無(wú)界解。如果都不是，下一步……第2步–最優(yōu)性檢驗(yàn)1.5.2迭代步驟062確定換入變量和換出變量第3步–換基，使目標(biāo)函數(shù)值更大換入變量=進(jìn)基變量=EnteringVariable根據(jù)，確定xk為換入變量換出變量=出基變量=LeavingVariable按

規(guī)則計(jì)算，可確定xl為換出變量7/16/20241.5.2迭代步驟637/16/20241.5.2迭代步驟以

alk

為主元素(pivotnumber)進(jìn)行迭代，得到新的單純形表。第3步–換基，使目標(biāo)函數(shù)值更大旋轉(zhuǎn)運(yùn)算Pivoting64

cj

c1…cl…cm…

cj…ck…CB

基b

x1…

xl

…

xm

…

xj

…

xk…

c1

x1b1：：：

ck

xk：：：

cm

xm

bm1…0…

…0…：：：：：0…0

…

…1…

：：

：：：0…1

…

…0…cj-zj0……0……0…1.5.2迭代步驟第3步–換基，使目標(biāo)函數(shù)值更大旋轉(zhuǎn)運(yùn)算Pivoting065例1.4

用單純形法求解線性規(guī)劃問(wèn)題maxz=40x1+50x2

x1+2x2

30

3x1+2x2

60

2x2

24x1,x20s.t.第4步–重復(fù)2、3步，直到計(jì)算結(jié)束7/16/20241.5.2迭代步驟66解：首先將上述問(wèn)題化為標(biāo)準(zhǔn)型：1.5.2迭代步驟7/16/202467單純法求解cBxBbx1x2x3x4x54050000x3x4x500030602413022210001000104050000-z

153012初始單純形表重新計(jì)算檢驗(yàn)數(shù)，結(jié)果如下頁(yè)檢驗(yàn)數(shù)判別換基迭代非基變量檢驗(yàn)數(shù)為計(jì)算

06850122x2501121/2036-106-11.5.2迭代步驟cBxBbx1x2x3x4x54050000x3x4001201010-1-11/2400-25-z

06

12--第2單純形表00336101x25060-840計(jì)算

非基變量檢驗(yàn)數(shù)為檢驗(yàn)數(shù)判別06904061x14011018-32000-4015第3單純形表-400701.5.2迭代步驟cBxBbx1x2x3x4x54050000x3x4012110-11/20-z

第3單純形表00x25060-840檢驗(yàn)數(shù)判別0700x1401018-32000-4015-400700x59-3/211/2015-1/211/2015/23/4-1/4-35/2-15/20-975檢驗(yàn)數(shù)全非正,已經(jīng)取得最優(yōu)解,最優(yōu)解為:X*=(15,15/2,0,0,9)TZ*=975最終單純形表FinalSimplextableau1.5.2迭代步驟1.6單純形法的進(jìn)一步討論前面的例子中，化為標(biāo)準(zhǔn)形式后約束條件的系數(shù)矩陣都含有單位矩陣，可以作為初始可行基。如果化為標(biāo)準(zhǔn)形式的約束條件的系數(shù)矩陣中不存在單位矩陣呢？如何建立初始單純形表？例1.5:maxz=x1+2x2+x3

x1+4x2-2x3

120x1+x2+x3=60x1

,x2,x30s.t.7/16/20241.6單純形法的進(jìn)一步討論72maxz=x1+2x2+x3x1+4x2-2x3-x4

=

120x1+x2+x3

=60x1

,x2,x3,x4

0s.t.可以添加兩列單位向量P5

，P6，構(gòu)成單位矩陣。maxz=x1+2x2+x3-Mx5

-Mx6x1+4x2-2x3-x4+x5

=

120x1+x2+x3

+x6

=

60x1,x2,x3,x4,

x5,x6

0s.t.人工變量-M罰因子7/16/20241.6.1人工變量法–大M法73

12

10-M

-M

CBXB

b

x1x2x3x4x5x6

2

x2

601

1

10010

x4

120306

1-14-10-100-2-M最終單純形表:7/16/20241.6.1人工變量法–大M法747/16/20241.6.1人工變量法–兩階段法大M是一個(gè)很大的數(shù),但計(jì)算機(jī)處理時(shí)取多大呢?兩階段法不用確定M具體值，可用于計(jì)算機(jī)求解。第一階段：先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的

線性規(guī)劃問(wèn)題，判斷其有否可行解：-當(dāng)人工變量取值為0時(shí)，這時(shí)的最優(yōu)解就是原線性規(guī)劃問(wèn)題的

一個(gè)基可行解；-如果最優(yōu)解的基變量中含有非零的人工變量，則原線性規(guī)劃問(wèn)題

無(wú)可行解。第二階段：有可行解時(shí)去掉人工變量再求解。757/16/20241.6.1人工變量法–兩階段法maxz=x1+2x2+x3x1+4x2-2x3-x4

=

120x1+x2+x3

=60x1

,x2,x3,x4

0s.t.x1+4x2-2x3-x4+x5

=

120x1+x2+x3

+x6

=

60x1,x2,x3,x4,

x5,x6

0s.t.maxz=x1+2x2+x3-Mx5

-Mx676第一階段的線性規(guī)劃問(wèn)題：minz=x5

+x6x1+4x2-2x3-x4+x5

=

120x1+x2+x3+x6

=

60x1,x2,x3,x4,

x5,x60s.t.第二階段去除人工變量，目標(biāo)函數(shù)回歸到：maxz=x1+2x2+x3(maxz=-x5

-x6

)maxz=x1+2x2+x3-Mx5-Mx6從第一個(gè)階段的最后一張單純形表出發(fā)，繼續(xù)用單純形法計(jì)算。1.6.1人工變量法–兩階段法077例1.6:maxz=2x1+x2x1+x2

22x1+2x2

6x1,x20s.t.maxz=2x1+x2+0x3+0x4-Mx5x1+x2+x3

=

22x1+2x2-x4

+x5

=

6x1,x2,x3,x4,

x50s.t.判定無(wú)解條件:

當(dāng)進(jìn)行到最優(yōu)表時(shí)，仍有人工變量在基中，且≠0，則說(shuō)明原問(wèn)題無(wú)可行解。7/16/20241.6.2無(wú)可行解78

2100-MCBXB

b

x1x2x3x4x50

x3211100-M

x56220-11cj-zj2+2M1+2M0-M02x1211100-Mx5200-2-11cj-zj0-1-2-2M-M07/16/20241.6.2無(wú)可行解79例1.7：maxz=4x1+x2-x1+x2

2x1–4x2

4x1–2x2

8x1,x20-x1+x2+x3

=2x1–4x2+x4

=

4x1–

2x2+x5

=

8x1,…,x50—當(dāng)表中存在

cj–zj

＞0時(shí)有Pj≤0，則問(wèn)題為無(wú)界解。7/16/20240801.6.3無(wú)界解7/16/202480

41000

CBXB

b

x1x2x3x4x50

x32-111000

x441-40100x581-2001

0410007/16/20240811.6.3無(wú)界解7/16/202481

41000

CBXB

b

x1x2x3x4x50x360-31104x141-40100x54020-11160170-400

x312001-1/23/24

x112100-121

x22010-1/21/2500009/2-17/21.6.3無(wú)界解082本問(wèn)題無(wú)界。x1x2OZ=00831.6.3無(wú)界解—當(dāng)所有檢驗(yàn)數(shù)時(shí)，對(duì)某個(gè)非基變量xj

有cj-zj=0，且可以找到?！@表明可以找到另一個(gè)頂點(diǎn)（基可行解），其目標(biāo)函數(shù)值也到達(dá)最大?！捎诳尚杏?yàn)橥辜?，所以該兩點(diǎn)連線上的點(diǎn)也屬于可行域，且目標(biāo)函數(shù)值相等。即有無(wú)窮多解?！绻蟹腔兞康?，則LP問(wèn)題唯一解。7/16/20241.6.4無(wú)窮多最優(yōu)解84例1.8:

maxz=40x1+80x2x1+2x2

30

3x1+2x2

60

2x2

24

x1,x20x1+2x2+x3

=

303x1+2x2

+x4

=

602x2+x5=

24

x1…x507/16/20241.6.4無(wú)窮多最優(yōu)解85

4080000CBXBbx1x2x3x4x50x3

30121000x4603

2

0100x5240

2001040800000x361010-10

x4

363

0

01-180x2

12

01001/2(接下表)

40000-400861.6.4無(wú)窮多最優(yōu)解

4080000CBXBbx1x2x3x4x5

40x161

010-10x4

1800-31280x21201001/2120000-400040x11510-1/21/200x5

900-3/21/2180x215/2

0

13/4-1/40

120000-40000871.6.4無(wú)窮多最優(yōu)解X(1)=(6,12)Z(1)=1200X(2)=(15,15/2)Z(2)=1200無(wú)窮多解全部解：X=α+(1-α)

(0

α1)6151215/27/16/20241.6.4無(wú)窮多最優(yōu)解88退化解：—有時(shí)存在兩個(gè)以上相同的最小值，從而使下一個(gè)表的基可行解中出現(xiàn)一個(gè)或多個(gè)基變量等于零的退化解。7/16/20241.6.5退化和循環(huán)89例:maxz=10x1+

12x23x1+4x2

64x1+x2

23x1+2x2

3x1,x203x1+4x2+x3

=64x1+x2+x4

=

23x1+2x2+x5

=

3x1…x507/16/20241.6.5退化和循環(huán)90

1012000XBb

x1x2x3x4x5θi

0

x36341003/20x42410102/10x53320013/20101200012x23/23/411/40020x41/213/40-1/4102/130x50

3/20-1/20101810-30012x23/2011/20-1/20x41/2005/61-13/610x1010-1/302/3

1800-8/30-2/3

()()

1.6.5退化和循環(huán)退化解zmax=18x*

=(0,3/2,0,1/2,0)T但是，退化解情形有可能出現(xiàn)迭代計(jì)算的死循環(huán)！7/16/20241.6.5退化和循環(huán)92死循環(huán)的例子：1.6.5退化和循環(huán)093和初始基可行解相同1.6.5退化和循環(huán)094—為避免出現(xiàn)計(jì)算循環(huán)，可采用Bland(1974)準(zhǔn)則:(1)當(dāng)存在多個(gè)時(shí)，始終選取下標(biāo)值為最小的變量作為換入變量；(2)當(dāng)計(jì)算

θ值出現(xiàn)兩個(gè)或以上相同的最小比值時(shí)，始終選取下標(biāo)值為最小的變量作為換出變量；7/16/20241.6.5退化和循環(huán)95前例中，在第5張表時(shí)我們運(yùn)用Bland法則，得：7/16/20241.6.5退化和循環(huán)961.7應(yīng)用舉例7/16/20241.7應(yīng)用舉例

(1)要求解問(wèn)題的目標(biāo)能用數(shù)值指標(biāo)來(lái)表示，并且目標(biāo)函數(shù)z=f(x)為線性函數(shù)；

(2)存在著多種可選方案；

(3)要達(dá)到的目標(biāo)是在一定約束條件下實(shí)現(xiàn)的,這些約束條件可用線性等式或不等式來(lái)描述。一般來(lái)講，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡滿足以下條件時(shí)，才能建立線性規(guī)劃的模型。下面舉例說(shuō)明線性規(guī)劃在經(jīng)濟(jì)管理等方面的應(yīng)用。98

7/16/20241.7.1風(fēng)險(xiǎn)控制問(wèn)題997/16/20241.7.1風(fēng)險(xiǎn)控制問(wèn)題該問(wèn)題可以表述為如下的線性規(guī)劃模型：

1007/16/20241.7.1風(fēng)險(xiǎn)控制問(wèn)題目標(biāo)函數(shù)是帶有絕對(duì)值的特殊線性規(guī)劃問(wèn)題，如何將其轉(zhuǎn)換成一般的線性規(guī)劃模型呢？

101例1.11某工廠生產(chǎn)三種不同型號(hào)的潤(rùn)滑油A，B和C，表1.28是工廠剛剛接到的一季度生產(chǎn)訂單。已知每月生產(chǎn)三種潤(rùn)滑油的單位成本如表1.29所示，生產(chǎn)單位潤(rùn)滑油所需的工時(shí)分別為1，0.8和1.5（小時(shí)/噸）。該工廠每個(gè)月的最大生產(chǎn)能力均為900（小時(shí)）。若生產(chǎn)出來(lái)的潤(rùn)滑油當(dāng)月不交貨，每噸庫(kù)存1個(gè)月的存儲(chǔ)費(fèi)分別為220，200和160元。請(qǐng)為該廠設(shè)計(jì)一個(gè)既保證完成訂單，又使一季度生產(chǎn)和庫(kù)存總成本最低的生產(chǎn)計(jì)劃。7/16/20241.7.2生產(chǎn)庫(kù)存問(wèn)題102表1.28一季度生產(chǎn)訂單（單位：噸）7/16/20241.7.2生產(chǎn)庫(kù)存問(wèn)題表1.29一季度單位生產(chǎn)成本（單位：元/噸）103

目標(biāo)函數(shù)：總成本由生產(chǎn)成本和庫(kù)存成本兩部分構(gòu)成：7/16/20241.7.2生產(chǎn)庫(kù)存問(wèn)題

104約束條件：工時(shí)約束——各個(gè)月生產(chǎn)工時(shí)均不超過(guò)最大生產(chǎn)能力：交貨要求——各個(gè)月足以完成訂單需求即每月庫(kù)存量不小于0，于是有：非負(fù)約束——決策變量為生產(chǎn)產(chǎn)品的數(shù)量，因此是非負(fù)的，即7/16/20241.7.2生產(chǎn)庫(kù)存問(wèn)題

105某工廠生產(chǎn)一型號(hào)的機(jī)床，每臺(tái)機(jī)床上分別需用2.9、2.1、1.5米長(zhǎng)的軸1根、2根和1根，這些軸需用同一種圓鋼制作，圓鋼的長(zhǎng)度為7.4米。如需要生產(chǎn)100臺(tái)機(jī)床，問(wèn)應(yīng)如何安排下料，才能使用料最??？試建立其線性規(guī)劃模型。B1B2B3B4B5B6B7B8需要量2.9m2.1m1.5m余料10302010.10220.21200.30130.81110.90301.10041.4100200100最少7/16/20241.7.3合理下料問(wèn)題106解：設(shè)x1,x2,x3,x4,x5

分別為上面前

5種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。

目標(biāo)函數(shù)：

minx1+x2+x3+x4+x5

約束條件：

s.t.

x1+2x2+x4≥1002x3+2x4+x5≥2003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0必須為整數(shù)！7/16/20241.7.3合理下料問(wèn)題107某部門在五年內(nèi)考慮給下列項(xiàng)目投資：項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115％。項(xiàng)目B：從第三年初需投資，到第五年末能回收本利125％，但規(guī)定最大投資額不超過(guò)4萬(wàn)元。項(xiàng)目C：第二年初需要投資，到第五年末能回收本利140％，但規(guī)定最大投資額不超過(guò)3萬(wàn)元。項(xiàng)目D：五年內(nèi)每年初可購(gòu)買公債于當(dāng)年末歸還并加利息6％。該部門現(xiàn)有資金10萬(wàn)元，問(wèn)應(yīng)如何確定給這些項(xiàng)目每年的投資額，使到第五年末擁有的資金本利總額最大。

7/16/20241.7.4組合投資問(wèn)題1087/16/20241.7.4組合投資問(wèn)題確定變量：

以XiA,XiB,XiC,XiD(i=1,2,3,4,5)分別表示第

i年年初給項(xiàng)目A,B,C,D的投資額。具體列于下表：第1年第2年第3年第4年第5年ABCDX1AX1DX2AX2CX2DX3AX3BX3DX4