www.806.net

为调解量; ij+
日期:2019-09-20    访问量:

  运输问题求解之表上功课法1.运输问题模子及其求解思 2.确定初始根基可行解 3.最优性查验 4.方案调整 1.运输问题模子及其求解思 运输问题: 研究把某种商品从若干个产地运至若 干个发卖地而使总运费最小的一类 问题。 方针: 总运费最小1.运输问题模子及其求解思 销地 产地 供应某种物资,其供应量(产量)别离为ai ,有n个销地Bj (j=1,2, 个发卖地的调运量,正在产销均衡的前提下( ),要确定总运输费用最小的调 运方案,可暗示为如下的数学模子 ij s.t.(i=1,2,…,m; j=1,2,…,n) 矩阵形式: CX s.t.1.运输问题模子及其求解思 1.运输问题模子及其求解思系数矩阵A 1.运输问题模子及其求解思对于产销均衡的运输问题, 若产地为m个,销地为n个, 变量个数为mn个,,束缚前提个数为m+n, 此中包含:总产量=总发卖 故线性无关的束缚前提个数为m+n-1, 根基解中的基变量个数为m+n-1。 运输问题求解思——表上功课法 因为运输规划系数矩阵的特殊性,若是间接利用线 性规划纯真形法求解计较,则无法操纵这些有益条 人们正在阐发运输规划系数矩阵特征的根本上成立了针对运输问题的表上功课法。 1.运输问题模子及其求解思 表上功课法是纯真形法正在求解产销均衡的运输问题时的一 种简化方式,其本色仍是纯真形法,所分歧的只是完成各 步采用的具体形式。 具体操做步调如下: (1)确定一个初始根基可行解:即正在mn阶产销均衡 表上给出m+n-1个数字格(基变量); (2)求各非基变量(空格)的查验数,即正在表上 计较空格的查验数。判别式否达到最优解。若是是最优解, 则遏制计较,不然进入下一步。 (3)确定换入变量和换出变量,找出新的基可行解。 (4)反复(2)、(3)曲至获得最优解为止。 1.运输问题模子及其求解思 2.确定初始根基可行解 1)最小元素法 根基思惟: 就近供应,按运价最小的优先调运准绳确 定初始方案,即从单元运价表当选择运价 最小的起头确定调运关系,然后次小。若 某行(列)的产量(销量)已满脚,则把 该行(列)的其他格划去。如斯进行下去, 一曲到给出初始基可行解为止。 例如,某公司运营某种产物,该公司下设A、B、C三个 出产厂,有甲、乙、丙、丁四个发卖点。公司每天把三个 工场出产的产物别离运往四个发卖点,各工场到各发卖点 的程分歧,单元产物的运费分歧。各工场每日的产量、 各发卖点每日的销量,以及从各工场到各发卖点单元产物 的运价如下表。问该公司若何调运产物,正在满脚各发卖点 需要的前提下,使总运费最小。 2.确定初始根基可行解34 33 32 31 24 23 22 21 14 13 12 11 3424 14 33 23 13 32 22 12 31 21 11 34 33 32 31 24 23 22 21 14 13 12 11 s.t2.确定初始根基可行解 ij 2.确定初始根基可行解Z=43+310+31+12+64+35=86 为基变量的个数有m+n-1个, 1、每次填完数,只能划去一行或一列,只 有最初一个格子破例。 2、用最小元素法时,可能会呈现基变量个 数还差两个以上但只剩下一行或一列的情 况,此时不克不及将剩下行或列按空格划掉, 应正在剩下的空格中标上0。(退化的根基可 2.确定初始根基可行解留意: 伏格尔法的根基思惟:若是某一地的产物不克不及按最小运费就近供应,就考虑次小运费,两者间就有一个差额。差额 越大,申明费用增量越大。因此对差额最大处,优先采用 最小运费调运。 步调: 别离计较表中各行和各列中最小运费和次小运费的差 额,并填入表中的最左列和最下行。 从行和列的差额当选出最大者,选择其所外行或列中的 最小元素,按雷同于最小元素法优先供应,划去响应的行 对表中未划去的元素,反复,曲到所有的行和列都划完为止。 2.确定初始根基可行解 两最小元素之差2.确定初始根基可行解 2.确定初始根基可行解Z=53+210+31+18+64+35=85 3.最优性查验 查验数的意义:非基变量添加一个单元, 使方针函数值添加的数量。 运输问题中方针函数值要求最小化,因而, 当所有的查验数都大于或等于零时该调运 方案就是最优方案;不然不是。 下面引见两种计较查验数的方式: 1、闭回法 闭回:正在已给出根基解的运输表上,从一个非基 变量出发,沿程度或竖曲标的目的前进,只要碰着基变 量,才能向左或向左转90 (当然也能够不改变标的目的)继续前进。 如许继续下去,总能回到出发的阿谁非基变量,由 此线,则总运费变化:7–5+10–3+2-1=10 31=10 3.最优性查验 最优尺度:所有查验数ij 2、位势法闭回法的错误谬误:当变量个数较多时,寻找闭回以及计较 两方面都容易犯错。 位势法查验步调: 1)设产地A ),操纵对基变量而言有ij =0,计较位 3)再由ij )计较非基变量的查验数ij 3.最优性查验 u1u2 u3 v1 v2 v3 v4 -1-5 24=-1 12=2当存正在非基变量的查验数 ij 0,申明现行方案为最优方案,不然方针 成本还能够进一步减小。 3.最优性查验 1、闭回法计较式: (闭回上的偶数极点运价之和) 2、位势法计较式: 当存正在非基变量的查验数ij 0,申明现行方案为最优方案,不然方针成本还 能够进一步减小。 4.方案调整 闭回调整法步调: 1、入基变量简直定:选负查验数中最小者 rk rk做为进基变量;(使总运费尽快削减) 2、出基变量简直定:正在进基变量x rk 的闭回上, 拔取偶数极点上调运量最小的值,将其对应的运量 做为出基变量。(刚好有一个基变量出基,其它基 变量都为正) 4.方案调整 即求=Min{xij 闭回上的偶数极点的x ij pq。那么 确定x pq 为出基变量,为调整量; ij+,对各偶数极点运量调整为:x ij -,出格x pq pq变为非基变量。 10(12) 最小查验数准绳,确定进基变量 最小偶点准绳,确定出基变 量和调整量 +1 -1 +1 -1 minmin 14 (12)四、方案调整 颠末一次基变换,所有 ij 0,已获得最优解:x13 3,其它为0。最优值: 85表上功课法计较中的相关问题 1.无限多最优解 当最优方案中存正在某空格(非基变量)查验数为0,时,则 该运输问题必然有多沉最优解。 2.退化解 当运输问题的最优表中无数格(基变量)的运量为0,则 呈现退化。 1)确定根基可行解中,呈现同时需要划去一行和一列的 环境,则需要正在填写数格的行或列上,写上一个0数格。 2)正在闭回中进行调整时,好像时有t(t

  运筹学表上功课法图文[讲授],运筹学表上功课法,运筹学表上功课法视频,运筹学功课法求解,运筹学讲授视频,运筹学大功课,运筹学讲授纲领,办理运筹学视频讲授,胡运权运筹学讲授视频,运筹学功课

  1)个最小数 格时,则只要一个运量为0的数格必需出基,其余的必需 补上(t-1)个0数格。 产销不均衡运输问题 当产大于销: s.t.(i=1,2,…,m; j=1,2,…,n) s.t.(i=1,2,…,m; j=1,2,…,n+1) ij 产销不均衡运输问题销地 产地 300销量 150 150 200 销地 产地 (虚销地)产量 300销量 150 150 200 100 产销不均衡运输问题 当产小于销: s.t.(i=1,2,…,m; j=1,2,…,n) s.t.(i=1,2,…,m+1; j=1,2,…,n) ij 产销不均衡运输问题销地 产地 300销量 250 200 200 销地 产地 150销量量PPT模板免费下载



友情链接:

Copyright 2019-2022 http://www.szqsly.com.cn 版权所有 未经协议授权禁止转载