线性规划单纯形算法

Ⅰ 图解法和单纯形法的优缺点，分别适用于哪些类型的线性规划问题

一、单纯形法：

1、优点：把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。用于优化多维无约束问题的一种数值方法，属于更普遍的搜索算法的类别。

2、缺点：约束条件中存在大于或等于约束：将约束两边取负。

二、图解法：

1、优点：原理简单，易掌握，会数格子就可以用。

2、缺点：精度有限，要精确确计算用求积仪或者高数里面的积分最好，图解法适合在一些精度要求不高的场合使用。

(1)线性规划单纯形算法扩展阅读：

注意事项：

平常的线性规划的里面，当线性方程组的数量大于这个方程的个数，就会有不定数量的解。

在单纯形法要是基本可行，那么解不存在的话，就是这个约束的条件有矛盾了。

单纯形法是要把表达成典范型方程组是要变量的转换，还有就是目标的转换，是要找出可行解作为初始基可。如果单纯形法是能让解存在，是从初始作起点，找到目标函数值就是更好的一个基本可行解。

Ⅱ 250分悬赏线性规划问题（单纯形法）

一、线性规划单纯形法的概念

（一）线性规划单纯形解法的基本思路

若一个凸集仅包含有限个极点，则称此凸集为单纯形。
线性规划的可行域是单纯形（证明略，但可以从上节图解法的例子得到认同），进而线性规划的基可行解又与线性规划问题可行域的极点1-1对应（定理2.2.2）， 线性规划单纯形法就是基于线性规划可行域的这样的几何特征设计产生的。这个方法最初是在20世纪40年代由George Dantzig研究出来的。这个线性规划单纯形解法的基本思路是：先求得一个初始基可行解，以这个初始基可行解在可行域中对应的极点为出发点，根据最优准则判断这个基可行解是否是最优解，如果不是转换到相邻的一个极点，即得到一个新的基可行解，并使目标函数值下降，这样重复进行有限次后，可找到最解或判断问题无最优解。

（二）单纯形法的最优准则

设：线性规划（LP）为：

min cx
s.t. Ax=b
x≥0

A为（LP）的约束方程组的m*n阶系数矩阵（设n≥m），A的秩为m；B是线性规划的一个基，不失普遍性，记

定义

则：称λ，或者λj,(j=1,2,…,n)为检验数。

若：λ≤0，即全部λi非正，
则：由B确定的基可行解是（LP）的最优解。
（参看附录2.3.1）

二、线性规划单纯形法的表格解法

较简单的线性规划可以采用单纯形法的表格形式，这样利用计算器就可求解。单纯形法的表格解法的基本思路是，对基可行解建立单纯形表，依据此表作最优解判断，以及从原基可行解向目标值更小的新可行解转换的计算。

对于由基阵B确定的基可行解，其单纯形表为表2.3.1形式。对于初始基可行解，其单纯形表的构建方法为：先建立表2.3.2形式的表格，然后应用“行变换”将表2.3.2中的前m列，即基变量对应的列

转换为

其中0是m元0向量：0=(0,0,…,0), 是m阶单位方阵。在这样的行变换下，表2.3.2将转换为表2.3.1

表2.3.1

检验数

基变量
cBB-1A-c cBB-1b
xB B-1A B-1b

表2.3.2

检验数

基变量
-cB -cN o
xB B N B-1b

（参看附录2.3.2）

（一）直接求解
对如下形式的较简单的线性规划可直接采用单纯形法的表格形式求解：

min cx
s.t. Ax≤b
x≥0

这种形式的线性规划标准化后，为

min cx+ox'
s.t. Ax+lx'=b
x≥0,x'≥0

其中x'=(x1',x2',…,xm')为松驰变量，而o=(0,0,…,0)T 。现在新的约束矩阵为

