線性規(guī)劃(單純形法)

1、Page 1Page 2單純形表單純形表jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 0 ijijjacc j 0 kjkjiiaab其其中中：Page 3例例1.8 用單純形法求下列線性規(guī)劃的最優(yōu)解用單純形法求下列線性規(guī)劃的最優(yōu)解 0,1241648232max21212121xxxxxxxxZ解：解：1）將問題化為標準型，加入松馳變量將問題化為標準型，加入松馳變量x3、x4、 x5則標準則標準型為型為: 0,1241648200043max54321524132154321xxxxxxxxxxxxxx

2、xxxZPage 42）求出線性規(guī)劃的初始基可行解，）求出線性規(guī)劃的初始基可行解，列出初始單純形表。列出初始單純形表。11311421531()2(0 1 0 40 0)2cc ac ac a cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204001323000Z=0檢驗數(shù)檢驗數(shù)j 3) 400020(3)(32522412322 acacacc 2) 004010(2)(31521411311 acacacc Page 53）進行最優(yōu)性檢驗）進行最優(yōu)性檢驗如果表中所有檢驗數(shù)如果表中所有檢驗數(shù) ，則表中的基可行解就是問題，則表中的基可行

3、解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。的最優(yōu)解，計算停止。否則繼續(xù)下一步。0 j4）從一個基可行解轉(zhuǎn)換到另一個目標值更大的基可行解，）從一個基可行解轉(zhuǎn)換到另一個目標值更大的基可行解，列出新的單純形表列出新的單純形表確定換入基的變量。選擇確定換入基的變量。選擇 ，對應的變量，對應的變量xj作為換入變作為換入變量，當有一個以上檢驗數(shù)大于量，當有一個以上檢驗數(shù)大于0時，一般選擇最大的一個時，一般選擇最大的一個檢驗數(shù)，即：檢驗數(shù)，即： ，其對應的，其對應的xk作為換入作為換入變量。變量。確定換出變量。根據(jù)下式計算并選擇確定換出變量。根據(jù)下式計算并選擇 ，選最小的選最小的對應基對應基變量作為換出

4、變量。變量作為換出變量。0 j0|max jjk 0minikikiLaabPage 6用換入變量用換入變量xk替換基變量中的換出變量，得到一個新的基。替換基變量中的換出變量，得到一個新的基。對應新的基可以找出一個新的基可行解，并相應地可以畫出對應新的基可以找出一個新的基可行解，并相應地可以畫出一個新的單純形表。一個新的單純形表。5）重復）重復3）、）、4）步直到計算結(jié)束為止。）步直到計算結(jié)束為止。Page 7j 換入列換入列bi /ai2，ai2043換換出出行行將將4化為化為1，本列，本列的其他值化為的其他值化為010201/4011/21003/4j 04001000第一步：將第三行除以

5、第一步：將第三行除以4第二步：將第一行減去第三行乘以第二步：將第一行減去第三行乘以2Page 8j 換入列換入列bi /ai2，ai20換換出出行行10001/4011/210-21/4j 000-41200將將4化為化為0第一步：將第二行減去第一行乘以第一步：將第二行減去第一行乘以4248Page 9j 換入列換入列換換出出行行1001/2000010-3/20j -1/800-21/211/4將將2化為化為1，本列的其他值化為，本列的其他值化為0第一步：將第二行除以第一步：將第二行除以244第二步：將第一行加上第二行乘以第二步：將第一行加上第二行乘以1/2第三步：將第三行減去第二行乘以第三

6、步：將第三行減去第二行乘以1/442-1/8Page 10 表表1-6中所有的中所有的 都小于或者等于都小于或者等于0，表明已經(jīng)達到了最，表明已經(jīng)達到了最優(yōu)解，因此，現(xiàn)行的基本可行解優(yōu)解，因此，現(xiàn)行的基本可行解X=（4，2，0，0，4）T是是最優(yōu)解，最優(yōu)解，Z=14是該線性規(guī)劃的最優(yōu)值。是該線性規(guī)劃的最優(yōu)值。jPage 11例例1.9 用單純形法求解用單純形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：將數(shù)學模型化為標準形式：解：將數(shù)學模型化為標準形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxx

7、xxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量，列單純形表計算。可作為初始基變量，列單純形表計算。Page 12j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 13 表表1-6中所有的中所有的 都小于或者等于都小于或者等于0，表明已經(jīng)達到了最，表明已經(jīng)達到了最優(yōu)解，因此，現(xiàn)行的基本可行解優(yōu)解，因此，現(xiàn)行的基本可行解X=（25，35 /3，0，0，0）T是最優(yōu)解，是最優(yōu)解，Z=95/3是該線性規(guī)劃的最優(yōu)值。是該線性規(guī)劃的最優(yōu)值。jPage 14學習要

8、點：學習要點：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個基本定理個基本定理2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟Page 15人工變量法：人工變量法：前面討論了在標準型中系數(shù)矩陣有單位矩陣，很容前面討論了在標準型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人

9、工變量，構(gòu)成的可行基稱為人工基，用大加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大MM法或兩階段法求解，這種用人工變量作橋梁的求解方法法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。稱為人工變量法。Page 16例例1.10 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃 0123241123max32131321321321xxxxxxxxxxxxxxZ、解：首先將數(shù)學模型化為標準形式解：首先將數(shù)學模型化為標準形式 5 , 2 , 1, 012324112003max315321432154321jxxxxxxxxxxxxxxxxZj系數(shù)矩陣中不存在系數(shù)矩陣中不存在單位矩陣，

10、無法建單位矩陣，無法建立初始單純形表。立初始單純形表。Page 17故人為添加兩個單位向量，得到人工變量單純形法數(shù)學模型：故人為添加兩個單位向量，得到人工變量單純形法數(shù)學模型： 7 , 2 , 1, 0121024112003max7316532143217654321jxxxxxxxxxxxxxMxMxxxxxxZj其中：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。紹的單純形法求解該模型，計算結(jié)果見

11、下表。 Page 18j j j j Page 19解的判別：解的判別：j 1）唯一最優(yōu)解判別）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非：最優(yōu)表中所有非基變量的檢驗數(shù)非零零,則線則線 規(guī)劃具有唯一最優(yōu)解。規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為：最優(yōu)表中存在非基變量的檢驗數(shù)為零零,則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別）無界解判別：某個：某個 0且且aij（i=1，2,m）則線）則線性規(guī)性規(guī) 劃具有無界解。劃具有無界解。4）無可行解的判斷）無可行解的判斷：當用大：當用大M單純

12、形法計算得到最優(yōu)解單純形法計算得到最優(yōu)解并且存在并且存在Ri0時，則表明原線性規(guī)劃無可行解。時，則表明原線性規(guī)劃無可行解。5）退化解的判別）退化解的判別：存在某個基變量為零的基本可行解。：存在某個基變量為零的基本可行解。Page 20不不處處理理圖圖解解法、法、單單純純形形法法xj0 xj無無約約束束令令xj = xj- xj xj 0 xj 0 xj 0令令 xj = -xj xj 0 bi 0不不處處理理不不處處理理bi 0約約束束條條件件兩兩端端同同乘乘以以-1= 加加松松弛弛變變量量xs加加入入人人工工變變量量xa減減去去xs,加加入入xamaxZminZ令令z=- ZminZ=max

13、 zxs0 xa-M兩兩個個三個三個以上以上單單純純形形法法jmiijjacc 1: 求求0 j 所所有有kj即即找找出出max)()0(0 jika對對任任一一)0( lklkiiaab 計計算算lkxx替替換換基基變變量量用用非非基基變變量量新新單單純純形形表表列列出出下下一一個個ax含有含有量中是否量中是否基變基變 0 j非非基基變變量量的的有有某某個個最最優(yōu)優(yōu)解解一一唯唯 無無可可行行解解最優(yōu)解最優(yōu)解無窮多無窮多是是否否環(huán)環(huán)循循否否否否否否是是是是是是循環(huán)循環(huán)無無界界解解列列出出初初始始單單純純形形表表找找出出基基變變量量Page 22單純形表單純形表jcnmmcccc11BcBXbm

14、cc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 0 ijijjacc j 0 kjkjiiaab其其中中：Page 23一般而言，一個經(jīng)濟、管理問題凡是滿足以一般而言，一個經(jīng)濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。下條件時，才能建立線性規(guī)劃模型。 要求解問題的目標函數(shù)能用數(shù)值指標來反映，且要求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)為線性函數(shù) 存在著多種方案存在著多種方案 要求達到的目標是在一定條件下實現(xiàn)的，這些約要求達到的目標是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述束可用線性等式或不等式描述Page 2

