运筹学作业题整理

1、运 筹 学 作 业 整 理1. 公交车调度安排某市欲对其公交车的投放数量进行优化。通过调查发现，所需的最少公交车数随一天中的时间不同而变化，而且所需的最少公交车数在若干连续的4小时内可以被近似地看做一个常数，时间段与所需公交车数的关系如图1所示。为了进行日常维修，每辆公交车一天只能连续运行8小时。图1 一天内不同时间段所需公交车数请确定每一班运行公交车的数量，以满足最小需求约束，且使所运行的公交车总数最少。2. Personnel SchedulingOne AIR Company is adding more flights to and from its hub airport, and

2、so it needs to hire additional customer service agents. However, it is not clear just how many more should be hired. Management recognizes the need for cost control while also consistently providing a satisfactory level of service to customers. Therefore, an OR team is studying how to scheduling the

3、 agents to provide satisfactory service with the smallest personnel cost. Based on the new schedule of flights, an analysis has been made of the minimum number of customer service agents that need to be on duty at different times of the day to provide a satisfactory level of service. The right most

4、column of the flowing table shows the number agents needs for the time periods given in the first column. The other entries in this table reflect one of the provisions in the companys current contract with the union that the represents the customer service agents. The provision is that each agent wo

5、rks an 8-hour shift 5 days per week. The five authorized eight-hour shifts are Shift 1:6:00 AM to 2:00 PM Shift 2:8:00 AM to 4:00 PM Shift 3:Noon to 8:00 PM Shift 4:4:00 PM to midnight- Shift 5:10:00 PM to 6:00 AM. How many agents should be assigned to each shift? Please set up a LP model and solve

6、it.3. 已知某工厂计划生产I，II，III三种产品，各产品需要在A，B，C设备上加工，有关数据见表4-24。表4-24产品设备IIIIII设备有效台时(月)A8210300B1058400C21310420单位产品利润(千元)322.9请回答：（1）如何发挥设备能力，使生产盈利最大？（2）若为了增加产量，可借用其他工厂的设备B，每月可借用60台时，租金为1.8万元，是否划算？（3）若另有两种新产品IV，V，其中IV需用A设备12台时，B设备5台时，C设备10台时，单位产品盈利2.1千元；新产品V需用A设备4台时，B设备4台时，C设备12台时，单位产品盈利1.87千元。且A，B，C设备台时不

7、增加，生产这两种新产品是否划算？（4）对产品工艺重新进行设计，改进构造。改进后生产每件产品I，需用A设备9台时，B设备12台时，C设备4台时，单位产品盈利4.5千元，这对原计划有何影响？4.求下述线性规划问题目标函数的上界和下界。5. 下表为用单纯形法计算时某一步的表格，已知该线性规划的目标函数为 max z=5x1+3x2，约束形式为，x3和x4为松弛变量，表中解代入目标函数后得z10。x1x2x3x4x3c011/52x1de01acj-zjb-1fg1. 求a,b,c,d,e,f,g的值；2. 表中给出的解是否为最优解。6. 分析下列参数规划中当和时最优解的变化情况。7. 分析下列参数规

8、划中当和时最优解的变化情况8. 消防车调度问题某市消防中心同时接到了三处火警报告。根据当前的火势，三处火警地点分别需要2辆、2辆和3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记tij为第j辆消防车到达火警地点i的时间（分钟），则三处火警地点的损失分别为：6t11+4t12，7t21+3t22，9t31+8t32+5t33；目前可供消防中心调度的消防车正好有7辆，分别属于三个消防站（可用消防车数量分别为3辆、2辆、2辆）。消防车从三个消防站到三个火警地点所需要的时间如表1所示。该公司应如何调度消防车，才能使总损失最小？表1 消防站到三个火警地点所需要的时间时间（分钟）火警

