运筹学课程设计要求及题目

《运筹学》课程设计要求及题目

要求：

1. 分组：每组由6名同学组成，共8组 —— 各位同学与学习委员协商分组； 各组组长为：

2. 题目：每组可在给定的题目中任选一题，也可以通过网络查询自行设置题目； 3. 提交形式 —— 提交课程设计报告（含纸质和电子版），提交时需答辩 电子版发至：[email protected] 4. 课程设计报告格式

字体及行间距：小四号宋体1.5倍行距 (表格中的数据为5号宋体) 提交的课程设计报告内容由以下部分组成： 一、 问题描述 二、 问题分析 三、 假设及符号说明 四、 建立模型 五、 软件求解结果 六、 结果分析 5. 封面格式

《运筹学》课程设计

设计题目：设计时间：所在院系：专业年级：成员姓名：

某厂排气管车间生产计划的优化分析 2012.7.16 - 2012.7.20 工程技术学院工业工程系 2010级工业工程 李红霞（2010311301） 王娇(2010311304)

供选题目

【案例C.1】某厂排气管车间生产计划的优化分析

1．问题的提出

排气管作为发动机的重要部件之一，极大地影响发动机的性能。某发动机厂排气管车间长期以来，只生产一种四缸及一种六缸发动机的排气管。由于其产量一直徘徊不前，致使投资较大的排气管生产线，一直处于吃不饱状态，造成资源的大量浪费，全车间设备开动率不足50%。

为了充分发挥车间的潜力，该车间在厂部的大力协助下主动出击，一方面争取到了工厂自行开发的特殊机型排气管生产权，另一方面瞄准国际市场以较低的价格和较高的质量赢得了世界两大著名汽车公司—CUMMINS和FORD的信任，成为其8种型号排气管最具竞争实力的潜在供应商。如果这8种排气管首批出口进入国际市场畅销的话，后续订单将会成倍增长，而且两大公司有可能逐步减少其它公司的订单，将其它型号排气管全部转移到该车间生产。

针对这种状况，该车间组织工程技术人员对8种排气管的产品图纸进行了评审，进行了工艺设计和开发（编排工艺流程图、进行PFMEA分析和编制控制计划），进行样品试制，同时对现生产能力和成本进行了认真细致的核算和预测工作。如何调整当前的生产计划，是否增加设备或改造生产线，其它类型新产品需要多长时间才能投入生产等一系列问题尚缺乏科学的、定量的依据。而目前厂部和车间最关心的资源问题，主要是加工设备的生产能力。一位工商管理硕士（MBA)毕业的厂部管理人员马上想到，这是一个合理利用有限资源，如何制定生产计划使产出最大的优化问题，理论上可以用线性规划方法解决。 2．生产概况及有关资料 （1）车间概况

该车间按两班制生产，每班8小时，标准工作日为22天。车间现有员工30名，其中生产工人27人，每月安排职工政治学习及业务培训时间为4小时，进行文明生产等非生产性工作每月平均2小时/人·月，排气管工废按产量的1%计算，料废按2%计算。 车间生产工人工作时间按44小时/人·周（每月4周）进行考核。 （2）生产状况

该车间排气管生产为10道工序，分别在不同的10类机床上进行加工，每种排气管所占用的设备时间如表C-1所示。各种排气管的成本构成如表C-2所示，

目前，由于市场不景气，排气管生产的上工序即铸造厂产能富裕，只要资金到位该厂可准时、足量供货，而且品种可以保证。而出口排气管外商的的资金可以及时到位，并且许诺如果需要可预付50%以上的预付款，只不过对某些产品提出了特殊要求，即第一种、第七种排气管月产量均不能低于10000，第三种不能低于5000/月，第六种排气管产量不高于60000/月，第二和第四种排气管配对使用，但由于第二种排气管使用中易损，故每月必须多生产3000根。因此原材料来源和资金不足是增加生产的制约因素。制约该车间排气管产量的主要是设备计划外停工及基本生产工人工时，即设备与人力资源。根据以往经验，各设备加工能力见表C-3。

表C-1 8种排气管设备消耗时间（单位：台时/1000件）

表C-2 8种排气管成本构成表（单位：元/根）

注：表中售价为含税价。

表C-3 设备加工能力一览表

根据以上资料，请你完成下列3和4两项工作。 3．制定利润最大的生产计划 （1）建立线性规划数学模型 （2）用WinQSB软件求解

