运筹学-整数规划ppt课件.ppt

《运筹学-整数规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学-整数规划ppt课件.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回整数规划（整数规划（integerprogramming)1.几个实例几个实例2.整数规划的算法整数规划的算法分支定界法和割平面方法分支定界法和割平面方法3.Lingo/Lindo求解整数规划求解整数规划篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回例例1。人员

2、安排问题。人员安排问题整数规划整数规划某宾馆一天各时段需要的人数如下所示。按规定，某宾馆一天各时段需要的人数如下所示。按规定，服务员连续工作八小时为一服务员连续工作八小时为一班。现要求安排服务员的班。现要求安排服务员的工作时间，使所需服务员总数最少。工作时间，使所需服务员总数最少。篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回时段始末时间所需服务员人数16:008:00628:0010:0012310:0012:00 10412:0014:00 85

3、14:0016:00 9616:0018:00 14718:0020:00 8820:0022:00 6922:0024:00 4某宾馆一天各时段需要的人数如下所示。按规定，某宾馆一天各时段需要的人数如下所示。按规定，服务员连续工作八小时为一服务员连续工作八小时为一班。现要求安排服务员的班。现要求安排服务员的工作时间，使所需服务员总数最少。工作时间，使所需服务员总数最少。篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回解：设解：设xj 表示第表示第j时

4、段开始上班的服务员人数。由于时段开始上班的服务员人数。由于每两小时为一时段，所以第每两小时为一时段，所以第j时段开始上班的服务员将在时段开始上班的服务员将在第第j+3时段结束时下班。因此只考虑时段结束时下班。因此只考虑相应的模型为：相应的模型为：时段始末时间所需服务员人数16:008:00628:0010:0012310:0012:0010412:0014:008514:0016:009616:0018:0014718:0020:008820:0022:006922:0024:004篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，

5、篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回时段始末时间所需服务员人数16:008:00628:0010:0012310:0012:0010412:0014:008514:0016:009616:0018:0014718:0020:008820:0022:006922:0024:004第第4阶段阶段5阶段阶段6阶段阶段7阶段阶段7阶段阶段9阶段阶段篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回整数规划整数规划篮球比

6、球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回利用数学软件利用数学软件lingo可求得一个最优解为：可求得一个最优解为：X1=12.000000 X2 =0.000000 X3 =6.000000 X4 =2.000000 X5 =1.000000 X6 =5.000000最优值为最优值为26，具体过程如下：，具体过程如下：篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计

7、分系分系统是一种得分是一种得分类型的系型的系统上页下页返回求解程序为求解程序为Liti1aMIN=x1+x2+x3+x4+x5+x6;x16;x1+x212;x1+x2+x310;x1+x2+x3+x48;x2+x3+x4+x59;x3+x4+x5+x614;x4+x5+x68;x5+x66;x64;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);end篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回OB

8、JECTIVEFUNCTIONVALUE(1)26.00000VARIABLEVALUEX112.000000X20.000000X36.000000X42.000000X51.000000X65.000000另一最优解为另一最优解为OBJECTIVEFUNCTIONVALUE1)26.00000VARIABLEVALUEX16.000000X26.000000X30.000000X40.000000X53.000000X611.000000最优解不唯一最优解不唯一liti1b篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比

9、球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回OBJECTIVEFUNCTIONVALUE1)26.00000VARIABLEVALUEREDUCEDCOSTX112.0000001.000000X20.0000001.000000X36.0000001.000000X42.0000001.000000X51.0000001.000000X65.0000001.000000篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回例2

10、（布线问题）解决某市消防站的布线解决某市消防站的布线问题。该城市共有问题。该城市共有6个区，每个区个区，每个区都可以建立消防站，市政府希望设置的消防站最少，但都可以建立消防站，市政府希望设置的消防站最少，但必须满足在城市任何地方发生火警时，消防车要在必须满足在城市任何地方发生火警时，消防车要在15分分钟之内赶到现场，根据实地考察，各区之间消防车行驶钟之内赶到现场，根据实地考察，各区之间消防车行驶的时间见下表的时间见下表请帮助该市制定一个最节省的计划。请帮助该市制定一个最节省的计划。篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮

11、球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回地区地区1 地区地区2地区地区3地区地区4地区地区5地区地区6地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140各区之间消防车行驶的时间表各区之间消防车行驶的时间表篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回解：每个地区是否设消防站

