江苏龙网

  1. 首页 > 人文 > >

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

你印象中的线性规划是什么样的？先在二维平面上画图再找最优解？
但毕竟是学理论嘛 ， 大家或多或少都会觉得枯燥晦涩 。那么为何不试试更加直观、好玩的学习方式呢？例如这样：

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

这是一位国外博主发布的机器学习 3D 教程 ， 用可视化的方法展示如何在线性规划问题中逐步逼近最优解 。
这篇帖子仅在一天之内就在 Reddit 上收获了接近 200 点的热度：

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

还收到了很多网友的好评：
我喜欢对数学问题高度可视化的描述 ， 太棒了！

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

是什么内容这么优质？不妨看看他到底做了什么工作 。
线性规划也可以一目了然
关于线性规划问题大家应该都不陌生 。
在一组线性方程或不等式的约束下 ， 求某一线性目标函数极值的问题就是线性规划问题 。
而它的其中一个解法 ， 就是上文中动图展示的单纯形法 ， 还曾被评为 20 世纪最伟大的算法之一 。在生产计划 ， 日程管理 ， 交通运输 ， 农业等诸多领域都有广泛的应用 。
接下来我们以一个生产计划为例子做讲解：
假如你现在是老板 ， 经营一家货运公司 ， 一共有两种货车 。

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

第一种货车跑一趟需要两天 ， 烧 4 桶油 ， 可以创造 1000 的利润 。
第二种跑一趟要 15 天 ， 烧 8 桶油 ， 但是可以创造 5000 的利润 。
那如果你手上有 500 桶油 ， 应该怎么配比两种货车的货运次数才能在一年内获得最大利润呢？

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

这就是一个简单的线性规划问题 。
这样的约束条件看起来并没有什么感觉 ， 但是放在空间中就不一样了 。
类似于许多平面把完整空间分割出一块多面体：

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

分割出的多面体（粉色部分）为可行域或者可行多面体 。它包含了所有符合约束条件的点 。
线性规划的目的 ， 简单来说就是在可行多面体上找到一个点 ， 来满足预期 。比如前面例子中的获得最大利润 。
那应该怎么找呢？博主对比了两种办法 。
第一种是单纯形法 。
由于约束函数和目标函数都是线性的 ， 所以最优解必然存在于可行多面体的顶点 。
所以寻找最优解的过程就可以描述为：沿着在可行多面体的棱上沿着目标函数值增加的方向搜索顶点 。
听起来不明所以吧？但是用图形解释就清楚多了：

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

但是这个方法只能用于求解线性规划的问题 。对于非线性规划就无能为力了 。
而第二种内点法 ， 在更广泛的凸集优化问题中都可以应用 。
它和单纯形法不同的地方在于 ， 内点法是通过增加一个惩罚函数 P (x) 来不断地调整路径：

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

在逐渐靠近可行多面体边界时 ， 惩罚函数会取越来越小的值 。
内点法直观来看是这样的：

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

它不再沿着可行多面体的棱进行迭代 ， 而是直接从内部开始 ， 逐渐逼近最优解 。是不是一目了然了？
相比于纯数学或者算法的推演 ， 可视化的形式明显更容易让人印象深刻 。
更多的可视化教程


推荐阅读


上一篇：宝马|宝马V12动力最后的荣光！M760i将限量发售：起售127万

下一篇：马斯克|十手火箭送49星上天！马斯克“太空版图”再扩大：星链卫星破2千颗