当前位置：文档之家 › 06第六章 单纯形法的灵敏度分析与对偶问题(新) 2

06第六章 单纯形法的灵敏度分析与对偶问题(新) 2

  • 格式：ppt
  • 大小：2.93 MB
  • 文档页数：168

下载文档原格式

  / 168

合集下载

运筹学-单纯形法灵敏度对偶

运筹学-单纯形法灵敏度对偶

若新增约束如下：
max z 50x1 100x2 x1 x2 300 2x1 x2 400 x2 250 10x1 30x2 5000(电力约束) x1, x2 , 0
x1 x2 s1
把最优解x1=50,x2 =250代入电力约束 1050+30 250=80005000 新约束不满足,最优解变化
例题：已知某线性规划初始可行基是（S1 S2 S3 a1）， 最终单纯形表如下，求对偶价格不变时的△bi变化范围
x1 x2 s1
50 100 0
X1 50
1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0
0
1
Zj
50 100 0
δj
0
0
0
（1） △b1的变化范围： ?
（2） △b2的变化范围：?
（3） △b3的变化范围： ? （4） △b4的变化范围：?
1 0 1 2 0.5
B1 p6'
2
1
1
0.5
2
0 0 1 1.5 1.5
Z6' 50 0.5 0 (2) 100 1.5 175
' 6
C6
Z6'
150 175
25
δ6´<0，最优解不变，即仍生产Ⅰ50件，Ⅱ100件。
2、变量xk系数列由pk变为pk´，在最终单纯形表 上xk是基变量
x1 x2 s1
50 100 0
X1 50 1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0

运筹学02对偶理论(2)对偶单纯形法,灵敏度与参数分析

运筹学02对偶理论(2)对偶单纯形法,灵敏度与参数分析
从满足条件(2)的基出发去找原问题的最优解→ 对偶单纯形法思想： 从满足条件(2) 的基(一般称为正则基)B出发，经 过换基运算到另一个正则基，即一直保证条件 (2)成立， 直到找到一个满足条件(1)的正则基。
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
注：当模型的数据发生变化后，不必对线性规划问题
重新求解，而用灵敏度分析方法直接在原线性规划取
得的最优结果的基础上进行分析或求解 . 线性规划的参数分析(Parametric Analysis)是研究和分
析目标函数或约束中含有的参数μ在不同的波动范围内 最优解和最优值的变化情况．这种含有参数的线性规划
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
X XB σ
b
B-1A B-1b C-CBB－1A －CBB－1b 若上表为最优单纯形表，则下列两个式子同时成立：
(1) B1b 0 (可行性条件，又叫对偶最优性条件)
(2) C CB B 1 A 0 (最优性条件,又叫对偶可行性条件)
4.最优解、无可行解的判断。
作业：教材P81 1.12 (2)
下一节：灵敏度分析与参数分析
3.4 灵敏度与参数分析
Sensitivity and Parametric Analysis
3.4 灵敏度与参数分析 Sensitivity and Parametric Analysis
Chapter3 对偶理论 Dual Theory
3.3 对偶单纯形法 Dual Simplex Method
max z 7 x1 3x 2

对偶单纯形法灵敏度分析

对偶单纯形法灵敏度分析
1、什么是灵敏度分析？ 灵敏度分析是指系统或事物因为周围条件变化
而显示出来的敏感程度分析。
第五节 灵敏度分析
在生产计划问题的一般形式中，A代表企业的技术状 况，b代表企业的资源状况，而C代表企业产品的市场状 况，在这些因素不变的情况下企业的最优生产计划和最大 利润由线性规划的最优解和最优值决定。
在实际生产过程中，上述三类因素均是在不断变化的， 如果按照初始的状况制订了最佳的生产计划，而在计划实 施前或实施中上述状况发生了改变，则决策者所关心的是 目前所执行的计划还是不是最优，如果不是应该如何修订 原来的最优计划。更进一步，为了防止在各类状况发生时， 来不及随时对其变化作出反应，即所谓“计划不如变化 快”，企业应当预先了解，当各项因素变化时，应当作出 什么样的反应。
也就是说，当原问题达到最优时，对偶问题的解可行。并且根据 对偶的性质，我们可以确定此时对偶问题也达到最优
初始单纯形表
项目
非基变量
XB XN
0 XS b B N
Cj-Zj
CB CN
基变量 XS I 0
项目
基变量
非基变量
CB XB B-1 b Cj-Zj
XB
XN
XS
I B-1 N
B-1
0 CN -CB B-1 N -CB B-1
s.t.
j1
n

