單純形方法補(bǔ)充例子

1、P124 例S1.3某旅館每日至少需要下表所示數(shù)量的服務(wù)員：某旅館每日至少需要下表所示數(shù)量的服務(wù)員：班次班次時(shí)間時(shí)間(日夜服務(wù)日夜服務(wù))最少服務(wù)員人數(shù)最少服務(wù)員人數(shù)(人人)1上午上午6點(diǎn)點(diǎn)-上午上午10點(diǎn)點(diǎn)802上午上午10點(diǎn)點(diǎn)-下午下午2點(diǎn)點(diǎn)903下午下午2點(diǎn)點(diǎn)-下午下午6點(diǎn)點(diǎn)804下午下午6點(diǎn)點(diǎn)-夜間夜間10點(diǎn)點(diǎn)705夜間夜間10點(diǎn)點(diǎn)-夜間夜間2點(diǎn)點(diǎn)406夜間夜間2點(diǎn)點(diǎn)-上午上午6點(diǎn)點(diǎn)30每班服務(wù)員從開始上班到下班連續(xù)工作每班服務(wù)員從開始上班到下班連續(xù)工作8小時(shí)，小時(shí)，為滿足每班所需要的最少服務(wù)員人數(shù)，該為滿足每班所需要的最少服務(wù)員人數(shù)，該旅館旅館至至少需要多少服務(wù)員少需要多少服務(wù)員?解：

2、解：班次班次時(shí)間時(shí)間(日夜服務(wù)日夜服務(wù))最少服務(wù)員人數(shù)最少服務(wù)員人數(shù)(人人)1上午上午6點(diǎn)點(diǎn)-上午上午10點(diǎn)點(diǎn)802上午上午10點(diǎn)點(diǎn)-下午下午2點(diǎn)點(diǎn)903下午下午2點(diǎn)點(diǎn)-下午下午6點(diǎn)點(diǎn)804下午下午6點(diǎn)點(diǎn)-夜間夜間10點(diǎn)點(diǎn)705夜間夜間10點(diǎn)點(diǎn)-夜間夜間2點(diǎn)點(diǎn)406夜間夜間2點(diǎn)點(diǎn)-上午上午6點(diǎn)點(diǎn)30設(shè)第設(shè)第i班班開始上班的服務(wù)員數(shù)量為開始上班的服務(wù)員數(shù)量為xi人，人，則該問題的目標(biāo)函數(shù)為：則該問題的目標(biāo)函數(shù)為：654321minxxxxxxz約約束束條條件件班次班次時(shí)間時(shí)間(日夜服務(wù)日夜服務(wù))最少服務(wù)員人數(shù)最少服務(wù)員人數(shù)(人人)1上午上午6點(diǎn)點(diǎn)-上午上午10點(diǎn)點(diǎn)802上午上午10點(diǎn)點(diǎn)-下午下午

3、2點(diǎn)點(diǎn)903下午下午2點(diǎn)點(diǎn)-下午下午6點(diǎn)點(diǎn)804下午下午6點(diǎn)點(diǎn)-夜間夜間10點(diǎn)點(diǎn)705夜間夜間10點(diǎn)點(diǎn)-夜間夜間2點(diǎn)點(diǎn)406夜間夜間2點(diǎn)點(diǎn)-上午上午6點(diǎn)點(diǎn)30每班服每班服務(wù)員從開務(wù)員從開始上班到下班始上班到下班連續(xù)連續(xù)工作工作8小小時(shí)時(shí)：8016 xx第第1班：班：9021 xx第第2班：班：8032 xx第第3班：班：7043 xx第第4班：班：4054 xx第第5班：班：3065 xx第第6班：班：該問題的數(shù)學(xué)模型為：該問題的數(shù)學(xué)模型為：654321minxxxxxxz . .ts8016 xx9021 xx8032 xx7043 xx4054 xx3065 xx0,654321xxxxx

4、x并且都是取整數(shù)并且都是取整數(shù)Lindo的程序?yàn)椋旱某绦驗(yàn)椋簃in x1+x2+x3+x4+x5+x6stx6+x1=80 x1+x2=90 x2+x3=80 x3+x4=70 x4+x5=40 x5+x6=30endgin 6Lindo的的計(jì)算結(jié)果計(jì)算結(jié)果： OBJECTIVE FUNCTION VALUE 1) 200.0000 VARIABLE VALUE REDUCED COST X1 80.000000 1.000000 X2 10.000000 1.000000 X3 70.000000 1.000000 X4 10.000000 1.000000 X5 30.000000 1.0

