当前位置：文档之家 › 第2章线性规划的对偶问题

第2章线性规划的对偶问题

  • 格式：ppt
  • 大小：965.51 KB
  • 文档页数：49

下载文档原格式

  / 49

合集下载

《运筹学》胡运权 第4版 第二章 线性规划的对偶理论及灵敏度分析

《运筹学》胡运权 第4版 第二章 线性规划的对偶理论及灵敏度分析

b2 bm
x1, x2 , , xn 0
对 称 形 式 的
的 定 义
m W ib 1 n y 1 b 2 y 2 b m y m 对
s.t.
a11 a12 a1n
a21 a22 a2n
am1 y1 c1
am2 y2 amn ym
c2 cn
偶 问 题
y1, y2 , , ym 0
a23 x3 a33 x3
b2 b3
x1 0， x2 0， x3无 约 束
（2.4a） （2.4b） （2.4c） （2.4d）
先转换成对称形式，如下：
的 的一个变量，其每个变量对应于对偶问题 的一个约束。
定
义
m Z a c 1 x 1 x c 2 x 2 c n x n 一
对 偶
a11x1 a12x2 a1n xn (,)b1
a2
1x1
a22x2
a2n xn
(, )b2
般 线 性
问 题 的 定 义
am1x1 am2 x2 amnxn (,)bm xj 0( 0,或符号不限) j 1 ~ n
问题。
对
对偶问题是对原问题从另一角度进
偶
行的描述，其最优解与原问题的最 优解有着密切的联系，在求得一个
原
线性规划最优解的同时也就得到对 偶线性规划的最优解，反之亦然。
理
对偶理论就是研究线性规划及其对 偶问题的理论，是线性规划理论的
重要内容之一。
问 题 的 导 出
例2-1
我们引用第一章中美佳公司的例子，如表1
的
x1, x2, , xn 0
对
m W ib 1 n y 1 b 2 y 2 b m y m

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

第二章 线性规划的对偶理论
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型)变量的最 优解等于原问题松弛变量的机会成本，或者说原问题松 弛变量检验数的绝对值 •容易证明，对偶问题最优解的剩余变量解值等于原问 题对应变量的检验数的绝对值 •由于原问题和对偶问题是相互对偶的，因此对偶问题 的检验数与原问题的解也有类似上述关系。 •更一般地讲，不管原问题是否标准，在最优解的单纯 型表中，都有原问题虚变量(松弛或剩余) 的检验数对应 其对偶问题实变量 (对偶变量)的最优解，原问题实变量 (决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩 余变量)的最优解。因此，原问题或对偶问题只需求解 其中之一就可以了。

线性规划的对偶问题

线性规划的对偶问题
第9页
(二)非对称型对偶问题
max z c1x1 c2x2 c3x3 c3x3 s.t. a11x1 a12 x2 a13x3 a13x3 b1
a21x1 a22 x2 a23x3 a23x3 b2 a2a1x21x1 a2a2 x222x2 a2a3x233x3 a2a3x233x3 b2b2 a31x1 a32x2 a33x3 a33x3 b3
min w b1y1 b2 y2 b3 y3 s.t. a11 y1 a21 y2 a31 y3 c1
a12 y1 a22 y2 a32 y3 c2
a13 y1 a23 y2 a33 y3 c3 y1 0，y2无约束，y3 0
第11页
(二)非对称型对偶问题
对偶问题（原问题）
目标函数 min
约束条件右端常数
目标函数的系数
3个
≥0
变
≤0
量
无符号限制
23个
约
≥
束
≤
条 件
=
第13页
二、原问题与对偶问题的对应关系
原问题（对偶问题）
目标函数 max
目标函数的系数
约束条件右端常数
约 m个
束≤
条 件
≥
=
n个
变
≥0
量
≤0
无符号限制
对偶问题（原问题）
目标函数 min
约束条件右端常数
第8页
(二)非对称型对偶问题
max z = c1x1 + c2x2 + c3x3 s.t. a11x1 + a12x2 + a13x3 ≤ b1
a21x1 + a22x2 + a23x3 = b2 a31x1 + a32x2 + a33x3 ≥ b3 x1≥0, x2≤0, x3无约束 分析：化为对称形式。令 x2 x2，x3 x3 x3 (x3 0, x3 0)

线性规划的对偶问题,DOC

线性规划的对偶问题,DOC

第二章线性规划的对偶问题习题2.1写出下列线性规划问题的对偶问题(1)maxz＝10x1＋x2＋2x3(2)maxz＝2x1＋x2＋3x3＋x4st.x1＋x2＋2x3≤10st.x1＋x2＋x3＋x4≤54x1＋x2＋x3≤202x1－x2＋3x3＝－4x j ≥0（j＝1,2,3）x1－x3＋x4≥1xj≥0（j＝1,2,3,4）其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。

