运筹学作业题整理解剖
运筹学作业整理
1. 公交车调度安排
某市欲对其公交车的投放数量进行优化。通过调查发现，所需的最少公交车数随一天中的时间不同而变化，而且所需的最少公交车数在若干连续的4小时内可以被近似地看做一个常数，时间段与所需公交车数的关系如图1所示。为了进行日常维修，每辆公交车一天只能连续运行8小时。
图1 一天内不同时间段所需公交车数
请确定每一班运行公交车的数量，以满足最小需求约束，且使所运行的公交车总数最少。
2. Personnel Scheduling
One AIR Company is adding more flights to and from its hub airport, and 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 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 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 company’s current contract with the union that the represents the customer service agents. The provision is that each agent works 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 it.
3.已知某工厂计划生产I，II，III三种产品，各产品需要在A，B，C 设备上加工，有关数据见表4-24。
产品设备I II III
设备有效台
时(月)
A 8 2 10 300
B 10 5 8 400
C 2 13 10 420
单位产品利润
(千元)
3 2 2.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设备台时不增加，生产这两种新产品是否划算？
（4）对产品工艺重新进行设计，改进构造。改进后生产每件产品I，需用A设备9台时，B设备12台时，C设备4台时，单位产品盈利4.5千元，这对原计划有何影响？
4.求下述线性规划问题目标函数的上界和下界。
5. 下表为用单纯形法计算时某一步的表格，已知该线性规划的目标函数为max z=5x1+3x2，约束形式为≤，x3和x4为松弛变量，表中解代入目标函数后得z＝10。
x1x2x3x4
x3 c 0 1 1/5 2
x1 d e 0 1 a
c j-z j b -1 f g
1. 求a,b,c,d,e,f,g的值；
2. 表中给出的解是否为最优解。
6. 分析下列参数规划中当0
θ≤时最优解的变化情况。
θ≥和0
7. 分析下列参数规划中当0
θ≤时最优解的变化情况
θ≥和0
8. 消防车调度问题
某市消防中心同时接到了三处火警报告。根据当前的火势，三处火警地点分别需要2辆、2辆和3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记t ij为第j辆消防车到达火警地点i的时间（分钟），则三处火警地点的损失分别为：
6t11+4t12，7t21+3t22，9t31+8t32+5t33；
目前可供消防中心调度的消防车正好有7辆，分别属于三个消防站（可用消防车数量分别为3辆、2辆、2辆）。消防车从三个消防站到三个火警地点所需要的时间如表1所示。该公司应如何调度消防车，才能使总损失最小？
表1 消防站到三个火警地点所需要的时间
如果三处火警地点的损失分别为：
4t 11+6t 12，3t 21+7t 22，5t 31+8t 32+9t
33，
调度方案是否需要改变？
9. 蔬菜供应方案：
某城市为人口不到20万的小城市，根据该市蔬菜种植情况，分别在A 、B 、C 设3个收购点。清晨4点前菜农将蔬菜运至各收购点，再由各收购点分别送到全市8个菜市场。该市道路情况、各路段距离（单位：100米）及各收购点、菜市场的具体位置如下图所示。
⑥
④
T 3
按统计数据，A 、B 、C 3个收购点每天收购量分别为200、170、160（单位：100千克），各菜市场每天的需求量以及发生供应短缺时的损失（单位：元/100千克）见表1.
表1 各菜市场日需求量及短期损失费用信息表
设从收购点至各菜市场蔬菜调运费用为1元（100千克·100米），试解决如下问题：
（1）为该市设计一个从各收购点至各菜市场的定点供应方案，使得蔬菜调运及预期的短缺损失最小；
（2）若规定各菜市场短缺量一律尽量不超过需求量的20%，重新设计定点供应方案；
（3）为满足居民的蔬菜供应，该市规划增加蔬菜种植面积，那么增产的蔬菜每天应分别向A、B、C3个采购点各供应多少最经济合理？
10.具有截止时间和误时惩罚的任务安排问题可描述如下：
（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的一个时间表（最优时间表）使得总误时惩罚达到最小。
11.一个单位时间任务是指恰好需要一个单位时间完成的任务。给定一个单位时间任务有限集S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序. 该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1,结束于时间2,……
单处理器上具有截止期限和误工惩罚的单位时间任务调度问题的输入如下:
1. 包含n个单位时间任务的集合S={1,2,……,n};
2. 截止期限d1 ,……,dn ,(1≤d,≤n),任务i要求在di前完成;
3. n个非负的权(误工惩罚)w1 ,……,wn .如果任务i没在时间di 之前结束,则导致罚款wi ;
要求找出S的一个调度,使之最小化总的惩罚
12.装箱问题描述
有无限多个箱子,每个箱子容量为V,有N件物品,每件体积分别为v1，v2 ，…，vn (0< vi≤V)，求能容纳这个N件物品的最少箱数。
13.树枝形专用线非直达车流取送车问题