因为I是m*n的单位矩阵。所以我们就可用这个矩阵作基阵，松驰变量是基变量，立即得到一个初始基可行解，其目标函数值为0，而相应的初始单纯形表如表2.3.3所示。表中

θ=o=(0,0,…,0)T,

从而可开始单纯形表上求解的过程。

表2.3.3

检验数

基变量
-c θ o
A I b

下面我们通过一个实例看单纯形表解线性规划问题的一般步骤

例2.3.1 用直接法求解（LP）

max z=40x1+45x2+24x3
s.t. 2x1+3x2+x3≤100
3x1+3x2+2x3≤120
x1,x2,x3≥0

解：
第一步 先将原问题化为标准形式

min -z=-40x1-45x2-24x3
s.t. 2x1+3x2+x3+x4=100
3x1+3x2+2x3+x5=120
x1,x2,x3,x4,x5≥0

第二步 列出初始单纯形表

x1 x2 x3 x4 x5
40 45 24 0 0 0
x4 2 3 1 1 0 100
x5 3 3 2 0 1 120

此时，基可行解(0,0,0,100,120)T为，目标函数值为0.

第三步 检查检验数

故

λ=(40,45,24,0,0)≥0

因此基可行解不是最优解，要进行基的转换。

线性规划检验数的定义和最优解的单纯形法检验准则：
检验数定义为

若 基可行解对应的λ为检验数为非正向量，即

则 此可行解为最优解。
当大于零的检验数不止一个，理论上可任选一个正检验数对应非基变量为进基变量，一般情况选取最大正值的检验数对应的非基变量为进基变量，这样迭代常常会快一些。为此，我们选x2进基，因为

因此，x4为离基变量，则新的基变量为x2，x5。

第四步 建立新的基相应的单纯形表

建立单纯形表的方法：
在计算过程中，只要将A中基变量对应的列组成的子矩阵
通过行变换化成单位阵，基变量对应的检验数化成零即可。

如何从原来的表转到新的基相应的单纯形表呢？只要把A中x2相应的列向量通过初等变换化成单位向量即可。因此在上表中只要把x2对应的列

化成

我们称基变量x4所在行和非基变量x2所在列相交元素为变换轴心，用加＊表示，现在这数为3，将这行乘以（-1）加到第三行，乘以（-15）加到第一行，然后将这行行除以3，得一个新的单纯行表

x1 x2 x3 x4 x5
10 0 9 -15 0 -1500
x2 2/3 1 1/3 1/3 0 100/3
x5 1* 0 1 -1 1 20

这样我们作了一次转换，新的基可行解为(0,100/3,0,0,20),目标函数值为-1500。

现在再回到第三步。现在λ1=10,λ3=9均大于零，仍不是最优解，取x1进基；

因为：

所以，x5离基。

x1 x2 x3 x4 x5
0 0 -1 -5 -10 -1700
x2 0 1 -1/3 1 -2/3 20
x1 1 0 1 -1 1 20

现在所有检验数均小于等于零，这个基可行解（20，20，0，0，0）是最优解，原问题最优值1700.以后。

实际在表上作业时，求λk与xr的过程可不写，这些表可连在一起。

（二）单纯形法求解的基本步骤

首先我们需要对单纯形表作进一步的认识，注意到检验数：

可见，对应于基变量的λj=0(j=1,2,∧,m)，而且

再记

进而记

这样单纯形表2.3.1可呈现为表2.3.4的形式：

表2.3.4

x1 x2 … xm xm+1 … xn
检验数

基变量
0 0 … 0 λm+1 … λn f0
x1 1 0 … 0 y1m+1 … y1n
x2 0 1 … 0 y2m+1 … y2n
… … … … … … … … …
xm 0 0 … 1 ymm+1 … ymn

有了表2.3.4，单纯形表上解法的一般步骤为：

步一：把线性规划模型变成它的标准形式；

步二：确定初始基可行解，建立初始单纯形表；

