运输模型方案的评估.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * 运输模型方案的评估 某公司有三座工厂均生产相同之产品。该公司另有四个仓库存放这些产品。请问该公司应如何将三座工厂生产之产品分配到四个仓库而使运输之成本最低? 从工厂1每期可供应量 从工厂1到仓库A之单位运输成本 仓库A每期可储存量 每期总需求量 每期总供应量 运输模型方案的评估 运输模型所具备之基本假设如下 1.运送之货物为同质之产品。 2.不论运货量多寡。每单位运输成本皆相同 3.各起站到各目的地运输路线只有一条 求解步骤 1.求初始解 2.最佳解测试 3.改进次佳解 求初始解之方法 1.直觉最低成本法 2.西北角法 3.差额法(Vogel’s 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最多可增加10→1-D减少10 3-D增加10→3-C减少10 所以此改变后可获得改进