aij xj bi
（i 1,
j1
xj 0
（j 1,
3. 分析系数 aij 的变化
,m） ,n）
4. 分析增加一个约束条件的变化 系数矩阵A
5. 分析增加一个变量 xj 的变化
表初 始 单 纯 形
基变量 基变量 基可
系数
行解
0

单纯形法的灵敏度分析28页PPT

单纯形法的灵敏度分析28页PPT

66、节制使快乐增加并使享受加强。 ——德 谟克利 特 67、今天应做的事没有做，明天再早也 是耽误 了。——裴斯 泰洛齐 68、决定一个人的一生，以及整个命运 的，只 是一瞬 之间。 ——歌 德 69、懒人无法享受休息之乐。——拉布 克 70、浪费时间是一桩大罪过。——卢梭
单纯形法的灵敏度分析
16、自己选择的路、跪着也要把它走 完。 17、一般情况下)不想三年以后的事， 只想现 在的事 。现在 有成就 ，以后 才能更 辉煌。
18、敢于向黑暗宣战的人，心里必须 充满光 明。 19、学习的关键--重复。
20、懦弱的人只会裹足不前，莽撞的 人只能 引为烧 身，只 有真正 勇敢的 人才能 所向披 靡。

对偶理论和灵敏度分析(新)

对偶理论和灵敏度分析(新)
Y’ A≥C’ Y’ ≥0
W＝Y’b=CBB-1b=Z
所以当原问题为最优解时，对偶问题为可行解且具有相 同的目标函数值。
非对称形式的原—对偶问题
minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x4≥5 2x1 +2x3-x4≤4 x2+x3+x4=6 x1≤0,x2,x3≥0
x2+x3+x4≥6 x2+x3+x4≤6
A(3,0)
B(1.8,0.4)
C(0,4)
D(2,2)
可行解
z
最优解
A
6
B
4.8
是
C
12
D
10
3 2 1
A(1,0)
B(0.8,0.6)
C(0,1)
O(0,0)
可行解
w
最优解
O
0
A
3
B
4.8
是
C
4
单纯形法计算的矩阵描述
Max Z=CX AX≤b
Max Z=CX+0Xs AX+IXs=b
I 为m×m的单位矩阵
≤
≥
=
≥
Free
≤
≥
≥
=
≤
≥
x1≥0
x2≤0
x3: Free
原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。 原始问题变量的性质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质。
*
写对偶问题的练习（2）
原始和对偶问题可行解目标函数值比较

单纯形法的灵敏度分析与对偶

单纯形法的灵敏度分析与对偶

