第5章线性模型及求解

线性规划问题的求解方法一、图解法特点：1、只能求解只有两个变量的线性规划问题（适用范围比较小）2、不需要对模型进行标准化二、单纯形法特点：1、可以求解任意多个变量的问题（适用范围比较广）2、求解前必须将模型化为标准型的线性规划问题第五章单纯形法线性规划问题的标准形式为了使线性规划问题的解法标准，就要把一般形式化为标准形式这可是个重点哦！21bi,xj≥0(i=1,2,…,m;j=1,2,…,n)43不标准化标准的方法：

目标函数为min型，价值系数一律反号。令z=-z=-CX,有minz=-max[-z]=-maxzExample:

minZ=x1+2x2+

x3maxZ’=-x1-2x2-

x31MaxzMinz’ab注意：z与z’的解相同但目标函数值相差一负号zz’

第i个约束的bi

为负值，则该行左右两端系数同时反号，同时不等号也要反向Example:

4x1-2x2-3x3=-6-4x1+2x2+3x3=6

第i个约束为型，在不等式左边增加一个非负的变量xn+i

，称为松弛变量；同时令cn+i

=0Example:

-2x1+x2+x39-2x1+x2+x3+x4=9

第i个约束为型，在不等式左边减去一个非负的变量xn+i

，称为剩余变量；同时令cn+i

=0Example:

-3x1+x2+2x34-3x1+x2+2x3–x5=4若xj0，令

xj=-xj

，代入非标准型，则有xj

0若xj不限，令

xj=xj-xj，xj

0，xj0，代入非标准型234

变换举例：解:令z`=-z，x3=x`3-x``3，并引入剩余变量x4和松弛变量x5、x6，将其代如原数学模型，则原模型转换为如下标准形式例题将下列线性规划模型化为标准形式，写出相应的矩阵表达式，并写出相应的技术系数矩阵A、资源向量b、价格系数向量C、决策变量X，指出其松弛变量和剩余变量。

minZ=-x1-2x2+x3-x4-4x5+2x6x1+x2+x3+x4+x5+x6≤62x1-x2-2x3+x4≤-4x3+x4+2x5+x6=

4X1,x2,x3≥0,x4,x5≤0,x6正负不限S.t.maxZ`=x1+2x2-x3+x`4+4x`5-2x`6+2x``6+0x7+0x8x1+x2+x3-x`4-x`5+x`6-x``6+x7=6-2x1+x2+2x3+x`4

=4x3-x`4-2x`5+x`6-x``6-x8=4x1,x2,x3,x`4,x`5,x`6,x``6,x7,x8≥0S.t.解：令Z`=-Z,x`4=-x4,x`5=-x5,x6=x`6-x``6

minZ=-x1-2x2+x3-x4-4x5+2x6x1+x2+x3+x4+x5+x6≤62x1-x2-2x3+x4=

-4x3+x4+2x5+x6≥4X1,x2,x3≥0,x4,x5≤0,x6正负不限S.t.

maxZ`=CXS.t.AX=bX≥0X=[x1,x2,x3,x`4,x`5,x`6,x``6,x7,x8]TC=[1,2,-1,1,-4,-2,2,0,0]b=[6,4,4]T

A=111-1-11-110-212100000001-1-21-101其矩阵形式表示为：其中：maxZ`=x1+2x2-x3+x`4+4x`5-2x`6+2x``6+0x7+0x8x1+x2+x3-x`4-x`5+x`6-x``6+x7=6-2x1+x2+2x3+x`4

=4x3-x`4-2x`5+x`6-x``6-x8=4x1,x2,x3,x`4,x`5,x`6,x``6,x7,x8≥0S.t.松弛变量：x7剩余变量：x8教科书:P31练习（1）课堂操练要求：将其化为标准形式，写出相应的矩阵表达式，并写出相应的技术系数矩阵A、资源向量b、价格系数向量C、决策变量X，指出其松弛变量和剩余变量。教科书:P31练习（2）课外作业要求：将其化为标准形式，写出相应的矩阵表达式，并写出相应的技术系数矩阵A、资源向量b、价格系数向量C、决策变量X，指出其松弛变量和剩余变量。线性规划问题标准型的矩阵形式：

