...如果原最优解不满足,如何得出新的约束条件。
发布网友
发布时间：3小时前
共1个回答
热心网友
时间：2小时前
因为线性规划往往解决原料、设备、资金、人力等资源的最优配置问题，因此了解资源在最优配置下所创造的（边际）价值即机会成本或机会收益对于成本分析、资源计划、投资计划等都有较重要的作用。此外，对偶规划也常和对资源的灵敏度分析联系在一起，对于更好地在变化环境中配置资源有一定的指导意义。
2、已知原线性规划问题如何写出其对偶问题？
（1）如果原问题是MAX问题，则其对偶问题是MIN问题。按下表可将其对偶问题写出。
原问题（L）
一
一
对
应
对偶问题（D）
max问题
min问题
有m个约束条件
有m个变量
第j个约束条件为≤关系
第j个变量≥0
第j个约束条件为≥关系
第j个变量≤0
第j个约束条件为等式关系
第j个变量无非负约束，是自由变量
第i个变量≥0
第i个约束条件为≥关系
第i个变量≤0
第i个约束条件为≤关系
第i个变量无非负约束，是自由变量
第i个约束条件为＝关系
资源向量
价值向量
价值向量
资源向量
（2） 如果原问题是MIN问题，则其对偶问题是MAX问题。按下表可将其对偶问题写出。
原问题（L）
一
一
对
应
对偶问题（D）
min问题
max问题
有m个约束条件
有m个变量
第j个约束条件为≤关系
第j个变量≤0
第j个约束条件为≥关系
第j个变量≥0
第j个约束条件为等式关系
第j个变量无非负约束，是自由变量
第i个变量≥0
第i个约束条件为≤关系
第i个变量≤0
第i个约束条件为≥关系
第i个变量无非负约束，是自由变量
第i个约束条件为＝关系
资源向量
价值向量
价值向量
资源向量
3、 如何写出下述线性规划问题的对偶模型？
min z=2x1+2x2+4x3
x1+3x2+4x3≥2
2x1+x2+3x3≤3
x1+4x2+3x3＝5
x1≥0, x2≥0, x3无约束。
答：其对偶模型如下，
max z=2y1+3y2+5y3
y1+2y2+y3≤2
3y1+y2+4y3≤2
4y1+3y2+3y3＝4
y1≥0, y2≤0, y3无约束。
4、 如何快速求出以下只有一个约束方程的线性规划的对偶问题的最优解？
Max Z=c1x1＋c1x2＋…＋cnxn
a1x1＋a1x2＋…＋anxn≤b
x1, x2,…, xn ≥0
ai, ci, b>0, i=1, 2, …, n.
答：
利用原问题与对偶问题间的相互转换关系，写出其对偶问题的模型如下，
Min f=by
a1y≥c1
a2y≥c2
……
any≥cn
y≥0
因为，y≥ , i=1, 2, …, n. 所以，其对偶问题的最优解y*= .
5、 如果原问题是如下所示的追求利润最大的生产计划问题，那么它的对偶问题中变量有何经济含义？
原问题的模型形式如下。
其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.
答：
其对偶问题即有如下形式，
对偶问题中的变量yk, k=1, 2,…, m, 可具有发现某种资源所创造的单位价值并对某种资源定价的经济含义。简言之，它反映了单位资源在某种配置、利用方式下能创造的价值，即单位资源（可能的）价值。
6、如果原问题是如下所示的追求利润最大的生产计划问题，当其中某个变量值减少一个生产单位时，所节约的各种资源的量有多少？
原问题的模型形式如下。
其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.
答：
当其中某个变量值，不妨设xj 的值减少一个生产单位时，所节约的各种资源量为 .它正好是系数矩阵A中变量xj所对应的列向量。
7、假设原问题是如下所示的追求利润最大的生产计划问题，它的对偶问题中的变量反映了单位资源可能创造的价值，那么当原问题中某个变量值减少一个生产单位时，所节约的各种资源的价值将如何借助对偶问题中的变量来表示？
原问题的模型形式如下。
.
其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.
答：
其对偶问题即有如下形式，
.
其中，对偶问题中的变量yk, k=1, 2,…, m, 反映了单位资源（所可能创造）的价值。
当原问题中某个变量值，不妨设xj 的值减少一个生产单位时，所节约的各种资源量为 , 则所节约的各种资源的价值可表示为： , 它正好是对偶问题第j个约束条件的左端项。
8、如果原问题是如下所示的追求利润最大的生产计划问题，当其中某个变量值增加一个生产单位时，所耗费的各种资源的量有多少？
原问题的模型形式如下。
其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.
答：
当其中某个变量值，不妨设xj 的值增加一个生产单位时，所耗费的各种资源量为 .它正好是系数矩阵A中变量xj所对应的列向量。
9、假设原问题是如下所示的追求利润最大的生产计划问题，它的对偶问题中的变量反映了单位资源可能创造的价值，那么当原问题中某个变量值增加一个生产单位时，所耗费的各种资源的价值将如何借助对偶问题中的变量来表示？
原问题的模型形式如下。
.
其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.
答：
其对偶问题即有如下形式，
.
其中，对偶问题中的变量yk, k=1, 2,…, m, 反映了单位资源（所可能创造）的价值。
当原问题中某个变量值，不妨设xj 的值增加一个生产单位时，所耗费的各种资源量为 , 则所耗费的各种资源的价值可表示为： , 它正好是对偶问题第j个约束条件的左端项。
10、在已求出原问题的最优单纯形表后，如何求出对偶问题的最优解？
在已求出原问题的最优单纯形表后，可确定出相应的最优基B和及其对应的CB, 然后通过公式Y*=CBB－1, 即可求出对偶问题的最优解，或甚至直接从其最终单纯形表中就能得到对偶问题的最优解。
11、如何计算影子价格？
线性规划问题的对偶问题的最优解被称为影子价格。当这个线性规划问题的最优基为B时，通过公式Y*=CBB－1, 或甚至直接从其最终单纯形表中就能得到影子价格。
12、如何通过公式Y*=CBB－1（B是线性规划问题的最优基）计算以下问题的影子价格及其对偶问题的最优解？
max z=x1＋x2＋4x3＋3x4
x1＋3x2＋8x3＋4x4≤45
2x1＋ x2＋ x3＋3x4≤40
x1, x2, x3, x4≥0
答：
a. 将原问题化为标准形
max z=x1＋x2＋4x3＋3x4
x1＋3x2＋8x3＋4x4＋x5 =45
2 x1＋ x2＋ x3＋3x4 ＋x6=40
x1, x2, x3, x4, x5, x6≥0
b. 用单纯形法求解，得到原问题的最终单纯形表为
c. 在最终单纯形表中观察影子价格
最终单纯形表中松弛变量x5, x6对应的检验数3/5, 1/5, 就是影子价格，即Y*= = (3/5, 1/5). 它也是对偶问题
min z'=45y1＋40y2
y1＋2y2≥1
3y1＋2y2≥1
8y1＋ y2≥
4y1＋3y2≥3
y1, y2≥0
的最优解。
并且最终单纯形表中松弛变量x5, x6对应的子阵 ，就是原问题最优基B的逆矩阵，即最优基B－1= .
14、通过对一个线性规划问题的最优单纯形表的观察直接得到其对偶问题的最优解（影子价格），这种观察法适宜于哪种类型的线性规划问题？
这种观察法最适宜于如下类型的线性规划问题，
.
此类线性规划问题正好在每个约束条件上添加了一个松弛变量后才化为标准形。因而，在其最优单纯形表上，直接观察那些松弛变量对应的检验数即可得到对偶问题的最优解（影子价格）。同时，原问题最优基B的逆矩阵B－1, 也可直接从最优单纯形表上松弛变量的检验数下方的那些列构成的方阵观察得出。具体的例子，请参阅本章FAQ（12）。
15、通过对一个线性规划问题的最优单纯形表的观察直接得到其对偶问题的最优解（影子价格），这种观察法的理论依据何在？
不妨设线性规划问题具有如下形式，
max z=CX
AX≤b
X≥0.
加入松弛变量向量Xs可化为如下标准形，
max z=CX
AX＋Xs=b
X, Xs≥0.
其系数矩阵 , 其中E是单位阵。
设其最优基存在且为B, 则在该基下的最优单纯形表具有如下形式，
可以看到，最优基B下松弛变量Xs对应的检验数CBB－1正好是求影子价格和对偶问题最优解的公式Y*=CBB－1（B是线性规划问题的最优基）的右端项，所以，直接观察最优单纯形表松弛变量的检验数即可得到影子价格和对偶问题的最优解。
同时，最优基B的逆矩阵也可直接在检验数正下方的子阵中观察得到。
16、影子价格的经济意义何在？
以原问题是如下所示的追求利润最大的生产计划问题为例。
.
其中，变量xj, j=1, 2,…, n, 是每种产品的产量；cj, j=1, 2,…, n, 是每种产品的单位利润；bi, i=1, 2,…, m, 是每种资源的总量，aij 表示生产第j种产品一个单位所消耗的第i 种资源的量，i=1, 2,…, m, j=1, 2,…, n.
其对偶问题即有如下形式，
.
其中，对偶问题中的变量yk, k=1, 2,…, m, 反映了单位资源（所可能创造）的价值。
我们知道这个线性规划问题的对偶问题的最优解Y*=CBB-1 （B是原问题的最优基）被称为影子价格。因此影子价格自然就反映了资源在最优配置模式下，单位资源所创造的（平均）价值。
如果我们从经济学的边际概念出发，那么可以看到影子价格实质上是资源最优配置下，关于资源的边际收益或边际成本。
（B是原问题的最优基）。
此外，从管理会计的角度看，影子价格在资源出售、出租或购入行为决策中，它也可作为机会成本或机会收益予以考虑。
最后，简单地说，影子价格反映了（稀缺）单位资源在最优配置下所创造的价值。
17、 影子价格和市场价格有何区别？
影子价格并不等同于市场价格。一般而言，在研究利用资源实现利润或收益等最大化的问题中，如果资源的影子价格低于市场价格，则这种资源被组织利用的效率比市场利用效率低，因此可以出售或出租；反之，就应该吸纳。因此，市场价格作为了一种资源吸纳、利用的基准，它与影子价格一道服务于企业或政府的资源利用策略中。
18、影子价格向量中，某种资源对应的值为0或非0值，反映了关于资源的什么信息？
当某种资源对应的值为0时，一般表示该种资源经最优配置后，还可能有剩余，因此继续吸纳这种有闲置性的资源并不会带来利润或收益的增加；当某种资源对应的值为非0时，一般表示该种资源经最优配置后，无剩余，是一种稀缺资源。
19、 对偶问题的性质，本章介绍了哪几条？
a. 对称性；
b. 弱对偶性；
c. 无界性；
d. 最优性；
e. 强对偶性；
f. 互补松弛性；
g. 原问题的检验数与对偶问题基解对应关系；
20、如何理解对偶问题的对称性质？
对偶问题的对称性质即是说原问题的对偶问题的对偶问题就是原问题本身。这个性质揭示了原问题和对偶问题的相互转换关系，并且如果把原问题的对偶问题看作另一个原问题，那么这个新的原问题的对偶问题就是过去那个旧的原问题本身。
21、 原线性规划问题的目标函数值一定不超过其对偶问题的目标函数值吗？
不一定。正确的说法应是：
a. 当原问题是MAX问题时，原问题的目标函数值一定不超过其对偶问题的目标函数值。
b. 当原问题是MIN问题时，原问题的目标函数值一定不低于其对偶问题的目标函数值。
22、当原线性规划问题是MAX问题时，为什么其目标函数值总是不超过它的对偶问题（MIN问题）的目标函数值呢？
不妨设原问题具有如下形式，
max z=cx
Ax≤b
x≥0.
则，其对偶问题可表示如下，
min f=yb
yA≥c
y≥0.
设x, y 分别是原问题和对偶问题的任一可行解，则由yA≥c, x≥0, 可得到yAx≥cx; 又因Ax≤b, y≥0, 故yAx≤yb; 所以，cx≤yAx≤yb, 即原问题的目标函数值总是不超过它的对偶问题的目标函数值。
23、当原线性规划问题是MIN问题时，为什么其目标函数值总是不低于它的对偶问题（MAX问题）的目标函数值呢？
有两种想法可供参考。
a. 其一，
(a) 首先将原线性规划问题（MIN问题）转化为MAX问题；
(b) 再将对偶问题（MAX问题）转化为MIN问题；
(c) 引用本章FAQ（22）得出合理解释。
b. 其二，
换位思考。利用“对称性”（对偶问题的对偶问题是原问题），将原问题的对偶问题看为一个新的原问题，那么旧的原问题就成为了这个新的原问题的对偶问题，直接引用本章FAQ（22）即可得出合理解释。
(24) 原问题有最优解，为什么其对偶问题就一定有最优解？
不妨设原问题具有如下标准形式，
max z=cx
Ax＝b
x≥0.
则，其对偶问题可表示如下，
min f=yb
yA≥c.
设B是原问题的最优基，x*是原问题的最优解，其最优值max z=cx*=cBB-1b.
令y*= cBB-1, 显然y*A= cBB-1A≥c, 这是因为cBB-1A－c, 正好是原问题最优基B下单纯形表的检验向量，所以必存在cBB-1A－c≥0, 即cBB-1A≥c, 也即y*A≥c. 故，y*= cBB-1,是对偶问题的可行解。
由于原问题（MAX问题）的目标函数值总是不超过它的对偶问题的目标函数值，所以，关于对偶问题的任一可行解y, 都有cx*≤yb存立。
而cx*=cBB-1b= y*b, 故，y*b≤yb, 所以，y*= cBB-1必是对偶问题的最优解。即原问题有最优解，其对偶问题也一定有最优解，且就是关于原问题的影子价格。
25、如果原问题有最优解，则原问题与其对偶问题的最优值就一定相等，为什么？
不妨设原问题具有如下标准形式，
max z=cx
Ax＝b
x≥0.
则，其对偶问题可表示如下，
min f=yb
yA≥c.
设B是原问题的最优基，x*是原问题的最优解，其最优值max z=cx*=cBB-1b.
令y*= cBB-1, 显然y*A= cBB-1A≥c, 这是因为cBB-1A－c, 正好是原问题最优基B下单纯形表的检验向量，所以必存在cBB-1A－c≥0, 即cBB-1A≥c, 也即y*A≥c. 故，y*= cBB-1,是对偶问题的可行解。
由于原问题（MAX问题）的目标函数值总是不超过它的对偶问题的目标函数值，所以，关于对偶问题的任一可行解y, 都有cx*≤yb存立。
而cx*=cBB-1b= y*b, 故，y*b≤yb, 所以，y*= cBB-1必是对偶问题的最优解。即原问题有最优解，其对偶问题也一定有最优解，且对偶问题的最优值min z= y*b =cBB-1b= cx*= max z.
因此，如果原问题有最优解，则原问题与其对偶问题的最优值就一定相等。
26、原线性规划问题的对偶问题有最优解，为什么原问题就一定有最优解？
“换位思考”，记住原问题和对偶问题是相互而言的。利用“对称性”（对偶问题的对偶问题是原问题），将对偶问题看为新的原问题，那么旧的原问题就成为了这个新的原问题的对偶问题，结合本章FAQ（24）就能得出合理的解释。
27、 如果线性规划原问题与对偶问题之中任一个有最优解，则另一个必有最优解，且二者的最优值相等，为什么？
记住原问题和对偶问题的说法是相互而言的，因此，结合本章FAQ的（24, 25, 26）进行思考，应该就能明白其中的道理。
28、如何快速求出以下只有一个约束方程的线性规划问题的最优解？
Max Z=c1x1＋c1x2＋…＋cnxn
a1x1＋a1x2＋…＋anxn≤b
x1, x2,…, xn ≥0
ai, ci, b>0, i=1, 2, …, n.
答：
a. 利用原问题与对偶问题间的相互转换关系，写出其对偶问题的模型如下，
Min f=by
a1y≥c1
a2y≥c2
……
any≥cn
y≥0
b. 因为，y≥ , i=1, 2, …, n. 所以，其对偶问题的最优解y*= .
c. 不妨设y*= , 则对偶问题目标函数最优值为by*= . 对原问题进行简单的观察，就可知道当xk= , xi=0, i=1, 2, …, n, i≠k时，这个可行解对应的原问题的目标函数值为 , 即它正好等于对偶问题的目标函数最优值。
d. 由对偶性质2（最优性）知， xk= , xi=0, i=1, 2, …, n, i≠k就是原问题的最优解。
29、只要判断出线性规划原问题与对偶问题二者之中的一个没有最优解，那么就可以下结论，另一个也没有最优解，为什么？
这是因为如果线性规划原问题与对偶问题之中任一个有最优解，则另一个必有最优解（解释见本章FAQ（27））。其逆否命题自然是“如果线性规划原问题与对偶问题二者之中有一个没有最优解，那么另一个也没有最优解”。所以，只要判断出线性规划原问题与对偶问题二者之一没有最优解，那么就可以下结论，另一个也没有最优解。
30、如何快速判断下述线性规划问题 L 无最优解？
Max Z=x1＋x3
－ x1＋x2 ＋x3 ≤2
－2x1＋x2 －x3 ≤1
x1, x2, x3 ≥0
答：
写出其对偶问题为
Min w=2y1＋y2
－y1－2y2≥1
y1＋ y2≥1
y1－ y2≥0
y1, y2≥0
显然，L对偶问题的第一个约束条件在y1, y2≥0时不可能满足，即对偶问题无解，由FAQ(29)知原问题L无最优解。
32. 结合本章FAQ（38），互补松弛定理的经济含义可解释如下。31、如果线性规划原问题（MAX问题）目标函数值没有上界，则对偶问题（MIN问题）就没有可行解，当然就没有最优解，为什么？
还可以吧？
