線性規(guī)劃與單純形法演示文稿

線性規(guī)劃與單純形法演示文稿當前第1頁\共有110頁\編于星期二\13點優(yōu)選線性規(guī)劃與單純形法當前第2頁\共有110頁\編于星期二\13點Chapter1線性規(guī)劃

(LinearProgramming)LP的數學模型圖解法單純形法單純形法的進一步討論

LP模型的應用本章主要內容：3當前第3頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型1.規(guī)劃問題生產和經營管理中經常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當任務或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設備、原標材料、人工、時間等）去完成確定的任務或目標（2）在一定的資源條件限制下，如何組織安排生產獲得最好的經濟效益（如產品量最多、利潤最大.）4當前第4頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型例1.1如圖所示，如何截取x使鐵皮所圍成的容積最大？xa5當前第5頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型例1.2某廠生產兩種產品，下表給出了單位產品所需資源及單位產品利潤問：應如何安排生產計劃，才能使總利潤最大？解：1.決策變量：設產品I、II的產量分別為x1、x22.目標函數：設總利潤為z，則有：

maxz=2x1+x23.約束條件：

5x2≤156x1+2x2≤24x1+x2≤5

x1，x2≥06當前第6頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型例1.3已知資料如下表所示，問如何安排生產才能使利潤最大？或如何考慮利潤大，產品好銷。

設備產品AB

C

D利潤（元）

Ⅰ21402

Ⅱ22043

有效臺時1281612解：1.決策變量：設產品I、II的產量分別為x1、x22.目標函數：設總利潤為z，則有：maxz=2x1+x23.約束條件：

x1≥0,x2≥0

2x1+2x2≤12x1+2x2≤84x1≤164x2≤127當前第7頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型例1.4

某廠生產三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量解：要求：生產A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過180單位，且使原料總成本最小。1.決策變量：設四種原料的使用量分別為：x1、x2、x3

、x42.目標函數：設總成本為zmin

z=5x1+6x2+7x3+8x43.約束條件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝2003x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥08當前第8頁\共有110頁\編于星期二\13點

例1.5

某航運局現(xiàn)有船只種類、數量以及計劃期內各條航線的貨運量、貨運成本如下表所示：航線號船隊類型編隊形式貨運成本（千元／隊）貨運量（千噸）拖輪A型駁船B型駁船1112—362521—4362023224724041—42720船只種類船只數拖輪30A型駁船34B型駁船52航線號合同貨運量12002400問：應如何編隊，才能既完成合同任務，又使總貨運成本為最??？線性規(guī)劃問題的數學模型9當前第9頁\共有110頁\編于星期二\13點

解：設xj為第j號類型船隊的隊數（j=1，2，3，4），

z

為總貨運成本則：

minz=36x1+36x2+72x3+27x4

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

＝20040x3+20x4＝400

xj≥0（

j

=1,2,3,4）線性規(guī)劃問題的數學模型10當前第10頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型2.線性規(guī)劃的數學模型由三個要素構成決策變量Decisionvariables目標函數Objectivefunction約束條件Constraints其特征是：（1）問題的目標函數是多個決策變量的線性函數，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式。

怎樣辨別一個模型是線性規(guī)劃模型？

11當前第11頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型3.建模條件(1)

優(yōu)化條件：問題所要達到的目標能用線型函數描述，且能夠用極值（max或min）來表示；(2)

限定條件：達到目標受到一定的限制，且這些限制能夠用決策變量的線性等式或線性不等式表示；(3)

選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。12當前第12頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型4.建模步驟(1)

確定決策變量：即需要我們作出決策或選擇的量。一般情況下，先從目標函數考慮決策變量；(2)寫出目標函數：即問題所要達到的目標，并明確是max還是min。(3)找出所有限定條件：即決策變量受到的所有的約束；13當前第13頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型約束條件：5.線性規(guī)劃數學模型的一般形式簡寫為：14目標函數：當前第14頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型向量形式：其中：15當前第15頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型矩陣形式：其中：16當前第16頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型6.線性規(guī)劃問題的標準形式特點：(1)目標函數求最大值（有時求最小值）(2)約束條件都為等式方程，且右端常數項bi都大于或等于零(3)決策變量xj為非負。17當前第17頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型（2）如何化標準形式

目標函數的轉換

