玩命加载中 . . .

数学建模学习笔记(一):线性规划和整数规划


最近在准备美赛,从0学起,用这些帖子记录一下学习过程。这篇文章包括 线性规划整数规划 的部分

线性规划

线性规划这部分其实比较简单,就是初高中的数学题类型,这里要记下 Matlab 线性规划函数的使用,其标准型为:

函数一般调用形式为:

[x, fval] = linprog(c, A, b, Aeq, beq, LB, UB)

注意要先把模型灵活地变为标准型,比如加负号以改变不等号方向等等。如果没有 UB 的话可以不写。

这些参数中,x 为列向量,其他的可以相应的推导。输出参数 fval 为最优解时的

整数规划

整数规划就是指要求参数为整数时的规划,不能简单的按线性规划来然后最后最优解取整,那样有可能是不满足约束条件的。目前所流行的这些整数规划方法,往往只适用于整数线性规划,没有「通解」。

整数规划分为纯整数规划和混合整数规划,纯整数就是所有的参数都要求是整数,混合整数则反之。

求解方法有如下几种:

  • 分枝定界法:可求纯或混合整数线性规划
  • 割平面法:可求纯或混合整数线性规划
  • 隐枚举法:求解「0-1」整数规划
    • 过滤隐枚举法;
    • 分枝隐枚举法。
  • 匈牙利法:解决指派问题
  • 蒙特卡洛法:求解各种类型规划

下面一个一个介绍一下:

分枝定界法

假设有一个求 Max 的整数规划问题

分枝定界法程序框图

0-1 型整数规划

变量取值只有0和1,二进制的整数规划。实际问题有如下几个:

  • 投资场所的选定 —— 相互排斥的计划
  • 相互排斥的约束条件
    可以设置一个很大的数,然后在约束条件不等号(需要是)右侧加上,且为约束条件个数。这样就只有的那个约束条件有用。
  • 固定费用的问题

解决方法:

过滤隐枚举法

简单来说就是列举法,但不是穷举,全部列出在 i 很大时几乎是不可能的,所以就只列一部分(分枝定界法其实也是一种隐枚举)

方法如下:

先试探一个显然的可行解,然后比这个解目标函数值弱的,就不需要验证条件即可舍去,减少了计算量。不断改进过滤条件,直至得到最优解。

注意在比较的时候,每一组应先从目标函数值大的开始比

蒙特卡洛法

针对非线性规划,穷举一部分的点,比如用显枚举法需要计算个点,这个计算量不可接受,可以用蒙特卡洛法只举个点,即可一个满意的解(不是最优解)


文章作者: Mond
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC 4.0 许可协议。转载请注明来源 Mond !
  目录