线性规划
引言
线性规划问题是目标函数和约束条件都是线性的最优化问题.
Mathematica 收集了大量的算法来解决实变量的线性最优化问题，这些算法都可通过 LinearProgramming、FindMinimum、FindMaximum、NMinimize、NMaximize、Minimize 和 Maximize 调用执行. LinearProgramming 对各种线性规划算法提供直接的支持，并提供了最灵活的方式来指定使用哪个算法，而且能够最有效地解决大规模问题. FindMinimum、FindMaximum、NMinimize、NMaximize、Minimize 和 Maximize 对求解等式和不等式形式的线性规划问题更为方便.
| Out[1]= |  |
| Out[2]= |  |
| Out[3]= |  |
LinearProgramming 函数
LinearProgramming 是线性规划问题的主要函数，它能够最灵活地指定应该使用哪一个函数，并且对于解决大规模问题是最有效的.
我们可以使用下面的选项.
LinearProgramming 的选项.
Method 选项用来指定求解线性规划问题所使用的算法. 可能值包括 Automatic、
、
和 
. 默认值是 Automatic，可以根据问题的大小和精度需要从其他方法中自动选择合适的算法.
Tolerance 选项可以用来指定收敛容差的大小.
例子
内点法和单纯形法和/或修正单纯形法的区别
单纯形法和修正单纯形法通过以下方法解决线性规划问题: 沿着约束条件所定义的多面体边缘移动，从一个顶点到达另一个顶点，以使得目标函数值逐渐减小，直至达到最小值. Mathematica 通过稠密线性代数实现单纯形法和修正单纯形法. 这种实现方法的独特之处在于它有可能解决精确/扩展精度问题. 因此，这些方法对于需要非机器精度结果的小规模问题或者当我们期待得到一个在顶点上的解时更为适用.
笼统地说，线性规划的内点算法是从约束条件定义的多面体的内部依次迭代的. 它们可以非常快地接近问题的解，但是与单纯形法/修正单纯形法不同的是，他们不能精确地找到解. Mathematica 利用机器精度稀疏线性代数执行内点法. 因此，对于大规模机器精度线性规划问题，内点法更为有效，更为适用.
这里求解一个具有多个解的线性规划问题 (任何在
和
之间的线段上的点是一个解)；内点算法给我们提供了一个位于解集中点的一个解.
| Out[6]= |  |
利用
或者
，则给出一个在解集边界上的解.
| Out[7]= |  |
这里表明对于下面的具有200个变量的随机稀疏线性规划问题，内点法要快的多，并且产生差不多相同的最优值.
| Out[44]= |  |
| Out[45]= |  |
| Out[46]= |  |
寻找对偶变量
对于一般线性规划问题
其相应的对偶问题是
对于一些应用问题来说，同事知道这两个问题的解是很有用的.
下列表格给出原始问题和对偶问题的解之间的关系.
| |
| 可行 | 可行 |
| 无界 | 不可行或者无界 |
| 不可行 | 无界或者不可行 |
当这两个问题都是可行的时候，(P) 和 (D) 的最优值是相同的，并且下面的补充条件对于原始问题的解 
和对偶问题的解 
是成立的.
返回一个列表 
.
这里求解原始问题
以及对偶问题
| Out[14]= |  |
| Out[15]= |  |
| Out[16]= |  |
约束条件的对偶是
，这意味着约束条件右边每增加一个单位的数量，目标函数就增加2个单位的数量. 这可以通过对约束条件右边进行 0.001 的微调得到确认:
| Out[17]= |  |
| Out[18]= |  |
内点法中不可行性和无界问题的处理
原始-对偶内点法是为可行问题而设计的；对于不可行/无界问题，它是发散的，而在目前的执行过程中，我们很难查明发散是由于不可行性，还是由于无界性.
一种启发式的方法捕捉到了不可行/无界问题，并且发布一个适当的信息.
| Out[19]= |  |
有时候，该启发式的方法不能肯定地告诉我们一个问题是否是不可行的或者无界的.
| Out[20]= |  |
使用提示中所建议的
单纯形法表明，该问题是无界的.
| Out[21]= |  |
InteriorPoint 的方法选项
是 
的一个方法选项，它决定对稠密列是否要分别处理. 稠密列指的是具有许多非零元素的约束矩阵的列. 在默认情况下，该方法选项的值为 Automatic，此时分别处理稠密列是分别处理的.
| Out[98]= |  |
| Out[99]= |  |
大数据集的导入和大规模问题的解决
一个用于记录线性规划问题的常用格式是数学规划系统 (MPS) 格式. 这是一个包含若干章节的文本格式.
以方程形式导入 MPS 格式文件
Mathematica 可以导入 MPS 格式的文件. 默认情况下，MPS 数据的 Import 返回一个方程形式的线性规划问题，这样就可以通过使用 Minimize 或者 NMinimize 求解.
这里求解
MPS 文件
指定的线性规划问题.
| Out[25]= |  |
| Out[26]= |  |
大规模问题：以矩阵和向量形式导入
对于大规模问题，导入 MPS 数据文件并用矩阵和向量表示线性规划问题，然后用LinearProgramming 求解更有效.
这里表明对于
MPS 格式的数据，可以导入下面三个元素.
| Out[101]= |  |
| Out[104]= |  |
使用
可以用来单独地获得稀疏矩阵.
| Out[105]= |  |
自由格式的MPS文件
标准格式的 MPS 文件采用一个固定的格式，其中每个域占有一个严格固定的字符位置. 然而，一些建模系统以自由格式输出 MPS 文件，其中每个域自由地放置. 对于这种文件，对 Import 可以选用选项"FreeFormat"->True.
这里获得一个临时文件名，并且把字符串导出到该文件中.
这里采用
"FreeFormat"->True 选项导入该文件.
| Out[126]= |  |
线性规划测试问题
通过 ExampleData 函数，所有 NetLib 线性规划测试问题都可以被访问.
| Out[12]= |  |
这里导入
问题并且求解该问题.
| Out[8]= |  |
| Out[9]= |  |
这里显示了对
问题可以导入的其他属性.
| Out[10]= |  |
这里以方程形式导入
.
| Out[11]= |  |
线性规划问题的应用实例
L1-范式极小化
一个 
极小化问题
有可能通过把系统转化成一个线性规划问题
来求解.
这里定义了一个求解
极小化问题的函数.
| Out[38]= |  |
而这里却找到了
极小化问题的解.
| Out[39]= |  |
| Out[40]= |  |
| Out[41]= |  |
| Out[42]= |  |
一个最优钎桩的设计
这个例子是从 [2] 中引入的. 目的是要设计一个钎桩，使用尽可能少的材料来支撑负载.
这个问题可以通过离散化并用节点和链路对其进行模拟来建模. 建模过程通过下面的图标显示. 在此一个具有7×10个节点的网格被产生. 每个节点通过链路与所有其他曼哈顿距离小于或等于三的节点链接. 三个红色节点假设固定在墙上，而在所有其他节点上，压力和张力必须平衡.
每个链路代表一个具有一定粗细的刚性棒，其重量和它上面的力以及它的长度成正比. 我们的目的是最小化使用的材料总量，即:
因此从数学理论上看，这是一个线性约束极小化问题，其目标函数是线性函数绝对值的和.
目标函数中绝对值 
可以通过把 
分成压力和张力的组合来代替，其中每个项都是非负的. 因此假设 
是链路的集合，
是节点的集合，
是节点 
和 
之间的链路长度，而 
和 
是链路上的压力和张力；那么上述模型可以被转化为一个线性规划问题.
下面我们建立一个模型，求解这个模型，并且把结果画成图形；这是以一个AMPL模型
[2] 为基础的.
这里我们通过在水平和垂直方向上各设置 30个节点来求解该问题.
| Out[6]= |  |
请注意，如果钎桩不是固定在墙上，而是固定在空间的某些点，你会发现求得的结果和树叶的形状很相似. 树叶的结构可能就是在进化的过程中达到最优化.
| Out[11]= |  |
线性规划的算法
单纯形法和修正单纯形法
单纯形法和修正单纯形法通过以下方法求解线性规划问题：先在约束条件所定义的多面体的一个顶点构造一个可行解，然后沿着该多面体边，从一个顶点移动到另一个顶点，以使得我们的目标函数值逐渐减小，直至达到最小值.
虽然单纯形法和修正单纯形法的稀疏实现方法在实践上很有效，并且能够保证找到全局最优解，该算法有一个很差的最坏情况下的行为表现：即有可能会建立这样一个线性规划模型，使得单纯形法和修正单纯形法的步骤数目与问题大小呈指数关系.
Mathematica 通过稠密线性代数实现单纯形法和修正单纯形法. 这种实现方法的独特之处在于它有可能可以解决精确/扩展精度问题. 因此，这些方法对于需要非机器精度结果的小规模问题更为适用.
这里我们建立一个具有20个约束条件和200个变量的随机线性规划问题.
下面求解该问题. 通常情况下，如果线性规划问题的变量数目远多于约束数目，修正单纯形法的速度比较快. 反过来，如果约束条件的数目比变量数目多的话，则单纯形法比较快.
如果我们只希望得到机器精度的结果，那么问题应该转化成机器精度数字，而且应该使用内点法.
内点算法
虽然单纯形法和修正单纯形法平均上看可以非常有效，可是它们最差情况下的行为却很糟糕. 我们有可能会建立一个线性规划模型，其中单纯形法和修正单纯形法的步骤数目随问题大小呈指数增长. 而内点算法收敛所需的步骤数目已经被证明随问题大小呈多项式变化.
此外，Mathematica 的单纯形法和修正单纯形法的实现利用稠密线性代数，而它的内点法的实现利用机器精度的稀疏线性代数. 因此对于大规模，机器精度线性规划问题，其内点法更为有效并且更应该使用.
内点法表述
考虑下面的标准化线性规划问题
其中 
、
、
. 这个问题可以通过使用障碍函数方法来处理正值约束来求解.
上述问题的一阶必要条件得出
设 
表示由向量 
构成的对角矩阵，并且 
.
这是一个由 
个有约束条件的线性/非线性方程组成的集合. 它可以使用牛顿法
及
得到求解.
求解这个线性系统的一个方法是使用高斯消去法把矩阵简化成块三角矩阵的形式.
为了求解这个块三角矩阵，我们可以求解所谓的正规系统，该正规系统中的矩阵
这个矩阵是正定的，但是当接近我们要求的解时就变得非常病态了. 因此我们使用数值技术来稳定求解的过程，并且通常情况下我们只能期待内点法求解该问题到一个大约为 
的容差，容差的概念在 "收敛容差" 中有解释. Mathematica 使用Mehrotra的预估校正方案 [1].
收敛容差
一般线性规划问题可以首先被转化成标准形式
其相应的对偶问题是
内点算法的收敛标准是
在默认情况下，容差设置为 
.
参考文献
[1] Vanderbei, R. Linear Programming: Foundations and Extensions. Springer-Verlag, 2001.
[2] Mehrotra, S. "On the Implementation of a Primal-Dual Interior Point Method." SIAM Journal on Optimization 2 (1992): 575-601.
