运筹学：第5章 整数规划

1、第五章 整数规划1. 整数规划模型2. 纯整数规划的割平面法3. 最优分配问题*(1.5,3.33)TX *(1,3)TX *(2,3)TX *(1,4)TX *(2,4)TX 四舍四舍五入五入原线性规划规划可行域原线性规划规划可行域整数规划规划可行域是什整数规划规划可行域是什么样的？么样的？如果有如果有60个变量，四舍五入的工作量有个变量，四舍五入的工作量有260次，计算机无法求解次，计算机无法求解IP，记为整数规划4.1 整数规划模型4.1 整数规划模型硬约束，软约束，书上硬约束，软约束，书上135页页通过引入0，1变量，将非线性问题转化为线性问题 作业： P204：1， 2，3（1），第

2、5题，第7题整数规划建模（二）5.4最优分配问题最优分配问题B1Bj.BnaiA11Ai1.An1bj111看193页di784118每行减每行减去去diuj每列减去每列减去uj( )( )( )( )( )( )( )( )( )( )( )( )5.2 纯整数规划的割平面法纯整数规划的割平面法 纯整数规划的算法本课程介绍两类：纯整数规划的算法本课程介绍两类： 割平面法割平面法 （基础算法）（基础算法） 分支定界法（实用算法）分支定界法（实用算法）1. 割平面法基本思想记（AIP）的可行域为KAIP。若将（AIP）中要求变量为整数这个约束去掉，则得到相应的线性规划（LP），记（LP）的可行域

3、为KLP LP0最优解X1=（9/2,7/2）T第一次割平面后LP1最优解X2=（32/7,3）T第二次割平面后LP2最优解X3=（4,3）T总结思想总结思想2.如何寻找割平面-柯莫利割 （1）数学记号2217722372222227770 xxxx 2.如何寻找割平面-柯莫利割 （1）数学记号容易出错22?722?7222222777 674P149页，记号2.如何寻找割平面-柯莫利割2.如何寻找割平面-柯莫利割请看书150页，然后回答问题。2.如何寻找割平面-柯莫利割如何在单纯形表中找柯莫利割如何在单纯形表中找柯莫利割注意：通常选择非整数部注意：通常选择非整数部分大的行来做割平面。分大的行

4、来做割平面。请同学做第二行的割平面。用什么方法求解TP?看书P154注意：筛掉的松弛变量只能是柯莫利割的松弛变量！P153 作业：204页8（1）对柯莫利割的说明P155总结5.2 纯整数规划的算法纯整数规划的算法 纯整数规划的算法本课程介绍两类：纯整数规划的算法本课程介绍两类： 割平面法割平面法 分支定界法分支定界法 5.4 分支定界法 引例：某区举行初中数学竞赛，1#，2# ， 3#三个重点中学参加，三个学校分别派出3个，2个，2个重点班的同学参赛。现在已知各个集合内的最高分数、得分人姓名和性别情况，见图。 问采用何种方法能够得知参赛女同学中的最高分数？ 5.4 分支定界法还可以再分还可以

5、再分 方法一：全部枚举 方法二：隐含枚举 松弛问题Bi的求解有现成答案或者简单算法。5.3.1 0-1背包问题背包问题 单位重量的价值最大的物品优先选取单位重量的价值最大的物品优先选取物品号xj重量价值1 #2 #3 #4 #5 #6 #7 #合计单位重量的价值最大的物品优先选取单位重量的价值最大的物品优先选取160页最后一段，为什么求解比较容易？K是松弛问题的一棵树。是松弛问题的一棵树。单位重量的价值最大的物品优先选取单位重量的价值最大的物品优先选取物品号xj重量价值1 #02 #3 #4 #5 #6 #7 #合计单位重量的价值最大的物品优先选取单位重量的价值最大的物品优先选取物品号xj重量

6、价值1 #12 #3 #4 #5 #6 #7 #合计谁先进行分支？单位重量的价值最大的物品优先选取单位重量的价值最大的物品优先选取物品号xj重量价值1 #02 #3 #04 #5 #6 #7 #合计单位重量的价值最大的物品优先选取单位重量的价值最大的物品优先选取物品号xj重量价值1 #02 #3 #14 #5 #6 #7 #合计是是K0最优值的下界。对其他分支进行比较。最优值的下界。对其他分支进行比较。如为如为213还要继续清查吗？还要继续清查吗？ 作业：206页10 树，表格要画整数规划作业112312312312312331max1502201901500200018003218002200031600,1,2,320,1,2,30 11,2,3jjjjjjzxxxyyyxxxxxxxxxxMyjyxjyj且为整数， ， 5.4 分支定界法4.3.2 分支定界法分支定界法 12(4,)5T12(5,)7T1K2K问：问：-61是是K。 的上界还是下界？的上界还是下界？问：关系问：关系120120KKKKKK(4,2)T5(,3)2T35(,1)6T(5,1)T6(6,)7T7K是什么形状？是什么形状？6(6,)