9、地点1火警地点2火警地点3消防站1679消防站25811消防站36910如果三处火警地点的损失分别为：4t11+6t12，3t21+7t22，5t31+8t32+9t33，调度方案是否需要改变？9. 蔬菜供应方案：某城市为人口不到20万的小城市，根据该市蔬菜种植情况，分别在A、B、C设3个收购点。清晨4点前菜农将蔬菜运至各收购点，再由各收购点分别送到全市8个菜市场。该市道路情况、各路段距离（单位：100米）及各收购点、菜市场的具体位置如下图所示。按统计数据，A、B、C 3个收购点每天收购量分别为200、170、160（单位：100千克），各菜市场每天的需求量以及发生供应短缺时的损失（单位：元/

10、100千克）见表1.表1 各菜市场日需求量及短期损失费用信息表菜市场日需求/千克75608070100559080短缺损失 /（元/100千克）10851010858设从收购点至各菜市场蔬菜调运费用为1元（100千克100米），试解决如下问题：（1） 为该市设计一个从各收购点至各菜市场的定点供应方案，使得蔬菜调运及预期的短缺损失最小；（2） 若规定各菜市场短缺量一律尽量不超过需求量的20%，重新设计定点供应方案；（3） 为满足居民的蔬菜供应，该市规划增加蔬菜种植面积，那么增产的蔬菜每天应分别向A、B、C3个采购点各供应多少最经济合理？10. 具有截止时间和误时惩罚的任务安排问题可描述如下： （

11、1）给定n个任务的集合S=1,2,n; （2）完成任务i需要ti时间，1=i=n; （3）任务i的截止时间为di，1=i=n，即要求任务i在时间di之前结束； （4）任务i的误时惩罚为wi，1=i=n，即任务i未在时间di之前结束将招致wi的惩罚；若按时完成，则无惩罚。 任务安排问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。任务i作业时间1211113期限di4243146罚款wi7060504030208011. 一个单位时间任务是指恰好需要一个单位时间完成的任务。给定一个单位时间任务有限集S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序. 该调度中的第一个任

12、务开始于时间0,结束于时1;第二个任务开始于时间1,结束于时间2, 单处理器上具有截止期限和误工惩罚的单位时间任务调度问题的输入如下: 1. 包含n个单位时间任务的集合S=1,2,n; 2. 截止期限d1 ,dn ,(1d,n),任务i要求在di前完成; 3. n个非负的权(误工惩罚)w1 ,wn .如果任务i没在时间di 之前结束,则导致罚款wi ; 要求找出S的一个调度,使之最小化总的惩罚12. 装箱问题描述 有无限多个箱子,每个箱子容量为V,有N件物品,每件体积分别为v1， v2 ， vn (0 vi V)，求能容纳这个N件物品的最少箱数。13. 树枝形专用线非直达车流取送车问题13.1

13、、设定条件 （1）一台调车机车作业,连送带取； （2）每专用线至少有两条股道（见下图）； （3）各专用线待送、待取车数已定； （4）各段距离和走行时间已知。13.2、优化目标 （1）使机车取送总时间F1最小； （2）在F1最小的基础上，使所有专用线总的入线车小时消耗F2最小。 （3）在F1最小的基础上，使总的走行车辆公里数F3最小。13.3、求合理的取送顺序，使目标实现。104.552.062.541.5123.092.0154.0102.582.071.5V0V1V2V3V4V5V6V7V8V9V10V1152.0图中顶点和边的意义： 树根车站；树枝走行线；树叶专用线； 分枝点道岔；共用枝连

14、接两个分枝点的边； -号代表送车，+号代表取车。14. 某工程各项工作间的逻辑关系如下表所示，试绘制双代号网络图，并计算各项工作的时间参数，判定关键线路。工作名称前导工作后续工作持续时间AC、D2BE、G3CAJ5DAF3EBF2FD、EH、I4GB2HFJ1IF3JC、H415. 发现的奇异现象：在上述经典的统筹网络图中加入下列时间约束：1. “A工序结束后至少10天，B工序才能结束”结束-结束型最小时间约束；2. “B工序开始后至少8天，C工序才能开始”开始-开始型最小时间约束。 计算出时间参数，求出关键路线。16.马尔科夫链：Starting from state 2, the probability of absorption into state 0 (A losing all his money) can be obtained byThe probability of A winning $4 (B going broke) ?17. 马尔科夫链：Customers who are fully paid (in state 0) and then subsequently fall into ar