2017年南京工业大学运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。
【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。
（2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。
（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不
使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，
行流水作业，同时消耗人、机、材等资源也合理。
2． 试写出M/M/1排队系统的Little 公式。
【答案】M/M/1排队系统的Little 公式为
二、计算题
3． （1）每月需要某种机械零件2000件，每件成本150元，每年的存储费用为成本的16%，每次订购费100 元，求E.O.Q 及最小费用。
（2）在题（1）中如允许缺货，求存储量s ，及最大缺货量，设缺货费为C 2=200元。
【答案】（1）用“不允许缺货，生产时间很短”的模型求解。
E.O.Q 为
最小费用为
所以，最佳批量为447件，最小费用约为10733元。
（2）用“允许缺货，生产时间很短”的模型求解。
第 2 页，共 31 页
最大缺货量为
所以库存量S 为423件，最大缺货量为50件。
4． 证明如下序列不可能是某个简单图的次的序列:
（l ）7，6，5，4，3，2;
（2）6，6，5，4，3，2，l ;
（3）6，5，5，4，3，2，l 。
【答案】（1）由定理知
，
不可能是图的次序列。
（2）此序列中，奇点为5，3，1，个数是奇数，所以此序列不可能为图的次的序列。
（3）对于七个顶点的图，若依次假定d （v 1）=6，d （v 2）=5，…，d （v 7）=l。
； v 2与v 1之间存在边e 12，①假定G 中无重复边，则v 1与其他六个顶点皆有连线（包括与v 7）
而v 7的次为1，所以必不与v 1外的其他点相连。因而，v 2与除v 1，v 7外的四点之间各有一条连线。
至此，v l 、v 2与v 3、v 4、v 5和v 6中任意一个就组成了环，则G 不是简单图。
②假定G 中无环，则根据情形①的分析，v 1的关联边中必存在重复边。从而G 不是简单图。由上可知，该图中必有环或多重边，不可能是简单图的次的序列。
5． 泰泽公司是一家制药公司。在研究了市场的需求，分析了当前药物的不足并且拜会了大量在有良好前景 的医药领域进行研究的科学家之后，总裁罗宾斯先生决定进行五个项目的开发研究:U P 项目、stable 项目、choice 项目、Hope 项目和Release 项目。公司现在有五位资深的科学家来领导进行这五个项目。总裁清楚，科学家们只 有在受到项目所带来的挑战和激励的时候才会努力工作。为了保证这些科学家都能够到他们感兴趣的项目中去， 项目开发部为这个项目建立了一个投标系统。这五位科学家每个人都有1000点的投标点。他们向每一个项目投 标，并且把较多的投标点投向自己最感兴趣的项目之中。如下表显示了这五位科学家进行投标的情况。
试建立反映如下各问题的数学模型并求解:
（l ）将这五位科学家指派各负责一个项目，使他们总的满意的投标点数最大;
（2）罗林斯博士接到哈佛医学院的邀请去完成一个教学任务必须离开公司，而且每个人只负责一个项目，这 时公司应当放弃哪个项目?
（3）若公司不愿意因罗林斯博士离开而放弃任何一个项目，这时应该由哪一个科学家兼任两个项目的研究才能使得对项目的总的热情最大?
表 五位科学家进行投标的情况 为偶数，而在此序列中，为奇数，所以此序列
第 3 页，共 31 页
【答案】首先建立这个问题的数学模型为:
（l ）这是个最大化指派问题，先将它化为最小化指派问题为:
现在对C 加圈，得到:
得到了4个独立元素，少于5个，不能确定最优指派方案，为了使它有5个独立元素，让第三行和第五行都 分别减去316，并且第五列加上316，得到
第 4 页，共 31 页
相关内容
相关标签