在一个网站上面发布广告怎么做,做软件下载网站,电子商务网站建设步骤百度文库,杭州绿城乐居建设管理有限公司网站第一步#xff1a;化“约束标准型”
在每个等式约束中至少有一个变量的系数为正#xff0c;且这个变量只在该约束中出现。在每个约束方程中选择一个这样的变量称为基本变量。
剩下变量称为非基本变量。
一个简单的栗子 上图是一个约束标准型线性规划的例子。 等式1#x…第一步化“约束标准型”
在每个等式约束中至少有一个变量的系数为正且这个变量只在该约束中出现。在每个约束方程中选择一个这样的变量称为基本变量。
剩下变量称为非基本变量。
一个简单的栗子 上图是一个约束标准型线性规划的例子。 等式1x₁3x₂-x₃2x₅7 x₁x₂x₅ 的系数为正但是等式2和3中有 x₂等式3中有 x₅所以等式1的基本变量是 x₁。 等式2x₄-2x₂4x₃12 x₄x₃ 的系数为正但是等式1和3中都有 x₃所以等式1的基本变量是 x₄。 等式3x₆-4x₂3x₃8x₅10 x₆x₃x₅ 的系数为正但是等式1和2中都有 x₃等式1中有 x₅所以等式1的基本变量是 x₆。
那么x₁x₄x₆ 是基本变量剩下的x₂x₃x₅ 是非基本变量。
————————简陋的分割线————————
如果我们让非基本变量 x₂x₃x₅ 都等于 0 呢
式子就变成了下面介个样子。 maxz0 x₁7 x₄12 x₆10 其中x₁7x₄12x₆10x₂0x₃0x₅0。 所以将所有非基本变量置为 0从约束方程式中解出满足约束的基本条件的值即可求出一个基本可行解。当然这个基本可行解未必是最优解。
而且很明显解等于该式子的常数部分。
————————简陋的分割线————————
单纯形算法的基本思想就是从一个基本可行解出发进行一系列的基本可行解的变换。每次变换将一个非基本变量与一个基本变量互调位置且保持当前的线性规划问题是一个与原问题完全等价的标准型线性规划问题。不懂的话继续往下看就懂啦~
第二步列初始单纯形表 很明显红色部分基本变量蓝色部分非基本变量。 其中的 071210 是常数项剩下的是系数项。很简单的填表不赘述了
————————简陋的分割线————————
接下来是选择入基变量和离基变量
入基变量从非基本变量里选
红框里选正的红框里选正的红框里选正的。所以选 x₃为入基变量
如果没有系数为正的那么当前基本可行解为最优解。 离基变量从基本变量里选
在前面我们选择了唯一的正值元素3它所在的列中有两个正元素4和3。
我们算min{12/410/3}3所以选 x₄ 为离基变量。
如果3所在的列没有正元素那么最优解无界计算结束。
第三步基变换直到找到最优解
然后做转轴变换目的是将入基变量与离基变量互调位置。
x₄-2x₂4x₃12
x₃ , x₄ 变换。
x₃-x₂/2x₄/43
代入x₁3x₂-x₃2x₅7 和 x₆-4x₂3x₃8x₅10 消去x₃。
x₁5x₂/2x₄/42x₅10
x₆-5x₂/2-3x₄/48x₅1
代入目标函数。
maxz9x₂/2-3x₄/4-2x₅
形成的新单纯形表如下 形成新的单纯形表重复前面过程直到所有非基本变量系数都变为负值为止。
