确定最佳初始方案

确定初始方案的方法有很多,在这里只介绍三种较为常用的方法:最小元素法、西北角法和伏格尔法。

(1)最小元素法(Matrix Minimum)。

最小元素法的基本思想是,就近供应,即优先考虑(最大可能满足)单位运价最小(或运距最短)的供销路线,最大限度地满足其需求量。从单位运价中最小的运价开始确定供销关系,然后次小,一直到求出初始基本可行解(初始方案)为止。具体步骤如下:

视频-3．2．1表上作业法-1-确定初始方案-最小元素法

首先,找出运价表中最小的元素,在对应的格中填入最多可以供应的数量,若某行(列)的产量(销量)已满足,则把所在行(列)划去;然后,再从未划去的元素中找到最小值,重复上述步骤,直至得到一个初始方案(基本可行解)。

【例3-3】用最小元素法确定【例3-1】中运输问题的初始方案。

视频-3．2．1表上作业法-2-确定初始方案-西北角法

解:

第一步,首先找到表中最小元素“65”,考察产销路线A2→B2,需求为“150”,产量为“250”,为最大限度满足B1的需求,应在空格中填入“150”,此时B2需求满足,因此将B2所在列划去(即不再考虑B2列元素),标注第①步,A2产量由“250”减少到“100”,如表3-4所示。

表3-4

第二步,在表3-4中,找到最小元素“75”(min{90,100,80,75}),对于路线A2→B3,需求为“200”,产量为“100”(A2已用150),为最大限度满足B3的需求,应在空格中填入“100”(因A2仅剩余100),此时A2产量用完,因此将A2所在行划去(不再考虑A2行),标注第②步,B3的需求由“200”减少为“100”,如表3-5所示。

表3-5

第三步,在表3-5中,找到最小元素“90”(min{90,100}),考察产销路线A1→B1,需求为“100”,产量为“200”,为最大限度满足B1的需求,应在空格中填入“100”,此时B1需求全部满足,因此将B1所在列划去,标注第③步,A1可提供的产量由“200”变为“100”,如表3-6所示。

表3-6

第四步,在表3-6中,找到最小元素“100”(只有一个数),考察产销路线A1→B3,需求为“100”,产量为“100”,为最大限度满足B3的需求,应在空格中填入“100”,此时B3需求全部满足,因此将B3所在列划去,因A1的产量用完,同时将B3所在列和A1所在行划去,标注第④步,如表3-7所示。

表3-7

由最小元素法确定的初始方案为:

调运方案为A1→B1(100),A1→B3(100),A2→B2(150),A2→B3(100),其他路线调运量为零,总费用为36 250。

注意:在此方案中,x11,x13,x22,x23为基变量(个数等于m＋n－1＝2＋3－1＝4),其他为非基变量。基变量对应数字格,非基变量对应空格。

使用最小元素法的主要缺点是,为了节约一处的费用,有时造成在其他处要多花几倍的运费。例如,在A2→B2路线上花费了9 750(150×65),虽然比A1→B2节省了750(150×5),但在A1→B3路线上的费用却为10 000(100×100)。

(2)西北角法。

西北角法是确定初始调运方案的基本方法之一,其基本思想是优先满足运价表中西北角(左上角,空格)的产销路线,从运价表的西北角位置开始,依次安排调运量。

【例3-4】用西北角法确定【例3-1】中运输问题的初始方案?

解:

第一步,首先找到表3-8中左上角元素“90”,考察产销路线A1→B1,需求为“100”,产量为“200”,在空格中填入“100”,此时B1需求满足,将B1所在列划去,标注第①步,A1可提供的产量由“200”变为“100”。

表38

第二步,在剩余元素中继续寻找左上角元素“70”,考察产销路线A1→B2,需求为“150”,产量剩余“100”,在空格中填入“100”,此时A1产量用完,因此将A1所在行划去,标注第②步,B2的需求由“150”变为“50”,如表3-9所示。

表3-9

第三步,找到左上角元素“65”,考察产销路线A2→B2,需求为“50”,产量为“250”,在空格中填入“50”,此时B2需求全部满足,因此将B2所在列划去,标注第③步,A2可提供的产量由“250”变为“200”,如表3-10所示。

表3-10

第四步,考察最后的产销路线A2→B3,需求为“200”,产量为“200”,在空格中填入“200”,A2产量用完,B3需求满足,同时划去一行和一列,如表3-11所示。(www.xing528.com)

