单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。

例2.6 试以例2.1来讨论如何用单纯形法求解。

解：约束条件(2-12)式的系数矩阵为

这个基可行解的经济含义：工厂没有安排生产产品Ⅰ和Ⅱ，资源都没有被利用，所以利润为z=0。

从(2-14)可以看到：非基变量x1,x2的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加。
所以只要在 目标函数 (2-14)的表达式中 还存在有正系数的非基变量 ，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。

为了确定初始基可行解，要首先找出初始可行基，其方法如下。
1）直接观察
2）加松弛变量
3）加非负的人工变量

例7 试用上述方法计算例6的两个基变换。

为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。
将(2-22)式与目标函数组成n+1个变量，m+1个方程的方程组。
线性规划的方程组

为了便于迭代运算，可将上述方程组写成增广矩阵的形式

总结一下计算单纯形表的步骤
1.写出线性规划标准形，找到初始基可行解。
2.列出单纯形表，计算检验数σ，和θ。按照σ最大原则找到换入变量，按照θ最小原则找到换出变量。这里要求在σ＞0中选择，θ在aj＞0中选择。 换入变量和换出变量的交点是主元素。

3 初等行变换，把主元素所在列化成只有一个1，其他全为0.

4 基变量位置上换入变量写上。
5迭代，直到所有的检验数σ都≤0.

人工变量法是解决：线性规划的 约束条件中没有可以作为初始基的单位矩阵



大M只需要添加在缺少单位变量的那个约束条件上。比如下面的第2、3个约束才需要添加，而第1个约束不需要添加，因为它已经有了x4可以提供单位矩阵。

求最大值问题，目标函数中的M的系数需要是负号；求最小值问题，目标函数中M的系数需要是正号，比如下面这道题目。

解答
设 Xk表示Xk名司机和乘务人员第k班次开始上班，接连工作8小时，也就是说，第k班次上班的工作人员可以在第k+1段时间工作，因此有如下的解答。

解答
常规的单纯形法

作业：使用大M法求解线性规划问题

用向量单纯形法求解线性规划问题
只要：使用非基变量表示基变量，然后确定入基变量，出基变量；令非基变量等于0，得到基解和目标函数值。查看目标函数中：非基变量的系数是否为负， 非基变量系数如果有正的，说明还不是最优解 ，一直入基出基迭代。

对称形式（约束条件没有等号）




解答

非对称形式

原问题中目标函数的价值向量C，在对偶问题中是约束条件的右端常数项；
原问题中约束条件的右端常数项b，在对偶问题中是目标函数的价值系数；
原问题中约束条件的系数矩阵在对偶问题中进行了转置

对于对称的LP问题，
如果原问题求的是 极大化
其对偶问题的决策变量的方向与原问题约束条件不等号方向相反，对偶问题的约束条件不等号的方向与原问题决策变量的方向相同。

如果原问题求的是 极小化 ，对偶问题的决策变量和原问题的约束条件不等号相同；对偶问题约束条件的不等号方向和原问题的决策变量的方向相反。

对偶问题的决策变量的方向，去找原问题的约束条件的不等号；
对偶问题的约束条件不等号的方向，去找原问题的决策变量的方向；

写出非对称的对偶问题的思路（仅限于原问题是求 极大值 ）
1.将系数矩阵A转置，把价值系数C转置放到常数项的位置；不等号的方向去找原问题的决策变量的方向；
2. 决策变量的方向去找原问题约束的不等号相反。

下面这道题：原问题是求极小值！！！

注意：本题原问题求的是最小值，也就是说对于对偶问题，其决策变量的方向与原问题不等号方向相同；其约束条件不等号方向与决策变量相反；

写出对偶问题

解答
这里利用的是互补松弛性，对偶问题的化为标准形需要添加松弛变量Xs，把最优解代入到各个约束条件中，发现条件1是等式，所以松弛变量为0，解不出x1；约束条件2 ：代入最优解发现是严格的不等式，所以松弛变量是不等于0的，那么根据互补松弛性： x 2 ​ ∗ y s 2 ​ = 0 ，可以得到x2=0，如下。

这里 原问题的两个约束条件应取等号原因如下：
y1，y2≥0，这里添加的松弛变量是0，只有在等式的时候才成立。

解答
第（1）、（2）题反例：

这里对偶变量的最优解由下表可得，就是松弛变量对应的检验数的相反数。


很难找到初始可行基的意思是：一组 1．在线性规划模型中，没有非负约束的变量称为 （ ） A．多余变量 B．松弛变量 C．自由变量 D．人工变量 2．约束条件为AX=b，X≥0的线性规划问题的可行解集是 （ ） A．补集 B．凸集 C．交集 D．凹集 1.可行解：满足所有约束条件的解成为可行解。 2. 基可行解：立足于基矩阵得到的解叫做基解，基解中的可行解叫做基可行解。 3. 凸集：设K是n维欧式空间的一个点集，若任意两点X(1)∈K,X(2)∈K均有X=aX(1)+(1-a)X(2) ∈K(0<=a<=1),则称K为凸集。 1.可行域(可行解的集合叫做可行域)可行域凸集。 2. 有限个最优解 3.最优解一定为基可行解 1.标准化