运输问题的匈牙利解法和表上作业法

运输问题的求解方法(过程)——表上作业法的解题思路和原理、具体步骤。

运输问题是一种常见的工业应用问题,涉及到如何安排运输工具和货物,以最小化总成本或最大化利润。

表上作业法(Tableau Programming)是解决运输问题的一种有效方法,其解题思路和原理、具体步骤如下:1. 确定问题的状态在表上作业法中,我们需要先确定问题的状态。

状态是指某个特定时间段内,某个运输问题需要满足的条件。

例如,在一个例子中,我们可以将运输问题的状态定义为“需要从A城市运输货物到B城市,运输工具数量为3,运输距离为100公里”。

2. 定义状态转移方程接下来,我们需要定义状态转移方程,以描述在不同状态下可能采取的行动。

例如,在这个问题中,我们可以定义一个状态转移方程,表示当运输工具数量为2时,货物可以运输到B城市,而运输距离为80公里。

3. 确定最优解一旦我们定义了状态转移方程,我们就可以计算出在不同状态下的最优解。

例如,在这个问题中,当运输工具数量为2时,货物可以运输到B城市,运输距离为80公里,总成本为200元。

因此,该状态下的最优解是运输距离为80公里,运输工具数量为2,总成本为200元。

4. 确定边界条件最后,我们需要确定边界条件,以确保问题的状态不会无限制地变化。

例如,在这个问题中,当运输工具数量为3时,运输距离为120公里,超过了B城市的运输距离范围。

因此,我们需要设置一个限制条件,以确保运输工具数量不超过3,且运输距离不超过120公里。

表上作业法是一种简单有效的解决运输问题的方法,其原理和具体步骤如下。

通过定义状态转移方程、确定最优解、确定边界条件,我们可以计算出问题的最优解,从而实现最小化总成本和最大化利润的目标。

运筹学运输问题,表上作业法运筹学李细霞 2013物流工程1班 2014~2015学年第二学期运筹学运输问题,表上作业法课程主要内容绪论线性规划及单纯形法对偶理论与灵敏度分析目标规划整数规划运输问题动态规划图与网络运筹学运输问题,表上作业法第三章运输问题Transportation problem运筹学运输问题,表上作业法学习目标什么是运输问题？复杂运输问题如何解决运输问题？运筹学运输问题,表上作业法用单纯形法求解线性规划问题的步骤基本可行解基变换初始解最优性检验调整检验数18运筹学运输问题,表上作业法表上作业法单纯形法在求解运输问题时的一种简化方法运筹学运输问题,表上作业法表上作业法步骤1.西北角法 2.最小元素法3.伏格尔法闭回路法初始方案最优性检验方案调整1.闭回路法2.位势法20运筹学运输问题,表上作业法B1 A1 A2 A3 销量B2B3B4 10 8 5 6产量 7 4 9总产=总销31 7 311 94 632 10 5运筹学运输问题,表上作业法最小元素法西北角法初始方案的确定伏格尔法运筹学运输问题,表上作业法西北角法B1 A1 A2 A3 销量3 4有何疑问？B2 4 2B3B4产量32 3 67 4 93656Z cij xij 3 3 11 4 9 2 2 2 10 3 5 6 108i 1 j 123 运筹学运输问题,表上作业法西北角法的优劣？太简单咯！最优解有点望尘莫及呢24。

相抵后，总的运费增加了1个单位。由检验数的经济
含义可以知道，（A，甲）处单位运量调整所引起的
运费增量就是（A，甲）的检验数，即σ 11=1。
仿照此步骤可以计算初始方案中所有空 格的检验数，表4-25～表4-30展示了各 检验数的计算过程，表4-30给出了最终 结果。可以证明，对初始方案中的每一 个空格来说“闭合回路存在且唯一”。
丁
3（+10） 24 = -1 3（-5）
6
产量（ai）
7 4 9
丁 3 24 = -1 3 6
产量（ai） 7 4 9
如果检验数表中所有数字均大于等于零， 这表明对调运方案做出任何改变都将导 致运费的增加，即给定的方案是最优方 案。在表4-30中， 24 = -1,说明方案 需要进一步改进。
表4-4 甲乙 丙
A
B
3
1
C
销量（bj） 3
6
5
表4-5
甲乙 丙
A
3 11
3
B
1
9
2
C
7
4
10
销量（bj） 3
6
5
丁 产量（ai） 7 4 9
6
丁 产量（ai）
10
7
8
4
5
9
6
表4-5
甲乙 丙
A
3 11
3
B
1
9
2
C
7
4
10
销量（bj） 3
6
5
丁 产量（ai）
10
7
8
4
5
9
6
第三步：在表4-5中再找出最小运价“3”， 这样一步步地进行下去，直到单位运价表上 的所有元素均被划去为止。

