我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 约束条件 >

运筹学灵敏度分析添加一个约束条件时如果原最优解不满足如何得出

归档日期:07-23       文本归类:约束条件      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  因为线性规划往往解决原料、设备、资金、人力等资源的最优配置问题,因此了解资源在最优配置下所创造的(边际)价值即机会成本或机会收益对于成本分析、资源计划、投资计划等都有较重要的作用。此外,对偶规划也常和对资源的灵敏度分析联系在一起,对于更好地在变化环境中配置资源有一定的指导意义。

  (1)如果原问题是MAX问题,则其对偶问题是MIN问题。按下表可将其对偶问题写出。

  (2) 如果原问题是MIN问题,则其对偶问题是MAX问题。按下表可将其对偶问题写出。

  5、 如果原问题是如下所示的追求利润最大的生产计划问题,那么它的对偶问题中变量有何经济含义?

  对偶问题中的变量yk, k=1, 2,…, m, 可具有发现某种资源所创造的单位价值并对某种资源定价的经济含义。简言之,它反映了单位资源在某种配置、利用方式下能创造的价值,即单位资源(可能的)价值。

  6、如果原问题是如下所示的追求利润最大的生产计划问题,当其中某个变量值减少一个生产单位时,所节约的各种资源的量有多少?

  当其中某个变量值,不妨设xj 的值减少一个生产单位时,所节约的各种资源量为 .它正好是系数矩阵A中变量xj所对应的列向量。

  7、假设原问题是如下所示的追求利润最大的生产计划问题,它的对偶问题中的变量反映了单位资源可能创造的价值,那么当原问题中某个变量值减少一个生产单位时,所节约的各种资源的价值将如何借助对偶问题中的变量来表示?

  其中,对偶问题中的变量yk, k=1, 2,…, m, 反映了单位资源(所可能创造)的价值。

  当原问题中某个变量值,不妨设xj 的值减少一个生产单位时,所节约的各种资源量为 , 则所节约的各种资源的价值可表示为: , 它正好是对偶问题第j个约束条件的左端项。

  8、如果原问题是如下所示的追求利润最大的生产计划问题,当其中某个变量值增加一个生产单位时,所耗费的各种资源的量有多少?

  当其中某个变量值,不妨设xj 的值增加一个生产单位时,所耗费的各种资源量为 .它正好是系数矩阵A中变量xj所对应的列向量。

  9、假设原问题是如下所示的追求利润最大的生产计划问题,它的对偶问题中的变量反映了单位资源可能创造的价值,那么当原问题中某个变量值增加一个生产单位时,所耗费的各种资源的价值将如何借助对偶问题中的变量来表示?

  其中,对偶问题中的变量yk, k=1, 2,…, m, 反映了单位资源(所可能创造)的价值。

  当原问题中某个变量值,不妨设xj 的值增加一个生产单位时,所耗费的各种资源量为 , 则所耗费的各种资源的价值可表示为: , 它正好是对偶问题第j个约束条件的左端项。

  在已求出原问题的最优单纯形表后,可确定出相应的最优基B和及其对应的CB, 然后通过公式Y*=CBB-1, 即可求出对偶问题的最优解,或甚至直接从其最终单纯形表中就能得到对偶问题的最优解。

  线性规划问题的对偶问题的最优解被称为影子价格。当这个线性规划问题的最优基为B时,通过公式Y*=CBB-1, 或甚至直接从其最终单纯形表中就能得到影子价格。

  12、如何通过公式Y*=CBB-1(B是线性规划问题的最优基)计算以下问题的影子价格及其对偶问题的最优解?

  并且最终单纯形表中松弛变量x5, x6对应的子阵 ,就是原问题最优基B的逆矩阵,即最优基B-1= .

  14、通过对一个线性规划问题的最优单纯形表的观察直接得到其对偶问题的最优解(影子价格),这种观察法适宜于哪种类型的线性规划问题?

  此类线性规划问题正好在每个约束条件上添加了一个松弛变量后才化为标准形。因而,在其最优单纯形表上,直接观察那些松弛变量对应的检验数即可得到对偶问题的最优解(影子价格)。同时,原问题最优基B的逆矩阵B-1, 也可直接从最优单纯形表上松弛变量的检验数下方的那些列构成的方阵观察得出。具体的例子,请参阅本章FAQ(12)。

  15、通过对一个线性规划问题的最优单纯形表的观察直接得到其对偶问题的最优解(影子价格),这种观察法的理论依据何在?

  可以看到,最优基B下松弛变量Xs对应的检验数CBB-1正好是求影子价格和对偶问题最优解的公式Y*=CBB-1(B是线性规划问题的最优基)的右端项,所以,直接观察最优单纯形表松弛变量的检验数即可得到影子价格和对偶问题的最优解。

  其中,对偶问题中的变量yk, k=1, 2,…, m, 反映了单位资源(所可能创造)的价值。

  我们知道这个线性规划问题的对偶问题的最优解Y*=CBB-1 (B是原问题的最优基)被称为影子价格。因此影子价格自然就反映了资源在最优配置模式下,单位资源所创造的(平均)价值。

  如果我们从经济学的边际概念出发,那么可以看到影子价格实质上是资源最优配置下,关于资源的边际收益或边际成本。

  此外,从管理会计的角度看,影子价格在资源出售、出租或购入行为决策中,它也可作为机会成本或机会收益予以考虑。

  最后,简单地说,影子价格反映了(稀缺)单位资源在最优配置下所创造的价值。

  影子价格并不等同于市场价格。一般而言,在研究利用资源实现利润或收益等最大化的问题中,如果资源的影子价格低于市场价格,则这种资源被组织利用的效率比市场利用效率低,因此可以出售或出租;反之,就应该吸纳。因此,市场价格作为了一种资源吸纳、利用的基准,它与影子价格一道服务于企业或政府的资源利用策略中。

  18、影子价格向量中,某种资源对应的值为0或非0值,反映了关于资源的什么信息?

  当某种资源对应的值为0时,一般表示该种资源经最优配置后,还可能有剩余,因此继续吸纳这种有闲置性的资源并不会带来利润或收益的增加;当某种资源对应的值为非0时,一般表示该种资源经最优配置后,无剩余,是一种稀缺资源。

  对偶问题的对称性质即是说原问题的对偶问题的对偶问题就是原问题本身。这个性质揭示了原问题和对偶问题的相互转换关系,并且如果把原问题的对偶问题看作另一个原问题,那么这个新的原问题的对偶问题就是过去那个旧的原问题本身。

  a. 当原问题是MAX问题时,原问题的目标函数值一定不超过其对偶问题的目标函数值。

  b. 当原问题是MIN问题时,原问题的目标函数值一定不低于其对偶问题的目标函数值。

  22、当原线性规划问题是MAX问题时,为什么其目标函数值总是不超过它的对偶问题(MIN问题)的目标函数值呢?

  设x, y 分别是原问题和对偶问题的任一可行解,则由yA≥c, x≥0, 可得到yAx≥cx; 又因Ax≤b, y≥0, 故yAx≤yb; 所以,cx≤yAx≤yb, 即原问题的目标函数值总是不超过它的对偶问题的目标函数值。

  23、当原线性规划问题是MIN问题时,为什么其目标函数值总是不低于它的对偶问题(MAX问题)的目标函数值呢?

  换位思考。利用“对称性”(对偶问题的对偶问题是原问题),将原问题的对偶问题看为一个新的原问题,那么旧的原问题就成为了这个新的原问题的对偶问题,直接引用本章FAQ(22)即可得出合理解释。

  设B是原问题的最优基,x*是原问题的最优解,其最优值max z=cx*=cBB-1b.

  由于原问题(MAX问题)的目标函数值总是不超过它的对偶问题的目标函数值,所以,关于对偶问题的任一可行解y, 都有cx*≤yb存立。

  而cx*=cBB-1b= y*b, 故,y*b≤yb, 所以,y*= cBB-1必是对偶问题的最优解。即原问题有最优解,其对偶问题也一定有最优解,且就是关于原问题的影子价格。

  25、如果原问题有最优解,则原问题与其对偶问题的最优值就一定相等,为什么?

  设B是原问题的最优基,x*是原问题的最优解,其最优值max z=cx*=cBB-1b.

  由于原问题(MAX问题)的目标函数值总是不超过它的对偶问题的目标函数值,所以,关于对偶问题的任一可行解y, 都有cx*≤yb存立。

  “换位思考”,记住原问题和对偶问题是相互而言的。利用“对称性”(对偶问题的对偶问题是原问题),将对偶问题看为新的原问题,那么旧的原问题就成为了这个新的原问题的对偶问题,结合本章FAQ(24)就能得出合理的解释。

  27、 如果线性规划原问题与对偶问题之中任一个有最优解,则另一个必有最优解,且二者的最优值相等,为什么?

  记住原问题和对偶问题的说法是相互而言的,因此,结合本章FAQ的(24, 25, 26)进行思考,应该就能明白其中的道理。

  c. 不妨设y*= , 则对偶问题目标函数最优值为by*= . 对原问题进行简单的观察,就可知道当xk= , xi=0, i=1, 2, …, n, i≠k时,这个可行解对应的原问题的目标函数值为 , 即它正好等于对偶问题的目标函数最优值。

  29、只要判断出线性规划原问题与对偶问题二者之中的一个没有最优解,那么就可以下结论,另一个也没有最优解,为什么?

  这是因为如果线性规划原问题与对偶问题之中任一个有最优解,则另一个必有最优解(解释见本章FAQ(27))。其逆否命题自然是“如果线性规划原问题与对偶问题二者之中有一个没有最优解,那么另一个也没有最优解”。所以,只要判断出线性规划原问题与对偶问题二者之一没有最优解,那么就可以下结论,另一个也没有最优解。

  显然,L对偶问题的第一个约束条件在y1, y2≥0时不可能满足,即对偶问题无解,由FAQ(29)知原问题L无最优解。

  32. 结合本章FAQ(38),互补松弛定理的经济含义可解释如下。31、如果线性规划原问题(MAX问题)目标函数值没有上界,则对偶问题(MIN问题)就没有可行解,当然就没有最优解,为什么?

本文链接:http://ksbuilders1.com/yueshutiaojian/331.html