最全运筹学习题及答案

第 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

第 6 页 共 6 页

解：（图略）

（1）max z=33/4 最优解是(15/4,3/4) 单纯形法：

标准型是max z=2x1+x2+0x3+0x4 s.t. 3x1+5x2+x3=15 6x1+2x2+x4=24 x1,x2,x3,x4?0 单纯形表计算： 2 b 15 24 0 3 4 -8 3/4 15/4 -33/4 1 0 0 cj CB 0 0 -z 0 2 -z 1 2 -z 解为：（15/4，3/4，0，0 )T Max z=33/4

?i XB x3 x4 x1 3 [6] 2 0 1 0 0 1 0 x2 5 2 1 [4] 1/3 1/3 1 0 0 x3 1 0 0 1 0 0 1/4 -1/12 -1/12 x4 0 1 0 -1/2 1/6 -1/3 -1/8 5/24 -7/24 5 4 3/4 12 x3 x1 x2 x1 迭代第一步表示原点；第二步代表C点（4，0，3，0)T； 第三步代表B点（15/4，3/4，0，0 )T。 （2）解：（图略）

Max z=34 此时坐标点为（2，6） 单纯形法，标准型是： Max z=2x1+5x2+0x3+0x4+0x5

第 7 页 共 7 页

s.t. x1+x3=4 2x2+x4=12 3x1+2x2+x5=18

x1,x2,x3,x4,x5?0 (表略)

最优解 X=（2，6，2，0，0 )T Max z=34

迭代第一步得X(1)=（0，0，4，12，18)T表示原点，迭代第二步得X(2)=（0，6，4，0，6)T，第三步迭代得到最优解的点。 1.5以1.4题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。 解：目标函数：max z=c1x1+c2x2 (1)当c2?0时

x2=-（c1/c2）x1+z/c2 其中，k=-c1/c2

kAB=-3/5，kBC=-3 ? k当c2当c2? 当c2当c2? 当c2当c2kBC 时，

c1，

c2同号。

0时，目标函数在C点有最大值 0时，目标函数在原点最大值。 kBCk

kABcc时，1，2同号。

0， 目标函数在B点有最大值； 0，目标函数在原点最大值。

kAB k

cc0时，1， 2同号。

0时，目标函数在A点有最大值 0时，目标函数在原点最大值。

第 8 页 共 8 页

? k 当c2当c2cc0时，1 ，2异号。 c0，1 c0，1 kAB0时，目标函数在A点有最大值； 0时，目标函数在C点最大值。

? k= 当c2当c2cc时，1， 2同号

0时，目标函数在AB线断上任一点有最大值 0，目标函数在原点最大值。

? k= 当c2当c2kBC时，

c1，

c2同号。

0时，目标函数在BC线断上任一点有最大值 0时，目标函数在原点最大值。 c? k=0时，1=0 当c2当c20时，目标函数在A点有最大值

0，目标函数在OC线断上任一点有最大值

（2）当c2=0时，max z= ? c1? ?

c1x1

0时，目标函数在C点有最大值

0时，目标函数在OA线断上任一点有最大值

c1c1=0时，在可行域任何一点取最大值。

1.6分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于哪类解。

（1）max z=2x1+3x2-5x3

x1+x2+x3?15 2x1-5x2+x3?24

x1，x2?0

（2）min z=2x1+3x2+x3

第 9 页 共 9 页

x1+4x2+2x3?8 3x1+2x2?6

x1，x2，x3?0

（3）max z=10x1+15x2+12x3 5x1+3x2+x3?9 -5x1+6x2+15x3?15 2x1+x2+x3?5

x1，x2，x3?0

（4）max z=2x1-x2+2x3

x1+x2+x3?6 -2x1+x3?2 2x2-x3?0

x1，x2，x3?0

解：（1）解法一：大M法 化为标准型：

Max z=2x1+3x2-5x3-Mx4+0x5-Mx6 s.t. x1+x2+x3+x4=7 2x1-5x2+x3-x5+x6=10

x1,x2,x3,x5,x4,x6?0 M是任意大整数。 单纯形表： 2 b 7 3 -5 -M 0 -M cj CB -M ?i XB x4 x1 1 x2 1 x3 1 x4 1 x5 0 x6 0 7

第 10 页 共 10 页

-M x6 -z 10 17M 2 5 [2] -5 1 2M-5 1/2 1/2 0 0 1 0 -1 -M 1/2 -1/2 1 0 -1/2 1/2 5 4/7 - -M 2 x4 x1 -z 3M+2 3-4M 0 [7/2] 1 -5/2 2M-10 0 4/7 45/7 0 1 (7/2)M+8 0.5M-6 0 1 0 0 1/7 6/7 -50/7 2/7 5/7 0.5M+1 -1.5M-1 1/7 -1/7 -1/7 1/7 3 2 x2 x1 -z -102/7 0 -M-16/7 -1/7 -M+1/7 最优解是： X=（45/7，4/7，0，0，0 )T 目标函数最优值 max z=102/7 有唯一最优解。 解法二： 第一阶段数学模型为 min w= x4+ x6 S.t. x1 +x2+ x3+ x4=7 2 x1-5 x2+ x3- x5+ x6=10 x1,x2,x3,x4，x5,x6?0 （单纯形表略） 最优解 X=（45/7，4/7，0，0，0 )T 目标函数最优值 min w=0 第二阶段单纯形表为： 2 cj 3 -5 0 ?i CB 3 2 XB x2 x1 b 4/7 45/7 x1 0 1 x2 1 0 x3 1/7 6/7 x5 1/7 -1/7

本文来源：https://www.bwwdw.com/article/ujdg.html