第1章 线性规划

运筹学在英国称为“OperationalResearch”，其他英语国家称为“OperationsResearch”，直译—“作业研究”或“操作研究”意译—运筹学，取“运筹帷幄之中，决胜千里之外”之意。在英国称为“OperationalResearch”，其他英语国家称为“OperationsResearch”，直译—“作业研究”或“操作研究”意译—运筹学，取“运筹帷幄之中，决胜千里之外”之意。“田忌赛马”故事

田忌与齐王赛马，约定每胜一马得千金，各按马力强弱，以强、中、弱的先后顺序捉对较量，齐王的马都比较好，田忌的三匹马都略逊一筹，因而比赛输了。异日又赛，田忌一改常策，以弱、强、中的出场次序分对齐王的强、中、弱三马，终以一负两胜赢得千金。之后的思考——博弈之前的故事，到此就截止了，后人都夸田忌有对策。可如果事情继续发展，接下来会怎样呢，齐王输了，肯定会仔细分析，为什么输呢，推断出田忌的对策，然后想到下回再赛马，该如何排兵布阵，安排顺序呢。如果田忌足够聪明，他应该也想到，齐王这回输了，肯定会分析输的原因，然后会采取什么对策呢。……如此双方都进行算计。最后结局如何呢！

哥尼斯堡的七桥”故事

18世纪著名古典数学问题之一。在哥尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来。当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥，每座桥只能经过一次而且起点与终点必须是同一地点。这就是柯尼斯堡七桥问题。

七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成

把一个实际问题抽象成合适的“数学模型”。这种研究方法就是“数学模型方法”。这并不需要运用多么深奥的理论，但想到这一点，却是解决难题的关键。运筹学的工作步骤

提出和形成问题建立模型求解检验实施第一章线性规划的基本概念

线性规划问题及其数学模型线性规划的图解法线性规划的标准形式标准型线性规划的解的概念线性规划的基本理论

问题的提出：

在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源：劳动力、原材料、设备或资金等最佳：有一个标准或目标，使利润达到最大或成本达到最小。

有限资源的合理配置有两类问题如何合理的使用有限的资源，使生产经营的效益达到最大；在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。线性规划问题及其数学模型

与规划问题有关的数学模型总有两部分组成：约束条件：反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务；目标函数：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。例１，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：每吨产品的消耗每周资源总量甲乙维生素（公斤）3020160设备（台班）5115

已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果，甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？

定义x1为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。目标：使总利润Z=5x1+2x2

极大化约束：每周资源总量的限制，30x1+20x2≤160

5x1+x2≤15甲种药品每周产量不应超过4吨的限制

x1≤4计划生产数不可能是负数，x1≥0x2≥0每吨产品的消耗每周资源总量甲乙维生素（公斤）3020160设备（台班）5115单位利润（万元）5２数学模型为

s.t.

（subjectto)(suchthat)这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。在满足一组约束条件的限制下，寻求决策变量x1，x2的决策值，使目标函数达到最大值。每吨产品的消耗每周资源总量甲乙维生素（公斤）3020160设备（台班）5115单位利润（万元）5２例２：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。已知甲、乙两种原料都含有A、B、C三种化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合同规定的产品中三种化学成分的最低含量如下表所示：已知甲、乙两种原料的成本分别是每公斤3元和2元，厂方希望总成本达到最小，问如何配置该产品？原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155化学成分定义x1，x2分别为每公斤产品中甲，乙两种原料的数量，目标：使总成本Z=3x1+2x2

极小化约束：配料平衡条件，x1+x2=1产品中A、B、C三种化学成分的最低含量

12x1+3x2≥4

2x1+3x2≥2

3x1+15x2≥5非负性条件x1≥0,x2≥0原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）３２化学成分数学模型：

s.t.

这是一个原料配制问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量x1和x2的值使目标函数取得最小值。原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）３２化学成分

线性规划的一般数学模型

线性规划模型的特征：（1）用一组决策变量x1，x2，…xn表示方案，且在一般情况下，变量的取值是非负的。（2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。（3）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。（4）要求目标函数实现极大化（max）或极小化（min）。满足上述4个特征的规划问题称为线性规划问题

