《整数规划及其应用.ppt》由会员分享，可在线阅读，更多相关《整数规划及其应用.ppt（67页珍藏版）》请在三一办公上搜索。
1、物流运筹学方法,缪兴锋 教授/高级工程师联系方法：E-mail:wuliuxitong 广东轻工职业技术学院2013,第三章 整数规划,整数规划(Integer Programming，简记IP)是近30年来发展起来的、规划论的一个分支。线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划。,对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划；如果仅要求部分决策变
2、量取整数，称为混合整数规划问题；有的问题要求决策变量仅取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，
3、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，满足约束条件，才是最优解。,一、问题的提出,为了满足整数要求，似乎可以把线性规划的小数最优解进行“舍入化整”以得到与最优解相近的整数解。“舍入化整”一般
4、是不可行的：化整后的解有可能成为非可行解；虽是可行解，却不是最优解。,解法概述,当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。,设想计算机每秒能比较100 0 000个式。那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。,先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划
5、时，往往不能成功。,说明：,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 必须取整数值，整
6、数规划问题的可行解只是线性规划可行域内的那些整数点。用凑整法求解时需要比较四种组合:（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 x
7、1+15x2+18x3+14x4+8x5+4x6+10 x7,用WINQSB软件求解,联 系 实 例-4,某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。,物品的容量及价格对照表,问题分析,变量对每个物品要确定是否带同时要确定放在
8、哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中,约束,包裹容量限制,必带物品限制,选带物品限制,目标函数未带物品购买费用最小,模 型,S.t.,例-5：,假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02M3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大：（1）所装物品不变；（2）如果选择旅行箱，则只能装载丙和丁两种物品。如下表所示。则载重量和体积的约束为：,解：此问题可
9、以建立两个整数规划模型。,引入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）式是多余的，即约束条件不起作用；,二、模型描述,整数规划问题就是要求决策变量取整数值的线性或非
10、线性规划问题。因此，整数规划分为：整数线性规划(I LP)整数非线性规划(IN LP)两类。,按对变量的不同要求，还可将整数规划分为下述几种类型：,纯整数规划(Pure IP)或全整数规划(All IP)：要求全部变量都取整数值。混合整数规划(Mixed IP)：只要求一部分变量取整数值 0-1整数规划（binary programming,简记为 BIP）。要求全部或部分变量只取0或1值。,在管理与规划的大量问题中，常要求变量 满足取整条件,如：生产计划中，生产机器多少台（整数）；人力资源管理中，招聘员工多少人（整数）；运输问题中，从一个港口到另一个港口的集装箱调运数量（整数）。,另外，运作
11、管理中的决策问题，如：物流中心选址、人员的工作指派、设备购置和配置、系统可靠性设计、机床加工任务的均衡分派等等。从技术角度看，这些问题的规划模型不同于前述的线性规划范畴，而属于一种新的类型整数规划。,例如-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.85
12、X51.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软件求解,第一步：,第
13、二步：,第三步：,结果：,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整数规划模型,混合整数规划模型,整数规划的应用领域,一、采购问题二、流通加工合理下料问题三、部门工作安排问题四、工厂选址问题五、派车问题,谢 谢,
