第 1 页 共 1 页
运筹学习题答案
第一章（39页）
1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max z?x1?x2 5x1+10x2?50
x1+x2?1 x2?4 x1，x2?0
（2）min z=x1+1.5x2
x1+3x2?3 x1+x2?2 x1，x2?0
（3）max z=2x1+2x2
x1-x2?-1 -0.5x1+x2?2 x1，x2?0 （4）max z=x1+x2
x1-x2?0 3x1-x2?-3
x1，x2?0
解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解
1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。
第 2 页 共 2 页
（1）min z=-3x1+4x2-2x3+5x4 4x1-x2+2x3-x4=-2
x1+x2+3x3-x4?14 -2x1+3x2-x3+2x4?2
x1，x2，x3?0，x4无约束 （2）max s?nmzkpk zk???aikxik i?1k?1??xk?1mik??1(i?1,...,n) xik?0 (i=1…n; k=1,…,m) （1）解：设z=-z?,x4=x5-x6, x5,x6?0 标准型： Max z?=3x1-4x2+2x3-5(x5-x6)+0x7+0x8-Mx9-Mx10 s. t .
-4x1+x2-2x3+x5-x6+x10=2 x1+x2+3x3-x5+x6+x7=14 -2x1+3x2-x3+2x5-2x6-x8+x9=2 x1,x2,x3,x5,x6,x7,x8,x9,x10?0 初始单纯形表: 3 cj? -4 2 -5 5 0 0 -M -M ?i CB -M 0 XB x10 x7 b 2 14 x1 -4 1 x2 1 1 x3 -2 3 x5 1 -1 x6 -1 1 x7 0 1 x8 0 0 x9 0 0 x10 1 0 2 14
第 3 页 共 3 页
-M x9 -z? 2 -2 [3] -1 2 -2 0 -1 1 0 0 2/3 4M 3-6M 4M-4 2-3M 3M-5 5-3M 0 -M 0 (2)解：加入人工变量x1，x2，x3，…xn，得： Max s=(1/pk)?i?1n?k?1m?ikxik-Mx1-Mx2-…..-Mxn
s.t.
xi??xik?1 (i=1,2,3…,n) k?1mxik?0, xi?0, (i=1,2,3…n; k=1,2….,m) M是任意正整数 初始单纯形表： --M … -a11cj pk M M b … xnx11 XBx1x2 -M -M … -M -s 1 1 … 1 nM 1 0 0 1 … … 0 0 0 0 … 0 1 … 0 … … … … 1 0 … 0 a11?Ma12pk … … a1mpk … an1… pk an2pk … … amnpk ?i CB x12 1 0 … 0 a12?Mx1m … 0 a1m?Mxn1 xn2 0 0 … 1 ?Man2?Mxnm 0 0 … 1 amn?Mx1 x2 … … … … … … … 0 … 0 … … … 1 … an1… … … … … xn pkpkpkpkpkpk 1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。 （1）max z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x4=8 x1-2x2+6x3-7x4=-3
x1,x2,x3,x4?0
(2)max z=5x1-2x2+3x3-6x4
第 4 页 共 4 页
x1+2x2+3x3+4x4=7 2x1+x2+x3+2x4=3
x1x2x3x4?0 （1）解：
系数矩阵A是：
?23?1?4??1?26?7? ??令A=(P1，P2，P3，P4)
P1与P2线形无关，以（P1，P2）为基，x1，x2为基变量。 有 2x1+3x2=8+x3+4x4 x1-2x2=-3-6x3+7x4 令非基变量x3，x4=0 解得：x1=1；x2=2
基解X(1)=（1，2，0，0)T为可行解
z1=8
(2)同理，以（P1，P=（45/13，0，-14/13，0)T是非可行解； 3）为基，基解X以（P1，P4）为基，基解X(3)=（34/5，0，0，7/5)T是可行解，z3=117/5；
(4)以（P2，P=（0，45/16，7/16，0)T是可行解，z4=163/16； 3）为基，基解X以（P2，P4）为基，基解X(5)=（0，68/29，0，-7/29)T是非可行解；
(6)TX以（P4，P）为基，基解=（0，0，-68/31，-45/31是非可行解； )3最大值为z3=117/5；最优解X(3)=（34/5，0，0，7/5)T。 （2）解：
系数矩阵A是：
?1234??2112? ??
第 5 页 共 5 页
令A=(P1，P2，P3，P4)
P1，P2线性无关，以（P1，P2）为基，有： x1+2x2=7-3x3-4x4 2x1+x2=3-x3-2x4 令 x3，x4=0得
x1=-1/3，x2=11/3
基解X(1)=（-1/3，11/3，0，0)T为非可行解；
(2)同理，以（P1，P=（2/5，0，11/5，0)T是可行解z2=43/5； 3）为基，基解X以（P1，P4）为基，基解X(3)=（-1/3，0，0，11/6)T是非可行解； (4)以（P2，P=（0，2，1，0)T是可行解，z4=-1； 3）为基，基解X(6)以（P4，P=（0，0，1，1)T是z6=-3； 3）为基，基解X最大值为z2=43/5；最优解为X(2)=（2/5，0，11/5，0)T。
1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。
（1）max z=2x1+x2 3x1+5x2?15 6x1+2x2?24
x1，x2?0
（2）max z=2x1+5x2
x1?4 2x2?12 3x1+2x2?18
x1，x2?0