运筹学第一次习题课

1.1用图解法求解下列线性规划问题，并指出问题具有最优解、无穷解无界解还是 无可行解。

(a) min z 2x1 3x2 S.T 4x 6x 61 2

4 x1 2 x2 4

x1 , x2 0

解：

该问题有无穷最优解，即满足 4 x1 6 x2 0 且 0 x2 1 的所有(x1 , x2 ),此时目标函数值 为3

(c)

max z x1 x2

6 x1 10x2 120 5 x1 10 3 x2 8

由图可知在点(10,6)处目标函数取得 最大值16。线性规划有唯一最优解。

(补充)

(b)

max z x1 x22 x1 x2 2 3x1 4 x2 12 x1 , x2 0

解：

用图解法找不到满足所有约束条件的公 共范围，则该问题无解。

1.2对下述线性规划找出所有基解，指 出哪些是基可行解，并确定最优解。

(a) max z 2x 4x1

2

5x3 6x4

s.t

x1 4 x2 2 x3 8x4 2 x . 1 2x2 3x3 4x4 1x j 0( j 1,...,4)

解:写出约束方程的系数矩阵p1 P P3 P4 2

A= 1 4 -2 8 -1 2 3 4 R(A)=2,所以只要找出2个列向量组成矩 阵满秩，这两个向量就是线性规划问题 的一个基， 由于 P 与 P 线性相关不能构 成基，构建表格列出全部基，基解，指 出基可行解，*标注的为最优解： 2 4

基

基解

是基可行解？

目标函数值

P1 P1 P1P2

x1P20 8 0 0 0

x2½ 0 0 ½ 0

x30 3 0 0 0

x40 0 1/4 是 是 是 -2 31* -3/2 -2 -3/2

P3P4

P3P4

0 是 1/4 是

P3

(补充)

(b)min z 5x1 2x2 3x3 2x4

x1 2 x2 3x3 4 x4 7 2 x1 2 x2 x3 2 x4 3x j 0( j 1,...,4)

1.3

分别用图解法和单纯形法求解下述线性规 划问题，并对照指出单纯形表中的各基行解分别

对应图解法中可行域的哪一个定点. (b) max z 2x1 x2S.t.5x2 15 6 x1 2 x2 24 x1 x2 5 x1 , x2 0

由图可知最优解为 6 x1 2 x2 24x1 x2 5

的解x=(7/2,3/2),最大值z=17/2

(2)单纯形法

首先在各约束条件上添加松弛变脸，将问 题转化为标准形式 max z 2x1 x2 0x3 0x4 0x5S.t.5x2 x3 15 6 x1 2 x2 x4 24 x1 x2 x5 5

则 P3 P4 P5 组成一个基，令 x1 x2 0 得基可行解 x (0,0,15,24,5) ,由此列出初始 单纯形表 2 1 0 0 0 cj T

cB0 0 0

基

b

x1 x2 x3 x4 x50 6 1 5 2 1 1 0 0 0 1 0 0 0 1 4 5

x3 x4 x5

15 24 5

i

cj z j

2

1

0

0

0

初始表对应定点(0,0)cj cB 基0 2 0 2 b 15 4 1 1 0 0 0

x1 x2 x3 x4 x50 5 1 0 0 1 1/3 0 1/6 0 0 2/3 0 -1/6 1 0 1/3 0 -1/3 0 3 12 3/2

i

x3 x1 x5

cj z j

对应点(4,0)

cj 基 cB0 2 1

2 b

1

0

0

0

x1

x2 x x4 30 0 1 0

x5

x3 x1 x2

15/2 0 7/2 1 3/ 2 0 0

1 5/4 -15/2 0 1/4 -1/2 0 -1/4 3/2 0 -1/4 -1/2

i

cj z

j

表明已经找到问题的最优解 7 3 15 7 3 ( , , ,0,0) 对应点 ( , ) ,最大值为17/2T

2 2 2

2 2

(补充)

(a)max z 10x1 5x2

5x1 2x2 8

st

3x1 4 x2 9 x1 , x2 0

(图解法)

(单纯形法)