2013上半年运筹学第一次作业.doc

一 填空题1.节点、箭线是网络计划图的基本元素。2. 一般的排队系统由 _输入过程_,排队规则_，_服务机构_组成。3.等待制的服务规有:_先到先服务_,_后到先服务_,_随机服务_,有优先权的服务_。4. _具有对策行为_的模型称为对策模型。5. 对策模型包含的基本要素有：_局中人_、_策略集_、_赢得函数_。二名词解释（1）策略：一局对策中，可供局中人选择的一个实际可行的完整的行动方案。（2）局中人：在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者。（3）主观概率：，是由决策者对事件的了解去确定，而这样确定的概率反映了决策者对事件出现的信念程度。（4）先验概率：是指根据以往经验或专家评估分析得到的概率。（5）决策树：有些决策问题，当进行决策后又产生一些新情况，并需要进行新的决策，又接着又有一些新情况，又需要进行新的决策，这样决策，情况，决策构成一个序列，这就是序列决策。描述序列决策的有力工具之一是决策树，决策树是由决策点，事件点及结果成的树形图。三解答题1.某厂有大量同一型号的车床，当这种车床损坏后或送机修车间或由机修车间派人来修理。已知该车床损坏率服从泊松分布，平均每天2台。又机修车间对每台损坏车床的修理时间为负指数分布的随机变量，平均每台的修理时间为1,天。但是一个与机修人员编制及维修设备好坏（即与机修车间每年开支费用K）有关的函数。已知K=0.1+0.001K（K1900）又知机器损坏后，每台每天的生产损失为400元，每个月工作天数为22天，试决定使该厂生产最经济的K及值。解：设机器损坏造成的生产损失S1；（2）机修车间的开支S2。要使整个系统最经济，就是要使S = S1 +S2为最小。以一个月为期进行计算如下：S1=（正在修理和待修机器数）（每台每天的生产损失）（每个月的工作日数）=S2 = K / 12 令 ，得 K=16430元 =17.65 2.某修理店只有一个修理工人，来修理的顾客到达次数服从泊松分布，平均每小时4人，修理时间服从指数分布，平均需6分钟，求：（1）修理店空闲的时间概率（2）店内有3个顾客的概率（3）店内至少一名顾客的概率（4）在店内顾客平均数（5）在店内平均逗留时间（6）等待服务的顾客平均数（7）平均等待修理的时间（8）必须在店内耗费15分钟以上的概率。解:本例可看成一个M/M/1/排队问题，其中（1）修理店空闲概率 （2）店内有3个顾客的概率（3）店内至少有1个顾客的概率（4）在店内的顾客平均数 Ls= /( - )=4/(10-4)=0.667人（5）在店内的平均逗留时间 Ws=1 =1/(10-4)=0.167h（6）等待服务的顾客平均数 Lq= / =4*0.4/(10-4)=0.267人 （7）平均等待修理(服务)时间（8）必须在店内消耗15分钟以上的概率P(T15)= exp(/4)=exp(-(10-4)/4)=exp(-1.5)=0.2232. 用线性规划求下列矩阵对策A=3-1-3-33-1-4-33解：求解问题可化成两个互为对偶的线性规划问题min（x1+x2+x3）3x1-1x2-3X3-3x1+3x2-1x3-4x1-3x2+3x3x1,x2,x3max(y1+y2+y3)3y1-1y2-3y3-3y1+3y2-1y3-4y1-3y2+3y3y1+y2+y3四证明题1. 证明如下序列不可能是某个简单图的次的序列：（1）7,6,5,4,3,2（2）6,6,5,4,3,2,1（3）6,5,5,4,3,2,1证明： 1. 已知定理：=2q,而在此序列中，=27，为奇数，所以此序列不可能为图的次的序列。又知定理：奇点的个数应为偶数，而在此序列中，奇点7，5，3为奇数个，所以此序列不可能为图的次的序列。2. 在序列中，奇点5，3，1为奇数个，所以此序列不可能为图的次的序列。3.对于七顶点的图，假定d(v1)=6,d(v2)=5,d(v7)=1,并假设G为简单图，则v1存在与其它六个点的连线（包含与v7）,v2与v1间存在边e12,而v7次为1，所以必不与v1外的其它点相连，因而v2 与除v1，v7外的四点间各有一连线。假设G（V，E）为简单位图，则余下的v3,v4,v5,v6中任一点（用vi表示）已确定存在ei,ei2，无ei7，对于d(vi)=5的该点来说，必与除 v7外的每