平衡问题的初始化求解.doc

摘要：运输问题是当今社会经济生活中经常出现的优化问题。在经济建设中，经常遇到物资的调运问题，如何制定调运方案，将物资运往指定地点，而且实现运输费用最小，即为运输问题。运输问题是特殊的线性规划问题，它是线性网络最优化的一个例子。最早研究这种运输问题的是美国学者希奇柯克（Hitchcock），1941年他在研究生产组织和铁路运输方面的线性规划问题的时候提出运输问题的基本模型。后来柯普曼（Koopmans）在1947年独立地提出运输问题并详细地加以讨论。从上个世纪40年代早期开始，康脱洛维奇（Kantorovich）围绕着运输问题作了大量的研究，所以运输问题又称为希奇柯克问题或康脱洛维奇问题。与一般线性规划问题不同的是它的约束方程组的系数矩阵具有特殊结构，这就需要采用不同甚至更为简洁的方法来解决这种在实际工作中遇到的问题。运输问题代表了物资合理调运、车辆合理调度等问题。其他类型问题经过一系列变换后也可以归结为运输问题。 物品运输问题在当今经济建设中是十分常见的问题，运输问题及运输成本的优化是运输企业制定调运方案时必须要考虑的问题。如何选择一个合理的运输方案使得运输费用最低是十分关键的。本课题主要研究的是产销平衡的问题，产销平衡是指生产量与销售量相同。即= ，公路货运企业时常会遇到若干货源地向若干需求地的货物运输问题，供货量与需求量不尽相同，怎样合理组织运输，满足货主的运输要求，同时使完成运输计划的运输费用最低，这是运输企业制定计划时优先考虑的问题。显然运输方案有多个，而且最优方案也只有一个，但是本课只讨论平衡运输问题初始的运输方案，就需要用最小元素法求出初始运输方案。 关键词：平衡运输 产销平衡 最小元素法 初始运输方案 一、问题的提出 某种货物有三个产地，分别是、、，每个产地的产量分别是3、7、4；另外有四个销地，分别是、、、，每个销地的销量分别是2、1、5、6；由此可以计算出产量为3+7+4=14，销量为2+1+5+6=14。根据= 可知， 此问题为产销平衡问题，此外，已知由产地向销地运一单位货物的运价为（各个数值给在表一中）。求平衡运输问题初始运输方案即运输问题的第一个基本可行解。 表一 销地 产量 产地 3 5 9 1 3 4 2 3 8 7 2 7 6 4 4 销量 2 1 5 6 二、求解过程 在此求解中需要用到最小元素法，英文名字为（the least cost rule）求出平衡运输问题的初始可行解，下面简单减少关于最小元素法的思想以及步骤： 最小元素法的思想：最小元素法的基本思想是就近供应，即从单位运价表中最小的运价（称为最小元素）开始确定产销关系，以此类推，一直到给出基本方案为止。 最小元素法的基本步骤： *找出最小运价，确定供求关系，最大量的供应； *划掉已满足要求的行或列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”； *在剩余的运价表中重复1、2两步，直到得到初始可行解。 求解上述提出的问题： 从表一中找出最小运价=1，即从开始，尽可能给以较大的值；这表示先将 的产品供应，产3，需要6，所以=min（3，6）=3，先画好一张空的表格，把相继求出的变量的值填在表上，我们把已求出的=3填在表二的处，并在3的右上方画*，这时所产的量全部提供给，即此时===0.在相应格上打×，表示无运输量，此时的需要量从6变到3，填在的一列的最后一格的下面。在没有填数和打×的位置上找出最小运价=2，仿上，令=min（1，7）=1，在表二的处天上1并画上*，此时的需求量得到满足，在所在列打×，的产品未分配完毕，还剩余6，在所在的行的最后写上6。重复上述步骤可以求出可以求出=2，=5， =2，=1，分别填在表二上，并在数字右上方画*，其余各处打×，这样表二给出第一个基本可行解：X=。 销地 产量 产地 × 3 × 5 × 9 1 3 × 4 2 3 8 7 6 1 2 × 7 × 6 4 4 2 销量 2 1 5 6 3 1 表二 应用最小元素法时有两点要特别注意：①若填完一个画*的数后，它所在的行，列的剩余量均为0，则规定只能在行、列之一的空格内打×，不能在该数所在行、列空格内同时打×。②若只剩下最后一行或一列没有填数和打×时，规定在每一个空格内只许填数，不许打×，即使变量取0也只能填0并在右上方画*，这样做的目的是保证基变量的个数有m+n-1个。 三、程序源代码 clear; a=[3 5 9 1;4 2 3 8;2 7 6 4]; b=[2 1 5 6]; %四个销地的