运筹学部分课后习题解答

P47用图解法求解线性规划问题124x6x6122x,x02min2用图解法和单纯形法求解线性规划问题123x4x912s.t.5x2x812x,x02这时的最优值为z=1015335max22原问题化成标准型为1234ccjCB43[5]4jj0x21/50[14/5]1-3/5310x8/512/501/51CZ010-2jj5x3/2015/14-3/14210x110-1/72/7110x0000980025xx10b0053XxxxB4234CC-Z00-5/14-25/1jj4 (2)max22 (2)max22P78已知线性规划问题：12341234据对偶理论，直接求出对偶问题的最优解。解：(1)该线性规划问题的对偶问题为：41234(2)由原问题最优解为X*=(2,2,4,0)，根据互补松弛性得：〈334把X*=(2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不315253455minP79考虑如下线性规划问题：1233123(1)写出其对偶问题；(2)用对偶单纯形法求解原问题；解：(1)该线性规划问题的对偶问题为：123123(2)在原问题加入三个松弛变量x,x,x把该线性规划问题化为标准456123〈100x4c)jCB-80x3-40x2-60x10x60x5XBb0040506j00jxxxj0jxxxjj-2-1-2-40-5/4]-250010-1-3-2-80-1/2-35-80/30100-1/12-1/4-1/2-15-1/3-20/300100010-5/6-2/3-50/3-3-2-6001000100-2-4-311-1000000000xxx63max633P81某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。要求：(a)确定获利最大的产品生产计划；(b)产品A的利润在什么范围内变动时，上述最优计划不变；(c)如果设计一种新产品D，单品是否值得生产(d)如果劳动力数量不增，材料不足时可从市场购买，每单位元。问该厂要不要购进原材料扩大生产，以购多少为宜。CC可用量(单位)A产品B劳动力材料产品利润(元/件)6333415545解：由已知可得，设x表示第j种产品，从而模型为：j123123a)用单纯形法求解上述模型为：cc)jCB00Xx4x5j0443j34jxxjj1x2341-14/5-11/5-1/31-20x4100100-1/5-1/50x5010-1-4/5-1/3-3/54x3540100103x1633100b653xxjmaxx1cc)jC4-1/31-1/53入-3/5jj1-2-1/5jj5-1/3x0001x34053xxb4000XxxxBB23要最优计划不变，要求有如下的不等式方程组成立〈|__共55C)设产品D用x表示，从已知可得66B666_L5|||把x加入上述模型中求解得：6cc)jCB31x2-1/30x5-1/30x43x6b54x303x1XBx13011-1/5-4/50-20-1/5-3/5jj-1/60-1/6151-1/154/150-1/1-59/30-7/30-17/300jj00从而得最优解x*=(0,0,5,0,0,5/2)T；最优值为z=45+35=27.5>27max2P101已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。产地产地A1A2A3销量产量543912527销地BBBB2解：由已知和最小元素法可得初始方案为产地产地A1A250产量B20B4B3A35销量5151510由于有两个检验数小于零，所以需调整，调整一：产产地A1A25A3销量5产量5B20B3B40由于还有检验数小于零，所以需调整，调整二：产产地A1A25A3销量5产量5B25B3B40从上表可以看出所有的检验数都大于零，即为最优方案zmin产产地A1A2A3量7B3144B1865B2493B4273销地iji=1j=1销量为3，构成产销平衡问题，其对应各销地的单位运费都为0。B50003B2产量7B50003B2产量7B3B4地A18A18A26A3544239393销量10由上表和最小元素法可得初始方案为B53B37B53B37B4产量产地913913A2A3销量从上表可以看出所有的检验数都大于零，即为最优方案产地产地A18A25A36销量25B26M3B3389B4746B5578产量ii=1jj=1产量为20，构成产销平衡问题，其对应各销地的单位运费都为0。产地产地A18A25A36A40销量25产量B26M30B47460B33890B55780由上表和最小元素法可得初始方案为产地产地A1A2A3A4销量5产量B2B4B30B55由于有两个检验数小于零，所以需调整，调整一：产地产地A1A2A3A4销量5产量B2B4B30B55由于还有检验数小于零，所以需调整，调整二：产地产地销地B1B2B3B4B5产量A1A2A3A4销量500从上表可以看出所有的检验数都大于零，即为最优方案P127用割平面法求解整数规划问题。21212解：该问题的松弛问题为：122则单纯形法求解该松弛问题得最后一单纯形表为：ccjCB2-1/221-28/111-15/1bjj00009xx900XxxxxB4232341717112223224222322452从而有ccjCB970Xx2x1x5jjb-1/27x101009x210000x3-1/22-7/22-28/10x4-1/22-15/10x0010119x23010017x110070x300177XxXxCCZ000-1-8jj145416164xx=xx40x+xx=7747515747567BBx2x1x3x6j2x1x3x4j0x51-1/7-22/7-6/7-81-1-46-20x40-1/7-100010b377-4/734143x6000100117-7cjCB9700j9700j9x210000100000x300100001007x0100001000由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优xT，最优值为z=74+93=55maxP144用图解分析法求目标规划模型3440+10=503440+10=5011223x1+x2+d1--d1+=1111244211223344x1解:由下图可知，满足目标函数的满意解为图中的A点。P170求下图中的最小树P171用标号法求下图中点v1到各点的最短路。P173用Ford-Fulkerson的标号算法求下图中所示各容量网络中从vs到vt的最大流，并标出其最小割集。图中各弧旁数字为容量c，括弧中为流ij量f.ijB)由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整s3s4s51t2t23所以从v到v的最大流为：f*=1+2+5+3+2+1=14stst由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整s1s325s到v的最大流为：tTaa2a3b1b2b3c1号a1c2紧紧前作无a1a2无b1b2a1，b1a2，b2，c1业a3，b3，c2作作业代ABC