《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第四章 整 数 规 划》由会员分享，可在线阅读，更多相关《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第四章 整 数 规 划（49页珍藏版）》请在金锄头文库上搜索。
1、第四章 整 数 规 划,第一节 分枝定界法 第二节 割 平 面 法 第三节 01规划 第四节 指 派 问 题,第一节 分枝定界法,1.求解相应松弛问题 2.分枝 3.定界 4.剪枝,1.求解相应松弛问题,如果松弛问题的最优解不满足整数要求，那么从非整数的xi=b i 中任选一个变量，例如选取x r=b r进行分枝。记b r为不大于b r的最大整数。,2.分枝,3.定界,对于分枝x rb r 相应的松弛问题，如果其最优解为X (r)，最优值为z r，那么在这个分枝中，原整数规划的所有可行解目标函数值，都不会优于z r,也就是说，z r是分枝x rb r中整数规划目标函数值的上界。对于分枝x rb
2、 r +1，也具有同样的分析。,4.剪枝,如果在分枝x rb r中已得到了符合整数要求的最优解X(0)，其目标函数值为z0，而在另一分枝x rb r1中，其上界(即这一分枝中松弛问题的最优值)不超过z0，那么可以肯定，在分枝x rb r1中，不可能含有原来整数规划的最优解，则就把这一枝剪掉，不必再讨论下去，这就是剪枝。,例1 运用分枝定界法求解整数规划,极大化z=3x1+5x2 满足4x1+10x250 2x1-5x21 x1,x20且为整数,表 4-1,例1 运用分枝定界法求解整数规划,图 4-1,例1 运用分枝定界法求解整数规划,例1 运用分枝定界法求解整数规划,图 4-2,例1 运用分枝
3、定界法求解整数规划,表 4-2,表 4-3,例1 运用分枝定界法求解整数规划,图 4-3 (注：图中“”号表示已剪枝),例1 运用分枝定界法求解整数规划,例2 用分枝定界法求解整数规划,极大化z=4x1+3x2 满足3x1+4x212 4x1+2x29 x1,x20且为整数,表 4-4,例2 用分枝定界法求解整数规划,表 4-5,表 4-6,例2 用分枝定界法求解整数规划,表 4-7,例2 用分枝定界法求解整数规划,表 4-8,表 4-9,例2 用分枝定界法求解整数规划,图 4-4,例2 用分枝定界法求解整数规划,图 4-5,例2 用分枝定界法求解整数规划,第二节 割 平 面 法,一、割平面法
4、的基本思想 二、构造割平面,一、割平面法的基本思想,由线性不等式的意义知道，增加的切割条件，相当于将可行解集合切割掉一部分，所以又称割平面。要求这个割平面将非整数最优解割去，但却不会割去任何整数解，即不会割去任何可行解。增添切割条件后，成为一个改进的松弛问题。如果它的最优解符合整数要求，那么这个解就是整数规划最优解；否则，再给这个改进的松弛问题增添一个切割条件(即再增添一个不等式约束)，把改进的松弛问题的不符合整数要求的最优解割法，形成新的松弛问题。如此继续下去，能够证明，经过有很多次切割，总可以求得式最优解。,二、构造割平面,(1)求解相应的松弛问题式(4-9)，若式(4-9)无解，那么整数
5、规划式(4-8)也无解；如果式(4-9)的最优解符合整数要求，那么这个最优解也是式(4-8)的最优解；否则，转到下一步。 (2)在不符合整数要求的bi中任选一个，例如br，以约束方程 (3)把切割条件增添在式(4-9)的最优单纯形表中，用对偶单纯形法求解，若仍不能得到满足整数要求的最优解，则再转入步骤(2)。,二、构造割平面,二、构造割平面,二、构造割平面,表 4-10,二、构造割平面,表 4-11,表 4-12,二、构造割平面,图 4-6,二、构造割平面,第三节 01规划,一、01规划的数学模型 二、01规划的解法,一、01规划的数学模型,1.投资决策问题 2.选择厂址问题,1.投资决策问题
6、,现有资金b，可用n个项目的投资，已知项目j所需资金为a j，投资后可得利润c j (j=1,2,n)，不妨设b、a j、c j都是整数，试问如何选择投资项目，才能使所获总利润最大？ 设x j=0,不对项目j投资1，对项目j投资得如下整数规划模型 极大化z=c1x1+c2x2+c n x n 满足a1x1+a2x2+an x n b X j=0或1,j=1,2,n,2.选择厂址问题,要建厂生产某种物资，有m个地址可供选择，每个地址最多可建一个厂，在地址i建厂，单位时间生产能力为d i，单位时间的固定生产成本为a i。有n个点需求这种物资，需求点j的需求量为b j，从厂址i到需求点j的单位运费为
7、c j。如果不考虑建厂费和可变生产成本，问应如何选择厂址，才能使总的花费最低。,二、01规划的解法,对于01规划的求解，由于每个变量只取0或1，人们自然会想到用穷举法来求解，即排出全部变量取值为0或1的全部组合，计算出每一种组合上的目标函数值，再比较它们的大小，以取得最优解。但是，当n较大时，要找出所有的组合几乎是不可能的，因为共有2n个组合。计算所有组合上的目标函数值，再加上比较，工作量是非常大的。因此，如何设计一种计算方法，只需要比较目标函数在一部分组合上取值的大小，就能够求得最优解，这样一类方法统称为隐枚举法。,例4 求解01规划,极大化z=3x1-2x2+5x3 满足x1+2x2-x3
8、2 x1+4x2+x34 x1+x23 4x2+x36 x1,x2,x3=0或1,表 4-13,例4 求解01规划,例5 背包问题,一辆载重汽车可载重15t，有4种货物可装载，各种货物的重量和价值为 货物种类 1 2 3 4 重 量 2 3 4 5 价 值 3 4 5 6 若各种货物的装载件数不限，问如何装运，可使一车货物的价值最大。,解 问题的数学模型为 极大化z=3x1+4x2+5x3+6x4 满足2x1+3x2+4x3+5x415 xj0且为整数 其中x1,x2,x3,x4分别为4种货物的装载件数。,例5 背包问题,例6 求解01规划,极大化z=7x1+5x2+9x3+6x4+3x5 满
9、足56x1+20x2+54x3+42x4+15x5100 X j=0或1，j=1,2,5,例6 求解01规划,图 4-7,例6 求解01规划,图 4-8,例6 求解01规划,第四节 指 派 问 题,一、指派问题的数学模型 二、匈牙利法,一、指派问题的数学模型,实践中常遇到这样的问题，有不同的n项工作要做，恰好有n个人(或设备)能够从事这些工作，但每人不能同时做两项或两项以上的工作。由于各人的条件不同，工作的性质也不同，所以每人做不同的工作创造的价值和所消耗的资源也不同。那么应指派哪个人做哪项工作，才能使总的效益最好呢？,表 4-14,一、指派问题的数学模型,二、匈牙利法,1.行简约化 2.用最
10、少的m条直线覆盖C1中的零元素 3.在第类元素中最小值e=1,1.行简约化,2.用最少的m条直线覆盖C1中的零元素,3.在第类元素中最小值e=1,(1)找出(cij)每行(列)的最小元素，将每行(列)的所有元素都减去该行(列)的最小元素，然后转下一步。 (2)找出(cij)每列(行)的最小元素，若它们都为零，则转下一步；否则，每列(行)的元素减去其最小元素。 (3)以最少的m条直线(水平的或竖直的)去覆盖(或称划去)简约化价值系数矩阵中所有零元素。 (4)若m=n，则可从简约化价值系数矩阵中找到不同行不同列的n个零，于是最优解也就找到了，然后用初始价值系数矩阵的相应元素求和，便得到最优的目标函数值。,
