1172線性規(guī)劃問題及其數(shù)學模型

第一章線性規(guī)劃與單純形法第一章線性規(guī)劃與單純形法第1節(jié)線性規(guī)劃問題及其數(shù)學模型第2節(jié)線性規(guī)劃問題的幾何意義第3節(jié)單純形法第4節(jié)單純形法的計算步驟第5節(jié)單純形法的進一步討論第6節(jié)應用舉例第一節(jié)線性規(guī)劃問題及其數(shù)學模型本節(jié)內(nèi)容的安排問題的提出線性規(guī)劃問題的標準形式線性規(guī)劃問題解的概念小*結(jié)圖解法【例1】最優(yōu)生產(chǎn)方案問題。某工廠在方案期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗，如表1-1所示。該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問應如何安排方案使該工廠獲利最多?1.1問題的提出預備知識：1、融會貫穿地理解要解決的問題，搞清在什么條件下，要追求什么目標？2、這個要實現(xiàn)的目標是由一組變量決定的——決策變量。定義決策變量，每一個問題用一組決策變量〔x1,x2,x3…,xn〕來表示某一方案，每組決策變量的值就代表一個具體方案；3、用決策變量的線性函數(shù)來表示寫出所要追求的目標，我們稱之為目標函數(shù)。按問題的不同，可能要求這目標函數(shù)實現(xiàn)最大化或最小化。4、這些決策變量需要一定的限制和約束，這些約束條件可以用一組線性等式或線性不等式來表示。解：將一個實際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟：1．確定決策變量：x1=產(chǎn)品Ⅰ的產(chǎn)量x2=產(chǎn)品Ⅱ的產(chǎn)量2．確定目標函數(shù)：目標是使工廠獲得的利潤最大maxz=2x1+3x23．確定約束條件：x1+2x28〔設備的有效臺時的限制〕4x116〔原材料A的消耗限制〕4x2≤12〔原材料B的消耗限制〕4．變量取值限制：一般情況，決策變量取非負值x10,x20數(shù)學模型maxz=2x1+3x2s.t.x1+2x21204x1

504x2≤12x1,x20線性規(guī)劃數(shù)學模型三要素：決策變量、約束條件、目標函數(shù)

【例2】.簡化的環(huán)境保護問題

靠近某河流有兩個化工廠(見圖1-1)，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。第一化工廠每天排放污水2萬m3，第二化工廠每天排放污水1.4萬m3。污水從工廠1流到工廠2前會有20%自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應不大于0.2%。而工廠1和工廠2處理污水的本錢分別為1000元/萬m3和800元/萬m3。問兩工廠各應處理多少污水才能使處理污水的總費用最低？圖1-1解：將此實際問題轉(zhuǎn)化為線性規(guī)劃模型步驟如下：1.明確問題，確定決策變量

設工廠1和工廠2每天分別處理污水x1萬m3和x2萬m3MinZ=1000x1+800x2(2-x1)/〔500+2〕≤0.002

x2≤1.4〔非負值約束〕x1,x2≥02.確定約束條件：工廠1的排污口污水含量：3.確定目標函數(shù)：4.確定決策變量的約束：工廠2的排污口：其他約束：

x1≥1[1.4-x2+0.8(2-x1)]/〔500+2+200+1.4〕≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002

x1≤20.8x1+x2

≥16(2-x1)/500≤0.002數(shù)學模型其他典型問題：合理下料問題運輸問題生產(chǎn)的組織與方案問題投資證券組合問題分派問題生產(chǎn)工藝優(yōu)化問題設置決策變量，它們表達解決問題的方案。小結(jié)1：建模的根本步驟確定目標函數(shù)，它是決策變量的函數(shù)。確定決策變量的取值范圍，給出優(yōu)化方向。確定約束條件，它們是含有決策變量的不等式或等式。小結(jié)2：數(shù)學模型的共同特征〔1〕每一個線性規(guī)劃問題都用一組決策變量,每組決策變量的值就代表一個具體方案。一般這些變量取值是非負且連續(xù)的；(2)要有各種資源和使用有關資源的技術數(shù)據(jù)創(chuàng)造新價值的數(shù)據(jù)；資源的數(shù)據(jù):(3)存在可以量化的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示;(4)要有一個到達目標的要求，它可用決策變量的線性函數(shù)(稱為目標函數(shù))來表示。按問題的不同，要求目標函數(shù)實現(xiàn)最大化或最小化。具有上述特征的數(shù)學模型稱為線性規(guī)劃模型一類是在有限的人力、物力、財力的條件下，研究如何合理地方案和安排，使得某一目標到達最大〔產(chǎn)量最大、利潤最大〕。另一類是任務確定后，如何方案和安排，用最少的人力、物力和財力，去實現(xiàn)該任務，使得本錢最小。線性規(guī)劃研究對象：決策變量目標函數(shù)約束條件線性規(guī)劃的一般模型形式

