运筹学第6章整数规划R5.pptVIP

*/54 Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 s.t. x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xi ≥ 0且为整数， yi 为0--1变量，i = 1,2,3 解：设x1、x2、x3为生产小、中、大容器的数量。 由于制造的固定费用只有生产了才投入，设 上式等价于约束 xi ≤ M yi ，i =1，2，3，M充分大. （显然当xi = 0 时，yi = 0; 当xi 0 时，yi =1 。） */54 4.2 0-1型整数规划的解法 */54 4.目标函数值最大（最小）的解就是最优解。 隐枚举法的步骤： 1.找出任意一可行解，目标函数值为Z0； 2.原问题求最大值时，则增加约束(过滤条件)： 当求最小值时，上式 改为 ； 3.列出所有可能解，对每个可能解先检验是否满足过滤条件。 若满足再检验其它约束；若不满足，则认为不可行。若所有约束都满足，则认为此解是可 行解，求出目标值； */54 例1 求解下列0－1 规划问题 */54 解（穷举法）0－1 规划问题中，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。 x1 . x2. x3 约束条件 满足条件 Z 值 (1) (2) (3) (4) 是∨ 否× ( 0. 0. 0 ) 0 0 0 0 ∨ 0 ( 0. 0. 1 ) －1 1 0 1 ∨ 5 ( 0. 1. 0 ) 2 4 1 4 ∨ －2 ( 1. 0. 0 ) 1 1 1 0 ∨ 3 ( 0. 1. 1 ) 1 5 × ( 1. 0. 1 ) 0 2 1 1 ∨ 8 ( 1. 1. 0 ) 3 × ( 1. 1. 1 ) 2 6 × */54 [解]： 容易看出X=(1,0,0)满足约束条件，对应Z=3，对MaxZ来说，希望Z?3,所以增加约束条件： Z=3x1- 2x2 + 5x3 ? 3 (◎) 称为过滤性条件。初看起来，增加过滤性条件似乎增加了计算量，实际上却减少了计算量。 因为添加过滤性约束条件◎到0-1整数规划的数学模型中后，实际做了24次运算，而原问题需要计算23×4=32次运算（3个变量，4个约束条件）。见下表： 隐枚举法 */54 最优值 表5－5 × 6 2 6 （1，1，1） × 1 （1，1，0） 8 √ 1 1 2 0 8 （1，0，1） 3 √ 0 1 1 1 3 （1，0，0） × 5 1 3 （0，1，1） × -2 （0，1，0） 5 √ 1 0 1 -1 5 （0，0，1） × 0 （0，0，0） ④ ③ ② ① Z值 满足条件？ 是( √ ) 否(×) 条件 点 过滤条件：3x1- 2x2 + 5x3 ? 3 (◎) */54 可采用以下两种方法减少计算量： 改进过滤性条件，在计算过程中随时调整右边常数。 价值系数按递增排列。 如上述例题中，改写 z = 3x1-2x2+5x3 =-2x2+3x1+5x3，因为系数-2,3,5是递增的。变量(x2, x1,x3)也按下述顺序取值：(0,0,0)，(0,0,1)，(0,1,0)，(0,1,1)……，这样最优解容易比较早的发现。再结合过滤条件的改进，更可以减少计算量. 现在仍以上例来介绍这两种减少计算量的方法。 这种方法对于变量个数少的0-1整数规划问题计算并不复杂，但变量个数增多时，会导致“组合爆炸”，能否有一些办法来减少计算量呢？？？ */54 循环 (x2,