运筹学PPT 第四章 线性整数规划

1、第四章 线性整数规划整数规划整数规划变量只能取整数的规划问题。变量只能取整数的规划问题。 当变量只能取当变量只能取0或或1两个值，两个值， 称称0-1规划。规划。整数规划的分类：整数规划的分类： 纯整数规划：所有变量都限制为整数纯整数规划：所有变量都限制为整数 混合整数规划：仅部分变量限制为整数混合整数规划：仅部分变量限制为整数 0-10-1整数规划：变量的取值仅限于整数规划：变量的取值仅限于0 0或或1 1整数规划的解法：分枝定界法或割平面法整数规划的解法：分枝定界法或割平面法 基本思想是把一个整数规划问题化为一基本思想是把一个整数规划问题化为一系列的线性规划问题来求解系列的线性规划问题来求

2、解例13 投资场所选址问题 计划在东、西、南三个区开设若干商业网点，拟在A1，A7 7个地点中选择。规定：东区在A1，A2，A3中至多选2个，西区在A4，A5中至少选1个，南区在A6，A7中至少选1个。已知在Ai建点需投资bi，可获利ci，现共有资金为B。问应如何布局可使总利润最大？分析：xbxcAAAxAAxx需投资为的利润为则不选选中即的选择变量分别表示地址决策变量, 0 1,7171变量是则模型为不选选中解：设10,1127176543217171xxxxxxxxxBxbxcMaxzAAxiiiiiiiii 0 1东区在A1，A2，A3中至多选2个怎样表示？2321xxx例14 固定费用