（3）写出各种产品月生产量及月总利润。 4．结果分析

（1）分析各种资源的利用情况，根据线性规划得到的结果，如何重新调整资源

（2）利用影子价格分析各资源对利润的边际贡献，分析哪些是影响增加利润的关键设备 （3）如果企业现有一订单，各种排气管的需要量是：15000，5000，5000，3000，15000，60000,10000,60000（根）。正常时间内1个月能否完成任务，如果不能完成，哪些资源需要加班多少时间，假定加班不额外增加成本。

（4）对现有资源和生产能力进行分析，提出你对排气管车间整个计划的看法和建议。

【案例C.2】配料问题

某饲料公司生产肉用种鸡配合饲料，每千克饲料所需营养质量要求如表C－4所示。

表

公司计划使用的原料有玉米，小麦，麦麸，米糠，豆饼，菜子饼，鱼粉，槐叶粉，DL-蛋氨酸，骨粉，碳酸钙和食盐等12种原料。各原料的营养成分含量及价格见表C－5。

表C－5

公司根据原料来源，还要求1吨配合饲料中原料的含量为：玉米不低于400 kg，小麦不低于100 kg，麦麸不低于100 kg，米糠不超过150 kg，豆饼不超过100 kg,菜子饼不低于30 kg，鱼粉不低于50 kg，槐叶粉不低于30 kg， DL-蛋氨酸，骨粉，碳酸钙适量。

（1）按照肉用种鸡公司标准，求1千克配合饲料中每种原料各配多少成本最低，建立数学模型并求解。

（2）按照肉用种鸡国家标准，求1千克配合饲料中每种原料各配多少成本最低。

（3）公司采购了一批花生饼,单价是0.6元/kg，代谢能到有机磷的含量分别为（2.4,38,120,0,0.92,0.15,0.17）,求肉用种鸡成本最低的配料方案。 （4）求产蛋鸡的最优饲料配方方案。

（5）公司考虑到未来鱼粉、骨粉和碳酸钙将要涨价，米糠将要降价，价格变化率都是原价的r %试对两种产品配方方案进行分析。

说明：以上5个问题独立求解和分析，如在问题（3）中只加花生饼，其它方案则不加花生饼。

【案例C.3】证券营业网点设置问题

证券公司提出下一年发展目标是：在全国范围内建立不超过12家营业网点。 1．公司为此拨出专款2.2亿元人民币用于网点建设。

2．为使网点布局更为科学合理，公司决定：一类地区网点不少于3家，二类地区网点不少于4家，三类地区网点暂不多于5家。

3．网点的建设不仅要考虑布局的合理性，而且应该有利于提升公司的市场份额，为此，公司提出，待12家网点均投入运营后，其市场份额应不低于10%。

4．为保证网点筹建的顺利进行，公司审慎地从现有各部门中抽调出业务骨干40人用于筹建，分配方案为：一类地区每家网点4人，二类地区每家网点3人，三类地区每家网点2人。 5．依据证券行业管理部门提供的有关数据，结合公司的市场调研，在全国选取20个主要城市并进行分类，每个网点的平均投资额（bj）、年平均利润（cj）及交易量占全国市场平均份额（rj）如表C－6所示。

试根据以上条件进行分析，公司下一年应选择哪些城市进行网点建设，使年度利润总额最大。

表C－6

【案例C.4】工程建设与财政平衡决策问题

阅读下列案例，完成计算和分析。

某市政府为改善其基础设施，在近3年内要着手如下5项工程的建设，按重要性排序的工程建设项目名称及造价如表C－7所示。

该市政府的财政收入主要来自国家财政拨款、地方税收和公共事业收费。3年内该三项总收入分别估计为e1，e2和e3。除此之外就靠向银行贷款和发行债券，3年中可贷款的上限为U11、U12和U13，，年利率为g；可发行债券的上限为U21、U22和U23，年利率为f。银行还贷款期限为1年(假定贷款在年初付出)，债券则由下年起每年按一定比例(r)归还部分债主的本金。市政府应如何作出3年的投资决策。

设x1t(t=1,2,3)为第t年向银行贷款数，x2t(t=1,2,3)为第t年发行债券数，yit(i=1,2,„,5;t=1,2,3)为项目i在第t年的完工率（投资比例），见表C－8。

表 C－8

除上述变量外，为了写出平衡式，引进第1年的起始财政平衡变量z0和每年末的财 政平衡变量z1、z2和z3。

