单纯形方法补充例子

1、P124 例S1.3某旅馆每日至少需要下表所示数量的服务员：某旅馆每日至少需要下表所示数量的服务员：班次班次时间时间(日夜服务日夜服务)最少服务员人数最少服务员人数(人人)1上午上午6点点-上午上午10点点802上午上午10点点-下午下午2点点903下午下午2点点-下午下午6点点804下午下午6点点-夜间夜间10点点705夜间夜间10点点-夜间夜间2点点406夜间夜间2点点-上午上午6点点30每班服务员从开始上班到下班连续工作每班服务员从开始上班到下班连续工作8小时，小时，为满足每班所需要的最少服务员人数，该为满足每班所需要的最少服务员人数，该旅馆旅馆至至少需要多少服务员少需要多少服务员?解：

2、解：班次班次时间时间(日夜服务日夜服务)最少服务员人数最少服务员人数(人人)1上午上午6点点-上午上午10点点802上午上午10点点-下午下午2点点903下午下午2点点-下午下午6点点804下午下午6点点-夜间夜间10点点705夜间夜间10点点-夜间夜间2点点406夜间夜间2点点-上午上午6点点30设第设第i班班开始上班的服务员数量为开始上班的服务员数量为xi人，人，则该问题的目标函数为：则该问题的目标函数为：654321minxxxxxxz约约束束条条件件班次班次时间时间(日夜服务日夜服务)最少服务员人数最少服务员人数(人人)1上午上午6点点-上午上午10点点802上午上午10点点-下午下午

3、2点点903下午下午2点点-下午下午6点点804下午下午6点点-夜间夜间10点点705夜间夜间10点点-夜间夜间2点点406夜间夜间2点点-上午上午6点点30每班服每班服务员从开务员从开始上班到下班始上班到下班连续连续工作工作8小小时时：8016 xx第第1班：班：9021 xx第第2班：班：8032 xx第第3班：班：7043 xx第第4班：班：4054 xx第第5班：班：3065 xx第第6班：班：该问题的数学模型为：该问题的数学模型为：654321minxxxxxxz . .ts8016 xx9021 xx8032 xx7043 xx4054 xx3065 xx0,654321xxxxx

4、x并且都是取整数并且都是取整数Lindo的程序为：的程序为：min x1+x2+x3+x4+x5+x6stx6+x1=80 x1+x2=90 x2+x3=80 x3+x4=70 x4+x5=40 x5+x6=30endgin 6Lindo的的计算结果计算结果： 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最优解最优解:例例1 利用单纯形方法求最优解利用单纯形方法求最优解 0,7 438 22 . .325max543215321432154321xxxxxxxxxxxxxtsxxxxxZ解法解法：, 0,7 438 22 . .

6、325max543215321432154321xxxxxxxxxxxxxtsxxxxxZ由于数学规划模型已是标准型由于数学规划模型已是标准型, ,故取基故取基B为为IPPB100154则基变量为则基变量为 .,54xx因此因此, ,对应于基对应于基B的初始单纯形表为的初始单纯形表为 0,7 438 22 . .325max543215321432154321xxxxxxxxxxxxxtsxxxxxZ对应于基对应于基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取最大的正检验数对应的变量取最大的正检验数对应的变量x3为换入变量为换入变量由于检验数中有正数，由于检验数中有正数，取最小的比值对应的变量取最小的比值对应的变量x4为换出变量为换出变量并且所有正检验数对应的并且所有正检验数对应的列向量都有正分量，列向量都有正分量， 故不是最优解，需要换基迭代故不是最优解，需要换基迭代换基迭代，换基迭代，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取最大的正检验数对应的变量取最大的正检验数对应的变量x1为换入变量为换入变量由于检验数中还有正数，由于检验数中还有正数，取最小的比值对应的变量取最小的比值对应的变量x5为

