运筹与决策之4整数规划（PPT46页)

11绪论—Introduction2线性规划—LinearProgramming3运输与指派问题—TransportationModels4整数规划—IntegerProgramming5网络模型—NetworkModels6项目计划—PERT&CPM7排队论—QueueingModels8模拟—Simulation9决策分析—DecisionTheory10多目标决策—Multi-objectiveDecision《管理数量方法》目录2授课内容•Case:分销系统设计（P192）•整数规划1.图解法及分枝定界法2.MS6.0软件求解3.整数规划应用举例•银行选址P209（讲义：消防站选址）•案例讨论：课本出版P2223Questions1.整数规划IP与线性规划LP有何不同？整数规划的分类？2.整数规划的求解方法？3.分枝定界法的基本思路？4.分枝问题解可能出现的情况？4Q1：整数规划与线性规划LP区别：（要求所有xj的解为整数，或者要求部分xj的解为整数）1）一般整数规划。要求所有xj的解为整数，称为纯整数规划；或者要求部分xj的解为整数，称为混合整数规划。2）0-1整数规划。它规定整数变量只能有两个值，0或1。njxmibxatsxcxfjnjijijnjjj,,2,1,0,,2,1,),(..)(max(min)11且为整数5Q2：整数规划的解法图解法穷举法分枝定界法(BranchandMethod)割平面法6Q3：分枝定界法的基本思路maxZ=CXAX=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：分枝问题解可能出现的情况序号问题1问题2说明1无可行解无可行解整数规划解如何？2无可行解整数解3无可行解非整数解4整数解整数解5整数解，目标函数优于问题2非整数解6整数解非整数解，目标函数优于问题1如何回答？9表分枝问题解可能出现的情况序号问题1问题2说明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即最优解3无可行解非整数解对问题2继续分枝4整数解整数解较优的一个为最优解5整数解，目标函数优于问题2非整数解问题1的解即最优解6整数解非整数解，目标函数优于问题1问题1停止分枝(剪枝)，其整数解为界，对问题2继续分枝情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝的整数解进行比较，结论如情况4。结果101绪论—Introduction2线性规划—LinearProgramming3运输问题—TransportationModels4整数规划—IntegerProgramming5网络模型—NetworkModels6项目计划—PERT&CPM7排队论—QueueingModels8模拟—Simulation9决策分析—DecisionTheory10多目标决策—Multi-objectiveDecision《管理数量方法》目录11授课内容•整数规划1.图解法及分枝定界法2.MS6.0软件求解3.整数规划应用举例•银行选址P230（讲义：消防站选址）•案例讨论：课本出版P24212整数规划举例产品桌椅备用资源木工1230油漆工3260搬运工0224利润4050例1、家具厂生产计划问题桌，椅各生产多少,可获最大利润?13图解法求最优解解：X*=(15,7.5)Zmax=975该解是否符合实际要求？0203010102030X1X2DABCDABCC点：X1+2X2=303X1+2X2=60如何求解整数解？144整数规划整数规划的难度远大于一般线性规划15整数规划简介要求所有xj的解为整数，称为纯整数规划要求部分xj的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解njxmibxatsxcxfjnjijijnjjj,,2,1,0,,2,1,),(..)(max(min)11且为整数16整数规划的解法图解法穷举法分枝定界法割平面法17§4.1整数规划的穷举法njxmibxatsxcxfjnjijijnjjj,,2,1,0,,2,1,),(..)(max(min)11且为整数穷举法：可以通过计算和比较所有整数格点的值来求解。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。枚举法？192100个整数解，用最现代化的计算机也要算上几亿亿年。穷举法是无法用来求解实际问题。最优解经过四舍五入的方法是否可以？若该整数规划问题有100个0－1整数变量，那么整数解有多少个？如何回答？20§4.2分枝定界法的基本思路maxZ=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）子问题得整数解的最优值是一个下界。23分枝问题解可能出现的情况序号问题1问题2说明1无可行解无可行解整数规划解如何？2无可行解整数解3无可行解非整数解4整数解整数解5整数解，目标函数优于问题2非整数解6整数解非整数解，目标函数优于问题1如何回答？24表分枝问题解可能出现的情况序号问题1问题2说明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即最优解3无可行解非整数解对问题2继续分枝4整数解整数解较优的一个为最优解5整数解，目标函数优于问题2非整数解问题1的解即最优解6整数解非整数解，目标函数优于问题1问题1停止分枝(剪枝)，其整数解为界，对问题2继续分枝情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝的整数解进行比较，结论如情况4。结果25举例例：maxZ=x1+x26x1+2x2175x1+9x244x1,x2为整数如何回答？26松弛问题Z0=5.545X1=1.477X2=4.068子问题1Z1=5.333X1=1X2=4.333子问题2Z2=4.5X1=2X2=2.5子问题3Z3=5X1=1X2=4子问题4无可行解x1≥2x1≤1x2≤4x2≥5分枝定界法求解过程∴最优整数解X1=1X2=4最优目标函数值Z=5270-1Programming(BinaryIP)0-1整数规划决策变量取值0或1，称0-1或二进制变量。0-1变量可数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件0-1规划应用：如工厂选址、生产计划安排、旅行购物、背包问题、人员安排、代码选取、线路设计、可靠性等28§4.3整数规划建模应用举例：0-1变量的作用1.Xj=未选中方案选中方案jj...0...1njjx11njjx133.从N个方案中最多选中3个:2.从N个方案中必须选中一个:29特殊约束的处理1.只有方案J选中时，方案I才可能被选中:如何表示？xi≤xj2.方案I与方案J是否选中是同时的:xi=xj3.矛盾约束:f(x)-5≥0与f(x)≤0→-f(x)+5≤M(1-y)与f(x)≤MyM表示很大的数，y为0－1变量。如何回答？30特殊约束的处理4.多个选一:fi(x)≤0,I=1,2,…,n.如何表示？5.逻辑关系约束：若f(x)无限制,则g(x)≤0;若f(x)0不成立,则g(x)无限制.如何表示？fi(x)≤M(1-yi)I=1,2,…,n.y1+y2+…+yn=1→f(x)≥-M(1-y),g(x)≤My，M表示很大的数，y为0－1变量。310-1整数规划模型及其应用•8.3.1资金预算（投资决策）问题•8.3.2固定成本问题•8.3.3配送系统设计•8.3.4银行选址（覆盖问题）•8.3.5产品设计与市场份额优化32整数规划应用举例例华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下约束：1.在项目1、2和3中必须（只）有一项被选中；2.项目3和4只能选中一项；（必须选一项）3.项目5被选中的前提是项目1必须被选中。如何在上述条件下选择一个最好的投资方案，使投资收益最大。33项目投资收益表项目投资额（万元）投资收益（万元）121015023002103100604130805260180Xj=1表项目j选中,Xj=0表项目j未选中.j=1,2,3,4,5.约束条件如何表示？34计算过程解:Xj=1表项目j选中,Xj=0表项目j未选中.j=1,2,3,4,5.Z表示总收益.则模型如下:MaxZ=150X1+210X2+60X3+80X4+180X5s.t:210X1+300X2+100X3+130X4+260X5≤600X1+X2+X3=1X3+X4=1X5≤X1Xj=0或1;j=1,2,3,4,5.35例解决某市消防站的布点问题。该城市共有6个区，每个都可以建消防站。市政府希望建设的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见下表：请帮助该市制定一个最节省的计划。消防车在各区行驶距离表地区1地区2地区3地区4地区5地区6地区1地区2地区3地区4地区5地区6010162827201002432171016240122721283212015252717271501420102125140Howtosolve？36计算过程解:Xj=1表地区设消防站,Xj=0表地区不设消防站.Z=消防站总数,则模型如下:MinZ=X1+X2+X3+X4+X5+X6s.t.X1+X2≥1X1+X2+X6≥1X3+X4≥1X3+X4+X5≥1X4+X5+X6≥1X2+X5+X6≥1Xj=0或1；j=1,2,3,4,5,6.37银行选址P209l俄亥俄信托公司（OhioTrustCompany）希望在俄亥俄西北部20个县进行选址，该地区还没有首席业务处（PrincipalPlaceofbusinessPPB）。根据俄亥俄州的银行法，如果金融企业在任何一个县设立PPB，就可以在该县及其比邻的县设立分支机构。俄亥俄信托公司想知道在那些县设立PPB会使其数量最少？38表俄亥俄信托公司考虑的各县邻居考虑的县邻县的数字代号考虑的县邻县的数字代号12，12，16118，10，13，14，15，18，19，2021，3，12121，2，3，10，13，1632，4，9，10，12，13133，10，11，12，15，1643，5，7，91411，15，2054，6，71511，13，14，1665，7，17161，12，13，1574，5，6，8，9，17，18176，7，1887，9，10，11，18187，8，11，17，1993，4，7，8，101911，18，20103，8，9，11，12，132011，14，1939整数规划选址模型使用OR软件对该问题进行求解，我们得出需要3个PPB，他们应分