（1）决策变量：为了列出目标规划决策模型，决策变量如表C－8所示。

(2)约束和目标：注意问题中有的目标(例如历年财政平衡)实际上是硬约束，其中不含偏差变量，因此引入松弛变量si(i=1,2,„,7)作等式的平衡。 （3）财政平衡约束条件：

① 变量的上限限制和财政平衡目标：变量包括决策变量、财政平衡变量和保证财政平衡的人工变量。表C－8所列变量都有上界限制的，把这些有上界约束的变量写成目标形式，其中只须引进负偏差变量njt。对平衡变量应使z0为零，使zl，z2，z3为正值，故除z0外其它平衡变量都引进了正偏差变量，而且把使z0为零和使其它平衡变量为正作“硬约束”的规定。因此有

xjtnjtUjt，j1,2；t1,2,3

3

贷款、债券平衡约束



yitdit1，i1,2,,5；t1,2,3各项目每年完工率平衡约束

y

t1

it

di1，i1,2,,5

完工率平衡约束第1年初财政平衡约束3年财政平衡约束

z0s40

zks4kd5k0,k1,2,3



式中：d5k为正偏差变量，s4+k是松弛变量(等价于负偏差变量)，z0是第1年年初的可用资金，

假设z0＝0，则约束z0－s4=0可以去掉。zk是第k年年末剩余（k＋1年年初可用）资金，所有变量非负。

②根据财政平衡的意义，可列出3年中每年的财政平衡约束条件，即

(该年银行贷款)+(该年发行债券)+(该年财政收入)—(该年各项工程拨款)—(该年银行还款)—(该年债券还款)—(该年银行贷款付息)—(该年债券付息)+(起始平衡)—(最终平衡)＝0。则有 第一年：x11x21e1

by

ii1

5

i1

fx21z0z1s10

第二年：

x12x22e2bi(yi2yi1)x11rx21gx11

i1

5

f(1f)(x21rx21)fx22z1z2s20

第三年：

x13x23e3bi(yi3yi2)x12rx22gx12

i1

5

f(1f)2(x212rx21)f(1f)(x22rx22)fx23z2z3s30

（4）目标函数：对问题目标函数的要求有如下几点：

①硬约束为1级目标，以首先保证各年财政平衡，这可使这些约束条件的相应松弛变量的和为最小；

②力图尽量获得银行贷款和发行债券，以解决工程建设的资金问题； ③保证头两项工程的优先完成(按重点顺序加权)； ④按重点顺序加权，抓紧后三项工程的建设； ⑤争取每个项目在3年内都完工； ⑥使各年最终财政平衡变量为最小。 因此，目标函数可列出：



minp1skp2[n1tn2t]p3[2dd2t]



1t5

k1

t1

t1

t1

t1

'

p4[3d3t2d4td5t]p5dip6d5k

t1

t1

t1

i1

k1

3

3

3

3

7

3

3

3

3

整理得到目标规划数学模型



minp1skp2[n1tn2t]p3[2dd2t]



1t5

k1

t1

t1

t1

t1



p4[3d3t2d4td5t]p5dip6d5k

t1

t1

t1

i1

k1

3

3

3

3

73333

xjtnjtUjt，j1,2；t1,2,3



yitdit1，i1,2,,5；t1,2,33

y

t15

it

d1，i1,2,,5



i

zks3kd5k0,k1,2,3

by

ii1

i15

x11(1f)x21z1s1e1

5

biyi1biyi2(1g)x11x12

i1

i1

[r(1r)f(1f)]x21(1f)x22z1z2s2e2

biyi2biyi3(1g)x12x13[r(12r)f(1f)2]x21

i1

i1

5

5

[r(1r)f(1f)]x22(1f)x23z2z3s3e3所有变量非负

要求：

（1）给定具体数据：b1＝700，b2＝500，b3＝800，b4＝400，b5＝680；e1＝700，e2＝900，e3＝1200，U11＝300，U12＝400，U13＝450，U21＝300，U22＝350，U23＝350，f＝0.055，g＝0.05，r=0.2。用软件求满意解；

（2）对结果进行分析，列出3年详细的项目投资计划、资金分配表和平衡表，资金是否有缺口，写出分析报告。

【案例C.5】综合生产计划编制

汽车制造厂现有一个6个月的产品生产任务，产品需要在车加工车间生产，每件产品需要5小时加工，有关资料如下。

