西北角法：运筹学表上作业法初始基可行解的确定

A B C 销量（ 销量（bj）
第一步：从表4 中找出最小运价“1”， 第一步：从表4-1中找出最小运价“1”， 最小运 价所确定的供应关系为（ ），在 价所确定的供应关系为（B，甲），在（B，甲） 的交叉格处填上“3”，形成表4 的交叉格处填上“3”，形成表4-2；将运价表的 甲列运价划去得表4 甲列运价划去得表4-3.
8.伏格尔法 8.伏格尔法
伏格尔法的基本步骤： 伏格尔法的基本步骤： 1.计算每行、列两个最小运价的差； 1.计算每行、列两个最小运价的差； 计算每行 2.找出最大差所在的行或列 找出最大差所在的行或列； 2.找出最大差所在的行或列； 3.找出该行或列的最小运价 确定供求关系， 找出该行或列的最小运价， 3.找出该行或列的最小运价，确定供求关系，最大量 的供应 ； 4.划掉已满足要求的行或 4.划掉已满足要求的行或 (和) 列，如果需要同时划 去行和列， 去行和列，必须要在该行或列的任意位置填个 0”； “0”； 5.在剩余的运价表中重复1~4步 在剩余的运价表中重复1~4 5.在剩余的运价表中重复1~4步，直到得到初始基可 行解。 行解。
2.表上作业法与单纯形法的关系 2.表上作业法与单纯形法的关系
表上作业法中的最小元素法和伏格尔法实质 上是在求单纯形表中的初始基可行解； 上是在求单纯形表中的初始基可行解； 表上作业法中的“位势法” 表上作业法中的“位势法”实质上是在求单 纯形表中的检验数； 纯形表中的检验数； 调运方案表中数字格的数实质上就是单纯形 法中基变量的值； 法中基变量的值； 调运方案表上的“闭回路法” 调运方案表上的“闭回路法”实质上是在做 单纯形表上的换基迭代。 单纯形表上的换基迭代。
甲 A B C 销量（ 销量（bj） 表4-14 A B C
两最小元素之差

销地 产地
B1
4
B2
12
B3
4 3
B4
11 9 6 14
产 量
A1 A2
A3
销 量
8
2
8
10
16
10
② ④
6
8 5
4
11
x32
22
48
8
①
14 6 ③
12 8
表 3-2
销地 产地
B1
4
B2
12
B3
4 3
B4
11 9 6
产 量
A1 A2
A3
销 量
8
2
8
10
16
10
② ④
6
8 5 14 6 ① ③
4
11 12 8 ⑤ 14
表上作业法
计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2
一、给出运输问题的初始可行解（初始调运方案） 下面介绍三种常用的方法。
最小元素法 西北角法 沃格尔(Vogel)法
1。最小元素法 思想：优先满足运价（或运距）最小的供销业务。
表 3-2
销地 产地
B1
11
产 量
1
2
3
A1 A2
16 9 10
0 0 1 1 1 2
A3
销 量 列 罚 数
6
8
22 48
14
8 2 2 14 5
14 6
3 3
1 2 3
销 地 产地
行罚数
B1
4
B2
12 10 5
B3 4 3 11 12 1 1 1
B4
11

