当前位置：文档之家 › 《运筹学》 第三章线性规划对偶理论与灵敏度分析习题及 答案

《运筹学》 第三章线性规划对偶理论与灵敏度分析习题及 答案

  • 格式：doc
  • 大小：263.00 KB
  • 文档页数：8

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

一、思考题

1．对偶问题和对偶变量的经济意义是什么？

2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？

3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？

4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检

验数之间的关系？

5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？

6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0knx，其经济意

义是什么？

7．在线性规划的最优单纯形表中，松弛变量knx的检验数0kn（标准形为

求最小值），其经济意义是什么？

8．将ijjibca,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解

将会出现什么变化？有多少种不同情况？如何去处理？

二、判断下列说法是否正确

1．任何线性规划问题都存在且有唯一的对偶问题。

2．对偶问题的对偶问题一定是原问题。

3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。

4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定

有最优解。

5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。

6．已知在线性规划的对偶问题的最优解中，对偶变量0iy，说明在最优生产计

划中，第i种资源已经完全用尽。

7．已知在线性规划的对偶问题的最优解中，对偶变量0iy，说明在最优生产计

划中，第i种资源一定还有剩余。

8．对于ijjibca,,来说，每一个都有有限的变化范围，当其改变超出了这个范围

之后，线性规划的最优解就会发生变化。

9．若某种资源的影子价格为u，则在其它资源数量不变的情况下，该资源增加k

个单位，相应的目标函数值增加 uk。

10．应用对偶单纯形法计算时，若单纯形表中某一基变量0ix，且ix所在行的

所有元素都大于或等于零，则其对偶问题具有无界解。

三、写出下列线性规划的对偶问题

（1）32123maxxxxZ （2）4321322maxxxxxz

0,,92372452321321321321xxxxxxxxxxxx ； 无约束43214313214321,,0,313212xxxxxxxxxxxxxx ；

（3）32132minxxxz （4）212minxxxz 无约束321321321321,0,1042742523xxxxxxxxxxxx ； 无约束321321321321,0,3453532722xxxxxxxxxxxx ；

（5）321347maxxxxz （6）321345minxxxz

无约束23132321221,0,030351546324624xxxxxxxxxxx ； 无约束1323232131,0,306415458872xxxxxxxxxx 。

四、用对偶单纯形法求解下列线性规划问题

（1）32123minxxxZ （2）321422maxxxxz

0,,3463213231321xxxxxxxxxx ； 0,,5643732532321321321321xxxxxxxxxxxx ；

（３）43211216812minxxxxz （４）321425minxxxz

0,,,34222424321421321xxxxxxxxxx ； 0,,12536723321321421xxxxxxxxx ；

五、对下列问题求最优解、相应的影子价格及保持最优解不变时jc与ib的变化范围。

（１）1213maxxxxz （２）4211935089maxxxxzx

0,,323222321321321xxxxxxxxx ； 0,,,6418410234321434321xxxxxxxxxx ；

（３）32134maxxxxz （４）432181026maxxxxxz

0,,622422321221321xxxxxxxxx ； 0,,,103242582332044654321432143214321xxxxxxxxxxxxxxxx ．

六、已知下表（表3—1）为求解某线性规划问题的最终单纯形表，表中54,xx为松弛变量，问题的约束为  形式

表 3—1

1x 2x 3x 4x 5x 3x 5/2 0 1/2 1 1/2 ０

1x 5/2 1 －1/2 0 －1/6 1/3

jjzc 0 －４ 0 －４ －２

（１）写出原线性规划问题；

（２）写出原问题的对偶问题；

（３）直接由表３—１写出对偶问题的最优解。

七、某厂利用原料Ａ、Ｂ生产甲、乙、丙三种产品，已知生产单位产品所需原料数、单件利润及有关数据如表1—4所示，分别回答下列问题：

表 ３—２

甲 乙 丙 原料拥有量

A

B 6

3 3

4 5

5 45

30

单件利润 4 1 5

（1）建立线性规划模型，求该厂获利最大的生产计划；

（2）若产品乙、丙的单件利润不变，产品甲的利润在什么范围变化，上述最优解不变？

（3）若有一种新产品丁，其原料消耗定额：Ａ为３单位，Ｂ为２单位，单件利润为２．５单位．问该种产品是否值得安排生产，并求新的最优计划；

（4）若原材料Ａ市场紧缺，除拥有量外一时无法购进，而原材料Ｂ如数量不足可去市场购买，单价为０．５，问该厂应否购买，以够劲多少为宜？

（5）由于某种原因该厂决定暂停甲产品的生产，试重新确定该厂的最优生产计划．

八、某厂生产甲、乙、丙三种产品，分别经过Ａ、Ｂ、Ｃ三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润见表３—４。

表 ３——４

甲 乙 丙 设备能力（台时）

Ａ

Ｂ

Ｃ １

１０

２ １

４

２ １

５

６ １００

６００

３００

单位产品利润（元） １０ ６ ４

