刘程浩 CPDA广州11期学员
暨南大学金融系 经济学硕士
擅长应用数据分析方法进行分析并量化业务痛点,
采集信息并进行数学建模,制定解决方案并将之落地。
前阵子外甥女突然问我,“姨酱,你会填9宫格吗?就是9个格子分别填入1-9这9个数字,使得每一行,每一竖排,对角线加起来都等于15?” 这个问题真难倒我了,因为我想起了高中那会儿给化学方程式配平,总是按下葫芦浮起瓢,填好这个系数那个系数又不平衡了。不过后来我还是用线性代数+R语言后搞定了这一心中遗憾。于是我脑海里灵光一闪:会不会用线性代数的方法也可以解出这个问题呢?我觉得这个思路还是靠谱的。为什么这么说呢?
我们看,九宫格其实就相当于一个3×3的矩阵,要求每个矩阵的元素按照特定的方向求和后,代数和为相等的一个值,也就是15。
转变成线性方程组的形式就是:
从上面的未知数个数和方程个数相比来看,因为未知数个数要>方程个数,所以在实数范围内,解是有无穷多个的。
不过,由于9宫格的要求,限定了所填的数必须是1-9这9个自然数,因此,则需要加入一些约束条件,来让它在解集中找到合适的解。
加入哪些约束条件,才可以表示“只能从1-9这9个自然数里挑选”呢?
单纯一个代数式恐怕是很难表现出来的,但是可以从4个约束条件来实现,即
这样一来,俨然构成了一个线性规划求解的的雏形了。只不过,如果用笔算来求解的话,够呛。因此得借助计算机软件。
那么最亲民的软件就是excel了,于是我们可以选择excel里面的规划求解模块的功能,来计算求解。
只不过在正式开机之前,我们得把上面的资料整理一下,让它能够符合线性规划求解的范式,直接代入到excel你是无法计算的。究竟怎么转变呢?其实不难
首先要有个目标函数。这个目标函数按道理来说就是刚才所说的“从1-9这9个自然数中挑选数字填到矩阵的各个元素位置上”,但是我们做不到将这个汉语直接翻译成代数式,刚才我们也用了4个约束条件,只满足了这个语文句子的前半句。因此,我们必须转变一下思路:将目标函数设定的简单一些,然后把约束条件加多一些,这样就可以间接实现了。请看如下操作
目标函数:
约束条件:
好,这样我们就可以开始excel的操作了
第一步,点击进入excel的线性规划求解模块
第二步,分别填入目标函数,约束条件
点击“求解”后,不到半秒钟,就计算出结果了
是不是很快呢?
其实在之前我提示到,因为线性方程组的未知数个数要>方程个数,因此方程组没有唯一解,实际上在这里也是成立的。比方说上面的9宫格看成3阶方阵的话,那么对其转置,或者对其进行初等行变换,也是成立的:
好,知道了方法之后,再去求16宫格,25宫格,下面就是求得的16宫格、25宫格的解
不过呢,25宫格倒是花了2分多钟让excel来跑才跑出结果。我的电脑配置是I5处理器,8G内存。如果你的电脑配置比我高,那么会跑的比我的更快就出结果了。
在这里补充一下:
如果是求16宫格,那么目标函数应该为所有单元格求和=136,约束条件要修改成每一行、列、对角线的和应该为34;
如果是求25宫格,目标函数就应该为所有单元格求和=325,约束条件为每一行、列、对角线的和应该是等于65。这个是我在数据分析师群里面,有个老司机告诉我的规则。
用数学表达就是
那么,是不是有了excel之后,36、49……任意n×n宫格都可以计算呢?
我倒不推荐你这么做,因为随着矩阵的阶数不断增大,线性规划求解的所要计算的子问题就越多,运算量就越大!而且有些数量的X宫格还不一定有解呢。
联系客服