10
应用西北角法、最小元素法和 Vogel法，每次填完数，都只划去一 行或一列，只有最后一个元例外（同 时划去一行和一列）。当填上一个数 后行、列同时饱和时，也应任意划去 一行（列），在保留的列（行）中没 被划去的格内标一个0。
11
[例 3-2] 某食品公司下属的 A1、A2、 A3 ，3 个厂生产方便食品，要运输到 B1、 B2、B3、B4 ，4 个销售点，数据如下： 表1 B1 B2 A1 3 11 A2 1 9 A3 7 4 销量 bj 3 6 求最优运输方案。 B3 3 2 10 5 B4 产量 ai 10 7 8 4 5 9 6 20（产销平衡）
（1）西 北 角 法 B3 B4 10
产量 ai 7
8 2 5 3 6 6
4
9
销量 bj
3
6
5
20
14
（ 2） 最 小 元 素 法 B1 B2 A1 3 11
B3 3 4 10
B4
产 量 ai 7 3
A2
1 3
9
2 1
8
4
A3
7
4 6
10
5 3 5 6
9
销 量 bj
3
6
2015
（ 2） 最 小 元 素 法 B1 B2 A1 3 11
(4)若运输平衡表中所有的行与列均被 划去，则得到了一个初始基本可行解。否 则在剩下的运输平衡表中选下一个变量， 转(4)。
4
上述计算过程可用流程图描述如下
取未划去的单元格xij ,令 xij = min { ai , bj }
ai’ = ai - xij bj’ = bj - xij
否
ai’ = 0?
第二节 运输问题求解 —表上作业法

运输问题的求解方法(过程)——表上作业法的解题思路和原理、具体步骤。

运输问题是指在给定的供应地和需求地之间，选择最佳的运输方案，使总运输成本最低的问题。

表上作业法是一种常用的解决运输问题的方法，它基于线性规划的思想，通过逐步逼近最优解的方式来求解运输问题。

表上作业法的原理是将运输问题转化为一个线性规划问题，通过构建一个供需平衡表来描述运输问题。

在该表中，将供应地和需求地分别作为行和列，并在表中填入运输量的变量。

同时，引入一个辅助表来记录每个供应地和需求地的运输量。

具体的求解步骤如下：1. 构建供需平衡表：将给定的供应地和需求地以及对应的运输量填入表格中，并计算每个供应地和需求地的供应总量和需求总量。

2. 确定初始基本可行解：根据运输量的限制条件，确定一个初始的基本可行解。

可以选择将某些运输量设置为0，使得每个供应地和需求地都满足其供应总量和需求总量。

3. 计算单位运输成本：根据给定的运输成本，计算每个供应地和需求地之间的单位运输成本，填入表格中。

4. 判断最优解条件：检查当前的基本可行解是否满足最优解的条件。

如果每个供应地和需求地都满足其供应总量和需求总量，并且没有其他更低成本的运输方案，则当前解为最优解。

5. 迭代改进解：如果当前解不满足最优解的条件，则需要进行迭代改进。

在每一次迭代中，选择一个非基本变量（即非0运输量）进行改变，并计算改变后的基本可行解。

6. 更新供需平衡表和辅助表：根据改变后的基本可行解，更新供需平衡表和辅助表的运输量，并重新计算单位运输成本。

7. 重复步骤4-6，直到找到最优解为止。

通过以上的步骤，表上作业法能够有效地求解运输问题，并得到最优的运输方案。

它在实践中广泛应用于物流管理、供应链优化等领域，为运输问题的决策提供了科学的依据。

2、确定初始方案的步骤：
（1）选择一个xij，令xij= min{ai，bj}=
第 a 第i个产地的产量全部运到 j个销地 i b 满足第j个销地需求 j
将具体数值填入xij在表中的位置；
（2）调整产销剩余数量：从ai 和bj 中分别减去 xij的值，若ai-xij=0，则划去产地Ai所在的行，即 该产地产量已全部运出无剩余，而销地Bj 尚有 需求缺口bj-ai ；若bj-xij =0，则划去销地Bj 所在 的列，说明该销地需求已得到满足，而产地Ai 尚有存余量ai-bj； （3）当作业表中所有行或列均被划去，说明所 有的产量均已运到各销地，需求全部满足，xij 的取值构成初始方案。否则，在作业表剩余的 格子中选择下一个决策变量，返回步骤（2）。
200 250 450
例3-2
的数学模型
min Z 90x11 70x12 100x13 80x21 65x22 75x23 总运输量 x11 x12 x13 200 x x x 250 日产量约束 21 22 23 x11 x21 100 s.t. x12 x22 150 需求约束 x13 x23 200 xij 0, i 1,2; j 1,2,3;
3、举例
例3-2 甲、乙两个煤矿供应A、B、C 三个城市用煤，各煤矿产量及各城 市需煤量、各煤矿到各城市的运输 距离见表3-4，求使总运输量最少的 调运方案。
表3-4
运距 煤矿 甲 乙 日销量 （需求量） 90 80 100 城市
例3-2有关信息表
A B C
日产量 （供应量）
70 65 150
100 75 200
可以证明，如果对闭回路的方向不加区别， 对于每一个非基变量而言，以其为起点的闭回 路存在且唯一。