（１）建立线性规划模型，求该厂获利最大的生产计划；

（２）产品丙每件的利润增加到多大时才值得安排生产？如产品丙每件的利润增加到

50/6 ，求最优生产计划。

（４）产品甲的利润在多大范围内变化时，原最优计划保持不变？

（５）设备A的能力如为100+10 ，确定保持原最优基不变的 的变化范围。

（６）如有一种新产品丁，加工一件需设备A、B、C的台时各为1、4、3小时，预期每件的利润为8元，是否值得安排生产？

（７）如合同规定该厂至少生产10件产品丙，试确定最优计划的变化。

《运筹学》

第三章线性规划对偶理论与灵敏度分析习题解答

二．解：（1）√ （2）√（3）X（4）√(5) √（6）√（7）X（8）X（9）X（10）X

三、（1）321975minyyyw （2）321312minyyyw 0,,12222334321321321321yyyyyyyyyyyy ； 无约束2313132121321,0,0133222yyyyyyyyyyyyy；

（3）3211075maxyyyw （4）321356maxyyyw

无约束321321321321,0,0342224123yyyyyyyyyyyy； 0,02421531322321321321321yyyyyyyyyyyy无约束，

（5）321301524minyyyw （6）32130158maxyyyz

无约束32132132121,0,033464562734yyyyyyyyyyy ； 无约束3213213221,0,03647445582yyyyyyyyyy。

四、解：（1）用对偶单纯形法求得的最终单纯形表如下：

表 ３—１

1x 2x 3x 4x 5x 6x

０

－３

－２ 4x

1x

2x －１

４

３ ０

１

０ ０

０

１ １

－１

－１ １

０

０ １

－１

０ １

０

－１

jjzc ０ ０ －６ ０ －３ －２

由于基变量4x所在行的jia值全为非负，故问题无可行解。

（２）最优解为 TXz]0,2.1,2.0[,8.2；

（３）最优解为 TXz]0,0,1,5.0[,14；

（４）最优解为 TXz]0,2,34[,332；

五、解：用单纯形法求得的最终单纯形表分别见表 ３— ２(1) , 2(2) , 2(3) , 2(4) ．

（1）

表 ３—２（１）

jc 1 1 3 0 0 BC BX b 1x 2x 3x 4x 5x

３ 3x １ １ 0．5 １ ０.5 0

０ 5x ２ ２ 1．5 ０ －0.5 1

jz ３ ３ 1．5 ３ 1.5 0

jjzc －２ －0.5 ０ －１.5 0

由此表可以看出，资源1的影子价格为1.5 ，资源2的影子价格为0 。

且 3212,5.1,3ccc ；

211,60bb。

(2)

表 3 — 2（2）

jc 9 8 50 19 0 0

BC BX b 1x 2x 3x 4x 5x 6x

19 4x 2 2 4/3 0 １ 2/3 －5/3

50 3x 1 －０.5 －1/3 1 ０ －1/6 2/3

jz ３ 1３ 26/3 50 19 13/3 5/3

jjzc －4 －2/3 ０ 0 －13/3 －5/3

合集下载

运筹学试题答案解析

运筹学试题答案解析

运筹学试题答案解析

⼀、单项选择题

线性规划的基本假设条件不包括以下哪⼀项？

A. ⽬标函数和约束条件都是线性的

B. 所有变量的取值范围都是离散的

C. ⽬标函数和约束条件都是确定的

答案：B

解析：线性规划的基本假设条件包括⽬标函数和约束条件都是线性的，所有变量的取

值范围都是连续的，并且⽬标函数和约束条件都是确定的。因此，选项B“所有变量的取值范围都是离散的

以下哪项不是单纯形法求解线性规划问题的特点？

A. 从⼀个初始可⾏解开始

B. 通过迭代的⽅式逐步逼近最优解

C. 每次迭代都保证解是最优的

答案：C

解析：单纯形法是⼀种求解线性规划问题的算法，它从⼀个初始可⾏解开始，通过迭

代的⽅式逐步逼近最优解。但单纯形法并不能保证每次迭代都达到最优解，⽽是逐步

改进解的质量，直到达到最优解。因此，选项C“每次迭代都保证解是最优的”不是单纯形法的特点。

对偶问题与原问题的关系描述错误的是？

A. 它们共享相同的技术系数矩阵

B. ⽬标函数和约束条件互换

C. 对偶问题的最优解⼀定等于原问题的最优解

答案：C

解析：对偶问题是指⼀个线性规划问题与其对应的另⼀个线性规划问题之间的关系。

它们共享相同的技术系数矩阵，但⽬标函数和约束条件互换。然⽽，对偶问题的最优

解并不⼀定等于原问题的最优解，只有在满⾜⼀定条件下（如原问题和对偶问题都有

最优解且满⾜强对偶性定理），两者的最优解才相等。因此，选项C的描述是错误的。

⼆、多项选择题

以下哪些属于线性规划问题的基本要素？

A. ⽬标函数

B. 约束条件

C. 决策变量

D. 可⾏域

答案：ABCD

解析：线性规划问题的基本要素包括⽬标函数、约束条件、决策变量和可⾏域。⽬标

函数是决策者希望最⼤化的⽬标或最⼩化的成本；约束条件是对决策变量的限制条

件；决策变量是决策者可以控制的变量；可⾏域是所有满⾜约束条件的决策变量的集

合。

灵敏度分析在运筹学中的作⽤包括哪些？

A. 评估参数变化对最优解的影响

B. 帮助决策者了解哪些参数对结果影响最⼤

规划数学(运筹学)第三版课后习题答案-习-题-1(1)

规划数学(运筹学)第三版课后习题答案-习-题-1(1)

规划数学(运筹学)第三版课后习题答案-习-题-1(1)

1 / 10 习 题 1

1 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。

0xx42x4x66x4x3x2xminz)a(21212121，

0x,x124x3x 2x2x2x3xmaxz)b(21212121

8x310x512010x6xxxmaxz)c(212121

0x,x23x2x2x2x6x5xmaxz)d(21212121

答案： (a)唯一解3*,)5.0,75.0(*zXT); (b)无可行解;

