數(shù)學建模第二章線性規(guī)劃及單純形法

數(shù)學建模第二章線性規(guī)劃及單純形法1第1頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法

線性規(guī)劃（LinearProgramming，簡稱LP）運籌學的一個重要分支，是運籌學中研究較早、發(fā)展較快、理論上較成熟和應用上極為廣泛的一個分支。

1947年G.B.Dantying提出了一般線性規(guī)劃問題求解的方法——單純形法之后，線性規(guī)劃的理論與應用都得到了極大的發(fā)展。

60年來，隨著計算機的發(fā)展，線性規(guī)劃已廣泛應用于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸、經(jīng)濟管理和國防等各個領(lǐng)域，成為現(xiàn)代化管理的有力工具之一。2第2頁，共67頁，2023年，2月20日，星期五§1線性規(guī)劃問題及其數(shù)學模型e.g.1

資源的合理利用問題問：如何安排生產(chǎn)計劃，使工廠獲總利潤最大？

表1

產(chǎn)品資源 甲乙?guī)齑媪?/p>

A 1 3 60 B 1 1 40

單件利潤

15 25

某工廠在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，要消耗A、B兩種資源，已知每件產(chǎn)品對這兩種資源的消耗，這兩種資源的現(xiàn)有數(shù)量和每件產(chǎn)品可獲得的利潤如表1。3第3頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

解：

設(shè)x1，x2為下一個生產(chǎn)周期產(chǎn)品甲和乙的產(chǎn)量；

約束條件：Subjecttox1+3x2≤60x1

+x2≤40x1，x2≥0目標函數(shù)：z=15x1+25x2

表1

產(chǎn)品資源 甲乙?guī)齑媪?/p>

A 1 3 60 B 1 1 40

單件利潤

15 25

決策變量4第4頁，共67頁，2023年，2月20日，星期五§1線性規(guī)劃問題及其數(shù)學模型e.g.2

營養(yǎng)問題

假定在市場上可買到B1,B2,…Bnn

種食品，第

i

種食品的單價是ci,另外有m

種營養(yǎng)A1,A2,…Am。設(shè)Bj內(nèi)含有Ai

種營養(yǎng)數(shù)量為aij

(i=1~m,j=1~n)，又知人們每天對Ai

營養(yǎng)的最少需要量為bi。見表2：

表2

食品最少營養(yǎng) B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amnbm

單價

c1c2…cn

試在滿足營養(yǎng)要求的前提下，確定食品的購買量，使食品的總價格最低。5第5頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法

表2

食品最少營養(yǎng) B1B2…Bn需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amnbm

單價

c1c2…cn

解：

設(shè)xj

為購買食品Bj

的數(shù)量(j=1,2,…,n)（i=1,2,…,m）xj≥0（j=1,2,…,n）0≤xj≤lj6第6頁，共67頁，2023年，2月20日，星期五§1線性規(guī)劃問題及其數(shù)學模型三個基本要素：Note：1、善于抓住關(guān)鍵因素，忽略對系統(tǒng)影響不大的因素；2、可以把一個大系統(tǒng)合理地分解成n

個子系統(tǒng)處理。1、決策變量xj≥0

2、約束條件——一組決策變量的線性等式或不等式3、目標函數(shù)——決策變量的線性函數(shù)7第7頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法max（min）z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1

a21x1+a22x2+…+a2nxn≤（或=，≥）b2

……am1x1+am2x2+…+amnxn≤（或=，≥）bm

xj≥0（j=1,2,…,n）

其中aij、bi、cj（i=1,2,…,m；j=1,2,…,n）為已知常數(shù)線性規(guī)劃問題的一般形式：8第8頁，共67頁，2023年，2月20日，星期五§1線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃問題的標準形式：max

z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn

=

b2

……am1x1+am2x2+…+amnxn=

bm

xj≥0（j=1,2,…,n）

bi≥0（i=1,2,…,m）

特點：1、目標函數(shù)為極大化；2、除決策變量的非負約束外，所有的約束條件都是等式，且右端常數(shù)均為非負；3、所有決策變量均非負。9第9頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法如何轉(zhuǎn)化為標準形式？1、目標函數(shù)為求極小值，即為：。

