天津科技大学12财务管理(双学位)运筹学复习提纲三四题部分答案

112级财务管理（双学位）运筹学复习提纲三、四题部分答案三、根据资料回答问题（部分题答案）3.下面是一个求Max问题、约束条件用“≤”连接的L.P问题最优单纯形表格,其中x4、x5、x6为松弛变量。XBｂx1x2x3x4x5x6x12110201x33/2001104x510-20116σj-5000-40-9要求：(1)写出该问题及其对偶问题的最优解；(2)如能以代价5/2增添第一种资源一个单位是否值得，为什么？(3)如有人愿意向你购买第三种资源，应要价多少才合算，为什么？(4)是否有其它最优解，为什么？答案：(1)该问题的最优解X*=(2,0,3/2,0,1,0)T，Z*=5；对偶问题最优解Y*=(4,0,9)，ω*=5。(2)值得。因5/2＜4(该资源影子价格)，所以可以盈利。(3)要价至少要在9以上才合算。因为这样能盈利，否则不如自己组织生产。(4)有其它最优解。因为非基变量x2的检验为0，若令x2入基可得另一最优解（最优值不变），这样它和原最优解的线性组合均为最优解。4.已知下表是某一约束条件用“≤”连接的L.P问题最优单纯形表格，其中x4、x5为松弛变量。XBｂx1x2x3x4x5x35/201/211/20x15/21-1/20-1/61/3σj0-40-4-2要求：写出原线性规划问题的数学模型。答案：由题意已知原线性规划问题目标函数为Max（因σj≤0为最优），且c4、c5为0（松弛变量目标函数系数为0）。(1)根据1jjBjcCBP知：23131111ccc422110cc42610c23，得：123c6c2c10(2)根据511222151112632010BA|b10，得：012105A|b3110110(3)则原线性规划问题的数学模型为：12323123123MaxZ6x2x10xx2x53xxx10s.t.x,x,x025.已知L.P问题：12121212MaxZ10x5x3x4x95x2x8s.t.x,x0用单纯形法求得最终表如下所示。XBｂx1x2x3x4x23/2015/14-3/14x1110-1/72/7σj00-5/14-25/14试用灵敏度分析的方法判断（假定其它参数不变）：(1)目标函数系数c1在何范围内变动，上述最优解不变；(2)约束条件右端项b2在何范围内变化，上述最优基不变。答案：(1)因c1CB，根据crCB得cr变化范围：{}{},,,,jrjrjrjrjrjjjMax/a|a0cMin/a|a0，其中：,1rjrjaBA。则：{()()}{()()}125251Max-cMin--147147。即，1255c42；亦即，11525c42时，最优解不变。(2)令原解()()-1iBiiixXBbb，得br的变化范围为：{}{}iirirriiririiMaxb/a|a0bMinb/a|a0，其中：1iriraB。则：{}{()}2233Max1bMin7214。即，27b72；亦即，29b152，最优基不变。四、求解下列各题（部分题答案）1.用表上作业法求下面运输问题的最小费用方案销地产地B1B2B3B4产量A1291079A213425A384257销量38463答案：(1)用Vogel法求初始解：销地产地B1B2B3B4产量差额A129107952222A21342511———A3842572221—销量384621差额1123—123—582—5—2—9—7(2)用位势法求检验数：销地产地B1B2B3B4产量UiA129310790A241-132425-5A311842357-5销量384621Vj2977(3)用闭回路法调整并进一步求检验数：销地产地B1B2B3B4产量UiA129310799A2513341253A3118423574销量384621Vj-70-2-2所有检验数均为大于零，已得最优解（退化解），基变量：*11x3，*12x0，*14x6，*22x5，*32x3，*33x4；其余非基变量：均等于零。最小总运费：Z*=832.用表上作业法求下面运输问题的最小费用方案销地产地B1B2B3B4产量A1518512A2241314A336744销量96874答案：(1)用伏格尔法确定初始初始方案如表一所示，表中带○的数字为初始基可行解。表1：B1B2B3B4产量差额A15185126044005—⑥⑥A224131460111———⑥⑧A33674410111144③①销量9306080710差额136113——11————12————1——————1——————4(2)用位势法（位势值见表2）计算检验数加以判别（即表中不带○的数字）。表2：位势值Vj4135UiB1B2B3B40A151851⑥5⑥-2A22413⑥5⑧0-1A33674③65①所有的检验数均大于等于0,已得最优解x12=6，x14=6，x21=6，x23=8，x31=3，x34=1；x11=x13=x22=x24=x32=x33=0；最小运输费用=6×1+6×5+6×2+8×1+3×3+1×4=69。(3)但空格x24的检验数为0，该问题为多重解，令其为调入格用闭回路法调整，得另一最优解：B1B2B3B4A15185⑥⑥A22413⑤⑧①A33674④3.用图解法求出目标规划问题的满意解(1)1122323441211122233124412iiMinZPdPdP8d5dPdxxdd100xdd80xdd55s.t.xxdd90x,x0;d,d0,i1,2,3,4(2)1122312111222123312iiMinZPddPdxxdd1x2xdd4s.t.6x4xdd50x,x0;d,d0,i1,2,35答案：(1)E点为满意解，即x1=80，x2=55。O102030405060708090100110102030405060708090100x1+x2=90x1+x2=100x1x2x1=80x2=55+1d-1d+2d-2d-3d+3d+4d-4dABDCE(2)4.对整数规划：12121212MaxZ8x5x2x3x12s.t.2xx6x,x0,整数解得其松弛问题最优表如下：cj8500CBXBbx1x2x3x45x23/2011/4-1/48x115/4101/83/8σj75/200-9/4-7/4要求：用割平面法完成求解过程。答案：(1)产生高莫雷约束：根据Max{fi}，应选取x1所在行为源行：134133xxx3884，即，134133x0x0x3884。产生高莫雷约束为：34313xx0488。(2)将高莫雷约束加入松弛变量x5，写入原表最后一行并用对偶单纯形法求解：1234567891011x1654321x20d3+d3-d2+d2-d1+1xx214x2x21504x6x21满意解x1=1;x2=06cj85000θCBXBbx1x2x3x4x55x23/2011/4-1/408x115/4101/83/800x5-3/400-1/8-3/81→σj75/200-9/4-7/4↑05x22011/30-2/38x13100010x42001/31-8/3σj3400-5/30-14/3b列均为正整数，所有σj均非正，已得最优整数解：X*=(3,2)T，Z*=34。5.有五辆卡车，需完成五项运输任务，不同卡车完成各任务的收益值不同（见下表）。求最大分配方案及最大总收益值。任务卡车甲乙丙丁戊A1518212425B1923221822C2617161919D1921231724E2623232425答案：设原矩阵为A，因求极大问题，令B=[M-aij]，其中M=Max{aij}=26，则：11852111074101073007348434015140041B091077091077099677539225317053060033210332B100000.0000321111m4n5lm41073117300107344150041441996708856996753663060.7300...7536021003211321131173541885663621或1173541885663621m=5=n，得最优解。7即，得解矩阵：*0001001000X100000010000001或*0000101000X100000010000010。即：A卡车→丁任务，B卡车→乙任务，C卡车→甲任务，D卡车→丙任务，E卡车→戊任务；或：A卡车→戊任务，B卡车→乙任务，C卡车→甲任务，D卡车→丙任务，E卡车→丁任务。最大收益值：26+23+23+24+25=121。6.某项工程的网络计划图如下所示（图例：()()A2工作代号持续时间）。要求：(1)用标号法求时间参数：ESi-j、EFi-j、LSi-j、LFi-j、TFi-j、FFi-j；(2)确定关键路线，计算工程完工期。答案：(1)时间参数()(2)关键路线由作TFi-j=0工作组成，即图中粗线，工程完工期29天。7.某项工程的网络计划图如下所示（图例：()()A15工作代号持续时间）。3245687B4C5D5E8F5G7H5I4J51A29K30002202646100610411154202112526126260292902207701515022220222202626077015150151612021071710122210T=29工程完工期29天ESi-jLSi-jTFi-jEFi-jLFi-jFFi-j3245687B4C5D5E8F5G7H5I4J51A29K38要求：(1)用标号法求时间参数：ESi-j、EFi-j、LSi-j、LFi-j、TFi-j、FFi-j；(2)确定关键路线，计算工程完工期。答案：(1)时间参数()(2)关键路线由作TFi-j=0工作组成，即图中粗线，工程完工期79天。12345678ABDEFGHI15151066130814C000151501515030300303553641541410717101516129301303004040040652546712540400414107171079790T=79ESi-jLSi-jTFi-jEFi-jLFi-jFFi-j12345678ABDEFGHI15151066130814C