对偶线性规划

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 写出下列线性规划的对偶问题

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

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

2.6 已知线性规划问题max z＝10x1＋5x2st. 3x1＋4x2≤95x1＋2x2≤8x j≥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 试从经济上解释对偶问题及对偶变量的含义。

min w 16y1 36y2 65y3
90 y1 3 y 2 y1 2 y 2 5 y 3 70 y , y , y 0 1 2 3
原问题 A b C 约束系数矩阵
对偶问题 约束系数矩阵的转臵
约束条件的右端项向量 目标函数中的价格系数向量 目标函数中的价格系数向量 约束条件的右端项向量 Max z=CX Min w=Y’b 目标函数 AX≤b A’Y≥C’ 约束条件 X≥0 Y≥0 决策变量
若原问题为求极小形式的对称形式线性规划问题， 对偶问题应该具有什么形式？
Min w Y 'b A'Y C Y 0
max w Y 'b A'Y C Y 0
min z CX
Max z CX
AX b X 0
AX b X 0
min w 5 y1 4 y2 6 y3 4 y1 3 y2 2 y3 2 y1 2 y2 3 y3 3 3 y1 4 y3 5 2 y 7 y y 1 2 3 1 y1 0, y2 0, y3无约束
对偶问题 约束系数矩阵的转臵
目标函数中的价格系数向量
目标函数 约束条件
变量
Max z=CX m个 ≤ ≥ = n个 ≥0 ≤0 无约束
约束条件的右端项向量 目标函数 Min w=Y’b m个 ≥0 变量 ≤0 无约束 n个 ≥ 约束条件 ≤ =
【例2-3】写出下列线性规划问题的对偶问题
min 2x1 3x2 5x3 x4
1.初始表中单位阵在迭代后单纯形表中对应的位臵就是B-1 2.对于原问题的最优解，各松弛变量检验数的相反数恰好 是其对偶问题的一个可行解，且两者具有相同的目标函数 值。根据下面介绍的对偶问题的基本性质还将看到，若原 问题取得最优解，则对偶问题的解也为最优解。

根据对偶性质；可将原问题与对偶问题解的对应关系列表如下： 表3－6 一个问题max 有最优解 无 最 优 解 无最优解 无界解 (有可行解) 无可行解 另一个问题min 有最优解 无最优解 无可行解 无界解 (有可行解) 性质4 性质4 性质2
应用
已知最优解 已知检验数
通过解方程
检验数乘以
求最优解 求得基本解
max w 2 y1 2 y 2 y1 y 2 1 1 y1 y 2 2 2 y1 , y 2 0
【性质2】 弱对偶性: 设X*、Y*分别为LP(mix)与 DP(max)的可行解，则
CX Y b
* *
【性质3】最优准则定理: 设X*与Y*分别是(LP)与(DP) 的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当 C X*= Y*b . 【性质4】对偶性：若互为对偶的两个问题其中一个有 最优解，则另一个也有最优解，且最优值相同。 另一结论：若(LP)与(DP)都有可行解，则两者都有最优 解，若一个问题无最优解，则另一问题也无最优解。 【性质5】互补松弛定理: 设X*、Y*分别为 (LP) 与 (DP) 的可行解，XS和YS分别是它们的松弛变量的可行解，则 X*和Y*是最优解当且仅当
YSX*=0 和 Y*XS=0
i 1
可写成下式
y x 0
i 1 n * i Si
m
y
j 1
n
Sj
x 0
* j
即
* S j* (2) yS j 0时x j j j 1
y
x 0, 反之当x* 0时y 0 0 j S
j
已知一个问题的最优解时求另一个问题的最优解的方法
max z 3 x1 4 x 2 x3 x1 2 x 2 x3 10 【例3.5】 已知线性规划 2 x 2 x x 16 1 2 3 x 0, j 1,2,3 j