第四章__整数规划.ppt

Chapter 1 第四章 整数规划Integer Programming 第一节 整数规划问题的提出 纯整数规划(全整数规划),混合整数规划，0－1整数规划。 为了满足整数解的要求，只要将已得到的小数或分数解“四舍五入”化整，就可以了吗？ 化整后一可能不在可行域内，不是可行解；二不一定是最优整数解,再者,有些实际问题的解还必须满足一些特殊条件。 例子：某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表。 问：两种货物各托运多少箱，可使获得利润为最大？ 设X1、X2为甲乙两种货物托运的箱数。(非负整数) 解：X2＝－2X1＋0.1Z ①：斜率为－1.25 ②：斜率为－0.4 得到最优解为X1=4.8，X2=0， Z=96 若将（X1=4.8，X2=0）凑整为（X1=5，X2=0），显然已不满足约束条件①，25。 若将（X1=4.8，X2=0）凑整为（X1=4，X2=0），是可行解，但是否最优呢？当（X1=4，X2=0），Z＝80。 向原点平行移动目标函数的等值线，第一次遇到“＋”的B点，即为最优解。(“＋”的点表示可行的整数解。) 当（X1=4，X2=1），Z＝90，更优。 第二节 分枝定界解法 对于整数规划问题，很容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。这对于变量数少，可行的整数组合数也是很小时，这个方法是可行的。 分枝定界法（branch and bound method） 主要思路：对于目标函数值来讲，整数规划的最优解不会更优于相应线性规划问题的最优解。 设最优化的整数规划问题为A，相应的线性规划问题为B。问题A的最优目标函数值为Z*。 若线性规划问题B的最优解不能满足整数的条件，那么，这时最优目标函数值必是问题A的最优目标函数值Z*的上界Z，记作 。而A的任意可行解的目标函数值作为Z*下界，记作 。 分枝定界法就是将问题的可行域分成子区域（分枝）。分枝：当 不符合整数要求时，构造两个约束条件： ，分别形成两个子问题。 再增加目标函数值的下界，减少上界，最终找到最优目标函数值Z*。 解：先不考虑X1,X2为非负整数的条件，得最优解:X1＝3/2，X2=10/3，Z0=29/6。 它不符合整数条件， Z0作为Z*的上界。显然，(0,0)是问题A的一个整数可行解。0≤Z*≤29/6 对于分枝S2，最优值Z2＝10/3，小于4，所以不必讨论。 因4与61/14之间只有4一个整数，故4为所求整数规划问题目标函数的最优值。最优解为(3,1)(2,2)。 分枝定界法是计算机求解整数规划，进行迭代的基础。——原理 例5.6 第三节 切割平面法 它的基本思路是先不考虑对某些变量取整数值的要求，把它们都作为连续变量而用一般的单纯形法来求出最优解，然后增加辅助约束条件切割掉可行域中不含有可行整数点的部分可行域，再求出最优解。反复运用，直到找到满足要求的整数解为止。 一、分数切割 整数规划问题模型的标准化： 1.把不等式划为等式 2.出于割平面的需要，将约束条件非整数系数和右边常数项全部化为整数。 如：X1+1/3X2=13/2 →6X1+2X2+X3=39 从最终表中得到变量间的表达方式后，注意将变量系数和常数项分解为整数和非负真分数之和并且移项。 把整数及带有整数系数的变量移方程左边，分数及带有分数系数的变量移方程右边。 松弛问题的最优解： 第四节 0－1型整数规划问题 0－1型整数规划是整数规划中的特殊问题。它的变量只取0或1，也叫二进制变量。 在实际问题中，如果引入0－1型变量可将需要分别讨论的线性规划问题统一在一个问题中讨论了。 一、投资场所的选择 例1：京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Ai(i＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1，A2，A3三个点至多选择两个； 在西区由A4，A5两个点中至少选一个； 在南区由A6，A7两个点中至少选一个； 在北区由A8，A9，A10三个点中至少选两个。 Ai各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见下表所示： (单位：万元) s.t. 100X1+120X2+150X3+80X4+70X5+90X6+80X7+140X8+160X9+180X10=720 X1+X2+X3=2 X4+X5=1 X6+X7=1 X8+X9+X10=2 X