第八章整数规划

《第八章整数规划》由会员分享，可在线阅读，更多相关《第八章整数规划（131页珍藏版）》请在金锄头文库上搜索。

1、占嫌笋垣持货瞩峪绽霸乞摧疗婴躯瞥顶小溶芹咋稠俏同人虎淑栓翻醇烛怒第八章整数规划第八章整数规划第八章第八章 整数规划整数规划Integer ProgrammingInteger Programming辕镣轰叼尉裁柴会醚堆惺蘸屠社痞拖盛涟酵敏殴晴汹雌网庞老彝副往衬讳第八章整数规划第八章整数规划第八章第八章 整数规划整数规划在前面讨论的线性规划问题中，最优解在前面讨论的线性规划问题中，最优解可能是整数，也可能不是整数，但对于可能是整数，也可能不是整数，但对于某些实际问题，要求答案必须是某些实际问题，要求答案必须是整数整数。如，如， 所求的解是安排上班的人数，所求的解是安排上班的人数， 按某个方案裁剪

2、钢材的根数，按某个方案裁剪钢材的根数， 生产机器的台数等。生产机器的台数等。钦胎连尽奔滓殉颅狗败某嘲尔职陀携罪陡豫舟怯矛募散特甜枯概掠油冻盒第八章整数规划第八章整数规划第八章第八章 整数规划整数规划n 8.1 8.1 整数规划模型整数规划模型氟冗瑰想庐液盈绳厉逮往庸郸徊缄哼按疯那淹烯瓦陶甚希菲作掣猜虐霖冕第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型整数规划模型的一般形式 Max Max（或（或MinMin） Z = Z = ccj jx xj js.t. s.t. aaijijx xj j ( ( 或或 = , ) b = , ) bi i i=1,2, i=1,2,

3、, m, m x xj j 0 0 j=1,2, j=1,2, , n, n x x1 1 , , x x2 2 , , x xn n 中部分或全部取整数中部分或全部取整数佰迈摆戍终祥敌裁界苫筒辆蛊捍双食路枕卑残摈劳宁显晒淑吝田矾授咎吼第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型在线性规划模型中在线性规划模型中 如果所有的决策变量都要求为非负整数，则这样的线性规划问题称之为纯整数规划问题。 如果只有一部分决策变量要求为非负整数，则这样的线性规划问题称之为混合整数规划问题。 如果决策变量的取值只限于 0 和 1，则这样的整数线性规划问题称之为 01型整数规划问题。邹刀掘佩

4、桶狞彝寇迸扭孪署钝蛋男蜗橡煎皖椅院枣既蠢垫婪虞挝敖茬兔阜第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型 例：例：一登山队员做登山准备，他需要一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假种物品的重要性系数和重量如下：假定登山队员可携带最大重量为定登山队员可携带最大重量为2525公斤。公斤。序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备重量重量5 55 52 26 6

5、12122 24 4重要重要系数系数20201515181814148 84 41010脱感靠哮敝厂永载害蹋奉孪悠焰渍盘叁冀跃窗呵塌列波粹颐奔硒蹭绳氓质第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型解：解： 令令x xi i=1=1表示登山队员携带物品表示登山队员携带物品i i， x xi i=0=0表示登山队员不携带物品表示登山队员不携带物品i:i:Max Z= 20xMax Z= 20x1 1+15x+15x2 2 +18x +18x3 3 +14x +14x4 4+8x+8x5 5+4x+4x6 6+10x+10x7 7s.t. 5xs.t. 5x1 1 + 5x

6、+ 5x2 2 +2x +2x3 3 +6x +6x4 4 +12x +12x5 5 +2x +2x6 6 +4x +4x7 7 2525 x xi i=1 =1 或或 x xi i=0 i=1,2,=0 i=1,2,.7.7序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备重量重量5 55 52 26 612122 24 4重要重要系数系数20201515181814148 84 41010蔑躯钡贡耗颤帖黍靳炉喧瘟碎厦缎屡箕舌踢姿疽渠嵌诵英刀酮擞卜还硫拌第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型背包问题

7、背包问题( Knapsack Problem)( Knapsack Problem) 一个旅行者一个旅行者, ,为了准备旅行的必须用品为了准备旅行的必须用品, ,要在背包要在背包内装一些最有用的东西内装一些最有用的东西, ,有限制有限制: :最多只能装b公斤的物品而每件物品只能整个携带每件物品规定了一个“价值”以表示其有用的程度如果共有n件物品,第 j 件物品aj公斤,其价值为cj. 问题变成问题变成: :在携带的物品总重量不超过在携带的物品总重量不超过b b公斤条件公斤条件下下, ,携带哪些物品携带哪些物品, ,可使总价值最大可使总价值最大? ?脏算键多铸霞鹃嗡澈卯径什吉韧夸毕念出劈扶姨荤寂

8、痘蔑侗矿酷靶康距欢第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型背包问题背包问题( Knapsack Problem)( Knapsack Problem) 解：解： 令令x xj j=1=1表示携带物品表示携带物品j, j, x xj j=0=0表示不携带物品表示不携带物品j j， Max Z = Max Z = c cj jx xj j s.t. s.t. aaj jx xj j b b x xj j=0 =0 或或 1 1驮诛囊佛瓦般憾徊龙灸仕拳木账贿坦凤曝杆局蛛玛挎沽傲元们魏震匠清屁第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型解：解： 令令

9、x xi i=1=1表示登山队员携带物品表示登山队员携带物品i i， x xi i=0=0表示登山队员不携带物品表示登山队员不携带物品i:i:Max Z= 20xMax Z= 20x1 1+15x+15x2 2 +18x +18x3 3 +14x +14x4 4+8x+8x5 5+4x+4x6 6+10x+10x7 7s.t. 5xs.t. 5x1 1 + 5x + 5x2 2 +2x +2x3 3 +6x +6x4 4 +12x +12x5 5 +2x +2x6 6 +4x +4x7 7 2525 x xi i=1 =1 或或 x xi i=0 i=1,2,=0 i=1,2,.7.7序号序号

10、1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备重量重量5 55 52 26 612122 24 4重要重要系数系数20201515181814148 84 41010昼娜殊坐庆吏帮丸弛柳唾侮步拭窗椎鼓熊疙丝绝尼罪憨匙袋慧铰租铰摆胰第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型 当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。 例

11、如，背包问题充其量有例如，背包问题充其量有 2 2n n种方式种方式 皑亡丑骄湍认辖柄书拉擞娜惧刑沤失批涎晤辩袋患当惑朝沙疗廖平怕彬鲜第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型解：解： 令令x xi i=1=1表示登山队员携带物品表示登山队员携带物品i i， x xi i=0=0表示登山队员不携带物品表示登山队员不携带物品i:i:Max Z= 20xMax Z= 20x1 1+15x+15x2 2 +18x +18x3 3 +14x +14x4 4+8x+8x5 5+4x+4x6 6+10x+10x7 7s.t. 5xs.t. 5x1 1 + 5x + 5x2 2 +

12、2x +2x3 3 +6x +6x4 4 +12x +12x5 5 +2x +2x6 6 +4x +4x7 7 2525 x xi i=1 =1 或或 x xi i=0 i=1,2,=0 i=1,2,.7.7序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备重量重量5 55 52 26 612122 24 4重要重要系数系数20201515181814148 84 41010胁售矮呕垣祈敞喜弊河并遮碧饰吕肩博屿馆楚鳖脖残忽职妓娇倦氦窃娄胸第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型 当人们开始接触整数规划问

13、题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。实际上这种方法是不可行。实际上这种方法是不可行。实际上这种方法是不可行。实际上这种方法是不可行。 设想计算机每秒能比较设想计算机每秒能比较设想计算机每秒能比较设想计算机每秒能比较1000000100000010000001000000个方式，个方式，个方式，个方式，那么要比较完那么要比较完那么要比较完那么要比较完20!20!20!20!（大于（大于（大于（大于2*102*102*102

14、*1018181818）种方式，）种方式，）种方式，）种方式，大约需要大约需要大约需要大约需要800800800800年。年。年。年。那么要比较完比较完那么要比较完比较完那么要比较完比较完那么要比较完比较完2 2 2 26060种方式，种方式，种方式，种方式，大约需要大约需要大约需要大约需要360360360360世纪世纪世纪世纪 许巍俘张没亩骤朴锋沤榜梨台瞥灿琵疤痉喂厅给支协邢盲戒难躯愧猾犁贱第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型 当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目

15、有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。2.2.先放弃变量的整数性要求，解一个线性先放弃变量的整数性要求，解一个线性规划问题，然后用规划问题，然后用“四舍五入四舍五入”法取整法取整数解。数解。幼减聘奖爽喉销隙茹粕瞒坞弄弱锰抵试区梭制瘴步吏卜剿宗皂奎幸客缮说第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型例例. . 某公司拟用集装箱托运甲、乙两种货物，这两种货某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如下物每件的体积、重量，可获利润以及托运所受限制如下表所示，甲种货物

16、至多托运表所示，甲种货物至多托运 4 4 件，问两种货物各托运多件，问两种货物各托运多少件，可使获得利润最大。少件，可使获得利润最大。货物货物每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲1951954 42 2乙乙27327340403 3托运限制托运限制13651365140140竣丁掇拥摩挡区佩撵伴骋券筹淌维斡边郊公断殉田闹萤卫锅剿厄愧钥账虑第八章整数规划第八章整数规划货物货物每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲1951954 42 2乙乙2732

17、7340403 3托运限制托运限制13651365140140解：解：设设 x x1 1、x x2 2 分别为甲、乙两种货物托运的件数，显然分别为甲、乙两种货物托运的件数，显然 x x1 1、x x2 2 应该是非负整数，该问题的数学模型如下所示：应该是非负整数，该问题的数学模型如下所示： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0

18、 x x1 1，x x2 2 为整数。为整数。钾调欠门梢泽虚梢折巳翌坟耐佣格破途坯傈囊荫柬呕草九究违盼涝阔靖烽第八章整数规划第八章整数规划解：设解：设 x x1 1、x x2 2 分别为甲、乙两种货物托运的件数，显然分别为甲、乙两种货物托运的件数，显然 x x1 1、x x2 2 应该是非负整数，该问题的数学模型如下所示：应该是非负整数，该问题的数学模型如下所示： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2

19、2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0 x x1 1，x x2 2 为整数。为整数。如果将上述整数线性规划中的最后一个约束：如果将上述整数线性规划中的最后一个约束： x1、x2 为整数为整数去掉，它就是一个去掉，它就是一个线性规划线性规划的问题。的问题。用用图解法图解法来解这个整数规划，来解这个整数规划，以及与它相应的线性规划问题，以及与它相应的线性规划问题，并把它们的最优解加以比较。并把它们的最优解加以比较。孜敌瑰袋窗脾拿捕婪翼枚舍膝捏破顿室眩嫡垒黄纲醚证貌爽磕荤犹统付厘第八章整数规划第八章整数规划 max max z z = 2 = 2x x1 1 +

20、 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 01234123x2x12x1+3x214.66做君扭瞅训浓保饭餐磕胎讣供滇汛力姿纫洱奶搭槐训甜禾存靴苞围褪悠臂第八章整数规划第八章整数规划 max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 +

21、 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 01234123x2x1平移目标函数的等值线，平移目标函数的等值线，得线性规划的得线性规划的最优解最优解为为 x x1 12.442.44，x x2 23.263.26，目标函数的最优值为目标函数的最优值为14.6614.66。2x1+3x214.66贤吃类畅昨呼危立炯烂斥根逻为功柒线棵幢磷兢硒苇峰儒迟总农喊宠轧痒第八章整数规划第八章整数规划 max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x

22、x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0 x x1 1，x x2 2 为整数为整数1234123x2x12 2x x1 1+3+3x x2 214.6614.662 2x x1 1+3+3x x2 21414同样把目标函数的同样把目标函数的等值线等值线尽量向右上方移尽量向右上方移以便取得最大值，同时又必须过整数规划以便取得最大值，同时又必须过整数规划的的可行点可行点，可得整数规划的最优解，可得整数规划的最优解 x x1 14 4，x x2 22 2，这时其最优目标函数值为这时其最优