线性规划的模型的一般形式:

目标函数

满足约束条件

通常称为决策变量，为价值系数，为消耗系数,为资源限制系数。

线性规划的图解法

适用于求解两个变量的线性规划问题

图解法的基本步骤利用例1说明图解法的主要步骤，例1的数学模型为

s.t.O51015x1x1=4x25101AB(2,5)C▽Z5x1+x2=1530x1+20x2=1605x1+2x2=5

线性规划图解法的基本步骤：（1）建立以x1,x2为坐标轴的直角坐标系，画出线性规划问题的可行域,（2）求目标函数Z=C1x1+C2x2的梯度▽Z=（c1,c2）,（3）任取等值线C1x1+C2x2=Z0,沿梯度▽Z正方向平移,

（若是极小化问题，则沿负梯度方向-▽Z平移），求等直线将离未离可行域时与可行域的交点。（4）若交点存在，则该点坐标就是最优解。

图解法的几种可能结果

(1）有唯一最优解，如例1。（2）有无穷多最优解如例1中的目标函数设为maxZ=10x1+2x2

则目标函数等值线10x1+2x2=Z与第二约束5x1+x2≤15

的边界线平行。将等值线沿梯度▽Z=（10，2）正方向平移至B点时与可行域OABC的整条边界线AB重合。这表明线段AB上的每一点都使目标函数取得同样的最大值，因而都是最优解。O51015x1x1=4x25101AB（2，5）C▽Z5x1+x2=1530x1+20x2=16010x1+2x2=5例5，试用图解法求解下列线性规划问题

st.（3）无界解（或称无最优解）无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值Z→+∝,

极小化问题则可使目标函数值Z→-∝，

有无界解的线性规划问题的可行域通常是无界区域，但反之则不必然。-1O24x1x224-▽Z=(3,2)-2x1+x2=2x1-3x2=3-1O33（4）无可行解某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。

标准线性规划模型

线性规划问题的标准形式：

s.t

其中(1.1)为目标函数，(1.2)为约束条件，(1.3)为非负条件，为称呼方便，有时将(1.3)也称为约束条件。（1.2）

（1.3）线性规划的标准形式（1.1）紧凑格式：

s.t.向量格式：

s.t.

其中称为价值向量，为决策变量向量，为决策变量xj所对应的消耗系数向量，为资源向量。矩阵格式：其中为m×n阶矩阵

为价值向量，

为决策变量向量，

为资源向量。非标准形式线性规划问题的标准化（1）极大化与极小化：若，令，则有

原目标函数。(2)

线性不等式与线性等式：

其中为非负松弛变量，

其中为非负剩余变量。

(3)非负变量与符号不受限制的变量若xi的符号不受限制，则可引进非负变量xi1,xi2，令

xi=xi1-xi2，这样就可以使线性规划里所有的变量都转化为有非负限制的变量。例6，将下述线性规划问题化为标准型

解：令,可将目标函数化为max型，令,其中符号不受限制考虑一个标准的线性规划问题：

s.t

其中Ｃ为n维行向量，

Ｘ是n维列向量，

ｂ是m维列向量，

Ａ是m×n阶矩阵，假定满足m≤n，且Ｒ(Ａ)=m，标准型线性规划的解的概念

线性规划问题解的概念：

(1)可行解。满足约束条件(1.5)，(1.6)的解称为线性规划问题的可行解。可行解集称为线性规划问题的可行域。

(2)最优解。使目标函数（1.4)达到最优值的的可行解称为最优解，最优解常用表示。

(3)基。若Ｂ是Ａ中m×m阶非奇异矩阵，即|Ｂ|≠0，则称Ｂ是线性规划问题的一个基。若Ｂ是线性规划问题的一个基，那么Ｂ一定是由m个线性无关的列向量组成，不失一般性，可设

称为基向量，

与基向量相对应的变量称为基变量。

