用线性规划和Excel求解器优化业务决策

发布时间:2021/07/12 00:00      浏览:249
作者:苏有熊
来源:我是苏有熊

01 乔治·伯纳德·丹齐格


1939年,25岁的乔治·丹齐格(George Bernard Dantzig)在美国加州大学伯克利分校攻读数学博士学位,在那里他在Jerzy Neyman 的指导下学习统计学。


有一天,临近上课时,Neyman教授在黑板上写了两道题。 


丹齐格迟到了,并认为它们是家庭作业。


根据丹齐格 的说法,它们“似乎比平时更难”,但几天后他提交了这两个问题的完整解决方案,仍然认为这是一项逾期未交的任务。


六个星期后,兴奋的Neyman教授急切地告诉他,他解决的“家庭作业”问题是统计学中最著名的两个未解决的问题。


他准备了丹齐格的解决方案之一,以在数学期刊上发表。


这个故事开始传播,并被用作展示积极思考力量的励志课。


后来,以这个故事作为蓝本,好莱坞在1997年改编并制作出了一部电影,《心灵捕手》。



随着第二次世界大战的爆发,丹齐格从伯克利的博士课程中休学,成为美国陆军空军的文职人员。


从 1941 年到 1946 年,他成为陆军航空兵司令部统计控制作战分析处处长。


1946年,他回到伯克利完成他的课程要求并获得博士学位。


1947年,丹齐格博士发表了单纯性算法,第一次有效地解决了大多数情况下的线性规划问题。


丹齐格最初的例子是找到 70 人到 70 个工作岗位的最佳分配。


测试所有排列以选择最佳分配所需的计算能力是巨大的;可能的配置数量超过了可观测宇宙中的粒子数量。


然而,通过将问题视为线性规划并应用单纯形算法,只需要片刻即可找到最优解。


线性规划背后的理论大大减少了必须检查的可能解决方案的数量。


1963 年,丹齐格博士的Linear Programming and Extensions由普林斯顿大学出版社出版。




这本书具有丰富的洞察力和重要主题的覆盖面,很快成为线性规划的“圣经”。


丹齐格博士通过他在数学理论、计算、经济分析和工业问题应用方面的研究,对线性规划的显着发展做出了比任何其他研究人员更多的贡献,因此,他也被称之为“线性规划之父”。


他于2005年5月19日离世。

丹齐格博士


《华盛顿邮报》为其发表的讣告


先锋数学家乔治.丹齐格于 2005 年 5 月 13 日星期四去世


George B. Dantzig,90 岁,是一位数学家,他设计了一个公式,彻底改变了规划、调度、网络设计和其他现代商业、工业和政府不可或缺的复杂功能,他于 5 月 13 日在加利福尼亚州帕洛阿尔托的家中去世。

据他女儿说,死因是糖尿病和心血管疾病的并发症。

Dantzig 博士被称为线性规划之父,也是“单纯形法”(一种用于解决线性规划问题的算法)的发明者。

“他真的创造了这个领域,”运营研究软件顾问欧文·卢斯蒂格说,他是丹齐格博士在斯坦福大学的学生。

例如,Dantzig 博士的开创性工作使航空业能够安排机组人员并进行机队分配。

这是航运公司用来确定他们需要多少架飞机以及他们的送货卡车应该部署在哪里的工具。

长期以来,石油工业一直在炼油厂规划中使用线性规划,因为它决定了多少原始产品应该成为不同等级的汽油,多少应该用于石油副产品。

它用于制造、收入管理、电信、广告、建筑、电路设计和无数其他领域。

“线性编程和计算机的几乎同时发展导致了应用的爆炸式增长,尤其是在工业领域,”斯坦福大学教授 Arthur F. Veinott Jr. 在一份声明中说。“历史上第一次,管理人员获得了一种强大而实用的方法,可以制定和比较大量相互依赖的替代行动方案,以找到最佳方案。”


George Bernard Dantzig 于 1914 年出生于俄勒冈州的波特兰。他的父亲 Tobias Dantzig 是一位俄罗斯数学家,曾前往巴黎师从著名的法国数学家和科学哲学家亨利·庞加莱 (Henri Poincare)。Tobias Dantzig 与 Anja Ourisson 结婚,Anja Ourisson 也是索邦大学的一名学生,他也在学习数学,这对夫妇移民到美国。1920 年代初,丹齐格一家搬到巴尔的摩,然后又搬到华盛顿,在那里安雅丹齐格成为国会图书馆的语言学家,她的丈夫在马里兰大学教授数学。他们的儿子就读于鲍威尔初中和中央高中,在那里他对几何很着迷。他的父亲通过向他挑战复杂的几何问题来培养他的兴趣——成千上万的几何问题。Dantzig 博士于 1936 年获得马里兰大学数学和物理学学士学位,1937年获得密歇根大学数学硕士学位。

