运筹学-第一章-单纯形法进一步讨论

格式：ppt
大小：1.56 MB
文档页数：24

下载文档原格式

运筹学第一章 1.3.1 单纯形法的基本思路

0 0 M 0 1 a 11 a 21 M a m1 a 12 a 22 M am2 L L L L a1n a 2n M a mn 1 0 M 0 0 0 1 M 0 0 L L L L 0 0 M 1 0
m
σ1
j
σ
2
σ
n+i
n
b1 b2 M bm − z0
其中，其中，σ
， − z0 = 0 − c b ∑ n +i i i =1 i =1 j=1，2，…，n ；，，，
= cj − a ij
∑c
m
增广矩阵的最后一行就是用非基变量表示目标函数的表达式, (j=1 ,n)就是非示目标函数的表达式, σ j (j=1,2,…,n)就是非基变量的检验数。基变量的检验数。检验数的两种计算方法：（3）检验数的两种计算方法： ①利用矩阵的行变换，把目标函数表达式中利用矩阵的行变换，基变量前面的系数变为0 基变量前面的系数变为0； ②使用计算公式—— 使用计算公式——
③ 确定出基变量：确定出基变量：
问题讨论 x2进基意味着其取值从变成一个正数（经济进基意味着其取值从0变成一个正数变成一个正数（意义——生产产品），能否无限增大？生产B产品意义生产产品）能否无限增大？增加时，、、如何变化如何变化？当x2增加时， x3、 x4、x5如何变化？增加时现在的非基变量是哪些？现在的非基变量是哪些？具体如何确定换出变量？具体如何确定换出变量？
b xj 8 16 12 0 2 16 3 -9 2 8 3 -13
--8/2
3/(1/4)
Cj
2 x1
1 0 0 0 1 0 0 0

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

10
2D0
30 X1
(3)、求最优解 Z=40x1+50x2 x2 =-4/5x1+Z/50
C点： x1+2x2 =30 3x1+2x2 =60
解：x1 = 15, x2 = 7.5
maxZ =975
x2
maxZ=40x1+ 50x2
x1+2x2 30
30
3x1+2x2 60
2x2 24
x1 , x2 0
线性规划的单纯形法一线性规划的基本概念二单纯形法的迭代原理三单纯形法的计算步骤四单纯形法的进一步讨论五单纯形法小结线性规划的相关概念?矩阵的秩矩阵a中不为零的子式的最高阶数称为矩阵a的秩
问题的提出
❖ 例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表1-1所示。问该公司应制造A、B 两种家电各多少件，使获取的利润为最大。
图解法的步骤： 1、在平面上建立直角坐标系 2、图示约束条件，找出可行域 3、图示目标函数和寻找最优解
例1、maxZ=40x1+ 50x2
x1+2x2 30 3x1+2x2 60
2x2 24
x1 , x2 0
解：(1)、建立坐标系
(2)、确定可行域
X2
x1+2x2 30
30
x1+2x2 =30
(0,15) (30,0)
20
maxZ=40xX1+1+52X0x2 2 30
3xx11++222xxx3222XX11+,362X22004X2X220

《运筹学》完整教案(本科)2011汇总

《运筹学》教案适用专业：适用层次：本科教学时间：2011年上学期授课题目：绪论第一章线性规划及单纯形法第一节：线性规划问题及数学模型。

教学目的与要求：1.知识目标：掌握运筹学的概念和作用及其学习方法；掌握线性规划的基本概念和两种基本建模方法。

2.能力目标：掌握线性规划建模的标准形式及将普通模型化为标准模型的方法。

要求学生完成P43习题1.2两个小题。

3.素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：1、线性规划的基本概念和两种基本建模方法；2、线性规划建模的标准形式及将普通模型化为标准模型的方法。

教学难点：1、线性规划的两种基本建模方法；2、将线性规划模型的普通形式化为标准形式。

教学过程：1.举例引入（ 5分钟）2.新课（60分钟）（1）举例引入，绪论（20分钟）（2）运筹学与线性规划的基本概念（20分钟）（3）结合例题讲解线性规划标准型的转化方法3.课堂练习（20分钟）4.课堂小结（5分钟）5.布置作业《线性规划及单纯形法》（2课时）【教学流程图】举例引入，绪论运筹学运筹学与线性规划的基本概念线性规划（结合例题讲解）线性规划的标准型目标函数结合例题讲解线性规划标准型的转化方法约束条件的右端常数约束条件为不等式课堂练习课堂小结布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。

任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。

自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。

