第八章整数规划

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

1、第八章第八章 整数规划整数规划Integer ProgrammingInteger Programming第八章第八章 整数规划整数规划在前面讨论的线性规划问题中，最优解在前面讨论的线性规划问题中，最优解可能是整数，也可能不是整数，但对于可能是整数，也可能不是整数，但对于某些实际问题，要求答案必须是某些实际问题，要求答案必须是整数整数。如，如，所求的解是安排上班的人数，所求的解是安排上班的人数，按某个方案裁剪钢材的根数，按某个方案裁剪钢材的根数，生产机器的台数等。生产机器的台数等。第八章第八章 整数规划整数规划n 8.1 8.1 整数规划模型整数规划模型8.1 8.1 整数规划模型整数规划模型

2、整数规划模型的一般形式 Max Max（或（或MinMin）Z =Z =ccj jx xj js.ts.t.aaij ijx xj j (或或 =,)b=,)bi i i=1,2,i=1,2,m,m x xj j 0 j=1,2,0 j=1,2,n,n x x1 1,x x2 2,x xn n 中部分或全部取整数中部分或全部取整数8.1 8.1 整数规划模型整数规划模型在线性规划模型中在线性规划模型中 如果所有的决策变量都要求为非负整数，则这样的线性规划问题称之为纯整数规划问题。如果只有一部分决策变量要求为非负整数，则这样的线性规划问题称之为混合整数规划问题。如果决策变量的取值只限于 0 和

3、1，则这样的整数线性规划问题称之为 01型整数规划问题。8.1 8.1 整数规划模型整数规划模型 例：例：一登山队员做登山准备，他需要一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假种物品的重要性系数和重量如下：假定登山队员可携带最大重量为定登山队员可携带最大重量为2525公斤。公斤。序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备重量重量5 55 52 26 612122 24 4重要重要

4、系数系数20201515181814148 84 410108.1 8.1 整数规划模型整数规划模型解：解：令令x xi i=1=1表示登山队员携带物品表示登山队员携带物品i i，x xi i=0=0表示登山队员不携带物品表示登山队员不携带物品i:i:Max Z=20 xMax Z=20 x1 1+15x+15x2 2+18x+18x3 3+14x+14x4 4+8x+8x5 5+4x+4x6 6+10 x+10 x7 7s.ts.t.5x.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 =

5、1 或或 x xi i=0 i=1,2,.7=0 i=1,2,.7序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备重量重量5 55 52 26 612122 24 4重要重要系数系数20201515181814148 84 410108.1 8.1 整数规划模型整数规划模型背包问题背包问题(Knapsack Problem)(Knapsack Problem)一个旅行者一个旅行者,为了准备旅行的必须用品为了准备旅行的必须用品,要在背包内要在背包内装一些最有用的东西装一些最有用的东西,有限制有限制:最多只能装b公斤的物品 而每件物

6、品只能整个携带 每件物品规定了一个“价值”以表示其有用的程度 如果共有n件物品,第 j 件物品aj公斤,其价值为cj.问题变成问题变成:在携带的物品总重量不超过在携带的物品总重量不超过b b公斤条件下公斤条件下,携带哪些物品携带哪些物品,可使总价值最大可使总价值最大?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=ccj jx xj j s.t.s.t.aaj jx xj

7、j b b x xj j=0 =0 或或 1 18.1 8.1 整数规划模型整数规划模型解：解：令令x xi i=1=1表示登山队员携带物品表示登山队员携带物品i i，x xi i=0=0表示登山队员不携带物品表示登山队员不携带物品i:i:Max Z=20 xMax Z=20 x1 1+15x+15x2 2+18x+18x3 3+14x+14x4 4+8x+8x5 5+4x+4x6 6+10 x+10 x7 7s.ts.t.5x.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

8、 xi i=0 i=1,2,.7=0 i=1,2,.7序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备重量重量5 55 52 26 612122 24 4重要重要系数系数20201515181814148 84 410108.1 8.1 整数规划模型整数规划模型 当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。例如，背包问题充其量有例如，背包问

