案例钢铁配矿问题教学用运输_第1页
案例钢铁配矿问题教学用运输_第2页
案例钢铁配矿问题教学用运输_第3页
案例钢铁配矿问题教学用运输_第4页
案例钢铁配矿问题教学用运输_第5页
已阅读5页,还剩42页未读, 继续免费阅读

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2024/1/27管理运筹学课程组391本章重点第三章运输问题

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

产销平衡运输问题的表上作业法

本章内容运输问题的数学模型表上作业法运输问题的扩展2024/1/27管理运筹学课程组392§1运输问题的数学模型bn…b2b1需求量Bn…B2B1

需方供方AmA2A1ama2a1供应量供需平衡运价2024/1/27管理运筹学课程组393§1运输问题的数学模型bn…b2b1需求量BnB2B1

需方供方AmA2A1ama2a1供应量cmncm2cm1c2nc22c21c1nc12c11…………如何建立供需搭配,使总的运输费用最小?供需平衡表2024/1/27管理运筹学课程组394平衡表、运价表和二为一:2024/1/27管理运筹学课程组395数学模型设从Ai到Bj的物资运量为xij,产销平衡运输问题的数学模型。Ai的产品全部供应出去Bj的需求全部得到满足2024/1/27管理运筹学课程组396

例3.1

某公司经销甲产品。它下设三个加工厂。每日的产量分别为:A1--7吨,A2--4吨,A3--9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为:B1--3吨,B2--6吨,B3--5吨,B4--6吨。已知从各工厂到各销售点的单位产品的运价为表所示。问该公司应如何调运产品,在满足各销售点的需要量的前提下,使总运费为最少。解先画出这问题的产销平衡表和单位运价表,

B1B2B3B4产量/tA13113107A219284A3741059销量/t3656销地运费产地2024/1/27管理运筹学课程组3971.决策变量xij表示第i产地运到第j个销地的产品数量2.目标函数z为总费用3.约束条件2024/1/27管理运筹学课程组398运输问题有有限最优解对于运输问题的模型,若令其变量则上述模型就是运输问题模型的一个可行解,运输问题的目标函数有下界,目标函数值不会趋于负无穷大,因此,运输问题必存在有限最优解。2024/1/27管理运筹学课程组399mn运输问题约束条件的系数矩阵2024/1/27管理运筹学课程组3910约束条件或解可用产销平衡表表示:2024/1/27管理运筹学课程组3911

ui‚vj无约束(i=1,2,…,m;j=1,2,…,n)uivj设ui,vj为对偶变量,对偶问题模型为m个n个2024/1/27管理运筹学课程组3912约束条件系数矩阵的元素等于0或1约束条件系数矩阵的每一列有两个非零元素,这对应于每一个变量在前m个约束方程中出现一次,在后n个约束方程中也出现一次。对产销平衡运输问题,除上述两个特点外,还有以下特点:所有约束条件都是等式约束;各产地产量之和等于各销地销量之和。运输问题的特点2024/1/27管理运筹学课程组3913根据运输问题的数学模型求出的运输问题的解,代表着一个运输方案,其中每一个变量的值表示由调运数量为物品给。前已指出运输问题是一种线性规划问题,可设想用迭代法进行求解,即先找出它的某一个基可行解,再进行解的最优性检验,若它不是最优解,就进行迭代调整,以得到一个新的更好的解,继续检验和调整改进,直至得到最优解为止。运输问题的解2024/1/27管理运筹学课程组3914为了能按上述思路求解运输问题,要求每步得到的解都必须是基可行解,这意味着:(l)解必须满足模型中的所有约束条件;(2)基变量对应的约束方程组的系数列向量线性无关;(3)解中非零变量的个数不能大于个,原因是运输问题中虽有个结构约束条件,但由于总产量等于总销量,故只有个约束条件是线性独立的;(4)为使迭代顺利进行,基变量的个数在迭代过程中保持为个。2024/1/27管理运筹学课程组3915§2表上作业法计算步骤:(1)找出初始调运方案。即在(m×n)产销平衡表上给出m+n-1个数字格。(最小元素法或差值法)(2)求检验数。(闭回路法或位势法)判别是否达到最优解。如已是最优解,则停止计算,否则转到下一步。(3)对方案进行改善,找出新的调运方案。(表上闭回路法调整)确定m+n-1个基变量

(4)重复(2)、(3),直到求得最优调运方案。空格2024/1/27管理运筹学课程组3916

