第2章 对偶问题

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流第2章 对偶问题.精品文档.第二章 对偶问题一、选择1. 如果原问题有最优解，则其对偶问题也一定具有最优解，且有（A ）。A maxZ=minW B maxZ<minW C maxZ>minW D maxZ与minW无关2. 影子价格是（C ）A、对偶可行解 B、对偶基本可行解 C、对偶最优解 D 无可行解3原问题有可行解，其对偶问题有非可行解，则目标函数值（ B） A、最优 B、 C、> D无可行解4. 影子价格是一种（C ） A、实际价格 B、市场价格 C、边际价格 D产品价格5. 资源的市场价格是已知数，相对比较稳定，

2、而它的影子价格则有赖于（c ），是未知数 A 市场的定价 B 买卖的多少 C 资源的利用情况 D 购买力6. 如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）（D）。A 唯一最优解B 无穷多最优解 C 无界解 D 无可行解7. 影子价格是一种边际价格，实际上又是一种（A ）。A机会成本B实际成本 C 市场价格 D 产品价格9.如果是原问题的可行解，是其对偶问题的可行解，则恒有（ A）A B C D 无法确定10. 如果是原问题的可行解，是其对偶问题的可行解，且有（ B），则是原问题的最优解，是其对偶问题的最优解A B C D 11.如果，其符合（D ）定理A 强对偶性B弱对偶性C最优性

3、D 互补松弛性12.如果有，其符合（D ）定理A 强对偶性B弱对偶性C最优性D 互补松弛性13. 如果，其符合（D ）定理A 强对偶性B弱对偶性C最优性D 互补松弛性14. 如果有，其符合（D ）定理A 强对偶性B弱对偶性C最优性D 互补松弛性15.在单纯形法中，最终单纯形表，原问题的变量对应着对偶问题的（ A）A 松弛变量B剩余变量C变量D 最优解16. 在单纯形法中，最终单纯形表，原问题的松弛变量对应着对偶问题的（C）A 松弛变量B剩余变量C变量D 最优解17. 在单纯形法中，最终单纯形表中，对偶问题的最优解由（B ）的值组成。A B - C D 018. 灵敏度分析 是指对系统或事物因周

4、围条件变化显示出来的（A）的分析。A敏感程度B 特性C 解D 状态19.在敏感性分析中，将参数变化反应到最终单纯形表中，原问题与对偶问题都是可行解，则（A ）A此解仍为问题最优解B用单纯形法继续计算C用对偶单纯形法继续计算D用人工变量法继续计算20.灵敏度分析中，增加一个变量在实际问题中反映为增加（ B）A一道工序B一种产品C一个约束条件D一个目标函数21.原问题中求目标函数极大化，对偶问题中为求目标函数（A ）A 极小化B 极大化C 极值D 不能确定22.原问题中约束条件个数等于对偶问题中（B ）A 约束条件个数 B 变量个数C 价值系数个数 D 技术系数个数23.原问题中变量个数等于对偶问

5、题中（A ）A 约束条件个数 B 变量个数C 价值系数个数 D 技术系数个数24.原问题中约束条件符号为小于等于，对偶问题中约束条件符号为（C ）A 等于 B 小于等于C 大于等于 D 大于25.原问题目标函数的系数是其对偶问题的（D ）A 目标函数的系数 B 价值系数C 技术系数 D 约束条件右端项26.原问题约束条件的右端项则是其对偶问题（）A 目标函数的系数 B 价值系数C 技术系数 D 约束条件右端项27.原问题某个约束条件为等式，那么对偶问题相应的变量为（D ）A 等于 B 小于等于C 大于等于 D 自由28.原问题与对偶问题互为对偶，称为（ C）A 弱对偶性 B 强对偶性 C 对称

6、性 D 互补松弛性29. 用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，得到对偶问题的一个（ A）。A基解 B 最优解 C 可行解 D 非可行解30.资源的影子价格是买主（B ）A最高出价 B 最低出价 C 期望价格 D 市场价格。二、填空1. 如果对偶问题具有（无界解），则其原问题无可行解。2. .如果是原问题的可行解，是其对偶问题的可行解，则恒有，则此定理称为（弱对偶性）3. 如果是原问题的可行解，是其对偶问题的可行解，且有，则是原问题的最优解，是其对偶问题的最优解，此定理称为（最优性）4. 如果原问题有最优解，则其对偶问题也一定具有最优解，且有 maxZ=minW ，此