一个线性规划的基通常不是唯一的，但是基的个数也不会超过个。一旦线性规划的基确定了，那么相应的基向量、基变量和非基变量也就确定了。(4)基本解。设B是线性规划的一个基，若令n-m个非基变量等于0，则所得的方程组ＡＸ=b的解称为线性规划问题的一个基本解（简称基解）。有一个基就可以求得一个基本解。由基的有限性可知，基本解的个数也不会超过个。由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5)基本可行解。满足非负条件的基本解称为基本可行解（简称基可行解）。与基本可行解对应的基成为可行基。基本可行解的非零向量的个数小于等于m，并且都是非负的。由于基本可行解的数目一般少于基本解的数目，因此可行基的数目也要少于基的数目。

当基本可行解中有一个或多个基变量是取零值时，称此解为退化的基本可行解。

线性规划问题各种解的关系可用文氏图表示，

可行解

基本解基本可行解例7、求下列约束方程所对应的线性规划的所有基本解，基本可行解。

s.t

解：化为标准形式为2×4阶矩阵。且R(A)=2,所以该线性规划基的个数≤=6个

取,为基变量，若令非基变量，约束方程组为可得对应的基本解是一个基本可行解。

按相同步骤，可求得线性规划其他4个基：对应基本解是一个基本可行解。

对应基本解是一个基本可行解。

对应基本解不是一个基本可行解。

对应基本解是一个基本可行解。

若利用图解法画出线性规划的可行域，如图，CDOBA448

线性规划的基本理论

由图解法的步骤，可以从几何的角度得出以下两个结论：（1）线性规划问题的可行域是一个有界或无界的凸多边形，其顶点个数是有限个。（2）若线性规划问题有最优解，那么最优解一定可在可行域的某个顶点上找到。几个基本概念

（1）凸集：设k是n维欧式空间的一个点集，若任意两点

X(1)∈k,X(2)∈k的连线上的一切点αX(1)+(1-α)X(2)∈k

(0<α<1),则称k为凸集。连接几何形体中任意两点的线段仍完全在该几何形体之中。有限个凸集的交集仍然是凸集。（2）凸组合：设X(1)，X(2)，…，X(k)是n维欧式空间中的k个点，若存在μ1,μ2,…,μk满足0≤μi≤1,(i=1,2,…,k),

使X=μ1X(1)+μ2X(2)+…μkX(k)，

则称X为X(1)，X(2)，…，X(k)的凸组合。凸集k中任意两点X(1)，X(2)连线上的任一点X都是X(1)与X(2)的一个凸组合。

(3)顶点：设k为凸集，X∈k,若X不能用X(1)∈k,X(2)∈k两点的一个凸组合表示为X=αX(1)+(1-α)X(2),其中0<α<1，

则称X为k的一个顶点。第二章单纯形法

单纯形法的一般原理表格单纯形法借助人工变量求初始的基本可行解单纯形表与线性规划问题的讨论改进单纯形法

Dantzig的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。

单纯形法的一般步骤如下：

（1）寻找一个初始的基本可行解。（2）检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。（3）移至目标函数值有所改善的另一个基本可行解，然后转回到步骤（2）。

确定初始的基本可行解

确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定

为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，…Ｐm）为基变量x1，x2，…xm的系数列向量构成的可行基，Ｎ=(Ｐm+1，Pm+2，

…Pn)为非基变量xm+1，xm+2，

…xn的系数列向量构成的矩阵。

所以约束方程就可以表示为

用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得：若令所有非基变量,则基变量由此可得初始的基本可行解问题：要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。基由系数矩阵Ａ中m个线性无关的系数列向量构成。但是要判断m个系数列向量是否线性无关并非易事。即使系数矩阵Ａ中找到了一个基B，也不能保证该基恰好是可行基。因为不能保证基变量ＸB=Ｂ-1b≥0。为了求得基本可行解，必须求基Ｂ的逆阵Ｂ-1。但是求逆阵Ｂ-1也是一件麻烦的事。结论：在线性规划标准化过程中设法得到一个m阶单位矩阵I作为初始可行基Ｂ，若在化标准形式前，约束方程中有“≥”不等式，那么在化标准形时除了在方程式左端减去剩余变量使不等式变成等式以外，还必须在左端再加上一个非负新变量，称为人工变量．若在化标准形式前，约束方程中有等式方程，那么可以直接在等式左端添加人工变量。为了设法得到一个m阶单位矩阵I作为初始可行基Ｂ，可在性规划标准化过程中作如下处理：

