运筹学线性规划习题(有参考解答)

《运筹学》前8周课程参考习题

一、考虑下列线性规划模型

某企业生产甲、乙、丙三类特种钢材，每吨甲，乙，丙钢材需要加入金属

求使得总利润最高的生产方案。使用《运筹学》教学软件，得到结果如下：

a．请根据上面求解线性规划问题输出表格说明：最优解，最优值，对偶价格是什么？他们的关系及含义是什么？

b．解释松弛 / 剩余变量的含义。如果原料A、B、C、D可以用相同的价格购买补充，你将优先考虑哪一种，为什么？购买价格在什么范围内，你可以接受？

c．当钢材甲的利润由12千元／吨变为10千元／吨的同时，产品乙的利润由9千元／吨变为9.5千元／吨，这时原来的最优方案变不变？为什么？

d．当其它金属原料的供应量不变时，金属原料C的供应量在什么范围内可以保证对偶价格不变？试解释其含义。 参考解答：

a．最优解：( 87.273，19.091,0 )T ； 最优值：1219.091；

对偶价格：( 1.273，0,0,1.545 )T；

对偶价格分量表示相应资源增加（或减少）1个单位，最优值增加（或减少）的数量。

b．解释松弛 / 剩余变量的含义：实际使用的资源与资源限额的差； 如果原料A、B、C、D可以用相同的价格购买补充，将优先考虑D，因为D的影子价格最高。D的购买价格在1.54千元以下时可以接受。 c．根据百分之一百法则：

12 109.5 9

0.268204 0.02381 0.292014 100%

12 4.54330 9

原来的最优方案不变。

d．当其它金属原料的供应量不变时，金属原料C的供应量大于等于201.818kg时，可以保证对偶价格不变。其含义是：在这个范围内，原料C的增加或减少都不会应影响最优利润，因为C在这个范围内对偶价格为0。

二、某企业生产三种仪器A、B、C，所需要的加工时间分别为10小时、8小时和13小时，每月的正常加工时间为 600 小时；生产成本分别为12万元、15万元和10万元，每月可支付生产成本的资金为700万元；各产品可获得的利润均为成本的10％。根据调查分析，市场对仪器A、B、C的需求分别为30台、20台和18台。决策者考虑：

首先，要尽可能达到产品数量的需求；其次，要充分发挥企业的加工能力；第三，要求尽可能获得较多的利润；最后，要求加班时间最少。问应如何安排生产？(建模，不求解)

参考解答

设x1, x2, x3 分别为仪器A、B、C的产量

minPd( d d )Pd Pd Pd1123243544

x1 d s.t.1 d1 30

x d d222 20

x3 d 3 d 3 18

10x1 8x2 13x3 d 4d 4600

1.2x 1.5x 1.0x d d 1235584

(1.2 30 1.5 20 1.0 18 84)

12x1 15x2 10x3 700

xi 0,d ,d i 1,2,3;j 1,2,3,4，5jj 0,

三、某企业生产甲、乙、丙三种产品，其每单位所消耗工时分别为1.6、2.0、2.5小时，每单位所需原料A分别为24、20、12 kg，所需原料B分别为14、10、18 kg。生产线每月正常工作时间为 240 小时，原料A、B的总供应量限制为 2400kg和1500kg 。生产一个甲、乙、丙产品各可获利润525、678、812元，试分别建立以下两种情况下的数学模型，不需要计算。

a．由于每单位丙产品的生产会产生 5kg 副产品丁，这些副产品丁一部分可以销售，利润为300元/kg，剩下的会造成污染，每kg需要排污费200元。副产品丁的需求量为每月不超过150kg。应如何确定生产计划，可使总利润最大？ b．工厂考虑到产品丙有污染，决定不生产丙而准备在另外的三种产品W、Q、G中选择1种或2种来进行生产，它们所消耗工时、所需原料A、B及利润如下表：

应如何确定生产计划，可使总利润最大？ 参考解答：

a．设x1, x2, x3 分别为产品甲、乙、丙的产量，x4, x5 分别为副产品丁销售和未销售的数量 模型：

x6x78 8x 2x00x maxz 5215 23143 5200

s.t.1.16x 22.x0 2x. 52403 24x1 20x2 1x224003

14x1 10x2 1x815003

x4 x5 5x3 x4 150

x1,x2,x3,x4,x 50

b．设x1, x2, x3, x4, x5 分别为产品甲、乙、W 、Q、G的产量，y1, y2, y3 为

0-1变量，分别表示产品W、Q、G生产（取值1）和不生产（取值0） 模型：

max s.t.

z 52x15 1.x16 24x1 2x02 14x1 1x02

6x27 81x9 31x4 3

x3 50x x34420x1 5x 1514x1 74

x2 50

5

380240

2x2. 0x1 .4x x 51.7341.5

24001 500

x3 My1,x4 My,2x 5My,31 y1 y2 y3 2x1,x2,x,3x,4x 50,

y,y1,y2 03or1