对偶理论和灵敏度分析

第二章 对偶理论与灵敏度分析练习题答案

1．判断下列说法是否正确：

(1) 任何线性规划问题存在并具有惟一的对偶问题；()

(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；()

(3) 设jˆx，iˆy分别为标准形式的原问题与对偶问题的可行解，*jx，*iy分别为其最优解，则恒有nnmm**jjjjiiiij1j1i1i1ˆˆcxcxbyby；()

(4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；()

(5) 已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源已完全耗尽；()

(6) 已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源一定有剩余；()

(7) 若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；()

(8) 应用对偶单纯形法计算时，若单纯形表中某一基变量ix0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；()

(9) 若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；()

(10) 在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。()

2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x4、x5为松弛变量。

XB ｂ x1 x2 x3 x4 x5

x3 5/2 0 1/2 1 1/2 0

x1 5/2 1 -1/2 0 -1/6 1/3

σj 0 -4 0 -4 -2

要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解；

山东大学期末考试知识点复习

第二章对偶理论和灵敏度分析

1．对偶问题间的关系

若某线性规划(原问题)约束系数矩阵为A，约束条件右端为向量6，目标函数中的价值系数向量为C，则其对偶问题形式如表2—1所示。

2．对偶理论及其性质

(1)对称性：对偶问题的对偶是原问题。 山东大学期末考试知识点复习

则原问题单纯形表的检验数行对应其对偶问题的一个基解。

3．影子价格

影子价格：根据资源在生产中作出的贡献而作的估价。影子价格是一种边际价格，其值相当于在资源得到最优利用的生产条件下，资源每增加一个单位时目标函数的增加量。

影子价格的大小反映了资源的稀缺和富有程度。在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源以扩大再生产；反之，则应将已有资源卖掉。可见，影子价格对市场有调节作用。

4．对偶单纯形法

(1)正则解：检验数全部为非正的基本解。它一般为不可行解，如果可行，则为最优解。

(2)原理：从一个正则解出发，用单纯形法进行迭代，迭代过程中始终保持解的正则性，使解的不可行性消失，所得第一个可行解即为最优解。

(3)适用范围：具有正则解，且在迭代过程中始终保持解的正则性不变的线性规划问题。 山东大学期末考试知识点复习

(4)求解步骤。

①根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得最优解，停止计算。若b列的数字至少还有一个负分量，检验数都为非正，转入下一步。

②确定换出变量。

θ=min{(B-1b)i|(B-1b)i＜0)=(B-1b)t

对应的基变量xi为换出变量。

③按θ规则确定换入变量。

在单纯形表中检查xt所在行的系数alj，(j=1，2，…，n)。

若所有atj≥0，则原问题是为无界解，停止计算。

若存在atj＜0，按θ规则计算

④以alk为主元素，按单纯形法在表中进行迭代，得到新的计算表，重复地做步骤①～步骤④。直至终止。

第二章 对偶理论与灵敏度分析练习题答案

1．判断下列说法是否正确：

(1) 任何线性规划问题存在并具有惟一的对偶问题；(?)

(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(?)

(3) 设jˆx，iˆy分别为标准形式的原问题与对偶问题的可行解，*jx，*iy分别为其最优解，则恒有nnmm**jjjjiiiij1j1i1i1ˆˆcxcxbyby；(?)

(4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；(?)

(5) 已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源已完全耗尽；(?)

(6) 已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源一定有剩余；(?)

(7) 若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；(?)

(8) 应用对偶单纯形法计算时，若单纯形表中某一基变量ix0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；(?)

(9) 若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；(?)

(10) 在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。(?)

2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x4、x5为松弛变量。

XB ｂ x1 x2 x3 x4 x5

x3 5/2 0 1/2 1 1/2 0

x1 5/2 1 -1/2 0 -1/6 1/3

σj 0 -4 0 -4 -2

要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解； (3)其它条件不变时，约束条件右端项b1在何范围内变化，上述最优基不变。(4)若以单价购入第一种资源是否值得，为什么若有人愿意购买第二种资源应要价多少，为什么 答案：

线性规划的对偶理论与灵敏度分析习题

1 第二章 线性规划的对偶理论与灵敏度分析习题

1. 写出下列线性规划问题的对偶问题。

(1)无约束321321321321321,0,534332243422minxxxxxxxxxxxxxxxz (2)

0,0,837435522365max321321321321321xxxxxxxxxxxxxxxz无约束

(3)),,1;,,1(0),,1(),,1(min1111njmixnjbxmiaxxczijmijijnjiijmiijnjij

2 (4)),,,,1(0),,2,1(),,1(min1211111nnjxmmmibxammibxaxczjnjijijnjijijnjjj无约束

2. 判断下列说法是否正确，为什么?

(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；

(2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解；

( 3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；

(4)任何线性规划问题具有唯一的对偶问题。

3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。

3 2 2 0 0 0

3 CB 基 B x1 x2 x3 x4 x5 x6

0 x4 (b) 1 1 1 1 0 0

2 x5 15 (a) 1 2 0 1 0

1 x6 20 2 (c) 1 0 0 1

jjzc 0 0 2 0 0 0

 

0 x4 5/4 0 0 (d) (l) -1/4 -1/4