第八章整数规划.ppt
《第八章整数规划.ppt》由会员分享,可在线阅读,更多相关《第八章整数规划.ppt(131页珍藏版)》请在三一文库上搜索。
1、第八章 整数规划,Integer Programming,第八章 整数规划,在前面讨论的线性规划问题中,最优解可能是整数,也可能不是整数,但对于某些实际问题,要求答案必须是整数。如, 所求的解是安排上班的人数, 按某个方案裁剪钢材的根数, 生产机器的台数等。,第八章 整数规划,8.1 整数规划模型,8.1 整数规划模型,整数规划模型的一般形式,Max(或Min) Z = cjxj s.t. aijxj ( 或 = , ) bi i=1,2, , m xj 0 j=1,2, , n x1 , x2 , xn 中部分或全部取整数,8.1 整数规划模型,在线性规划模型中,如果所有的决策变量都要求为非
2、负整数,则这样的线性规划问题称之为纯整数规划问题。 如果只有一部分决策变量要求为非负整数,则这样的线性规划问题称之为混合整数规划问题。 如果决策变量的取值只限于 0 和 1,则这样的整数线性规划问题称之为 01型整数规划问题。,8.1 整数规划模型,例:一登山队员做登山准备,他需要携带的物品有:食品,氧气,冰镐,绳索,帐篷,照相机和通讯设备,每种物品的重要性系数和重量如下:假定登山队员可携带最大重量为25公斤。,8.1 整数规划模型,解: 令xi=1表示登山队员携带物品i, xi=0表示登山队员不携带物品i: Max Z= 20x1+15x2 +18x3 +14x4+8x5+4x6+10x7
3、s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 xi=1 或 xi=0 i=1,2,.7,8.1 整数规划模型,背包问题( Knapsack Problem) 一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,有限制: 最多只能装b公斤的物品 而每件物品只能整个携带 每件物品规定了一个“价值”以表示其有用的程度 如果共有n件物品,第 j 件物品aj公斤,其价值为cj. 问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?,8.1 整数规划模型,背包问题( Knapsack Problem),解: 令xj=1表示携
4、带物品j, xj=0表示不携带物品j, Max Z = cjxj s.t. ajxj b xj=0 或 1,8.1 整数规划模型,解: 令xi=1表示登山队员携带物品i, xi=0表示登山队员不携带物品i: Max Z= 20x1+15x2 +18x3 +14x4+8x5+4x6+10x7 s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 xi=1 或 xi=0 i=1,2,.7,8.1 整数规划模型,当人们开始接触整数规划问题时,常会有如下两种初始想法: 因为可行方案数目有限,因此经过一一比较后,总能求出最好方案。 例如,背包问题充其量有 2n种方式,8
5、.1 整数规划模型,解: 令xi=1表示登山队员携带物品i, xi=0表示登山队员不携带物品i: Max Z= 20x1+15x2 +18x3 +14x4+8x5+4x6+10x7 s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 xi=1 或 xi=0 i=1,2,.7,8.1 整数规划模型,当人们开始接触整数规划问题时,常会有如下两种初始想法: 因为可行方案数目有限,因此经过一一比较后,总能求出最好方案。 实际上这种方法是不可行。 设想计算机每秒能比较1000000个方式, 那么要比较完20!(大于2*1018)种方式, 大约需要800年。 那么要比较
6、完比较完260种方式, 大约需要360世纪,8.1 整数规划模型,当人们开始接触整数规划问题时,常会有如下两种初始想法: 因为可行方案数目有限,因此经过一一比较后,总能求出最好方案。 先放弃变量的整数性要求,解一个线性规划问题,然后用“四舍五入”法取整数解。,8.1 整数规划模型,例. 某公司拟用集装箱托运甲、乙两种货物,这两种货物每件的体积、重量,可获利润以及托运所受限制如下表所示,甲种货物至多托运 4 件,问两种货物各托运多少件,可使获得利润最大。,解:设 x1、x2 分别为甲、乙两种货物托运的件数,显然 x1、x2 应该是非负整数,该问题的数学模型如下所示: max z = 2x1 +
7、3x2 s.t. 195x1 + 273x2 1365 4x1 + 40x2 140 x1 4 x1,x2 0 x1,x2 为整数。,解:设 x1、x2 分别为甲、乙两种货物托运的件数,显然 x1、x2 应该是非负整数,该问题的数学模型如下所示: max z = 2x1 + 3x2 s.t. 195x1 + 273x2 1365 4x1 + 40x2 140 x1 4 x1,x2 0 x1,x2 为整数。 如果将上述整数线性规划中的最后一个约束: x1、x2 为整数去掉,它就是一个线性规划的问题。 用图解法来解这个整数规划, 以及与它相应的线性规划问题, 并把它们的最优解加以比较。,max z
8、 = 2x1 + 3x2 s.t. 195x1 + 273x2 1365 4x1 + 40x2 140 x1 4 x1,x2 0,max z = 2x1 + 3x2 s.t. 195x1 + 273x2 1365 4x1 + 40x2 140 x1 4 x1,x2 0,1,2,3,4,1,2,3,x2,x1,平移目标函数的等值线,得线性规划的最优解为 x12.44,x23.26, 目标函数的最优值为14.66。,2x1+3x214.66,max z = 2x1 + 3x2 s.t. 195x1 + 273x2 1365 4x1 + 40x2 140 x1 4 x1,x2 0 x1,x2 为整数
9、,2x1+3x214,同样把目标函数的等值线尽量向右上方移以便取得最大值,同时又必须过整数规划的可行点,可得整数规划的最优解 x14,x22, 这时其最优目标函数值为14。,8.1 整数规划模型,当我们对相应的线性规划的最优解进行四舍五入或去尾法时,得 x12,x23,这时目标函数值为 13,并不是此整数规划的最优解。 当我们对相应的线性规划的最优解进行进一法时, 取 x13, x23; x12, x2 4; x13,x24 都不是此整数规划的可行解。,线性规划的最优解 x12.44,x23.26, 最优值为 14.66 整数规划的最优解 x14 ,x22, 最优值为 14,8.1 整数规划模
10、型,当人们开始接触整数规划问题时,常会有如下两种初始想法: 因为可行方案数目有限,因此经过一一比较后,总能求出最好方案。 先放弃变量的整数性要求,解一个线性规划问题,然后用“四舍五入”法取整数解。 这个整数规划的最优解并不可以将它对应的线性规划的不为整数的最优解进行四舍五入法或去尾法或进一法而得到的。,8.1 整数规划模型,当人们开始接触整数规划问题时,常会有如下两种初始想法: 因为可行方案数目有限,因此经过一一比较后,总能求出最好方案。 先放弃变量的整数性要求,解一个线性规划问题,然后用“四舍五入”法取整数解。 结论: 求解整数规划问题必须要有自己的解法。,8.1 整数规划模型,任何求最大目
11、标函数值的纯整数规划或混合整数规划的最大目标函数值,小于或等于相应的线性规划的最大目标函数值; 任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值,大于或等于相应的线性规划的最小目标函数值。,max z = 2x1 + 3x2 s.t. 195x1 + 273x2 1365 4x1 + 40x2 140 x1 4 x1,x2 0 x1,x2 为整数,2x1+3x214.66,2x1+3x214,A,B,第八章 整数规划,8.1 整数规划模型 8.2 整数规划的应用,8.2 整数规划的应用,一、投资场所的选择,例 京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部,拟议中有
12、10 个位置 Aj ( j 1,2,3,10 ) 可供选择,考虑到各地区居民的消费水平及居民居住密集度,规定: 在东区从 A1 , A2 ,A3 三个点中至多选择两个; 在西区从 A4 , A5 两个点中至少选一个; 在南区从 A6 , A7 两个点中至少选一个; 在北区从 A8 , A9 , A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的。但投资总额不能超过 720 万元,问应选择哪几个销售点,可使年利润为最大?,8.2 整数规划的应用,AT&T公司(美国电信电报公司),公司商业用户服务的电话销售中心的优化选址,用户规划及特征 竞争对手 地理位置 成
13、本的核算 交通状况 经营场地面积,例 京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部,拟议中有 10 个位置 Aj ( j 1,2,3,10 ) 可供选择,考虑到各地区居民的消费水平及居民居住密集度,规定: 在东区从 A1 , A2 ,A3 三个点中至多选择两个; 在西区从 A4 , A5 两个点中至少选一个; 在南区从 A6 , A7 两个点中至少选一个; 在北区从 A8 , A9 , A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的。但投资总额不能超过 720 万元,问应选择哪几个销售点,可使年利润为最大?,解:设:01 变量 xi =
14、1, 当 Ai 点被选用时; xi = 0 ,当 Ai 点没被选用时。,max z = 36x1 + 40x2 + 50x3 + 22x4 + 20x5 + 30x6 + 25x7 + 48x8 + 58x9 + 61x10 s. t. 100x1+120x2+150x3+80x4+70x5+90x6 +80x7+140x8+160x9 +180x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 ,且 xj 为 01 变量,j = 1,2,10。,用 “管理运筹学软件包” 中的 01 整数规划程序求解得: max z
15、= 245; x1 = x2 = x5 = x6 = x9 = x10 = 1,其余为 0 。,8.2 整数规划的应用,一、投资场所的选择 二、固定成本问题,例 高压容器公司制造小、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机器设备,制造一个容器所需的各种资源的数量如下表所示。不考虑固定费用,每种容器售出一只所得的利润分别为 4 万元、5 万元、6 万元,可使用的金属板有 500 吨,劳动力有 300 人月,机器有 100 台月,此外不管每种容器制造的数量是多少, 都要支付一笔固定的费用:小号是 l00 万元,中号为 150 万元,大号为 200 万元。现在要制定一个生产计划,使获得
16、的利润为最大。,固定成本问题,“不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是 l00 万元,中号为 150 万元,大号为 200 万元。”,解:这是一个整数规划问题。 设 x1,x2, x3 分别为小号容器、中号容器和大号容器的生产数量。 各种容器的固定费用只有在生产该种容器时才投入, 即 yi = 1, 当生产第 i 种容器,即 xi 0 时; yi = 0, 当不生产第 i 种容器,即 xi = 0 时。,可建立如下的数学模型: max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s. t. 2x1 + 4x2 + 8x3 500
17、 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ,i =1,2,3, xj 0,且为整数,yj 为 01 变量,j = 1,2,3。 M 充分大,以保证当 yi = 0 时,xi = 0 。,8.2 整数规划的应用,一、投资场所的选择 二、固定成本问题 三、指派问题,例.有四个工人,要分别指派他们完成四项不同的工作,每人做各项工作所消耗的时间如下表所示,问应如何指派工作,才能使总的消耗时间为最少。,指派问题,解:引入 01 变量 xij,并令 xij = 1, 当指派第 i 人去完成第 j 项工作时; xij = 0, 当不指派第 i 人去完成第
18、 j 项工作时。 这样该问题即被表示成一个 01 整数规划问题: min z =15x11+18x12+21x13+24x14 +19x21+23x22+22x23+18x24 +26x31 +17x32+16x33+19x34 +19x41 +21x42+23x43+17x44,s. t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作),x11+ x21+ x31+ x41= 1
19、 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 为 01 变量,i,j = 1,2,3,4。 求解得: min z = 70; x21=1, x12 = 1, x33 = 1, x44 = 1 。,例.有四个工人,要分别指派他们完成四项不同的工作,每人做各项工作所消耗的时间如下表所示,问应如何指派工作,才能使总的消耗时间为最少。,指派问题,8.2 整数规划的应用,一、投资场所的选择 二、固定成本问题 三、指
20、派问题 四、分布系统设计,例某企业在 A1 地已有一个工厂,其产品的生产能力为 30 千箱,为了扩大生产,打算在 A2,A3,A4,A5 地中再选择几个地方建厂。已知在 A2 , A3,A4,A5 地建厂的固定成本分别为 175 千元、300 千元、375 千元、500 千元,另外, A1 产量及 A2,A3,A4,A5 建成厂的产量,那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。 a) 问应该在哪几个地方建厂,在满足销量的前提下,使得其总的固定成本和总的运输费用之和最小? b) 如果由于政策要求必须在 A2,A3 地建一个厂,应在哪几个地方建厂?,解: a) 设 xij 为
21、从 Ai 运往 Bj 的运输量(单位千箱), yk = 1,当 Ak 被选中时; yk = 0,当 Ak 没被选中时, k =2,3,4,5。 这样我们的问题可以被表示成一个(混合)整数规划问题:,min z = 175y2+300y3+375y4+500y5 + 8x11+4x12+3x13 +5x21+2x22+3x23 +4x31+3x32+4x33 +9x41 +7x42+5x43 +10x51 +4x52+2x53 s. t. x11+ x12+ x13 30 ( A1 厂的产量限制) x21+ x22+ x23 10y2 ( A2 厂的产量限制) x31+ x32+ x33 20y
22、3 ( A3 厂的产量限制) x41+ x42+ x43 30y4 ( A4 厂的产量限制) x51+ x52+ x53 40y5 ( A5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制) xij 0,且为整数,i = 1,2,3,4,5; j = 1,2,3, yk 为 01 变量,k = 2,3,4,5。,min z = 175y2+300y3+375y4+500y5 +
23、8x11+4x12+3x13 +5x21+2x22+3x23 +4x31+3x32+4x33 +9x41 +7x42+5x43 +10x51 +4x52+2x53 s. t. x11+ x12+ x13 30 ( A1 厂的产量限制) x21+ x22+ x23 10y2 ( A2 厂的产量限制) x31+ x32+ x33 20y3 ( A3 厂的产量限制) x41+ x42+ x43 30y4 ( A4 厂的产量限制) x51+ x52+ x53 40y5 ( A5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 整数 规划
链接地址:https://www.31doc.com/p-2565059.html