线性规划的一般求解方法——单纯形法

第三章 线性规划的一般求解方法 ——单纯形法
它的一般形式为：

称为约束条件(Subject to)。 称为变量的非负约束条件。其余的变量可取正值、负值、或零值，称这样的变量为符号无限制变量或自由变量。 线性规划模型的特征是：一组决策变量 ，一组约束条件。一个目标函数。目标函数和约束条件都是线性的。

二、线性规划问题的标准行式是什么？ 如何将一个LP问题的一般形式转换为 标准形式？ (1)、这里规定的标准形式为：

简记为：
用矩阵表示为：
用列向量表示为：
（2）为了把一般形式的LP变换为标准形式，必须消除其不等式约束和符号无限制变量。
目标函数的转换
约束条件的转换
变量的非负约束的转换
任何形式的线性规划数学模型都可以转换成标准型的线性规划


三、什么是可行解、可行域，可行域的几何结构？
满足所有约束条件的决策变量，称为可行解或可行点(feasible point)。
使目标函数值最大的可行解称为最优解
所有可行点组成的集合称为可行域（feasible region），记为D.
给定一个LP问题可行域D,下列三种情况必居其一
D = ø 称该问题无解或不可行。 D ø 且可行域有界。则线性规划问题一定存在最优解。这时最优解唯一，也可能有无穷多。 D ø， 且可行域为无界，则线性规划问题或者有最优解（唯一或无穷多）也可能没有有限的最优解。 当可行域非空时，可行域的几何结构为(多面)凸集
四、基本解、基本可行解 (basic solution、basic feasible solution)



五、 LP问题的几何意义（单纯形表的数学原理）
若线性规划问题存在可行域，则其可行域D是凸集
线性规划问题的可行解为基可行解的充要条件是的正分量所对应的系数列向量线性无关。
X是基本可行解的充分必要条件是X是可行域D的顶点
一个标准的LP问题，若有可行解，则至少有一个基本可行解
一个标准的LP问题，若有有限的最优值，则一定存在一个基本可行解是最优解。


X是基本可行解的充分必要条件是X是可行域D的顶点

由以上定理可知，最优解一定在某一基本可行解处达到。因此单纯形法的基本思想是：先找一个基本可行解，然后判断它是否为最优解，如不是，就找一个更好的基本可行解，再进行判断，如此迭代进行，直到找到最优解或者判断该问题无界。
1．单纯形表 为了计算的方便，我们可以将单纯形法的全部计算过程在一个类似增广矩阵的数表上进行，这种表格称单纯形表，不同的教材设计表格稍有不同，这里设计如下：
2．  单纯形方法步骤

 Step1　转换一般的LP模型为标准型。
Step2 　找一个初始可行基。
Step3 　计算单纯形表中的各矩阵。
Step4 构造单纯形表。
Step5 判断最优解，是，则结束。否　　　　 则，转入下一步。
Step6 换基迭代，返回Step5。

如何得到第一个基本可行解？ 为了得到初始基本可行解，要首先找到初始基本可行基，设B为约束矩阵的一个m阶子式，如果B非奇异，则矩阵B是一个基， 进一步，若 ，那么B是初始基本可行基。 就是初始基本可行解。找初始基本可行基的方法如下 1．观察法与试验法。2.大M法。3.两阶段法
如何判断基本可行解是最优解？ 对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，



——掌握线性规划问题的数学原理及代数的单纯形解法是学习LP的最高境界。 ——掌握这一方法对于以后的学习大有裨益，希望同学们发扬十二分的耐心和钻研精神。


2、写出初始单纯形表

3、判断基本可行解是最优解 由于检验数有正数，且对应的列向量不全为负，故进行换基迭代，
4、换基迭代 选上表中的　为轴心项
5、判断、由于检验数有正数且对应的列向量不全为负，故进行换基迭代，选上表中的　为轴心项
由单纯形表得一基最优解， 由于有非基变量的检验数为零，则此线性规划有无穷解。选上表中的 为轴心项.
原线性规划所有最优解为：
如何用QM软件求解LP问题 三角洲航空公司的航班配置问题（怎样为各条航线分配班机和为乘客分配座位）。用LP模型解决，用到60000个变量，40000个约束条件。
课堂练习 A、用单纯形法求解两个变量的LP问题。 B、用QM软件求解LP问题
谢谢

线性规划的一般求解方法——单纯形法