.如何得到松驰问题的最优解
图形法求解松驰问题的最优解是一种较为简单方便的方法；但由于其很难用计算机实现。最终应用LINGO9.0数学软件求解，这就需要VC++与LINGO的混合编程，以VC++为主体调用LINGO的接口，实现求解过程，并将结果返回给VC处理。与此同时，VC++调用LINGO接口函数求解时，需要执行LINGO源代码文件；在每次要分支时，得改变松驰问题的约束条件，这就需要动态改变LINGO源文件的代码。
3.1.4.如何提高求解效率
每当求解一个结点时，若需要分支则保存结点，多个结点分支时，将达到分支的结点预先保存的目的，在需要分枝求解的时候进行读取可实现两个分支的并行计算；在每次分支与定界时都需通过得到的最优解与上、下界进行比较，若减少比较次数，效率也会提高；
保存最优解信息，当前的目标值与保存的目标值进行比较，选出最优的方案进行保存，在求解完成后，最优解的信息即可得到⑦，无需进行查找。本文来自辣.文~论^文·网原文请找腾讯324,9114
3.2. 改进分支定界实现的策略和算法描述
3.2.1.实现策略
预先保存分支结点：对于大规模整数规划问题中，可能分支的次数比较大，若每次判断到结点需分支时，就进行分支后子结点的求解，求解过程比较不清晰，与预先保存分支结点统一求解做法相比效率较低；
减少比较次数：对子结点进行求解时，都需要对目标值的上、下界再定界。若每次都进行比较，则需要花费较多的计算时间在比较方面；因此将比较分为需要与原来上、下界进行比较和不需要与原来上、下界进行比较。
3.2.2.算法描述(以目标最大值为例)
(1)将问题LP作为树根插入树中，求解LP可能得到以下情况之一：
①若LP没有可行解，这时IP也没有可行解，则停止计算。
②若LP有最优解，并符合问题IP的整数条件，此时LP的最优解即为 IP的最优解，则停止计算。
论文网http://www.751com.cn/
③若LP有最优解，但不符合问题IP的整数条件，将此结点预先保存， 作为后继求解的分支结点，进入(2)步骤。
(2)将IP目标的上界置为问题LP的最优解，下界置为负无穷大；在问题LP的最优解中选第一个不符合整数条件的变量进行分支。设i为变量中第一个不符合整数条件变量的下标， = ，以[ ]表示不超过 的最大整数：
构造两个约束条件 <=[ ]和 >=[ ]+1，将这两个约束条件分别加入问题LP中，得到两个后继子问题，分别作为左分支与右分支插入树中，不考虑整数条件求解此分支的左子树与右子树。
(3)在求解左子树与右子树时，没有可行解，则停止计算；若有最优解并符合整数条件，则保存最优解。若有最优解但不符合整数条件，则将此结点预先保存作为后继的分支结点；以每个后继子问题为一分支并标明求解的结果，与当前目标最优解的结果进行比较，第一个子问题不需要比较，若符合整数条件，则将此最优解置为下界，若不符合整数条件，则将此最优解置为上界；第二个子问题依据第一个子问题的求解结果判断是否与上、下界进行比较。若两个子问题的解都符合整数条件或都不符合整数条件，则第二个子问题需与目标上下界进行比较；
(4)若各分支的最优目标函数值不在上、下界范围内，则剪掉此分支，即以后不再考虑进行求解；若在上、下界中，且不符合整数条件，则重复(3)步骤。直至分支的存储结构没有结点为止,即没有结点可再分支。
论文网http://www.751com.cn/
(5)求解最小值整数规划的算法步骤，与求解最大值的整数规划相似，只需在定界过程中将上、下界对换即可。本文来自辣.文~论^文·网原文请找腾讯324.9114
3.3. 改进分支定界算法框架结构及数据结构
从输入区中输入整数规划模型，从中解析出所需的目标函数与约束条件，并将对应的松驰问题模型写入LINGO源代码文件中，VC调用LINGO接口执行LINGO源文件，求解的结果会自动存入LINGO日志文件中。再从LINGO日志文件中解析出最优解信息。应用改进的分支定界算法对得到的最优解进行分析，判断是否需要分支，定界，剪枝等。
上一页 [1] [2] [3] [4] [5] [6] [7] [8]
分支定界法求解整数规划问题的设计与实现 第8页下载如图片无法显示或论文不完整，请联系qq752018766
