《运筹08(第四章整数规划)》由会员分享，可在线阅读，更多相关《运筹08(第四章整数规划)（43页珍藏版）》请在金锄头文库上搜索。
1、2018/10/16,1,运筹学 OPERATIONS RESEARCH,2018/10/16,2,第四章 整数规划与分配问题 （Integer Programming, IP),整数规划的有关概念及特点 整数规划的求解方法：分枝定界法、割平面法 指派问题及匈牙利解法 整数规划的应用,2018/10/16,3,纯整数规划：在整数规划中，如果所有的变量都为非负整 数，则称为纯整数规划问题； 混合整数规划：如果有一部分变量为非负整数，则称之为混合整数规划问题。0-1变量：在整数规划中，如果变量的取值只限于0和1，这 样的变量我们称之为0-1变量。 0-1规划：在整数规划问题中，如果所有的变量都为0
2、-1变量，则称之为0-1规划。,1 整数规划的有关概念及特点,一、 概念,整数规划： 要求决策变量取整数值的规划问题。（线性整数规划、非线性整数规划等）,2018/10/16,4,求整数解的线性规划问题，不是用四舍五入法或去尾法对 性规划的非整数解加以处理就能解决的，用枚举法又往往 会计算量太大，所以要用整数规划的特定方法加以解决。例： 求解下列整数规划：,二、 整数规划的求解特点,2018/10/16,5,分析： 若当作一般线性规划求解，图解法的结果如下。,1、非整数规划最优解 显然不是整数规划的可行解。 2、四舍五入后的结果 也不是整数规划的可行解。,3、可行解是阴影区域交叉点，可比较这些
3、点对应的函数值，找出最优。,2018/10/16,6,2 应用举例,一、 逻辑变量在数学模型中的应用,1、m个约束条件中只有k个起作用 设有m个约束条件,定义0-1整型变量：M是任意大正数。,第i个约束起作用 第i个约束不起作用,则原约束中只有k个真正起作用的情况可表示为：,2018/10/16,7,2、约束条件右端项是r个可能值中的一个,则通过定义,约束条件右端项不是bi 约束条件右端项是bi,可将上述条件表示为,2018/10/16,8,3、两组条件中满足其中一组 例如表示条件：若 ，则 ；否则 时,则通过定义,第i组条件起作用，i=1，2 第i组条件不起作用,可将上述条件表示为,又：M是
4、任意大正数，,2018/10/16,9,定义,4、表示含有固定费用的函数 例如： 表示产品 j 的生产数量，其生产费用函数为：,目标函数：,其中 是与产量无关的生产准备费用,则原问题可表示为,2018/10/16,10,二、 应用举例,例1： 书P120,例3,解：设 表示学生i在周j日的值班时间。,目标函数,约束条件,每天开放14小时,大学生值班不少于8小时,设,学生i个在周j不值班 学生i个在周j值班,2018/10/16,11,研究生值班不少于7小时,每周不超过3次,每天不超过3人,每天有一研究生,值班不超过每人可安排的时间,表示学生i在周j日的最多可值班时间。,2018/10/16,1
5、2,例2： 书P120,例4,解：设 表示代号为j的包装箱的订做数量。,不订j包装箱 订j包装箱,目标函数,约束条件,2018/10/16,13,2018/10/16,14,例3（固定成本问题） 高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为
6、最大。,2018/10/16,15,解：这显然是一个整数规划的问题。设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各 种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这 种性质，设 yi = 1(当生产第 i种容器, 即 xi 0 时) 或0（当不生产第 i种容器即 xi = 0 时）。引入约束 xi M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 建立如下的数学模型：Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 5002x1 +
7、3x2 + 4x3 300x1 + 2x2 + 3x3 100xi M yi ，i =1，2，3，M充分大xi 0 yj 为0-1变量，i = 1,2,3,2018/10/16,16,3 指派问题及匈牙利解法,一、 指派问题与模型,m项任务分配给m个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配使得效率最高？aij是第j个人完成第i项任务的效率。,2018/10/16,17,设于是建立模型如下：,2018/10/16,18,二、 指派问题的匈牙利解法,该指派问题可当作运输问题解决，但匈牙利解法更有效。解法思想：效率矩阵的元素 ，若有一组位于不同行不同列的零元素，则令这些位
8、置的决策变量取值为1，其余均为0，这显然就是最优解。,2018/10/16,19,定理2：若矩阵A的元素可分为“0”元和“非0”元，则覆盖“0”元的最少直线数等于位于不同行、不同列的“0”元的最大个数。,定理1：效率矩阵 的每一行元素分别减去（加上）一个常数 ，每一列元素分别减去（加上）一个元素 ，得新效率矩阵 ， ，则 的最优解等价于 的最优解。,2018/10/16,20,例：有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高。,2018/10/16,21,匈牙利解法步骤： 1、在效率矩阵每行减去该行最小元素； 2、在
9、效率矩阵每列减去该列最小元素；,2018/10/16,22,3、寻找独立“0”元素(不同行不同列） （1）从第一行开始，若该行只有一个“0”元素，则对该“0”元素打括号（ ）（表示这一行的人只有这一个任务可指派），并划去该“0”元素所在的列（表示该项任务不能再指派给别人） ；若该行无“0”元素或有两个以上的“0”元素（不含划去的0），则转下一行；（2）从第一列开始，若该列只有一个“0”元素，则对该“0”元素打括号（ ），并划去该“0”元素所在的行；若该列无“0”元素或有两个以上的“0”元素（不含划去的0），则转下一列；,2018/10/16,23,完成上述步骤后可能出现下列情况： ）效率矩阵的
10、每一行都有一个打括号的0元素，则按照打括号的0元素位置指派任务，即是最优解； ）打括号的0元素个数小于m，但未被划去的0元素之间存在闭回路，则沿此闭回路，每隔一个0元打一括号，然后对打括号的0元素所在行或所在列画直线；,）矩阵中所有0元素或被打括号，或被划去，但打括号的0元素个数 ，则进入下一步；,2018/10/16,24,3、设法使每一行都有一个打括号的“0”元素。按定理1继续对矩阵进行变换： ）从矩阵未被直线覆盖的元素中找出最小者k， ）对矩阵中无直线覆盖的行，令 ，有直线覆盖的列，令 。其余为0。 ）对矩阵的每个元素计算 ，得到一个新矩阵，转第三步重复进行，直至每一行都有一打括号的0元
11、素。,2018/10/16,25,根据上图，k=2，,最优解：,2018/10/16,26,4 分枝定界法,分枝定界法是求解整数规划的一种常用的有效的方法，它 既能解决纯整数规划的问题，又能解决混合整数规划的问 题。大多数求解整数规划的商用软件就是基于分枝定界法编 制而成的。,下面举例来说明分枝定界法的思想和步骤。,2018/10/16,27,性质求MAX的问题：整数规划的最优目标函数值小于或等于相应的线性规划的最优目标函数值；求MIN的问题：整数规划的最优目标函数值大于或等于相应的线性规划的最优目标函数值。,1、求解整数规划相应的一般线性规划问题（即先去掉整数约束）。易知：整数规划的可行域（
12、小）包含于线性规划的可行 域 (大）。若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。,2018/10/16,28,例： 求解下列整数规划：,解：1、解对应的线性规划：,其最优解为 ， 显然不是整数规划的可行解。,L0：,2018/10/16,29,2、分枝与定界：将对应的线性规划问题分解成几个子问题，每个子问题就是一分枝，而所有子问题的解集之和要包含原整数规划的解集。求解每一分枝子问题：若其最优解满足整数约束，则它就是原问题的一个可行解（不一定是最优）；否则，就是该枝的上界或下界。若所有分支的最优解都不满足整数条件（即不是源问题的可行解），
13、则选取一个边界值最优的分支继续分解，直至找到一个原问题的可行解。若在同一级分枝中同时出现两个以上的原问题可行解，则保留目标值最优的一个，其余不再考虑。,从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。,2018/10/16,30,将上述线性规划问题分为两枝，并求解。,解得,解得,L1：,L2：,显然两个分枝均非整数可行解，选边界值较大的L1继续分枝。,2018/10/16,31,将L1分为两枝，并求解。,解得,解得,L11：,L12：,两个分枝均是整数可行解，保留目标值较大的L12。,2018/10/16,32,3、比较与剪枝将各子问题的边界值与保留下的整数可行解对应的目标值比较，将边界
14、值劣于可行行解的分支减剪去。若比较剪枝后，只剩下所保留的整数可行解，则该解就是原整数规划的最优解；否则选取边界值最大的一个分枝继续分解，在其后的过程中出现新的整数可行解时，则与原可行解比较，保留较优的一个，重复第三步。,2018/10/16,33,L0：,X22,X23,X13,X14,用图表示上例的求解过程与求解结果,2018/10/16,34,5 割平面法,一、 基本思想,在整数规划的松弛问题中，依次引进新的约束条件（割平面），使问题的可行域逐步减小，但每次割去的只是部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后的可行域的一个顶点，这样就可以用线性规划的方法求得整数最优解。
15、,2018/10/16,35,例： 求解下列整数规划：,解： 1、解对应的线性规划（松弛问题），并将约束条件的系数均化为整数：,2018/10/16,36,加入松弛变量后求解，得最终单纯形表：,如果上述求解结果是整数解，则结束；否则转下一步；,2、找出非整数解中分数部分最大的一个基变量，并将该行对应的约束方程所有常数（系数及常数项）分解成一个整数与一个正分数之和；将所有分式项移到等式右端。 例如上例，取第一行约束,2018/10/16,37,易知，左端为整数，要是等式成立，右端也必为整数，且,将 代入上式，得,2018/10/16,38,这就是一个割平面。将其添加到原约束中，得到新的可行域如图所示。 割去的只是部分非整数解。,2018/10/16,39,3、将新的约束添加到原问题中，得到一个新的线性规划问题，求解此问题，可用灵敏度分析的方法。4、重复上述的1-3步，直至求出整数最优解。,将 反应到最终表中，得,2018/10/16,40,运用对偶单纯形法，解得,此解仍非整数解，将基变量 对应的约束分解为：,得到新的约束,2018/10/16,