因為求minz等價于求max(-z)，令z’=-z，即化為：

2、約束條件為不等式，xn+1≥0松弛變量如何處理？10第10頁，共67頁，2023年，2月20日，星期五§1線性規(guī)劃問題及其數(shù)學模型

３、右端項bi<0時，只需將等式兩端同乘（-1）則右端項必大于零

4、決策變量無非負約束

設(shè)xj

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

，則xj’≥0；

又若xj

為自由變量，即xj

可為任意實數(shù)，可令xj=xj’-xj’’，且xj’,xj’’≥011第11頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法e.g.3試將LP

問題minz=-x1+2x2-3x3

s.t.x1+x2+x3

≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0

化為標準形式。解：令x3=x4-x5

其中x4、x5

≥0；對第一個約束條件加上松弛變量x6

；對第二個約束條件減去松弛變量x7

；對第三個約束條件兩邊乘以“-1”；令z’=-z

把求minz

改為求maxz’maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

12第12頁，共67頁，2023年，2月20日，星期五§1線性規(guī)劃問題及其數(shù)學模型LP的幾種表示形式：13第13頁，共67頁，2023年，2月20日，星期五§2線性規(guī)劃問題的圖解法定義1在LP問題中，凡滿足約束條件(2)、(3)的解x=(x1,x2,…,xn)T

稱為LP問題的可行解，所有可行解的集合稱為可行解集（或可行域）。記作D={x|Ax=b,x≥0}。定義2

設(shè)LP問題的可行域為D，若存在x*∈D，使得對任意的x∈D

都有cx*≥cx，則稱x*為LP問題的最優(yōu)解，相應的目標函數(shù)值稱為最優(yōu)值，記作z*=cx*。14第14頁，共67頁，2023年，2月20日，星期五§2線性規(guī)劃問題的圖解法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目標函數(shù)變形：x2=-3/5

x1+z/25x2x1最優(yōu)解：

x1=30x2=10最優(yōu)值：zmax=700B點是使z達到最大的唯一可行點15第15頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法LP問題圖解法的基本步驟：1、在平面上建立直角坐標系；2、圖示約束條件，確定可行域和頂點坐標；3、圖示目標函數(shù)（等值線）和移動方向；4、尋找最優(yōu)解。16第16頁，共67頁，2023年，2月20日，星期五§2線性規(guī)劃問題的圖解法maxz=3x1+5.7x2

s.t.x1+1.9x2≥3.8

x1-1.9x2≤3.8x1+1.9x2≤11.4

x1-1.9x2≥-3.8

x1

，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1

+5.7x2

maxZ

minZ（3.8,4）34.2=3x1

+5.7x2

可行域x1-1.9x2=-3.8(0,2)(3.8,0)

綠色線段上的所有點都是最優(yōu)解,即有無窮多最優(yōu)解。Zman=34.217第17頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0OA(１,0)x1x2Note:可行域為無界區(qū)域，目標函數(shù)值可無限增大，即解無界。稱為無最優(yōu)解?？尚杏驗闊o界區(qū)域一定無最優(yōu)解嗎？18第18頁，共67頁，2023年，2月20日，星期五§2線性規(guī)劃問題的圖解法由以上兩例分析可得如下重要結(jié)論：1、LP問題從解的角度可分為：⑴

有可行解⑵

無可行解a.有唯一最優(yōu)解b.有無窮多最優(yōu)解c.無最優(yōu)解2、LP問題若有最優(yōu)解，必在可行域的某個頂點上取到；若有兩個頂點上同時取到，則這兩點的連線上任一點都是最優(yōu)解。19第19頁，共67頁，2023年，2月20日，星期五§2線性規(guī)劃問題的圖解法圖解法優(yōu)點：直觀、易掌握。有助于了解解的結(jié)構(gòu)。圖解法缺點：只能解決低維問題，對高維無能為力。20第20頁，共67頁，2023年，2月20日，星期五§3線性規(guī)劃問題解的基本性質(zhì)討論如下

LP

問題：其中系數(shù)矩陣決策向量

假設(shè)

A的秩為

m,且只討論

m<n的情形。什么意思？為什么？21第21頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法定義3在上述