9、题充其量有 2 2n n种方式种方式 8.1 8.1 整数规划模型整数规划模型解：解：令令x xi i=1=1表示登山队员携带物品表示登山队员携带物品i i，x xi i=0=0表示登山队员不携带物品表示登山队员不携带物品i:i:Max Z=20 xMax Z=20 x1 1+15x+15x2 2+18x+18x3 3+14x+14x4 4+8x+8x5 5+4x+4x6 6+10 x+10 x7 7s.ts.t.5x.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

10、=0 i=1,2,.7=0 i=1,2,.7序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备重量重量5 55 52 26 612122 24 4重要重要系数系数20201515181814148 84 410108.1 8.1 整数规划模型整数规划模型 当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。6060 8.1 8.1 整数规划模型整数规

11、划模型 当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。2.2.先放弃变量的整数性要求，解一个线性先放弃变量的整数性要求，解一个线性规划问题，然后用规划问题，然后用“四舍五入四舍五入”法取整法取整数解。数解。8.1 8.1 整数规划模型整数规划模型例例.某公司拟用集装箱托运甲、乙两种货物，这两种货某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如下物每件的体积、重量，可

12、获利润以及托运所受限制如下表所示，甲种货物至多托运表所示，甲种货物至多托运 4 4 件，问两种货物各托运多件，问两种货物各托运多少件，可使获得利润最大。少件，可使获得利润最大。货物货物每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲1951954 42 2乙乙27327340403 3托运限制托运限制13651365140140货物货物每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲1951954 42 2乙乙27327340403 3托运限制托运限制13651365

13、140140解：解：设设 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.ts.t.195.195x x1 1+273+273x x2 2 1365 1365 4 4x x1 1+40+40 x 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

14、2 分别为甲、乙两种货物托运的件数，显然分别为甲、乙两种货物托运的件数，显然 x x1 1、x x2 2 应该是非负整数，该问题的数学模型如下所示：应该是非负整数，该问题的数学模型如下所示：max max z z =2 =2x x1 1+3+3x x2 2 s.ts.t.195.195x x1 1+273+273x x2 2 1365 1365 4 4x x1 1+40+40 x x2 2 140 140 x x1 1 4 4 x x1 1，x x2 2 0 0 x x1 1，x x2 2 为整数。为整数。如果将上述整数线性规划中的最后一个约束：如果将上述整数线性规划中的最后一个约束：x1、x

15、2 为整数为整数去掉，它就是一个去掉，它就是一个线性规划线性规划的问题。的问题。用用图解法图解法来解这个整数规划，来解这个整数规划，以及与它相应的线性规划问题，以及与它相应的线性规划问题，并把它们的最优解加以比较。并把它们的最优解加以比较。max max z z =2 =2x x1 1+3+3x x2 2 s.ts.t.195.195x x1 1+273+273x x2 2 1365 1365 4 4x x1 1+40+40 x 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

16、 x1 1+3+3x x2 2 s.ts.t.195.195x x1 1+273+273x x2 2 1365 1365 4 4x x1 1+40+40 x 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.ts.t.195.195x x1 1

17、+273+273x x2 2 1365 1365 4 4x x1 1+40+40 x 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，这时其最优目标函数

18、值为这时其最优目标函数值为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 13 3，x x2 24 4 都不是此整数规划的可行解。都不是此整数规划的可行解。线性

19、规划的最优解线性规划的最优解 x x1 12.442.44，x x2 23.263.26，最优值为最优值为 14.6614.66整数规划的最优解整数规划的最优解 x x1 14 4 ，x x2 22 2，最优值为最优值为 14148.1 8.1 整数规划模型整数规划模型 当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。2.2.先放弃变量的整数性要求，解一个线性先放弃变量的整数性要求，解一个线性规划问题，然后用

20、规划问题，然后用“四舍五入四舍五入”法取整法取整数解。数解。这个这个整数规划的最优解整数规划的最优解并不可以将它对并不可以将它对应的应的线性规划的不为整数的最优解线性规划的不为整数的最优解进行进行四舍五入法或去尾法或进一法而得到的四舍五入法或去尾法或进一法而得到的。8.1 8.1 整数规划模型整数规划模型 当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：1.1.因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。比较后，总能求出最好方案。2.2.先放弃变量的整数性要求，解一个线性先放弃变量的整

