整数规划及其应用.ppt

,物流运筹学方法,缪兴锋 教授/高级工程师 联系方法：13802924378 E-mail: wuliuxitong 广东轻工职业技术学院 2013,第三章 整数规划,整数规划 (Integer Programming，简记IP)是近30年来发展起来的、规划论的一个分支。 线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。 例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。 要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划。,对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划； 如果仅要求部分决策变量取整数，称为混合整数规划问题； 有的问题要求决策变量仅取0或1两个值,称为0-1规划问题.,例如1：生产安排问题,问如何安排甲、乙两产品的产量，使利润为最大。,解题：,用WINQSB软件求解,用WINQSB软件求解,第一步：,第二步：,第三步：,分析结果,X1=3.11 ; x2= 2.77 Max Z=32.556,当 X1 , X 2 取整数的几种情况 不考虑整数约束则是一个LP问题, 称为原整数规划的松弛问题。不考虑整数约束的最优解： x1 *=28/9， x2 * =25/9，Z * =293/9 舍入化整 (1) x1 =3， x2 =3，Z =33，不满足约束条件5x1 +7 x2 35，非可行解； (2) x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解； (3) x1 =4， x2 =1，Z =29，满足约束条件，才是最优解。,x1, x2 取整数 不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题。不考虑整数约束的最优解：x1 *=28/9， x2 * =25/9，Z * =293/9 舍入化整 x1 =3， x2 =3，Z =33，不满足约束条件5x1 +7 x2 35，非可行解； x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解； x1 =4， x2 =1，Z =29，满足约束条件，才是最优解。,一、问题的提出,为了满足整数要求，似乎可以把线性规划的小数最优解进行“舍入化整”以得到与最优解相近的整数解。 “舍入化整”一般是不可行的： 化整后的解有可能成为非可行解； 虽是可行解，却不是最优解。,解法概述,当人们开始接触整数规划问题时，常会有如下两种初始想法： 因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式； 连线问题充其量有n!种方式；实际上这种方法是不可行。,设想计算机每秒能比较100 0 000个式。 那么要比较完20!（大于2*1018）种方式，大约需要800年。 比较完260种方式，大约需要360世纪。,先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。,说明：,1. 整数规划只是线性规划问题中的一个特例。 2. 求整数规划问题用线性规划方法并不能完全得出最佳解，还需要采用其他特殊方法。,例2：背包问题,某人有一背包可以装10公斤重、0.025M3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。问每件物品各装多少件，所装物品的总价值最大。,解：设甲、乙两种物品各装X1，X2件，则数学模型：,Max Z 4X13X2,（1）用图解法画出可行域,（2）用WINQSB软件求解,第一步：,第二步：,第三步：,分析:,由软件计算得： X1=3.5; X2=7.1, Max Z = 35.71 由于x1, x2 必须取整数值，整数规划问题的可行解只是线性规划可行域内的那些整数点。 用凑整法求解时需要比较四种组合: （4,7）;（4,8）; （3,8）; （3,7）。 显然，（4,7）;（4,8）; （3,8）都不是可行解， （3,7）虽是可行解，代入目标函数得Z=33。 实际上得最优解是（5, 5），Z=35. 即两种物品各装5件，总价值35元。,实例-3,一登山队员做登山准备，他需要携带的物品有： 食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下： 假定登山队员可携带最大重量为25公斤。,解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:,Max Z= 20 x1+15x2 +18x3 +14x4 +8x5 +4x6 +10 x7,用WINQSB软件求解,联 系 实 例-4,某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。 这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。,物品的容量及价格对照表,问题分析,变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中,约束,包裹容量限制,必带物品限制,选带物品限制,目标函数未带物品购买费用最小,模 型,S.t.,例-5：,假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02M3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大： （1）所装物品不变； （2）如果选择旅行箱，则只能装载丙和丁两种物品。如下表所示。则载重量和体积的约束为：,解：此问题可以建立两个整数规划模型。,引入01变量（或称逻辑变量）yi,令,i=1, 2 分别是采用背包及旅行箱装载。,（1）由于所装物品不变， 式,Max Z 4X13X2,上式 约束左边不变，整数规划数学模型为：,Max Z 4X13X2,（2）由于不同载体所装物品不一样，但物品价值相同，目标函数不变，数学模型为：,Max Z 4X13X2,式中，M 为充分大的正数。,从上式可知： 当使用背包时（ y1=1，y2 =0 ），（2）式（4）式是多余的，即约束条件不起作用； 当使用旅行箱时（ y1=0，y2 =1 ），（1）式（3）式是多余的，即约束条件不起作用；,二、模型描述,整数规划问题就是要求决策变量取整数值的线性或非线性规划问题。 因此，整数规划分为： 整数线性规划 (I LP) 整数非线性规划 (IN LP) 两类。,按对变量的不同要求，还可将整数规划分为下述几种类型：, 纯整数规划 (Pure IP)或全整数规划( All IP)：要求全部变量都取整数值。 混合整数规划( Mixed IP)：只要求一部分变量取整数值 0-1整数规划（binary programming, 简记为 BIP）。要求全部或部分变量只取0或1值。,在管理与规划的大量问题中，常要求变量 满足取整条件,如： 生产计划中， 生产机器多少台（整数）； 人力资源管理中，招聘员工多少人（整数）； 运输问题中，从一个港口到另一个港口的集装箱调运数量（整数）。,另外，运作管理中的决策问题，如： 物流中心选址、 人员的工作指派、 设备购置和配置、 系统可靠性设计、 机床加工任务的均衡分派等等。 从技术角度看，这些问题的规划模型不同于前述的线性规划范畴，而属于一种新的类型整数规划。,例如-6 挑选球队队员问题,2. 某篮球教练要从8名业余队员中挑选3名队员参加专业球队，使平均身高达到最高。队员的号码、身高及所擅长的位置如下表 所示。要求：中锋1人；后卫1人；前锋1人，但1号、3号与6号队员中必须保留1人给业余球队。,表2-27 队员身高,解：设：Xj 1 表示j号队员被挑选 Xj 0表示j号队员不被挑选,Max F(X) 1.92 X11.91X21.90X31.86X41.85X51.83X61.80X7 1.79X8,用WINQSB软件求解,第一步：,第二步：,第三步：,结果,X10，X21，X31，X40， X50，X61，X70，X80。 平均身高：SF/35.64/31.88。,例如-7 人员值班配置问题,某医院急症室需昼夜24小时值班，将24小时分成六个时段，每个时段所需值班人数由表2-06给出，每位值班人员在某一时段的开始时刻上班，连续工作两个时段后下班。问医院每天至少配备多少名值班人员才能满足急症室的需要？,解： 设各时段新上班的人数分别为X1，X2，X3，X4，X5，X6,Min Z= X1+X2+X3+X4+X5+ X6,用WINQSB软件求解,第一步：,第二步：,第三步：,结果：,X18，X24，X36， X42，X54，X60。 最少：24人。,例 8 安排生产,某公司用限额为150万元的资金，拟购进一批运输货车。经调查待选的货车有甲、乙、丙三种类型，其价格分别为6.7，5.0，3.5万元；估计年运输净利润分别为4.2， 3.0 ，2.3万元。 现该公司仅有30个汽车司机能开这几类货车，而维修保养能力不允许购买超过40台丙类货车，据估计甲、乙两类货车的维修保养工作量相当于丙类货车维修保养工作量的5/3和4/3倍。 在上述条件下，为使年运输净利润达最大，应购买各类货车各多少台？试建立该问题的数学模型。（不要求求解）,解：设购买甲、乙、丙货车分别为X1、X2、X3台。运输净利为z，为使运输净利最大，满足模型为：,三、线性整数规划模型,一般整数规划模型 0-1整数规划模型 混合整数规划模型,一般整数规划模型,0-1整数规划模型,混合整数规划模型,整数规划的应用领域,一、采购问题 二、流通加工合理下料问题 三、部门工作安排问题 四、工厂选址问题 五、 派车问题,谢 谢,