运筹学作业-王程130404026

运筹学作业

王程 信管1302 130404026

目录

运筹学作业 .................................................................................. 1 第一章 线性规划及单纯形法 ................................................... 3 第二章 线性规划的对偶理论与灵敏度分析 ......................... 24 第三章第四章第五章第六章第七章第八章第九章

运输问题 ................................................................... 53 ..................................................................... 63 整数规划 ................................................................... 73 ................................................................. 85 动态规划 ................................................................... 94 ............................................................. 97 ..................................................................... 99 目标规划 非线性规划 图与网络分析 网络计划第一章 线性规划及单纯形法

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

（1）minz?2x1?3x2（2）maxz?3x1?2x2?4x1?6x2?6?2x1?x2?2?? s.t.?3x1?2x2?4 s.t.?3x1?4x2?12

?x1,x2?0?x1,x2?0??（3）maxz?10x1?5x2（4）maxz?5x1?6x2?3x1?4x2?9?2x1?x2?2? s.t.?5x1?2x2?8 s.t.??2x1?3x2?2

??x1,x2?0?x1,x2?0?? 解：⑴图解法：

x2212(6/5 1/5).3OO3x1x1

2161x1?z经过点（，）时，z最小，且有无穷多个最优解。

5533 ⑵图解法：

当x2?x232O124x1

该问题无可行解。 ⑶图解法：

x24A(0,9/4)B(1,3/2)OC(5/8,0)3x1

13（，）1 当x2??2x1?z经过点时，z取得唯一最优解。

25 单纯形法：

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

maxz?10x1+5x2?0x3?0x4?3x1?4x2?x3?9?s.t.?5x1?2x2?x4?8?x,x,x,x?0?1234

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

CjCB00XBx3x4cj -zj010x3x1cj -zj510x2x1cj -zj3/2121/58/5b9810 5 0 0 x13x24x31x40θi38/5520110 5 0 00114/52/510-3/51/53/240 1 0 -20101005/14-1/7-5/14-3/142/7-25/1433单纯形表的计算结果表明：X*?(,1,0,0)T,Z*?10??5?1?2022单纯形表迭代的第一步得X（0）?(0,0,9,8)T，表示图中原点O（0,0）821

单纯形表迭代的第二步得X（1）?(,0,,0)T，表示图中C点553单纯形表迭代的第三步得X（2）?(1,,0,0)T，表示图中B点2⑷图解法：