销地
B3 3 x14 8 B4 10
供应
7 4
需求
3
6
5
6
20
元素差额法(VAM法) 例 设有A1, A2和A3的产品需要运到B1, B2, B3 . 元素差额法是在最小元素法的基础上改进的 和 B4四个销地，求如何调运使总运费最少？ 在确定产销关系时，不从最小元素开始，而 从运输表中各行各列的最小元素和次小元素 产地 销地 供应 B1 B2 B3. B4 之间的差额来确定产销关系
2
5
×
3 差 额
3
8
4
4
×
6
2 1
1
1 5
2 8
3 2
初始调运方案为
2 3 5 9 7 1 2 5 4 3 2 4 88
作业： 用元素差额法求解下列问题的调运方案
产地
B1 A1 x11 A2 x21 A3 x31 7 x32 1 x22 4 x33 3 x12 9 x23 10 x34 B2 11 x13 2 x24 5 9
初始总运费为
5 9 4 7 3 1 2 2 3 4 4 2 100
作业： 用最小元素法求解下列问题的调运方案
产地
B1 A1 x11 A2 x21 A3 x31 7 x32 1 x22 4 x33 3 x12 9 x23 10 x34 B2 11 x13 2 x24 5 9
供 应
9 9-3 9-3-6 5 5-2 5-2-3 7 7-1 21
3
A2 A3 需求
1
6-6 6
初始调运的运费为
3 2 6 9 2 3 3 4 1 2 6 5 110

2、判断是否最优；——闭回路法、位势法
3、若不是最优，进行调整，直到找到最优解。
例：某公司有三个生产厂商和四个销售公司，运价，产量， 销量如下表： 运
销 地
B1
3 1 7 3
B2
11 9 4 6
B3
3 2 10 5
B4
10 8 5 6
产量
7 4 9 20|20
产
费
地
A1 A2 A3
销量
1、确定初始基本可行解——西北角法 运
目标函数：
min f
c
i 1 j 1
m
n
ij
x ij
约束条件：

j 1 n
x ij s i ( i 1, 2 ,..., m ) x ij d j ( j 1, 2 ,..., n )

i 1
m
x ij 0
注意：
运输问题可能的一些变化：
1、目标函数是求最大值。如运输公司要求营业额最大化。
销 地
B1 2 10 7 2
B2 11 3 8 3
B3 3 5 1 4
B4 4 9 2 6
D 0 0 0 4
产量 7 5 7 19
A1 A2 A3 销量
例：有三个地方B1、B2、B3 分别需要煤3000、1000、2000吨， 由A1,A2两个地方来供应，其供应量分别为4000，1500吨，其 运价如下表：
1 广州
2 大连
解：Xij表示从I到j的运输量。
min f 2 x13 3 x14 3 x 23 x 24 2 x 35 6 x 36 4 x 45 3 x 37 6 x 38 4 x 46 6 x 47 5 x 48 4 x 28

22
13
12 0
最小元素法(2)
1 6 1 8 2 5 3 22 9 4 7
2 5
3 3
4 14 1
132 712来自10 62715
19 13 12 0 13 0
最小元素法(3)
1 6 1 8 2 5 3 22 9 4 7
2 5
3 3
4 14 1
13
2 7
13
10
12
6
27
2
19 13 0 12 0 13 0
解: 西北角法
销地 产地
B1 6 4 7 2
B2 5 4 6 4
B3 3 7 5 3
B4 4 5 8 4
产量
A1 A2 A3
销量
4 6 3 13
(1) 从图的西北角开始, 填入a1与b1较小的值,b1=2, 即从A1运 给B1(2吨)B1已满足, 划去b1列, 并将a1=4-2=2
销地 产地
B1 26 4 7 2-2
例2
供应地 运价 销售地 1 a1=14 供 应 量 1 6 7 5
b1=22
a2=27
2
a3=19
3
3 8 4 2 7 5 9 10 6
2
b2=13
销 售 量
3
b3=12
4
b4=13
解:
初始基础可行解—最小元素法(1)
1 1 6 7
2 5
3 3
4 14
2
8
4
2
7
27
15
12
3 5 9 10 6 19 13
如何调运产品才能使总运费最小？
销地 产地
B1 6 4 7 2
B2 5 4 6 4

