当前位置：文档之家 › 第二章 对偶问题

第二章 对偶问题

  • 格式：ppt
  • 大小：3.28 MB
  • 文档页数：45

下载文档原格式

  / 45

合集下载

第2章 对偶问题

第2章 对偶问题

第2章 对偶问题判断下列说法是否正确：对偶问题的对偶问题一定是原问题；根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解； 已知*i y 为线性规划的对偶问题的最优解，若*i y >0，说明在最优生产计划中的i 种资源已完全耗尽；已知*i y 为线性规划的对偶问题的最优解，若*i y ＝0，说明在最优生产计划中第i 种资源一定有剩余；若某种资源的影子价格等于k ，在其它条件不变的情况下，当改种资源增加5个单位时，相应的目标函数值将增大5k ； 在线性规划问题的最优解中，如某一变量j x 为非基变量，则在原来问题中，无论改变它在目标函数中的系数j c 或在各约束中的相应系数ij a ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其它列数字的变化。

简答题、试述对偶单纯形法的优点及其应用上的局限性。

、试述对偶单纯形法的步骤。

、试解释对偶解的经济含义和影子价格在市场决策中的作用。

、什么是资源的影子价格？同相应的市场价格之间有何区别？以及研究影子价格的意义是什么？:判断下列说法是否正确，为什么？（a ）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； （b ）如果线性规划的对偶问题存在可行解，则其原问题也一定无可行解；（c ）在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数都一定不超过其对偶问题可行解的目标函数。

若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数最大值将增加5k 吗？ 已知*i y 为某线性规划问题的对偶问题最优解中的第i 分量，若*i y ＝0，能否肯定在最优生产计划种第i 种资源一定有剩余？写出对偶问题写出下列线性规划问题的对偶问题123max 102Z x x x =++123123123420,,0x x x x x x ++≤≥写出下列线性规划问题的对偶问题1234max 23Z x x x x =+++12341231341324252341,0,,x x x x x x x x x x x x x x +++≤-+=--+≥≥无约束写出下列线性规划问题的对偶问题1234min 3234Z x x x x =+-+1234234123414232343345237420,0,,x x x x x x x x x x x x x x x -++≤++≥----=≥≤无约束写出下列线性规划问题的对偶问题123min 567Z x x x =---123123123123531556102050,0,x x x x x x x x x x x x -+-≥--+≤--=-≤≥无约束写出下列线性规划问题的对偶问题123max 25Z x x x =++12312313123235237365,,0x x x x x x x x x x x ++≤++≤+≤≥写出下列线性规划问题的对偶问题123max Z x x x =++1231312327664,,0x x x x x x x x ++=+≥≥写出下列线性规划问题的对偶问题123min 423Z x x x =++123123131232562742,0,0x x x x x x x x x x x ++≤++=+≥≤≥无约束写出下列线性规划问题的对偶问题：1231231231231232242352373..465,,0MinZ x x x x x x x x x s t x x x x x x =++++≥⎧⎪++≤⎪⎨++≤⎪⎪≥⎩写出下列线性规划问题的对偶问题：12312312312312323231325..34,,0,MinZ x x x x x x x x x s t x x x x x x =--+-=⎧⎪-+≥-⎪⎨-+≤⎪⎪≥⎩无限制写出下列线性规划问题的对偶问题：123123123131232423134..40,0,MaxZ x x x x x x x x x s t x x x x x =++++≥⎧⎪-+≤⎪⎨+=⎪⎪≥≤⎩无限制写出下列线性规划问题的对偶问题：1234512345123451~45275354625..232690,MaxZ x x x x x x x x x x s t x x x x x x x =++++++++=⎧⎪++++=⎨⎪≥⎩无限制写出下面线性规划问题的对偶问题12max 52z x x =-+1212123235,0x x x x x x -+≤-+≤≥写出下面线性规划问题的对偶问题12max 56z x x =+12122553x x x x +=-+≥1x 无限制2,0x ≥设有原始问题123max 325z x x x =++约束条件：12313121232560324204400,,0x x x x x x x x x x ++≤+≤+≤≥写出以上原始问题的对偶问题。

运筹学课件 第二章-对偶问题

运筹学课件 第二章-对偶问题

