《管理运筹学》03-整数规划.ppt

第 3 章,Integer Programming,I P,整 数 规 划,3.1 整数规划问题及其建模3.2 分支定界法3.3 割平面法3.4 0-1型整数线性规划的解法3.5 指派问题3.6 整数规划应用,第3章 整数规划,第3章 整数规划,2,基本概念,整数规划：变量取整数的线性规划；纯整数规划：所有变量都取整数的线性规划；混合整数规划：部分变量取整数的线性规划；0-1规划：所有变量都取0、1两个值的规划；0-1混合规划：部分变量取0、1两个值的规划。,例3-1背包问题,3.1 整数规划问题及其建模,4,线性规划最优解为:x1=0，x2=0，x3=2.5而整数规划的最优解是 x1=1，x2=0，x3=2,例3-2厂址选择问题在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。设,3.1 整数规划问题及其建模,5,整数规划模型为:,0-1规划,例3-3 考虑固定成本的最小生产费用问题 在最小成本问题中，设第j种设备的固定成本为，运行的变动成本为，则生产成本与设备运行时间的关系为：,6,混合0-1规划,设第j种设备运行每小时可以生产第i种产品 件，而第i种产品定货为 件。要满足定货同时使设备运行的总成本最小的问题为：,3.1 整数规划问题及其建模,线性规划与整数规划的关系,7,线性规划,整数规划,X*=（13/5，19/5）Z*=89/5=17.8,X*=（5，3）Z*=17,基本思想分支（Branch）定界（Bound）,3.2 分支定界法（B&B）,第3章 整数规划,8,分支（Branch）这两个子问题的可行域都是原线性规划问题可行域的子集，这两个子问题的最优解的目标函数值都不会比原线性规划问题的最优解的目标函数值更小。如果这两个问题的最优解仍不是整数解，则继续选择一个非整数的变量，继续将这个子问题分解为两个更下一级的子问题。这个过程称为“分枝（Branch）”。定界（Bound）如果某一个子问题的最优解是整数解，则它的目标函数值可作为整数规划最优目标函数值的上界。如果某一个子问题的解还不是整数解，但这个非整数解的目标函数值已经超过这个上界，那么这个子问题不必再进行分枝。如果在分枝过程中得到新的整数解且该整数解的目标函数值小于已记录的上界，则用较小的整数解的目标函数值代替原来的上界。上界的值越小，就可以避免更多不必要的分枝。确定整数解目标函数值上界并不断更新上界，并且不断“剪除”目标函数值超过上界的分枝的过程，称为定界（Bound）。,第3章 整数规划,9,例3-4 用分枝定界法求解以下整数规划先求得相应的线性规划的最优解，为,3.2 分支定界法（B&B）,第3章 整数规划,10,11,Sub-6无可行解,原问题,Sub-2,Sub-1,Sub-3,Sub-4,Sub-5,Sub-7,Sub-9,Sub-8,Sub-10无可行解,x22,x23,x15,x15,x21,x22,x14,x16,x20,x21,图3-3.探索过程示意图,1,3.3.1 割平面法基本思想,3.3 割平面法,第3章 整数规划,12,首先放弃变量的整数要求，求得线性规划的最优解。如果最优解恰是一个整数解，则线性规划的最优解就是相应的整数规划的最优解。如果线性规划的最优解不是整数解，则要构造一个新的约束，对线性规划问题的可行域进行切割，切除已经得到的线性规划的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。,3.3.1 割平面法基本思想,第3章 整数规划,13,设放弃变量整数要求得到的线性规划的最优单纯形表如下：,设其中基变量Xr的值br不是整数，以I表示整数，以 F表示正的真分数，令,yrj=Irj+Frj(0 Frj 1),b r=Ir+Fr(0 Fi 1),将上面两式代入约束r中，得,第6章 整数规划,14,改写成,因此对于整数可行解，约束（3-2）可以写成更严格的不等式,这就是源于第r行的割平面。线性规划的任何整数可行解都满足这个约束；未切割掉任何一个整数解。线性规划的非整数最优解不满足这个约束。切割掉了非整的LP解X；,第3章 整数规划,15,2 若Xk的分量全为整数，则Xk即为原问题的最优解，停止计算；否则根据Xk的一个非整分量所在单纯形表的那一行，譬如第 r 行，构造源于第 i行的割平面，给它引入一个弛变量 xn+k+1，得,3 把这个新约束添到最优单纯形表中，并增加一列(即 xn+k+1列)，用对偶单纯形法继续迭代，求得一个新解Xk+1，令k:=k+1，返2。,3.3.2 割平面法基本步骤 1 用单纯形法求解IP的伴随LP问题，得到其解X0，令k=0；,n,第6章 整数规划,16,例3-5 试用割平面法求解以下整数规划：,解 求解线性规划得最优单纯形表,选择一个非整数的基变量，例如 x2=8/5，构造约束条件(3-4）b2=8/5=1+3/5，I2=1，F2=3/5 y23=1/5=0+1/5，I23=0，F23=1/5 y24=-3/5=-1+2/5，I24=-1，F24=2/5附加的约束条件 为 3/5-（1/5x3+2/5x4）0即1/5x3+2/5x43/5将这个约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5,得下表,第3章 整数规划,17,第3章 整数规划,18,用对偶单纯形法，x5离基，x3进基,已获得整数的最优解：X*=（2，1）Z*=10,为了得到切割约束1/5x3+2/5x43/5在（x1,x2）平面中的表达式，将其中的松弛变量x3，x4用x1，x2表示 x3=3x1+x2-4，x4=x1+2x2-4代入切割约束，得到 x1+x23这个切割过程的图解如下图,第3章 整数规划,19,隐枚举法（Implicit Eumeration）例3-6 用隐枚举法求解下列问题 可行解：X=(1，0，0)，Z=3 增加过滤条件（filtering constraint）,3.4 0-1型整数规划的解法,第3章 整数规划,20,3.4 0-1型整数规划的解法,第3章 整数规划,21,按价值系数从小到大排列max z=-2x2+3x1+5x3-2x2+3x1+5x33 2x2+x1-x32 4x2+x1+x34 x2+x1 3 4x1+x36,改进算法（更早发现最优解）,第3章 整数规划,22,-2x2+3x1+5x35,第3章 整数规划,23,-2x2+3x1+5x38,指派问题或分派问题（assignment problem）：需完成n项任务，恰好有n个人可承担这些任务。各人完成任务的效率(或所费时间)不同。应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。例3-5 甲、乙、丙、丁四人配送A,B,C,D四种货物,所需时间如下表所示。若一种货物只交一人送货，则应指派何人配送何种货物,能使总的时间最少？,3.5 指派问题,第3章 整数规划,24,效率矩阵,设xij=1表示第 i人送j货，否则xij=0 上述问题的模型为：,第3章 整数规划,25,一般指派问题的模型,指派问题的求解方法匈牙利法性质3-1.若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。性质3-2.若一个方阵的一部分元素为0，另一部分元素不为0，则覆盖方阵内所有0元素的最少直线数恰好等于独立0元素（位于不同行，不同列的0元素）的最多个数。,第3章 整数规划,26,例3-7：匈牙利法的步骤一、系数矩阵经变换，在各行各列中都出现0元素。二、寻找独立0元素最优值为：Z*=11+9+4+5=29,第3章 整数规划,27,甲C，乙A，丙D，丁B,例3-5：先减列元素独立0元素的个数为3，小于矩阵的阶数。,3.5 指派问题,第3章 整数规划,28,三、找出能覆盖非最优阵中所有0元的最少直线集合,第6章 整数规划,29,(4)重复(2)、(3)步骤，直到找不出新的打 号的行、列为止；(5)对没有打号的行画横线，对所有打号 的列画竖线，这就是能覆盖所有0元的最少 直线的集合。,三、用最少的直线数覆盖矩阵中的所有0元素,第3章 整数规划,30,四、增加矩阵中的0元素 在没有被直线覆盖的部分中找出最小元素。然后在打行各元素中都减去这最小元素，而在打列的各元素都加上这最小元素。若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。,第3章 整数规划,31,最优解,可令 bij=M-cij。其中M是足够大的常数(如选（cij）中最大元素为M即可)，这时系数矩阵可变换为B=(bij),极大化的指派问题,第3章 整数规划,32,目标函数经变换后，即解,所得(bij)最小解即为原问题(cij)的最大解。,例3-8某航空公司是一家经营小型飞机、短途航线的运输企业。管理层准备拓展经营领域，面临的问题是：是采购更多的小型飞机来开辟一些新的短途航，还是开始通过为一些跨地区航线购买大型飞机来进军全国市场，或者两种方法同时进行，已知采购成本、年利润、最多购买的数量限制如下表。并且可用资金为1亿元，如何进行决策，能使年利润达到最大？,3.6 整数规划的应用,第3章 整数规划,33,x1,x2,3.6 整数规划的应用,第3章 整数规划,34,整数规划模型为：,例3-9 某速递公司的线路选择问题。公司提供快递服务，所有快件两天内都能送到。快件在晚上到达各收集中心，并于第二天早上装上送往该区域地区的几辆汽车。因为快递行业竞争激烈，为了减少平均送货时间，必须将各快件根据目的地的地理位置加以分类，并分装到不同的汽车上。假设每天有三辆汽车，汽车可行的路线有10条，如下表所示。表中的各列的数字表示送达的顺序，最后一行是各方案的汽车运行时间（小时），现假设有9个不同地点的快件需要送出，试求出总运行时间最短的方案。,第3章 整数规划,35,第3章 整数规划,36,该问题可视为0-1规划问题。设 表示第i个方案是否被选择（0表示不选择，1表示选择）,第3章 整数规划,37,