例运输问题供需平衡表和运价表如下,求最优调运方案。

供需B1B2B3B4供应量(T)A13113107A219284A3741059需求量(T)36562024/1/27管理运筹学课程组3917基本思想:应优先考虑单位运价最小(或运距最短)的供销业务,最大限度地满足其供销量。即对所有i和j找出,的物品量由Ai0供应给Bj0.若xi0j0

=ai0,则产地Ai0的可供物品已用完,以后不再继续考虑这个产地,且Bj0的需求量由bj0减少为bj0-ai0;如果xi0j0

=bj0

,则销地Bj0的需求已全部得到满足,以后不再考虑这个销地,且Ai0的可供量由ai0减少为aj0-bi0

。然后,在余下的供、销点的供销关系中,继续按上述方法安排调运,直至安排完所有供销任务,得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。1最小元素法2024/1/27管理运筹学课程组3918314

633Z=4×3+3×10+3×1+1×2+6×4+3×5=86该方案总运费:2024/1/27管理运筹学课程组3919例3.2某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售,各工厂的生产量、各销售点的销售量(单位为吨)以及各工厂到各销售点的单位运价(元/吨)示于表中。问:要求产品如何调运才能使总运费最小?2024/1/27管理运筹学课程组3920解:由于总产量和总销量均为48,故知这是一个产销平衡运输问题。最小费用法的初始分配方案如下表所示

总运费(目标函数值)z=10×4十6×ll十8×2十2×3十14×5十8×6=246

这个解满足所有约束条件,其非零变量的个数为6(等于m+n-1=3+4-1=6)不难验证,这6个非零变量(基变量)对应的约束条件系数列向量线性无关。

2024/1/27管理运筹学课程组3921基本思想:首先计算运输表中每一行和每一列的次小单位运价和最小单位运价之间的差值,并分别称之为行罚数和列罚数。将算出的行罚数填入位于运输表右侧行罚数栏的左边第一列的相应格子中,列罚数填入位于运输表下边列罚数栏的第一行的相应格子中,见下表。在这些罚数中,确定最大者,对应的运输格优先填入尽可能大的运量,同最小元素法一样,划去相应的行或列。在尚未划去的各行和各列中如上重新计算各行罚数和列罚数,并分别填入行罚数栏,用上述方法继续作下去,依次算出每次迭代的行罚数和列罚数,根据其最大罚数值的位置在运输表中的适当格中填入一个尽可能大的运输量,并划去对应的一行或一列。用这种方法可以得到一个初始基可行解。2.伏格尔法2024/1/27管理运筹学课程组3922.

分别计算各行、各列次小、最小运价的差额,优先在最大差额处进行供需搭配。步骤:10计算未划去行、列的差额;20

找出最大差额对应的最小元素cij进行供需分配;30

在未被划去的行、列重新计算差额。2024/1/27管理运筹学课程组3923

销产B1B2B3B4供量A17A24A39销量

3656

6B1B2B3B4行差额A13113100A219281A3741051列差额25132024/1/27管理运筹学课程组3924

销产B1B2B3B4供量A17A24A3

9销量

3656

6B1B2B3B4行差额A13113100A219281A3741052列差额21332024/1/27管理运筹学课程组3925

销产B1B2B3B4供量A17A24A3

9销量

3656

6B1B2B3B4行差额A13113100A219281A374105列差额212332024/1/27管理运筹学课程组3926

销产B1B2B3B4供量A17A24A3

39销量

3656

6B1B2B3B4差额A13113107A219286A374105差额12

35122024/1/27管理运筹学课程组3927以3.2为例,用伏格尔法给出初始调运方案的过程如下表第一步:在上表中分别计算出各行和各列的最小运费和次最小运费的差额,并填入该表的最右列和最下行第二步:从行或列差额中选出最大者,选择它所在行或列的最小元素。在上表中B2列差额最大为5。在该列最小元素位置填上产销量的最小值14,然后将运价表中的B2列数字划去;运价表中划去B2列数字后重新计算行或列差额,形成第二列和行的罚数,进入下一步,如表所示第三步:对表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额,并填入该表的最右列和最下行,重复第一、二步,直到给出初始解为止伏尔加法与最小元素法除在确定供求关系原则上不同外,其余步骤相同,伏尔加法给出的初始解比用最小元素法给出的初始解更接近最优解。目标函数值z=12×4十8×2十2×9十14×5十8×6=2442024/1/27管理运筹学课程组3928用伏尔加法给出例3.1的初始解如下表此初始解即为最优解,总费用为z=5*3+2*10+3*1+1*8+6*4+3*5=85(元)