目標函數(shù)約束條件Subjectto資源系數(shù)(右邊項)價值系數(shù)工藝系數(shù)目標函數(shù)價值系數(shù)工藝系數(shù)資源系數(shù)決策變量它們的對應關系可用表格表示：1.2二維線性規(guī)劃問題的圖解法對于只有兩個決策變量的LP，可以在平面直角坐標系上作圖表示其有關概念，并進行求解。因存在，所以必須在直角坐標系的第1象限內(nèi)作圖，求解。定義1在LP問題中，凡滿足約束條件的解稱為LP問題的可行解，所有可行解的集合稱為可行解集〔或可行域〕。定義2使目標函數(shù)取得最優(yōu)值的可行解，稱為最優(yōu)解。相應的目標函數(shù)值稱為最優(yōu)值.圖解法的步驟：建立平面直角坐標系根據(jù)約束條件找出可行域圖示目標函數(shù)確定最優(yōu)解【例1】x2=-(2/3)x1+z/3目標函數(shù)等值線定義3當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線〞。

maxz=2x1+3x2 s.t. x1+2x2≤8 4x1≤16 4x2≤12x1≥0,x2≥0最優(yōu)解840x1x2最優(yōu)解為x=(4,2)T最優(yōu)值z=1443Q4〔3，0〕Q2〔4，2〕Q1〔4，0〕可行域目標函數(shù)等值線:x2=-(2/3)x1+z/3目標函數(shù)Z增加最快的方向就是函數(shù)的梯度方向Q3〔2，3〕LP圖解法的根本步驟：1、在平面上建立直角坐標系；2、圖示約束條件，確定可行域和頂點坐標；3、圖示目標函數(shù)〔等值線〕和其移動方向；4、尋找最優(yōu)解。64-860x1x2maxz=x1+3x2 s.t. x1+x2≤6-x1+2x2≤8 x1≥0,x2≥0可行域目標函數(shù)等值線x2=-x1/3+z/3最優(yōu)解最優(yōu)解必落在可行域的頂點上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/5x1+z/25x2x1最優(yōu)解：

x1=30x2=10最優(yōu)值：zmax=700B點是使z到達最大的唯一可行點LP問題從解的角度可有兩種分類方式：⑴有可行解⑵無可行解有唯一最優(yōu)解b.有無窮優(yōu)多最解線性規(guī)劃問題解的幾種情況：

唯一最優(yōu)解無窮多最優(yōu)解無界解無可行解〔1〕有最優(yōu)解〔2〕無最優(yōu)解第一種分類第二種分類有最優(yōu)解無最優(yōu)解〔無界解〕【例1】

maxz=2x1+3x2 s.t. x1+2x2≤8 4x1≤16 4x2≤12x1≥0,x2≥0目標函數(shù)等值線最優(yōu)解8x1x2403423可行域無窮多最優(yōu)解(多重最優(yōu)解)

4結(jié)論：LP假設有最優(yōu)解，必在可行域的某個頂點上取到；假設在兩個頂點上同時取到，那么這兩點的連線上任一點都是最優(yōu)解。例：

max z=x1+x2 s.t. -2x1+x2≤4 x1-x2≤2 x1≥0,x2≥0目標函數(shù)等值線4x1x202無界解即可行域的范圍延伸到無窮遠，目標函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件。

無可行解增加的約束條件當存在矛盾的約束條件時，為無可行域。在例1的數(shù)學模型中增加一個約束條件:那么可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解唯一最優(yōu)解無窮多最優(yōu)解無界解無可行解小結(jié):線性規(guī)劃的可行域和最優(yōu)解的情況可行域為封閉的有界區(qū)域有唯一的最優(yōu)解有無窮多個最優(yōu)解可行域為非封閉的無界區(qū)域有唯一的最優(yōu)解有無窮多個最優(yōu)解目標函數(shù)無界可行域為空集沒有可行解，原問題無最優(yōu)解1、可行域為封閉的有界區(qū)域

唯一最優(yōu)解

無窮多個最優(yōu)解

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

唯一最優(yōu)解

無窮多個最優(yōu)解

無界解3、可行域為空集

