运筹学作业-王程130404026.docVIP

运筹学作业

王程

信管1302

130404026

目录

TOC\o1-3\h\u5746运筹学作业 1

4985第一章线性规划及单纯形法 3

16829第二章线性规划的对偶理论与灵敏度分析 24

27352第三章运输问题 53

10243第四章目标规划 63

2690第五章整数规划 72

2735第六章非线性规划 84

29209第七章动态规划 93

10045第八章图与网络分析 96

7193第九章网络方案 98

第一章线性规划及单纯形法

1.1分别用图解法和单纯形法求以下线性规划问题，⑴指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解；⑵当具有限最优解时，指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

解：⑴图解法：

当经过点时，最小，且有无穷多个最优解。

⑵图解法：

该问题无可行解。

⑶图解法：

当经过点时，取得唯一最优解。

单纯形法：

在上述问题的约束条件中分别参加松弛变量，化为标准型：

由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所示：

⑷图解法：

当经过点时，取得唯一最优解。

1.2将下述线性规划问题化成标准形式。

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

解：〔1〕该线性规划问题的全部基解见下表中的①～⑧，打√者为基可行解，注*者为最优解，z*=36。

〔2〕该线性规划问题的标准形式为：

其全部基解见下表中的①～⑥，打√者为基可行解，注*者为最优解，z*=5。

1.4题1.1〔3〕中，假设目标函数变为，讨论的值如何变化，使该问题可行域的每个顶点依次使目标函数到达最优。

解：由目标函数可得：，其中。

⑴当时，可行域的顶点A使目标函数到达最优；

⑵当时，可行域的顶点B使目标函数到达最优；

⑶当时，可行域的顶点C使目标函数到达最优；

⑷当或时，最优解为O点。

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

其中M是一个任意大的正数，据此可列出初始单纯形表如下：

cj

2

3

1

0

0

M

M

θi

CB

XB

b

x1

x2

x3

x4

x5

x6

x7

M

M

x6

x7

8

6

1

3

[4]

2

2

0

-1

0

0

-1

1

0

0

1

2

3

cj-zj

2-4M

3-6M

1-2M

M

M

0

0

3

M

x2

x7

2

2

1/4

[5/2]

1

0

1/2

-1

-1/4

1/2

0

-1

1/4

-1/2

0

1

8

4/5

cj-zj

3

2

x2

x1

9/5

4/5

0

1

1

0

3/5

-2/5

-3/10

1/5

1/10

-2/5

3/10

-1/5

-1/10

2/5

cj-zj

0

0

0

1/2

1/2

M-1/2

M-1/2

由单纯形表的计算结果得：最优解,

目标函数最优值

X存在非基变量检验数，故该线性规划问题有无穷多最优解。

据此可列出单纯初始形表如下：

cj

0

0

0

0

0

1

1

θi

CB

XB

b

x1

x2

x3

x4

x5

x6

x7

1

1

x6

x7

8

6

1

3

[4]

2

2

0

-1

0

0

-1

1

0

0

1

2

3

cj-zj

-4

-6

-2

1

1

0

0

0

1

x2

x7

2

2

1/4

[5/2]

1

0

1/2

-1

-1/4

1/2

0

-1

1/4

-1/2

0

1

8

4/5

cj-zj

0

0

x2

x1

9/5

4/5

0

1

1

0

3/5

-2/5

-3/10

1/5

1/10

-2/5

3/10

-1/5

-1/10

2/5

cj-zj

0

0

0

0

0

1

1

第一阶段求得的最优解，目标函数的最优值，因人工变量，所以是原线性规划问题的基可行解。于是可以进行第二阶段计算，将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，如下表：

cj

2

3

1

0

0

θi

CB

XB

b

x1

x2

x3

x4

x5

3

2

x2

x1

9/5

4/5

0

1

1

0

3/5

-2/5

-3/10

1/5

1/10

-2/5

cj-zj

0

0

0

1/2

1/2

由表中计算可知，原线性规划问题的最优解，目标函数的最优值，由于存在非基变量检验数，故该线性规划问题有无穷多最优解。

其中M是一个任意大的正数，据此可列出单纯形表如下：

cj

10

15

12

0

0

0

-M

θi

CB

XB