运筹学课程设计指派问题的匈牙利法专业：姓名：学号：1.算法思想：匈牙利算法的基本思想是修改效益矩阵的行或列，使得每一行或列中至少有一个为零的元素，经过修正后，直至在不同行、不同列中至少有一个零元素，从而得到与这些零元素相对应的一个完全分配方案。

当它用于效益矩阵时，这个完全分配方案就是一个最优分配，它使总的效益为最小。

这种方法总是在有限步內收敛于一个最优解。

该方法的理论基础是：在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最优分配。

2.算法流程或步骤：1.将原始效益矩阵C的每行、每列各元素都依次减去该行、该列的最小元素，使每行、每列都至少出现一个0元素，以构成等价的效益矩阵C’。

2.圈0元素。

在C’中未被直线通过的含0元素最少的行（或列）中圈出一个0元素，通过这个0元素作一条竖（或横）线。

重复此步，若这样能圈出不同行不同列的n个0元素，转第四步，否则转第三步。

3.调整效益矩阵。

在C’中未被直线穿过的数集D中，找出最小的数d，D中所有数都减去d，C’中两条直线相交处的数都加的d。

去掉直线，组成新的等价效益矩阵仍叫C’，返回第二步。

X=0，这就是一种最优分配。

最低总4.令被圈0元素对应位置的X ij=1,其余ij耗费是C中使X=1的各位置上各元素的和。

