实实 验验 报报 告告运筹学运筹学 A（二）（二）学学 号：号： 姓姓 名：名： 学学 院：院： 交通运输工程交通运输工程指导教师：指导教师： 叶鸿叶鸿 二零一零年六月二零一零年六月实验一：最小树、最短路与最大流问题实验一：最小树、最短路与最大流问题（一）实验目的：掌握 WinQSB 软件求最小树、最短路与最大流问题，掌握其操作方法二）内容和要求：用 WinQSB 软件完成下三例最小树问题：求下图的最小生成树和最大生成树：6V1 V26 6 2 2V6 7 V7 3 V38 3 4 3V5 1 V4最短路问题：如图所示网络，各线段上的数字代表相应两节点间的距离，请求出从节点 1 到节点 10 之间的最短距离网络图①① 最大流问题：最大流问题：某单位招收懂俄、英、日、德、法文的翻译各一人，有 5 人应聘已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这 5 个人是否都能得到聘书？最多几个得到招聘，招聘后每人从事哪一方面翻译任务？（三）操作步骤最小树、最短路问题和最大流问题的运算程序是 Network Modeling（网络模型） 。
最小树（1）选择 Minimal Spanning Tree， ，输入节点数两点间的权数只输入一次（上三角） 2）点击菜单栏 Solve and Analyze，输出表最小树结果， ；点击菜单栏 Results→Graphic Solution,，显示最小部分树形最短路问题（1）1 选择 Shortest Path Problem，如果是有向图就按弧的方向输数据，本例是无向图，每一条边必须输入两次，无向边变为两条方向相反的弧（2）点击 Solve and Analyze 后系统提示用户选择图的起点和终点，点击 Result→Graphic Solution，显示最短路线图最大流问题（1）选择 Maximal Flow Problem输入节点数，输入弧容量即可2）点击 Solve and Analyze 后系统提示用户选择图的起点和终点;点击 Result→Graphic Solution，显示各点的流量图实验二：实验二：网络计划网络计划（一）实验目的：掌握 WinQSB 软件计算网络计划时间参数，并进行时间费用优化二）内容和要求：用 WinQSB 软件完成已知下表所列资料：工序代号正常时间最短时间紧前工序正常完成的直 接费用（百元）费用斜率 （百元/天）A43—205B86—304C64B153D32A52E53A184F75A407G43B、D103H32E、F、G156合 计153工程的间接费用5（百元/天）绘制网络图；计算各工序最早开工，最早完工，最迟开工，最迟完工时间及总时差，并指出关键工序。
并求出该项工程总费用最低的最优工期（最低成本日程） 实验三：排队论和存储论实验三：排队论和存储论（一）实验目的：掌握 WinQSB 软件排队论和存储论相关参数的计算二）内容和要求：分别用 WinQSB 软件和 Delph 软件完成两个算例排队论：模型排队论：模型 M / M / C / ∞/∞/ ∞∞ 某运输公司有一个装卸队服务于卡车队，装卸每辆车所用时间服从平均时间为20 分钟的指数分布，卡车到达时间服从平均时间为 30 分钟的泊松分布管理层想提高装卸队的效率，把装卸队分成两队，每队装卸每辆车所用时间服从平均时间为 40 分钟的指数分布，请问效率是否得到提高？存储论存储论某电子设备厂对一种元件的需求为 R＝2000 件/年，订货提前期为零，每次订货费为 25 元该元件每件成本为 50 元，年存储费为成本的 20％如发生缺货，可在下批货到达时补上，但缺货损失费为每件每年 30 元求：（1）经济订货批量及全年的总费用；（2）如不允许发生缺货，重新求经济订货批量，并同（1）的结果进行比较实验四：对策论实验四：对策论（一）实验目的：掌握运筹学程序 Delph 求解对策论的解二）内容和要求：完成下面算例对策论对策论设矩阵对策 G＝{S1,S2;A}，其中 S1={a1,a2,a3,a4},S2={b1,b2,b3,b4},赢得矩阵为6 5 6 51 4 2 -1A= 8 5 7 50 2 6 2实验五：实验五：动态规划中的最短路问题和背包问题动态规划中的最短路问题和背包问题（一）实验目的：掌握 WinQSB 软件求解动态规划中的最短路问题和背包问题。
掌握操作方法二）内容和要求：用 WinQSB 软件完成下两例：（最短路问题）考虑如下图的网络，设 A 为电源，E 为变电站，B，C，D 分别为三个必须建立铁塔的地区，其中 B1，B2，B3；C1，C2，C3；D1，D2 分别为可供选择的铁塔站位图中线段表示可架线位置，线段旁数字表示架线所需费用（或距离） ，问如何架线才能使总费用（或距离）最小？（一维“背包”问题）有一辆最大货运量为 10 吨的卡车，用于装载三种货物，每种货物的单位重量及相应单位价值如下，应如何装载可使总价值最大？货物的单位重量及相应单位价值货物编号 i123单位重量（吨）345单位价值 Ci456（三）操作步骤：(1)、启动程序，点击开始（start）→程序→Winqsb→Dynamic Programming (DP)2)、求解最短路问题：建立新问题，选择 Stagecoach Problem，输入标题明、网络节点树；输入节点到节点的距离，求解并确定起点与终点，读写结果3)、求解背包问题：建立新问题，选择 Knapsack Problem，输入标题名、物品名数；分别输入每种物品可装载数量、单位物品容量、单位物品价值函数及背包容量，求解并分析结果。
实验六：综合设计实验六：综合设计（一）排队问题设计排队问题在我们生活中到处可见，我们打水时、我们吃饭时、还有我们在买票回家时等等，研究排队问题可以帮助我们了解当前的排队状况，了解站台的服务效率以及服务强度，为我们的生活提供方便请作实地调查，对一个站台排一队的问题做研究1，数据调查2.确定模型，并求出：1）买票窗口空闲及繁忙的概率2）排队买票的人数3）排队等待的人数4）顾客在站台逗留的时间5）顾客排队等待的时间3． 对所得数据进行分析（二）校园洒水车最短路径设计进行数据调查后，请选择合适的模型，自行设计方案实验报告格式（每一个实验分四部分）：实验名称，实验目的，实实验报告格式（每一个实验分四部分）：实验名称，实验目的，实验内容与要求，实验结果与分析验内容与要求，实验结果与分析。