12、可用一个解：每个地区是否设消防站可用一个0-1变量来表示。令变量来表示。令i=1,2,6本题要求消防站的个数最少，故目标函数为：本题要求消防站的个数最少，故目标函数为：约束条件为：约束条件为：篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回时间时间123456地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140各区

13、之间消防车行驶的时间表各区之间消防车行驶的时间表约束条件为：约束条件为：篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回时间时间123456地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛

14、的的计时计分系分系统是一种得分是一种得分类型的系型的系统OBJECTIVEFUNCTIONVALUE1)2.000000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X21.0000001.000000X30.0000001.000000X41.0000001.000000X50.0000001.000000X60.0000001.000000min=x1+x2+x3+x4+x5+x6;x1+x21;x1+x2+x61;x3+x41;x3+x4+x51;x4+x5+x61;x2+x5+x61;bin(x1);bin(x2);bin(x3);bin(x4);

15、bin(x5);bin(x6);end计算程序为计算程序为求解报告为求解报告为最优方案为最优方案为x2=x4=1,即在第即在第2区和第区和第4区设置消防站即可。区设置消防站即可。liti3bin(x)-表示表示x取值为取值为0或或1篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回例3（最优装载问题）例例3（美国（美国1988年大学生建摸竞赛年大学生建摸竞赛B题题)要把七种规格的包装箱装到两辆平板车上去，箱子的要把七种规格的包装箱装到两辆平板车上去，箱子

16、的宽、高、相同，而厚度和重量不同。下表给出了他们的厚宽、高、相同，而厚度和重量不同。下表给出了他们的厚度和重量及数量。度和重量及数量。第i种箱子1234567 厚度t（厘米）48.752.061.372.048.752.064.0 重量w（千克）200030001000 5004000 2000 1000数量n8796648篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回每辆平板车有每辆平板车有10.2米的地方用于装箱，载重米的地方用于装箱，载重40吨

17、。由吨。由于货物的限制，对于第于货物的限制，对于第5、6、7三种包装箱的装载有三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过如下约束：它们所占的空间（厚度）不得超过302.7厘米，试把这些包装箱装到平板车上去，使浪费的空厘米，试把这些包装箱装到平板车上去，使浪费的空间最小。间最小。解：容易计算出所有的包装箱的厚度为解：容易计算出所有的包装箱的厚度为27.495米，而米，而两俩平板车共有两俩平板车共有20.4米长的地方，所以不可能都装上。米长的地方，所以不可能都装上。记表中所给出的第记表中所给出的第i种箱子的厚度、重量和数量分别为种箱子的厚度、重量和数量分别为ti、wi和和ni（i=