無可行解兩個變量的LP問題的解的啟示：(1)可行域非空時，它是有界或無界凸多邊形〔凸集〕，頂點個數(shù)只有有限個。(4)假設最優(yōu)解存在，那么最優(yōu)解或最優(yōu)解之一一定是可行域的凸集的某個頂點。(5)假設在兩個頂點上同時取到最優(yōu)解，那么這兩點的連線上任一點都是最優(yōu)解(2)求解LP問題時，解的情況有：唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解。(3)假設可行域非空且有界那么必有最優(yōu)解，假設可行域無界，那么可能有最優(yōu)解，也可能無最優(yōu)解。求解線性規(guī)劃問題最優(yōu)解的方法：確定可行域=凸集(凸多邊形)確定可行域頂點=求基可行解尋找最優(yōu)解，如果最優(yōu)解存在，那么必在可行域的某一頂點=在基可行解中尋找由圖解法得到的結(jié)論：圖解法優(yōu)點：直觀、易掌握。有助于了解解的結(jié)構(gòu)。圖解法缺點：只能解決低維問題，對高維無能為力。1.3線性規(guī)劃問題的標準型式

一般式

矩陣式

向量式

化標準形式其中bi0(i=1,2,…,m)一般標準式：目標函數(shù)約束條件其中bi0(i=1,2,…,m)向量式：矩陣式：化標準式：

2.約束條件

3.變量

1.目標函數(shù)4.右端項系數(shù)(1)目標函數(shù)假設目標函數(shù)是求最小值，即minz=CX。因為求minz等價于求max(-z)，故令z’=-z，于是得到maxz′=-CX。這就同標準型的目標函數(shù)的形式一致了?；瘶藴适剑毫頩'=-ZxoZZ’=-ZminZ=2X1+5X2+6X3+8X4maxZ'=-2X1-5X2-6X3-8X4(2)約束條件假設約束方程為不等式，那么有兩種情況：一種是約束方程為“≤〞不等式，那么可在“≤〞不等式的左端參加非負松弛變量，把原“≤〞不等式變?yōu)榈仁剑涣硪环N是約束方程為“≥〞不等式，那么可在“≥〞不等式的左端減去非負剩余變量(也可稱松弛變量)，把不等式約束條件變?yōu)榈仁郊s束條件。下面舉例說明:例：maxZ=2x1+x2+0·X3+0·X4+0·X5

5x2

156x1+2x2

24

x1+x2

5

xi

0+X3=15+X4

=24+X5

=5松弛變量例：minZ=2x1+5x2+6x3+8x4

4x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)-X5=12-X6=14-X7=8剩余變量

7〕+0X5+0X6+0X7例3：將例1的數(shù)學模型化為標準型。例1的數(shù)學模型,加松馳變量后例：令X1=X1'-X1"(3)變量其中假設xk為自由變量，即xk可為任意實數(shù)，,可令

設xk沒有非負約束，假設xk≤0，可令xk，=-xk，那么xk’≥0；3X1+2X28X1-4X214X203X1'-3X1"+2X28X1'

-X1"-4X2

14X1',X1",X20處理的步驟：例4：將下述線性規(guī)劃問題化為標準型(1)令x4－x5＝x3，其中x4，x5≥0；(2)在第一個約束不等式≤號的左端參加松弛變量x6；(3)在第二個約束不等式≥號的左端減去剩余變量x7；(4)令z′=-z，把求minz改為求maxz′，即可得到該問題的標準型標準式〔4〕右端項系數(shù)右端項bi<0時，只需將等式兩端同乘〔-1〕那么右端項必大于零例：將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

1.4線性規(guī)劃問題的解的概念1.可行解、可行解集〔可行域〕最優(yōu)解、最優(yōu)值2.基、基變量、非基變量3.根本解，根本可行解4.可行基、最優(yōu)基1.可行解，可行域，最優(yōu)解滿足約束條件(1-5)，(1-6)式的解X=(x1,x2，…，xn)T，稱為線性規(guī)劃問題的可行解；其中使目標函數(shù)到達最大值的可行解稱為最優(yōu)解最大的目標函數(shù)值稱為最優(yōu)值；全部可行解的集合稱為可行域。對于標準的LP來說滿足這兩個條件的x是可行解或者可行點三者皆滿足是最優(yōu)解2.基，基向量，基變量，非基變量設A是約束方程組m×n維的系數(shù)矩陣，其秩為m，B是矩陣A中m×m階非奇異子矩陣〔B的行列式│B│≠0〕，那么稱B是線性規(guī)劃問題的一個基陣或基。此標準型最多有個基〔1〕基maxz=2x1+3x2+0x3+0x4+0x5

