_线性规划方法.ppt

销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销量 3 6 5 6 销地 产地 B1 B2 B3 B4 A1 A2 A3 0 9 2 2 1 12 表5.3.19 表5.3.20 三、产销不平衡的运输问题的求解方法 前面求解运输问题的表上作业法，是以产销平衡为前提的 ，即 实际情况需要把产销不平衡的问题化成产销平衡的问题。 ★当产大于销 运输问题的数学模型为求 使 且满足： 考虑多余的物资在哪一个产地就地储存的问题。设 是产地Ai的储存量，于是有： 当 时，令 当 时，令 产销不平衡的运输问题就可以改写成：求 使 且满足： 此时，该问题变为产销平衡问题 ，可用用表上作业法对其求解。 ★当销大于产时，只要在产销平衡表中增加一个假想的产地，让该地的产量为 ，并在单位运价表中令从假想的产地到各消费地的运价为 ，就可以将其转化为一个产销平衡的运输问题。然后可以用表上作业法对其求解 。 例1：试用对偶单纯形法求解如下线性规划问题 首先将该问题化为： -2 -3 -4 0 0 CB XB b X1 X2 X3 X4 X5 0 0 X4 X5 -3 -4 -1 [-2] -2 1 -1 3 1 0 0 1 -2 -3 -4 0 0 初始单纯形表，如表5.2.4所示 表5.2.4 b列各行为负，进行迭代计算，确定换出变量。 故X3为换出变量 。 故X1为换入变量。换入、换出变量所在列、行的交叉处“2”为主元项。进行迭代运算，得表5.2.5。  表5.2.5 -2 -3 -4 0 0 CB XB b X1 X2 X3 X4 X5 0 -2 X4 X1 -1 2 0 1 [-5/2] -1/2 1/2 3/2 1 0 -1/2 -1/2 0 -4 -1 0 -1 从上表可看出，b列中仍有负分量，继续迭代计算，重复上述步骤，得表5.2.6。 表5.2.6 -2 -3 -4 0 0 CB XB b X1 X2 X3 X4 X5 -3 -2 X2 X1 -2/5 11/5 0 1 1 0 -1/5 7/5 -2/5 -1/5 1/5 -2/5 0 0 -3/5 -8/5 -1/5 在上表中，b列各分量全为非负，检验数全为非正，故问题的最优解为 ，其对偶问题的最优解为 第三节 运输问题的求解方法——表上作业法 产销平衡表与单位运价表 表上作业法 产销不平衡的运输问题的求解方法 一、产销平衡表与单位运价表 运输问题还可用产销平衡表与单位运价表进行描述。 假设某种物资有m个生产地点Ai（i=1，2，…，m），其产量（供应量）分别为ai（i=1，2，…，m），有n个销地Bj（j=1，2，…，n），其销量（需求量）分别为bj（j=1，2，…，n）。从Ai到Bj运输单位物资的运价（单价）为Cij。将这些数据汇总可以得到产销平衡表和单位运价表5.3.1。 销地 产地 产量 销量 表5.3.1 产销平衡表与单位运价表 二、表上作业法 运输这一类特殊问题可用更加简便的求解方法—表上作业法求解，实质仍是单纯形法，步骤如下： （一）找出初始基可行解，即在产销平衡表上给出m+n-1个数字格。 确定初始可行基的方法： 最小元素法： 从单位运价表中最小的运价开始确定供销关系，然后考虑运价次小的，一直到给出初始基可行解为止。 伏格尔法 采用最小元素法可能造成其他处的更多浪费，伏格尔法考虑最小运费与次小运费之间的差额，差额越大，就按次小运费调运。 （二）求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。若已是最优解，则停止计算，否则转入下一步。 最优解的判别 计算非基变量（空格）的检验数 时为最优解。 求空格检验数的方法有： 1.闭回路法：以某一空格为起点找一条闭回路，用水平或垂直线向前划，每碰到一数字格转90○后，继续前进，直到回到起始空格为止。 闭回路如图4.3.1的（a）、（b）、（c）等所示。从每一个空格出发一定存在并且可以找到唯一的闭回路。因为，m+n-1个数字格（基变量）对应的系数向量是一个