[工学]运筹学课件 2运输问题.pptVIP

第三章 特殊的线性规划——运输问题 ?3.1 运输问题模型与性质 一、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？ 2、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足： 运输问题的数学模型 三、运输问题的求解方法 1、单纯形法（为什麽？） 2、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法 3、举例 例3-2 甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4，求使总运输量最少的调运方案。 表3-4 例3-2有关信息表 例3-2 的数学模型 运输问题的计算机求解——表上作业法 1、适用软件 Transportation/Transshipment Problem（TRP） 2、输入数据： Maximize 1 minimize 2 2 Number of sources? 2 Number of destinations? 3 Number of transshipment point? 0 Use the default names(S1 …Sn ,D1 …Dn ,T1…Tn) Y Press the Space Bar to continue if your entries are correct Capacities of Sources S1: 200 S2: 250 Demands of destinations D1: 100 D2: 150 D3: 200 ENTER THE Cost/Profit Coefficients of the TRP Model Minimization From To S1 D1: 90 D2: 70 D3: 100 S2 D1: 80 D2: 65 D3: 80 3、计算过程中的初始表 Initial solution by  4、求解结果报告 几点说明： 分别使用最小元素法和西北角法求出初始方案。 最小元素法的基本思想是“就近供应” ； 西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同 ； 450 200 150 100 销 量 250 75 X23 65 X22 80 X21 A2 200 100 X13 70 X12 90 X11 A1 产 量 B3 B2 B1 调 销地 运 量 产地 用最小元素法确定例3-2初始调运方案 150 100 100 100 100 100 100 得到初始调运方案为： x11=100，x13=100，x22=150，x23=100 最小元素法实施步骤口诀 《运价表》上找最小，《平衡表》上定产销； 满足销量划去“列”，修改“行产”要记牢； （满足产量划去“行”，修改“列销”要记牢） 划去列(行)对《运价》， 修改“行产(列销)”在《产销》； 余表再来找最小，方案很快就找到。 450 200 150 100 销 量 250 75 X23 65 X22 80 X21 A2 200 100 X13 70 X12 90