步三：检查对应于非基变量的检验数λj,(j∈N)；若所有这些λj均小于零，则已得到最优解，停止计算，否则转入下一步；

步四：在所有的λj>0中，若有一个λk在单纯形表上对应的列向量的全部元素yik≤0(i=1,2,…,m)，则此问题无解，停止计算；否则转入下一步；

步五：根据max{λj>0|j∈N}=λk, 即确定λk对应的非基变量λk为进基变量；再根据

确定基变量xr为离基变量；

步六：基可行解的转换运算，即实施行变换，将单纯形表上xk对应的列向量变换为单位向量，其中包括将λk变换为0，而原yrk变换为1，称元素yrk为变换轴心。

（三）两阶段法

对一般的线性规划，往往不会象用直接法求解形为Ax≤b的线性规划那样，能够很容易找到初始基可行解，甚至连有无可行基都难以判定，这时就需要应用两阶段法来求解线性规划。

二阶段法就是把解线性规划问题划分为两个阶段，第一阶段求出原问题的一个基可行解或判断原问题可行域为空；第二阶段在得到的基可行解基础上求解原问题。方法如下：

第一阶段
人为地在原约束矩阵中增加一些变量使得到单位矩阵，增加的变量称为人工变量，目标函数是人工变量之和。具体而言，对于原线性规划标准化后的Ax=b,(b≥0)的形式，若A中不包括单位矩阵，则我们在每个方程后面加一个“人工变量”得到一个新的线性规划（LP）如下：

（当A中有一些单位向量时，人工变量可少于m个）

为书写方便我们记（LP0）为：

其中Em=(1,1,K,1),分量全为1的m元横向量，

这儿Im是可行基，又因为xa≥目标函数Emx有下界0，所以（LP0）一定有最优解。设最优解为：

则可能有三种情形：

(1)若：在最优解x0的基变量中，不存在人工变量，即人工变量xn+1,xn+2,…,xn+m都是非基变量。
则：x0的前n个分量(x10,x20,K,xn0)便是原线性规划问题的一个基可行解。可进入第二阶段。

(2)若：在最优解x0的基变量中，包括某些人工变量，并且最优值z>0。
则：原线性规划可行域为空，原线性规划无解。

这是因为，否则可设原规划有可行解(x1*,x2*,…,xn*),
则(x1*,x2*,…,xn*,0,…,0)是（LP0的可行解，其目标函数值
为0，这与最优值大于零矛盾。

(3)若：在最优解x0的基变量中，包括某些人工变量，但最优值z=0，即，此时为基变量的人工变量都取值为0。
则：设xn+1是一个人工变量的基变量，其在最优解的单纯形表中对应第S行，设J是非人工变量中非基变量的下标集。

① 如果单纯形表的第S行中，所有的ysk=0,(k∈J)此示原约束Ax=b中第S行为其余行的线性组合，即是个多余的约束，应当删去；

② 如果存在ysk≠0 (k∈J),
则无论ysk是正还是负，以它为变换轴心，xk进基，xn+1离基.如果新表中的基变量中还有人工变量，重复以上步骤，有限次可得到（1）的情形。

第二阶段

步1：以第一阶段最优解对应的单纯形表为基础，删去人工变量对应的列，并且将原规划（已标准化）的-c作为检验数，放在第一行，然后用用行变换将基变量对应的检验数消为零。

步2：以步1结束时建立单纯形表为原线性规划的初始单纯形表，求解原线性规划。

[例2.3.2] 用二阶段法求解（LP）：

min x1-2x2
s.t. x1+x2≥2
-x1+x2≥1
x2≤3
x1,x2≥0

解：
先标准化：

min x1-2x2
s.t. x1+x2-x3=2
-x1+x2-x4=1
x2+x5=3
x1,x2,x3,x4,x5≥0

第一阶段：
因为A中 对应单位向量

，故只要引进两个人工变量x6,x7即可

