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

课题：工学院计算机系年10月3.2 用用表表上上作作业业法法求求解解运运输输问问题题销销地地产产地地 B1 B2 B3 B4 产产量量 A1 9 3 8 7 3 A2 4 9 4 5 3 A3 5 7 6 2 5 销销量量 1 3 2 5 3.3 运运输输问问题题的的进进一一步步讨讨论论销销地地产产地地 B1 B2 B3 B4 产产量量 A1 9 3 8 7 3 A2 4 9 4 5 3 A3 5 7 6 2 5 销销量量 1 3 2 5 3.3 运运输输问问题题的的进进一一步步讨讨论论销销地地产产地地 B1 B2 B3 B4 产产量量 A1 9 3 8 7 3 A2 4 9 4 5 3 A3 5 7 6 2 5 销销量量 1 3 2 5 课课堂堂内内容容3.3 运运输输问问题题的的进进一一步步讨讨论论 销销地地 产产地地 B1 B2 Bn 产产量量ai A1 C11 x11 C12 x12 C1n x1n a1 A2 C12 x21 C12 x22 C12 x23 a2 Am Cm1 xm1 Cm2 xm2 Cmn xmn am 销销量量 bj b1 b2 bn 3.3 运运输输问问题题的的进进一一步步讨讨论论1 1 产量大于销量产量大于销量目标函数：目标函数：st.st.3.3 运运输输问问题题的的进进一一步步讨讨论论2 2 销量大于产量销量大于产量目标函数：目标函数：st.st.3.3 运运输输问问题题的的进进一一步步讨讨论论3.3 运运输输问问题题的的进进一一步步讨讨论论 1 1 产量大于销量产量大于销量minjjiba11增加一个假想的销地增加一个假想的销地Bn+1，其销量为，其销量为bn+1；从从Ai 运到运到Bn+1的物品数量的物品数量xi,n+1；（3）ci,n+1=0 0；因为因为Bn+1实际上不存在，所以实际上不存在，所以xi,n+1 实际上就是就实际上就是就地存储在产地地存储在产地Ai 的物品数量。的物品数量。（1）（2）3.3 运运输输问问题题的的进进一一步步讨讨论论st.st.产量大于销量的：产量大于销量的：3.3 运运输输问问题题的的进进一一步步讨讨论论 2 2 销量大于产量销量大于产量增加一个假想的产地增加一个假想的产地Am+1，其产量为，其产量为am+1；从从Am+1 运到运到Bj的物品数量的物品数量xm+1,j；（3）ci,n+1=0 0；因为因为Am+1实际上不存在，所以实际上不存在，所以xm+1,j实际上是各销实际上是各销地地Bj所需物品的欠缺额。所需物品的欠缺额。xm+1,jxm+1,j（1）（2）3.3 运运输输问问题题的的进进一一步步讨讨论论st.st.销量大于产量的：销量大于产量的：m+1m+1m+1m+13.3 运运输输问问题题的的进进一一步步讨讨论论销地销地产地产地 B1 B2 B3 产量产量 A1 6 4 5 70 A2 8 3 2 40 A3 7 5 6 50 A4 5 1 2 20 销量销量 30 40 30 180 100 3.3 运运输输问问题题的的进进一一步步讨讨论论销销地地产产地地 B1 B2 B3 产产量量 A1 6 4 5 70 A2 8 3 2 40 A3 7 5 6 50 A4 5 1 2 20 销销量量 30 40 30 B43.3 运运输输问问题题的的进进一一步步讨讨论论销销地地产产地地 B1 B2 B3 B4 产产量量 A1 6 4 5 0 70 A2 8 3 2 0 40 A3 7 5 6 0 50 A4 5 1 2 0 20 销销量量 30 40 30 80 180 3.3 运运输输问问题题的的进进一一步步讨讨论论销销地地 产产地地 B1 B2 B3 B4 产产量量 A1 6 30 4 10 5 0 30 70 A2 8 3 10 2 30 0 40 A3 7 5 6 0 50 50 A4 5 1 20 2 0 20 销销量量 30 40 30 80 180 3.3 运运输输问问题题的的进进一一步步讨讨论论运价 地区煤矿甲乙丙丁产量 A B C161419131320221923171525506050最低需求最高需求3050707003010不限设有三煤矿供应四地区，资料如下：3.3 运运输输问问题题的的进进一一步步讨讨论论虚拟产量的运输费用为零虚拟产量的运输费用为零,但它对于基本需求来讲但它对于基本需求来讲,运费为无穷大。运费为无穷大。本题产量本题产量160万吨，最低需求万吨，最低需求110万吨，最高需求万吨，最高需求无限。实质上比较现实的最高需求无限。实质上比较现实的最高需求210万吨万吨;(?)产量大于最小需求；小于最大需求。而标准型是：产量大于最小需求；小于最大需求。而标准型是：产量产量=销量；销量；处理办法：设想一个虚拟煤矿处理办法：设想一个虚拟煤矿D，生产，生产50万吨万吨,但但这个产量只能供应可有可无的最高需求部分这个产量只能供应可有可无的最高需求部分,于是于是各地的需求各地的需求也应分为两个部分：也应分为两个部分：基本需求基本需求、机动机动需求需求；运运价价 地地区区 煤煤矿矿 甲甲 乙乙 丙丙 丁丁 产产量量 A 16 13 22 17 50 B 14 13 19 12 60 C 19 20 23 25 50 需需求求量量 50运运价价 地地区区 煤煤矿矿 甲甲 乙乙 丙丙 丁丁 产产量量 A 16 13 22 17 50 B 14 13 19 12 60 C 19 20 23 25 50 最最 低低 需需 求求 最最 高高 需需 求求 30 50 70 70 0 30 10 不限 设想一个虚拟煤矿设想一个虚拟煤矿D,生产生产5050万吨万吨,这个产量只能供应可有可这个产量只能供应可有可无的最高需求部分无的最高需求部分,于是各地的需求分为于是各地的需求分为基本需求基本需求和和机动需求机动需求；3.3 运运输输问问题题的的进进一一步步讨讨论论 甲甲1 甲甲2 乙乙 丙丙 丁丁1 丁丁2 产产 量量 A 16 16 13 22 17 17 50 B 14 14 13 19 12 12 60 C 19 19 20 23 25 25 50 D M 0 M 0 M 0 50 需需 求求 量量 30 20 70 30 10 50 3.3 运运输输问问题题的的进进一一步步讨讨论论 甲甲1 甲甲2 乙乙 丙丙 丁丁1 丁丁2 ui A 16 16 13 50 22 17 17 B 14 14 13 19 12 10 12 50 C 19 30 19 20 20 23 25 25 D M 0 0 M 20 0 30 M 0 0 vj 3.3 运运输输问问题题的的进进一一步步讨讨论论 甲甲1 甲甲2 乙乙 丙丙 丁丁1 丁丁2 ui A 16 16 13 50 22 17 17 B 14 14 13 20 19 12 10 12 30 C 19 30 19 20 20 23 25 25 D M 0 0 M 0 30 M 0 20 vj 3.3 运运输输问问题题的的进进一一步步讨讨论论假定假定m个产地个产地A1,A2,Am和和n个销地个销地B1,B2,Bn都可以作为中间转都可以作为中间转运站使用，从而发送物品的地点和接收物品的地点都有运站使用，从而发送物品的地点和接收物品的地点都有m+n个。个。例例令：令：ai第第i个产地的产量（净供应量）；个产地的产量（净供应量）；bj第第j个销地的销量（净需要量）；个销地的销量（净需要量）；xij由第由第i个发送地运到第个发送地运到第j个接收地的物品数量；个接收地的物品数量；cij由第由第i个发送地到第个发送地到第j个接收地的单位运价；个接收地的单位运价；ci第第i个地点转运单位物品的费用；个地点转运单位物品的费用；Q3.3 运运输输问问题题的的进进一一步步讨讨论论 产地 销地 接收 发送 1 m m+1 m+n 发送量 1 x11 x1m x1,m+1 x1,m+n Q+a1 产地 m xm1 xmm xm,m+1 xm,m+n Q+am m+1 xm+1,1 xm+1,m xm+1,m+1 xm+1,m+n Q 销地 m+n xm+n,1 xm+n,m xm+n,m+1 xm+n,m+n Q 接收量 Q Q Q+bm+1 Q+bm+n 产销表产销表3.3 运运输输问问题题的的进进一一步步讨讨论论 产地 销地 接收 发送 1 m m+1 m+n 发送量 1-c1 c1m c1,m+1 c1,m+n Q+a1 产地 m cm1 -cm cm,m+1 cm,m+n Q+am m+1 cm+1,1 cm+1,m-cm+1 cm+1,m+n Q 销地 m+n cm+n,1 cm+n,m cm+n,m+1 -cm+n Q 接收量 Q Q Q+bm+1 Q+bm+n 运价表运价表3.3 运运输输问问题题的的进进一一步步讨讨论论st.st.m+nm+n转运模型：转运模型：m+nm+nm+nm+n3.3 运运输输问问题题的的进进一一步步讨讨论论左图显示出了一个运输系统左图显示出了一个运输系统,它包括二个它包括二个产地产地(和和)二个销地二个销地(和和)及一及一个中间转运站个中间转运站(),),各产地的产量和各销各产地的产量和各销地的销量用相应节点处箭线旁的数字表地的销量用相应节点处箭线旁的数字表示，节点连线上的数字为该地的转运单示，节点连线上的数字为该地的转运单价价,试确定最优运输方案。试确定最优运输方案。产地 转运 销地 接收 发送 1 2 3 4 5 发送量 1 产地 2 转运 3 4 销地 5 接收量 运价表运价表3.3 运运输输问问题题的的进进一一步步讨讨论论 产地 转 运 销地 产地 转 运 销地 接收 发送 1 1 2 2 3 3 4 4 5 5 发 量 1 2 3 4 5 1 1 60-4 5 3 2 M 产地 2 2 90 5-1 2 M 4 转 运 3 3 50 3 2-3 5 5 4 4 50 2 M 5-3 6 销地 5 5 50 M 4 5 6-5 收量 50 50 50 80 70 一、初始调运方案一、初始调运方案解解初始调运方案：初始调运方案：x12,x22x24x25x33x34x14，,x44x55=相应运价为：相应运价为：c12,c22c24c25c33c34c14，,c44c5550,50 20 20 50010，,50 50=-4,-1M4-352，,-3-5 二、解的最优性检验和改进二、解的最优性检验和改进3.3 运运输输问问题题的的进进一一步步讨讨论论 产 地 转 运 销 地 接 收 发 送 1 1 2 2 3 3 4 4 5 5 ui 1 1 -4 4 50 5 3 2 2 10 M 产地 2 2 5 5 -1 1 50 2 M M 20 4 4 20 转 运 3 3 3 3 2-3 3 50 5 5 0 5 4 4 2 2 M 5-3 3 50 6 销地 5 5 M M 4 5 6-5 5 50 vj 解解3.3 运运输输问问题题的的进进一一步步讨讨论论 产 地 转 运 销 地 接 收 发 送 1 1 2 2 3 3 4 4 5 5 ui 1 1 -4 4 50 5 3 2 2 10 M 产地 2 2 5 5 -1 1 50 2 20 M M 4 4 20 转 运 3 3 3 3 2-3 3 30 5 5 20 5 4 4 2 2 M 5-3 3 50 6 销地 5 5 M M 4 5 6-5 5 50 vj 解解三、解的最优性检验三、解的最优性检验x14,x23x25x34,=10,20 202020,x34,3.3 运运输输问问题题的的进进一一步步讨讨论论谢谢观看/欢迎下载BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES.BY FAITH I BY FAITH