学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】一、教学过程：（一）举例引入：（5分钟）（1）齐王赛马的故事（2）两个囚犯的故事导入提问：什么叫运筹学？（二）新课：绪论一、运筹学的基本概念（用实例引入）例1-1战国初期，齐国的国王要求田忌和他赛马，规定各人从自己的上马、中马、下马中各选一匹马来比赛，并且说好每输一匹马就得支付一千两银子给予获胜者。

运筹学第章单纯形法

C’ B X B
b
4
1
5
x1
x2
x3
0
x0 11/22 1/4
1
Zj Cj–Zj
5/2 5/4 5 3/2 -1/4 0
K
当前解为：X=(0, 0, 750, 5000，0)
LP
0
0
x4
x5
1
-1 5000
0
1/4 1500 L
0 5/4 0 -5/4
Z=3750
cj
8000 3000
x j 0, j 1,2,3,4,5
初始单纯形表：
cj
C’ B
XB
b
4
1
5
0
x1
x2
x3
x4
0
X4
8000
3
1
4
1
0
X5
3000
2
1
4
0
Zj
0
0
0
0
Cj–Zj
4
1
5
0
LP
0 x5 0 1 0 0
初始解为X=(0,0,0,8000,3000) Z=0
Z j m ciaij ？推导 i 1
x4
5000
x1
0
x3
750
1 2
x1
0
则：x1 min5000,750* 2 1500
当x1=1500时，x3=0即为非基变量，x4=3500
则：基变量为x1, x4; 非基变量为x2, x3 x5 ，变换标准型的约束条件：
32xx11
x4 8000 x2 4x3 3000 x2 4x3 x5
x c MaxZ 人工 ,即人工 1 x c 或 MinS 人工,即人工 1

川大运筹学资料及试题答案

即
x j ay j (1 a)z j (0 a 1, j 1,, n) 因为a>0,1-a>0，故当 x j 0时，必有y j＝z j ＝0
因为所以
n
r
Pj x j Pj x j b
j1
j1
n
r
Pj y j Pj y j b
j1
ai1 x1 ai 2 x2 ain xn si bi , si 0
或
ai1 x1 ai 2 x2 ain xn bi
松弛变量
ai1 x1 ai 2 x2 ain xn si bi , si 0
剩余变量
几个概念
可行解（或可行点）：满足所有约束条件的向量 x ( x1 , x2 , xn ) 可行集（或可行域）：所有的可行解的全体
定理 2 可行解 x 是基本可行解的充要条件是它的正分量所对应的矩阵 A 中列向量线性无关。
定理 3 x 是基本可行解的充要条件是 x 是可行域 D 的顶点。
定理 4 一个标准的 LP 问题如果有有限的最优值，则一定存在一个基本可行解是最优解。
定理2
证明：由基可行解的定义知，必要性显然成立。充分性：若向量 p1, p2 , pk 线性独立，则必有 k m 当 k m 时，它们恰好构成一个基，从而为相应的基可行解；当 k m 时，则一定能从剩余的列向量中取出m-k个与 p1, p2, pk 构成最大的线性独立向量
组其对应的解恰为x，所以，x是基可行解。
定理3
证明 (1) x不是基可行解，则x不是可行域的顶点。
不失一般性，假设x的前m个分量为正，则有
m
Pi xi b

第一章单纯形法

B、C的物资数量应该分别等于两产地甲、乙的产量,所以 xij 应满足：
运到A、B、C三销地的物资数量应
x11 x12 x13 2000 x21 x22 x23 1000
x11 x21 1700 x12 x22 1100 x x 200 13 23
1.1
a11 x1 a12 x2 a1n xn b1 a x a x a x b 1.2 21 1 22 2 2 n n 2 s.t. a x a x a x b m2 2 mn n m m1 1 x 0, x 0, , x 0 1.3 1 2 n 1、方程组（1.2）中不含有多余的方程一般m n 2、 bi 0(i 1...m)
上述例子表明．规划问题的数学模型由三个要素组成： (1) 变量，或称决策变量，是问题中要确定的未知量，它用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制； (2)目标函数，它是决策变量的函数，按优化目标分别在这个函数前加上max或min；
(3)约束条件，指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。
x11 x21 1700 x x 1100 12 22 x13 x23 200 s.t. x11 x12 x13 2000 x21 x22 x23 1000 xij 0 i 1,2; j 1,2,3
1.2 图解法
图解法适用于求解只有两个变量的线性规划问题.
max(min) z c1 x1 c 2 x 2 a11 x1 a12 x2 b1 a x a x b 21 1 22 2 2 s.t. a x a x b m2 2 m m1 1 x1 0, x 2 0

第1章-线性规划及单纯形法-课件(1)

