6.2 单纯形方法在线视频

大家好

我们刚才说到了 两个变量的线性规划问题

我们说两个变量线性规划问题

我们可以用图解的方式 来对它进行刻画

但是 如果我们决策变量比较多了

以后我们说用图解的方式 显然就有点困难了

显然就有点困难了

因此呢 在这地方

我们开始提出一种

单纯形方法 来求解线性规划的问题

单纯形方法 实际上的话想法呢

非常简单 就是我们说的

在一个确定的一个 约束方程

它的基本解 然后就开始

计算它的对应的目标函数值

那么

在整个这个可行解在这个范围里面呢

我们来寻找它的最优解

那么从广义上来说

它属于一种搜索的 穷举的一种算法

为了方便的话

我们做这么一件事情 首先呢

我们把它的模型跟它标准化

把它的模型跟它标准化

那我们大家都知道

我们刚刚线性规划的模型是什么样的呢

我们说有若干个决策变量

x1 x2 xn

有个线性的目标函数

也就是说c1x1 c2x2加上cnxn

构成的Z对吧

将来要求这个目标函数 是最大还是最小

有个约束条件 有个约束条件

那么实际上把它写在一块呢

就是我们说的a1x1 a2x2 等等

把它写在一块

它应该小于等于b1 当然也可能是大于等于b1

那么这么一个若干个约束条件 构成在一块的对吧

这个不等式约束 好的

我们现在首先呢 想把它变成一个标准形式

怎么来变呢

首先呢

我们把约束条件

我们把它变成不等式约束

变成个等式约束

不等式约束怎么变成等式约束呢

例如 我们说

如果左边是小于等于右边

那我们就开始跟它补入一个 正的一个变量

或者引入一个正的变量

xn加i 使得它左右两边的就相等

这是我们说不等式约束

就变成等式约束

如果 我们说左边的约束

比右边的约束来的大

那这个时候怎么办呢

我们也是引用一个新的一个变量过来

把左边的呢 刨掉一点点

或者减掉一点点 使得它左右两边相等

所以这个时候呢就引入了一个变量呢

我们就xn加j 那么说

左边的减掉xn加j

那么跟右边就相等了

跟右边就相等了

这是我们说把不等式约束 就变成等式约束

那么相对来说

我们觉得目标函数呢

我们只有n个 对吧

只有n个

那你现在增加了xn加i xn加j

那不是增加了这么多

那怎么呢 对我的目标有影响了

所以我这时候目标函数呢

就跟它 换一种形式来写啦

对于我新增加的那些变量

那么它的系数呢

就用0来替代

所以这样一来目标函数 就像当是跟原来就一样了

就没有发生变化了

这是我们说的第一件事情

把不等式约束变成等式约束

第二个 我们将统一起来的话 把目标函数呢

都跟它改成 目标函数极大化

目标函数极大化

原来如果是要求极小的话

那么大家可以通过一个数学的变换

把它乘上一个负数

对吧 乘上一个负数

那么这一来的话 极小呢就变成了极大了

那么这么一来了 就相当对我们的Z撇呢

求最大

这是我们的统一起来

目标函数 求最大 求最大

第三种 可能还有些变量

原来对它没有做一些要求

因为我们刚才通过例子可以看得出来

我们对那些变量都有一个非负的要求

如果我们在 过程当中有些变量

它没有一些非负的要求

那怎么办呢

所以这个时候呢

我们就开始引入一组

引入两个变量 来进行刻画它

例如 引入xi撇xi两撇

那么这么一来的话

我们用xi撇减去xi两撇的话

那么这个时候就变成

我说引入了两个非负的对吧

非负的决策变量 xi撇 xi两撇

来使得大家都满足我们的非负的这么一个要求

非负的这么一个要求 好的

经过这三个步骤以后的话

我们把原来的

线性规划模型 或者线性规划问题呢

我们就可以变成一个标准的

线性规划模型 或者标准的线性规划问题

