《北邮运筹学作业.doc》由会员分享，可在线阅读，更多相关《北邮运筹学作业.doc（9页珍藏版）》请在金锄头文库上搜索。
1、2运 筹 学 作 业 题 集-仅供学习，不得买卖No.1 线性规划1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目ABCD单位产值 (元)1681401050406单位成本 (元)4228350140单位纺纱用时 (h)32104单位织带用时 (h)0020.5工厂有供纺纱的总工时7200h，织带的总工时1200h。(1) 列出线性规划模型，以便确定产品的数量使总利润最大；(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？（所谓一次性投入就是与产量无关的初始投资）2、将下列
2、线性规划化为极大化的标准形式3、用单纯形法解下面的线性规划No.2 两阶段法和大M法1、用两阶段法解下面问题：2、用大M法解下面问题，并讨论问题的解。No.3 线性规划的对偶问题1、写出下列线性规划问题的对偶问题：(1) (2)2、写出下问题的对偶问题，解对偶问题，并证明原问题无可行解3、用对偶单纯形法求下面问题No.4 线性规划的灵敏度分析1、下表是一线性规划最优解的单纯形表Cj 2194000CBXBbx1x2x3x4x5x621x14101/32/301/30x5200-2/3-4/311/39x223011/3-1/30-2/3zj219101101cj - zj00-6-110-1原
3、问题为max型，x4，x5为松驰变量，x6为剩余变量，回答下列问题：(1)资源1、2、3的边际值各是多少？(x4，x5是资源1、2的松驰变量，x6是资源3的剩余变量)(2)求C1, C2 和C3的灵敏度范围；(3)求Db1，Db2的灵敏度范围。No.5 运输问题1、分别用西北角法、最低费用法和运费差额法，求下面运输问题(见表)的初始可行解，并计算其目标函数。(可不写步骤)2、以上题中最低费用法所得的解为初始基础可性解，用表上作业法（踏石法）求出最优解。（要求列出每一步的运费矩阵和基础可行解矩阵）销地产地B1B2B3B4B5产量A16948520A2106128730A365920940A421
4、3614360销量2515354530No.6 指派问题1、有4个工人。要指派他们分别完成4项工作。每人做各项工作所消耗的时间(h) 如下表，问如何分派工作，使总的消耗时间最少？消耗 工作工人ABCD甲3353乙3252丙1516丁464102、学生A、B、C、D的各门成绩如下表，现将此4名学生派去参加各门课的单项竞赛。竞赛同时举行，每人只能参加一项。若以他们的成绩为选派依据，应如何指派最有利？得分 课程学生数学物理化学外语A89926881B87886578C95908572D75788996No.7 动态规划1、某公司有9个推销员在全国三个不同市场里推销货物，这三个市场里推销员人数与收益的
5、关系如下表，做出各市场推销人员数的分配方案，使总收益最大。推销员市场0123456789120324757667182901001102405060718293104115125135350617284971091201311401502、设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。生产这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为(12-x1)和(13-2x2)。这里x1和x2分别为两种产品的产量。假设两种产品的生产费用分别是4x1和3x2，问如何安排两种产品的生产量使该机器在5小时内获利最大。No.8 最短路问题1、求下图中v1到所有
6、点的最短路径及其长度。(要求最短路用双线在图中标出，保留图中的标记值)2、将右图看作无向图，写出边权邻接矩阵，用Prim算法求最大生成树，并画出该树图。No.9 网络流问题1、求下面网络s到t的最大流和最小截，从给定的可行流开始标号法。(要求每得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可行流，再进行标号法)No.10 随机服务系统：输入过程1、对一服务系统进行观察，总观察时间为102.7分钟，到达系统的累计人数为40人，顾客累计的排队等待时间为44.8分钟，顾客累计的服务时间为79.6分钟，求(1) 系统中平均排队长度；(2)平均同时接受服务的人数。2、某选举站对甲、乙二人进
7、行选举，选票中只能选其中一人才有效。假设投票的人流服从泊松分布，投甲票的人的到达率为l1 =4人/小时，投乙票的人的到达率为l2 =2人/小时；再假设所有投票人的票都是有效的，而选举结果的统计是在一个与选民不见面的屋里与投票过程同时进行的。问选举开始后半小时统计结果为：(1)甲得三票，乙得1票的概率；(2)总票数为5的概率；(3)甲得全票的概率。No.11 随机服务系统：标准服务系统1、某自动交换台有4条外线，打外线的呼叫强度为2次/分钟，为泊松流，平均通话时长为2分钟。当4条外线全忙时，用户呼叫将遇忙音。假设用户遇忙音后立即停止呼叫。问(1)用户拨外线遇忙的概率为多大？(2)一小时内损失的话
8、务量为多少？(3)外线的利用率为多少？(4)过负荷为100%时，外线的利用率为多少？2、某车间机器发生故障为一泊松流，平均4台/小时。车间只有一名维修工，平均7分钟处理一台故障。若为该维修工增加一特殊工具可使平均故障处理时间降到5分钟，但这一特殊工具的使用费用为5元/分钟。机器故障停工每台每分钟损失5元，问购置这台特殊工具是否合适？3、有M/M/n：/FIFO(先到先服务)系统，输入业务量为r，求：当n=1, 2 , 3时的等待概率D，和平均逗留队长Ld 的公式。No.12 存储论1、某工厂每年需某种原料1000kg，一次定购费为200元，定购量Q与单价k的关系为0 Q 500kg，k1 =2
9、元/kg500 Q 1000kg，k2 =1.5元/kg1000 Q, k3 =1.2元/kg已知原料存储费也与Q有关0 Q 500kg，Cs1 =2元/kg.年500 Q 1000kg，Cs2 =1.5元/kg.年1000kg Q, Cs3 =1.2元/kg.年求最佳订货量Qm，并求该订货量下的全年总费用C(Qm)。2、推导连续进货、允许缺货模型的最佳订货量Q0和最佳订货周期T0的公式。附录：爱尔兰损失表 En(A) n B0.0050.010.050.10.20.310.0050.0100.0530.1110.2500.42920.1050.1530.3810.5951.0001.4493
10、0.3490.4550.8991.2711.9302.63340.7010.8691.5252.0452.9453.89151.1321.3612.2182.8814.0105.18961.6221.9092.9603.7585.1096.51472.1572.5013.7384.6666.2307.85782.7303.1284.5435.5977.3699.21393.3333.7835.3706.5468.52210.579103.9614.4616.2167.5119.68511.953114.6105.1607.0768.48710.85713.333125.2795.8767.95
11、09.47412.03614.719135.9646.6078.83510.47013.22216.109146.6637.3529.73011.47314.41317.503157.3768.10810.63312.48415.60818.899168.1008.87511.54413.50016.80720.300178.8349.65212.46114.52218.01021.702189.57810.43713.38515.54819.21623.1051910.33111.23014.31516.57920.42424.5102011.09212.03115.24917.61321.
12、63525.9172111.86012.83816.18918.65122.8482212.63513.65117.13219.69224.0642313.41614.47018.08020.73725.2812414.20415.29519.03121.78426.4992514.99716.12519.98522.83327.7202615.79516.95920.94323.88528.9412716.59817.79721.90424.93930.1642817.40618.64022.86725.99531.3882918.21819.48723.83327.05332.6143019.03420.33724.80228.11333.8403119.85421.19125.77329.17435.0673220.67822.04826.74630.23736.2953321.50522.90927.72131.30137.5243422.33623.77228.69832.36738.7543523.16924.63829.67733.43439.9853624.00625.50
