zt线性规划的运输问题(PPT 32)作业讲解

1、课题：线性规划的运输问题13.2 用表上作业法求解运输问题作业讲解1 求解初始调运方案（最小元素法）50210010300初始运费3*3+4*1+4*2+2*531(元)023.3 运输问题的进一步讨论作业讲解1 求解初始调运方案（西北角法）1221221005初始运费9*1+3*2+9*1+4*2+2*542(元)033.3 运输问题的进一步讨论供大于求的运输问题1 求解初始调运方案（沃格尔法）04初始运费3*3+4*1+4*2+2*531(元)hi vj 324133110500021100041 运输问题的类型；运输问题课堂内容一 知识点回顾二 新知识点1 产销不平衡运输问题的类型；2

2、产销不平衡运输问题的数学模型；3 产销不平衡运输问题最优解的计算；(1) 编制初始调运方案最小元素法、(2) 解的最优性检验(3) 解的改进闭回路法、确定换入的非基变量；确定换出的基变量；GO TO 2对偶变量法（位势法）西北角法、沃格尔法2 产销平衡运输问题的表上作业法;4 运输问题的应用；53.3 运输问题的进一步讨论运输表产销不平衡问题一 产销不平衡问题的类型63.3 运输问题的进一步讨论一、产销不平衡问题的类型产销不平衡问题1 产量大于销量目标函数：st.73.3 运输问题的进一步讨论2 销量大于产量目标函数：st.一、产销不平衡问题的类型产销不平衡问题8产销不平衡问题3.3 运输问题

3、的进一步讨论1 产销不平衡转化为产销平衡的模型求解；2 方法：增加一个虚拟的产地或销地，从而变成标准型产销平衡问题。3 运输问题产销平衡模型，实质上就是一个求解运输问题的标准型。二、解题思路93.3 运输问题的进一步讨论 1 产量大于销量增加一个假想的销地Bn+1，其销量为bn+1 ；从Ai 运到Bn+1的物品数量xi,n+1 ；（3） ci,n+1 =0 ； 因为Bn+1实际上不存在，所以xi,n+1 实际上就是就地存储在产地Ai 的物品数量。因为就地存贮的物品无需运输，所以上式结果为三 不平衡模型转化为平衡模型（1）（2）产销不平衡问题103.3 运输问题的进一步讨论st.产量大于销量的：

4、n+1n+1n+1三 不平衡模型转化为平衡模型产销不平衡问题113.3 运输问题的进一步讨论 2 销量大于产量增加一个假想的产地Am+1，其产量为am+1 ；从Am+1 运到Bj的物品数量xm+1,j ；（3） ci,n+1 =0 ； 因为Am+1实际上不存在，所以xm+1,j实际上是各销地Bj所需物品的欠缺额。因为xm+1,j实际上并没有被运输，所以上式结果为xm+1,j（1）（2）三 不平衡模型转化为平衡模型产销不平衡问题123.3 运输问题的进一步讨论st.销量大于产量的：三 不平衡模型转化为平衡模型产销不平衡问题m+1m+1m+1m+1133.3 运输问题的进一步讨论供大于求的运输问题

5、143.3 运输问题的进一步讨论引入虚拟销地B4 ，（或理解为仓库），就地“销售”，运费为零000080180供大于求的运输问题B4153.3 运输问题的进一步讨论1 求解初始调运方案（运用最小元素法）供大于求的运输问题2030201030601010303050105016解的改进3.3 运输问题的进一步讨论0-306-1034-3-2-3-1-1-1-2-3-2供大于求的运输问题ui vj 2 解的最优性检验（运用位势法）3 所有非基变量的检验数都小于零，所以该解已经是最优解。173.3 运输问题的进一步讨论弹性需求问题运价 地区煤矿甲乙丙丁产量 A B C1614191313202219

6、23171525506050最低需求最高需求3050707003010不限设有三煤矿供应四地区，资料如下：183.3 运输问题的进一步讨论对问题进行分析：虚拟产量的运输费用为零,但它对于基本需求来讲,运费为无穷大。本题产量160万吨，最低需求110万吨，最高需求无限。实质上比较现实的最高需求210万吨;(?)1产量大于最小需求；小于最大需求。而标准型是：产量=销量；2处理办法：设想一个虚拟煤矿D，生产50万吨,但这个产量只能供应可有可无的最高需求部分,于是各地的需求也应分为两个部分：基本需求、机动需求；34弹性需求问题19D 甲2 丁2 11MMM00030205010307050191416

7、251217 设想一个虚拟煤矿D,生产50万吨, 这个产量只能供应可有可无的最高需求部分,于是各地的需求分为基本需求和机动需求；16011021060203.3 运输问题的进一步讨论求初始调运方案1（使用最小元素法）105050050203020202003030000弹性需求问题213.3 运输问题的进一步讨论解的最优性检验2（使用位势法）013M-13M-16+M13-M13-M13-M13-M13-M-3-M-3-M-9-M-4-M-4-M-2-2M-1-7M-1-4-6-6-M-M有大于零的检验数,所以原初始调运方案不是最优方案3解的改进302020GO TO 2弹性需求问题223.3

8、 运输问题的进一步讨论013-12071212121212-4-4-10-5-5-2-2-7-4-6-6-M-M1-M0因为所有非基变量的检验数都已经小于等于零，所以该方案就是最优调运方案。弹性需求问题4进行解的最优性检验；523X44X423.3 运输问题的进一步讨论三 转运与平衡的关联假定m个产地A1,A2,Am和n个销地B1,B2,Bn都可以作为中间转运站使用，从而发送物品的地点和接收物品的地点都有m+n个。A1 A2 B1 B2 B3 例令：ai第i个产地的产量（净供应量）；bj第j个销地的销量（净需要量）；xij由第i个发送地运到第j个接收地的物品数量；cij由第i个发送地到第j个接

9、收地的单位运价；ci第i个地点转运单位物品的费用；Q有转运的运输问题243.3 运输问题的进一步讨论产销表转运的运输问题25转运的运输问题3.3 运输问题的进一步讨论运价表263.3 运输问题的进一步讨论st.m+nm+n转运模型：m+nm+nQ+Q+Qm+nm+n转运的运输问题27转运例题3.3 运输问题的进一步讨论左图显示出了一个运输系统,它包括二个产地(和)二个销地(和)及一个中间转运站(),各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点连线上的数字为该地的转运单价,试确定最优运输方案。 32145311045403203052325645运价表-4-1-3-5-3352M

10、5235425M2M65M54610+5040+5050505050505030+5030+5028表上作业法求解步骤3.3 运输问题的进一步讨论502050105030020405010205020125430687209一、初始调运方案解初始调运方案：x12,x22x24x25x33x34x14，,x44x55=相应运价为：c12,c22c24c25c33c34c14，,c44c5550,50202050010，,5050=-4,-1M4-352，,-3-529二、解的最优性检验和改进3.3 运输问题的进一步讨论0M-23-5-11+M-41-M6-M-62-4-2M2-M-4-M-14-15-M-11-4M-116-2M-22+M-16M-10-94-M-5-M-15+M203020解新总运费=+=300（元）2*10+4*20+2*205*203*20+表上作业法求解步骤303.3 运输问题的进一步讨论083-5-1-4-9-4-62-14-M-8-14-14-5-M-11-4-1-4-M-12-16-9-6-15-5解10-M空格检验数都小余零，所以是最优解.=300最小运费三、解的最优性检验表上作业法求解步骤x14,x23x25x34,=10,20202020,x34,31知识点回顾产销不平衡运输问题求解最优运输