《整数规划问题》PPT课件.ppt

《《整数规划问题》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第四章整数规划与分配问题数学模型割平面法分枝定界法0-1整数规划分配问题整数规划IntegerLinearProgramming简述LP虽然用途广泛，但经常地，客观上要求L.P.最优解中不能含有非整数值（如股票的购买之解答），整数规划就是专门用来求解这类问题的有效工具重点掌握：0-1规划灵活应用、分枝定界法。提出问题某厂生产A1，A2两种品牌电视，用B1，B2两种原料，具体数据如下，求如何安排生产使利润最大整数规划数学模型若所有xj的解为整数，称为纯整数规划pureintegerlinearpr

2、ogramming若部分xj的解为整数，称为混合整数规划mixedintegerlinearprogramming若xj只取0或1，成为0-1整数规划zero-oneintegerlinearprogramming松弛问题整数规划整数规划的最优解不会优于其松弛问题的最优解注释最优解不一定在顶点上达到最优解不一定是松弛问题最优解的邻近整数解整数可行解远多于顶点，枚举法不可取整数规划问题的求解方法分枝定界法branchandboundmethod分枝定界法是一种隐枚举方法（implicitenume

3、ration）或部分枚举方法，是枚举方法基础上的改进，几乎所有的计算机计算都用此算法。其关键是分支和定界。例——MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0X1，X2取整数s.t.分支定界法思路与解题步骤只解松弛问题1、在全部可行域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程若松弛问题最优解中某个xk=bk不是整数，令bk为bk的整数部分构造两个新的约束条件xkbk和xkbk+1，分别加于原松弛问题，形成两个新的整数规

4、划3、求解分枝的松弛问题—定界过程设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况整数规划分支问题解可能出现的情况情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或5整数规划分支定界法图解整数规划松弛问题MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0该整数规划松弛问题的解为：（X1，X2）=（3/2,10/3）Z1=29/614X1+9X2≤51-6X

5、1+3X2≤151/141/3整数规划IntegerProgramming（IP）分支定界法图解整数规划松弛问题MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0（3/2，10/3）Z1=29/6B1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X1，X2≥0B2MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≤1X1，X2≥0B2：解（1,7/3）Z21=17/3B1：解（2,23/9）Z11=41/912B1B2整数规划In

6、tegerProgramming（IP）整数规划问题的求解方法分支定界法图解整数规划（3/2,10/3）Z1=29/6B1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X1，X2≥0B2：解（1,7/3）Z21=17/3B1：解（2,23/9）Z11=41/9B11MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≥3X1，X2≥0B12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≤2X1，X2≥0B12：解（33/1

7、4,2）Z12=61/1412X=2X=3整数规划IntegerProgramming（IP）整数规划问题的求解方法分支定界法图解整数规划（3/2，10/3）Z1=29/6B2：解（1,7/3）Z21=17/3B12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≤2X1，X2≥0B12：解（33/14,2）Z12=61/14B121MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥3X2≤2X1，X2≥0B122MaxZ=X1+X214X1+9X2≤

8、51-6X1+3X2≤1X1≤2X2≤2X1，X2≥0B121：解（3，1）Z121=4B122：解（2，2）Z122=4B1：解（2，23/9）Z11=41/9123割平面法cuttingplaneapproach割平面法求解整数规划问题时，若其松驰问题的最优解X*不满足整数要求时，则从X*的非整分量中选取一个，用以构造一个线性约束条件（Gomory割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整