整数规划(运筹学).ppt

02:57,1,前两章内容回顾和总结,1，线性规划模型 2，线性规划的建模实例分析 3，线性规划的求解图解法和lindo 4，对偶问题 5，敏感性分析,02:57,2,总结1：,目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。,线性规划问题（lp问题）的共同特征：,每一个问题变量都用一组决策变量（x1, x2, , xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。,存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。,若lp问题有最优解，则要么最优解唯一，要么有无 穷多最优解。,02:57,3,总结2:,lp问题,有可行解,有最优解,唯一解 无穷多解,无最优解（可行域为无界）,无可行解（无解）,规律1：,02:57,4,规律2：,线性规划问题的可行域为一凸集 线性规划问题凸集的顶点个数是有限的 最优解肯定可在凸集的某顶点处达到,02:57,5,总结3： 线性规划问题的标准型,1. 标准型,02:57,6,2. 所有lp问题均可化为标准型,02:57,7,3，标准型lp问题的解,02:57,8,线性规划对偶的一般形式,02:57,9,敏感性分析,很多软件可以生成目标函数系数或者约束右端参数的灵敏度报告，可以很快计算出最优域 ； 运用目标函数系数的百分百法则，可进一步方便地检验所有参数同时变动的情况 ； 通过影子价格分析，发现改变决策会产生的影响，从而为管理层更好的决策提供指导 ； 用约束右端值变动的百分百法则来判断变动的幅度。,02:57,10,第四章 整数规划,整数规划问题的提出 整数规划的求解-分支定界法 0-1规划建模,02:57,11,什么时候需要整数解？ 得到小数解时如何处理呢？,整数解,你有什么绝招吗？,02:57,12,舍入解的挑战,舍入解可能不是可行解 舍入解与最优解离很远 可能有多个舍入解出现,02:57,13,第一节.整数规划问题的提出,一、整数规划的一般形式,1、实例：,例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表51：,问两种货物各托运多少箱，可使获得的利润为最大？,02:57,14,2、整数规划一般形式,解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为：,02:57,15,（2）求解方法方面,3、与线性规划问题的区别,在例1中，,此ip问题的最优解(值)为：,线性规划问题的最优解(值)为：,（1）放松整数约束的整数规划就是线性规划,02:57,16,例2 做图分析例1的最优解(直观),x1,x2,4,8,4,0,z=96,1,2,3,5,6,7,3,1,2,5x1+4x2=24,2x1+5x2=13,c(4.8,0),z=90(最优解),b(4,1),z=80,02:57,17,二、整数规划的分类,1、全整数规划问题,2、纯整数规划问题,在下列ip问题中，,在上述ip问题中，,02:57,18,3、0-1整数规划问题,在上述ip问题中，,4、混合整数规划问题,在上述ip问题中，,5、线性整数规划和非线性整数规划问题,在上述ip问题中，目标函数是线性的,02:57,19,第二节 分枝定界法,一、几何解释,适用范围： 全整数规划问题 纯整数规划问题 0-1规划问题 混合整数规划问题,例3 求解a,02:57,20,解：图解法。,x1,x2,0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9x1+7x2=56,7x1+20x2=70,b,c,问题b1 z1=349 x1=4.00 x2=2.10,问题b2 z2=341 x1=5.00 x2=1.57,x1=x(0),x1=x(0)+1,z=40x1+90x2,02:57,21,二、分枝规则,情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4 或 5,02:57,22,三、运算步骤,解松弛问题,满足要求?,结束,分枝,y,n,02:57,23,例4 求解下列ip问题,松弛问题的最优解为：x*=(5/2,2),z*=23,分枝b1:x12,分枝b2:x13,02:57,24,max 6x1+4x2 st 2x1+4x213 2x1+x27 end gin x1 gin x2,02:57,25,问题ii的解即原整数问题的最优解,可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，np-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题,分枝问题的松弛解,02:57,26,图解法,x1,x2,0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,2x1+x2=7,2x1+4x2=13,02:57,27,第三节 01规划,例5（选址决策问题）因业务需要某公司要建立12个新工厂：甲地或乙地。同时考虑建立一个仓库。仓库必须和某个新厂建在同一地点。不设新厂也就不用建仓库。这次扩建可使用的资金总额为1000万。问对公司的选址问题应如何决策。,02:57,28,整数规划中的0-1整数变量,决策变量 多中选一 对于决策之间的相互依赖的逻辑关系 决策i和决策j是一种紧相关关系 选择性约束，如选择和不选择x8分别触发约束条件5x4+3x5100和5x4+3x550。表示为: 5x4+3x5100x8（如果x8=1） 5x4+3x550(1-x8 ） （如果x8=0） 进一步写为： 5x4+3x5-100x8 0； 5x4+3x5+50x8 50,02:57,29,想一想,某公司拟从六个项目中选择若干项目，请用0-1变量表示下列关系 1,2,3项目中至少选择一个. 若项目4被选中，则项目6不能被选中. 某足球队要从1、2、3、4、5号五名队员中挑选若干名上场?令 请用 的线性表达式表示下列要求: 从1, 2, 3号中至少选2名 只有3号上场，4号才上场,阅读材料 参考书 p79-80，第4.2.3节,02:57,30,02:57,31,例5模型为,02:57,32,整数规划的计算方法 软件实现 例5在lindo中的实现为,02:57,33,例6：某厂打算生产三种型号的容器，使用的资源情况、利润如下：,其中固定费用是指，只要生产，不管数量多少，都要投入的费用。问题是三种容器要不要投产、产多少？,02:57,34,求解：,假设计划生产小、中、大号容器的数量分别为x1、x2、x3 是否生产的逻辑变量为y1、y2、y3，取值1表示生产，取值0表示不生产, 那么利润函数为,金属板的限制为,劳动力的限制为,机器设备的限制为,xi与yi之间的关系,02:57,35,例7.投资场所的选择 在10个位置ai当中选择若干个, 总投资额不超过720万元, 其中a1, a2, a3最多选两个; a4, a5至少选一个; a6, a7至少选一个; a8, a9, a10至少选两个. 投资额及利润见表82. 选中的有收益(费用), 未选中的则没有.,02:57,36,假设逻辑变量xi=1表示