整数规划(运筹学)教材教学课件.ppt

* * 前两章内容回顾和总结 1，线性规划模型 2，线性规划的建模实例分析 3，线性规划的求解－图解法和Lindo 4，对偶问题 5，敏感性分析 * * 总结1： 目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。 线性规划问题（LP问题）的共同特征： 每一个问题变量都用一组决策变量（x1, x2, …, xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 若LP问题有最优解，则要么最优解唯一，要么有无 穷多最优解。 * * 总结2: LP问题 有可行解 有最优解 唯一解 无穷多解 无最优解（可行域为无界） 无可行解（无解） 规律1： * * 规律2： 线性规划问题的可行域为一凸集 线性规划问题凸集的顶点个数是有限的 最优解肯定可在凸集的某顶点处达到 * * 总结3： 线性规划问题的标准型 1. 标准型 * * 2. 所有LP问题均可化为标准型 * * 3，标准型LP问题的解 * * 线性规划对偶的一般形式 * * 舍入解的挑战 舍入解可能不是可行解 舍入解与最优解离很远 可能有多个舍入解出现 * * 第一节.整数规划问题的提出 一、整数规划的一般形式 1、实例： 例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5－1： 货物 体积 每箱（米3） 重量 每箱（百斤） 利润 每箱（百元） 甲 乙 5 4 2 5 20 10 托运限制 24 13 问两种货物各托运多少箱，可使获得的利润为最大？ * * 2、整数规划一般形式 解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为： * * （2）求解方法方面 3、与线性规划问题的区别 在例1中， 此IP问题的最优解(值)为： 线性规划问题的最优解(值)为： （1）放松整数约束的整数规划就是线性规划 * * 例2 做图分析例1的最优解(直观) IP 问题可行域不为凸集 （3）理论方面 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 * * 二、整数规划的分类 1、全整数规划问题 2、纯整数规划问题 在下列IP问题中， 在上述IP问题中， * * 3、0-1整数规划问题 在上述IP问题中， 4、混合整数规划问题 在上述IP问题中， 5、线性整数规划和非线性整数规划问题 在上述IP问题中，目标函数是线性的 * * 第二节 分枝定界法 一、几何解释 适用范围： 全整数规划问题 纯整数规划问题 0-1规划问题 混合整数规划问题 例3 求解A * * 解：图解法。 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 x(0)=(4.81,1.82) Z0=356 问题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 * * 二、分枝规则 情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4 或 5 * * 三、运算步骤 解松弛问题 满足要求? 结束 分枝 Y N * * 例4 求解下列IP问题 松弛问题的最优解为：x*=(5/2,2),Z*=23 分枝B1:x1?2 分枝B2:x1?3 * * max 6x1+4x2 st 2x1+4x213 2x1+x27 end gin x1 gin x2 * * 问题II的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题 分枝问题的松弛解 * * 图解法 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 x*=(5/2,2