锐客网

  1. 首页 > 睿知 > it技术 > >

python的仿射函数 仿射变换matlab代码( 四 )

IT技术Hog


在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
基于单纯型表迭代的实质
求出非基变量的检验数
σ j ( k ) = c j ( k ) ? C B T B ? 1 P j ( k )m + 1 ≤ k ≤ n \sigma_{j(k)}=c_{j(k)}-C_{B}^{T}B^{-1}P_{j(k)}\ m+1 \leq k \leq n
σ
j(k)
=c
j(k)
?C
B
T
B
?1
P
j(k)
m+1≤k≤n
确定进基变量
σ j ( t ) = m a x { σ j ( m + 1 ) , σ j ( m + 2 ) , . . . σ j ( n ) } \sigma_{j(t)} = max\{\sigma_{j(m+1)},\sigma_{j(m+2)},...\sigma_{j(n)}\}
σ
j(t)
=max{σ
j(m+1)
,σ
j(m+2)
,...σ
j(n)
}
确定出基变量
在这里插入图片描述
得到新的可行基矩阵
在这里插入图片描述
基于逆矩阵的单纯形法
在这里插入图片描述
核心问题：如何基于B ? 1 B^{-1}B
?1
计算出B ? 1 ~ \tilde{B^{-1}}
B
?1
~
。这两个矩阵仅仅有1列不一样，这是一个线性代数问题，与本课程的主要内容无关，此处不再赘述 。
总结：单纯形法中可能遇到的3中特殊情况 。
1. 退化问题：某些基变量为0
退化问题的现象是某些基变量为0，本质是一个退化的顶点对应多个可行基矩阵 ， 后果是可能使得单纯形法不收敛 。
在选择入基变量时，应该遵循blend法则，即每次选择可入基变量下标最小的那个 。
2. 没有最小非负比值 。
当选定入基变量后，需要根据“保证可行性的最小非负比值原理”选定出基变量，如果没有非负比值，则说明该变量可以趋于无穷，则该问题没有有限的最优目标函数值 。
3. 某个非基变量的检验数为0.
在选择入基变量时，需要将目标函数表示成非基变量的表达式 。以目标值是求最大问题的为例，此时应该选择检验数大于0的非基变量入基才能改善目标函数值 。
当所有非基变量的检验数都为小于等于0的时候，无论选择谁入基 ， 都会值得目标函数变得更差 ， 因此这时候就达到了最优条件 。
有一种特殊情况是某个非基变量的检验数为0 ， 如果选取该变量入基 ， 则目标函数值和原来一样 ， 但是我们得到另一组不同的基本可行解，即最优目标函数值对应了多个基本可行解，这说明原问题有无穷多最优解 。
4. 退化问题和非基变量检验数为0.
前者是一个顶点对应多个可行基矩阵 ， 后者是最优目标函数值对应多个顶点 。
前者可能导致单纯形法不收敛，后者说明该问题有无穷多解 。
文章知识点与官方知识档案匹配
算法技能树首页概览
31789 人正在系统学习中
打开CSDN，阅读体验更佳
最优化技术——线性规划
最优化技术——线性规划 线性规划基本概念 线性规划问题就是在一组线性约束条件下，求解目标函数最优解的问题 标准形式 线性规划问题的标准形式： 目标函数求最大值 所有约束条件均由等式表示 每个约束条件右端常数常为非负值 所有决策变量为非负值 改造方法 所有的情况与改造方法 目标函数求最小值则应该改为求最大值： 方法——添加负号： minF=Σcjxj→maxF=?Σcjxj min F ...
继续访问
线性规划和对偶规划学习总结
在学习列生成和分解算法的时候 ， 会频繁用到线性规划和对偶的知识，可以说LP和DP是基础 。因此理解线性规划和对偶的本质是很重要的 。单纯形法是纯代数运算 ， 从一个顶点跳到另一个顶点；且我们知道最优解一定在顶点取得 ， 可是为什么在顶点一定会取得最优解？为什么从一个顶点跳到另一顶点，通过进基出基就可以实现 ， 它俩为什么是一一对应的？除此以外，在分解算法中的极点和极射线和LP的解是什么样的对应关系？ 这些问题，应该说必须了解了线性规划和对偶的本质才能够深刻理解，而不至于陷入机械无脑的计算 。大概看了慕课的课程，感觉山东大

推荐阅读


上一篇：postgresql修改分区命名的简单介绍

下一篇：电商记如何卸载，电商记怎么下载