您的当前位置:首页>资讯 > 正文

3D演示帮你一眼看懂线性规划问题 这篇可视化教程火了

  • 2022-01-19 14:07:53 来源:量子位

你印象中的线性规划是什么样的?

先在二维平面上画图再找最优解?

但毕竟是学理论嘛,大家或多或少都会觉得枯燥晦涩。

那么为何不试试更加直观、好玩的学习方式呢?例如这样:

这是一位国外博主发布的机器学习3D教程,用可视化的方法展示如何在线性规划问题中逐步逼近最优解。

这篇帖子仅在一天之内就在Reddit上收获了接近200点的热度:

还收到了很多网友的好评:

我喜欢对数学问题高度可视化的描述,太棒了!

是什么内容这么优质?不妨看看他到底做了什么工作。

线性规划也可以一目了然

关于线性规划问题大家应该都不陌生。

在一组线性方程或不等式的约束下,求某一线性目标函数极值的问题就是线性规划问题。

而它的其中一个解法,就是上文中动图展示的单纯形法,还曾被评为20世纪最伟大的算法之一。

在生产计划,日程管理,交通运输,农业等诸多领域都有广泛的应用。

接下来我们以一个生产计划为例子做讲解:

假如你现在是老板,经营一家货运公司,一共有两种货车。

第一种货车跑一趟需要两天,烧4桶油,可以创造1000的利润。

第二种跑一趟要15天,烧8桶油,但是可以创造5000的利润。

那如果你手上有500桶油,应该怎么配比两种货车的货运次数才能在一年内获得最大利润呢?

这就是一个简单的线性规划问题。

这样的约束条件看起来并没有什么感觉,但是放在空间中就不一样了。

类似于许多平面把完整空间分割出一块多面体:

分割出的多面体(粉色部分)为可行域或者可行多面体。它包含了所有符合约束条件的点。

线性规划的目的,简单来说就是在可行多面体上找到一个点,来满足预期。比如前面例子中的获得最大利润。

那应该怎么找呢?博主对比了两种办法。

第一种是单纯形法。

由于约束函数和目标函数都是线性的,所以最优解必然存在于可行多面体的顶点。

所以寻找最优解的过程就可以描述为:沿着在可行多面体的棱上沿着目标函数值增加的方向搜索顶点。

听起来不明所以吧?

但是用图形解释就清楚多了:

但是这个方法只能用于求解线性规划的问题。对于非线性规划就无能为力了。

而第二种内点法,在更广泛的凸集优化问题中都可以应用。

它和单纯形法不同的地方在于,内点法是通过增加一个惩罚函数P(x)来不断地调整路径:

在逐渐靠近可行多面体边界时,惩罚函数会取越来越小的值。

内点法直观来看是这样的:

它不再沿着可行多面体的棱进行迭代,而是直接从内部开始,逐渐逼近最优解。

是不是一目了然了?

相比于纯数学或者算法的推演,可视化的形式明显更容易让人印象深刻。

更多的可视化教程

除了这篇3D教程之外,该博主还在另一个介绍凸优化的KKT条件和内点法的视频中,可视化了内点法是如何通过牛顿迭代逐渐得到最优解的:

视频中x(t)每经过一个黄色的圆框代表进行一次牛顿迭代,左下方的图像代表x(t)在不断地迭代下趋近于最优解。

同样,也比视频上方的一长串公式容易理解多了。

用这样的形式去呈现复杂的内容不禁让网友联想到了另一位可视化视频博主:

好内容!还看到了3blue1brown的影子,动画也很清晰。

在博主的回复中,也能看到他受到另一个数学可视化博主3blue1brown的启发。

后者也同样输出了很多数学可视化的相关视频,如果有兴趣可以多多了解。

标签: 函数 线性规划 博主 教程 数学 货车 利润 单纯形法 算法

推荐阅读

三星试生产4080圆柱型电池 媲美特斯拉4680

据报道,4680电池商用时间已被推迟到2023年。

地铁安检机辐射到底太可怕 真相:你可能多虑了

辐射无处不在,担心就做好防护。

汤加火山灰会飘到中国吗?专家解答

目前火山出现的气体已经向西飘散,飘到了澳大利亚。

猜您喜欢

【版权及免责声明】凡注明"转载来源"的作品,均转载自其它媒体,转载目的在于传递更多的信息,并不代表本网赞同其观点和对其真实性负责。亚洲科技网倡导尊重与保护知识产权,如发现本站文章存在内容、版权或其它问题,烦请联系。 联系方式:8 86 239 5@qq.com,我们将及时沟通与处理。

业界