天津大学硕士研究考试复习题

./例9已知某线性规划问题用单纯形法迭代时,得到的中间某两步的单纯形表如表2.8。请将表中空白的数字填上。表2.8354000bx1x2x3x4x5x6<1>5x210000x505-100x60401Z0-400<2>5x24x33x1Z表2.9bx1x2x3x4x5x6x2010x3001x1100Z000例16某厂准备生产三种产品A,B,C,需消耗劳动力和原料两种资源,其有关数据如表2.15.表2.15.表2.15产品单位消耗资源ABC资源限量劳动力原料63534545〔单位30〔单位单位利润315<1>用单纯形法确定总利润最大的生产计划.<2>分别求出劳动力和原料的影子的价格.若原料不够,可到市场上购买,市场价格0.8问是否要购进,最多可购进多少?总利润增加多少?〔3当产品A,C的单位利润在何围变化时,最优生产计划不变？〔4劳动力可减少多少而不改变原最优计划？解<1>该问题的线性规划模型为s.t.其中分别为产品A,B,C的产量.用单纯形法迭代的最优表如表2.16所示表2.16因而最优生产计划为生产A,B产品均为0,生产C产品可使利润最大,最大利润为30.<2>劳动力和原料的影子价格分别为0和1.这说明在企业最优安排中,劳动里资源没有用完<实际用了30个单元>,而原料资源已耗尽.若原料市场价格0.8<影子价格1,因此应适量购进原料扩大生产.设购进的原材料数为,为保持最优基不变,必须有,而=解得因而最多可购进原料15单位,总利润增加.净利润增加15-0.815=3单位.〔3产品A<>在最优方案中是非基变量,设变化为则当〔为的检验数,即当时,原最优计划不变.产品在最优方案中是基变量,设变化为,要使最优计划不变,则所有非基变量检验数应非负,即即因此当产品C的单位利润时,最优计划不变〔4设劳动力减少,即右边常数列变化为,为使最优计划不变,则即所以即劳动力可减少15单位,原最优计划不变.〔实际上减去的是富余劳动力.例1某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使总的钻探费用为最小。若10个井位的代号为s1,s2,…s10,相应的钻探费用为c1,c2,…c10,并且井位选择上要满足下列限制条件：eq\o\ac<○,1>或选择s1和s7,或选择s8;eq\o\ac<○,2>选择了s3或s4就不能选s5,或反过来也一样；eq\o\ac<○,3>在s5,s6,s7,s8,中最多只能选两个。试建立这个问题的整数规划模型。例3某科研项目由三个小组用不同方法独立进行研究,它们失败的概率分别为0.40,0.60和0.80为了减少三个小组都失败的可能性,现决定暂派两名高级科学家参加这一科研项目,把这两个分配到各组后,各小组仍失败的概率如表4.4所示,问应如何分派这两各高级科学家以使三个小组都失败的概率最小?表4.4高级科学家人数小组1230120.400.200.150.600.400.200.800.500.30解<1>建立动态规划模型按小组数将问题划分3个阶段,阶段变量状态变量表示第阶段初可用于分配的科学家数,决策变量表示第阶段分配给第个小组的高级科学家人数.状态转移方程:允许决策集合:阶段指标过程指标函数因而基本方程采用乘积形式,即<2>采用逆序法求解:当=3时,因为<即尚未分配给第1和第2小组的全部分配给第3小组>.计算结果如表4.5所示.表4.50120120.800.500.30当=2时,计算结果如表4.6所示.表4.60120.480.300.180.320.200.160020.480.30.0.16当时,计算结果如表4.7所示.表4.7s1x1=0x1=1x1=220.0640.0600.07210.060由表4.7可知x1*=1,=0.060,由s1=1查表4.6可得x2*=0;由s3=1查表4.5得x3*=1.因而此问题的最优解为x1*=1,x2*=0,x3*=1.即把两名高级科学家分派到第1和第3两小组各一名,可使三个小组都失败的概率减小到0.060.0.800.48注：此问题还有一种更简捷的解法,将它化为最短路模型.即将各阶段状态作为结点,各小组失败的概率为弧线上的数据,见图4.1.然后在图上用逆序法计算,计算结果标于图上的方框.0.800.48S3=0S3=0S2=00.150.800.500.060.300.400.500.060.30S4=0S3=1S1S4=0S3=1S1=2S2=10.200.300.160.300.160.400.400.30S3=2S3=2S2=20.60图4.1由图4.1可知,整个项目失败的概率为0.060,最优路线为图中双线表示,即s1=2→s2=1→s3=1→s4=0,由此同样得出最优解为x1*=1,x2*=0,x3*=1.因此,所有一维资源分配〔离散型均可化为最短路问题来求解,在图上用逆序算法求解较简便.已知如表6.8中的资料,求该工程的最低成本日程。表6.8活动作业时间〔天紧前活动正常完成进度的直接费用〔百元赶进度一天所需费用〔百元abcdefgh48635743——baaab,de,f,g20301551840101554324736合计153工程间接费用5〔百元/天6.19解其网络图如图6.39所示.其中方框数据表示结点最早时间,三角形框数据表示结点最晚时间。关键线路为：①→③→④→⑤→⑥。方案一：正常进度完工的工程费用：工程费用=153+15*5=22800〔元。方案二：在方案一中,关键路线是①→③→④→⑤→⑥,且由表6.8中已知数据费用率<即赶进度一天所需费用>知,min{c13,c45,c56}={4,3,6}=3=c45,为此缩短关键工序g一天.工程费用=228+1*3-1*5=22600<元>.调整后,关键路线有3条：①③④⑤⑥;①③⑥;①②⑤⑥,工期为14天,见图：6.40。hheq\o\ac<△,11>faeq\o\ac<□,4>68eq\o\ac<○,1>eq\o\ac<○,3>eq\o\ac<○,2>eq\o\ac<○,5>eq\o\ac<○,6>eq\o\ac<○,4>eq\o\ac<△,0>eq\o\ac<□,0>beq\o\ac<□,8>ceq\o\ac<△,8>d34eq\o\ac<△,4>5e7eq\o\ac<□,11>3eq\o\ac<△,8>eq\o\ac<□,8>eq\o\ac<○,4>g3eq\o\ac<△,14>eq\o\ac<□,14>eq\o\ac<○,6>14141414图6.40图6.40在图6.40中各结点最早时间与最迟时间已相等,因而该项工程的最低成本日程以求出,为14天,方案二为最优方案。5.1解：〔1错。当一个矩阵对策的鞍点不唯一时,结论不正确。例如：〔2对。〔3对。〔4错。当矩阵对策有唯一的鞍点时,局中人采取纯策略。5.3解BA即P=用优超法化简得解得5.13表5.8YBby1y2y3s1s2s3y1y2y3100-010--001-W000表5.9YBby1y2y3s1s2s3y3y1y2001-100-010-W000例2某电子设备厂对一种元件的需求为R=2000件／年,订货提前期为零,每次订货费为25元.该元件每件成本为50元,年存储费为成本的20%,如发生供应短缺,可在下批货到达时补上,但是缺货损失费为每件每年30元.要求:①经济订货批量及全年的总费用；②如不允许发生供应短缺,重新求经济订货批量,并同①的结果进行比较.解①k=25,D=2000,=5020%=10,=30,则=.=115.②=.与①相比,②中的经济订货批量减少了,而全年的总费用增加了。3．离散型的报童问题例3某商店准备在新年前定购一批挂历批发出售,已知每售出一批〔100本可获利70元.如果挂历在新年前售不出去,则每100本损失40元,根据已往销售经验,该商店售出挂历的数量如表7.1所示.问一次订货几百本,使期望的获利数最大？表7.1销售量<100本>123456概率0.050.100.250.350.150.10解由公式,其中可得.所以一次应定购300本表8.4如果勘探费用需1万元,问〔1应先勘探还是直接钻井,〔2应该怎样根据勘探结果来决定是否钻井？解并求得：同理有故,不钻井为最优选择故,钻井为最优选择。日销售量〔件10000〔s120000<s2>30000<s3>40000<s4>销售概率0.150.300.350.20又企业的月最大生产能力为40000件,且通过调查知各种销售量状态下销路好与不好的概率如表8.6所示。Xs10000<s1>20000<s2>30000<s3>40000<s4>销路好0.30.50.70.8销路不好0.70.50.30.2X为销路,s为销量。试求EVPI.求在调查结果销路好与不好的生产方案。试求EVSI.例3某亭有一部,来打的顾客数服从泊松分布,相继两个人到达的平均时间为10分钟,通话时间服从指数分布,平均数为3分钟,求顾客到达亭要等待的概率等待打的平均顾客数当一个顾客至少要等3分钟才能打时,电信局打算增设一台机,问到达速度增加到多少时,装第二台机才是合理的？打一次要等10分钟以上的概率是多少？第二台机安装后,故可的平均等待时间是多少？解例4某航运局拟自己建设1个港口,据资料知货船按泊松流到达,平均每小时到达21条,卸货时间服从负指数分布,平均卸货时间为2分钟。每条船的售价8万元,每建设1个泊位需投资12万元,试问建设多少个泊位合理？解用线性规划方法求解下列对策问题。[解]<a>此问题无鞍点,支付矩阵无法用优势原则简化,对策双方各拥有3个策略,故用线性规划方法求解。将矩阵中各元素,分别加上3〔