7、定理称为（强对偶性）。5.在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。此定理为（互补松弛性定理）6.在线性规划问题的对偶问题中， 是生产某种产品所消耗各项资源的影子价格的总和，即（ 产品的隐含成本）7.对线性规划问题的求解是确定资源的（最优分配方案），而对于对偶问题的求解则是确定对资源的（恰当估价）。8. 10. 灵敏度分析中，增加（一个变量）在实际问题中反映为增加一种新的产品。11. 灵敏度分析中，增加（一个约束条件）在实际问题中反映为增加一道工序。12.在实际问题中需要研究当参数值连续变

8、化时，问题的最优解如何随参数值变化而变化，这样的问题需要用到（参数线性规划）理论。13.原问题的(变量的个数)对应着对偶问题的约束条件的个数14.原问题变量的不等式的符号，正对应着对偶问题的（约束条件 ）不等式的符号。15.原问题约束条件的(右端项)，对应着对偶问题目标函数中变量的系数。16.原问题的约束条件的不等式符号，（反 ）对应着对偶问题变量的不等式符号。17.原问题的变量为无约束，对应着对偶问题的约束条件是（ 等式）18.19.在对偶问题的基本性质中，强对偶性应用（夹逼定理）进行推导。20.灵敏度分析中，如果市场条件发生变化，那么反映到线性规划模型中是（）发生变化。21.对偶约束的经济

9、解释就是（产品机会成本）。22.用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在（检验数行 ）得到对偶问题的一个基解。23.原问题的影子价格是当该资源增加1单位时引起的（总收入的增量 ）。24. 原问题的影子价格是卖主的（内控价格）。25.影子价格反映了资源的稀缺性，影子价格越高，则（越稀缺）。26.在利润最大化的生产计划中，安排生产的产品机会成本（等于）利润。27.互补松弛性定理中，如果则（ ）28.互补松弛性定理中，如果，则（）29. 互补松弛性定理中，如果则（ ）30. 互补松弛性定理中，如果，则()三、判断1.任何线性规划问题存在并具有唯一的对偶问题。（正确）2.对偶

10、问题的对偶问题一定是原问题。（正确）3.若某种资源的影子价格等于k，在其他条件不变的情况下，当某种资源增加5个单位时，相应的目标函数值将增大5k。（不正确）4. 在线性规划问题中，对偶变量yi的意义代表一个单位第i种资源的估价。（正确 ）5.对偶单纯形法必须首先化为对偶形式才能进行（不正确）6. 对偶问题的性质中，无界性指如果原问题具有无界解，则其对偶问题无可行解（正确）7.影子价格在市场上是已知的。（不正确）8.机会成本是一个实际的成本。（不正确）9. 在对偶问题的互补松弛性定理中，有，表明生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零。(正确)10. 在对偶问题的互补松弛性

11、定理中，有，表明当资源的影子价格不为零时，表明该种资源生产中已经耗费完毕。（正确）11.对偶单纯形法使用的前提是有一个基，其对应的基本解满足，单纯形表的检验数行全部非正。（不正确）12. 对偶单纯形法使用的前提是有一个基，其对应的基本解满足，单纯形表的变量取值可有负数。（不正确）13. 对偶单纯形法使用的前提是有一个基，其对应的基本解满足，单纯形表的检验数行全部非正；变量取值可有负数。 （正确）14.对偶单纯形法的计算时，先确定换入基的变量。（不正确）15.对偶单纯形法的计算时，直到时，计算结束。（正确）16. 对偶单纯形法的计算时，若，时，则原问题无可行解，对偶问题也为无可行解。（不正确）1

12、7. 对偶单纯形法的计算时，若，时，则原问题无可行解，对偶问题也为无界解。（正确）18.灵敏度分析是研究使问题的最优解或最优基保持不变时的参数值变化范围。（正确）19在互为的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值。（不正确）20.21. 机会成本表示减少一件产品所节省的资源可以增加的利润。（正确）22.机会成本在经济学上是一种即虚即实的一种成本。（ 正确）23.机会成本是指一笔投资在专注于某一方面后所失去的在另外其他方面的投资获利机会。（正确）24.在纯市场经济条件下，当市场价格低于影子价格的时候，可以卖出这种资源。（不