2.4 运输问题
2.1 线性规划的模型与图解法
2.1.1 问题的引入 （１）生产安排问题 如何合理使用有限的人力、物力和资金， 使得收到最好的经济效益。
例1：某工厂可生产甲、乙两种产品，需消耗煤、 电、油三种资源。现将有关数据列表如下：
资源单耗 资源 产品
甲 9 4 3 7
乙 4 5 10 12
•约束条件的类型与非负条件对偶 •非标准的约束条件类型对应非正常的非负规划：
min z 5 x x 3 x
1 2
3
2x 2x x 1
1 2 3
x 3 x 4 x 10
1 2 3
2x 2x x 5
2.3.2 灵敏度分析
一、定义：
灵敏度分析讨论建模时的系数及有关变量变化时对 解的影响。 反映在两个方面
最优性： j C j C B B 1 Pj 1 可行性：X B B b
二、目的：
（1）参数在何范围内变化最优解（基）不变。 （2）参数变化，最优解有何变化。 1.资源向量b的变化分析
4.最优性
设X，分别是( P )与( D )问题的可行解， Y 且C X Y b，则 X， Y皆为最优解。
图示为：
CX Yb
z w CX Yb
* *
5.强对偶性 设 如果(P)问题有最优解，则(D)问题也有最 优解，且最优值相等。 证：对(P)增加松弛变量XS，化为标准型：
min w 2 y1 y2 y1 2 y2 1 y1 y 2 1 y1 y2 0 y , y 0 1 2
s.t.
s.t.
若原问题xj≤0，则对偶问题第j个约束
反号（与规定形式比）。同理，若原问题 第i个约束反号（与规定形式比），则对偶 问题yi≤0。

运筹学课件第二章对偶问题

运筹学课件第二章对偶问题

第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求 1、掌握对偶理论及其性质 2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法 二、课时 6学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。

应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。

例：某家具厂木器车间生产木门与木窗；两种产品。

加工木门收入为56元/扇，加工木窗收入为30元/扇。

生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。

问：(1)该车间应如何安排生产才能使每日收入最大？(2)假若有一个个体经营者，手中有一批木器家具生产订单。

他想利用该木器车间的木工与油漆工来加工完成他的订单。

他就要考虑付给该车间每个工时的价格。

他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。

解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为⎪⎩⎪⎨⎧≥≤+≤++=-0502120343056max 21212121x x x x x x x zX*=(15,20)’ Z*=1440元解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格⎪⎩⎪⎨⎧≥≥+≥++=-0303562450120min 21212121y y y y y y y wY*=(2,24)’ W*=1440元将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。

第二章对偶理论

第二章对偶理论
第二章 对偶线性规划
原始问题（prime)与对偶问题之间的关系
•
极小化问题 （min)
• 变量 • • • 约束 • •
Xj ≥0 Xj :unr Xj ≤ 0 ∑aijxj ≥ bi ∑aijxj = bi ∑aijxj ≤ bi
极大化问题 （max)
约束 ∑aijwj ≤ bi ∑aijwj =bi ∑aijwj ≥ bi
变量 wj ≥0 wj: unr wj ≤ 0
第二章 对偶线性规划
对偶问题的形成
min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 ≥ 6
-x1+2x2-3x3 = 12 2x1+x2+2x3 ≤ 8 x1+3x2-x3 ≥ 15
x1≥0 x2≤0 x3: unr
max w=6y1+12y2+8y3+15y4 s.t. 3y1- y2+2y3+ y4 ≤ 2
单纯形法的迭代过程
Ъi≥0 σj ≥ 0
Ъi≥0 σj≤0
对偶单纯形法的迭代过程
Ъi ≤ 0 σj≤0
第二章 对偶线性规划
Ъi≥0 σj≤0
2、对偶单纯形法 例题1
Hale Waihona Puke minω=15y1+5y2+11y3 s.t. 3y1+2y2+2y3≥5 5y1+y2+2y3≥4 y1，y2，y3≥0
直接写成标准式时有-S1 和-S2,则无法有初始基, 因此乘个-1
对偶问题是资源定价问题，对偶问题的最优解y1、y2、...、 ym称为m种资源的影子价格（Shadow Price）
第二章 对偶线性规划

第二章对偶理论

第二章对偶理论

