1 模型概览1.1 学科分属1.2 历史发展线性规划模型及概念构成要素线性规划模型的形式一般形式矩阵形式数学标准型一般形式向标准型的转化线性规划模型的求解方法MATLAB求解（1）基于问题的求解（2）基于求解器的求解图解法、单纯形法与对偶理论可转化为线性规划的形式分段函数绝对值函数3：MaxMin/MinMax函数4：逻辑或5：MaxMax/MinMin函数6：含有0-1变量的乘积形式（逻辑与）7：分式目标函数形式8：Max/Min函数9：混合整数经典应用例题生产决策问题运输问题(产销平衡)《数学模型》4.2 例1指派问题灵敏度分析在国赛中的运用1998年A题参考文献练习
1 模型概览
1.1 学科分属
在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支——数学规划，而线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。
1.2 历史发展
1939 年，苏联数学家康托洛维奇出版《生产组织和计划中的数学方法》一书。
1947 年，美国数学家丹兹格提出了线性规划问题的单纯形求解方法。
1951 年，美国经济学家库普曼斯（J.C.Koopmans,1910–1985）出版《生产与配置的活动分析》一书。
1950∼1956 年，线性规划的对偶理论出现。
1960 年，丹兹格与沃尔夫（P.Wolfe）建立大规模线性规划问题的分解算法。
1975 年，康托洛维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖。
1978 年，苏联数学家哈奇扬（L.G.Khachian）提出求解线性规划问题的多项式时间算法（内点算法），具有重要理论意义。
1984 年，在美国贝尔实验室工作的印度裔数学家卡玛卡（N.Karmarkar）提出可以有效求解实际线性规划问题的多项式时间算法 —Karmarkar 算法。
线性规划模型及概念
构成要素
线性规划的数学模型主要包括三个部分：决策变量、目标函数和约束条件。
- 决策变量：表示问题中的未知数，通常是需要最优化的数量。
- 目标函数：是决策变量的线性函数，表示需要最大化或最小化的经济指标或其他目标。
- 约束条件：是决策变量需要满足的条件，通常以线性不等式或等式的形式出现。
线性规划模型的形式
一般形式
矩阵形式
式中：
- 是目标函数的系数向量，
- 是决策向量，
- 是一个 的矩阵，其中元素 表示第 个约束条件中变量 的系数，
- 是约束条件右侧的常数向量.
数学标准型
一般形式向标准型的转化
1. 将最大化问题转化为最小化问题（如果需要）
可以通过将目标函数的系数取反来转化，但实际上，这一步在求解时可以忽略，因为大多数求解器都接受两种形式。
2. 转换不等式约束为等式约束
对于小于等于（）类型的约束，通过添加非负松弛变量来转换为等式。例如，如果约束是 ，则添加松弛变量使之成为等式 。
对于大于等于（）类型的约束，通过添加非负剩余变量来转换为等式。例如，如果约束是 ，则添加剩余变量 使之成为等式 。
3. 处理自由变量（无符号限制的变量）
如果某个决策变量 是自由变量（即没有非负约束），可以通过引入两个非负变量 和 来替换 ，其中，并且 。
4. 确保所有的变量都是非负的
通过以上步骤，所有的变量（包括原始变量、松弛变量、剩余变量）都应该被约束为非负。
线性规划模型的求解方法
MATLAB求解
（1）找出目标函数中决策变量对应的系数向量c；（2）寻找不等式约束向量A，b；（3）寻找等式约束Aeq,beq;(4)寻找决策变量的上下界lb,ub;（5）[x,fval]=linprog(c,A,b,Aeq,beq,lb,ub)
注意：此方法只能用于求最小值，求max需加负号；不等式约束中只能是<,>号需要加负号变为<进行求解。
（1）基于问题的求解
Matlab基于问题的求解数学规划方法，首先需要用变量和表达式构造优化问题，然后用solve函数求解。具体求解步骤可以通过下面例子看出来，或者在命令窗口运行doc optimproblem,看Matlab的详细帮助。
optimconstr()函数用来创建约束方程组。具体用法查看以下链接
（2）基于求解器的求解
线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于等于号也可以是大于等于号。为了比卖你这种形式多样性带来的不便，Matlab基于求解器的求解方法中规定线性规划的标准形式为
式中：为列向量，其中为价值向量，为资源向量；分别为不等式约束和等式约束对应的矩阵。
Matlab基于求解器的求解线性规划函数调用格式为
其中返回决策变量的取值，fval返回目标函数的最优值，为价值向量，对应线性不等式约束，分别对应决策变量的下界向量和上界向量。
例如线性规划
的Matlab标准型为
图解法、单纯形法与对偶理论
- 图解法：适用于包含两个变量的线性规划问题。通过在二维平面上绘制约束条件和目标函数，找到目标函数在可行解区域内的最优值点。
- 单纯形法：是一种迭代的算法，用于解决包含多个变量的线性规划问题。通过从一个可行解向另一个更好的可行解迭代，直到找到最优解。
- 对偶理论：线性规划问题可以构造一个对偶问题，对偶问题的最优解可以帮助解决原问题，对偶理论在理论研究和算法设计中都有重要应用。
考虑下列一对线性规划模型：
称（P）为原始问题，（D）为它的对偶问题。
不太严谨地说，对偶问题可被看作是原始问题的“行列转置”：
（1） 原始问题中的第 j 列系数与其对偶问题中的第 j 行的系数相同；
（2） 原始目标函数的各个系数行与其对偶问题右侧的各常数列相同；
（3） 原始问题右侧的各常数列与其对偶目标函数的各个系数行相同；
（4） 在这一对问题中，不等式方向和优化方向相反。
其他的我也不太会。。。
可转化为线性规划的形式
具有分段函数形式、绝对值函数形式、最小/大值函数形式、逻辑或形式、含有0-1变量的乘积形式、混合整数形式以及分式目标函数，均可实现线性化。
而线性化的主要手段其实就两点：一是引入0-1变量，二是引入很大的整数M。
分段函数
举例说明：假设你有一个产品，其采购成本不仅仅取决于采购的数量（），还包括一个固定成本（）。那么其采购成本应分为不采购和采购两段
直接处理这样的分段函数在很多优化问题中是困难的，因此我们引入一个辅助的0-1变量y来帮助线性化这个问题。y的作用是用来指示是否进行了采购：
- 当y=0时，表示没有采购，因此x应该等于0。
- 当y=1时，表示进行了采购，此时x可以大于0。
为了将原问题转化为一个线性问题，我们构造了以下线性化模型：
这里，是一个很大的正数，用来确保当时，可以取到大于0的任何值（实际上，应该大于可能达到的最大值）。当时，根据约束，我们有，结合非负的前提，得到。
应用举例绝对值函数
举例：要求线性化如下数学模型
求解方法1：用代替绝对值部分
注意，的数学含义其实就是：和。这个数学思想非常重要，可以解决很多有关绝对值的问题。
求解方法2：用代替
这种方法没有那么直观，一回生，二回熟嘛，以后看到绝对值问题，脑海中有这种思路就好啦。
高中或是高数课上学过如下定理：
则之前的数学模型可以线性化为：
将左边转化为，x转化为。注意，这里的x是向量奥，对于x下标中的每个i都是成立的，可不能以为只有一个约束条件。
3：MaxMin/MinMax函数
以下图上半部分的MaxMin函数为例：基于k 项min CX函数的值（矩阵写法，省略了求和号，不方便打转置符号，望大家理解），再取其中的最大值。
该形式下的线性化方法是：用z 替代min CX函数，这样z 便 ≤ CX，又由目标函数是取最大的z，从而限制住z 不会无限小下去，而只会取满足条件的z。图中下半部分的MinMax函数同理。
此时数学感觉良好的同学可能已经意识到这类似于高数课上的夹逼定理（判断极限是否存在），进一步也可能意识到，如果换为MaxMax和MinMin函数，以上这套思路就行不通了。
实际也确实是这样，线性化MaxMax和MinMin函数较为复杂一些，需要借助下面第四点线性化逻辑或的思维。
4：逻辑或
该部分主要针对约束条件（含有逻辑或）的线性化操作。通常，逻辑或两端的约束存在三种情形。
- 情形1：逻辑或两段均为≤，即：
此时线性化方法为：
引入u 和v 两个0-1变量和大M。分类讨论u 和v 取0或1的四种情形便能理解以上过程。思路非常巧妙，希望大家多悟几遍并消化。
这里虽然只讲了"均为≤"的情形，大家理解了这个逻辑，对于"两边均为≥"和"一边≥一边≤"的情形，线性化思路是类似的。
大家可以试着写一些，我这里总结句口诀：大减小加。含义是：
只要用了大于等于，后面M前面的符号一定是减号；
- 情形2：一端为≤，一端为=，即：
此时线性化方法为：
可见，多添加一个≥的式子即可。那么，情形3如何处理相信大家也猜到了。
- 情形3：两端均为=，即：
此时线性化方法为：
可见，逻辑或是通过新引入的两个0-1变量u和v来控制的.
5：MaxMax/MinMin函数
该部分综合运用了前述技巧。 以MaxMax函数为例：
首先，令z =max CX，但若此时约束条件写成z ≥ CX的形式是不行的，因为这样会让z 取值到无穷大，故一定要写出“z ≤ 某个值”的形式。
这时，就需要引入0-1变量和大M，如上图所示。yk求和≥1的含义是“至少有一个成立”。实际计算时，只会有一个k 让yk=1，其余yk为0。具体原因，也是夹逼定理的思想，大家多多领会。
同理，MinMin函数的线性化过程如下。
注意，这里是加号。yk=0该约束不起作用，只有当yk=1时才会起作用。
6：含有0-1变量的乘积形式（逻辑与）
众所周知，决策变量（连续型）乘以决策变量（连续型）即为二次型，是非线性的。该形式确实无法转化为线性。
但如果将其中一个（或两个）连续型变量改为0-1变量，或者是0-1变量的连乘，此时是可以进行线性化操作的。
设该非线性形式为 y = x1*x2，根据x1、x2两个变量的取值范围不同，会存在以下三种情形：
- 情形1：x1、x2均为0-1变量
分析 y = x1*x2 不同取值下的计算结果，有下表：
x1 | x2 | y |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
总结表中呈现的规律，有：
这里很巧妙地提出变量 y 也为0-1变量，然后通过变量 x 来限制其上下界。
依此类推，大家也可以试试x1、x2、y取其他0-1对应值时的线性化构造方法。
- 情形2：x1为0-1变量，x2取值范围为[0，a]
同样试着画出取值表：
x1 | x2 | y |
0 | [0, a] | 0 |
1 | [0, a] | x2 |
总结表中呈现的规律，有：
第一个和最后一个约束主要为了限定 y 的范围属于[0, a]。第三个约束是最为巧妙的，要限制 y 的范围，必须还要写出“y ≥ 某值”的形式。该思想是需要大家领悟消化的。
- 情形3：x1为0-1变量，x2取值范围为[a，b]
同样试着画出取值表：
总结表中呈现的规律，有：
其中，M 可以是任意正值，因为该约束只有在 x1 = 1 时才起作用，而此时M (1-x1) = 0。
7：分式目标函数形式
举例说明：
观察上式，只有目标函数为分式（非线性）。除法形式在数学上通常是不讨喜的，此时可以考虑转化为乘法形式。即令：
则目标函数转化为：
观察如上形式，又出现新的非线性函数：xz 和 yz 。此时若令xz = u，yz = v，则约束条件也需要做出相应的改变（约束两边同乘 z ）：
可见，分式目标函数的线性化有两个步骤。一是将分母的倒数设置为新的线性参数；二是令非线性的xz 和 yz 等于新的线性参数。
该方法对分式函数具有普适性，巧妙且简单。
8：Max/Min函数
该形式虽较为常见，但其线性化方法却不那么直观。
以 z = max(x, y) 为例。很容易可以写出约束 z ≥ x 和 z ≥ y。但显然这是不够的，因为该约束只约束了 z 的下界，未约束上界。
上界的约束可以转化为逻辑或的表述法，即：x ≥ z 或 y ≥ z 成立。
由线性化方法/技巧（上）的第四部分可知，需引入0-1变量u、v且u + v = 1，和大M 来实现逻辑或的线性化，具体地：
同理，Min函数的线性化方法如下：
消化吸收以上思想后，聪明的你知道 z = max(x, y, 10) 的三个值取大函数如何线性化吗？欢迎私信交流（提示：引入三个0-1变量并使得u + v + w = 1）。
9：混合整数
这里提到的混合整数指的是：某变量是整数或者是连续变量。如下：
此时，只需要用另两个变量 x 和 y 代替 z 即可。
基于此，构造如下的线性化方法：
不知大家发现没有，该方法也是非常巧妙的，没有直接借鉴逻辑或的线性化思路，而是仅通过引入一个0-1变量 u 实现。
当 u = 0 时，前两个约束不起作用，后两个约束起作用，使得 z = y；当 u = 1 时，后两个约束不起作用，前两个约束起作用，使得 z = x。
经典应用例题
生产决策问题
运输问题(产销平衡)
《数学模型》4.2 例1
指派问题
灵敏度分析
灵敏度分析是指对系统因周围条件变化显示出来的敏感程度的分析。
在线性规划问题中，都设定是常数，但在许多实际问题中，这些系数往往是估计值或预测值，经常有少许的变动。
因此提出以下两个问题：
（1）如果参数q，b，c;中的一个或者几个发生了变化，现行最优方案会有什么变化?
（2）将这些参数的变化限制在什么范围内，原最优解仍是最优的?
当然，有一套关于"优化后分析"的理论方法，可以进行灵敏度分析。具体参见有关的运筹学教科书。
但在实际应用中，给定参变量一个步长使其重复求解线性规划问题，以观察最优解的变化情况，不失为一种可用的数值方法，特别是使用计算机求解时。
对于数学规划模型，一定要做灵敏度分析。
在国赛中的运用
1998年A题
市场上有n种资产（如股票、债券等）供投资者选择’某公司有数额为M的一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这n种资产进行了评估，估算出在这一时期内购买资产的平均收益率为，并预测出购买的风险损失率为。考虑到投资越分
散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的S_i中最大的一个风险来度量。
参考文献
[1] 司守奎，孙玺菁.数学建模算法与应用（第三版）
[2] 知乎：干货 | 令人拍案叫绝的线性化方法/技巧 https://zhuanlan.zhihu.com/p/552076713
[3] SJTU MCM 资料库
[4] 司守奎，数学建模算法与程序