x1+2x2+x3=8

4x1+x4=16

4x2+x5=12

x1,x2≥0LP的基有：B1，B2，B3B4不是LP的基

100010001B1=系數(shù)矩陣:121004001004001A=

121400040B2=120401040B3=

210000401B4=〔2〕基向量，基變量，非基向量〔a)稱pi(i=1,2,…,m)為基向量，它們是一組線性無關的向量組；(b)對應的向量xi(i=1,2,…,m)為基變量；(d)對應的變量xj(j=m+1,…,n)為非基變量，非基變量也稱為自由變量或獨立變量，可自由取值。(c)其他向量pj(j=m+1,…,n)為非基向量，有n-m個，上述基B中〔│B│≠0〕2.基，基向量，基變量，非基向量基變量在有n個變量、m個約束方程的標準型線性規(guī)劃問題中，假設取其中的m個變量，且這些變量在約束方程中對應的m個系數(shù)列向量是線性無關的，那么它們組成一組基變量。確定了一組基變量后，其它n-m個變量稱為非基變量。約束方程可改寫為：

X1＋X2＋…＋Xm＝－Xm＋1－…－Xn用向量的形式表示為：

1-7B1中P3=〔1，0，0〕T，P4=〔0，1，0〕TP5=〔0，0，1〕T是基向量對應基變量為：

x3，x4，x5非基變量為：

x1，x2=〔P3，P4，P5〕系數(shù)矩陣:121004001004001A=

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

x1+2x2+x3=8

4x1+x4=16

4x2+x5=12

x1,x2≥0令方程組〔1-5)的基是B，設XB是對應于這個基B的基變量，記XB=〔X1，X2，…，Xm〕T,假設令上式的非基變量Xm＋1＝Xm＋2＝…＝Xn＝0，約束方程變成m元一次方程，利用=BjB│B│≠0X=〔X1，X2，…，Xm，0，…，0〕T，稱X為基解。n-m該基解所得非零分量的個數(shù)不大于方程的個數(shù)m3.基解,基可行解

(1)基解可以求出一個解：滿足非負約束條件(1-6)的基解。稱為基可行解。(2)根本可行解一個基可行解的非零分量個數(shù)也不超過m個，并且都是非負的。一個基解的非零分量個數(shù)不超過m個，其分量可以有負的；基可行解和基解的數(shù)目最多是個。一般基可行解的數(shù)目要小于基解的數(shù)目。4.可行基對應于基可行解的基，稱為可行基。當基可行解為最優(yōu)解時,對應的基稱最優(yōu)基?；尚薪獾姆橇惴至總€數(shù)<m時，此時的基可行解稱為退化解。關于標準型解的假設干根本概念小結(jié)：可行解與非可行解滿足約束條件和非負條件的解X稱為可行解，滿足約束條件但不滿足非負條件的解X稱為非可行解?；饬罘腔兞縓N=0，求得基變量XB,那么(XB,XN)稱為基解，其中XB=B1b,XN=0。(XB,XN)是基解的必要條件為XB的非零分量的個數(shù)m。基可行解基解中,XB的非零分量都0時，稱為基可行解，否那么為基非可行解。基可行解的非零分量個數(shù)<m時，稱為退化解?？尚薪獠豢尚薪饣饣尚薪鉂M足全部約束條件的解，對應可行域內(nèi)的所有點只滿足約束方程，不滿足非負條件的解，對應所有約束直線的交點滿足全部約束條件，且有n-m個分量為0的解，對應可行域的頂點以上提到的幾種解的概念，它們之間的關系可用下面圖說明。是根本解不是可行解可行解例如對于LP：根本可行解可行基基可行解、根底解和根底可行解舉例反之，如果有一個基變量也取零值，那么稱它是退化解,即基解中的非零分量的個數(shù)小于m個時，那么該基解是退化解。在以下討論時，假設不出現(xiàn)退化的情況。以上給出了線性規(guī)劃問題的解的概念和定義，它們將有助于用來分析線性規(guī)劃問題的求解過程。在LP的一個基可行解中，如果它的所有的基變量都取正值，那么稱它是非退化的解；小結(jié)1.線性規(guī)劃問題的模型特征2.通過圖解法了解如何求解線性規(guī)劃問題3.為求解高維線性規(guī)劃問題，必須建立的概念練習1：X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50121003201002001P1P2P3P4P5A=X1X2X3X4X5X=b=306024B=(P3P4P5)=I

是滿秩子矩