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

1、單純形法的計算步驟,單純形表,單純形法的計算步驟,例1.8 用單純形法求下列線性規(guī)劃的最優(yōu)解,解：1）將問題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4、 x5則標(biāo)準(zhǔn)型為,單純形法的計算步驟,2）求出線性規(guī)劃的初始基可行解，列出初始單純形表,檢驗(yàn)數(shù),單純形法的計算步驟,3）進(jìn)行最優(yōu)性檢驗(yàn),如果表中所有檢驗(yàn)數(shù) ，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步,4）從一個基可行解轉(zhuǎn)換到另一個目標(biāo)值更大的基可行解，列出新的單純形表,確定換入基的變量。選擇 ，對應(yīng)的變量xj作為換入變量，當(dāng)有一個以上檢驗(yàn)數(shù)大于0時，一般選擇最大的一個檢驗(yàn)數(shù)，即： ，其對應(yīng)的xk作為換入變量。 確定換出變量。根據(jù)下式計

2、算并選擇 ，選最小的對應(yīng)基變量作為換出變量,單純形法的計算步驟,用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。 5）重復(fù)3）、4）步直到計算結(jié)束為止,單純形法的計算步驟,換入列,bi /ai2，ai20,4,3,換出行,將4化為1，本列的其他值化為0,1,0,2,0,1/4,0,1,1/2,1,0,0,3/4,0,4,0,0,1,0,0,0,第一步：將第三行除以4,第二步：將第一行減去第三行乘以2,單純形法的計算步驟,換入列,bi /ai2，ai20,換出行,1,0,0,0,1/4,0,1,1/2,1,0,2,1/4

3、,0,0,0,4,1,2,0,0,將4化為0,第一步：將第二行減去第一行乘以4,2,4,8,單純形法的計算步驟,換入列,換出行,1,0,0,1/2,0,0,0,0,1,0,3/2,0,1/8,0,0,2,1/2,1,1/4,將2化為1，本列的其他值化為0,第一步：將第二行除以2,4,4,第二步：將第一行加上第二行乘以1/2,第三步：將第三行減去第二行乘以1/4,4,2,1/8,單純形法的計算步驟,表1-6中所有的 都小于或者等于0，表明已經(jīng)達(dá)到了最優(yōu)解，因此，現(xiàn)行的基本可行解X=（4，2，0，0，4）T是最優(yōu)解，Z=14是該線性規(guī)劃的最優(yōu)值,單純形法的計算步驟,例1.9 用單純形法求解,解：將

4、數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,不難看出x4、x5可作為初始基變量，列單純形表計算,單純形法的計算步驟,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,1/9,2/3,35/3,0,0,98/9,1/9,7/3,單純形法的計算步驟,表1-6中所有的 都小于或者等于0，表明已經(jīng)達(dá)到了最優(yōu)解，因此，現(xiàn)行的基本可行解X=（25，35 /3，0，0，0）T是最優(yōu)解，Z=95/3是該線性規(guī)劃的最優(yōu)值,單純形法的計算步驟,學(xué)習(xí)要點(diǎn)： 1. 線性規(guī)劃解的概念以及3個基本定理 2. 熟練掌握單純

5、形法的解題思路及求解步驟,單純形法的進(jìn)一步討論人工變量法,人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法,單純形法的進(jìn)一步討論人工變量法,例1.10 用大M法解下列線性規(guī)劃,解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表,單純形法的進(jìn)一步討論人工變量法,故人為添加兩個單位向量，得到人工變量單

6、純形法數(shù)學(xué)模型,其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表,單純形法的進(jìn)一步討論人工變量法,單純形法的總結(jié),解的判別,1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線 規(guī)劃具有唯一最優(yōu)解,2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解,3）無界解判別：某個 0且aij（i=1，2,m）則線性規(guī) 劃具有無界解,4）無可行解的判斷：當(dāng)用大M單純形法計算得到最優(yōu)解并且存在Ri0時，則表明原線性規(guī)劃無可行解,5）退化解的判別：存在某個基變量為零