MaxZ=CX

s.t.AX=bX0

a11a12….a1nb1A=a21a22….a2nb

=b2………am1am2….amnbm一、关于标准型解的若干基本概念

a11a12…….a1nA=a21a22…….a2n……………am1am2……..amnP1,P2,…

Pnx1,x2,

…..,xn=(P1,P2,…

Pn)假若标准型有n个变量，m个约束行且m<=n“基”的概念在标准型中，系数矩阵有n列，即

A=(P1,P2,…,Pn)A中线性独立的m列，构成该标准型的一个基，即

B=(P1,P2,…,Pm)，|B|0

P1,P2

,…,Pm称为基向量，

其余的Pm+1,Pm+2

,…,Pn称为非基向量与基向量对应的变量称为基变量，记为

XB=(x1,x2,…,xm)T，其余的变量称非基变量，记为XN=(xm+1,xm+2,…,xn)T

，故有

X=(XB,XN)T

举例说明一000032020001010x1x2x4x3001300321=目标函数约束条件行列式|B1|≠0x1,x2,x3为基变量,x4为非基变量p1,p2,p3为基向量,p4为非基向量B1为A的基矩阵A=B1=标准型的线性规划问题举例说明二000030020011010x1x2x4x3001300321=目标函数约束条件行列式|B2|=0x3,x4会不会同时为基变量？B2为A的基矩阵？A=B2=标准型的线性规划问题线性规划的基矩阵、基向量、非基向量、基变量、非基变量=目标函数约束条件行列式≠0基矩阵右边常数Cnm可行解满足约束条件和非负条件的解X称为可行解，基解(基本解、基础解)令非基变量

XN=0，求得基变量

XB的值：

AX=b令A=(B,N),X=(XB,XN)

TBXB+NXN=b令

XN=0得XB=B1b

因此X=（B1b，0）T称为基本解(基解)基可行解（基本可行解、基础可行解）基解

X

的非零分量都0时，称为基本可行解，否则为基本非可行解基本可行解的非零分量个数<

m

时，称为退化解最优解：使目标函数达到最优的可行解

线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解退化解最优解基、可行基、最优基

可行解、基解和基可行解举例说明

系数矩阵:A=11001101001001x1x2x3x4x5

系数矩阵:A=11001101001001x1x2x3x4x5100010001

B=x3x4x5211100x1x2

N=A=(B,N)令非基变量X1=0,X2=0得：X3=10,X4=8,X5=7因此可得一基解：X=(0,0,10,8,7)T行列式|B|≠0B为A的基矩阵知识点总结n个变量，m个约束条件的标准形的线性规划问题（秩为m）中最多有（

Cnm

）个基矩阵n个变量，m个约束条件的标准形的线性规划问题（秩为m）中最多有（

Cnm

）个基解n个变量，m个约束条件的标准形的线性规划问题（秩为m）的一个基矩阵B中有（m

）个基变量，（n-m）个非基变量n个变量，m个约束条件的标准形的线性规划问题（秩为m）的最优解中最多有（

m

）个非零分量n个变量，m个约束条件的标准形的线性规划问题（秩为m）的最优解中最少有（

n-m

）个零分量定理1.1

线性规划问题的可行解集是凸集。（即连接线性规划问题任意两个可行解的线段上的点仍然是可行解。)定理1.2

线性规划问题的可行解x为基可行解的充分必要条件是：x的非零分量所对应的系数矩阵A的列向量线性无关。定理1.3

线性规划问题的可行解集D中的点x是顶点的充分必要条件是：x是基础可行解。二、线性规划问题解的基本性质推论1.1：可行解集D中的顶点个数是有限的。推论1.2

