运筹学第三章对偶理论第二讲对偶单纯形法,灵敏度与参数分析

格式：ppt
大小：683.50 KB
文档页数：47

下载文档原格式

运筹学第三章对偶理论第二讲对偶单纯形法,灵敏度与参数分析

1
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 (最优性条件,又叫对偶可行性条件)
定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基
变量；
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
(5)普通单纯形法的最小比值是问题的基本解可行，
bi min aik 0 其目的是保证下一个原 i aik
Chapter3 对偶理论 Dual Theory
例2.9 用对偶单纯形法求解：
m i n Z 9 x 1 12 x 2 15 x 3 2 x 1 2 x 2 x 3 10 2 x 1 3 x 2 x 3 12 x 1 x 2 5 x 3 14 x j 0( j 1.2.3)
Chapter3 对偶理论 Dual Theory
设线性规划问题为：
max Z CX ( P)
原始单纯形法的思想：从满足可行性条件的一个基可行解(即基B满足
AX ＝ b X 0
B b 0 )出发，经过换基运算迭代到另一个基可行解，
直到找到满足最优性条件( C C B 1 A 0 )的基可行解， B 这就是原问题的最优解。
y1 y2 2 y 4y 3 1 2 s.t. y1 7 y2 3 y1 0, y2 0

《管理运筹学》第3章--线性规划的对偶问题

x1 x2 x3 2
s.t.
x12x1x2
x3 x2
1 x3
2
x1 0; x2 , x3 ?
•
这样所有的约束条件均为“≤”和“=”类型，按前述对
应关系原则，可写出其对偶问题为：
minW ( y) 2 y1 y2 2 y3
y1 y2 2 y3 1
s.t.
y1 y1
y2 y2
min W ( y) 2 y1 6 y2 0 y3/ 0 y3//
y1
s.t.
0
y1
y1
2 y2 y3/ y3// 0
y2
y/ 3
y3/ /
2
6 y2 3 y3/ 3 y3//
5
y1
,
y2
,
y/ 3
,
y3/ /
0
13
OR:SM
• 再设y/3-y//3=y3，代入上述模型得：
始问题，则（3-2）称为对偶问题。
8
OR:SM
• 3.1.2 对称型线性规划问题——对称型对偶问题
•
• 每一个线性规划问题都必然有与之相伴随的对偶问题存在。先讨论对称型对偶问题；对于非对称型对偶问题，可以先转化为对称型，然后再进行分析，也可以直接从非对称型进行分析。
• 对称型线性规划问题数学模型的一般形式为
变量 m个
约束 ≤ ≥
= （方程）系数矩阵
b c
变量 ≥0 ≤0
无非负约束转置
c b
19
OR:SM
•
这样对于任意给定的一个线性规划问题，均可依据上述
对应关系直接写出其对偶问题模型，而无须先化成对称型。
• 例3 写出下列线性规划的对偶问题

运筹学 03 对偶理论及灵敏度分析

目标函数取值变量目标函数系数常数约束条件系数变量 - 约束约束 - 变量
例2：将下述线性规划作为原问题，请转换为对偶问题 max z=5x1+3x2+2x3+4x4 5x1+x2+x3+8x4≤8 2x1+4x2+3x3+2x4=10 x1≥0,x2≥0,x3任意,x4任意
1 对偶理论
对偶问题的提出原问题与对偶问题的数学模型原问题与对偶问题的对应关系对偶问题的基本性质影子价格对偶单纯形法
对偶问题的提出
例1：某厂利用现有资源(设备A、设备B、调试工序)生产两种产品(产品Ⅰ、产品Ⅱ)，有关数据如下表。问如何安排生产，使厂家利润最大？产品Ⅰ 产品Ⅱ 资源限量 0 5 15 6 2 24 1 1 5 2 1
CX*=bTY*
从弱对偶性可得到以下重要结论： (1)极大化问题(原问题)的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。 (2)极小化问题(对偶问题)的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。 (3)若原问题可行，但其目标函数值无界，则对偶问题无可行解。 (4)若对偶问题可行，但其目标函数值无界，则原问题无可行解。 (5)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。 (6)对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。
原问题与对偶问题的数学模型
原问题 max z=2x1+x2 5x2≤15 6x1+2x2≤24 x1+x2≤5 x1,x2≥0 互为对偶问题厂家对偶问题 min w=15y1+24y2+5y3 6y2+y3≥2 5y1+2y2+y3≥1 y1,y2,y3≥0

运筹学第三章对偶问题与灵敏度分析

