运筹学基础及应用 习题解答习题一 P461.1 (a)x244x 1 2x 243 2 1123 x 14x 1 6x 26该问题有无穷多最优解，即满足14x 1x 2 6且0 x 2的所有 x 1,x 2 ，此时目标函数值62z 3。
(b)x23 20 1 4x1用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。
1.2(a) 约束方程组的系数矩阵12 3 6 3 0 0 A8 1 4 0 2 03 0 00 01基基解是否基可行解目标函数值x 1xxxxx23456p 1pp2 30 16 3 - 760 0 0 否p10 0 7 0是101 pp24p 1p p250 3 0 07 2是3p1 p p2 6 7 21否4 0 0 04 4p1 p p3 4 0 0 528 0 0否p1 p p3 5 0 0 320 8 0是 3p1 p p3 6 1 0 120 0 3否p1 p p 0 0 0 3 5 0 是04 5p1 p p4 65 否150 0 2 04 4T最优解x 0,10,0, 7,0,0。
(b) 约束方程组的系数矩阵A 12223142基基解是否基可行解目标函数值x1 x x x2 3 4p1 p2 4 1120 0否p1 p3 2 11是0 05 5435p1 p4 1 11否0 03 6p2 p3 0 122 0是 5p2 p 40 120 2否p3 p 0 0 1 1 是 5 42 11 x ,0, ,05 5 T最优解。
1.3(a)(1) 图解法x243210 1 2 3 x1最优解即为3x15x14x22 x298的解3x 1,，最大值2z352(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式max z 10x1 5x20 x30x4s.t.3x15x14x22x2x3x498则P3 , P4 组成一个基。
令x1 x2 0得基可行解x 0,0,9,8 ，由此列出初始单纯形表c 10 5 0 0jc 基 b x1 x2 x3 x4B0 x3 3 4 1 090 x4 [5] 2 0 18c j zj10 5 0 01 。
2 min85,9385c 10 5 0 0 jc 基 b x1 x2 x3 x4 B0 x321514513510 x18512515c j z 0 1 0 2j0 2 ，min2114,8232新的单纯形表为c 10 5 0 0jc 基 b x1 x2 x3 x4 B5 x 2320 151431410 x1 11 0 1727c j zj 0 0514251431, 2 0，表明已找到问题最优解x1 1, x2 , x3 0,x4 0 。
最大值2*z352(b)(1) 图解法6x1 x22 24x2129x1 x25630 3 6 9 x1最优解即为6x1x12x2x2245的解7 3x , ，最大值2 2z172(2) 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式max z 2x x 0x 0x 0x1 2 3 4 55x x 152 3s.t .6x 2x x 241 2 4x x x1 2 55则P，P4 ，P5 组成一个基。
令x1 x2 0 3得基可行解x 0,0,15,24,5 ，由此列出初始单纯形表c 2 1 0 0 0jc 基 b x1 x2 x3 x4 x5 B0 x3 15 0 5 1 0 0 0 x4 24 [6] 2 0 1 00 x5 5 1 1 0 0 1c 2 1 0 0 0 j zj1 。
224 5 min , , 46 1c 2 1 0 0 0jc 基 b x1 x2 x3 x4 x5 B0 x3 15 0 5 1 0 02 x4 4 113160 x5 10 23161c 0 j zj 13 013 00 2 ，15 3 3 min , 24,5 2 2新的单纯形表为c 2 1 0 0 0jc 基 b x1 x2 x3 x4 x5 B0 x31520 0 1541522 x4721 0 014120 x5320 1 01432c j zj 0 0 014127 151 ，表明已找到问题最优解x1 1 ，x2 ，x3 ，x4 0，x5 0 。
最大, 2 02 2值* 17z21.6' '' ''(a) 在约束条件中添加松弛变量或剩余变量，且令x2 x x x 0, x 02 2 2 2，'x x3, z'3z该问题转化为max z' 3x1'x2''x22x ' 3 0 x40 x52x 1 '3x2 3x '' 2 '4x3x412s.t .4 '''x2''x2'x ,3x13x1x ,1x2x'x2' '', x ,2 22x'xx35'3x3,x4568其约束系数矩阵为2 3 3 4 1 0A 4 1 1 2 0 13 1 1 3 0 0在A 中人为地添加两列单位向量P7 ,P82 3 3 4 1 0 0 04 1 1 2 0 1 1 03 1 1 3 0 0 0 1' '' '令 4 5 6 7 max z'3x1 x x 2x 0x 0x Mx Mx2 2 3得初始单纯形表c 3 1 1 2 0 0 M Mj' '' 'c 基 b 1 x x x x4 x5 x6 x7xB 2 2 30 x4 2 3 3 4 1 0 0 012M x6 4 1 1 - 2 0 -1 1 08M x7 6 3 1 1 -30 0 0 1c j z 3 7M 1 1 2 5M 0 M 0 0j(b) 在约束条件中添加松弛变量或剩余变量，且令' '' ' ''x x x x x3 3 3 3 0, 3 0 ，z' z该问题转化为' ''max z'3x 5x x x 0x0x1 2 3 3 4 5' ''x 2x x x x 61 2 3 3 4s.t.' ''2x x 3x 3x x 161 2 3 3 5' ''x x 5x 5x 101 2 3 3' ''x , x , x , x , x , x 01 2 3 3 4 5其约束系数矩阵为1 2 1 1 1 0A 2 1 3 3 0 11 1 5 5 0 0在A 中人为地添加两列单位向量P7 ,P81 2 1 1 1 0 1 02 13 3 0 1 0 01 1 5 5 0 0 0 1令' ''max z'3x 5x x x 0x 0x Mx Mx1 2 3 3 4 5 6 7得初始单纯形表c 3 -5 1 -1 0 0 -M Mjc 基 b x1 x2 x3 x3 x4 x5 x6 x7BM x6 61 2 1 -1 -1 0 1 00 x 1652 13 -3 0 1 0 0M x7 101 1 5 -5 0 0 0 1c j z 3 2M 5 3M 1+6 M-1-6 M-M 0 0 0j1.7(a)解1：大M 法在上述线性规划问题中分别减去剩余变量x4, x6 ,x8, 再加上人工变量x5, x7 ,x9 ,得max z 2x x 2x 0x Mx 0x Mx 0x Mx1 2 3 4 5 6 7 8 9x x x x x123456s,t,2x x x x213672x x x x02389 x,x,x,x,x,x,x,x,x0 123456789其中M是一个任意大的正数。
据此可列出单纯形表c2120M0M0Mji c基b x1x2x3x4x5x6x7x8x9bM x561111100006M x72201001100M x900[2]10000110c z2M3M12M M0M0M0j jM x56103/211001/21/24M x7220[1]0011002 1x02011/200001/21/2c z205300113M M M j jM M M222222M x53[4]00113/23/21/21/23/42x232010011001x12110001/21/21/21/2c z450003353113M M M M j jM M22222x3/411001/41/43/83/81/81/82x7/230011/21/21/41/41/41/41x7/420101/41/41/81/83/83/8c z0005/453/8399M M M j j4888由单纯形表计算结果可以看出，40且a i40(i1,2,3)，所以该线性规划问题有无界解解2：两阶段法。
现在上述线性规划问题的约束条件中分别减去剩余变量x4,x6,x8,再加上人工变量x5,x7,x9,得第一阶段的数学模型据此可列出单纯形表c000010101 ji c基b x1x2x3x4x5x6x7x8x9b1x651111100006 1x272010011001x090[2]10000110c z131101010j j1x65103/211001/21/24 1x2720[1]0011002 0x02011/200001/21/2c z105/2101013j j221x35[4]00113/23/21/21/23/4 0x232010011000x12110001/21/21/21/2c z000010101j j2x3/411001/41/43/83/81/81/82x7/230011/21/21/41/41/41/4 1x7/420101/41/41/81/83/83/8c z000010101j j第一阶段求得的最优解*377TX(,,,0,0,0,0,0,0)442,目标函数的最优值*0。
因人工变量x5x7x90，所以*377TX(,,,0,0,0,0,0,0)是原线性规划问题的基可442行解。
于是可以进行第二阶段运算。
将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。
c z2120000ij jc基b x1x2x3x4x6x8b2x3/411001/43/81/82x7/20011/21/41/4 31x7/40101/41/83/8 2c z0005/43/89/8j j由表中计算结果可以看出，40且a i40(i1,2,3)，所以原线性规划问题有无界解。