若可行解集D有界，则线性规划问题的最优解，必定在D的顶点上达到。注1：若可行解集D无界，则线性规划问题可能有最优解，也可能无最优解。若有最优解，也必在顶点上达到。注2：有时目标函数也可能在多个顶点上达到最优值。这些顶点的凸组合也是最优值。（有无穷多最优解）基本思想：从可行域中某一个顶点开始,判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解，直到找到一个顶点为其最优解，或者能判断出线性规划问题无最优解为止。这里，可行域的顶点已经不再象图解法中那样直观了，在单纯形法中的可行域的顶点就是基本可行解，找到的第一个可行域的顶点叫做初始基本可行解。三、单纯形法的基本思路和原理单纯形法的基本步骤：初始概念回顾前提是标准型的线性规划问题，假设n个变量，m个约束条件基（基矩阵）、可行基、最优基基解、基可行解、最优解、退化解决策变量、松弛变量、剩余变量、基变量m、非基变量n-m基向量m、非基向量n-m系数矩阵A：m*n基矩阵B:m*m最多有Cnm个基解:非零分量<=m（一）、单纯形法的基本思路首先，将线性规划问题化为标准形式；其次，寻找一个初始可行基，为确保基为可行基，我们这里以单位矩阵作为初始可行基，即可求出初始基可行解第三，判断该可行解是否是最优解，如果是，明确解的类型，结束；如果不是，继续换基迭代，找出使目标函数更优的基可行解。第四，返回第三，循环往复直到找出最有解Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0x1x2x3x4x5x3x4x5非奇异子阵，做为一个基（可行基）基变量:x3x4x5非基变量:x1x2例1maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.可见，单位矩阵作为初始可行基，基变量在目标中的系数为0将基变量用非基变量线性表示，即x3=8-x1x4=12-2x2x5=36-3x1-4x2

令非基变量x1=0，x2=0，找到一个初始基可行解：

x1=0，

x2=0，x3=8，x4=12，

x5=36即X0=(0,0,8,12,36)T一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0

。1.求初始基可行解

确定进基变量

Z=3x1+5x2

+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36从目标函数Z=3x1+5x2+0x3+0x4+0x5可知：非基变量x1和x2的系数均为正数，生产哪种产品都会增加利润。

增加单位产品对目标函数的贡献，这就是检验数的概念。因为x2的系数大于x1的系数，即生产单位乙产品比甲产品利润更高一些，对目标函数的贡献大，故应优先多生产乙产品。（最大检验数原则），把非基变量x2换成基变量，称x2为进基变量。同时为保证基变量的个数必须确定一个离基变量。（在选择离基变量时，一定保证所有的变量是正的）（最小比值原则）2.第一次迭代

бX0=(0,0,8,12,36)T确定离基变量基变量用非基变量线性表示x3=8–x1x4=12-2x2

x5=36-3x1-4x2保持原非基变量x1=0，x2变成基变量时应保证x3,x4,,x5非负，即有2.第一次迭代（续）x3=8≥0x4=12-2x2≥0x5=36-4x2≥0x2≤12/2x2≤36/4

x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥02.第一次迭代（续）主行主列主元x1+0x2+x3=82x2+x4=123x1+4x2+x5=36

进基变量x2所在列为主列，离基变量x4所在行为主行主行和主列交叉项的系数为主元素

为了确保新构成的基矩阵为可行基矩阵，将x2的系数列向量P2化为单位的，即主元素变为1，主列中其它项的系数化为0，使其与其它基变量的系数向量组成为单位矩阵基变换进行初等变换，变主元为1，主列为单位列向量。2.第一次迭代（续）x1+x3=8

x2+1/2x4=63x1+-2x4+x5=12

x1+x3=8

x2+1/2x4=6

3x1+-2x4+x5=12

x1+0x2+x3=82x2+x4=123x1+4x2+x5=36Z=3x1+5x2+0x3+0x4+0x5

x1+x3=8