9、换出变量为换出变量故需要进行换基迭代。故需要进行换基迭代。并且该正检验数对应的并且该正检验数对应的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最优性检验最优性检验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由于所有的检验数都是非正数，由于所有的检验数都是非正数，则可得则可得最优解为：最优解为： x1=6/5, x2=0, x3=17/5, x4=0, x5=0最优值：最优值： Z = 81/5例例2 用单纯形法求解线性规划问题用单纯形法求解线性规划问题 0,8 23 4 . .2min54321521423121xxxxxxxxxxxxtsxxZ解解: 由于该线性规划问题的目标函数求最小值由于该线性规划问题的目标函数求最小值 0,8 23 4 . .2max54321521423121xxxxxx

11、xxxxxxtsxxZ则可化为标准型则可化为标准型,令令Z= - Z， 可得标准型可得标准型取基取基B为为:IPPPB100010001 543则基变量为则基变量为 .,543xxx因此因此, ,对应于基对应于基B的初始单纯形表为的初始单纯形表为 0,8 23 4 .2max54321521423121xxxxxxxxxxxxtsxxZ对应于基对应于基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最优性判断最优性判断CiCBXBbZjx1x2x3x5x412000 x3x4x50004381 0 1 0 00 1 0 1 01 2 0 0 101 2 0 0 0由于检验数中有正数，由于检验数中有正数， 故基可行解不是最优解故基可行解不是最优解需要进行换基迭代。需要进行换基迭代。 取最大的正检验对应的取最大的正检验对应的变量变量x2为换入变量，为换入变量，-34取比值最小的取比值最小的3对应的变对应的变量量x4为换入变量，进行换基迭代。为换入变量，进行换基迭代。主元为主元为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由于检验数中有正数，其对应分量中有正数，由于检验数中有正数，其对应分量中有正数，故此可行解不是最优解，需要进行换基迭代。故此可行解不是最优解

14、，需要进行换基迭代。取最大的正检验对应的变量取最大的正检验对应的变量x1为换入变量，为换入变量，取比值最小的取比值最小的2对应的对应的x5为换入变量。为换入变量。进行换基迭代，进行换基迭代，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由于所有的检验数都是非正数，由于所有的检验数都是非正数，则可得则可得最优解为：最优解为： x1=2, x2=3, x3=2, x4=0, x5=0最优值：最优值： Z = 8. 而而 Z = -8.目标函数为求最大值与最小值目标函数为求最大值与最小值的线性规划问题的区别的线性规划问题的区别、求最大值问题：若所有的检验数都为非、求最大值问题：若所有的检验数都为非正数正数(0)(0)，则基，则基B B 为最优基，由单纯形表为最优基，由单纯形表可得最优解。可得最优解。 换基迭代时，取最大的正检验换基迭代时，取最大

16、的正检验数对应的变量为换入变量。数对应的变量为换入变量。 2 2、求最小值问题：若所有的检验数都为非、求最小值问题：若所有的检验数都为非负数负数(0)(0)，则基，则基B B 为最优基，由单纯形表为最优基，由单纯形表可得最优解。可得最优解。 换基迭代时，取最小的负检验换基迭代时，取最小的负检验数对应的变量为换入变量。数对应的变量为换入变量。 另解例另解例2： 直接用单纯形法求最小值的问题直接用单纯形法求最小值的问题 0,8 23 4 . .2min54321521423121xxxxxxxxxxxxtsxxZ取基取基B为为:IPPPB100010001 543则基变量为则基变量为 .,543x

17、xx因此因此, ,对应于基对应于基B的初始单纯形表为的初始单纯形表为 0,8 23 4 .2min54321521423121xxxxxxxxxxxxtsxxZ对应于基对应于基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最优性判断最优性判断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由于检验数中有负数，且其分量都有正数，由于检验数中有负数，且其分量都有正数，故基可行解不是最优解，需要进行换基迭代。故基可行解不是最优解，需要进行换基迭代。取最小的负检验对应的变量取最小的负检验对应的变量x2为换入变量，为换入变量，-34取比值最小的取比值最小的3对应的对应的x4为换入变量，为换入变量，进行换基迭代。进行换基迭代。 主元为主元为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