当前位置:文档之家› 运筹学-表上作业法

运筹学-表上作业法


3.最优性检验
B1
B2
B3
B4
A1 A2
A3 销量
3 11 =1 11
1
9
3
3 4
2 1
7
4
10
31 =10
6
3
6
5
10 3
8
5 3
6
产量 7 4 9
❖若让x11=1,则总运费变化:3–1+2–3=1 。 ❖若让x31=1,则总运费变化:7–5+10–3+2-1=10 。
3.最优性检验
A1 A2 A3 销量




产量
A
3
11
3
10
7
B
1
9
2
8
4
C
7
4
10
5
9
销量
3
6
5
6
2.确定初始基本可行解
x ❖ 若j=1设,2,3,i4j ) 代表从第i个产地到第j个销售地的运输量(i=1,2,3;
min z 3x11 11x12 3x13 10x14 x21 9x22 2x23 8x24 7x31 4x32 10x33 5x34
2.确定初始基本可行解
B1 B2 B3 B4 两最小元素之差
A1
3 11 3 10
7
A2
1 928
6
A3
7 4 10 5
两最小元素之 差
12
2.确定初始基本可行解
B1 B2 B3 B4 两最小元素之差
A1
3
A2
1
A3
7
两最小元素之 差
11 3 10 928 4 10 5
2
2.确定初始基本可行解
:
:
:
:
:
:
:
:
Am
cm1
cm2

cmn
am
销量
b1
b2

bn
1.运输问题模型及其求解思路
若销设平衡xij的代条表件从下第(Am ia个i 产n b地j 到)第,B要j个确销定售总地运的输调费运用量最,小在的产调
运方案,可表示为i1如下j1的数学模型
mn
min z
cij xij
❖ 具体操作步骤如下: ❖ (1)确定一个初始基本可行解:即在m×n阶产销平衡
表上给出m+n-1个数字格(基变量); ❖ (2)求各非基变量(空格)的检验数,即在表上
计算空格的检验数。判别式否达到最优解。如果是最优解, 则停止计算,否则进入下一步。 ❖ (3)确定换入变量和换出变量,找出新的基可行解。 ❖ (4)重复(2)、(3)直至得到最优解为止。
❖2、用最小元素法时,可能会出现基变量个 数还差两个以上但只剩下一行或一列的情 况,此时不能将剩下行或列按空格划掉, 应在剩下的空格中标上0。(退化的基本可 行解)
2.确定初始基本可行解
B1
B2
B3
B4
A1 3
11
3 5 10 3
A2 1
39
2 08
A3 7
4 6 10
53
销量
3
6
5
6
产量 8 3 9
min x23, x14 min1,3 1
四、方案调整
❖得到新的基变量:x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3。重新计算检验数。
B1
B2
B3
B4
产量ai
A1 3 (1) 11 (2) 3
10
5
2
7
A2 1
选取偶数顶点上调运量最小的值,将其对应的运量 作为出基变量。(刚好有一个基变量出基,其它基 变量都为正)
4.方案调整
➢ 即求=Min{xij闭回路上的偶数顶点的xij}= xpq。那么 确定xpq为出基变量,为调整量;
➢ 3、换基调整:对闭回路的奇数顶点运量调整为: xij+,对各偶数顶点运量调整为:xij-,特别 xpq=0,xpq变为非基变量。
1
1
1
1
· ·
·
1
· · ···
·
1
· ·
·
1
1
1
m行
n行
1.运输问题模型及其求解思路
对于产销平衡的运输问题, 若产地为m个,销地为n个, 则 变量个数为m×n个,
约束条件个数为m+n, 其中包含:总产量=总销售
故线性无关的约束条件个数为m+n-1, 基本解中的基变量个数为m+n-1。
2
1.运输问题模型及其求解思路
i1 j 1
n xij ai j 1
s.t.
m
xij bj
i 1
xij 0
min z CX
矩阵形式: s.t. AX b X0
(i=1,2,…,m; j=1,2,…,n)
1.运输问题模型及其求解思路
系数矩阵A
1 1 ··· 1
A=
1 1 ··· 1
1 1 ··· 1
❖ 已知有m个产地Ai(i=1,2, … , m )可供应某种 物资,其供应量(产量)分别为ai ,有n个销地Bj (j=1,2, … , n)其销量(需求量)分别为bj ,从 A到B的单位物资运价为cij 。
销地
B1
B2

Bn
产量
产地
A1
c11
c12

c1n
a1
A2
c21
c22

c2n
a2
:
:
:
:
❖运输问题中目标函数值要求最小化,因此, 当所有的检验数都大于或等于零时该调运 方案就是最优方案;否则不是。
❖下面介绍两种计算检验数的方法:
3.最优性检验
❖ 1、闭回路法 ❖ 闭回路:在已给出基本解的运输表上,从一个非基
变量出发,沿水平或竖直方向前进,只有碰到基变 量,才能向右或向左转90o (当然也可以不改变方向) 继续前进。 ❖ 这样继续下去,总能回到出发的那个非基变量,由 此路线形成的封闭曲线,叫闭回路。
运输问题求解
——表上作业法
运输问题求解之表上作业法
1.运输问题模型及其求解思路 2.确定初始基本可行解 3.最优性检验 4.方案调整
1.运输问题模型及其求解思路
❖运输问题: 研究把某种商品从若干个产地运至若 干个销售地而使总运费最小的一类 问题。
❖目标: 总运费最小
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
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
3 9 (2)2 (1) 8
1
4
A3 7 (9)4
10 (12)5
6
3
9
销量bj
3
6
5
6
四、方案调整
❖经过一次基变换,所有ij ≥ 0,已得到最优解: x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3,其它为0。
❖最优值: ❖f* =3×5+10×2+1×3+8×1+4×6+5×3 = 85
的偶数顶点运价之和)
❖ 2、位势法计算式: ❖ij = cij - ui – vj
当存在非基变量的检验数ij ≥0,说明现行方案为 最优方案,否则目标成本还可以进一步减小。
4.方案调整
➢ 闭回路调整法步骤: ➢ 1、入基变量的确定:选负检验数中最小者 rk,那
么 xrk 作为进基变量;(使总运费尽快减少) ➢ 2、出基变量的确定:在进基变量xrk 的闭回路上,
51
3
2.确定初始基本可行解
B1 B2 B3 B4 两最小元素之差
A1
3 11 3 10
0
A2
1ቤተ መጻሕፍቲ ባይዱ928
1
A3
7 4 10 5
2
两最小元素之 2 差
13
2.确定初始基本可行解
B1 B2 B3 B4 两最小元素之差
A1
3 11 3 10
0
A2
1 928
1
A3
7 4 10 5
两最小元素之 2 差
12
表上作业法计算中的相关问题
❖ 1.无穷多最优解
❖ 当最优方案中存在某空格(非基变量)检验数为0,时,则 该运输问题一定有多重最优解。
❖ 2.退化解
❖ 当运输问题的最优表中有数格(基变量)的运量为0,则 出现退化。
❖ 1)确定基本可行解中,出现同时需要划去一行和一列的 情况,则需要在填写数格的行或列上,写上一个0数格。
❖ ②从行和列的差额中选出最大者,选择其所在行或列中的 最小元素,按类似于最小元素法优先供应,划去相应的行 或列。
相关主题