ij算法流程图：3.算法源程序：#include<iostream.h>typedef struct matrix{float cost[101][101];int zeroelem[101][101];float costforout[101][101];int matrixsize;int personnumber;int jobnumber;}matrix;matrix sb;int result[501][2];void twozero(matrix &sb);void judge(matrix &sb,int result[501][2]);void refresh(matrix &sb);void circlezero(matrix &sb);matrix input();void output(int result[501][2],matrix sb);void zeroout(matrix &sb);matrix input(){matrix sb;int m;int pnumber,jnumber;int i,j;float k;char w;cout<<"指派问题的匈牙利解法:"<<endl;cout<<"求最大值，请输入1;求最小值，请输入0:"<<endl;cin>>m;while(m!=1&&m!=0){cout<<"请输入1或0:"<<endl;cin>>m;}cout<<"请输入人数(人数介于1和100之间):"<<endl;cin>>pnumber;while(pnumber<1||pnumber>100){cout<<"请输入合法数据:"<<endl;cin>>pnumber;}cout<<"请输入工作数(介于1和100之间):"<<endl;cin>>jnumber;while(jnumber<1||jnumber>100){cout<<"请输入合法数据:"<<endl;cin>>jnumber;}cout<<"请输入"<<pnumber<<"行"<<jnumber<<"列的矩阵,同一行内以空格间隔,不同行间以回车分隔,以$结束输入:\n";for(i=1;i<=pnumber;i++)for(j=1;j<=jnumber;j++){cin>>sb.cost[i][j];sb.costforout[i][j]=sb.cost[i][j];}cin>>w;if(jnumber>pnumber)for(i=pnumber+1;i<=jnumber;i++)for(j=1;j<=jnumber;j++){sb.cost[i][j]=0;sb.costforout[i][j]=0;}else{if(pnumber>jnumber)for(i=1;i<=pnumber;i++)for(j=jnumber+1;j<=pnumber;j++){sb.cost[i][j]=0;sb.costforout[i][j]=0;}}sb.matrixsize=pnumber;if(pnumber<jnumber)sb.matrixsize=jnumber;sb.personnumber=pnumber;sb.jobnumber=jnumber;if(m==1){k=0;for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)if(sb.cost[i][j]>k)k=sb.cost[i][j];for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)sb.cost[i][j]=k-sb.cost[i][j];}return sb;}void circlezero(matrix &sb){int i,j;float k;int p;for(i=0;i<=sb.matrixsize;i++)sb.cost[i][0]=0;for(j=1;j<=sb.matrixsize;j++)sb.cost[0][j]=0;for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)if(sb.cost[i][j]==0){sb.cost[i][0]++;sb.cost[0][j]++;sb.cost[0][0]++;}for(i=0;i<=sb.matrixsize;i++)for(j=0;j<=sb.matrixsize;j++)sb.zeroelem[i][j]=0;k=sb.cost[0][0]+1;while(sb.cost[0][0]<k){k=sb.cost[0][0];for(i=1;i<=sb.matrixsize;i++){if(sb.cost[i][0]==1){for(j=1;j<=sb.matrixsize;j++)if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0)break;sb.zeroelem[i][j]=1;sb.cost[i][0]--;sb.cost[0][j]--;sb.cost[0][0]--;if(sb.cost[0][j]>0)for(p=1;p<=sb.matrixsize;p++)if(sb.cost[p][j]==0&&sb.zeroelem[p][j]==0){sb.zeroelem[p][j]=2;sb.cost[p][0]--;sb.cost[0][j]--;sb.cost[0][0]--;}}}for(j=1;j<=sb.matrixsize;j++){if(sb.cost[0][j]==1){for(i=1;i<=sb.matrixsize;i++)if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0)break;sb.zeroelem[i][j]=1;sb.cost[i][0]--;sb.cost[0][j]--;sb.cost[0][0]--;if(sb.cost[i][0]>0)for(p=1;p<=sb.matrixsize;p++)if(sb.cost[i][p]==0&&sb.zeroelem[i][p]==0){sb.zeroelem[i][p]=2;sb.cost[i][0]--;sb.cost[0][p]--;sb.cost[0][0]--;}}}}if(sb.cost[0][0]>0)twozero(sb);elsejudge(sb,result);}void twozero(matrix &sb){int i,j;int p,q;int m,n;float k;matrix st;for(i=1;i<=sb.matrixsize;i++)if(sb.cost[i][0]>0)break;if(i<=sb.matrixsize){for(j=1;j<=sb.matrixsize;j++){st=sb;if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0){sb.zeroelem[i][j]=1;sb.cost[i][0]--;sb.cost[0][j]--;sb.cost[0][0]--;for(q=1;q<=sb.matrixsize;q++)if(sb.cost[i][q]==0&&sb.zeroelem[i][q]==0){sb.zeroelem[i][q]=2;sb.cost[i][0]--;sb.cost[0][q]--;sb.cost[0][0]--;}for(p=1;p<=sb.matrixsize;p++)if(sb.cost[p][j]==0&&sb.zeroelem[p][j]==0){sb.zeroelem[p][j]=2;sb.cost[p][0]--;sb.cost[0][j]--;sb.cost[0][0]--;}k=sb.cost[0][0]+1;while(sb.cost[0][0]<k){k=sb.cost[0][0];for(p=i+1;p<=sb.matrixsize;p++){if(sb.cost[p][0]==1){for(q=1;q<=sb.matrixsize;q++)if(sb.cost[p][q]==0&&sb.zeroelem[p][q]==0)break;sb.zeroelem[p][q]=1;sb.cost[p][0]--;sb.cost[0][q]--;sb.cost[0][0]--;for(m=1;m<=sb.matrixsize;m++)if(sb.cost[m][q]=0&&sb.zeroelem[m][q]==0){sb.zeroelem[m][q]=2;sb.cost[m][0]--;sb.cost[0][q]--;sb.cost[0][0]--;}}}for(q=1;q<=sb.matrixsize;q++){if(sb.cost[0][q]==1){for(p=1;p<=sb.matrixsize;p++)if(sb.cost[p][q]==0&&sb.zeroelem[p][q]==0)break;sb.zeroelem[p][q]=1;sb.cost[p][q]--;sb.cost[0][q]--;sb.cost[0][0]--;for(n=1;n<=sb.matrixsize;n++)if(sb.cost[p][n]==0&&sb.zeroelem[p][n]==0){sb.zeroelem[p][n]=2;sb.cost[p][0]--;sb.cost[0][n]--;sb.cost[0][0]--;}}}}if(sb.cost[0][0]>0)twozero(sb);elsejudge(sb,result);}sb=st;}}}void judge(matrix &sb,int result[501][2]){int i,j;int m;int n;int k;m=0;for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==1)m++;if(m==sb.matrixsize){k=1;for(n=1;n<=result[0][0];n++){for(i=1;i<=sb.matrixsize;i++){for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==1)break;if(i<=sb.personnumber&&j<=sb.jobnumber)if(j!=result[k][1])break;k++;}if(i==sb.matrixsize+1)break;elsek=n*sb.matrixsize+1;}if(n>result[0][0]){k=result[0][0]*sb.matrixsize+1;for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==1){result[k][0]=i;result[k++][1]=j;}result[0][0]++;}}else{refresh(sb);}}void refresh(matrix &sb){int i,j;float k;int p;k=0;for(i=1;i<=sb.matrixsize;i++){for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==1){sb.zeroelem[i][0]=1;break;}}while(k==0){k=1;for(i=1;i<=sb.matrixsize;i++)if(sb.zeroelem[i][0]==0){sb.zeroelem[i][0]=2;for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==2){sb.zeroelem[0][j]=1;}}for(j=1;j<=sb.matrixsize;j++){if(sb.zeroelem[0][j]==1){sb.zeroelem[0][j]=2;for(i=1;i<=sb.matrixsize;i++)if(sb.zeroelem[i][j]==1){sb.zeroelem[i][0]=0;k=0;}}}}p=0;k=0;for(i=1;i<=sb.matrixsize;i++){if(sb.zeroelem[i][0]==2){for(j=1;j<=sb.matrixsize;j++){if(sb.zeroelem[0][j]!=2)if(p==0){k=sb.cost[i][j];p=1;}else{if(sb.cost[i][j]<k)k=sb.cost[i][j];}}}}for(i=1;i<=sb.matrixsize;i++){if(sb.zeroelem[i][0]==2)for(j=1;j<=sb.matrixsize;j++)sb.cost[i][j]=sb.cost[i][j]-k;}for(j=1;j<=sb.matrixsize;j++){if(sb.zeroelem[0][j]==2)for(i=1;i<=sb.matrixsize;i++)sb.cost[i][j]=sb.cost[i][j]+k;}for(i=0;i<=sb.matrixsize;i++)for(j=0;j<=sb.matrixsize;j++)sb.zeroelem[i][j]=0;circlezero(sb);}void zeroout(matrix &sb){int i,j;float k;for(i=1;i<=sb.matrixsize;i++){k=sb.cost[i][1];for(j=2;j<=sb.matrixsize;j++)if(sb.cost[i][j]<k)k=sb.cost[i][j];for(j=1;j<=sb.matrixsize;j++)sb.cost[i][j]=sb.cost[i][j]-k;}for(j=1;j<=sb.matrixsize;j++){k=sb.cost[1][j];for(i=2;i<=sb.matrixsize;i++)if(sb.cost[i][j]<k)k=sb.cost[i][j];for(i=1;i<=sb.matrixsize;i++)sb.cost[i][j]=sb.cost[i][j]-k;}}void output(int result[501][2],matrix sb) {int k;int i;int j;int p;char w;float v;v=0;for(i=1;i<=sb.matrixsize;i++){v=v+sb.costforout[i][result[i][1]];}cout<<"最优解的目标函数值为"<<v;k=result[0][0];if(k>5){cout<<"解的个数超过了限制."<<endl;k=5;}for(i=1;i<=k;i++){cout<<"输入任意字符后输出第"<<i<<"种解."<<endl;cin>>w;p=(i-1)*sb.matrixsize+1;for(j=p;j<p+sb.matrixsize;j++)if(result[j][0]<=sb.personnumber&&result[j][1]<=sb.jobnumber)cout<<"第"<<result[j][0]<<"个人做第"<<result[j][1]<<"件工作."<<endl;}}void main(){result[0][0]=0;sb=input();zeroout(sb);circlezero(sb);output(result,sb);}4. 算例和结果：自己运算结果为：->⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡3302102512010321->⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡330110241200032034526635546967562543----⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡可以看出：第1人做第4件工作；第2人做第1件工作；第3人做第3件工作；第4人做第2件工作。