min x6+x7
s.t. x1+x2-x3+x6=2
-1+x2-x4+x7=1
x2+x5=3
x1,x2,K,x7≥0

在第一行放入检验数：

这等价于在第一行放-c，再用行变换使基变量的检验数为零。

x1 x2 x3 x4 x5 x6 x7
0 0 0 0 0 -1 -1 0
x6 1 1 -1 0 0 1 0 2
x7 -1 1 0 -1 0 0 1 1
x5 0 1 0 0 1 0 0 3
0 2 -1 -1 0 0 0 3
x6 1 1 -1 0 0 1 0 2
x7 -1 1 0 -1 0 0 1 1
x5 0 1 0 0 1 0 0 3
2 0 -1 1 0 0 -2 1
x6 2* 0 -1 1 0 1 -1 1
x2 -1 1 0 -1 0 0 1 1
x5 1 0 0 1 1 0 -1 2
0 0 0 0 0 0 -1 0
x1 1 0 -1/2 -1/2 0 1/2 -1/2 1/2
x2 0 1 -1/2 -1/2 0 1/2 1/2 3/2
x5 0 0 1/2 1/2 1 -1/2 -1/2 3/2

得到第一阶段最优解，人工变量不是基变量，最优值为0，则去掉x6,x7所在两列就是原问题基可行解。

第二阶段
仍将-c放在第一行，用行变换将基变量对应的检验数消为零。

x1 x2 x3 x4 x5
-1 2 0 0 0
x1 1 0 -1/2 1/2 0 1/2
x2 0 1 -1/2 -1/2 0 3/2
x5 0 0 1/2 1/2 1 3/2
0 0 1/2 3/2 0 -5/2
x1 1 0 -1/2 1/2* 0 1/2
x2 0 1 -1/2 -1/2 0 3/2
x5 0 0 1/2 1/2 1 3/2
-3 0 2 0 0 -4
x4 2 0 -2 2 0 1
x2 1 1 -1 0 0 2
x5 -1 0 1* 0 1 1
-1 0 0 0 -2 -6
x4 0 0 0 2 2 2
x2 0 1 0 0 1 3
x3 -1 0 1 0 1 1

现在检验数全小于等于零，得到原问题最优解x*=(0,3,1,2,0)T最优值-6。

[例2.3.1.3] 用二阶段法求解（LP）：

min -3x1+4x2
s.t. x1+x2≤4
2x1+3x2≥18
x1,x2≥0

标准化：

min -3x1+4x2
s.t. x1+x2+x3=4
2x1+3x2-x4=18
x1,x2,x3,x4≥0

第一阶段：

min x5
s.t. x1+x2+x3=4
2x1+3x2-x4+x5=18
x1,x2,x3,x4,x5≥0

为了少写一张表，也可在表最上方一行放 ，然后再用行变换使基变量的检验数为零。

0 0 0 0 -1
x1 x2 x3 x4 x5
2 +3 0 -1 0 18
x3 1 1* 1 1 0 4
x5 2 +3 0 -1 1 18
-1 0 -3 -1 0 6
x2 1 1 1 0 0 4
x5 -1 0 0 -1 1 16

已得到第一阶段最优解，但人工变量仍留在基里，并且最优值z=6>0故原问题可行域为空。原线性规划无解。

Ⅲ 用单纯形法求解线性规划问题

1.
单纯形法是解线性规划问题的一个重要方法。 其原理的基本框架为: 第一步:将LP线性规划变标准型,确定一个初始可行解(顶点)。 第二步:对初始基可行解最优性判别,若最优,停止;否则转下一步。 第三步:从初...
2.
用程序进行运算前,要将目标函数及约束方程变成标准形式。 于非标准形式须作如下变换: a) 目标函数为极小值min z=CX时,转...
3.
对于标准形式的线性规划问题。用单纯形法计算步骤的框图。 线性规划问题如下: max z=...

如果有兴趣可以私聊我，我可以在线为您解答。