21、数性要求，解一个线性规划问题，然后用规划问题，然后用“四舍五入四舍五入”法取整法取整数解。数解。结论：结论：求解整数规划问题必须要有自己的解法。求解整数规划问题必须要有自己的解法。8.1 8.1 整数规划模型整数规划模型 任何求任何求最大目标函数值最大目标函数值的纯整数的纯整数规划或混合整数规划的最大目标规划或混合整数规划的最大目标函数值，函数值，小于或等于小于或等于相应的线性相应的线性规划的规划的最大目标函数值最大目标函数值；任何求任何求最小目标函数值最小目标函数值的纯整数的纯整数规划或混合整数规划的最小目标规划或混合整数规划的最小目标函数值，函数值，大于或等于大于或等于相应的线性相应的线性

22、规划的规划的最小目标函数值最小目标函数值。max max z z =2 =2x x1 1+3+3x x2 2 s.ts.t.195.195x x1 1+273+273x x2 2 1365 1365 4 4x x1 1+40+40 x 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 整数规划

23、的应用整数规划的应用8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择例例 京成畜产品公司计划在市区的东、西、南、北四区建立京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有销售门市部，拟议中有 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

24、 5 两个点中至少选一个；两个点中至少选一个；在南区从在南区从 A A6 6 ，A A7 7 两个点中至少选一个；两个点中至少选一个；在北区从在北区从 A A8 8 ，A A9 9 ，A A1010 三个点中至少选两个。三个点中至少选两个。Aj 各点的设备投资及每年可获利润由于地点不同都是不各点的设备投资及每年可获利润由于地点不同都是不一样的。但投资总额不能超过一样的。但投资总额不能超过 720 万元，问应选择哪几个万元，问应选择哪几个销售点，可使年利润为最大销售点，可使年利润为最大?8.2 8.2 整数规划的应用整数规划的应用AT&TAT&T公司（美国电信电报公司）公司商业用户服务的电话销售

25、中心的优化选址公司商业用户服务的电话销售中心的优化选址一一用户规划及特征用户规划及特征二二竞争对手竞争对手三三地理位置地理位置四四成本的核算成本的核算五五交通状况交通状况 六六经营场地面积经营场地面积例例 京成畜产品公司计划在市区的东、西、南、北四区建立京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有销售门市部，拟议中有 10 10 个位置个位置 A Aj j (j j 1 1，2 2，3 3，10)10)可供选择，考虑到各地区居民的消费水平及居民居住可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：密集度，规定：在东区从在东区从 A A1 1 ，A A2 2 ，

26、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 万元，问应选择哪几个万元，问应选择哪几个销售点，可使年利润为最大销售点，可使年利润为最大?解：设：解

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

28、 x7 7+140+140 x x8 8+160+160 x x9 9+180+180 x 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 为为 01 01 变量，变量，j j=1=1，2 2，1010。用用“管理运筹学软件包管理运筹学软件包”中的中的 01 01 整数规划程序整数规划程序求解得：求解得：max max z z =245=245；x x1 1=x x2 2=x x5 5=x x6 6=x

29、x9 9=x x1010=1=1，其余为其余为 0 0。8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择二、固定成本问题二、固定成本问题例例 高压容器公司制造小、中、大三种尺寸的金属容器，高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示。不考虑固定费用，每种需的各种资源的数量如下表所示。不考虑固定费用，每种容器售出一只所得的利润分别为容器售出一只所得的利润分别为 4 4 万元、万元、5 5 万元、万元、6 6 万元，万元，可使用的金属板有

30、可使用的金属板有 500 500 吨，劳动力有吨，劳动力有 300 300 人月，机器有人月，机器有 100 100 台月，此外不管每种容器制造的数量是多少，台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是都要支付一笔固定的费用：小号是 l00 l00 万元，中号为万元，中号为 150 150 万元，大号为万元，大号为 200 200 万元万元。现在要制定一个生产计划，使获。现在要制定一个生产计划，使获得的利润为最大。得的利润为最大。固定成本问题固定成本问题“不管每种容器制造的数量是多少，都要支付一笔固不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是定的费用：

