内容发布更新时间 : 2024/11/18 13:49:26星期一 下面是文章的全部内容请认真阅读。

运筹学习题答案

第一章（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将下列线性规划问题变换成标准型，并列出初始单纯形表。

（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? CB XB -4 x2 2 x3 -5 x5 5 x6 0 x7 0 x8 -M -M x9 x10 ?i b 2 14 x1 -M 0 x10 x7 -4 1 1 1 -2 3 1 -1 -1 1 0 1 0 0 0 0 1 0 2 14 -M x9 2 -2 [3] -1 2 -2 0 -1 1 0 0 2/3 -z? 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)

CB M是任意正整数 初始单纯形表： --M … -a11cj pkM M b … XBxnx11 x1x2 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 x12 x1m xn1 xn2 xnm -M -M … -M -s x1 x2 1 0 … 0 a12?M… … … … … … 0 a1m?M… 0 … 0 … … … 1 … an1?M0 0 … 1 an2?M… … … … … 0 0 … 1 amn?M … 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

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

同理，以（P1，P3）为基，基解X(2)=（45/13，0，-14/13，0)T是非可行解； 以（P1，P4）为基，基解X(3)=（34/5，0，0，7/5)T是可行解，z3=117/5； 以（P2，P3）为基，基解X(4)=（0，45/16，7/16，0)T是可行解，z4=163/16； 以（P2，P4）为基，基解X(5)=（0，68/29，0，-7/29)T是非可行解； 以（P4，P3）为基，基解X(6)=（0，0，-68/31，-45/31)T是非可行解； 最大值为z3=117/5；最优解X(3)=（34/5，0，0，7/5)T。 （2）解：

系数矩阵A是：

?1234??2112? ??令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为非可行解；

同理，以（P1，P3）为基，基解X(2)=（2/5，0，11/5，0)T是可行解z2=43/5； 以（P1，P4）为基，基解X(3)=（-1/3，0，0，11/6)T是非可行解； 以（P2，P3）为基，基解X(4)=（0，2，1，0)T是可行解，z4=-1； 以（P4，P3）为基，基解X(6)=（0，0，1，1)T是z6=-3； 最大值为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