3 5
x1 , x2 , x3 0
解：首先将原式变形
max Z 2 x1 3 x2 4 x3
2 x 3 x2 5 x3 2
3 x1 x2 7 x3 3
x1 4 x2 6 x3
5
x1 , x2 , x3 0
注意：以后不强调等式右段项 b≥0，原因在对偶单
纯型表中只保证 而j 不0 保证
=（1.1），分别是
（P_）_ 和__（D）的可行解。Z=10 ，W=40，故有
C X ＜ Y b ，弱对偶定理成立。由推论⑴可知，W 的最
小值不能小于10，Z 的最大值不能超过40。
例二、已知
p : max Z x1 2x2
D : minW 2 y1 y2
x1 x2 x3 2
2x1 x2 x3 1
n
j 1
aij
yi
cj
（对偶问题）
yi 0
目标函数 约束条件
原问题
对偶问题
max
min
≤
≥
变量数量 约束条件个数
约束条件个数 变量数量
例三、
23
x1
x2
原问题
12 y1 2
2
≤ 12
8
y2
1
2
≤
8
16 y3 4 0 ≤ 16 12 y4 0 4 ≤ 12
对偶问题 2 3
二、线性规划的对偶理论
原问题 问题无界
无可 行解
对偶问题 无可 行解
问题无界
（对）
y1 y1
y1
y2 y2 0, y2
2 1 0
无可 行解
推论⑶.在一对对偶问题（P）和（D）中，若一个可 行（如P），而另一个不可行，（如D），则该可行的 问题无界。

运筹学第二章对偶问题

运筹学第二章对偶问题

y1
1 2
y2
4 0
y3
0
y4
1 0
M
y5
1 0
0
y6
0 1
M
y7
0 1 0
i

3/4
y5 y7
[ 4]
83M 164M 124M
8
16
12
0
M
0
M
CB XB
M M
b
2 3
y1
1 2
y2
4 0
y3
0
y4
1 0
M
y5
1 0
0
y6
0 1
M
y7
0 1 0iFra bibliotek3/4y5 y7
[4]
83M 164M 124M
对偶
3y1 +4y2 3y4 +3y5 4
6y1 + y2 + y4 y5 6
y1 , y2 , y4 , y5 0
x1 ，x2 ，x3 0
Min w = 440y1 100y2 +200y4 200y5 2y1 6y2 +5y4 5y5 3 3y1 +4y2 +3y4 3y5 4 6y1 + y2 + y4 y5 6 y1 , y2 , y4 , y5 0
两边乘以“1”
Min w = 3x1 +9x2 +4x3 St. x1 + 2x2 +3x3 = 180 2x1 +3x2 x3 60
对偶
Max z = 180y1 60y2 +240y3 y1 2y2 +5y3 3
2y1 +3y2 +3y3 9 3y1 y2 =4 y1 ：unr, y2 , y3 0,

第二章 线性规划的对偶理论1-对偶问题


矩阵表达形式：
min w Y b AY C Y 0
对偶的经济解释
1、原问题是利润最大化的生产计划问题
总利润（元）
单位产品的利润（元/件）
产品产量（件）
max z c1 x1 c2 x2 cnx n b1 s.t. a11 x1 a12 x2 a1n xn xn 1 xn 2 b2 a21 x1 a22 x2 a2 n xn xn m bm am1 x1 am 2 x2 amn xn x1 x2 xn xn 1 xn 2 xn m ≥ 0 消耗的资源（吨）
第二章 对偶理论与灵敏度分析
第一节 线性规划的对偶问题
每一个线性规划问题都存在一个与其对偶的问题，在求出
一个问题的解的时候，同时也给出了另一问题的解。
例：某公司计划生产甲、乙两种产品，已知各生产一件时 分别占用的设备A、B的台时、调试时间和调试工序每天可用于 这两种产品的能力、各销售一件时的获利情况，如下表所示。 问该公司应生产两种产品各多少件，使获取的利润为最大。
A
b
约束系数矩阵
约束条件右端项向量
约束系数矩阵的转置
目标函数中价格系数向量
C
目标函数
目标函数中价格系数向量
max z
约束条件右端项向量
min w
c
j 1
n
j
xj
b
i 1
m
i
yi
变量 xj (j=1,·,n) · ·
约束条件有n个
xj ≥0
xj ≤0 xj 无约束 约束条件有m个 ≤bi ≥bi =bi
min z 2 x1 3x 2 5 x3 x 4

第二章对偶问题

