3 2
11
12
12
B4
产量
11 16
6
9 10
-1
6 22
8
14
48
24 9 3 4 11 1
检验数中有负数，说明原方案不是最优解。
20
五。。无向图情形
求网络中v1至v7的最短路。
v2
2
2
7
v1
5
v3
5
v6 5
v7
3
13
1
7
v4
5
v5
2020/9/25
无向图情形
答案（1）：
v2 [2,v1]
2
y2 y2
2 y3 3 y3
75 2
y1
y2 2 y3 1
y1, y2 , y3 0
对偶与灵敏度 10
写出下列线性规划的对偶问题：
（1）
s.t.
max z 3x1 x2 x3 x1 2x2 x3 4
x1 2x2 4x3 1 x1 x2 3x3 1
x1 0, x2 0, x3无约束
1
00
5 g
2
a6
3 14 14
h3 b4
l
5
4
7
5599
14 14
7f
5
19 19
k 10
1
16 17
9J
2
20 20
11
8
d
3
16 17
• 关键工序：hbgafk
24
七。决策分析
• 悲观准则 • 乐观准则
悲观准则
（行动方案）（自然状态） 需求数量
订购量 6 7 8 9 10
6*
30 30 30 30 30
DP
对偶与灵敏度 12
四。运输问题
• 书78页 最小元素法 • 书81页 闭回路法
以最小元素法的初始解为例。假设产地 A1 供应 1 个单位 的物品给销地 B1。则解的变化和目标函数的变化如何。
销地 产地
A1
A2
A3 销量
B1 4
2 8
8
8
B2 12
10
5 14
14
B3 4
10 3
2 11
12
B4
在目标函数中人工变量的系数是任意大正数 M的相反数-M；
用线性规划的优化机制迫使人工变量出基；
如果无法使人工变量出基，原问题无 可行解。
2020/9/25
6
CB 0 -M -M
0 -M -1
2020/9/25
cj
XB
b
X4 11
X6
3
X7
1
j
X4 10
X6
1
X3
1
j
3 -1
x1
x2
1 -2
-4 1
2020/9/25
5
例题1.17：
大M法
max z = 3x1 – x2 –x3 –Mx6 –Mx7
s.t.
x1 – 2x2 + x3 + x4
=（）11
-4x1 + x2 +2x3 – x5+ x6 =（ ）3
-2x1
+ x3
+ x7 =（=）1
x1,x2, x3,x4,x5,x6,x7 0
通过引入人工变量构成初始基，从而找到一个初始基可行解；
1
（2）如何化标准形式
目标函数的转换
如果是求极小值即 minz c j x j，则可将目标函数乘以
(-1)，可化为求极大值问题。
即 maxz z cj x j
也就是：令 z z，可得到上式。
变量的变换
若存在取值变量
x
≤0
j
，可令
xj x j
其中： xj 0
若存在取值无约束的变量
x
-2 0
-1 0
x3
x4
1
1
2
0
1
0
3-6M -1+M -1+3M 0
3
-2
0
1
0
1
0
0
-2 0
1
0
1 -1+M 0
0
0 -M -M
x5
x6
x7
00
0
-1 1
0
00
1
-M 0
0
0 0 -1
-1 1 -2
00
1
-M
0 -3M+1
7
• 与书上39页11题 相似
三。写出下面线性规划的对偶规划模型
max 3x1 75x2 2x3 x4
18
销地 产地
A1
A2
A3 销量
B1
4
1
2 8
8
10
8
B2
B3
12
2
10
1
5 14
14
4 10
3 2
11
12
12
B4
产量
11 16
6 9 10
6 22
8
14
48
33 11 4 11 6 12
19
销地 产地
A1
A2
A3 销量
B1
4
1
2 8
8
10
8
B2
B3
12
2
10
1
5 14
14
4 10
15
销地 产地
A1
A2
A3 销量
B1 4
1
2 8
8
8
B2
B3
12
2
10
5 14
14
4 10
3 2
11
12
B4
产量
11 16
6 9 10
6 22
8
14
48
12 12 11 6 5 2
16
销地 产地
A1
A2
A3 销量
B1 4
1
2 8
8
8
B2
B3
12
2
10
1
5 14
14
4 10
3 2
11
12
B4
v1
2
2
5
7
v[4,v2/
3
v4]
5
[8,v5]
v6 5
[0,v1]
3
13
1
7
v4
5
[3,v1]
v [7,v3]
5
[13,v6]
v7
2020/9/25
六。网络计划（30分）
• 计算各工序的最早开工、最早完工、最迟 开工、最迟完工时间及总时差、单时差， 并指出关键工序。
78
c
2
e
7
5
m
3 11 11
产量
11 16
6 9 10
6 22
8
14
48
22 10 3 4 11 6 5 1
17
销地 产地
A1
A2
A3 销量
B1
4
1
2 8
8
10
8
B2
B3
12
2
10
1
5 14
14
4 10
3 2
11
12
B4
产量
11 16
6 9 10
6 22
8
14
48
31 8 2 3 4 11 6 10
产量
11 16
6 9 10
6 22
8
14
48
14
销地 产地
A1
A2
A3
B1
4
1
2 8
8
销量
8
要保证产销平衡，则
B2 12
10
5 14
14
B3 4
10 3
2 11
12
B4
产量
11 16
6 9 10
6 22
8
14
48
xx1111 1x13 x13 x213 xx2231为1闭回x路21 1
11 4 4 3 2 1
7
10 35 35 35 35
8
-10 15 40 40 40
9
-30 -0
min 30 10 -10 -30 -50
Max 30
乐观准则
（行动方案）（自然状态） 需求数量
订购量 6 7 8 9 10
6
30 30 30 30 30
7
10 35 35 35 35
xni 0 称为剩余变量
常量 bi＜0 的变换:约束方程两边乘以（－1）
2020/9/25
3
• 书上11页例1-8 1-9
二。加入人工变量构造初始基：
把所有约束方程的右端常数调整为大于等于零。 对 约束, 引入松弛变量。 对 约束, 引入一剩余变量和一人工变量。 对 = 约束，引入一人工变量。
一。线性规划问题的数学模型
• . 线性规划问题的标准形式
n
max Z c j x j j 1
特点：
s.t
n j 1
aij x j
bi
i 1,2,, m
x j 0, j 1,2,, n
(1) 目标函数求最大值（有时求最小值）
(2) 约束条件都为等式方程，且右端常数项bi都大于或等于零
202(03/9)/25决策变量xj为非负。
，
j
可令x j xj xj
其中： xj , xj 0
2020/9/25