18、1,2,.,7),又记第又记第i种箱子装到第种箱子装到第1、2辆平板辆平板车上的数量分别为车上的数量分别为xi1,xi2（i=1,2,.,7)篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回第i种箱子1234567 厚度ti（厘米）48.752.061.3 72.0 48.7 52.0 64.0 重量wi(吨）2310.5421数量ni8796648篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的

19、，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回问题要求浪费的空问题要求浪费的空间最小，即装载所间最小，即装载所占的空间最大，故占的空间最大，故目标函数为：目标函数为：约束条件为：约束条件为：厚度约束：厚度约束：重量约束：重量约束：第i种箱子1234567厚度ticm48.752.061.372.048.752.064.0 重量wi(t）2310.5421数量ni8796648每辆平板车有每辆平板车有10.2米的地方用于米的地方用于装箱，载重装箱，载重40吨吨记第记第i种箱子装到第种箱子装到第1、2辆平板车上的辆平板车上的数量分别为数量分别为（i=1,2

20、,.,7)篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页 下页 返回数量约束：数量约束：特殊约束：特殊约束：或或第i种箱子1234567厚度ticm48.752.061.372.048.752.064.0 重量wi(t）2310.5421数量ni8796648第第5、6、7三种包装箱的装载有三种包装箱的装载有如下约束：它们所占的空间如下约束：它们所占的空间（厚度）不得超过（厚度）不得超过302.7厘米，厘米，(每辆平板车不每辆平板车不超过超过302.7cm)

21、篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回故得到两个整数规划模型为：故得到两个整数规划模型为：(IP1)(IP2)篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回现解第一个问题：现解第一个问题：(IP1)Liti3.ltxLiti3.txt篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少

22、来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回利用利用lindo求解得到最优解为：求解得到最优解为：平 板 车 1平 板 车 2箱子类型c1c2c3c4c5c6c7c1c2c3c4c5c6c7最优值解10 5 6 0 0 0 08 2 7 0 2 0 0 2039.4解28 5 6 0 0 0 00 2 3 6 3 3 0 2039.4解30 6 9 0 0 3 08 1 0 6 3 0 0 2039.4解45 1 9 1 2 0 03 6 0 5 1 3 0 2039.4篮球比球比赛是根据运是根据运动队在在规定的

23、比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回MAX48.7x11+48.7x12+52.0 x21+52.0 x22+61.3x31+61.3x32+72.0 x41+72.0 x42+48.7x51+48.7x52+52.0 x61+52.0 x62+64x71+64x72st48.7x11+52x21+61.3x31+72x41+48.7x51+52x61+64x71102048.7x12+52x22+61.3x32+72x42+48.7x52+52x62+64x7210242x11+

24、3x21+x31+0.5x41+4x51+2x61+x71402x12+3x22+x32+0.5x42+4x52+2x62+x7240 x11+x128x21+x227x31+x329x11+x128x21+x227x31+x329x41+x426x51+x526x61+x624x71+x72848.7x51+48.7x52+52.0 x61+52.0 x62+64.0 x71+64.0 x72302.7ENDGIN14篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的

25、系统上页下页返回 objectivefunctionvalue1)2039.400variablevaluereducedcostx115.000000-48.700001x123.000000-48.700001x211.000000-52.000000 x226.000000-52.000000 x319.000000-61.299999x320.000000-61.299999 篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回 X411.0000

26、00-72.000000X425.000000-72.000000X512.000000-48.700001X521.000000-48.700001X610.000000-52.000000X623.000000-52.000000X710.000000-64.000000X720.000000-64.000000篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统MAX=48.7*x11+48.7*x12+52.0*x21+52.0*x22+61.3*x31+61

27、.3*x32+72.0*x41+72.0*x42+48.7*x51+48.7*x52+52.0*x61+52.0*x62+64*x71+64*x72;48.7*x11+52*x21+61.3*x31+72*x41+48.7*x51+52*x61+64*x711020;48.7*x12+52*x22+61.3*x32+72*x42+48.7*x52+52*x62+64*x721024;2*x11+3*x21+x31+0.5*x41+4*x51+2*x61+x7140;2*x12+3*x22+x32+0.5*x42+4*x52+2*x62+x7240;x11+x128;x21+x227;x31+x

28、329;x41+x426;x51+x526;x61+x624;x71+x728;48.7*x51+48.7*x52+52.0*x61+52.0*x62+64.0*x71+64.0*x72302.7;gin(x11);gin(x12);gin(x21);gin(x22);gin(x31);gin(x32);gin(x41);gin(x42);gin(x51);gin(x52);gin(x61);gin(x62);gin(x71);gin(x72);END篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统

29、是一种得分是一种得分类型的系型的系统model:!平板车装载问题平板车装载问题;sets:box/1.7/:t,w,n;car/1,2/;links(box,car):x;endsets!目标函数目标函数;max=sum(links(i,j):t(i)*x(i,j);!厚度约束厚度约束;for(car(j):sum(box(i):t(i)*x(i,j)=1020;);!重量约束重量约束;for(car(j):sum(box(i):w(i)*x(i,j)=40;);!数量约束数量约束;for(box(i):x(i,1)+x(i,2)=n(i););!特殊约束特殊约束;sum(box(i)|i#g

30、e#5:t(i)*x(i,1)+t(i)*x(i,2)2x3+x5+x6+x8+x93x4+x6+x7+x922x3-x1-x20 x4-x702x5-x1-x20 x6-x70 x8-x502x9-x1-x26/5分支得两个线性分支得两个线性规划：规划：篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回和和解（解（P1)得最优解为得最优解为再将（再将（P1)利用利用x1 9/4和和x19/4进行进行分支得：分支得：篮球比球比赛是根据运是根据运动队在在规

31、定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回（s.t.)(P3)(S.t.)(P4)篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统上页下页返回解（解（P3)得最优解为得最优解为而而(P4)无可行解。无可行解。再回头解一下（再回头解一下（P2),得最优解为得最优解为比较得最优解为比较得最优解为篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多

32、少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统割平面法的基本思想：割平面法的基本思想：若整数规划若整数规划IP的松弛规划的松弛规划P0的最优解不是整数解，的最优解不是整数解，对对P0增加一个约束条件，得线性规划增加一个约束条件，得线性规划P1，此过程缩小，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划同时，保留松弛规划的任一整数解，因此整数规划IP的解均在的解均在P1中，若中，若P1的最优解为整数解，则得的最优解为整数解，则得

33、IP的最的最优解。若优解。若P1的最优解不是整数解，重复以上步骤，由的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留于可行解域在不断缩小，且保留IP所有的整数解，总所有的整数解，总可以在有限次后得到可以在有限次后得到IP的最优解的最优解.篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统割平面法由松弛问题的可行域向整数规划的可行域逼近方法利用超平面切除要求整数解保留 松弛问题最优值向最优解逼近目标得到的新的可行域的某个整数坐标的极点恰好是问题的最优解

34、篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统15.2 割平面解法v例例1 1 求解 目标函数 min z=-x1-x2 约束条件：-x1+x21 3x1+x24 (15-1)x1，x20 x1，x2 整数 47篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统v先不考虑整数约束，求得相应的线性规划的最优解为：x1=34，x2=74，

35、min z=-104 最优解是下图中域R的极点A，但不符合整数约束条件。min z=-x1-x2 约束条件：-x1+x21 3x1+x24 (15-1)x1，x20 48篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统15.2节 割平面解法v现设想，如能找到像CD那样的直线去切割域R(图5-6)，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域R的一个极点。如在域R上求解，而得到的最优解又恰巧在C点就得到原问题的整数解，所以解法的关键是怎样构造一个这样的

36、“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。图5-649篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统x1 xixmxm+1xm+jxn解x11 00y1m+1y1m+jy1nb1xi0 10yim+1yim+jyinbixm0 01ymm+1ymm+jymnbm0L0的最优单纯形表：的最优单纯形表：对应于生成行对应于生成行i的方程的方程篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因

37、此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统v(15-2.3)将bi和yik都分解成整数部分N与非负真分数f之和，即而a表示不超过a的最大整数。例如：若b=2.35，则b=2，f=0.35 若b=0.45，则b=1,f=0.55 代入(15-2.3)式得篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统将上述约束加到将上述约束加到原约束中去，得原约束中去，得到等价的整数规到等价的整数规划划篮球比球比赛是根据运是根据运动队在在规定的比定的比

38、赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统解：考虑松弛问题，并化为标准型：解：考虑松弛问题，并化为标准型：篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统Cj1-200CBXBx1x2x3x4b-2x2-1/311/302/30 x44/30-1/3110/3Z-c-1/30-2/30-4/3松弛问题最优解为松弛问题最优解为篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时

39、间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统即：即：原方程加上原方程加上上约束上约束篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统Cj1-200CBXBx1x2x3x4b-2x2-1/311/302/30 x44/30-1/3110/3Z-c-1/30-2/30-4/3篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮

40、球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统Cj1-200XBx1x2x3x4bx2-1/311/302/3x44/30-1/3110/3Z-c-1/30-2/30-4/3CBXBx1x2x3x4x5b-2x2-1/311/3002/30 x44/30-1/31010/30 x5-20-101-2Z-c-1/30-2/300-4/3对应的单纯形表为对应的单纯形表为篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统CBXBx1x2x3x4x5b-2x2-1/311/3002/30 x44/30-1/31010/30 x5-20-101-2Z-c-1/30-2/300-4/3对偶单纯形法，对偶单纯形法，x5进基进基X1退基退基CBXBx1x2x3x4x5b-2x2011/20-1/610 x400-112/321x1101/20-1/21Z-c00-1/20-1/6-1得到原问题的最优解为得到原问题的最优解为篮球比球比赛是根据运是根据运动队在在规定的比定的比赛时间里得分多少来决定里得分多少来决定胜负的，因此，的，因此，篮球比球比赛的的计时计分系分系统是一种得分是一种得分类型的系型的系统