m z i1 n y 1 5 2y 2 4 5 y 3
本次您浏览到是第四页，共五十五页。
这样得到一个新的线性规划问题
minw 15y1 24y2 5y3
5y1
6y2 2y2
y3 y3
2 1
y1, y2, y3 0
称这一问题是原来的LP问题的对偶线性规 划问题或对偶问题，原来的LP问题也称为原问 题。
内容总结
第二章对偶问题。变量：所有变量均具有非负约束。A’Y ≥C’。若迭代后的 单纯形表为最终表则该表也同时给出对偶问题的最优解。反之若一个约束条 件中松弛变量非零,则其对应的对偶变量为零。式中bi是线性规划原问题约束 条件的右端项，它代表第i种资源的拥有量。影子价格是资源的边际价格。最 优目标函数值：w*=-8.5（z*=8.5）。问题的最优解或最优基不变。例：在第 一章美佳公司的例1中。由弱对偶性，原问题目标函数无界
• 利用影子价格可以说明：单纯形法中的检验数可以看 成生产某种产品的产值与隐含成本的差
• 可以利用影子价格确定企业内部的核算价格，以便 控制有限资源的使用和考核下属企业经营的好坏。
本次您浏览到是第二十四页，共五十五页。
例1
6x1+2x2 =24
资源的变化 ：设备B的可 用时间从增 加一小时
可行域
x2=3
本次您浏览到是第二十六页，共五十五页。
第四节 对偶单纯形法
按对偶问题与原问题之间的关系，对最大 化问题，在用单纯形法求解原问题时，最 终表不但给出了原问题的最优解，而且其 检验数的相反数就是对偶问题的最优解。
本次您浏览到是第二十七页，共五十五页。
单纯形法求解的基本思路
基可行解
保持解的可行性
检验数非正
设 x*j(j1,,n) 和 yi*(i1,,n) 分别是原问题和 对偶问题的最优解，则由对偶性质，有

运筹学第2章-线性规划的对偶理论

❖ 影子价格不是市场价格，而是在现有技术和管理条件下， 新增单位资源所能够创造的价值，是特定企业的一种边 际价格；不同企业或同一企业不同时期，同种资源的影 子价格可能不同；当市场价格高于影子价格，可以卖出； 相反，则应买进，以获取更大收益
Ma例x：Z （ 2第x一1 章3例x22）
2 x1 2 x2 12
当原问题和对偶问题都取得最优解时，这 一对线性规划对应的目标函数值是相等的：
Zmax=Wmin
二、原问题和对偶问题的关系
1、对称形式的对偶关系
（1）定义：若原问题是
MaxZ c1 x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn b1
s.t.a21
x1
a22
二、 手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量；
5y3 3
，y
2
3
0
（用于生产第i种产 品的资源转让收益不 小于生产该种产品时 获得的利润）
对偶变量的经济意义可以解释为对工时及原材 料的单位定价 ；
若工厂自己不生产产品A、B和C，将现 有的工时及原材料转而接受外来加工时， 那么上述的价格系统能保证不亏本又最富 有竞争力（包工及原材料的总价格最低）
内，使得产品的总利润最大 。
MaxZ 2x1 3x 2
2x1 2x2 12
s.t.54xx12
16 15
x1, x 2 0
它的对偶问题就是一个价格系统，使在平衡了 劳动力和原材料的直接成本后，所确定的价格系统 最具有竞争力：
MinW 12y1 16y2 15y3
2y1 4y2
2
s.t.2y1y，1y
y1, y2, , ym 0

第2章 线性规划(对偶问题)


