由于B11和B12目标值最优解已经不在Z*的上、下界里，则停止计算。
于是可以断定原问题的最优解为：
。
2.3.2. 优缺点
优点：分支定界法可以用于求解多类整数规划问题；采用这种方法求解整数规划问题灵活且便于用计算机编程实现；
缺点：分支定界法在作切割后形成了两个分支，如不加于选择，后继计算便为两个较小子域上的整数规划，随着分枝增多[15]，计算量较大。
2.4. 本课题设计目标
割平面法与基本分支定界法只能求解全整数规划与部分整数规划问题，隐枚举法只适用于求解0-1规划，若要将三类整数规划混合在同一数学模型中统一求解，上面的这三种方法都不能达到统一求解的要求，并综合分析各类求解方法的优缺点，最终选择以基本的分支定界法为基础，并稍做改进，减少目标值比较次数，提高求解的效率；应用MFC图形化界面输入，使得操作简单；求解的结点采用树型结构进行存储；
3. 算法设计
3.1. 研究设计中要解决的问题
3.1.1.如何使得模型(目标函数与约束条件)的输入简单方便
在单文档应用程序中，可将视图区域分为输入区与显示区⑥。制定一些简单的输入规则；并编写对输入字符串的解析类，从中解析出变量个数，目标函数，全部约束条件，松驰问题对应的约束条件等等。
输入规则如下：
(1)由于采用LINGO9.0数学软件求解整数规划对应的松弛问题，则默认设置所有变量非负，无需输入X>=0之类的；
(2)字母不区分大小写；
(3)所有变量皆为x后接数字格式，比如：x1；
(4)每条语句以"；"结束，包括注释语句(以'!'开始)；
(5)目标函数格式：max(或min)=x1+2*x2； (*号不可省略)；
(6)约束条件以"["开头，以"]"结束；本文来自辣.文~论^文·网原文请找腾讯324.9114
(7)@GIN(x)：限制变量x为整数；@BIN(x)：限制变量x为0或1；@FREE(x)：取消对变量x的符号限制(即可取任意实数包括负数)；@BND(l,x,u)：限制l<=x<=u；论文网http://www.751com.cn/
3.1.2.分支过程中，涉及的结点比较混杂，采用什么数据结构存储效率比较高
由于求解过程中，切割后分为左分支与右分支，与二叉树比较类似；比较适合采用非连续型存储结构，因而树型存储结构是一个不错的选择，以键值搜索树结点，插入结点都比较方便。
树结点数据结构：
typedef struct Node
{
int key; //结点(编号)键值
char *Value; //目标函数值与变量值
struct Node *rchild; //右孩子指针
struct Node *lchild; //左孩子指针
char *condition; //约束条件
char *rCon; //右分支条件
char *lcon; //左分支条件
上一页 [1] [2] [3] [4] [5] [6] [7] [8] 下一页
分支定界法求解整数规划问题的设计与实现 第7页下载如图片无法显示或论文不完整，请联系qq752018766