23、目标函数值为1414。局畅扫圆绎爪栈犊陇眯蛀太到锄尺誓凤拼豹秤氧铜送洱族或牧峙妖掷柞床第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型当我们对相应的线性规划的当我们对相应的线性规划的最优解最优解进行进行四舍五入或去尾法四舍五入或去尾法时，得时，得 x x1 12 2，x x2 23 3，这时目标函数值为，这时目标函数值为 1313，并不是此，并不是此整数规划的最优解。整数规划的最优解。当我们对相应的线性规划的最优解进行进一法时，当我们对相应的线性规划的最优解进行进一法时，取取 x x1 13 3， x x2 23 3； x x1 12 2， x x2 2 4 4； x x1

24、 13 3，x x2 24 4 都不是此整数规划的可行解。都不是此整数规划的可行解。线性规划的最优解线性规划的最优解 x x1 12.442.44，x x2 23.263.26，最优值为最优值为 14.6614.66整数规划的最优解整数规划的最优解 x x1 14 4 ，x x2 22 2，最优值为最优值为 1414囤要帖幻争栓肛吝但挚快茵硬睛佃启显支铅护明宰鼠豆呕敷祖新韦敢榷覆第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型 当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目有限，因此经过一

25、一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。2.2.先放弃变量的整数性要求，解一个线性先放弃变量的整数性要求，解一个线性规划问题，然后用规划问题，然后用“四舍五入四舍五入”法取整法取整数解。数解。 这个这个整数规划的最优解整数规划的最优解并不可以将它对并不可以将它对应的应的线性规划的不为整数的最优解线性规划的不为整数的最优解进行进行四舍五入法或去尾法或进一法而得到的四舍五入法或去尾法或进一法而得到的。侩秽让博痒阉踊盯蔼尿青英挖颊宴粮随敷窍刹釜抱章猛页男搪茹雍铡毙龚第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型 当人们开始接触整数

26、规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。2.2.先放弃变量的整数性要求，解一个线性先放弃变量的整数性要求，解一个线性规划问题，然后用规划问题，然后用“四舍五入四舍五入”法取整法取整数解。数解。结论：结论：求解整数规划问题必须要有自己的解法。求解整数规划问题必须要有自己的解法。秘萎臣酪驴释深材叼梯郭帕滴准栖点饮橇壤空宵迸汰厂刚映胸延踩百极诛第八章整数规划第八章整数规划8.1 8.1 整数规划模型整数规划模型任何求任何求最

27、大目标函数值最大目标函数值的纯整数的纯整数规划或混合整数规划的最大目标规划或混合整数规划的最大目标函数值，函数值，小于或等于小于或等于相应的线性相应的线性规划的规划的最大目标函数值最大目标函数值；任何求任何求最小目标函数值最小目标函数值的纯整数的纯整数规划或混合整数规划的最小目标规划或混合整数规划的最小目标函数值，函数值，大于或等于大于或等于相应的线性相应的线性规划的规划的最小目标函数值最小目标函数值。哟衡煮摸耻高付胖榔阑邱剩殆贪余膊趣涎基睁瞥济稳鳖宣危烦矗欧脾毒辞第八章整数规划第八章整数规划 max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s

28、.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0 x x1 1，x x2 2 为整数为整数1234123x2x12 2x x1 1+3+3x x2 214.6614.662 2x x1 1+3+3x x2 21414A AB B扦脖沥和孪团沤衡芋决裕灼甄枝诀头馋襄倔筷嘶漆落梅烛醇执谜避光驳吃第八章整数规划第八章整数规划第八章第八章 整数规划整数规划n 8.1 8.1 整数规划模型整数规划模型n 8.2 8.2 整数规划的应用整数规划的应

29、用蜗架脑剑淖篙陆执烘承鲜或炼隋舍掏发渣礼倘农吓纂冲耍揽簇涂杆讣屹宽第八章整数规划第八章整数规划8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择溢滤魁星编帚婶迂蝶操浩阶嘿晰嗜迄厅哦枯解浮凰丧丝期鄂抨铺荔逢桂乌第八章整数规划第八章整数规划例例 京成畜产品公司计划在市区的东、西、南、北四区建立京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有销售门市部，拟议中有 10 10 个位置个位置 A Aj j ( ( j j 1 1，2 2，3 3，10 ) 10 ) 可供选择，考虑到各地区居民的消费水平及居民可供选择，考虑到各地区居民的消费水平及居民居住密

30、集度，规定：居住密集度，规定：在东区从在东区从 A A1 1 ， A A2 2 ，A A3 3 三个点中至多选择两个；三个点中至多选择两个；在西区从在西区从 A A4 4 ， A A5 5 两个点中至少选一个；两个点中至少选一个；在南区从在南区从 A A6 6 ， A A7 7 两个点中至少选一个；两个点中至少选一个；在北区从在北区从 A A8 8 ， A A9 9 ， A A1010 三个点中至少选两个。三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不各点的设备投资及每年可获利润由于地点不同都是不一样的。但投资总额不能超过一样的。但投资总额不能超过 720 万元，问

31、应选择哪几个万元，问应选择哪几个销售点，可使年利润为最大销售点，可使年利润为最大?储班据肝嚷扛歹值陨郡恨况困严抡旅贯节炳主类徊澜拘怔异落舅醛杭袖唉第八章整数规划第八章整数规划8.2 8.2 整数规划的应用整数规划的应用AT&TAT&T公司（美国电信电报公司）公司商业用户服务的电话销售中心的优化选址公司商业用户服务的电话销售中心的优化选址1 1用户规划及特征用户规划及特征2 2竞争对手竞争对手3 3地理位置地理位置4 4成本的核算成本的核算5 5交通状况交通状况 6 6经营场地面积经营场地面积英叭评拂峦勺看墨炭菩宿砸襟柞袜瘁实慌基肇嚣浸酬城钱窍堆痉次翅蕉逢第八章整数规划第八章整数规划例例 京成畜

32、产品公司计划在市区的东、西、南、北四区建立京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有销售门市部，拟议中有 10 10 个位置个位置 A Aj j ( ( j j 1 1，2 2，3 3，10 ) 10 ) 可供选择，考虑到各地区居民的消费水平及居民可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：居住密集度，规定：在东区从在东区从 A A1 1 ， A A2 2 ，A A3 3 三个点中至多选择两个；三个点中至多选择两个；在西区从在西区从 A A4 4 ， A A5 5 两个点中至少选一个；两个点中至少选一个；在南区从在南区从 A A6 6 ， A A7 7

33、 两个点中至少选一个；两个点中至少选一个；在北区从在北区从 A A8 8 ， A A9 9 ， A A1010 三个点中至少选两个。三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不各点的设备投资及每年可获利润由于地点不同都是不一样的。但投资总额不能超过一样的。但投资总额不能超过 720 万元，问应选择哪几个万元，问应选择哪几个销售点，可使年利润为最大销售点，可使年利润为最大?菌寨袁虚奎丸槛猎凶抠弛怒谣豁腋涸握涩吟乃检床腺詹庇予邑绥岭获选原第八章整数规划第八章整数规划解：设：解：设：01 变量变量 xi = 1， 当当 Ai 点被选用时；点被选用时； xi = 0 ，当

34、当 Ai 点没点没被选用时。被选用时。max max z z = 36 = 36x x1 1 + 40+ 40x x2 2 + 50+ 50x x3 3 + 22+ 22x x4 4 + 20+ 20x x5 5 + 30 + 30x x6 6 + 25+ 25x x7 7 + 48+ 48x x8 8 + 58+ 58x x9 9 + 61+ 61x x1010s. t. 100s. t. 100x x1 1+120+120x x2 2+150+150x x3 3+80+80x x4 4+70+70x x5 5+90+90x x6 6 +80 +80x x7 7+140+140x x8 8+

35、160+160x x9 9 +180 +180x x1010 720 720 x x1 1 + + x x2 2 + + x x3 3 2 2x x4 4 + + x x5 5 1 1 x x6 6 + + x x7 7 1 1 x x8 8 + + x x9 9 + + x x1010 2 2x xj j 0 0 ，且，且 x xj j 为为 0 01 1 变量，变量，j j = 1= 1，2 2，1010。用用 “管理运筹学软件包管理运筹学软件包” 中的中的 0 01 1 整数规划程序整数规划程序求解得：求解得： max max z z = 245= 245； x x1 1 = = x x

36、2 2 = = x x5 5 = = x x6 6 = = x x9 9 = = x x1010 = 1 = 1，其余为，其余为 0 0 。滩版痪梭厨杭牧靖穿暇鞠税域帅容瓤狱沦瘸愉选锁寂龚隶顽岗味蔑胰溶荷第八章整数规划第八章整数规划8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择二、固定成本问题二、固定成本问题指日断啮历乏基淀心消霜抚汰鸟孔靶吼铬向仆殷去梦扶孜泻篡彬坝眩宗蓬第八章整数规划第八章整数规划例例 高压容器公司制造小、中、大三种尺寸的金属容器，高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所所用资源为金属板

37、、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示。不考虑固定费用，每种需的各种资源的数量如下表所示。不考虑固定费用，每种容器售出一只所得的利润分别为容器售出一只所得的利润分别为 4 4 万元、万元、5 5 万元、万元、6 6 万元，万元，可使用的金属板有可使用的金属板有 500 500 吨，劳动力有吨，劳动力有 300 300 人月，机器有人月，机器有 100 100 台月，此外不管每种容器制造的数量是多少，台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是都要支付一笔固定的费用：小号是 l00 l00 万元，中号为万元，中号为 150 150 万元，大号为万

38、元，大号为 200 200 万元万元。现在要制定一个生产计划，使获。现在要制定一个生产计划，使获得的利润为最大。得的利润为最大。 贱烙予树乏旅虚椅融勺羽郴阜磋轿吹透嚷奏膏匡瓢灯厘茁稀纵磐噎杰属卿第八章整数规划第八章整数规划固定成本问题固定成本问题“不管每种容器制造的数量是多少，都要支付一笔固不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是定的费用：小号是 l00 l00 万元，中号为万元，中号为 150 150 万元，万元，大号为大号为 200 200 万元。万元。”解：这是一个整数规划问题。解：这是一个整数规划问题。设设 x x1 1，x x2 2， x x3 3 分别为小号容器

39、、中号容器和大号容分别为小号容器、中号容器和大号容器的生产数量。器的生产数量。各种容器的固定费用只有在生产该种容器时才投入各种容器的固定费用只有在生产该种容器时才投入，即即 y yi i = 1 = 1， 当生产第当生产第 i i 种容器，即种容器，即 x xi i 0 0 时；时； y yi i = 0 = 0， 当不生产第当不生产第 i i 种容器，即种容器，即 x xi i = 0 = 0 时。时。蔗惺头柄芯踌帽堑重因午儡欣曳耙玫介措随风抿码哦攫舟称线脖槐绕娟占第八章整数规划第八章整数规划可建立如下的数学模型：可建立如下的数学模型： max max z z = 4= 4x x1 1 +

40、5+ 5x x2 2 + 6+ 6x x3 3 - 100- 100y y1 1 - 150- 150y y2 2 - - 200200y y3 3 s. t. 2 s. t. 2x x1 1 + 4+ 4x x2 2 + 8+ 8x x3 3 500 500 2 2x x1 1 + 3+ 3x x2 2 + 4+ 4x x3 3 300 300 x x1 1 + 2+ 2x x2 2 + 3+ 3x x3 3 100 100 x xi i M M y yi i ，i i =1=1，2 2，3 3，x xj j 0 0，且为整数，且为整数，y yj j 为为 0 01 1 变量，变量，j j

41、= 1= 1，2 2，3 3。M 充分大，以保证当充分大，以保证当 yi = 0 时时，xi = 0 。洋落搽糯阔眶悔簇郑黄哩玲贴男搓库毡洲陷习丑纵槐余玻览糜焰凌矮护耻第八章整数规划第八章整数规划8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择二、固定成本问题二、固定成本问题三、指派问题三、指派问题提脂伤欣宫甲宠酪鳖俩茎钙降涪揉鹰下重搁壁俯茨构梳鞠蔡渠亨迷先闺淘第八章整数规划第八章整数规划例例. .有四个工人，要分别指派他们完成四项不同的工作，有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指每人做各项工作所消耗的时间

