当前位置：文档之家 › 线性规划对偶理论

线性规划对偶理论

  • 格式：pdf
  • 大小：152.44 KB
  • 文档页数：24

下载文档原格式

  / 24

合集下载

第三章 线性规划的对偶理论

第三章 线性规划的对偶理论

s.t. AX=b X≥0 由于 AX=b 即 AX=b
AX≤b AX≥b
AX≤b -AX≤-b 所以，原问题可化为 max z=CX s.t. AX≤b -AX≤-b X≥0
A
X≤ -A
b
-b
14
设Y'：AX≤b的对偶变量（行向量） Y''：-AX≤-b的对偶变量（行向量） 按对称形式的对偶关系可得出原问题的对偶问题如下： min w =Y'b-Y''b= （Y'-Y''）b （Yb=bTYT） s.t Y'A-Y''A≥C （ YA=ATYT） Y'≥0，Y''≥0 令Y= Y'-Y''，则对偶问题为 min w =Yb s.t YA≥C Y符号不限 结论：原问题中约束条件为等式，对应的对偶变量 无非负要求；反过来同样成立。
s.t. 2y1+ y2+ 4y3 ≥2
2y1+2y2+ 4y4 ≥3 y1, y2 , y3 , y4 ≥ 0
解：2.首先将原式变形
m axZ 2 x1 3 x 2 4 x 3 2 x 3 x 2 5 x 3 2 3 x1 x 2 7 x 3 3 x1 4 x 2 6 x 3 5 x1 , x 2 , x 3 0
对于非对称形式的规划，可以按照下面的对应关系直接给 出其对偶规划。 （1）对原问题模型为“max，约束条件为≤”或“min，约 束条件为≥” 的形式，对应的对偶规划的变量大于 0 ；反之， 若原问题模型为“max，≥”或“min，≤” 的形式，对应的 对偶规划的变量小于0。 （ 2 ）原问题线性规划的决策变量大于 0 ，则对偶问题的模 型为“max，约束条件为≤”或“min，约束条件为≥” 的形 式；若原问题线性规划的决策变量小于0；则对偶问题的模型 为“max，≥”或“min，≤” 的形式。

第二章 线性规划的对偶理论

第二章 线性规划的对偶理论
max 3 2 A= 2 1 0 3 c=
对偶问题： Min f = 65 y1 + 40 y2 + 75 y3
s.t. 3y1 + 2 y2
y1, y2 , y3
min
≥1500
≥ 0
2y1 + y2 + 3y3 ≥2500
b=
65 40 75
A=
3 2
2 1
0 3
b=
1500 2500
1500 2500
例：
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
二、对偶规划问题的求解
1、利用原问题的最优单纯形表
3x1 x2 3x3 ≤100 x1, x2 , x3 ≥0 解: 对偶问题为
min w 100y1 100y2
max z 4 x1 3x2 7 x3 s.t. x1 2 x2 2 x3≤100
s.t.
2 y1 y2 ≥3 2 y1 3 y2≥7
原问题检验数与对偶问题的解的总结
•在主对偶定理的证明中我们有：对偶(min型)变量的最 优解等于原问题松弛变量的机会成本，或者说原问题松 弛变量检验数的绝对值 •容易证明，对偶问题最优解的剩余变量解值等于原问 题对应变量的检验数的绝对值 •由于原问题和对偶问题是相互对偶的，因此对偶问题 的检验数与原问题的解也有类似上述关系。 •更一般地讲，不管原问题是否标准，在最优解的单纯 型表中，都有原问题虚变量(松弛或剩余) 的检验数对应 其对偶问题实变量 (对偶变量)的最优解，原问题实变量 (决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩 余变量)的最优解。因此，原问题或对偶问题只需求解 其中之一就可以了。