15、4 人力資源分配問題人力資源分配問題例例1.11 某晝夜服務的公交線路每天各時間段內(nèi)某晝夜服務的公交線路每天各時間段內(nèi)所需司機和乘務人員人數(shù)如下表所示：所需司機和乘務人員人數(shù)如下表所示：班次班次時間時間所需人員所需人員16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030設司機和乘務人員分別在各時間段開始時上班，并連續(xù)工作設司機和乘務人員分別在各時間段開始時上班，并連續(xù)工作8小時，問該公交線路應怎樣安排司機和乘務人員，即能滿小時，問該公交線路應怎樣安排司機和乘務人員，即能滿足工作需要，又使配備司機和乘

16、務人員的人數(shù)減少足工作需要，又使配備司機和乘務人員的人數(shù)減少?Page 25解：設解：設xi表示第表示第i班次時開始上班的司機和乘務人員人數(shù)。班次時開始上班的司機和乘務人員人數(shù)。 0,302050607060.min654321655443322161654321xxxxxxxxxxxxxxxxxxtsxxxxxx此問題最優(yōu)解：此問題最優(yōu)解：x150， x220， x350， x40， x520， x610，一共需要司機和乘務員，一共需要司機和乘務員150人。人。Page 262. 生產(chǎn)計劃問題生產(chǎn)計劃問題某廠生產(chǎn)某廠生產(chǎn)、三種產(chǎn)品，都分別經(jīng)三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設兩道工序加工

