发布时间 : 星期一 文章题目：线性规划在运输中的运用更新完毕开始阅读b634885ebe23482fb4da4cf5
由于该方法基于优先满足单位运价（或运距）最小的供销业务，故称为最小元素法。在例4中，因A2到B1的单位运价2最小，故首先考虑这项运输业务。由于min(a2,b1)= b1=8,所以令x21=8,在表4-1的（A2，B1）格中填入数字8，这时A2可供量变为A2?B1?10?8?2;B1需求量全部得到满足，在以后运输量分配时不再考虑，故划去B1列。
在运输表尚未划去的各格中再寻求最小单位运价，它等于3对应（A2，
B3）格。由于A2供应B1后其供应能力变为2，小于b3=12,故在格（A2，B3）中填入数字2。这时A2的供应能力已用尽，划去A2行。
继续如上进行，在（A2，B3）格中填入数字10，划去B3列；在（A2，
B3）格中填入数字14，划去B2列；在（A3，B4）格中填入数字8，划去A3行；至此，只有（A1，B4）格未被划去，在其中填入数字6，使A1的可供量和B4的需求量同时得到满足，并同时划去A1行和B4列。这时，运输表中的全部格子均被划去，所有供销要求均得到满足。上述过程和结果示于表4-2中，表中下部和如右侧小圆圈中的数字表示各列和各行划去的先后顺序。
表4-2
产 地 销 地 B1 4 2 8 B2 B3 12 10 5 4 3 11 B4 11 9 6 产量 A1 A2 A3 销量 48
第 9 页 共 14 页
这时得到了该运输问题的一个初始解：
x13?10,x14?6 ,x21?8 ,x23?14 ,x34?8，其它变量全等于零。即由A1运10单位物品给B3，运单位物品给B4;由A2运8单位物品给B1，运2单位物品给B3；由A3运14单位物品给B2，运8单位物品给B4。总运费(目标函数值)
34z??cijxij
i?1?j?1=10×4+6×11+8×2+2这个解满足所有约束条件读者不难验证，这6个非零变量（基变量）对应的约束条件系数列向量线性无关。
2、西北角法
西北角法与最小元素不同，务，而是优先满足运输表中西北角（即左上角）上空格的供销需求。现再看例4，由表先在(A1，B1)格中填入划去B1列, A1的可供量变为供量已用完,划去A1行运输表剩下部分的左上角格子字6,并划去B2列。如此继续，在8，最后在(A3,B4)格中填入案的过程示于表4－3
3+14×5+8×6=246
,其非零变量的个数为6(等于m?n－1=3+4它不是优先考虑具有最小单位运价的供销业4-1知，其左上角的空格是（A1，B1）用西北角法时x11?min(a1,b1)?min(16,8)=8,因B1的销量已满足16－8=8,故在(A1，B1)格子中填入8,因B2的需求量由b2=14变为14－8=6.这时(A2,因min(a2,b2?8)?6,在(A2,B2)中填入数(A2,B3)格中填入4，在(A3,B3)格中填入14，并同时划去A3行和B4列。寻求初始调运方
第 10 页 共 14 页
－1=6),
,A1的可B2)是 ×,,中。
表 4－3中
B1 4 2 B2 12 10 B3 4 3 B4 11 9 产量 A1 A2 A3 销量 至此得到初始基可行解：x11=8,x12=8,x22=6,x23=4,x33=8,x34=14,其它变量全等于0。即由A1运8个单位物品至B1，运8个单位物品至B2；由A2运6个单位物品至B2，4个单位物品至B3，14个单位物品至B2，4个单位物品至B3；由A3运8个单位物品至B3，14个单位物品至B4。总运输费用B
z=8×4＋8×12＋6×10＋4×3＋8×11+14×6
3．沃格尔（Vogel法）
初看起来，最小元素法十分合理，但是，有时按某一最小单位运价优先安排物品调运时，却可能导致不得不采用运费很高的其它供销点对，从而使整个运输费用增加。对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，帮应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。
现再结合例题说明这种方法。
首先计算运输表中每一行和每一列的次小单位运价和最小单位运价之间的差值，并分别称之为行罚数和列罚数。将算出的行罚数填入位于运输表
第 11 页 共 14 页
右侧行罚数栏的左边第一列的相应格子中，列罚数填入位于运输表下边列罚数栏的第一行的相应格子中（见表4-4）。例如，A1行中的次小和最小单位运价均为4，帮其行罚数码相机等于0；A2行中的次小和最小单位运价分别为3和2，其行罚数等于3－2=1；B1列中的次小单位运价和最小单位运价分别为4和2，其列罚数等于2。如此进行，计算出本例A1,A2和A3行的行罚数分别为0，1和1；B1，B2,B3和B4列的列罚数分别为2，5，1和3。在这些罚数中，最大者为5（在表4—4中用小圆圈示出），它位于B2列中的最小单位运价是位于（A3，B2）格中的5，故在（A3，B2）格中填入尽可能大的运量14，此时B2的需要量得到满足，划去B2列。
表4-4 销 产 地 地 行罚数 B1 4 2 8 8 2 2 ② B2 12 10 5 B3 4 3 11 B4 11 9 6 产量 1 2 0 1 2 3 0 1 4 ⑦ 6 5 0 0 A1 A2 8 14 12 4 2 8 16 10 22 48 0 1 1 A3 销量 1 2 列 罚 3 数 4 5
14 ⑤ 12 1 1 1 1 14 3 ③ 2 2 ② 第 12 页 共 14 页