数学建模常见模型学习笔记——线性规划

在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。 此类问题构成了运筹学的一个重要分支—数学规划,而线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。

线性规划的 Matlab 标准形式

线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便,Matlab 中规定线性规划的标准形式为

数学建模常见模型学习笔记 | 第①期——线性规划

其中 c 和 x 为 n 维列向量, A 、 Aeq 为适当维数的矩阵, b 、 beq 为适当维数的列向量。

线性规划模型的特点

优点

有统一算法,任何线性规划问题都能求解,解决多变量最优决策的方法。

缺点

对于数据的准确性要求高,只能对线性的问题进行规划约束,而且计算量大,有由线性规划演变的非线性规划法等等后续的方法弥补,但是计算量增加许多。

例题实战

 线性规划常用于运输问题(产销平衡)、指派问题(匈牙利算法)、对偶理论与灵敏度分析、投资的收益和风险等。接下来让我们通过几个具体实例来体会“线性规划”在建模方面的实际应用。

运输问题

例:

某商品有m个产地,n个销地,各产地的产量分别为a1,…,am,各销地的需求量分别为b1,…,bm。若该商品由i产地运到j销地的单位运价为c(ij),问应该如何调运才能使总运费最省?

数学建模常见模型学习笔记 | 第①期——线性规划

01、产销平衡

存在产销平衡问题(当有也有生产与销售量不平衡的情况),实际上不平衡的运输问题可以转换成平衡型的问题。通过虚设一个产地或销售地并令运输成本为0。

02、

当产量等于销售量的时候有可行解且必有最优解。并且若产量与销售量均为整数时,必存在决策变量均是整数的解。

03、表上作业法

其约束条件的系数矩阵相当特殊,可用比较简单的计算方法,习惯上称为表上作业法(由康托洛维奇和希奇柯克两人独立地提出,简称康—希表上作业法)。

指派问题

例:

拟分配n人去干n项工作,每人干且仅干一项工作,若分配第i人去干第j项工作,需花费C(ij)单位时间,问应如何分配工作才能使工人花费的总时间最少?

数学建模常见模型学习笔记 | 第①期——线性规划数学建模常见模型学习笔记 | 第①期——线性规划

01、矩阵表示法

指派问题的可行解可以用一个矩阵表示,其每行每列均有且只有一个元素为1,其余元素均为 0;问题中的变量只能取 0 或1,从而是一个0-1 规划问题。一般的0-1 规划问题求解极为困难。但指派问题并不难解,其约束方程组的系数矩阵十分特殊(被称为全单位模矩阵,其各阶非零子式均为±1),其非负可行解的分量只能取 0或 1,故约束xijxij = 0或1可改写为xijxij≥ 0而不改变其解。此时,指派问题被转化为一个特殊的运输问题

02、费药类

由于指派问题的特殊性,又存在着由匈牙利数学家 Konig 提出的更为简便的解法—匈牙利算法。算法主要依据:如果系数矩阵 C=(cij)C=(cij)一行(或一列)中每一元素都加上或减去同一个数,得到一个新矩阵BB,则以C或B为系数矩阵的指派问题具有相同的最优指派。

对偶理论与灵敏度分析

对偶问题的基本性质:

01、对称性

对偶问题的对偶是原问题。

02、无界性

若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。

03、对偶定理

若原问题有最优解,那么对偶问题也有最优解;且目标函数值相同。

03、互补松弛性

若xˆ,yˆx^,y^分别是原问题和对偶问题的最优解,则

数学建模常见模型学习笔记 | 第①期——线性规划

 

本期的模型学习笔记之线性规划到此告一段落啦。如果你对该算法有兴趣,可以自己动手查阅相关资料,进行更加深入的了解~

【竞赛报名/项目咨询请加微信:mollywei007】

微信扫一扫,分享到朋友圈

数学建模常见模型学习笔记——线性规划
上一篇

到底哪些因素阻碍了学生取得托福写作高分

下一篇

EPQ课题选择四大误区你中招了吗?附满分EPQ标准解析!

你也可能喜欢

  • 暂无相关文章!

关注热点

返回顶部