x2+1/2x4=63x1+4x2+x5=36Z=3x1+5x2+0x3+0x4+0x5Z=3x1+5x2+0x3+0x4+0x5Z=3x1+0x2+0x3–5/2x4+0x52.第一次迭代（续）将基变量用非基变量线性表示，即x3=8–x1x2=6-1/2x4

x5=12-3x1+4x4令非基变量x1=0，x4=0，找到另一个基可行解

x1=0，

x2=6，x3=8，x4=0，

x5=12即X1=(0,6,8,0,12)T原目标函数Z=30这个方案比前方案好，但是否是最优？确定进基变量3.第二次迭代

第一次迭代结果

x1+x3=8

x2+1/2x4=63x1+-2x4+x5=12

Z=3x1+0x2+0x3–5/2x4+0x5=30目标函数Z系数变化为:Z=3x1+0x2+0x3–5/2x4+0x5=-30非基变量x1的系数1=3（检验数）为正数，确定x1为进基变量。X4仍然为非基变量确定离基变量3.第二次迭代（续）x3=8-x1≥0x2=6≥0

x5=12-3x1≥0x1≤8/1x1≤12/3基变量用非基变量线性表示

x3=8–x1x2=6-1/2x4x5=12-3x1+4x4保持原非基变量x4=0，x1变成基变量时应保证x2,x3,,x5非负，即基变换变主元为1，主列为单位列向量。3.第二次迭代（续）

x1+x3=8

x2+1/2x4=6

x1+-2/3x4+1/3x5=4

Z=3x1+0x2+0x3–5/2x4+0x5

x3+2/3x4-1/3x5=4

x2+1/2x4=6x1+-2/3x4+1/3x5=4

Z=3x1+0x2+0x3–5/2x4+0x5x3+2/3x4-1/3x5=4

x2+1/2x4=6x1+-2/3x4+1/3x5=4

Z=0x1+0x2+0x3-1/2x4-x5

1x1+x3=8

x2+1/2x4=63x1+-2x4+x5=12

Z=3x1+0x2+0x3–5/2x4+0x53.第二次迭代（续）将基变量用非基变量线性表示，即x3=4–2/3x4+1/3x5x2=6-1/4x4x1=4+2/3x4-1/3x5

令非基变量x4=0，x5=0，又找到一个基可行解

目标函数Z系数变化为:

Z=42+0x1+0x2+0x3-1/2x4-x5=42x1=4，

x2=6，x3=4，x4=0，

x5=0即X2=(4,6,4,0,0)T检验数σj非正，得最优解X*=(4,6,4,0,0)T，Z*=42单纯形法的几何意义x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)DX0=(0,0,8,12,36)TX1=(0,6,8,0,12)TX1=(4,6,4,0,0)TmaxZ=3x1+5x2+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36

为了计算步骤更加清晰，以下列表格的方式求解：CjθiCBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000

35000-12/2=636/4=9检验数j81010060101/2012300-21x3x2x5050

300-5/208-4CjθiCBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000

35000-12/2=636/4=9CjθiCBXBb检验数jx1x2x3x4x53500081010060101/2012300-21x3x2x5050

300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053

000-1/2-1原问题具有唯一最优解

:X*=(4,6,4,0,0)T，Z*=42c1x10c2x20CT=……X=..….0=……cnxn0

并且r(A)=m<n.（二）、单纯形法的基本原理线性规划标准型的矩阵形式：MaxZ=CXs.t.

AX=b

X≥0

a11a12….a1nb1A=a21a22….a2nb

=

b2……am1am2….amn

bmAX=bZ=CX设A=（B,N）（B为一个基）

XT=(XB,XN)TC=(CB,CN)则有：AX=（B,N）(XB,XN)T=B

XB+N

XN=b移项得：B

XB=b-N

XN因为B为基,故有XB=B-1b-B-1NXN

-----------（1）又因为Z=CX=

(CB,CN)(XB,XN)T=CBXB+CNXN

