西北角法
不考虑运价,从西北角的格子开始分配运量,按尽可能满足一方取小的原则,第一行和第一列的格子分配完后,依次向东南角方向的格子进行运量分配。 例如: 第一步:列出产售平衡表 第二步:利用西北角法进行运量分配:
首先在产售平衡表的x11处尽可能取最小值:min{50,100}=50x11为50后,由表可知x21,x31只能为0,划去第一列,在剩下的方格中,找出x12x12=min{70,100-50}=50x12为50后,由表可知x13,x14只能为0,划去第一行,在剩下的方格中,找出x22x22=min{70-50,80}=20x22为20后,由表可知x32只能为0,划去第二列,在剩下的方格中,找出x23x23=min{80,80-20}=60x23为60后,由表可知x23只能为0,划去第二行,在剩下的方格中,找出x33x33=min{80-60,50}=20x33为20后,由表可知,划去第三列,在剩下的方格中,找出x34x34=30,分配结束
![在这里插入图片描述](https://img-blog.csdnimg.cn/7c660e5982f246d5a0c95492ce304575.png)
最小元素法
将运价从小到大进行排序0.3->0.8->1.2->1.4->1.5->2->2.5->3->7,从运价最小的格子开始分配运量,按尽可能满足一方取小的原则,依次按运价从小到大的顺序进行运量分配。 还是以上述为例:
第一步:列出产售平衡表 第二步:利用最小元素法进行运量分配:
运费最小0.3的格子为x32,优先满足x32,则x32=50x32为50,A3产量耗尽,划去第三行,B2需求量更新为70-50=20另有0.3的格子为x13,优先满足x13,则x13=80x13为80,A1产量更新为100-80=20,B3需求量耗尽,划去B3列运费第二小0.8的格子为x22,优先满足x22,则x22=20(因为B2需求量为20)x22为20,A2产量更新为80-20=60,B2需求量耗尽,划去B2列在可选择的格子中,运费最小为1.5,优先满足x11,则x11=20x11=20,A1产量耗尽,划去A1行,B1需求量更新为30在可选择的格子里,运费最小为2,优先满足x24=30,更新A2产量为30,划去B3列剩余x21,补充即可
![在这里插入图片描述](https://img-blog.csdnimg.cn/fad792f9e34542c6a75bb6c7513a2ae4.png)
验证当前调运方案是否最优
首先明确基格和空格: 基格:已分配运量的格子,对应变量是基变量 空格:未分配运量的格子,对应变量是非基变量 是否为最优方案的判断: 表上所有空格的检验数均为非负 求校验数的方法有两种:1.闭回路法;2.位势法
闭回路法
闭回路的定义: 起点和终点在同一空格外,其余的顶点都要是基格所构成的闭合多边形 凡可运行的方案皆唯一闭回路
![在这里插入图片描述](https://img-blog.csdnimg.cn/1085f90daf574c2bb709cf6e93c97bad.png)
位势法
步骤:
在运输表上添加行位势Ui和Vj利用基格求行和列位势值利用已经求出的行列位势值计算空格的检验数
例如: ![在这里插入图片描述](https://img-blog.csdnimg.cn/915793ef92a94a849c267ac382302d53.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/5d6b5ceaeb004a45835ee9ba624a8a20.png)
调整方法
确定入基的空格取空格检验数中最小的负数λ31所对应的空格x31入基确定出基的基格在x31形成的闭合路中,取标负号的基格中运输量最小的x31出基沿闭回路方向调整运输量(数量为出基基格的运输量,+号加运输量,-号减去该运输量)
如图: 再次判断是否为最优方案,不是则重复上述操作,直至最优。
|