5、00000 X6 0.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 0.000000 4) 0.000000 0.000000 5) 10.000000 0.000000 6) 0.000000 0.000000 7) 0.000000 0.000000最優(yōu)解最優(yōu)解:例例1 利用單純形方法求最優(yōu)解利用單純形方法求最優(yōu)解 0,7 438 22 . .325max543215321432154321xxxxxxxxxxxxxtsxxxxxZ解法解法：, 0,7 438 22 . .

6、325max543215321432154321xxxxxxxxxxxxxtsxxxxxZ由于數(shù)學(xué)規(guī)劃模型已是標(biāo)準(zhǔn)型由于數(shù)學(xué)規(guī)劃模型已是標(biāo)準(zhǔn)型, ,故取基故取基B為為IPPB100154則基變量為則基變量為 .,54xx因此因此, ,對(duì)應(yīng)于基對(duì)應(yīng)于基B的初始單純形表為的初始單純形表為 0,7 438 22 . .325max543215321432154321xxxxxxxxxxxxxtsxxxxxZ對(duì)應(yīng)于基對(duì)應(yīng)于基B的初始單純形表為的初始單純形表為 x4 x5IPPB54基-1 11 2 2 1 03 4 1 0 130400-1C iCBXBb Zj781 1- 3 2 554321 x

7、x x xxx4 x5-1 11 2 2 1 03 4 1 0 130400-1C 5 2 3 -1 1iCBXBb x1 x2 x3 x4 x5Zj782/841 /77取最大的正檢驗(yàn)數(shù)對(duì)應(yīng)的變量取最大的正檢驗(yàn)數(shù)對(duì)應(yīng)的變量x3為換入變量為換入變量由于檢驗(yàn)數(shù)中有正數(shù)，由于檢驗(yàn)數(shù)中有正數(shù)，取最小的比值對(duì)應(yīng)的變量取最小的比值對(duì)應(yīng)的變量x4為換出變量為換出變量并且所有正檢驗(yàn)數(shù)對(duì)應(yīng)的并且所有正檢驗(yàn)數(shù)對(duì)應(yīng)的列向量都有正分量，列向量都有正分量， 故不是最優(yōu)解，需要換基迭代故不是最優(yōu)解，需要換基迭代換基迭代，換基迭代，x4 x5-1 11 2 2 1 03 4 1 0 130400-1C5 2 3 -1 1

8、iCBXBbx1 x2 x3 x4 x5Zj782/841 /77x3 x53 1C 5 2 3 -1 1iCBXBb x1 x2 x3 x4 x51121421003252113151-4020取取x3為換入變量，為換入變量，x4為換出變量。為換出變量。列向量有正分量，列向量有正分量，x3 x53 1C 5 2 3 -1 1iCBXBb x1 x2 x3 x4 x5Zj1121421003252113151-402086/5取最大的正檢驗(yàn)數(shù)對(duì)應(yīng)的變量取最大的正檢驗(yàn)數(shù)對(duì)應(yīng)的變量x1為換入變量為換入變量由于檢驗(yàn)數(shù)中還有正數(shù)，由于檢驗(yàn)數(shù)中還有正數(shù)，取最小的比值對(duì)應(yīng)的變量取最小的比值對(duì)應(yīng)的變量x5為

9、換出變量為換出變量故需要進(jìn)行換基迭代。故需要進(jìn)行換基迭代。并且該正檢驗(yàn)數(shù)對(duì)應(yīng)的并且該正檢驗(yàn)數(shù)對(duì)應(yīng)的x3 x53 1C 5 2 3 -1 1iCBXBb x1 x2 x3 x4 x5Zj1121421003252113151-402086/5取取x1為換入變量為換入變量,換基迭代換基迭代x5為換出變量為換出變量x3 x1C 5 2 3 -1 1iCBXBb x1 x2 x3 x4 x5Zj3516/56/50-1/52/5017/52/513/5-1/581/50-26/50-9/5-2/5最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)x3 x1C 5 2 3 -1 1iCBXBb x1 x2 x3 x4 x5Zj351