x2 3x3 4x4 5
2x1 3x2 7x3 4x4 2
x1 0，x2 0, x3、x4无约束
答案： 1. max W 2 y1 3 y2 5 y3
2y1 3y2 y3 2
35yy11
y2 7y2
4y3 6y3
2 4
y1 0,y2 .y3 0
2. max W 3 y1 5 y2 2 y3
对偶理论与灵敏度分析
❖ 线性规划的对偶问题 ❖ 对偶问题的基本性质 ❖ 影子价格 ❖ 对偶单纯形法 ❖ 灵敏度分析
3.1 线性规划的对偶问题
一、问题的提出回顾例题1
例1 某工厂在计划期内要安排生产A、B两种产品（假定产
品畅销）。已知生产单位产品的利润与所需的劳动力、设备
台时及原材料的消耗，如表1.1所示
y3
2 3 5 1 无约束
课堂练习
1. min Z 2x1 2x2 4x3
2x1 3x2 5x3 2
3x1 x2 7 x3 3
x1 4x2 6x3 5
x1, x2 , x3 0
2. min Z 3x1 2x2 3x3 4x4
x1 2x2 3x3 4x4 0
CB XB b
0 x4 60 0 x5 10 0 x6 20
检验数j
CB XB b
0 x4 2 x1 -1 x2
检验数j
课堂练习
2 -1 1
x1
x2
x3
311 2 -1 2 1 1 -1
2 -1 1
x1
x2
x3
000 x4 x5 x6 100 010 001
00 0 x4 x5 x6 1 -1 -2 0 1/2 1/2 0 -1/2 1/2

运筹学对偶理论和灵敏度分析

对偶理论和灵敏度分析
1.单纯形的矩阵描述
用矩阵语言描述单纯形法的关键是写出两个基本的表达式,设线性规划的标准型为 maxz=CX AX=b X≥0
C=(CB,CN)，X=(XB,XN)’，A=(B,N)
由约束条件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得到用非基变量表示基变量的表达式:
-2 -3 -1 -1 1/3 x3 -1/3 0 x1 4/3 1 x5 1/3 0 0
' ' - a 1k / alk ' ' - a 2k / alk ... ' 1 / alk ... ' ' - a mk / alk
3对偶理论
某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。工时单耗生产能力产品甲乙车间 A 1 0 8 B 0 2 12 C 3 4 36 单位产品获利 3 5 • maxZ= 3x1 +5 x2 x1 ≤8 2x2 ≤12 S.t. 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0
(4)影子价格在资源采购决策中的应用。
当资源的市场价格低于影子价格，企业买进该资源，扩大生产，当资源的市场价格高于影子价格，企业应设法转让该资源。
(5)利用影子价格分析工艺改变后对资源节约的收益。例如设工厂现有钢材100吨，其影子价格为3/4，采用新工艺后，钢材可以节约2%，则由此带来的经济收益为：
(3)影子价格在新产品开发决策中的应用。产品资源 A B 影子价格(万元)
钢材煤机时
单位利润(万元)

对偶理论

第四节
灵敏度分析
灵敏度分析也称为优化后分析，是研究线性规划模型某些系数或限制量的变化对最优解的影响及其影响程度的分析过程。
一、影子价格及其应用
例7 某企业生产Ａ、Ｂ、Ｃ三种产品，每吨的利润分别为2000元、3000元和 1000元，生产单位产品所需的工时及原材料如表3-8所示。若供应的原材料每天不超过3吨，所能利用的劳动力总工时是固定的，应如何制定日生产计划，使三种产品的总利润最大？表3-8 生产每吨产品所需资源所需工时占总工时比例所需原材料（吨）产品Ａ 1/3 1/3 Ｂ 1/3 4/3 Ｃ 1/3 7/3
二、对偶问题的基本性质１．对称性。对偶问题的对偶是原问题。２．弱对偶性。若 X 是原问题的可行解， Y 是对偶问题的可行解。则存在 C X Yb ３．无界性。若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 ˆ ˆ ４．可行解是最优解时的性质。设 X 是原问题的可行解， Y ˆ ˆ ˆ Y 是对偶问题的可行解，当 CX Yb 时，X ， ˆ 是最优解。５．对偶定理。若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。 Y ６．互补松弛性。若 Xˆ ，ˆ 分别是原问题和对偶问题的可行 ˆ ˆ Y 解。那么 YˆX 0 和 Y X 0，当且仅当 X ，ˆ 为最优解。７．对应基解。设原问题是
y1 4 y 2 2
同理将生产每件产品Ⅱ的设备台时和原材料出租和出让的所有收入应不低于生产一件产品Ⅱ的利润，这就有
2 y1 4 y 3 3
把企业所有设备台时和资源都出租和出让，其收入为 8 y1 16y 2 12y 3
从企业的决策者来看当然ω愈大愈好，但从接受者来看他的支付愈少愈好，所以企业的决策者只能在满足所有产品的利润条件下，使其总收入尽可能地小，他才能实现其意愿，为此需解如下的线性规划问题：