2
P 4 6 5 6
3
P 1 5 4 5
4
A B C D
c
ij
OR课件
装卸组 待卸车
TP & AP
P 4 2 4 3
1
P 3 3 3 2
2
P 4 6 5 6
3
P 1 5 4 5
4
§5 指 派 问 题
A B C D
bj
ai 1 1
1
1
1
1
1
1
解：引入0－1变量xij， 并令:
Z
min
cij xij
3
产 量 9 5 7 4
A 虚 销 量
OR课件
TP & AP
问题的提出
§5 指 派 问 题
设有n个人，需要分派他们去做n件 工作。要求一个人做一件事，一件事只
能由一个人完成；由于每人的专长不同，
各人做任一种工作的效率可能不同，因
而创造的价值也不同。问如何安排，才
能使创造的总价值最大？
OR课件
TP & AP
Z
min
TP & AP
cij xij
i 1 j 1 n ij
n
n

x
j 1 n
1 , i 1, 2, , n 1, j 1, 2, , n
x
i 1
ij
x
ij
0 或1
特殊的运输问题
OR课件
TP & AP
算法原理
OR课件
TP & AP
§2 表 上 作 业 法
算法的提出：观测模型的特征 【简例】已知有关资料如下表

3
版权所有 违者必究
精品课程《运筹学》
版权所有 违者必究
精品课程《运筹学》
版权所有 违者必究
精品课程《运筹学》
版权所有 违者必究
例1：三煤矿A1，A2，A3运往B1，B2，B3，B4三个城市 销售，各煤矿的供应量和需求量如下页表，各城市的需 求量其间的距离(或单位运价)cij如表下页表方格中的数 据所示，试建立使总运输量(或总运费)最小的运输问题 数学模型。
销售地Bj B1 1 x11=20 7 3 x31=10 30 3 2 x32=25 25 10 5 x23=10 9 8 x24=10 4 x34=5 15 B2 6 B3 2 B4 10
供应 量 ai 20 20 40 80 80
9
版权所有 违者必究
西北角法分配初始调运方案
单价cij A1 供 应 地 Ai A2 A3 需求量bj
15
版权所有 违者必究
重新调整调运方案，现再用位势法或闭回路法求这个新 解各非基变量的检验数，结果示于下页表中。由于所有 非基变量的检验数全非负，故这个解为最优解。
16
版权所有 违者必究
位势法或闭回路法计算新检验数结果
vi ui u1=1 u2=4 u3=3 需求量bj
v1=(0) 1 x11=20 7 σ21=3 3 x31=10 30
v2=–1 6 σ12=6 3 x22=10 2 x32=15 25
v3=–2 2 σ13=0 5 x23=10 9 σ33=5 10
v4=1 10 σ14=8 8 σ24=3 4 x34=15 15
供应量 ai 20 20 40
17
版权所有 违者必究
步骤 （1）找出初始即可行解，即在产销平衡表上分配 初始调运方案，保证xij≥0， （又称实格）必须有m+n-1个； （2）求出各非基变量的检验数σij（空格检验数）， σij≥0时停止计算；σij<0时在继续调整调运方案（换 基迭代法）； （3）确定进基变量（空格换入变量）和出基变量 （实格调出变量），找出新的基可行解（用空格闭 回路法调整）； （4）重复第1-3步，直至获得σij≥0，输出xij*和 minZ=Z*为止。

