第一章線性規(guī)劃及單純形法課件

案例：確定潘得羅索工業(yè)公司的產(chǎn)品組合潘得羅索工業(yè)公司是一家墨西哥公司，截至在2019年的銷售，公司生產(chǎn)了全國膠合板產(chǎn)量的四分之一，與其他膠合板生產(chǎn)廠商一樣，潘得羅索工業(yè)公司的許多產(chǎn)品根據(jù)厚度和所用木材的質(zhì)量而有所不同。因為產(chǎn)品在一個競爭的環(huán)境中進(jìn)行銷售，產(chǎn)品的價格由市場決定，所以產(chǎn)品的價格每月都有很大的變化。結(jié)果導(dǎo)致每項產(chǎn)品對公司整體利潤的貢獻(xiàn)也有很大的變動。從1980年開始，潘得羅索工業(yè)公司管理部門每個月使用線性規(guī)劃指導(dǎo)下個月的產(chǎn)品組合決策。線性規(guī)劃的數(shù)學(xué)模型考慮了這一決策的所有相關(guān)限制條件，包括生產(chǎn)產(chǎn)品所需的有限的可得數(shù)量。然后對模型求解，找出可行并且最大可能利潤（largestpossibleprofit）的產(chǎn)品組合。采用線性規(guī)劃后，潘得羅索工業(yè)公司的成績是顯著的。改進(jìn)的產(chǎn)品組合使公司的總利潤增加了20%，線性規(guī)劃的其他貢獻(xiàn)包括更好的原材料利用，更好的資本投資，和更好的人員利用。7/22/20231§1一般線性規(guī)劃問題的數(shù)學(xué)模型1.規(guī)劃問題生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)。（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多、利潤最大）。7/22/20232§1一般線性規(guī)劃問題的數(shù)學(xué)模型[例1]如圖所示，用一塊邊長為a的正方形鐵皮做一個容器，如何截取x使鐵皮圍成的容器容積最大？

xa7/22/20233§1一般線性規(guī)劃問題的數(shù)學(xué)模型[例2]常山機器廠生產(chǎn)I、Ⅱ兩種產(chǎn)品。這兩種產(chǎn)品都要分別在A、B、C三種不同設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺時和利潤如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)總的利潤最大？設(shè)備產(chǎn)品ABC利潤（元）

I2402

Ⅱ2053有效臺時1216157/22/20234§1一般線性規(guī)劃問題的數(shù)學(xué)模型解：設(shè)x1、x2分別為I、Ⅱ兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤124x1≤165x2≤157/22/20235§1一般線性規(guī)劃問題的數(shù)學(xué)模型2.線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式；（3）決策變量為可控的連續(xù)變量。

怎樣辨別一個模型是線性規(guī)劃模型？(LinearProgramming——LP)7/22/20236§1一般線性規(guī)劃問題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：線性規(guī)劃數(shù)學(xué)模型的一般形式簡寫為：7/22/20237§1一般線性規(guī)劃問題的數(shù)學(xué)模型向量形式：其中：7/22/20238§1一般線性規(guī)劃問題的數(shù)學(xué)模型矩陣形式：其中：7/22/20239§1一般線性規(guī)劃問題的數(shù)學(xué)模型3.線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點：(1)目標(biāo)函數(shù)求最大值（有時求最小值）(2)約束條件都為等式方程(3)右端常數(shù)項bi都大于或等于零(4)決策變量xj為非負(fù)。7/22/202310§1一般線性規(guī)劃問題的數(shù)學(xué)模型如何化標(biāo)準(zhǔn)形式？目標(biāo)函數(shù)的轉(zhuǎn)換如果是求極小值即，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問題。也就是：令，可得到上式。即

若存在取值無約束的變量，可令其中：變量的變換7/22/202311§1一般線性規(guī)劃問題的數(shù)學(xué)模型約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量變量的變換可令，顯然7/22/202312§1一般線性規(guī)劃問題的數(shù)學(xué)模型[例3]將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式用替換，且解:（１）因為x3無符號要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以（2）因為x1≤0，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以7/22/202313§1一般線性規(guī)劃問題的數(shù)學(xué)模型(3)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(4)第二個約束條件是“≥”號，在“≥”左端減去剩余變量x5，x5≥0；(5)第3個約束方程右端常數(shù)項為-6，方程兩邊同乘以(-1),將右端常數(shù)項化為正數(shù)；(6)目標(biāo)函數(shù)是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當(dāng)z達(dá)到最小值時z′達(dá)到最大值，反之亦然;7/22/202314§1一般線性規(guī)劃問題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：7/22/202315§1一般線性規(guī)劃問題的數(shù)學(xué)模型4.線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標(biāo)函數(shù)(1)達(dá)到最大值。7/22/202316§1一般線性規(guī)劃問題的數(shù)學(xué)模型

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

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。

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

