数学课|中学生也能看懂的线性规划问题

2019-06-21 11:32
美国

作者|吴昊&编辑|罗数君

文1967字 阅读时间约 5分钟

导语:

你是否有过这样的经历,在琳琅满目的商品前无法抉择,希望在预算内买到最有价值的东西?其实无论在个人的日常生活还是工作中,懂得线性规划的数学知识都将使你事半功倍。想了解这个数学知识吗?请读者们看今天的文章吧!

假如给你100块钱,你会做什么?学生们可能会买一本日趋昂贵的教材,家长们可能会给孩子买一套,加班族们可能会买一张咖啡店的会员卡……哪个选择最优呢?这就要看每个人心中,每件东西的价值了。

博深购物城最近举办了这样一场活动:每一个到店中的顾客都会领到100块钱的代金券,可以在购物城中任意挑选商品消费。皮卡丘转了一圈,列了一个他看中的物品清单:

皮卡丘的目的,就是在不超过100块钱的前提下,最大化他的皮卡皮卡!可是由于他的手力量有限,只能拿总共不超过30克的物品。转化成数学的语言,这就是说:

给定两个条件15m+20f+12s≤100,以及5m+5f+7s≤30,最大化25m+35f+40s。当然,由于物品的数量只能是非负数,所以我们规定m,f,s≥0。同时,由于以上物品都可以按重量卖,而重量可以是小数,所以我们不规定这三个变量是整数。

图片来源:zh.fanpop.com/

这种生活中十分常见的最大化问题叫作线性规划(linear programming)问题。它的严格定义是:已知x1,x2,x3…≥0,并给定一些线性的条件a1x1+a2x2+a3x3…≤c,最大化线性函数d1x1+d2x2+d3x3…的取值。

我们来举几个最简单的例子:x+y≤3,-2x+5y≤3,x+2y≤2,x和y都非负,要最大化的线性函数f=6x+y。这该怎么解决呢?我们可以画一张图:

这张图里的横轴为x,纵轴为y,三条线对应的不等式已在图中标出,而同时符合三个不等式,并满足两个变量均非负的可行域(可取值范围)就是蓝色的这片区域。在这片区域上,我们画出6x+y的等值线(比如6x+y=1,6x+y=2,6x+y=3等),发现其中函数6x+y在(2,0)这一点的取值最大。因此,我们就可以得到所求的最大值为12。

注释:等值线是制图对象某一数量指标值相等的各点连成的平滑曲线。

图片来源:deansforimpact.org/content-of-thinking/

二元线性函数的等值线很容易找到:固定函数的值,只需解一个二元一次方程即可,比如6x+y=1。多元线性函数稍复杂一点,因为我们要找到的不再是等值线,而是使函数值相等的高维平面,比如三维平面6x+3y+7z=5。

那么问题来了:在高维空间中,就算我们能找出所有等值面,那如何看出哪个与可行域相交的等值面取值是最大的呢?画出来是不太可能了,那该如何计算呢?

我们先来证明一个引理:使线性函数f取值最大的点一定是不等式对应的平面的交点,也就是可行域的顶点,而不会是可行域内部的点。

注释:引理是数学中为了取得某个更好的结论而作为步骤被证明的命题,其意义并不在于自身被证明,而在于为达成最终目的作出贡献。

图片来源:tenor.com/view/garfield-thinking-think-get-to-work-gif-12041090

这个看似很复杂的定理证明却十分简洁明了:任意一个多维的多面体里,任取一个点v,它对应的函数值f(v)=r。如果它不是顶点,那么经过v的任何平面(多面体本身的表面除外)都会把多面体切成至少两块(如果是凹多面体的话可能多于两块),v所在的等值面f=r也不例外。它也会把可行域这个多面体切成至少两块,也就是说,等值面的两边都有可行域。又因为我们的函数f是线性的,所以两边中一定会有一边取值大于r,所以v取得的值r一定不是最大值。

那么,如果等值面恰好就是多面体本身的一个表面呢?那么这个表面也一定会经过至少一个顶点,引理证明完毕。

图片来源:giphy.com/gifs/cheer-cheering

知道了这个性质之后,我们就可以用一个最基础的方法——枚举法:把多面体的每个顶点代入函数进行计算,最大的值就是我们想要的结果。

那么,皮卡丘最多能得到多少皮卡皮卡呢?我们一共有5个不等式(包括3个非负变量)。每3个平面都会产生0个,1个,或无穷个交点。在本题目中,每三个不等式都会产生1个交点,但有些交点并不在可行域内。根据排列组合的知识,我们一共可以得到10个交点。但是事实上,在10个可能的交点里,只有6个满足所有的不等式,而这六个交点里,皮卡丘能获得皮卡皮卡的最大值是198.75。此时,m=0,f=4.25,s=1.25。也就是说,皮卡丘要拿4.25单位的番茄酱,1.25单位的饲料以最大化他的皮卡皮卡。

图片来源:stockphoto.com/illustrations/aha

在现实问题中,我们通常会有很多个变量和条件,这时枚举法就太耗时间了。线性规划最常用的几个方法包括单纯形法、椭球算法、内点法等,比枚举法快得多。有兴趣的读者们可以深入探索一番哦!

假如给你一百块钱,你会怎么花呢?下一次,不妨建个模最大化你的皮卡皮卡~

喜欢这篇文章吗?欢迎给我们留言,探讨有趣的数学问题,如果你还想看其他的相关内容,也可以向我们提出来哦!

(原载于“罗博深数学”公众号:LuoboshenMath)

    特别声明
    本文为澎湃号作者或机构在澎湃新闻上传并发布,仅代表该作者或机构观点,不代表澎湃新闻的观点或立场,澎湃新闻仅提供信息发布平台。申请澎湃号请用电脑访问https://renzheng.thepaper.cn。