购买

¥11.0

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 4-2表上作业法

4-2表上作业法.ppt

4-2表上作业法

爱问主播
2019-03-05 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《4-2表上作业法ppt》,可适用于高等教育领域

第二节运输问题的表上作业法由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性本节将由此给出运输问题的比单纯形法更为简便的求解方法mdash表上作业法。运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法单纯形法与表上作业法的关系:()找出初始基可行解()求各非基变量的检验数()判断是否最优解运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法换基:()确定换入变量和换出变量找出新的基可行解。()重复()、()直至求出最优解。停止运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法举例说明表上作业法某部门三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表:运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法第一步:确定初始基可行解mdashmdash最小元素法、伏格尔法【】最小元素法思路:就近供应从单价中最小运价确定供应量逐步次小直至得到mn个数字格。运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法最小元素法举例运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法最小元素法得到的初始调运方案运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法练习某部门三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表:运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法最小元素法练习运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法初始调运方案最小元素法缺点:会出现顾此失彼(运费差额问题)考虑运价差运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法罚数(即差额)=次小运价最小运价【】伏格尔法思路:第一步:确定初始基可行解mdashmdash最小元素法、伏格尔法运输问题mdashmdash表上作业法*伏格尔法思路罚数(即差额)的解释:差额大则不按最小运费调运运费增加大。差额小则不按最小运费调运运费增加不大。运输问题mdashmdash表上作业法运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法结合例说明这种方法。①=第一次运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法=第一次运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法第一次运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法①第一次运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法下次不考虑该列第一次运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法第二次下次不考虑该行运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法下次不考虑该列第三次运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法下次不考虑该列第四次运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法第五次运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法例用伏格尔法得到的初始基可行解用最小元素法求出的目标函数z=一般说来伏格尔法得出的初始解的质量最好常用来作为运输问题最优解的近似解。运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法练习行罚数①第一次运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法行罚数②第二次②运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法行罚数③第三次③运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法行罚数④第四次④运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法行罚数⑤第五次⑤运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法练习题用伏格尔法得到的初始基可行解销量产量销地产地用最小元素法求出的目标函数z=运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法第二步:解的最优性检验思路:计算空格(非基变量)的检验数。两种方法:【】闭回路法每一空格出发一定存在且可以找到唯一的闭回路。【】位势法由对偶理论得检验数为。运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法【】闭回路法在给出调运方案的计算表上从每一空格出发找一条闭回路。以某空格为起点用水平或垂直线向前划当碰到一数字格时可以转度(也可以越过)后继续前进直到回到起始空格为止。运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法每一空格出发一定存在且可以找到唯一的闭回路。因mn个数字格(基变量)对应的系数向量是一个基。则任一空格(非基变量)对应的系数向量均可由这个基线性表示。运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法闭回路法的经济解释若令运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法从初始表分析:要保证产销平衡则运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法检验数表运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法或称对偶变量法【】位势法运输问题mdashmdash表上作业法*运输问题运输问题的对偶问题可写为运输问题的对偶问题mdashmdash对偶变量与原问题检验数的关系运输问题mdashmdash表上作业法*运输问题运输问题的对偶问题mdashmdash对偶变量与原问题检验数的关系运输问题mdashmdash表上作业法*运输问题设运输问题的一组基变量为运输问题的对偶问题mdashmdash对偶变量与原问题检验数的关系运输问题mdashmdash表上作业法*运输问题由于基变量的检验数为零故有运输问题的对偶问题mdashmdash对偶变量与原问题检验数的关系mn个方程mn个变量有一个自由未知量运输问题mdashmdash表上作业法*运输问题方程组有解且不唯一。求出方程组的解(称为位势)运输问题的对偶问题mdashmdash对偶变量与原问题检验数的关系运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法最小元素法得到的初始基可行解运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法销地产地存在负检验数说明不是最优解。检验数表运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法第三步:解的调整当在表中空格处出现负检验数时表示未得最优解。若有两个和两个以上的负检验数一般选其中最小的负检验数以它对应的空格为调入格。即选择最小检验数对应的非基变量为换入变量。运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法第三步:解的调整调整位置(AB)非空回路角上的格至少为空且保证数字的非负性。()()()()运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法调整后的解为:有无穷多最优解运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法几点说明:当检验数为负的变量超过两个选择最小者对应的变量换入在最优解的表中若有非基变量的检验数=则该运输问题有无穷多最优解运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法几点说明:退化一迭代过程中若某一格填数时需同时划去一行和一列此时出现退化。为保证mn个非空格需在上述的行或列中填入数字。运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法退化情况一:某部门三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表:运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法几点说明:退化二闭回路上出现两个或两个以上的具有()标记的相等的最小值。只能选一个作为调入格经调整后得退化解。则在另一数字格上填入。运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法退化情况二:闭回路法调整回路角上的格至少为空且保证数字的非负性。()()()()运输问题mdashmdash表上作业法*运输问题mdashmdash表上作业法退化情况二:只能选一个作为调入格另一个数字格填入。运输问题mdashmdash表上作业法下一节产销不平衡的运输问题产大于销产小于销运输问题mdashmdash表上作业法

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/54

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利