對應(yīng)的變量xj為基變量。除基變量以外的變量為非基變量。7/22/202317§1一般線性規(guī)劃問題的數(shù)學(xué)模型

基解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個數(shù)不大于方程數(shù)m，基解的總數(shù)不超過基可行解：滿足變量非負(fù)約束條件的基本解，簡稱基可行解。

可行基：對應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解7/22/202318§1一般線性規(guī)劃問題的數(shù)學(xué)模型[例4]列出線性規(guī)劃問題的全部基、基解、基可行解、最優(yōu)解。解:約束方程的系數(shù)矩陣為3×5矩陣

r(A)=3，3階子矩陣有10個，其中基矩陣只有8個，即基基解可行目標(biāo)x1x2x3x4x5P1P2P343-200否17P1P2P433040是15*P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是07/22/202319§1一般線性規(guī)劃問題的數(shù)學(xué)模型 學(xué)習(xí)要點： 1.掌握有關(guān)線性規(guī)劃的基本概念（目標(biāo)函數(shù)、約束條件、線性規(guī)劃、可行解、可行域、最優(yōu)解、最優(yōu)值、基、基解、基可行解、可行基） 2.能將線性規(guī)劃轉(zhuǎn)化為指定的標(biāo)準(zhǔn)型。

作業(yè)：（P47）1.2，1.6（化為標(biāo)準(zhǔn)型）7/22/202320§2圖解法線性規(guī)劃問題的求解方法一般有兩種方法圖解法單純形法兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡單的情況——只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。7/22/202321§2圖解法例用圖解法求解線性規(guī)劃問題7/22/202322§2圖解法maxZ=2X1+3X2x2x1o2X1+2X2=12(≤)4X1=16(≤)5X2=15(≤)D可行域此點是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值maxZ=15（3，3）6=2X1+3X2

maxZ15=2X1+3X2

Lo：0=2X1+3X2

minZ7/22/202323§2圖解法（1）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

藍(lán)色線段上的所有點都是最優(yōu)解。這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏?/22/202324§2圖解法（2）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)解7/22/202325§2圖解法246x1x2246無界解(無最優(yōu)解)（3）maxZ=x1+2x2x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ7/22/202326x1x2O10203040102030405050無可行解(即無最優(yōu)解)（4）maxZ=3x1+4x27/22/202327AAB唯一解無窮多解無界解無可行解7/22/202328思考題1.LP模型的可行域是否一定存在？2.圖解中如何去判斷模型有唯一解、無窮多解、無界解和無可行解？3.LP模型的可行域的頂點與什么解具有對應(yīng)關(guān)系？4.你認(rèn)為把所有的頂點都找出來，再通過比較目標(biāo)函數(shù)值大小的方式找出最優(yōu)解，是否是最好的算法？為什么？7/22/202329§2圖解法 學(xué)習(xí)要點： 1.通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解） 2.作圖的關(guān)鍵有三點： (1)可行解區(qū)域要畫正確 (2)目標(biāo)函數(shù)增加的方向不能畫錯 (3)目標(biāo)函數(shù)的直線怎樣平行移動作業(yè)：（P47）1.17/22/202330§3單純形法基本原理凸集：如果集合C中任意兩個點X1、X2，其連線上的所有點也都是集合C中的點，稱C為凸集。凸集凸集不是凸集頂點7/22/202331§3單純形法基本原理定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應(yīng)可行域(凸集)的頂點。定理3：若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（或在某個頂點取得）7/22/202332§4單純形法的計算步驟單純形法的思路找出一個初始基本可行解是否最優(yōu)轉(zhuǎn)移到另一個基本可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束7/22/202333§4單純形法的計算步驟單純形表7/22/202334§4單純形法的計算步驟[例5]用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4、x5，則標(biāo)準(zhǔn)型為:7/22/202335§4單純形法的計算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj23000θicB基bx1x2x3x4x50x312221000x416400100x5150500123000檢驗數(shù)7/22/202336§4單純形法的計算步驟3）進(jìn)行最優(yōu)性檢驗如果表中所有檢驗數(shù)，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。4）從一個基可行解轉(zhuǎn)換到另一個目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對應(yīng)的變量xj作為換入變量，當(dāng)有一個以上檢驗數(shù)大于0時，一般選擇最大的一個檢驗數(shù)，即：，其對應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計算并選擇θ

，選最小的θ對應(yīng)基變量作為換出變量。 7/22/202337§4單純形法的計算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。5）重復(fù)3）、4）步直到計算結(jié)束為止。