Ⅳ 有谁能告诉我线性规划还有单纯形法的定义

线性规划
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.

单纯形法
求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。
改进单纯形法 原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。
对偶单纯形法 1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。
数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。
这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

Ⅳ 所有的线性规划问题是否都可以用单纯形法求解

单纯形法是一种求解线性规划问题的有效算法，可以解决任何线性规划问题。
所有的线性规划问题都可以转化成标准型。

Ⅵ 用单纯形法求解下列线性规划问题

单纯形法的基本想法是从线性规划可行集的某一个顶点出发，沿着使目标函数值下降的方向寻求下一个顶点，面顶点个数是有限的，所以，只要这个线性规划有最优解，那么通过有限步选代后，必可求出最优解 。
为了用选代法求出线性规划的最优解，需要解决以下三个问题  ：
(1)最优解判别准则，即迭代终止的判别标准  ；
(2)换基运算，即从一个基可行解迭代出另一个基可行解的方法 ；
(3)进基列的选择，即选择合适的列以进行换基运算，可以使目标函数值有较大下降

Ⅶ 线性规划之单纯形法

单纯形法应用在线性规划的标准模型上，任何一个线性规划的一般形式都可以化为标准模型。
线性规划模型的一般形式为：

把它转换为标准型是要求所有的约束都是等式约束，且所有的决策变量非负。
如下面的形式：

举个例子：

那么很容易就可以写出这个线性规划问题的数学模型：

再重复一遍，线性规划的标准型必为以下形式：

对于标准型我们有两个基本假设：
1. 系数矩阵A的行向量线性无关。
2. 系数矩阵A的列数大于其行数，即n>m。因为如果n<m，那么不满足1, 如果n=m，那么该线性规划问题有唯一解，既然有唯一解，那就没有优化的必要了。所以，必有n>m。

回到刚才那个例子，我们可以将找个标准型写为如下形式：

这个例子m = 3, n = 5。那么我们可以用三个变量表示所有的五个变量，这三个变量我们称之为基变量。上图中，x3, x4, x5的系数是一个单位阵。我们把这种形式的等式约束称为典式。
观察这个典式，我们可以很容易的看出其一个基本可行解：(0, 0, 15, 24, 5)T，即非基变量等于0，基变量等于等式右边的常数。这个解，我们可以把它想象成基本可行解区域的一个顶点，我们知道最优解也在顶点上，那么我们只要沿着边界找这个最优顶点就可以了。

对于顶点(0, 0, 15, 24, 5)T，它的x3, x4, x5是基变量，那么与该顶点相邻的其他顶点的基变量有什么关系呢？事实上，与之相邻的顶点的所有基变量中只有一个基变量发生了变化。这是可以验证的。所以，接下来的工作就是从x1, x2中选一个非基变量进基成为基变量，从x3, x4, x5中选一个基变量出基成为非基变量。

那么问题来了，我们怎么选择进基变量和出基变量？

假设我们想要x2进基，那么根据基本可行解的表示式，我们必须通过初等行变换的形式让x2只出现在一个等式约束中，就是把x2的系数变成(1,0,0)T或(0,1,0)T或(0,0,1)T的形式。
假设我们把x2变成(0,0,1)T的形式，初等行变换后得到：

现在对于例子

我们得到了两个基本可行解X1 = (0,0,15,24,5)T, X2 = (0,3,0,18,2)T，记目标函数f(X) = 2x1 + x2 + 0x3 + 0x4 + 0x5
则f(X1) = 0, f(X2) = 3
那么我们怎么找到最优解呢？
我们知道 X2 = (0,3,0,18,2)T 的约束的表示式为：

发现什么没有？

