运筹学基础及应用第四版胡运权主编课后练习答案.doc

运筹学基础及丨、V:用习题解答习题一 P461.1(a)2 = 3。 (b)用亂解法找+到满足所打约柬条仲的公：it范W，所以该问题无可行解。1.2(a) 约束方程组的系数矩阵M2 36 300A =8 1-4 02013 00 00-b基基解是否基可行解目标函数值A入2太34入*5太6PPiIh06T76000否PPiPa0100700是10PP2Ps0300720是3P Pi Po1 -4 400021T否P P3 Pa0 05 一 2800P ih l)s0 032080是3P P3 P61 0 -i 0 0 32否P Pa Ps0 003500P Pa Pe1 0 40-205T否最优解 A. = (o，iao,7，o，o)r(b)约束方程组的系数矩阵 f I 2 3 4、4 = l2 2 I 2,基基解X x2 x3 x4是否基可行解目标函数值P P2-40 0 2否Pi P31 o ii 05 5是43TP Pa-i 0 o H3 6否Pi Pi0-202是5Pi Pa P3 !U0 - 0 2 2(J 0 丨 1否是5最优解1 = (,0，11，0 V5 5 )1.3(a)(1)图解法技术官员村位于位于亚运城东部，主干道二以东石楼涌以西的地块，占地面积、m2，总建筑面积、m2，共包括地下室南区、地下室北区、地上部分1栋12栋、服务中心、室外工程等多个单体工程。其中住宅面积m2，共12栋，17栋建筑层数为11层，812栋11层（局部复式顶层），首层局部架空，布置公建配套设施。integrated energy, chemicals and textile Yibin city, are the three core pillars of the industry. In 2014, the wuliangye brand value to 73.58 billion yuan, the citys liquor industry slip to stabilise. Promoting deep development of integrated energy, advanced equipment manufacturing industry, changning district, shale gas production capacity reached 277 million cubic metres, built the countrys first independent high-yield wells and pipelines in the first section, the lead in factory production and supply to the population. 2.1-3 GDP growth figure 2.1-4 Yibin, Yibin city, Yibin city, fiscal revenue growth 2.1.4 topography terrain overall is Southwest, North-Eastern State. Low mountains and hills in the city landscape as the main ridge-and-Valley, pingba small fragmented nature picture for water and the second land of the seven hills. 236 meters to 2000 meters above sea level in the city, low mountain, 46.6% hills 45.3%, pingba only 8.1%. 2.1.5 development of Yibin landscapes and distinctive feature in the center of the city, with limitations, and spatial structure of typical zonal group, 2012-cities in building with an area of about 76.2km2. From city-building situation, old town-the South Bank Center construction is lagging behind, disintegration of the old city is slow, optimization and upgrading, quality public service resources are still heavily concentrated in the old town together. Southbank Centre has not been formed, functions of the service area space is missing. Meanwhile, peripheral group centres service was weak and inadequate accounting for city development, suspicious pattern could not be formed. As regards transport, with the outward expansion of cities, cities have been expanding, centripetal city traffic organization has not changed, integrated energy, chemicals and textile Yibin city, are the three core pillars of the industry. In 2014, the wuliangye brand value to 73.58 billion yuan, the citys liquor industry slip to stabilise. Promoting deep development of integrated energy, advanced equipment manufacturing industry, changning district, shale gas production capacity reached 277 million cubic metres, built the countrys first independent high-yield wells and pipelines in the first section, the lead in factory production and supply to the population. 2.1-3 GDP growth figure 2.1-4 Yibin, Yibin city, Yibin city, fiscal revenue growth 2.1.4 topography terrain overall is Southwest, North-Eastern State. Low mountains and hills in the city landscape as the main ridge-and-Valley, pingba small fragmented nature picture for water and the second land of the seven hills. 236 meters to 2000 meters above sea level in the city, low mountain, 46.6% hills 45.3%, pingba only 8.1%. 2.1.5 development of Yibin landscapes and distinctive feature in the center of the city, with limitations, and spatial structure of typical zonal group, 2012-cities in building with an area of about 76.2km2. From city-building situation, old town-the South Bank Center construction is lagging behind, disintegration of the old city is slow, optimization and upgrading, quality public service resources are still heavily concentrated in the old town together. Southbank Centre has not been formed, functions of the service area space is missing. Meanwhile, peripheral group centres service was weak and inadequate accounting for city development, suspicious pattern could not be formed. As regards transport, with the outward expansion of cities, cities have been expanding, centripetal city traffic organization has not changed,单纯形法首先在各约朿条件上添加松弛变铽，将问题转化为标准形式max z = 10a-, +5a2 +0x3 +0a43a-. +4 义2 + A3 = 9 si. 5a-j + 2x2 + a4 = 8则A，P4组成个猫=令A = ;c2 = 0得-站可行解a_ = (0.0.9,8)，山此列出初始单纯形表新的单纯形农为x2A, XoXA14 14_5_ _25M T?xi =，a-3 =0, a4q.qcO，表明已找到问题垴优解.(b)(1)图解法最优解即为严+2X2=24的解x=卩，2V最大值z: I Ai + X y = 5I 2 2 /17(2) 单纯形法苘先在外约朿条件.h添加松弛变M，将问题转化为标准形式 max z = 2.v, + x2 + Ox3 + 0.v4 + Oa5 5a2 + = 15 6.y, + 2x2 + .v4 = 24-3 + 7M -J 1 -2-5M 0 -M 0 02 *40 00 -o a:5、Q 0 一4(7,2 0,.v； o)Xx = X-该问题转化为max z = -3a, - x2 + .v2 - 2a3 + 0.v4 + (Xv5 2x | + 3a-2 - 3a2 + 4a3 +a4 =12攀MI4a| +x2 -A*2 -2a*3 5 =8 3a*, -x2 +x2 3a*3 = 6A*, A2，X2, x3，A-4 , A3 0-K约朿系数矩陴为2 3 -3 4 I 0 4 丨-1-2 0-13 -丨丨一3 0 0在A屮人为地添加两列单位向虽/7，2 3 -3 4 1 0 0 0 4 丨-1 -2 t) -1 丨 0 3-1 I -3 0 0 0 1令 max z= -3a-i - x2 +x2- 2.v3 + Oa:., + 0.v5 - Mx6 - Mx7 得初始单纯形表15最大a 4 = 0，x5SS Xi x2x4 x5 x6-2 0 0M -M4 10-I0 00 0 0(b) 在约朿条件中添加松弛变M或剩余变M，.R令a:3(jc30,.x；0)该问题转化为max z = 一3 - 5.v2 + x?- x? + 0,v4 + Ox5 x, + 2x2 + x- x-x4 =6 2.v, + x2 - 3jc3 - 3：3 + a*5 = 16 x2+ 5 a*3 一 5a*3 = 10 vpA：2，“x4，A5 0-I艽约柬系数矩阵为02 13-30-1 115-50 0v/ft A屮人为地添加两列单位向觉p7,12 1-1-10 10、2 13-30 100 115 -5 0 0 01、 /令 max z, = -3a*, 一 5,v2 + .v3 一 x3 + 0x4 + 0xs 一 Mxb - Mx1衍初始单纯形表-50 0 -M - MX. X, X, X, X, X, X, xn-A/ x616-M x7 10-3 + 2A/ 5 + 3M 1+6M -1-6M -M 0 0 0(a)解1:大1法在上述线性规划问题中分别减去剩余变萤x4，x6,再加上人工变蛩15，17，得 max z = 2xt - x2 + 2x3 + 0,v4 - Mxs + 0,v6 - Mx7 + 0a8 - MxA, + X2 + A：3 - + JC5 = 6-2xl + jc3 a*6 + x1 2 2xz jc3 - a*8 + jc9 =0 a-,.v2,a*3,j:4,a:5,6,x7,x8,a-9 0，r,其中MS个任意人的正数-据此可列出单纯形表22MMMjc, x2x4X5X6A-M xs 6 -M x7 一 2 M a、000000200M 02-M 3A/-1 2 + A/ -M1/2 -1/2 0 0 -1/2 -1/2xs-M x, I x11/20 5M 3 A/ I 1 3A/2-M0 + - M0 -M 0一十2 2 2 2 2 2-M jr5 32 .v3 2 -I x2 I3/2 -3/2 1/2 -1/2 -110 0 -1/2 1/2 -1/2 1/20 0 0 1 1 03/400?M +3 -5M -3 M-3M4Af+5 0M222-1/41/43/8-3/81/8-1/8-1/21/2-1/41/41/4-1/4-1/41/4一 1/81/8一 3/83/8x, 3/4 a3 7/2 7/4000105 | 433/8 - 8-998-5/4 -M8山单纯形表计算结果可以ft出，ct4 0且0 Pl -*y 其中M是个任意大的正数。据此可列出单纯形表M-MM4Jc#基办M x6 8 M x7 6M2-AM 3-6M I-2M1/4 15/2 01/2-1/41/21/4-1/25 X2 M xn3 M3MY-M 0MM3/5-2/5-3/10 1/10 3/10 一 1/10x2 9/5 a:, 4/51/5-2/5 -1/5 2/51/2 1/2 M-M2 Af-1/2山单纯形表计算结果可以fhh.最优解欠=(|,|，0，0,0，0，0/ , 1=1标函数的垴优解值z* =2xl + 3x| = 7。父存在非变萤检验数cr3 = 0,故该线性规划问埋Yf无穷多鍛优解 解2:两阶段法。阶段的数学模耶min似:jc, + 4x2 + 2x3 一 a*4 + jc6 = 8 3.v, + 2x2 -xs + jc7 =6,v,，A ”v5，A，a.7，A ”vy 0 据此可列出单纯形表0a.242A X6023xt-4 -61/4 1 5/2 001/4-1/21/2 -1/4-1 1/284/5jv27-5/21/23/20x2 9/5 a*. 4/53/5 -3/10 1/10 3/10 -1/10 -2/5 1/5 -2/5 -1/5 2/500第阶段求得的最优解又別行标函数的最优值； =0。丨入1人:1:变跫jc6=a =0，所以（H，0，0,0，OO)1足原线性规划问题的骓可行解。于足可以进行第：阶段运箅。将第阶段的最终表屮的人工变M取消，井填入原问题的R标函数的 系数，进行第.：阶段的运箅，见下表。crz)231000丨cb bA又4义s3 a-2 9/5 2 jc, 4/50 1 3/5 -3/10 1/101 0 -2/5 1/5 -2/5ci_h0 0 0 1/2 1/2由单纯形表计算结果可以稽出，最优解；T=(|，|，0，0，0，0，0)T，R标函数的最优解值=2x- + 3x- = 7山于存在非基变罱检验数q = 0，故该线性规划问题荷无穷多最优5 53解。1.8表 1-23A文2太3文4AA-4624-210夂5 1-13 2 0 1C广3-12u0表 1-24Xl丨3文4尤531 2 -1 1/2 0夂5 10511/2IcJ-zi0-75-3/201.10354000xix2a3a4丨5x65 x28/32/3101/3000 a:514/3-4/305-2/3100 a:629/35/304-2/30Icjzj-1/304-5/300-i尤2人.3又.4丨5又.65 x28/32/3101/3004 a-314/15-4/1501-2/151/50max z= -4aj -12.v2 -18x3 十 0jc4 +0a5-17/15 -4/5义1 xia3又5x65 x2 50/410 10 丨 5/418/41-10/414 x3 62/410 01 -6/415/414/413 a-, 89/411 00 -2/41-12/4115/41czi0 00 -45/41-24/41一 11/4111/15最后-个表为所求。习题二 P762.1 写出对偶问题 (a)min z = 2a-! + lx2 + 4a3 + 3a2 + 4jc3 2 2.vt + x2 + 3.v3 + y4 3 + 4x2 + 3a-3 = 5 Aj,a-2之0，.v3无约朿max w = 2y +3.V2 +5y3 .Vi + 2.v2 +y3 2 对偶 M 题为：3_y, + y2 + 4v3 0, v2 3无约束 = 5,+3.v2+8y3 ,i 一.V2+4y3 =5 2y, +5.v2+7.y3 6 2-,-2+3*33 、无约束,2 0,3 0max z = 5a*, + 6x2 + 3a*3m.v, + 2x2 + 2x3 = 5-a, + 5a2 -jc3 3对偶问题为：4a、+ lx2 + 3jc3 正确。2.6对偶单纯形法 (a)min z = 4a、+12x2 + I8.V3 + 3.V3 3 sJ. 5Ai，尤2，久3 - 0解：先将问题改W为求Plfe函数极人化，并化为标准形式列单纯形表，尸fr对偶单纯形法求解，步骤如下ci -4 -12 -18 0 0Cft 湛 bAj A*2 X3 Xa X50 a4 -3 0 a5 -5-10-3 10 0 -2 -2 0 1cj-j-4 -12 -18 0 00 一 3-1 0 -3 1 0-12 x2 20 1 1 0 2cjzJ-4 0 -6 0 -6-18 a:3 10 1 - 03 3-12 丨 2 |- 1 0 - -3 3 2C； 一-2 0 0 -2 -6-Xi -3a-3 +x4 : -2a2 - 2jc3 + ;c5 Af 0(i = 1，.”，5)最优解为A= 0，丨目标值Z =39sj.min z 二 5a-, + 2义2 + 4jc33a_, +a-2 + 2a_3 4 10A*,.A：2.A3 0解：先将问题改h为求Mfe函数极人化，并化为称准形式max z= -5jc, -2a: 2 - 4.v3 +04 +0a5 -3a丨 _ JC2 _ 2A3 + A*4 = -4 sj. -6, -3a2 -5j 0(/ = 1，,5)列雄纯形表，Jil对偶单纯形法求解-5 -2-4 0 0Cff -基 bAj X2 X3 X50 -4 0 x5 -10-3 -1-2 10 -6 -3 -5 0 1cj_zj-5 -2-4 0 00 a-4 - 3-10 - 1 .3j 3, 10_2 X2 T2 1 - 0 上3 3cj-zj2 2 -1 0 - 0 - 3 3-4 a:3 -23 0 1-31一 2 x2 0_3 1 0 5-2ci_zi1 0 0-2 0maxSJ.cB 基b最优解为A = (ao，2f， R标值z = 8.2.8 将该问题化为标准形式：用单纯形表求浑2-1 10 0cB Si bX x2 x4 x50 a*4 6 0 义5 4in i 丨 io-12 0 0 1c广2-1100=2.V, A-2 +A-3 +Ojf4 +0a5 ,+ A2 + + x4 = 6 -A*, +2x2 + a*5 =4 A/ 0(/ = l, -.5)A：, x2 Jl3 A4 .V*5山于i 0，所以己找到最优解X * = (6,0,0,0,10)，n标函数侦=12(a) 令目标函数max z = (2 + 4) x +(-i +/l2) x2+C 1+/1,) xi1)令; = 4 = 0，将;反映到最终单纯形表屮ci 2+4 -丨丨 0 0cB 魅厶A-, JC2 A1, .V4 X52 + xA 61 1 丨 丨 00 a5 100 3 111CJZJ0 -3-A, 0表中解为最优的条件：-3 -幺0，-1 - 0 2 - Aj 1 令 =毛=0，将;反映到最终单纯形表中ci 2 -1 + A2 1 0 0cB 恶厶A24 A2c丨61II1 00v5 100311 Iczi0/l2 -3-1-2 01+3 0 0V5CHXl X2 AV.0 32 0表屮解为最优的条件：4 -丨幺0 ,从而;13 1(b)令线性规划问题为s.tmax z = 2x -x2- x3 at, + a:2 + a:3 6 + XA A*, + 2a*2 -6使M题最优站f、变的条件圮/T + Al/(2)同理有10 + A2(c) 山于Z 二（6,0，0，0，丨0)代入-& +2;v3 =62，所以将约朿条件减去剩余变爾后的方 程-;r, + 2x, - x6 = 2直接反映到最终单纯形表中cj42-11000cB bx x2 x3Axs2 A*,61111000 Xs100 3 11100 A*6-21 0 -20010 -3 -1-200对表屮系数矩阵进行初等变换，得Ci 2-11000CB bx, jt2AA62 A-,61 1 1100o x5100 3 11100 ,v6-80 -1 -3-10128丨利此增加约朿条件后，新的锒优解为10 8 22xt =一，i3 = ;，x5 =一.最仇m 为2.12(a)线性规划问题max z = 3| +.v2 +4a*3 6.V, +32 + 5a*3 45 sj. 3.v, + Ax2 + 5a-3 30 v.,A,a-, 0单纯形法求解最优解为(a、, x2，) = (5,0,3)，目称值 z = 27。单纯形法求解(a) 设产品A的利润为3 +A，线性规划问题变为羅 bA, Xl Xy -V4 xsx4 45 a5 306 3 5 10 3 4 5 0 1ci_zi3 + A, 1 4 0 0A-4 153 63 -1 0 1-12 1 1 0 I5 5 5CJZJ3 丨丨 4 - + /1 0 U - 5 5 5A 5 a3 31 - 0 - -3 3 30 1 1 丄一5 5CJ_ZJ A 八 丨 /I 3 A () 一 2 + 0 一一 一一 + 3 5 3 5 3max z = (3 + 又)a丨+ a.2 + 4a*3 6a-, +3a-2 +53 45 SJ. 3a-| +4a2 +5a3 30 ，a2，a3 之 0-/l都小于等于0，解得为保持最优计划不变，应使-2 + 1(b) 线性规划问题变为max z = 3a-, + x2 + 4.v3 + 3xA 6a-, + 3a2 + 5a3 + 8a4 45 3a1, + 4x2 +5a:3 + 2x4 0屯纯形法求解此时最优解为(aVa_2j3；)=(OA5)，目标值z = 20，小于原最优值刚t该种产品不值得 生产t(c) 设购买材料数量为y，则规划问题变为max 7. = 3a, + x2 + 4a3 - 0.4 v 6.v, + 3jc