13、正确）25. 在纯市场经济条件下，当市场价格高于影子价格的时候，可以买进这种资源。（不正确）26.在线性规划问题中，当市场条件发生变化时，值就会变化。（不正确）27. 在线性规划问题中，值则是根据资源投入后能产生多大经济效果来决定的一种决策选择。（正确）28.在灵敏度分析中，当原问题和对偶问题都为非可行解时，用两阶段方法，编制新的单纯形表重新计算。（不正确）29. 在求解对偶问题的最优解的时候，可以通过原问题的单纯形表的终表求得。（正确）30.31.影子价格是对偶规划解的一个经济学解释，它能够告诉决策者，在现有生产情况下，哪种资源最为关键？企业以什么样的价格买进或卖出某种资源才是合适的。（正确

14、）四、名词解释1.弱对偶性：如果是原问题的可行解，是其对偶问题的可行解，则恒有，则此定理称为弱对偶性。2.最优性：如果是原问题的可行解，是其对偶问题的可行解，且有，则是原问题的最优解，是其对偶问题的最优解，此定理称为最优性。3.无界性：如果原问题（对偶问题）具有（无界解），则其对偶问题（原问题）无可行解。4.强对偶性：如果原问题有最优解，则其对偶问题也一定具有最优解，且有 maxZ=minW ，此定理称为强对偶性。5.对偶定理：如果原问题有最优解，则其对偶问题也一定具有最优解，且有 maxZ=minW ，此定理称为对偶定理。6.互补松弛性：在线性规划问题的最优解中，如果对应某一约束条件的对偶变

15、量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。此定理为互补松弛性定理。7.基解的互补性：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有。8.影子价格：在单纯形法的每步迭代中有目标函数， 的意义代表对一个单位第i种资源的估价。这种估计不是资源的市场价格，而是根据资源在生产中做出的贡献而作的估价，为区别起见，称为影子价格。9. 机会成本是由于

16、资源的稀缺性，考虑了某种用途，就失去了其他被使用而创造价值的机会，在所有这些其他可能被利用的机会中，把能获取最大价值作为项目方案使用这种资源的成本，称为机会成本。10.产品的隐含成本：从影子价格的含义上来考察单纯形法的计算。有，其中是生产一个单位该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。11.对偶单纯形法：则是将单纯形法应用于对偶问题的计算，基本思想是保持对偶问题为可行解（这时一般原问题为非可行解）的基础上，通过迭代，减小目标函数，当原问题也达到可行解时，即得到了目标函数的最优值。12. 灵敏度分析：是指对系统或事物因周围条件变化显示出来的敏感程度的分析。13.参数线性规划：在

17、实际的线性规划问题中，往往需要研究当参数值连续变化时，问题的最优解如何随参数值的变化而变化，此类问题为参数线性规划。14. 边际价格是指在其他条件不变的前提下，厂商增加一单位要素投入所增加的产品的价值四、简答1.线性规划的原问题与对偶问题的表达式 (一般形式)(1) 原问题max z = (i = 1,m)s.t.(j = 1,n)(2) 对偶问题(j = 1,n)s.t.(i = 1,m)2.对偶单纯形法的基本思想是什么？答：对偶单纯形法基本思想是保持对偶问题为可行解（这时一般原问题为非可行解）的基础上，通过迭代，减小目标函数，当原问题也达到可行解时，即得到了目标函数的最优值。3.影子价格的

18、经济含义？答：影子价格是对现有资源实现最大效益时的一种估价；影子价格表明资源增加对总效益产生的影响。影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。这可以通过灵敏度分析讨论。4.对偶问题的基本性质有哪些？1）弱对偶性2）最优性3）无界性4）强对偶性5）互补松弛性6）线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w5.根据对偶问题的性质，请填写下