7、的基本可行解,單純形法小結(jié),不 處 理,圖解法、 單純形法,xj0,xj無 約束,令xj = xj- xj xj 0 xj 0,xj 0,令 xj = -xj xj 0,bi 0,不 處 理,不 處 理,bi 0,約束條件兩端同乘以-1,加松弛變量xs,加入人工變量xa,減 去 xs, 加入 xa,maxZ,minZ,令 z=- Z minZ = max z,xs,0,xa,M,兩 個,三個 以上,單純形法,單純形法的計算步驟,單純形表,線性規(guī)劃模型的應(yīng)用,一般而言，一個經(jīng)濟(jì)、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型,要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù) 存在著多種方案

8、 要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述,線性規(guī)劃在管理中的應(yīng)用,人力資源分配問題,例1.11 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示,設(shè)司機(jī)和乘務(wù)人員分別在各時間段開始時上班，并連續(xù)工作8小時，問該公交線路應(yīng)怎樣安排司機(jī)和乘務(wù)人員，即能滿足工作需要，又使配備司機(jī)和乘務(wù)人員的人數(shù)減少,線性規(guī)劃在管理中的應(yīng)用,解：設(shè)xi表示第i班次時開始上班的司機(jī)和乘務(wù)人員人數(shù),此問題最優(yōu)解：x150， x220， x350， x40， x520， x610，一共需要司機(jī)和乘務(wù)員150人,線性規(guī)劃在管理中的應(yīng)用,2. 生產(chǎn)計劃問題,某廠生產(chǎn)、三種產(chǎn)品，都

9、分別經(jīng)A、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1和A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序。已知產(chǎn)品可在A、B任何一種設(shè)備上加工；產(chǎn)品可在任何規(guī)格的A設(shè)備上加工，但完成B工序時，只能在B1設(shè)備上加工；產(chǎn)品只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序時間及其他各項(xiàng)數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大,線性規(guī)劃在管理中的應(yīng)用,線性規(guī)劃在管理中的應(yīng)用,解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條件有,線性規(guī)劃在管理中的應(yīng)用,目標(biāo)是利潤最大化，即利潤的計算公式如下,帶入數(shù)據(jù)整理得到,線性規(guī)劃在管理中的應(yīng)用,因此該規(guī)劃問題的模型為,線性規(guī)劃在管理中的應(yīng)用,3

10、. 套裁下料問題,例：現(xiàn)有一批某種型號的圓鋼長8米，需要截取2.5米長的毛坯100根，長1.3米的毛坯200根。問如何才能既滿足需要，又能使總的用料最少,解：為了找到一個省料的套裁方案，必須先設(shè)計出較好的幾個下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計出4種下料方案以供套裁用,線性規(guī)劃在管理中的應(yīng)用,設(shè)按方案、下料的原材料根數(shù)分別為xj (j=1，2,3,4)，可列出下面的數(shù)學(xué)模型,線性規(guī)劃在管理中的應(yīng)用,3. 多周期動態(tài)生產(chǎn)計劃問題,華津機(jī)器制造廠專為拖拉機(jī)廠配套生產(chǎn)柴油機(jī)。今年頭四個月收到的訂單數(shù)量分別為3000，4

11、500，3500，5000臺柴油機(jī)。該廠正常生產(chǎn)每月可生產(chǎn)柴油機(jī)3000臺，利用加班還可生產(chǎn)1500臺。正常生產(chǎn)成本為每臺5000元，加班生產(chǎn)還要追加1500元成本，庫存成本為每臺每月200元。華津廠如何組織生產(chǎn)才能使生產(chǎn)成本最低,線性規(guī)劃在管理中的應(yīng)用,決策變量： xi 為第 i月正常生產(chǎn)的柴油機(jī)數(shù)； yi 為第 i月加班生產(chǎn)的柴油機(jī)數(shù)； zi 為第 i月初柴油機(jī)的庫存數(shù),線性規(guī)劃在管理中的應(yīng)用,數(shù)學(xué)模型如下： min z = 5000(x1+x2+x3+x4)+6500(y1+y2+y3+y4) +200(z2+z3+z4) s.t. x1 + y1 - z2 = 3000 x2 + y2