第三章对偶单纯形法

··
≥ (c1,c2,…,cn)
y1，y2，…，ym≥0
m个变量，n个约束条件
2﹒约束条件全部为“=”的对偶
原问题：
max z=CX
max z=CX
max z=CX
AX＝b
等价
AX≤b AX≥b
AX≤b 等价－AX≤－b
X≥0
min ω=(Y1,Y2) A
(Y1,Y2) －A Y1,Y2≥0
b －b
承租
出让代价应不低于用同等数量的资源自己生产的利润。
厂家能接受的条件：
出用同让6等代y数价2量应的不y资低3 源于 2 5 y自1 己生2产y2的利y润3。 1
收购方的意愿：
min w 15 y 24 y 5 y
1
2
3
Ⅰ
Ⅱ
D
设备A
0
设备B
6
调试工序
1
5 15时 2 24时 1 5时
利润（元） 2
x1 0, x2 , x3 0, x4无限制max变S量个数5n y1 约4束y方2 程个6数yn3
2、求下列问题的对偶问题 min Z 2x1 3x2 5x3 x4
4x1 x2 3x3 2x4 5
s.t
3x1 2x2 7x4 2x1 3x2 4x3
4 x4
6
s.t
3﹒约束条件为“≥”的对偶
原问题：
max z=CX
max z=CX
对
AX≥b
等价
－AX≤ － b
偶
X≥0 min ω=Yb
对偶问题
X≥0
问
题
min ω=Y1 (－ b)
YA ≥C Y≤0
令Y= － Y1

运筹学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

第三章-对偶理论及灵敏度分析3课件

二、原问题与对偶问题的数学模型
继续
三、原问题与对偶问题的对应关系
返回
第三章-对偶理论及灵敏度分析3
一、对偶问题的提出
对
偶问
实例：某家电厂家利用现有资源生产两种
题
产品，有关数据如下表：
上页下页返回
设备A 设备B 调试工序
产品Ⅰ 产品Ⅱ
0
5
6
2
1
1
利润（元） 2
1
D
15时 24时 5时
第三章-对偶理论及灵敏度分析3
第三章对偶理论及灵敏度分析
3.1.1 线性规划对偶问题 3.1.2 对偶问题的基本性质 3.1.3 影子价格 3.1.4 对偶单纯形法 3.2.1 灵敏度问题及其图解法 3.2.2 灵敏度分析 3.2.3 参数线性规划
第三章-对偶理论及灵敏度分析3
3.1.1 线性规划的对偶问题
一、对偶问题的提出
下页
(Y1,Y2
)
A A
C
返回
Y1 0 ,Y2 0
第三章-对偶理论及灵敏度分析3
对偶问
(mY1inwY2 )(YA1YC2 )b
题
Y1 0, Y2 0
令 YY1 ，Y 得2对偶问题为：
上页
下页
maYxA
w C
Yb
返回
Y无约束
证毕。
第三章-对偶理论及灵敏度分析3
三、原问题与对偶问题的对应关系
设备B –––– 元／y时2
问题
调试工序 –––– 元y／3时
付出的代价最小，
且对方能接受。
上页
下页
出让代价应不低于
返回
用同等数量的资源
收

运筹学线性规划对偶问题

