运筹学 本(复习资料)

《运筹学》课程复习资料一、判断题：TOC\o"1-5"\h\z图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。 []线性规划问题的每一个基本解对应可行解域的一个顶点。 []任何线性规划问题存在并具有惟一的对偶问题。 []已知y*为线性规划的对偶问题的最优解，若y.*>0,说明在最优生产计划中第i种资源已完全耗尽。 1 []运输问题是一种特殊的线性规划问题，因而其求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。 []动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。 []如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。 []用单纯形法求解Max型的线性规划问题时，检验数Rj>0对应的变量都可以被选作入基变量。[]对于原问题是求Min，若第i个约束是“=”，则第i个对偶变量yiW0。 []用大M法或两阶段法单屯形迭代中若人工变量不能出基人工变量的值不为0），则问题无可行解。[]如图中某点vi有若干个相邻点与其距离最远的相邻点为j,则边[vi,vj]必不包含在最小支撑树内[ ]在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。 []根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。 []在线性规划的最优解中，若某一变量xj为非基变量，则在原来问题中，改变其价值系数cj，反映到最终单纯形表中，除xj的检验数有变化外，对其它各数字无影响。 []单纯形迭代中添加人工变量的目的是为了得到问题的一个基本可行解。 []订购费为每订一次货所发生的费用，它同每次订货的数量无关。 []一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的选择。]在物资价格有折扣的存贮模型中，计算费用时必须考虑物资本身的费用。 []若线性规划问题具有可行解，且可行解域有界,则该线性规划问题最多具有有限个数的最优解。[]对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为。〃个。 []检验数Rj表示非基变量xj增加一个单位时目标函数的改变量。 ” []在求网络最大流问题中，最大流的流量是惟一的，但最大流不一定惟一。 []动态规划的基本方程是将一个多阶段决策问题转化为一系列具有递推关系的单阶段的决策问题。]状态转移方程为状态变量和决策变量的函数关系。 []任何线性规划问题一定有最优解。 []一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字若从单纯形表中删除，将会影响后面的计算结果。 []影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念。 []指派问题效率矩阵的每一行（或每一列）元素分别减去一个常数，将不影响最优指派方案。[]任意可行流的流量不超过任意割集的割量。 []当订货数量超过一定的值允许打折扣的情况下，打折扣条件下的订货批量要大于不打折扣时的订货批量。 []Dijkstra算法（T、P标号算法）要求边的长度非负。 []32目标函数极大化（MAX型）的指派问题，是将目标函数乘以“1工化为求最小值，再用匈牙利法求解[]在其他费用不变的情况下，随着单位存贮费用的增加，最优订货批量也相应增大。 []运输问题用闭回路法和用位势法求得的检验数不相同。 []容量网络中可行流是最大流的充要条件是不存在发点到收点的增广链。 []在其他费用不变的情况下，随着单位缺货费用的增加，最优订货批量也相应减小。 []在任一图G中，当点集V确定后，树图是G中边数最少的连通图。 []对偶问题的对偶是原问题。 []求网络最大流问题可归结为求解一个线性规划模型。 []互为对偶问题，或者同时都有最优解，或者同时都无最优解。 []二、建模题：某炼油公司为提高炼油能力和增加企业经济效益，经研究有五种技术改造的投资方案可供选择，它们所需的投资费用年收益如表1所示。其中：方案1和方案2只能选择其中一种，不能兼而实现，并且，如选择方案2,则方案3必须同时选择，或者都不选择。现该公司可供支配的资金总额为：第一年有650万元，第二年仅有460万元。技术履行的结果要求至少应增加出油能力500桶/天，但又不得超过1100桶/天。为了确定该公司总经济效益最大的投资方案，试建立该问题的线性规划模型。表1投资方案表方案序号技改方案内容决策变量投资（万元）年收益（万元）第一年第二年1更新旧装置，提高炼油能力500桶/天X 1 2002001002建造新装置，提高炼油能力1000桶/天X 2 3001502003往新厂建输油管，提高炼油能力100桶/天X 3 15050504往老厂建输油管，提高炼油能力50桶/天X10070305增加槽车运输能力，能提高出油20桶/天X 5 504020某钢厂轧制的薄铜板知卷宽度为100CM，现在要在宽度上进行切割以完成下列订货任务：24cm宽的75卷，40cm的50卷和32cm宽的110卷，长度都是一样的。试求解决切割方案的线性规划模型，使切割剩余的边料最少。写出下面线性规划问题的对偶问题。MinZ=5x+4x+3x'2x+7x>88x+5x-4x<15TOC\o"1-5"\h\z< 1 2 34x+6x=30x,x>0,x自由变量23 1写出下面线性规划问题的对偶问题：maxz=70x+30x'3x+9x<5401 25x+5x<450S.t< 1 29x+3x<72012x,x>0