19、表：目标函数值原问题可行解非可行解对偶问题可行解 非可行解 答：目标函数值原问题可行解非可行解对偶问题可行解最优非可行解6.对偶单纯形法的步骤？答：1）将原线性规划问题改写为目标函数极大化，并化为标准形式2）列出单纯形表3）确定换出基的变量4）确定换入基的变量5）用换入变量替换换出变量得到一个新的基。用新的基再检查是否所有。如果是，找到了问题的最优解，如果否，回到第3步再重复计算。7.灵敏度分析的步骤是什么？1）将参数的改变计算反映到最终单纯形表上来：2）检查原问题是否仍为可行解；3）检查对偶是否仍为可行解；4）按下表所列情况得出结论和决定继续计算的步骤。原问题对偶问题结论或继续计算的步骤可行

20、解可行解仍为问题最优解可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算8.敏感性分析中的变化，的变化，增加一个变量的分析，增加一个约束条件的分析在实际问题中分别代表的什么含义。答：的变化代表的是价值系数的变化；的变化代表的是资源的限制的变化；增加一个变量的分析相当于增加一种新的产品；增加一个约束条件的分析相当于在实际问题中增加一道工序。9. 根据原问题和对偶问题的对应关系，填写出下表。 原问题（对偶问题）对偶问题（原问题）目标函数目标函数原问题（对偶问题）对偶问题（原问题）目标函数目标函数目标函数中变量的

21、系数约束条件右端项约束条件右端项目标函数中变量的系数 10.影子价格在管理决策中的作用?答：1）影子价格不等于市场价格。若影子价格大于市场价格，则应买进该资源；若影子价格小于市场价格，则应卖出该资源。2）影子价格反映了资源的稀缺性，影子价格越高，则越稀缺。11.单纯形法中各个检验数的经济意义是什么？答：从影子价格的含义上来考察单纯形法的计算。有，其中代表第j种产品的产值，是生产一个单位该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。当产品产量大于隐含成本时，表明生产该项产品有利，可在计划中安排，否则用这些资源来生产别的产品更为有利，就不在生产计划中安排。这就是单纯形法中各个检验数的经

22、济意义。12.参数线性规划的解法要求？答:当问题中有多个参数变化时，应使目标函数是的线性函数。因此有多个值变动时，可表为，式中可以是任意一个实数；同样当有多个值变动时，也应有关系式，式中可以是任意一个实数。13. 灵敏度分析包括哪几种参数改变的情况。答：1）分析的变化范围2）分析变化的范围3）增加一个变量的分析4）增加一个约束条件的分析。14. 线性规划的原问题与对偶问题的表达式 (矩阵)原问题:对偶问题：15.对偶问题中的互补松弛性定理的实际经济含义？答：在对偶问题的互补松弛性定理中有如果，则，如果则，这表明生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不

23、为零时，表明该种资源在生产中已经耗费完毕。16.对偶单纯形法应用的前提是什么？答：有一个基，其对应的基本解满足1）单纯形表的检验数行全部非正（对偶可行）2）变量取值可有负数（非可行解）（注）通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。17.灵敏度分析中由参数的变化而引起的最终单纯形表上有关数字的变化公式是什么？答：；18.灵敏度分析分析的变化范围的步骤。答：目标函数中系数的变化仅仅影响到检验数（）的变化，所以将的变化直接反映到最终单纯形表中，继续进行计算。19. 灵敏度分析分析的变化范围的步骤。答：的变化反映到最终单纯形表上只引起基变量列数字变化。1）按公式，算出，将其

24、加到基变量列的数字上。2）由于其对偶问题仍为可行解，故只需检查原问题是否仍为可行解，再按照下表进行计算。原问题对偶问题结论或继续计算的步骤可行解可行解仍为问题最优解非可行解可行解用对偶单纯形法继续迭代求最优解20.灵敏度分析中，增加一个变量的分析的步骤。答：1）计算；2）计算；3）若,只需将和的值直接反映到最终单纯形表中，原最优解不变；若>0，则按单纯形表继续迭代计算。21.灵敏度分析中，增加一个约束条件的分析的步骤。答：先将原来问题的最优解变量取值代入这个新增的约束条件中，如满足，说明新增约束未起到限制作用，原最优解不变。否则，将新增约束直接反映到最终表中，再进行分析。22. 对偶单纯

