6.1 两变量的线性规划在线视频

同学们大家好

我们今天开始介绍一种新的 建模的方法

或者说 一种新的模型

我们把它称作为 线性规划

日常生活当中跟一些最大

最小 最长 最短

有关的一些问题

我们都把它称作为 最优化的问题

那么

研究并求解最优化的问题的这些数学方法

我们把它称之为 运筹学

目前来看

运筹学的主要分支 包括一些线性规划

非线性规划

动态规划 以及图与网络分析等等这方面内容

那我们今天要讲的 线性规划属于这么一个范畴

那么

说起它的源头来说

线性规划应该起源于1939年的

前苏联的一个数学家 康托洛维奇

那么他首先发表了一篇论文

然后到了47年

由美国的数学家

他开始提出了一些 线性规划的一般的模型

或者说一般的理论

然后进行发展

我们首先看这么一个例子

看这么一个例子 就是我们通常说家具厂的生产

那么一个公司

那么要生产桌子跟椅子

那么桌子跟椅子

大家可以想象需要一些材料

首先我们需要一些木材 需要一些人工

那么在这里面

我们跟它做一个限制

人工呢

总共能提供我们说450个工时

木材呢 我们能提供4个立方米的木材

那么在这里面

我们生产一张桌子

需要多少工时 需要15个工时

需要0.2的立方的木材

那么卖出的价钱呢 大概是80块钱

一样的道理

那么生产椅子呢

需要10个工时

那么木材呢 需要0.05个立方的木材

那么卖出的价钱呢 是45块钱

那么从厂家来说

如果想使得收益 或者效益能最大化的话

那么应该怎么安排 对吧

生产生产多少桌子

生产多少椅子出来

那么这么一来

我们就开始把它转化为一个数学问题了

那么接下来的话

我们考虑产值为 最大化

也就说最大收益

假设生产 我们的桌子是x1

椅子呢是x2

我们把x1 x2呢

称作为决策变量

目标函数呢很自然的话 一张桌子我们说卖80

那么两张桌子就卖到160了

所以我们的x1呢

那么多桌子就卖到了

我们说80乘上x1

同样道理来说

那么就是就乘上

加上我们说的45乘上x2了

所以构成的目标函数 极大化了

就从80的x1加上45的x2

这么一个函数f

使得它最大

那我们刚刚说过了

那么既然要生产桌子跟椅子的话

我们有两个限制条件

一个是我们的工时的限制

一个是我们说的

木材的限制

那么构成这两个限制条件

分别为0.2的x1

加上0.05的x2 小于等于4

还有呢

我们说是15的x1

加上10倍的x2 小于等于450

那么

既然让生产桌子跟椅子

那么很自然x1 x2就应该大于等于0

大于等于0了

那么从这里面

我们可以看得出来

我们说的x1 x2

整个的过程当中

我们的目标函数

它是个线性函数

它的约束条件 或者说限制条件也是个线性函数

我们把它称作为 线性规划

这是我们名字的由来

在这里面的话很自然

我们要做的事情

就是说 怎么来求出决策变量

x1 x2的取值

使得 我们都说目标函数值能够最大化

那么对于它来说

因为这个数值比较小

我们可以穷举一下

可以算出来 分别x1 x2呢

为14跟24 那目标函数呢

可以算出来是2200了

这是我们说的 这么一个问题

把我们刚才说的 线性规划问题跟它一般化的话

那我们来看看

一般来说

包括这三部分的内容

首先呢

是要有个目标函数

也就是说

线性的目标函数

求这个线性目标函数 最大或者最小

这是一方面的事情

那么 在这里面的话 牵扯了我们的一些变量

我们把它称之为决策变量

那么 现在呢我们的约束条件

我们刚说的 目标函数跟约束条件都是个线性函数

我们把它称作为线性规划

如果目标函数跟约束条件 属于我们的非线性函数的话

当然我们就变成另外一个范畴了

就变成我们的 非线性规划的问题

为了对它进行求解

我们有几个概念

我们简单的回顾一下

首先第一个概念叫做可行解

所谓可行解的话就说 满足我们的线性

约束条件或者我们的限制条件

那么这些变量 我们把它称之为可行解 对吧

有可能满足我们的约束条件的

第二个

把自己解呢 装到一块也就构成一个集合了

可行解的集合呢

我们把它称作为可行解集

或者说可行域

另外一个 如果能够使得

目标函数达到最值或者达到最大

或者达到最小的这种可行解

我们把它称作为 最优解

把它称为最优解 所谓的线性规划的话

我们将来就是要寻找这种最优解了

最优解了

那么涉及到我们的决策变量

对吧

刚才例子里面我们涉及的决策变量

是两个决策变量

当然

对于我们的问题复杂一点

可能会涉及到多个决策变量

那么首先呢

我们得考虑两个变量

两个决策变量

它的线性规划问题

两个线 决策变量

它的线性规划问题了

我们来看看 它不就个不等式约束条件嘛

不等式约束条件很自然的话

我们就可以建立一个直角坐标系

把它的不等式约束条件 可以跟它画出来

画出来

类似于我们右边的这个图啦 对吧

一个不等式约束条件就是一个半个平面

那么另外一个不等式约束条件又是半个平面

再加上有了我们说的x1大于0 x2大于0

因此呢就构成了

我们绿色的这一块的区域了

绿色的这块区

那么这一块区域呢

大家可以图可以看得出来

它现在就是一个图集了

它就是一个图集了

那我们将来要寻找的

就是说

在这个绿色区域里面

我们在这里面找了个什么

找个最优解

找个最优解

关于这个最优解

我们说有这么一个结论

我们可以看得出来

以目标函数呢

我们设定它不同的值

设定它不同的值 那目标函数设定不同的值

那就像我们刚才说的45的x2

加上80的x1

那么等于一个不同的值等于一个k值

那么大家可以看得出来

在图上呢画出来就是一组 平行的直线 一组平行的直线

那么我们所谓最优解的话

那将来就是我们说的取决于

它离原点的远近的程度

它离原点的远近的程度

那我们从这里面可以看得出来

我们如果过x2

这条点上的这个某个顶点的话

我们说它将是离原点最远的一个点

那么相对的那个点的 也可能会是我们的最优的顶点

这是我们用图 可以看得出来的一个事情

好的

一般来说

属于线性规划里的最优解的话

我们说一定是在什么

一定是可行解的那个集合上面

的某一个极点上达到 某一个极点上达到

那么我们可以看得出来

如果 像我们两个变量的这种问题的话

总共也就是我们的四个极点

那我们就可以一个个极点去跟它穷举一下

或者说得到最优值了

当然

大家可以说了

如果我们决策变量数量要多的话

那么这个时候穷举 可能就有一定的困难

就有一定的困难了 好的

关于决策变量比较多的情况之下

那个时候 线性规划问题的求解怎么求解

那我想我们下次课再说

今天这次课说到这

下课