重庆文理学院 数学与财经 统计学 石艳泓 QQ：593982714 电话：18716350620第 1 页 共 9 页管理运筹学论文-产销不平衡运输问题姓名：石艳泓 学号：201002054030 班级：10 级统计摘要：运输问题是运筹学中的一个重要问题，也是物流系统优化中常见的问题，同时也是一种特殊的线性规划问题。怎么样尽可能的在产地与销地之间减少运输成本和降低运输费用是很多运输公司热切关注的话题。本文涉及的是一个总产量大于总销量的产销不平衡运输问题，通过对产地与销售地车辆运输的建立模型，在运用表上作业迭代法（最小元素法）求解后，再根据模型用 lingo 软件编写程序进行求解。然后对结果进行分析，以及运输问题的延伸。最后证明用 lingo 解决车辆运输的可行性。关键字：运输问题，产销不平衡，表上作业法， lingo 模型问题提出：重庆有三家电子厂分别是新普，隆宇和恒华，生产的笔记本电脑将要运向北京，天津，广东，上海四个城市销售，其产量和销售量见下表：（单位：万台）表：1-1北京 天津 广东 上海 产量新普 6 2 6 7 30隆宇 4 9 5 3 25恒华 8 8 1 5 21销量 15 17 22 12 -问：哪种销售方案将会取得最少的运输费用，费用为多少？问题分析：图表数据显示产量总和为 30+25+21=76 万台，销量的总和为15+17+22+12=66 万台，说明了此问题是一个总产量大于总销量的运输问题（7666）。该问题一方面要求满足北京，天津，广东，上海四个销售地的供货需求，而另一方面又要考虑新普，隆宇和恒华三个产地的运往销售地的运输费用，此外问题不但要求满足销售地分配要足，同时也要保证最大化的减少运输费用。这里选择何种分配方案，将涉及不同的运输费用，所以其是一个典型的线性规划问题，同时也是一个总产量大于总销量的产销不平衡运输问题。重庆文理学院 数学与财经 统计学 石艳泓 QQ：593982714 电话：18716350620第 2 页 共 9 页根据题目已知可以得出以下图论：新普隆宇恒华北京天津广东上海模型建立：假设某物品有 m 个产地 A1、A 2、 Am，各产地的产量是a1、a 2、a m；有 n 个销地 B1、B 2、B n，各销售地销量分别为b1、b 2、b n；假定从产地 Ai（i=1,2，m）向销售地Bj（j=1，2，n）运价单位物品的运价是 cij，问这样调运这些物品才能使运费最少？ 设 xij 为从产地 Ai 运往销地 Bj 的运输量，若各产地产量之和大于各销地销量之和，即有： njjmiiba11则得到下列产销平衡运输量问题的模型： 0,.21,.,in111ijjmiijijijminjijxnbxaxcz其中，约束条件右侧常数 ai 和 bj，约束条件最多有 m+n-1 个有效，即最多有m+n-1 个基可行解。为了能使用表上作业法，可增加一个假想的销地虚销地 Bn+1而由产地重庆文理学院 数学与财经 统计学 石艳泓 QQ：593982714 电话：18716350620第 3 页 共 9 页Ai（i=1,2，m）调运到这个假想销地的物品数量的销量 Xi，n+1 （相当于松弛变量） ，实际上就地储存在 Ai。因为就地储存没有运输，故单价为Ci，n+1 =0， （i=1,2，m）令假想销地的销量为： njjmiinbab11从而数学模型： 0,.21,.,in111ijjmiijijijminjijxnbxaxcz基本假设：针对该运输问题，为了方便计算，可以设新普（A1），隆宇（A2）和恒华（A3）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为x11、x12、x13、x14、x21、x22、x23、x24、x31、x32、x33、x34。建立以下模型：表：1-2B1 B2 B3 B4 产量A1 6 2 6 7 30A2 4 9 5 3 25A3 8 8 1 5 21销量 15 17 22 12 -目标（The objective）最少费用：重庆文理学院 数学与财经 统计学 石艳泓 QQ：593982714 电话：18716350620第 4 页 共 9 页3432312423 231 211411214 5x8xx5 9x766zMin ijjic约束条件：供应限制（The supply constrains）21xx53034321214312指标约束（The damand constrains）12x x7 534241432211定义符号说明：A1、A2、A3 分别代表新普，隆宇和恒华生产商；B1、B2、B3、B4 分别代表北京，天津，广东，上海销售地。x11、x12、x13、x14、x21、x22、x23、x24、x31、x32、x33、x34 为新普、隆宇和恒华分别销往北京、天津、广东和上海四个城市销售量。Cij 为从产地Ai（i=1,2，m）向销售地 Bj（j=1，2，n）运价单位物品的运价， xij 为从产地 Ai（i=1,2，m）运往销地 Bj（j=1，2，n）的运输量。Z 即为整个运输过程中涉及的运输费用。Min z 则为该运输问题中的最小费用。表上作业法（最小元素法）：最小元素法：是找出运价表中最小的元素，然后在运量表内对应的格填入允许取得的最大数值，若某行或者某列的产量或者销量已得到满足，则把运价表中该运价所在行或者列划去；找出未划去的运价中的最小数值，按此办法依次进行下去，直至得到一个基本可行解的方法。表上作业法：是求解运输问题的一种简便而有效的方法，求解过程在运输表上进行行，这是一种迭代求解法，迭代步骤为：步骤一：按某种规则找出一个初始基可行解。重庆文理学院 数学与财经 统计学 石艳泓 QQ：593982714 电话：18716350620第 5 页 共 9 页步骤二：对进行解作最有判断，即求个非基变量的检验数，判别是否达到最优解。如果已经是最优解，则停止计算；如果不是最优解，则进行下一步骤。步骤三：在表上对初始方案进行改进，找出新的基可行解，再按照步骤二进行判别，直至找出最优解。表上作业法具体求解如下：表：1-3：-12221715销量21501218080A3253125090413A2172 30706126A1产量B4B3B2B1步骤一：从表 1-2 中找出最小运价为 1，故首先考虑此项，由于 A3 产地产量小于 B3 销量（2117），故在表 1-3 的（A1，B2）交叉格填上 17，由于 B2 销量已经饱和，故划去表 1-4 中的 B2 列得表 1-5。表：1-5B1 B3 B4A1 6 6 7A2 4 5 3步骤三：从表 1-5 中找出最小运价为 3，故首先考虑此项，由于 A2 产地产量大于 B4 销量（2512），故在表 1-3 的（A2，B4）交叉格填上 12，由于 B4 销量重庆文理学院 数学与财经 统计学 石艳泓 QQ：593982714 电话：18716350620第 6 页 共 9 页已经饱和，故划去表 1-5 中的 B2 列得表 1-6。表：1-6B1 B3A1 6 6A2 4 5步骤四：从表 1-6 中找出最小运价为 4，故首先考虑此项，由于 A2 产地剩余产量小于 B1 销量（25-12=1315-13=2），故在表 1-3 的（A1，B1）交叉格填上 2，由于 B1 销量已经饱和，故划去表 1-5中的 B2 列。步骤六：由于 B3 销地为达到饱和，故在（A1，B3）交叉格填上 1，然后在其它空格位置统一填上 0。经以上步骤得到一个总产量大于总销量，且销量全部满足的调配方案。经过计算，空格的检验数均大于零，最优方案为： 0x2113172 ij3242311 ， 其 它， xxxx最小费用为： 314 16676ijjixczlingo 求解模型：LINGO模型：model:sets:origin/1.3/:a;sale/1.4/:b;重庆文理学院 数学与财经 统计学 石艳泓 QQ：593982714 电话：18716350620第 7 页 共 9 页routes(origin,sale):c,x;endsetsdata:a=30,25,21;b=15,17,22,12;c=6,2,6,7,4,9,5,3,8,8,1,5;enddataOBJmin=sum(routes:c*x);for(origin(i):SUPsum(sale(j):x(i,j)=a(i);for(sale(j):DEMsum(origin(i):x(i,j)=b(j);endlingo结果：Global optimal solution found.Objective value: 161.0000Infeasibilities: 0.000000Total solver iterations: 6Variable Value Reduced CostX( 1, 1) 2.000000 0.000000X( 1, 2) 17.00000 0.000000X( 1, 3) 1.000000 0.000000X( 1, 4) 0.000000 2.000000X( 2, 1) 13.00000 0.000000X( 2, 2) 0.000000 9.000000X( 2, 3) 0.000000 1.000000X( 2, 4) 12.00000 0.000000X( 3, 1) 0.000000 7.000000重庆文理学院 数学与财经 统计学 石艳泓 QQ：593982714 电话：18716350620第 8 页 共 9 页X( 3, 2) 0.000000 11.00000X( 3, 3) 21.00000 0.000000X( 3, 4) 0.000000 5.000000Row Slack or Surplus Dual PriceOBJ 161.0000 -1.000000SUP( 1) 10.00000 0.000000SUP( 2) 0.000000 2.000000SUP( 3) 0.000000 5.000000DEM( 1) 0.000000 -6.000000DEM( 2) 0.000000 -2.000000DEM( 3) 0.000000 -6.000000DEM( 4) 0.000000