12、 + 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,線性規(guī)劃在管理中的應(yīng)用,線性規(guī)劃在管理中的應(yīng)用,5. 證券投資組合優(yōu)化,某人有一筆50萬元的資金可用于長期投資，可供選擇的投資機(jī)會包括購買國庫卷、債卷、房地產(chǎn)、股票或銀行儲蓄等。他希望投資組合的平均年限不超過5年，平均的期望收益率不低于13%，風(fēng)險系數(shù)不超過4，收益的增長潛力不低于10%。在滿足上述要求的前提應(yīng)如何

13、選擇投資組合才能使平均收益率最高,線性規(guī)劃在管理中的應(yīng)用,投資 投資期 年收益 風(fēng)險 增長潛 方式 限(年) 率() 系數(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)金存款 0 3 0 0,線性規(guī)劃在管理中的應(yīng)用,決策變量：各種投資方式站總投資的比例； 目標(biāo)函數(shù)：平均投資收益最大 ； 約束方程：滿足各種指標(biāo)要求： 1、平均投資年限不超過5年 2、平均的期望收益率不低于13% 3、風(fēng)險系數(shù)不超過4 4、收益的增長潛力不低于15,線性規(guī)劃在管理中的應(yīng)用,證券組合優(yōu)化

14、模型,max z = 11x1+15x2+25x3+20 x4+10 x5+12x6+3x7 s.t. 3x1+10 x2+ 6x3+ 2x4+ x5 + 5x6 5 11x1+15x2+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,線性規(guī)劃在管理中的應(yīng)用,線性規(guī)劃在管理中的應(yīng)用,6. 生產(chǎn)庫存計劃問題,線性規(guī)

15、劃在管理中的應(yīng)用,利用加班：加班需付加倍工資，每人每月利用加班生產(chǎn)的產(chǎn)品不能超過10件。 利用庫存：每件產(chǎn)品庫存費(fèi)用為10元/月。 臨時增聘或解雇工人：新聘工人培訓(xùn)費(fèi)為1000元，解雇工人的解聘費(fèi)為600元 。每月新聘工人數(shù)量不能超過10人。企業(yè)目前有庫存500件，希望六月底的庫存不低于700件，其他月份應(yīng)保持不少于 200件的安全庫存，企業(yè)應(yīng)如何組織生產(chǎn),線性規(guī)劃在管理中的應(yīng)用,變量設(shè)置： xi ：第 i 月在崗的工人數(shù)； yi ：第 i 月新聘的工人數(shù)； zi ：第 i 月解聘的工人數(shù)； ki ：產(chǎn)品在第 i 月期末的庫存數(shù)量； ui ：第 i 月正常生產(chǎn)的產(chǎn)品數(shù)量； vi ：第 i 月加

16、班生產(chǎn)的產(chǎn)品數(shù)量,線性規(guī)劃在管理中的應(yīng)用,目標(biāo)函數(shù)：生產(chǎn)和庫存費(fèi)用最小 min i (800 xi+1000yi+600zi+10ki,線性規(guī)劃在管理中的應(yīng)用,約束條件： 1) 每月在崗工人的平衡約束 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 = 0,線性規(guī)劃在管理中的應(yīng)用,2）每月生產(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 7500,線性規(guī)劃在管理中的應(yīng)用,3）正常生產(chǎn)限制約束： ui 40 xi i = 1, , 6 u1 40 x1 u2 40 x2 u3 40 x3 u4 40 x4 u5 40 x5 u6 40 x6,