（1）车间现有200名工人，每天正常工作8小时，每小时的工资8元。

（2）如果正常时间不能完成任务可以加班生产，每小时的工资10元，每位工人每月加班时间不得超过60小时。

（3）工厂可以提供原材料外协加工，每月最多1000件，每件产品的加工费第1、2个月为85元，第3～6月份为80元。

（4）可以延期交货，但6个月的总生产任务必须完成。每件产品延期一个月必须支付延期费用8元。

（5）已知第1月月初有300件库存产品，为了预防产品需求量的波动，工厂决定每月月末最少要库存一定数量的产品（安全库存量），每月最大库存量不超过800件，每件产品一个月的储存费为1.2元。

（6）如果当月工人不够可以雇佣新工人，对雇佣工人除了支付工资外还要额外支付技术培训

费800元，如果当月工人有剩余，工厂必须支付每人每月基本生活费400元。 （7）设备正常生产和加班生产的折旧费均为每小时6元。

（8）产品月末交货。6个月的需求量、每月正常生产天数、安全存量及每件产品其它费用如表C－9所示。

工厂希望制定6个月总成本最低的生产计划。 要求：

（1）详细安排每个月正常时间生产、加班时间生产、外协生产、延期交货及月末库存的产品数量。

（2）分别画出每月正常时间生产量的的柱状统计图和百分比饼图。 （3）求出每月生产工人数、富余工人数及雇佣工人数并画出饼图。 （4）求出总成本及各分项成本。

（5）画出总成本及各分项成本的柱状图和百分比饼图。

提示：（1）案例不需要建立模型，调用WinQSB软件的子程序Aggregate Planning即可完成。建议在建立新问题之前打开系统自带例题aplp.app文件，观察问题的数据表格内容，点击菜单栏Edit→Problem Specification，查看对话框的选项及详细输入格式。

（2）正常生产能力需要将工作日转换成小时，产品成本等于工人的工资加折旧费。 （3）本案例的总成本等于3139097元。

【案例C.6】购车问题

Anly大学毕业后刚取得汽车驾驶执照，对SKY05型小汽车情有独钟。准备第1年年初买一辆使用了3年的SKY05型二手车，价格为7.12万元。1年后可以继续使用该车，也可以卖掉购买同一品牌的新车，不再购买二手车。通过市场调查和预测，得到有关资料。

（1）该车第1年初的价格为10万元，以后逐年降价，第2年到第5年的的降价幅度分别为4％、5％、7%、5%。第t年的价格记为Pt，t＝1，2，„。

（2）购新车必须支付10%的各项税费。购置费用记为Ct，Ct＝1.1Pt。

1.3

（3）该车第t年的维护费用Mt是使用年限t的函数，Mt＝0.4t。

（4）汽车年折旧率为15％，汽车残值为：Bt＝0.85 tPt。

无论第5年末更新或不更新，将汽车残值从总成本中减去，等价于将车卖掉。Anly如何制定一个5年的购车方案使5年的总成本最低(不计其它成本)。

【案例C.7】房屋拆迁还建问题 1．问题的提出

近年来，随着我国市场经济的不断发展和城市建设步伐的进一步加快，城市规模不断扩大，房地产业飞速发展。房地产业的发展意味着需要大量的征收征用城市及其周边的土地，牵涉到对土地上的房屋及其附属物的拆迁与还建问题。目前，对被拆迁房屋的偿还政策有两种，即产权调换和货币偿还。

某房地产公司在武汉市汉正街开发商品住宅，需拆迁285户民用住宅。经房地产公司与

住户（拆迁户）协商，达成以下主要偿还协议。

（1）被拆迁房屋按产权调换政策偿还。新建房屋建筑完毕后房地产公司将免费给每户被

拆迁居民分配一套住房，分配的住房面积不小于要补偿的房屋面积。

（2）如果被拆迁房屋的面积大于新建房屋中最大面积，则可分成两套或三套等，由居民

自己决定房屋套数和每套的房屋面积（各套房屋面积之和为原本的补偿面积）。

（3）如果偿还新建房屋面积大于被拆迁房屋的面积，多偿还的面积按成本价出售给住户。

（4）其它。如楼层要求等因素本案例省略。

2．有关资料

被拆迁的285户住宅的拆迁建筑面积、使用面积已知，这里只讨论偿还建筑面积，如表C

