菜单
  

    1.分枝定界算法

    1.1分枝定界算法概述

    分枝定界算法(Branch-and-Bound  Algorithm,简称B&B)已被Land  Doig等人提出几十年之久.人们不单能够用其解决整数线性规划问题,而且还能用其解决近乎任意的最优化问题.

    1.2分枝定界算法的基本思想

    因有界 问题的整数解数目有有限多个,故可以通过“巧妙”的枚举 问题的可行 得到求解 问题的一种算法: 分枝定界法.先把给定的一个  的某些整数约束条件去掉,得到 的  并对其求解.若 无解,则 无解; 若 的最优解 各个分量都是整数,则 是 的最优解; 若 的某个分量不是整数,则有以下两种方法: 第一是对LP问题不停的改变以得到 的最优解; 第二是应用分枝术,将给定的原 问题 分解为若干个子问题,假如每个可行域内的最优解能在对应的子问题的可行域内找到,或者明确这个可行域内没有原  的最优解,这样原  就得到了简化.分解的过程称为分枝,步骤如 :

    对整数线性规划问题                                                  

    其中,A为整数矩阵,b, c为整数向量.如果  的  ,则 是 .如果 存在某个分量 不是整数,在可行域 或 中必然存在(P)的整数最优解的第i个分量,( 为不超过数 的最大整数),因而原问题 将被分解为以下两个子问题: 的可行域被这两个子问题分成了两个部分,若 的某个分量不是整数,排除.继续求 和 对应的LP问题,若 的LP问题的解 的分量全为整数,就不必再继续分枝; 若 的LP问题的最优解 的某个分量 不为整数,就把 按 或 分解成 .类似的,用上述方法继续分解下去,

  1. 上一篇:数学分析中不等式证明的常用方法
  2. 下一篇:线性无关的向量组正交化方法探讨
  1. 多项式拟合在变形数据分析中的应用

  2. 非线性差分方程解的单调性

  3. 因子分析在学生成绩综合评价中的应用

  4. 方差分析在小麦亩产量中的应用

  5. 威布尔分布的参数估计

  6. 教师视野下我校校园道路交通安全调查与分析

  7. 多元统计分析对能源消费总量及构成的研究

  8. 酸性水汽提装置总汽提塔设计+CAD图纸

  9. 当代大学生慈善意识研究+文献综述

  10. java+mysql车辆管理系统的设计+源代码

  11. 乳业同业并购式全产业链...

  12. 大众媒体对公共政策制定的影响

  13. 杂拟谷盗体内共生菌沃尔...

  14. 河岸冲刷和泥沙淤积的监测国内外研究现状

  15. 十二层带中心支撑钢结构...

  16. 中考体育项目与体育教学合理结合的研究

  17. 电站锅炉暖风器设计任务书

  

About

751论文网手机版...

主页:http://www.751com.cn

关闭返回