【数学建模】线性规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数学建模】线性规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、线性规划

1.1线性规划的实例与定义

数学建模线性规划,数学建模,matlab,算法,矩阵

1.2线性规划的Matlab标准形式

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

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

数学建模线性规划,数学建模,matlab,算法,矩阵

1.3线性规划问题的解的概念

一般线性规划问题的标准型为
数学建模线性规划,数学建模,matlab,算法,矩阵
可行解：
满足约束条件（4）的解x=（x1,x2,…,xn），称为线性规划问题的可行解，使目标函数（3）达到最大值的可行解叫最优解

可行域：
所有可行解构成的集合称为问题的可行域，记为R。

1.4线性规划的图解法

数学建模线性规划,数学建模,matlab,算法,矩阵

从上面的图解过程可以看出以下断言：
①可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时，它必是若干个半平面的交集（除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。
②在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）
③若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域 R 的“顶点”。

1.5求解线性规划的Matlab解法

数学建模线性规划,数学建模,matlab,算法,矩阵

基本函数形式为linprog（c,A,b），它的返回值是向量x的值。还有其他的一些函数调用形式（在Matlab指令窗口运行help linprog可以看到所有的函数调用形式），如：
[x,fval]=linprog（c,A,b,Aeq,beq,LB,UB,X0,OPTIONS）
这里fval返回目标函数的值，LB和UB分别是变量x的下界和上界，x0是x的初始值，OPTIONS是控制参数。
数学建模线性规划,数学建模,matlab,算法,矩阵

数学建模线性规划,数学建模,matlab,算法,矩阵

1.6可以转化为线性规划的问题

数学建模线性规划,数学建模,matlab,算法,矩阵

二、运输问题（产销平衡）

数学建模线性规划,数学建模,matlab,算法,矩阵

三、指派问题

3.1指派问题的数学模型

数学建模线性规划,数学建模,matlab,算法,矩阵

3.2求解指派问题的匈牙利算法

数学建模线性规划,数学建模,matlab,算法,矩阵

四、对偶理论与灵敏度分析

4.1原始问题和对偶问题

考虑下列一对线性规划模型：

数学建模线性规划,数学建模,matlab,算法,矩阵

4.2 对偶问题的基本性质

1、对称性：对偶问题的对偶是原问题
2、弱对偶性：若x是原问题的可行解，y是的对偶问题的可行解。则存在
3、无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。
4、可行解是最优解时的性质：设x是原问题的可行解，y是对偶问题的可行解，当,x、y是最优解。
5、对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相同。
6、互补松弛性：若x、y分别是原问题和对偶问题的最优解，则