扩展适用范围
进一步扩展表上作业法的适用范 围，使其能够处理更多类型的运 输问题，包括带有特殊约束条件 的运输问题。
引入现代信息技术
利用现代信息技术，如大数据和 云计算等，提高表上作业法的计 算效率和精度，以满足实际应用 的需求。
THANKS
感谢您的观看
的优化配置。
应用实例二：农产品运输问题
总结词
多约束优化问题
详细描述
农产品运输问题需要考虑时间、保鲜度、运 输量等多种约束条件，要求在满足需求的前 提下，实现运输成本和损耗的最小化。表上 作业法可以通过多目标优化算法，综合考虑 各种约束条件，制定最优的农产品运输方案
。
应用实例三：城市物流配送问题
要点一
在迭代过程中，需要有一个判断准则来确定何时停止迭代并输出最优解。常用的判断准则包括最大最 小准则和最小最大准则。
迭代求解
根据判断准则，通过不断调整运输方案，使目标函数（通常是总运输费用最小）逐渐逼近最优解。在 每次迭代中，需要检查运输方案的可行性，并更新基可行解。
终止阶段：确定最优解并输出结果
确定最优解
03
表上作业法原理
表上作业法的定义与步骤
在此添加您的文本17字
定义：表上作业法是一种求解运输问题的线性规划方法， 通过在运输表上逐行计算和调整，最终找到最优解。
在此添加您的文本16字
步骤
在此添加您的文本16字
1. 建立初始运输方案；
在此添加您的文本16字
2. 检查运输方案的可行性；
在此添加您的文本16字
确定单位运输成本
根据运输距离、运输方式等因素确定单位运输成本。
建立数学模型
根据供求关系、运输能力限制等因素建立线性规划模型。