(c)唯一解16*,)6,10(*zXT); (d)无界解）

2 用单纯形法求解下列线性规划问题。

0x,x82x5x94x3x5x10xmaxz)a(21212121

0x,x5xx242x6x155xx2xmaxz)b(212121221

答案：

(a)唯一解5.17*,)5.1,1(*zXT)，对偶问题5.17*,)786.1,357.0(*wYT;

(b)唯一解5.8*,)5.1,5.3(*zXT），5.8*,)5.0,25.0,0(*wYT

3 用大M法和两阶段法求解下列线性规划问题，并指出属于哪一类解。

0xxx0x2x2x2x6xxx2xx2xmaxz)a(3,2,13231321321

0x,x,x62x3x82x4xxx3x2xminz)b(32121321321

答案：

(a)无界解；(b)唯一解8*,)0,8.1,8.0(*zXT)，对偶问题8*,)0,1(*wYT

《运筹学》课堂作业及相应答案解析

《运筹学》课堂作业及相应答案解析

第一部分 绪 论

第二部分 线性规划与单纯形法

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

(a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的；

(b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大；

(c)线性规划问题的每一个基解对应可行域的一个顶点；

(d)如线性规划问题存在可行域,则可行域一定包含坐标的原点；

(e)对取值无约束的变量xi,通常令其中,在用单纯形法求得的最优解中有可能同时出现

(f)用单纯形法求解标准型的线性规划问题时,与对应的变量都可以被选作换入变量；

(g)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负；

(h)单纯形法计算中,选取最大正检验数δk对应的变量xk作为换入变量,将使目标函数值得到最快的增长；

(i)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果；

(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；

(k)若x1,x2分别是某一线性规划问题的最优解,则

也是该线性规

划问题的最优解,其中λ1,λ2可以为任意正的实数；

(1)线性规划用两阶段法求解时,第一阶段的目标函数通常写为Xai为人工变量),但也可写为,只要所有ki均为大于零的常数；

(m)对一个有n个变量、m个约束的标准型的线性规划问题,其可行域的顶点恰好 为个；

(n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解；

(o)线性规划问题的可行解如为最优解,则该可行解一定是基可行解；

(p)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解；

(q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优； (r)将线性规划约束条件的“≤”号及“≥”号变换成“＝”号,将使问题的最优目标函数值得到改善；

规划数学(运筹学)第三版课后习题答案习题1(1)

规划数学(运筹学)第三版课后习题答案习题1(1)

Word格式

完美整理 习 题 1

1 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。

0xx42x4x66x4x3x2xminz)a(21212121，

0x,x124x3x 2x2x2x3xmaxz)b(21212121

8x310x512010x6xxxmaxz)c(212121

0x,x23x2x2x2x6x5xmaxz)d(21212121

答案： (a)唯一解3*,)5.0,75.0(*zXT); (b)无可行解;

(c)唯一解16*,)6,10(*zXT); (d)无界解）

2 用单纯形法求解下列线性规划问题。

0x,x82x5x94x3x5x10xmaxz)a(21212121

0x,x5xx242x6x155xx2xmaxz)b(212121221

答案：

(a)唯一解5.17*,)5.1,1(*zXT)，对偶问题5.17*,)786.1,357.0(*wYT; (b)唯一解5.8*,)5.1,5.3(*zXT），5.8*,)5.0,25.0,0(*wYT

3 用大M法和两阶段法求解下列线性规划问题，并指出属于哪一类解。

0xxx0x2x2x2x6xxx2xx2xmaxz)a(3,2,13231321321

0x,x,x62x3x82x4xxx3x2xminz)b(32121321321

答案：

(a)无界解；(b)唯一解8*,)0,8.1,8.0(*zXT)，对偶问题8*,)0,1(*wYT Word格式