产销不平衡的运输问题运筹学ppt课件.ppt

运筹学 产销不平衡运输问题 1运输问题2运输问题的表上作业法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 运输问题 产销不平衡的运输问题实际问题中产销往往是不平衡的 就需要把产销不平衡的问题转化成产销平衡问题 产大于销销大于产 运输问题 一 产销不平衡的运输问题 若总产量大于总销量 即 令假象销地的销量为 运输问题 这里 松弛变量xin 1可以视为从产地Ai运往销地Bn 1的运输量 由于实际并不运送 它们的运费为cin 1 0i 1 2 m 于是 这个运输问题就转化成了一个产销平衡的问题 运输问题 原产大于销平衡问题的数学模型 运输问题 修改后产大于销平衡问题的数学模型 运输问题 决策变量表示由到的物品数量 注意 用最小元素法求初始调运方案时 最后一列的零运价最后考虑 运输问题 例 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 运输问题 解 增加一个虚设的销地运输费用为0 运输问题 若总产量小于总销量 即 令假象产地的销量为 一 产销不平衡的运输问题 仿照上述类似处理 运输问题 这里 松弛变量xm 1 j可以视为从产地Am 1运往销地Bj的运输量 由于实际并不运送 它们的运费为cm 1 j 0j 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 如果运输问题