42、如下表所示，问应如何指派工作，才能使总的消耗时间为最少。派工作，才能使总的消耗时间为最少。指派问题指派问题构襄蓄蓟项液疹阀朴虱热码澈催鬃咳空蝶明矣逢疏础娃句毅抵疹旋梢誊槐第八章整数规划第八章整数规划解：解：引入引入 0 01 1 变量变量 x xijij，并令，并令 x xij ij = 1= 1， 当指派第当指派第 i i 人去完成第人去完成第 j j 项工项工作时；作时； x xij ij = 0= 0， 当不指派第当不指派第 i i 人去完成第人去完成第 j j 项项工作时。工作时。这样该问题即被表示成一个这样该问题即被表示成一个 0 01 1 整数规划问题整数规划问题：min min

43、z z =15 =15x x1111+18+18x x1212+21+21x x1313+24+24x x1414+19+19x x2121+23+23x x2222+22+22x x2323+18+18x x24 24 +26+26x x31 31 +17+17x x3232+16+16x x3333+19+19x x3434+19+19x x41 41 +21+21x x4242+23+23x x4343+17+17x x4444滤幽痰禽尸疹吾拴攀缓梧豁山段涣性孟监绰职荡薄泉搏颊赘剑狸锭纹豹揪第八章整数规划第八章整数规划s. t.s. t.x x1111+ + x x1212+ + x x

44、1313+ + x x1414= 1 (= 1 (甲只能干一项工作甲只能干一项工作) ) x x2121+ + x x2222+ + x x2323+ + x x2424= 1 (= 1 (乙只能干一项工乙只能干一项工作作) ) x x3131+ + x x3232+ + x x3333+ + x x3434= 1 (= 1 (丙只能干一项工丙只能干一项工作作) ) x x4141+ + x x4242+ + x x4343+ + x x4444= 1 (= 1 (丁只能干一项工丁只能干一项工作作) ) x x1111+ + x x2121+ + x x3131+ + x x4141= 1 (

45、 A= 1 ( A工作只能一人干工作只能一人干) ) x x1212+ + x x2222+ + x x3232+ + x x4242= 1 ( B= 1 ( B工作只能一人干工作只能一人干) ) x x1313+ + x x2323+ + x x3333+ + x x4343= 1 ( C= 1 ( C工作只能一人干工作只能一人干) ) x x1414+ + x x2424+ + x x3434+ + x x4444= 1 ( D= 1 ( D工作只能一人干工作只能一人干) ) x xijij 为为 0 01 1 变量，变量，i i，j j = 1= 1，2 2，3 3，4 4。求解得求解得

46、: : min min z z = 70= 70； x x2121=1=1， x x1212 = 1 = 1，x x3333 = 1 = 1， x x4444 = 1 = 1 。计焦俊直铆翟珊费攻跺驹柑灿磨日矗彦痰雾途琼洗域遏佣服蛰骤敷佛啮气第八章整数规划第八章整数规划例例. .有四个工人，要分别指派他们完成四项不同的工作，有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。派工作，才能使总的消耗时间为最少。指派问题指派问题鲍条泣吻简涤巍谴口纺揩巢矽滨婶朽桂烽蹈荐瞄甩纳妆

47、稽卖筒砌耙弟振仙第八章整数规划第八章整数规划8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择二、固定成本问题二、固定成本问题三、指派问题三、指派问题四、分布系统设计四、分布系统设计缓刹避孵锚瞳继卫祥暇绑抉候啮离廖件叮技执乳券矿效陆匣殊巧予园椿免第八章整数规划第八章整数规划例例某企业在某企业在 A A1 1 地已有一个工厂，其产品的生产能力为地已有一个工厂，其产品的生产能力为 30 30 千箱，千箱，为了扩大生产，打算在为了扩大生产，打算在 A A2 2，A A3 3，A A4 4，A A5 5 地中再选择几个地方建厂。地中再选择几个地方建厂。已知在已知在 A A

48、2 2 ， A A3 3，A A4 4，A A5 5 地建厂的固定成本分别为地建厂的固定成本分别为 175 175 千元、千元、300 300 千元、千元、375 375 千元、千元、500 500 千元，另外，千元，另外， A A1 1 产量及产量及 A A2 2，A A3 3，A A4 4，A A5 5 建建成厂的产量，那时销地的销量以及产地到销地的单位运价成厂的产量，那时销地的销量以及产地到销地的单位运价( (每千箱每千箱运费运费) )如下表所示。如下表所示。 a) a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和

49、总的运输费用之和最小的固定成本和总的运输费用之和最小? ? b) b) 如果由于政策要求必须在如果由于政策要求必须在 A A2 2，A A3 3 地建一个厂，应在哪几个地地建一个厂，应在哪几个地方建厂方建厂? ? 蔡圾鸯箔缓于沥死逐寝流咋还污瘁周追哎郸鞠钥峭基谬鸯湿含篆哦芍鄙百第八章整数规划第八章整数规划解：解： a) 设设 xij 为从为从 Ai 运往运往 Bj 的运输量的运输量(单位千箱单位千箱)， yk = 1，当当 Ak 被选中时；被选中时； yk = 0，当当 Ak 没被选中时，没被选中时， k =2，3，4，5。这样我们的问题可以被表示成一个这样我们的问题可以被表示成一个(混合混合

50、)整数规划问题整数规划问题: :矢锌绘跋凶谈旱屡彼莲鞍掩犁嫡娟晨祸铆参武换搂卓多挥催涯讼莱栽忍搐第八章整数规划第八章整数规划minmin z z = 175 = 175y y2 2+300+300y y3 3+375+375y y4 4+500+500y y5 5 + 8+ 8x x1111+4+4x x1212+3+3x x1313 +5+5x x2121+2+2x x2222+3+3x x23 23 +4+4x x3131+3+3x x3232+4+4x x3333 +9+9x x41 41 +7+7x x4242+5+5x x4343 +10+10x x51 51 +4+4x x5252

51、+2+2x x5353 s. t. s. t. x x1111+ + x x1212+ + x x1313 30 ( A 30 ( A1 1 厂的厂的产量限制产量限制) ) x x2121+ + x x2222+ + x x2323 10 10y y2 2 ( A ( A2 2 厂的厂的产量限制产量限制) ) x x3131+ + x x3232+ + x x33 33 20 20y y3 3 ( A ( A3 3 厂的厂的产量限制产量限制) ) x x4141+ + x x4242+ + x x43 43 30 30y y4 4 ( A ( A4 4 厂的厂的产量限制产量限制) ) x x5

52、151+ + x x5252+ + x x53 53 40 40y y5 5 ( A ( A5 5 厂的厂的产量限制产量限制) ) x x1111+ + x x2121+ + x x3131+ + x x41 41 + + x x51 51 = 30 ( B= 30 ( B1 1 销地销地的限制的限制) ) x x1212+ + x x2222+ + x x3232+ + x x42 42 + + x x52 52 = 20 ( B= 20 ( B2 2 销地的销地的限制限制) ) x x1313+ + x x2323+ + x x3333+ + x x43 43 + + x x53 53 =

53、 20 ( B= 20 ( B3 3 销地的销地的限制限制) ) x xijij 0 0，且为整数，且为整数，i i = 1= 1，2 2，3 3，4 4，5 5； j j = 1= 1，2 2，3 3， y yk k 为为 0 01 1 变量，变量，k k = 2= 2，3 3，4 4，5 5。闷致屠颊隋绣惕骚撬猴嗜闽哈舔贫搭度曝宽蛀刚转汽限起职坊卡豫靛人咨第八章整数规划第八章整数规划minmin z z = 175 = 175y y2 2+300+300y y3 3+375+375y y4 4+500+500y y5 5 + 8+ 8x x1111+4+4x x1212+3+3x x131

54、3 +5+5x x2121+2+2x x2222+3+3x x23 23 +4+4x x3131+3+3x x3232+4+4x x3333 +9+9x x41 41 +7+7x x4242+5+5x x4343 +10+10x x51 51 +4+4x x5252+2+2x x5353 s. t. s. t. x x1111+ + x x1212+ + x x1313 30 ( A 30 ( A1 1 厂的厂的产量限制产量限制) ) x x2121+ + x x2222+ + x x2323 10 10y y2 2 ( A ( A2 2 厂的厂的产量限制产量限制) ) x x3131+ +

55、x x3232+ + x x33 33 20 20y y3 3 ( A ( A3 3 厂的厂的产量限制产量限制) ) x x4141+ + x x4242+ + x x43 43 30 30y y4 4 ( A ( A4 4 厂的厂的产量限制产量限制) ) x x5151+ + x x5252+ + x x53 53 40 40y y5 5 ( A ( A5 5 厂的厂的产量限制产量限制) ) x x1111+ + x x2121+ + x x3131+ + x x41 41 + + x x51 51 = 30 ( B= 30 ( B1 1 销地销地的限制的限制) ) x x1212+ + x

56、 x2222+ + x x3232+ + x x42 42 + + x x52 52 = 20 ( B= 20 ( B2 2 销地的销地的限制限制) ) x x1313+ + x x2323+ + x x3333+ + x x43 43 + + x x53 53 = 20 ( B= 20 ( B3 3 销地的销地的限制限制) ) x xijij 0 0，且为整数，且为整数，i i = 1= 1，2 2，3 3，4 4，5 5； j j = 1= 1，2 2，3 3， y yk k 为为 0 01 1 变量，变量，k k = 2= 2，3 3，4 4，5 5。俐勉骡厨顺划骸慨勒择斩藻腐谍领筏隅壬

57、奋坯广夸胯剧西冉牛安抽镁篇聂第八章整数规划第八章整数规划分布系统设计分布系统设计ReynoldsReynolds金属制品公司金属制品公司 200200多个工厂、仓库和供应商的货多个工厂、仓库和供应商的货物装载调度系统的自动化物装载调度系统的自动化叁苹筏碎媒嫂聊竟抚间胡润毕丝硕借埔谜啃乱挡术驶室恬脑岛粪酷光久澈第八章整数规划第八章整数规划01 01 整数规划整数规划DeltaDelta航空公司航空公司 超过超过25002500个国内航线的飞机类型配置个国内航线的飞机类型配置 以达到利润最大化以达到利润最大化请尊先专匿阳逊榷劣龟喳憋需朴分伙楷硝迪靴瞄耍玲浸壤骚赞攒委菠宜御第八章整数规划第八章整数规

58、划8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择二、固定成本问题二、固定成本问题三、指派问题三、指派问题四、分布系统设计四、分布系统设计五、投资问题五、投资问题 -P183 -P183 案例案例9 9竹捧与意情屁诲哥询深屉冉巾枫洪蛾撑侦午肾组帜双枯挛掖秃票苟僻券令第八章整数规划第八章整数规划案例案例9 9：华南公司投资方案：华南公司投资方案设设 X Xij ij 为第为第 i i 年在第年在第 j j 方案上的投资额，方案上的投资额，例如例如X X2121表示在第二年投资在项目表示在第二年投资在项目A A1 1上的金额上的金额Y Yijij=1=1，当第，当第

59、 i i 年给第年给第 j j 项目投资时，项目投资时，Y Yijij=0=0，当第，当第 i i 年不给第年不给第 j j 项目投资时。项目投资时。因此第一年投资在项目因此第一年投资在项目A A1 1上的金额上的金额X X1111可表示为可表示为: X: X1111220Y220Y1111胺貉葵蛛剥鹊殉舅掀剐敷灭腿厩刀井赶汰蔑倦诸辉漓襟坤寞誉坍蜕宵仍孰第八章整数规划第八章整数规划A A1 1：建立彩色印刷厂，第一、二年年初分别投入：建立彩色印刷厂，第一、二年年初分别投入220220万元万元和和220220万元，第二年年底可获利万元，第二年年底可获利6060万元，第三年起每年获万元，第三年起每