7/22/202338cj23000θicB基變量bx1x2x3x4x50x3122210060x41640010—0x51505001323000換入列bi/ai2，ai2>0換出行將5化為1,乘以1/5[]x2x3x43003 0100 1/56 2010 -2/516 4001 0200 0-3/534—[]x12x40x233 101/20 -1/54 00-21 4/5

3 0100 1/500-1 0-3/57/22/202339§4單純形法的計算步驟用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計算。7/22/202340§4單純形法的計算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x22[]1/3150120753017131/30-90-22560[]x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/37/22/202341§4單純形法的計算步驟 學(xué)習(xí)要點： 1.線性規(guī)劃解的概念以及3個基本定理 2.熟練掌握單純形法的解題思路及求解步驟作業(yè)：（P47）1.37/22/202342§5單純形法的進(jìn)一步討論－人工變量法人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。7/22/202343§5單純形法的進(jìn)一步討論－人工變量法例6用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。7/22/202344§5單純形法的進(jìn)一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。

7/22/202345cj-30100-M-MCBXBbx1x2x3x4x5x6x7θi0x4411110004-Mx61-21-10-1101-Mx7903100013-3-2M4M↑10-M000x4330211-1010x21-21-10-110—-Mx7660403-3116M-304M+103M-4M00x400001-1/21/2-1/2—0x23011/30001/39-3x11102/301/2-1/21/63/200303/2-M-3/21/2-M0x400001-1/21/2-1/20x21-2100-1101x33/23/20103/4-3/41/4-9/2000-3/43/4-M-1/4-M→→→7/22/202346§5單純形法的進(jìn)一步討論－解的判別

解的判別（Max型）：

：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解。2）無窮多最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或多重最優(yōu)解）。3）無界解判別：某個σk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大M單純形法計算得到最優(yōu)解并且存在人工變量在基，且不為0時，表明原問題無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。

7/22/202347檢驗數(shù)反號，即-令負(fù)檢驗數(shù)中最小的對應(yīng)的變量進(jìn)基；-當(dāng)檢驗數(shù)均大于等于零時為最優(yōu)。或者轉(zhuǎn)換為Max型，再求解Min型單純形表與Max型的區(qū)別僅在于：解的判別（Min型）：

§5單純形法的進(jìn)一步討論－解的判別7/22/202348§5單純形法的進(jìn)一步討論 學(xué)習(xí)要點： 1.掌握人工變量法—大M法 2.能準(zhǔn)確根據(jù)單純形表中的檢驗數(shù)判別所解問題的解的類型作業(yè)：(P48)1.6（列初始單純形表）

，1.7（a）(大M法)7/22/202349§5單純形法的進(jìn)一步討論

—單純形法計算的向量矩陣描述非基變量基變量XBXNXs0XsbBNIcj-zjCBCN0……基變量非基變量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1矩陣形式表述的線性規(guī)劃標(biāo)準(zhǔn)型：單純性表迭代過程：左乘B-17/22/202350§5單純形法的進(jìn)一步討論

—單純形法計算的向量矩陣描述cj23000cB基bx1x2x3x4x50x312221000x416400100x5150500123000[例10]用單純形法求例5線性規(guī)劃問題的初始單純形表和最終單純形表如下所示：cj23000cB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/500-10-1/57/22/202351§5單純形法的進(jìn)一步討論

—單純形法計算的向量矩陣描述則7/22/202352§5單純形法的進(jìn)一步討論 學(xué)習(xí)要點：

1.能根據(jù)初始和最終單純形表找出B-1，會利用公式計算檢驗數(shù)。作業(yè)：1.8，1.127/22/202353§7應(yīng)用舉例1.混合配料問題[例13]某糖果廠用原料A、B、C加工成不同牌號的糖果甲、乙、丙。有關(guān)參數(shù)如下表所示，問該廠每月生產(chǎn)這三種各多少千克，使該廠獲利最大。試建立該問題的線性規(guī)劃模型。甲乙丙原料成本（元/kg）每月限制用量（kg）A≥60%≥30%22000B1.52500C≤20%≤50%≤60%11200加工費（元/kg）0.50.40.3售價（元/kg）3.42.852.25其中，百分?jǐn)?shù)表示各糖果中各原料的含量7/22/202354§7應(yīng)用舉例解：設(shè)xij表示生產(chǎn)第j種糖果使用的第i種原料的質(zhì)量，則MaxZ=（3.4-0.5）(x11+x21+x31)+（2.85-0.4）(x12+x22+x32)+（2.25-0.3）（x13+x23+x33）-2（x11+x12+x13）-1.5(x21+x22+x23)-1(x31+x32+x33)s.t.x11+x12+x13≤2000x21+x22+x23≤2500