●对偶(min型)变量的最优解等于原问题松弛变量检验数的对偶(min型变量的最优解等于原问题松弛变量检验数的松弛变量绝对值 ●对偶问题最优解的剩余变量解值等于原问题对应变量的对偶问题最优解的剩余变量解值等于原问题对应变量的对应变量检验数的绝对值 ●由于原问题和对偶问题是相互对偶的,因此对偶问题的由于原问题和对偶问题是相互对偶的, 检验数与原问题的解也有类似上述关系. 检验数与原问题的解也有类似上述关系. ●更一般地讲,不管原问题是否标准,在最优解的单纯型更一般地讲,不管原问题是否标准, 都有原问题虚变量松弛或剩余) 虚变量( 表中,都有原问题虚变量(松弛或剩余) 的检验数对应其对偶问题实变量对偶变量)的最优解,原问题实变量实变量( 对偶问题实变量 (对偶变量)的最优解,原问题实变量(决策变量) 的检验数对应其对偶问题虚变量策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变的最优解.因此, 量)的最优解.因此,原问题或对偶问题只需求解其中之一就可以了. 一就可以了.
n
* j
,
∑b y
i =1 n i j =1 m
m
* i
≤ ∑ bi yi
i =1
m
∑ c j x j = ∑ bi yi ,
∴
∑cjxj ≤
* *
∑ bi yi
i =1 m i =1
m
*
∑c x = ∑c x
j =1 j j j =1 j
j
=
∑b y
i =1 i
* i
= ∑ bi yi
3.强对偶性(对偶定理) 强对偶性(对偶定理) 强对偶性定理如果原问题和对偶问题都有可行解, 定理如果原问题和对偶问题都有可行解,则它们都有最优且它们的最优解的目标函数值相等. 解,且它们的最优解的目标函数值相等. 证:第一步,证明都有最优解.原问题和对偶问题都有可第一步,证明都有最优解. 行解,由弱对偶定理推论1可知原问题目标函数有上界, 可知, 行解,由弱对偶定理推论可知,原问题目标函数有上界, 对偶问题的目标函数有下界,故一定存在最优解. 对偶问题的目标函数有下界,故一定存在最优解. 第二步,证明最优解的目标函数值相等.根据单纯形第二步,证明最优解的目标函数值相等. 法的矩阵描述,原问题有最优解,对偶问题为可行解, 法的矩阵描述,原问题有最优解,对偶问题为可行解,且二者的目标函数值相等,根据最优性定理, 二者的目标函数值相等,根据最优性定理,二者的解均为最优解. 最优解.

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

a
i 1
m
ij
yi
是生产该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。
当产品产值大于隐含成本时，表明生产该产品有利。当产品产值小于隐含成本时，表明用资源生产别的产品有利。
3.3 对偶单纯形法 Dual Simplex Method
3.3 对偶单纯形法 Dual Simplex Method
若第i 种资源的单位市场价格为mi ，则有当yi > mi 时，企业愿意购进这种资源，单位纯利为yi*－mi ，则有利可图；如果yi* < mi ，则企业有偿转让这种资源，可获单位纯利mi－yi * ，否则，企业无利可图，甚至亏损。结论：若yi* > mi 则购进资源i，可获单位纯利yi*－mi 若yi* < mi则转让资源i ，可获单位纯利mi－yi
2x1+ x2 = 51
P
1365=50x1+30x2
4x1+3x2 = 121 x1 4x1+3x2 = 120
可行域
L0： 50x1+30x2
Chapter3 对偶理论 Dual Theory
•2）影子价格是一种机会成本 • 影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。 *
y1 y2 2 y 4y 3 1 2 s.t. y1 7 y2 3 y1 0, y2 0
Chapter3 对偶理论 Dual Theory
特点4、表明生产过程中该种资源的影子价格不等于0，表明生产过程中资源得到充分利用。如果某种资源未得到充分利用，该种资源的影子价格=0；
定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基
变量；
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
(5)普通单纯形法的最小比值是问题的基本解可行，
bi min aik 0 其目的是保证下一个原 i aik
影子价格举例
A 工时材料 1 1
B 1 4
Chapter3 对偶理论 C Dual拥有量 Theory
1 7
3 9y1 9 y2
y*1=5/3, y*2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。如果有客户以高于5/3 的价格购买工时，则可以出售一些工时，反之则反
min W 3 y1 9 y2 y1 y2 2 y 4y 3 1 2 s.t. y1 7 y2 3 y1 0, y2 0
y*1=5/3, y*2=1/3
即工时的影子价格为 5/3，材料的影子价格为1/3。
影子价格的经济意义
Chapter3 对偶理论 Dual Theory
解:（1）将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行，即全部检验数≤0（求 max问题）。
Chapter3 对偶理论 Dual Theory
m axZ 9 x1 12x 2 15 x 3 10 2 x1 2 x 2 x 3 x 4 x5 12 2 x1 3 x 2 x 3 x 6 14 x1 x 2 5 x 3 x16 0
• 1. 影子价格的数学分析：
maxZ CX AX b P X 0 minW Yb YA C D Y 0
由对偶问题得基本性质可得：
z c j x j bi yi
j 1 i 1
n
m
影子价格举例
Chapter3 对偶理论 Dual Theory
对偶单纯形法的计算步骤：
(1)将线性规划的约束化为等式，找出一个正则基，即全部检验数λj≤0（max）或λj≥0（min）, 求出其对应的基本解，当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi<0，则进行换基计算； (2) 换基计算 (i)先确定出基变量: bl＝min bi | bi 0 l 行对应的变量出基；
Chapter3 对偶理论 Dual Theory
表3-7
XB
表(1) λj 表(2) λj
x4 x5 x2 x5 x2 x1
x1 -1 -1 4 1 [-2] 3↑ 0 1 0
x2 [-1] 1 1↑ 1 0 0 1 0 0
x3 -1 4 3 1 3 2 5/2 -3/2 13/2
x4 1 0 0 -1 1 1 -1/2 -1/2 5/2
j min | alj 0 对偶单纯形法的最小比值是 j alj
其目的是保证下一个对偶问题的基本解可行； (6)对偶单纯形法在确定出基变量时，若不遵循
bl min bi | bi 0
规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样．
A 工时材料单件利润 1 1 2
B 1 4 3
C 1 7 3
拥有量 3 9
分析： 1. y1=5/3说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来5/3元的利润；如果要出售该资源，其价格至少在成本价上加5/3元。如果y1为0，则表示增加第一种资源不会增加利润，因为第一种资源还没有用完。
•2. 影子价格的经济意义
•1）影子价格是一种边际价格 • 在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量yi 就是第 i 种资源的影子价格。即：
Z * y i * ( i 1,2 m ) bi
Chapter3 对偶理论 Dual Theory
问题：可否从满足条件(2)的基出发去找原问题的最优解？对偶单纯形法思想：从满足条件(2) 的基(一般称为正则基)B出发，经过换基运算到另一个正则基，即一直保证条件 (2)成立，直到找到一个满足条件(1)的正则基。
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
1
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 (最优性条件,又叫对偶可行性条件)
L0： 50x1+30x2
Chapter3 对偶理论 Dual Theory

