《运筹学课件第三章 运输问题(浙江)》由会员分享，可在线阅读，更多相关《运筹学课件第三章 运输问题(浙江)（50页珍藏版）》请在金锄头文库上搜索。
1、第三章 运输问题3.1 运输问题的表示3.2 初始基础可行解3.3 非基变量的检验数3.4 基解的调整3.5 运输问题的进一步讨论Date1运筹学本章学习要求n掌握表上作业法及其在产销平衡运输问题求解中的应用n掌握产销不平衡运输问题的求解方法Date2运筹学3.1 运输问题的表示n网络图表示n线性规划模型n运输表Date3运筹学某种物资从两个供应地A1，A2运往三个需求地B1，B2， B3。各供应地的供应量、各需求地的需求量、每个供应 地到每个需求地每吨物资的运输价格如下表：运价（元/吨）B1B2B3供应量（吨 ）A123535A247825需求量（吨）10302060求总运费最低的运输方案。
2、Date4运筹学运价 （元/吨）B1B2B3供应量 （吨）A123535A247825需求量（吨）10302060min z=2x11+3x12+5x13+4x21+7x22+8x23 s.t. x11+x12+x13 =35 供应地A1x21+x22+x23 =25 供应地A2x11 +x21 =10 需求地B1x12 +x22 =30 需求地B2x13 +x23 =20 需求地B3x11, x12, x13, x21, x22, x230 Date5运筹学 运输问题的一般提法：假设有m个生产地点，可以供 应某种物资（以后称为产地），用Ai来表示， i=1,m,有n个销地，用Bj来表示，j=
3、1,n，产地 的产量和销地的销量分别为ai,bj，从产地Ai到销地Bj 运输一个单位物资的运价为Cij，这些数据可汇总于下 表，在假设产销平衡的条件下，即ai= bj，问该如 何调运物品使总运费最小？B1B2Bn产量A1C11C12C1na1A2C21C22C2na2 AmCm1Cm2Cmnam 销量b1b2bnDate6运筹学建模：设xij表示从Ai到Bj的运量，则所求的数 学模型为：min =cijxij s.t. xij=ai i=1,mxij=bj j=1,nj=1ni=1mi=1mj=1nxij0 i=1,m,j=1,nDate7运筹学1.运输问题的网络图表示2312341d1=22
4、d2=13d3=12d4=13s2=27s3=19s1=14产地运价销地6 7 53482 759 10 6产量销量总产量60吨 总销量60吨产销平衡的运输问题Date8运筹学2.运输问题线性规划模型产地约束销地约束由于前m个产地约束和后n个销地约束是线性相关的，因此运 输问题系数矩阵的秩bj 方法：虚购一销地Bn+1，其销量bn+1= ai-bj Ai运往Bn+1物资的数量xin+1，就是产地就地贮存的 物资量，因此，产地到虚销地的单位运价均为0， 即cin+1 =0，这样，就转化成了一个产销平衡问题 。Date34运筹学例：某建筑公司有A1、 A2、 A3三个水泥库，其水泥 贮存量分别为3
5、0吨、 50吨、 60吨，四个工地B1、 B2、 B3 、 B4需要水泥的数量依次为15吨、 10吨 、 40吨、 45吨，已知从各库到各工地运送每吨水 泥的费用如下表，求使运费最少的调运方案？B1B2B3B4产产量 A13050804030A27040806050 A310030502060 销销量15104045解：计算ai=140，bj =110，aibj 所以要虚构一销地B4，其销量b5=30，而ci5 =0，这样，就转 化成了一个产销平衡问题。Date35运筹学2）产小于销，即aibj 方法：虚购一产地Am+1，其产量Am+1= bj -ai Am+1运往Bj物资的数量xm+1j，就
6、是各销地缺货的物资量， 因此，虚产地到各销地的单位运价均为0，即cm+1j=0， 这样，就转化成了一个产销平衡问题。 例如：B1B2B3B4产产量A13113109A219284A3741057销销量136156Date36运筹学二、一些变形和推广 1、最大化问题作法：1）找出单位物资效益表（cij）中的最大元素M，即 M=maxcij 2)令bij =M-cij，并视为运价。 3）由bij构成单位运价表，按通常的表上作业法求解，求得 最优解后还要把所得结果转换为原问题的答案。 2、销量不确定（有最高需求和最低需求）设销地Bk的最低需求为bk，最高需求为bk ，这时可把看作 Bk和Bk两个销地
7、， Bk需求量bk ， Bk的需求量bk - bkDate37运筹学例：设某种材料有A1、 A2、 A3三个生产厂家，其产品供应B1 、 B2、 B3 、 B4四个城市，假定等量的材料在这些城市的 使用效果相同，已知各建材厂的年产量、各城市的年需求 量以及各厂到各城市运送单位建材的运价如表所示，求使 运费最少的调运方案？ B1B2B3B4产产量 A11613221750A21413191560 A3192023M50 最低需求3070010 最低需求507030不限解释c34 =M（M是一个无穷大的正数），这意味着不允许从 A3运货至B4，或者因为交通不方便等原因，使从A3到B4不可 能送货。
8、Date38运筹学B1B2B3B4产产量 A11613221750A21413191560 A3192023M50 最低需求3070010 最低需求507030不限B1B1B2B3B4B4销量302070301050A1A2A3A4产量50605050161419M1614190131320M22192301715MM1715M0Date39运筹学3、指定销售问题 如规定销地1的需求量必须由产地4供应，如 何处理？ 1）直接令x41=b1 2)令c41=-M，或者c11=c21=c31=M这样销地1 的需求量肯定是由产地1供应了。Date40运筹学4、缺货损失问题 如下表，设销地1不允许缺货；
9、销地2缺货，单位损失费3 元；销地3缺货，单位损失费2元，问如何处理？B1B2B3产产量A151710A264680A332515销销量655525B1B2B3产产量A151710A264680A332515销销量655525A440M32Date41运筹学三、生产与存储问题例：某厂按合同须于当年每个季度末分别提供10、15、25、20 台同一规格的起重机，已知该厂各季度的生产能力及生产每 台起重机的成本如表所示，若生产出来的起重机当季不交货 ，每台每积压一个季度工厂需支付保管及维护费0.15元，试 问在按合同完成任务的情况下，工厂应如何安排生产计划才 能使全年消耗的生产与存贮费用的总和最少？
10、季度工厂生产产能力（台/季 ）成本（元/台）交货货量（台 ） 12510.81023511.101533011.002541011.3020Date42运筹学发货点：生产起重机的四个季度 发货量：生产能力 收货点：按合同交付起重机的四个季度 收货量：按合同提供起重机的数量 cij=第i季度每台起重机的生产成本+（j-i）个季度每台起重机 的存贮费（ji）12345发发量（台 ） 125235330410收量（台）101525203010.8010.9511.1011.25M11.1011.2511.40MM11.0011.15MMM11.300000Date43运筹学四、有转运的运输问题1、运
11、输表的构成1）产地：原产地、中间转运站、转运物资的销地 2）销地：原销地、中间转运站、转运物资的产地 3）设各转运站转运物资的数量均为 ai 这样专职转运站的产量和销量均为 ai 而原产地Ai的产量均为（ai+ ai） 原销地Bj的销量均为（ bj+ ai） 4)将各条线路实际的运输单位列成单位运价表，其中 不可能的运输其单位运价用M表示。Date44运筹学2、举例： A、B两个化肥厂每年各生产磷肥900、600万吨，这些 化肥要通过公路运到三个港口，然后再装船运往其他各 地，已知三个港口C、D、E每年能承担的船运量分别为 700、400、300万吨，两个工厂及三个港口之间均有公 路相通，且已
12、知单位运价如表所示，为按需要把磷肥运 到各港口，怎样安排运输才能使运费最少？ABCDEA029107B2071010C97034D1010302E710420Date45运筹学ABCDEA029107B2071010C97034D1010302E710420P发量收量240021001500150015001500150022001900180010000000Date46运筹学例：该问题是一个产销平衡问题，也是求极小化问题， 可用表上作业法求解。Date47运筹学解：1.用沃格尔法求初始基可行解行罚数列罚数3122111* 5012*6254* 215 *133Date48运筹学解：2.用位势法求非基变量检验数(求位势）562133uivj0141001Date49运筹学解：2.用位势法求非基变量检验数（求检验数）562133uivj0141001361115由此可知，所有非基变量检验数全0，已得最优调运方案；总 运费为：51+ 34+ 61+ 20+ 35+ 11=39Date50运筹学