3、问题 某工厂为生产某种产品，有3种不同的生产方式可供选择。设第j种生产方式的固定成本为kj，可变成本为cj 。若不考虑其他约束，请建立使总成本最小的规划模型。0 0 0 , jjjjjjxxxckjxj种方式时的成本为则使用第种生产方式时的产量为设采用第分析： 0, 00, ,1 种生产方式时即不采用第，种生产方式时即采用第若设jxj xyjjj)()()(333322221111xcykxcykxcykz则总费用100或初步建立模型为jjyxxcykxcykxcykMinz)()()(333322221111怎样解决？时必有问题：不能保证当1,0jjyx的上界。则最后模型为为加约束jjjjj

4、xMyMx , 100)()()(333322221111或jjjjjyyMxxxcykxcykxcykMinz 例例 人力资源分配的问题人力资源分配的问题 某昼夜服务的公交线路每天各时间段内所需司机和乘某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员足工作需要，又配备最少司机和乘务人员? ?班次班次时间时间所需人数所需人数1

5、6 6：00 00 10 10：00006021010：00 00 14 14：00007031414：00 00 18 18：00006041818：00 00 22 22：00005052222：00 00 2 2：00002062 2：00 00 6 6：000030 解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘务人班次时开始上班的司机和乘务人员数员数, ,于是于是L3L3模型为模型为: : x x1 1 + x + x6 6 60 60 x x1 1 + x + x2 2 70 70 x x2 2 + x + x3 3 60 60 x x3 3 + x + x

6、4 4 50 50 x x4 4 + x + x5 5 20 20 x x5 5 + x + x6 6 30 30 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6 0 0且为整数且为整数min z=xmin z=x1 1 + x + x2 2 + x + x3 3 + x + x4 4 + x + x5 5 + x + x6 6 班班 次次 时时 间间 所所 需需 人人 数数 1 6： 00 10： 00 60 2 10： 00 14： 00 70 3 14： 00 18： 00 60 4 18： 00 22： 00 50 5 22： 00 2： 00 20

7、 6 2： 00 6： 00 30 最优解：最优解：X* =(60 ，10，50 ，0 ，30 ，0），）， Z*=150二、二、 0-10-1整数规划整数规划 投资场所的选址问题投资场所的选址问题 指派问题指派问题 背包问题背包问题 消防队问题消防队问题1. 投资场所的选址问题投资场所的选址问题 某城市拟在东、西、南三区设立商业网点，备选位置有某城市拟在东、西、南三区设立商业网点，备选位置有A1A7共共7个，如果选个，如果选Ai，估计投资为，估计投资为bi元，利润为元，利润为ci元，要元，要求总投资不超过求总投资不超过B元，规定元，规定 东区：东区：A1、A2、A3中至多选中至多选2个个 西

8、区：西区：A4、A5中至少选一个中至少选一个 南区：南区：A6、A7中至少选一个中至少选一个问如何设点使总利润最大？问如何设点使总利润最大？ 1， Ai被选中被选中 0， Ai没被选中没被选中 解：令解：令 xi=max z= 71iiixcxi=0或或 1，i=1, ,7 bixiBi=17x1+x2+x32x4+x51x6+x71s.t.课堂练习课堂练习1: 某钻井队要从某钻井队要从S1S10共共10个井位中确定五个钻个井位中确定五个钻井探油，如果选井探油，如果选Si，估计钻探费用为，估计钻探费用为ci元，并且元，并且井位选择上要满足下列条件：井位选择上要满足下列条件： （1）或选择或选择

9、S1和和S7，或选择，或选择S8 ; （2）选择了选择了S3或或S4就不能选择就不能选择S5，反，反 过来也一样过来也一样;（3）在在S5，S6 ，S7，S8中最多只能选中最多只能选两个。两个。问如何选择井位使总费用最小？问如何选择井位使总费用最小？ 课堂练习课堂练习1: 某钻井队要从某钻井队要从S1S10共共10个井位中确定五个钻井探油，个井位中确定五个钻井探油，如果选如果选Si，估计钻探费用为，估计钻探费用为ci元，并且井位选择上要满足下列条件：元，并且井位选择上要满足下列条件： （1）或选择）或选择S1和和S7，或选择，或选择S8 （2）选择了）选择了S3或或S4就不能选择就不能选择S5

10、，反过来也一样，反过来也一样 （3）在）在S5，S6 ，S7，S8中最多只能选两个中最多只能选两个问如何选择井位使总费用最小？问如何选择井位使总费用最小？ 1， Si被选中被选中 0， Si没被选中没被选中 解：令解：令 xi=min z= 101iiixcs.t. 5101iix 181 xx187 xx153 xx154 xx28765xxxx或 1，i=1, ,10 0ix 某篮球队有某篮球队有8名队员，其身高和专长如下表，现要选名队员，其身高和专长如下表，现要选拔拔5名球员上场参赛，要求：名球员上场参赛，要求：（1）中锋只有）中锋只有1人上场人上场（2）后卫至少有一人上场）后卫至少有一

11、人上场（3）只有）只有2号上场，号上场，6号才上场号才上场要求平均身高最高，应如何选拔队员？要求平均身高最高，应如何选拔队员？队队员员 1 2 3 4 5 6 7 8 身身高高 1.92 1.90 1.88 1.86 1.85 1.83 1.80 1.78 专专长长 中中锋锋 中中锋锋 前前锋锋 前前锋锋 前前锋锋 后后卫卫 后后卫卫 后后卫卫 课堂练习课堂练习2:1， 队员队员i被选中被选中 0，队员，队员i没被选中没被选中 解：令解：令 xi=max z= 8151iiixc 581iix 121 xx1876xxx 26xx 或 1，i=1, ,8 0ixs.t. 某篮球队有某篮球队有8

12、名队员，其身高和专长如下表，现要选名队员，其身高和专长如下表，现要选拔拔5名球员上场参赛，要求：名球员上场参赛，要求：（1）中锋只有）中锋只有1人上场人上场（2）后卫至少有一人上场）后卫至少有一人上场（3）只有）只有2号上场，号上场，6号才上场号才上场要求平均身高最高，应如何选拔队员？要求平均身高最高，应如何选拔队员？2. 指派问题指派问题 例：例： 有一份中文说明书，需译成英、日、德、俄四种文字，有一份中文说明书，需译成英、日、德、俄四种文字，分别记作任务分别记作任务E、J、G、R，现有甲、乙、丙、丁四人，他们，现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种说明书所需的时间如下表所示

13、，将中文说明书翻译成不同语种说明书所需的时间如下表所示，问应指派何人去完成何项任务，使所需总时间最少？问应指派何人去完成何项任务，使所需总时间最少？ E J G R 甲甲 2 15 13 4 乙乙 10 4 14 15 丙丙 9 14 16 13 丁丁 7 8 11 9 问题描述：问题描述：n项任务可由项任务可由n个人完成，由于专长不同，各人个人完成，由于专长不同，各人完成各任务的时间也不同，求最优安排。完成各任务的时间也不同，求最优安排。要求：要求：每人只能完成一项任务，每项任务只能由一人完成。每人只能完成一项任务，每项任务只能由一人完成。 x x1111+ + x x1212+ + x x

14、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 (

15、 E= 1 ( E任务只能一人干任务只能一人干) ) x x1212+ + x x2222+ + x x3232+ + x x4242= 1 ( J= 1 ( J任务只能一人干任务只能一人干) ) x x1313+ + x x2323+ + x x3333+ + x x4343= 1 ( G= 1 ( G任务只能一人干任务只能一人干) ) x x1414+ + x x2424+ + x x3434+ + x x4444= 1 ( 5= 1 ( 5任务只能一人干任务只能一人干) ) x xijij = 0 = 0 或或 1 1，i,j i,j = 1,2,3,4= 1,2,3,4min z=2m

16、in z=2x x1111+15+15x x1212+13+13x x1313+4+4x x1414+10+10 x x2121+4+4x x2222+14+14x x2323+15+15x x2424 +9 +9x x3131+14+14x x3232+16+16x x3333+13+13x x3434+7+7x x41 41 +8+8x x4242+11+11x x4343+9+9x x44441， 指派第指派第i人去完成第人去完成第j项任务项任务 0， 不指派第不指派第i人去完成第人去完成第j项任务项任务 解：令解：令 xij=课堂练习课堂练习:P57例例2.23例：例：甲、乙、丙、丁是

17、四名游泳运动员，他们各种甲、乙、丙、丁是四名游泳运动员，他们各种姿势的姿势的100m游泳成绩如表。为组成一个游泳成绩如表。为组成一个4100m混合泳接力队，怎样选派运动员，方使接力队的游混合泳接力队，怎样选派运动员，方使接力队的游泳成绩最好？泳成绩最好？运动员运动员仰泳仰泳蛙泳蛙泳蝶泳蝶泳自由泳自由泳甲甲75.586.866.658.4乙乙65.866.257.052.8丙丙67.684.377.859.1丁丁74.069.460.857.03. 背包问题背包问题问题描述问题描述已知：已知：一个背包最大容量为一个背包最大容量为b公斤；有公斤；有m件物品供选择，每件物品供选择，每件物品重件物品重

18、ai公斤，价值为公斤，价值为ci（i=1,m）。）。问题：问题：携带哪些物品可使总价值最大？携带哪些物品可使总价值最大？一般模型一般模型 miiixczMax1s.t.bxamiii 110或或 ix1， 物品物品i被选中被选中 0，物品，物品i没被选中没被选中 xi=例：例：一个徒步旅行者要在背包中选择一些最有价值的物品携一个徒步旅行者要在背包中选择一些最有价值的物品携带。他最多能带带。他最多能带115kg的物品，现有的物品，现有5件物品，分别重件物品，分别重54、35、57、46、19kg，其价值依次为，其价值依次为7、5、9、6、3。问携带哪些物。问携带哪些物品可使总价值最大？品可使总价值最大？解：解：模型为：模型为：5432136957xxxxxZMax s.t.115194657355454321 xxxxx),51,i (10 或或ix4. 消防队问题消防队问题