LP問題中，約束方程組（2）的系數(shù)矩陣A的任意一個m×m階的非奇異的子方陣B（即|B|≠0），稱為LP問題的一個基陣或基。

稱

pi(i=1,2,…,m)為基向量;xi(i=1,2,…,m)為基變量；xj(j=m+1,…,n)為非基變量pj(j=m+1,…,n)為非基向量;記：則A=(B,N)22第22頁，共67頁，2023年，2月20日，星期五§3線性規(guī)劃問題解的基本性質(zhì)

A=(B,N)xB=(x1,…,xm)T,xN=(xm+1,…,xn)T則,代入約束方程（2），得

自由變量（獨立變量）令稱（4）為相應于基

B的基本解23第23頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法是可行解嗎？maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

令x1=x2=x4=0

如果

B-1b

≥0，則稱（4）為相應于基

B的基可行解，此時的基

B

稱為可行基。24第24頁，共67頁，2023年，2月20日，星期五§3線性規(guī)劃問題解的基本性質(zhì)基本解唯一嗎？最多有多少？Rn非可行解基可行解可基解行解稱它是非退化的解；反之，如果有一個基變量也取零值，則稱它是退化的解。一個LP問題，如果它的所有基可行解都是非退化的就稱該是非退化的，否則就稱它是退化的。定義4

在LP問題的一個基可行解中，如果它的所有的基變量都取正值，則25第25頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法LP

問題解的基本性質(zhì)定理1設(shè)x是LP問題的可行解(1)若x=0，則它一定是基可行解；(2)若x≠0，則x是基可行解的充要條件是它的非零分量所對應的列向量線性無關(guān)。Ax=0定理

2

如果一個LP問題有可行解，則它必有基可行解。定理

3

如果一個LP問題有最優(yōu)解，則必存在一個基可行解是它的最優(yōu)解。

定理2、定理3稱為LP問題的基本定理

定理2證明向前定理3證明LP問題是一個組合優(yōu)化問題26第26頁，共67頁，2023年，2月20日，星期五§3線性規(guī)劃問題解的基本性質(zhì)定理2證明

設(shè)x=(x1,x2,…,xn)T

是LP問題的一個可行解，如果x=0，則由定理1知，它是LP問題的一個基可行解，定理成立。

如果x≠0，不妨設(shè)

x的前k個分量為非零分量。則有

x1p1+x2p2+…+xkpk=b，及x1>0,x2>0,…,xk>0，分兩種情況討論：

如果p1,p2,…,pk線性無關(guān)，即x的非零分量對應的列向量線性無關(guān)，則由定理1知，它是LP的一個基本可行解，定理成立。(2)如果p1,p2,…,pk線性相關(guān)，則必存在一組不全為零的數(shù)

δ1,δ2,…,δk使得27第27頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法假定有δi≠0，取作其中由（6）式知，必有即又因為由（5）式知故有，，即也是LP的兩個可行解。28第28頁，共67頁，2023年，2月20日，星期五§3線性規(guī)劃問題解的基本性質(zhì)

再由的取法知，在式(7)的諸式中，至少有一個等于零，于是所作的可行解中，它的非零分量的個數(shù)至少比x的減少1，如果這些非零分量所對應的列向量線性無關(guān)，則為基可行解，定理成立。

否則，可以從出發(fā)，重復上述步驟，再構(gòu)造一個新的可行解，使它的非零分量的個數(shù)繼續(xù)減少。這樣經(jīng)過有限次重復之后，必可找到一個可行解使它的非零分量對應的列向量線性無關(guān)，故可行解必為基可行解。證畢。返回e29第29頁，共67頁，2023年，2月20日，星期五§3線性規(guī)劃問題解的基本性質(zhì)定理3證明設(shè)是LP

的一個最優(yōu)解。如果

x*是基本解，則定理成立；如果

x*不是基本解，則由定理2的證明過程可構(gòu)造兩個可行解它的非零分量的個數(shù)比x*

的減少，且有

，

又因為x*

是最優(yōu)解，故有由式（8）和（9）知，必有即x(1),x(2)

仍為最優(yōu)解。如果x(1)或x(2)