左边这边来看的话

我们仍然用n个变量来表示

那就是x1 x2 xn n个变量

求一个目标函数最大值

那当然就是c1x1 c2x2

一直到cnxn

相加起来

目标还是最大值

这些n个变量的满足

我们这个时候 就是满足一个等式的约束条件

满足一个等式的约束条件

也就是说

每一个呢 都是个相等的

总共呢 约束条件有M个约束条件

到了最后每个xi

我们都非负的

都大于等于0的 把这个了

如果用数学语言来描述的话

那就变乘我们右边的非常简单的这么一个表达方式了

求一个c乘上x一个函数的最大化

满足约束条件呢 就是满足

一个矩阵方程了 ax等于b

a当然就是我们说的n行m列的一个矩阵

那么b呢

也就是我们说这个向量

x也是个向量

这是我们这么一个表达式

那么从这个表达式大家可以看得出来

如果 变量的个数是n个

约束条件是m个

我们说

一般来说 m一定会比n要来的小

因为大家可以想想

约束条件越多

那么解的集合就越来越小

解得集合可能最后

多了太多了以后

可能就变成我们说一个空集了

所以一般来说

m都会比n要来的小点

来的小点 好的基于这么一个想法的话

大家可以看得出来

对于一个代数方程AX等于B来说

它的解向量对吧

它的解向量

我们说 如果会有满足这么个条件

由n减m个分量为零

剩下的m对吧

剩下的m个向量呢 构成的一个

m的线性无关列 也就构成一个积的话

那么我们说这么一个解

我们把它称作为基本解

这么解把它称之为基本姐

当然 在线性规划问题当中

如果一个可行解 也是一个基本解的话

我们将来给它一个名字

我们把它叫做基本的可行解 基本的可行解

基本的可行解

那么对于线性规划来说

我们将来要做单纯形方法

那么是要做一件什么事情呢

做些什么事情呢

实际上呢

它就是说

在这个解里面 可行域里面

找一个极点 然后根据一定的规矩

根据一定的准则

对吧 来判断它是不是最优

如果不是最优的话

那我们就开始跟旁边的一个极点呢

来进行迭代

使得最后使得他

目标函数值呢 达到更好或者达到更优

直到 找到一个最优解为止

这是我们说 单纯形方法实际上是个迭代的过程

是一个迭代的过程

那么在这个迭代的过程当中

我想的话 可能有三个方面的事情

需要特别跟大家做个交代

首先

最优解

到没到

也就是我们说的最优解的判别的一个准则

如果是到了最优解的话

那么说迭代终止了

迭代就可以终止下来

所以这是一个要有个判别的准则

第二个

你不要从这个极点 换到另外一个极点上去吗

那么实际上就是换机的运算

换机的运算 也是从一个基本可行解

换到另外一个基本可行解

那么换机的准则是什么样的

你第三个 也就是说换进来

那么它是有什么准则

它的准则是什么样的

实际上我们说 在运用单纯形方法的话

那么这三个准则 我们需要特别去考虑它

当然了

对于我们现在来说的话

线性规划的问题求解就不用那么复杂了

我们有现成的软件matlab

或者还有专门的软件来对它进行求解

我想这个问题 就比较简单

只要用软件来进行操作

我们过多的理论就可以展示先

有兴趣可以下去讨论一下它

总的来说

我们说建立 或者说得到一个线性规划的模型的话

我们说是一个非常重要的一个 探索的过程

也就是我们通常说的一个数学建模

这个过程 对吧

对于线性规划模型

它问题的求解到目前为止

仍然是计算数学的一个 难点问题

那么如果有兴趣

我们大家可以进一步的探讨 它相关的一些数学理论

它的相关的一些数学理论 对它的计算的话

我们可以借助一些 现成的一些软件

来进行求解

那我想关于线性规划问题的求解

模型的建立 以及求解

我们今天说到这地方

我们下次课 再见

谢谢大家