wang-第4章 整数线性规划.pptVIP

教学要求：;整数线性规划定义;整数线性规划的一般模型;应用与实例 ;整数规划建模举例;整数线性规划建模举例;例2：组合投资问题。;例3：某产品有n 个区域市场，各区域市场的需求量为 bj 吨/月；现拟在m 个地点中选址建生产厂，一个地方最多只能建一家工厂；若选 i 地建厂，生产能力为 ai 吨/月，其运营固定费用为Fi 元/月；已知址i至j区域市场的运价为 cij 元/吨。如何选址和安排调运，可使总费用最小？;混合整数线性规划;特征—变量整数性要求 来源 问题本身的要求 引入的逻辑变量的需要 性质—可行域是离散集合;整数规划;一、舍入化整法;二、枚举整数法;三、分支定界法;在分支的过程中，若当前已经得到的满足整数要求 的最优值为 ，则该 就可是作为一个过滤条 件，对于最优值小于或等于 的子问题无需再分 支，则这样的子问题称为被剪枝。未???剪枝的子问 题需继续分支。;例：;例：;易得其最优解为(3/2,5/2),最优值为-4;3、分别解这两个子问题的松弛问题：;4、选取目标函数较优(-7/2)的那个点先分枝 (即第二个子问题)，引进 得：;5、解这两个子问题的松弛问题：;6、对第一个子问题继续分枝，引进约束条件 得到：;7、解这两个子问题的松弛问题：;8、再看另一个分枝：;分支定界法求解举例--2;x1 ≥ 2;例1 投资问题;例2、互斥约束问题;互斥约束的推广;互斥约束的推广;例3 逻辑变量;第四节 指派问题;指派问题标准形式;指派问题数学模型