三、填空题：某公司利用三种原料生产五种产品，其有关数据如表2,企业的决策是这五种产品各生产多少使企业获利最大。表2产品万件产品所用原料数（千克）资源量（千克）原料ABCDE甲0.510.500.55乙0.50一0.51.5112丙0.5111110.5万件产品利润（万元）41051010.5已知该问题建立的线性规划模型的最优单纯形表如表3所示，根据提供的信息完成填空。表3cj41051010.5000CBXBx1x2x3x4x5x6x7x8b10.5x512101200100x70.25-0.5-1.50011-1.51.2510x4-0.5-1010-2010.5-Z-1.5-1-5.500-10-101） 该问题的最优解。TOC\o"1-5"\h\z2） 目标函数值 。3） 设y],y2,y3为相应的对偶变量，则yi5y2,y3的含义可表述为：。4） 对偶问题的最优解是 。5） 企业的关键资源是。已知某求极大值（Max型）的线性规划问题初始单纯形表及最终单纯形表如下，根据表中提供的信息及单纯形表迭代规律完成填空。Cj41500C B_X B xxxxxbe0x43141080000x 5 214013000-Z4150000x40-1/2-21-3/235004x ] 1a201/2b-Zc-1d0e-60001）该规划问题的初始基本可行解为 TOC\o"1-5"\h\z2） 初始单纯形表中，若选变量乂入基，则出基变量为 ，目标函数增加值为 。3） 单纯形表迭代时，围绕主元：通过线性变换需把入基列变。4） 最终单纯形表中，基变量为。5） 最终单纯形表中，系数a=。6） 最终单纯形表中，x1的值b=—7） 最终单纯形表中，检验数＜2= ,d= ,e= 。已知某线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表见下表，根据单纯形表迭代规律完成填空。

cj2-11000CBXBx1x2x3x4x5x6b0 x4311100600 x51-12010100 x611-100120-Z2-110000……0 x40a11-1-2b2 x1c00.501/21/2de x201-1.50-1/21/2f-Z0gh0-3/2-1/2i1） 最终单纯形表中的基变量为。2） 最终单纯形表第一行，a=,b=。3） 最终单纯形表第二行，c=,d=。4） 最终单纯形表第三行，e=,f=。5） 目标函数行，g=,h=,i=。下面为一线性规划模型（Max型）迭代过程中的某一单纯形表，表中CB列表示对应基变量的价值系数。Cj行表示各变量的价值系数。cj( )( )( )( )( )cxxxxxxb4()102-1206()021-1130-Z0-30-2-2-260要求：1） 把单纯形表中的空格补充完整。2） 基本可行解为：X*=（ ）T。3） 目标函数值为：Z=（ ）。4） 当前基本可行解是否是最优解。（ ）［注：填是或不是］四、计算题：maxz=70x+30xf3x+9x<5401 2对于线性规划模型s，5气+5x2<450，请先把模型化成标准型，然后用单纯形表迭代求其最优解。',19x+3x<72012x,x>0

某厂从国外引进一台设备，由工厂人至仔港口有多条通路可供选择，其路线及费用如图1所示。现要确定一条从A到G的使总运费最小的路线，请将该问题描述成一个动态规划问题，然后求其最优解。图13.已知某运输问题的供输关系及单位运价表如下表示:产地\'一*、销地B1B2B3产量A4258a235371324需求量485列出产销平衡表，并用行列差值法给出该运输问题的初始基可行解。用位势法求初始可行解对应的各非基变量的检验数。求出该运输问题的最优解。4.把下列线性规划问题化成标准型，然后用单纯形法求最优解及目标函数值。minz—x-x+x-3xx+2x-2x—5⑴1 2 4x+x-x+2x—6⑵2 3 4 52x+x+3x+x—8⑶2 4 5 6x>0j求下面网络节点1到节点7的最短路径。