60、年获利利130130万元万元X X1111-220Y-220Y1111=0 =0 （A A1 1 第一年初投入第一年初投入220220万元）万元）X X2121-220Y-220Y2121=0 =0 （A A1 1 第二年初投入第二年初投入220220万元）万元）Y Y1111-Y-Y2121=0 =0 （A A1 1 第一、二年都要投入）第一、二年都要投入）赏傲牡助笔怕蛆柳惩砖檀捍险喀材非断赠晓砍舱词铝旗嘴赢普橙胳霹仰余第八章整数规划第八章整数规划A A2 2：投资离子镀膜基地，第一年投资：投资离子镀膜基地，第一年投资7070万元，第二年起万元，第二年起每年可获利每年可获利5050万元万元X

61、 X1111-220Y-220Y1111=0 =0 （A A1 1 第一年初投入第一年初投入220220万元）万元）X X2121-220Y-220Y2121=0 =0 （A A1 1 第二年初投入第二年初投入220220万元）万元）Y Y1111-Y-Y2121=0 =0 （A A1 1 第一、二年都要投入）第一、二年都要投入）X X1212-70Y-70Y1212=0 =0 （A A2 2 第一年初投入第一年初投入7070万元）万元）涵珐拔胆踌悲愁嗡自泊陇役佬威潦景适肪锻涎添茬镊寂豹崭厌返徽室委奢第八章整数规划第八章整数规划A A3 3：投资参股：投资参股F F企业，第二年投入企业，第二年

62、投入180180万元设备，第三年万元设备，第三年起每年可获利起每年可获利5050万元万元X X1111-220Y-220Y1111=0 =0 （A A1 1 第一年初投入第一年初投入220220万元）万元）X X2121-220Y-220Y2121=0 =0 （A A1 1 第二年初投入第二年初投入220220万元）万元）Y Y1111-Y-Y2121=0 =0 （A A1 1 第一、二年都要投入）第一、二年都要投入）X X1212-70Y-70Y1212=0 =0 （A A2 2 第一年初投入第一年初投入7070万元）万元）X X2323-180Y-180Y2323=0 =0 （A A3 3

63、 第二年初投入第二年初投入180180万元）万元）硫棉墒灰性霓转承妨至锚键国辟泄卧非嫁吝拓腥良吩贡掳角富读叛棱泪淘第八章整数规划第八章整数规划A A4 4：投资：投资D D企业，每年年底可获投资额的企业，每年年底可获投资额的2525利润，但是利润，但是第一年最高投资额为第一年最高投资额为 80 80 万元，以后每年递增不超过万元，以后每年递增不超过 15 15 万元。万元。X X1111-220Y-220Y1111=0 =0 （A A1 1 第一年初投入第一年初投入220220万元）万元）X X2121-220Y-220Y2121=0 =0 （A A1 1 第二年初投入第二年初投入220220

64、万元）万元）Y Y1111-Y-Y2121=0 =0 （A A1 1 第一、二年都要投入）第一、二年都要投入）X X1212-70Y-70Y1212=0 =0 （A A2 2 第一年初投入第一年初投入7070万元）万元）X X2323-180Y-180Y2323=0 =0 （A A3 3 第二年初投入第二年初投入180180万元）万元）X X141480 80 （A A4 4 第一年最高为第一年最高为 80 80 万元）万元）X X2424-X-X141415 15 （A A4 4每年递增不超过每年递增不超过 15 15 万元）万元）X X3434-X-X242415 15 （A A4 4每年

65、递增不超过每年递增不超过 15 15 万元）万元）X X4444-X-X343415 15 （A A4 4每年递增不超过每年递增不超过 15 15 万元）万元）X X5454-X-X444415 15 （A A4 4每年递增不超过每年递增不超过 15 15 万元）万元）消轮鲜残嚷脓胜镶舔递月锦蝴傣工翻缩玫策荆筹橡唯诵弯籽浓墒茸硷蒋褐第八章整数规划第八章整数规划A A5 5：建立细骨粉生产线，第三年投入：建立细骨粉生产线，第三年投入320320，第四年起每年，第四年起每年可获利可获利9090万元。万元。X X1111-220Y-220Y1111=0 =0 X X2121-220Y-220Y212

66、1=0=0Y Y1111-Y-Y2121=0=0X X1212-70Y-70Y1212=0=0X X2323-180Y-180Y2323=0=0X X14148080X X2424-X-X14141515X X3434-X-X24241515X X4444-X-X34341515X X5454-X-X44441515X X3535-320Y-320Y3535=0 =0 (A(A5 5 第一年初投入第一年初投入220220万元万元) )肚跨胖丧毛浓葡蛋嘿芬草勤亥认接锁频肆贴织躇采耪荧怜棋宙囊需孟汁塌第八章整数规划第八章整数规划A A6 6：投资所属中北机电设备公司，年底回收本利：投资所属中北机电

67、设备公司，年底回收本利120120。但每年投资额不低于但每年投资额不低于6060万元。万元。X X1111-220Y-220Y1111=0 =0 X X2121-220Y-220Y2121=0=0Y Y1111-Y-Y2121=0=0X X1212-70Y-70Y1212=0=0X X2323-180Y-180Y2323=0=0X X14148080X X2424-X-X14141515X X3434-X-X24241515X X4444-X-X34341515X X5454-X-X44441515X X3535-320Y-320Y3535=0 =0 (A(A5 5 第一年初投入第一年初投入2

68、20220万元万元) )X X161660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）X X262660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）X X363660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）X X464660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）X X565660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）磊牧徐吕桑连前炽断渤贮诛摊批峦符躬镑灿慧硕躇寂辙岁教残咨蔬蛇貉影第八章整数规划第八章整数规划A A7 7：投资所属澳得技术公司

69、，年底回收本利：投资所属澳得技术公司，年底回收本利115115。X X1111-220Y-220Y1111=0 =0 X X2121-220Y-220Y2121=0=0Y Y1111-Y-Y2121=0=0X X1212-70Y-70Y1212=0=0X X2323-180Y-180Y2323=0=0X X14148080X X2424-X-X14141515X X3434-X-X24241515X X4444-X-X34341515X X5454-X-X44441515X X3535-320Y-320Y3535=0 =0 (A(A5 5 第一年初投入第一年初投入220220万元万元) )X

70、X161660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）X X262660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）X X363660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）X X464660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）X X565660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）烟游栋邵肥面樱啪阁哼靛渔凑浩咱颈诀答乃男点很胺栖悼缕勾鲍飘矩痈套第八章整数规划第八章整数规划一、项目资金约束一、项目资金约束X X1111-220Y-22

71、0Y1111=0 =0 X X2121-220Y-220Y2121=0=0Y Y1111-Y-Y2121=0=0X X1212-70Y-70Y1212=0=0X X2323-180Y-180Y2323=0=0X X14148080X X2424-X-X14141515X X3434-X-X24241515X X4444-X-X34341515X X5454-X-X44441515X X3535-320Y-320Y3535=0=0X X16166060X X26266060X X36366060X X46466060X X56566060晨葵葬虚捐湃潞腕踪鹤耳债誉宦出若邹裴亿淌尼蔽粟式牢裙赚拉扛

72、谗朗颂第八章整数规划第八章整数规划一、项目资金约束一、项目资金约束二、年度资金约束二、年度资金约束债处联陪梧坪篱蚜织叶众帆竞曳地议术哑碌危深牟乳阂先耪脖噶筑摊辜票第八章整数规划第八章整数规划投资总额为投资总额为800800万元，其中第一年万元，其中第一年350350万，第二年万，第二年300300万，万，第三年第三年150150万万第一年：第一年： X X1111+X+X1212+X+X1414+X+X1616+X+X1717= 350= 350第二年：第二年： X X2121+X+X2323+X+X2424+X+X2626+X+X27 27 = 0.25X = 0.25X1414+1.2X+

73、1.2X1616+1.15X+1.15X1717+300+300第三年第三年: X: X3434+X+X3535+X+X3636+X+X3737 = 60Y = 60Y1111+18Y+18Y1212+0.25X+0.25X2424+1.2X+1.2X2626+1.15X+1.15X2727+150+150第四年第四年: X: X4444+X+X4646+X+X4747 =130Y =130Y1111+18 Y+18 Y1212+50Y+50Y2323+0.25X+0.25X3434+1.2X+1.2X3636+1.15X+1.15X3737第五年第五年: X: X5454+X+X5656+X

74、+X5757 = 130Y = 130Y1111+18Y+18Y1212+50Y+50Y2323+0.25X+0.25X4444+90Y+90Y3535+1.2X+1.2X4646+1.15X+1.15X4747盾凌胎澳枕参蕴禄烬召剂则磺稼抨抱爸渐肤敲露桨馋各想巧茅鹅椭戮推旬第八章整数规划第八章整数规划一、项目资金约束一、项目资金约束二、年度资金约束二、年度资金约束三、目标函数三、目标函数须刃陨渔筐钱楚米傲铃布滔诵撂内侠毫绢惰嚷撵洞千狐默掉扬涤倡腥浊龟第八章整数规划第八章整数规划A A1 1：建立彩色印刷厂，第一、二年年初分别投入：建立彩色印刷厂，第一、二年年初分别投入220220万元和万元和

75、220220万万元，第二年年底可获利元，第二年年底可获利6060万元，万元，第三年起每年获利第三年起每年获利130130万元万元; ;A A2 2：投资离子镀膜基地，第一年投资：投资离子镀膜基地，第一年投资7070万元，万元，第二年起每年可获第二年起每年可获利利1818万元万元; ;A A3 3：投资参股：投资参股F F企业，第二年投入企业，第二年投入180180万元设备，万元设备，第三年起每年可第三年起每年可获利获利5050万元万元A A4 4：投资：投资D D企业，每年年底企业，每年年底可获投资额的可获投资额的2525利润利润，但是第一年，但是第一年最高投资额为最高投资额为 80 80 万

76、元，以后每年递增不超过万元，以后每年递增不超过 15 15 万元。万元。A A5 5：建立细骨粉生产线，第三年投入：建立细骨粉生产线，第三年投入320320，第四年起，第四年起每年可获利每年可获利9090万元万元。A A6 6：投资所属中北机电设备公司，：投资所属中北机电设备公司，年底回收本利年底回收本利120120。但每年。但每年投资额不低于投资额不低于6060万元。万元。A A7 7：投资所属澳得技术公司，：投资所属澳得技术公司，年底回收本利年底回收本利115115。MAX 130YMAX 130YMAX 130YMAX 130Y11111111+18Y+18Y+18Y+18Y121212

77、12+50Y+50Y+50Y+50Y23232323+0.25X+0.25X+0.25X+0.25X54545454+90Y+90Y+90Y+90Y35353535+1.2X+1.2X+1.2X+1.2X56565656+1.15X+1.15X+1.15X+1.15X57575757夫邹胎针孙非履浩蕊购叫泼缘浸肯婴黄瞻姻舱抬畴胖翰蛋呕也编慧挝跳坎第八章整数规划第八章整数规划案例案例9 9：华南公司投资方案：华南公司投资方案解：解：设设 X Xij ij 为第为第 i i 年在第年在第 j j 方案上的投资额，方案上的投资额，Y Yijij=1=1，当第，当第 i i 年给第年给第 j j 项目

78、投资时，项目投资时，Y Yijij=0=0，当第，当第 i i 年不给第年不给第 j j 项目投资时。项目投资时。MAX 130YMAX 130Y1111+18Y+18Y1212+50Y+50Y2323+0.25X+0.25X5454+90Y+90Y3535+1.2X+1.2X5656+1.15X+1.15X5757稀寐登此雷胆版心改宴纲器酪稼篮颧砍喀榴夏爽宾吱晓惟疵譬毡林仲澄杯第八章整数规划第八章整数规划X X1111-220Y-220Y1111=0 =0 X X2121-220Y-220Y2121=0=0Y Y1111-Y-Y2121=0=0X X1212-70Y-70Y1212=0=0X

