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