某商店拟购进一种应时商品出售。经估算，在未来旺季中每出售一箱可净得利润5000元，如旺季过后则只能削价出售，每箱要赔本2000元。这种商品的需求情况经统计分析，具有以下的分布规律：需求量（箱）012345概率P(R)0.050.10.250.350.150.1现商店经理需作出订购该商品多少箱的决策，其最优决策是订购多少箱？获利期望值为多大？最小损失期望值又是多大？求图中的最小树及最小树的权。某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如表1所示。试问在各个地区应如何设置销售点，才能使每月获得的总利润最大？其值是多少？某公司每年需电感5000个，每次订购费50元，存贮费为1元/个•年，不允许缺货。若采购少量电感每个单价3元，若一次采购1500个以上则每个单价1.8元，问该公司每次应采购多少个？某地的电力公司有三个发电站，它们负责5个城市的供电任务，其输电网络如图4所示。由图可知，城市8由于经济的发展，要求供应电力65MW，三个发电站在满足城市4、5、6、7的用电需要量后，它们还分别剩余15MW、10MW、40MW，输电网络剩余的输电能力见图4节点上是数字。三个发电站在满足城市4、5、6、7的用电需要量后，剩余发电能力共有65MW，与城市8的用电量刚好相等。问：（1）输电网络的输电能力是否满足输电65MW的电力；（2）如不满足，需要增建或改建那些输电线路？

加工制作羽绒服的工厂预测下年度的销售量为15000件。准备在全年的300个工作日内均衡组织生产。假如为加工制作一件羽绒服所需的各种原材料成本为48元，又制作一件羽绒服所需原料的年存贮费为其成本的22%。提出一次订货所需费用为250元，订货提前期为零，不允许缺货，试求经济订货批量及订购周期。设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可选择，而进口港又有三个可选择，进口后可经由两个城市到达目的地，其间的运输费用如图所示（单位：百元）试把该问题描述成一个多阶段决策问题，并用动态规划方法求解。试用表上作业法求解下面运输问题的最优解。（要求用行列差值法给初始解，用位势法求检验数。）" 销地产地B1B2B3供应量A16424A28575需求量33314.某建筑工地每月需求水泥量为1200吨，每吨定价为1500元，不允许缺货。设每吨每月的存储费为价格的2%，每次订货费为1800元，需要提前7天订货。试求经济订购批量、每月总费用和再订货点。

《运筹学》课程复习资料参考答案一、判断题:1.J2.X3.J8.J1.J2.X3.J8.J9.X10.J11.X12.J13.X18.J19.X20.X21.J22.J23.J28.J29.J30.J31.J32.X33.X38.J39.J40.J34.X5.X15.J25.X35.J26.X36.X7.J17.J27.J37..J二、建模题：见教材1.2节线性规划问题建模。解：设在100cm宽的薄铜板上能切割40cm宽的薄铜板U个，32cm宽的薄铜板V个，24cm宽的薄铜板可个,则有以下切割方式：UVW余料＜24①20020②1114③10212④0304⑤02112⑥01220⑦0044设％为上述第j种切割方式切割100cm铜板数，有：MinZ=20x+4x+12x+4x+12x+20x+4x2x+x+x>50x+3x+2x+x>110x+2x+x+2x+4x>752 3 5 6 7、乂分>0(j=1,7)其对偶问题为:

