运筹学课件第四章 整数规划与分配问题

1、 表表 4-1-14-1-1 个城市建立配货中心不在第个城市建立配货中心在第 , 0 , 1iiyinjiyxnjbxiyDxmyyaxcZiijjiijiinjijiiiiinjijij, 1 , ,1 , 0 , 0, 1 ,n, 1 ,s.t.minn11n1in1n11表表4-3-1且均取整数值, 0,255 . 22108 . 02 . 1. .34max21212121xxxxxxtsxxz2025 . 1126 . 08 . 12121xxxx且均取整数值, 0,255 . 22108 . 02 . 1. .34max21212121xxxxxxtsxxz2 , 10, 1iii

2、yi种方式装载时不采用第，种方式装载时采用第i i=1,2=1,2分别是采用背包及旅行箱装载。分别是采用背包及旅行箱装载。（1 1） 由于所装物品不变，约束左边不变，整数规划数由于所装物品不变，约束左边不变，整数规划数学模型为学模型为2 , 110, 0120255 . 2212108 . 02 . 134max212121212121iyxyyyyxxyyxxxxZii或且取整数且均取整数值, 0,255 . 22108 . 02 . 1. .34max21212121xxxxxxtsxxz（2 2） 由于不同载体所装物品不一样，数学模型由于不同载体所装物品不一样，数学模型为为1212212

3、11221211212max431.20.810( )1.80.612( )22.525( )1.5220( )1,0,01ZxxxxMyaxxMybxxMycxxMydyyx xy且均取整数或2025 . 1126 . 08 . 12121xxxx且均取整数值, 0,255 . 22108 . 02 . 1. .34max21212121xxxxxxtsxxz甲、乙：甲、乙：丙、丁：丙、丁：M M为充分大的正数。为充分大的正数。当使用当使用背包背包时时( (y y1 1=1=1，y y2 2=0)=0)，式，式( (b b) )和和( (d d) )是多余的；是多余的；当使用当使用旅行箱旅行

4、箱时时( (y y1 1=0=0，y y2 2=1)=1)式式( (a a) )和和( (c c) )是多余的。是多余的。121221211221211212max431.20.810( )1.80.612( )22.525( )1.5220( )1,0,01ZxxxxMyaxxMybxxMycxxMydyyx xy且均取整数或且均取整数值, 0,5 . 45 . 01432. .23max21212121xxxxxxtsxxz结论：结论：且均取整数值, 0,5 . 45 . 01432. .23max21212121xxxxxxtsxxz0,5 . 45 . 01432. .23max212

5、12121xxxxxxtsxxz0,5 . 45 . 01432. .23max21212121xxxxxxtsxxz0,25 . 45 . 01432. .23max212212121xxxxxxxtsxxz0,35 . 45 . 01432. .23max212212121xxxxxxxtsxxz0,25 . 45 . 01432. .23max212212121xxxxxxxtsxxz0,35 . 45 . 01432. .23max212212121xxxxxxxtsxxz0,325 . 45 . 01432. .23max2112212121xxxxxxxxtsxxz0,425 .

6、45 . 01432. .23max2112212121xxxxxxxxtsxxzL0L0： （3.253.25，2.52.5） z=14.75z=14.75L1L1： （3. 53. 5，2 2） z=14.5z=14.5L2L2： （2.52.5，3 3） z=13.5z=13.5L11L11： （3 3，2 2） z=13z=13L12L12： （4 4，1 1） z=14z=14L0L0： （3.253.25，2.52.5） z=14.75z=14.75L1L1： （3. 53. 5，2 2） z=14.5z=14.5L2L2： （2.52.5，3 3） z=13.5z=13.5L11

7、L11： （3 3，2 2） z=13z=13L12L12： （4 4，1 1） z=14z=14整数规划问题整数规划问题的最优解的最优解若这个分枝的若这个分枝的14.5如何处理？如何处理？ （4.81，1.82）图图4-6-24-6-2找到最优整数解了吗？找到最优整数解了吗？解解 题题 过过 程程且均取整数值, 0,255 . 22108 . 02 . 1. .34max21212121xxxxxxtsxxz练习：练习：P126 4.7P126 4.7且均取整数值, 0,921432. .23max21212121xxxxxxtsxxz最终单纯形表最终单纯形表最终单纯形表最终单纯形表2122

8、121432xxx分离系数为整数和分数：分离系数为整数和分数：212211210432xxx）（）（2122121432xxx分离系数为整数和分数：分离系数为整数和分数：212211210432xxx）（）（将整数部分写在等号左边；分数部分写在等号的右边：将整数部分写在等号左边；分数部分写在等号的右边：43422121212xxxx00加上松弛变量使得加上松弛变量使得 变为变为= =：0212121543xxx212121543xxx212121543xxx将将 作为约束条件增加到单纯形表中，用对偶单纯形法求解作为约束条件增加到单纯形表中，用对偶单纯形法求解 对偶单纯形法求解：对偶单纯形法求解

9、：换出变量：换出变量：x5 x5 换入变量：换入变量：x3x31 11 11 1-2-22 20 0-1-11/21/27/27/20 01 1-1/2-1/20 0-1-1-1/2-1/2还没有得到整数解，所以继续重复第二步骤：还没有得到整数解，所以继续重复第二步骤：21321531xxx213211541xxx）（554121213xxxx写出约束条件：写出约束条件：分离整数和分数：分离整数和分数：000212165xx212165xx将将 作为约束条件增加到单纯形表中，用对偶单纯形法求解作为约束条件增加到单纯形表中，用对偶单纯形法求解 212165xx1 11 1-2-23 30 0-4

10、-44 40 0-1-11 10 02 20 0-1-1最优整数解最优整数解x1=4 x2=1x1=4 x2=1通过图形理解分割平面的含义！通过图形理解分割平面的含义！图图2 2（3/4,7/43/4,7/4）从表从表1 1的最终计算表中，得到非整数的最优解：的最终计算表中，得到非整数的最优解： x x1 1=3/4=3/4，x x2 2=7/4=7/4，x x3 3= =x x4 4=0=0，max max z z=5/2=5/2表表1 1474143434141432431xxxxxx43243314143431414343xxxxxxx041434343xx61121,321min0minljljjjjaazc由于由于x x1 1、x x2 2的值已都是整数，解题已完成。的值已都是整数，解题已完成。 练习：练习： 用割平面法求解下列用割平面法求解下列IPIP问题问题且为整数0,102304634max21212121xxxxxxxxZ252141431xxx212)