《运筹学教程》第二章习题答案

《运筹学教程》第二章习题答案

1、（1）解：引入松弛变量x4≥0,x5≥0,化不等式为等式为： minz=2X1 +3X2+4X3

s.t. X1+3X2+2X3+X4=7

4X1+2X2+X5=9 X1,X2,X4,X5≥0

化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ： minz=2X1 +3X2+4X3′-4X3〞

s.t. X1+3X2+2 X3′-2 X3〞+X4=7

4X1+2X2+X5=9

X1,X2, X3′，X3〞，X4,X5 ≥0

(2)解：引入松弛变量x5≥0,剩余变量X6≥0，化不等式为等式为：

maxz=X1 -5X2+4X3- X4 s.t. X1+2X3+X5=7

X2-2X4-X6=9 X1,X2，X4,X5 ，X6≥0

化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ： maxz=X1 -5X2+4X3′-4X3〞- X4 s.t. X1+2 X3′-2 X3〞+X5=7

X2-2X4-X6=9

X1,X2, X3′，X3〞，X4,X5 , X6≥0

化极大的目标函数为极小的目标函数：

minz=-X1+5X2-4X3′+4X3〞+X4

s.t. X1+2 X3′-2 X3〞+X5=7

X2-2X4-X6=9

X1,X2, X3′，X3〞，X4,X5 , X6≥0

2、(1)是 不等式表示下图阴影区域，过阴影部分任意两点的直线仍在该区域内。

(2)不是 不等式表示下图阴影区域，过阴影部分且通过曲线上部的直线上的点不完全在该区域内。

(3)不是 不等式表示下图阴影区域，过阴影部分且通过圆内部的直线上的点不完全在该区域内。

3、在以下问题中，指出一组基础变量，求出所有基础可行解以及最优解。

maxz 2x1 x2 x3

s.t.x1 x2 2x3 6

（1）

x1 4x2 x3 4

x1,x2,x3 0

解：将上式化成标准形式，如下：

minp 2x1 x2 x3

s.t.x1 x2 2x3 x4 6

x1 4x2 x3 x5 4

x1,x2,x3,x4,x5 0

从上式中可以得出系数矩阵为A P1

P2P3P4

1

P5

1

14

2 1

10

0 ， 1

取基础变量为x4,x5，令非基变量x1,x2,x3=0，解方程组得基础可行解x(1) (0,0,0,6,4)T

x1 x2 2x3 x4 6x1 4x2 x3 x5 4

同理得基础解：x(2) (0,6,0,0, 20)T，x(3) (0,0,3,0,7)T，x(4) (0,0, 4,24,0)T，

xx

(5)

(0,1,0,5,0)

T

，x(6) (0,，x(9) (

3

1420T

,,0,0)99, 23,0,0,0)

T

，x(7) (6,0,0,0, 2)T，

(10)x (，

(8)

(4,0,0,2,0)

T

20143

,0,

23

,0,0)

T

。

其中基础可行解为：x(1) (0,0,0,6,4)T，x(3) (0,0,3,0,7)T，x(5) (0,1,0,5,0)T，

x

(6)

(0,

1420T

,,0,0)99

23

，x(8) (4,0,0,2,0)T，x(10) (

26323

143

,0,

23

,0,0)

T

。

将上解逐一带入原目标函数，得

Z1=0，Z3=-3，Z5=1，Z6=

，Z8=8，Z10=

143

。

,0,0)

T

其中Z10=

263