第二步：进行试指派以寻求最优解。
（1）进行行检验：从只有一个0元素的行开始，给这 个0元素加（），记作（0）；再划去（0）所在列的其它 0元素，记作φ。若遇到有两个0元素以上的行，先放下。 （2）进行列检验：给只有一个0元素的列0元素加（） ，记作（0）；然后划去（0）所在行的0元素，记作φ。 （3）再对两个以上0元素的行和列标记，任意取一个 加（）。
B1 A1 A2 A3 4 7 6
B2 8 9 9
B3 7 17 12
B4 15 14 8
B5 12 10 7
A4
A5
6
6
7
9
14
12
6
10
10
6
三、其它指派问题
（1）目标函数求最大值的指派问 题 对于此问题可做一个新的 矩阵B=(bij)。找出原矩阵的最 大元素m，令B=(bij)=m-cij
∑
产 量 与 销 量 平 衡
解： 设产地Ai到销地Bi的运量为xij，由问题构造运量平衡表
可以知道：
（1）产销平衡 （2）Ai运出量等于产量 （3）Bj运入量等于销量
a b
i 1 i j1
m
n
j
x
j 1
n
ij
ai
x
i 1
m
ij
bj
运量平衡表
销地Bi 运价 产地Ai A1 A2 C11 C21 C12 C22 B1 B2
4 2 (cij ) 4 3 3 3 3 2 4 6 5 6 1 - 1 3 5 - 2 0 1 4 - 3 5 -2 1 2 1 0 0 3 0 - 1 3 4 3 - 2 0 1 2 1-3 4 3 -2 1 -2 2 1 0 0 1 2 0 2 0 3 (b ) ij 1 3

用改进的匈牙利算法求解运输问题李雪娇，于洪珍中国矿业大学信电学院，江苏徐州 (221008)Email ：liaohuchushan@摘 要：本文提出用改进的匈牙利算法求解运输问题。

此算法不但可以直接求取最优解，而且在运量受限制的运输问题中有很好的应用。

关键词：改进，匈牙利算法，运输问题，最优解0. 引言在现实生活中，我们常常会遇到许多运输问题。

运输问题的求解多采用表上作业法。

在此方法中，我们需要先利用最小元素法或西北角法求出一组基本可行解，再对此解检验其最优性。

若此解非最优解，则又要进行解的改进。

这一过程比较麻烦，尤其对一些结构不太大的模型，编程时往往过于繁琐。

同时，经典运输问题在实际应用中有很大的局限性, 对一些运输量受限制或运输能力受限制的运输问题，我们无法用表上作业法直接求取。

在此，我们采用改进的匈牙利算法处理这类运输问题。

为了便于描述，设物资供应量12[...]m A a a a =，物资需求量12[...]n B b b b =，从到i A j B 的单物的物资运价，最小运输量 (假设m )。

i j C i j L n >1. 匈牙利算法[1][4]匈牙利算法的基本思想是修改效益矩阵的行和列，使得每行和每列中至少有一个零元素。

经过一定的变换，得到不同行、不同列只有一个零元素。

从而得到一个与这些零元素相匹配的完全分配方案。

这种方法总是在有限步内收敛于一个最优解。

该方法的理论基础是：在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最优解的分配。

求解步骤如下：第一步：使指派问题的系数矩阵经变换后，在各行各列中都出现零元素，即从系数矩阵的每行（或列）元素中减去该行（或列）的最小元素。

第二步：寻求找n 个独立的零元素，以得到最优解：（1）从只有一个0元素的行（或列）开始，对这个0元素加圈，记为θ。

然后划去此元素所在列（或行）的其他0元素，记作∅。

反复进行，直到所有的0元素被划完。

（2）若仍有没有划圈的0元素，则从剩有0元素最少的行开始，比较这行0元素所在各列中0元素的数目，选择0元素少的那列的0元素加圈θ，然后划掉同行同列的其他0元素，反复进行直到所有的0元素被划掉或圈出。

运筹学课程设计报告书---运输问题的表上作业法运筹学课程设计报告书专业班级学号姓名LMZZ日期2011.09.01设计题目：运输问题的表上作业法设计方案：运输问题是一种应用广泛的网络最优化模型，该问题的主要目的是为物资调运、车辆高度选择最经济的运输路线。

有些问题，如m 台机床加工零件问题、工厂合理布局问题，虽要求与提法不同，经适当变化也可以使用本模型求得最佳方案。

运输问题的一般提法：某种物资有m 个产地Ai ，产量是ai （i ＝1，2,…,m ），有m 个销售地Bi ，销量(需求量)是bj(j=1,2,…,m)。

