好文档 - 专业文书写作范文服务资料分享网站

运筹学课件第三章运输问题

天下 分享 时间: 加入收藏 我要投稿 点赞

.

第三章运输问题

一、学习目的与要求

1、掌握表上作业法及其在产销平衡运输问题求解中的应用 2、掌握产销不平衡运输问题求解方法 二、课时 6学时

第一节 运输问题及其数学模型

一、运输问题的数学模型

单一品种运输问题的典型情况:设某种物品有m个产地A1,A2,…,Am,各产地的产量分别是a1,a2,…,am;有N个销地B1,B2,…,Bn,各销地地销量分别为b1,b2,…,bn。假定从产地Ai(i=1,2, …,m)向销地Bj(j=1,2,…,n)运输单位物品的运价是cij,问怎样调运这些物品才能使总运费最小?

为直观清楚起见,列出运输表: 销地 B2 … Bn 产量 B1 产地 A1

c11 x11 c12 x12 c1n x1n a1 A2 c21 x21 c22 x22 c2n x2n a2 … c11 x11 c12 x12 … c1n x1n … Am 销量 cm1 xm1 b1 cm2 Xm2 b2 cmn xmn bn am 表中xij为由产地Ai到销地Bj的物品数量,cij表示产地Ai到销地Bj的单位运价。

如果运输问题的总产量等于其总销量,即有

?a??bii?1j?1mnj

则称该运输问题为产销平衡运输问题;反之,称为产销不平衡运输问题。

产销平衡运输问题的数学模型如下:

精品

.

minz???cijxij

i?1j?1

mn?1

?n

??xij?ai

?1?jm?

s.t.??xij?bj

?i?1

?xij?0??

i?1,2,...,m

j?1,2,...,n

这就是运输问题的数学模型,它包含m×n个变量,(n十m)个约束方程.其系数矩阵的结构比较松散,且特殊。

二、运输问题数学模型的特点

1、运输问题有有限最优解,即必有最优基本可行解 2、运输问题约束条件的系数矩阵A的秩为(m+n-1)

该系数矩陈中对应于变量xij的系数向量pij,其分量中除第i个和第m十j个为1以外,其余的都为零.即 Aij=(0…1…1…0)’=ei+em+j

对产销平衡的运输问题具有以下特点: (1)约束条件系数矩阵的元素等于0或1

(2)约束条件系数矩阵的每一列有两个非零元素,对应于每一个变量在前m个约束方程中出现一次,在后n个约束方程中也出现一次。

此外,对于产销平衡问题,还有以下特点 (3)所有结构约束条件都是等式约束 (4)各产地产量之和等于各销地销量之和

精品

.

第二节 用表上作业法求解运输问题

解题步骤

第1步:确定初始基本可行解。

第2步:最优性判别,若最优准则σij≥0,则当前解最优,计算停止,否则转第3步。 第3步:取一个检验数最小的非基变量做进基变量。 第4步:调整当前基本可行解,转第2步

一、确定初始基本可行解(初始调运方案) 以实例介绍:

例 某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售,各工厂的生产量、各销点的销售量(假定产位均为t)以及各工厂到各销售点的单位运价(元/t)于下表中,要求研究产品如何调运才能使总运费最小? 销地 产地 A1 A2 A3 销量

A最小元素法

销地 产地 A1 A2 A3 销量 3B1 4 B2 12 2 8 14 5 10 B3 4 3 11 12 B4 11 9 6 14 产量 16 10 8 22 B1 B2 4 2 8 14 14 ijB3 12 10 5 10 2 12 11 3 4 B4 11 6 9 6 8 14 产量 16 10 22 8 8 总运费(目标函数):z?m+n-1=3+4-1=6)。 B 西北角法

销地 产地 A1 ??ci?1j?14xij?246这个解满足约束条件,其非零变量的个数为6(等于

B1 8 4 B2 12 8 精品

B3 4 B4 11 产量 16

运筹学课件第三章运输问题

.第三章运输问题一、学习目的与要求1、掌握表上作业法及其在产销平衡运输问题求解中的应用2、掌握产销不平衡运输问题求解方法二、课时6学时第一节运输问题及其数学模型一、运输问题的数学模型单一品种运输问题的典型情况:设某种物品有m个产地A1,A2,…,Am,各产
推荐度:
点击下载文档文档为doc格式
6f27o5jxug0ne2d1fovz9epjx24qwd012tg
领取福利

微信扫码领取福利

微信扫码分享