数学建模
模型知识点
2 优化模型-线性规划-理论
Wang Haihua
2022/04/21
🚅 🚋😜 🚑 🚔
线性规划简介¶
在数学中，线性规划是一种具有一定约束条件的优化操作的方法。线性规划的主要目标是最大化或最小化数值。 它由线性函数组成，这些函数以线性方程的形式或不等式的形式受到约束。线性规划被认为是一种重要的技术，用来寻找最优的资源利用。
术语“线性规划”由两个词组成:线性和规划。线性”一词定义了多个变量之间的一阶关系。“编程”一词定义了从各种备选方案中选择最佳解决方案的过程
线性规划广泛应用于数学和其他一些领域，如经济、商业、电信和制造领域。在这篇文章中，让我们讨论线性规划的定义，它的组成部分，以及解决线性规划问题的不同方法。
线性规划的组成部分¶
LP的基本组成如下:
决策变量 决策变量是指问题中可以改变的量，例如生产多少货物，选择哪条路径等；线性规划的目标就是找到最优的决策变量。在线性规划中决策变量包括实数变量，整数变量，0-1变量等。
目标函数 目标函数就是把问题中的决策目标量化，一般分为最大化目标函数$\max$和最小化目标函数$\min$ 在线性规划中，目标函数为一个包含决策变量的线性函数，例如$\max x_1 + x_2$
约束条件 约束条件是指问题中各种时间，空间，人力，物力等限制。 在线性规划中约束条件一般表示为一组包含决策变量的不等式，例如$x_1 + 2x_2 \leq 10 $或者$4x_1 + 3x_2 \leq 24$。此外，决策变量的取值范围称为符号约束，例如$x_1 \geq 0, x_2 \geq 0$。
线性规划的特点¶
线性规划问题(LPP)是一个关于寻找给定线性函数的最优值的问题。最优值可以是最大值也可以是最小值。这里，给定的线性函数被认为是目标函数。目标函数可以包含多个变量，这些变量受条件约束，并且它必须满足一组称为线性约束的线性不等式。
线性规划问题可用于求解以下几种情况的最优解，如制造问题、饮食问题、运输问题、分配问题等。
以下是线性规划问题的五个特点:
- 约束—关于资源的限制应以数学形式表示。
- 目标函数-在一个问题中，目标函数应该以定量的方式指定。
- 线性—函数中两个或多个变量之间的关系必须是线性的。这意味着变量的次数是1。
- 有限-应该有有限和无限的输入和输出数字。如果函数有无限个因子，则最优解是不可行的。
- 非负性—变量值应为正或为零。它不应该是负值。
- 决策变量-决策变量将决定输出。它给出了问题的最终解决方案。对于任何问题，第一步都是识别决策变量。
一个线性规划问题的例子¶
假设一家巧克力生产公司只生产两种类型的巧克力——A和B。这两种巧克力只需要牛奶和巧克力。制造A和B的每一个单位，需要以下数量:
- 每单位A需要1单位牛奶和3单位巧克力
- 每单位B需要1单位牛奶和2单位巧克力
公司厨房里有5个单位的牛奶和12个单位的巧克力。每卖出一笔，公司就赚一笔
- 每单位A卖出6卢比
- 每单位B卖出5卢比
现在，该公司希望实现利润最大化。它应该分别生产多少单位的A和B ?
设A生产的总单位数为$X$
设B生产的总单位数为$Y$
总利润用$Z$表示
公司的总利润是A和B生产的总单位数乘以单位利润分别为6卢比和5卢比。
总利润为
$$Z = 6X+5Y$$
这意味着我们要使$Z$最大化。
公司将尽可能多地生产A和B以使利润最大化。但是Milk和Choco的资源是有限的。 根据上上述信息，每单位A和B需要1单位牛奶。可供应的牛奶总量是5个单位。数学形式为 $$X + Y \le 5$$ 每单位的A和B需要3单位和2单位的Choco。可供使用的Choco总数量为12个单位。数学形式为： $$3 x + 2 y \le 12$$ 而且，A和B的单位只能是整数。
我们还有有两个约束条件 $$X≥0,Y≥0$$ 为了使公司获得最大的利润，上述的不等式必须得到满足。 这样我们就将一个现实世界的问题转化为了一个数学模型。
线性规划模型的标准形式¶
对于一个线性规划模型：
$$ \begin{aligned} &\min \quad z= x_{1}+ x_{2}\\ &\text { s.t. }\left\{\begin{array}{l} {x_{1}+2 x_{2} \leq 10} \\ {4 x_{1}+3 x_{2} \leq 24} \\ { x_{1}, x_{2} \geq 0} \end{array}\right. \end{aligned} $$其中$s.t.$为subject to的缩写。上述模型可以写成如下的矩阵形式：
其中
$$ c = [1,1]^T $$$$ x= [x_1,x_2]^T $$$$ A = \left[ \begin{matrix} 1 & 2\\ 4&3 \end{matrix}\right] $$$$ b = \left[\begin{matrix}10\\24 \end{matrix} \right] $$对于有 $n$ 个决策变量，$m$ 个约束的线性规划模型, $c,x$ 为 $n$ 维列向量，$b$ 为 $m$ 维列向量，$A$ 为 $m \times n$ 维矩阵。
线性规划的目标函数可能是最大化，也可能是最小化，约束条件的符号可能是小于等于，也可能是大于等于。甚至还有等于。因此为了编程方便，一般统一为最小化目标函数，小于等于约束。
最大化目标函数可以添加负号变为最小化约束：
$$ \max z = x_1 + x_2 \implies \min -z = -x_1 - x_2 $$大于等于约束可以两边乘以 $-1$ 变为小于等于约束：
$$ x_1 + 2x_2 \geq 10 \implies -x_1 - 2x_2 \leq -10 $$等于约束可以变为一个大于等于约束和一个小于等于约束，但在编程中一般支持直接写等式约束,可以不进行转换：
$$ x_1 + 2x_2 = 10 \implies x_1 + 2x_2 \leq 10, x_1 + 2x_2 \geq 10 $$综上，考虑了等式约束后的线性规划的标准形式可以写为：
线性规划的标准形式
$$ \begin{aligned} &\min c^{T} x\\ &\text { s.t. }\left\{\begin{array}{l} {A x \leq b} \\ { Aeq \cdot x=b e q} \\ {l b \leq x \leq u b} \end{array}\right. \end{aligned} $$线性规划问题的解法¶
线性规划问题可以用不同的方法求解，如图解法、单纯形法，或用R、开解器等工具求解。在这里，我们将详细讨论两个最重要的技术，即单纯形法和图解法。
图解法¶
对于较为简单且只有两个决策变量的线性规划问题可以使用图解法。
例如考虑如下线性规划模型：
$$ \begin{aligned} &z= x_{1}+ x_{2}\\ &\text { s.t. }\left\{\begin{array}{l} {x_{1}+2 x_{2} \leq 10} \\ {4 x_{1}+3 x_{2} \leq 24} \\ {x_{1}, x_{2} \geq 0} \end{array}\right. \end{aligned} $$以决策变量 $x_1$ 为 $x$ 轴，决策变量 $x_2$ 为 $y$ 轴，可以将约束条件表示为如下所示的多边形，其中多边形的每一个边界即为一个约束条件，目标函数则为一条直线，优化目标为使该条直线在 $y$ 轴上的截距最大。
从图中可以看出，当目标函数经过多边形的顶点A(即表示两个约束条件的直线交点)时， $y$ 轴截距取得最大值。 即：当$x_1 = 3.6, x_2 = 3.2$ 时，目标函数取得最大值为 $z = x_1 + x_2 = 3.6 +3.2 = 6.8$
单纯形法¶
对于决策变量比较多的线性规划模型，图解法不再适用。 单纯形法是1947 年G. B. Dantzig提出的一种十分有效的求解方法，极大地推广了线性规划的应用， 直到今日也在一些线性规划的求解器中使用。
从图解法的例子中，我们可以看出，约束条件所围成的区域为一个凸多边形，当决策变量多于两个时，约束条件围城的区域为一个凸多面体，称之为可行域。其中每一个面（称之为超平面）即代表一个约束条件。
可以证明：线性规划的最优解一定在可行域的边界上
单纯形法的思路就是在可行域的一个顶点处找到一个初始可行解，判断该解是不是最优，若不是，则迭代到下一个顶点处进行重复判断。因为最优解的搜索范围从整个可行域缩小到了可行域的有限个顶点，算法的效率得到了极大的提升。
此外，求解线性规划的方法还有椭球法、卡玛卡算法、内点法等。 其中内点法因为求解效率更高，在决策变量多，约束多的情况下能取得更好的效果，目前主流线性规划求解器都是使用的内点法。