2.5考虑线性规划问题maxz＝2x1＋4x2＋3x3st.3x1＋4x2＋2x3≤602x1＋x2＋2x3≤40x 1＋3x2＋2x3≤80xj≥0（j＝1,2,3）（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；仅供个人学习参考（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。

2.6已知线性规划问题maxz＝10x1＋5x2st.3x1＋4x2≤95x1＋2x2≤8xj≥0（j＝1,2）（1）给出a，b，c，d，e，f，g的值或表达式；（2）指出原问题是求目标函数的最大值还是最小值；（3）用a+?a，b+?b分别代替a和b，仍然保持上表是最优单纯形表，求?a，?b满足的范围。

仅供个人学习参考仅供个人学习参考2.9某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。

该厂现有工人100人，每月白坯纸供应量为30000千克。

已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本30打，或练习本30箱。

已知原材料消耗为：每捆原稿纸用白坯纸310千克，每打日记本用白坯纸340千克，每箱练习本用白坯纸380千克。

又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生产一箱练习本获利1元。

试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？2.10某厂生产甲、乙两种产品，需要A 、B 两种原料，生产消耗等参数如下表（表中2.12试从经济上解释对偶问题及对偶变量的含义。

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

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

目
标函数求极小时取“≥”号
注：对称形式与线性规划标准型是两种不同的形 式，对称形式中约束条件的符号由目标函数决定
从以下方面比较(LP1)与(LP2)：
原问题
对偶问题 约束系数矩阵的转 臵 目标函数中的价格 系数向量 约束条件的右端项 向量 Min w=Y’b A’Y≥C’ Y≥0
A
b C 目标函数 约束条件 决策变量
非基变量 基变量
XB
0 b Xs C j - zj B
XN
N
Xs
I
0
初始 单纯形表
非基变量
CB
CN
基变量
最终
单纯形表
CB
XB
XB B-1b Cj - zj
I 0
Xs B-1 N B-1 CN-CBB-1N -CBB-1
XN
若B-1b为最优解，则
CB CB ( B 1B) 0 C N CB B N 0 CB B 1 0
令 y 2 y 2 , y3 y3 y3 ，则
min 2 y1 y2 4 y3
2 y1 3 y2 y3 1 3 y y y 4 1 2 3 s.t. 5 y1 6 y2 y3 3 y1 0, y2 0, y3无约束
n j 1 m j j
C X Y b, 即 c j x j y i bi
j 1 i 1
__
__
n
m
c x ( a
j 1 m i 1 n i i i 1 i 1 j 1
n
m
ij
yi ) x j aij x j yi ( a ji yi c j )
例1

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

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

(5.5) (5.6)
4.3 对偶问题的基本性质
证： 设B是一可行基，于是A=(B,N)
max z=CBXB+ CNXN BXB+BXN +Xξ=b X,XB,Xξ ≥0
其中Yξ=(Yξ1, Yξ2)
min ω =Yb YB－Yξ1=CB YN－Yξ2=CN Y, Yξ1 Yξ2 ≥0
(5.5) (5.6)
x1﹐x2 ≥0
关系？
对原模型设： 1 2
A= 4 0 b=(8,16,12)T C=(2，3) 04
X=（x1，x2）T Y=（y1，y2 ，y3 ） 则可得:
4.1 对偶问题的提出
min ω=8 y1+16y2 +12y3
y1+4y2
≥2
2 y1 +4y3≥3
与
y1 ， y2 ，y3≥0 12
max z＝2x1+3x2 x1＋ 2x2 ≤8
4x1
≤16
4x2 ≤12
x1﹐x2 ≥0
有何关 系？
对愿模型设： A= 4 0 04
b=(8,16,12)T C=(2，3)
X=（x1，x2）T
Y=（y1，y2 ，y3 ） 则可得:
max z=CX AX≤b （5.1） 和
min ω =Yb YA ≥ C （5.2）
120
A=
1 -3
0 2
1 1
1 -1 1
b=(2,3,-5,1)T C=(5,4, 6)
确定约束条件
YA
C
x1 ≥0 ﹐x2≤0, x3 无约束
解：因原问题有3个变 于是 量，4个约束条件， 所以对偶问题4个 变量，3个约束条

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

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


