第2章：线性规划专题.ppt

《第2章：线性规划专题.ppt》由会员分享，可在线阅读，更多相关《第2章：线性规划专题.ppt（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第二章：运输问题第二章：运输问题3.1 3.1 产销平衡的运输问题：直接用表作业法产销平衡的运输问题：直接用表作业法 例：某地有三个有色金属矿例：某地有三个有色金属矿A A1 1、A A2 2、A A3 3，生产同一种金属矿石，生产同一种金属矿石，A A1 1矿的年产量为矿的年产量为100100万吨，万吨，A A2 2矿矿为为8080万吨，万吨，A A3 3矿为矿为5050万吨。矿石全部供应四个冶炼厂，万吨。矿石全部供应四个冶炼厂，B B1 1厂的全部需求量为厂的全部需求量为5050万吨，万吨，B B2 2厂厂7070为为万吨，万吨，B B3 3厂为厂为8080万吨，万吨，B B4 4厂为厂

2、为3030万吨。产量恰好等于总需求量，矿石由各矿山运到冶炼厂的单万吨。产量恰好等于总需求量，矿石由各矿山运到冶炼厂的单位运价已知，如下表。问如何安排运输，使各矿山的矿石运到冶炼厂，满足各厂的需要，且位运价已知，如下表。问如何安排运输，使各矿山的矿石运到冶炼厂，满足各厂的需要，且运输费用最小，运输费用最小，试建立该问题的数学模型试建立该问题的数学模型？1 第一步：列出产售平衡第一步：列出产售平衡表。表。第二步：给出初始调运方案第二步：给出初始调运方案(相当于单纯形法的初始基本可行解相当于单纯形法的初始基本可行解)。用最小元素法用最小元素法：从：从运价最小的变量格子开始分配，按尽可能满足一方取小的

3、原则。运价最小的变量格子开始分配，按尽可能满足一方取小的原则。508020203030 总运费：总运费：Z(1)=1.520+0.380+730+0.820+230 +0.350=390 基格：已分配运量的格子，对应的变量为基变量，共基格：已分配运量的格子，对应的变量为基变量，共6个个。空格：未分配运量的格子，对应的变量为非基变量空格：未分配运量的格子，对应的变量为非基变量(打打)，共，共6个个。2第三步：判断当前调运方案是否最优第三步：判断当前调运方案是否最优。若表上所有若表上所有空格的检验数空格的检验数 ij均为非负，则均为非负，则当前调运方案最优。当前调运方案最优。否则，当前调运方案非最

4、优，否则，当前调运方案非最优，须调整改进。须调整改进。用闭回路法求用闭回路法求 ij：508020203030+-+-+-闭闭回路：起点和终点是同一空格以外，其余顶点均为基格的曲折闭合多边形。回路：起点和终点是同一空格以外，其余顶点均为基格的曲折闭合多边形。性质：性质：凡可行调运方案均只能画唯一闭回路。下以空格凡可行调运方案均只能画唯一闭回路。下以空格x33为例作闭回路。为例作闭回路。空格空格x33的检验数：的检验数：沿闭回路增加沿闭回路增加1个单位个单位的运输量，由此带来的运输量，由此带来的费用代数和，即的费用代数和，即 33=2-0.3+1.5-7+0.8-0.3=-3.3其余类推。其余类

5、推。-3.36.76.5-4.41-5.33确定入基确定入基空格：取最小的负数空格：取最小的负数-5.3对应的空格对应的空格(非基变量非基变量)x31入基。入基。508020203030-3.36.76.5-4.41-5.3+-+-确定出基基确定出基基格：在格：在x31的闭回路中，标负号的的闭回路中，标负号的基基格运输量最小者格运输量最小者 Min50，30=30，对应的基格对应的基格(基变量基变量)x21出基。出基。沿沿闭回路方向闭回路方向调整运输量：调整运输量：标正号的格子增加标正号的格子增加30，标负号的格子减少，标负号的格子减少30，得新，得新调运方案如下。调运方案如下。4208050

