运筹学第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??xk?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,其中:

2?a21?4,4?a22?6