是基可行解，則定理成立。否則，按定理2證明過程，可得基可行解x(s)或x(s+1),使得即得基可行解x(s)或x(s+1)為最優(yōu)解。返回30第30頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法LP

問題解的幾何意義定義5設(shè)集合是n維歐氏空間中的一個點集，如果及實數(shù)

則稱

S是一個凸集。幾何意義：如果集合中任意兩點連線上的一切點都在該集合中，則稱該集合為凸集。

Note:空集和單點集也是凸集。31第31頁，共67頁，2023年，2月20日，星期五§3線性規(guī)劃問題解的基本性質(zhì)定義6

設(shè)則稱為點的一個凸組合。定義7設(shè)凸集兩點表示為則稱x為S

的一個極點（或頂點）。定理4LP問題的可行解集32第32頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法定理5設(shè)D為

LP問題的可行解集，，則x是

D的極點的充分必要條件是

x為

LP問題的基可行解。prove推論1如果LP

問題的可行解集非空，則極點集合也一定非空，且極點的個數(shù)是有限的。推論2如果LP

問題有最優(yōu)解，則一定可在可行解集

D的極點上達到。定理6設(shè)LP

問題在多個極點x(1),x(2),…x(k)處取到最優(yōu)解，則它們的凸組合，即也是LP

問題的最優(yōu)解.（此時，該LP

問題有無窮多最優(yōu)解）33第33頁，共67頁，2023年，2月20日，星期五§3線性規(guī)劃問題解的基本性質(zhì)Note:1、如何判斷

LP

問題有最優(yōu)解；2、計算復雜性問題。

設(shè)有一個50個變量、20個約束等式的LP問題，則最多可能有個基。即約150萬年

如果計算一個基可行解只需要1秒，那么計算所有的基可行解需要：1364.7101.510360024365′?′′′（年）34第34頁，共67頁，2023年，2月20日，星期五§4單純形法的基本原理

單純形法（SimplexMethod）是1947年由

G.B.Dantzig提出，是解

LP問題最有效的算法之一，且已成為整數(shù)規(guī)劃和非線性規(guī)劃某些算法的基礎(chǔ)。

基本思路：基于LP問題的標準形式，先設(shè)法找到一個基可行解，判斷它是否是最優(yōu)解，如果是則停止計算；否則，則轉(zhuǎn)換到相鄰的目標函數(shù)值不減的一個基可行解.（兩個基可行解相鄰是指它們之間僅有一個基變量不相同）。35第35頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法單純形法引例

首先，化原問題為標準形式：x3,x4

是基變量.基變量用非基變量表示：x3=60-x1-3x2

x4=40-x1

-x2代入目標函數(shù)：z=15x1+25x2令非基變量x1=x2=0z=0

基可行解

x(0)=(0,0,60,40)T是最優(yōu)解嗎？maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60

x1

+x2+x4=40x1，x2,x3,

x4≥0

36第36頁，共67頁，2023年，2月20日，星期五§4單純形法的基本原理z=15x1+25x2x3=60-x1-3x2

x4=40-x1

-x2因為x2的系數(shù)大，所以x2換入基變量。x3=60-3x2≥0x4=40-x2≥

0誰換出？如果x4換出，則x2=

40，x3=-60，不可行。如果是“+”會怎樣？如果x3換出，則x2=

20，x4=

20。最小比值法則所以x3

換出?；兞坑梅腔兞勘硎荆捍肽繕撕瘮?shù)：z=500+20/3

x1-25/3

x3令非基變量x1=x3=0z=500

基可行解

x(1)=(0,20,0,20)T大于零！37第37頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法因為x1的系數(shù)大，所以x1換入基變量。所以x4換出。基變量用非基變量表示：代入目標函數(shù)：z=700–5x3–10

x4令非基變量x3=x4=0z=700

基可行解

x(2)=(30,10,0,0)T

因為非基變量的系數(shù)都小于零，所以x(2)=(30,10,0,0)T是最優(yōu)解zmax=700

38第38頁，共67頁，2023年，2月20日，星期五§4單純形法的基本原理

目標函數(shù)用非基變量表示時，非基變量的系數(shù)稱為檢驗數(shù)(40,0)(0,0)(0,20)ABC(30,10)OL1L2Z=250x2x1x(0)=(0,0,60,40)Tz=0

