线性规划的对偶理论与灵敏度分析习题
1
第二章 线性规划的对偶理论与灵敏度分析习题
1. 写出下列线性规划问题的对偶问题。
(1)
??????
?≥=++≤++≥++++=无约束
3213213213213
21,0,5343322
43422min x x x x x x x x x x x x x x x z (2)
??????
?≤≥≤++≥-+-=++++=0
,0,8374355
22365max 321321321321321x x x x x x x x x x x x x x x z 无约束
(3)
?????
??????==≥=====∑∑∑∑====),,1;,,1(0),,1(),,1(min 1
111
n j m i x n j b x m i a x x c z ij m
i j ij n
j i ij m i ij
n
j ij
2
(4)
?????
??????=≥++==<=<=∑∑∑===)
,,,,1(0),,2,1(),,1(min 1
211
111
n n j x m m m i b x a m m i b x a x c z j n
j i j ij n
j i j ij n
j j
j 无约束
2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行
解，则其对偶问题也一定存在可行解；
(2)如果线性规划的对偶问题无可行
解，则原问题也一定无可行解；
( 3)在互为对偶的一对原问题与对偶
问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；
(4)任何线性规划问题具有唯一的对
偶问题。
3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。
3 2 2 0 0 0
3
C B 基 B x 1 x 2 x 3 x 4 x 5 x 6
0 x 4 (b) 1
1 1 1 0 0
2 x 5 15 (a) 1 2 0 1 0 1 x 6 20
2 (c )
1 0 0
1
j
j z c -
0 2 0 0 0
0 x 4 5/4 0 0
(d ) (l ) -1/4 -1/4 3 x 1
25/4
1
0 (e ) 0 3/4 (i ) 2 x 2 5/2 0
1 (f ) 0 (h ) 1/
2 j
j z c -
-1
(k
) (g)
-5/4
(j)
4. 给出线性规划问题
???
??=≥-≤+-+-≥++++++=)4,,1(03
22
326532min 43214
3
2
1
4
321 j x x x x x x x x x x x x x z j
(1)写出其对偶问题；(2)用图解法求解对偶
4
问题；(3)利用(2)的结果及根据对偶问题性质写出原问题最优解。
5. 给出线性规划问题
??????
?≤≥≥++=+-≤-+++=无约束
3213213213213
21,0,0221222max x x x x x x x x x x x x x x x z
(1)写出其对偶问题；(2)利用对偶问题性质证明原问题目标函数值z ≤1。 6. 已知线性规划问题
???
??≥≤-+-≤++-+=0,,122max 3
213213212
1x x x x x x x x x x x z
试根据对偶问题性质证明上述线性规划问题目标函数值无界。
7. 给出线性规划问题
?????
??
??=≥≤++≤++≤+≤+++++=)
4,,1(09
6628342max 3
21432214214321 j x x x x x x x x x x x x x x x x z j
5
要求：（1）写出其对偶问题；（2）已知原问题最优解为X *
=(2,2,4,0)，试根据对偶理论，直接求出对偶问题的最优解。
8. 已知线性规划问题A 和B 如下： 问题A
问题B
()
?
??????????=≥≤≤≤=∑∑∑∑====n j x y b x a y b x a y b x a x c z j n
j j j n
j j j n
j j j n
j j
j ,,10max 3133212
21
1111 对偶变量
()
?
??????????=≥+≤+≤≤=∑∑∑∑====n j x y b b x a a y b x a y b x a x c z j n
j j j j n j j j n
j j j n
j j
j ,,10?3)3(?51
51?55max 311313212
2111
11
对偶变量
试分别写出i
y
?同)3,2,1(=i y i
间的关系式。 9. 用对偶单纯形法求解下列线性规划问题。
6
（1）
???
??=≥≥+≥+++=)3,2,1(05
223318124min 32213
21j x x x x x x x x z j
（2）
???
??=≥≥++≥++++=)3,2,1(010*********min 321421321j x x x x x x x x x x z j
10. 考虑如下线性规划问题：
???
???
?=≥≥++≥++≥++++=)3,2,1(03222434223804060min 321321321321j x x x x x x x x x x x x x z j
要求：(1)写出其对偶问题；(2)用对偶单纯形法求解原问题；(3)用单纯形法求解其对偶问题；(4)对比(2)与(3)中每步计算得到的结果。
11. 已知线性规划问题：
???
??=≥≤+-≤+++-=)3,2,1(0426
2max 22321321j x x x x x x x x x z j
先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。
7
(1)目标函数变为max z ＝2x 1+3x 2+x 3； (2)约束右端项由
???
? ??46变为
???
? ??43。
(3)增添一个新的约束条件-x 1+2x 3≥2。 12. 给出线性规划问题
????
??
???=≥≤++≤++++=)3,2,1(03
37343
1
131313132max 221321321j x x x x x x x x x x z j
用单纯形法求解得最终单纯形表见下表。
2 3 1 0 0 C B 基 B x 1 x 2 x 3 x 4 x 5 2 x 1
1
1 0 -1 4
-1
3
x 2 2 0 1 2
-1 1
j
j
z c -
-3 -5 -1
试分析下列各种条件下最优解(基)的变化： (1)目标函数中变量x 3的系数变为6； (2)分别确定目标函数中变量x l 和x 2的系数c 1、c 2在什么范围内变动时最优解不
8
变；
（3）约束条件右端项由
???
? ??31变为
???
? ??32； （4）增加一个新的变量7,11,66
6
=???
? ??=c P
x ；
(5)增添一个新的约束x 1+2x 2+x 3≤4。 13. 分析下列线性规划问题中，当且变化时最优解的变化，并画出z (λ)对λ的变化关系图。
()
()
()()()()()
???
?
???
??????
?=≥≤-≤+≤+=≥=++=++++--=+-+=2,10112610524,105322223max 22min 1212121421431214321j x x x x x x x j x x x x x x x x x z x x x x z j j λλλλλ
()
()()
()()()
???
?
???
??????
?=≥-≤++≤+-≤++=≥+-=+--=--++=+++=3,2,107304260234024,10122523max 42min 321313214324313214321j x x x x x x x x j x x x x x x x x x x z x x x x z j j λλλλλλλ
14. 某厂生产A ，B ，C 三种产品，其所需劳动力、材料等有关数据见下表。要求：(1)确定获利最大的产品生产计划；(2)产品
9
A 的利润在什么范围内变动时，上述最优计划不变；(3)如果设计一种新产品D ，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产?(4)如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。
A B C 可用量
劳动力 6 3 5 45 材料
3 4 5 30 产品利润（元/件）
3
1
4
15.已知线性规划问题
???
??=≥+=++++=++++++++=)5,...,1(0300)(max 225323222121214313212111543322111j x t b x x a x a x a t b x x a x a x a x x x c x c x t c z j
当0
21
==t t
时求得解最终单纯形表进见下表。
项目 1
x
2x 3x 4x 5
x 3
x 0 0.5 1 0.5 0
10
5/2
1
x 5/2 1 -0.5 0 -1/6 1/3
j
j z c -
0 -4
-4
-2
（1）确定23
2221131211
3
2
1
,,,,,,,,a a a a a a
c c c 和2
1
,b b 的值；
（2） 当0
2
=t 时，1
t 在什么范围内变化上述最
优解不变；
（3）当0
1
=t
时，2
t 在什么范围内变化上述最优
基不变；
16．某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂有工人100人，每天白坯纸的供应量为30000kg 。如单独生产各种产品时，每个工人每天可生产原稿纸30捆，或日记纸30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸3
13kg, 每打日记本用白坯纸3113
kg, 每箱练习本用白坯纸 3
226kg 。 已知
生产各种产品的赢利为：每捆原稿纸1元，每打日记本2元，每箱练习本3元。试决定：（1）在现有生产条件下使该厂赢利最大的方案；（2）如白坯纸供应量不变，而工人数量不足时可从市场上招收临时工，临时工费用为每人每天15元。问该厂应否招临时工及招收多少人为宜。
11
欢迎阅读 第二章线性规划的对偶问题 习题 2.1 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4 st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤5 4x1＋x2＋x3≤20 2x1－x2＋3x3＝－4 x j≥0 （j＝1,2,3）x1－x3＋x4≥1 x j≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3 st. 3x1＋4 x2＋2x3≤60 2x1＋x2＋2x3≤40 x1＋3x2＋2x3≤80 x j≥0 （j＝1,2,3） （1）写出其对偶问题 （2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解； 欢迎阅读
欢迎阅读 （3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解； （4）比较（2）和（3）计算结果。 2.6 已知线性规划问题max z＝10x1＋5x2 st. 3x1＋4x2≤9 5x1＋2x2≤8 x 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千克，每箱练习本用白坯纸3 80千克。又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生产一箱练习本获利1元。试确定： （1）现有生产条件下获利最大的方案； （2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？ 2.10 某厂生产甲、乙两种产品，需要A 、B 两种原料，生产消耗等参数如下表（表中 2.12 试从经济上解释对偶问题及对偶变量的含义。 2.13 根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间、解以及检验数之间的对应关系。 2.14 什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。 2.15 试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。 2.16 将a ij ，b ，c 的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题的解各自将会出现什么变化，有多少种不同情况以及如何去处理。 2.17 判断下列说法是否正确 (a)任何线性规划问题存在并具有唯一的对偶问题；
线性规划的对偶原理 3.1 线性规划的对偶问题 一、 对偶问题的提出 换位思考 家具厂的线性规划问题，该问题站在家具厂管理者的角度追求销售收入最大 213050max x x z += ?? ? ??≥≤+≤+0 ,50212034212121x x x x x x 某企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。他 需要与家具厂谈判付给该厂每个工时的价格。如果该企业家已对家具厂的经营情况有详细了 解，他可以构造一个数学模型来研究如何才能既让家具厂觉得有利可图，肯把资源出租给他， 又使自己付的租金最少。 目标:租金最少；1y -付给木工工时的租金；2y -付给油漆工工时的租金 2150120min y y w += 所付租金应不低于家具厂利用这些资源所能得到的利益 1）支付相当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收 入 502421≥+y y 2）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收 入 30321≥+y y 3）付给每种工时的租金应不小于零 0,021≥≥y y 二、 原问题与对偶问题的数学模型 1. 对称形式的对偶
原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称的，称为对称形式的对偶。 原问题： ?? ? ??≥≥=0min X b AX CX z 对偶问题： ?? ? ??≥≤=0max Y C YA Yb w 2. 非对称形式的对偶 若原问题的约束条件全部是等式约束（即线性规划的标准型），即 ?? ? ??≥==0min X b AX CX z 则其对偶问题的数学模型为 ?? ? ??≤=是自由变量Y C YA Yb w max 可把原问题写成其等价的对称形式： min z =CX AX ≥b AX ≤b X ≥0 即 min z =CX ? ? ????-A A X ≥??????-b b X ≥0 设Y 1=(y 1,y 2,…,y m ), Y 2=(y m+1,y m+2,…,y 2m )。根据对称形式的对偶模型，写出上述问题的对偶问题：
§2 对偶与灵敏度分析 §2.1 LP 的对偶问题 无论从理论和实践角度，对偶理论是LP 中的一个最重要和有趣的概念，支持对偶理论的基本思想是：每一个LP 问题都存在一个与其对偶的问题，在求解一个问题解的时候，也同时给出了另一问题的解。 一、问题的提出 例2.1：设某工厂生产两种产品甲乙，生产过程需要4种设备ABCD 进行加工，每件产品加工所需机时数，每件产品的利润值及每种设备的可利用机时如下表： 1.问：充分利用设备时，应怎样安排甲乙产品的生产数量，利润才能最大？ 2.问：如有另外一家公司想租用该厂设备加工生产，那么，这家公司应至少对每台设备的机时价格为多少时，才能使该厂愿意出租设备？ 解：1.设甲乙产品各生产1x 2x 件
LP1：?????? ?≥≤≤+≤++=0 ,1648 212 2232211 21212 1x x x x x x x x x MaxZ 2.设每台设备的机时最低价分别为：1y ，2y ，3y ，4y LP2：??? ??=≥≥++≥+++++=4,3,2,1,03422242121681242 13 214 321i y y y y y y y y y y y MinZ i 二、原问题和对偶问题之间的关系： 1.对称形式下的原问题与对偶问题 对称形式下原问题的一般式： 矩阵形式： ????? ?? ??=≥≤+++≤+++≤++++++=n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c MaxZ j m n mn m m n n n n n n ....... 21,0 (221) 1222221211 12121112211 ???≥≤=0X b AX CX Max 若用i y 代表第i 种资源的估价，则其对偶问题的一般式为： ????? ?? ??=≥≥+++≥+++≥++++++=m j y c y a y a y a c y a y a y a c y a y a y a y b y b y b MinZ j n m mn n n m mn m m m m ....... 21,0 (221) 1222221121 12211112211 ???≥≥=0Y C Y A Yb Min T T ω 2.非对称形式下原问题与对偶问题： 方法一：将非对称形式转化为对称形式，求出对偶问题，然后再还原。
第二章 对偶理论与灵敏度分析练习题答案 1．判断下列说法是否正确： (1) 任何线性规划问题存在并具有惟一的对偶问题；() (2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；() (3) 设j ? x ，i ?y 分别为标准形式的原问题与对偶问题的可行解，* j x ，*i y 分别为其最优解，则恒有n n m m **j j j j i i i i j 1j 1i 1i 1??c x c x b y b y ====≤=≤∑∑∑∑；() (4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；() (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；() (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；() (7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；() (8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；() (9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；() (10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。() 2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。 要求：(1) (3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。(4)若以单价购入第一种资源是否值得，为什么若有人愿意购买第二种资源应要价多少，为什么
数学建模对偶问题和灵敏度分析
对偶问题 例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为c j 。试问，应如何对这n 种饲料配方，使这批饲料的费用最小? 解 设x j 为第j 种天然饲料的用量。 显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1n ij j j a x =∑为这批混 合饲料中第i 种营养成分的总含量；它不应低于bi 。于是，我们得下列线性规划模型(1—1)： 1 min n j j j f c x ==∑ 1 1,,..01,,n ij j i j j a x b i m s t x j n =?≥=???≥=? ∑ 现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。 设第i 种营养丸的价格为ui(i ＝1，…，m)。则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1m ij i i a u =∑养 鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件： 1 1, ,m ij i j i a u c j n =≤=∑ 另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i
对偶问题 例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为c j 。试问，应如何对这n 种饲料配方，使这批饲料的费用最小 解 设x j 为第j 种天然饲料的用量。 显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1n ij j j a x =∑为这 批混合饲料中第i 种营养成分的总含量；它不应低于bi 。于是，我们得下列线性规划模型(1—1)： 1 min n j j j f c x ==∑ 1 1,,..01,,n ij j i j j a x b i m s t x j n =?≥=???≥=? ∑ 现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。 设第i 种营养丸的价格为ui(i ＝1，…，m)。则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1m ij i i a u =∑养鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件： 1 1, ,m ij i j i a u c j n =≤=∑ 另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i 饲料加工厂面临的问题是：应把这m 种营养丸的单价ui(f=1，…，m)定为多少，才能使养鸡场乐意全部采用该厂生产的营养丸来取代这批天然饲料，且使本厂在竞争中得到最大收益。为该问题建立数学模型，即得如下线性规划(1—2)：
第二章线性规划的对偶问题 习题 2.1 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4 st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤5 4x1＋x2＋x3≤20 2x1－x2＋3x3＝－4 x j≥0 （j＝1,2,3）x1－x3＋x4≥1 x1，x3≥0，x2，x4无约束 (3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15 x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤20 2x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束 2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化： （1）问题的第k个约束条件乘上常数λ（λ≠0）； （2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上； （3）目标函数改变为max z＝λCX（λ≠0）； 'x代换。 （4）模型中全部x1用3 1 2.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4 st. x1＋2x2＋x4≥3 3x1＋x2＋x3＋x4≥6 x3 ＋x4＝2 x1 ＋x3 ≥2 x j≥0（j＝1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。 2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量 st. 2x1 ＋x3＋x4≤8 y1 2x1＋2x2＋x3＋2x4≤12 y2 x j≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3 st. 3x1＋4 x2＋2x3≤60 2x1＋x2＋2x3≤40 x1＋3x2＋2x3≤80 x j≥0 （j＝1,2,3） （1）写出其对偶问题 （2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；
第二章 对偶理论与灵敏度分析练习题答案 1．判断下列说法是否正确： (1) 任何线性规划问题存在并具有惟一的对偶问题；() (2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；() (3) 设j ? x ，i ?y 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m **j j j j i i i i j 1 j 1 i 1 i 1 ??c x c x b y b y ====≤=≤∑∑∑∑；() (4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；() (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；() (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；() (7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；() (8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；() $ (9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；() (10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。() 2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。 X B ｂ x 1 x 2 x 3 x 4 x 5 — x 3 5/2 0 1/2 1 1/2 0 x 1 5/2 1 — -1/2 0 -1/6 1/3 σj 0 -4 0 -4 -2 ; 要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解； (3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。(4)若以单价购入
2.1 写出线性规划问题的对偶问题，并进一步写出其对偶问题的对偶问题 (a) min z=2x1+2x2+4x3(b) max z=5x1+6x2+3x3 s.t. x1+3x2+4x3≥2 s.t. x1+2x2+2x3=5 2x1+x2+3x3≤3 -x1+5x2-3x3≥3 x1+4x2+3x3=5 4x1+7x2+3x3≤8 x1, x2≥0, x3无约束x1无约束,x2≥0, x3≤0 解：(a)对偶问题的原问题为 max w=2y1+3y2+5y3 s.t. y1+2y2+y3≤2 3y1+y2+4y3≤2 4y1+3y2+3y3=4 y1≥0, y2≤0, y3无约束 (b)原问题的对偶问题为 min w=5y1+3y2+8y3 s.t. y1-y2+4y3=5 2y1+5y2+7y3≥6 2y1-3y2+3y3≤3 y1无约束, y2≤0, y3≥0 2.3 已知线性规划问题： max z=x1+x2 s.t. -x1+ x2+ x3 ≤2 -2x1+x2- x3 ≤1 x1, x2, x3≥0 试应用对偶理论证明上述线性规划问题最优解为无界。 解：原问题的对偶问题为 min w=2y1+ y2 s.t. -y1- 2y2 ≥1 2y1+ 5y2 ≥1 y1- y2 ≥0 y1, 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原问题无界.
作业： 问题1：书本P71第7题 1、设x1 、x2 、x3分别为A产量，B产量，C产量 目标函数：Z=4 x1 +x2 +5x3 约束条件： +3x2 + 5x3<=45 6x 3x1 +4x2 +5x3<=30 x1 、x2 、x3>0 2、A的利润在3~6之间，最优计划不变。 3、设x1 、x2 、x3、x4 分别为A产量，B产量，C产量，D产量 目标函数：Z=4 x1 +x2 +5x3+2.5x4 约束条件： +3x2 + 5x3+3x4<=45 6x 3x1 +4x2 +5x3+2x4<=30 x1 、x2 、x3、x4>0 利润从35增加到37.5，值得生产。 4、见Excel 问题2：某厂拟生产甲、乙、丙三种产品，都需要在A，B两种设备上加工，有关数据如下表所示： （1）如何充分发挥设备能力，使产品总产值最大？ 设x1 、x2 、x3分别为甲产量，乙产量，丙产量 目标函数：Z=3 x1 +2x2 +x3 约束条件： +2x2 + 1x3<=400 x 2x1 +1x2 +2x3<=500 x1 、x2 、x3>0 最优解 甲产量乙产量丙产量 200 100 0 总产值最大800 （2） 200个甲产品在A设备上加工1小时，B设备上加工2小时。
100个乙产品在A设备上加工2小时，B设备上加工1小时。 丙产品不生产。 使得总产值最大为80万。 （3）试分别确定甲产品单位产值、B设备供量各自的影响范围。 甲产品的范围是198~201。 B设备供量的范围是200~800。 （4）若每月能以39万元租金租用外厂B设备300台时，则应否租用？为什么？ 原来的产值为80万，租用外厂之后的产值为120万，则产值增加了40万，而租金要39万，则增加的产值足够支付租金，最后剩余1万，说明能租用。 （5）若每月A设备提供量减少200台时，B设备供量增加100台时，试问最优解与影子价格有何变化？ 最优解是600 影子价格：A设备从0.333~3 ；B设备从1.333~0
线性规划的对偶理论与灵敏度分析习题
1 第二章 线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1) ?????? ?≥=++≤++≥++++=无约束 3213213213213 21,0,5343322 43422min x x x x x x x x x x x x x x x z (2) ?????? ?≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 321321321321321x x x x x x x x x x x x x x x z 无约束 (3) ????? ??????==≥=====∑∑∑∑====),,1;,,1(0),,1(),,1(min 1 111 n j m i x n j b x m i a x x c z ij m i j ij n j i ij m i ij n j ij
2 (4) ????? ??????=≥++==<=<=∑∑∑===) ,,,,1(0),,2,1(),,1(min 1 211 111 n n j x m m m i b x a m m i b x a x c z j n j i j ij n j i j ij n j j j 无约束 2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行 解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行 解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶 问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； (4)任何线性规划问题具有唯一的对 偶问题。 3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。 3 2 2 0 0 0
对偶理论与灵敏度分析 对偶问题的提出 对偶理论 影子价格 对偶单纯形法 灵敏度分析
对偶问题的提出 定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题。 应用: 1. 在某些情况下，解对偶问题比解原问题更加容易 2. 对偶变量有重要的经济解释(影子价格) 3. 作为灵敏度分析的工具 4. 对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解) 5. 避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量) 一、对偶问题的提出 例：某家具厂木器车间生产木门与木窗；两种产品。加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。 问：(1)该车间应如何安排生产才能使每日收入最大？ (2)假若有一个个体经营者，手中有一批木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。他就要考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。 解(1)：设该车间每日安排生产木门x 1扇，木窗x 2扇，则数学模型为 X*=(15,20)’ Z*=1440元 ?? ? ??≥≤+≤++=-0502120343056max 21212121x x x x x x x z
解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格 Y*=(2,24)’ W*=1440元 将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的练习与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。 二、L P 和D P 的联系与区别 (1)一个极大化，一个极小化 (2)L P 的价值系数行向量＝(D P 右端项)’ (3)L P 的系数矩阵＝(D P 系数矩阵)’ (4)L P 的右端项＝(D P 的价值系数)’ (5)L P 的约束个数＝D P 的变量个数 (6)L P 的变量个数＝D P 的约束个数 三、原问题与对偶问题的关系 1．对称形式下对偶问题的一般形式 定义：满足下列条件的线性规划问题称为具有对称形式：(1)其变量均为非负约束；(2)其约束条件当目标函数求极大时取“≤”号，当目标函数求极小时取“≥”号；(3)右端项b 可取负值。 ?? ? ??≥≥+≥++=-0303562450120min 2121212 1y y y y y y y w ????? ???????=≥≤+???++???? ??≤+???++≤+???++ +???++=),,1(0max :221122222121112121112211n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c z LP j m n mn m m n n n n n n
线性规划原问题与对偶问题的转化及其应用 摘要 线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进行科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进行解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解. 关键词：线性规划；原问题；对偶问题；转化
Linear Programming is the Original Problem and the Transformation of the Dual Problem and Applications Abstract: Linear programming in operational research is research earlier, rapid development and wide application, the method is an important branch of mature, it is one of the scientific management of auxiliary people mathematical method. Can from different angles to linear programming dual problem for policy makers to provide more scientific theory basis. This article mainly probes into the linear programming problem and the relationship between the dual problem, linear programming problem and the transformation of the dual problem, the application of linear programming dual problem. This article is the complex of the original problem into its dual problem to be solved, simplifies the linear programming problem, enables us to rapidly find the optimal solution of linear programming problem. Keywords: linear programming; the original problem; the dual problem; conversion
第四章 线性规划的对偶理论 一、填空题 1．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的线性规划问题与之对应，反之亦 然。 2．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。 3．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。 4．对偶问题的对偶问题是原问题_。 5．若原问题可行，但目标函数无界，则对偶问题不可行。 6．若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时。相应的目标函数值将增加3k 。 7．线性规划问题的最优基为B，基变量的目标系数为C B，则其对偶问题的最优解Y﹡= C B B－1。 8．若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX ﹡= Y﹡b。 9．若X、Y分别是线性规划的原问题和对偶问题的可行解，则有 CX≤Yb。 10．若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡=Y*b。 11．设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为min=Yb YA≥c Y≥0_。 12．影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。 13．线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为A T 。 14．在对偶单纯形法迭代中，若某b i<0，且所有的a ij≥0(j=1，2，…n)，则原问题_无解。 二、单选题 1．线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为A形式。 A．“≥” B．“≤” C，“>” D．“=” 2．设、分别是标准形式的原问题与对偶问题的可行解,则 C 。 3．对偶单纯形法的迭代是从_ A_开始的。 A．正则解 B．最优解 C．可行解 D．基本解 4．如果z。是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值w﹡A。
例4-7 用对偶单纯形法求解线性规划问题 Min z =5x 1+3x 2 X 1 - 6 x 2 A 4 在表4-17中,b=-16<0,而yA 0,故该问题无可行解. 注意：对偶单纯形法仍是求解原问题 ，它是适用于当原问题无可行基 ，且所有检验数均为负 的情况. 若原问题既无可行基，而检验数中又有小于 0的情况.只能用人工变量法求解. 在计算机求解时，只有人工变量法，没有对偶单纯形法. 3.对偶问题的最优解 由对偶理论可知，在原问题和对偶问题的最优解之间存在着密切的关系 从求解原问题的最优单纯形表中 ，得到对偶问题的最优解. (1)设原问题(P)为 Min z= ex s.t. -2 X i + 3x 2 A 6 A 0 (j=1,2 ) 解：将问题转化为 Xj Max z = -5 X 1 -3 x 2 s.t. 2 x i - 3x X 3 = -6 -3 x i + 6 X 2 + x 4A -4 Xj 其中，X 3 , X 4 ,3,4 ) A 0 (j=1,2 为松弛变量，可以作为初始基变量，单纯形表见表 4-17. ,可以根据这些关系，
Xj > 0 (j=1,2 , 3,4 ) 则标准型 (LP) 为 AX b s.t. X0 Max z=CX AX b s.t. X0 其对偶线性规划(D )为 Max z=b T Y AX b s.t. X0 用对偶单纯形法求解 时，有 Pj=-e i ， c j =0 (LP ),得最优基B 和最优单纯形表 T ( B )。对于(LP )来说，当j=n+i T (B )中，对于检验数，有 (b n+1,b n+2???b n+m) = (C n+i , c n+2…，c n+m ) -C B B -1 (Pn +1,Pn+2 …,Pn+m ) =- C B B -1 (-I) 于是，Y*= (b n+1,b n+2…b n+m T 。可见，在(LP )的最优单纯形表中，剩余变 量对应的检验数就是对偶问题的最优解。 同时，在最优单纯形表 T ( B )中，由于剩余变量对应的系数 所以 从而，在最优单纯形表 b n +2 …b B 1 = ( -y n+1 , -y n+2 …-y n+m ) 例 4-8 求下列线性规划问题的对偶问题的最优解。 Min z =6x 1+8x 2 s.t. X i + 2x 2 >20 X 1 + 2x 2 A 50 Xj > 0 (j=1,2 ) 解： 将问题转化为 Max z =-6x 1-8x 2 s.t. -x 1 — 2x 2 + x 3=20 -3 X 1 - 2X 2 + X 4 =50