快点击上方 蓝字 关注我们吧!! 数学建模与MATLAB–整数规划
本文简单介绍了整数规划的问题和一些常见的解法,对于此类问题大家可以与线性规划(/md/?articleId=) 相互对比。
规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。 注意: 目前所流行的求解整数规划的方法,往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
用以解决生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题:
求解范围:纯或混合整数线性规划思路:
对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系统搜索,这就是分枝与定界内容。
通常,把全部可行解空间反复地分割为越来越小的子集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于最小值问题),这称为定界。在每次分枝后,凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,这样,许多子集可不予考虑,这称剪枝。这就是分枝定界法的主要思路。
求解范围:纯或混合整数线性规划
先不考虑变量的取整约束,求解相应的线性规划,然后不断增加线性约束条件(割平面),将原可行域割掉不含整数可行解的一部分,最终得到一个具有整数坐标顶点的可行域,而该顶点恰好是原整数规划问题的最优解
求解范围:“0-1”整数规划
它的基本思路时从所有变量等于零出发,依次指定一些变量为1,直至得到一个可行解,并将它作为最好的可行解。
此后,依次检查变量等于0或1的某些组合,以便使最好的可行解不断加以改进,最终获得最优解。隐枚举法不同于穷举法,它不需要将所有可行的变量一一列举。它通过分析、判断派出了许多变量组合作为最优解的可能性。也就是说,它们被隐含枚举,故此得名。
求解范围:“0-1”规划特殊情形(指派问题)
匈牙利解法是求解指派问题的一种新颖而又简便的解法,它是美国数学家库恩(Kuhn)于1955年提出的.库恩引用了匈牙利数学家康尼格(Konig)一个关于矩阵中0元素的定理:系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最小直线数。
指派问题的最优解有这样一个性质,若从系数矩阵的一行(列)各元素中分别减去该行(列)的最小元素,得到新矩阵,那么以新矩阵为系数矩阵求得的最优解和用原矩阵求得的最优解相同.利用这个性质,可使原系数矩阵变换为含有很多0元素的新矩阵,而最优解保持不变,这就是匈牙利法的基础。
求解范围:各种类型规划
蒙特卡罗是一种随机模拟的方法,对于枚举法解决困难的大型问题,使用蒙特卡罗模拟便可以使用较少的计算量得到较为准确的结果。
1、0-1整数规划(指派类问题)
有n项不同的任务,需要n个人分别完成其中的1项,每个人完成任务的时间不一样。于是就有一个问题,如何分配任务使得花费时间最少。
上表为指派矩阵,表中数值代表不同人员做不同任务需要的时间对于此问题我们可以使用linprog进行求解,MATLAB代码如下:
欢迎大家加入我们的MATLAB学习交流群:
END 扫码关注我们 更多精彩等待你发现 出品: Asoul水云天课堂工作室
fun 单独的函数文件里定义的目标函数
x0 决策变量的初始值,不知道的话随便写个数
A,b 线性约束条件的不等式变量系数矩阵和常数项矩阵
Aeq,beq 线性约束条件的等式 变量系数矩阵和常数项矩阵
nonlcon 非线性约束,包括等式和不等式
1.飞机位置,速度,进入区域后判定是否碰撞,飞机方向角的调整幅度尽量小
2.电影院的视角,仰角影响观影体验,什么样的位置观影最佳
3.涉及三角函数的,为非线性规划
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。