若在化标准形式前，m个约束方程都是“≤”的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量xn+i(i=12…m)。判断现行的基本可行解是否最优

假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值

其中

分别表示基变量和非基变量所对应的价值系数子向量。

要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非基变量表示，即：

其中称为非基变量ＸN的检验向量，它的各个分量称为检验数。若σN的每一个检验数均小于等于0，即σN≤0，那么现在的基本可行解就是最优解。定理1：最优解判别定理

对于线性规划问题若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。定理2：无穷多最优解判别定理

若是一个基本可行解，所对应的检验向量，其中存在一个检验数σm+k=0，

则线性规划问题有无穷多最优解。

基本可行解的改进

如果现行的基本可行解Ｘ不是最优解，即在检验向量中存在正的检验数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由可知，这样的变换一定能使目标函数值有所增加。换入变量和换出变量的确定：换入变量的确定—最大增加原则

假设检验向量，若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用“最大增加原则”，即选取最大正检验数所对应的非基变量为换入变量，即若

则选取对应的为换入变量，由于且为最大，因此当由零增至正值，可使目标函数值最大限度的增加。换出变量的确定—最小比值原则如果确定为换入变量，方程

其中为Ａ中与对应的系数列向量。现在需在中确定一个基变量为换出变量。当由零慢慢增加到某个值时，

的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：若则选取对应的基变量为换出变量。定理3：无最优解判别定理

若

是一个基本可行解，有一个检验数，但是，则该线性规划问题无最优解。证：令，则得新的可行解将上式代入

因为,故当λ→+∞时，Z→+∞。

用初等变换求改进了的基本可行解

假设Ｂ是线性规划的可行基，则令非基变量，则基变量。可得基本可行解

。

用逆阵左乘约束方程组的两端，等价于对方程组施以一系列的初等“行变换”。变换的结果是将系数矩阵Ａ中的可行基Ｂ变换成单位矩阵I，把非基变量系数列向量构成的矩阵Ｎ变换成，把资源向量b变换成。

且改进了的基本可行解只是在Ｘ的基变量的基础上用一个换入变量替代其中一个换出变量，其它的基变量仍然保持不变。这些基变量的系数列向量是单位矩阵I中的单位向量。为了求得改进的基本可行解，只需对增广矩阵施行初等行变换，将换入变量的系数列向量变换成换出变量所对应的单位向量即可。

由于行初等变换后的方程组与原约束方程组或同解例1解：(１)确定初始的基本可行解。，基变量

，非基变量

。(2)检验

是否最优。检验向量

因为σ1=3，σ3=4均大于零，所以不是最优解。（3）基本可行解的改进

①

选取换入变量因为max{3，4}=4，取x3为换入变量。

②

选取换出变量且

，

选取x4为换出变量.（4）求改进了的基本可行解

对约束方程组的增广矩阵施以初等行变换，使换入变量x3所对应的系数列向量

变换成换出变量x4所对应的单位向量,

注意保持基变量x5的系数列向量

为单位向量不变。第一行除以２第二行减去第一行——————————————————————————可得改进的基本可行解。，基变量，非基变量。

基本可行解

目标函数值易见目标函数值比原来的Z=-1增加了，再转向步骤(2)（2）检验

是否最优。检验向量

因为，所以仍不是最优解。（3）基本可行解的改进

①

选取换入变量因为，取为换入变量。

②

选取换出变量且

，选取为换出变量.（4）求改进了的基本可行解

对约束方程组的增广矩阵施以初等行变换，使换入变量所对应的系数列向量变换成换出变量所对应的单位向量

,

第二行乘以２/５第一行减以第二行的１/２倍——————————————————————————可得改进的基本可行解。，基变量，非基变量

基本可行解

目标函数值比Z=15增加了，再转向步骤(2)（2）检验

是否最优。检验向量

因为所有检验数均小于零，所以是最优解，表格单纯形法

通过例１我们发现，在单纯形法的求解过程中，有下列重要指标：每一个基本可行解的检验向量根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。每一个基本可行解所对应的目标函数值通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。

