第一章 线性规划及单纯形法

6.6单纯形法小结Drawingontheexampl,thetwoaxisinterceptsa
replotted.2、求初始基可行解并进行最优性检验Cj比值CBXBb检验数?jx1x2x
3x4x53500081010012020103634001x3x4x5
000035000令非基变量x1=0，x2=0，找到一个初始基可行解：x1=0，x2=0，x3=8，
x4=12，x5=36，σj＞0，此解不是最优（因为z=3x1+5x2+0x3+0x4+0x5)
即X0=(0,0,8,12,36)T，此时利润Z=03、寻找另一基可行解Cj比值CBXBb检验数?jx1
x2x3x4x53500081010012020103634001x3x
4x5000035000-12/2=636/4=9主元首先确定入基变量再确定出
基变量检验数?j81010060101/2012300-21x3x2x5050
-30300-5/20Cj比值CBXBb检验数?jx1x2x3x4x5350008
1010012020103634001x3x4x5000035000-
12/2=636/4=9令x1=0，x4=0，得x2=6，x3=8，x5=12，即得基可行解X1=(0,6,8,0,1
2)T此时Z＝30σ1=3＞0，此解不是最优迭代4、寻找下一基可行解Cj比值CBXBb检验数?
jx1x2x3x4x53500081010060101/2012300-2
1x3x2x5050-30300-5/208-4检验数?j40012/3-1/36
0101/204100-2/31/3x3x2x1053-42000-1/2-1令x
4=0，x5=0，得x1=4，x2=6，x3=4，即X0=(4,6,4,0,0)T?j＜0最优解:X=(4,6,4,0,0
)T最优值:Z=42小结：单纯形表格法的计算步骤①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基
，建立初始单纯形表。③计算各非基变量xj的检验数?j=Cj-CBPj′，若所有?j≤0，则问题已得到最优解，停止计算，否则转入
下步。④在大于0的检验数中，若某个?k所对应的系数列向量Pk′≤0，则此问题是无界解，停止计算，否则转入下步。⑤根据max
{?j｜?j＞0}=?k原则，确定xk为换入变量(进基变量)，再按?规则计算：?=min{bi′/aik′|aik′＞0}=bl
′/alk′确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。⑥以aik′为主元素进行迭代，把xk
所对应的列向量变为单位列向量，即aik′变为1，同列中其它元素为0，转第③步。单纯形法的进一步讨论一、大M法二、两阶
段法--人工变量法人工变量法问题：线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始
可行基？约束条件中加入人工变量设线性规划问题的标准型为：加入人工变量,构造初始可行基.系数矩阵为单
位矩阵，可构成初始可行基。约束条件已改变，目标函数如何调整？“惩罚”人工变量！（1）大
M法（2）两阶段法一、大M法人工变量在目标函数中的系数为-M,其中，M为任意大的正数。目标函数中添加
“罚因子”-M（M是任意大的正数）为人工变量系数，只要人工变量>0，则目标函数不可能实现最优。例:求解线性规划问题
一、大M法一、大M法解:加入松弛变量和剩余变量进行标准化,加入人工变量构造初始可行基.求解结
果出现检验数均非正时：若基变量中含非零的人工变量，则无可行解；否则，有最优解。一、大M法用单纯
形法求解（见下页）。1-21-412-201
3-6MM-13M-13-1-1x1x2x30
x411-Mx63-Mx71Cj-Zj
CjCBXBb100-100
0-M00x4x5113/21
0010010
0-M-Mx6x7表1（初始单纯形表）一、大M法（单纯形法求解）3
-20010-2011M-103
-1-1x1x2x30x410-Mx61
-1x31Cj-ZjCjCBXBb1
00-1000-M00
x4x510-11
-20101-3M-M-Mx6x7一、大
M法（单纯形法求解）表2300010-2
011003-1-1x1x2x3
0x412-1x21-1x31Cj-Zj
CjCBXBb1-20-1
000-100x4x54
i2-51-2011-M
-1-M-M-Mx6x7表3一、大M法（单纯形法求解）1
0001000100
03-1-1x1x2x33x14-1x2
1-1x392CjCB
XBb1/3-2/30-12/3-4/3-1/3-1/3
00x4x52/3-5/3
1-24/3-7/31/3-M2/3-M-M-Mx6x7
表4一、大M法（单纯形法求解）最优解为目标函数值z=2检验数均非正，此为最终单纯形表M在计算机上
处理困难。分阶段处理——先求初始基，再求解。二、两阶段法二、两阶段法第一阶段:构造如下的线性规划问题并求解人工变
量的系数矩阵为单位矩阵，可构成初始可行基。目标函数仅含人工变量，并要求最小化。若其最优解的目标
函数值不为0，也即最优解的基变量中含有非零的人工变量，则原线性规划问题无可行解。第二阶段：在第一阶段求解的最终单纯形表中
去掉人工变量，还原目标函数系数，计算检验数，并列出第二阶段的初始单纯形表。用单纯形法继续往下求解即可。二、两阶段法下面举例说明
，仍用大M法求解过的例子。例：二、两阶段法二、两阶段法构造第一阶段问题并求解解：二、两阶段法—（第一阶
段、求minω）1-21-412-201
-613000x1x2x30x4
11-1x63-1x71CiCB
XBb1000-11000
0-1000-1--1x4x5x60
1103/2110-1x7
i表1-1--211--3
-1x73-20010-2
01010000x1x2x3
0x410-1x610x31
CiCBXBb1000-110
000-1000-1x4x5x6二
、两阶段法—（第一阶段、求minω）表2-54-2-1-
-1-1x730001
0-201000000x1x
2x30x4120x210x31
CiCBXBb1-220-11
00000-100-1x4x5
x6二、两阶段法—（第一阶段、求minω）表3：最终单纯形表第二阶段不含人工变量且ω=0二、两阶段法
第二阶段去掉第一阶段最终单纯形表中的人工变量，还原目标函数系数，列出第二阶段初始单纯形表。300
010-2013-1-1x1x2
x30x412-1x21-1x31
CiCBXBb1-220-11
00000x4x5100
0-1二、两阶段法10001000
13-1-1x1x2x33x14-1
x21-1x39CiCBXB
b1/3-2/30-12/3-4/300x4
x5第二阶段000-1/3-1/3最优解为目标函数值z=2
单纯形法计算中的几个问题1、目标函数极小化时解的最优性判断只需用检验数作为最优性的标志。
2、无可行解的判断当求解结果出现所有时，如基变量仍含有非零的人工变量（两阶段法求
解时第一阶段目标函数值不等于0），则问题无可行解。退化基可行解中存在基变量=0的解——退化解换入变
量和换出变量的Bland规则选择中下标最小的非基变量为换入变量,这里:当按规则计算存在两
个和两个以上最小比值时,选下标最大的基变量为换出变量。单纯形法计算中的几个问题9—8—7—6—5—4—
3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1
+2x2?84x1?16
4x2?12x1、x2?0|
| | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2=84x1=164x2=
12可行域9—8—7—6—5—4—3—2—1—0x2目标函数M
axZ=2x1+3x2约束条件x1+2x2?84x1
?164x2?12
x1、x2?0| | | | | | | | |1 2 3 4 5 6 7 8 9
x1x1+2x2=84x1=164x2=12BCDEA2x1+3x2=69—8—
7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2
约束条件x1+2x2?84x1?16
4x2?12
x1、x2?0| | | | | | | | |1 2 3 4 5 6 7 8 9x1BCDEA最优解
(2,4)线性规划解的几种可能结果(a)唯一最优解x26—5—4—3—2—1—0
| | | | | | | | |1 2 3 4 5 6 7 8 9x1(b)无穷多最优解6—5—4—3
—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1(c
)无界解MaxZ=x1+x2-2x1+x2?4x1-
x2?2x1、x2?0x2x1(d)无可行解
MaxZ=2x1+3x2x1+2x2?84x1
?164x2?12-2x1
+x2?4x1、x2?0此模型可行域为空。图解法的几点结论:1、
可行域是非空有界或无界的凸多边形,也可能为空集。2、可行域为有界时，一定有最优解1）有唯一最优解2）有两个以上的最优解（也必
有无穷多个最优解）3、可行域为无界时，可能有最优解，也可能无最优解1）有唯一最优解2）有两个以上的最优解（也必有无穷多个最优
解）3）无界解4、可行域为空集，一定没有最优解若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最
优解，则其连线上的所有点都是最优解。§3单纯形法原理3-1预备知识：基本概念凸集：顶点:若K是凸集，X∈K；若
X不能用不同的两点的线性组合表示为：则X为K的一个顶点。凸集顶点定理1:若线性规
划问题存在可行域,则其可行域:是凸集.3-2基本定理证明:只要验证X在D中即可
引理：线性规划问题的可行解X为基可行解的充要条件是X的正分量对应的系数列向量是线性独立的。定理3：若可行域有界，线性规划问题的
目标函数一定可以在其可行域的顶点上达到最优。定理2：线性规划问题的基可行解X对应于可行域D的顶点。证明：反证法。分两步。
几点结论：线性规划问题的可行域是凸集。若线性规划问题有最优解，一定存在一个基可行解是最优解。基可行解与可行域的顶点一一对应，
可行域有有限多个顶点。最优解必在顶点上得到。3-3初始基可行解的确定因线性规划问题如果存在最优解，一定可以在基可行解中找到
。因此单纯形法的基本思路是：先找到一个初始基可行解，如果不是最优解，设法转换到另一个基可行解，并使目标函数值不断增大，一直到找到最
优解为止。如何找到初始基可行解？第一步需先找到一个初始基。当约束条件均为“≤”时；每个方程加一个松弛变量，形成一个单位阵。给
定线性规划问题：在第i个约束条件上加入松弛变量xsi，化为标准形式：经过整理，重新对各变量进行编号，可得下列方程组：显然，得
到一个m×m的单位阵，可作为初始基。移项得x1=b1-a1,m+1xm+1-…-a1nxn
x2=b2-a2,m+1xm+1-…-a2nxn ……xm=
bm-am,m+1xm+1-…-amnxn令xm+1=xm+2=…=xn=0,可得：xi=bi (i=1,2,…
,m)又因bj≥0，所以得到一个初始基可行解X=(x1,x2,…,xm,0,…,0)T=(b1,b2,…,bm,0,…,0)T
当约束条件有≤、≥、＝时，加入人工变量，形成一个单位阵。（P29例6）3-4基可行解的转换（此部分内容见P2
2.）3-5最优解检验和解的判断线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，为此需要建
立解的判别准则。一般情况下，经过迭代后，有下式成立。非基变量检验数将上式式代入目标函数，整理后得最优解的判别定理（1）当
所有的非基变量的检验数σj≤0时,表明现有基可行解的目标函数值已达到最大，所以目前解为最优解。（2）当所有的的非基变量的检验数σ
j≤0时，又对某个非基变量xj的检验数σj=0，线性规划问题有无穷多最优解。（3）如果存在某个非基变量的检验数σj>0，且有ai
j≤0，那么该线性规划问题具有无界解.§4单纯形法的计算步骤第一步，列出初始单纯形表，求出线性规划的初始基可行解。当约束条
件均为“≤”时；每个方程加一个松弛变量，形成一个单位阵。当约束条件有≤、≥、＝时，加入人工变量，形成一个单位阵。Cjc1
…cm…cj…cnCBxBbx1…xm…xj…xnc1x1b110…a1j…a1n
c2x2b200…a2j…a2n…………….……………cmxmbm01…amj
…amnσj=cj-zj0…0……找出初始基，建立初始单纯形表
1000