－9所示。

表C－9 应偿还拆迁户建筑面积表(单位：m2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 拆迁号

1~15 44.62 44.62 34.4 36.27 22.51 23.02 35.26 47.65 40.79 24.09 25.37 18.46 19.63 37.91 30.29 16～30

31～45

46～60

61～75

76～90 34.98 24.38 31.15 31.96 38.37 33.91 23.66 48.99 26.04 45.78 36.35 34.41 54.17 27.89 56.57 18.7 18.88 28.8 17.97 31.16 34.49 27.01 25.01 32.52 30.97 33.77 28.84 57.79 26.21 29.8 26.44 18.3 43.35 22.53 62.98 33.96 27.87 27.32 43.56 42.47 26.56 33.46 32.44 25.44 34.74 28.37 19.65 42.6 35.93 26.74 34.48 19.52 41.58 36.7 33.35 27.74 26.8 29.42 20.69 16.09 68.1 44.43 29.56 31.4 36.75 38.77 44.24 41.3 20.51 19.15 27.88 32.31 42.15 24.39 29.17

24 23.39 40.14 39.5 24.17 20.52 27.21 31.6

33 18.86 28.8 18.77 90～105 34.43 26.33 33.43 35.24 34.03 29.88 33.33 38.87 17.43 64.83 29.14 37.88 29.95 39.96 17.89 106～120 19.55 28.85 19.03 15.49 28.8 39.52 33.35 121～135 29.29 34.5 30.28 25.13 31.29 51.66 31.02 46.45 30.15 35.97 20.95 54.41 28.87 40.07 19.17 136～150 41.32 29.41 31.79 19.5 34.41 46.45 25.89 58.58 34.04 53.16 51.31

151～165 35.12 28.37 41.02 39.07 36.56 32.55 46.12 27.47 44.97 46.66 30.84 50.02 30.52 38.5 27.97 166～180 39.36 38.06 34.15 44.21 55.1 24.48 37.17 39.07 29.94 31.55 32.06 28.07 30.88 30.32 25.15 181～195 24.48 36.78 33.87 19.2 28.12 44.71 33.17 38.93 20.95 31.71 35.32 29.48 41.65 30.86 48.58 196～210 52.12 42.14 25.35 44.62 26.78 30.88 25.7 33.92 25.12 31.37 37.06 44.16 49.94 35.96 31.55 211～225 61.88 49.49 25.21 36.44 30.66 37.78 18.22 25.59 44.9 34.92 49.34 29.56 31.92 40.79 25.47 225～240 149.98 60.37 25.18 85.96 60.37 44.64 54.17 61.89 19.53 24.66 27.4 75.17 64.93 47.83 29.33 241～255 67.26 43.56 63.28 69.27 84.36 38.95 78.04 162.04 71.28 20.13 60.83 62.4 38.46 12.9 73.15 255～270 155.69 72.59 71.58 100.42 94.85 108.97 41.29 68.4 41.26 32.94 60.55 181.54 113.68 110.14

271～285 40.07 29.3 26.34 26.34 42.01 28.33 27.9 56.74 39.6 39.6 39.6 68 72 333.96 35.53 93.2

房地产公司根据表C－9需要偿还的面积分布，设计了17种面积的户型，每一种户型有

25套，见表C－10。

2户数为原则（实际中由住户确定），例如第258户的面积有108.97m2，平均拆分成两户，又如第248户的面积有162.04m2，同样平均拆分成两户。

3．设计偿还方案

由于实际偿还面积一般要大于等于应偿还面积，多偿还面积越大房地产公司损失越大（按成本价出售），房地产公司的目标是实际偿还面积尽可能接近应偿还面积。

请设计一个偿还方案，哪一个拆迁户应分配哪一种户型的住房，使房地产公司总损失最小。

【案例C.8】小组课程实践

在您所居住的城市选择一条公共汽车路线，完成下列课程实践并写出研究报告。

（1）记录每个站点一天或多天乘客到达车站的时间、人数；

（2）记录每个站点一天或多天公共汽车到站时间和上车人数；

（3）对记录的数据进行统计分析，求出每个站点顾客到达时间分布和公共汽车的服务时间分布；

（4）求出每个站点的有关排队系统指标；

（5）给定等待成本和服务成本，分别按路线和站点设计最优的车辆台数。

（6）如果按时间分段设计，又怎样合理安排车辆台数。