maxwmaxw=8y+15y+30y1 2 3'2yi+8y2=55y+4y<4J2 37yi-4y2+6y3<3y>0,y<0,y 为自由变量123对偶问题为：minw=540y+450y+720y[3y+5y+9y>70" '1 2 3J9y+5y+3y>301 2 3y,y,y>0123三、填空题：1.X=(0,0,0,0.5,10,0,1.25)t。Z=110。maxw=8y-15y+30y[2y-8y=5 ''1 2或-5y+4y<4次J2 37y1+4y2+6y3<3y>0,y>0,y为自由变量123y^yy3分别为甲、乙、丙三种资源出售带来的价值增值(或利润)。Y=(y,y,y)=(1,0,10)。甲、丙资源。3提示：若原问题是Max型，则对偶变量的值为相应松弛变量检验数的负值。2.1)(0,0,0,8000,3000)t 2)x5 3750 3)单位列向量4)x4,x15)-1/2 6)51500 7) 0-3 -2 4提示：求该题时注意：单纯形表中基变量的系数列向量为单位列向量，检验数为0。根据单纯形表的计算公式R=c-CP求出各变量xj的检验数，由Z=CX计算目标函数的值或某个基变量的值。 7 7 ^7 bb在最优单纯形表中，松驰变量x4,x5两列系数向量为当前基的逆矩阵B-1,由X=B-1b(向量b为初始单纯形表中方程右边常数向量)，也可求出基变量的值。如此题： BXB=B-1b=「1_0-3/21/2_「8000」_3000_=「3500」_1500_3.1)x4,x「x22)0103)1154)-155)0-1.5-254.cj(4)(2)(6)(0)(0)cXXXXXXb4(x1)1202-1206(X3)021-1130-Z0-30-2-2-260单纯形表填空如上表示。基本可行解为：X*=(20,0,30,0,0)t

3)目标函数值为：Z=(260)。4)是四、计算题:1.见教材1.4.5单纯形表。2.解：把问题分为4个阶段，A-B(可选B,B),B-C(可选C,C),C-D(可选D,D),D-G各为一个阶段。1 2 1 2 1 2阶段。设每为每一阶段的起点，xk为第k阶段的决策变量，状态转移方程为：S=xk(Sk)。k=1,2,3,4。阶段指标函数d(S,x)为0到.邕)的距离值，最优指标函数fk(Sk)为第即阶段状态为每时，从Sk到终点G的最短距离值。指标函数递推方程：f(S)=min{f(S)+d(S,x)}，k=3,2,1、，一，、“I厂/c\7/c八、kk k+1k+1 kkk边界方程为：f(S)=d(S,G)o xk 4 4 4 4下面列表计算如下：k=4时:k=3k=3时:叩七G)f4(S4)X4GD13030Gd24040GSx3d(S,x)+f(S)f3(S3)x^3 3 34 4D1D2C10+30—30D1C240+3030+4070D或D。C3—0+4040D2k=2时:—d(S,x)+f(S)2 2 2 3 3f2(S2)x4C 1 C 2 C 3 B1 70+3060+70—100C1 B □ 10+7050+4080C □ k=1时:d(S,x)+f(S)1 1 1 2 2f1(S1)X4B1B,A20+10030+80110B2最优路线有两条：A—B—C—D—G或A—B—C—D—G，最短距离值为110。3.①产大于销，增添假想销地B4，，列出产销平衡表,用行列差值法给初始解如下表示:',、•■■'销地产地'JrB1B2B3B4产量行差值A 1 4(X)2(8)5(X)0(X)82,2,3A 2 3(X)5(0)3(5)0(2)73,0,2A 3 1(4)3(X)2(0)0(X)41,1,-需求量4852

列差值2,2,-1,1,3 1,1,22,-列差值2,2,-1,1,3 1,1,22,-用位势法求初始可行解对应的各非基变量的检验数：对基变量有：Ri.=cij—(ui+vj)=0,求出行、列位势，如表示:项肖地产地B1B2B3B4产量行位势A4(X)2(8)5(X)0(X)8u=0——1 A——2 3(X)5(0)3(5)0(2)7u2=3A——3 1(4)3(X)2(0)0(X)4u3=2需求量4852列位势v=—1—1 v2=2v3=0v=—3 4 利用Rij=c『(Ui+Vj)求出非基变量的检验数：R11=5,R13=5,R14=3,R21=1，R32=—1，R34=1o选X32为入基变量，作闭回路调整，调整量为0,如表示：销地产地***、B1B2B3B4行位势A——1 4(X)2(8)5(X)0(X)u1=0A——2 3(X)5(X)3(5)0(2)u2=2A——3 1(4)3(0)2(0)0(X)u3=1列位势v1=0v2=2v3=1v=—2 4 再次利用Rij=cij—(ui+vj)求出非基变量的检验数：R=4,RJ=4,R=2,，R=1,R=1,R=1。11 13 14 21 22 34当前调运方案为最优方案，如上表示，最小运费Z=2X8+3X5+1X4=35。见教材1.4.5单纯形表。用T、P标号算法：给v点标P标号，其他点标T标号，为+8。从v1点出发，修改v2、v3、v4点的T标号，并把其中最小者改为P标号。T(v)=4=P(v),T(v)=6,T(v)=5=P(v)。从刚刚获得S标号的点v出发,4可达v,v4(与其相邻的且还未获得P标号的点)，修改其T标号，并把最TOC\o"1-5"\h\z小T标号v3,v5改为P标号。。 35T(v)=min{6,p(v)+d}=min{6,4+1}=5=P(v),T(v)=11。依此类推，各点的IP标号如图所示。 3 5Av至Uv的最短路为：v—v—v—v—v或v—v—v—v—v—v,距离为16。1 7 1 23571 23657