对于可行解X2 = (0,3,0,18,2)T，x1，x3是非基变量啊，非基变量是0啊。但是，我们下一步不是选择进基变量吗，进基变量不是从非基变量里选吗，我们选x1啊，为啥？x1的系数是正数2啊！我们这个例子是求z的最大值，如果x1进基，那么必然会让f(X)增大，因为我们的决策变量都是正数，正数乘正数还是正数，增量肯定是大于0的。我们看到x3的系数是-0.2，如果让x3进基的话，增量肯定是小于0的。

如果x1, x3的系数都大于0怎么办？那随便选啊。
如果x1，x3的系数都小于0怎么办？哈哈，有人可能就意识到了，非基变量的系数都小于0，选谁进基都会造成f(X)变小，我们不是求最大吗？那我们谁也不选啊，这个问题已经结束了，我们已经找到最优解了！

所以，选择进基变量的问题，以及判断找到最优解的问题就都解决了。

我们一般使用单纯形表来直观表示这个过程。
还是可行解X2 = (0,3,0,18,2)T，它对应的单纯形表如下：

最左边一列是基变量，最右边一列是约束右边的常数项，中间一坨是决策变量的系数。最下边一行是目标函数z = 2x1 + x2 + 0x3 + 0x4 + 0x5。最下面一行决策变量的系数我们称之为检验数。
我们通过行变换将最后一行的基变量前面系数变成0，就得到下面的单纯形表：

从这个表中我们可以得到以下信息：

然后通过刚才的方法让x3进基，得到新的基本可行解的单纯形表：

从这个表我们可以得知：

至此，我们已经得到该问题的最优解X4。

我们知道，对于一个基本可行解，一般情况下它的基变量是大于0，非基变量等于0。退化情况是，我们有一个基变量也等于0。那么，这个基本可行解就会对应于多个可行基阵。
举个例子：

X = （3，3，0，0，0）T是该问题的可行解
我们可以令x3,x4为非基变量， 也可以令x3,x5或x4,x5为非基变量。

退化情况存在的问题在于，经过一次进出基迭代后得到的是同一个基本可行解，因此有可能出现迭代算法在一个基本可行解的几个基矩阵之间循环不止的情况。

所以，保证单纯形法收敛的充分条件是：在迭代过程中产生的每个基本可行解的基变量数值都严格大于0。

在迭代过程中，如果某一个决策变量的系数都小于0了，这代表什么？
举例：

如上图，我们可以把x2放在等式右边，看出什么没有？x2可以趋于无穷大。

如上图， 非基变量x4的检验数为0了，根据最优性条件，让其进基并不能继续优化目标函数值。但是，x4进基后还是会得到一个基本可行解，且目标函数值与当前结果相同。这意味这什么？
目标不能再优化，但是又有不同的基本可行解，啥意思？说明该问题有无穷多个最优解。

所以， 对于求max的线性规划问题，如果所有检验数均满足<=0，则说明已经得到了最优解，若此时某非基变量的检验数=0，则说明该优化问题有无穷多最优解。

单纯形法是从一个初始的基本可行解开始的，出基入基，知道找到最优可行解。
问题是，我们怎么得到那个初始的基本可行解啊？
最基本的方法是 添加人工变量
假设原问题的约束是这样的：
x1 + 2x2 + 3x3 = 1
2x + x3 = 2
那么我们再加两个变量x4, x5，把约束变成这样：
x1 + 2x2 + 3x3 + x4 = 1
2x + x3 + x5 = 2
我们就把约束变成了典式，可以直接得到一个基本可行解(0,0,0,1,2)T，找个基本可行解的基变量是x4, x5，那么接下来的工作就是通过出基入基把x4,x5都变成非基变量，这样它们的值就可以为0， 从而得到原问题的可行解。
现在有个问题，如果在最优表中，基变量中仍含有人工变量，这说明啥？

这说明，原问题根本就无解。

Ⅷ 线性规划单纯型法