79、 X2323-180Y-180Y2323=0=0X X14148080X X2424-X-X14141515X X3434-X-X24241515X X4444-X-X34341515X X5454-X-X44441515X X3535-320Y-320Y3535=0=0X X16166060X X26266060X X36366060X X46466060X X56566060X X1111+X+X1212+X+X1414+X+X1616+X+X17 17 = 350= 350X X2121+X+X2323+X+X2424+X+X2626+X+X2727 = 0.25X = 0.25X141

80、4+1.2X+1.2X1616+1.15X+1.15X1717+300+300X X3434+X+X3535+X+X3636+X+X3737 = 60Y = 60Y1111+18Y+18Y1212+0.25X+0.25X2424+1.2X+1.2X2626+1.15X+1.15X2727+150+150X X4444+X+X4646+X+X47 47 = 130Y= 130Y1111+18Y+18Y1212+50Y+50Y2323+0.25X+0.25X3434+1.2X+1.2X3636+1.15X+1.15X3737X X5454+X+X5656+X+X5757 = 130Y = 130Y

81、1111+18Y+18Y1212+50Y+50Y2323+0.25X+0.25X4444+90Y+90Y3535+1.2X+1.2X4646+1.15X+1.15X4747X Xi,ji,j0, i=1,2,3,4,5, j=1,2,3,4,5,6,70, i=1,2,3,4,5, j=1,2,3,4,5,6,7Y Y1111, Y, Y1212,Y,Y2323, Y, Y3535 为为0-1 0-1 变量变量约束条件约束条件: :枝祟剧致撬波寝挚涂铱斗眉捍锐映怀臭挣葵散电犀瘪顷溶议射皱破飘椽屡第八章整数规划第八章整数规划第八章第八章 整数规划整数规划n 8.1 8.1 整数规划模型整数规划模

82、型n 8.2 8.2 整数规划的应用整数规划的应用n8.3 8.3 整数规划的分枝定界法整数规划的分枝定界法哺隅蛇栏桐犯囱在禾峙迈蒙革违詹京破悼沸斤条剁沈乐反兑嘛及嗡烹悦颊第八章整数规划第八章整数规划8.3 8.3 整数规划的分枝定界法整数规划的分枝定界法 分枝定界法是求解整数规划的一种常用分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决的有效的方法，它既能解决纯整数规划纯整数规划的问题，又能解决的问题，又能解决混合整数规划混合整数规划的问题。的问题。大多数求解整数规划的商用软件就是基大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。于分枝定界法而编制成的。丹禁矫危铅咕锗有枪

83、幕赞顺澄蛙即秒吟皇妖叉锈谅卸煌免朵咕忍经茵森棠第八章整数规划第八章整数规划8.3 8.3 整数规划的分枝定界法整数规划的分枝定界法混合整数规划混合整数规划问题一般存在穷多个可行解；问题一般存在穷多个可行解；纯整数规划纯整数规划问题，随着问题规模得扩大，其可行解问题，随着问题规模得扩大，其可行解得数目也急剧增加。得数目也急剧增加。因此通过枚举全部可行解，并从中筛选出最优解的因此通过枚举全部可行解，并从中筛选出最优解的算法无实际应用价值。算法无实际应用价值。分枝定界法是一种分枝定界法是一种隐枚举法或部分枚举法隐枚举法或部分枚举法，是枚举，是枚举法基础上的改进。法基础上的改进。仁萌率褒互栓孪昏猪材塞

84、胶幕计鸳烈赃摧憨习卤涝旷粹路驭洛妻吹员蒂泊第八章整数规划第八章整数规划8.3 8.3 整数规划的分枝定界法整数规划的分枝定界法原问题的松驰问题：原问题的松驰问题：任何整数规划，凡放弃某些约束条件任何整数规划，凡放弃某些约束条件（如整数要求）后，所得到的问题都称（如整数要求）后，所得到的问题都称为松驰问题。为松驰问题。瞳虽举犁喘苏玩狭啦义邦孺除奇衷粤琴耙封坟锨懒惰愧什垮闹捧鸣膳编献第八章整数规划第八章整数规划解：设解：设 x x1 1、x x2 2 分别为甲、乙两种货物托运的件数，显然分别为甲、乙两种货物托运的件数，显然 x x1 1、x x2 2 应该是非负整数，该问题的数学模型如下所示：应该

85、是非负整数，该问题的数学模型如下所示： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0 x x1 1，x x2 2 为整数。为整数。整数规划问题整数规划问题粕隆克授搁碌咐框饭第碴朴豁炽创瘁拽吓位长霸耐仪海牺誓砖奸峪讨军摸第八章整数规划第八章整数规划解：设解：设 x x1 1、x x2 2 分别为甲、乙两种货物托运的件数，显然分别为甲、乙

86、两种货物托运的件数，显然 x x1 1、x x2 2 应该是非负整数，该问题的数学模型如下所示：应该是非负整数，该问题的数学模型如下所示： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0 x x1 1，x x2 2 为整数。为整数。原问题原问题松驰问题松驰问题劣灵回趟浅疙娘绝陪氰妹贬柴帮厅恨烙咙句霓凑添钝练痔族芍定描倘企唾第八章整数规划

87、第八章整数规划解：设解：设 x x1 1、x x2 2 分别为甲、乙两种货物托运的件数，显然分别为甲、乙两种货物托运的件数，显然 x x1 1、x x2 2 应该是非负整数，该问题的数学模型如下所示：应该是非负整数，该问题的数学模型如下所示： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0 x x1 1，x x2 2 为整数。为整数。原

88、问题原问题松驰问题松驰问题书巩毗出帆切花唆僻脂其挑危酿切师残些帆描枣阁捻秒鬼敖懊龙擦啃酶竭第八章整数规划第八章整数规划8.3 8.3 整数规划的分枝定界法整数规划的分枝定界法原问题的松驰问题：原问题的松驰问题：任何整数规划，凡放弃某些约束条件任何整数规划，凡放弃某些约束条件（如整数要求）后，所得到的问题都称（如整数要求）后，所得到的问题都称为松驰问题。为松驰问题。哉奎榔祈幅束啥攀陵夜跋榜玖觅蔼撤熏淤固炎影倾苑梁购诅疤巧旁圈喳些第八章整数规划第八章整数规划8.3 8.3 整数规划的分枝定界法整数规划的分枝定界法分枝定界法：分枝定界法：1.1.1.1.求整数规划相应的线性规划问题。求整数规划相应的

89、线性规划问题。求整数规划相应的线性规划问题。求整数规划相应的线性规划问题。2.2.2.2.如果其最优解不符合整数条件，则求出整数规划最如果其最优解不符合整数条件，则求出整数规划最如果其最优解不符合整数条件，则求出整数规划最如果其最优解不符合整数条件，则求出整数规划最优解的上下界优解的上下界优解的上下界优解的上下界3.3.3.3.增加约束条件的将相应的线性规划问题的可行域分增加约束条件的将相应的线性规划问题的可行域分增加约束条件的将相应的线性规划问题的可行域分增加约束条件的将相应的线性规划问题的可行域分成子区域成子区域成子区域成子区域( ( ( (称为分枝称为分枝称为分枝称为分枝) ) ) )，

90、再求解这些子区域上的线性，再求解这些子区域上的线性，再求解这些子区域上的线性，再求解这些子区域上的线性规划问题，规划问题，规划问题，规划问题，4.4.4.4.不断缩小整数规划最优解上下界的距离，最后求得不断缩小整数规划最优解上下界的距离，最后求得不断缩小整数规划最优解上下界的距离，最后求得不断缩小整数规划最优解上下界的距离，最后求得整数规划的最优解整数规划的最优解整数规划的最优解整数规划的最优解5.5.分枝定界法的关键是分枝和定界分枝定界法的关键是分枝和定界仪囱谨耕只攫越窄缘炬醇该奶侧议束较严调站玻彦宠姆韧垛迁子锋最矣幢第八章整数规划第八章整数规划分枝：分枝：若整数规划的松弛问题的最优解不符合

91、整数要求。若整数规划的松弛问题的最优解不符合整数要求。假设假设x xi i = b = bi i不符合整数要求，不符合整数要求， b bi i 是不超过是不超过b bi i最大整数最大整数构造两个附加约束：构造两个附加约束： x xi i b bi i 和和 x xi i b bi i+1 , +1 , 分别将其并入上述松弛问题中，从而形成两个分枝。分别将其并入上述松弛问题中，从而形成两个分枝。加入这两个约束，可得到两个子问题，即两个后续问题。加入这两个约束，可得到两个子问题，即两个后续问题。痰失勒搽悉夸射墩炬于嘎肺翅酋房镣躇抄萨襄郧尝滞邮陈臭堵猜鞍租之韧第八章整数规划第八章整数规划例：例：

92、用分枝定界法求解下面整数规划用分枝定界法求解下面整数规划 max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0 x x1 1，x x2 2 为整数。为整数。券鹅扣抿滨允抨亿汾蔗杜膊此钮囤彬创崭探硷亭闭勋蠢郊孜誓泊楚所乘饲第八章整数规划第八章整数规划例：例： 用分枝定界法求解下面整数规划用分枝定界法求解下面整数规划 max max z z =

93、2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0解：解：先求出先求出相应的线性规划问题相应的线性规划问题(LP1)，即松弛问题的解。，即松弛问题的解。求得这个线性规划的最优解为求得这个线性规划的最优解为 x12.44，x23.26，目标，目标函数的函数的最优值为最优值为 14.66。显然，这个解不是显然，这个解不是原整数规划原整数规划的可行解。的可行解。鞘口探蜡钝砧

94、蔑茹篆驳菩还腐捍告佃袋苞浑钦童忙驻州坑旷晓炸冬吭贝丈第八章整数规划第八章整数规划分枝：分枝：若整数规划的松弛问题的最优解若整数规划的松弛问题的最优解不符合整数要求不符合整数要求。假设假设x xi i = b = bi i不符合整数要求，不符合整数要求， bbi i 是不超过是不超过b bi i最大整数最大整数构造两个附加约束：构造两个附加约束： x xi i b bi i 和和 x xi i b bi i+1 , +1 , 分别将分别将其并入上述松弛问题中，从而形成其并入上述松弛问题中，从而形成两个分枝两个分枝。加入这两个约束，可得到两个加入这两个约束，可得到两个子问题子问题，即两个，即两个后

95、续问题后续问题。酷很考钦兰云咱突厕喊喊沁铲罢贾钟嗓棋嘲坚嚼虫雅蹋槛捅阶牡促鞘护猴第八章整数规划第八章整数规划将一个线性规划问题分为两枝，并求解。将一个线性规划问题分为两枝，并求解。 在线性规划在线性规划 ( (LP1LP1) ) 的最优解的两个非整数的最优解的两个非整数变量变量x x1 12.442.44， x x2 23.26 3.26 中，挑选中，挑选一个一个最远离整数最远离整数的那个变量的那个变量 x x1 12.44 2.44 进行分枝，即增加约束条件进行分枝，即增加约束条件 x x1 12 2 和和 x x1 13 3 ，并将线性规划并将线性规划 ( (LPLP1 1) ) 分为两个

