运筹学教学课件-第三章运输问题.pptx

1第三章运输问题

运输问题与有关概念运输问题的求解—表上作业法运输问题应用—建模本章内容重点

1.运输问题模型及有关概念2问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。

1.运输问题模型及有关概念3例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？

1.运输问题模型及有关概念4解：产销平衡问题：01总产量=总销量02设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：03

MinZ=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）1.运输问题模型及有关概念

系数矩阵1.运输问题模型及有关概念61100000100010011001000111

模型系数矩阵特征1.运输问题模型及有关概念7共有m+n行，分别表示各产地和销地；m?n列，分别表示各决策变量；每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。0102

1.运输问题模型及有关概念8一般运输问题的线性规划模型及求解思路一般运输问题的提法：假设A1,A2,…,Am表示某物资的m个产地；B1,B2,…,Bn表示某物资的n个销地；ai表示产地Ai的产量；bj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价（表4-3）。如果a1+a2+…+am=b1+b2+…+bn则称该运输问题为产销平衡问题；否则，称产销不平衡。首先讨论产销平衡问题。

1.运输问题模型及有关概念9表4-3运输问题数据表销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmna1a2┇am销量b1b2…bn?设xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可以建立运输变量表（表4-4）。

1.运输问题模型及有关概念10表4-4运输问题变量表销地产地B1B2…Bn产量A1A2┇Amx11x12…x1nx21x22…x2n┇┇┇┇xm1xm2…xmna1a2┇am销量b1b2…bn?

1.运输问题模型及有关概念11mnMinZ=??cijxij（4-1）i=1j=1ns.t.?xij?aii=1,2,…,m（4-2）j=1m?xij?(=,?)bjj=1,2,…,n（4-3）i=1xij?0(i=1,2,…,m;j=1,2,…,n)（4-4）于是得到下列一般运输问题的模型：在模型（4-1）—（4-4）中，式（4-2）为m个产地的产量约束；式（4-3）为n个销地的销量约束。

1.运输问题模型及有关概念12mnMinZ=??cijxiji=1j=1ns.t.?xij=aii=1,2,…,m(4-5)j=1m