对偶问题（或原问题）
目标函数为 Min W
n个
约束条件
＝
m个
变量
0 0 无约束
约束条件右端项cj 价值系数bi 约束条件的系数矩阵AT
例：
• 写出下面线性规划问 题的对偶问题：
• 1.
max Z 2x1 x2 3x3 x4
x1 x2 x3 x4 5
s.t.
2x1 x2 3x3
原问题（对偶问题）
目标函数 限定向量 价值向量 技术系数 约束条件 变量数目 约束条件个数 变量正负
对偶问题（原问题）
目标函数 价值向量 限定向量 技术系数 对偶变量 约束条件个数 对偶变量数目 约束条件
非对称形式的对偶问题
• 在原线性规划问题为Max型，且变量非负 的前提下：
1. 原问题约束条件是“”型
x1
x3
x4
1
4
x1, x3 0, x2 , x4无约束
• 解：根据上述对偶关 系，可以写出原问题 的对偶问题：
min W 5 y1 4 y2 y3
y1 2 y2 y3 2
s.t.
y1 y1
y2 1 3y2 y3
3
y1
y3
1
y1 0, yLeabharlann 0, y2无约束例：y1
0,
y3
0,
y2无约束
对偶的基本性质
• 原问题： Max Z=CTX
• 对偶问题： Min W=bTY
s.t. AXb X0
s.t. ATY C Y0
• ①对称性：对偶问题的对偶是原问题； • ②弱对偶性：若X是原问题的可行解，Y是
对偶问题的可行解，则CTX bTY
• 弱对偶性的证明： AX’ b X’TAT bT X’TATY’ bTY’
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
引例 1 生产计划问题 max Z 2 x1 3 x2 原问题 某工厂用三台设备生产两种产品，已知的条 2 x1 2 x2 12 x 2x 8 件如表所示，试制订总利润最大的生产计划 1 2
3 x2 9 设备 I产品 x1 , x2 0
II产品
总有效台时
则有
CX 。 Yb
三、最优性定理
ˆ,Y ˆ 分别是(1)和(2)的可行解，且 如果 X ˆ Y ˆb，则 X ˆ,Y ˆ 分别是(1)和(2)的最优解. 有 CX
原问题 max Z CX
对偶问题 min Yb
YA C s.t. （4） Y自由变量
AX b s.t. （3） X 0
0 6 1 1 0 1. 得到原问题的基本可 A 行解的同时，其检验 5 2 1 0 1
例： max( ) 15y1 松弛变量 24 y2 5 y 0 y 4 0 y5 3 ←→ 决策变量
5 x2 15 ←→剩余变量 6 y2 y 4y 2 6 y2 2决策变量 3 y 4 3y 6 x 1 2 x2 24 基变量 ←→非基变量 y12 y2 y y y 1 5 y15 y y 1 2 3 5 2 3 5 x x 5 2 1 非基变量 ←→ 基变量 y 0 , i 1 , 2 , , 5 i 0, i 1, 2, ,5 y i x1 , x2 0
x1 2 x 2 2 x3 3 x 4 20 2 x1 x 2 3 x3 2 x 4 20 x 0 ( j 1,2,3,4) j
其对偶问题为： minW 20y1 20y 2
y1 2 y 2 1 2 y y 2 1 2 2 y1 3 y 2 3 3 y 2 y 4 2 1 y1 , y 2 0
1
i 1
m
2.5
对偶单纯形法
例： min 15y1 24 y2 5 y3 6 y2 y3 2 5 y1 2 y2 y3 1 y 0, i 1,2,3 i 原问题
小结：在单纯形表格中
数的相反数就构成了 0 6 1 1 0 对偶问题的一个基本 A 解。
min b Y
T
T
AT Y T C T 对称式对偶 s.t. Y 0 max min
价值向量 限定向量
限定向量b 价值向量C
m个约束，n个变量
约束条件“≤”
n个约束，m个变量
变量“≥”
变量“≥”
约束条件“≥”
原问题 max Z CX
对偶问题
min bT Y T
T T T AX b A Y C s.t. s.t. 非对称式对偶 X 0 Y自由变量 min max
1 、松弛变量与对偶变量的乘积有什么关系？
松弛变量与对偶变量的乘积=0 2、对偶问题的最优解与什么对应？ 对偶问题的最优解是原问题松弛变量检 验数的相反数. 结论：将原始单纯形表中松弛变量的检 验数反号恰好得对应对偶问题的一个解。
事实上，我们把原始问题写成
max Z CX 0 X S AX IX S b X , X S 0
基变量
X3 X1
X1
X2
X3
X4
X5
解
0 1
0 0
1 0
5/4 1/4
-15/2 15/2 -1/2 7/2
X2
0
0
1
0
0
0
-1/4 3/2
-1/4 -1/2
3/2
-17/2
-Z(目标)
检验数全部<0,于是得到最优解为
X=(7/2,3/2,15/2,0,0) ,最优值为:Z=17/2, 把松弛变量的检验数的相反数(0,1/4,1/2)带 入对偶问题中,看有什么规律?
目标函数中变量的系数
m个 第i个为 约束条件 第i个为 第i个为
约束条件右端项
m个 yi 变量 yi yi 无约束
约束条件右端项
目标函数中变量的系数
例2：给出下列线性规划的对偶问题： min Z=2X1+ 8 X2 -4X3 X1+3X2 – 3X3 > =30 -X1 +5X2 + 4X3 =80 st. 4X1+ 2X2 -4X3 < =50 X1 < =0, X2 > =0, X3 无约束 其对偶问题为： MAX w=30 y1 +80 y2 +50y3 y1 - y2 +4y3 〉=2 st. 3 y1 +5y2 +2 y3 <=8 -3y1 +4y2 -4y3 =-4 y1 >=0, y2 无约束，y3 <=0
（ 1）
其中 其对偶问题写成
X S ( xn1 , xn2 ,, xnm )T
minW Yb 0YS
YA YS C Y , YS 0
（ 2）
其中
YS ( ym1 , ym2 ,, ymn )T
T 设 (X T , X S ) 为原始问题（1）的一个基本可行解
四、强对偶定理 对于一对对偶问题，其中一个有有限最优 解，则另一个也有最优解，且两个目标函数值 相等。 五、无界性定理
对于一对对偶问题，若一个有无界解， 则另一个无可行解。
例 3 已知原问题 maxZ x1 2x2 3x3 4x4
x1 2 x 2 2 x3 3 x 4 20 2 x1 x 2 3 x3 2 x 4 20 x 0 ( j 1,2,3,4) j
A B C
单位产品的利 润（千元）
2 2 12 对偶问题 1 2 8 min 12 y1 8 y2 9 y3 0 3 92 2 y y 1 2 2 3 求max 2 y 2 y 3 y 3
y 0 i 1,2,3 i
1 2 3
换一角度：将设备卖出，售价定为多少适宜？
原问题的松弛变量为: X5 , X6 , 对偶问题的剩余变量为: Y3,Y4, Y5,Y6, 将(6/5,1/5)代入1)和2)知: Y3,Y4, 均不为0,于是由松 弛互补定理知: X1, X2 , =0 又由 Y1>0,Y2>0和松弛互补定理知: X5 , X6 ,=0 从而,原问题的约束变为: 2X3 + 3X4 =20 3X3 + 2X4 =20 解此方程得: X3 = X4 =4 于是原问题的最优解为:(0,0,4,4)
其对偶问题为： minW 20y1 20y 2
y1 2 y 2 1 2 y y 2 1 2 2 y1 3 y 2 3 3 y 2 y 4 2 1 y1 , y 2 0
试估计它们的目标函数值的界，并验证弱对偶定理的正确性。
解: 由观察知
七、单纯形表的双重含义 例6：用单纯形法，解线性规划， （LP1） maxZ=2X1+ X2 5 X2<=15 6 X1+2 X2<=24 st. X1+ X2<=5 X1>=0, X2>=0
对偶问题为: （LP2） min W=15Y1+24Y2+5Y3 6Y2+Y3>=2 ST. 5Y1+2Y2+Y3>=1 Y1>=0,Y2>=0
要求：1）写出对偶问题；
2）已知原问题的最优解为x1= -5, x2=0, x3= -1; 试根据对偶理论直接求出对偶问题最优解。
解：1）对偶问题 max 4 y1 6 y 2
y1 y 2 2 y y 1 1 2 y1 y 2 2 y1 , y 2 无 约 束
ˆ i 0时 ， 必 有 ˆ j bi ; 1 ） 如y aij x
j 1 n
Байду номын сангаас
六、互补松弛性定理
ˆ j bi 时 ， 必 有 ˆ i 0；i 1,2,, m 当 aij x y
j 1
ˆ j 0时 ， 必 有 ˆi c j ; 2 ） 如x aij y
i 1
YS 和 Y 中至少有一个小于零。
这时对应的对偶问题的解为非可行解。 当原始问题获得最优解时，表明 1 1 和 C C B A0 CB B 0 B YS 0 Y 0 , 即 此时对偶问题也同时获得最优解。
2.4 影子价格
一、影子价格的含义 根据资源在生产中作出的贡献而作的估 价。 是对第i 种资源实现最大利润的一种估计， 是对偶问题的最优解。 二、影子价格的特点 1.区别于市场价格，市场价格相对稳定； 而影子价格不稳定，依赖于资源的利用。
YS ,Y
上述对应关系如表
重要结论： 1.原始问题的单纯形表中，原始问题的松弛变量 的检验数对应于对偶问题的决策变量，而原始问题 的决策变量的检验数对应于对偶问题的松弛变量， 只是符号相反；
1 1 CB B A 2.在获得最优解之前， C C B B ，及 的各分 量中至少有一大于零，即
限定向量b 价值向量C
价值向量
限定向量
m个约束，n个变量
约束条件“=”
n个约束，m个变量
变量自由变量
原问题（对偶问题）
目标函数max
n个 x j 0 变量 x j 0 x 无约束 j
对偶问题（原问题）
目标函数min
第j个为 约束条件 第j个为 第j个为 n个
m
ˆ i c j时 ， 必 有 ˆ j 0；j 1,2,, n 当 aij y x
i 1
m