《运筹学思想方法及应用》线性规划发展简史.doc

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

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

3、T.C.Koopmans, 19101985)一起分享1975年度诺贝尔经济学奖.乔治伯纳德丹兹格（G.B.Dantzig，19142005），美国数学家. 因创造了单纯形法，被称为“线性规划之父”. 他在去世之前拥有3个院士头衔(国家科学院，国家工程院和美国科学院). 他1936年在马里兰大学科利奇帕克分校获得数学和物理学士学位，在密歇根大学获得数学硕士学位，1946年在加利福尼亚大学伯克利分校获得博士学位.1976年他在马里兰大学获得荣誉博士学位. 丹兹格出生在美国，他的父亲托比阿斯丹兹格是俄罗斯数学家，曾在巴黎师从著名数学家亨利庞加莱(J.H.Poincar)学习.托比阿斯与索邦大学学生

4、安雅乌里松结婚，他们移民美国. 1939年丹兹格在伯克利作研究生.有一堂课丹兹格迟到了，上课不久，耶日內曼（J.Neyman）教授在黑板上写了两个著名的未解统计学问题的例子. 丹兹格稍后到达时把它们当作习题抄下.按丹兹格的话，那些问题“看来比平常难了点”，不过几天后他递交了两题的完整解答，仍以为它们是已逾期的功课.六周后心情激动的教授內曼探访丹兹格，他准备好把丹兹格其中一题的解答递交往一份数学期刊发表. 多年后另一个研究者亚伯拉罕瓦尔德（A.Wald）得到第二题的结论，要发表一份论文.他知道了丹兹格之前的解答，就把丹兹格列为合著者.第二次世界大战中断丹兹格的伯克利研究生学习.他成了美国空军管理

5、部统计控制战斗分析处主任，处理供应链的补给和管理成千上百的人员和物资. 1946年，丹兹格获得伯克利的博士学位，仍回到美国空军管理部. 丹兹格的上司伍德（M.ood）和希奇赫克（D.Hitchock）要他解决如何使计划过程机械化的问题. 具体任务是：寻找一个方法能更快地计算出分时间段的调度、训练和后勤供给的方案.当时计算这些问题，都是依靠经验总结出的优先准则，而不是当成一个大系统来考虑，也没有一个明确的目标函数.丹兹格深入研究了这个问题以后，提出了目标函数的概念，并提出了单纯形求解方法(1947年).这个方法在线性规划领域沿用多年，至今还在发挥作用. 1952年他在兰德公司任研究数学家，在公司

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

7、的数学方法一书.1947年，美国数学家丹兹格提出了线性规划问题的单纯形求解方法.1951年，美国经济学家库普曼斯（J.C.Koopmans,19101985）出版生产与配置的活动分析一书.19501956年，线性规划的对偶理论出现.1960年，丹兹格与沃尔夫（P.Wolfe）建立大规模线性规划问题的分解算法.1975年，康托洛维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖.1978年，苏联数学家哈奇扬（L.G.Khachian）提出求解线性规划问题的多项式时间算法（内点算法），具有重要理论意义.1984年，在美国贝尔实验室工作的印度裔数学家卡玛卡（N.Karmarkar）提出可以有效求解实际线性规划问题的多项式时间算法Karmarkar算法.线性规划的基本点就是在满足一定约束条件下，使预定的目标达到最优. 现在线性规划已不仅仅是一种数学理论和方法，而且成了现代化管理的重要手段，是帮助管理者与经营者做出科学决策的一个有效的数学技术.