x(1)=(0,20,0,20)Tz=500

x(2)=(30,10,0,0)Tz=700

39第39頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法單純形法的基本原理稱(1a)(2a)(3a)為LP問題對應于基B

的典則形式（典式）.Ax=b基變量用非基變量表示：代入目標函數(shù)：40第40頁，共67頁，2023年，2月20日，星期五§4單純形法的基本原理如果記則典式(1a)(2a)(3a)可寫成41第41頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法定理7在LP問題

的典式(1b)

～(3b)中，如果有則對應于基B

的基可行解是

LP問題的最優(yōu)解，記為相應的目標函數(shù)最優(yōu)值z*=z(0)此時，基B稱為最優(yōu)基42第42頁，共67頁，2023年，2月20日，星期五§4單純形法的基本原理定理8在LP問題

的典式(1b)

～(3b)中，是對應于基B

的一個基可行解，如果滿足下列條件：(1)有某個非基變量

xk的檢驗數(shù)

σk>0(m+1≤k≤n);(2)aik(i=1,2,…,m)不全小于或等于零，即至少有一個

aik>0(i=1,2,…,m);(3)>0(i=1,2,…,m),即x(0)為非退化的基可行解。則從

x(0)出發(fā)，一定能找到一個新的基可行解>43第43頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法定理9在LP問題的典式(1b)

～(3b)中，如果檢驗數(shù)滿足最優(yōu)準則σj≤0(j=m+1,…,n)，且其中有一個σk=0(m+1≤k≤n)，則該

LP問題有無窮多個最優(yōu)解。這在應用中很有價值定理10在LP問題的典式(1b)

～(3b)中，如果有某個非基變量的檢驗數(shù)σk>0(m+1≤k≤n)，且有則該

LP問題解無界（無最優(yōu)解）。44第44頁，共67頁，2023年，2月20日，星期五§5單純形法的計算步驟單純形表

c

c1c2cmcm+1cm+2cncBxBx1x2xmxm+1xm+2xnbc1c2cmx1x2xm

100a’1m+1a’1m+2a’1n

010a’2m+1a’2m+2a’2n

001a’mm+1a’mm+2a’mnb’1b’2b’m檢驗數(shù)

0

00-z(0)45第45頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法如何得到單純形表？

cAb檢驗數(shù)0B-1b-

cBB-1b

-z0IB-1NB-1b0σN檢驗數(shù)BNcBcNIB-1N0cN-cBB-1N46第46頁，共67頁，2023年，2月20日，星期五§5單純形法的計算步驟e.g.4

列出如下

LP

問題的初始單純形表。maxz=4x1+3x2+2x3+5x4s.t.x1+3x2+x3+2x4=54x1+2x2+3x3+7x4=

17

x1，x2

，x3，x4≥0不妨已知x3、x4

為可行基變量

ccBxB25x3x4檢驗數(shù)4325x1

x2

x3

x4131242374325b51701-70126-3105-2-117101140-12x(0)=(0,0,1,2

)Tz0=1247第47頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法單純形法求解LP

問題的計算步驟：Step1

找出初始可行基，列初始單純形表,確定初始基可行解；Step2

檢驗各非基變量xj的檢驗數(shù)σj,如果所有

的

σj

≤0（j=1,2,…,n），則已求得最優(yōu)解，停止計算。否則轉(zhuǎn)入下一步；Step3

在所有的σj

>0中，如果有某個σk>0，所對應的xk的系數(shù)列向量p’k≤0（即a’ik≤0，i=1,2,…,m），則此問題解無界，停止計算。否則轉(zhuǎn)入下一步;48第48頁，共67頁，2023年，2月20日，星期五§5單純形法的計算步驟Step4根據(jù),確定xk為換入基變量，又根據(jù)最小比值法則計算:確定xr為換出基變量。轉(zhuǎn)入下一步;Step5以為主元進行換基變換，用初等行變換將

xk所對應的列向量變換成單位列向量，即同時將檢驗數(shù)行中的第k個元素也變換為零，得到新的單純形表。返回Step2。49第49頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60

x1

+x2++x4=40x1，x2

，x3

，x4≥0

00

ccBxB00x3x4檢驗數(shù)152500x1