✓ x1、 x2 0
IБайду номын сангаас
设备
1
原材料 A 4
原材料 B 0
利润
2
II 资源限量
2 8 台时
0
16kg
4
12kg
3
第一章线性规划及单纯形法运筹学
该计划的数学模型
✓ 目标函数 ✓ 约束条件
Max Z = 2x1 + 3x2
x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0
x1
✓ 美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策。
✓ 美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策。
✓ ……
第一章线性规划及单纯形法运筹学
二、线性规划问题的数学模型
✓ 1、一般形式 ✓ 2、简写形式 ✓ 3、表格形式 ✓ 4、向量形式 ✓ 5、矩阵形式
1、唯一最优解
max Z 2 x 1 3 x 2
2 x 1 2 x 2 12 ⑴
x1 4 x1
2 x2
8 16
⑵ ⑶
4 x 2 12 ⑷
x 1 0 , x 2 0
1 234 56
x2
⑶ ⑷
(4，2)
0 1 234 5678
x1
⑵
⑴
✓最优解：x1 = 4,x2 = 2，有唯一最优解Z=14。
第一章线性规划及单纯形法运筹学
三、线性规划模型的标准形式
✓ 1、标准形式 ✓ 2、转换方式
第一章线性规划及单纯形法运筹学
1、标准形式
maZx cjxj
xj
aijxj 0
bi

1-5 单纯形法的进一步讨论

B 1b B 1NX N
令非基变量XN=0，XB=B—1b，由 B是可行基的假设，则得到
基本可行解
X=(B－1b，0)T
将目标函数写成
Z

(CB
,
CN
)

X X
B N

CB X B
CN X N
CB (B1b B1NX N ) CN X N
CBB1b (CN CBB1N )) X N
MaxZ=-3x1+x3 x1+ x2+ x3≤4
-2x1+ x2- x3≥1 3x2+x3=9
xi ≥0,j=1,2,3
求解辅助问题，得到辅助问题的最优解
引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为
所有人工变量之和的极小化
MaxW=-x6-x7
x1+ x2+ x3+x4
=4
-2x1+ x2-x3 -x5+x6 =1
z zσ
XB … 0T …
xj cj - zj
… RHS … z0
XB xB I …
Yj
…b
基变量在目标函数中的系数等于0，基变量在约束条件中的系数是一个单位矩阵
单纯形表的结构
注意： Z行中有m 个0，它们与基变量相对应。一般情况下，这m 个0分散在Z行的各列中，并与基变量相对应。
其余m行中有一个m阶单位矩阵I，其各列与基变量相对应。一般情况下，组成I的各列分散在表的各列中，它们与基变量相对应。
X1 1
0
a1
0
a2 a6
X2 0
1
1
0
-2

运筹学-第1章 3-单纯形法

解就是原问题的最优解
若变化后的问题中含有非零的人工变量则元问题无可行
解
7
2.最优性检验和解的判别
x i bi a im 1 x m 1 , ,a in x n i 1, , m代入目标函数 Z
c1 x1 c2 x 2 c n x n c1 (b1 a1m 1 x m 1 a1n x n ) c2 (b2 a 2 m 1 x m 1 a 2 n x n ) cm (bm a mm 1 x m 1 a mn x n ) c m 1 x m 1 c n x n ci bi
（1）因为所有 Xj ≥0，当所有σ j<0 时，则 Z≤Z0,则该基可行解对应最优解；（2）因为所有 Xj ≥ 0 ，当 σ j≤ 0 且存在 σ j ＝0 （ j=m+1,„,n) 时，则该线性规划问题有无穷多最优解；（ 3 ）对基可行解 X0, 若存在某个 σ k>0, 且所有 aik≤0(Pj≤0), i=1,2,„,m，则该问题无界（无界解）；（4）因为所有Xj≥0，当存在σ j>0时，则该基可行解不是最优解，需要寻找另一个基可行解；
9
3.基变换
• 变换目的：使目标函数Z值得到改善，接近最优解，一次基变换，是从该顶点到相邻顶点，即一次基变换仅变换一个基变量。换入变量的确定（入基变量）
σk>0,aik 至少一个大于0，若σk=Max{σj| σj>0},则xk为换入变量。
换出变量的确定（出基变量）
bi bl bi , i 1,, m, min | aik 0 aik aik alk
13
一.求初始基可行解
1.当约束条件为“≤”时，直接在约束不等式左边加上非负的松弛变量，使约束方程的系数矩阵很容易找到一个单位矩阵，求出一个初始基可行解。

运筹学第1章