从上面的讨论可以看出，当某个非 基变量增加一个单位时，有若干个基变 量的取值受其影响。
22
这样，利用单位产品变化（运输的 单位费用）可计算出它们对目标函数的 综合影响，称这个综合影响为该非基变 量对应的检验数。
上面计算的两个非基变量的检验数
为 24 = -1，22 = 1。
闭回路方法原理就是通过寻找闭回路 来找到非基变量的检验数。
表4-11 初始基本可行解及检验数
销地
B1
B2
B3
B4
产地
A1
3
11
3
10
[1] [2]
4
3
A2
1
9
2
8
3 [1]
1 [-1]
A3
7
4
10
5
[10]
6 [12]
3
销量
3
6
5
6
产量 7 4 9
20(产销平衡)
25
显然，当所有非基变量的检验数 均大于或等于零时，现行的调运方案就 是最优方案，因为此时对现行方案作任 何调整都将导致总的运输费用增加。
mn
Min f = cij xij
i=1 j=1
n
s.t.

j=1
xij
si
i = 1,2,…,m
m
xij =dj j = 1,2,…,n
i=1
xij≥0(i=1,2,…,m;j=1,2,…,n)
40
2.运输问题求解
—表上作业法
只要在模型中的产量限制约束（前m
个不等式约束）中引入m个松弛变量 xin+1 i= 1,2,…,m 即可，变为：
第二节 运输问题求解 —表上作业法

则称该运输问题为产销平衡问题；否则，称 产销不平衡。首先讨论产销平衡问题。
8
1.运输问题模型及有关概念
表4-3 运输问题数据表
销地
产地
A1 A2
┇
Am
销量
B1 B2 … Bn
c11
c12 … c1n
c21
c22 … c2n
┇ ┇ ┇┇
cm1
cm2 … cmn
b1
b2 … bn
产量
a1 a2
┇
am
设 xij 为从产地 Ai 运往销地 Bj 的运
式（4-8）中的变量称为这个闭回路的顶点。
22
1.运输问题模型及有关概念
例如，x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是闭回路。
若把闭回路的各变量格看作节点， 在表中可以画出如下形式的闭回路：
得到下列运输量表：
4
1.运输问题模型及有关概念
Min Z s.t.
= 6x11+4x12+6x13+6x21+5x22+5x23 x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
2.每列只有两个 1，其余为 0，分别 表示只有一个产地和一个销地被使用。
7
1.运输问题模型及有关概念
一般运输问题的线性规划模型及求解思路
一般运输问题的提法：
假设 A1, A2,…,Am 表示某物资的m个 产地；B1,B2,…,Bn 表示某物资的n个销地； ai表示产地 Ai 的产量；bj 表示销地 Bj 的 销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价（表4-3）。如果 a1 + a2 + … + am = b1 + b2 + … + bn

B1
B2
B3
B4
产量
A1 3
11
3 4 10 3 7
A2 1 3 9
2 18
4
A3 7
4 6 10
5 39
销量
3
6
5
6
Z=4×3+3×10+3×1+1×2+6×4+3×5=86
13
2.确定初始基本可行解
为保证基变量的个数有m+n-1个， 注意：
❖1、每次填完数，只能划去一行或一列，只 有最后一个格子例外。
B1
B2
11 = 1
3
12 = 2 22= 1
B3
B4
4
3
1
24 = -1
31 = 10
6
33 = 12
3
3
6
5
6
产量 7 4 9
❖最优标准：所有检验数ij ≥0
27
3.最优性检验 ❖2、位势法
❖ 闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算 两方面都容易出错。
位势法检验步骤：
❖ 1）设产地Ai对应的位势量为ui ，销地Bj对应的位势量为vj； ❖ 2势）U由i ，ijV=Cj ，ij-（即UCii+j-V（j）Ui,+利V用j）对=基0，变令量U而1=言0；有ij=0，计算位 ❖ 3）再由ij=Cij-（Ui+Vj）计算非基变量的检验数ij
❖2、用最小元素法时，可能会出现基变量个 数还差两个以上但只剩下一行或一列的情 况，此时不能将剩下行或列按空格划掉， 应在剩下的空格中标上0。（退化的基本可 行解）
14
2.确定初始基本可行解
B1

