运筹学整数的规划PPT学习教案

1、会计学1 运筹学整数的规划运筹学整数的规划 10 1 1 2 . max 76 54 321 7 1 7 1 orx xx xx xxx Bxb ts xcZ i i ii i ii 例2: 相互排斥的约束条件 某厂拟采用集装箱托运甲乙两种货物，每箱的体积、重量、可获 利润以及托运(车运)所受限制如下表, 如采用船运, 其体积托运限制则 为45,问两种货物托运多少箱，可使获得利润为最大？ 第1页/共10页 货物 体积 每箱（m3） 重量 每箱（吨） 利润 每箱（百元） 甲424 乙513 托运限制206 解: 设x1, x2分别表示甲乙两种货物的托运箱数, 则其整数规划数学模型 为 取整数,

2、0, 62 )1(4554 2054 . 34max 21 21 21 21 21 21 xx xx xx Myxx yMxx ts xxZ 0 1 y 当采用船运方 式 当采用车运方 式 其中 第2页/共10页 一般情况下, m个约束条件中选择q个约束条件, 则可变成为: ai1x1+ai2x2+ainxnbi+yiM, i=1,2,m y1+y2+ym=m-q 其中yi是0, 1变量，且只有一个取0。 0-1整数规划问题的解法整数规划问题的解法 若有n个决策变量, 则可以产生2n个可能变量的组合, 故完全 枚举是不可能的. 求解0-1整数规划问题的解法均是部分枚举法或 称为隐枚举法(Imp

3、licit enumeration) 基本思想基本思想是: 在2n个可能的变量组合中, 往往只有一部分是可 行解. 只要发现某个变量组合不满足其中的某一约束条件时, 就不 必要检验其它的约束条件是否可行。 若发现一个可行解, 则根据 它的目标函数值可以产生一个过滤条件(Filtering constraint), 对于 目标函数值比它差的的变量组合就不必再去检验它的可行性（类 似分支定界法中的定界。实际上，隐枚举法是一种特殊的分支定 界法）。 在以后求解过程中, 每当发现比原来更好的可行解, 则依 次替代原来的过滤条件 (可减少运算次数, 较快地发现最优解)。 第3页/共10页 10, 64

4、3 44 22 . 523max 321 32 21 321 321 321 orxxx xx xx xxx xxx ts xxxZ 以例子说明上述求解方法 例1: 求解下述0-1整数规划问题 解：求解过程见下表 第4页/共10页 所以，最优解为（x1，x2，x3)T=(1,0,1)T, 最优值为8. 第5页/共10页 注： 当决策变量(x1, x2 , x3)按(0,0,0), (0,0,1), (0,1,0), (0,1,1),.方式取值时, 为了减少计算次数, 通常将目标函数中的决 策变量的顺序按其系数的大小重新排序, 以使最优解能较早出现 。对最大化问题, 按从小到大的顺序排列；对极小

5、化问题, 则相反 。 例2：求解下述0-1整数规划问题 10, 535 846 12 . 73min 4321 421 4321 4321 4321 orxxxx xxx xxxx xxxx ts xxxxZ 第6页/共10页 解：重新排序为 10, 553 864 12 . 37min 4321 412 3412 3412 3412 orxxxx xxx xxxx xxxx ts xxxxZ 第7页/共10页 (x2,x1,x4 ,x3)Z 值 约束条件 过滤条件 （0,0,0,0）0 (0,0,0,1)-1 (0,0,1,0)1 (0,0,1,1)0 (0,1,0,0)3 (0,1,0,1)2 (0,1,1,0)4 (0,1,1,1)3 Z3 (1,0,0,0)7 (1,0,0,1)6 (1,0,1,0)8 (1,0,1,1)7 (1,1,0,0)10 (1,1,0,1)9 (1,1,1,0)11 (1,1,1,1)10 第8页/共10页 练习：求解下述整数规划问题 5 ,