线
作者： 指导教师：
[摘要]本文主要对线性规划的数学模型，运输问题中产销平衡，产销不平衡问题作一简单介绍，并举出了具体实例。同时也给出了常用的几种运输问题的算法。这样从数学建立到得出实践问题的最优解，都做出了系统、完整的介绍。
[关键字]线性规划 运输问题 数学模型
线性规划在各类经济活动和生产中的应用极其广泛。多的人们所重视。尤其是近几年，线性规划无论是在深度和广度方面都取得了重大进展。本文主要介绍线性规划理论在运输问题中的应用。
一、线性规划的三种模型
在各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力，物力资源，组织生产过程，使总的经济效益最好，这样的问题常常可以化为或近似化成所谓的“线性规划”（Linear Programming，简记为有一般形式，规范形式和标准形式这三种。 1. 线性规划问题的一般形式为：
minz?c1?x1???cxxn
st. ai1x1?ai2x2???ainxn?bi,i?1,?,p,
ai1x1?ai2x2???ainxn?b,i?p?1,?n
xj?0,j?1,?p xj 0, j?q?1,?,n
其中xj, j?1, ?,n为待定的决策变量，已知的细数?a11?a1A??n????????
?am1?amn??称为约束矩阵 称c1x1?c2x2???cnxn为目标函数
第 1 页 共 14 页
其作用已为越来越 aij组成的矩阵
LP）问题，线性规划问题
记为z??cjxj, 向量c?(c1,?cn)T称为价值向量，cj(j?1,?n)
j?1n称为价值系数；向量为b?(b1,?bm)T称为右端向量，条件xj?0称为非负约束；符号xj 0 表示变量xj可取正值，负值或零值，称这样的变量为符号无限制变量或自由变量。 2. 线性规划的规范形式
在很多时候，我们往往考虑的即为LP的规范形式。
min cTx
如下： st. AX?b
x?0
3. 线性规划的标准形式
当p?m,q?n时即为LP的一般形式 min cTx
如下： st. AX?b
x?0
二、运输问题的三种情况运输问题从大的方面可分为两种类型来研究：输问题。即当总产量等于总销量时的情况；题，而供需不平衡的问题，又分为两种即产大于销的情况和产小于销的情况，所以运输问题也可分为三种情况来研究。 在产销平衡的条件下需求解运输问题就是求一组变量以下三组条件：
(1)产地Ai运出物资的总量等于(2)运输到销地B的总产量应等于?mxij?abi(i?1,2,?,n)
j?1
第LP问题的某些特殊情况，当Ai产量B2 页 共另一种就是供需不平衡的运输问
nai?xijj?1bi页
p?0,q
xij的值，使它满足ai(i?1,2,?,m)
n时，?
一种类型是供需平衡的运?的需求量即 14
(3)运输量xij须大于或等于零，即xij?0并使总的运输费用为
min:z??i?1m?j?1ncijxij
m根据上述供需平衡问题，数学模型可描述如下：minz???ncijxij
n ?xij?ai(1,2?m)
j?1m ?xij?bi(j?1,2?n)
j?1 xij?0
同样，对于产大于销的问题，数学模型为：n minz??mcijxij
i?1?j?1?mxij?bi(j?1,2?n)i?1?mxij?bi(j?1,2?n)i?1xij?0
对于产小于销的问题，数学模型为：三、三种运输问题的实例上一节给出了运输问题的三种类型，这一节对上节的三种模型分别举出一
i?1j?1 mn minz??cijxij
i?1?j?1?mxij?ai(j?1,2?m)
j?1?mxij?bi(j?1,2?n)
j?1xij?0
3 页 共 14 页
第
例.
例1某种物品先存放在两个仓库A1和A2中，再运往三个使用地B1,B2和B3，其间的距离（或单位运价）如表3—1小方格中的收据所示，各仓库的存量和使用地的需用量也都表示表3—2中，试建立使总运输量（或总运费）最小的运输问题数学模型
解：本题中的仓库相当于物品的产地，使用地即为销地。 表3—1 销 地 B2 B1 B3 产量 产 地 A1 A2 销量 3 5 6 10 4 设由A1运到B1, B2和B3的物品数量分别为x11,x12和x13,由A2运到B1,B2和
B3的物品数量分别为x21,x22和x23,则可写出其数学模型如下: minz?3x11?4x12?2x13?3x21?5x22?x12?3x23
x11?x12?x13?10 x21?x22?x23?4 x11?x21?3 x12?x23?5 x13?x23?6
x11,x12,x13,x21,x22,x12,x23?0
本题中a1?a2?b1?b2?b3,故是产销平衡的运输问题
例2 某市有三个造纸厂A1,A2,A3,其纸的产量分别为8，5和9个单位，有4个集中用户B1,B2,B3,和B4其用量分别为4,3,5和6个单位,由各造纸厂到各用户的单位运价如表3—2所示，请确定总运费最小的调用方案。
表3—2
第 4 页 共 14 页