运筹学第1章习题

运筹学第1章习题

运筹学

第1章线性规划与单纯形法习题详解(习题)

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.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

x

k 1mik 1(i 1,...,n)

xik 0 (i=1。n; k=1,。,m)

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.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

1.5以1.4题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。

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

x1+4x2+2x3 8

3x1+2x2 6

x1，x2，x3 0

1.7求下述线性规划问题目标函数z的上界和下界；

Max z=c1x1+c2x2

a11x1 a12x2 b1

a21x1 a22x2 b2

其中：8 b1 12，10 b2 14，2 a12 5，1 c1 3，4 c2 6，

，

1 a11 3