四整数规划.pptVIP

第三章 整数规划 整数规划 * * 分枝定界法 整 数 规 划 在许多线性规划问题中,要求最优解必须取整数.例如 所求的解是机器的台数、人数车辆船只数等.如果所得的解 中决策变量为分数或小数则不符合实际问题的要求. 对于一个规划问题,如果要求全部决策变量都取整数, 称为纯(或全)整数规划;如果仅要求部分决策变量取整数, 称为混合整数规划问题.有的问题要求决策变量仅取0或l两 个值,称为0-l规划问题. 整数规划简称为IP问题.这里主要讨论的是整数线性规 划问题,简称为ILP问题. 对于整数线性规划问题,为了得到整数解,初看起来,似乎只 要先不管整数要求,而求线性规划的解,然后将求得的非整 数最优解“舍零取整”就可以了.但实际上,这个想法却常常行 不通,有时“舍零取整”后的整数解根本就不是可行解,有虽 然为可行解,却不是最优解 . 例7.0.1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、 重量、可获利润以及托 运所受限制见表7.1.问每集装箱中 两种货物各装多少箱,可使所获利润最大? 表 7.1 13 24 托运限制/集装箱 10 5 4 乙 20 2 5 甲 利润/百元 重量/百斤 体积/米3 货物/箱 解 设 分别为甲、乙两种货物的托运箱数.则这是一个 纯整数规划问题 .其数学模型为: （1） 若暂且不考虑 取整数这一条件.则(1)就变为下列 线性规划 : （2） 我们将式(2)称为(1)的伴随规划.解(2)得到最优解: （3） 但它不满足(1)的整数要求.因此它不是(1)的最优解,若把 解(3)舍零取整,如取X1=(5.0,0)T,但它不是式(1)的可行解. 因为它不满足 (1) 中的约束条件, 若取X2=(4.0,0)T. X2是 (1) 的可行解, 但它却不是(1) 的最优解, 因为当X2=(4.0,0)T 时,Z2 = 80, 但当X3 = (4,1)T 时,Z3 = 90 Z2 ·即伴随规划的最优 解通过 “ 舍零取整 ” 得到的X1,X2 都不是 (1) 的最优解 .因此通 过伴随规划最优解的 “ 舍零取 整 ” 的办法 , 一般得不到原整数 规划问题的最优解 . 若伴随规划(2)的可行域 K 是有界的,则原整数规划(1)的可行 域 K 0应是K中有限个格点(整数点）的集合.见图1, 图中“* 为整数点(格点). 图1 中四边形 OABC 是伴随 规划(2)的可行域.它的最优解 为 C 点(4.8, 0), 而 (1) 的可 行域为k0 ={(0,0),(0,1), (0,2), (1,0),(1, l),(1,2), (2,0), (2,1),(3,0), (3,1),(4,0),(4, l)}. 将C点“舍零取整”后得到的X1=(5.0,0)T不在 K0中,而X2=(4,0)T在K0中,但不是(1)的最优解,最优解在B点. 当然, 我们也会想到能否用“穷举法”来求解整数规划.如(1) 问题,将 K0 中所有整数点的目标函数值都计算出来,然后逐 一比较找出最优解.这种方法对变量所能取的整数值个数较少 时,勉强可以应用.如本例 可取 0,1,2,3,4共5个数值. 而 只能取0,1,2共三个数值,因此其组合最多为15个 (其中有不可行的点).但对大型问题,这种组合数的个数 可能大得惊人! 如在指派问题中,有n 项任务指派n个人 去完成,不同的指派方案共有n! 种 .当 n=20 时 ,这个 数超过2×1018. 如果用穷举法每一个方案都计算一遍 , 就是用每秒百万次的计算机,也要几万年 . 显然 “穷举法” 并不是一种普遍有效的方法.因此研究求解 整数规划的一般方法是有实际意义的.自20世纪60年代以来, 已发展了一些常用的解整数规划的算法,如各种类型的割平 面法、分枝定界法、解 0-1 规划的隐枚举法、分解方法、 群论方法、动态规划方法等等。近十年来有人发展了一些 近似算法及用计算机模拟法,也取得了较好的效果 . 分枝定界法 在20世纪60年代初 Land Doig 和 Dakin 等人提出了分枝 定界法.由于该方法灵活且便于用计算机求解,所以目前已 成为解整数规划的重要方法之一.分枝定界法既可用来解纯 整数规划,也可用来解混合整数规划. 分枝定界法的主要思路是首先求解整数规划的伴随规划 , 如果求得的最优解不符合整数条件,则增加新约束—— 缩小可行域;将原整数规划问题分枝——分为两个子规划, 再解子规划的伴随规划……通过求解一系列子规划的伴随 规划及不断地定界 .最后得到原整数规划问题的整数最 优解 . 下面结合一个极大化例题来介绍分枝定界法的主要思路 . 例2 某公司计划建筑两种类型的宿舍.甲种每幢占地0.25 ×10