最大，所以，最优解为x(10) (

,0,

，最优值为Z10=

263

。

minz 3x1 4x2 x3

s.t.3x1 4x2 x3 9

（2）5x1 2x2 x4 8

x1 2x2 x3 1

x1,x2,x3,x4 0

解：将上式化成标准形式，如下：

s.t.3x1 4x2 x3 x5 9

5x1 2x2 x4 8 x1 2x2 x3 x6 1

x1,x2,x3,x4,x5,x6 0 minz 3x1 4x2 x3

从上式中可以得出系数矩阵为

A P1

P2

P3

P4

P5

3

P6 5

1

422

101

010

100

0

0， 1

3x1 4x2 x3 x5 9

取基础变量为x4,x5,x6，令非基变量x1,x2,x3=0，解方程组5x1 2x2 x4 8

x1 2x2 x3 x6 1

得基础可行解x(1) (0,0,0,8,9, 1)T。

当基变量为x3,x5,x6时，子矩阵为奇异矩阵，x(2)不是该题的基，其他的都为非奇异矩阵，共有19个基。

类似上述，得其他基础解：

xx

(3)

(0,0,9,8,0,8) (0,

94,0,

72,0,

T

，x(4) (0,0,1,8,8,0)T，x(5) (0,4,0,0, 7,7)T，

)

T

(6)

72

，x(7) (0,,0,7,7,0)T，x(8) (0,4, 7,0,0,0)T，

2

1

xx

(9)

(0,4, 7,0,0,0)

T

，x(10) (0,4, 7,0,0,0)T，x(11) (,0,0,0,

5

T

8215

,

135

)

T

，

(12)

(3,0,0, 7,0, 4)

，x(13) ( 1,0,0,13,12,0)T，x(14)=(8/5,0,21/5,0,0,8/5)T，

xx

(15)

8138T (,0,,0,,0)555 (

7137T

,,0,0,,0)6126

，x(16) (2,0,3, 12,0,0)T，x(17) (1,,0,0,0,1)T，

2

3

(18)

，x(19) (,,0,,0,0)T，x(20) (0,4, 7,0,0,0)T。

55

5

9

7

7

767

其中基础可行解为：

xx(3)

(0,0,9,8,0,8) (0,1T

，x(4) (0,0,1,8,8,0)T，x(6) (0,,0,,0,)T，

4

2

2

T

(7)

,0,7,7,0)，x(14)=(8/5,0,21/5,0,0,8/5)Tx

(15)

8138T (,0,,0,,0)，

2555

x

(17) (1,

3T

2

,0,0,0,1)

，x(18) (7,

13612,0,0,

76,0)

T

。

将上解逐一带入原目标函数，得

Z=

1，Z1153=-9，Z4=-1，Z6=-9，Z72

14=3/5 , Z15 5

，Z17=-3，Z18

6

。

其中Z3=Z6= 9最小，所以，最优解为x(3) (0,0,9,8,0,8)Tx

(6)

(0,

94

,0,

72

,0,

72

)

T

，，最优值为Z3=Z6= 9。

4.用图解法和单纯形法求如下线性规划问题的最优解

maxz 4x1 x2（1）

x1 3x2 7

s.t.

4x9 1 2x2 x1,x2

0解：解法（一）如图可知最优解为(x*

*

9

*1,x2) (4

,0)，最优值为z 9。

解法（二）将原线性规划问题化成标准形式：

，

minp 4x1 x2

x1 3x2 x3 7

s.t. 4x1 2x2 x4 9 x,x,x,x 0 1234

不难发现，这个标准形式已经是一个正规定价方程组了，它给出了一个初始基础可行解为

x (0,0,7,9),目标值为p0 0，列出单纯形初始表如下：

T

''

4 0,c2 1 0,且负判别数对应列元素均有元素大于零者，故从初始表可以看出，c1

'''

可求下一个基础可行解。选x1作进基变量，计算bi/ai1(ai1 0,i 1,2)后得，p

94

，定a21

'

''

作旋转项，出基变量为x4，作一次旋转运算后得第二表，此时c1,c2 0，第二表对应的基

础可行解为(,0,

4

9194

,0)，目标值p 9。因此原LP问题的最优解为(x1,x2) (

T

'**

94

,0)，

最优值为z* 9。

minz 2x1 3x2

x1 x2 350

（2） x1 125

s.t.

2x1 x2 600 x,x 0 12

**

解法（一）由图可知该线性规划的最优解为(x1,x2) (250,100)，它与可行域的顶点相对

应，最优目标值z 800。

*

解法（二）将线 …… 此处隐藏：5010字，全部文档内容请下载后查看。喜欢就下载吧 ……