基本思想：构造一个辅助线性规划问题（ALP）,通过求解它得到线性规则（LP）的初始可行基。

目录

基本概念：

例题分析：

对于标准形式的线性规则问题：

其中 ,A 是  矩阵，，但 A 不一定满秩。

首先，增加两个 m 维向量：

其中  称为人工变量。

然后，构造辅助标准线性规划问题（ALP） ：

其中 M 是一个很大的正数，这样在极小化目标函数的过程中，由于大 M 的存在，即迫使人工变量离基。

用单纯形法求解（ALP），其结果为下列几种情形之一：

（1）求得（ALP）的最优解，并且人工变量全是零，此时得到的 x 就是（LP）的最优解；

（2）求得（ALP）的最优解，但是人工变量不全是零，则（LP）无最优解；

（3）发现（ALP）没有最优解，则（LP）没有最优解或者没有可行解。

例题：用大 M 法求解线性规划问题：

解：构造辅助线性规划（ALP）

可以得到下列矩阵：

，，

ALP 选取  作为基，

离基变量：，进基变量：

离基变量：，进基变量：

离基变量：，进基变量：

此时，检验数全负，得到 ALP 的最优解 

原问题的最优解为： ，最优值为 f =-2。

（行文中若有纰漏，希望大家指正）