最优化理论——运输问题的案例

《最优化理论——运输问题的案例》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运输问题产销平衡运输问题的数学模型可表示如下：以下题为例：产地销地产量4124111621439108511622销量814121448一、求最小运费1、最小元素法从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。产地销地产量412410116162814329108514116822销量814121448最小运费为：2、西北角法从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格

2、的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。产地销地产量48128411162146349108511861122销814121448量最小运费为：2、Vogel（沃格尔）法①　计算出各行各列中最小元素和次小元素差额（罚数），并标出。②　在罚数最大的行和列中填上尽可能大的数（若有两个罚数最大，则选择最大罚数所在行或所在列运费最小的）。若有行或列饱和，划去。③　重复以上步骤。产地销地产量行罚数1234412412114160007281439101116851411682212销量81

3、4121448列罚数1251322133212412二、检验是否是最优解1、闭回路法闭回路：从空格出发，遇到数字格可以旋转90度，最后回到空格所构成的回路；原理：利用检验数的经济含义；检验数：非基变量增加一个单位引起的成本变化量。当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。产地销地产量412410116162814329108514116822销量814121448检验数，故知该最小元素法的

4、解不是最优解。1、对偶变量法原问题检验数：特别对于m+n-1个基变量，有当为基变量时，由此，任选一个对偶变量为0，可求出其余所有的，。再根据求出所有非基变量的检验数。产地销地产量行罚数1234412412114160007281439101116851411682212销量814121448列罚数1251322133212412令，解之得：所以，不是最优解。