【运筹学】表上作业法 ( 运输规划问题最优解分析 | 退化与非退化 )

文章目录

• 一、运输规划问题
• 二、退化与非退化

一、运输规划问题

运输规划最终的求解最优解结果有如下情况 :

① 有唯一最优解 : 有一个检验数等于

;

② 有无穷多最优解 : 这种情况下 所有的检验数都严格小于

;

运输规划中不存在 ① 无界解 , ② 无可行解 两种情况 , 运输问题是一个实际的问题 , 运费肯定有一个可行的解 ;

二、退化与非退化

退化问题 :

运输问题的退化问题比较多 ,

给定一个线性规划 , 其中的变量分为两部分 , 基变量 和 非基变量 ,

非退化解 :

一个问题是 非退化的 ,

当且仅当 ,

所有的 基变量 都是非

的 , 即 严格大于

;

退化解 :

一个问题是 退化的 ,

当且仅当 ,

存在 一个的 基变量 是 等于

的 ;

在 【运筹学】表上作业法 ( 示例 | 使用 “ 闭回路法 “ 计算检验数判定最优解 ) 博客中求解的运输规划问题是 非退化的 , 所有的基变量都是 严格大于

的 ;