题目:线性规划在运输中的运用 下载本文

线

作者: 指导教师:

[摘要]本文主要对线性规划的数学模型,运输问题中产销平衡,产销不平衡问题作一简单介绍,并举出了具体实例。同时也给出了常用的几种运输问题的算法。这样从数学建立到得出实践问题的最优解,都做出了系统、完整的介绍。

[关键字]线性规划 运输问题 数学模型

线性规划在各类经济活动和生产中的应用极其广泛。多的人们所重视。尤其是近几年,线性规划无论是在深度和广度方面都取得了重大进展。本文主要介绍线性规划理论在运输问题中的应用。

一、线性规划的三种模型

在各类经济活动中,经常遇到这样的问题:在生产条件不变的情况下,如何通过统筹安排,改进生产组织或计划,合理安排人力,物力资源,组织生产过程,使总的经济效益最好,这样的问题常常可以化为或近似化成所谓的“线性规划”(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 页