§5.4算法步骤
综合以上讨论,设计平衡型运输问题算法如下:
表上作业法:
1.利用最小元素法求的一个初始基本格子集及相应的初始基本可行解.
2.求关于基的检验数:.
3.令.
若,则即为的最优解;
否则,求出中的一条闭回路,并将划分为和,转4.
4.修正:令,,
,转2.
注:(1)本算法实际上是单纯形法在运输问题上的具体体现,它从算法的思想,步骤,设计到执行都体现了单纯形法的思想.表上作业法实质上就是单纯形法,只不过前者是在运输表上进行,而后者则是在单纯形表上进行.
(2)算法的步骤4实际上对应于单纯形法的转轴过程.
例1求解运输问题:,,.
解:作运输表,并利用最小元素法解之.
的一个基本格子集为,相应的基本可行解为,其它.
求位势和检验数:
.
求中的一条闭回路,并划分为和:
修正:.
求检验数:
,
的最优解为,其它,最优值为.▍
Ex.求解运输问题:,,.
解:最优解为,其它,最优值为.▍
综合以上讨论,设计平衡型运输问题算法如下:
表上作业法:
1.利用最小元素法求的一个初始基本格子集及相应的初始基本可行解.
2.求关于基的检验数:.
3.令.
若,则即为的最优解;
否则,求出中的一条闭回路,并将划分为和,转4.
4.修正:令,,
,转2.
注:(1)本算法实际上是单纯形法在运输问题上的具体体现,它从算法的思想,步骤,设计到执行都体现了单纯形法的思想.表上作业法实质上就是单纯形法,只不过前者是在运输表上进行,而后者则是在单纯形表上进行.
(2)算法的步骤4实际上对应于单纯形法的转轴过程.
例1求解运输问题:,,.
解:作运输表,并利用最小元素法解之.
的一个基本格子集为,相应的基本可行解为,其它.
求位势和检验数:
.
求中的一条闭回路,并划分为和:
修正:.
求检验数:
,
的最优解为,其它,最优值为.▍
Ex.求解运输问题:,,.
解:最优解为,其它,最优值为.▍