≤9
y1≤0， y2≥0， y3无约束
2.1 线性规划的对偶模型 Dual model of LP
1.本节以实例引出对偶问题; 2.介绍了如何写规范与非规范问题的对偶问题;
作业：教材P61 T 1、2 下一节：对偶性质
2.2 对偶性质
Dual property
2.2 对偶性质 Dual property
时得到最优解，C CB B 1 A 是 X＝（X B，X N）的检验数 CB CB B 1B 和
CN CB B1N 的合并。
令 Y CB B1 ,由 C CB B 1 A 0与 CB B 1 0 得
YA C Y 0
可见，这是Y是对偶问题的一个可行解。 思考：Y右边的部分是什么？
C X°≤Y°AX≤Y°b
这一性质说明了两个线性规划互为对偶时，求最大值的 线性规划的任意目标值都不会大于求最小值的线性规划 的任一目标值，不能理解为原问题的目标值不超过对偶 问题的目标值。
2.2 对偶性质 Dual property
由这个性质可得到下面几个结论：
（1）（LP）的任一可行解的目标值是（DP）的最优值下界； （DP）的任一可行解的 目标是（LP）的最优值的上界；
【例2.3】 写出下列线性规划的对偶问题
max Z 4x1 3x2
5x1 x2 6 7x1x135x2x2108 x1 0, x2 0
【解】这是一个规范形式的线性规划，它的对偶问题求 最小值，有三个变量且非负，有两个“ ≥”约束，即
min w 6 y1 8 y2 10 y3
5yy1172yy22
y3 3y3
4
3
yi 0,i 1,2,3
2.1 线性规划的对偶模型 Dual model of LP

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

在某些情况下，求解对偶问题可能比直接求解原问题更简单。通过对偶转化，可以将复杂的问题 转化为相对简单的问题进行求解。
灵敏度分析（Sensitivity Analysis）
对偶问题的解可以用于分析原问题参数变化对最优解的影响。通过对偶问题的灵敏度分析，可以 了解原问题解的稳定性以及参数调整对最优解的影响程度。
Part
05
目标规划与多目标决策
目标规划基本概念
目标函数
在目标规划中，目标函数表示决策者希望优化的目标，可以是最 大化或最小化某个或多个变量的函数。
约束条件
约束条件限制了决策变量的取值范围，确保解在实际可行域内。
优先级与权重
不同目标之间可能存在冲突，通过设定优先级和权重可以权衡各 个目标的重要性。
分支定界法的步骤
分支定界法主要包括分支、定界和剪枝三个步骤。首先，将原问题分解为若干个子问题；其次，对每个子问题分别求 解，并更新上下界；最后，通过剪枝策略删除不可能得到最优解的子问题，以减少计算量。
分支定界法的优缺点
分支定界法具有适用范围广、可求得全局最优解等优点；但同时也存在计算量大、求解效率不高等缺点。 因此，在实际应用中需要根据问题的特点和要求选择合适的算法。
多目标决策方法
线性加权法
将多个目标函数线性加权为一个综合目标函数，通过求解该综合目 标函数的最优解来实现多目标决策。
理想点法
先确定每个目标的理想值，然后构造一个评价函数来衡量实际解与 理想解之间的差距，通过最小化该评价函数来求解多目标决策问题。
分层序列法
将多个目标按照重要程度排序，依次求解各层目标的最优解，最终得 到综合考虑所有目标的满意解。
要点三
混合整数规划的应用 案例
混合整数规划在实际应用中有着广泛 的应用，如生产调度中的任务分配问 题、物流运输中的路径优化问题等。 通过运用混合整数规划方法，可以有 效地解决这些问题，提高生产效率和 运输效率。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