虽然他喜欢统计学,但抽象数学让他感到厌烦。他放弃了学术界,于 1937 年搬回华盛顿,并在劳工统计局工作。

1939 年,他继续在加州大学伯克利分校学习,师从数学家 Jerzy Neyman 学习统计学。他在伯克利的第一年发生的一件事成为了数学界的传奇。正如丹齐格博士多年后回忆的那样,有一天他上课迟到了,在黑板上看到两个他认为是家庭作业的问题。他把它们抄下来,带回家,几天后解决了。“这些问题似乎比平时更难解决,”他说。

六周后的一个星期天早上,兴奋的内曼敲响了他学生的前门,急切地告诉他,他解决的家庭作业问题是统计学中最著名的两个未解决的问题。“那是我第一次意识到它们有什么特别之处,”Dantzig 博士回忆道。

1941年至1946年任空军总部统计控制作战分析处文职负责人。他的任务是找到一种方法来管理“数十万种不同种类的物质商品,也许还有五万名职能人员”,这些看似棘手的问题促使他寻找一种数学模型,从而将成为线性规划。他于 1946 年从伯克利获得博士学位,并返回华盛顿,在那里他成为国防部的数学顾问,负责计划过程的自动化。

部分基于他早期在飞机供应流方面的工作,他制定了单纯形算法。1952 年,他成为兰德公司的研究数学家,并开始在计算机上实现线性规划。1960年任伯克利教授和运筹学中心主席,1966年任斯坦福大学运筹学和计算机科学教授。


他一直留在斯坦福大学,直到 1990 年代中期退休。他的开创性工作赢得了无数奖项,包括 1975年的国家科学奖章,他同时也是美国国家科学院和美国艺术与科学学院的成员。他是开创性著作“线性规划和扩展”(1963 年)的作者,并于 1997 年和 2003 年更新,他与人合著了“紧凑城市”(1973 年)。近年来,他一直在写一部科幻小说,《以他自己的形象》,讲述一场毁灭人类的瘟疫。


02 线性规划的关键要素



许多决策需要确定或推荐特定的行动方案,以在有限的资源集(例如生产投入)下产生最佳结果(例如利润最大化或成本最小化)。


因此,重要的是他们在做出此类决定时应用适当的分析技术。


线性规划是通常可以轻松应用的一种技术,以确定在这些情况下的最佳结果。


线性规划是一种数学优化形式,旨在确定使用有限资源实现给定目标的最佳方式。


线性规划问题的关键要素包括:


决策变量


在最初处理问题时,决策变量通常是未知的。这些变量通常代表管理者可以控制的可识别的“事物”或输入(即,要生产多少每种特定型号的洗衣机)。


然后,目标是确定最大化或最小化目标函数的那些值。


目标函数


这是一个数学函数,它结合了决策变量来表达管理者的目标。


管理者的目标是最大化或最小化目标函数。


约束


这些是包含决策变量以表达可能解决方案边界的数学函数。


变量边界


决策变量很少允许取任何值(从负无穷大到正无穷大)。相反,它们通常有界限(例如,≥ 0)。


还应该注意的是,虽然线性规划中目标函数和约束的所有数学表达式本质上都必须是线性的,但该技术仍然存在最广泛使用的优化方法之一,最大和最复杂的线性规划问题有数百万个决策变量和数十万个约束条件。


03 斯蒂格勒饮食问题



单纯形法是一种在极简可行解集合中寻找线性优化模型最优解的算法。


使用这种方法解决的第一个实际问题是乔治.斯蒂格勒(George Stigler)提出的饮食问题。


斯蒂格勒饮食问题最初是要解决如下问题:


斯蒂格勒饮食问题


对于一个体重154磅的适度运动的人来说,为了满足9种不同营养素的推荐摄入量,每天应该摄入77种食物中的哪些品类,食物的总成本是最低的?


这个问题包括9个约束,77个变量,在当时是一个非常复杂的问题。


由于缺乏解决此类问题的任何复杂方法,斯蒂格勒被迫使用启发式方法来找到解决方案。


他首先列出了77种可选食物的清单:



通过“反复试验、数学洞察力和敏捷性”,斯蒂格勒能够从最初的 77 种食物中剔除 62 种食物(这些食物被移除是因为与其余 15 种食物相比,它们缺乏营养)。




从简化后的清单中,斯蒂格勒计算了剩余 15 种食物中每一种所需的量,以找到解决问题的成本最低的解决方案。

斯蒂格勒 使用启发式算法计算出的最优解——年成本为 39.93 美元。


1947年,George Dantzig 发表了单纯形算法(Simplex),使得在不依赖启发式方法的情况下解决问题成为可能。


