运筹学--运输问题运输问题的数学模型设xij代表为从第i个产地调运给第j个销地的物资的数量.在产销平衡的条件下，即使总的运费支出最小，可以表为以下数学形式：m行n行运输问题的数学模型,包含m×n个变量,m+n个约束条件,系数矩阵如下:表上作业法的基本思路：确定初始调运
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
最优性检验改进方案1确定初始调运方案运输问题确定初始基可行解，就是求出运输问题的初始调运方案.确定初始基可行解的方法有最小元素法和伏格尔法。【例2-1】某公司经销甲产品,下设3个加工厂A1、A2、A3，产品分别运往销售点B1、B2、B3、B4，各工厂的日产量和各销售点的日需求量及各工厂到各销售点的运价如下表所示：（运输问题供需平衡表和运价表如下），求总运费最少的调运方案。销地产地B1B2B3B4发量（T）A13113107A219284A3741059收量（T）3656表3-31.最小元素法314633Z=4×3+3×10+3×1+1×2+6×4+3×5=86该方案总运费：（思想：就近供应）不能同时划去行和列保证填有运量的格子为m+n-1表3-42.Vogel法①2513①011表3-6[]6②213②0123③212③01[][]3④12④76[]521表3-5Z=851若有两个以上相同的最大差值，可任取其一。2剩下一行或者一列有空格，填数字，不能划掉。3计算行差，列差时，已经划去的列或者行不再考虑。4用伏格尔法所求的初始解是基可行解，所以基变量个数为m+n-1个。销产B1B2B3产量A151812A224114A33674销量91011
例题
求函数的导数例题eva经济增加值例题计算双重否定句的例题20道及答案立体几何例题及答案解析切平面方程例题
用伏格尔法求初始调运方案销产B1B2B3产量A121012A231114A344销量91011初始调运方案2.2最优解的判别判别办法是计算空格(非基变量的检验数),因为运输问题的目标函数是实现最小化,所以当所有空格处的检验数大于等于零时,为最优解.下面分别介绍两种计算检验数的方法:闭回路法(2)位势法①闭回路法闭回路：从空格出发画水平(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格一定存在唯一闭回路。销产B1B2B3B4供量A1527A2314A3639销量3656表3-751047A38291A2103113A1B4B3B2B1销地产地633431计算最小元素法得到的初始基可行解的检验数(+1)(-1)(+1)(-1)(+1)×3+(-1)×3+(+1)×2+(-1)×1=1调整后总运费增加：空格处检验数为1表3-851047A38291A2103113A1B4B3B2B1销地产地633431(+1)(-1)(+1)(-1)7-5+10-3+2-1=10调整后总运费增加：空格处检验数为10(-1)(+1)表3-9检验数表110121-12因为存在小于零的检验数,所以最小元素法给出的方案不是最优方案.表3-10位势法 求检验数的步骤:1在表中下面和右面增加一行和一列,列中添入ui,行中添入vj,令u1=0,按照,根据表中已有的数字确定所有的ui及vj;2计算所有空格处的检验数.01128-37检验数表121-1101224=-1＜0，当前方案不是最优方案。最优方案判别准则表3-122.3闭回路调整法改进方案xpq为换入变量从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格，并从(p,q)空格开始给闭回路上的点按+1，-1，+1，-1编号，-1格的最小运量为调整量。表3-13找到最小调整量以后,按照闭回路上的正、负号，分别加上和减去此值，得到新的运输方案。销产B1B2B3B4供量A1527A2314A3639销量3656再用闭回路法或者位势法求检验数，得到下表:表3-14销产B1B2B3B4供量A1027A2214A39129销量3656这时所有的检验数都非负，表中的解就是最优解.表3-15销产B1B2B3B4供量A137645A224322A343853销量3322例求该运输问题的最优解2.3表上作业法计算中的问题1.退化:用表上作业法求解运输问题当出现退化时，在相应的格中一定要填一个0，以表示此格为数字格。有以下两种情况：(1)当确定初始解的各供需关系时，若在(i,j)格填入某数字后，出现Ai处的余量等于Bj处的需量。这时在产销平衡表上填一个数，而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有(m+n-1)个数字格。不能同时划去行和列。(2)在用闭回路法调整时，在闭回路上出现两个和两个以上的具有(-1)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时另一个数字格必须填入一个0，表明它是基变量。当出现退化解后，并作改进调整时，可能在某闭回路上有标记为(-1)的取值为0的数字格，这时应取调整量θ=0。销产B1B2B3B4供量A11067124A21610599A35410104销量5246当销大于产时，可以在产销平衡表中增加一个假想的产地i=m+1，该地产量为，在单位运输表上令从该假象产地至各销地的运价为0当销小于产时，可以在产销平衡表中增加一个假想的销地（库存）j=m+1，，在单位运输表上令从产地至该假象销地的运价为0销产B1B2B3B4供量A1211347A2103595A378127销量2346例：设有三个产地生产某种物资，其产量分别为7吨，5吨，7吨，四个销地需要该种物资，销量分别为2吨，3吨，4吨，6吨，又知各产销地之间的单位运价，试决定总运费最少的调运方案。产大于销例2：设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。已知各化肥厂年产量，各地区年需要量及从各化肥厂到各地区单位化肥的运价如表3-25所示。试决定使总的运费最节省的化肥调拨方案。表3-25运价：万元/万t解这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为210吨。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。由于各地区的需要量包含两部分，如地区Ⅰ，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M(任意大正数)，而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表(表3-26)和单位运价表(表3-27)。表3-27单位运价表表3-26产销平衡表表3-28某百货公司去外地采购ABCD四种规格的服装，数量分别为1500，2000，3000，3500套。有三个城市供应上述规格的服装，供应数量为第一个城市2500，第二个2500，第三个5000.由于这些城市的服装质量和运价等等的不同，预计售出后的利润也不同，利润表如下，请帮助该公司确定一个预期盈利最大的采购方案。ABCDa10567b9276c8348此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢
浙公网安备 33021202002483