（第三版）《运筹学》教材编写组编清华大学出版社运筹学第1章线性规划与单纯形法第1节线性规划问题及其数学模型二.线性规划与目标规划第1章线性规划与单纯形法第2章对偶理论与灵敏度分析第3章运输问题第4章目标规划第1章线性规划与单纯形法第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例第1节线性规划问题及其数学模型•1.1 问题的提出•1.2 图解法•1.3 线性规划问题的标准形式•1.4 线性规划问题的解的概念第1节线性规划问题及其数学模型线性规划是运筹学的一个重要分支。

线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。

特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。

从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。

它已是现代科学管理的重要手段之一。

解线性规划问题的方法有多种，以下仅介绍单纯形法。

1.1 问题的提出从一个简化的生产计划安排问题开始例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。

资源产品ⅠⅡ拥有量设备 1 2 8台时原材料A40 16kg原材料B0 4 12kg续例1该工厂•每生产一件产品Ⅰ可获利2元，•每生产一件产品Ⅱ可获利3元，•问应如何安排计划使该工厂获利最多?如何用数学关系式描述这问题，必须考虑称它们为决策变量。

产品的数量，分别表示计划生产设II I,,21x x ∙12416482212121≤≤≤+∙x ;x ;x x ,x ,x 这是约束条件。

即有量的限制的数量多少，受资源拥生产021≥∙x ,x ,即生产的产品不能是负值这是目标。

最大如何安排生产，使利润,∙数学模型⎪⎪⎩⎪⎪⎨⎧≥≤≤≤++=0124164823221212121x ,x x x x x :x x z max 约束条件目标函数例2. 简化的环境保护问题靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

退化即计算出的 θ（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。为避免出现计算的循环，勃兰特(Bland)提出一个简便有效的规则（摄动法原理）： ⑴ 当存在多个 j 0 时，选下标最小的非基变量为换入变量；
解：首先将数学模型化为标准形式
max Z 3 x1 2 x 2 x 3
4 x1 3 x 2 x 3 x 4 4 系数矩阵中不存在单位矩阵，无法建 x1 x 2 2 x 3 x 5 10 立初始单纯形表。 2 x 2 x x 1 2 3 1 x j 0, j 1,2, ,5
1
0 0 0 1 0 0 2 5/3 2/3 -25/3
0
0 0
8/3
—— —— ——
j
x2 x5 x3 x2 x1 x3
x3
31/3 →
j
j
单纯形法的进一步讨论－人工变量法
例1.11 用大M法解下列线性规划
max Z 3 x1 x2 x3
x1 2 x2 x3 11 4 x x 2 x 3 1 2 3 +x3 1 2 x1 解：首先将数学模型化为标准形式 x1、x2、x3 0
max z=-2x1-3x2+0x3 -M x4-M x5 s .t x1+x2 -x3+ x4 =3 x1+2x2 +x5 =4 xj0, (j=1,2,3,4,5)
这种处理方法称为大M法，以下则可完全按单纯形法求解。
单纯形法的进一步讨论－人工变量法
例1.10 用大M法解下列线性规划
max Z 3 x1 2 x 2 x 3 4 x1 3 x 2 x 3 4 x1 x 2 2 x 3 10 2 x 1 2 x 2 x 3 1 x1、x 2、x 3 0
运筹帷幄之中云南财经大学物流学院窦志武
决胜
单纯形法进一步讨论
千里之外
单纯形法的进一步讨论－人工变量法
人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M 法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。
单纯形法的进一步讨论－人工变量法
故人为添加两个单位向量，得到人工变量单纯形法数学模型：
max Z 3x1 x2 x3 + 0x4 + 0x5－Mx6 Mx7 11 3 x1 x2 x3 x4 -4x x 2 x x5 +x6 3 1 2 3 x3 x7 1 2 x1 x j 0, j 1, 2, L , 7
其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。
单纯形法的进一步讨论－人工变量法
Cj CB 0 XB x4 b 11 3 x1 1 -1 x2 -2 -1 x3 1 0 x4 1 0 x5 0 -M x6 0 -M x7 0 11
单纯形法的进一步讨论－两阶段法
第一阶段的线性规划问题可写为：
min x6 x7 x4 =11 x1 2 x2 x3 4 x x 2 x x x6 3 1 2 3 5 x3 x7 1 2 x1 x1 , x2 ,，x7 0
2
1 3 0 0
0
0 0 1 0
-1
0 -1 0 -1
1
0 0 0 1
0
1 0 -1 -2
3/2
1 － 1
→ →
0
ω 0 0 0 ω
x3
x4 x2 x3
1
1 12 1 1 0
-2
0 3 0 -2 0
0
1 0 1 0 0
1
0 0 0 1 0
0
0 1 0 0 0
0
-1 -2 -1 0 0
0
0 2 1 0 -1
-M
-M 0 -M -1
x6
3
1 10 1 1
-4
-2 3-6M 3 0 -2 1
1
0 -1+M -2 1 0 -1+M
2
1 -1+3M 0 0 1 0
0
0 0 1 0 0 0
-1
0 -M 0 -1 0 -M
1
0 0 0 1 0 0
0
1 0 -1 -2 1 -3M+1
3/2
1 － 1 －
j
x7 x4 x6 x3
单纯形法的进一步讨论
C 0 C 0 0 Z XB X3 X4 B 1 2 0 x1 -1 -1/2 2 x2 1 1 2 x3 1 0 0 x4 0 1 0 2 2 0 θ
-1 因1 = 2>0 但 P1 = 1 0 所以原问题无最优解 - 2
单纯形法的进一步讨论
第一阶段单纯形法迭代的过程见下表
单纯形法的进一步讨论－两阶段法
Cj CB 0 XB x4 b 11 0 x1 1 0 x2 -2 0 x3 1 0 x4 1 0 x5 0 -1 x6 0 -1 x7 0 11
-1
-1 ω 0 -1
x6
x7 x4 x6
3
1 4 10 1
-4
-2 6 3 0
1
0 1 -2 1
j
0
-1 2 0 -1 2 3 -1
→ →
x5
8
1 3/5 31/5 11/5 13 31/3 19/3
-3
2 5-6M －6/5 3/5 －2/5 5↑ 0 1 0 0
3
-2 5M↑ 1 0 0 0 1 0 0 0
0
1 0 0 0 1 0 0 0 1 0
0
0 -M －1/5 3/5 －2/5 0 1 1 0 -5
→ →
j
单纯形法的进一步讨论－人工变量法
Cj CB 0 XB x4 b 12 3 x1 3 -1 x2 0 -1 x3 0 0 x4 1 0 x5 -2 -M x6 2 -M x7 -5 4
→
-1
-1 Z 3 -1 -1 Z
x2
x3 x1 x2 x3
1
1 -2 4 1 9 2
0
-2 1 1 0 0 0
1
0 0 0 1 0 0
0
1 0 0 0 1 0
0
0 0 1/3 0 2/3 -1/3

