大家好，欢迎来到IT知识分享网。

什么是线性规划：

线性规划就是特殊的有约束优化问题，目的是通过一组线性等式或者不等式下得可行集合点，来寻找一个目标函数的极值；

通常来说，极值可以是极大极小，但是一般采用极小，看到相关的案例，求极大值直接前面加负号变为极小值即可；

线性规划的基本问题形式：

线性规划问题可以采用最基本的数学符号进行描述：

minimize c^Tx

subject to Ax=b

x>=0;

对于上述可以这样理解，对于某个参数向量x，所满足的可行域条件为Ax=b，也成为约束方程，可行域内点集由该方程组确定，其中值得注意的是可行域条件不一定为等式，只需要线性即可；

c^Tx为目标等式，两个都为向量，所以值为一个单值，旨在找到一个极小值，使得满足minimize的要求；

因此，对于任何的问题，都可以转为标准的问题形式进行求解；

其中，比较有意思的是约束条件实际定义了求解的维数，也就是如何直观的通过对x的选择，使得c^Tx最大；

如果从空间思想来考虑，就可以分为简单二维和三位情况下的最优化；

如果是简单的二维情况：

c^Tx相当于ax1+bx2，相当于二维平面上的一条直线，其中要求的是如何选定x1,x2的值，使得k=ax1+bx2存在最大最小值（因为向量c相当于已经确定了斜率）；

而约束条件也为围成的一系列可行域，在二维平面内选择点，使得k=ax1+bx2最大，也就是和x2轴交点值最大；

如下图所示，书上也给了一个很好的例子：

而对于多维情况，则需要涉及凸多面体问题：

c^Tx中的c的个数已经限定了多维空间下n的目标函数；

约束条件Ax=b，其中A为m*n维数向量，定义了m个超平面所围成的一个凸多面体，并且假设该多面体非空有界；

书上讨论了很多种情况，例如多面体超平面的维数问题；

但是这里还是说一下常规的转换求法；

根据c^Tx得到一个超平面c^Tx=0；

找到一个支撑超平面c^Tx=β，使得整个胞体M在半平面，且M和超平面交集为M’；

所以无论任何属于负半区的点y，都会有c^Ty<β；

而任何属于M’的点y，都有c^Ty=β；

所以可得到支撑超平面的点是极值点，同样如果支撑超平面为单点情况下，仍然适用；

线性规划问题的标准型：

对于标准型，和之前谈到的基本形式类似，实对所有高维线性规划下的问题做一个基本的形式定义；

minimize c^Tx

subject to Ax=b

x>=0

值得注意的是Ax=b的条件，所有大于等于的线性条件都应该转为等于进行讨论，个人认为是使得所构成的解集范围是多胞体而非多个超平面围成的范围；

而对于非标准形式，往往有Ax>=b或者Ax<=b，所以通过变换来变成一般的标准形式； 

 其中注意下不同的说辞，Ax>=b,Ax<=b，无非就是加减y而已，保持y>=0即可，两种情况称之为剩余变量y和松弛变量y，名字记不记住感觉无伤大雅；

基本解：

当给出线性规划的基本形式之后，就可以对基本解进行构造；

总的来说，解和传统的线性齐次、非齐次方程组不同，主要关注两个类型：

1.基本解；

2.可行解；

两者其实有交集，交集的形式为基本可行解；

基本解求法：

可行解求法：

可行解本质就是满足标准形式的解，也就是满足Ax=b,且x>=0的解，两个条件缺一不可；

而基本可行解就是既为基本解满足x>=0的解；

对于书上，有给出的相关例题，说明怎么求解可行解和基本解：

基本解的性质：

最优可行解：能够使得目标函数c^Tx取最小值的解；

最优基本可行解：该最有可行解为基本解；

其中对于线性规划来说，有挺重要的一条性质：

1.如果存在可行解，则一定存在基本可行解；

2.如果存在最优可行解，则必定存在最优基本可行解；

基本可行解的实际意义：

如果对于一个凸集，求目标函数极值，则必定取值点必定是凸集上的极点，对应的就是可行基本解；

所以最后只需要寻找可行基本解中哪一个可以使得目标函数c^Tx最大(最小)，就可以得到最优基本可行解；

【注意】关于为什么要找极点：

根据前面二维推广至多维的推导，都是根据支撑超平面来进行极值寻找，所以找极值点也就相当于找使得距离原点超平面最远的支撑超平面；

所以有定理：

如若存在一个可行解组成的凸集，集合中的所有n维向量x满足Ax=b，x>=0，其中A维m*n维向量，则x是凸集中的极值点当且仅当x是Ax=b，x>=0的基本可行解；

证明过程如下所示：