请大家分别计算一下用以上三种方法求得的可行解对应的目标函
第二节 运输问题初始基本可行解的求法
请大家分别计算一下用以上三种方法求得的可行解对 应的目标函数值，看看那个值更小一些。 应的目标函数值，看看那个值更小一些。 由以上可见； 由以上可见；伏格尔格法同最小元素法除在确定供 求关系的原则上不同外，其余步骤相同， 求关系的原则上不同外，其余步骤相同，伏格尔法求 得的初始解比用最小元素法给出的初始解更接近最优 解。 上面只说求得的解是可行解， 上面只说求得的解是可行解，那么它是不是基本可 行解呢，下面的定理将给出结论。 行解呢，下面的定理将给出结论。 定理：西北角法、最小元素法、差值法得到的x 定理：西北角法、最小元素法、差值法得到的 ij的值 是一组基本可行解，没有画“ 是一组基本可行解，没有画“×”的地方对应的变量 的地方对应的变量 正好是基变量。 正好是基变量。
第二节 运输问题初始基本可行解的求法
列变
列不变
列变
列变
x i1 j1 ,
行不变
x i1 j 2 ,
行变
x i2 j2 ,
行不变
x i 2 j3 , … , x i s j s ,
x i s j1
最终变到同一列（或同一行） 最终变到同一列（或同一行） 其中i表示行标 表示列标 表示行标， 也各不相同。 其中 表示行标，j表示列标 各不相同 ； 也各不相同。
第二节 运输问题初始基本可行解的求法
二．求初始基本可行解的方法 西北角法（参考课本例题） 西北角法（参考课本例题） 西北角法的一般步骤； 西北角法的一般步骤； 先决定左上角变量的值， 先决定左上角变量的值 ， 令这个变量取尽 可能大的值， 可能大的值 ， 并将这个数字标在对应运费 的右上角。 的右上角。 在填数的格子所在的行或列的应该为0的格 在填数的格子所在的行或列的应该为 的格 子上打“ 若行或列都应该取0， 子上打 “ ×”若行或列都应该取 ， 则在行 若行或列都应该取 上打“ 上打 “ ×”后， 就不能在列上打 “ ×”；反 后 就不能在列上打“ ； 在列上“ 后就不能在行上打“ 之 ， 在列上 “ ×”后就不能在行上打“ ×”。 后就不能在行上打 。

《运筹学》第三版（清华大学出版社）P79例1，表上作业法，运用西北角法确定初始基可行解。

西北角法是从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数；然后按行（列）标下一格的数；若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去；如此进行下去，直至得到一个基本可行解的方法。

西北角法的例子： P79例1从表1中可知，总的产量=总的销量，故产销是平衡的。

第一步：列出运价表和调运物资平衡表。

运用表上作业法时，首先要列出被调运物资的运价表和供需平衡表（简称平衡表），如表1，2所示。

第二步：编制初始调运方案。

首先在表2的西北角方格（即左上角方格，对应变量x11），尽可能取最大值：x11=min{3,7}=3将数值3填入该方格(见表3)。

由此可见x21,x31必须为0，即第一列其他各方格都不能取非零值，划去第一列。

在剩下的方格中，找出其西北角方格x12，x12=min{6,7-3}=4将4填入它所对应方格，第一行饱和，划去该行。

再找西北角方格x22，x22=min{6-4,4}=2将2填入x22所对应方格，于是第二列饱和，划去该列。

继续寻找西北方格为x23，x23=min{5,4-2}=2将2填入x23所对应方格，第二行饱和，划去该行。

剩下方格的西北角方格为x33，x33=min{5-2,9}=3将3填入x33所对应方格，第三列饱和，划去该列。

最后剩下x34方格，取x34 = 6。

