1、010-62374836(宅 )华北电力大学华北电力大学线性规划图解法单纯形表结构线性规划单纯形法 (1)最小元素法 伏格尔法闭回路法 位势法闭回路调整法目标规划图解法 (1)目标规划图解法 (2)整数规划 (分枝定界法 )和和线性规划单纯形法 (2)图解法与单纯形法的联系指派问题 (匈牙利法 )(1)使用计算机软件包求解指派问题 (匈牙利法 )(2)0-1规划 (隐枚举法 )整数规划 (割平面法 )典型应用案例线性规划单纯形法 (3)目标规划单纯形法线性规划求解几种结果几种常用规划数学软件比较动态规划 (1)动态规划(2)最小树问题 (破圈法 /避圈法 )最短路问题 (迪克斯拉法 )(1)最
2、大流问题 (福克逊法 )最小费用最大流问题(2)对偶单纯形法改进单纯形法 动态规划 (逆推法 )(顺推法 )(3)对于整数规划问题对于整数规划问题 , 先不考虑整数约束先不考虑整数约束 ,求相应的线性求相应的线性规划问题的最优解规划问题的最优解 ,如果最优解是一个非整数最优解如果最优解是一个非整数最优解 , 构造构造约束条件约束条件 , 缩小线性规划问题的可行域缩小线性规划问题的可行域 ,丢弃不含整数解的丢弃不含整数解的区域，然后在缩小后的子可行域中继续求解区域，然后在缩小后的子可行域中继续求解 ,直止求出相直止求出相应的线性规划的最优解为整数解。应的线性规划的最优解为整数解。分枝： 如果求出
3、的最优解是一个非整数解，则以这个解任一分量相邻的两个整数点为边缘将线性规划的可行域分成两个子区域，每个子区域就是一个分枝（或子问题）；定界： 在分枝过程中，通过分枝找到更好的最优值和整数解不断地修改上下界，和减小上下界之间的范围，当上下界相同时，即得到整数最优解。分枝定界法的基本思想分枝定界法的基本思想 :2. 定界。设整数规划的目标最优值为 z*， 则 ，其中， 和 为整数规划目标值的上、下界；3. 分枝。在非整数最优解中，任选一个不符合整数条件的变量，构造两个约束条件：4. 修改上下界。方法如下：q 在各分枝中，找出目标值最大者作为新的上界；q 从已符合整数条件的分枝中，找出目标值最大者作
4、为新的下界。5. 比较和剪枝。比较各个分枝的目标值，如果有小于 者，则剪掉这个分枝；否则，继续分枝。反复进行，当 ，得到整数最优解 。 例例 1：用分枝定界法求整数规划：用分枝定界法求整数规划分枝定界法的求解步骤分枝定界法的求解步骤 :1. 先不考虑整数约束条件，求解相应的线性规划，有以下几种情况： 如果线性规划没有可行解，则整数规划也没有可行解，停止计算； 如果线性规划有最优解，且为整数最优解，则这个解为整数规划的整数最优解； 如果线性规划有最优解，但为非整数最优解，则转入下一步；9x1+7x2=56BC0x1x21 2 53 4 6 7 8 9125346787x1+20x2=70整数规划
5、整数规划 (分枝定界法分枝定界法 ) (例例 1)Bz = 40x1+90x2x1=4.81x2=1.82 z=356B0 Z* 3569x1+7x2=56x1=4x1=5BC0x1x21 2 53 4 6 7 8 9125346787x1+20x2=70B1B2x1=4.81x2=1.82 z=356BB2x1=4.00x2=2.10 z=349x1=5.00x2=1.57 z=341B1整数规划整数规划 (分枝定界法分枝定界法 ) (例例 2)0 Z* 356 349z = 40x1+90x29x1+7x2=56x2=3x1=4x1=5BC0x1x21 2 53 4 6 7 8 91253
6、46787x1+20x2=70B3B4x2=1x2=2 x2=2B25B4B3 x1=4.00x2=2.00 z=340x1=1.42x2=3.00 z=327x1=4.81x2=1.82 z=356BB2x1=4.00x2=2.10 z=349x1=5.00x2=1.57 z=341B1B5x1=5.44x2=1.00 z=308无无可可行行解解B6整数最优解整数最优解 : x1=4.0 ,x2=2.0整数规划整数规划 (分枝定界法分枝定界法 ) (例例 1)0 Z* 356 3490 Z* 349Z下界 = Z*=Z上界z = 40x1+90x2对于整数规划问题 ,首先不考虑整数约束 ,求
7、解相应的线性规划问题的解 ,如果最优解是一个非整数解 ,就 增加一增加一个约束条件个约束条件 ,缩小线性规划问题的可行域 ,继续求解 ,直到求出相应的线性规划问题的最优解为整数解。割平面法的基本思想割平面法的基本思想 :例：求解下列整数规划：整数整数最优解整数最优解 :例 3： 用割平面法求解整数规划整数1 1 0 01400-1 1 1 03 1 0 11 1 0 0解：先不考虑整数约束，求相应的线性规划的最优解，用单纯形法求解，标准型和初始单纯形表如下：1 1 0 03/47/4111 0 -1/4 1/40 1 3/4 1/40 0 -1/2 -1/2-5/2经过若干步迭代后，得到如下最优表及最优解：最优解： x1=3/4 , x2=7/4 , x3= x4=0 , max z =5/2 ,显然不符合整数条件。构造切割方程： 首先，从最优表中任意选一非整数分量，写出其相应的约束条件，如：再将上式中的系数和常数都分解成整数和非负真分数之和，并移项 (整数移到左边，分数移到右边 )，如：
