运筹与决策之4整数规划（46).ppt

《运筹与决策之4整数规划（46).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、11绪论—Introduction2线性规划—LinearProgramming3运输与指派问题—TransportationModels4整数规划—IntegerProgramming5网络模型—NetworkModels6项目计划—PERT&CPM7排队论—QueueingModels8模拟—Simulation9决策分析—DecisionTheory10多目标决策—Multi-objectiveDecision《管理数量方法》目录2授课内容Case:分销系统设计（P192）整数规划图解法及分枝定界法MS6.0软件求解整数规划应用举例银行选址P209（

2、讲义：消防站选址）案例讨论：课本出版P2223Questions整数规划IP与线性规划LP有何不同？整数规划的分类？整数规划的求解方法？分枝定界法的基本思路？分枝问题解可能出现的情况？4Q1：整数规划与线性规划LP区别：（要求所有xj的解为整数，或者要求部分xj的解为整数）1）一般整数规划。要求所有xj的解为整数，称为纯整数规划；或者要求部分xj的解为整数，称为混合整数规划。2）0-1整数规划。它规定整数变量只能有两个值，0或1。5Q2：整数规划的解法图解法穷举法分枝定界法(BranchandMethod)割平面法6Q3：分枝定界法的基本思路maxZ=C

3、XAX=bX0(A)maxZ=CXAX=bX0X为整数(B)(B)为(A)的线性规划松弛问题。7(C)(D)(B)Xji+1(B)XjiX*最优解Xj*i+1i(C)(D)X*最优解为非整数解，则对(B)每次分两枝,每枝多一个约束条件8Q4：分枝问题解可能出现的情况如何回答？9表分枝问题解可能出现的情况情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝的整数解进行比较，结论如情况4。结果101绪论—Introduction2线性规划—LinearProgramming3运输问题—Tr

4、ansportationModels4整数规划—IntegerProgramming5网络模型—NetworkModels6项目计划—PERT&CPM7排队论—QueueingModels8模拟—Simulation9决策分析—DecisionTheory10多目标决策—Multi-objectiveDecision《管理数量方法》目录11授课内容整数规划图解法及分枝定界法MS6.0软件求解整数规划应用举例银行选址P230（讲义：消防站选址）案例讨论：课本出版P24212整数规划举例产品桌椅备用资源木工1230油漆工3260搬运工0224利润4050例1、

5、家具厂生产计划问题桌，椅各生产多少,可获最大利润?13图解法求最优解解：X*=(15,7.5)Zmax=975该解是否符合实际要求？0203010102030X1X2DABCDABCC点：X1+2X2=303X1+2X2=60如何求解整数解？144整数规划整数规划的难度远大于一般线性规划15整数规划简介要求所有xj的解为整数，称为纯整数规划要求部分xj的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解16整数规划的解法图解法穷举法分枝定界法割平面法1

6、7§4.1整数规划的穷举法穷举法：可以通过计算和比较所有整数格点的值来求解。18例：maxZ=40x1+60x2+70x3+160x416x1+35x2+45x3+85x4100x1,x2,x3,x4为0,1X1=1X1=0111010101X2=0X3=00解法1：枚举法：x1=1,x2=1,x3=1,x4=0。枚举法？192100个整数解，用最现代化的计算机也要算上几亿亿年。穷举法是无法用来求解实际问题。最优解经过四舍五入的方法是否可以？若该整数规划问题有100个0－1整数变量，那么整数解有多少个？如何回答？20§4.2分枝定界法的基本思路maxZ=

7、CXAX=bX0(A)maxZ=CXAX=bX0X为整数(B)(B)为(A)的线性规划松弛问题。21(C)(D)(B)Xji+1(B)XjiX*最优解Xj*i+1i(C)(D)X*最优解为非整数解，则对(B)每次分两枝,每枝多一个约束条件22分枝定界法的步骤思路:暂不考虑整数条件,用单纯形法求解,得整数解,停;不是整数解,分枝。分枝:每次分两枝,每枝多一个约束条件，（每个节点代表一个子问题）。停止分枝条件:1）子问题无可行解.2）子问题得整数解.3）子问题的目标值比下界差。maxZ定界:1）初始整数规划的松弛问题的最优值是上界.2）子问题得整数解的

8、最优值是一个下界。23分枝问题解可能出现的情况如何回答？24表分枝