对偶理论和灵敏度分析

对偶问题

例题1：某养鸡场所用的混合饲料由n种天然饲料配合而成。要求在这批配合饲料中必须含有m种不同的营养成分，且第i种营养成分的含量不低于bi。已知第i种营养成分在每单位第j种天然饲料中的含量为aij，每单位第j天然饲料的价格为cj。试问，应如何对这n种饲料配方，使这批饲料的费用最小

解 设xj为第j种天然饲料的用量。

显然，aijxj即为所用第j种天然饲料中第i种营养成分的含量，1nijjjax为这批混合饲料中第i种营养成分的总含量；它不应低于bi。于是，我们得下列线性规划模型(1—1)：

1minnjjjfcx

11,,..01,,nijjijjaxbimstxjn

现设想有一个饲料加工厂欲把这m种营养成分分别制成m种营养丸。

设第i种营养丸的价格为ui(i＝1，…，m)。则养鸡场采购一个单位的第j种天然饲料，就相当于对这m种营养丸分别采购数量a1j，…amj，所化费用为1mijiiau养鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件：

11,,mijijiaucjn

另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i种营养丸就需采购bi个单位，所化费用为biui，总费用为z=∑biui

饲料加工厂面临的问题是：应把这m种营养丸的单价ui(f=1，…，m)定为多少，才能使养鸡场乐意全部采用该厂生产的营养丸来取代这批天然饲料，且使本厂在竞争中得到最大收益。为该问题建立数学模型，即得如下线性规划(1—2)： 1maxmiiizbu

11,,..01,,mijijiiaucjnstuim

我们称问题(1—2)为原有问题 (1—1)的对偶问题(记为(D))。

原有问题（P） 对偶问题（D）

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

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. 已知线性规划问题：

332211maxxcxcxcz

)5,,1(01001.2154323132221212111jxbbxxxaaxaaxaastj 用单纯形法求解得最终单纯形表如下表所示：

（a） 求232221131211,,,,,aaaaaa和21,bb

（b） 求321,,ccc

1x 2x 3x 4x 5x

3x 3/2

2x 2 1

1/2 0

1 1

0 1/2

－1 -1/2

2

jjzc -3 0 0 0 -4

答：8,4,7,5,8,2,4,1,1,2/5,2/932121231322122111cccbbaaaaaa

2. 已知矩阵A及其逆矩阵1A如下：

104020012A 11202/1004/12/11A

试根据改进单纯形法中求逆矩阵的方法原理求下述矩阵B的逆矩阵1B，已知

144210152B

答：先设144010052C  72/14/114151A

 16201002/52/1114002002/11111AC

144210152B 有 1322/111211C  26/226/1226/426/426/226/826/1126/126/913/10013/21026/110111CB

3. 已知线性规划的原问题与对偶问题分别为：