运筹学作业题整理分解.docx
- 文档编号:13257038
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:16
- 大小:112.33KB
运筹学作业题整理分解.docx
《运筹学作业题整理分解.docx》由会员分享,可在线阅读,更多相关《运筹学作业题整理分解.docx(16页珍藏版)》请在冰点文库上搜索。
运筹学作业题整理分解
运筹学作业整理
1.公交车调度安排
某市欲对其公交车的投放数量进行优化。
通过调查发现,所需的最少公交车
数随一天中的时间不同而变化,而且所需的最少公交车数在若干连续的4小时内可以被近似地看做一个常数,时间段与所需公交车数的关系如图1所示。
为了进行日常维修,每辆公交车一天只能连续运行8小时。
前-V10
午
12:
004:
008:
0012:
004:
008:
0012:
00
公交车数
图1一天内不同时间段所需公交车数
请确定每一班运行公交车的数量,以满足最小需求约束,且使所运行的公交车总数最少。
2.PersonnelScheduling
OneAIRCompanyisaddingmoreflightstoandfromitshubairport,andsoitneedstohireadditionalcustomerserviceagents.However,itisnotclearjusthow
manymoreshouldbehired.Managementrecognizestheneedforcostcontrolwhilealsoconsistentlyprovidingasatisfactorylevelofservicetocustomers.Therefore,anORteamisstudyinghowtoschedulingtheagentstoprovidesatisfactoryservicewiththesmallestpersonnelcost.
Basedonthenewscheduleofflights,ananalysishasbeenmadeoftheminimumnumberofcustomerserviceagentsthatneedtobeondutyatdifferenttimesofthedaytoprovideasatisfactorylevelofservice.Therightmostcolumnoftheflowingtableshowsthenumberagentsneedsforthetimeperiodsgiveninthefirstcolumn.
scurrent
Theotherentriesinthistablereflectoneoftheprovisionsinthecompany
contractwiththeunionthattherepresentsthecustomerserviceagents.Theprovisionisthateachagentworksan8-hourshift5daysperweek.
Thefiveauthorizedeight-hourshiftsare
-Shift5:
10:
00PMto6:
00AM.
TimePeriod
TimePeriodsCovered
byShift
Miiiiiuiuii
JNiunberof
AgentsiNeeded
1
2
34
5
6AMtoHAM
7
4H
苦AMto10AM
V
79
10AMtonoon
寸
V
65
Noonto2PM
V
87
2PMto4PM
V
寸
64
4PMto6PM
73
6PMtoSPM
7V
82
SPMto10PM
t
V
43
10PMtomidnight
1
V
J
52
Midnightto6AM
寸
15
Dailycostperagent
$170
$160$175$180
$195
Howmanyagentsshouldbeassignedtoeachshift?
PleasesetupaLPmodelandsolveit.
3.已知某工厂计划生产1,11,III三种产品,各产品需要在A,B,C设备上加工,有关数据见表4-24。
表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.求下述线性规划问题目标函数迄的上界/和下界{。
max:
z=q%4$£
1
%斥*叫巧
%王"
其中1£丘兰戈4兰勺兰免8兰毎兰1210兰$£14
5.下表为用单纯形法计算时某一步的表格,已知该线性规划的目标函数为maxz=5x+3x?
,约束形式为§冷和X4为松弛变量,表中解代入目标函数后得z=10。
Xi
X2
X3
X4
X3
c
0
1
1/5
2
Xi
d
e
0
1
a
Cj-Zj
b
-1
f
g
1.求a,b,c,d,e,f,g的值;
2.表中给出的解是否为最优解
6.分析下列参数规划中当=一0和”乞0时最优解的变化情况
m«2(tf)=(8—fifi)xj+(2+^X2+(5-26)ix^\+2]4+^<40
st?
7.分析下列参数规划中当-_0和―:
0时最优解的变化情况
msz(硏=2珂+込
r2^+2^<12+3fl
Xj+Zxjd+H
sX4j|<16-^
4^<12-2fl
8.消防车调度问题
某市消防中心同时接到了三处火警报告。
根据当前的火势,三处
火警地点分别需要2辆、2辆和3辆消防车前往灭火。
三处火警地点的损失将依赖于消防车到达的及时程度:
记tj为第j辆消防车到达
火警地点i的时间(分钟),则三处火警地点的损失分别为:
6t1l+4tl2,7t2l+3t22,9t3l+8t32+5t33;
目前可供消防中心调度的消防车正好有7辆,分别属于三个消防站(可用消防车数量分别为3辆、2辆、2辆)。
消防车从三个消防站到三个火警地点所需要的时间如表1所示。
该公司应如何调度消防车,才能使总损失最小?
表1消防站到三个火警地点所需要的时间
时间(分钟)
火警地点1
火警地点2
火警地点3
消防站1
6
7
9
消防站2
5
8
11
消防站3
6
9
10
如果三处火警地点的损失分别为:
4tll+6tl2,3t2l+7t22,5t3l+8t32+9t33,
调度方案是否需要改变?
9.蔬菜供应方案:
某城市为人口不到20万的小城市,根据该市蔬菜种植情况,分
别在A、B、C设3个收购点。
清晨4点前菜农将蔬菜运至各收购点,再由各收购点分别送到全市8个菜市场。
该市道路情况、各路段距离
(单位:
100米)及各收购点、菜市场的具体位置如下图所示
按统计数据,AB、C3个收购点每天收购量分别为200、170、
160(单位:
100千克),各菜市场每天的需求量以及发生供应短缺时的损失(单位:
元/100千克)见表1.
表1各菜市场日需求量及短期损失费用信息表
菜市场
①
②
③
④
⑤
⑥
⑦
⑧
日需求/千克
75
60
80
70
100
55
90
80
短缺损失/(元
/100千克)
10
8
5
10
10
8
5
8
设从收购点至各菜市场蔬菜调运费用为1元(100千克•100米),试
解决如下问题:
(1)为该市设计一个从各收购点至各菜市场的定点供应方案,使得蔬菜调运及预期的短缺损失最小;
(2)若规定各菜市场短缺量一律尽量不超过需求量的20%重新设计定点供应方案;
(3)为满足居民的蔬菜供应,该市规划增加蔬菜种植面积,那么增
产的蔬菜每天应分别向AB、C3个采购点各供应多少最经济合理?
10.具有截止时间和误时惩罚的任务安排问题可描述如下:
(1)给定n个任务的集合S={1,2,……,n};
(2)完成任务i需要ti时间,1<=iv=n;
(3)任务i的截止时间为di,1<=iv=n,即要求任务i在时间di之前结束;
(4)任务i的误时惩罚为wi,1<=iv=n,即任务i未在时间di
之前结束将招致wi的惩罚;若按时完成,则无惩罚
任务安排问题要求确定S的一个时间表(最优时间表)使得总
误时惩罚达到最小。
任务i作业
时间
1
2
1
1
1
1
3
期限di
4
2
4
3
1
4
6
罚款wi
70
60
50
40
30
20
80
11.一个单位时间任务是指恰好需要一个单位时间完成的任务。
给定一个单位时间任务有限集S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序•该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1,结束于时间2,……
单处理器上具有截止期限和误工惩罚的单位时间任务调度问题的输入如下:
1.包含n个单位时间任务的集合S={1,2,……,n};
2.截止期限d1,,dn,(1 3.n个非负的权(误工惩罚)w1,……,wn.如果任务i没在时间di之前结束,则导致罚款wi; 要求找出S的一个调度,使之最小化总的惩罚 12.装箱问题描述 有无限多个箱子,每个箱子容量为V,有N件物品,每件体积分别为vl,v2,…,vn(0 13.树枝形专用线非直达车流取送车问题 13.1、设定条件 (1)一台调车机车作业,连送带取; (2)每专用线至少有两条股道(见下图); (3)各专用线待送、待取车数已定; (4)各段距离和走行时间已知。 13.2、优化目标 (1)使机车取送总时间F1最小; (2)在F1最小的基础上,使所有专用线总的入线车小时消耗F2最小。 (3)在F1最小的基础上,使总的走行车辆公里数F3最小 树根车站;树枝走行线;树叶专用线;分枝点——道岔;共用枝——连接两个分枝点的边;-号代表送车,+号代表取车。 14.某工程各项工作间的逻辑关系如下表所示,试绘制双代号网络图,并计算各项工作的时间参数,判定关键线路。 工作名称 前导工作 后续工作 持续时间 A C、D 2 B E、G 3 C A J 5 D A F 3 E B F 2 F D、E H、I 4 G B 2 H F J 1 I F 3 J C、H 4 15.发现的奇异现象: 蜃I 在上述经典的统筹网络图中加入下列时间约束: 1.“工序结束后至少10天,B工序才能结束”结束-结束型最小时间约束;2.“B工序开始后至少8天,C工序才能开始”一-始-开始型最小时间约束。 计算出时间参数,求出关键路线。 16•马尔科夫链: ItwaspointedoutinSec.16.4thatastatekiscalledanabsorbingslateif/加=Lsothatoncelhechainvisitskitremainsthereforever,Ifkisanabsorbingstate,andtheprocessstartsinstaleltheprobabilityofevergoingtoslatekiscalledtheprobabilityofabsorp>tionintostate&giventhatlhesystemstartedinstateLThisprobabilityisdenotedby WhentherearetwoormoreabsorbingstatesinaMarkovchain,anditisevidentthattheprocesswillbeabsorbedintooneofthesestales*itisdesirabletofindtheseprobabilitiesofubsoq? tion.Theseprobabilitiescanbeobtainedbysolvingasystemoflinearequationsthatconsidersallthepossibilitiesforthefirsttransitionandthen,giventhefirsttransition,considerstheconditionalprobabilityofabsorptionintostateLInparticular,ifthestatekisanabsorbingstate,thenthesetofabsorptionprobabilitiessatisfiesthesystemofequations M 血=工卩过掷forj=0、M subjecttolheconditions 血=1* 血=0・ifslateiisrecunentandi丰A+ 10 00 20 10 40 Absorptionprobabilitiesareimportantinrandomwalks.ArandomwalkisaMaikovchainwiththeproperlythatifthesysltjnisinastatehtheninasingletrunsitionthesystemeitherremainsatiormovestooneofthetwostatesimmediatelyadjacenttoLForexample,arandojnwalkoftenisusedasamodelforsituationsinvolvinggambling・ Tojllustrate.consideragamblingexamplesimilartothatpresentedinSec.16.2.However.supposenowthattwoplayers(AandR*eachhaving$2.agreetokeepplayingthegameandbetting$1atatimeuntiloneplayerisbroke.TheprobabilityofAwinningasinglebells予soBwinsthebetwithprobability£ThenumberofdollarsthatpluyerAhasbeforeeachbet(0,k2,3.or4)providestheslatesofaMaikovchainwithtransitionniulrix Startingfromstate2,theprobabilityofabsorptionintostate0(Alosing allhismoney)canbeobtainedby 00 30 20 40 TheprobabilityofAwinning$4(Bgoingbroke)? Therearemanyothersituationswhereabsorbingstatesplayanimportantrole,Consideradepartmentstorethatclassifiesthebalanceofacustomer'sbillasfullypaid(state0).Ito30daysinarrears{statelh31to6()daysinuirears(state2}.orbaddebt(state3).Theaccountsarecheckedmonthly10determinethestateofeachcustomer.Ingeneral,creditisnotextendedandcustomersareexpectediopaytheirbillswithin30days,Occasionally,customerspayonlyportionsoftheirbill.Ifthisoccurswhenthebalanceiswithin30daysinarrears(state1},thestoreviewsThecustomerasremaininginstuteI.Ifthisoccurswhenthebalanceisbetween31and60daysinaiTeurs,tliestoreviewsthecustomerasmovingtostateI(1to30duysinarrears).Cuslomei^(hataremurethan60daysinarrearsarepulintothebad-debtcategory(state3),andthenbillsaresenttoacolleciionagency.AfterexaminingdataoverthepastseveralyearsonThemonthbymonthprogressionofindividualcustomersfromstatetostate,thestorehasdevelopedthefollowingtransitionmatrix: 1 17.马尔科夫链: Customerswhoarefullypaid(instate0)andthensubsequentlyfallintoarrearsonnewpurchasesareviewedas“new”customerswhostartin state1. ...State State" o: FullyPaid 1: 1toJODaysinArrears 2: to60Days tnArrears i: BadDebt 0: fullyp^id 1 0 0 0 1: 1to30days O.7 0.2 OJ 0 inarrears 2: 31to60days O.5 0.1 0.2 0.2 inarrears 3: baddebt 0 0 0 1 Althougheachcustomerendsupinst^te0or3,thestoreisinterest亡lIindeterniiningtheprobabilitythatacustomerwillendupas,baddebtgiven(hattheaccountbelongstotheIto30daysinarrearsstate,andsimilarly,giventhattheaccountbelongstothe3]to60daysinarrearsstate* Tdobtainthisinformation,thesetofequationspresentedatthebeginningofthisseedonmustbesolvedtoobtainypandBysubstituting,thefollowingtwoequationsareobtained: fl3=P10f03+Pllfi3+P12f23+Pl加 fl3=/? 20/)3+P2tfi3+Pllfn+Pishy NotingThat°andfyy=I.wenowhavetwoequationsintwounknowns,namely, (1一Pl])/13=P\3+Pi述琳 (1一/>22)/23=P对+Plyf13- Substituringthevaluesfromthetransitianmatrixleadsto 0+gfi3=0・lfm O.8/23=0・2+0.1/13, andthesolutionis /15=0.032, f23=0-254, Thus,approximately3percentofdiecustomerswhoseaccountsart1to3()ciiiysmiLr-rearsendupasbaddebt^.whereasabout25percentofrhecus
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 作业题 整理 分解
![提示](https://static.bingdoc.com/images/bang_tan.gif)