线性规划发展简史

1、线性规划的发展简史1.两个重要人物利奥尼德康托洛维奇(L.V.Kantorovich, 19121986)，苏联数学家，出生于俄国圣彼得 堡的一个医生家庭.1930年毕业于列宁格勒大学,1934年成为该校最年轻的数学教授,1935年 获该校数学博士学位.19481960年任列宁格勒科学院数学所研究室主任,1958年当选为苏L.V.Kantoiovich联科学院通讯院士，并于1964年成为苏联科学院院士.19601971 年任苏联科学院西伯利亚分院数学所副所长,19711976年任苏联 国家科学技术委员会管理研究所室主任.1976年任苏联科学院系统 分析所所长.他曾于1949年获斯大林数学奖,1

2、965年获列宁经济学 奖.康托洛维奇对经济学的贡献主要在于，他建立和发展了线性规 划方法，并运用于经济分析，对现代经济应用数学的重要分支 线性规划方法的建立和发展做出了开创性贡献.他把资源最优利用 这一传统的经济学问题,由定性研究和一般的定量分析推进到现实 计量阶段,对于在企业范围内如何科学地组织生产和在国民经济范 围内怎样最优地利用资源等问题做出了独创性的研究.康托洛维奇 的主要著作包括：生产组织和计划中的数学方法(1939年)，经 济资源的最优利用(1959年)，经济最优决策(1972年，合著)，最优规划文集(1976年) 等.因在创建和发展线性规划方法以及革新、推广和发展资源最优利用理论

3、方面所做出的杰 出贡献，与美籍荷兰经济学家库恰林库普曼斯(T.C.Koopmans, 19101985) 一起分享1975 年度诺贝尔经济学奖.G.B .D antzig乔治伯纳德丹兹格(G.B.Dantzig，19142005)，美国数 学家.因创造了单纯形法，被称为“线性规划之父”他在去世之 前拥有3个院士头衔(国家科学院，国家工程院和美国科学院). 他1936年在马里兰大学科利奇帕克分校获得数学和物理学士学 位，在密歇根大学获得数学硕士学位，1946年在加利福尼亚大 学伯克利分校获得博士学位.1976年他在马里兰大学获得荣誉博 士学位.丹兹格出生在美国，他的父亲托比阿斯丹兹格是俄罗斯数

4、学家，曾在巴黎师从著名数学家亨利庞加莱(J.H.PoincarE)学习. 托比阿斯与索邦大学学生安雅乌里松结婚，他们移民美国.1939年丹兹格在伯克利作研究生.有一堂课丹兹格迟到了，上课不久，耶日内曼 (J.Neyman)教授在黑板上写了两个著名的未解统计学问题的例子.丹兹格稍后到达时把它 们当作习题抄下.按丹兹格的话，那些问题“看来比平常难了点”，不过几天后他递交了两题 的完整解答，仍以为它们是已逾期的功课.六周后心情激动的教授内曼探访丹兹格，他准备 好把丹兹格其中一题的解答递交往一份数学期刊发表多年后另一个研究者亚伯拉罕瓦尔 德(A.Wald)得到第二题的结论，要发表一份论文.他知道了丹兹

5、格之前的解答，就把丹兹 格列为合著者.第二次世界大战中断丹兹格的伯克利研究生学习.他成了美国空军管理部统计控制战斗 分析处主任，处理供应链的补给和管理成千上百的人员和物资.1946年，丹兹格获得伯克利的博士学位，仍回到美国空军管理部.丹兹格的上司伍德(M. Wood)和希奇赫克(D.Hitchock)要他解决如何使计划过程机械化的问题具体任务是：寻找一个方法能更快地计算出分时间段的调度、训练和后勤供给的方案当时计算这些问题， 都是依靠经验总结出的优先准则，而不是当成一个大系统来考虑，也没有一个明确的目标函 数.丹兹格深入研究了这个问题以后，提出了目标函数的概念，并提出了单纯形求解方法 (194

6、7年).这个方法在线性规划领域沿用多年，至今还在发挥作用.1952年他在兰德公司任研究数学家，在公司电脑上实行线性规划.1960年他被母校聘任 教授计算机科学，当上运筹学中心主任1966年他在斯坦福大学当类似职位，留在那里直到 1990年代退休.他除了线性规划和单纯形法的杰出工作，还推进很多领域的发展，有分解论、灵敏度分 析、互补主元法、大系统最优化、非线性规划和不确定规划.从1982年开始，为表彰丹兹格，国际数学规划协会设立丹兹格奖，1982年起每三年颁 给一至两位在数学规划有突出贡献的人.2005年5月13日，丹兹格因糖尿病和心血管疾病的并发症，在加利福尼亚州帕洛阿尔 托他的家中逝世，享年

7、91岁.2,线性规划发展过程中的几个重大历史事件1939年，苏联数学家康托洛维奇出版生产组织和计划中的数学方法一书1947年，美国数学家丹兹格提出了线性规划问题的单纯形求解方法1951年，美国经济学家库普曼斯(J.C.Koopmans,19101985)出版生产与配置的活 动分析一书.19501956年，线性规划的对偶理论出现.1960年，丹兹格与沃尔夫(P.Wolfe)建立大规模线性规划问题的分解算法.1975年，康托洛维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖.1978年，苏联数学家哈奇扬(L.GKhachian)提出求解线性规划问题的多项式时间算法 (内点算法)，具有重要理论意义.1984年，在美国贝尔实验室工作的印度裔数学家卡玛卡(N.Karmarkar)提出可以有效 求解实际线性规划问题的多项式