在单纯形法求解过程中，每一个基本可行解Ｘ都以某个经过初等行变换的约束方程组中的单位矩阵Ι为可行基。当Ｂ=Ｉ时，Ｂ-1=Ｉ，易知：

可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：C

CBCN

θ

CB

XB

b

X1X2···Xm

Xm+1Xm+2···Xn

C1C2..Cm

X1X2

.Xm

b1b2..bm

I

N

θ1θ2..θm

Z

CBb

0

CN-CBN

例2、试利用单纯形表求例1中的最优解：

得初始的单纯形表：初始基本可行解，Z=-1，

122108x4-1

30400-1Z

341017x51

x1x2x3x4x5bXBCBΘ

523-11C

换入变量，换出变量，２为主元进行旋转变换基本可行解，Z=15，1/2

1

1

1/2

04x331-40-2015Z5/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C122108x4-130400-1Z341017x51x1x2x3x4x5bXBCBΘ523-11C8/27/1

最优解最优值

换入变量，换出变量，５/２为主元进行旋转变换4/1/21/2

1

1

1/2

04x331-40-2015Z3/5/25/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C02/513/5-1/517/5x33

0-26/50-9/5-2/581/5Z16/50-1/52/56/5x15x1x2x3x4x5bXBCBΘ

523-11C例3、用单纯形方法求解线性规划问题解：本题的目标函数是求极小化的线性函数，可以令则这两个线性规划问题具有相同的可行域和最优解，只是目标函数相差一个符号而已。

010103x220012-12x30-010103x224/1101004x303/1010103x40_101004x30

0000-18Z’100-212x11

100-206Z’2/1100-212x50

120000Z’8/2120018x50

x1x2x3x4x5bXBCBΘ12000C最优解最优值2/23/1-

因为非基变量x4的检验数σ4=0，由无穷多最优解判别定理，本例的线性规划问题存在无穷多最优解。事实上若以x4为换入变量，以x3为换出变量，再进行一次迭代，可得一下单纯形表：最优解最优值最优解的一般表示式C12000ΘCBXBb

x1x2x3x4x5021x4x2x1124001/21-1/201-1/201/210100Z’8

0000-1对于极小化的线性规划问题的处理：先化为标准型，即将极小化问题变换为极大化问题，然后利用单纯形方法求解．直接利用单纯形方法求解，但是检验是否最优的准则有所不同，即：若某个基本可行解的所有非基变量对应的检验数（而不是≤０），则基本可行解为最优解．否则采用最大减少原则（而非最大增加原则）来确定换入变量，即：若则选取对应的非基变量xm+k为换入变量．确定了换入变量以后，换出变量仍采用最小比值原则来确定。

借助人工变量求初始的基本可行解

若约束方程组含有“≥”不等式，那么在化标准形时除了在方程式左端减去剩余变量，还必须在左端加上一个非负的人工变量。因为人工变量是在约束方程已为等式的基础上，人为的加上去的一个新变量，因此加入人工变量后的约束方程组与原约束方程组是不等价的。加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解．而这正是我们引入人工变量的主要目的。考虑线性规划问题：为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为初始可行基，在每个约束方程组的左端加上一个人工变量

可得到：

————————————————————————

添加了m个人工变量以后，在系数矩阵中得到一个m阶单位矩阵，以该单位矩阵对应的人工变量为基变量，即可得到一个初始的基本可行解这样的基本可行解对原线性规划没有意义的。但是我们可以从X(0)出发进行迭代，一旦所有的人工变量都从基变量迭代出来，变成只能取零值的非基变量，那么我们实际上已经求得了原线性规划问题的一个初始的基本可行解。此时可以把所有人工变量剔除，开始正式进入求原线性规划最优解的过程。大M法

大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-Ｍ。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。

以后的计算与单纯形表解法相同，Ｍ只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。例4、用大M法求解下面的线性规划问题:解：

首先将原问题化为标准型添加人工变量，并在目标函数中分别赋予-Ｍ

-

01-1/2-1/201/21/23/2X2210-1/21/201/2-1/21/2X1-1--110-10011X221/220-1101-11X6-M1/1-110-10011X7-M2/111-100102X6-M