17、。設A工序可分別在設備工序可分別在設備A1和和A2上完上完成，有成，有B1、B2、B3三種設備可用于完成三種設備可用于完成B工序。已工序。已知產(chǎn)品知產(chǎn)品可在可在A、B任何一種設備上加工；產(chǎn)品任何一種設備上加工；產(chǎn)品可可在任何規(guī)格的在任何規(guī)格的A設備上加工，但完成設備上加工，但完成B工序時，只能工序時，只能在在B1設備上加工；產(chǎn)品設備上加工；產(chǎn)品只能在只能在A2與與B2設備上加工。設備上加工。加工單位產(chǎn)品所需工序時間及其他各項數(shù)據(jù)如下表，加工單位產(chǎn)品所需工序時間及其他各項數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大。試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大。Page 27Page 28解：設解：設x

18、ijk表示產(chǎn)品表示產(chǎn)品i在工序在工序j的設備的設備k上加工的數(shù)量。約束條上加工的數(shù)量。約束條件有：件有：）（上加工的數(shù)量相等）上加工的數(shù)量相等），在工序在工序（產(chǎn)品（產(chǎn)品上加工的數(shù)量相等）上加工的數(shù)量相等），在工序在工序（產(chǎn)品（產(chǎn)品上加工的數(shù)量相等）上加工的數(shù)量相等），在工序在工序（產(chǎn)品（產(chǎn)品設備設備設備設備）（設備（設備）（設備（設備設備設備3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(60001053223122212122111231221211121111233221

19、22221121312212112211111 kjixxxxxxxxxxxxxxxxxxxxxijkPage 29目標是利潤最大化，即利潤的計算公式如下：目標是利潤最大化，即利潤的計算公式如下： 5131)()(ii該該設設備備實實際際使使用用臺臺時時每每臺臺時時的的設設備備費費用用該該產(chǎn)產(chǎn)品品件件數(shù)數(shù)銷銷售售單單價價原原料料單單價價利利潤潤帶入數(shù)據(jù)整理得到：帶入數(shù)據(jù)整理得到：12332212222112131221221111211135. 023. 1448. 05 . 0375. 0915. 136. 115. 1775. 075. 0maxxxxxxxxxxx Page 30因此該規(guī)

20、劃問題的模型為：因此該規(guī)劃問題的模型為： ）（3,2,1;2,1;3,2,104000770001144000861000012976000105.35.023.1448.05.0375.0915.136.115.1775.075.0max322312221212211123122121112111123322122221121312212112211111123322122221121312212211112111kjixxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxijkPage 313. 套裁下料問題套裁下料問題例：現(xiàn)有一批某種型號的圓鋼長例：現(xiàn)有一批某種型號的圓鋼長8

21、米，需要截取米，需要截取2.5米米長的毛坯長的毛坯100根，長根，長1.3米的毛坯米的毛坯200根。問如何才能根。問如何才能既滿足需要，又能使總的用料最少？既滿足需要，又能使總的用料最少？解：為了找到一個省料的套裁方案，必須先設計出較好的幾解：為了找到一個省料的套裁方案，必須先設計出較好的幾個下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格個下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對各種不同規(guī)格圓鋼的需要并達到省料的目的圓鋼，以滿足對各種不同規(guī)格圓鋼的需要并達到省料的目的，為此可以設計出的，為此可以設計出4種下料方案以供套裁用。種下料方案以供套裁用。Page 32 )