10、6/56/50-1/52/5017/52/513/5-1/581/50-26/5 0-9/5-2/5由于所有的檢驗(yàn)數(shù)都是非正數(shù)，由于所有的檢驗(yàn)數(shù)都是非正數(shù)，則可得則可得最優(yōu)解為：最優(yōu)解為： x1=6/5, x2=0, x3=17/5, x4=0, x5=0最優(yōu)值：最優(yōu)值： Z = 81/5例例2 用單純形法求解線性規(guī)劃問題用單純形法求解線性規(guī)劃問題 0,8 23 4 . .2min54321521423121xxxxxxxxxxxxtsxxZ解解: 由于該線性規(guī)劃問題的目標(biāo)函數(shù)求最小值由于該線性規(guī)劃問題的目標(biāo)函數(shù)求最小值 0,8 23 4 . .2max54321521423121xxxxxx

11、xxxxxxtsxxZ則可化為標(biāo)準(zhǔn)型則可化為標(biāo)準(zhǔn)型,令令Z= - Z， 可得標(biāo)準(zhǔn)型可得標(biāo)準(zhǔn)型取基取基B為為:IPPPB100010001 543則基變量為則基變量為 .,543xxx因此因此, ,對(duì)應(yīng)于基對(duì)應(yīng)于基B的初始單純形表為的初始單純形表為 0,8 23 4 .2max54321521423121xxxxxxxxxxxxtsxxZ對(duì)應(yīng)于基對(duì)應(yīng)于基B的初始單純形表為的初始單純形表為 CiCBXBbZjOCB0,8 23 4 .2max54321521423121xxxxxxxxxxxxtsxxZIPPPB543 基x1x2x3x5x412000 x3x4x50004381 0 1 0 00

12、 1 0 1 01 2 0 0 101 2 0 0 0最優(yōu)性判斷最優(yōu)性判斷CiCBXBbZjx1x2x3x5x412000 x3x4x50004381 0 1 0 00 1 0 1 01 2 0 0 101 2 0 0 0由于檢驗(yàn)數(shù)中有正數(shù)，由于檢驗(yàn)數(shù)中有正數(shù)， 故基可行解不是最優(yōu)解故基可行解不是最優(yōu)解需要進(jìn)行換基迭代。需要進(jìn)行換基迭代。 取最大的正檢驗(yàn)對(duì)應(yīng)的取最大的正檢驗(yàn)對(duì)應(yīng)的變量變量x2為換入變量，為換入變量，-34取比值最小的取比值最小的3對(duì)應(yīng)的變對(duì)應(yīng)的變量量x4為換入變量，進(jìn)行換基迭代。為換入變量，進(jìn)行換基迭代。主元為主元為a24C 1 2 0 0 0iCBXBb x1 x2 x3 x

13、4 x5Zjx3x4x50004381 0 1 0 00 1 0 1 01 2 0 0 101 2 0 0 0-34取取x3換入換入,主元為主元為x24，x4換出換出,換基迭代換基迭代C 1 2 0 0 0iCBXBb x1 x2 x3 x4 x5Zjx3x2x50201030100141000120-216100-20C 1 2 0 0 0iCBXBb x1 x2 x3 x4 x5Zjx3x2x50201030100141000120-216100-20由于檢驗(yàn)數(shù)中有正數(shù)，其對(duì)應(yīng)分量中有正數(shù)，由于檢驗(yàn)數(shù)中有正數(shù)，其對(duì)應(yīng)分量中有正數(shù)，故此可行解不是最優(yōu)解，需要進(jìn)行換基迭代。故此可行解不是最優(yōu)解

14、，需要進(jìn)行換基迭代。取最大的正檢驗(yàn)對(duì)應(yīng)的變量取最大的正檢驗(yàn)對(duì)應(yīng)的變量x1為換入變量，為換入變量，取比值最小的取比值最小的2對(duì)應(yīng)的對(duì)應(yīng)的x5為換入變量。為換入變量。進(jìn)行換基迭代，進(jìn)行換基迭代，4-2主元為主元為a15C 1 2 0 0 0iCBXBbx1 x2 x3 x4 x5Zjx3x2x50201030100141000120-216100-204-2換基迭代，換基迭代， 取取x1換入，換入，x5換出換出C 1 2 0 0 0iCBXBb x1 x2 x3 x4 x5Zjx3x2x102110301000212-10120-210000-1C 1 2 0 0 0iCBXBb x1 x2 x3

