6运筹学第五章2007.ppt

运筹学基础 第一节 整数规划数学模型及解的特点 第一节 整数规划数学模型及解的特点 整数规划与其松弛问题最优解和最优值的关系 三、 整数规划数学模型举例 第二节 整数规划的割平面法 第二节 整数规划的割平面法 第二节 整数规划的割平面法 第二节 整数规划的割平面法 第三节 整数规划的分支定界法 第三节 整数规划的分支定界法 第三节 整数规划的分支定界法 第三节 整数规划的分支定界法 第四节 0—1 型整数规划法 第四节 0—1 型整数规划法 第四节 0—1 型整数规划法 第四节 0—1 型整数规划法 第四节 指派问题 第四节 指派问题 第四节 指派问题 第四节 指派问题 第四节 指派问题 * * 主讲教师： 联系电话： 短 号： E-mail: 清华大学出版社 《运筹学教程》（第三版） 胡运权 主编 教材 运 筹 帷 幄 之 中 决 胜 千 里 之 外 运 筹 学 课 件 整 数 规 划 第 五 章 Dynamic Programming 一、线性规划的数学模型的表示 max（min） z = xj ≥ 0 (j=1,2, … … ,n) st. cjxj aijxj ≤ (或=,≥) bi (i=1,2, … … ,m) 线性规划问题的特征 ： （1）目标函数是决策变量的线性函数 （2）约束条件是含决策变量的线性等式或不等式 二、整数规划的数学模型的表示 max（min） z = xj ≥ 0，xj部分或全部取整数(j=1，2, … … ,n) st. cjxj aijxj ≤ (或=,≥) bi (i=1,2, … … ,m) 整数规划的矩阵表示： 整数规划的松弛问题： 整数规划的可行解一定是其松弛问题的可行解。 整数规划的最优值不优于其松弛问题的最优值。 解 设：xi 为服务员在 i 时段开始上班人数 min z= x1 + x2 + x3 + x4 + x5+ x6 + x7 + x8 约束条件 x1≥10 st . 例1 时段（2h） 1 2 3 4 5 6 7 8 服务员最少数目 10 8 9 11 13 8 5 3 要求：服务员要连续工作4个时段 目标：人数最少 目标 x1 + x2 ≥8 x1 + x2 + x3 ≥9 x1 + x2 + x3 + x4 ≥11 x2 + x3 + x4 + x5 ≥13 x4 + x5 ≥5 x3 + x4 + x5 ≥8 x5 ≥3 且xj为整数 xj≥0 (j=1,2,3,4,5) 例2、例3见书P124，125 例1 时段（2h） 1 2 3 4 5 6 7 8 服务员最少数目 10 8 9 11 13 8 5 3 要求：服务员要连续工作4个时段 目标：人数最少 四、整数线性规划的数学模型及解的特点 max（min） z = xj ≥ 0 且 取整数 (j=1,2, … … ,n) st. cjxj aijxj ≤ (或=,≥) bi (i=1,2, … … ,m) 整数线性规划问题与一般线性规划最大区别是 ： (1) 整数规划中决策变量必须为整数 (2) 设两组可行解X1、X2，(aX1+bX2)不一定是整数规划的解 （其中，a，b0 且 a+b=1） (3) 一般线性问题的可行域为一个凸集，而整数规划的可行域 是一些离散点。 ? 取整数 全部决策变量都取整数时称全（纯）整数规划 部分决策变量取整数时称混合整数规划 决策变量只能取0或1时称0-1型整数规划 ? 五、整数线性规划的求解方法 max z= x1 + 4x2 例2 -2x1 + 3x2 ≤ 3 x1 + 2x2 ≤ 8 x1 ,x2 ≥ 0 且取整数 St. x1=18/7 x2=19/7 Z=94/7 x1=3 x2=3 Z=15 x1=2 x2=3 Z=14 x1=2 x2=2 Z=10 x1=3 x2=2 Z=11 X1*=4 x2*=2 Z*=12 一种最简单的方法：枚举法 这种思路为：找出所有整数可行解，并分别算出其目标值，通过比较求得问题 的最优解 红色区域与原区域区别： 1.是原区域的一部分 2.与原问题有相同的可行解 这种方法的思路： 把原区域割去不含原问题可行解的那部分区域，从而可以求得原问题的最优解。 我们称这种思路为割平面法 第一步：先不考虑整数约束，利用单纯形法进行求解 割平面法——如何割？ 1958年，高莫瑞提出一种每次增加一个约束——割平面 约束，来割除一些多余的可行域。 ………………. 0