影子价格的直观含义： x2 2x1+ x2 = 50
（P）max Z = 50x1+30x2 s.t. 4x1+3x2 ≤ 120 2x1+ x2 ≤ 50 x1，x2 ≥ 0 Z*=1350 Y*=(5,15)
1355=50x1+30x2
Chapter3 对偶理论 Dual Theory
min z 4 x1 x2 3x3
【例3.9】用对偶单纯形法求解
x1 x2 x3 5 x1 x2 4 x3 3 x , x , x 0 1 2 3
【解】先将约束不等式化为等式，再两边同乘以(－1)，得到
cj cB xB
-9 x1
-12 -15 x2 x3
0 x4
0 x5
0 x6
b
i
0 0 0
x4 x5 x6
-2 -2 -1 -9
-2 -3 -1
-1 -1 -5
1 0 0 0
0 1 0 0
0 0 1 0
λj
-12 -15
-10 (-9/-1 -12 .-12/-1 -14 . -15/-5 0 )
Chapter3 对偶理论 Dual Theory
例2.9 用对偶单纯形法求解：
m i n Z 9 x 1 12 x 2 15 x 3 2 x 1 2 x 2 x 3 10 2 x 1 3 x 2 x 3 12 x 1 x 2 5 x 3 14 x j 0( j 1.2.3)
影子价格王老板的家具生产模型的图解： x2
2x1+ x2 = 50
（P）max Z = 50x1+30x2 s.t. 4x1+ 3x2 ≤ 120 2x1+ x2 ≤ 50 x1，x2 ≥ 0 Z*=1350 Y*=(5,15)
（15，20）
P
1350=50x1+30x2
可行域
4x1+3x2 = 120 x1
若yi 0, 有 aij x j bi
j 1
n
若 aij x j bi, 有yi 0
j 1
n
Chapter3 对偶理论 Dual Theory
特点5、从影子价格考察单纯形表的计算。
j c j C B B Pj c j aij yi
1 i 1
m
Cj代表第j种产品的产值，
min z 4 x1 x2 3x3 x1 x2 x3 x4 5 x1 x2 4 x3 x5 3 x 0, j 1, 2,,5 j
x4、x5 为基变量，用对偶单纯形法，迭代过程如表2-7所示。
3.3 对偶单纯形法 Dual Simplex Method
• 影子价格是根据资源在生产中作出的贡献而作出的估价，这种估价不是资源的市场价格。它反映了在最优经济结构中，在资源得到最优配置前提下，资源的边际使用价值。单纯形表中松弛变量所对应的检验数的相反数是在该经济结构中的影子价格，也可以说对偶问题的最优解向量是结构中的影子价格。

运筹学第三章对偶理论第二讲对偶单纯形法,灵敏度与参数分析

合集下载