x2

x3

x413101101152500b6040001θx(0)=(0,0,60,40

)Tz0=0x21/3-500x(1)=(0,20,0,20

)Tz1=500x10-700x(2)=(30,10,0,0

)Tz2=7001/2檢驗數(shù)都小于等于零x(2)為最優(yōu)解

zmax=70060/340/12531/312000-1/312020/3-25/3020/1/320/2/3152/32/310-1/23/2300-1/2100-5-1050第50頁，共67頁，2023年，2月20日，星期五§5單純形法的計算步驟思考：在單純形法中根據(jù)確定xk為進基變量，是否在這次變換中，使目標函數(shù)值提高最大？

如果不是，應選擇哪個變量進基，保證這次變換使得目標函數(shù)值提高最大？目標函數(shù)值能提高多少？51第51頁，共67頁，2023年，2月20日，星期五§6單純形法的進一步討論一、初始可行基的求法

maxz=c1x1+c2x2+…+cnxn(1c)s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

……

…….

(2c)

am1x1+am2x2+…+amnxn=bm

xj≥0（j=1,2,…,n）

(3c)a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2

……

……

am1x1+am2x2+…+amnxn+xn+m

=bm

xj≥0（j=1,2,…,n,n+1,…,n+m）人工變量1、試算法人造基本解：x0=(0,0,…,0,b1,…,bm)T2、人工變量法52第52頁，共67頁，2023年，2月20日，星期五§6單純形法的進一步討論(1)大M法懲罰法maxw=c1x1+c2x2+…+cnxn–M(xn+1+…+xn+m)s.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2

……

……

am1x1+am2x2+…+amnxn+xn+m

=bm

xj≥0（j=1,2,…,n,n+1,…,n+m）M是一個充分大的正數(shù)結(jié)論：設(shè)為上述問題的最優(yōu)解則為原問題的最優(yōu)解，這時的目標函數(shù)值為最優(yōu)值；則原問題無可行解。不全為零，53第53頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法e.g.5用大M

法求解maxz=3x1-x2–

x3s.t.x1-2x2+x3≤11-4x1

+x2+2x3≥3-2x1+x3=1x1，x2，x3≥0

maxz=3x1-x2–

x3+0

x4+0

x5-M

x6-M

x7s.t.x1-2x2+x3+x4=11-4x1

+x2+2x3-x5+x6=3-2x1+x3+

x7=1xj≥0(j=1,2,…,7)解：引入松弛變量

x4，

x5

和人工變量

x6，

x7得

ccBxB-M0x4x6檢驗數(shù)3-1-100-M-Mx1

x2

x3

x4x5

x6

x7131011012-100b110001θ-2-4-20011x7-M3-1-100-M-M3-4MM-12M-10-M0-M3M3-6MM-13M-10-M004M11/13/21/1x3-113-201100-1100100-11-211M-100-M1-3MM+11/11x2-13001-22-5121000-1-1-M2112/3x13001/3-2/32/3-5/340012/3-4/34/3-7/39000-1/3-1/32/3-M-23101-M1/3-M

200-0.2M>0?

由于人工變量

x6=x7=0,

所以,得原問題的最優(yōu)解x*=(4,1,9,0,0)T

目標函數(shù)最優(yōu)值

zmax=2

Note:在計算過程中,某個人工變量一旦變?yōu)榉腔兞?則該列可被刪去

54第54頁，共67頁，2023年，2月20日，星期五§6單純形法的進一步討論(2)兩階段法第一階段：

maxz=c1x1+c2x2+…+cnxn(1c)s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

……

…….

(2c)

am1x1+am2x2+…+amnxn=bm

xj≥0（j=1,2,…,n）

(3c)

maxw=–xn+1

–

xn+2

–…–

xn+m(1d)s.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2

……

……

(2d)

am1x1+am2x2+…+amnxn+xn+m

=bm

xj≥0（j=1,2,…,n,n+1,…,n+m）(3d)

判斷原LP

問題（1c）~（3c）是否存在可行解，如果存在就找出一個初始基可行解；解之可得：（a）如果

wmax<0,

則原問題無可行解，停止計算；（b）如果

