第4章整数规划讲稿11.pptVIP

第四章 整数规划(Integer Programming，简称为IP） ; §1 整数规划问题的提出 在线性规划问题中，所有的解都假设为具有连续型的数值，即解可以是整数、分数或小数。但对于某些具体的问题，常要求最优解是整数的情形。例如，所求的解是机器台数，完成工作的人数或装货的车数等，还有逻辑变量，只允许取整数值的一类变量，比如x=1或0。这时，分数或小数的解就不符合要求。;一、整数规划的定义：决策变量要求取整数的LP。 IP的松驰问题：任何IP，放弃整数要求后，所得到的问题称为原IP的松驰问题（Slack Problem）或称作和原IP相应的LP问题。 二、分类 1、纯整数规划(Pure Integer Programming)或全整数规划(All Integer Programming)：全部决策变量均要求取整数的LP。 2、混合整数规划(Mixed Integer Programming )：要求部分决策变量取整数的LP。 3、0-1型整数规划：决策变量只取 0、1 的整数规划。;三、求解 1、整数规划是数学规划中一个较弱的分支，它的求解要比一般的线性规划困难得多，到目前为止还没有一个十分有效的解法，只能对一些特定的问题提出求解的方法。而且目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法。 2、但在实践中，许多问题可以归结为IP。由于决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？因此，对求最优整数解的问题，有必要另行研究。它作为数学规划论的一个重要分支，近二十多年发展起来了。 ;3、当人们开始接触整数规划问题时，常会有如下两种初始想法： 1）因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行的。 设想计算机每秒能比较一百万个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。 理解：几何级数的惊人增长：复式利率; ;某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？ maxZ=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1 ， x2 ≥0且为整数 解此IP的松弛问题，得： x1 =4.8， x2 =0 显然不是可行解;整数规划图解法;图解法的启示;四、整数规划的性质（一般指纯IP) 1、可行域为点集。 2、整数规划的解是可数个的，最优解不一定发生在顶点。 3、整数规划的最优解的目标值不会优于其松弛问题的最优解的目标值。(max不大于，min不小于);五、整数规划的典型问题;１、投资决策问题 设有n个投资项目，其中项目j需要资金aj万元，将来可获利润cj万元。若现有资金总额为b万元，则应选择哪些项目投资才能获利最大？ 　设xj＝１,当投资项目j时 　　　 ０,不投资项目j时（j=1, 2, … n） 设ｚ为可获得的总利润,则该问题的模型为 　max z = ? cj xj s.t. ? aj xj ≤ b , xj = 0 或1 ，( j=1,2,…,n) 　 这是一个０─１规划，因为决策变量xj 只能取值０或１。它是整数规划的一个重要类型，许多实际问题可归结为这类模型。; 例：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： ; 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 目标函数：minZ= x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0; ; m n Max z = ??cij x