整数规划的难度远大于一般线性规划(PPT 16页)
所属分类：职业规划
文件大小：71 KB
下载要求：10 学币或VIP
点击下载
资料简介：
整数规划
整数规划的难度远大于一般线性规划
4.1 整数规划简介
要求所有 xj 的解为整数，称为纯整数规划
要求部分 xj 的解为整数，称为混合整数规划
对应没有整数解要求的线性规划称之为松弛问题
整数规划的解是可数个的，最优解不一定发生在极点
整数规划的最优解不会优于其松弛问题的最优解
4.2 整数规划的分枝定解法
4.2.1 思路与解题步骤
只解松弛问题
1、在全部可行性域上解松弛问题
若松弛问题最优解为整数解，则其也是整数规划的最优解
2、分枝过程
若松弛问题最优解中某个 xk=bk 不是整数，令 bk 为 bk 的整数部分
构造两个新的约束条件 xk bk 和 xk bk +1，分别加于原松弛问题，形成两个新的整数规划
3、求解分枝的松弛问题 — 定界过程
设两个分枝的松弛问题分别为问题 1 和问题 2 ，它们的最优解有如下情况
..............................
上一篇：人力资源规划(PPT 86页)
精品资料网 m.cnshu.cn
Copyright © 2004- 粤ICP备10098620号-1