31、小号是 l00 l00 万元，中号为万元，中号为 150 150 万元，万元，大号为大号为 200 200 万元。万元。”解：这是一个整数规划问题。解：这是一个整数规划问题。设设 x x1 1，x x2 2，x x3 3 分别为小号容器、中号容器和大号容分别为小号容器、中号容器和大号容器的生产数量。器的生产数量。各种容器的固定费用只有在生产该种容器时才投入各种容器的固定费用只有在生产该种容器时才投入，即即 y yi i=1 1，当生产第当生产第 i i 种容器，即种容器，即 x xi i 0 0 时；时；y yi i=0 0，当不生产第当不生产第 i i 种容器，即种容器，即 x xi i =

32、0=0 时。时。可建立如下的数学模型：可建立如下的数学模型：max max z z=4=4x x1 1+5+5x x2 2+6+6x x3 3-100-100y y1 1-150-150y y2 2-200-200y 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 MM y yi i ，i i=1=1，2 2，3 3，x xj j 0 0，且为整数，且为整数，y yj j 为为 01

33、 01 变量，变量，j j=1=1，2 2，3 3。M 充分大，以保证当充分大，以保证当 yi =0 时时，xi=0。8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择二、固定成本问题二、固定成本问题三、指派问题三、指派问题例例.有四个工人，要分别指派他们完成四项不同的工作，有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。派工作，才能使总的消耗时间为最少。指派问题指派问题解：解：引入引入 01 01 变量变量 x xij ij，并令并令

34、x xij ij =1=1，当指派第当指派第 i i 人去完成第人去完成第 j j 项工作时；项工作时；x xij ij =0=0，当不指派第当不指派第 i i 人去完成第人去完成第 j j 项工作时。项工作时。这样该问题即被表示成一个这样该问题即被表示成一个 01 01 整数规划问题整数规划问题：min min 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

35、 x3333+19+19x x3434+19+19x x41 41+21+21x x4242+23+23x x4343+17+17x x4444s.t.s.t.x x1111+x x1212+x x1313+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 (丁只能干一项工作丁只能干一

36、项工作)x x1111+x x2121+x x3131+x x4141=1 (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 xij ij 为为 01 01 变量，变量，i i，j j=1=1，2 2，3 3，4 4。求解得求解得:min min z z =70=7

37、0；x x2121=1=1，x x1212=1=1，x x3333=1 1，x x4444=1 1。例例.有四个工人，要分别指派他们完成四项不同的工作，有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。派工作，才能使总的消耗时间为最少。指派问题指派问题8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择二、固定成本问题二、固定成本问题三、指派问题三、指派问题四、分布系统设计四、分布系统设计例例某企业在某企业在 A A1 1 地已有一个工厂，其

38、产品的生产能力为地已有一个工厂，其产品的生产能力为 30 30 千箱，千箱，为了扩大生产，打算在为了扩大生产，打算在 A A2 2，A A3 3，A A4 4，A A5 5 地中再选择几个地方建厂。地中再选择几个地方建厂。已知在已知在 A A2 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 建成厂的产量，那时销地的销量以及产地到销地的单位运价建

39、成厂的产量，那时销地的销量以及产地到销地的单位运价(每每千箱运费千箱运费)如下表所示。如下表所示。a)a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小固定成本和总的运输费用之和最小?b b)如果由于政策要求必须在如果由于政策要求必须在 A A2 2，A A3 3 地建一个厂，应在哪几个地地建一个厂，应在哪几个地方建厂方建厂?解：解：a)设设 xij 为从为从 Ai 运往运往 Bj 的运输量的运输量(单位千箱单位千箱)，yk=1，当当 Ak 被选中时；被选中时；yk=0，当当 Ak 没被选中时，没被选中

40、时，k=2，3，4，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 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+10 x x51 51+4+4x x5252+2+2x x5

