線性規劃和單純形法第1頁，課件共77頁，創作于2023年2月目錄線性規劃實例與模型線性規劃的圖解法單純形法原理改進單純形法應用第2頁，課件共77頁，創作于2023年2月目錄線性規劃實例與模型第3頁，課件共77頁，創作于2023年2月實用舉例

某公司通過市場調研，決定生產高中檔新型拉桿箱。某分銷商決定買進該公司3個月內的全部產品。拉桿箱生產需經過原材料剪裁、縫合、定型、檢驗和包裝4過程。通過分析生產過程，得出：生產中檔拉桿箱需要用7/10小時剪裁、5/10小時縫合、1小時定型、1/10小時檢驗包裝；生產高檔拉桿箱則需用1小時剪裁、5/6小時縫合、2/3小時定型、1/4小時檢驗包裝。由于公司生產能力有限，3月內各部的最大生產時間為剪裁部630小時、縫合部600小時、定型部708小時、檢驗包裝部135小時。通過市場調研部和會計部的調查核算得出結論：生產中檔拉桿箱的利潤是10元，高檔拉桿箱的利潤是9元。公司應各生產多少中檔和高檔拉桿箱才能使公司利潤最大？第4頁，課件共77頁，創作于2023年2月實用舉例某公司通過市場調研，決定生產高中檔新型拉桿箱。某分銷商決定買進該公司3個月內的全部產品。拉桿箱生產需經過原材料剪裁、縫合、定型、檢驗和包裝4過程。通過分析生產過程，得出：生產中檔拉桿箱需要用7/10小時剪裁、5/10小時縫合、1小時定型、1/10小時檢驗包裝；生產高檔拉桿箱則需用1小時剪裁、5/6小時縫合、2/3小時定型、1/4小時檢驗包裝。由于公司生產能力有限，3月內各部的最大生產時間為剪裁部630小時、縫合部600小時、定型部708小時、檢驗包裝部135小時。通過市場調研部和會計部的調查核算得出結論：生產中檔拉桿箱的利潤是10元，高檔拉桿箱的利潤是9元。公司應各生產多少中檔和高檔拉桿箱才能使公司利潤最大？可以通過線性規劃求解！第5頁，課件共77頁，創作于2023年2月線性規劃模型的建立

設生產中、高檔拉桿箱數量分別為：稱為決策變量。目標函數約束條件第6頁，課件共77頁，創作于2023年2月一般線性規劃模型Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1(

0) a21x1+a22x2+…+a2nxn=b2

(

0) :am1x1+am2x2+…+amnxn=bm(

0)

x1,x2,…,xn

0s.t.

為約束限制（Subjectto）的縮寫(LP)x1..xnb1..bma11…a1n…………am1…amnx=b= A=c1..cnc=其中c=(c1,c2,…,cn)，稱為價值系數向量；第7頁，課件共77頁，創作于2023年2月稱為資源限制向量

X=(x1,x2,…,xn)T

稱為決策變量向量稱為技術系數矩陣(也稱消耗系數矩陣)一般線性規劃模型第8頁，課件共77頁，創作于2023年2月線性規劃模型的標準形式MaxZ=c1x1+c2x2+…+cnxnSubjectto(s.t.) a11x1+a12x2+…+a1nxn

=

b1

a21x1+a22x2+…+a2nxn

=

b2

…… am1x1+am2x2+…+amnxn=

bm

x1

0,x2

0,…,xn

0為了討論方便，把最大化、等式約束型的線性規劃稱為線性規劃的標準型，即第9頁，課件共77頁，創作于2023年2月標準化原問題標準化方法目標函數Maxf(x)Maxf(x)Minf(x)Max–f(x)約束條件引入松弛變量和人工變量引入松弛變量,不變變量不變對某個對某個是任意的

第10頁，課件共77頁，創作于2023年2月線性規劃模型的標準化例:將如下線性規劃模型標準化：minz=x1+5x2-8x3-x4s.t.2x1-3x2+x3+x4≤20

x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50

x1,x3,x4≥0，x2取值無約束。

maxz1=-x1-5x2+8x3+x4s.t.2x1-3x2+x3+x4≤20

x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50

x1,x3,x4≥0，x2取值無約束。

目標優化標準化第11頁，課件共77頁，創作于2023年2月線性規劃模型的標準化Maxz2=-x1-5y2+5y3+8x3+x4s.t.2x1-3y2+3y3+x3+x4≤20-x1-2y2+2y3-3x3+x4≤

