8x1 + 10x2 + d3- - d3+ =56
x1,x2,x3,di-,di+ ≥0 i=1,2,3
取x3、d1-、 d2- 、 d3-为初始基变量，列初始单纯形表 4-2
cj
0
0
0
0 P1 P2 P2 P3 0
CB XB b
x1
x2
x3
d1- d1+ d2- d2+ d3- d3+
0 x3 11 2 1 1 0 0 0 0 0 0
因为x2的检验数≤0且最小，故确定x2为换入变量
继续迭代，得单纯形表 4-3
cj
0
0
0
0 P1 P2 P2 P3 0
CB XB b
x1
x2
x3
d1- d1+ d2- d2+ d3- d3+
0 x3 6 3/2 0 1 0 0 -1/2 1/2 0 0
0 d1- 5 3/2 0 0 1 -1 1/2 -1/2 0 0
继续迭代，得单纯形表 4-4
cj
0
0
0
0 P1 P2 P2 P3 0
CB XB b
x1
x2
x3
d1- d1+ d2- d2+ d3- d3+
0 x3 3 0 0 1 0 0 2 -2 -1/2 1/2
0 d1- 2 0
0 0 1 -1 3 -3 -1/2 1/2
0 x2 4 0
1 0 0 0 4/3 -4/3 -1/6 1/6
min{ P1 d1+ , P2 ( d2- + d2+ ) , P3 d3- }
2x1 + x2
≤11
x1 - x2 + d1- - d1+ =0
s.t. x1 + 2x2 + d2- - d2+ =10
8x1 + 10x2 + d3- - d3+ =56
x1,x2,di-,di+ ≥0 i=1,2,3
3
9
销量
3
6
5
6
2) 沃格尔法
B1 3
A1
B2 11
B3 3
5
B4 产量 行罚数
10
2
7 0 0 0 70
1
9
2
8
3 A2
1
4 1 1 1 60
7
4
A3
6
销量
3
6
列 罚 数
2 2 2
5
10
5
3
9 12
5
6
1
3
1
3
1
2
1
2
2
2、解的最优性检验 1) 闭回路法
B1 3
A1 1
1
A2
3
7 A3
B2 11
i1
j1
st ui + vj ≤ cij i=1, …, 3 j=1, …,4
ui , vj无约束
检验数：σij = cij –CBB-1Pij = cij –y*Pij = cij –(u1 … um ,v1 …vn) Pij = cij – (ui+vj)
目标规划模型的一般形式：
Min
K
﹛Pl（∑k =（1
wlk-dk-
+
wlk+dk+
））,l=1,2…,L﹜
n
∑j =a1 ij xj
≤（=，≥） bi
，i =1，2，…，m
S.t.
n
∑ckj xj
+ dk- - dk+ = gk
，
k =1，2，…，K
j =1
xj ≥ 0 , dk- ，dk+ ≥ 0 ,
C
d3-
D
E
d1- F
d2+
AB
x1=24,x2=26 为满意解
d4-
4.1.4 解目标规划的单纯形法
目标规划可以用单纯形法求解。
检验数是各优先因子的线性组合，其正负首先决定于P1 的系数的正负。若为正，此时检验数的正负就决定于P2 的系数的正负，依此类推。
目标规划问题以检验数非负作为最优准则。
1 0 -1/3 1/3 1/3 -1/3 0 0
0 x1 10/3 1 0 0 2/3 - 2/3 1/3 -1/3 0 0
P1 0 0 0 0 1 0 0 0 0
cj-zj
P2 0 0 0 0 0 1 1 0 0
P3 0 0 0 0 0 0 0 1 0
所以得到另一个满意解x1=10/3, x2=10/3，此解相当于图41中点D。G、D两点的凸线性组合都是例4.2的满意解。
= 4 u2
x31+x32+x33+x34= 9 u3
x11
+x21
+x31
= 3 v1
x12
+x22
+x32
= 6 v2
x13
+x23
+x33 = 5 v3
x14
+x24
+x34= 6 v4
xij≥0 , i=1, 2, 3 ; j=1, 2, 3, 4
对偶问题
3
4
max
aiui
bjv j
j =1，2，…，n k =1，2，…，K
6
x2
B
4.1.3 目标规划的图解法
min{ P1 d1+ , P2 ( d2- + d2+ ) , P3 d3- }
2x1 + x2
≤11
x1 - x2 + d1- - d1+ =0
s.t. x1 + 2x2 + d2- - d2+ =10
8x1 + 10x2 + d3- - d3+ =56
x34
=6 ≥0
运输问题含有m×n个变量，m+n个约束方程。其系数矩阵的结构比
较特殊，对应变量xij的系数向量，其分量中除第i个和第m+j个为1以 外，其余的都为零
模型中只有个相互独立的约束方程。因此，运输问题的任一基可行解 都有m+n-1个基变量 。
4.2.3 运输问题的表上作业法
A1 A2 A3 销量
4.2 运输问题
供应地
运价
a1=7 A1
3 11
130
1
总 产
a2=4 A2
9 2
量
8 7
a3=9 A3
4 10 5
需求地
B1 b1=3
B2 b2=6
总
销
B3 b3=5
量
B4 b4=6
当总产量 = 总销量，称为产销平衡问题 当 总产量≠总销量，称为产销不平衡问题
产销平衡的运输问题的数学模型如下
minz= 3x11 +11x12 +3x13 +10x14 +x21 +9x22 +2x23 +8x24 +7x31 +4x32 +10x33 +5x34
第四章 线性规划进一步讨论
4.1 目标规划 4.2 运输问题
4.1 目标规划基本概念
（1）偏差变量 d+：正偏差变量，表示决策值超出目标值的部分 d-：负偏差变量，表示决策值未达到目标值的部分 按定义有：d+ ≥0， d- ≥0 ，d+ • d- = 0
（2）绝对约束和目标约束 绝对约束（硬约束）：必须严格满足的约束条件
B1 3
x11
1
x21
7
x31
3
B2 11
x12
9
x22
4
x32
6
B3 3
x13
2
x23
10
x33
5
B4
产量
10 7
x14
8 4
x24
5 9
x34
6
20
1、给出运输问题的初始基可行解（初始调运方案） 1）最小元素法
B1 3
A1
B2 11
B3 3
4
B4
产量
10
3
7
1
A2 3
9
2
1
8 4
7
4
A3
6
9
5
E
G
d1+
x1,x2,di-,di+ ≥0 i=1,2,3
DC
所以满意域为线段GD
d2+
d3- d2-
x1
0
A
min{ P1d1- , P2d2+ , P3d3- , P4d4- }
x1 + x2 + d1- - d1+ =40
st. x1 + x2 + d2- - d2+ =50 x1 + d3- - d3+ =24 x2 + d4- - d4+ =30 x1,x2,di-,di+ ≥0 i=1,2,3,4
例4.4 试用单纯形法求解例4.2。 解：首先将此目标规划模型化为线性规划标准形式：
min{ P1 d1+ , P2 ( d2- + d2+ ) , P3 d3- }
2x1 + x2 +x3
=11
x1 - x2 + d1- - d1+ =0 s.t. x1 + 2x2 + d2- - d2+ =10
A1 1
1