整数规划及其应用.pptxVIP

物流运筹学方法缪兴锋教授/高级工程师联系方法：E-mail:wuliuxitong@163.com广东轻工职业技术学院2013

整数规划(IntegerProgramming，简记IP)是近30年来发展起来的、规划论的一个分支。1线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。2例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。3要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划。4第三章整数规划

对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划；如果仅要求部分决策变量取整数，称为混合整数规划问题；有的问题要求决策变量仅取0或1两个值,称为0-1规划问题.

例如1：生产安排问题问如何安排甲、乙两产品的产量，使利润为最大。产品资源甲乙现有量A219B5735单台利润63

解题：

用WINQSB软件求解

用WINQSB软件求解

第二步：

第三步：

当X1,X2取整数的几种情况分析结果X1=3.11;x2=2.77MaxZ=32.556当X1,X2取整数的几种情况不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题。不考虑整数约束的最优解：x1*=28/9，x2*=25/9，Z*=293/9舍入化整(1)x1=3，x2=3，Z=33，不满足约束条件5x1+7x2≤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+7x2≤35，非可行解；x1=3，x2=2，Z=28，满足约束条件，是可行解，但不是最优解；x1=4，x2=1，Z=29，满足约束条件，才是最优解。

为了满足整数要求，似乎可以把线性规划的小数最优解进行“舍入化整”以得到与最优解相近的整数解。“舍入化整”一般是不可行的：化整后的解有可能成为非可行解；虽是可行解，却不是最优解。一、问题的提出

当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。解法概述

设想计算机每秒能比较1000000个式。01那么要比较完20!（大于2*1018）种方式，大约需要800年。02比较完260种方式，大约需要360世纪。03

先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。

说明：整数规划只是线性规划问题中的一个特例。求整数规划问题用线性规划方法并不能完全得出最佳解，还需要采用其他特殊方法。

例2：背包问题某人有一背包可以装10公斤重、0.025M3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。问每件物品各装多少件，所装物品的总价值最大。物品重量（公斤/件）体积（m3/件）价值（元/件）甲乙020.002543

解：设甲、乙两种物品各装X1，X2件，

则数学模型：MaxZ＝4X1＋3X2S.t.1.2X1+0.8X2≤102X1+2.5X2≤25X1≥0，X2≥0且均取整数

（1）用图解法画出可行域

（2）用WINQSB软件求解

第一步：

第二步：

第三步：

分析:由软件计算得：X1=3.5;X2=7.1,MaxZ=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一登山队员做登山准备，他需要携带的物品