wmax=0,且人工變量都不是基變量，則轉(zhuǎn)入第二階段；55第55頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法（c）如果

wmax=0,但仍有取零的人工變量為基變量；x1

x2

…

xn

xn+1

…xn+k

…

xn+mba’l1a’l2…

a’lna’ln+1…

1

…

a’n+m0如xn+k=0

是基變量，在最終單純形表中：a’l1a’l2…

a’ln

不可能全為零，必有某個a’lj≠0，這時xj不是基變量，與xn+k交換即可。第二階段：從第一階段所求得的初始可行基出發(fā)，求解原問題56第56頁，共67頁，2023年，2月20日，星期五§6單純形法的進一步討論二、關(guān)于退化和循環(huán)1955

年

Beale

給出如下例子：最優(yōu)解：B0=(P1,P2,P3)作為初始可行基，經(jīng)6次迭代又得B057第57頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法Bland

法則：（對極大值問題而言）則選擇xk作為進基變量。選擇進基變量：選取σj

>0（1≤j≤n）中下標最小的檢驗數(shù)σk所對應的非基變量xk作為進基變量，即如果(2)選擇出基變量：當按θ規(guī)則計算此值時，如果存在n個，同時達到最小值，就選其中下標最小的那個基變量作為出基變量。即如果則選擇xl作為出基變量。58第58頁，共67頁，2023年，2月20日，星期五§7線性規(guī)劃應用舉例e.g.6

生產(chǎn)計劃問題

某工廠明年根據(jù)合同，每個季度末向銷售公司提供產(chǎn)品，有關(guān)信息如表，若當季生產(chǎn)的產(chǎn)品過多，季末有積余，則一個季度每積壓一噸產(chǎn)品需支付存貯費0.2萬元.現(xiàn)該廠考慮明年的最佳生產(chǎn)方案，使該廠在完成合同的情況下，全年的生產(chǎn)費用最低.試建立線性規(guī)劃模型.季度

j生產(chǎn)能力（aj）生產(chǎn)成本（dj）需求量（bj）13015．02024014．02032015．33041014．81059第59頁，共67頁，2023年，2月20日，星期五第二章線性規(guī)劃及單純形法解：方法一設(shè)工廠第j季度生產(chǎn)產(chǎn)品xj

噸需求約束：第一季度末需交貨20噸，x1≥20第二季度末需交貨20噸，x1-20+x2≥20這是上季末交貨后積余第三季度末需交貨30噸，x1+x2-40+x3≥30第四季度末需交貨10噸，x1+x2+x3-70

+x4=10生產(chǎn)能力約束：0≤xj≤aj

j=1,2,3,4季度

j生產(chǎn)能力（aj）生產(chǎn)成本（dj）需求量（bj）13015．02024014．02032015．33041014．810生產(chǎn)、存儲費用：第一季度：15x1第二季度:14x2+0.2(x1-20)第三季度:15.3x3+0.2(x1+x2-40)第四季度:14.8x4+0.2(x1+x2+x3-70

)min

z

=15.6x1

+14.4x2+15.5x3+

14.8x4-26s.t.x1+x2≥40,x1+x2+x3≥70

x1+x2+x3+

x4=80,20≤x1≤30,0

≤x2≤40,0

≤x3≤20,0≤

x4≤10.60第60頁，共67頁，2023年，2月20日，星期五§7線性規(guī)劃應用舉例季度

j生產(chǎn)能力（aj）生產(chǎn)成本（dj）需求量（bj）13015．02024014．02032015．33041014．810方法二設(shè)第i季度生產(chǎn)而用于第j季度末交貨的產(chǎn)品數(shù)量為

xij噸.需求約束：x11=20

x12+x22=20x13+x23+x33=30

x14+x24+x34+x44=10

生產(chǎn)能力約束：x11

+x12

+x13+x14

≤30x22

+x23

+x24≤

40,x33+x34≤20,x44≤

10

xij的費用cij=di+0.2(j-i)minz=15x11+15.2x12

+15.4x13+15.6x14

+14x22

+14.2x23+14.4x24+15.3x33+15.5x34+14.8x44s.t.x11=20

x11

+x12

+x13+x14

≤30x12+x22=20x22

+x23

+x24≤40x13+x23+x33=30