第三章单纯形法的灵敏度分析与对偶1、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（） A．b列元素不小于零 B．检验数都大于零C．检验数都不小于零 D．检验数都不大于零2、关于线性规划的原问题和对偶问题，下列说法正确的是（）A．若原问题为元界解，则对偶问题也为无界解B．若原问题无可行解，其对偶问题具有无界解或无可行解c．若原问题存在可行解，其对偶问题必存在可行解D．若原问题存在可行解，其对偶问题无可行解3、下面哪些不是线性规划问题的标准形式所具备的（）A 所有的变量必须是非负的B 所有的约束条件（变量的非负约束除外）必须是等式C 添加新变量时，可以不考虑变量的正负性D 求目标函数的最小值4、已知线性规划问题Max Z=4X1+7X2+2X3X1+2X2+X3 ≤10S.t 2X1+3X2+3X3≤10X1，X2，X3 ≥0应用对偶理论证明该问题最优解的目标函数值不大于255、已知线性规划问题max Z=3x1+4x2+x3-x1+2x2+3x3≤6S.t -3x1+x2-4x3≤7x1,x2,x3 ≥0利用对偶理论证明其目标函数值无界6、写出下列线性规划问题的对偶问题⎪⎩⎪⎨⎧=≥≤++≤++⋅⋅++=)3,2,1(0205432553643max 321321321j x x x x x x x t S x x x Z j7、已知线性规划123123123max 3421022160,1,2,3jz x x x x x x x x x x j =++⎧++≤⎪++≤⎨⎪≥=⎩的最优解为*(6,2,0)T X =，试利用互补松弛定理，求对偶问题的最优解。

8、已知线性规划问题12341341234max 25628..222120, 1,2,3,4jz x x x x x x x s t x x x x x j =+++⎧++≤⎪+++≤⎨⎪≥=⎩其对偶问题的最优解为*14y =、*21y =，试用对偶理论求解原问题的最优解。

管理运筹学 第6章 对偶

管理运筹学 第6章 对偶
' '' 3 ' 3
' 3 ' 3
y 3 ) 3,
''
y 3 ) 4,
'' ''
y 3 ) 6, 0,
14
管
理
运
筹
学
§2
线性规划的对偶问题
3,
s.t. 2 y 1 6 y 2 5 y 3
。
3 y1 4 y 2 3 y 3 4 , 6 y1 y 2 y 3 6 , y1 , y 2 0 ,
则
A
T
a 11 a 1n
a 21 a2n
管


理 运
a m1 a mn
8
筹
学
§2
max z cx , Ax b , x 0
线性规划的对偶问题
如果我们用矩阵形式来表示，则有原问题：
其中A是 矩阵m*n，该问题有m个约束条件n个变量，x= x1 , x 2 , , x n T ,b= ( b1 , b 2 ,..., b m ) T c= ( c , c ,..., c ).
3 y1 4 y 2 3 y 6 y1 y 2 y y1 , y 2 , y 3 , y
' ' 3 '' 3 ' 3
3y
'' 3
'' 3
4,
y
6,
0,
13
管
理
运
筹
学
§2
线性规划的对偶问题
这里 一样都是不同的决策变量，为了表示这 两个决策变量都来源于原问题的第三个约束条件，记 为 y ' 3 , y '' 3 。 ' '' y 3 和 y 3 的系数只相差一个符号，我们可 因为在该对偶问题中 以把上面的对偶问题化为：

运筹学 第六章1

运筹学 第六章1

-1 1 1 50 -50
50 50 250
9
cj − zj
50 100 50 0 0 -50
0 0
1 进行灵敏度分析： 对 b1 进行灵敏度分析： D1 = − 2, 0 xBi xBi 50 50 m − ax di′1 > 0 = − = −50, m − ′1 < 0 = − in di = 25. ′1 1 −2 di di′1 − 50 ≤ ∆b1 ≤ 25,
判断最优解的原则： 判断最优解的原则： σj≤0
4
} c′ −100 ≤ 0
′ −c1 ≤ 0
1
注：用此方法对目标函数中的系数进行灵敏度分析，指的是只有 用此方法对目标函数中的系数进行灵敏度分析， 一个系数发生变化。 一个系数发生变化。 二.约束方程右边常数灵敏度分析 对偶价格：在约束条件右边量增加一个单位，而使最优目 对偶价格：在约束条件右边量增加一个单位， 标函数值得到改进的数量。 标函数值得到改进的数量。 一般地说， 发生变化，资源投入起了变化， 一般地说，由于 bi 发生变化，资源投入起了变化，最优解是 变化的。对右边常数进行灵敏度分析，是指求出 bi 的取值范围， 变化的。对右边常数进行灵敏度分析， 的取值范围， 在这个范围内变化时，其对偶价格不变。 使得 bi 在这个范围内变化时，其对偶价格不变。
1 2 0 0 50
x1 50
1 1 10 E 1 0 0 0
s2 0
0 0
s1 0
300 400 250 0 0 0
0 0 1
(
)
s3 0
bi
θi
x1 s2
50 0 100
2
x2 zj

单纯形法的灵敏度分析

单纯形法的灵敏度分析