同年,美国国家标准局的Jack Laderman尝试使用单纯形法解决该问题,他找了9个办事员,使用手持式计算机足足计算了120人天,得到了39.69美元的最优解,与斯蒂格勒的结果仅仅差0.24美元。


1952年,单纯形方法在计算机上的首次实现完成了;由48个约束条件和71个变量组成的线性模型可以在18小时内求解。


如今,可以在数小时(甚至数分钟)内解决含有数百万个变量和约束的线性模型。


单纯形算法是一种有趣的“蛮力”算法。该算法以线性代数为基础,采用迭代方法,搜索可行域极值点,直到再也找不到比之前检测的极值点更好的极值点为止。


其算法可以这样简单描述:


单纯形算法利用多面体的顶点构造一个可能的解,然后沿着多面体的边走到目标函数值更高的另一个顶点,直至到达最优解为止。


如果一个线性优化模型是可行且有界的,那么它在可行区域的一个顶点上至少有一个最优解由于顶点的数量是有限的,它足以在这个简化的点集合中寻找一个最优解。


这是单纯形法所遵循的方法:


通过可行域定义的顶点集合迭代地改进目标函数。


与通过遍历多面体集合上顶点之间的边来寻找最优解的单纯形算法相反,内部点算法通过可行区域的内部移动。


下方是一个线性规划的单纯形法图解:



线性规划由于其技术的普适性和功能的强大,可以应用在几乎所有行业,解决诸多问题。


数十年来,对线性规划的研究一直在持续发展和深化,积累了无数与业务紧密结合的实例。


今天先通过一个随机选择的案例,演示如何使用Excel规划求解执行线性规划。


04 西意大战球迷运送问题



7月4日凌晨,随着欧洲杯1/4决赛最后两场比赛战罢,丹麦2-1淘汰捷克,英格兰4-0大胜乌克兰。


至此,本届欧洲杯四强全部诞生:意大利、英格兰、西班牙、丹麦。


意大利vs西班牙在北京时间7月7日凌晨3点打,比赛地点是英国伦敦的温布利球场。


以下数据为模拟:


西班牙有数万球迷打算前往伦敦为本国球队助威,西班牙本地的旅行社Travel and Transport (T&T,简称TT公司),很快就从各种包机公司手中抢到了7600个座位的使用权。


无论如何,TT公司在决定包机使用哪个机场,以及安排这些身着红色服装的球迷在伦敦的哪个机场落地方面有一定的灵活性。


他们的第一个决定是确定他们将从4个机场运送7600名球迷:从毕尔巴鄂机场、萨拉戈萨机场、马德里-巴拉哈斯机场以及塞维利亚机场。


这些球迷的居住地及人数分别为,毕尔巴鄂的750人,萨拉戈萨的2000人,马德里的4500人,塞维利亚的350人。


T&T获得了运送不超过1500人到卢顿机场的权利,运送不超过3000人到盖特威克机场的权利,并且可以运送任何数量的人到希思罗机场。


在做一些总体规划时(不是在飞机层面),由于一些法律原因,飞机尺寸等,萨拉戈萨机场和马德里-巴拉哈斯机场限制了他们可以发送到伦敦任何一个机场的最大数量。


萨拉戈萨机场最多可以运送900人到任何一个单独的机场,而马德里-巴拉哈斯机场也有类似的限制,但是上限更大——它最多可以运送2000人到任何一个单独的机场。


所以这些限制并不能阻止TT公司满足客户的需求,他们只会对运送西班牙球迷的最佳方式造成额外的限制。


TT希望在制订将7600名球迷运往伦敦的计划时将成本降至最低。


目前已知基于不同的出发机场和到达机场,每人费用分摊如下(单位:欧元):




这种情况是一个典型的运输问题,试图最优化类似从A点到B点(以及C点、D点...)的路径,一般运输问题优化的目标是使总里程最短,总用时最少,或者成本最小。


本问题的优化目标即是最小化成本地解决供需平衡问题,使运输这7600名球迷的费用最少。


具体到这个问题的Excel求解方法,过程非常简单,先搭建一个模型:




然后用Excel规划求解进行求解,得到最优方案:



该问题也可以被看作是基础的供应链优化模型的一种,因为我们正试图将球迷从目前所在的地方(供应地)最佳地运到他们需要抵达的地方(需求地)。


在日常生活和工作中,我们遇到的运输问题和供应链问题,要远远比这个示例复杂得多,但是我们从这些简单示例中学到的基础知识可以用于复杂模型的构建和优化求解。

© 2011~2015 3 北京勺海市场调查有限责任公司 | 京ICP备12031756号 | 京公网安备11010802012285号

电话:北京总部010-58696306,上海OFFICE:021-52285671    总部地址:中国北京朝阳区东三环中路建外SOHO18号楼1506室   技术支持:混沌鸿蒙