一般说来,沃格尔法得出的初始解的质量最好,常用来作为运输问题最优解的近似解,最小元素法解的目标函数值比较大。

2024/1/27管理运筹学课程组3929最优解的判别(检验数的求法)①闭回路法要判别运输问题的某个解是否为最优解,可仿照一般单纯形法,检验这个解的各非基变量(对应于运输表中的空格)的检验数,若有某空格的检验数为负,说明将其变成基变量将使运输费用减少,故当前这个解不是最优解。若所有空格的检验数全为非负,则不管怎样变换,解均不能使运输费用降低,即目标函数值已无法改进,这个解就是最优解。

2024/1/27管理运筹学课程组3930

闭回路:从空格出发顺时针(或逆时针)画水(或垂直)直线,遇到填有运量的方格可转90°,然后继续前进,直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。

销产B1B2B3B4供量A1527A2314A36

39销量

36562024/1/27管理运筹学课程组3931

闭回路:从空格出发顺时针(或逆时针)画水平(或垂直)直线,遇到填有运量的方格可转90°,然后继续前进,直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。

销产B1B2B3B4供量A1527A2314A36

39销量

36562024/1/27管理运筹学课程组3932314

633最小元素法+-+-

x11为换入变量,x11增加1,运费的变化为3-1+2-3=1。这个变化就是x11的检验数,故

11=12024/1/27管理运筹学课程组3933

从每一空格出发一定存在和可以找到唯一的闭回路。因(m+n-1)个数字格(基变量)对应的系数向量是一个基.任一空格(非基变量)对应的系数向量是这个基的线形组合.如Pij,(i,j∈N

)可表示为而这些向量构成了闭回路。空格(i,j)对应非基变量xij,其检验数(闭回路上奇数次顶点的运价之和)-(闭回路上偶数次顶点的运价之和)2024/1/27管理运筹学课程组3934闭回路法计算检验数的经济解释为:在已给出初始解的表3-8中,可从任一空格出发,如(A1,B1),若让A1的产品调运1吨给B1。为了保持产品平衡,就要依次作调整:在(A1,B3)处减少1吨,(A2,B3)处增加1吨,(A1,B3)处减少1吨,即构成了以(A1,B1)空格为起点,其它为数字格的闭回路,如表3-8中折线所示。在这表中闭回路各顶点所在格的右上角数字是单位运价。检验数通常可用等数字表示,正的检验数可简记为-5+2024/1/27管理运筹学课程组3935

基变量的检验数为零(

基变量xij),

ij=cij-(ui+vj),ui,vj自由变量②.位势法

标准型运输问题的对偶问题是:

XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y检验数

得m+n-1个方程,令某个ui

(或vj)=0,可解出m+n个ui

和vj;由此得非基变量的检验数。对偶变量值等于原问题的检验数松弛变量2024/1/27管理运筹学课程组393601122024/1/27管理运筹学课程组393701128-37位势表2989-3-2检验数2024/1/27管理运筹学课程组393801128-37检验数表121-11012

24=-1<0,当前方案不是最优方案。2024/1/27管理运筹学课程组3939闭回路调整法改进方案pqijj,i)(min

=<0xpq为换入变量

从(p,q)空格开始画闭回路,其它转角点都是填有运量的方格,并从(p,q)空格开始给闭回路上的点按+1,-1,+1,-1编号,-1格的最小运量为调整量。换出变量运量表3-102024/1/27管理运筹学课程组3940

新的调运方案为:2024/1/27管理运筹学课程组3941得到的一个解2024/1/27管理运筹学课程组3942

需供B1B2B3B4uiA10210A2218A39125Vj

-7-1-70713491110231085对应上述解的非基变量检验数2024/1/27管理运筹学课程组3943表上作业法中的问题(1)无穷多最优解在前面提到,产销平衡的运输问题必定存在最优解。那么有唯一最优解还是无穷多最优解?依线性规划单纯性最优解判别标准,即某个非基变量(空格)的检验数为0时,该问题有无穷多最优解。表3-10空格(1,1)的检验数是0,表明例3.1有无穷多最优解。可在表4-12中以(1,1)为调入格,作闭回路(1,1)+-(1,4)--(2,4)+-(2,1)--(1,1)+。确定

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论