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

在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。 此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(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^分别是原问题和对偶问题的最优解，则

 

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