i i i
i
第二章 线性规划的对偶理论和灵敏度分析自测题
1. 判断下述说法是否正确
(1) 任何线性规划问题存在并具有唯一的对偶问题。 (2) 线性规划原问题的对偶问题的对偶是原问题本身。
(3) 原问题的任一可行解对应的目标函数值都不超过其对偶问题的任一可行解对应的目标函数值。
(4) 已知对偶问题的最优解中， y * > 0 ，则原问题中在资源最优配置下，第i 种资源已完全消 耗殆尽。
(5) 已知对偶问题的最优解中， y * = 0 ，则原问题中在资源最优配置下，第 i 种资源一定未 完全消耗。
(6) 影子价格就是市场价格。
(7) 若第 i 种资源的影子价格为 y * > 0 ，则在保持原问题中其它条件不变时，在资源最优配置下，当第i 种资源增加10个单位时，最优值将一定增加10 y * .
(8) 在应用对偶单纯形法计算时，若在某一个单纯形表中，出现某行除该行对应的基变量值
小于0外，该行其余元素全部大于或等于0，则可以判断该线性规划问题无最优解。
(9) 在应用对偶单纯形法计算时，若在某一个单纯形表中，出现某行除该行对应的基变量值小于0外，该行其余元素全部小于或等于0，则可以判断该线性规划问题的对偶问题无最优解。 (10)线性规划的原问题和其对偶问题的最优值如果存在，则必然相等。
(11)线性规划问题的最终单纯形表中，当仅某一非基变量在目标函数中的系数变化时，线性规划问题的最优解一定不改变。
(12)线性规划问题的最终单纯形表中，当仅有某一基变量在目标函数中的系数变化时，线性规划问题的最优解一定不改变。 (13)线性规划问题的最终单纯形表中，当仅有某一非基变量在系数矩阵中的列变化时，线性规划问题的最优解一定不改变。
(14)线性规划问题的最终单纯形表中，当仅有某一基变量在系数矩阵中的列变化时，线性规划问题的最优解一定不改变。 (15)线性规划问题的最终单纯形表中，当仅有某种资源的数量变化时，线性规划问题的最优值一定改变。
2. 简述影子价格的经济含义。
3. Min ω=2x 1＋3x 2＋5x 3＋6x 4
x 1＋2x 2＋3x 3＋ x 4 ≥ 2
－2x 1＋ x 2－ x 3＋3x 4 ≤－3 x j ≥0, j =1,2, …,4 (1) 写出其对偶问题。 (2) 求解其对偶问题。
(3) 利用对偶性质求原问题的解。
4. 某企业生产A
(1)列出数学模型。
(2)求出最优的生产计划。
(3)影子价格是多少？
(4)B产品的价格提高多少，才进行生产？
(5)增加人工500小时，最大利润为多少？5.
(1)由结果图表读出最优解。
(2)由结果图表进行灵敏度分析。
判断题 判断正误，如果错误请更正 第二章线形规划的对偶理论 1.原问题第i个约束是<=约束,则对偶变量yi>=0. 2.互为对偶问题,或则同时都有最优解,或则同时都无最优解. 3.原问题有多重解,对偶问题也有多重解. 4.对偶问题有可行解,原问题无可行解,则对偶问题具有无界解. 5.原问题无最优解,则对偶问题无可行解. 6.设X,Y分别为｛minZ=CX｜AX>=b,X>=0｝和｛maxw=Yb｜YA<=C,Y>=0｝的可行 解,则有(1)CX<=Yb; (2)CX是w的上界; (3)当X,Y为最优解,CX=Yb; (4)当CX=Yb 时,有YXs+YsX=0; (5)X为最优解且B是最优基时,则Y=C B B-1是最优解; (6)松弛变量Ys的检验数是λs,则X=-λs是基本解,若Ys是最优解, 则X=-λs是 最优解. 7.原问题与对偶问题都可行,则都有最优解. 8.原问题具有无界解,则对偶问题可行. 9.若X,Y是原问题与对偶问题的最优解.则X=Y. 10.若某种资源影子价格为0,则该资源一定有剩余. 11影子价格就是资源的价格. 12.原问题可行对偶问题不可行,可用对偶单纯形法计算. 13.对偶单纯形法比值失效说明原问题具有无界解. 14.对偶单纯形法是直接解对偶问题的一种解法. 15.减少一个约束,目标值不会比原来变差. 16.增加一个约束,目标值不会比原来变好. 17增加一个变量, 目标值不会比原来变差. 18.减少一个非基变量, 目标值不变. 19.当Cj(j=1,2,3,……，n)在允许的最大范围内同时变化时，最优解不变。 选择题 在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。 第二章线性规划的对偶理论 1.如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划 A约束 条件相同 B目标函数相同 C最优目标函数值相同 D以上结论都不对 2.对偶单纯形法的最小比值规则是为了保证 A使原问题保持可行 B使对偶问题 保持可行 C逐步消除原问题不可行性 D逐步消除对偶问题不可行性 3.互为对偶的两个线性规划问题的解存在关系 A若最优解存在，则最优解相同 B原问题无可行解，则对偶问题也无可行解 C对偶问题无可行解，原问题可能无可行解D一个问题无界，则另一个问题无可行解 E一个问题无可行解，则另一个问题具有无界解 4.已知规范形式原问题（max）的最优表中的检验数为（λ1，λ2，……λn），
i i i i 第二章 线性规划的对偶理论和灵敏度分析自测题 1. 判断下述说法是否正确 (1) 任何线性规划问题存在并具有唯一的对偶问题。 (2) 线性规划原问题的对偶问题的对偶是原问题本身。 (3) 原问题的任一可行解对应的目标函数值都不超过其对偶问题的任一可行解对应的目标函数值。 (4) 已知对偶问题的最优解中， y * > 0 ，则原问题中在资源最优配置下，第i 种资源已完全消 耗殆尽。 (5) 已知对偶问题的最优解中， y * = 0 ，则原问题中在资源最优配置下，第 i 种资源一定未 完全消耗。 (6) 影子价格就是市场价格。 (7) 若第 i 种资源的影子价格为 y * > 0 ，则在保持原问题中其它条件不变时，在资源最优配置下，当第i 种资源增加10个单位时，最优值将一定增加10 y * . (8) 在应用对偶单纯形法计算时，若在某一个单纯形表中，出现某行除该行对应的基变量值 小于0外，该行其余元素全部大于或等于0，则可以判断该线性规划问题无最优解。 (9) 在应用对偶单纯形法计算时，若在某一个单纯形表中，出现某行除该行对应的基变量值小于0外，该行其余元素全部小于或等于0，则可以判断该线性规划问题的对偶问题无最优解。 (10)线性规划的原问题和其对偶问题的最优值如果存在，则必然相等。 (11)线性规划问题的最终单纯形表中，当仅某一非基变量在目标函数中的系数变化时，线性规划问题的最优解一定不改变。 (12)线性规划问题的最终单纯形表中，当仅有某一基变量在目标函数中的系数变化时，线性规划问题的最优解一定不改变。 (13)线性规划问题的最终单纯形表中，当仅有某一非基变量在系数矩阵中的列变化时，线性规划问题的最优解一定不改变。 (14)线性规划问题的最终单纯形表中，当仅有某一基变量在系数矩阵中的列变化时，线性规划问题的最优解一定不改变。 (15)线性规划问题的最终单纯形表中，当仅有某种资源的数量变化时，线性规划问题的最优值一定改变。 2. 简述影子价格的经济含义。 3. Min ω=2x 1＋3x 2＋5x 3＋6x 4 x 1＋2x 2＋3x 3＋ x 4 ≥ 2 －2x 1＋ x 2－ x 3＋3x 4 ≤－3 x j ≥0, j =1,2, …,4 (1) 写出其对偶问题。 (2) 求解其对偶问题。 (3) 利用对偶性质求原问题的解。 4. 某企业生产A
第二章 线性规划的对偶理论与灵敏度分析 主要内容 对偶问题、对偶基本性质、对偶单纯形方法、灵敏度分析、参数规划 讲授重点 对偶基本性质、对偶单纯形方法、灵敏度分析 讲授方式 讲授式、启发式 本章知识结构图 第一节 线性规划的对偶问 题 一、对偶问题的提出 首先通过实际例子看对偶问题的经济意义。 例1 第一章例1中美佳公司利用该公司资源生产两种家电产品时，其线性规划问题为： (LP 1) max z ＝2x l +x 2 ⎪⎪⎩⎪⎪⎨ ⎧≥≤+≤+≤0,5242615 52121212x x x x x x x 现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源.显然美佳公司愿出让自己资源的条件是,出让代价应不低于用同等数量资源由自己组织生产活动时获取的盈利.设分别用y 1、y 2、和y 3代表单位时间(h ）设备A 、设备B 和调试工序的出让代价。因美佳公司用6小时设备A 和1小时调试可生产一件家电I ，盈利2元；用5小时设备A,2小时设备B 及1小时调试可生产一件家电Ⅱ，盈利1元。由此y1，y2，y3的取值应满足 6y 2+y 3≥2 5y 1+2y 2+y 3≥1 （2。1) 又另一公司希望用最小代价把美佳公司的全部资源收买过来，故有 min z ＝15y 1+24y 2+5y 3 （2。2） 显然y i ≥0(i ＝l ，2，3），再综合（2。1)，(2。2)式有。 (LP 2) min ω＝15y 1+24y 2+5y 3
⎪⎩⎪ ⎨⎧≥≥+≥+0,,125263212132y y y y y y y 上述LP 1和LP 2是两个线性规划问题,通常称前者为原问题，后者是前者的对偶问题。 二、对称形式下对偶问题的一般形式 定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“≤"号，当目标函数求极小时均取“≥”号’. 对称形式下线性规划原问题的一般形式为: max z=c 1x 1+c 2x 2+…+c n x n ⎪⎪⎪⎩⎪ ⎪⎪ ⎨⎧=≥≤+⋅⋅⋅++≤+⋅⋅⋅++≤+⋅⋅⋅++),,1(022112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n （2.3) 用y i （i=1，…,m ）代表第i 种资源的估价，则其对偶问题的一般形式为： min w=b 1y 1+b 2y 2+…+b m y m ⎪⎪⎪⎩⎪ ⎪⎪⎨⎧⋅⋅⋅=≥≥+⋅⋅⋅++⋅ ⋅⋅⋅⋅⋅⋅⋅⋅≥+⋅⋅⋅++≥+⋅⋅⋅++),,1(0221 12222212111212111m i y c y a y a y a c y a y a y a c y a y a y a y i n m mn n n m m m m (2。4) 用矩阵形式表示,对称形式的线形规划问题的原问题为： max z=CX ⎩⎨ ⎧≥≤0X b AX （2。5） 其对偶问题为： min w=Y ’b ⎩ ⎨ ⎧≥≥0'Y C Y A 将上述对称形式下线性规划的原问题与对偶问题进行比较,可以列出如表2—1所示的对应关系。
第二章线性规划的对偶理论 2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3 x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0 解：其对偶问题为 min w=30y1+ 80y2 y1+ 4y2≥2 3y1 + 2y2 ≥2 3y1 + 4y2≥－4 y1、y2≥0 2.2 写出下列线性规划问题的对偶问题 min z=2x1+8x2－4x3 x1 + 3x2－3x3 ≥30 －x1 + 5x2 + 4x3 = 80 4x1 + 2x2－4x3≤50 x1≤0、x2≥0，x3无限制 解：其对偶问题为 max w=30y1+80 y2+50 y3 y1－y2 + 4 y3≥2 3y1+5y2 + 2y3≤8 －3y1 + 4y2－4y3 =－4 y1≥0，y2无限制，y3≤0 2.3已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0 其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。 解：其对偶问题为
min w=20y1+ 20y2 y1 + 2y2≥1 （1） 2y1 + y2 ≥2 （2） 2y1 +3y2≥3 （3） 3y1 +2y2≥4 （4） y1、y2≥0 将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以 2x3*+3x4* = 20 3x3* +2x4* = 20 解得x3* = x4* = 4。故原问题的最优解为 X*=（0，0，4，4）T 2.4用对偶单纯形法求解下列线性规划 min z=4x1+2x2+6x3 2x1 +4x2 +8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2，x3≥0 解将问题改写成如下形式 max（－z）=－4x1－2x2－6x3 －2x1－4x2 －8x3 + x4=－24 －4x1－x2－4x3+x5 =－8 x1、x2，x3，x4，x5≥0 显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。
习题 2-1 判断下列说法是否正确： （1） 任何线性规划问题存在并具有惟一的对偶问题； （2） 对偶问题的对偶问题一定是原问题； （3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之， 当对偶问题无可行解时，其原问题具有无界解； （4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优 解； （5） 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出 现原问题与对偶问题均为非可行解的情况； （6） 应用对偶单纯形法计算时，若单纯形表中某一基变量x i <0，又x i 所在行的元素全 部大于或等于零，则可以判断其对偶问题具有无界解。 （7） 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加 5个单位时，相应的目标函数值将增大5k ； （8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优生产计划中第 i 种资源已经完全耗尽；若y i =0，说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ??? ?? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束43214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z ()??? ??≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 解：(1)令''' 444 x x x =-，增加松弛变量5x ，剩余变量6x ，则该问题的标准形式如下所示： ''' 12344''' 12344''' 123445''' 123446'''1234456max 342554222214..232 ,,,,,,0 z x x x x x x x x x x x x x x x x s t x x x x x x x x x x x x x =-+-+-?-+-+-=?+-+-+=??-++-+-=??≥? (2)令' z z =-，'11x x =-，''' 333x x x =-，增加松弛变量4x ，则该问题的标准 形式如下所示：
习题二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) 第一章 线性规划 ........................................................................................................... 1 第二章 对偶规划及灵敏度分析 ........................................................................................... 12 第三章 运输问题 ................................................................................................................... 17 第四章 整数规划 ................................................................................................................... 22 第五章 动态规划 ................................................................................................................... 27 第六章 图与网络分析 .. (34) 第一章 线性规划 1.1将下列线性规划模型转化为标准型： （1）2164.x x Z Min += （2）212.x x Z Min --= ⎪⎪⎩⎪⎪⎨ ⎧≥=-≤+≥-0,46710263. .21212 121x x x x x x x x t S ⎪⎪⎩ ⎪⎪⎨ ⎧≤≥+-=--≤+03023505270 53..1212 121x x x x x x x t S 【解】（1）—2164)(x x Z Max --=- ⎪⎪⎩⎪⎪⎨ ⎧≥=-=++=--0 ,,,4671026 3. .2121212 21121s s x x x x s x x s x x t S （2）—v u y Z Max 22)(1+--=- ⎪⎪⎩ ⎪⎪⎨ ⎧≥=-+=+-=+-+-0,,302235055270553. .111 11v u y v u y v u y s v u y t S 1.2 用图解法解下列线性规划问题：
第二章线性规划的对偶理论4-灵敏度分析 是指对系统或事物因周围条件变化显示出来 的敏感程度的分析。 以前在线性规划问题中，都假定问题中的a ij ，b i ，c j 是已知数。但实际上这些数往往是一些估计和预测的数据，如c j 随市场条件的改变而改变；a ij 随工艺条件的改变而改变；b i 则是根据资源投入后能产生多大经济效果来决定的一种决策变量。 当这些参数中的一个或几个变化时，问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变。这就是灵敏度分析所要研究解决的问题。 第二章对偶理论与灵敏度分析 2.4 灵敏度分析 C N -C B B -1N -C B B -1 0c j -z j B -1N B -1 I C B X B B -1b X N X s X B 非基变量基变量 当B 为最优基时，上表检验数行应≤0 灵敏度分析的步骤可以归纳如下： 1.将参数的改变计算反映到最终单纯形表上来： △b /=B -1△b △P /j =B -1 △P j (c j -z j ) /= c j -∑=*m i i ij y a 12. 检查原问题是否仍为可行解 3. 检查对偶问题是否仍为可行解 4. 按下表所列情况得出结论和决定继续计算的步骤 原问题对偶问题结论或继续计算的步骤 可行解可行解问题的最优解或最优基不变 可行解非可行解用单纯形法继续迭代求最优解 非可行解可行解用对偶单纯形法继续迭代求最优解 非可行解非可行解引进人工变量，编制新的单纯形表重新计算
一、分析c 的变化 j 的变化 二、分析b i 的分析 三、增加一个变量x j 的变化 四、分析参数a ij 五、增加一个约束条件的分析 、分析c j 的变化 例：在最初讲的第一个例子中，（1）若甲种产品的利润降至 1.5元/件，而乙的利润增至2元/件时，该公司的最优生产计划有何变化；解：(1) 将甲、乙的利润变化直接反映到最终单纯形表中得下表 c j 1.52000C B 基b x 1 x 2 x 3 x 4x 5 0x 315/20015/4-15/2 1.5 x 1 7/21001/4-1/22x 2 3/2010-1/43/2c j -z j 0001/8-9/4 [ ]例一
第二章 对偶理论与灵敏度分析练习题答案 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)若以单价2.5购入第一种资源是否值得，为什么？若有人愿意购买第二种资源应要价多少，为什么？
一、填空题 1、对偶问题的对偶问题是（）。 正确答案：原问题 2、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y﹡b。 正确答案：= 3、若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX（）Yb。 正确答案：<= 4、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y*b。 正确答案：= 5、设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为（）。 正确答案：min=Yb YA>=c Y>=0 6、影子价格实际上是与原问题各约束条件相联系的（）的数量表现。 正确答案：对偶变量 7、线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为（）。 正确答案：AT 8、在对偶单纯形法迭代中，若某bi<0，且所有的aij≥0(j=1，2，…
n)，则原问题（）。 正确答案：无解 二、选择题 1、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。 A. “≥” B. “≤” C. “>” D. “=” 正确答案：A 2、如果z*是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值w﹡满足（）。 A.W﹡=Z﹡ B.W﹡≠Z﹡ C.W﹡≤Z﹡ D.W﹡≥Z﹡ 正确答案：A 3、如果某种资源的影子价格大于其市场价格，则说明（）。 A.该资源过剩 B.该资源稀缺 C.企业应尽快处理该资源 D.企业应充分利用该资源，开辟新的生产途径
正确答案：B 4、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。 A.≥ B.≤ C. > D. = 正确答案：A 5、对偶单纯形法的迭代是从（）开始的。 A.正则解 B.最优解 C.可行解 D.可行解 正确答案：A 6、如果某种资源的影子价格大于其市场价格，则说明（）。 A.该资源过剩 B.该资源稀缺 C.企业应尽快处理该资源 D.企业应充分利用该资源，开辟新的生产途径 正确答案：B 7、线性规划灵敏度分析的主要功能是分析线性规划参数变化对（）的影响。
线性规划的灵敏度分析试题 一、填空题 1、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。 2、在线性规划的灵敏度分析中，我们主要用到的性质是_可行性，正则性。 3．在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的变化。 4．如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应出基。 5．约束常数b；的变化，不会引起解的正则性的变化。 6．在某线性规划问题中，已知某资源的影子价格为Y1，相应的约束常数b1，在灵敏度容许变动范围内发生Δb1的变化，则新的最优解对应的最优目标函数值是Z*+y i△b(设原最优目标函数值为Z﹡) 7．若某约束常数b i的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用对偶单纯形法求解。 8．已知线性规划问题，最优基为B，目标系数为C B，若新增变量x t，目标系数为c t，系数列向量为Pt，则当C t≤C B B－1P t时，x t不能进入基底。 9．如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个变量。 10、若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加一行，一列。 11．线性规划灵敏度分析应在最优单纯形表的基础上，分析系数变化对最优解产生的影响12．在某生产规划问题的线性规划模型中，变量x j的目标系数C j代表该变量所对应的产品的利润，则当某一非基变量的目标系数发生增大变化时，其有可能进入基底。 二、单选题 1．若线性规划问题最优基中某个基变量的目标系数发生变化，则C。 A．该基变量的检验数发生变化B．其他基变量的检验数发生变化C．所有非基变量的检验数发生变化D．所有变量的检验数都发生变化 2．线性规划灵敏度分析的主要功能是分析线性规划参数变化对D的影响。 A．正则性B．可行性C．可行解D．最优解 3．在线性规划的各项敏感性分析中，一定会引起最优目标函数值发生变化的是B。 A．目标系数c j的变化B．约束常数项b i变化C．增加新的变量 D．增加新约束 4．在线性规划问题的各种灵敏度分析中，B_的变化不能引起最优解的正则性变化。 A．目标系数B．约束常数C．技术系数D．增加新的变量E．增加新的约束条件 5．对于标准型的线性规划问题，下列说法错误的是C A．在新增变量的灵敏度分析中，若新变量可以进入基底，则目标函数将会得到进一步改善。B．在增加新约束条件的灵敏度分析中，新的最优目标函数值不可能增加。C．当某个约束常数b k增加时，目标函数值一定增加。D．某基变量的目标系数增大，目标函数值将得到改善 6.灵敏度分析研究的是线性规划模型中最优解和 C 之间的变化和影响。 A 基 B 松弛变量 C原始数据 D 条件系数 三、多选题 1．如果线性规划中的c j、b i同时发生变化，可能对原最优解产生的影响是_ ABCD. A．正则性不满足，可行性满足B．正则性满足，可行性不满足C．正则性与可行性都满足D．正则性与可行性都不满足E．可行性和正则性中只可能有一个受影响 2．在灵敏度分析中，我们可以直接从最优单纯形表中获得的有效信息有ABCE。 A．最优基B的逆B-1B．最优解与最优目标函数值C．各变量的检验数D．对偶问题的解E．各列向量 3．线性规划问题的各项系数发生变化，下列不能引起最优解的可行性变化的是ABC_。A．非基变量的目标系数变化 B．基变量的目标系数变化C．增加新的变量D，增加新的约束条件 4．下列说法错误的是ACD A．若最优解的可行性满足B-1b≥0，则最优解不发生变化B．目标系数c j发生变化时，解的正则性将受到影响C．某个变量x j的目标系数c j发生变化，只会影响到该变量的检验数的变化D．某个变量x j的目标系数c j发生变化，会影响到所有变量的检验数发生变化。 四、名词、简答题 1.灵敏度分析：研究线性规划模型的原始数据变化对最优解产生的影响 2．线性规划问题灵敏度分析的意义。（1）预先确定保持现有生产规划条件下，单位产品利
第二章 线性规划问题的对偶理论与灵敏度分析总结 一．对偶问题统一归纳表 注意：对偶问题允许i b 小于0，也正是对于原问题i b 小于0，才引入了后面的对偶单纯形法解决问题。 二．对偶问题的基本性质 ⎩⎨ ⎧≥≤=0 X ..max 设原问题为b AX t s CX z ⎩⎨ ⎧≥≥=是列向量 ,0A .. min 对偶问题为 T Y Y C Y t s Yb T T ω
1.对称定理：对偶问题的对偶是原问题 2.弱对偶性定理：若Y X 和分别是原问题和对偶问题的可行解，则有b T Y X C ≤ 推论（1）max 问题的任一可行解的目标是对偶问题最优目标值的一个下界。min 问题的任一可行 解的目标函数 值是原问题最优目标值的一个上界。 （2）若原问题可行且其目标函数值无界，则对偶问题无可行解。反之对偶问题可行且其目标函数值无界，则原问题无可行解。 （3）若原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而原问题无可行解，则对偶问题目标函数值无界。 3. 最优性定理：若Y X 和分别是原问题和对偶问题的可行解，并且b T Y X C =，则X 是原问题最优解，Y 是其对偶问题的最优解 4. 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。 5.互不松弛性：若Y X 和分别是原问题和对偶问题的可行解，则它们分别是最优解的充要条件是： 0ˆ,ˆˆ0ˆ1 j 1 =<=>∑∑==i i n j ij i n j j ij i y b x a b x a y 则如果，则如果 练习：判断下列说法是否正确： (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 ====≤=≤∑∑∑∑；(✓) (5) 已知* i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；(✓) (6) 已知* i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；(✗) 简析：对(5)、(6)，由互补松弛性质判断，具体详见课本P59 三．对偶单纯形法 (1). 对偶单纯形法应用前提： 1.检验数行全部非正 2.变量取值有负数 (2). 对偶单纯形法计算步骤：
第二章 对偶问题与灵敏度分析 一、写出下列线性规划的对偶问题 1、P89,2.1(a) 321422m in x x x Z ++= s.t ⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++. ,0,;534;332;2433213213 21321无约束x x x x x x x x x x x x 解：原模型可化为 321422m in x x x Z ++= s.t ⎪⎪⎩⎪⎪ ⎨⎧≥=++≥≥++. ,0,;534; 3-3--2-;24332 13 2 1 32132 1321无约束x x x y y y x x x x x x x x x 于是对偶模型为 321532m ax y y y W +-= s.t ⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+-≤+-.,0,;4334;243;223213213 21321无约束 y y y y y y y y y y y y 2、P89,2.1(b) 321365m ax x x x Z ++= s.t ⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++. 0,0,;8374;35;5223213213 21321x x x x x x x x x x x x 无约束 解：令033 ≥-='x x 原模型可化为 3 21365m ax x x x Z '-+=
s.t ⎪⎪⎩⎪⎪ ⎨⎧≥'≥≤'+≤'='+. 0,0,; 83-74;3--5-;52-2321 3 21 3213 21321x x x y y y x x x x x x x x x 无约束 于是对偶模型为 321835m in y y y W +-= s.t ⎪⎪⎩⎪⎪⎨⎧≥-≥---≥+-=++.0,,;332;6752;54321321321321y y y y y y y y y y y y 无约束 或⎪⎪⎩⎪⎪⎨⎧≥≤++≥+-=++. 0,,;332;6752; 543213213 21321y y y y y y y y y y y y 无约束 二、灵敏度分析 1、P92, 2.11线性规划问题 213m ax x x Z += s.t ⎪⎩⎪ ⎨⎧≥≤+≤+0,1025; 742 12121x x x x x x 最优单纯形表如下 试用灵敏度分析的方法，分析： （1） 目标函数中的系数21,c c 分别在什么范围内变化，最优解不变？ （2） 约束条件右端常数项21,b b 分别在什么范围内变化，最优基保持不变？ 解：（1） 1c 的分析：要使得最优解不变，则需
《运筹学》课程练习题 第一章：线性规划及单纯形法 1.1 用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。 1.4.1用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。 1.7.1 用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。 1.13某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲养可供选用，各种饲料每kg营养成分含量及单价如表1-20所示。 表1-20
要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。（建立这个问题的线性规划模型，不求解） 1.15一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表1-22所示。现有三种货物待运，已知有关数据列于表1-23。 表1-22 表1-23 第二章：线性规划的对偶理论与灵敏度分析 2.12
2.14 某厂生产A,B,C三种产品，其所需劳动力、材料等有关数据见表2-34。 要求：（1）确定获利最大的产品生产计划；（2）产品A的利润在什么范围内变动时，上述最优计划不变；（3）如果设计一种新产品D,单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？（4）如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以构多少为宜。 表2-32 第三章：运输问题
3.10 3.11 1，2，3三个城市每年需分别供应电力320，250和350单位，由I ，II 两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用如表3-34所示。由于需要量大于可供量，决定城市1的供应量可减少0～30单位，城市2的供应量不变，城市3的供应量不能少于270单位，试求总费用最低的分配方案（将可供电量用完）。 表3-34 第四章：目标规划 4.4 某成品酒有三种商标（红、黄、蓝），都是由三种原料酒（等级I ，II ，III ）兑制而成。三种等级的原料酒的日供应量和成本见表4-13，三种商标的成品酒的兑制要求和售价见表4-14。决策者规定：首先必须严格按规定比例兑制各商标的酒；其次是获利最大；再次是红商标的酒每天至少生产2 000kg 。试列出该问题的数学模型。 表4-13
第二章 线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1)⎪⎪⎩⎪⎪ ⎨ ⎧≥=++≤++≥++++=无约束 3213213213213 21,0,5343 32243422min x x x x x x x x x x x x x x x z (2) ⎪⎪⎩⎪⎪ ⎨ ⎧≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 3213213213213 21x x x x x x x x x x x x x x x z 无约束 (3)⎪⎪ ⎪⎪⎩ ⎪⎪⎪ ⎪⎨⎧==≥=====∑∑∑∑====) ,,1;,,1(0) ,,1(),,1(min 1 111n 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 (4)⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥++==<=<=∑∑∑===),,,,1(0),,2,1() ,,1(min 1 211111n 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. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。
第一章 线性规划及单纯形法 （作业） 1.4 分别用图解法和单纯型法求解下列线性规划问题，并对照指出单纯形表中的各基可行 解对应图解法中可行域的哪一顶点。 （1）Max z=2x 1+x 2 St.⎪⎩⎪ ⎨⎧≥≤+≤+0,242615532 12121x x x x x x 解：①图解法： 由作图知，目标函数等值线越往右上移动，目标函数越大，故c 点为对应的最优解，最优解 为直线⎩⎨⎧=+=+24 2615532121x x x x 的交点，解之得X=(15/4,3/4)T 。 Max z =33/4. ② 单纯形法： 将上述问题化成标准形式有： Max z=2x 1+x 2+0x 3+0x 4 St. ⎪⎩⎪ ⎨⎧≥≤++≤++0,,,242615535 421421321x x x x x x x x x x 其约束条件系数矩阵增广矩阵为：
P 1 P 2 P 3 P 4 ⎥⎦ ⎤⎢⎣⎡241026150153 P 3,P 4为单位矩阵，构成一个基，对应变量向，x 3,x 4为基变量，令非基变量x 1,x 2为零，找到 T 优解，代入目标函数得Max z=33/4. 1.7 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题，并指出属哪一类。 （3）Min z=4x 1+x 2 ⎪⎪⎩⎪⎪⎨ ⎧=≥=++=-+=+) 4,3,2,1(0426343 34213 2121j xj x x x x x x x x 解：这种情况化为标准形式： Max z ＇=-4x 1-x 2 ⎪⎪⎩ ⎪⎪⎨ ⎧=≥=++=-+=+)4,3,2,1(0426343 34213 2121j xj x x x x x x x x 添加人工变量y1,y2 Max z ＇=-4x 1-x 2+0x 3+0x 4-My 1-My 2