运筹学 本复习资料

《运筹学》课程复习资料一、判断题：1.图解法与单纯形法即使求解形式不一样，但从几何上了解，二者是一致。[]2.线性规划问题每一个基本解对应可行解域一个顶点。[]3.任何线性规划问题存在并具备惟一对偶问题。[]4.已知yi*为线性规划对偶问题最优解，若yi*＞0，说明在最优生产计划中第i种资源已完全耗尽。[]5.运输问题是一个特殊线性规划问题，因而其求解结果也可能出现以下四种情况之一：有惟一最优解，有没有穷多最优解，无界解，无可行解。[]6.动态规划最优性原理确保了从某一状态开始未来决议独立于先前已做出决议。[]7.假如线性规划问题存在最优解，则最优解一定能够在可行解域顶点上取得。[]8.用单纯形法求解Max型线性规划问题时，检验数Rj＞0对应变量都能够被选作入基变量。[]9.对于原问题是求Min，若第i个约束是“＝”，则第i个对偶变量yi≤0。[]10.[]11.[]12.在允许缺货发生短缺存贮模型中，订货批量确实定应使因为存贮量降低带来节约能抵消缺货时造成损失。[]13.依照对偶问题性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具备无界解。[]14.在线性规划最优解中，若某一变量xj为非基变量，则在原来问题中，改变其价值系数cj，反应到最终单纯形表中，除xj检验数有改变外，对其它各数字无影响。[]15.单纯形迭代中添加人工变量目标是为了得到问题一个基本可行解。[]16.订购费为每订一次货所发生费用，它同每次订货数量无关。[]17.[]18.在物资价格有折扣存贮模型中，计算费用时必须考虑物资本身费用。[]19.若线性规划问题具备可行解,且可行解域有界,则该线性规划问题最多具备有限个数最优解。[]20.对一个有n个变量，m个约束标准型线性规划问题，其可行域顶点数恰好为个。[]21.检验数Rj表示非基变量xj增加一个单位时目标函数改变量。[]22.在求网络最大流问题中，最大流流量是惟一，但最大流不一定惟一。[]23.[]24.状态转移方程为状态变量和决议变量函数关系。[]25.任何线性规划问题一定有最优解。[]26.一旦一个人工变量在迭代中变为非基变量后，该变量及对应列数字若从单纯形表中删除，将会影响后面计算结果。[]27.影子价格是企业生产过程中资源一个隐含潜在价值，表明单位资源贡献，与市场价格是不一样两个概念。[]28.指派问题效率矩阵每一行（或每一列）元素分别减去一个常数，将不影响最优指派方案。[]29.任意可行流流量不超出任意割集割量。[]30.当订货数量超出一定值允许打折扣情况下，打折扣条件下订货批量要大于不打折扣时订货批量。[]31.Dijkstra算法(T、P标号算法)要求边长度非负。[]32[]33.在其余费用不变情况下，伴随单位存贮费用增加，最优订货批量也对应增大。[]34.运输问题用闭回路法和用位势法求得检验数不相同。[]35.容量网络中可行流是最大流充要条件是不存在发点到收点增广链。[]36.在其余费用不变情况下，伴随单位缺货费用增加，最优订货批量也对应减小。[]37.在任一图G中，当点集V确定后，树图是G中边数最少连通图。[]38.对偶问题对偶是原问题。[]39.求网络最大流问题可归结为求解一个线性规划模型。[]40.互为对偶问题，或者同时都有最优解，或者同时都无最优解。[]二、建模题：1.某炼油企业为提升炼油能力和增加企业经济效益，经研究有五种技术改造投资方案可供选择，它们所需投资费用年收益如表1所表示。其中：方案1和方案2只能选择其中一个，不能兼而实现，而且，如选择方案2，则方案3必须同时选择，或者都不选择。现该企业可供支配资金总额为：第一年有650万元，第二年仅有460万元。技术推行结果要求最少应增加出油能力500桶/天，但又不得超出1100桶/天。为了确定该企业总经济效益最大投资方案，试建立该问题线性规划模型。表1投资方案表方案序号技改方案内容决策变量投资（万元）年收益（万元）第一年第二年1更新旧装置，提升炼油能力500桶/天X12002001002建造新装置，提升炼油能力1000桶/天X23001502003往新厂建输油管，提升炼油能力100桶/天X315050504往老厂建输油管，提升炼油能力50桶/天X410070305增加槽车运输能力，能提升出油20桶/天X55040202.某钢厂轧制薄铜板知卷宽度为100CM，现在要在宽度上进行切割以完成以下订货任务：24cm宽75卷，40cm50卷和32cm宽110卷，长度都是一样。试求处理切割方案线性规划模型，使切割剩下边料最少。3.写出下面线性规划问题对偶问题。4.写出下面线性规划问题对偶问题：三、填空题：1.某企业利用三种原料生产五种产品，其关于数据如表2，企业决议是这五种产品各生产多少使企业赢利最大。表2产品原料万件产品所用原料数（千克）资源量（千克）ABCDE甲乙丙0.510.500.50.50－0.51.510.5111151210.5万件产品利润（万元）41051010.5已知该问题建立线性规划模型最优单纯形表如表3所表示，依照提供信息完成填空。表3cj41051010.5000CBXBx1x2x3x4x5x6x7x8b10.5010x5x7x4121012000.25-0.5-1.50011-1.5-0.5-1010-201101.250.5－Z-1.5-1-5.500-10-101)该问题最优解。2)目标函数值。3)设y1,y2,y3为对应对偶变量，则y1,y2,y3含义可表述为：。4)对偶问题最优解是。5)企业关键资源是。2.已知某求极大值（Max型）线性规划问题初始单纯形表及最终单纯形表以下，依照表中提供信息及单纯形表迭代规律完成填空。Cj41500CBXBx1x2x3x4x5bθ0x43141080000x5214013000－Z415000……0x40-1/2-21-3/235004x11a201/2b－Zc-1d0e-60001)该规划问题初始基本可行解为。2)初始单纯形表中，若选变量x3入基，则出基变量为，目标函数增加值为。3)单纯形表迭代时，围绕主元，经过线性变换需把入基列变成。4)最终单纯形表中，基变量为。5)最终单纯形表中，系数a＝。6)最终单纯形表中，x1值b=。7)最终单纯形表中，检验数c=,d=,e=。3.已知某线性规划问题用单纯形法计算时得到初始单纯形表及最终单纯形表见下表，依照单纯形表迭代规律完成填空。cj2－11000CBXBx1x2x3x4x5x6b000x4x5x63111－1112－1100010001601020－Z2－110000……0x40a11－1－2b2x1c00.501/21/2dex201－1.50－1/21/2f－Z0gh0－3/2－1/2i1)最终单纯形表中基变量为。2)最终单纯形表第一行，a=，b=。3)最终单纯形表第二行，c=，d=。4)最终单纯形表第三行，e=，f=。5)目标函数行，g=，h=，i=。4.下面为一线性规划模型（Max型）迭代过程中某一单纯形表，表中CB列表示对应基变量价值系数。Cj行表示各变量价值系数。（）（）（）（）（）4（）102-1206（）01-1130-Z0-30-2-2-260要求：1)把单纯形表中空格补充完整。2)基本可行解为：X*＝（）T。3)目标函数值为：Z＝（）。4)当前基本可行解是否是最优解。（）[注：填是或不是]四、计算题：1.对于线性规划模型，请先把模型化成标准型，然后用单纯形表迭代求其最优解。2.某厂从国外引进一台设备，由工厂A至G港口有多条通路可供选择，其路线及费用如图1所表示。现要确定一条从A到G使总运费最小路线，请将该问题描述成一个动态规划问题，然后求其最优解。AAB1C2G2030图1B2C1C3D11D217060504000304030103.已知某运输问题供输关系及单位运价表以下表示：产地销地B1B2B3产量A14258A23537A31324需求量485①列出产销平衡表，并用行列差值法给出该运输问题初始基可行解。②用位势法求初始可行解对应各非基变量检验数。③求出该运输问题最优解。4.把以下线性规划问题化成标准型，然后用单纯形法求最优解及目标函数值。5.求下面网络节点1到节点7最短路径。vv2v3v4v6v7v14655567v5418126.某商店拟购进一个应时商品出售。经估算，在未来旺季中每出售一箱可净得利润5000元，如旺季过后则只能削价出售，每箱要赔本元。这种商品需求情况经统计分析，具备以下分布规律：需求量（箱）012345概率P（R）0.050.10.250.350.150.1现商店经理需作出订购该商品多少箱决议，其最优决议是订购多少箱？赢利期望值为多大？最小损失期望值又是多大？7.求图中最小树及最小树权。55v1v2v3v4v6v7v8v5654562783334418.某企业打算在三个不一样地域设置4个销售点，依照市场预测部门估量，在不一样地域设置不一样数量销售店，每个月可得到利润如表1所表示。试问在各个地域应怎样设置销售点，才能使每个月取得总利润最大？其值是多少?表1销售店利润地域012341016253032201217212230101416179.某企业每年需电感5000个，每次订购费50元，存贮费为1元/个·年，不允许缺货。若采购少许电感每个单价3元，若一次采购1500个以上则每个单价1.8元，问该企业每次应采购多少个？10.某地电力企业有三个发电站，它们负责5个城市供电任务，其输电网络如图4所表示。由图可知，城市8因为经济发展，要求供给电力65MW，三个发电站在满足城市4、5、6、7用电需要量后，它们还分别剩下15MW、10MW、40MW，输电网络剩下输电能力见图4节点上是数字。三个发电站在满足城市4、5、6、7用电需要量后，剩下发电能力共有65MW，与城市8用电量刚好相等。问：（1）输电网络输电能力是否满足输电65MW电力；（2）如不满足，需要增建或改建那些输电线路?4545101520203015401540MW15MW1010MW21346578图411.加工制作羽绒服工厂预测下年度销售量为15000件。准备在整年300个工作日内均衡组织生产。假如为加工制作一件羽绒服所需各种原材料成本为48元，又制作一件羽绒服所需原料年存贮费为其成本22％。提出一次订货所需费用为250元，订货提前期为零，不允许缺货，试求经济订货批量及订购周期。12.设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可选择，而进口港又有三个可选择，进口后可经由两个城市抵达目标地，其间运输费用如图所表示（单位：百元），试把该问题描述成一个多阶段决议问题，并用动态规划方法求解。202040307040203010405603030303040401050AB1B2B3C1C2C3D1D2E13.试用表上作业法求解下面运输问题最优解。（要求用行列差值法给初始解，用位势法求检验数。）销地产地B1B2B3供给量A16424A28575需求量33314.某建筑工地每个月需求水泥量为1200吨，每吨定价为1500元，不允许缺货。设每吨每个月存放费为价格2％，每次订货费为1800元，需要提前7天订货。试求经济订购批量、每个月总费用和再订货点。《运筹学》课程复习资料参考答案一、判断题：1.√2.×3.√4.√5.×6.√7.√8.√9.×10.√11.╳12.√13.×14.√15.√16.√17.√18.√19.×20.×21.√22.√23.√24.√25.╳26.×27.√28.√29.√30.√31.√32.×33.×34.×35.√36.×37..√38.√39.√40.√二、建模题：1.见教材1.2节线性规划问题建模。2.解：设在100cm宽薄铜板上能切割40㎝宽薄铜板U个，32㎝宽薄铜板V个，24㎝宽薄铜板W个，则有以下切割方式：UVW余料<24①20020②1114③10212④0304⑤02112⑥01220⑦0044设xj为上述第j种切割方式切割100㎝铜板数，有：3.其对偶问题为：或4.对偶问题为：三、填空题：1.X＝(0,0,0,0.5,10,0,1.25)T。Z＝110。y1,y2,y3分别为甲、乙、丙三种资源出售带来价值增值（或利润）。。甲、丙资源。提醒：若原问题是Max型，则对偶变量值为对应松弛变量检验数负值。2.1）（0,0,0,8000,3000）T2）x537503）单位列向量4）x4，x15）-1/26）15007）0-3-2提醒：求该题时注意：（1）单纯形表中基变量系数列向量为单位列向量，检验数为0。（2）依照单纯形表计算公式求出各变量xj检验数，由计算目标函数值或某个基变量值。（3）在最优单纯形表中，松驰变量x4,x5两列系数向量为当前基逆矩阵B-1，由（向量b为初始单纯形表中方程右边常数向量），也可求出基变量值。如此题：3.1）x4,x1,x22)0103）1154)-155）0-1.5-254.（4）（2）（6）（0）（0）4（x1）102-1206(x3)01-1130-Z0-30-2-2-2601)单纯形表填空如上表示。2)基本可行解为：X*＝（20,0,30,0,0）T3)目标函数值为：Z＝（260）。4)是四、计算题：1.见教材1.4.5单纯形表。2.解：把问题分为4个阶段，A→B（可选B1,B2）,B→C（可选C1,C2）,C→D（可选D1,D2）,D→G各为一个阶段。设Sk为每一阶段起点，xk为第k阶段决议变量，状态转移方程为：SK+1＝xk(Sk)。k=1,2,3,4。阶段指标函数为Sk到xk(Sk)距离值，最优指标函数fk(Sk)为第k阶段状态为Sk时，从Sk到终点G最短距离值。指标函数递推方程：，k=3,2,1边界方程为：。下面列表计算以下：k=4时：x4S4x4GD13030GD24040Gk=3时：x3S3x4D1D2C10+30－30D1C240＋3030＋4070D1或D2C3－0＋4040D2k=2时：x2S2x4C1C2C3B170+3060+70－100C1B210＋7050＋4080C2k=1时：x1S1x4B1B2A20+10030＋80110B2最优路线有两条：A→B2→C2→D1→G或A→B2→C2→D2→G，最短距离值为110。3.①产大于销，增添假想销地B4，列出产销平衡表，用行列差值法给初始解以下表示：销地产地B1B2B3B4产量行差值A14（×）2（8）5（×）0（×）82,2,3A23（×）5（0）3（5）0（2）73,0,2A31（4）3（×）2（0）0（×）41,1,-需求量4852列差值2,2,-1,1,31,1,22,-②用位势法求初始可行解对应各非基变量检验数：对基变量有：Rij=cij－(ui+vj)=0，求出行、列位势，如表示：销地产地B1B2B3B4产量行位势A14（×）2（8）5（×）0（×）8u1=0A23（×）5（0）3（5）0（2）7u2=3A31（4）3（×）2（0）0（×）4u3=2需求量4852列位势v1=－1v2=2v3=0v4=－3利用Rij=cij－(ui+vj)求出非基变量检验数：R11=5，R13=5，R14=3，R21=1，R32=－1，R34=1。③选x32为入基变量，作闭回路调整，调整量为0，如表示：销地产地B1B2B3B4行位势A14（×）2（8）5（×）0（×）u1=0A23（×）5（×）3（5）0（2）u2=2A31（4）3（0）2（0）0（×）u3=1列位势v1=0v2=2v3=1v4=－2再次利用Rij=cij－(ui+vj)求出非基变量检验数：R11=4，R13=4，R14=2，R21=1，R22=1，R34=1。当前调运方案为最优方案，如上表示，最小运费Z＝2×8＋3×5＋1×4＝35。4.见教材1.4.5单纯形表。5.用T、P标号算法：①给v1点标P标号，其余点标T标号，为＋∞。②从v1点出发，修改v2、v3、v4点T标号，并把其中最小者改为P标号。T(v2)=4=P(v2)，T(v3)=6，T(v4)=5=P(v4)。③从刚才取得P标号点v2出发，可达v3,v5（与其相邻且还未取得P标号点）,修改其T标号，并把最小T标号v3,v5改为P标号。T(v3)=min{6，p(v2)+d23}=min{6,4+1}=5=P(v3)，T(v5)=11。④依这类推，各点P标号如图所表示。从v1到v7最短路为：v1→v2→v3→v5→v7或v1→v2→v3→v6→v5→v7，距离为16。44v2v2v3v4v6v7v14655567v541812105516016099556.解：由题意有：α＝5000元，β＝元由表中累计概率可知：最优决议是订购3箱。赢利期望值：E[C(Q)]＝－×3×0.05＋（5000－×2）×0.1＋（5000×2－×1）×0.25＋5000×3×0.6＝10800元。同理可计算出最小损失期望值为2950元。7.解：用破圈法求得最小部分树为：vv1v2v3v4v6v7v8v54233315最小部分树权为：1＋3+3＋3+2＋4+5＝21。8.解：设给每一个地域设置一个销售点为一个阶段，共三个阶段。xk为给第k个地域设置销售点数。Sk为第k阶段还剩下销售点数，S1＝4状态转移方程为：Sk+1=Sk－xkdk(xk)为在第k个地域设置xk个销售点增加利润。最优指标函数fk(Sk)为第k阶段把Sk个销售点时分给第k、k+1,…3个销售点获取最大收益。指标函数递推方程：，k=2,1边界方程为：。逆推计算以下：k=3时：S3=x3x3S3x3012340000110101214142316163417174k=2时：S3=S2－x2x3S3x201234000010＋1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312或3k=1时：S2=S1－x1x1S1x20123440＋3116＋2725＋2230＋1232＋0472最优决议方案为：第一个地域设置2个销售点，第二个地域设置1个销售点，第三个地域设置1个销售点，每个月可获总利润为47。9.R=5000(个/年)，co=50(元/次),ch=1(元/个·年)首先计算出经济订购批量：（个）分情况讨论：①设Q*=715，则每年订购7次，年费用为：F1=5000×3+50×7+（1×715）/2=15707.5元②设Q*=1500，则每年订购4次，年费用为：F1=5000×1.8+50×4+（1×1500）/2=9950元③设Q*=5000，则每年订购1次，年费用为：F1=5000×1.8+50+（1×5000）/2=11550元故应考虑折扣，该企业每次采购1500个以上，5000个以下。详细采购数量可视企业流动资金等详细情况而定。10.解：(1)虚构发点vs，如图示。(2)求出网络最大流如图示，最大流量为55，不满足输电65MW电力。(3)在饱和弧v5－v8上增建输送10MW新线路，使其容量增加到20MW，而把非饱和弧vs→v1→v4→v6及vs→v3→v6弧上各增加5MW流量，v6→v5弧上增加10MW流量，即可满足输电65MW电力需求量。vvs45,4510,1015,1520,1020,2030,1515,1040,10