《整数规划问题剖析》由会员分享，可在线阅读，更多相关《整数规划问题剖析（69页珍藏版）》请在金锄头文库上搜索。
1、第四章 整数规划与分配问题,数学模型 割平面法 分枝定界法 0-1整数规划 分配问题,整数规划,Integer Linear Programming,简述,LP虽然用途广泛，但经常地，客观上要求 L.P.最优解中不能含有非整数值（如股票的购买之解答），整数规划就是专门用来求解这类问题的有效工具 重点掌握：0-1 规划灵活应用、分枝定界法。,提出问题,某厂生产A1，A2两种品牌电视，用B1，B2两种原料，具体数据如下，求如何安排生产使利润最大,整数规划,数学模型,若所有 xj 的解为整数，称为纯整数规划pure integer linear programming 若部分 xj 的解为整数，称为
2、混合整数规划mixed integer linear programming 若xj 只取0或1，成为0-1整数规划zero-one integer linear programming,松弛问题,整数规划,整数规划的最优解不会优于其松弛问题的最优解,注 释,最优解不一定在顶点上达到 最优解不一定是松弛问题最优解的邻近整数解 整数可行解远多于顶点，枚举法不可取,整数规划问题的求解方法,分枝定界法branch and bound method 分枝定界法是一种隐枚举方法（implicit enumeration）或部分枚举方法，是枚举方法基础上的改进，几乎所有的计算机计算都用此算法。其关键是分支
3、和定界。 例,Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0 X1 ， X2 取整数,s.t.,6,分支定界法,思路与解题步骤 只解松弛问题 1、在全部可行域上解松弛问题 若松弛问题最优解为整数解，则其也是整数规划的最优解 2、分枝过程 若松弛问题最优解中某个 xk=bk 不是整数，令 bk 为 bk 的整数部分 构造两个新的约束条件 xk bk 和 xk bk +1，分别加于原松弛问题，形成两个新的整数规划 3、求解分枝的松弛问题 定界过程 设两个分枝的松弛问题分别为问题 1 和问题 2 ，它们的最优解有如下情况,整数规划,分支问题
4、解可能出现的情况,情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4或5,整数规划,分支定界法图解整数规划,松弛问题 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0,该整数规划松弛问题的解为： （X1 ，X2 ）=（3/2 ,10/3） Z1 = 29/6,14X1 + 9X2 51,- 6X1 + 3X2 1,51/14,1/3,9,整数规划 Integer Programming（IP）,分支定界法图解整
5、数规划,松弛问题 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0,（3/2 ，10/3） Z1 = 29/6,B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0,B2 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 1 X1 ， X2 0,B2：解 （1,7/3 ） Z21 = 17/3,B1：解 （2,23/9 ） Z11 = 41/9,1,2,10,整数规划 Integer Programming（IP）,整数规划
6、问题的求解方法 分支定界法图解整数规划,（3/2 ,10/3） Z1 = 29/6,B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0,B2：解 （1,7/3 ） Z21 = 17/3,B1：解 （2,23/9 ） Z11 = 41/9,B11 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 3 X1 ， X2 0,B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,B12：解 （33
7、/14,2 ） Z12 = 61/14,1 2,X=2,X=3,11,整数规划 Integer Programming（IP）,整数规划问题的求解方法 分支定界法图解整数规划,（3/2 ，10/3） Z1 = 29/6,B2：解 （1,7/3 ） Z21 = 17/3,B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,B12：解 （33/14,2 ） Z12 = 61/14,B121 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 3 X2 2 X1 ， X2 0
8、,B122 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,B121：解 （3，1 ） Z121 = 4,B122：解 （2，2 ） Z122 = 4,B1：解 （2，23/9 ） Z11 = 41/9,1 2 3,12,割平面法cutting plane approach,割平面法求解整数规划问题时，若其松驰问题的最优解 X* 不满足整数要求时，则从 X* 的非整分量中选取一个，用以构造一个线性约束条件（Gomory 割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束
9、条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而不会切割掉问题的任何整数解。,13,整数规划 Integer Programming（IP）,整数规划问题的求解方法 割平面法cutting plane approach 构造切割方程的步骤： 1、令 xi 是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得： xi + aik xk = bi （1 式） 其中 i Q （Q 指基变量下标集） k K （K 指非基变量下标集）,14,整数规划 Integer Programming（IP）,整数规划问题的求解方法 割平面法cutting plane appro
10、ach 构造切割方程的步骤： 2、将 bi 和 aik 都分解成整数部分 N （不超过 b 的最大整数）与非负真分数部分 f 之和，即： bi = Ni + fi ， 其中 0 fi 1 （2 式） aik = Nik + fik ，其中 0 fik 1 例如：若 b = 2.35 ，则 N = 2 ，f = 0.35； 若 b = -1.45 ，则 N = -2 ，f = 0.55,15,整数规划 Integer Programming（IP）,割平面法cutting plane approach 构造切割方程的步骤： 2、将（2 式）代入（1 式）得： xi + Nik xk - Ni =
11、 fi - fik xk （3 式） 3、提出变量为整（当然含非负）的条件： 由于（3 式）中等式左边需整，而 0 fi 1 ，故有 fi - fik xk 0 （4 式） 此即为所需切割方程。,16,整数规划 Integer Programming（IP）,割平面法cutting plane approach 构造切割方程的步骤： （1）切割方程 fi - fik xk 0 真正进行了切割，至少把非整数最优解这一点切割掉了。 证明：（反证法）假设松驰问题的最优解 X* 未被切割掉，则由 fi - fik x*k 0， 又因为 x*k = 0，（因 x*k 为非基变量） 有 fi 0 ，这与
12、fi 0 矛盾。 （2）不会切割掉任何整数解，因为切割方程是由变量为整的条件提出的。,17,整数规划 Integer Programming（IP）,割平面法cutting plane approach 例求解,IP Max Z = X1 + X2 - X1 + X2 1 3X1 + X2 4 X1 ，X2 0 X1 ，X2 整数,LP Max Z = X1 + X2 - X1 + X2 1 3X1 + X2 4 X1 ，X2 0,18,1、求解 LP 得到非整数最优解： X =（3/4，7/4，0，0），Max Z = 5/2,求解步骤：,19,整数规划 Integer Programmin
13、g（IP）,求解步骤： 2、构造切割方程： 由 B 表中的第 2 个方程 X2 + 3/4 X3 + 1/4 X4 = 7/4 有 b2 = 7/4 = 1 + 3/4 a23 = 3/4 = 0 + 3/4 ， a24 = 1/4 = 0 + 1/4 因此，切割方程为 3/4 3/4 X3 1/4 X4 0 增加松弛变量 X5 ，并将如下方程的约束条件添加到 B 表中。 - 3 X3 - 1 X4 + X5 = - 3 X5 0,20,整数规划 Integer Programming（IP）,求解步骤： 3、求解新的松弛问题,21,0-1整数规划问题,0-1 变量及其应用 0-1变量作为逻辑
14、变量（Logical variable），常常被引用来表示系统是否处于某个特定的状态，或者决策变量是否取某个特定的方案。,xj =,1 当决策取方案 P j 时 0 当决策不取方案 Pj 时,22,0-1整数规划,一、项目选定(选址）问题,整数规划,在经济全球化的时代，许多公司为在全球范围内最优地配置资源（如获取廉价劳动力或原料等），要在不同地方建厂或仓库及其他服务设施，这些都要进行项目或地址的选择。在选址之前，许多侯选地点要进行分析和比较，而每个决策都涉及到一个选还是不选的问题。,案例一,某销售公司打算通过在武汉或长春设立分公司（也许两个城市都设）增加市场份额，管理层同时也计划在新设分公司的
15、城市最多建一个配送中心，当然也可以不建配送中心。经过计算，每种选择对公司收益的净现值、所需费用列在下表中，总预算投资费用不得超过20万。如何决策使总净现值最大,设 xj=,10,- 决策j问题的答案是“是” - 决策j问题的答案是“否”,max z = 18x1 + 10x2 + 12x3+8x4,最优解 x1 =1，x2=1,案例练习,例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收净益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？,设 xj=,10,- 选择开采第j个构造 -不选择开采第j个构造,max z=cjxj,j=1,10,ajxj b,xj0或1 (j=1,2,-,10),j=1,10,-年总收益,-投资额限制,1、表示