线性规划的对偶理论(第一部分

线性规划的对偶理论(第一部分

对偶问题的约束条件 对应于原问题的目标 函数和约束条件的系 数。
对偶问题的可行解集 是原问题可行解集的 凸包。
原问题与对偶问题关系
弱对偶性
对于任意一对原问题和对偶问题 的可行解，原问题的目标函数值 总是大于或等于对偶问题的目标
函数值。
强对偶性
当原问题和对偶问题都存在可行 解时，它们的最优解对应的目标
强对偶性定理
若原问题和对偶问题都有可行解，则 它们分别存在最优解，且这两个最优 解的目标函数值相等。
在满足某些约束规格（如Slater条件） 的情况下，强对偶性成立。
互补松弛条件
在原问题和对偶问题的最优解中，如果某个约束条件的对偶变量值为正，则该约束 条件必须是紧的（即取等号）。
如果原问题（对偶问题）的某个变量在最优解中取正值，则其对应的对偶问题（原 问题）的约束条件必须是紧的。
标准形式
通常将线性规划问题转化为标准 形式，即求解目标函数的最小值 ，约束条件为一系列线性不等式 。
对偶问题定义与性质
对偶问题定义：对于 给定的线性规划问题， 可以构造一个与之对 应的对偶问题，该问 题的目标函数和约束 条件与原问题密切相 关。
对偶问题性质
对偶问题的目标函数 是原问题约束条件的 线性组合。
解决对偶间隙等关键问题
在实际应用中，由于原问题和对偶问题之间可能存在对偶间隙，导致对偶理论的实用性受到一定的限制。 未来可以研究如何缩小或消除对偶间隙，提高对偶理论的实用性和应用范围。
THANKS
感谢您的观看
简化了复杂问题的求解过程
对偶理论能够将一些复杂的线性规划问题转化为相对简单的对偶问题进行求解，从而降低了问题 的求解难度和计算量。
揭示了原问题和对偶问题之间的内在联系

第二章线性规划的对偶理论

第二章线性规划的对偶理论

2.1 写出线性规划问题的对偶问题，并进一步写出其对偶问题的对偶问题(a) min z=2x1+2x2+4x3(b) max z=5x1+6x2+3x3s.t. x1+3x2+4x3≥2 s.t. x1+2x2+2x3=52x1+x2+3x3≤3 -x1+5x2-3x3≥3x1+4x2+3x3=5 4x1+7x2+3x3≤8x1, x2≥0, x3无约束x1无约束,x2≥0, x3≤0解：(a)对偶问题的原问题为max w=2y1+3y2+5y3s.t. y1+2y2+y3≤23y1+y2+4y3≤24y1+3y2+3y3=4y1≥0, y2≤0, y3无约束(b)原问题的对偶问题为min w=5y1+3y2+8y3s.t. y1-y2+4y3=52y1+5y2+7y3≥62y1-3y2+3y3≤3y1无约束, y2≤0, y3≥02.3 已知线性规划问题：max z=x1+x2s.t. -x1+ x2+ x3 ≤2-2x1+x2- x3 ≤1x1, x2, x3≥0试应用对偶理论证明上述线性规划问题最优解为无界。

解：原问题的对偶问题为min w=2y1+ y2s.t. -y1- 2y2 ≥12y1+ 5y2 ≥1y1- y2 ≥0y1, y2≥0由于约束条件3可得y1-y2 ≥0 →y1≥y2 →-y1≤-y2 且y2≥0所以-y1-2y2 ≤-3y2≤0 （1）由于约束条件1可得-y1- 2y2 ≥1 （2）（1）（2）不等式组无解所以其对偶问题无可行解,又知点X=(1,1,1)为原问题一个可行解,即原问题有可行解, 现在其对偶问题无可行解。

根据对偶理论性质3原问题无界.2.4 已知线性规划问题：max z=2x 1+4x 2+ x 3+x 4 s.t. x 1+ 3x 2 +x 4 ≤8 2x 1+ x 2 ≤6 x 2+ x 3 +x 4 ≤6 x 1+ x 2+ x 3 ≤9 x j ≥0 (j=1,…4)要求(a)写出其对偶问题;(b)已知原问题最优解X=(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优解. 解:对偶问题: min w=8y 1+ 6y 2+6y 3+9 y 4 s.t. y 1+ 2y 2 +y 4 ≥2 3y 1+ y 2 + y 3 +y 4 ≥4 y 3+ y 4 ≥1 y 1 +y 3 ≥1 y 1, y 2,y 3, y 4≥0将最优解X=(2,2,4,0)代入原问题的约束条件得: x 1+ 3x 2 +x 4 =8 2x 1+ x 2 =6 x 2+ x 3 +x 4 =6 x 1+ x 2+ x 3 =8<9根据对偶理论性质5， 如果∑=<ni i j ij b xa 1ˆ，则0ˆ=i y 。

2.454线性规划的对偶理论

2.454线性规划的对偶理论

故y=CBB-1 是对偶问题的最优解
由对偶定理可得：
（1）对偶问题最优解的表达式：
Y* =CB B-1 (2) 对于Y* 没必要重新求解，可从原问题的
最终单纯形表中获得。
即：对偶问题的最优解(即实变量的值)是原 问题虚变量（即松弛变量）检验数的负值.
任何一个LP问题总是属于下列三种情况之一
⑴有最优解； ⑵问题无界； ⑶无可行解. 一个原问题和它的对偶问题有四种可能的组合
(5) 主对偶定理(可行解是最优解的性质）
互为对偶的线性规划问题中，若一个有最优解, 则另一个也有最优解,且目标函数值相等.
推论：若原问题和对偶问题两者皆可行,则
两者均有最优解,且此时目标函数值相等.
由于原问题和对偶问题均可行,根据弱对偶性, 可知两者均有界,于是均有最优解.
证：设原问题有最优解， 当XB=B-1b是原问题的最优解时，有
解： 对偶问题是
因为x1≠0, x2≠0, 所以对偶问题的第一，第
二约束的松弛变量为0
即y1 + 2y2 = 3 2y1 +2y2 =4
得解y1 =1 , y2=1 从而对偶的最优解为
Y=(1 ,1), 最优值为 w=26
利偶m用问ax上题述（Z 关或 系原3x，问1 建题4立）x2对的 x3 约程2x束组x1 线的12性解2x方即x2 2程为x组最x3 3，优1则解016方， 即解x得可j 到由 0另一, 一个j 个问1,问题2,题的3 的最最优
2x1 2x2 x3
12 y1
4x1
5x2
x4
16 y2
x5 15 y3
xj 0(j 1,,5)
s.t.
22yy11
4y
2

线性规划对偶理论

线性规划对偶理论

线性规划对偶理论前言线性规划（linear programming, LP）是一种求解线性模型的算法，该算法可以在目标函数下寻找最佳的解决方案。

通常情况下，线性规划可以被看作是一种最优化问题，其目的是在满足一组约束条件的前提下，找到可以最大化或最小化目标函数的变量值。

而对偶理论是线性规划问题中的重要概念之一，在很多情况下，使用对偶理论能够有效地求解出更优的解答。

线性规划与对偶理论在介绍线性规划对偶理论之前，我们先来简单了解一下线性规划的概念。

线性规划可以被定义为一组决策变量的线性函数，该函数的取值范围应在满足一组线性方程（或不等式）约束条件的前提下，使得目标函数达到最小（或最大）值。

换句话说，线性规划要求我们在可接受的条件下，寻找到最优的决策变量值。

围绕这种思想，我们可以进一步探讨线性规划的对偶问题。

在实践中，我们常常会面对一些较复杂的线性规划问题，此时我们可以使用对偶理论对其进行简化处理。

形式化地说，对于一个线性规划问题，我们可以构建一个对应的对偶问题，二者之间的关系可以被描述为一种对称的互补关系。

具体而言，在每个线性规划问题中，我们可以根据不同的约束条件求出一个对应的乘法因子，这个乘法因子可以在构建对偶问题时被使用。

通过这种方式，我们总是可以在对偶问题中找到一组最优解，而这组最优解实际上是原始问题的一个下界。

同时，我们可以利用对偶问题的最优解来求解原始问题的最优解，这种方法被称为对偶算法。

相比于原始的线性规划问题，对偶问题有着更为简洁的约束条件和更为易于求解的优化问题，因此其求解效率较高。

对偶问题的分析与求解在实际求解中，我们通常需要对给定的线性规划问题进行对偶化处理，并使用一系列的对偶算法来求解对偶问题。

下面，我们将会举两个例子来说明对偶问题的分析与求解。

例1：最小费用最大流问题最小费用最大流问题是一种最优化问题，其目的是在给定图中求出最大流量下的最小费用。

在具体求解中，我们可以通过建立一个对应的线性规划问题，并将其对偶化得到一个更加简洁的对偶问题。

3对偶理论


4
0
0 4
8
C (2, 3)
b
16
12
X
(x1, x2 )T
x1 x2
max Z 2x1 3x2
x1 2x2 8
4
x1
16 4x2 12
x1, x2 0
max
z
(2, 3)
x1 x2
CX
1 2
8
4 0
0 4
x1 x2
16 12
总利润（元）
单位产品旳利润（元/件）
产品产量（件）
max z c1x1 c2x2
c2 x2
s.t.
a11x1 a12x2
a1n xn xn1
b1
a21x1 a22 x2
a2n xn
xn2
b2
am1x1 am2 x2
消耗旳资源（吨） x1
x2
单位产品消耗旳资源（吨/件）
amn xn xn xn1 xn2
2x1 3x2 7x3 4x4 2
x1 0，x2 0, x3、x4无约束
答案： 1. maxW 2 y1 3 y2 5 y3
2y1 3y 2 y 3 2
3y
5y
1 1
y 2 4y 3 7y 2 6y 3
2 4
y1 0, y 2 .y 3 0
2. maxW 3 y1 5 y2 2 y3
对偶问题
min W 5 y1 4 y2 6 y3
4 y1 3 y2 2 y3 2
y1 3 y1
2 y2
3 y3 3 4 y3 5
2 y1 7 y2 y3 1
y1 0, y2 0, y3无约束
例4、线性规划问题如下：

第2章线性规划的对偶理论


max z 5x1 6x2 3x3
x1 2x2 2x3 5
(1)
s.t
.
4xx1 175xx223xx33

3 8
x2 0, x3 0
n
max z c j x j j1


n
aij x j
bi
(i 1,, m1 m)
-15 y3 1/5 0 -4/5 1
zj - cj
0 4 0
原问题松 弛变量
00
y4 y5 -1/2 0
1/5 -1/5
3 3
原问题 变量
第19页
说明：1)只需求解其中一个问题, 从最优解的单纯形表中同时得
到另一个问题的最优解.
2)单纯形法迭代的每一步中, 原问题及对偶问题解的关系
目标函数值
n)
m
min w bi yi i 1
yi 0 (i 1,, m1 )
yi无约束(i m1 1,, m)
m
aij yi c j ( j 1,, n1 )
i 1 m
aij yi c j ( j n1 1,, n)
i 1
第10页
写出下列线性规划的对偶问题

m i 1
aij
yi

c
j
(
j

1,, n)
yi 0 (i 1,, m)
min w bY
AY C
s.t.
Y 0
第4页
2-2 原问题与对偶问题
对应关系： (1) max
min
= (2)
约束条 件个数
变量的 个数

线性规划对偶理论(含影子价格)_21136


对 偶
a11 a12
s.t.
a21
a22
a1n x1 b1
a2n
x2
b2
对 称
问
am1 am2
amn
xn
bm
形
题
x1, x2 , , xn 0
的
min Z c1x1 c2 x2 cn xn
定 义
a11 a21
s.t.
a12
a22
a1n a2n
x2 0,
x2
2
0
无界
关于无界性有如下结论： minW 4 y1 2 y2
原问题
问题无界
无可 行解
对偶问题 无可行解 无可行解
问题无界
y1 y2 2
（对）
y1
y1
y2 0, y2
1 0
无可 行解
原 : max Z x1 2x2
x1 x2 x3 2
2x1 x2 x3 1
m
m
A
≥b
n
对偶问题的特点
〔1〕目标函数在一个问题中是求最大值在 另一问题中则为求最小值
〔2〕一个问题中目标函数的系数是另一个 问题中约束条件的右端项
〔3〕一个问题中的约束条件个数等于另一 个问题中的变量数
〔4〕原问题的约束系数矩阵与对偶问题的 约束系数矩阵互为转置矩阵
一般
线性规 划问题 的对偶 问题
〔4〕强对偶性〔最优解的目标函数之间的关系〕 如果原问题有最优解，则其对偶问题也一定有 最优解，且两者的目标函数值相等
3、互补松弛性
在线性规划问题的最优解中， 如果对应某一约束条件的对偶变量值为非零，
则该约束条件取严格等式；
反之如果约束条件取严格不等式，

运筹学课件第二章线性规划的对偶理论及其应用

对偶问题同时解
– 原问题为基础可行解，对偶问题为非可行解，但满足
互补松弛条件；则当对偶问题为可行解时，取得最优 解
13
2.2.5 原问题检验数与对偶问题的解
• 在主对偶定理的证明中我们有：对偶(min型)变量的最 优解等于原问题松弛变量的机会成本，或者说原问题松 弛变量检验数的绝对值
• 容易证明，对偶问题最优解的剩余变量解值等于原问题 对应变量的检验数的绝对值
1
1/2 5/2
1
1
0
1/2 3/2
0
0
0
1/2 3/2
OBJ=
39
9/2
3
6
6
0
3/2
3/2
cj - zj
1/2
0
0
0
0
3/2 -M-3/2
0
x4
4
0
0
1
1
1
1
3
5
x1
6
1
0
2
2
0
1
1
3
x2
4
0
1
1
(1)
0
1
2
OBJ=
42
5
3
7
7
0
2
1
cj - zj
0
0
1
1
0
2 -M+1
0
x4
ቤተ መጻሕፍቲ ባይዱ
8
0
1
0
0
1
0
1
5
x1
数值，
g(Y0)=Y0b= CBB1 b
而原问题最优解的目标函数值为
f(X0)=CX0= CBB1 b 故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0
IE5001
4
LP Duality: Dakota Example
• The first dual constraint is associated with desks, the second dual constraint with tables, and the third dual constraint with chairs
Primal Problem (or Dual Problem) Maximize z Constraint i form = form ≥ form Variable xj xj ≥ 0 xj unrestricted in sign xj 0
Dual Problem (or Primal Problem)
• Thus, the solution to the Dakota dual will yield optimal
prices for lumber, finishing hours, and carpentry hours
IE5001
7Байду номын сангаас
LP Duality: Shadow Prices
• In summary, when the primal is a normal maximization problem, the dual variables are related to the value of resources available to the decision maker
• Then
• The dual LP is a minimization problem
• A dual variable is defined for each of the m primal constraints and is required to be nonnegative
• A dual constraint is defined for each of the n primal variables and is of “≥” type
Primal Variables
Right-hand
Variables
x1
…
xj
…
xn
y1
a11
…
a1j
…
a1n
y2
a21
…
a2j
…
a2n
…
……………
Side
b1 b2 …
…
……………
…
ym
am1
…
amj
…
amn
bm
c1
…
cj
…
cn
1st Dual
jth Dual
nth Dual
Dual
Constraint
2x1 + 1.5x2 + 0.5x3 ≤ 8
x2
≤5
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
• The dual problem is
(lumber constraint) (finishing constraint) (carpentry constraint) (table demand constraint)
• The decision variable y1 is associated with lumber, y2 with finishing hours, y3 with carpentry hours and y4 with table demands
• Suppose an entrepreneur wants to purchase all of Dakota’s resources. The entrepreneur must determine the price he or she is willing to pay for a unit of each of Dakota’s resources
desk that could be sold for $60. Since the entrepreneur is
offering 8y1 + 4y2 + 2y3 for the resources used to produce a desk, he or she must chose the y variables to satisfy:
• For this pair of LPs, the original LP is called the primal problem, while the other LP is called the dual problem
• Knowledge of the dual problem also provides interesting economic insights
min w = 48y1 + 20y2 + 8y3 + 5y4
s.t.
8y1 + 4y2 + 2y3 ≥ 60 (desk constraint)
6y1 + 2y2 + 1.5y3 + y4 ≥ 30 (table constraint)
y1 + 1.5y2 + 0.5y3 ≥ 20 (chair constraint)
• Objective coefficients of the dual LP are given by RHS of primal constraints
IE5001
10
LP Duality
Let x = (x1, x2,…, xn)T, y = (y1, y2,…, ym)T, c = (c1, c2,…, cn)T, b = (b1, b2,…, bm)T ,
• In setting the resource prices, the prices must be high enough to induce Dakota to sell. They must be nonnegative
IE5001
6
LP Duality: Dakota Example
• The entrepreneur must offer Dakota at least $60 for a
a11 a12 ... a1n
A


a21
a22
...
a2n


am1
am2
...
amn

Primal LP :
Dual LP :
Max z cT x
Min w bT y
s.t. Ax b
s.t. yT A cT
IE5001
x0
y0 11
LP Duality
8y1 + 4y2 + 2y3 ≥ 60
• Similar reasoning shows that at least $30 must be paid
for the resources used to produce a table. Thus the y
variables must satisfy: 6y1 + 2y2 + 1.5y3 + y4 ≥ 30
combination of resources that includes 8 board feet of
lumber, 4 finishing hours, and 2 carpentry hours because
Dakota could, if it wished, use the resources to produce a
min
w b1 y1 b2 y2 ... bm ym
s.t.
a11 y1 a21 y2 ... am1 ym c1
a12 y1 a22 y2 ... am2 ym c2
a1n y1 a2n y2 ... amn ym cn
IE5001
Minimize w
Variable yi
↔
yi ≥ 0
↔
yi unrestricted in sign
↔
yi 0
Constraint j
↔
≥ form
↔
= form
↔
form
IE5001
12
LP Duality: Example
• Consider the following LP
Linear Programming Duality
LP Duality
• For each LP, we can define another LP directly or systematically such that for this pair of LPs, the optimal solution of one LP automatically yields the optimal solution of the other LP
• For this reason, dual variables are often referred to as resource shadow prices
IE5001
8
LP Duality
For every primal LP, we have an associated dual LP
Dual
Constraint
Constraint Objective
IE5001
9
LP Duality
• Assume that the primal LP is a maximization problem with all the constraints being of “” type and all decision variables are assumed to be nonnegative