锐客网

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

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

IT技术Hog


一般模型与标准模型的转化
主要方式是增加决策变量 。有两种情况需要增加
不等式变等式，每个不等式增加一个决策变量 。
1个自由决策变量转化为2个约束的决策变量 。
在这里插入图片描述
线性规划问题解的可能情况
唯一最优解
没有有限的最优目标函数
没有可行解
无穷多的最优解（一维问题中不会出现）
凸集
Def. 凸集：该集合中任意两个元素的凸组合仍然属于该集合 。
在这里插入图片描述
注：此处的α \alphaα不能是0或1 。
Thm. 线性规划的多面体模型是凸集 。
Def. 凸集的顶点：顶点无法表示成集合中其他元素的凸组合 。
在这里插入图片描述
顶点的等价描述
从系数矩阵中抽取m列线性无关的列向量，组成可逆方阵 。则由此可求得m个决策变量的值，再令其余的决策变量为0即可 。
推论
顶点中正分量对应的系数向量线性无关 。
一个线性规划问题标准模型最多有C n m C_{n}^{m}C
n
m
个顶点 。
定义总结
基矩阵§：系数矩阵中抽取m列线性无关的列向量组成可逆方阵 。
基本解：m个基变量有基矩阵和b ? \vec{b}
b
决定，剩余(n-m)个变量都置0，称之为非基变量 。
基本可行解（顶点）：基本解中可行的，即满足非负性约束
Thm. 线性规划标准模型的基本可行解就是可行集的顶点 。
Thm. 标准模型的线性规划问题如有可行解，则定有基本可行解 。
Thm. 线性规划标准模型中顶点的个数是有限的 。
Thm. 线性规划标准模型的最优目标函数值如果有有限的目标函数值，则总在顶点处取到 。
单纯形法
在顶点中沿着边搜索最优解的过程 。
按照上述的原理，我们固然可以求出所有的基矩阵，进入求出所有的顶点 。计算每一个顶点的目标函数值，找出其中最大的那个 ， 但是这样做的计算量未免太大，因此有了单纯行法，即沿着边搜索顶点 。
在这里插入图片描述
单纯形法就是一个不断的选择变量入基出基的过程 。
假定已知一个基本可行解 。（问题4）
如何计算选定进基变量后的基本可行解 。(问题1）
如何选择进基变量使得目标函数值改善 。（问题2）
如何判断已经找到最优的目标函数值 。（问题3）
计算选定进基变量的基本可行解
Def. 基本可行解的表示式：基变量只出现在一个等式约束中 。如：
在这里插入图片描述
此处的x 3 , x 4 , x 5 x_3,x_4,x_5x
3
,x
4
,x
5
就是基变量 。
选定出基变量：保可行性的最小非负比值原理
由上所述 ， 一个顶点对应一个基本可行解，其中m个基变量，(n-m)个非基变量 。假定我们要选择某个非基变量x i x_ix
i
入基，实际上就是通过对增广矩阵做初等行变化使得x i x_ix
i
仅仅出现在一个等式约束中 。比如我们通过变换，使得x i x_ix
i
仅仅出现在第j个等式约束中，如果此时仍然满足可行性，那么x i x_ix
i
就取代了原来在此处的基变量，成为新的基变量 。
在进行初等行变换的过程中，要保证可行性，即
b ? ≥ 0 \vec{b} \geq 0
b
≥0
。因此要选择最小非负比值 。请看下面的例子：
在这里插入图片描述
假设我们要选择x 2 x_2x
2
入基，那么就是要通过初等行变换，使得x 2 x_2x
2
的系数向量中某一行是1 ， 其余行都是0 。如我们选择x 2 x_2x
2

推荐阅读


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

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