如果是求極小值即，則可將目標函數乘以(-1)，可化為求極大值問題。也就是：令，可得到上式。即

若存在取值無約束的變量，可令其中：

變量的變換18當前第18頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型

約束方程的轉換：由不等式轉換為等式。稱為松弛變量稱為剩余變量

常量bi＜0

的變換:約束方程兩邊乘以（－1）19當前第19頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型例1.6

將下列線性規(guī)劃問題化為標準形式用替換，且解:（１）因為x3無符號要求，即x3取正值也可取負值，標準型中要求變量非負，所以20當前第20頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型(2)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個約束條件是“≥”號，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個約束方程右端常數項為-5，方程兩邊同乘以(-1),將右端常數項化為正數；(5)目標函數是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當z達到最小值時z′達到最大值，反之亦然;21當前第21頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型標準形式如下：22當前第22頁\共有110頁\編于星期二\13點

例1.7將下列線性規(guī)劃問題化為標準形式為無約束（無非負限制）線性規(guī)劃問題的數學模型23當前第23頁\共有110頁\編于星期二\13點

解:用替換，且，將第3個約束方程兩邊乘以（－1）將極小值問題反號，變?yōu)榍髽O大值標準形式如下：引入變量線性規(guī)劃問題的數學模型24當前第24頁\共有110頁\編于星期二\13點

例1.8將線性規(guī)劃問題化為標準型解：線性規(guī)劃問題的數學模型25當前第25頁\共有110頁\編于星期二\13點

例1.9將線性規(guī)劃問題化為標準型解：Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0；x2無約束

Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

線性規(guī)劃問題的數學模型26當前第26頁\共有110頁\編于星期二\13點線性規(guī)劃問題的數學模型7.線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標函數(1)達到最大值。27當前第27頁\共有110頁\編于星期二\13點線性規(guī)劃問題解的概念

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

最優(yōu)解：使目標函數達到最大值的可行解。

基：設A為約束條件②的m×n階系數矩陣(m<n)，其秩為m，B是矩陣A中m階滿秩子矩陣（∣B∣≠0），稱B是規(guī)劃問題的一個基。設：稱B中每個列向量Pj(j=12…

…m)

為基向量。與基向量Pj

對應的變量xj

為基變量。除基變量以外的變量為非基變量。28當前第28頁\共有110頁\編于星期二\13點線性規(guī)劃問題解的概念

基解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個數不大于方程數m，基解的總數不超過

基可行解：滿足變量非負約束條件的基本解，簡稱基可行解?？尚谢簩诨尚薪獾幕Q為可行基。非可行解可行解基解基可行解29

基解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個數不大于方程數m，基解的總數不超過

基可行解：滿足變量非負約束條件的基本解，簡稱基可行解?？尚谢簩诨尚薪獾幕Q為可行基。當前第29頁\共有110頁\編于星期二\13點線性規(guī)劃問題解的概念例1.10

求線性規(guī)劃問題的所有基矩陣。解:約束方程的系數矩陣為2×5矩陣r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即30當前第30頁\共有110頁\編于星期二\13點圖解法線性規(guī)劃問題的求解方法一般有兩種方法圖解法單純形法兩個變量、直角坐標三個變量、立體坐標適用于任意變量、但必需將一般形式變成標準形式下面我們分析一下簡單的情況——

只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。31當前第31頁\共有110頁\編于星期二\13點

解題步驟4將最優(yōu)解代入目標函數，求出最優(yōu)值。1在直角平面坐標系中畫出所有的約束等式，并找出所有約束條件的公共部分，稱為可行域，可行域中的點稱為可行解。2標出目標函數值增加或者減小的方向。3若求最大（?。┲担瑒t令目標函數等值線沿（逆）目標函數值增加的方向平行移動，找與可行域最后相交的點，該點就是最優(yōu)解。圖解法32當前第32頁\共有110頁\編于星期二\13點圖解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.11用圖解法求解線性規(guī)劃問題33當前第33頁\共有110頁\編于星期二\13點圖解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此點是唯一最優(yōu)解，且最優(yōu)目標函數值

maxZ=17.2可行域maxZ=2X1+X234當前第34頁\共有110頁\編于星期二\13點圖解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）34.2=3X1+5.7X2