bk bk
时，也就是原来的初始单
纯形表中的b向量变成了b’向量
0 0 ... 令 b bk ... 0 则有 b ' b b
9
这样在最终单纯形表中基变量XB的解就变成了
X 'B B .(b b ) B b B b 。
中从0变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利 50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品
而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。
对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时 这个约束条件的对偶价格就和这个剩余变量的 z j有关了。这将使得最优目
+ CK a’Kj 。要使最优解不变，只要当J
δj a' kj
δ j ΔC k a' kj 0, ΔC k a' kj δ j 当 a' kj 0时 , ΔC
k

, 这里
0;
当 a' kj 0时 , ΔC
k
, 这里
δj a' kj
0; Z k ΔC a' kk , 因为 X K 是基变量， δj a' kj
14
zj 标值 “变差”而不是改进，故这时约束条件的对偶价格应取
值的相反数-j z
。
对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的 人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的 值z j 。
7
下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。

对偶单纯形法灵敏度分析

对偶单纯形法灵敏度分析
对偶单纯形法灵敏度分析
汇报人：XX
单击输入目录标题 对偶单纯形法概述 对偶单纯形法灵敏度分析的步骤 对偶单纯形法灵敏度分析的优点和局限性 对偶单纯形法灵敏度分析的改进方向 对偶单纯形法灵敏度分析的实际应用案例
添加章节标题
对偶单纯形法概述
对偶单纯形法的定义
对偶单纯形法是一种线性规划 算法
它基于对偶理论，通过迭代寻 找最优解
结论：对偶单纯形法灵敏度分析在资源分配问题中具有广泛的应用前景，能够为企业带来巨大 的经济效益。
THANK YOU
汇报人：XX
各变量对目标函数的影响程度。
求解最优解
确定初始对偶解
确定迭代步长
计算对偶方向 更新最优解
计算灵敏度
计算对偶问题的 最优解
确定最优解对应 的基变量和自由 变量
计算基变量的灵 敏度
计算自由变量的 灵敏度
对偶单纯形法灵敏度分析的优 点和局限性
优点
计算简单：对偶单 纯形法在计算上相 对简单，易于理解 和实现。
对偶单纯形法适用于求解标准 型线性规划问题
它具有简单、高效、可靠等优 点
对偶单纯形法的原理
对偶性：将原问题转化为对偶问题，通过对偶问题的最优解得到原问题 的近似最优解 单纯形法：利用线性规划的迭代方法，通过不断迭代寻找最优解
灵敏度分析：分析决策变量变化对最优解的影响，为决策提供参考
对偶单纯形法的应用场景
分析灵敏度结果：根据灵敏度系数的大 小和符号，分析各变量对目标函数的灵
敏度，为决策提供依据。
添加标题
添加标题
添加标题
添加标题
确定约束条件和目标函数：在分析过程 中，首先需要确定问题的约束条件和目 标函数，这是对偶单纯形法灵敏度分析

第二章 对偶问题与灵敏度分析(修改版)

第二章 对偶问题与灵敏度分析(修改版)
31
（4）最优性。
□如果 xj (j=1,…,n) 是原问题的可行解，yi (i= 1,…,m)是其
第二节 对偶问题的基本性质
单纯形法计算的矩阵描述 对偶问题的基本性质
1
复习线性规划问题的标准化
加 c2 x2 ... cn xn a11 x1 a12 x2 ... a1n xn b1 a x a x ... a x b 21 1 22 2 2n n 2 ................................................... a x a x ... a x b m2 2 mn n m m1 1 x1 , x2 ,..., xn 0
1 2
2 3 1 2 3 1 2 3
厂 家
3
对 偶 问 题
18
原问题化为极小问题，最终单纯形表：
原问题 的变量
原问题松弛变量
化为极小问题
x1 x3 15 / 2 0 x1 7 / 2 1 x2 3 / 2 0 （c j z） 0 j y4
对偶问题 剩余变量
x2 0 0 1 0 y5
x3 1 0 0 0 y1
cj xB b
x4 x5
σj
3 -1 2 0 0 x1 x3 x2 x4 x5
1 0 0 1
量为XB时，此过程相当
于用B-1（基B的逆矩阵）
左乘增广矩阵。 1 1 6 2 -2 4 1 0 × 1 -1 2 3 0 1 1/2 1
6 2 -2 4 1 -1 2 3 7 4
x1 x3
σj
3 2 -1 0 0 1 0 7 1 1 0 1 5 1/2 1 0 0 -32 -4 -5
XB = B-1· b
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

