问答题 一般说来,用最小元素法得出的调运方案还不是最优方案,其原因何在?能否提出改进措施?
【正确答案】原因在于最小元素法没有从全局考虑,具体地说,若最小元素所在的行(或列)有他元素与之相差甚小,在划去该行(或列)时就会把这些有利的元素都划去了,于是有可能到后来只剩下最不利的元素供选取.因此,可提出如下改进措施:把同一行(或列)中次小元素与最小元素之差称为该行(或列)的差额,每次从具有最大差额的行或列选取最小元素.这种方法称之为差额法.例如对上题的问题(1),具有最大差额的是第三列(其差额为3),故首先在第三列取其最小元素c32,令x32=10,并划去第三列;在余表中,具最大差额的是第二行(其差额为4),取其最小元素c21,令x21=2,并划去第二行;照此做下去,得调运方案为x11=7,x21=2,x23=10,x31=1,x32=10,其余xij=0,对应运费为40.可见此方案比最小元素法所得方案优越.
【答案解析】