96、分为两个线性规划线性规划-( (LPLP2 2) ) 和和 ( (LPLP3 3) )：咐织坦朵赘遮篮蔷圃酬侗眩铂备表偏深殿瞎计边头萨玫纠邢渠坤螟池辊时第八章整数规划第八章整数规划( (LPLP2 2) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 2 2 2 2 x x1 1，x x2 2 0 0。( (LPLP3 3) )：max

97、max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 3 3 3 3 x x1 1，x x2 2 0 0。( (LPLP1 1) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x

98、 x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0。卤裳艳啦菩们倍罕粉朽靖脂兵媳坤挠弗庆克墟党交难兵业厩抗车敢脉曳涎第八章整数规划第八章整数规划1234123x2x1(LP1) 的可行域的可行域亏败瓮钨炬恐删草裙姓殆痢颗流框耳发如柑巢壤仑苦兰野驾束兴芒姑瘪赶第八章整数规划第八章整数规划1234123x2x1(LP2) 的可行域的可行域(LP3) 的可行域的可行域x x1 21 2x x1 31 3佐俘商湘效暖葬且域急双蝶置闰遵郁李蛔鸡慌鳞抢眺佳争剥再洋蟹被姻析第八章整数规划第八章整数规划分枝：分枝：若整数规划的松弛问题的最优解不符合整数要求。假设xi = bi

99、不符合整数要求， bi 是不超过bi最大整数构造两个附加约束： xr bi 和 xr bi+1 , 分别将其并入上述松弛问题中，从而形成两个分枝。加入这两个约束，可得到两个子问题，即两个后续问题。显然这两个子问题的域中包含原整数规划问题的显然这两个子问题的域中包含原整数规划问题的显然这两个子问题的域中包含原整数规划问题的显然这两个子问题的域中包含原整数规划问题的所有可行解所有可行解所有可行解所有可行解。而在原松弛问题可行域中，满足而在原松弛问题可行域中，满足而在原松弛问题可行域中，满足而在原松弛问题可行域中，满足bbbbi i i i x x x xi i i i b b b bi i i i

100、+1+1+1+1的一部的一部的一部的一部分区域在以后的求解过程中被遗弃了，然而它不包含分区域在以后的求解过程中被遗弃了，然而它不包含分区域在以后的求解过程中被遗弃了，然而它不包含分区域在以后的求解过程中被遗弃了，然而它不包含整数规划整数规划整数规划整数规划的的的的任何可行解任何可行解任何可行解任何可行解 忿桐竣割区挺撵工波栅吁猪灼唯薄乓亦顶反钓统俐谊尽座龟咒被锁贷含现第八章整数规划第八章整数规划1234123x2x1(LP2) 的可行域的可行域(LP3) 的可行域的可行域被遗弃的区域被遗弃的区域x x1 21 2x x1 31 3侥误并肤截养筹堰庚号央甫睦认求兰撤捞绅旨田焰拓祷西附向坝躲惧楞继

101、第八章整数规划第八章整数规划分枝：分枝：若整数规划的松弛问题的最优解不符合整数要求。假设xi = bi不符合整数要求， bi 是不超过bi最大整数构造两个附加约束： xr bi 和 xr bi+1 , 分别将其并入上述松弛问题中，从而形成两个分枝。加入这两个约束，可得到两个子问题，即两个后续问题。显然这两个子问题的域中包含原整数规划问题的所有可行解。而在原松弛问题可行域中，满足bi xi bi+1的一部分区域在以后的求解过程中被遗弃了，然而它不包含整数规划的任何可行解 根据需要，各后续问题问题可以类似地产生自己的分支，直到根据需要，各后续问题问题可以类似地产生自己的分支，直到根据需要，各后续问

102、题问题可以类似地产生自己的分支，直到根据需要，各后续问题问题可以类似地产生自己的分支，直到获得整数规划的最优解获得整数规划的最优解获得整数规划的最优解获得整数规划的最优解吩绎烂蹦胞省滞鉴房锑湿拇贵击枚英琶瞥徒仪羽豁服柒可浓踪楔陛怯铂与第八章整数规划第八章整数规划1234123x2x1(LP2) 的可行域的可行域(LP3) 的可行域的可行域被遗弃的区域被遗弃的区域x x1 1 2 2x x1 1 3 3x xi i b bx xi i b+1 b+1b b x xi i b+1 b+1侈秘垣肤戮享秀案假磨遂濒仆订炭界障陀狞匣馆揉瑶嚎衫雇瑞澈韶笔摘懂第八章整数规划第八章整数规划1234123x2x

103、1(LP4) 的可行域的可行域(LP3) 的可行域的可行域被遗弃的区域被遗弃的区域(LP5) 的可行域的可行域看佛食茵证监谬粘茶偿乡漂沈靖嘲授鲤寝切倦的样缆秀左酉辩陷嗓鸽奄碗第八章整数规划第八章整数规划1234123x2x1(LP1) 的可行域的可行域证铱滞屠蟹啸妨敝葛履瞅氮刻曾樟疆峦天爹警弱拭饱郴磐躬呻搏娱招旗客第八章整数规划第八章整数规划1234123x2x1(LP4) 的可行域的可行域(LP3) 的可行域的可行域被遗弃的区域被遗弃的区域(LP5) 的可行域的可行域赃清筛凉镁尾戈擦扣客撤泥镭月梆请牟履侣杉饼瓤绑垣特殆丽具饿讥僵狠第八章整数规划第八章整数规划分枝：分枝：若整数规划的松弛问题的

104、最优解若整数规划的松弛问题的最优解不符合整数要求不符合整数要求。假设假设x xi i = b = bi i不符合整数要求，不符合整数要求， b bi i 是不超过是不超过b bi i最大整数最大整数构造两个附加约束：构造两个附加约束： x xr r b bi i 和和 x xr r b bi i+1+1 , , 分别将其分别将其并入上述松弛问题中，从而形成并入上述松弛问题中，从而形成两个分枝两个分枝。加入这两个约束，可得到两个加入这两个约束，可得到两个子问题子问题，即两个，即两个后续问题后续问题。显然这两个子问题的域中包含显然这两个子问题的域中包含原整数规划问题的所有可行解原整数规划问题的所有

105、可行解。而在原松弛问题可行域中，满足而在原松弛问题可行域中，满足bbi i x xi i bbi i+1+1的一部的一部分区域在以后的求解过程中被分区域在以后的求解过程中被遗弃遗弃了，然而它不包含整数规划了，然而它不包含整数规划的任何可行解的任何可行解 根据需要，各后续问题问题可以类似地产生自己的分支，直到根据需要，各后续问题问题可以类似地产生自己的分支，直到获得整数规划的获得整数规划的最优解最优解忘盛监婴砖连刹视穗扇洼举须刚必柱铁钎隔悉台挚赂秉宏驹嘛渊颧芬驴啄第八章整数规划第八章整数规划定界：定界：在分枝过程中，若某个后续问题恰好获得整数规划在分枝过程中，若某个后续问题恰好获得整数规划问题的

106、一个可行解。问题的一个可行解。那么，它的目标函数值就是一个那么，它的目标函数值就是一个“界限界限”，可以作，可以作为衡量处理其他分支的一个依据。为衡量处理其他分支的一个依据。整数规划问题的整数规划问题的可行解集可行解集是它的松弛问题是它的松弛问题可行解集可行解集的一个的一个子集子集，前者最优解前者最优解的目标函数不会优于的目标函数不会优于后者最后者最优解优解的目标函数值。的目标函数值。对于那些相应松弛问题最优解的目标函数比上述对于那些相应松弛问题最优解的目标函数比上述“界限界限”值差的后继问题，就可以剔除不再考虑了。值差的后继问题，就可以剔除不再考虑了。区赦桑杖织隧罕内席蓄拐间愉此榨伍羡昆殉惜

107、吝铡史答逝枕诫工撒绪酝闽第八章整数规划第八章整数规划例：例： 用分枝定界法求解下面整数规划用分枝定界法求解下面整数规划 max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. 195 s.t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0解：解：1.先求出先求出相应的线性规划问题相应的线性规划问题(LP1)，即松弛问题的解。，即松弛问题的解。求得这个线性规划的最优解为求得这个线性规划的最优解为 x12.44

108、，x23.26，目标函，目标函数的数的最优值为最优值为 14.66。显然，这个解不是显然，这个解不是原整数规划原整数规划的可行解。的可行解。敌酷琴诫渍剔衰抵畏脊蛊敏毖镰撕悄痴符伊哭林岂倒空折蔚版舵把扫洞冲第八章整数规划第八章整数规划2.2.确定确定整数规划的最优目标函数值整数规划的最优目标函数值z z* *的初始上界的初始上界 和下界和下界 。 因因 ( (LPLP1 1) ) 目标函数的最优值为目标函数的最优值为 14.66 14.66，故可取，故可取袄骗冶倘肄羞役坞呆阀穆玖渴樟探梅马央斯碎岳久孕悠勿趾埃高侄腿鼓淘第八章整数规划第八章整数规划定界：定界：在分枝过程中，若某个后续问题恰好获得整

109、数规划问题的一个可行解。那么，它的目标函数值就是一个“界限”，可以作为衡量处理其他分支的一个依据。整数规划问题的整数规划问题的整数规划问题的整数规划问题的可行解集可行解集可行解集可行解集是它的松弛问题是它的松弛问题是它的松弛问题是它的松弛问题可行解集可行解集可行解集可行解集的一个的一个的一个的一个子集子集子集子集，前者最优解前者最优解前者最优解前者最优解的目标函数不会优于的目标函数不会优于的目标函数不会优于的目标函数不会优于后者最后者最后者最后者最优解优解优解优解的目标函数值。的目标函数值。的目标函数值。的目标函数值。对于那些相应松弛问题最优解的目标函数比上述“界限”值差的后继问题，就可以剔除

110、不再考虑了。蹲筏消瘩啡侗座荔旁邱降故遣兴暮庞身妨捡入酮池姚庶旭俞像跟剧临缔谨第八章整数规划第八章整数规划2.2.确定确定整数规划的最优目标函数值整数规划的最优目标函数值z z* *的初始上界的初始上界 和下界和下界 。 因因 ( (LPLP1 1) ) 目标函数的最优值为目标函数的最优值为 14.66 14.66，故可取，故可取 又用观察法可知，又用观察法可知， x x1 12 2，x x2 23 3 是是原原整数规划整数规划的的可行解，可行解，其对应的目标函数值为其对应的目标函数值为 z z = 2 = 2x x1 1 + 3 + 3x x2 213 13 ， 故可取故可取 =13 =13

111、。 因为因为 ，所以需要进行分枝。，所以需要进行分枝。 盂疟惜漆侦捶递朴酿蛇筐伍雀子馈瑟委烁南锋怀锡望袖鄂臣班钮议圃楚壶第八章整数规划第八章整数规划3.3.将一个线性规划问题分为两枝，并求解。将一个线性规划问题分为两枝，并求解。 在线性规划在线性规划 ( (LP1LP1) ) 的最优解的两个非整数的最优解的两个非整数变量变量x x1 12.442.44， x x2 23.26 3.26 中，挑选中，挑选一个一个最远离整数最远离整数的那个变量的那个变量 x x1 12.44 2.44 进行分枝，即增加约束条件进行分枝，即增加约束条件 x x1 12 2 和和 x x1 13 3 ，并将线性规划并

112、将线性规划 ( (LPLP1 1) ) 分为两个分为两个线性规划线性规划-( (LPLP2 2) ) 和和 ( (LPLP3 3) )：盯命湛雹术境抽鞭阑垦粤畅容挎哲始疹唁灭勿咬涩祭蜘枉奠如办漳炯占长第八章整数规划第八章整数规划( (LPLP2 2) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 2 2 2 2 x x1 1，x x2

113、2 0 0。( (LPLP3 3) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 3 3 3 3 x x1 1，x x2 2 0 0。( (LPLP1 1) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1

114、365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0。龚汉站蹲脑神帖匣思啊尿瞬校溪猛灾重拥册度驮沪朝滁迁绒哗琶卡瘤脓长第八章整数规划第八章整数规划( (LP2LP2) )： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1 2 2 x x1 1，x x2 2 0 0。求得这个线性规

115、划的最优解为求得这个线性规划的最优解为 x x1 12 2，x x2 23.33.3，目标函数的最优，目标函数的最优值为值为 13.9 13.9。( (LP3LP3) )： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1 3 3 x x1 1，x x2 2 0 0。求得这个线性规划的最优解为求得这个线性规划的最优解为 x x1 13 3，x x2 22.86

116、2.86，目标函数的最，目标函数的最优值为优值为 14.58 14.58。扫迎仓浮底胡欺尺枕那夜霍毖瑶垢俞赂立葫英屹匿炎翔祖咒漆赌晓痴偷误第八章整数规划第八章整数规划4 4. .修改修改整数规划的最优目标函数值整数规划的最优目标函数值 z* z* 的上、下界。的上、下界。 因为因为 ( (LP2LP2) ) ( ( x x1 1 2 2 ) )目标函数的最优值为目标函数的最优值为 13.9 13.9，( (LP2LP2) ) 对应的对应的整数规划的最优目标函数值不会超过整数规划的最优目标函数值不会超过13.913.9；( (LP3LP3) ( ) ( x x1 133) )目标函数的最优值为目

117、标函数的最优值为 14.58 14.58，( (LP3LP3) ) 对应的对应的整数规划的最优目标函数值不会超过整数规划的最优目标函数值不会超过 14.58 14.58。综上所述，不论综上所述，不论 x x1 1 ( ( 4 4) ) 取任何整数值，原整数规划的最取任何整数值，原整数规划的最优目标函数值不会超过优目标函数值不会超过 14.58 14.58，于是整数规划的最优目标函数，于是整数规划的最优目标函数值值 z z* * 的上界可修改为的上界可修改为俗目阀俊韵殴驼蔡艇资槐甸偿负伊晦演备惩气葵膝钓煞折堰讣茄铃巩熏抵第八章整数规划第八章整数规划又用观察法可知，又用观察法可知， 在在 ( (L

118、P2LP2) ) ( (x x1 122) ) 中中 x x1 12 2，x x2 23 3 是是该该整数规划整数规划的一个的一个可可行解，其对应的目标函数值为行解，其对应的目标函数值为 z z = 2 = 2x x1 1 + 3 + 3x x2 21313；在在 ( (LP3LP3) ) ( (x x1 133) ) 中中 x x1 13 3，x x2 22 2 是是该该整数规划整数规划的一个的一个可可行解，其对应的目标函数值为行解，其对应的目标函数值为 z z = 2 = 2x x1 1 + 3 + 3x x2 212 12 。综上所述，不论综上所述，不论 x x1 1 ( ( 4 4)

119、) 取任何整数值，原整数规划的最取任何整数值，原整数规划的最优目标函数值不会小于优目标函数值不会小于 13 13，于是整数规划的最优目标函数值，于是整数规划的最优目标函数值 z z* * 的下界可的下界可 ( (修改修改) ) 为为: : 隔扩澎扛莽晨卡砂例椒内琳毖新股掣卸迅迷谁棺动负德揣婉硝糙埋玻祝哀第八章整数规划第八章整数规划 注意：在分枝定界求解过程中，为了求出最优整数解，注意：在分枝定界求解过程中，为了求出最优整数解，我们要不断地缩小其最优目标函数值上界与下界的距离，我们要不断地缩小其最优目标函数值上界与下界的距离，故通过分枝要使得其故通过分枝要使得其上界越来越小上界越来越小，而其，而

120、其下界越来越大下界越来越大。 由前可知，通过对上、下界的修改，上下界的距离有所由前可知，通过对上、下界的修改，上下界的距离有所缩小，但因为缩小，但因为 ，所以还要继续进行分枝。，所以还要继续进行分枝。纂寞耗蜀怀谤梁介克喊硕瞒兜宪绵荡篇赌锡翠矿瀑蝇恫幕捎橡胯孔祝扦沮第八章整数规划第八章整数规划(LP1)z1 = 14.66x1 = 2.44x2 = 3.26(LP2)z2 = 13.90x1 = 2x2 = 3.30(LP3)z3 = 14.58x1 = 3x2 = 2.86x12x13彪纠袋啄揭雾蜀哎辟吹壁龄倘撞专德柠偏惋秤桓犯持逞迄坐援鞘巨柔阻拦第八章整数规划第八章整数规划5.5.重复重复(

121、3.)(3.)，将一个线性规划问题分为两枝，并求解。，将一个线性规划问题分为两枝，并求解。在在 ( (LPLP2 2) ) 与与 ( (LPLP3 3) ) 中选择中选择目标函数的最优值大的那个目标函数的最优值大的那个线线性规划进行分枝，即对性规划进行分枝，即对( (LPLP3 3) ) 进行分枝。进行分枝。因为因为 ( (LPLP3 3) ) 的最优解为的最优解为 x x1 13 3，x x2 22.862.86，挑选挑选一个一个最远离整数的那个变量最远离整数的那个变量 x x2 22.862.86，进行分枝，进行分枝，即增加约束条件即增加约束条件 x x2 22 2 和和 x x2 23

122、3 ，将线性规划将线性规划 ( (LPLP3 3) ) 分为两个分为两个线性规划线性规划 ( (LPLP4 4) ) 和和 ( (LPLP5 5) )：壳烩祸淮呢针辣莎纪丧钞聊楷酮蛊仆养疫浩篙赎驴鸽安八拘堵陡嘱疾冻撰第八章整数规划第八章整数规划( (LP2LP2) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 2 2 2 2 x x1

123、1，x x2 2 0 0。( (LP3LP3) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 3 3 3 3 x x1 1，x x2 2 0 0。( (LP1LP1) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1

124、365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0。碧瘴烬喻湖烤爽坟持抽宝嘉钨搪长盟下荤延遥剖贡竹骑弯迟创滁堤啼灰训第八章整数规划第八章整数规划( (LP2LP2) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 2 2 2 2 x x1 1，x

125、x2 2 0 0。( (LP3LP3) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 3 3 3 3 x x1 1，x x2 2 0 0。( (LP1LP1) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365

126、1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0。涅目焉卧苔肛鞋孽彬让烛截痪悄协韦趣盛椒敖钟应拔叮诸巳蕴狠洒惨涯妥第八章整数规划第八章整数规划( (LP2LP2) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 2 2 2 2 x x1 1，x x2 2

127、 0 0。( (LP3LP3) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 3 3 3 3 x x1 1，x x2 2 0 0。( (LP1LP1) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365

128、 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0。( (LP4LP4) )：max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 3 3 3 3 x x x x2 2 2 2 2 2 2 2 x x1 1，x x2 2 0 0。( (LP5LP5) )：max max z

129、 z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x x x1 1 1 1 3 3 3 3 x x x x2 2 2 2 3 3 3 3 x x1 1，x x2 2 0 0。及族孪齐揖狼缀请抵俐晾疮微廊肺仑芯物钠扑呼瀑柴士焦抗宙迭鳖笆抄饶第八章整数规划第八章整数规划5.5.重复重复(3.)(3.)，将一个线性规划问题分为两枝，并求解。，将一个线性规划问题分为两枝，并求解。在在 ( (LP

130、2LP2) ) 与与 ( (LP3LP3) ) 中选择中选择目标函数的最优值大的那个目标函数的最优值大的那个线线性规划进行分枝，即对性规划进行分枝，即对( (LP3LP3) ) 进行分枝。进行分枝。因为因为 ( (LP3LP3) ) 的最优解为的最优解为 x x1 13 3，x x2 22.862.86，挑选挑选一个一个最远离整数的那个变量最远离整数的那个变量 x x2 22.862.86，进行分枝，进行分枝，即增加约束条件即增加约束条件 x x2 22 2 和和 x x2 23 3 ，并将线性规划，并将线性规划 ( (LP3LP3) ) 分为两个分为两个线性规划线性规划 ( (LP4LP4)

131、 ) 和和 ( (LP5LP5) )：秧冗喷绘胞陶弦橱惊厨创骚逢相垃凯徊胃埂县宗过爸费桐滁编卉队苗仲锦第八章整数规划第八章整数规划( (LP4LP4) )： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1 3 3 x x2 2 2 2 x x1 1，x x2 2 0 0。秦嘿物柿枷账洲糙呛站逼弛袁炽扭饶剂可钾亡梨试皖室抿垛剩也霓溯嘻泻第八章整数规划第八章整数

132、规划1234123x2x1(LP2) 的可行域的可行域(LP3) 的可行域的可行域又第管肌模蛹陀萤略惯喻碳玫辙元短云石衰获漂份底蔓钨烦童窥荫丹剔慈第八章整数规划第八章整数规划1234123x2x1(LP2) 的可行域的可行域(LP4) 的可行域的可行域x2 2沂纠益狼幻存艇饿嘻蛹扎丸颁豁苑饿辩吾斧常逢月草鸽硕烘戊啮腾集霖盲第八章整数规划第八章整数规划( (LP4LP4) )： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 4

133、0x x2 2 140 140 x x1 1 4 4 x x1 1 3 3 x x2 2 2 2 x x1 1，x x2 2 0 0。求得这个线性规划的最优解为求得这个线性规划的最优解为x x1 14 4，x x2 22 2，目标函数的最优值为目标函数的最优值为 14 14。赋塔煌溯荫抄泵堂男瘁智捣跪渍嚣琴霍雕执玫袍姻棠恿扎渗马察菜紊锚吟第八章整数规划第八章整数规划(LP4)： max z = 2x1 + 3x2s. t. 195x1 + 273x2 1365 4x1 + 40x2 140 x1 4 x1 3 x2 2 x1，x2 0。求得这个线性规划的最优解为x14，x22，目标函数的最优值

134、为 14。( (LP5LP5) )： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1 3 3 x x2 2 3 3 x x1 1，x x2 2 0 0。合旬桂澜磅读哦篷踪孙嫁低欣行娄蜕矽傻佩处爬灾输侯贼榴愧融久锦滨漾第八章整数规划第八章整数规划1234123x2x1(LP2) 的可行域的可行域(LP3) 的可行域的可行域跺琴蔷脊嫩稽椭歇昌钦闰扮饯野赖陛命盔颠

135、官撇诫蛙译贫靴蓟浇填涸炉医第八章整数规划第八章整数规划1234123x2x1(LP2) 的可行域的可行域(LP4) 的可行域的可行域(LP5) 无可行域无可行域x2 2x2 3禽描扼制锡浊诺扳鼎缺魁匠嫂缚苦登剑珐但柔荷焕霍蜗献科凄咱冀川受皑第八章整数规划第八章整数规划(LP4)： max z = 2x1 + 3x2s. t. 195x1 + 273x2 1365 4x1 + 40x2 140 x1 4 x1 3 x2 2 x1，x2 0。求得这个线性规划的最优解为x14，x22，目标函数的最优值为 14。( (LP5LP5) )： max max z z = 2 = 2x x1 1 + 3 +

136、 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1 3 3 x x2 2 3 3 x x1 1，x x2 2 0 0。这个线性规划问题无可行解。这个线性规划问题无可行解。炎葱冰痞流喳恕早藉念荤肄粗橡籽陛来勉瞎埋翱周晰战棵硒床烯趟克躲蝉第八章整数规划第八章整数规划6. 6. 重复重复(4.)(4.)，进一步修改，进一步修改整数规划的最优目标函数值整数规划的最优目标函数值 z* z* 的的上、下界。上、下界。 因为因为 ( (

137、LP2LP2) ) 目标函数的最优值为目标函数的最优值为 13.9 13.9，( (LP2LP2) ) 对应的对应的整数规划的最优目标函数值不会超过整数规划的最优目标函数值不会超过 13.913.9；庸盼某支哼消隙盈赏论溪欧榔卓摇叹亥托浪铣类适款枷品嗅核措图搏港腹第八章整数规划第八章整数规划(6) (6) 重复重复(4)(4)，进一步修改，进一步修改整数规划的最优目标函数值整数规划的最优目标函数值 z* z* 的的上、下界。上、下界。 因为 (LP2) 目标函数的最优值为 13.9，(LP2) 对应的整数规划的最优目标函数值不会超过 13.9；( (LP3LP3) ) 目标函数的目标函数的最优

138、值为最优值为 14.58 14.58，但但 ( (LP3LP3) ) 被分枝为被分枝为 ( (LP4LP4) ) 和和 ( (LP5LP5) )，( (LP4LP4) ) 目标函数的最优值为目标函数的最优值为 14 14， ( (LP5LP5) ) 无可行解，无可行解，所以所以 ( (LP3LP3) ) 对应的对应的整数规划的最优目标函数值不会超过整数规划的最优目标函数值不会超过 14 14。综上所述，原整数规划的最优目标函数值不会超过综上所述，原整数规划的最优目标函数值不会超过 14 14，于是，于是整数规划的最优目标函数值整数规划的最优目标函数值 z z* * 的上界可修改为的上界可修改为

139、按违诫聘刀装册框全阴廉作茹毁声综汰够舔坝绘坚冶诸绢旅荔沈鸽淋柠炔第八章整数规划第八章整数规划1234123x2x1(LP2) 的可行域的可行域(LP4) 的可行域的可行域(LP5) 无可行域无可行域Z=13.9Z=14估明连电忱茹芯词嗡鬼纶诡呐缠僚翱淡烈蹋糠算哗瑚滨塔缨屉疼齿昆泊笺第八章整数规划第八章整数规划(6) (6) 重复重复(4)(4)，进一步修改，进一步修改整数规划的最优目标函数值整数规划的最优目标函数值 z* z* 的的上、下界。上、下界。 因为 (LP2) 目标函数的最优值为 13.9，(LP2) 对应的整数规划的最优目标函数值不会超过 13.9； ( (LP3LP3) ) 目标

140、函数的目标函数的最优值为最优值为 14.58 14.58，但但 ( (LP3LP3) ) 被分枝为被分枝为 ( (LP4LP4) ) 和和 ( (LP5LP5) )，( (LP4LP4) ) 目标函数的最优值为目标函数的最优值为 14 14， ( (LP5LP5) ) 无可行解，无可行解，所以所以 ( (LP3LP3) ) 对应的对应的整数规划的最优目标函数值不会超过整数规划的最优目标函数值不会超过 14 14。综上所述，原整数规划的最优目标函数值不会超过综上所述，原整数规划的最优目标函数值不会超过 14 14，于是，于是整数规划的最优目标函数值整数规划的最优目标函数值 z z* * 的上界可

141、修改为的上界可修改为蓟氢易弯病佃疆谱奖故柠橇理力攘吠恐淆搅鲍拱颁竖机筹腆煮噶朔互滇翠第八章整数规划第八章整数规划( (LP4LP4) )： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1 3 3 x x2 2 2 2 x x1 1，x x2 2 0 0。求得这个线性规划的最优解为求得这个线性规划的最优解为x x1 14 4，x x2 22 2，目标函数的最优

142、值为目标函数的最优值为 14 14。( (LP5LP5) )： max max z z = 2 = 2x x1 1 + 3 + 3x x2 2s. t. 195s. t. 195x x1 1 + 273 + 273x x2 2 1365 1365 4 4x x1 1 + 40 + 40x x2 2 140 140 x x1 1 4 4 x x1 1 3 3 x x2 2 3 3 x x1 1，x x2 2 0 0。这个线性规划问题无可行解。这个线性规划问题无可行解。羞捐咀哈淡妨煮颂盼株删难旧猾颤终布轧且切倾皖蓑理彭倪炭蚕恶盔画毡第八章整数规划第八章整数规划又因为在又因为在 ( (LP4LP4)

143、 ) 中存在整数可行解中存在整数可行解 x x1 14 4，x x2 22 2，其对应的，其对应的目标函数值为目标函数值为 z z = 2 = 2x x1 1 + 3 + 3x x2 214 14 ； 综上所述，原整数规划的最优目标函数值不会小于综上所述，原整数规划的最优目标函数值不会小于1414，于是，于是整数规划的最优目标函数值整数规划的最优目标函数值 z z* * 的下界可修改为的下界可修改为 治替媚统斯斧俩屹诚羡发察狰檄苦祖虑悯凑妆嫩座埂拒了颁沿铲丽险琴息第八章整数规划第八章整数规划性质性质 2. 2. 当整数规划的最优目标函数值当整数规划的最优目标函数值 z z* * 的上界的上界

144、等于其下界等于其下界 z z 时，该整数规划的最优解已被求出，这个整数规划的最优解时，该整数规划的最优解已被求出，这个整数规划的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。即为其目标函数值取此下界的对应线性规划的整数可行解。 在此例题中在此例题中可知此整数规划的最优目标函数值可知此整数规划的最优目标函数值 z z* =14* =14，其最优解为其最优解为 x x1 14 4，x x2 22 2。皇桑塞糜呢醋宝蛆钱所屎阵接贸紊酋悬剃究巴治父梦悦津兹择劲蔫栓眉熄第八章整数规划第八章整数规划用下图表示例题的求解过程与结果。用下图表示例题的求解过程与结果。(LP1)z1 = 14.66x

145、1 = 2.44x2 = 3.26(LP2)z2 = 13.90x1 = 2x2 = 3.30(LP3)z3 = 14.58x1 = 3x2 = 2.86(LP4)z4 = 14.00x1 = 4x2 = 2(LP5)无可行解无可行解z z =13，x12x13z z =13，x22x23z z =14，田重佃慕贯托临喇深愉哀能扩简枫董自烹拄操行瑚忽弱批制苞遁嚼乏赁涤第八章整数规划第八章整数规划用分枝定界法求解整数规划的步骤：用分枝定界法求解整数规划的步骤：问题问题 (A) (A)： max max z z = = c c1 1 x x1 1 + + c c2 2 x x2 2 + + + +

146、 c cn n x xn n s.t. s.t. a a1111 x x1 1 + + a a1212 x x2 2 + + + + a a1 1n n x xn n = = b b1 1 a a2121 x x1 1 + + a a2222 x x2 2 + + + + a a2 2n n x xn n = = b b2 2 a am m1 1 x x1 1 + + a am m2 2 x x2 2 + + + + a amnmn x xn n = = b bm m x x1 1 ，x x2 2 ， ，x xn n 0 0 为整数。为整数。内鸟糙风位韵胸啃萌蕉伍搐吏论挞动夸垒跨痒纬舒编焰诌脾

147、锦湘梦敛吨辨第八章整数规划第八章整数规划将问题将问题 (A) (A) 中的整数约束去掉，并记松弛问题为中的整数约束去掉，并记松弛问题为(B)(B)。问题问题 (B) (B)： max max z z = = c c1 1 x x1 1 + + c c2 2 x x2 2 + + + + c cn n x xn n s. t. s. t. a a1111 x x1 1 + + a a1212 x x2 2 + + + + a a1 1n n x xn n = = b b1 1 a a2121 x x1 1 + + a a2222 x x2 2 + + + + a a2 2n n x xn n =

148、 = b b2 2 a am m1 1 x x1 1 + + a am m2 2 x x2 2 + + + + a amnmn x xn n = = b bm m x x1 1 ，x x2 2 ， ，x xn n 0 0。 寸椽锋寸乔抡茨租插圣炉淹锗饿惠纬饿杉棋频祈厉炼全娩瓷誉机暂堆谴龙第八章整数规划第八章整数规划第一步：第一步： 求解问题求解问题(B)(B)，将会出现以下情况之一：，将会出现以下情况之一：1.1.松弛问题松弛问题无可行解，则无可行解，则整数规划问题整数规划问题亦无可行解，求解过亦无可行解，求解过程停止。程停止。2.2.松弛问题松弛问题有最优解，并满足整数约束，这时有最优解，并

149、满足整数约束，这时松弛问题松弛问题的最的最优解也同时为优解也同时为整数规划问题整数规划问题的最优解，求解过程停止。的最优解，求解过程停止。珊看吾防端密亡便播雷睦话揉亏皮闪咎喊亚卷抨菏棉浮撬乱向两侄千脊苇第八章整数规划第八章整数规划第一步：第一步： 求解问题求解问题(B)(B)，将会出现以下情况之一：，将会出现以下情况之一：1.松弛问题无可行解，则整数规划问题亦无可行解，求解过程停止。2.松弛问题有最优解，并满足整数约束，这时松弛问题的最优解也同时为整数规划问题的最优解，求解过程停止。3.3.松弛问题松弛问题有最优解，但不符合有最优解，但不符合整数规划问题整数规划问题的整数条件，的整数条件，记其

150、目标函数值为记其目标函数值为 z z1 1。盾晦肘印犹辐轻研蔽聘陆彦溉唁颠柑险圣晴佯昭瞎淡酝磅屿凄舔险猎野拥第八章整数规划第八章整数规划第二步：第二步： 确定确定整数规划整数规划整数规划问题整数规划问题的最优目标函数值的最优目标函数值 z z* * 的上的上下界，取其上界为下界，取其上界为 z z1 1 ，即，即 再用观察法找再用观察法找整数规划问题整数规划问题的一个整数可行解，求其目标函数的一个整数可行解，求其目标函数值作为值作为 z* 的下界，记为的下界，记为 z 。 第三步：第三步： 判断判断 是否等于是否等于 z z 。 如果如果 ，则整数规划的最优，则整数规划的最优解即为目标函数值等

151、于解即为目标函数值等于 z z 的的整数规划问题整数规划问题的那个整数可行解。的那个整数可行解。如果如果 ，则进行第四步工作。，则进行第四步工作。窑嚼眼芋吉脂拘君匠梭梢峰舵舵让突桔岁祥腻垃钢砾炎摄弱晤侠奄珐炉葫第八章整数规划第八章整数规划第四步：第四步： 在在 (B) (B) 的最优解中选一个最远离整数要求的变量，不妨设此变的最优解中选一个最远离整数要求的变量，不妨设此变量为量为 x xj j = = b bj j ，以，以 b bj j 表示小于表示小于b bj j的最大整数，构造两个约束的最大整数，构造两个约束条件：条件： x xj j b bj j 和和 x xj j b bj j +

152、1 + 1 ，将这两个约束条件分别加入问题将这两个约束条件分别加入问题 (B) (B)，得到，得到 (B) (B) 的两个分枝线的两个分枝线性规划性规划 (B (B1 1) ) 和和 (B (B2 2) )。距乡兄刚它滦杰嫉又歹勿难衙毡侨焊夜哥丢围磨鸽净按稽孵裁费豆运趣趾第八章整数规划第八章整数规划第五步：第五步：求解分枝线性规划求解分枝线性规划 (B (B1 1) ) ，(B(B2 2) )，修改，修改 (A) (A) 问题的最优目问题的最优目标函数值标函数值 z z* * 的上下界。的上下界。先取先取 (B (B1 1) )、(B(B2 2) ) 最优目标函数值的最大值为新的上界最优目标函

153、数值的最大值为新的上界 。然后，用观察法各取然后，用观察法各取 (B (B1 1) )、(B(B2 2) ) 问题中的一个整数可行解问题中的一个整数可行解并选择其中一个较大的目标函数值作为新的下界并选择其中一个较大的目标函数值作为新的下界 z z 的值。的值。挟夯婶虞速辨绸墅旅将乾葡丙汾谢没艾陕岿俱祁巡锈脯欺腮辙裴情灌撕星第八章整数规划第八章整数规划第六步：比较与剪枝。第六步：比较与剪枝。若某分枝若某分枝无可行解或其最优目标函数无可行解或其最优目标函数值小于值小于z，则剪掉这枝则剪掉这枝（用打用打表示表示），即以后不再考虑了；，即以后不再考虑了；若大于若大于 z ，且不符合整数条件，则重复第三

154、步至第六步，且不符合整数条件，则重复第三步至第六步，直至直至 ，求出最优整数解为止。，求出最优整数解为止。磋帖妇埔棕盆幻死艇渤试矫蛆污蒜敖扒肠止苑博站搓慷出折港驮缆亢弃呀第八章整数规划第八章整数规划用下图表示例题的求解过程与结果。用下图表示例题的求解过程与结果。(LP1)z1 = 14.66x1 = 2.44x2 = 3.26(LP2)z2 = 13.90x1 = 2x2 = 3.30(LP3)z3 = 14.58x1 = 3x2 = 2.86(LP4)z4 = 14.00x1 = 4x2 = 2(LP5)无可行解无可行解z z =13，x12x13z z =13，x22x23z z =14，逛盯瓣曰摄践咆迁妹硕吻营鸯孩技族稍吧尊路鬃厄娟匠桌蚕罗骂靴返啮至第八章整数规划第八章整数规划整数规划常用的求解方法有：整数规划常用的求解方法有：割平面法割平面法分枝定界法分枝定界法0 1 规划常用的求解方法有：规划常用的求解方法有：隐枚举法隐枚举法 一种特殊的分枝定界法一种特殊的分枝定界法指派问题常用的求解方法有：指派问题常用的求解方法有：匈牙利法匈牙利法运筹学教程，胡运权，清华大学出版社运筹学教程，胡运权，清华大学出版社确误悔疚俄底趣闺乓抨闻衬视哨榆霜狠腆把滞潘虑冒漳簇蹋捆诺蹬告昼扔第八章整数规划第八章整数规划