6、203030 21.41.20.91 5.3 全部空格检验数均为非负，当前调运方案最优：全部空格检验数均为非负，当前调运方案最优：X11=20，X13=80，X22=50，X24=30，X31=30，X32=20 Z*=1.520+0.380+0.850+230+1.230+0.320=196 5 用位势法求用位势法求 ij：利用基格求行列利用基格求行列位势：令位势：令Ui+Vj=Cij 有有 U1+V1=C11=1.5 U1+V3=C13=0.3 U2+V1=C21=7 U2+V2=C22=0.8 U2+V4=C24=2 U3+V2=C32=0.3508020203030-3.3 6.7 6

7、.5-4.4 1-5.31.520.3370.81.421.20.322.5令令U1=0计算空格检验数计算空格检验数：ij=Cij(Ui+Vj)有有 12=C12 (U1+V2)=2-(0-4.7)=6.7 14=C14 (U1+V4)=3-(0 3.5)=6.5 23=C23 (U2+V3)=1.4-(5.5+0.3)=-4.4 31=C31 (U3+V1)=1.2-(5+1.5)=-5.3 33=C33 (U3+V3)=2-(5+0.3)=-3.3 34=C34 (U3+V4)=2.5-(5 3.5)=1 U1=0 U2=5.5 U3=5 V1=1.5 V2=-4.7 V3=0.3 V4=

8、-3.5+-6利用基格求行列利用基格求行列位势：令位势：令Ui+Vj=Cij 有有 U1+V1=C11=1.5 U1+V3=C13=0.3 U2+V2=C22=0.8 U2+V4=C24=2 U3+V1=C31=1.2 U3+V2=C32=0.3208050203030 2 1.4 1.20.9 1 5.31.520.3370.81.421.20.322.5令令U1=0计算空格检验数计算空格检验数：ij=Cij(Ui+Vj)有有 12=C12 (U1+V2)=2-(0+0.6)=1.4 14=C14 (U1+V4)=3-(0+1.8)=1.2 21=C21 (U2+V1)=7-(0.2+1.5

9、)=5.3 23=C23 (U2+V3)=1.4-(0.2+0.3)=0.9 33=C33 (U3+V3)=2-(-0.3+0.3)=2 34=C34 (U3+V4)=2.5-(-0.3+1.8)=1 U1=0 U2=0.2 U3=-0.3 V1=1.5 V2=0.6 V3=0.3 V4=1.8全部空格检验数均为非负，全部空格检验数均为非负，当前调运方案最优：当前调运方案最优：X11=20，X13=80，X22=50，X24=30，X31=30，X32=20Z*=1.520+0.380+0.850+230+1.230+0.320=196 7 表上作业法的步骤：表上作业法的步骤：第一步：列出产售

10、平衡第一步：列出产售平衡表和运价表。表和运价表。第二步：用最小元素法给出初始调运方案。第二步：用最小元素法给出初始调运方案。第三步：用第三步：用闭回路闭回路法或位势法求出所有空格法或位势法求出所有空格(非基变量非基变量)检验数检验数 ij。若若 ij 0，则，则当前方案最优；否则转入下一步。当前方案最优；否则转入下一步。第四步：对第四步：对当前方案调整改进。选负当前方案调整改进。选负检验数中绝对值最大的空格入基，并作检验数中绝对值最大的空格入基，并作闭回路，确定闭回路，确定 出基变量和调整量，沿闭回路调整运输量，得新可行出基变量和调整量，沿闭回路调整运输量，得新可行方案方案。第五步：重复以上步骤，直至所有空格检验数第五步：重复以上步骤，直至所有空格检验数 ij 0 为止，得为止，得最优方案。最优方案。8 3.2 产销不平衡的运输问题产销不平衡的运输问题 1 1、产大于销问题：设置一个假想销地，用来接受多余的产量，但运价为、产大于销问题：设置一个假想销地，用来接受多余的产量，但运价为0 0。92 2、销大于产问题：设置一个假想产地，用来满足过多的需求量，但运价为、销大于产问题：设置一个假想产地，用来满足过多的需求量，但运价为0 0。10