解：由题意有：a=5000元，8=2000元a5000 °…SSa+厂5000+2000—'由表中的累计概率可知：支p(x)=0.40V—^V±p(x)=0.75x=0 a+Px=0最优决策是订购3箱。X0.25获利期望值：E[C(Q)]=—2000X3X0.05+(5000—2000X2)X0.1+(5000X2—2000X1)X0.25+5000X3X0.6=10800元。同理可计算出最小损失期望值为2950元。解：用破圈法求得的最小部分树为：最小部分树的权为：1+3+3+3+2+4+5=21。解：设给每一个地区设置一个销售点为一个阶段，共三个阶段。x为给第k个地区设置的销售点数。kSk为第k阶段还剩余的销售点数，S1=4状态转移方程为：Sk=Sk—xkd(x)为在第k个地区设置x个销售点增加利润。最优指标函数fk(Sk)为第k阶段把Sk个销售点时分给第k、k+1, 个销售点获取的最大收益。指标函数递推方程：f(S)=max{f(S)+d(S,x)},k=2,1kk k+1k+1 kkk边界方程为：f(S)=d(S,x%… 3 3 3 3 3逆推计算如下：k=3时：S=xr3——3 f(S)=d(S,x)3 3 3 3 3f3(S3)乂③012340000110101

214142316163417174k=2时：S=S^xk=2时：S=S^x q q 322d(S,x)+f(S—x)2 2 2 3 2 2f2(s2)x201234000010+1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312或3k=1时：S=S—x*d(S,x)+f(S一x)111 21 1f1(S1)x20123440+3116+2725+2230+1232+0472最优决策方案为：第一个地区设置2个销售点，第二个地区设置1个销售点，第三个地区设置1个销售点，每月可获总利润为47。R=5000(个/年),co=50(元/次),ch=1(元/个•年)首先计算出经济订购批量:Q*==首先计算出经济订购批量:Q*==707(个)—v6—v6量。(3)在饱和弧v5—v8及vs—v3—v6弧上各增加5MW的流量，v6—v5弧上增加10MW的流量分情况讨论：设Q*=715，则每年订购7次，年费用为：F1=5000X3+50X7+(1X715)/2=15707.5元设Q*=1500，则每年订购4次，年费用为：F1=5000X1.8+50X4+(1X1500)/2=9950元设Q*=5000，则每年订购1次，年费用为：F1=5000X1.8+50+(1X5000)/2=11550元故应考虑折扣，该公司每次采购1500个以上，5000个以下。具体采购数量可视企业流动资金等具体情况而定。解：(1)虚构发点七，如图示。(2)求出网络的最大流如图示，最大流量为55，不满足输电65MW的电力。上增建输送10MW的新线路，使其容量增加到20MW，而把非饱和弧vs—v1—V4即可满足输电65MW的电力需求

解：R=15000件/年，Ch=10.56元/(件-年)，Co=250元/次。〜 ,2RC ：2x15000x250故经济订购批量：Q*= = =843(件/次)C\ 10.56[h订购周期：t*=g=[mcc=0.0562(年)R15000解：按决策的过程分为四个阶段。状态变量Sk为第k阶段的起点。xk为第k阶段的决策变量，状态转移方程为：S=\邕)。k=1,2,3,4。阶段指标函数d(S,x)为S至Ux(S)的距离值，最优指标函数f(S)为第k阶段状态为S时，火到终点kkkkkk kk k kE的最短距离值。指标函数递推方程：f(S)=min{f(S)+d(S,x)}，k=3,2,1边界方程为：f4(S4)