运输问题ppt课件

一、运输问题的数学模型，例如：一个运输问题的数据如下：1、2、某一物品有m个产地a1、a2、每个生产区的产量是a1，a2，分别是am；B2有n个引脚位置B1，每个pin站点的销售量是B1，B2，bn。假设从原产地运输的每单位货物的运费率A1(I=1，2，m)到销售地点BJ (j=1，2，n)是cij，如何通过运输这些货物将总运费率降至最低？运输问题的数学模型，4，运输问题的数学模型的特点，1。运输问题的最优解有限。运输问题约束条件的特点：运输问题的数学模型包含mn个变量和(m n)个约束方程，系数矩阵的结构松散而特殊。5、运输问题的解决，运输问题也是一个线性规划问题，其解决方案仍然可以找到一个基本可行的解决方案，这个解决方案的最优性检验，如果不是最优的，则反复进行检验和调整，直到最优，因此要求解决方案的每一步都是一个基本可行的解决方案，需要满足满足所有约束；(2)对应于基变量的系数列向量是线性无关的；(3)解中非零变量的数量不能大于m n-1，因为尽管在运输问题中有m n个约束，但只有m n-1个约束是线性独立的，因为总产出等于总销售量；(4)在迭代过程中保持基变量的数量m n-1。6，2，表运算法，表运算法是单纯形法在解决运输问题中的一种简化方法，其实质是单纯形法，但具体的计算和术语不同，其步骤可概括如下：(1)找出初始基的可行解：即通过最小元素法或西北角法在(mn)产销平衡表上给出mn-1数，称为数格，它们是初始基变量的值。(2)找出每个非基变量的测试次数，即计算表上空格的测试次数，以确定是否达到最优解。如果是最优解，停止计算，否则进入下一步。(3)确定换入变量和换出变量，找出新的基本可行解。用闭环方法调节仪表。(4)重复(2)和(3)，直到获得最佳解。(1)初始基本可行方案的确定，示例2:煤矿A和B为三个城市A、B和C供应煤。每个煤矿的产量和每个城市所需的煤量以及从每个煤矿到每个城市的运输单价显示在表格中，以找到使总运输成本最小化的运输方案。(1)最小元素法：从运费最低的箱子开始，标出允许在箱子中获得的最大数量。然后根据货运单从小到大。如果某行(列)的产量(销售量)已经达到，则该行(列)的其他单元格将被划掉。这种情况一直持续到获得基本可行的解决方案。最小元素法用于确定初始运输计划。最初的运输计划是：x11=100，x13=100，x22=150，x23=100，14。锻炼。例如，附属于食品公司的A1、A2、A3和3家工厂生产方便食品，这些食品将被运输到B1、B2、B3、B4和4个销售点。数据如下：初始运输计划由表格运算方法确定。15，3，11，3，10，1，9，2，7，4，10，5，8，3，4，1，6，3，3，总运输成本=(31) (64) (43) (12) (310) (35)=86元，16，(2)西北角法不优先考虑单位运费率最低的供销业务，但优先满足交通运输北中西角(左上角)空间的供销要求用西北角法确定初始调度方案，100，100，100，50，50，200，200，18，得到初始调度方案如下：x11=100，x12=100，x22=50，x23=200，19，(2)最优性检验，根据最小元素法或西北角法得到运输问题的初始基本可行解后，按照表运算法的第二步，下一步，我们需要进行最优性判断如果某个空间(A1，Bj)的测试数为负，则意味着将Xij更改为基变量会降低运输成本，因此当前的解决方案不是最佳解决方案。如果所有空间的测试数都为非负，无论如何变化，运输成本都不能降低，即目标函数值不能提高，该解是最优解。21，闭路：在给定运输方案的运输表上，从空间(非基变量)开始，沿水平或垂直方向前进。只有触摸代表基本变量的数字网格，左转或右转90才能继续进行，直到最终返回到初始空间以形成回路。从每个空间开始，必须有并且只有一个闭环。1，闭环方法，22，用xij空间作为第一个奇数顶点，沿闭环顺时针(或逆时针)向前，依次编号闭环上的每个顶点；非基变量的测试次数xij:现在，基于通过最小元素法确定示例2的初始分配方案，非基变量的测试次数X12:23，从初始分配方案中的X12(X21)开始的闭环、24，非基变量的测试次数X12:非基变量的测试次数X21:=(c12 c23)-(c13 c22)=70 75-(100 65)=-20，=(c21 c13)-(c13)经济意义：在保持产销平衡的条件下，当目标函数值变化时，非基本变量增加单位交通量成为基本变量。25，2，双变量法(位势法)，测试数公式：分别表示与前M个约束方程对应的双变量；分别表示对应于最后n个约束方程的对偶变量。26，初始分配方案的对偶变量对应表，27，以初始分配方案为例，建立对偶变量的和，然后构造如下方程：28，其中，如果u1=0，v1=90，v3=100，u2=-25，v2=90可以求解，那么12=c12-(u1 v2)=70-(090)=2021=c21-(U2 v1)=80-(-2590)=15是方程的个数是m n-1=2 3-1=4，对偶变量有m n=2 3=5。初始方案的每个基础变量xij对应于等式-对应于行和列的双重变量的总和等于对应于基础变量的运输距离(或运费率):uivj=cij方程只有一个自由变量，这可以证明方程中的任何变量都可以作为自由变量。此时方程的解可以称为势。公式中，如果u1=0，v1=90，v3=100，u2=-25，v2=90，则12=c12-(u1 v2)=70-(0 90)=-2021=c21-(U2 v1)=80-(-2590)=15与闭环方法得到的结果相同。对用位势法计算非基变量xij检验数的公式ij=cij-(ui vj)进行了评述，并与计算检验数的两种方法32、练习33、34和(3)解的改进闭环调整法进行了比较。如果证实初始解不是最优解，即非基变量的测试数为负，当非基变量变为基变量时，运费将减少。根据表操作方法的第三步，需要改进初始方案。35，解决方案改进步骤，1。(如果多个非基变量的测试数为负，取测试数最小负数所在空间对应的变量)作为变化变量，在运输表中找出其闭环；2.把这个空间作为第一个奇数顶点，顺时针(或逆时针)进行闭环，依次给闭环上的每个顶点编号；3.在闭环的所有偶数顶点中，找出流量最小的顶点，并使用网格中的变量作为交换变量；4.将闭环中所有奇数顶点的交通量增加该交换变量的值，并从所有偶数顶点的交通量中减去该值，最终得出一个新的运输方案。对得到的新方案进行了最优性检验。如果不是最优解，则重复上述步骤并继续调整，直到获得最优解。36，因为12=-20，画一个以x12为起始变量的闭环，0，200，50，100，37，并计算调整量：=min (100，150)=100。根据以下方法调整调度数量：在封闭循环上，获取新的运输计划：38，重复上述步骤，直到找到最佳运输计划：39，40。结果最佳运输方案为：x11=50，x12=150，x21=50，x23=200。相应的最小总运输成本是：Zmin=905070150805075200=34000，41，42，43，(4)产销不平衡的运输问题。上述表格操作方法是以均衡产销为前提的。然而，生产和营销在实际问题中往往是不平衡的，这就需要努力把不平衡的生产和营销问题转化为平衡的生产和营销问题。1.当总产量大于总销售量时，运输问题的数学模型可以写成，44。为了解决这个问题，原来的问题需要变成一个平衡问题。可以假设销售地点Bn 1(即生产地点的库存在实际问题中被考虑)，即45，单位运输价格表2中的单位运费率，并且销售金额大于生产金额：也可以假设生产地点，并且变化与上面相同。必须有一个生产和销售平衡的运输问题的最佳解决方案。如果非基变量的 ij=0，则该问题有无穷多个最优解。(2)退化：一般来说，表格中应该有(m n-1)个单元格。但是，有时在分配流量时，需要同时划掉一行和一列，并且需要添加0以确保(m n-1)个单元格。通常，您可以在要划掉的行和列中的任何空格处添加一个0。用闭环方法调节时，闭环上会出现两个或多个带有(-)标记的相等最小值。此时，只能选择其中一个作为转入案例。但经过调整后，它已被化解。此时，另一个数字网格必须用0填充，表示它是一个基变量。当存在倒退解决方案并进行改进调整时，闭合电路上可能会有标有(-)值的数字网格，然后应采用调整量=0。对于具有特殊调度约束的运输问题，供应数量约束是，例如，从某个供应商到某个需求方的供应数量不超过百分之几。过境运输的问题增加了几个配送中心(或物流网点)，但限制了它们的吞吐量。一家公司从三家供应商(A1、A2、A3)购买某些材料，以满足四家分销商(B1、B2、B3、B4)的生产需求，制造商的供应、分销商的需求以及供需点之间的运输距离如表所示。由于供应短缺和产品质量问题，公司决定必须保证B2和B3的需求，B4不能从A3采购，必须寻求最佳的材料分配方案。练习：一家公司从三家供应商(A1、A2、A3)处购买某些材料，以满足四家分销商的生产需求，制造