-1 x3 2
0 x4 -1
0 x5 0
-M x6 1
-M x7 0 初 始 单 纯 形 表 格
-M
-M
XB x6 x7
b
8
x1 1
6
3
2
0
0
-M
-1
-M
0
0
1
0
检验数j
Cj
4M-2 6M -3 2M-1
-2
-3
-1
0
0
-M
-M
CB
-3 -2
XB X2
x1
b
9/5
x1
0
x2
1
4/5
1
0
0
0
检验数j
分别用大M法和两阶段法求解下列 线形规划问题,并指出解的类型
• minZ=2x1+3x2+x3 • x1+4x2+2x3≥8 • S.t. 3x1+2x2 ≥6 • x1,x2,x3 ≥0
• 时间:1:40—2:10
Cj
CB
-2
-3 x2 4
-1 x3 2
0 x4 -1
0 x5 0
-M x6 1
-M x7 0 初 始 单 纯 形 表 格
s.t. 3y1 + 2 y2
≥1500
≥ 0
2y1 + y2 + 3y3 ≥2500 y1, y2 , y3
min
b=
65 40 75
A=
3 2
2 1
0 3
b=
1500 2500
1500 2500
c=
65 40 75
二、对偶问题的形式
1、对称型对偶问题
原问题 Max Z=cX
对偶问题 Min W=bTY
• 考虑： • 1、定价不能太高？ • 2、定价不能太低？
设A、B、C资源的出售价格分别为 y1 、 y2和y3
甲 A 3 乙 2 资源 限制 65 y1
min w 65y1 40y2 75y3B来自C 单件 利润2
0
1
3
40
75
y2
y3
3 y1 2 y2 ≥1500 2 y1 y2 3 y3 ≥2500
s.t.
s.t.
2x1+x2 ≤400
x2 ≤250 x1,x2 ≥0 CB
2x1+x2 +x4 =400
x2 +x5=250 x1,x2 , x3 ,x4,x5 ≥0
50
b
100 x2 1 1 1
100
0 x3 1 0 0
0
0 x4 0 1 0
0
0 x5 0 0 1
0
CB 0 0 0
XB x3 x4 x5
怎么样 简单吧
对称型线性规划问题
2、非对称型对偶问题
表 对偶变换的规则
好难记呀！
原问题(max,) 技术系数矩阵 A 价值系数 C 右端项 b 第 i 行约束条件为 型 第 i 行约束条件为 型 第 i 行约束条件为 = 型 决策变量 xj 0 决策变量 xj 0 决策变量 xj 不限
s.t.
AX≤b X ≥0
C
s.t.
ATY≥CT Y ≥0
bT
max
min
m
n
A
≤ b
n
AT
≥ CT
m
• 对偶关系表
x1 c1 x2 c2 … … xm cm … … xn cn maxZ minW
Y1
Y2
A11
a21
a12
a22
…
…
a1m
a2m
…
…
a1n
a2n
≤
b1
≤ b2
Ym
am1
am2
…
amm
对偶问题(min,) 技术系数矩阵 AT 右端项 b 价值系数 C 对偶变量 yi 0 对偶变量 yi 0 对偶变量 yi 不限 第 j 行约束条件为 型 第 j 行约束条件为 型 第 j 行约束条件为 = 型
• 约束条件的类型(规范与否)与非负条件相互对应 • 非标准的约束条件类型对应非正常的非负条件 • 对偶变换是一一对应的
例3：
Min z= 5x1+ 25x2 7x1+ 75x2 ≤98 s.t. 5x1 + 6x2 = 78 24x1+ 12x2≥54 x1≥0 、x2 ≤ 0
怎么样， 没问题吧！
Max w= 98y1+ 78y2 + 54y3 7y1+ 5y2 + 24y3 ≤ 5 s.t. 75y1+ 6y2 + 12y3 ≥25 y1 ≤ 0 、y2无限制、 y3≥0
x3
x4
x5
x6
x7
第六章 单纯形法的灵敏度分析 与对偶
窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象
DUAL
学习重点与难点
• §1 单纯形表的灵敏度分析(重点.难点.掌握)
• §2 线性规划的对偶问题 (重点.理解.掌握)
• §3 对偶规划的基本性质(重点.应用)
• §4 对偶单纯形法(难点.掌握---前面已讲) §1 单纯形表的灵敏度分析(重点.难点.掌握)
XS
b
B CB
检验数j
当迭代若干步，基变量为X B时，新的单纯形表: Cj
CB XB CB CN XN B-1N CN- CB B-1N 0 XS B-1 - CB B-1
XB
B-1b
I 0
检验数j
举例
maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36
• 最优基的逆
B*
1
例4：对称形线性规划问题：
maxZ=2x1+x2 5x2≤15
s.t.
6x1+2x2 ≤24
x1+x2 ≤5 x1,x2 ≥0 标准型：
maxZ=2x1+x2+0x3 +0x4 +0x5 5x2+x3 s.t. 6x1+2x2 x1+x2 +x4 =15 =24 +x5 = 5
…
amn
≤
bm
• 由表可以看出：
1. 从行看是原问题（Ⅰ），从列看是对偶问题（Ⅱ），两个问题 的变量系数矩阵互为转置矩阵。 2. 原问题（Ⅰ）的常数项是对偶问题（Ⅱ）的目标系数，反之， 原问题（Ⅰ）的目标系数是对偶问题（Ⅱ）的常数项。 3. 原问题（Ⅰ）有n个决策变量，对偶问题（Ⅱ）有n个约束方程； 原问题有m个约束方程，对偶问题就有m个决策变量。 4. 原问题的约束是“≤”型，对偶问题的约束是“≥”型。 5. 原问题的目标函数是求极大，对偶问题的目标是求极小。
y1 , y2 , y3 ≥0
1500 2500
原问题： max Z=1500x1+2500x2 s.t. 3x1+2x2 65 A资源 2x1+ x2 40 B资源 3x2 75 C资源 x1,x2 0
max 3 2 A= 2 1 0 3 c=
对偶问题： Min W = 65 y1 + 40 y2 + 75 y3
初始单纯形表为: Cj
0
CB XB CN XN N CN 0 XS I 0
XS
b
B CB
检验数j
当迭代若干步，基变量为X B时，新的单纯形表: Cj
CB XB CB CN XN B-1N CN- CB B-1N 0 XS B-1 - CB B-1
XB
B-1b
I 0
检验数j
小结
1. 对应初始单纯表中的单位矩阵I，迭代后的 单纯形表中为B-1 2. 初始单纯表中的基变量Xs=b，迭代后的单 纯形表中为XB= B-1b 3. 初始单纯表中的约束系数矩阵为： [A,I]=[B,N,I] 迭代后的单纯形表中约束系数矩阵为： [B-1A, B-1I]=[B-1B, B-1N, B-1I]=[I , B-1N, B-1] 4. 若初始矩阵中变量xj的系数向量为Pj，迭代 后为Pj ` ，则有： Pj ` =B-1 Pj
Cj CB 0 XB x3 x4 x5
b
8 12 36
3 x1
5 x2
0 x3
0 x4
0 x5
比 值
0 0
1 0 3
3
0 2 4
5
1 0 0
0
0 1 0
0
0 0 1
0
检验数j
• 最优基和最优基的逆
Cj
CB 0 5 XB x3 x2
3
5
x2 0 1
0
x3 1 0
0
x4 2/3 1/2
0
x5 -1/3 0
-M
-M
XB x6 x7
b
8
x1 1
6
3
2
0
0
-M
-1
-M
0
0
1
0
检验数j
Cj
4M-2 6M -3 2M-1
-2
-3
-1
0
0
-M
-M
CB
-3 -2
XB X2
x1
b
9/5
x1
0
x2
1
4/5
1
0
检验数j
4M-2 6M -3
最 终 3/5 -3/10 1/10 3/10 -1/10 单 纯 -2/5 1/5 -2/5 -1/5 2/5 形 表 2M-1 -M -M 0 0 格