一、平衡运输问题及其表上作业法
- 平衡问题及数学建模
平衡运输问题： 就是生产数量与销售数量相等的运输问题。对总产量等于总需求量的运输问题，可直接采用表上作业法求最优运输方案
数学模型：
2、表上作业法
表上作业法步骤：
1：求解初始可行解(最小元素法、西北角法)
2：位势法求非基变量的检验数(当所有检验数>=0时，为最优解)
3：若检验数不满足时，找出负检验数中最小的格子，用闭回路法调整得到更优的基变量
4：重复2和3 直到得到最优解
运输问题如下例题1:有3个产地,4 个销地的运输规划问题 , 表格中的内容是某产地运往某销地的运费
| 产地 销地 |
B1 |
B2 |
B3 |
B4 |
产量 |
| A1 |
3 |
11 |
3 |
10 |
7 |
| A2 |
1 |
9 |
2 |
8 |
4 |
| A3 |
7 |
4 |
10 |
5 |
9 |
| 销量 |
3 |
6 |
5 |
6 |
目标函数：minz=3X11+11X12+3X13+10X14+1X21+9X22+2X23+8X24+7X31+4X32+10X33+5X34
最小元素法：从单位运价表中逐次挑选最小的元素，然后划去满足销量或者产量的行或者列，确定初始可行解
第1个基变量
第2个基变量
第3个基变量
第4个基变量
第5个基变量
第6个基变量
直到所有的行列全部划掉 , 所有的产销全部安排完毕 ，此时找到的解就是运输问题的初始可行解
######################
最优解判别 : 得到一组 基可行解 之后 , 使用 检验数 判定该解是否是最优解 ;
检验数判定原则 : 运输规划的 目标函数求最小值 时 , 所有的 非基变量检验数 λij λij 都非负 , 该基可行解就是最优解 , 该运输方案是最优方案 ;
求检验数的方法 : ① 位势法
计算出的非基变量 检验数使用蓝色括号字体 红色字体为基变量对应的运量
上述检验数中σ24 为负数 , 需要进行换基 , 该非基变量就是入基变量 ;
该检验数的闭合回路中在 − 符号的基变量中挑选一个最小的 , 作为出基变量 ;
重新计算检验数验证>=0 , 即为最优解
二、指派问题及数学模型
有n项任务需要均分给n个人完成，工人i完成任务j的成本为cij，确定人和任务之间 一一对应的一个分配方案，使得总成本最小。
Cij的取值为0或者1(表示安排第i人完成第j项任务，且每个人完成一项任务、每项任务由一人完成)
匈牙利解法步骤
| 人员 任务 |
A |
B |
C |
D |
| 甲 |
7 |
16 |
9 |
11 |
| 乙 |
6 |
11 |
10 |
5 |
| 丙 |
18 |
12 |
10 |
11 |
| 丁 |
12 |
13 |
14 |
8 |
1：变化效率矩阵，使每行每列至少有一个0
行变化：找每行最小的元素，从该行各元素减去
列变化：找出每列最小元素，从该列各元素减去
文章来源地址https://www.toymoban.com/news/detail-424375.html
2：找出独立0元素，行有独立划掉列，列有独立划掉行
3：独立0的个数若小于n,则转2、3、4，否则结束
4：在未划线的元素中找出最小的，未划线的各个元素减去这个最小元素，而交叉划线的元素加上这个最小的元素
5独立0的个数若小于n,则转4，否则结束
文章来源：https://www.toymoban.com/news/detail-424375.html
到了这里，关于平衡运输问题及其表上作业法---指派问题及其匈牙利解法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