表3-11

由西北角法确定的初始方案为:

S(0)＝100×90＋100×70＋50×65＋200×75＝34 250

调运方案为A1→B1(100),A1→B2(100),A2→B2(50),A2→B3(200),其他路线调运量为零,总费用为34 250。

(3)伏格尔法(Vogel's Approximation Method)。

伏格尔法又称差值法,基本思想是若某供应地的物资不能按最小运费就近供应,就要考虑次小运费,最小运费和次小运费之间的差额越大,说明未按最小运费调运所增加的运费越多,因此,对于差额最大产销路线,应尽量采用最小运费进行调运。伏格尔法的具体计算步骤如下:

①算出各行各列中最小元素和次小元素的差额,选出最大的差额(若几个差额同为最大,可任取其一)。

②让差额最大的行或列中的最小元素处的调运量尽量大。③对未划去的行列重复以上步骤,直到得到一个初始方案。

由此可见,伏格尔法同最小元素法除在确定供求关系的原则上不同外,其余步骤相同。一般来说,伏格尔法给出的初始解比用最小元素法给出的初始方案更接近最优方案。

【例3-5】用伏格尔法确定【例3-1】中运输问题的初始方案。

解:

第一步,找出各行和各列的最小运价和次小运价,分别计算差值。如表3-12中第1列(B1)中,最小运价为80,次小运价为90,两者差值为10(90－80＝10),其他计算结果如表3-12所示。

表3-12

第二步,在行和列的差值中找出最大值,并找出该最大值所在行或列中的最小元素。如表3-12中第三列B3是最大差值(25)所在列,在该列中找到最小元素“75”,优先满足产销路线A2→B3的需求量,在对应空格中填入“200”,此时B3需求满足,将B3所在列划掉,标注第①步,A2产量由“250”变为“50”,第二行差值变为15,如表3-13所示。

表313

第三步,考察差值为20(20,15,10,5中的最大值)的第1行(A1),找到最小元素“70”,尽可能满足产销路线A1→B2的需求量,在对应空格中填入“150”,此时B2的需求量已满足,将B2所在列划掉,标注第②步,A1的产量由“200”变为“50”,如表3-14所示。

表3-14

此时,在表3-14中,只有B1列有最小运价和次小运价。

第四步,考察B1列中的元素“80”,满足A2→B1的需求量,在对应空格中填入“50”,A2产量用完,将A2所在行划掉,标注第③步,B1的需求量由“100”变为“50”,如表3-15所示。

表3-15

第五步,只差一个元素“90”,满足产销路线A1→B1的需求量,在对应空格中填入“50”,同时划去一行和一列,标注第④步,如表3-16所示。

表3-16

由伏格尔法确定的初始方案为:

调运方案为A1→B1(50),A1→B2(150),A2→B1(50),A2→B3(200),其他路线的调运量为零,总费用为34 000。

(4)退化解及“0”元素的添加。

在确定初始方案时,每次填入数字后,都只划去一行或一列,只有在填入最后一个元素时除外(同时划去一行和一列)。但有时会出现退化解(基变量取值为零)的情形。例如,在确定初始方案的过程中,当遇到某行及某列的供需余量相等的情形时,这样填上运量后应当划去该行及该列,为了保证基变量个数,在将它们同时划去时,须在所划去的列或行某个空格中填入一个“0”运量。

需要注意的是,“0”的位置确定不是随意的,需要遵循一定的规则,否则会影响接下来的计算。有学者认为,这个“0”应填在不与其他数字格构成闭回路的空格里,且对应单位运价最小。例如,表3-17和表3-18是用最小元素法确定某运输问题初始方案的前四步和最后结果。在进行第三步时,将“3”填入空格后,A3产量(3)用完,B2需求量(3)满足,此时应同时划掉一列(③)和一行(④),并在所在行和列的空格中填入“0”,以补齐基变量的个数,因此可将“0”填在对应A2→B2的空格处。

表3-17

在确定初始方案后,需要考察这个“0”与其他数字格(基变量)是否构成闭回路(关于闭回路的概念将在接下来的内容中介绍),如表3-18所示,该“0”与其他数字格没有构成闭回路。对于本例,也可在其他空格处中填入“0”,均不会构成闭回路,如A1→B2,A3→B3,A3→B4的空格处。

表3-18