=CB（B-1b-B-1NXN）+CNXN=

CBB-1b+(CN-

CBB-1N)

XN--------（2）常数项非基变量的系数，即检验数基变量的系数为0AX=bZ=CXXB=B-1b-B-1NXN-----------（1）Z=CBB-1b+(CN-

CBB-1N)

XN-----------（2）由（1）令非基变量XN=0，则有：XB

=B-1b所以XT=(XB,XN)T=（B-1b,0)T

代入（2），得到：

Z=

CBB-1b目标函数中非基变量的系数C

N-

CBB-1N即为检验数由（2）可知道：当≤0时，Z没有增大的可能了，CBB-1b就是原问题的最优值。一个基可行解CjCBXBb检验数jx1x2x3x4x53500081010060101/2012300-21x3x2x5050

300-5/20单纯形表格中的检验数有两种方法得到：一种是迭代中的初等变换，一种是利用公式计算；初始单纯形表中的检验数只能用公式计算方法得到；中间单纯形表两种方法都可以，一般先采用迭代方法得到，再使用公式计算进行验证，可以确保相邻两张表中数据的准确无误。j=Cj-CBB-1pj=Cj-CBp`j

（三）、表格形式的单纯形法

利用单纯形表的方法求解线性规划——重点.

此项内容是本章的重点，学习中应注意掌握表格单纯形法求解线性规划问题的基本过程。要通过读懂教材内容以及大量练习来掌握。表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。1、单纯形法表CjC1C2…Cj…CnθiCBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1n1CB2xB2b2a21a22…a2j…a2n2………………………CBnxBnbmam1am2…amj…amnmj→12…j…n①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。③计算各非基变量xj的检验数j=Cj-CBPj′，若所有j≤0，则问题已得到最优解（唯一最优或无穷多最优解），停止计算，否则转入下步。④在大于0的检验数中，若某个k所对应的系数列向量Pk≤0，则此问题是无界解，停止计算，否则转入下步。⑤根据max{j｜j＞0}=k原则，确定xk为换入变量(进基变量)，再按规则计算：=min{bi/aik|aik＞0}=bl/aik

确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。⑥以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第③步。2、单纯形法的计算步骤

课堂举例用单纯形法求解下述线性规划问题首先化为标准形如下：+0x3+0x4CjθiCBXBb检验数jx1x2x3x4x3x498001050034105201105009/38/5CjθiCBXBb检验数jx1x2x3x4x3x121/501010500014/51-3/512/501/5010-28/5CjθiCBXBb检验数jx1x2x3x4x2x13/251010500015/14-3/1410-1/72/700-5/14-25/1413/28/2原问题具有唯一最优解

:

maxZ=12x1+8x2+5x33x1+2x2+x3≤20x1+x2+x3≤1112x1+4x2+x3≤48x1,x2,x3≥0课堂作业用单纯形法求解下列问题:minZ=x1+2x2-x32x1+2x2-x3≤4X1-2x2+2x3≤8x1+x2+x3≤5x1,x2,x3≥0maxZ=4x1+x2x1+3x2≤74X1+2x2≤9x1,x2≥0课后作业用单纯形法求解下列问题:课堂例题1用单纯形法求解下列线性规划问题

CjθiCBXBb检验数jx1x2x3x4x5x62-11000x4x5x600060311100101-1201060/310/120/12011-1001

2-11000+0x4+0x5+

0x6CjθiCBXBb检验数jx1x2x3x4x5x62-11000x4x1x60203004-51-30101-1201030/4--10/21002-30-11

01-30-20CjθiCBXBb检验数jx1x2x3x4x5x62-11000x4x1x202-1100011-1-215101/201/21/2501-3/20-1/21/2

00-3/20-3/2-1/2原问题具有唯一最优解

:目标函数为Max的标准型线性规划问题的单纯性表格中唯一最优解的判断标准如下:当所有非基变量的检验数都＜0时当所有非基变量的检验数都≤0且存在某个非基变量xj的检验数为0，而它所对应的系数Pj全部≤0maxZ=

40x1+45x2+25x32x1+x2+x3≤1003x1+3x2+2x3≤120x1,x2,x3≥0S.t.maxZ=

40x1+45x2+25x3+0x4+0x52x1+x2+x3+x4=1003x1+3x2+2x3+x5=120x1,x2,x3,x4,x5≥0S.t.解:首先，化为标准型:其次，列出初始单纯形表格:课堂例题2CjCBXBb检验数jx1x2x3x4x540452500x4x5001002311012033201

40452500100/3120/3CjCBXBb检验数jx1x2x3x4x540452500x2x5450100/32/311/31/3020101-11

10010-150100/220/1CjCBXBb检验数jx1x2x3x4x540452500x2x145402001-1/31-2/320101-11

000-5-10CjCBXBb检验数jx1x2x3x4x540452500x2x3452580/31/3102/3-1/320101-11

000-5-10最优解为：x*=(20,20,0)T最优值为：Z*=1700最优解为：x*=(0,80/3,0)T最优值为：Z*=1700有两个最终单纯形表，所以有两个最优解：

x1*=(20,20,0)T

x2*=(0,80/3,0)T

最优值为：Z*=1700

因此原问题具有无穷多个最优解目标函数为Max的标准型线性规划问题的单纯性表格中无穷多最优解的判断标准如下:

当所有非基变量的检验数都≤0且存在某个非基变量xj的检验数为0，而它所对应的系数Pj不全≤0（即存在＞0的系数）解

:+0x5+0x6+

0x7课堂例题3CjCBXBb检验数jx1x2x3x4x5x6x762108000x5x6x70002056-4-4100253-328010--25/210/1104-213001

62108000θiCjCBXBb检验数jx1x2x3x4x5x6x762108000x5x6x300106021-2081045-510201-2--5/1--104-213001

-34220-2200-10θiCjCBXBb检验数jx1x2x3x4x5x6x762108000x5x2x30210701100121205-510201-220-601702-3

7600-660-2234原问题具有无界解

目标函数为Max的标准型线性规划问题的单纯性表格中无界解的判断标准如下:

当存在某个非基变量的检验数＞

0且它所对应的系数Pj全部≤0原问题解的类型的判断

对于所有约束条件都是≤的线性规划问题的解的类型有三种：唯一最优解无穷多最优解无界解CjCBXBb检验数80-512x3x10331-3010110-3x1x2x3x43200原问题具有无界解判断原问题解的类型(一)CjCBXBb检验数jx1x2x3x4x535000x3x2x105340012/3-1/360101/204100-2/31/3

000-1/2-1原问题具有唯一最优解

:X*=(4,6,4,0,0)T，Z*=42判断原问题解的类型(二)CjCBXBb检验数jx1x2x3x4x540452500x2x145402001-1/31-2/320101-11

000-5-10判断原问题解的类型(三)原问题具有无穷多个最优解CjCBXBb检验数jx1x2x3x4x54045-2500x2x145402001-1/31-2/32010-1/4-11

000-5-10判断原问题解的类型(四)原问题具有唯一最优解例：分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基本可行解对应图解法中可行域的哪一顶点.课堂练习由图知：单纯形法：化为标准形如下：CjθiCBXBb检验数jx1x2x3x410500x3x4009341085201

10500

9/38/5CjCBXBb检验数jx1x2x3x410500x3x4009341085201

10500

CjCBXBb检验数jx1x2x3x410500x2x15103/2015/14-3/14110-1/72/7

00-5/14-25/14

最终单纯形表初始单纯形表原问题具有唯一最优解

:①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。③计算各非基变量xj的检验数j=Cj-CBPj′，若所有j≤0，则问题已得到最优解（唯一最优或无穷多最优解），停止计算，否则转入下步。④在大于0的检验数中，若某个k所对应的系数列向量Pk≤0，则此问题是无界解，停止计算，否则转入下步。⑤根据max{j｜j＞0}=k原则，确定xk为换入变量(进基变量)，再按规则计算：=min{bi/aik|aik＞0}=bl/aik

确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。⑥以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第③步。单纯形法的计算步骤

CjC1C2…Cj…Cn比值CBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1n1CB2xB2b2a21a22…a2j…a2n2………………………CBmxBmbmam1am2…amj…amnm检验数j12…j…nbi,xj≥0(i=1,2,…,m;j=1,2,…,n)Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0x1x2x3x4x5x3x4x5例1maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.分析CjCBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000

35000Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0初始单纯形表格Z=3x1+5x2+0x3+0x4+0x5x1-x3=82x2-x4=123x1+4x2-x5=36x1,x2,x3,x4,x5≥0例1maxZ=

3x1+5x2x1

≥82x2

≥123x1+4x2

≥36x1≥0,x2≥0S.t.分析úúúûùx1x2x3x4x5êêêëé=-100-100043020-101Aúúúûùêêêëé=100010001B100010001x6x7x8x6x7x8人工变量+x6

=8+x7

=12+x8=36x6,x7,x8

≥0CjCBXBb检验数jx1x2x3x4x5x6x7x8810-100100x6x7x8x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0初始单纯形表格部分+x6

=8+x7

=12+x8=36x6,x7,x8

≥012020-10010363400-1001Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2-x4=123x1+4x2-x5=36x1,x2,x3,x4,x5≥0x1x2x3x4x5例1maxZ=

3x1+5x2x1

≤82x2

≥123x1+4x2

≥36x1≥0,x2≥0S.t.分析úúúûùêêêëé=-100-100043020

101Aúúúûùêêêëé=100010001B100100x6x7x3x6x7人工变量=8+x6

=12+x7=36x6,x7≥0CjCBXBb检验数jx1x2x3x4x5x6x781010000x3x6x7x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0初始单纯形表格部分12020-1010363400-101=8+x6

=12+x7=36x6,x7≥0Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2-x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0x1x2x3x4

x5例1maxZ=

3x1+5x2x1

≤82x2

≥123x1+4x2

≤

36x1≥0,x2≥0S.t.分析úúúûùêêêëé=100-100043020

101Aúúúûùêêêëé=100010001B010x6x3x6x5人工变量=8+x6=12=36x6≥0CjCBXBb检验数jx1x2x3x4x5x68101000x3x6x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0初始单纯形表格部分12020-10136340010=8+x6

=12=36x6≥0单纯形法的进一步讨论主要讨论初始基本可行基不明显时常用的方法，要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题。考虑一般问题：

bi>=0i=1,…,m

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0此时若系数矩阵中无单位矩阵，则可以引入人工变量。Maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn+

xn+1

=b1a21x1+a22x2+…+a2nxn

+

xn+2

=b2s.t.…

am1x1+am2x2+…+amnxn+xn+m

=bm

x1，x2，…，xn≥0此时人工变量xn+1、xn+2、….xn+m

的系数向量构成一个m*m的单位矩阵，因此可以作为初始可行基。但是由于人工变量在原问题的解中是不能存在的，因此应尽快被迭代出去，为此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定.两种方法大M法两阶段法s.t.a11x1+a12x2+…+a1nxn

+xn+1

=b

a21x1+a22x2+…+a2nxn

+

xn+2

=b2

…………

…………

am1x1+am2x2+…+amnxn

+xn+m

=bm

xj≥0（j=1,2,…,n,n+1,…,n+m）Maxz=c1x1+c2x2+…+cnxn-M(xn+1+xn+2+…+xn+m

)1、大M法例：用大M法求解下列问题:maxz=3x1-x2-x3s.t.x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1,x2,x3≥0maxz=3x1-x2-x3+0x4+0x5x1-2x2+x3+x4=11-4x1+x2+2x3–x5=3s.t.2