-30-2y2+2y3-2x3-3x4≤

50

x1,x3,x4,y2,y3≥0

決策變量的標準化:y2-y3=x2maxz1=-x1-5x2+8x3+x4s.t.2x1-3x2+x3+x4≤20

x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50

x1,x3,x4≥0，x2取值無約束

第12頁，課件共77頁，創作于2023年2月線性規劃模型的標準化Maxz2=-x1-5y2+5y3+8x3+x4

s.t.2x1-3y2+3y3+x3+x4+x5=20-x1-2y2+2y3-3x3+x4+x6=

-30-2y2+2y3-2x3-3x4+x7=50

x1,x3,x4,x5,x6,x7,y2,y3≥0約束關系標準化Maxz2=-x1-5y2+5y3+8x3+x4

s.t.2x1-3y2+3y3+x3+x4≤20-x1-2y2+2y3-3x3+x4≤

-30-2y2+2y3-2x3-3x4≤

50

x1,x3,x4,y2,y3≥0

第13頁，課件共77頁，創作于2023年2月可行解:滿足所有約束條件的解x=（x1，x2，….，xn），所有可行解的集合稱為可行域。基：設A是約束方程組的m×n階系數矩陣，秩為m，是A中階非奇異子矩陣（即），則稱是線性規劃問題的一個基矩陣，簡稱基。B中的列向量稱為基向量，與基向量對應的變量x稱為基變量，其它變量稱為非基變量。

基本解：令非基變量值為0，由Ax=b可求出一個解，這個解x稱為基本解。基本可行解：滿足非負條件的基本解稱為基本可行解。最優解：使目標函數達到最優值的可行解稱為最優解。線性規劃的解

第14頁，課件共77頁，創作于2023年2月可行解、基本解、基本可行解的關系可行解基本解基本可行解第15頁，課件共77頁，創作于2023年2月目錄線性規劃實例與模型線性規劃的圖解法與基本性質第16頁，課件共77頁，創作于2023年2月線性規劃的圖解法當只有兩個決策變量時，可用圖解法求解！例：用圖解法求解以下線形規劃問題。maxz=4x1+3x2

s.t.x1≤62x2≤82x1+3x2≤18x1≥0，x2≥0x1

x2

L3：2x1+3x2=18可行域L1：x1=6L2：x2=4最優解B4x1+3x2第17頁，課件共77頁，創作于2023年2月解的特殊情況——多個最優解第18頁，課件共77頁，創作于2023年2月解的特殊情況——無可行解第19頁，課件共77頁，創作于2023年2月解的特殊情況——無界解第20頁，課件共77頁，創作于2023年2月線性規劃的基本性質

X可行域內部的點可行解?是最優解?不若線性規劃有最

優解，則最優解必在可行域的頂點上達到。第21頁，課件共77頁，創作于2023年2月凸集的概念

凸集是線性規劃中一個很重要的概念，凸集的一般定義為：如果在集合C中任意取兩個點x1，x2，其連線上的所有點也都在集合C中，則稱集合C為凸集合。用數學解析式表達為：對任意，均有，則稱C是凸集合。非凸集非凸集凸集第22頁，課件共77頁，創作于2023年2月線性規劃的基本性質定理2.1：線性規劃的可行域：是凸集（凸多面體）。

引理2.1：線性規劃的可行解為基本可行解的充分必要條件是x的正分量所對應的系數列向量是線性無關的，即每個正分量都是一個基變量。定理2.2：線性規劃問題的基本可行解x對應于可行域的頂點

