产销不平衡的运输问题.ppt

,第四章 运输问题,4.1 运输问题4.2 运输问题的表上作业法4.3 运输问题的进一步讨论,运输问题,产销平衡问题的数学模型,运输问题,表上作业法是单纯形法在求解运输问题的一种简便方法。单纯形法与表上作业法的关系：（1）找出初始基可行解（2）求各非基变量的检验数（3）判断是否最优解,运输问题,换基：,（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。,停止,运输问题,举例说明表上作业法,例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：,运输问题,第一步：确定初始基可行解 最小元素法、伏格尔法,最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。,运输问题,最小元素法举例,8,2,2,0,10,10,0,6,14,8,6,8,0,0,0,0,6,0,运输问题,例1用伏格尔法得到的初始基可行解,目标函数值,用最小元素法求出的目标函数z=246,一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。,运输问题,第三步：解的调整,调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。,（-2）,（-2）,（+2）,（+2）,运输问题,调整后的解为：,此时的解为最优解。,有无穷多最优解,运输问题,几点说明：,当检验数为的负的变量超过两个，选择最小者对应的变量换入；在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。,运输问题,产销不平衡的运输问题实际问题中产销往往是不平衡的，就需要把产销不平衡的问题转化成产销平衡问题。产大于销销大于产,运输问题,一、产销不平衡的运输问题,（）若总产量大于总销量，即,令假象销地的销量为：,运输问题,这里，松弛变量 xi n+1 可以视为从产地 A i 运往销地 Bn+1 的运输量，由于实际并不运送，它们的运费为 ci n+1=0 i=1,2,m。于是，这个运输问题就转化成了一个产销平衡的问题。,运输问题,原产大于销平衡问题的数学模型,运输问题,修改后产大于销平衡问题的数学模型,运输问题,决策变量 表示由 到 的物品数量。,注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。,运输问题,例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,运输问题,解：增加一个虚设的销地运输费用为0,运输问题,（）若总产量小于总销量，即,令假象产地的销量为：,一、产销不平衡的运输问题,仿照上述类似处理。,运输问题,这里，松弛变量 x m+1,j 可以视为从产地 A m+1 运往销地 B j 的运输量，由于实际并不运送，它们的运费为 c m+1,j=0 j=1,2,n。于是，这个运输问题就转化成了一个产销平衡的问题。,运输问题,例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,运输问题,解：增加一个虚设的产地运输费用为0,运输问题,产销不平衡运输问题举例 设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表,举例,运输问题,根据题意，作出产销平衡运价表：,运输问题,最低要求必须满足，因此把相应的虚设产地运费取M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0。对应 4”的销量50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。,运输问题,Ex.2,已知运输问题由表给出，试建立运输模型.,解:,本题产量为25，销量为29，是销大于产问题,虚设一个产地 A3，由于并没有生产，所以运价为零，得运输模型.,如果各销地不满足时，单位缺货费为 4，3，7，则运输模型为,4,3,7,运输问题,讨论,运输问题,一、概念题（判断）,1、运输问题是一种LP问题，其求解结果有四种情况。2、在运输问题中，只要给出一组含（m+n-1）个非零的，且满足 就可以作为一个初始基可行解。,运输问题,3、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。5、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。6、如果.分别乘上一个常k,.不会发生变化。,