0 x6 1 -2 1 -1 -1 0 1 0
0 x7 9 0 3 1 0 0 0 1
j
-3 0 1 0 0 0 0
……
0 x5 0 0 0 0 -1/2 1 1/2 -1/2
0 x2 3 0 1 1/3 0 0 0 1/3
-3 x1 1 1 0 2/3 1/2 0 -1/2 1/6
j
0 0 3 0 0 -3/2 1/2
…………………………
a1n y1 a2n y2 amn ym cn
y1, y2 , , ym 0
3
二、对称形式下对偶问题的一般形式
LP1：s.t.
n
Max Z c j x j
j 1 n
aij x j bi
i 1,2, , m
j 1
xj 0
j 1,2, , n
m
Min W bi yi i 1
j 1,2, , n
yi 0
i 1,2, , m
12
对称形式的线性规划问题：
max z 3x1 x3
x1 x2 x3 4
st.3x22x1
x2 x3
9
x3
x4
1
x1~3 0
13
-3 0 1 0 0 0 0
CB 基 b x1 x2 x3 x4 x5 x6 x7
0 x5 4 1 1 1 0 1 0 0
例：
二、对称形式下对偶问题的一般形式
线性规划问题具有对称形式，若：
➢ 变量非负
➢ 目标函数求极大值时，约束方程均为≤
目标函数求极小值时，约束方程均为≥
2
二、对称形式下对偶问题的一般形式
对称形式的LP问题(LP1)：
Max Z c1x1 c2 x2 cn xn a11x1 a12 x2 a1n xn b1 a21 x1 a22 x2 a2n xn b2
X 0 Xs 0
16
一、单纯形算法的矩阵描述
LP2的初始单纯形表及经过若干步迭代后某一步的
单纯形表如下：
表1
B为某步单 纯形表中基 变量在初始 单纯形中对 应的矩阵
N由A中去 掉B后剩下 的列向量 组成
项目
非基变量
XB
XN
基变量
XS
0 XS b B
N
I
cj-zj
CB
CN
0
表2
项目
基变量
XB
CB XB B-1b
10
2.2 对偶问题的基本性质
本节讨论的问题假定原问题及对偶问题为对称形式
LP1：s.t.
n
Max Z c j x j
j 1 n
aij x j bi
i 1,2, , m
j 1
xj 0
j 1,2, , n
m
Min W bi yi i 1
m
LP2：s.t.
aij yi c j
i 1
n
则两侧同乘以“-1”， aij x j bi j 1
8
三、非对称形式的原--对偶问题的关系
P50 例题 2. 线性规划原问题同对偶问题的对应关系如下：
原问题
对偶问题
目标函数 Max
目标函数 Min
约
m个
m个
决
束
0
策
条
0
变
件
=
无约束
量
决
n个
n个
约
策
0
束
变
0
条
量
无约束
=
件
资源向量 b
价值系数 b‘
14
0 -3 0 1 0 0 0 0
CB 基 b x5 x2 x1 x3 x4 x5 x6 x7
0 x5 4 1 1 1 1 0 1 0 0
B 0 x6 1 0 1 -2 -1 -1 0 1 0
0 x7 9 0 3 0 1 0 0 0 1
j
0 0 -3 1 0 0 0 0
……
0 x5 0 1 0 0 0 -1/2 1 1/2 -1/2
价值系数 C
资源向量 C’
约束条件系数矩阵 A 约束条件系数矩阵 A ‘
9
三、非对称形式的原--对偶问题的关系 练习: 给出下述LP问题的对偶问题:
max z x1 2x2 3x3
x1 x2 x3 4
st.
x1 x1
2x2 2x2
3x3 3x3
5 6
x1 0, x2无约束, x3 0
0 x2 3 0 1 0 1/3 0 0 B0-1 1/3
-3 x1 1 0 0 1 2/3 1/2 0 -1/2 1/6
j
0 0 0 3 0 0 -3/2 1/2
15
一、单纯形算法的矩阵描述
Max Z CX
对称形式的LP： AX b
s.t.
X 0
加上松驰变量Xs后为(LP2)：
Max Z CX 0X s s.t. AX IX s b
s.t. ………………………… am1 x1 am2 x2 amn xn bm x1, x2 , , xn 0
注：对称形式的LP问 题,对b没有非负要求。
其对偶问题为(LP2) ：
s.t.
Min W b1 y1 b2 y2 bm y m a11 y1 a21 y2 am1 ym c1 a12 y1 a22 y2 am2 ym c2
I
cj-zj
0
非基变量
XN
XS
B-1N
B-1
CN-CB B-1N -CB B-1 17
一、单纯形算法的矩阵描述
x1~3 0
6
三、非对称形式的原--对偶问题的关系
1. 非对称转化为对称LP问题的步骤
➢ 目标函数及变量约束的转化同标准形:
n
aij x j bi
j 1
n
aij x j bi
j 1
n
aij x j bi j 1
n
➢ 约束方程若为” ≥”， aij x j bi j 1
资源向量
价格系数
价格系数
资源向量
max z=CX
min w=Y’b
AX≤b
A’Y ≥C’
X≥0
Y≥0
5
二、对称形式下对偶问题的一般形式
练习: 给出下述LP问题的对偶问题:
max z 2x1 4x2 3x3
3x1 4x2 2x3 60
st.2x1x1 3xx22
2 x3 2 x3
40 80
第二章 线性规划的对偶理论 与灵敏度分析
➢ 线性规划的对偶问题 ➢ 对偶问题的基本性质 ➢ 影子价格 ➢ 对偶单纯形法 ➢ 灵敏度分析 ➢ 参数线性规划
1
2.1 线性规划的对偶问题
一、对偶问题的提出
支持对偶理论的基本思想是：每一个线性规划问题都存 在一个与其对偶的问题。在求一个问题的解的同时，也 给出了另一个问题的解。
m
LP2：s.t.
aij yi c j
i 1
j 1,2, , n
yi 0
i 1,2, , m
Max Z CX AX b
s.t.
X 0
Min Y 'b A'Y C'
s.t.
Y 0
4
二、对称形式下对偶问题的一般形式
项目
A b C 目标函数 约束条件 决策变量
原问题
对偶问题
约束系数矩阵 约束系数矩阵的转置