41、353 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 x5151+x x5252+x x53 53 40 40y y5 5 (A (A5 5 厂的产量限制厂的产量限制)x

42、 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=20 (B=20 (B3 3 销地的限制销地的限制)x xij ij 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 为为 01 01 变量，变量，k k=2=2，3 3，

43、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 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+10 x x51 51+4+4x x5252+2+2x x5353 s.t.s.t.x x1111+x x1212+x x1313 30 (A 30 (A1 1 厂的

44、产量限制厂的产量限制)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 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

45、 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=20 (B=20 (B3 3 销地的限制销地的限制)x xij ij 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 为为 01 01 变量，变量，k k=2=2，3 3，4 4，5 5。分布系统设计分布系统设计 ReynoldsReynolds金属制品公司金属制品公司 200

46、200多个工厂、仓库和供应商的多个工厂、仓库和供应商的货物装载调度系统的自动化货物装载调度系统的自动化0 01 1 整数规划整数规划 DeltaDelta航空公司航空公司 超过超过25002500个国内航线的飞机类型配置个国内航线的飞机类型配置 以达到利润最大化以达到利润最大化8.2 8.2 整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择二、固定成本问题二、固定成本问题三、指派问题三、指派问题四、分布系统设计四、分布系统设计五、投资问题五、投资问题 -P183-P183 案例案例9 9案例案例9 9：华南公司投资方案：华南公司投资方案设设 X Xij ij 为第为第 i i

47、年在第年在第 j j 方案上的投资额，方案上的投资额，例如例如X X2121表示在第二年投资在项目表示在第二年投资在项目A A1 1上的金额上的金额Y Yijij=1=1，当第，当第 i i 年给第年给第 j j 项目投资时，项目投资时，Y Yijij=0=0，当第，当第 i i 年不给第年不给第 j j 项目投资时。项目投资时。因此第一年投资在项目因此第一年投资在项目A A1 1上的金额上的金额X X1111可表示为可表示为:X:X1111220Y220Y1111A A1 1：建立彩色印刷厂，第一、二年年初分别投入：建立彩色印刷厂，第一、二年年初分别投入220220万元万元和和220220万

48、元，第二年年底可获利万元，第二年年底可获利6060万元，第三年起每年万元，第三年起每年获利获利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

49、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企业，第二年投入企业，第二年投入180180万元设备，第三年万元设备，第三年起每年可获利起每年可获利5050万元万元 X

50、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 第二年初投入第二年初投入180180万元）万元）A A4 4：投资：投资D D企业，每年年

51、底可获投资额的企业，每年年底可获投资额的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万元）万元）Y Y1111-Y-Y2121=0 =0 （A A1 1 第一、二年都要投入）第一、二年都要投入）X X1212-70Y-70Y1212=0 =0 （A A2 2 第一年初

52、投入第一年初投入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每年递增不超过每年递增不超过 15 15 万元万元）X X4444-X-X343415 15 （A A4 4每年递增不超过每年递增不超过 15 15 万元万元）X X5454-X-X44441

53、5 15 （A A4 4每年递增不超过每年递增不超过 15 15 万元万元）A A5 5：建立细骨粉生产线，第三年投入：建立细骨粉生产线，第三年投入320320，第四年起每年，第四年起每年可获利可获利9090万元。万元。X X1111-220Y-220Y1111=0 =0 X X2121-220Y-220Y2121=0=0 Y Y1111-Y-Y2121=0=0 X X1212-70Y-70Y1212=0=0 X X2323-180Y-180Y2323=0=0 X X14148080 X X2424-X-X14141515 X X3434-X-X24241515 X X4444-X-X3434

54、1515 X X5454-X-X44441515 X X3535-320Y-320Y3535=0=0 (A(A5 5 第一年初投入第一年初投入220220万元万元)A A6 6：投资所属中北机电设备公司，年底回收本利：投资所属中北机电设备公司，年底回收本利120120。但每年投资额不低于但每年投资额不低于6060万元。万元。X X1111-220Y-220Y1111=0 =0 X X2121-220Y-220Y2121=0=0 Y Y1111-Y-Y2121=0=0 X X1212-70Y-70Y1212=0=0 X X2323-180Y-180Y2323=0=0 X X14148080 X

55、X2424-X-X14141515 X X3434-X-X24241515 X X4444-X-X34341515 X X5454-X-X44441515 X X3535-320Y-320Y3535=0=0 (A(A5 5 第一年初投入第一年初投入220220万元万元)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 每年投资不低于每年

56、投资不低于6060万元）万元）X X565660 60 （A A6 6 每年投资不低于每年投资不低于6060万元）万元）A A7 7：投资所属澳得技术公司，年底回收本利：投资所属澳得技术公司，年底回收本利115115。X X1111-220Y-220Y1111=0 =0 X X2121-220Y-220Y2121=0=0 Y Y1111-Y-Y2121=0=0 X X1212-70Y-70Y1212=0=0 X X2323-180Y-180Y2323=0=0 X X14148080 X X2424-X-X14141515 X X3434-X-X24241515 X X4444-X-X34341

57、515 X X5454-X-X44441515 X X3535-320Y-320Y3535=0=0 (A(A5 5 第一年初投入第一年初投入220220万元万元)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

58、万元）万元）一、项目资金约束一、项目资金约束 X X1111-220Y-220Y1111=0 =0 X X2121-220Y-220Y2121=0=0 Y Y1111-Y-Y2121=0=0 X X1212-70Y-70Y1212=0=0 X X2323-180Y-180Y2323=0=0 X X14148080 X X2424-X-X14141515 X X3434-X-X24241515 X X4444-X-X34341515 X X5454-X-X44441515 X X3535-320Y-320Y3535=0=0 X X16166060 X X26266060 X X36366060

59、X X46466060 X X56566060一、项目资金约束一、项目资金约束二、年度资金约束二、年度资金约束投资总额为投资总额为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+1.2X1616+1.15X+1.15X1717+300+300第三年第三年:X:X3434

60、+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+X5757 =130Y =130Y1111+18Y+18Y1212+50Y+50Y2323+0.25X+0

61、.25X4444+90Y+90Y3535+1.2X+1.2X4646+1.15X+1.15X4747一、项目资金约束一、项目资金约束二、年度资金约束二、年度资金约束三、目标函数三、目标函数A A1 1：建立彩色印刷厂，第一、二年年初分别投入：建立彩色印刷厂，第一、二年年初分别投入220220万元和万元和220220万万元，第二年年底可获利元，第二年年底可获利6060万元，万元，第三年起每年获利第三年起每年获利130130万元万元;A A2 2：投资离子镀膜基地，第一年投资：投资离子镀膜基地，第一年投资7070万元，万元，第二年起每年可获第二年起每年可获利利1818万元万元;A A3 3：投资参

62、股：投资参股F F企业，第二年投入企业，第二年投入180180万元设备，万元设备，第三年起每年可第三年起每年可获利获利5050万元万元A A4 4：投资：投资D D企业，每年年底企业，每年年底可获投资额的可获投资额的2525利润利润，但是第一年，但是第一年最高投资额为最高投资额为 80 80 万元，以后每年递增不超过万元，以后每年递增不超过 15 15 万元。万元。A A5 5：建立细骨粉生产线，第三年投入：建立细骨粉生产线，第三年投入320320，第四年起，第四年起每年可获利每年可获利9090万元万元。A A6 6：投资所属中北机电设备公司，：投资所属中北机电设备公司，年底回收本利年底回收本

63、利120120。但每年。但每年投资额不低于投资额不低于6060万元。万元。A A7 7：投资所属澳得技术公司，：投资所属澳得技术公司，年底回收本利年底回收本利115115。案例案例9 9：华南公司投资方案：华南公司投资方案解：解：设设 X Xij ij 为第为第 i i 年在第年在第 j j 方案上的投资额，方案上的投资额，Y Yijij=1=1，当第，当第 i i 年给第年给第 j j 项目投资时，项目投资时，Y Yijij=0=0，当第，当第 i i 年不给第年不给第 j j 项目投资时。项目投资时。MAX 130YMAX 130Y1111+18Y+18Y1212+50Y+50Y2323+

64、0.25X+0.25X5454+90Y+90Y3535+1.2X+1.2X5656+1.15X+1.15X5757X 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=0X X16166060X

65、 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.25X1414+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

66、+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=130Y1111+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 整数规划模型整数规划模型n 8.2 8.2 整数规划的应用整数规划的应用n8.3 8.3 整数规划的分枝定界法整数规划的分枝定界法8.8.3 3 整数规划的分枝定界法整数规划的分枝定界法 分枝定界法是求解整数规划的一种常分枝定界法是求解整数规划的一种常用的有效的方法