这样我们就找到了m＋n-1＝3＋5-1＝7个基变量，它们为：x11 = 3,x12 = 4,x22 = 2,x23 = 2,x33 = 3,x34 = 6。

显然它们用折线连接后不形成闭回路。

这就是西北角法所找初始基可行解，所对应的目标值为：2×200＋1×250＋3×150＋1×150＋3×250＋3×300＋4×200＝4000我们找到的初始基可行解可通过各行方格中数值之和是否等于产量，各列方格中数值之和是否等于销量来简单验证。

4．最优解：（x13，x14，x21，x24，x32，x34）=（5，2，3，1，6，3）
5．提示：（1）产销平衡问题。（2）虚设一个销地G。（3）虚设一个产地B1，初始解
最好用差值法给出。
6．（1）x11=x22=x33=1，其余xij= 0。（2）x13=x22=x34=x41=1，其余xij=0。
（1）
销地
产地
B1
B2
B3
B4
B5
B6
产量
A1
20
10
30
A2
30
20
50
A3
10
10
50
5
75
A4
20
20
销量
20
40
30
10
50
25
（2）
销地
产地
B1
B2
B3
B4
B5
B6
产量
A1
30
30
A2
20
30
50
A3
10
30
10
25
75
A4
20
20
销量
20
40
30
10
20
25
（3）
销地
产地
B1
B2
B3
B4
人员
任务
E
J
G
R
甲
2
15
13
4
乙
10
4
14
15
丙
9
14
16
13
丁
7
8
11
9
答案与提示
一．1．×；2．×；3．√；4．√；5.×.

3.3试对、最小元素法、和vogel法进行比较，分析给出的解之质量不同的原因。

3.7试判断表3-30和表3-31中给出的调运方案可否作为表上作业法迭代时的基可行解？为什么？表3-313.11表3-36示出一个运输问题及它的一个解，试问：(1) 表中给出的解是否为最优解？请用位势法进行检验。

C由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。