定理2.3：若線性規劃有最優解，則最優解必在可行域的頂點上達到。第23頁，課件共77頁，創作于2023年2月目錄線性規劃實例與模型線性規劃的圖解法單純形法原理第24頁，課件共77頁，創作于2023年2月一、初始基本可行解的確定考慮如下形式的線性規劃問題maxz=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21x1+a22x2+……+a2nxn≤b2(2.17）

……….am1x1+am2x2+…+amnxn≤bmx1，x2，….，xn≥0（2.18）對每個不等式約束引入一個非負松弛變量，得標準形式：maxz=c1x1+c2x2+…..+cnxns.t.a11x1+……+a1nxn+xn+1=b1a21x1+……+a2nxn+xn+2=b2（2.19）

……………..am1x1+……+amnxn+xn+m=bm

x1，x2，….，xn，xn+1，…，xn+m≥0第25頁，課件共77頁，創作于2023年2月是線性規劃(2.19)的一個可行基。令

得由此得到一個初始基本可行解為第26頁，課件共77頁，創作于2023年2月二、最優性檢驗

定理2.4：在最大化問題中，對于某個基本可行解，如果所有的，則這個基本可行解是最優解。在最小化問題中，對于某個基本可行解，如果所有的，則這個基本可行解是最優解。第27頁，課件共77頁，創作于2023年2月單純形法求解步驟將所給問題化為標準形找出一個初始可行基,建立初始單純形表檢查所有檢驗數(若全為非負,則已得到最優解,計算停止.否則繼續下一步)考察是否無解(若是,計算停止,否則繼續下一步)確定入基變量,出基變量對初始單純形表進行單純形變換第28頁，課件共77頁，創作于2023年2月單純形方法的一般步驟確定一個初始可行角點根據某種法則進行角點的最優性判斷不是最優角點是最優角點考察與當前角點相鄰的“更好”的一個角點，并置為當前角點。根據某種法則進行LP的無界或不可行判斷無界或不可行還不能做出判斷求解結束第29頁，課件共77頁，創作于2023年2月單純形法舉例解：引進松馳變量x3,x4，化為標準形得：第30頁，課件共77頁，創作于2023年2月

4300CBXBb

x1

x2x3x4b/y00x3x42426

231024/2

320126/3

043004=4－（0×3+0×2）；3=3－（0×2+0×3）……

4300CBXBbx1x2x3x4b/y04x3x120/326/305/31-2/312/301/3

-104/301/30-4/3第31頁，課件共77頁，創作于2023年2月

4300CBXBbx1x2x3x434x2x146013/5-2/510-2/53/5

3600-1/5-6/5表中最后一行的所有檢驗數均為非正數，表明目標函數已達到最大值，上述表為最優表。從表中可得到最優解為X=（x1,x2,x3,x4）=（6，4，0，0），最優值為Z=36

4300CBXBbx1

x2x3x4b/y04x3x120/326/305/31-2/3412/301/313

-104/301/30-4/3第32頁，課件共77頁，創作于2023年2月單純形法的進一步討論人工變量法人工變量法： 前面討論了在標準型中系數矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。第33頁，課件共77頁，創作于2023年2月單純形法的進一步討論人工變量法例1.10用大M法解下列線性規劃解：首先將數學模型化為標準形式系數矩陣中不存在單位矩陣，無法建立初始單純形表。第34頁，課件共77頁，創作于2023年2月單純形法的進一步討論人工變量法故人為添加兩個單位向量，得到人工變量單純形法數學模型：其中：M是一個很大的抽象的數，不需要給出具體的數值，可以理解為它能大于給定的任何一個確定數值；再用前面介紹的單純形法求解該模型，計算結果見下表。

第35頁，課件共77頁，創作于2023年2月單純形法的進一步討論人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M0000x63-650-1013/5-Mx58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→第36頁，課件共77頁，創作于2023年2月單純形法的進一步討論人工變量法

解的判別：1）唯一最優解判別：最優表中所有非基變量的檢驗數非零,則線規劃具有唯一最優解。（檢驗數為負數或0）2）多重最優解判別：最優表中存在非基變量的檢驗數為零,則線則性規劃具有無窮多最優解（檢驗數為負數或0）。3）無界解判別：某個檢驗數>0且aik≤０（i=1，2,…,m）則線性規劃具有無界解。4）無可行解的判斷：當用大M單純形法計算得到最優解并且存在Ri>0時，則表明原線性規劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。第37頁，課件共77頁，創作于2023年2月大M法基本思想：在約束條件中增加人工變量，同時修改目標函數，對目標函數加上具有很大正系數M的懲罰項，為使人工變量不影響目標函數取值，在迭代過程中，應把人工變量從基變量中退出，使其成為非基變量。

其中，M是很大的正數，同時增加兩個人工變量。

不容易找到初始可行解第38頁，課件共77頁，創作于2023年2月找初始可行解11-300MMbi/yibx1X2x3x4x5x6x70X4111-21100011MX6321-40-1103/2MX71(1)0-2000111-3M1-M-3+6M0M00要求最后得到的基變量中不含人工變量X1進基，x7出基11-300MMbi/yibx1x2x3x4x5x6x7-3X340011/3-2/32/3-5/31X210100-11-211X191002/3-4/34/3-7/30001/31/3M-1/3M-2/3可以從表中移去，然后繼續求解經過幾次變換，得到基變量為x1，x2，x3第39頁，課件共77頁，創作于2023年2月兩階段法原理兩階段法的第一階段是用單純形法消去人工變量，即把人工變量都變為非基變量，求出原問題的一個基本可行解。如果第一階段求解結果表明問題有可行解時，進行第二階段，就是從得到的基本可行解出發，用單純形方法求原問題的最優解。第40頁，課件共77頁，創作于2023年2月5.2退化

LP問題

有退化最優解第41頁，課件共77頁，創作于2023年2月單純形法計算中用θ規則確定換出變量時，有時存在兩個以上相同的最小比值，這樣在下一次迭代中就有一個或幾個基變量等于零，這就出現退化解。

這時換出變量xl=0，迭代后目標函數值不變。這時不同基表示為同一頂點。有人構造了一個特例，當出現退化時，進行多次迭代，而基從B1,B2，…又返回到B1，即出現計算過程的循環，便永遠達不到最優解。第42頁，課件共77頁，創作于2023年2月兩階段法舉例例：第一階段：第二階段：用單純形法求得第一階段的解為：用單純形法求解規劃問題得最優解

目標函數的最優解是

第43頁，課件共77頁，創作于2023年2月ExcelSolver（規劃求解）

Excel采用了電子表格的形式，幫助管理者提高數據管理的能力，因而得以廣泛應用。Solver插件專門用于求解帶約束的最優化問題。Solver——“規劃求解”，可在Excel的工作表中根據對話框提示調用該項功能。第44頁，課件共77頁，創作于2023年2月

可能出現以下情況：①進行進基、出基變換后，雖然改變了基，但沒有改變基本可行解（極點），目標函數當然也不會改進。進行若干次基變換后，才脫離退化基本可行解（極點），進入其他基本可行解（極點）。這種情況會增加迭代次數，使單純形法收斂的速度減慢。②在特殊情況下，退化會出現基的循環，一旦出現這樣的情況，單純形迭代將永遠停留在同一極點上，因而無法求得最優解。3.單純形法第45頁，課件共77頁，創作于2023年2月

在單純形法求解線性規劃問題時，一旦出現這種因退化而導致的基的循環，單純形法就無法求得最優解，這是一般單純形法的一個缺陷。但是實際上，盡管退化的結構是經常遇到的，而循環現象在實際問題中出現得較少。盡管如此，人們還是對如何防止出現循環作了大量研究。1952年Charnes提出了“攝動法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”，3.單純形法第46頁，課件共77頁，創作于2023年2月

這些方法都比較復雜，同時也降低了迭代的速度。1976年，Bland提出了一個避免循環的新方法，其原則十分簡單。僅在選擇進基變量和出基變量時作了以下規定：①在選擇進基變量時，在所有j

>0的非基變量中選取下標最小的進基；②當有多個變量同時可作為出基變量時，選擇下標最小的那個變量出基。這樣就可以避免出現循環,當然，這樣可能使收斂速度降低。3.單純形法第47頁，課件共77頁，創作于2023年2月加載“規劃求解”如果在您的Excel中，沒有在“工具”菜單中發現“規劃求解”，請在下圖所示的界面中點擊“加載宏”。第48頁，課件共77頁，創作于2023年2月加載“規劃求解”點擊“加載宏”后，顯示界面如下：如果列表中沒有“規劃求解”，表明您還沒有安裝該插件。這時，您需要插入MicrosoftOffice安裝盤，選擇“添加安裝”后選擇該插件的安裝。第49頁，課件共77頁，創作于2023年2月第1步導入已知數據可采用‘復制粘貼’或‘直接輸入’的方式導入數據。第50頁，課件共77頁，創作于2023年2月第2步確定‘可變單元格’

可變單元格存放決策變量的取值，可變單元格數目等于決策變量個數圖中，規定B16、C16為可變單元格第51頁，課件共77頁，創作于2023年2月第3步確定‘目標單元格’

在目標單元格中，需要填入計算目標函數值的公式。第52頁，課件共77頁，創作于2023年2月第4步確定‘約束單元格’

在約束單元格中，需要填入計算約束函數值的公式。第53頁，課件共77頁，創作于2023年2月第5步調用‘規劃求解’模塊在上圖顯示的界面中，需要輸入目標單元格、可變單元格，添加約束條件，另外還可能需要進行選項設置。第54頁，課件共77頁，創作于2023年2月第6步填寫目標單元格和可變單元格第55頁，課件共77頁，創作于2023年2月第7步添加約束第56頁，課件共77頁，創作于2023年2月第8步“選項”設置選擇：采用線性模型，假定非負。如果求解過程在找到結果之前即達到最長運算時間或最大迭代次數，則會彈出“顯示中間結果”對話框。第57頁，課件共77頁，創作于2023年2月第9步保存求解結果第58頁，課件共77頁，創作于2023年2月顯示求解結果第59頁，課件共77頁，創作于2023年2月使用Excel求解例2.10第60頁，課件共77頁，創作于2023年2月第61頁，課件共77頁，創作于2023年2月

合理利用線材問題：如何下料使用材最少。

配料問題：在原料供應量的限制下如何獲取最大利潤。

投資問題：從投資項目中選取方案，使投資回報最大。4.線性規劃應用建模

一、線性規劃---第62頁，課件共77頁，創作于2023年2月

產品生產計劃：合理利用人力、物力、財力等，使獲利最大。

勞動力安排：用最少的勞動力來滿足工作的需要。

運輸問題：如何制定調運方案，使總運費最小。4.線性規劃應用第63頁，課件共77頁，創作于2023年2月

數學規劃的建模有許多共同點，要遵循下列原則：(1)容易理解。建立的模型不但要求建模者理解，還應當讓有關人員理解。這樣便于考察實際問題與模型的關系，使得到的結論能夠更好地應用于解決實際問題。(2)容易查找模型中的錯誤。這個原則的目的顯然與(1)相關。常出現的錯誤有：書寫錯誤和公式錯誤。4.線性規劃應用第64頁，課件共77頁，創作于2023年2月

(3)容易求解。對線性規劃來說，容易求解問題主要是控制問題的規模，包括決策變量的個數和約束條件的個數。這條原則的實現往往會與(1)發生矛盾，在實現時需要對兩條原則進行統籌考慮。4.線性規劃應用第65頁，課件共77頁，創作于2023年2月

建立線性規劃模型的過程可以分為四個步驟：

(1)設立決策變量；(2)明確約束條件并用決策變量的線性等式或不等式表示；(3)用決策變量的線性函數表示目標，并確定是求極大（Max）還是極小（Min）；(4)根據決策變量的物理性質研究變量是否有非負性。4.線性規劃應用第66頁，課件共77頁，創作于2023年2月

例2.:明興公司生產甲、乙、丙三種產品，都需要經過鑄造、機加工和裝配三個車間。甲、乙兩種產品的鑄件可以外包協作，亦可以自行生產，但產品丙必須本廠鑄造才能保證質量。數據如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產品各生產多少件？甲、乙兩種產品的鑄造中，由本公司鑄造和由外包協作各應多少件？生產計劃的問題第67頁，課件共77頁，創作于2023年2月解：設x1,x2,x3

分別為三道工序都由本公司加工的甲、乙、丙三種產品的件數，x4,x5分別為由外協鑄造再由本公司機加工和裝配的甲、乙兩種產品的件數。

生產計劃的問題第68頁，課件共77頁，創作于2023年2月

求xi

的利潤:利潤=售價-各成本之和可得到xi（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。這樣我們建立如下數學模型：目標函數:Max15x1+10x2+7x3+13x4+9x5

約束條件：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0

生產計劃的問題第69頁，課件共77頁，創作于2023年2月

例2.:永久機械廠生產Ⅰ、Ⅱ、Ⅲ三種產品，均要經過A、B兩道工序加工。假設有兩種規格的設備A1、A2能完成A工序；有三種規格的設備B1、B2、B3能完成B工序。Ⅰ可在A、B的任何規格的設備上加工；Ⅱ可在任意規格的A設備上加工，但對B工序,只能在B1設備上加工；Ⅲ只能在A2與B2設備上加工；數據如下表。問：為使該廠獲得最大利潤，應如何制定產品加工方案？

生產計劃的問題第70頁，課件共77頁，創作于2023年2月解：設xijk表示第i種產品，在第j種工序上的第k種設備上加工的數量.

利潤=[（銷售單價-原料單價）×產品件數]之和-（每臺時的設備費用×設備實際使用的總臺時數）之和。

生產計劃的問題第71頁，課件共77頁，創作于2023年2月這樣我們建立如下的數學模型:Max

0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123

s.t

5x111+10x2