1.6线性规划ppt课件.ppt

第1章线性规划,1.6运输问题编程算法与编程实践,1.6.1运输问题的理论基础,1.6.2运输问题的算法和原理,1.6.3运输问题的程序流程图,1.6.4运输问题的实例及操作,1.6运输问题编程算法与编程实践,1.6.1运输问题的理论基础,1.运输问题的数学模型一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。在这里，我们先以一个示例来简单描述一下运输问题的数学模型。例1：某公司从两个产地A1，A2将产品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和各产地运往各销地的单位产品运费如表18所示。问如何调运，使得总运输费最小？,表18产、销、运价关系表,解：从表中可以看到，A1，A2两个产地的总产量为500件；B1，B2，B3三个销地的总销量为500件，因此这是一个产销平衡的运输问题。把A1，A2的产量全部分配给B1，B2，B3，正好满足这三个销地的需要。设xij表示从产地Ai调运到销地Bj的运输量（i=1，2；j=1，2，3），则可以写出此运输问题的数学模型，即：,minZ=6x11+4x12+6x13+6x21+5x22+6x23x11+x12+x13200 x21+x22+x23300 x11+4x21150 x12+x22150 x13+x23200 xij0（i1，2；j=1，2，3）,销地,产地,此数学模型当然可用线性规划的常用方法求解，但求解的程序相对复杂，即使利用计算机程序来求解，其输入和解决问题的规模也受到一定的限制。因此，运筹学中有专门的求解运输问题的程序，一般只要输入产点数，各产地的产量，销点数，各销地的销量，以及各产地到各销地的运输单价，立即可得到运输问题的最优解。把本例的相关数据输入运输问题的程序，得到最优解为：,1.6运输问题编程算法与编程实践,1.6.1运输问题的理论基础,x1150，x12=150，x13=0，x21=100，x22=0，x23=200最优值为：minz=2700最优解的表格描述如表19所示：,表19供、需、运价关系表,销地,单位运价,产地,通过上例，我们对运输问题已有了简单的认识，下面我们将给出一般运输问题的数学模型。我们用，A1，Am表示某种物资的m个产地；B1，B2，Bn表示某种物资的n个销地；ai表示Ai产地的产量；bj表示销地Bj的销量；cij表示把物资从Ai产地运到Bj销地的单位运价；并设为xij为从产地Ai运到销地Bj的运输量，则产销平衡的运输问题的线性规划模型如下所示,1.6运输问题编程算法与编程实践,1.6.1运输问题的理论基础,minZ=，（j1，2，n），（i1，2，m）xij0（i1，2，m；j=1，2，n）,有时上述问题的一般模型会发生如下一些变化：（1）求目标函数值的最大值而不是最小值。有些运输问题中，其目标是找出利润最大或营业额最大的调运方案，这时需要求目标函数的最大值。（2）当某些运输线路的运输能力有一定限制时，这时要在线性规划模型的约束条件上加上运输能力限制的约束条件。（3）当生产总量不等于销售总量，即产销不平衡时，这时需要通过一个假想销地或假想产地来化成产销平衡的问题，具体做法在后面阐述。,2.运输问题的求解方法表上作业法,直接采用单纯形法求解运输问题明显是不利的。好在运输问题具有特殊的结构，因此可以利用单纯形法的原理，提出一种直接在运输表上计算以求解产销平衡运输问题的简便方法-表上作业法。它大大简化了计算，其原理如下：（1）求初始调运方案（初始基可行解）。对于有m个产地n个销地的产销平衡的问题，从其线性规划的模型上可知其有m+n个约束方程，由于产销平衡，前m个约束方程之和等于后n个约束方程之和，故只有m+n-1个独立的约束方程，也就是说运输问题的约束方程组系数矩阵的秩等于m+n-1，因此其基可行解中基变量的个数为m+n-1。表上作业法中找初始基可行解，就是在产销平衡表上mn个数字格中找出m+n-1个数字格，其相应的调运量就是基变量，格子中所填写的值即为基变量的值。（2）求表中各空格（对应于非基变量）的检验数以判定当前解是否最优，若已是最优解则停止计算；否则转到下一步。,（3）如果检验数中有负数，那么就以最小的负检验数所在的空格为调入格，并用这个空格的闭回路来进行调整，得出新的调运方案。（4）重复2、3直至得到最优解。上述步骤在表上进行十分方便，下面以例子来说明。示例：某食品公司有三个生产面包的分厂A1，A2，A3，有四个销售分公司B1，B2，B3，B4，其各分厂每日的产量、各分销售公司每日的销量以及各分厂到各分销售公司,的单位运价如表110所示。问该公司应如何调运产品在满足各销点的需求量的前提下，总运费最少？表110供、需、运价关系表,销地,产地,一、求初始调运方案-最小元素法该方法的基本思想是采用优先安排单位运价最小的产地与销地之间的运输业务这个规则来确定初始基可行解。我们直接在运输表中的格子里填数表示基变量。为了把初始基可行解与运价分开，把运价放在每一栏的右上角，每一栏的中间填上初始基可行解（调运量）见表1-12。在表上找到单位运价最小的x21开始分配运输量，并使x21取尽可能大的值，即取x21=min（4，3）=3，把x21所在空格里填上3，然后把A2的产量改写为4-3=1，把B1的销量改写为3-3=0，并把B1列划去。在剩下的33矩阵里找到运价最小的变量x23，取x23=min（1，5）=1，A2的产量改为1-1=0，B3的销量改,1.6运输问题编程算法与编程实践,1.6.1运输问题的理论基础,为5-1=4，并把A2行划去。在剩下的矩阵里找到运价最小的变量x13，取x13=min（7，4）=4，A2的产量改为3，B3的销量改为0，并划去B3列。在剩下的矩阵里再找到运价最小的变量x32，取x32=min（9，6）=6，A3的产量改为3，B2的销量改为0，并把B2列划去。接着在剩下的表中找到运价最小的变量x34，取x34=min（3，6）=3，A3的产量改为0，B4的销量改为3，并把A3行划去。最后在剩下的表中找到运价最小的变量x14，取x14=min（3，3）=3，A1的产量改为0，B4的销量改为0，并划去A1行。这就得到一个初始基可行解，有6个基变量，其中x13=4，x14=3，x21=3，x23=1，x32=6，x34=3，其总运费为34+103+13+21+46+53=86。在用最小元素法确定初始基可行解时要注意两个问题：（1）当确定xij的值后，会出现Ai的产量与Bj的的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行和Bj列。（2）最小元素法时，可能会出现只剩一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或列中除去已填的数外均填0，不能按空格划掉。这样可以保证基变量的个数为m+n-1个。说明：求初始调运方案的方法具有很多种。例如，西北角法、最小行法、最小列法、混合法、频率法等，其基本原理都和最小元素法大同小异，在此将不再赘述。二、最优解的判别-位势法同单纯形法一样，表上作业法也是用检验数来检验方案的最优性。所谓位势法，即对运输表上的每一行赋予一个数值ui，对每一列赋予一个数值vj，它们的数值是由基变量xij的检验数ij=cij-ui-vj=0所决定的，则非基变量xij的检验数就可用公式ij=cij-ui-vj求出。下面用位势法对本例的初始基可行解求检验数。对给出的初始基可行解作一个表，栏中表示调运量，栏中无数值的表示此栏为非基变量，调运量为零。如表111所示：,1.6.1运输问题的理论基础,1.6运输问题编程算法与编程实践,表111运价及供需平衡表,产地,销地,先给u1赋个任意数值，不妨令u1=0，则从基变量x13的检验数13=c13-u1-v3=0，求得v3=c13-u1=3-0=3。同样：从14=c14-u1-v4=0，得v4=c14-u1=10-0=10；从13=c13-u2-3=0，得u2=c13-v3=2-3=-1；从34=c34-u3-v4=0，得v4=c34-u3=5-10=-5；从32=c32-u3-v2=0，得v2=c32u3=4-（-5）=9；然后，利用求得的ui与vj的值来计算非基变量的检验数：11=c11-u1-v1=3-0-21；12=c12-u1-v2=11-0-92；22=c22-u2-v2=9-（-1）-91；24=c24-u2-v4=8-（-1）-10-1；31=c31-u3-v1=7-（-5）-210；33=c33-u3-v3=10-3-（-5）12；对求出的检验数可表示如表112：,1.6运输问题编程算法与编程实践,1.6.1运输问题的理论基础,表112检验数表,1.6运输问题编程算法与编程实践,1.6.1运输问题的理论基础,该表中，把原来表中的最后一列的产量改为ui值，最后一行的销量改为vj值，表中每一栏的右上角仍表示运价，左下角的数中不带括弧的为基变量的运输单位，带括弧的表示非基变量的检验数。当表中某个非基变量的检验数为负值时，表明未得到最优解，要进行方案调整以得到更好的方案。说明：同求初始可行解一样，检验已得的运输方案是否是最优解的方法有两种：一种是闭回路法，另一种是位势法。为了节省篇章，闭回路法的求解原理，请参阅其它书籍。,三、方案的调整首先选取检验数中的最小的负检验数，以它对应的非基变量为入基变量。本例中选非基变量x24为入基变量，并以x24所在格为出发点找一条闭回路。如表113所示：,表113调运方案表,销地,4（+）,产地,闭回路的确定方法为：在给出的调运方案的计算表中，如表113，以入基变量所在格为起点，用水平或垂直线向前划，每遇到一数字格则转90度后继续前进，直到回到起始空格为止。可以证明这样的闭回路一定存在而且唯一。在上表中，由于24=-1，表明增加一个单位的x24的运输量使总运输减少1。所以应尽量多增加x24的运输量，但为了保证运输方案的可行性（即所有的调运量必须大于等于零），所以从出发点x24所在空格定点序号为1的闭回路中，找出所有偶数的顶点的调运量：x14=3，x23=1，取其中的最小值为x24的值，即x24=min(x14，x23,)=min（3，1）=1。为了使产销平衡，把闭回路上所有偶数顶点的运输量都减少这个值，所有奇数顶点的运输量都增加这个值，即得到了调整后的运输方案，如表114所示：,表114调运方案表,销地,1.6运输问题编程算法与编程实践,1.6.1运输问题的理论基础,对调整后的运输方案，再运用位势法求得检验数如表115所示：表115检验数表,产地,销地,表中带括弧的数字是非基变量的检验数，可知所有检验数都大于等于零（基变量的检验数都等于零），此解是最优解，这时得到最小总运输费用为85元，具体的运输方案如下：A1分厂运5吨到销售公司B3，运2吨给销售公司B4；A3分厂运3吨给销售公司B1，运1吨给销售公司B4；A3分厂运6吨给销售公司B2，运3吨给销售公司B4。,3.对供需不平衡的运输问题的处理前面讲的表上作业法的计算和理论，都是以供需平衡，即以为前提的。但是实际问题中供需往往是不平衡的，为了应用表上作业法计算，就需要把供需不平衡的问题转化为供需平衡的问题。当供大于需时，即时,只要增加一个假想的需求单位（实际上是贮存），该需求单位的需求量为（-），而在里程表里，从各供应站到假想单位的运价为0,这样原问题就转化为了一个产销平衡的运输问题。,1.6运输问题编程算法与编程实践,1.6.1运输问题的理论基础,类似地，当需大于供时，即0,则dij0。第二步：计算基变量的检验数。令v10，并计算所有其它的ui和vj，使得ui+vjcij对任意dij0成立。若这样做不可能求出所有的ui和vj，则令dij0,以便能计算所有的ui和vj。这步计算结果得到至少（m+n-1）个元素的检验数dij0。第三步：计算非基变量的检验数。计算公式：dijcijui+vj,结果求得矩阵所有元素的检验数。第四步：在运输矩阵X中，给使得xijdij0的所有的xij元素标上符号“*”（若此种情况发生，则问题称为退划的）。第五步：确定dijmaxcij,（i1，2,m；j1，2，,n）。第六步：判断。对任意i，j，dij0是否成立？若是，则停止计算，当前的运输计划X为最优，其总运费Z定义为Z此处略去往返虚设物的运费。若否，则转至第七步。第七步：新解的确定。（1）给元素xrs标上“+”号。（2）在r行中找出一个大于零的元素，给此元素标以“-”号。该元素满足条件：在其相应的列中至少有一个标有“*”或大于零的元素。,1.6运输问题编程算法与编程实践,1.6.2运输问题的算法和原理,（3）在这样确定的列中找出一个标有“*”或大于零的元素，给此元素标以“+”号。该元素满足条件：在其相应的行中至少有一个大于零的元素。（4）判断。在s列中是否有一个元素标以“-”？若是，则转至第八步；,1.6运输问题编程算法与编程实践,1.6.2运输问题的算法和原理,若否，则转至（2），继续这种标定过程。第八步：在标以“-”的元素中，找出绝对值最小的元素。令此元素为xkl。根据以下计算公式更新运输矩阵xij+xkl，当xij标定为“+”号时；xijxij-xkl，当xij标定为“-”号时；xij，在其它情况下。删去所有标记并转至第一步。示例：给定具有（10，4，6）组货单的三个仓库以及要求（5，12，8）组货物的三家用户。每组货物的运费矩阵为：需大于供，加入一虚拟的仓库，按西北角法，求得初始可行解X(1)），根据步进法，可求得该运输矩阵的检验数。,进一步迭代结果为：,对任意i，j，dij0，所以X(4)给出了货物运输路线的最佳分配方案。最优方案的表格形式如表119；表119产销平衡、运价矩阵表,销地,1.6运输问题编程算法与编程实践,1.6.2运输问题的算法和原理,1.6运输问题编程算法与编程实践,1.6.3运输问题的程序流程图,1.西北角法求初始调运方案的程序流程图,开始,是,输出初始可行调运方案X,输入：供应站的数量m；需求站的数量n,输入：运价矩阵C；供应站的供应量A；需求站的需求量B,定义：所有供应站的下标的集合RRi；所有需求站的下标的集合SSj,根据rminiiRR；sminjjSS；求待分配元素,确定minar,bs；并令xrs；arar；bsrbs,更新下标集合：当ar0时，RRRRr；当br0时，SSSSs,RR为空集,SS为空集,停止,2.步进法求最优调运方案的程序流程图,读取初始可行调运方案X,drs0,s列中有元素标以“-”,是,是,否,输出最优解,停止,开始,在r行中找满足条件的元素标以“-”,计算基变量的检验数；计算位势,计算非基变量的检验数；标定退化元素,求检验数的最大值drs,否,给元素xrs标以“+”号,在标有“-”的之中找出绝对最小者,在s行中找满足条件的元素标以“+”,更新运输矩阵,1.6运输问题编程算法与编程实践,1.6.3运输问题的程序流程图,1.6.4运输问题的实例及操作,1.6运输问题编程算法与编程实践,1.实例例1设中国电子元件公司在上海、武汉、桂林分别设有电容器元件制造厂，它的区域性批发总部在大连、北京、广州和重庆。公司当月在三个产地工厂生产电容器的数量是上海50单位；武汉80单位；桂林120单位。为了满足各批发总部预测市场的需求量，公司必须运送90单位到大连，70单位到北京，40单位到广州，50单位到重庆。公司要求确定一个最优的运输方案，既要满足各批发总部的需求量，又要使运输成本最小。试问，该如何分配运输方案？解：根据数据分析，这是一个平衡运输问题。有关单位产品的运输成本以及需求量和供应量可归结如表120所示数据。表120供需平衡、运价矩阵表,销地,表中A1,A2,A3,分别代表上海，武汉，桂林；B1，B2，B3，B4分别代表大连，北京，广州，重庆。例2某公司从两个产地A1，A2将产品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和