运筹学各种流程图
2018-11-08 17:41:14 0 举报
管理运筹学各种流程图
作者其他创作
大纲/内容
是
不存在0元素
找出min{bi}行作为换出变量
∀检验数σj≤0
使用初等行变换将锁定的aij化为1，同列其他元素化为0，再次计算检验数
∃检验数σj＞0
用max{系数}减去所有系数，得到的矩阵求解最小值后即为原问题最大值
逐次逼近法
max z型的对偶单纯形法
仍有没画圈0元素且同行(列)0数目≥2
第二阶段
∃右端系数bi＜0
存在单行单列0元素
一人完成多任务或不能完成某任务
非负权
∀aik≤0
方程中不存在单位矩阵
min{σj/aij}不存在
无界解
初始条件：①初始单纯形表的检验数全为非正②基底变量取值有负数
大M法（惩罚法）
Floyd算法
含有负权
l=n且mn
添加人工变量Xi凑出单位矩阵其目标系数为-M
得到最优解
最大化问题
在上述求得表中去掉人工变量对应列恢复目标函数系数继续求得最优解
化为标准型填入表中
图论最短路问题
①可看作2个相同的人(若多人中任意一人可完成2件事，则新增一人，完成时间取全部人中最小值)②相应费用修改为足够大的M
开始试探：选择0元素最少的行，将该行0元素中对应0元素最少的列记为⓪，同时去掉同行同列其他0，反复进行
将方程填入表格
①在没被直线覆盖部分中找出最小元素a②在打√行各元素减去a，在打√列各元素加上a
by izumi
非标准指派
整数规划之指派问题匈牙利算法
①将矩阵每行元素减去该行最小元素②将矩阵每列元素减去该列最小元素
⓪的数量m=矩阵阶数n
是否还存在0元素
全局遍历求得最小
两阶段法
人工变量法
继续寻找独立0元素
将原目标函数系数取为0人工变量系数为-1
其中M当作一个很大的正数
方程中存在一个单位矩阵
动态规划思想
计算检验数σj
单纯形法求解，使得人工变量换出基底
ln 则增加0元素
将表格数据填写为数字矩阵
否
∀右端系数bi≥0
为了使每行每列出现0
⓪处即为最优解
max z型的单纯形法流程图
直线数l与n的关系
Dijkstra算法
选取max{σj}列X为换入变量（记住Cj同时换入）
①.从只有一个0元素的行开始，记为⓪，同时去掉所在列其他0，记为Φ②给只有一个0元素的列记为⓪，该行0元素记为Φ
最优解
第一阶段
人数≠任务
计算θi根据最小比值规则选取min{θi}行X作为换出变量
①.对没有⓪的行打√②对打√的行中所有含Φ的列√③再对打√的列中含有⓪的行打√如此重复④对没有打√的行画横线，对打√的列画竖线
要求任意两点距离
mn 则作最少直线覆盖所有0元素
最小化问题
将图转化为矩阵
虚拟人数/任务数其中虚拟的费用为0
0 条评论
回复 删除
下一页