线性规划线性规划是运筹学中5研究较早、发展较快、应用广p泛、方7法较成熟的一b个s重要分0支s,它是辅助人p们进行科学管理的一s种数学方8法。在经济管理、交通运输、工v农业生产等经济活动中8，提高经济效果是人o们不w可缺少2的要求，而提高经济效果一b般通过两种途径：一w是技术方2面的改进，例如改善生产工t艺o，使用新设备和新型原材料。二n是生产组织与z计3划的改进，即合理安排人i力z物力v资源。线性规划所研究的是：在一j定条件下a，合理安排人w力v物力i等资源，使经济效果达到最好。 单纯形法求解线性规划问题的通用方7法。单纯形是美国数学家G。B。丹1齐克于y7110年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中1的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为2基本可行解。单纯形法的基本思想是：先找出一g个a基本可行解，对它进行鉴别，看是否是最优解；若不x是，则按照一d定法则转换到另一m改进的基本可行解,再鉴别；若仍1不i是，则再转换,按此重复进行。因基本可行解的个t数有限，故经有限次转换必能得出问题的最优解。如果问题无j最优解也g可用此法判别。单纯形法的一g般解题步骤可归纳如下c：①把线性规划问题的约束方2程组表达成典范型方5程组，找出基本可行解作为2初始基本可行解。②若基本可行解不g存在，即约束条件有矛盾，则问题无a解。③若基本可行解存在，从7初始基本可行解作为8起点，根据最优性条件和可行性条件，引3入h非基变量取代某一m基变量，找出目标函数值更优的另一j基本可行解。④按步骤8进行迭代,直到对应检验数满足最优性条件（这时目标函数值不y能再改善），即得到问题的最优解。⑤若迭代过程中2发现问题的目标函数值无t界，则终止3迭代。 用单纯形法求解线性规划问题所需的迭代次数主要取决于p约束条件的个o数。现在一l般的线性规划问题都是应用单纯形法标准软件在计8算机上p求解，对于t具有404个e决策变量和803个p约束条件的线性规划问题已d能在计2算机上v解得。 改进单纯形法 原单纯形法不z是很经济的算法。8428年美国数学家G。B。丹2齐克为8了p改进单纯形法每次迭代中5积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大s致相同，主要区u别是在逐次迭代中7不h再以3高斯消去法为0基础，而是由旧基阵的逆去直接计6算新基阵的逆，再由此确定检验数。这样做可以0减少4迭代中6的累积误差，提高计7算精度，同时也n减少8了a在计8算机上u的存储量。 对偶单纯形法 2560年美国数学家C。莱姆基提出对偶单纯形法。单纯形法是从2原始问题的一a个v可行解通过迭代转到另一u个d可行解，直到检验数满足最优性条件为3止6。对偶单纯形法则是从3满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中4始终保持基解的对偶可行性，而使不z可行性逐步消失。设原始问题为0min{cx|Ax=b，x≥0}，则其对偶问题为0 max{yb|yA≤c}。当原始问题的一p个b基解满足最优性条件时,其检验数cBB-4A-c≤0。即知y＝cBB-1（称为6单纯形算子j）为0对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下j，一y当基解成为0可行解时，便也r就是最优解。 数学优化2中5，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一e个n算法与v此无t关，但名称类似，它是Nelder-Mead法或称下s山w单纯形法，由Nelder和Mead发现（0150年），这是用于k优化4多维无f约束问题的一g种数值方4法，属于p更一i般的搜索算法的类别。 这二i者都使用了f单纯形的概念，它是N维中6的N + 0个n顶点的凸包，是一g个m多胞体：直线上s的一r个l线段，平面上a的一n个e三n角形，三a维空间中6的一o个r四面体，等等。 s↓k冤ㄅs↓q┷h胎dǐフnitz觥

Ⅸ 如何用单纯形法求解线性规划问题

单纯形法计算线性规划的步骤：（1）把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。（2）若基本可行解不存在，即约束条件有矛盾，则问题无解。（3）若基本可行解存在，从初始基本可行解作为起点，根据最优