运筹学基础及应用习题解答z 3。

(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。

(a)约束方程组的系数矩阵12 3 6 3 0A 8 1 4 0 23 0 0 0 0基基解是否基可行解目标函数值X1 X2 X3 X4 X5 X6P1 P2 P3163 7-60 0 0否P1 P2 P4 0 10 0 7 0 0 是10P1 P2 P50 3 0 0 72是 3习题一P46x i1-的所有X i,X2，此时目标函数值o(b)约束方程组的系数矩阵A 12 3 4A2 2 12⑻(1)图解法基 基解 是否基可行解 目标函数值X 1X 2X 3X 4P 1P 24 11否"2P 1P 3 2 0 110 是435 ~5~5P 1P 4111否—36P 2P 312是52P 2P 41否22P 3P 40 0 1 1是5最优解xT2 11 5吋omax z 10x 1 5x 2 0x 3 0x 4 3x i 4X 2 X 3st. 5x 1 2x 2 x 48 9 8 12。

min—,— — 5 3 5C j 105 0 0 C B基b X 1X 2X 3X 421143 0 X 3— 1—"5"5582110X 11C j 105 0 0 C B 基bX 1 X 2 X 3 X 4 0 X 3 9 341 0 0X 48[5] 20 1 C j Z j105令 X iX 20,0,9,8，由此列出初始单纯形表最优解即为3x1 4x2 9的解x5x 1 2x 2 81,-，最大值z 竺 2 2(2)单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式则P 3，P 4组成一个基。

得基可行解xC j Z j0 1221 8320，min14 22新的单纯形表为C j 105 0 0 C B基b X 1X 2X 3X 435 3 5X 2— 01— —2141410X 11121—7525c jZ j14 143*35x i 1, x 2 - , X 3 0, X 4 0。

最大值 z —2 25x 2 x 3 15 st. 6x 1 2x 2 X 4 24X i X 2 X 55表明已找到问题最优解最优解即为6x 1 x i2X2 24的解x x 2 5I ，最大值z 号（2）单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式max z 2x 1 x 2 0x 3 0x 40x 5(b则R , F 4, F 5组成一个基。

令X 1 X 2得基可行解x 0,0,15,24,5，由此列出初始单纯形表新的单纯形表为C B基bX 1X 2X 3X 4X 50 X 3 15 0 5 1 0 0 0 X 4 24 ⑹ 2 0 1 0 0 X 55111C j 2 10 0 02 10 0 0C j Z j C j2 1 00 0CB基bX 1X 2X 3X 4X 551X 315111 ——2X 443621X 510 —0 —136C jZ j1 01 0332 0,1 2。

min ,24,5 4 6 115 3 min —,24,— 5 2在约束条件中添加松弛变量或剩余变量，且令X 2 X 2 X 2 X 2 0,X 2 00 X sC j Z j1 41 40 0 0 -42_ 1 0,表明已找到问题最优解X 11， X 227一 ，X 3 215 —，X 40， X s 0。

最大2 X3 X 3, z' z该问题转化为max z' 3X 1 X 2 X 2 2X 3 0X 4 0X 5st.2x 1 3x 2 3x 2 4x 3 x 4 I 11I 4X 1 X 2 X 2 2X 3 X sI 11 I3x 1 x 2 x 2 3x 3 6IMI12其约束系数矩阵为在A 中人为地添加两列单位向量P 7,P 8令 max z'3X 1 X 2 X 20x 4 0X 5 M X 6 Mx y(b)在约束条件中添加松弛变量或剩余变量，且令X 3X 3 X 3 X 3 0,X 3 0 z' z该问题转化为X i , X 2, X 3, X 3, X 4, X 5其约束系数矩阵为表在上述线性规划问题中分别减去剩余变量x 4,x 6,x 8,再加上人工变量x 5, x 7,x 9,得max z 2x 1x 22x 30x 4Mx 50x 6Mx 70x 8Mx 9C j Z j3 7M 11 2 5M 0 M 0max z' 3x 15x 2X3X30x 40x 5st.X 1 2x 2 X 3I2x 1x 23x 3x-i x 25x 35X 3X 3 3x 3X 4 X51016在A 中人为地添加两列单位向量P 7,P 8令max 3X 15X 2X 3 X 30X 4 0X 5 M X 6 MX 7N X 2 X 3 X 4 X 52X I X 3 X 6 X 7 2 2X 2 X 3 X 8 X 9 0 X i ,X 2,X 3,X 4,X 5,X 6,X 7,X 8,X 9解2:两阶段法。

现在上述线性规划问题的约束条件中分别减去剩余变量X 4,X 6,X 8,再加上人工变量X 5,X 7,X 9,得第一阶段的数学模型s,t.由单纯形表计算结果可以看出，40且a i4 0(i 1,2,3)，所以该线性规划问题有无界解C j 0 0 0 0 1 0 1 0 1C b 基 b X 1X 2X 3X 4X 5X 6X 7X 8X 9i1 X 5 6 1 1 1 1 1 0 0 0 06 1 X7 2 2 0 1 0 0 1 1 0 01 X 9 0 0[2]111C j Z j1311111 X 5 6 1 0 3/2 1 1 0 0 1/21/ 24 1 x 7 2 2 0 [1] 0 0 1 1 0 020 x 2 0 0 1 1/2 0 0 0 0 1/ 2 1/ 2C j Z j 15/2110 132 21 X 5 3 [4] 0 0 1 1 3/23/21/2 1/ 2 3/40 X 3 2 2 0 1 0 0 1 1 0 0 0 X 2 1 111/ 2 1/ 21/2 1/ 2C j Z j 00 1 0112 x 1 3/4 1 0 0 1/ 4 1/ 4 3/8 3/8 1/8 1/ 82 X3 7/2 0 0 1 1/ 2 1/2 1/4 1/4 1/41/41 x2 7/411/41/41/81/83/8 3/8据此可列出单纯形表0 0 0 0 1 0 1 0 1C j Z j3 7 7第一阶段求得的最优解 X *(―, —, —,0,0,0,0,0,0) T ,目标函数的最优值4 4 2 C j Z j2 1 2 0 0 0 0iC b 基bX 1X 2X 3X 4X 6X 82 X 1 3/4 1 0 0 1/4 3/81/82 X3 7/2 0 0 1 1/2 1/4 1/4 1 x 2 7/411/41/83/8因人工变量x 5x 7x 90，所以X (-,丄，丄，0,0,0,0,0,0) T是原线性规划问题的基可4 4 2行解。

于是可以进行第二阶段运算。

将第一阶段的最终表中的人工变量取消， 并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。

现在上述线性规划问题的约束条件中分别减去剩余变量X 4, X 5,再加上人工变量 X 6, X 7,得第40且a i4 0(i 1,2,3)，所以原线性规划问题有无界解。

在上述线性规划问题中分别减去剩余变量X 4,X 6, X 8,再加上人工变量X 5, X 7,X 9,得z 2x 4 3X 2 X 3 0X 4 0X 5 M X 6 M X 7X i 4X 2 2X 3 X 4 X 683X I 2X 2 X 5 X 7 6X i ，X 2，X 3，X 4，X 5，X 6，X 7，X 8，X 9 097。

X 存在非基变量检验数 3 0，故该线性规划问题有无穷多最优解。

C j Z j 0 5/43/8 9/8 C j2 1 2 0 M 0 M0 MC b 基 bX 1 X 2X 3X 4X 5X 6 X 7iM x 6 8 1[4] 2 1 0 1 0 2 Mx 7 632113C j Z j2 4M3 6M1 2M M M 0 03 x 2 2 1/4 1 1/2 1/4 0 1/4 0 8 M X 72[5/2] 01 1/2 1 1/2 14/55 5 “ 1 3 1M 3M 3C j Z j——M 0 M -M4 22 4 22 43 x 29/50 1 3/53/10 1 /10 3/10 1/102 X 4/512/51/52/51/52/5C j Z j 0 0 0 1/2 1/2 M 1/2 M 1/2其中 M 是一个任意大的正数。

据此可列出单纯形表由单纯形表计算结果可以看出，最优解* 4 9 TX (― , —,0,0,0,0,0) T，目标函数的最优解值5 5由表中计算结果可以看出,min s,t.*4 z 2 —3 55现在上述线性规划问题的约束条件中分别减去剩余变量 X 4, X 5,再加上人工变量 X 6, X 7,得第X i 4x 2 2x 3 X 4 X 683x i 2X 2 X 5 X 7 6第一阶段求得的最优解 0。

X l ,X 2,X 3,X 4,X 5,X 6,X 7,X 8,X 9 0据此可列出单纯形表以进行第二阶段运算。

将第一阶段的最终表中的人工变量取消， 并填入原问题的目标函数的一阶段的数学模型minX 6 X 7s,t,*49 TX (-,-,0,0,0,0,0)，目标函数的最优值5 54 9 T0(一,,0,0,0,0,0)因人工变量x 6x 7z * 2 43 97。

由于存在非基变量检验数3 0,故该线性规划问题有无穷多最优55解。

表 1-23表由单纯形表计算结果可以看出，最优解X (4,-,0,0,0,0,0) T，目标函数的最优解值5 54 X3 14/15 4/15 0 1 2/15 15 0现在上述线性规划问题的约束条件中分别减去剩余变量X4, X5,再加上人工变量X6, X7,得第解: 先将问题改写为求目标函数极大化，并化为标准形式(a) 错误。

原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。

(b) 错误。

线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。

(C)错误。

(d)正确。

对偶单纯形法最后一个表为所求。

min z 2x 1 2X 2 4X 3max w 2y 13y25y 3X 1 3x 2 4x 32y 1 2y 2 y 3 st.2x 1 X 2 3x 3 y 4 3对偶问题为：3y 1 S ・t.y 2 4y 3X 1 4x 2 3x 3 5 4y 1 3y2 3y 32 y i 2 4习题二 P76 写出对偶问题X 1,X 2 0,X 3无约束z 5X 16X 23x 3X 1 2X 2 2x 3 5 X 1 5X 2 X 3 3 4X 17X 2 3X 3 8X 1无约1 束,X 2 0,X 3 st .0 (b)max 对偶问题为：st.0, y 2 0, y 3无约束5y 1 3y 28y 3y 1 y 2 4y 3 52y 1 5y 2 7y 3 6 2y 1 y 23y33min w y i 无约束川2 0, y 3 0min st.z 4x 1 12X 2 X 13x 3 2X 2 2X 3X 1, X 2 , X 3 018X 3 3max z'4x i 12x 2 18X 30x 4 0x 5(b)max z'5x 1 2x 2 4x 3 0x 4 0x 5列单纯形表，用对偶单纯形法求解C jx ist.X i 3x 3 2X 2 2x 30i 1,,5X 4 X 5列单纯形表，用对偶单纯形法求解,步骤如下3 T目标值z 39。