运输模型方案的评估,某公司有三座工厂均生产相同之产品。该公司另有四个仓库存放这些产品。请问该公司应如何将三座工厂生产之产品分配到四个仓库而使运输之成本最低?,从工厂1每期可供应量,从工厂1到仓库A之单位运输成本,仓库A每期可储存量,每期总需求量,每期总供应量,运输模型方案的评估,运输模型所具备之基本假设如下 1.运送之货物为同质之产品。 2.不论运货量多寡。每单位运输成本皆相同 3.各起站到各目的地运输路线只有一条 求解步骤 1.求初始解 2.最佳解测试 3.改进次佳解 求初始解之方法 1.直觉最低成本法 2.西北角法 3.差额法(Vogels Approximation Method) VAM又称为惩罚法(Penalty Method),运输模型求初始解,运输模型求初始解西北角法求解步骤 1.由西北角方格开始 2.将最大可行量分配给该方格，并划掉该列或行或两者 3.继续由西北角方格重复步骤2。直到分配完毕,80,20,20,70,70,130,120,10,10,150,150,初始解之总成本 =80*4+20*7+70*3+120*8+10*8+150*5=2460,运输模型求初始解,运输模型求初始解直觉最低成本法求解步骤 1.找最低成本方格 2.将最大可行量分配给该方格，并划掉该列或行或两者 3.找次低成本方格重复步骤2。直到分配完毕,100,60,90,110,60,90,80,10,110,10,10,运输模型求初始解,运输模型求初始解差额法求解步骤 1.分别找每列及每行，最低成本与次低成本之差额(若相同差额=0) 2.选择差额最大之行或列中方格成本最低者优先分配，并划掉该列或行或两者。 3. 重复步骤1。直到分配完毕,行差額,4,4,1,4,列差額,3,5,3,90,110,5,运输模型求初始解,运输模型求初始解差额法求解步骤 1.分别找每列及每行，最低成本与次低成本之差额(若相同差额=0) 2.选择差额最大之行或列中方格成本最低者优先分配，并划掉该列或行或两者。 3. 重复步骤1。直到分配完毕,行差額,4,1,4,列差額,3,0,3,90,110,4,100,60,运输模型求初始解,运输模型求初始解差额法求解步骤 1.分別找每列及每行，最低成本與次低成本之差額(若相同差額=0) 2.選擇差額最大之行或列中方格成本最低者優先分配，並劃掉該列或行或兩者。 3. 重覆步驟1。直到分配完畢,行差額,4,8,3,列差額,0,3,90,110,8,100,60,110,10,60,80,10,运输模型最佳解测试.,初始解之总成本 =100*1+90*3+110*8+80*8+10*16+60*5=2350 运输模型求初始解后最佳解测试需要评估每个未分配方格是否有改进之可能。评估之方法有两种 1.踏石法 2.修正分配法,100,90,60,80,110,10,运输模型最佳解测试.踏石法,空方格1-A评估 若1-A增加一单位1-D必须减少一单位 1-D减少一单位3-D必须增加一单位 3-D增加一单位3-A必须减少一单位 是否采用方格1-A就要看成本是否有减少 (+)=4+5=9 (- )=1+8=9,100,90,60,80,110,10,+,-,+,-,所以此改变对成本没有影响，继续评估空方格1-B,1-C,2-A,2-D,3-B看那个改变成本降低最多 用踏石法建立封闭路径时，必须选择最少之实方格 且实方格数必须等于行数+列数-1 若实方格数行数+列数-1则该矩阵称为退化,运输模型最佳解测试.踏石法,空方格1-B评估 (+)=7+5+8=20 (- )=1+16+3=20 所以此改变对成本没有影响，继续评估空方格,1-C,2-A,2-D,3-B看那个改变成本降低最多,100,90,60,80,110,10,+,-,+,-,+,-,运输模型最佳解测试.踏石法,空方格1-C评估 (+)=7+5=12 (- )=1+16=17 所以此改变对成本会降低5，继续评估空方格2-A,2-D,3-B看那个改变成本降低最多,100,90,60,80,110,10,+,-,+,-,运输模型最佳解测试.踏石法,空方格全部评估之后若有成本均大于等于0表示此解以是最佳解 若有负成本表示，此解可发展出改良解 所以我们从最大负成本开始改良 1-C最多可增加10 改良后，继续评估空方格看看是否已经是最佳解,100,90,60,80,110,10,+,-,+,-,运输模型最佳解测试.踏石法,空方格1-C评估后成本降低最多 空方格1-C最多可增加101-D减少10 3-D增加103-C减少10 所以此改变后可获得改进解,100,90,60,80,110,10,+,-,+,-,10,90,70,0,运输模型最佳解测试.踏石法,所以此改变后可获得改进解之总成本 =10*7+90*1+90*3+110*8+80*8+70*5=2300 继续评估空方格(1-A,1-B,2-A,2-D,3-B,3-C方格)看看是否有改进之可能。,90,80,110,10,90,70,全部空方格(1-A,1-B,2-A,2-D,3-B,3-C)成本均大于等于0 所以已经是最佳解了。,运输模型最佳解测试.修正分配法,修正分配法(Russel) 1.首先利用实方格找出每列及每行之指数 指定第一列指数=0 实方格成本=列指数+行指数,100,90,60,80,110,10,0,1,4,4,12,-4,7,2.找出每列及每行之指数后计算空方格之评估值 空方格之评估值 =空方格之成本-(列指数+行指数),运输模型最佳解测试.修正分配法,2.找出每列及每行之指数后计算空方格之评估值 空方格之评估值=空方格之成本-(列指数+行指数),100,90,60,80,110,10,0,1,4,4,12,-4,7,运输模型最佳解测试.修正分配法,100,90,60,80,110,10,0,1,4,4,12,-4,7,空方格全部评估之后若有成本均大于等于0表示此解以是最佳解 若有负成本表示，此解可发展出改良解 所以我们从最大负成本开始改良 1-C最多可增加10 改良后，继续评估空方格看看是否已经是最佳解,运输模型最佳解测试.修正分配法,空方格1-C评估后成本降低最多 空方格1-C最多可增加101-D减少10 3-D增加103-C减少10 所以此改变后可获得改进解,100,90,60,80,110,10,+,-,+,-,10,90,70,0,运输模型最佳解测试.修正分配法,修正分配法 1.首先利用实方格找出每列及每行之指数 指定第一列指数=0 实方格成本=列指数+行指数,90,90,70,80,110,0,1,4,4,7,1,2,10,2.找出每列及每行之指数后计算空方格之评估值 空方格之评估值 =空方格之成本-(列指数+行指数),运输模型最佳解测试.修正分配法,2.找出每列及每行之指数后计算空方格之评估值 空方格之评估值=空方格之成本-(列指数+行指数),90,90,70,80,110,0,1,4,4,7,1,2,10,空方格全部评估之后若有成本评估值均大于等于0表示此解以是最佳解 全部空方格(1-A,1-B,2-A,2-D,3-B,3-C)成本评估值均大于等于0 所以已经是最佳解了。,特殊运输模型,并非所有运输问题都可如上述问题直接处理 若出现不规则性，在求解前必须作一些调整。 常见之不规则性有两种 1.供需不平衡 2.退化解实方格数不足，无法评估每个空方格 通常用实方格数是否等于R+C-1 若实方格数R+C-1则有退化解,特殊运输模型供需不平衡,供需不平衡时加入一虚拟行或列,30,70,90,10,10,70,70,特殊运输模型供需不平衡,评估空方格1-B,2-C是否为最佳解,30,90,10,70,空方格全部评估之后若有成本评估值均大于等于0表示此解以是最佳解 全部空方格(1-B,2-C)成本评估值均大于等于0 所以已经是最佳解了。,特殊运输模型退化解,实方格=4个 R+C-1=3+3-1=5 因为实方格数R+C-1 所以此解为退化解,50,10,40,10,20,20,解决方法,必须将一非常小之数量加入其中一个空方格内 才能评估每个空方格 空方格全部评估之后若所有成本均大于等于0表示此解以是最佳解 若有负成本表示，此解可发展出改良解,特殊运输模型退化解,要如何将一非常小之数量加入其中一个空方格内 才能评估每个空方格 原则为避免将放入评估路径中有-号之空方格内 且要能评估每个空方格,50,40,10,20,+,特殊运输模型退化解,要如何将一非常小之数量加入其中一个空方格内 才能评估每个空方格 原则为避免将放入评估路径中有-号之空方格内 且要能评估每个空方格,50,40,10,20,+,特殊运输模型退化解,要如何将一非常小之数量加入其中一个空方格内 才能评估每个空方格 原则为避免将放入评估路径中有-号之空方格内 且要能评估每个空方格,50,40,10,20,特殊运输模型退化解,50,40,10,20,空方格全部评估之后若有成本评估值均大于等于0表示此解以是最佳解 所以已经是最佳解了。 总成本=40*3+50*1+10*4+20*6+0*7=330,