001/23/20-1/2-M-3/2-M5/2Z

001/21/21-1/2-1/23/2X501+2M0-M2+M00-2-2M2-MZ2/1100110-12X50

-12+2M-M-M000-3MZ3/101001003X50

X1x2x3x4x5x6x7bXBCBθ

-12000-M-MC01001003X22100110-12X4011-100102X2220-1101-11X40-

01-1/2-1/201/21/23/2X221/2/1/210-1/21/201/2-1/21/2X1-1-1000-2-M-M6Z-10101-101X30-30200-2-M-M4Z-10101-101X50

001/23/20-1/2-M-3/2-M5/2Z3/2/1/2

001/21/21-1/2-1/23/2X50

X1x2x3x4x5x6x7bXBCBθ

-12000-M-MC最优解最优值两阶段法

两阶段法引入人工变量的目的和原则与大M法相同，所不同的是处理人工变量的方法。两阶段法的步骤：求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化；约束条件为原问题中引入人工变量后包含一个单位矩阵的标准型的约束条件。如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算；否则说明原问题没有可行解，可停止计算。求原问题的最优解。在第一阶段已求得原问题的一个初始基本可行解的基础上，继续用单纯形法求原问题的最优解例5、用两阶段法求解例4中的线性规划问题。解：首先将问题化为标准型添加人工变量x6,x7,并建立辅助线性规划如下：由于辅助线性规划的目标函数是极小化，因此最优解的判别准则应为：

01-1/2-1/201/21/23/2X2010-1/21/201/2-1/21/2X10--110-10011X201/220-1101-11X611/1-110-10011X712/111-100102X6100000110W

001/21/21-1/2-1/23/2X50-201-10021W2/1100110-12X50

0-2110003W3/1

01001003X50x1x2x3x4x5x6x7bXBCBθ0000011C辅助规划所有检验数：原问题已得一个初始基本可行解，由上表可知，通过若干次旋转变换，原问题的约束方程组已变换成包含一个单位矩阵的约束方程组该约束方程组可作为第二阶段初始约束方程组，将目标函数则还原成原问题的目标函数，可继续利用单纯形表求解。-1000-26Z1001101001-10101231X4X2X3020-302004Z20-11011-100-10101121X4X2X5020001/23/205/2Z1/2/1/2-3/2/1/2

10-1/21/2001-1/2-1/20001/21/211/23/23/2X1X2X5-120x1x2x3x4x5

bXBCBθ-12000C可得最优解，目标函数值maxZ=6，与用大M法的结果完全相同。单纯形表与线性规划问题的讨论

无可行解

通过大Ｍ法或两阶段法求初始的基本可行解。但是如果在大Ｍ法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空集。例6、求解下列线性规划问题解：首先将问题化为标准型令，则

故引入人工变量，并利用大M法求解C

-3-2-1000-M-M

CB

XB

b

x1x2x3x4x5x6x7x8

θ

0-M-M

x4x7x8

643

1111000010-10-101001-100-101

6/1-3/1

Z’

-7M

-6-4M

-15-M

-3+M-2+M-1-2M0-M-M00

0-M-2

x4x7x2

343

1021010-110-10-101001-100-101

3/14/1-

Z’

Z’

-3+M0-3-M0-M-202-M

-3-M-2

x1x7x2

313

1021010-100-3-1-1

-11101-100-101

003-3M3-M-M1-M0-1

在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。无最优解

无最优解与无可行解时两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。

判别方法：无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解，可以可以例7、试用单纯形法求解下列线性规划问题：解：引入松弛变量x3,x4化为标准型C

2200θ

CXB

B

x1

x2

x3

x4

0X3

1-11100X4

2-1/2101Z02200因但所以原问题无最优解

退化解

当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值θ，那么在下次迭代中就会出现一个甚至多个基变量等于零。遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点，解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。例8、求解下述线性规划问题：解：引入松弛变量化标准型000-242-8030Z-5-60-420-805Z10001001x3

212060-2411x1

3321300-803x5

00-30-425-800Z11001001x7

00106-1-2410x1

30-1130-3-800x5

0-11001001x7

000106-1-2410x6

0000136-4-3210x5

0x7

x6