第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么？ 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量 0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量 0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0数学建模 对偶问题和灵敏度分析
对偶问题 例题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 m i n 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 i j 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 对偶与灵敏度分析 §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．判断下列说法是否正确： (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)若以单价购入
作业： 问题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