运输问题(新)

1、第三章运输问题、运输问题数学模型示例：某公司销售甲方产品，设有三个加工厂的四个销售点，其加工厂的产量、销售地的销售量及各工厂到各销售点的单位运价见表，如何运输， 总运输费最少的xij是从ai到bj的销售量minz=3x 1111 x 123 x 1310 x 147 x 314 x 3210 x 335 x 34 x 11 x 12 x 13 x 14=7a1x 21 x 22 x 23 x 24=4a2x 31x 32 x 33 x 34=9a 3 i=1，2，3 j=1，2，3，4， x11x20 j=1、2、3、4，上述问题可以扩展到m产地的n个大头针地的运输问题，设ai为ai产量，bj

2、为bj大头针地销售量，从ai到bj单位运输价格cij，则生产销售平衡的运输问题的数学模型是，i=1、2、 的m n个方程对于产销平衡问题ai=bj运输问题(产销平衡)始终是可行解和最优解1，cij0 xij 0 cij xij 0运输问题必有有界，2，必有可行解xij=，3，因有界有可行解， 最佳解约束方程式系数矩阵具有稀疏结构(参照下一页为p 11 p 12 p1n p2p 22 pm1pm2pmn 11 a 111 a 233601 am1b 11 b 2336011 bm，m行，n行，第i个成分，第m个第j个成分。 关于系数矩阵pij，除了第i个和第m个j个分量为1以外，其馀分量都是0

3、a的前m行之和减去后n行之和后得到的是零向量、即a的行向量线性相关，其不等于零的子式的最大次数是m n-1， 表操作法步骤：1.确定初始基本可行解有3种方法进行最佳解的判别，如果是最佳则停止，否则下一步骤3 .确定进化学基距离化学基变量，查找新的基本可能解，返回2，重复2、3直到得到最佳解。 最小尺元素体、基本思想：步骤：1.从单位运输价目表中查找最小元素体ckt=min cij 2.根据与ckt对应的产地生产量ak，根据销售地销售量bt决定运输量调整量xkt=min ak，bt，将xkt记入销售平衡表中ak=ak-btakbt，xkt bt=bt-akakak=bt删除第bt行或第t列，从b

4、t=0或ak=0 3 .未被删除的要素中查找最小，3、1、4、6、3、3、注意：如果存在多个最小运价，则任一保证数字格式的数量为(m n-1 )个， 可以选择在产销平衡表中填写数字的格是数字格，螺栓凝胶法，思维方法：步骤：1.修正各行各列的最小元素和下一个最小元素cij的差，分别选择最右边的列和最下面的行2 .选择差最大的行(或列)，该行(列)的最小元素cij 确定0的2，行差额，7，6，最佳解判别： 2个方法：闭回路法电位法1 .闭回路法：互不相同的2k个变量x 11 x 21 x kk x1k，闭回路求法：提出了调运方案的生产销售平衡表，从某个空格(k，t )格出发遇到合适的数字格，转90

5、圈继续前进，再遇到一个合适的数字格，转90圈，继续前进，最后返回原始的出发点(k，t )，注意：以空格为起点，以一部分数字格为拐点，最终返回起点，构成的路径称为闭路。闭合回路是唯一的！ 每个空间点都可以构成闭合回路！ 从(k，t )格出发对闭环的各顶点依次编号，将(k，t )格作为第一顶点，对经过的其他各顶点依次编号，将第二、第三顶点设为11=(c 11 c 23 )-(c 13 c 21 )=(32 )-(31 )=1， 电势法设xij为从ai到bj的运输量，根据例1的运输问题数学模型，设u1、u2、u3的其对偶问题为max=ui ai vj bj ui vjcij、ui、vj无约束、i=1

6、、2、3j=1、2、3、4，同理：一般运输问题数学模型vn是与运输问题m的n个拘束方程式对应的对偶变量对偶问题数学模型： max=ui ai vj bj ui vjcij ui，vj无拘束ui，vj也分别称为与出发点(产地) i和收点(大头针地) j对应的电位，i=1，2， 如果将mj=1，2，n，化学基b作为运输问题的可执行化学基，则双对变量y=cbb-1=(u1，u2，um，v1，v2， vn )根据用于确定变量xij的系数列向量的简单算法的原理，基本变量检验常数为零的cij-ui-vj=0 cij=ui vj xijxb可以将一个运输场景中所有基本变量的运输价格cij分解为对应的行电势和

7、列电势两者接下来的页面：能够求出基于基变量cij=ui vj的非基变量检验常数ij=的ij例：例1初始传送表如下表所示，该例： m=3、n=4、基变量为6个、对应的cij方程式也为6个、电位量(双对变量)为7个、6个方程式为对设u1为自由的u1=0c 13=u1v3=3v3=3c 14=u1v4=10 c 23=u2v3=2u2=-1 c 21=u2v1=2c 34=的非基础变量的检查数ij=cij-ui-vj进行校正，上述的校正运算过程能够在表中进行注：上表右上犄角旮旯的数字为单位运费，左下犄角旮旯的红色数字为非基本变量检验数，中间蓝色数字说明运量上表有负检验数，不是最佳解。 1、2、1、-

8、1、10、12、势能法的步骤除此之外的情况下，转3、计划调整。调试方案的改良闭路调整法1、将进化学基格(进化学基变量) min=ij ij 0=kt xkt进行化学基格2、从进化学基格(k，t )制作闭路，对各顶点依次决定编号、3、调整量和距离化学基格调整量4、闭路调整：闭路上：奇数顶点运输量q双位数顶点运输量-q其本身5、2、3、1、6、3、0、3、10、-5、9，对于运输问题解： 1，无穷多最佳解：2，解：基本变量可能取零值。、31145、738、12106、3、6、4、1、6、0、31145、738、12106、第3 k行或第t列删除，继续查找其他数字，在云同步中删除第k行和第t列，在删

9、除的行或列中的某个空格中填入零作为数字格式2 ) 用闭环法改善调整方案时：闭环顶点出现2个以上的最小运输量，调整后从这些个的双位数顶点减去调整量后，运输量为零，产销不平衡运输问题及其解决方法1，产销： ai bj，xijaiii=1，2 mxij=bj=1，2n，松弛变量4，2，3，3，3，3，2，2，3，ui，vj，0，2，4，0，- 2，3，0，3 xij=ai 1，21，j=1，n，ij=bjj=1，2 n，i=1，m 1，示例2:设有三个化学肥料工厂17、15、-、d、m、0、m、0、m、0、50、30、70、30、10、20、50，用表工艺要求的最佳方案如下。 1500、500、500、500、500、500、500、ui、vj、0、0、4、6、5、4、12 17、18-c22、-3c220、10-c220、24-c22018-c22