22、4.3.2.1(020064210023min4323214321jxxxxxxxxxxxZj設按方案設按方案、下料的原材料根數(shù)分別為下料的原材料根數(shù)分別為xj (j=1，2,3,4)，可列出下面的數(shù)學模型：，可列出下面的數(shù)學模型：Page 33 華津機器制造廠專為拖拉機廠配套生產(chǎn)柴油機。今年頭華津機器制造廠專為拖拉機廠配套生產(chǎn)柴油機。今年頭四個月收到的訂單數(shù)量分別為四個月收到的訂單數(shù)量分別為3000，4500，3500，5000臺臺柴油機。該廠正常生產(chǎn)每月可生產(chǎn)柴油機柴油機。該廠正常生產(chǎn)每月可生產(chǎn)柴油機3000臺，利用加臺，利用加班還可生產(chǎn)班還可生產(chǎn)1500臺。正常生產(chǎn)成本為每臺臺。正常生產(chǎn)

23、成本為每臺5000元，加班生元，加班生產(chǎn)還要追加產(chǎn)還要追加1500元成本，庫存成本為每臺每月元成本，庫存成本為每臺每月200元。華津元。華津廠如何組織生產(chǎn)才能使生產(chǎn)成本最低。廠如何組織生產(chǎn)才能使生產(chǎn)成本最低。Page 34決策變量：決策變量：xi 為第為第 i月正常生產(chǎn)的柴油機數(shù)月正常生產(chǎn)的柴油機數(shù)；yi 為第為第 i月加班生產(chǎn)的柴油機數(shù)月加班生產(chǎn)的柴油機數(shù)；zi 為第為第 i月初柴油機的庫存數(shù)。月初柴油機的庫存數(shù)。Page 35 數(shù)學模型如下：數(shù)學模型如下： min z = 5000(x1+x2+x3+x4)+6500(y1+y2+y3+y4) +200(z2+z3+z4) s.t. x1

24、+ y1 - z2 = 3000 x2 + y2 + z2 - z3 = 4500 x3 + y3 + z3 - z4 = 3500 x4 + y4 + z4 = 5000 0 xi 3000 i = 1 , 2 , 3 , 4 0 yi 1500 i = 1 , 2 , 3 , 4 zi 0 i = 1 , 2 , 3 , 4 Page 36Page 375. 證券投資組合優(yōu)化證券投資組合優(yōu)化 某人有一筆某人有一筆50萬元的資金可用于長期投資，可供選擇的萬元的資金可用于長期投資，可供選擇的投資機會包括購買國庫卷、債卷、房地產(chǎn)、股票或銀行儲蓄投資機會包括購買國庫卷、債卷、房地產(chǎn)、股票或銀行儲蓄

25、等。他希望投資組合的平均年限不超過等。他希望投資組合的平均年限不超過5年，平均的期望收年，平均的期望收益率不低于益率不低于13%，風險系數(shù)不超過，風險系數(shù)不超過4，收益的增長潛力不低，收益的增長潛力不低于于10%。在滿足上述要求的前提應如何選擇投資組合才能使。在滿足上述要求的前提應如何選擇投資組合才能使平均收益率最高。平均收益率最高。Page 38 投資 投資期 年收益 風險 增長潛 方式 限(年) 率() 系數(shù) 力() 國庫卷 3 11 1 0 債卷 10 15 3 15 房地產(chǎn) 6 25 8 30 股票 2 20 6 20 短期存款 1 10 1 5 長期存款 5 12 2 10 現(xiàn)金存款

26、 0 3 0 0Page 39決策變量決策變量：各種投資方式站總投資的比例；：各種投資方式站總投資的比例；目標函數(shù)目標函數(shù)：平均投資收益最大：平均投資收益最大 ；約束方程約束方程：滿足各種指標要求：滿足各種指標要求： 1、平均投資年限不超過、平均投資年限不超過5年年 2、平均的期望收益率不低于平均的期望收益率不低于13% 3、風險系數(shù)不超過、風險系數(shù)不超過4 4、收益的增長潛力不低于收益的增長潛力不低于15%Page 40max z = 11x1+15x2+25x3+20 x4+10 x5+12x6+3x7 s.t. 3x1+10 x2+ 6x3+ 2x4+ x5 + 5x6 5 11x1+1

27、5x2+25x3+20 x4+10 x5+12x6+3x7 13 x1 + 3x2 + 8x3+ 6x4 + x5 + 2x6 4 15x2+30 x3+20 x4+ 5x5 + 10 x6 10 x1 + x2 + x3 + x4 + x5 + x6 + x7 = 1 x1 , x2 , x3 , x4 , x5 , x6 , x7 0 Page 41證券投資模型證券投資模型年限年限 收益率收益率 風險系數(shù)風險系數(shù)增長潛力增長潛力 投入比例投入比例國庫券國庫券3 311111 10 00.48840.488424.4224.42債券債券101015153 315150.11630.11635

28、.8145.814房地產(chǎn)房地產(chǎn)6 625258 830300.39530.395319.7719.77股票股票2 220206 620200 00 0短期存款短期存款1 110101 15 50 00 0長期存款長期存款5 512122 210100 00 0活期儲蓄活期儲蓄0 03 30 00 00 00 0平均值平均值5 517174 413.6046513.604651 15050希望值希望值5 513134 410101 15050Page 42企業(yè)根據(jù)預測知道上半年市場對該企企業(yè)根據(jù)預測知道上半年市場對該企業(yè)產(chǎn)品的需求變化較大（見下表）：業(yè)產(chǎn)品的需求變化較大（見下表）： 月份月份 1

29、 2 3 4 5 6 需求需求 6000 2500 5000 3500 5500 6000企業(yè)目前有企業(yè)目前有100名工人，每人每月可生產(chǎn)名工人，每人每月可生產(chǎn)40件件產(chǎn)品，工人平均工資每月產(chǎn)品，工人平均工資每月800元，企業(yè)可元，企業(yè)可以通過以下方法調(diào)節(jié)生產(chǎn)：以通過以下方法調(diào)節(jié)生產(chǎn)： Page 43利用加班：加班需付加倍工資，每人每月利用加班生產(chǎn)的產(chǎn)品不能超過10件。利用庫存：每件產(chǎn)品庫存費用為10元/月。臨時增聘或解雇工人：新聘工人培訓費為1000元，解雇工人的解聘費為600元 。每月新聘工人數(shù)量不能超過10人。企業(yè)目前有庫存500件，希望六月底的庫存不低于700件，其他月份應保持不少于

30、200件的安全庫存，企業(yè)應如何組織生產(chǎn)。Page 44xi ：第：第 i 月在崗的工人數(shù)；月在崗的工人數(shù)；yi ：第：第 i 月新聘的工人數(shù)；月新聘的工人數(shù)；zi ：第：第 i 月解聘的工人數(shù)；月解聘的工人數(shù)；ki ：產(chǎn)品在第：產(chǎn)品在第 i 月期末的庫存數(shù)量；月期末的庫存數(shù)量；ui ：第：第 i 月正常生產(chǎn)的產(chǎn)品數(shù)量；月正常生產(chǎn)的產(chǎn)品數(shù)量；vi ：第：第 i 月加班生產(chǎn)的產(chǎn)品數(shù)量；月加班生產(chǎn)的產(chǎn)品數(shù)量；Page 45目標函數(shù)：目標函數(shù)：生產(chǎn)和庫存費用最小生產(chǎn)和庫存費用最小min i (800 xi+1000yi+600zi+10ki)Page 461) 每月在崗工人的平衡約束每月在崗工人的平衡

31、約束 x1 - x0 - y1 + z1 = 0 x2 - x1 - y2 + z2 = 0 x3 - x2 - y3 + z3 = 0 x4 - x3 - y4 + z4 = 0 x5 - x4 - y5 + z5 = 0 x6 - x5 - y6 + z6 = 0Page 472）每月生產(chǎn)的平衡約束 ui + vi + ki-1 - ki di i = 1 , , 6 u1 + v1 + k0 - k1 5500 u2 + v2 + k1 - k2 3200 u3 + v3 + k2 - k3 6700 u4 + v4 + k3 - k4 4300 u5 + v5 + k4 - k5 6400 u6 + v6 + k5 - k6 7500Page 483）正常生