藍色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標函數值maxZ=34.2是唯一的?？尚杏?5當前第35頁\共有110頁\編于星期二\13點圖解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點是唯一最優(yōu)解36當前第36頁\共有110頁\編于星期二\13點圖解法246x1x2246無界解(無最優(yōu)解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ37當前第37頁\共有110頁\編于星期二\13點x1x2O10203040102030405050無可行解(即無最優(yōu)解)maxZ=3x1+4x2例1.738當前第38頁\共有110頁\編于星期二\13點

由圖解法得到的幾種情況

根據以上例題，進一步分析討論可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況：

1.可行域為封閉的有界區(qū)域

(a)有唯一的最優(yōu)解；(b)有無窮多個最優(yōu)解；

2.可行域為封閉的無界區(qū)域

(c)有唯一的最優(yōu)解；(d)有無窮多個最優(yōu)解；

(e)目標函數無界(即雖有可行解，但在可行域中，目標函數可以無限增大或無限減少)，因而沒有有限最優(yōu)解。

3.可行域為空集

(f)沒有可行解，原問題無最優(yōu)解圖解法39當前第39頁\共有110頁\編于星期二\13點

由圖解法得到的啟示(1)線性規(guī)劃問題解的情況：唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解(3)最優(yōu)解一定是在凸集的某個頂點(2)線性規(guī)劃問題的可行域是凸集（凸多邊形）(4)解題思路是，先找出凸集的任一頂點，計算其目標函數值，再與周圍頂點的目標函數值比較，如不是最大，繼續(xù)比較，直到找出最大為止。圖解法40當前第40頁\共有110頁\編于星期二\13點圖解法

學習要點：

1.通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）

2.作圖的關鍵有三點：

(1)可行解區(qū)域要畫正確

(2)目標函數增加的方向不能畫錯

(3)目標函數的直線怎樣平行移動41當前第41頁\共有110頁\編于星期二\13點單純形法基本原理凸集：如果集合C中任意兩個點X1、X2，其連線上的所有點也都是集合C中的點，稱C為凸集。凸集凸集不是凸集頂點

頂點：如果凸集C中不存在任何兩個不同的點X1，X2，使X成為這兩個點連線上的一個點42當前第42頁\共有110頁\編于星期二\13點單純形法基本原理當前第43頁\共有110頁\編于星期二\13點單純形法基本原理定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應可行域(凸集)的頂點。定理3：若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（或在某個頂點取得）44當前第44頁\共有110頁\編于星期二\13點單純形法的計算步驟單純形法的思路找出一個初始可行解是否最優(yōu)轉移到另一個基本可行解（找出更大的目標函數值）最優(yōu)解是否循環(huán)核心是：變量迭代結束45當前第45頁\共有110頁\編于星期二\13點單純形法的計算步驟單純形表46當前第46頁\共有110頁\編于星期二\13點單純形法的計算步驟例1.12用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問題化為標準型，加入松馳變量x3、x4則標準型為:47當前第47頁\共有110頁\編于星期二\13點單純形法的計算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicB基bx1x2x3x40x34021100x43013013400檢驗數48當前第48頁\共有110頁\編于星期二\13點單純形法的計算步驟3）進行最優(yōu)性檢驗如果表中所有檢驗數，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。4）從一個基可行解轉換到另一個目標值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對應的變量xj作為換入變量，當有一個以上檢驗數大于0時，一般選擇最大的一個檢驗數，即：，其對應的xk作為換入變量。確定換出變量。根據下式計算并選擇θ

，選最小的θ對應基變量作為換出變量。 49當前第49頁\共有110頁\編于星期二\13點單純形法的計算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應新的基可以找出一個新的基可行解，并相應地可以畫出一個新的單純形表。5）重復3）、4）步直到計算結束為止。 50當前第50頁\共有110頁\編于星期二\13點單純形法的計算步驟cj3400θicB基變量bx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－151當前第51頁\共有110頁\編于星期二\13點單純形法的計算步驟例1.13

用單純形法求解解：將數學模型化為標準形式：不難看出x4、x5可作為初始基變量，列單純形表計算。52當前第52頁\共有110頁\編于星期二\13點單純形法的計算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/353當前第53頁\共有110頁\編于星期二\13點變成標準型單純形法的計算步驟例1.14用單純形法求解54當前第54頁\共有110頁\編于星期二\13點約束方程的系數矩陣為基變量為非基變量I為單位矩陣且線性獨立單純形法的計算步驟55當前第55頁\共有110頁\編于星期二\13點56當前第56頁\共有110頁\編于星期二\13點57當前第57頁\共有110頁\編于星期二\13點58當前第58頁\共有110頁\編于星期二\13點單純形法的計算步驟

學習要點：

1.線性規(guī)劃解的概念以及3個基本定理

2.熟練掌握線性規(guī)劃問題的標準化

3.熟練掌握單純形法的解題思路及求解步驟59當前第59頁\共有110頁\編于星期二\13點單純形法的進一步討論－人工變量法60當前第60頁\共有110頁\編于星期二\13點單純形法的進一步討論－人工變量法人工變量法： 前面討論了在標準型中系數矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。61當前第61頁\共有110頁\編于星期二\13點大M法約束條件：“≥”→減一個剩余變量后，再加一個人工變量“＝”→加一個人工變量目標函數：人工變量的系數為“－M”，即罰因子若原線性規(guī)劃問題有最優(yōu)解則人工變量必為0。62當前第62頁\共有110頁\編于星期二\13點MaxZ=-3x1+x3-Mx6-Mx7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,7MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3增加人工變量后，線性規(guī)劃問題中就存在一個B為單位矩陣，陣，后面可以根據我們前面所講的單純形法來進行求解。標準化及變形63當前第63頁\共有110頁\編于星期二\13點cj-30100-M-MCBXBbix1x2x3x4x5x6x7θ0x441111000-Mx61-21-10-110-Mx790310001σj-3-2M4M100[]3x2入，x6出-M041[]0x40x2-Mx7330211-10σj6M-304M+10-4M[]-x1入，x7出3M01-21-10-1101660403-311[]0x40x2-3x100001-1/21/2-1/2σj0030-M-3/2[]9x3入，x1出3/2-M+1/23011/30001/33/21102/301/2-1/21/6-[]0x40x21x300001-1/21/2-1/2σj-9/2000-M+3/4-3/4-M-1/45/2-1/2100-1/41/41/43/23/20103/4-3/41/4所以：X*=(x2,x3,x4)T=(5/2,3/2,0)TZ*=3/264當前第64頁\共有110頁\編于星期二\13點

第一階段：暫不考慮原問題是否存在基可行解，給原問題加入人工變量，并構建一個僅含人工變量的目標函數（求極小化），人工變量的價值系數一般為1，約束條件和原問題的一樣。當第一階段中目標函數的最優(yōu)值＝0，即人工變量＝0，則轉入第二階段；若第一階段中目標函數的最優(yōu)值不等于0，即人工變量不等于0，則判斷原問題為無解。

第二階段：將第一階段計算所得的單純形表劃去人工變量所在的列，并將目標函數換為原問題的目標函數作為第二階段的初始單純形表，進行進一步的求解。兩階段法65當前第65頁\共有110頁\編于星期二\13點輔助問題66當前第66頁\共有110頁\編于星期二\13點輔助問題與原問題的關系67當前第67頁\共有110頁\編于星期二\13點求輔助問題的三種情況68當前第68頁\共有110頁\編于星期二\13點求解輔助問題，得到輔助問題的最優(yōu)解引進人工變量x6，x7，構造輔助問題，輔助問題的目標函數為所有人工變量之和的極小化MaxW=0?原問題沒有可行解。把輔助問題的最優(yōu)解作為原問題的初始基礎可行解用單純形法求解原問題，得到原問題的最優(yōu)解否是兩階段法的算法流程圖MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3MaxW=-x6-x7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,769當前第69頁\共有110頁\編于星期二\13點cj00000-1-1CBXBbix1x2x3x4x5x6x7θ0x441111000-1x61-21-10-110-1x790310001(第一階段）單純形表1σj-24000[]3x2入，x6出-1041[]0x40x2-1x7330211-10σj6040-4[]－x1入，x7出301-21-10-1101660403-311[]0x40x20x100001-1/21/2-1/2σj0000-10-13011/30001/31102/301/2-1/21/6所以：已得最優(yōu)解，且人工變量為非基變量，則可去掉人工變量，得原問題的一個即可行基。70當前第70頁\共有110頁\編于星期二\13點（第二階段）單純形表2cj-30100CBXBbix1x2x3x4x5θ0x400001-1/20x23011/300-3x11102/301/2σj00303/2[]-93/2[]0x40x21x35/2-1/2100-1/400001-1/23/23/20103/4x3入，x1出σj-9/2000-3/4所以：X*=(x2,x3,x4)T=(5/2,3/2,0)TZ*=3/271當前第71頁\共有110頁\編于星期二\13點單純形法的進一步討論－人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數學模型化為標準形式系數矩陣中不存在單位矩陣，無法建立初始單純形表。72當前第72頁\共有110頁\編于星期二\13點單純形法的進一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數學模型：其中：M是一個很大的抽象的數，不需要給出具體的數值，可以理解為它能大于給定的任何一個確定數值；再用前面介紹的單純形法求解該模型，計算結果見下表。73當前第73頁\共有110頁\編于星期二\13點單純形法的進一步討論－人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M-Mx63-650-1013/50x58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——0x531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→74當前第74頁\共有110頁\編于星期二\13點單純形法的進一步討論－人工變量法例1.11用大M法解下列線性規(guī)劃解：首先將數學模型化為標準形式系數矩陣中不存在單位矩陣，無法建立初始單純形表。75當前第75頁\共有110頁\編于星期二\13點單純形法的進一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數學模型：其中：M是一個很大的抽象的數，不需要給出具體的數值，可以理解為它能大于給定的任何一個確定數值；再用前面介紹的單純形法求解該模型，計算結果見下表。76當前第76頁\共有110頁\編于星期二\13點單純形法的進一步討論－人工變量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z-4M3-6M-1+M-1+3M0-M000x4103-20100-1－-Mx610100-11-21-1x31-2010001－Z-M-11-1+M00-M0-3M+1→→77當前第77頁\共有110頁\編于星期二\13點單純形法的進一步討論－人工變量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4123001-22-54-1x210100-11-2－-1x31-2010001－Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+2/3→78當前第78頁\共有110頁\編于星期二\13點單純形法的進一步討論－兩階段法

用計算機處理數據時，只能用很大的數代替M,可能造成計算機上的錯誤，故多采用兩階段法。

第一階段：在原線性規(guī)劃問題中加入人工變量，構造如下模型：

對上述模型求解（單純形法），若ω=0,說明問題存在基可行解，可以進行第二個階段；否則，原問題無可行解，停止運算。79當前第79頁\共有110頁\編于星期二\13點單純形法的進一步討論－兩階段法第一階段的線性規(guī)劃問題可寫為：第一階段單純形法迭代的過程見下表（注意：沒有化為極大化問題）80當前第80頁\共有110頁\編于星期二\13點單純形法的進一步討論－兩階段法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011ω46-1-301000x4103-20100-1－1x610100-11-210x31-2010001－ω10-1001030x4123001-22-50x210100-11-20x31-2010000ω00000011→→81當前第81頁\共有110頁\編于星期二\13點單純形法的進一步討論－兩階段法

第二階段：在第一階段的最終表中，去掉人工變量，將目標函數的系數換成原問題的目標函數系數，作為第二階段計算的初始表（用單純形法計算）。例：82當前第82頁\共有110頁\編于星期二\13點單純形法的進一步討論－兩階段法cj3-1-100cBxBbx1x2x3x4x50x4123001-24-1x210100-1－-1x31-20100－Z-21000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3Z2000-1/3-1/3→第二階段：∴最優(yōu)解為（41900），目標函數Z=283當前第83頁\共有110頁\編于星期二\13點單純形法的進一步討論

通過大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標函數的極小值大于零，那么該線性規(guī)劃就不存在可行解。

無可行解84當前第84頁\共有110頁\編于星期二\13點C

-3-2-1000-M-MCB

XB

bx1x2x3x4x5x6x7x8

θ0-M-Mx4x7x8

6431111000010-10-101001-100-1016/1-3/1Z-7M-6-4M-15-M-3+M-2+M-1-2M0-M-M000-M-2x4x7x2

3431021010-110-10-101001-100-1013/14/1-ZZ-3+M0-3-M0-M-202-M-3-M-2x1x7x2

3131021010-100-3-1-1-11101-100-101003-3M3-M-M1-M0-1例單純形法的進一步討論運算到檢驗數全負為止，仍含有人工變量，無可行解。85當前第85頁\共有110頁\編于星期二\13點單純形法的進一步討論

無最優(yōu)解與無可行解時兩個不同的概念。無可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指線性規(guī)劃問題的可行域為空集；無最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目標函數達不到最優(yōu)值，即目標函數在可行域內可以趨于無窮大（或者無窮?。?。無最優(yōu)解也稱為有限最優(yōu)解，或無界解。

判別方法：無最優(yōu)解判別定理在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗行存在某個大于零的檢驗數，但是該檢驗數所對應的非基變量的系數列向量的全部系數都為負數或零，則該線性規(guī)劃問題無最優(yōu)解

無最優(yōu)解86當前第86頁\共有110頁\編于星期二\13點C2200θ

CXB

B

x1

x2

x3

x4

0X3

1-11100X4

2-1/2101Z02200因但所以原問題無最優(yōu)解單純形法的進一步討論87當前第87頁\共有110頁\編于星期二\13點

退化即計算出的θ（用于確定換出變量）存在有兩個以上相同的最小比值，會造成下一次迭代中由一個或幾個基變量等于零，這就是退化（會產生退化解）。為避免出現(xiàn)計算的循環(huán)，勃蘭特(Bland)提出一個簡便有效的規(guī)則（攝動法原理）：⑴當存在多個時，選下標最小的非基變量為換入變量；(2)當θ值出現(xiàn)兩個以上相同的最小值時，選下標最小的基變量為換出變量。單純形法的進一步討論88當前第88頁\共有110頁\編于星期二\13點000-242-8030Z-5-60-420-805Z10001001x3

212060-2411x1

3321300-803x5

00-30-425-800Z11001001x7

00106-1-2410x1

30-1130-3-800x5

0-11001001x7

000106-1-2410x6

0000136-4-3210x5

0x7

x6

x5

x4

x3

x2

x1

b

XB

CB

000-242-803C

θ

第一次迭代中使用了攝動法原理，選擇下標為6的基變量x6離基?？傻米顑?yōu)解maxZ=５，單純形法的進一步討論89當前第89頁\共有110頁\編于星期二\13點

無窮多最優(yōu)解若線性規(guī)劃問題某個基本可行解所有的非基變量檢驗數都小于等于零，但其中存在一個檢驗數等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。例３：最優(yōu)表：非基變量檢驗數，

所以有無窮多最優(yōu)解。C12000θCBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z’80000-1單純形法的進一步討論90當前第90頁\共有110頁\編于星期二\13點單純形法的進一步討論解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數非零,則線性規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數為零,則線性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當用大M單純形法計算得到最優(yōu)解并且存在Ri>0時，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。91當前第91頁\共有110頁\編于星期二\13點單純形法的進一步討論單純性法小結:建立模型個數取值右端項等式或不等式極大或極小新加變量系數兩個三個以上xj≥0xj無約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj’

=-xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′=-ZminZ=－maxz′0-M92當前第92頁\共有110頁\編于星期二\13點A93當前第93頁\共有110頁\編于星期二\13點應用舉例將經濟管理領域的實際問題抽象為數學模型，是一項技巧性很強的創(chuàng)造性工作，它要求對研究對象的本質有深刻的理解，并能熟練的掌握有關線性規(guī)劃模型的結構特點，運用數學技巧。因此在研究一些復雜問題的數學模型時需要各方面專業(yè)人員的通力協(xié)作配合。94當前第94頁\共有110頁\編于星期二\13點

線性規(guī)劃模型的應用

一般而言，一個經濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。

要求解問題的目標函數能用數值指標來反映，且為線性函數存在著多種方案要求達到的目標是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述95當前第95頁\共有110頁\編于星期二\13點

線性規(guī)劃模型的應用常見問題合理利用線材問題：如何下料使用材最少。配料問題：在原料供應量的限制下如何獲取最大利潤。投資問題：從投資項目中選取方案，使投資回報最大。產品生產計劃：合理利用人力、物力、財力等，使獲利最大。勞動力安排：用最少的勞動力來滿足工作的需要。運輸問題：如何制定調運方案，使總運費最小。96當前第96頁\共有110頁\編于星期二\13點

線性規(guī)劃模型的應用(1)設立決策變量；

(2)用決策變量的線性函數表示目標，并確定是求極大（Max）還是極?。∕in）；

(3)明確約束條件并用決策變量的線性等式或不等式表示；

(4)根據決策變量的