(2) 若价值系数24(3) 若所有价值系数均增加1，最优解是否改变？为什么？(4) 若所有价值系数均乘以2，最优解是否改变？为什么？4.2 利用图解法解下列目标规划问题：(1) min {}+++-+1323211),2(,d P d d P d Pst.⎪⎪⎭⎪⎪⎬⎫⎪⎪⎩⎪⎪⎨⎧=≥=-+=-+=-+++-+-+-+-3,2,10,,,40401502213322211121i d d x x d d x d d x d d x x i i (2) min {})5.1(,,),(4342312431---+++++d d P d P d P d d PSt.⎪⎪⎪⎭⎪⎪⎪⎬⎫⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=-+=-+=-++=-+++-+-+-+-+-4,3,2,10,,,1530100402144233122211121i d d x x d d x d d x d d x x d d x x i i4.3 用单纯形法解下列目标规划问题：（1） min {})35(,,),(2343322111++--+-++d d P d P d P d d Pst.⎪⎪⎭⎪⎪⎬⎫⎪⎪⎩⎪⎪⎨⎧=≥=-+=-+=-+++-+-+-+-3,2,10,,,1400325005800213322211121i d d x x d d x d d x d d x x i i (2) min {}+--+-+144332211),35(,,d P d d P d P d PSt.⎪⎪⎪⎭⎪⎪⎪⎬⎫⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=-+=-+=-++=-+++-+-+-+-+-4,3,2,10,,,457090802144233122211121i d d x x d d x d d x d d x x d d x x i i4.4对于目标规划问题min {})53(),35(,,3243234211++--+-++d d P d d P d P d PSt.⎪⎪⎪⎭⎪⎪⎪⎬⎫⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=-+=-+=-+=-+++-+-++-+-+-4,3,2,10,,,10457080214413322211121i d d x x d d d d d x d d x d d x x i i（1） 用单纯形法求问题的满意解；（2） 若目标函数变为min {}+++---++4432332211),53(),35(,d P d d P d d P d P则满意解有什么变化？（3） 分别对第二和第三优先级各目标权系数作灵敏度分析。

A1
X11
X12
X13
80 150 65 100 75 250
A2
X21
X22
X23
100
150
200
销量
450
非基变量X12的检验数：
12 =（c12+c23）-（c13+c22）
=70+75-（100+65）=-20，
非基变量X21的检验数：
21 =（c21+c13）-（c11+c23）
=80+100-（90+75）=15。
得到初始调运方案为： x11=100,x13=100,x22=150,x23=100
总运价为： 9* 0 10 100 *100 60* 5 15 100 *100 3087
2西北角法
不是优先考虑具有最小单位运价的供销业 务,而是优先满足运输表中西北角左上角 上空格的供销要求
用西北角法确定初始调运方案
取
中ij最小0者对应的变量为换
入变量；
2、当迭代到运输问题的最优解时,如果 有某非基变量的检验数等于0,则说明该 运输问题有多重最优解；
3当运输问题某部分产地的产量和,与某部分销 地的销量和相等时,在迭代过程中间有可能有某 个格填入一个运量时需同时划去运输表的一行 和一列,这时就出现了退化.为了使表上作业法 的迭代工作能顺利进行下去,退化时应在同时划 去的一行或一列中的某个格中填入0,表示这个 格中的变量是取值为0的基变量,使迭代过程中 基变量个数恰好为m+n-1个.
u 1 v1 c11 90
u u
1 2
v3 v2
c13 c 22
100 65
u 2 v 3 c 23 75

B1 A1 A2 A3 vj 3 1 11 9 B2 3 4 2 8 B3 10 3 B4
ui
u 01 u -1 2
3
7 v2 1 4 6 v9 2 10
1
5 3 v3 3 v4 10
u 3 -5
3.最优性检验
B1 A1 A2 3
(1)
B2 11
(2)
B3 3 4 2 8 10
B4 3
ui
0 -1
1
9
3
7 2 4 6 9 3 10
1
5 3 10
A3
vj
-5
ij=Cij-（Ui+Vj） 11=C11-（U1+V1）=3-(0+2)=1
12=C12-（U1+V2）=11-(0+9)=2
3.最优性检验
B1 A1 A2 A3
11=1
B2
12=2 22=1
B3 4
B4 3
24= -1
产量 7 4 9
1）设产地Ai对应的位势量为ui ，销地Bj对应的位势量为vj； 2）由ij=Cij-（Ui+Vj）,利用对基变量而言有ij=0，计算位 势Ui ， Vj ，即Cij-（Ui+Vj） = 0，令U1=0； 3）再由ij=Cij-（Ui+Vj）计算非基变量的检验数ij
3.最优性检验
4.方案调整
闭回路调整法步骤： 1、入基变量的确定：选负检验数中最小者 rk，那 么 xrk 作为进基变量；（使总运费尽快减少） 2、出基变量的确定：在进基变量xrk 的闭回路上， 选取偶数顶点上调运量最小的值，将其对应的运量 作为出基变量。（刚好有一个基变量出基，其它基 变量都为正）
2

41、学问是异常珍贵的东西，从任何源泉吸 收都不可耻。——阿卜·日·法拉兹42、只有在来自群中间，才能认识自 己。——德国
43、重复别人所说的话，只需要教育； 而要挑战别人所说的话，则需要头脑。—— 玛丽·佩蒂博恩·普尔
运输问题-初始基可行解的确定
16、人民应该为法律而战斗，就像为 了城墙 而战斗 一样。 ——赫 拉克利 特 17、人类对于不公正的行为加以指责 ，并非 因为他 们愿意 做出这 种行为 ，而是 惟恐自 己会成 为这种 行为的 牺牲者 。—— 柏拉图 18、制定法律法令，就是为了不让强 者做什 么事都 横行霸 道。— —奥维 德 19、法律是社会的习惯和思想的结晶 。—— 托·伍·威尔逊 20、人们嘴上挂着的法律，其真实含 义是财 富。— —爱献 生
44、卓越的人一大优点是：在不利与艰 难的遭遇里百折不饶。——贝多芬
45、自己的饭量自己知道。——苏联

3.3试对、最小元素法、和vogel法进行比较，分析给出的解之质量不同的原因。

3.7试判断表3-30和表3-31中给出的调运方案可否作为表上作业法迭代时的基可行解？为什么？表3-313.11表3-36示出一个运输问题及它的一个解，试问：(1) 表中给出的解是否为最优解？请用位势法进行检验。

C由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。

(2) 若价值系数24(3) 若所有价值系数均增加1，最优解是否改变？为什么？(4) 若所有价值系数均乘以2，最优解是否改变？为什么？4.2 利用图解法解下列目标规划问题：(1) min {}+++-+1323211),2(,d P d d P d Pst.⎪⎪⎭⎪⎪⎬⎫⎪⎪⎩⎪⎪⎨⎧=≥=-+=-+=-+++-+-+-+-3,2,10,,,40401502213322211121i d d x x d d x d d x d d x x i i (2) min {})5.1(,,),(4342312431---+++++d d P d P d P d d PSt.⎪⎪⎪⎭⎪⎪⎪⎬⎫⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=-+=-+=-++=-+++-+-+-+-+-4,3,2,10,,,1530100402144233122211121i d d x x d d x d d x d d x x d d x x i i4.3 用单纯形法解下列目标规划问题：（1） min {})35(,,),(2343322111++--+-++d d P d P d P d d Pst.⎪⎪⎭⎪⎪⎬⎫⎪⎪⎩⎪⎪⎨⎧=≥=-+=-+=-+++-+-+-+-3,2,10,,,1400325005800213322211121i d d x x d d x d d x d d x x i i (2) min {}+--+-+144332211),35(,,d P d d P d P d PSt.⎪⎪⎪⎭⎪⎪⎪⎬⎫⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=-+=-+=-++=-+++-+-+-+-+-4,3,2,10,,,457090802144233122211121i d d x x d d x d d x d d x x d d x x i i4.4对于目标规划问题min {})53(),35(,,3243234211++--+-++d d P d d P d P d PSt.⎪⎪⎪⎭⎪⎪⎪⎬⎫⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=-+=-+=-+=-+++-+-++-+-+-4,3,2,10,,,10457080214413322211121i d d x x d d d d d x d d x d d x x i i（1） 用单纯形法求问题的满意解；（2） 若目标函数变为min {}+++---++4432332211),53(),35(,d P d d P d d P d P则满意解有什么变化？（3） 分别对第二和第三优先级各目标权系数作灵敏度分析。

产 量
12
3
11 16 0 0
9 10 1 1
68
22 1 2
14 6 48
3 3
销 地 产地
A1
A2
A3
销量
列1
罚
数2 3
B1
B2
4
12
2
10
8
5
14
8 14
2
5
2
2
B3 4
3
11
12 1 1 1
行罚数
B4
产 量
12
3
11 16 0 0 0
92
8 10 1 1 1
6 8 22 1 2 14 6 48
4
12
A1 8
8
4
11
16
②
A2
2
10
3
6
4
9 10
④
A3
8
5
11
6 14
8
x34
22
销量 8
14 6 12 8 1448①ຫໍສະໝຸດ ③⑤表 3-2
销地
产地
B1
B2
B3
B4
4
12
4
11
A1 8
8
2
10
3
9
A2
6
4
A3
8
5
11
6
8
销量 8
14 6 12 8 14
产 量
16 ②
10
④
2214 ⑥
48
①
③
⑤
⑥
此时得到一个初始调运方案（初始可行解）： x11 8, x12 8, x22 6, x23 4, x33 8, x34 14, 其余变量全等于零。 此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6).