若从Ai 运到Bi 单位运价为dij(i=1,2,…,m;j=1,2,…,m),又假设产销平衡，即∑∑===m i n j j ib a 11问如何安排运输可使总运费最小？若用x ij (i=1,2,…,m;j=1,2,…,n)表示由A i 运到B j 的运输量，则平衡运输问题可写出以下线性规划模型：∑∑===m i n j ij ij x d Z 11min约束条件==≥====∑∑==),...,2,1;...,2,1(0)...,2,1()...,2,1(11n j m i x n j b x m i a x ij m i j ij n j i ij表上作业法原理同于单纯形法，首先给出一个初始的调运方案(实际上是初始基本可行解)，求出各非基变量的检验数去判定当前解是否为最优解，若不是则进行方案调整(即从一个基本可行解转换成另一个基本可行解)，再判定是否为最优解，重复以上步骤，直到获得最优解为止。

这些步骤在表上进行十分方便。

操作过程在表上进行方案实施：通过运输问题在C++程序中的运用，从而实现方案的最优。

程序主要分两部：（1）求解，（2）最优解判断结果与结论：程序运行过程中，依次输入所需要的运价，产量，销量等数据，单击回车可以再次现实所需数据，按任意键可以运行至求出初始可行解并显示，再次按任意键程序进行最优解的判断，并求出最优解，显示在程序页面上，从而可以得到该运输问题的最优方案。

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

郑州航 空工 业管理 学院 学报
一 九 八七 年
第一 期
匈牙 利 法解运输 问题初探
崔
摘要
.
耀
东
,
本 文 主 要介 绍 用 句 牙 利 解 法 把 分 配 问 题 转 化 为运 输 问题 进 行 求 解
在简
化 计 算方 面 获 得 了 较 好 的 效 果 一
、
引盲
,
所 谓分 配问题
n
即 在 每 项 资 源 只 分 配 给一 个 接 纳 者 的 前 提 下
.
,
销 地销 量均 为 1 )
用 匈 牙 利 法 求 出 解 答后
.
,
可 还 原 为运 输问 题
.
例一
、
已知 运 输 问 题 的 产 销 平 衡 表 与 单 位 运 价 表 如 表 1
试 转 化 为分 配 问 题
裹
1
裹2
I 产盈
B
B
!
产
净
\
, :
:
.
B
B
滋 B
B
B
3
-
:
: :
{
!
且 . 人舀
`
A 人 A
试 用匈 牙利 法求 解
.
表 3
一
-
二 一少 …
1
、
列出 初始 矩 阵
、
即 列 出 单 位 运 价 矩 阵 及 各行
列 相 应权 数
三 一
.
…
初 始 矩 阵 等价 于 解 分 配 问 题 的 8 阶 方 阵
,
3 3
7 7
7 3 6
7 7
7 2 2
6 6 4 2 2 2 5 5 5

13 11 2 0 10 11 5 7 4 1 4 2 4 2
0 6 ⇒B= 0 0
13 7 0 0 6 9 = (b ) ij 5 3 2 1 0 0
其每行、 经变换后的效率矩阵 B 中，其每行、每列至少有一个 零元素。 进行得： 零元素。对矩阵 B 零元素按 step2 进行得：
⇒ 0 1 10 2 3 6 9 5 4 0 1 0 3 4 6 0
由解矩阵得最优指派方案为 甲—D，乙—B ，丙—A，丁—C
小时) 小时 总的消耗时间为 min z＝C31+c22+c43+c14=28(小时
• 实例（m<n） 实例（ ）
例
3.5.3 标准指派问题的举例 标准指派问题的举例 个工人甲、 有 4 个工人甲、乙、丙、丁，要指派他们分别
完成 4 项工作 A、B、C、D，每人做各项工作所消耗的时 间如下表所示，问指派哪个人去完成哪项工作，可使总的 间如下表所示，问指派哪个人去完成哪项工作， 消耗时间为最小? A 甲 乙 丙 丁 15 19 26 19 B 18 23 17 21 C 21 22 16 23 D 24 18 19 17
• step4 在没有被直线覆盖的部分中找出最 小元素，然后在打√号的行各元素中都减 小元素，然后在打 号的行各元素中都减 去这最小元素，而在打√号的列的各元素 去这最小元素，而在打 号的列的各元素 都加上这是小元素，以保证原来的0元素 都加上这是小元素，以保证原来的 元素 不变．这样得到新的系数矩阵，若得到n 不变．这样得到新的系数矩阵，若得到 个独立的0元素 则已得到最优解， 元素， 个独立的 元素，则已得到最优解，否则 回到step3重复进行。 重复进行。 回到 重复进行
4.3.1指派问题的解法 指派问题的解法———匈牙利解法 指派问题的解法 匈牙利解法 • 这种方法是匈牙利数学家考尼格 这种方法是匈牙利数学家考尼格(Konig) 提出的，因此得名匈牙利解法。 提出的，因此得名匈牙利解法。 • 匈牙利法是针对指派问题的标准型进行 求解。 求解。