25、形法的特点答：1)与单纯形法不同，对偶单纯形法是先确定出基变量，然后才能确定进基变量，这不同正是对偶关系所致。2）初始基解可以是不可行的，只要检验数符合最优性条件，就可以进行基的转换，不需要增添人工变量，这样就可使计算大为简化。3）如果原规划的决策变量很少，但约束条件却较多时，可转用对偶单纯形表求解其对偶规划，这样可以简化计算。4）灵敏度分析中，许多运算用对偶单纯形法求解比较方便，否则会使问题变得复杂；但是在一般情况下，大多数对称型的线性规划及其对偶规划，都较难找到一个检验数全部非负的初始基解。因而在求一般线性规划时，较少单独使用对偶单纯形法。23. 线性参数规划，求解的主要步骤是什么。答：1

26、）对含参数t的参数规划，先令t=0，用单纯形法求出最优解。2）将t直接反映到最优单纯形表中，并用灵敏度分析的方法进行分析。3）当t连续变化时，观察b列和检验数行各元素的变化。如果b列出现负分量，则按对偶单纯形法消除不可行性；如果检验数出现负的，则用单纯形法进行迭代。4）在迭代后的单纯形表上，令t继续变化，重复步骤（3），直到b不出现负值，检验数不出现负值为止。五、计算1.将原问题化成对偶问题解：2.设原问题如下，写出其对偶问题。解：对偶问题写出下面线性规划的对偶问题.解：3.用对偶单纯行法求解解： 大M法求解解： 引入人工变量、，线性规划问题为：X=(5/2,5/2,5/2,0,0,0);Z=

27、15用对偶单纯形法求解线性规划问题s. t.表2-4原问题的解转变成了可行解，且对应的对偶问题的解仍可行（即检验数全为非正），因此原问题的最优解为2.影子价格： 下述线性规划问题：已知最优解中的基变量为且已知要求根据上述信息确定三种资源各自的影子价格。解： 三种资源的影子价格分别为 六.综合题1.灵敏度分析已知线性规划问题；用单纯形法求解最终的单纯形法表如下：2611110010031110-3-1-20试说明分别发生下列变化时，新的最优解是什么？（a） 目标函数变为（b） 约束条件右端由变为（c） 增添一个新的约束解：（a）CBXb261111060100311101-1-202103010

28、0最优解（b）CBXb2-1100231111007031110-3-1-20原问题最优解不变 （c）CBXb2611110001003111002-10200-1261111000100311100-80-1-3-1010-3-1-200 32210/312/302/301/3022/308/304/31-1/318/301/311/30-1/30-0-0-2.灵敏度分析已知线性规划问题用单纯形法求解时得到的最终单纯形表如下表所示X1X2X3X4X5X1361604-1X360-11-11/20-90-11-1/2当约束条件变为时，问题的最优解如何变化。解：等价于2x3应为x3，因此约束条件

29、只是右端项发生变化，将变化反映到最终单纯形表中，并用对偶单纯形法迭代得到新的最优解为，maxZ=368CBXbX1X2X3X4X56361604-11360-11-11/2CBXbX1X2X3X4X56761604-113-40-11-11/20-90-11-1/2-9-11-52106-2-4401-11-1/2已知线性规划问题 对偶变量 s. t. 其对偶问题的最优解为，试应用对偶问题的性质，求原问题的最优解。解 原问题的对偶问题为 s. t. 将代入，知约束条件、为严格不等式，由互补松弛定理，得。 因为，则原问题的两个约束条件应取等式，即联立求解得，故原问题的最优解为3.已知线性规划问题

30、：其最优解为（a）求k的值（b）写出并求其对偶问题的最优解解：写出其对偶问题如下由及互补松弛性质得：因为x1=-5<0,则，即又因为Z=2*(-5)-0+2*(-1)=-12=W求方程组解得已知线性规划问题用单纯形表求得最终表如下所示3/21-5/14-25/14试用灵敏度分析的方法分别判断：（a) 目标函数系数或分别在什么范围内变动，上述最优解不变。（b) 约束条件右端项，当一个保持不变，另一个在什么范围内变化，上述最优基保持不变。解：（a）（b）分析似变量。七证明题1.已知线性规划问题如下，试应用对偶理论证明上述线性规划问题无最优解。证明：该问题存在可行解，如X=（0,0,0）；又上述问题的对偶问题为：由第一个约束条件知对偶问题无可行解，由此可知其原问题无最优解。2.已知线性规划问题如