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

运筹学线性规划习题有

参考解答

YUKI was compiled on the morning of December 16, 2020

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

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

某企业生产甲、乙、丙三类特种钢材，每吨甲，乙，丙钢材需要加入金属材料A，B，C，D的数量，原料限制及每吨甲，乙，丙钢材的利润如下表： 金属A 金属B 金属C 金属D 利润 （kg／（kg／（kg／（kg／（千元／吨） 吨） 吨） 吨） 吨） 钢材甲 钢材乙 钢材丙 原料限制（kg） 7 1 8 630 5 8 1 600 1 6 2 708 2 5 5 270 12 9 10 求使得总利润最高的生产方案。使用《运筹学》教学软件，得到结果如下：

OPTIMAL SOLUTION Objective Function Value = Variable Value Reduced Costs -------------- --------------- ------------------ X1 X2 X3 Constraint Slack/Surplus Dual Prices -------------- --------------- ------------------ 1 2 3 4 OBJECTIVE COEFFICIENT RANGES Variable Lower Limit Current Value Upper Limit ------------ --------------- --------------- --------------- X1 X2 X3 No Lower Limit RIGHT HAND SIDE RANGES Constraint Lower Limit Current Value Upper Limit ------------ --------------- --------------- --------------- 1 2 No Upper Limit 3 No Upper Limit 4

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

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

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

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

 参考解答：

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

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

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

b．解释松弛 / 剩余变量的含义：实际使用的资源与资源限额的差； 如果原料A、B、C、D可以用相同的价格购买补充，将优先考虑D，因为D的影子价格最高。D的购买价格在千元以下时可以接受。 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的产量

minP1(d1d2d3)P2d4P3d5P4d4tx1d1d130s..xdd20222x3d3d31810x18x213x3d4d4600 

1.2x1.5x1.0xdd8412355(1.2301.5201.01884)12x115x210x3700xi0,d,di1,2,3;j1,2,3,4，5jj0,

三、某企业生产甲、乙、丙三种产品，其每单位所消耗工时分别为、、小时，每单位所需原料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及利润如下表： W Q G 消耗工时 (小时/单位) 所需原料A (kg/单位) 19 15 11 所需原料B （kg／单位） 14 17 20 利润 (元/单位) 350 420 380 应如何确定生产计划，可使总利润最大？

 参考解答：

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

maxs..t 

z525x1678x2812x3300x4200x51.6x12.0x22.5x324024x120x212x3240014x110x218x31500x4x55x3x4150x1,x2,x3,x4,x50

b．设x1, x2, x3, x4, x5 分别为产品甲、乙、W 、Q、G的产量，y1, y2, y3 为0-1变量，分别表示产品W、Q、G生产（取值1）和不生产（取值0） 模型：

maxs..t z525x1678x2350x3420x4380x51.6x12.0x21.4x31.5x41.7x524024x120x219x315x411x5240014x110x214x317x420x51500x3My1,x4My2,x5My3,1y1y2y32x1,x2,x3,x4,x50,y1,y2,y30or1