检验数单纯形表结构—24/65/1C已知第二步，进行最优
性检验。利用最优解判别定理进行最优性检验。第三步，从一个基可行解转换到另一个使目标函数值更大的基可行解，列出新的单纯形表。确
定换入变量（进基变量）；确定换出变量（出基变量）。重复第二、第三步，直到计算终止。单纯形法求解线性规划问题的实例解：化标准
型2
1000
015
051000
2462010
051100
121
000—24/65/1主元化为1主列单位向量
换出换入列初始单纯形表（单位矩阵对应的变量为基变量）正检验数中最大者对应的列为主列最小的值
对应的行为主行
21000
0
15051002
412/601/6
00104/60
-1/6101/3
0-1/3015/524/26/405
22/6+04/61-2/3=换基（初等行变换，主列化为单位向量，
主元为1）检验数>0确定主列最小确定主列主元
21000

015/20015/4-1
5/227/2100
1/4-1/213/201
0-1/43/20
00-1/4-1/2检验数<=0最优解为X=
(7/2,3/2,15/2,0,0)目标函数值Z=8.527/213/2+015/28.5换基
（初等行变换，主列化为单位向量，主元为1）maxZ=3x1+5x2x1≤8
2x2≤123x1+4x2≤36Cj比值
CBXBb检验数?jx1x2x3x4x5350008101001202010
3634001x3x4x5000035000maxZ=3x1+5x2+0x3+0x4
+0x5x1+x3=8
2x2+x4=12
3x1+4x2+x5=36标准型基变量x3,x4,x5，
1、建立初始单纯形表非基变量x1,x2上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第一章线性规划及单
纯形法张林刚经济与管理学院课件下载邮箱：[e-mail]密码：2012teach§1一般线性
规划问题的数学模型1-1问题的提出企业的生产和经营管理过程中，经常碰到如何合理安排人力、物力、财力等资源，并使所获收益最大化
的问题。这就是所谓的规划问题。而运筹学首先要解决的问题是如何将生产经营和管理过程中的决策问题转化成数学模型。【例】某机器厂生产
Ⅰ、Ⅱ两种产品，这两种产品都要分别在A、B、C三种不同设备上加工。按工艺资料规定，生产每件产品Ⅰ需占用各设备分别为2h、4h、0h
，生产每件产品Ⅱ需占用各设备分别为2h、0h、5h。已知各设备计划期内用于生产这两种产品的能力分别为12h、16h、15h，又知每
生产一件产品Ⅰ企业获得2元利润，每生产一件产品Ⅱ企业获得3元利润。问该企业应安排生产两种产品各多少件，使总的利润最大。假定x1和
x2分别表示Ⅰ、Ⅱ两种产品计划期内的产量。如果在规划问题的数学模型中，决策变量为可控的连续变量，目标函数和约束条件都是线性的，这
类模型称为线性规划模型。目标函数：约束方程：【例】环境保护问题设：化工厂1每天处理的污水量为x1万立方米；化工厂2每天
处理的污水量为x2万立方米建模型之前的分析和计算整理得到本问题的数学模型为：1-2线性规划问题的数学模型线性规划问题的数
学模型的组成要素：决策变量目标函数约束条件线性规划问题的一般模型线性规划问题的简化模型模型的向量形式用矩阵形式表示的
模型A为约束方程的系数矩阵1-3线性规划问题的标准形式目标函数最大约束条件等式决策变量非负可简写为一般线性规划问题
的标准化过程minZ=CX等价于maxZ’=-CX“?”约束：加入非负松驰变量，例目标函数MaxZ=
2x1+3x2约束条件x1+2x2?84x1
?164x2?12
x1、x2?0“?”约束：减去非负剩余变量；xj可正可负（即无约束）；这时可令其中，
1-4线性规划问题的解线性规划问题的标准形式为求解线性规划问题，就是从满足约束条件（1）、（2）的方程组中找出一个解，使
目标函数达到最大值。可行解：满足约束条件（1）、（2）的解X=(x1,x2,…,xn)T称为线性规划问题的可行解。全部可行解的
集合称为可行域。最优解：使目标函数最大的可行解称为最优解。基：若B是约束方程系数矩阵A中m×m阶非奇异子矩阵（︱B︱≠0），则
B是线性规划问题的一个基。基向量：基变量：非基变量：基解：基可行解：满足非负条件的基解，称为基可行解。可行基：其约束
方程组系数矩阵为：【例】：基变量非基变量基向量非基向量（一）对应于基B1的基解X1的求解令非基变量x4、x5等于0
，由以上方程组求得：x1=4；x2=3；x3=-2。所以由基B1求得的一个基解为：X1=（x1，x2，x3，x4，
x5）=（4,3，-2,0,0）。由于x3=-2，不满足非负条件，故该解为基解，而不是基可行解。例基变量非基变量基向量
非基向量（二）令非基变量x1、x2等于0，由以上方程组求得：x3=8；x4=16；x5=12。所以由基B2求得的一个基解为：X2=（x1，x2，x3，x4，x5）=（0,0，8,16,12）。且x3≥0；x4≥0；x5≥0，所以X2是基可行解。对应于基B2的基解X2的求解线性规划解的关系图非可行解可行解基可行解基解最优解？§2图解法图解法的步骤(1)画出可行区域1)在坐标系中作出每个约束取等号时的直线；2)根据每个约束不等式判断可行域位于直线的哪一边；画出可行域的范围。(2)找出最优解1)作目标函数等值线，确定使目标函数最优的移动方向；2)平移目标函数的等值线，找出最优点，算出最优值。【例】目标函数MaxZ=2x1+3x2约束条件x1+2x2?84x1?164x2?12x1、x2?0x1x29—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2=8(0,4)(8,0)目标函数MaxZ=2x1+3x2约束条件x1+2x2?84x1?164x2?12x1、x2?04x1=164x2=12上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院Drawingontheexampl,thetwoaxisinterceptsareplotted.