管理运筹学作业答案(韩大卫)MBA

运筹学作业答案-1-第1章线性规划基本性质P47P47P47P471111————1111（（（（2222））））解：设每天从i煤矿()2,1=i运往j城市()3,2,1=j的煤为ijx吨，该问题的LP模型为：()⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥=+=+=+=++=+++++++==∑∑==3,2,1;2,10200150100250200..85.681079min2313221221112322211312112322211312112131jixxxxxxxxxxxxxtsxxxxxxxcijijijijωP48P48P48P481111————2222（（（（2222））））⎪⎩⎪⎨⎧≥−≤−≥−+=0,)2(33)1(0..max21212121xxxxxxtsxxz31x-10（1）（2）1R2R2x解：Φ=21RR∩∵，则该LP问题无可行解。P48P48P48P481111————2222（（（（3333））））运筹学作业答案-2-⎪⎩⎪⎨⎧≥−≥−≥−−=0,)2(55)1(0..102min21212121xxxxxxtsxxz11x-50（1）（2）2xQZ=0Z=10-1P解：目标函数等值线与函数约束（2）的边界线平行，由图可知则该LP问题为多重解（无穷多最优解）。⎪⎩⎪⎨⎧==⇒⎩⎨⎧−=−=−4545550212121xxxxxx∵则10,45,45**1−=⎟⎠⎞⎜⎝⎛=zXT（射线QP上所有点均为最优点）P48P48P48P481111————2222（（（（4444））））⎪⎪⎩⎪⎪⎨⎧≥≤−≤+≤+−−=0,)3(22)2(825)1(1043..1110min2121212121xxxxxxxxtsxxz运筹学作业答案-3-1x2x（1）（2）（3）Z=011−=zQ解：由图可知Q点为最优点。⎪⎩⎪⎨⎧==⇒⎩⎨⎧=+=+713768251043212121xxxxxx∵则29,713,76**−=⎟⎠⎞⎜⎝⎛=zXTP48P48P48P481111————3333（（（（2222））））⎪⎪⎩⎪⎪⎨⎧≥≥−=++−−≥++≤+++++=0,1466473..243min2143213213214321xxxxxxxxxxxxtsxxxxz⇒⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=−=+−+−+=−−++=+−+++−+−−−=−=−=≥0,,,,,,,,14666473..2243max,1765//4/4//3/32171//4/4//3/3216//3/3215//3/321//4/4//3/321//4/44//3/331xxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxzxxxxxxx令自由变量看作一函数约束解：把P49P49P49P491111————5555运筹学作业答案-4-解：可行域的极点与基本可行解是一一对应的。解：可行域的极点与基本可行解是一一对应的。解：可行域的极点与基本可行解是一一对应的。解：可行域的极点与基本可行解是一一对应的。（（（（1111）对于）对于）对于）对于()TX8,0,0,7,92=，不满足约束条件，不满足约束条件，不满足约束条件，不满足约束条件8527454321=−−−+xxxxx，即，即，即，即()TX8,0,0,7,92=不是可行解，也就不是基本可行解，故不是该可行域的极点。不是可行解，也就不是基本可行解，故不是该可行域的极点。不是可行解，也就不是基本可行解，故不是该可行域的极点。不是可行解，也就不是基本可行解，故不是该可行域的极点。（（（（2222））））对于对于对于对于()TX0,20,0,15,51=，，，，是可行解是可行解是可行解是可行解。。。。此时基变量为此时基变量为此时基变量为此时基变量为421,,xxx，，，，由此得到的基矩阵为由此得到的基矩阵为由此得到的基矩阵为由此得到的基矩阵为0274131012=−−，所以，所以，所以，所以()TX0,20,0,15,51=不是基本解，也就不是基本可行解，故不是该不是基本解，也就不是基本可行解，故不是该不是基本解，也就不是基本可行解，故不是该不是基本解，也就不是基本可行解，故不是该可行域的极点。可行域的极点。可行域的极点。可行域的极点。（（（（3333））））对于对于对于对于()TX0,0,10,5,153=，，，，是可行解是可行解是可行解是可行解。。。。此时基变量为此时基变量为此时基变量为此时基变量为321,,xxx，，，，由此得到的基矩阵为由此得到的基矩阵为由此得到的基矩阵为由此得到的基矩阵为0174031112=−−，，，，所以所以所以所以()TX0,0,10,5,153=不是基本解不是基本解不是基本解不是基本解，，，，也就不是基本可行解也就不是基本可行解也就不是基本可行解也就不是基本可行解，，，，故不是该可故不是该可故不是该可故不是该可行域的极点。行域的极点。行域的极点。行域的极点。P50P50P50P501111————888811112222333344445555666677778888A(2.9)A(2.9)A(2.9)A(2.9)11111111111122220000000000000000100100100100B(2.1)B(2.1)B(2.1)B(2.1)11112222000000001111000022223333100100100100C(1.2)C(1.2)C(1.2)C(1.2)22220000333311114444666622220000100100100100余料余料余料余料00000.30.30.30.30.90.90.90.90.40.40.40.40.50.50.50.50.20.20.20.20.80.80.80.81.11.11.11.1解：设按第解：设按第解：设按第解：设按第j种截法下料种截法下料种截法下料种截法下料()8,,2,1⋯=jxj根，该问题的根，该问题的根，该问题的根，该问题的LPLPLPLP模型为：模型为：模型为：模型为：()⎪⎪⎩⎪⎪⎨⎧=≥≥+++++≥++++≥++++++++++=8,,2,10100264321003221002..min76543187521432187654321⋯jxxxxxxxxxxxxxxxxtsxxxxxxxxjω运筹学作业答案-5-第2章单纯形法P70P70P70P702222————1111（（（（2222））））解：标准化为⎪⎪⎩⎪⎪⎨⎧≥=++=++=++=0,,,,52426155..2max543215214213221xxxxxxxxxxxxxtsxxz，容易得()0,5,24,15,0,000==zXT第一次迭代：{}()121,2maxσ==则1x为进基变量（此时2x仍为非基变量）⎪⎩⎪⎨⎧=+=+=52461551413xxxxx⇒⎪⎩⎪⎨⎧≥−=≥−=≥=05062401515143xxxxx⇒⎪⎩⎪⎨⎧≤≤1562411xx则4x为进基变量，6为主元⎪⎪⎪⎩⎪⎪⎪⎨⎧=+−=++=+161324613115554242132xxxxxxxx此时：()8,1,0,15,0,4313186131422114224221==−+=+⎟⎠⎞⎜⎝⎛−−=+=zXxxxxxxxzT第二次迭代：0312=σ则2x为进基变量⎪⎪⎪⎩⎪⎪⎪⎨⎧≥−=≥−=≥−=032103140515252123xxxxxx⇒⎪⎪⎩⎪⎪⎨⎧≤≤≤3/213/14515222xxx则5x为进基变量，32为主元⎪⎪⎪⎩⎪⎪⎪⎨⎧=+−=++=+2323414613115554242132xxxxxxxx⇒⎪⎪⎪⎩⎪⎪⎪⎨⎧=+−=−+=−+23234127214121521545542541543xxxxxxxxx运筹学作业答案-6-此时：217,0,0,215,23,2721412173123412331831318225445442=⎟⎠⎞⎜⎝⎛=−−=−⎟⎠⎞⎜⎝⎛−++=−+=zXxxxxxxxzT此时0≤jσ，则217,23,27**=⎟⎠⎞⎜⎝⎛=zXT（图解法略）注意由方程组形式求的每个基本可行解与图解法求得的可行域的极点之间的一一对应关系。P70P70P70P702222————2222（（（（1111））））解：化标准形为：⎪⎩⎪⎨⎧≥=++−=++−+=0,,,25.01..22max432142132121xxxxxxxxxxtsxxzjc2200iθBCBXb1x2x3x4x03x11−11004x25.0−101jσ2222200,021=σ∵而它所对应的系数列向量()()TT0,05.0,11−−=α则该LP问题无最优解（无界解）。运筹学作业答案-7-补充作业：补充作业：补充作业：补充作业：求解下列LP问题：⎪⎪⎩⎪⎪⎨⎧≥≤−+≤+−≤+++−=0,,6033320422603..336max321321321321321xxxxxxxxxxxxtsxxxz解：标准化后求解过程如下：jc63−3000iθBCBXb1x2x3x4x5x6x04x603111002005x10（1111）1−20101006x20111−00120jσ63−300004x30045−13−030/461x1011−2010——06x100（2222）3−01−15jσ039−06−004x1000111−2−61x15101/201/21/23−2x501-3/20-1/21/2jσ00-9/20-9/2-3/20≤jσ∵，则最优解为：()75,0,5,15**==zXT运筹学作业答案-8-P70P70P70P702222————2222（（（（4444））））解：建立该LP问题的大M法辅助问题如下：⎪⎩⎪⎨⎧≥=+−+=+−++−−−−−=0,,,,,,223824..32max765432175216432176321xxxxxxxxxxxxxxxxtsMxMxxxxzjc2−3−1−00000000M−M−iθBCBXbbbb1x2x3x4x5x6x7xM−6x88881111（4444）22221−0000111100002222M−7x666633332222000000001−000011113333jσ24−m36−m12−mm−m−000000003−2x22221/41/41/41/411111/21/21/21/24/1−00001/41/41/41/400008888M−7x2222（5/25/25/25/2）00001−1/21/21/21/21−2/1−11114/4/4/4/5555jσ4525−m0000m−21432−mm−4323+−m00003−2x5900001111（3/53/53/53/5）10/3−1/101/101/101/103/103/103/103/1010/1−2−1x54111100005/2−1/51/51/51/55/2−5/1−2/52/52/52/5jσ0000000000002/1−1−/2/2/2/21−3x333300005/35/35/35/311112/1−1/61/61/61/61/21/21/21/21−/6/6/6/62−1x222211112/32/32/32/3000000001−/3/3/3/300001/31/31/31/3jσ0000000000001−/2/2/2/21−/2/2/2/2由于出现非基变量的检验数为0，故该LP问题有多重解。()TTXX3,0,2,0,59,54*2*1=⎟⎠⎞⎜⎝⎛=运筹学作业答案-9-则最优解为：()()()TTXXX3,0,210,59,541*2*1*µµµµ−+⎟⎠⎞⎜⎝⎛=−+=⎟⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎜⎝⎛−−=µµµ3359562()10≤≤µ7*=ω运筹学作业答案-10-P71P71P71P712222————2222（（（（5555））））解：目标函数化标准形为：43212maxxxxxz++−−=函数约束添加人工变量76