15、 x4 x5Zjx3x2x102110301000212-10120-2180000-1由于所有的檢驗(yàn)數(shù)都是非正數(shù)，由于所有的檢驗(yàn)數(shù)都是非正數(shù)，則可得則可得最優(yōu)解為：最優(yōu)解為： x1=2, x2=3, x3=2, x4=0, x5=0最優(yōu)值：最優(yōu)值： Z = 8. 而而 Z = -8.目標(biāo)函數(shù)為求最大值與最小值目標(biāo)函數(shù)為求最大值與最小值的線性規(guī)劃問題的區(qū)別的線性規(guī)劃問題的區(qū)別、求最大值問題：若所有的檢驗(yàn)數(shù)都為非、求最大值問題：若所有的檢驗(yàn)數(shù)都為非正數(shù)正數(shù)(0)(0)，則基，則基B B 為最優(yōu)基，由單純形表為最優(yōu)基，由單純形表可得最優(yōu)解?？傻米顑?yōu)解。 換基迭代時(shí)，取最大的正檢驗(yàn)換基迭代時(shí)，取最大

16、的正檢驗(yàn)數(shù)對(duì)應(yīng)的變量為換入變量。數(shù)對(duì)應(yīng)的變量為換入變量。 2 2、求最小值問題：若所有的檢驗(yàn)數(shù)都為非、求最小值問題：若所有的檢驗(yàn)數(shù)都為非負(fù)數(shù)負(fù)數(shù)(0)(0)，則基，則基B B 為最優(yōu)基，由單純形表為最優(yōu)基，由單純形表可得最優(yōu)解?？傻米顑?yōu)解。 換基迭代時(shí)，取最小的負(fù)檢驗(yàn)換基迭代時(shí)，取最小的負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的變量為換入變量。數(shù)對(duì)應(yīng)的變量為換入變量。 另解例另解例2： 直接用單純形法求最小值的問題直接用單純形法求最小值的問題 0,8 23 4 . .2min54321521423121xxxxxxxxxxxxtsxxZ取基取基B為為:IPPPB100010001 543則基變量為則基變量為 .,543x

17、xx因此因此, ,對(duì)應(yīng)于基對(duì)應(yīng)于基B的初始單純形表為的初始單純形表為 0,8 23 4 .2min54321521423121xxxxxxxxxxxxtsxxZ對(duì)應(yīng)于基對(duì)應(yīng)于基B的初始單純形表為的初始單純形表為 CiCBXBbZjOCB0,8 23 4 .2min54321521423121xxxxxxxxxxxxtsxxZIPPPB543 基x1x2x3x5x4-1-2000 x3x4x50004381 0 1 0 00 1 0 1 01 2 0 0 10-1 -2 0 0 0最優(yōu)性判斷最優(yōu)性判斷C -1 -2 0 0 0iCBXBb x1 x2 x3 x4 x5Zjx3x4x5000438

18、1 0 1 0 00 1 0 1 01 2 0 0 10-1 - 2 0 0 0由于檢驗(yàn)數(shù)中有負(fù)數(shù)，且其分量都有正數(shù)，由于檢驗(yàn)數(shù)中有負(fù)數(shù)，且其分量都有正數(shù)，故基可行解不是最優(yōu)解，需要進(jìn)行換基迭代。故基可行解不是最優(yōu)解，需要進(jìn)行換基迭代。取最小的負(fù)檢驗(yàn)對(duì)應(yīng)的變量取最小的負(fù)檢驗(yàn)對(duì)應(yīng)的變量x2為換入變量，為換入變量，-34取比值最小的取比值最小的3對(duì)應(yīng)的對(duì)應(yīng)的x4為換入變量，為換入變量，進(jìn)行換基迭代。進(jìn)行換基迭代。 主元為主元為a24C -1 -2 0 0 0iCBXBb x1 x2 x3 x4 x5Zjx3x4x50004381 0 1 0 00 1 0 1 01 2 0 0 10-1 -2 0 0 0-34取取x2換入換入, x4換出換出,C -1 -2 0 0 0iCBXBb x1 x2 x3 x4 x5Zjx3x2x50-201030100141