-1
0 -1 -2/3 -1 -4/3 -1/3
1
0 -M+1 2/3 1 4/3 -M+1/3
-2
1 -M-1 -5/3 -2 -7/3 -M+2/3
－
－
单纯形法的进一步讨论－两阶段法
用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。第一阶段：在原线性规划问题中加入人工变量，构造如下模型：
单纯形法的进一步讨论－两阶段法
第二阶段：
cj
cB 0 -1 -1 Z 3 -1 -1 Z x1 x2 x3 xB x4 x2 x3 b 12 1 1 -2 4 1 9 2
maxZ 3x1 x2 x3 0x4 0 x5
3
x1 3 0 -2 1 1 0 0 0
-1
x2 0 1 0 0 0 1 0 0
单纯形法的进一步讨论－人工变量法
故人为添加两个单位向量，得到人工变量单纯形法数学模型：
max Z 3 x1 2 x2 x3－Mx6 Mx7 x6 4 4 x1 3 x2 x3 x4 x x 2x x5 10 1 2 3 x7 1 2 x1 2 x2 x3 x j 0, j 1, 2, L , 7
max Z 3 x1 x2 x3 x1 2 x2 x3 x4 11 4 x x 2 x x 3 1 2 3 5 x3 1 2 x1 x j 0, j 1, 2, L ,5
系数矩阵中不存在单位矩阵，无法建立初始单纯形表。
其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。
单纯形法的进一步讨论－人工变量法
cj CB -M 0 -M -M XB x6 x5 x7 x6 b 4 10 1 3 3 x1 -4 1 2 3-2M -6 2 x2 3 -1 -2 2+M 5 -1 x3 1 2 1 -1+2M↑ 0 0 x4 -1 0 0 -M -1 0 1 3/5 0 x5 0 1 0 -M x6 1 0 0 -M x7 0 0 1 θi 4 5 1
-1
x3 0 0 1 0 0 0 1 0
0
x4 1 0 0 0 1/3 0 2/3 -1/3
0
x5 -2 -1 0 -1 -2/3 -1 -4/3 -1/3 4 －－
→
∴最优解为（4 1 9 0 0），目标函数 Z = 2
单纯形法的进一步讨论
无可行解通过大Ｍ法或两阶段法求初始的基本可行解。但是如果在大Ｍ法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。
1
-3 -5 -2 0 -1
－
单纯形法的进一步讨论－两阶段法