锐客网

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

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

IT技术Hog


仅出现在第3个等式约束中 ， 即
在这里插入图片描述
则此时无法保证可行性，因为b ? \vec{b}
b
中第1个分量是负数 。
为了避免等式右侧出现负数，只能选择比值最小的一行，即第1行 。即化成如下的形式：
在这里插入图片描述
如果此时我们想让x 3 x_3x
3
入基 ， 此时的最小比值是第2行，即让该行为1，其余行为0 。但是，为了让x 3 x_3x
3
的第二行为1，该行两端必须同时乘以一个负数，此时仍然无法保证b ? ≥ 0 \vec{b} \geq0
b
≥0，因此只能选择系数非负的一行 。
注：这里的非负性是指系数非负 ， 而不是比值非负 。即当b中某行分量是0，而该行入基变量系数是负数，仍不能入基 。
在这里插入图片描述
特殊情况：没有非负比值，即没有有限的目标函数值 。
在这里插入图片描述
选择入基变量的原则
选择某个入基变量使得目标函数能改善 ， 通过检验数选择 。
此处假设优化目标是求最大值 。通过等式约束，将目标函数表示成非基变量的线性组合 。即
f ( X ) = c 1 x j ( m + 1 ) + c 2 x j ( m + 2 ) + . . . + c n x j ( n ) + c o n s t f(X)=c_1x_{j(m+1)}+c_2x_{j(m+2)}+...+c_nx_{j(n)}+const
f(X)=c
1
x
j(m+1)
+c
2
x
j(m+2)
+...+c
n
x
j(n)
+const
只有选择检验数是正数的变量入基才有可能使得目标函数继续增大，因为入基之后变量只可能增大或者不变 ， 而不可能减少 。
如何确定已经找到了最优的目标函数值
此处假设优化目标是求最大值 。
当每个非基变量的检验数都是负数时，目标函数已经达到了最大值 。
退化情况
Thm. 收敛条件：每次迭代过程中，每个基本可行解的基变量都严格大于0，则每次迭代都能保证目标函数严格增加 。而基本可行解的数目是有限的，因此上述过程不会一直进行下去，因此一定能在有限次迭代过程中找到最优解 。
Def. 退化情况：某些基变量是0 。则多个基矩阵对应同一个退化的顶点 。
Thm. 循环迭代导致不收敛：多个基矩阵对应一个顶点 ， 即每次出基入基都换了基矩阵，但是对应的退化顶点不变 ， 即目标函数也不变 。因此可能出现在几个基矩阵之间循环不止的情况 。
避免退化：由于顶点的个数是有限的，我们只需标记那些已经迭代过的顶点，即可避免循环 。
**bland法则：**始终选择下标最小的可入基和出基的变量 。
当所有的基变量都严格大于0时，则这个基矩阵对应于非退化的顶点，此时可行基矩阵和顶点是一一对应的；
当某些基变量为0时，则这个基矩阵对应退化的顶点，一个退化的顶点对应数个可行基矩阵 。
即给定一个可行基矩阵 ， 一定能确定一个顶点，但是给定一个顶点时，其对应的基矩阵可能不唯一 。
更一般地说，当顶点非退化时，可行基矩阵唯一；否则可行基矩阵不唯一 。
如何确定初始的基本可行解
先将一般模型转化为标准模型 ， 然后添加人工变量，在迭代过程中将人工变量都变成非基变量，则基变量就只剩下原来的变量 。
在这里插入图片描述
大M法在这里插入图片描述
两阶段法
在这里插入图片描述
例题
本质就是不断的迭代单纯型表
在这里插入图片描述
在这里插入图片描述
一般线性规划问题总结
一般模型转化为标准型
在这里插入图片描述
在这里插入图片描述

推荐阅读


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

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