运筹学复习题ppt课件

算
bj
3/0
88/5
4/0
6/1
列差 1 111115155 22222828 333332322
4
伏 用伏格尔法寻找初始基：
格
B1
B2
B3
B4
ai 行差
尔 A1 3 2 5 9 0 10 1 7 9/6 5 252 2
法 A2 0 1 0 3 0 4 5 2 5/0 1 11
计
A3 0 8 3 4 4 2 0 5 77/3/3/0 2 222 1
max w 4 y1 3 y2
y1 2 y2 2
y1
y2
3
2 y1 3 y2 5
y1
y2
2
3
y1
y2
3
y1 0, y2 0
min z 2 x1 3 x2 5 x3 2 x4 3 x5
x1
x2
2 x3
x4
3 x5
4
2 x1 x2 3 x3 x4 x5 3
算
bj
3/0
88/5
4/0
6/1
列差 1 1 115 5 2 228 3 332 2
5
得到产销平衡运输问题的一个初始方案.
B1
B2
A1 3 2 5 9
B3
B4
ai
10 1 7 9
A2
1
3
452 5
A3
8 3 442
57
bj
3
8
4
6
可以得到基可行解对应的位势方程组是：
u1 v1 2
u1
v2
9
增加如下割平面，
1 2
1 2
x3
1 2

3
v1
5
2
v4 5
2
1
3
1
5
v3
v5
第32页/共40页
班次 1 2 3 4 5 6
时间 6：00 —— 10：00 10：00 —— 14：00 14：00 —— 18：00 18：00 —— 22：00 22：00 —— 2：00 2：00 —— 6：00
所需人数 60 70 60 50 20 30
设司机和乘务人员分别在各时间段一开始时上班，并 连续工作八小时，问该公交线路怎样安排司机和乘务人员， 既能满足工作需要，又配备最少司机和乘务人员?
第28页/共40页
28
§3
复杂情况下的目标规划
例7．一工艺品厂商手工生产某两种工艺品A、B，已知生产一
件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3
工时。A、B产品的单位利润分别为260元和125元。为了最
大效率地利用人力资源，确定生产的首要任务是保证人员高
负荷生产，要求每周总耗费人力资源不能低于600工时，但也
（*）并整理得
50 c2
+
• 假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来 判断。
• 假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则
- 2 - (60 / 55) - 1
那么，最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100第，8页x/共24=0页 200 。
23
17
• 如果把工作时间看成创造的效益，那么又该如何指派，
才能获得最大效益？
• 如果再增加一项工作E，四人完成的时间分别是
17,20,15,16分钟，那么又该如何指派使得所花时 目标规划

将下列线性规划转化为标准型
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无约束
max z 3x1 5x2
3x1 2 x2 18

x1

4 2 x2 12
x1 , x2 0
1
标准型为：
max
z'

3x1

4x2

2x3

5x
' 4

5x
'' 4

4 x1

x2

2 x3
x1 x2 3x3 x

' 4
x
'
4 x '' 4
x''4 2 x5 14
i1 j1
2x21 10x22 3x23 9x24 8x31 5x32 11x33 6x34

x11 x21

x12 x22

x13 x23
x14 x24
16 10

x31

x32

x33

x34

22
st
.
x11 x12

B4
14 35
8 4-3-1
4
产量 行差额 hi
4-3-1
4
6-2-1-3
5
3-3
2
13
27
初始方案如下:x13=3,x14=1,x21=2,x22=1,x24=3,x32=3, 费 用=3*3+4*1+4*2+4*1+5*3+6*3=58(元)

1 5/4 -15/2 0 1/4 -1/2 0 [-1/4] 3/2 0 表2-12 -1/4 -1/2
用对偶单纯形法继续计算得表2-13。
2009年8月
管理工程学院
《运筹学》 运筹学》
25
基 b x3 15 x1 5 x4 2 c j- z j 2 x1 0 1 0 0 1 x2 5 1 -4 -1 0 x3 1 0 0 0 表2-13 0 0 x4 x5 0 0 0 1 1 -6 0 -2
5/4 -15/2 1/4 -1/2 -1/4 3/2 -8/7 1/4
对偶变量 -y4
-y5
-y1 - y2
2009年8月
-y3
管理工程学院
《运筹学》 运筹学》
18
5 b x1 0 1 0 0 1.5 x2 5 1/3 2/3 -1/6 表2-10 0 x3 1 0 0 0 x4 0 1/6 -1/6 0 x5 0 0 1
-15 -24 -5 0 -5
1 1/6 -1/6 0 0 [-2/3] -1/3 1
-15 0 -1 -4 0 -4/5 1 0 -1/4 1/4 15/2 0 [-2/3] -1/3 1 -15 0 0 -7/2 -3/2
管理工程学院
2009年8月
《运筹学》 运筹学》
13
三、参数变化后情形结合具体实例的讨论 1. 分析 j变化的影响 分析c 变化仅影响到检验数(c 的变化， ◆cj变化仅影响到检验数 j- zj)的变化，只可能出 的变化 现表2-7中所示的前两种情况 中所示的前两种情况。 现表 中所示的前两种情况。
管理工程学院
原问题(对偶问题 原问题 对偶问题) 对偶问题 目标函数 max n个 个 变量 ≥0 ≤0 无约束 函数变量系数(价值系数 价值系数) 函数变量系数 价值系数 m个 个 约束条件 ≤ ≥ 表2-2 ＝ 约束条件右端项