第五章+线性规划方法.ppt

第五章 线性规划 本章主要内容 关于线性规划的发展简史 两个重要人物 几个重大历史事件 利奥尼德·康托洛维奇(L.V.Kantorovich) 利奥尼德·康托洛维奇(L.V.Kantorovich, 1912—1986) ，苏联数学家，1930年毕业于列宁格勒大学,1934年成为该校最年轻的数学教授,1935年获该校数学博士学位.1948—1960年任列宁格勒科学院数学所研究室主任,1958年当选为苏联科学院通讯院士,并于1964年成为苏联科学院院士.1960—1971年任苏联科学院西伯利亚分院数学所副所长,1971—1976年任苏联国家科学技术委员会管理研究所室主任.1976年任苏联科学院系统分析所所长.他曾于1949年获斯大林数学奖,1965年获列宁经济学奖.康托洛维奇对经济学的贡献主要在于,他建立和发展了线性规划方法,并运用于经济分析,对现代经济应用数学的重要分支——线性规划方法的建立和发展做出了开创性贡献.他把资源最优利用这一传统的经济学问题,由定性研究和一般的定量分析推进到现实计量阶段,对于在企业范围内如何科学地组织生产和在国民经济范围内怎样最优地利用资源等问题做出了独创性的研究.康托洛维奇的主要著作包括:《生产组织和计划中的数学方法》(1939年),《经济资源的最优利用》(1959年),《经济最优决策》(1972年,合著),《最优规划文集》(1976年)等.因在创建和发展线性规划方法以及革新、推广和发展资源最优利用理论方面所做出的杰出贡献，与美籍荷兰经济学家库恰林·库普曼斯(T.C.Koopmans, 1910—1985)一起分享1975年度诺贝尔经济学奖. 乔治?伯纳德?丹兹格（G.B.Dantzig） 乔治?伯纳德?丹兹格（G.B.Dantzig，1914—2005），美国数学家. 因创造了单纯形法，被称为“线性规划之父”. 他在去世之前拥有3个院士头衔(国家科学院，国家工程院和美国科学院). 他1936年在马里兰大学科利奇帕克分校获得数学和物理学士学位，在密歇根大学获得数学硕士学位，1946年在加利福尼亚大学伯克利分校获得博士学位，仍回到美国空军管理部. 丹兹格的上司伍德（M.Ｗood）和希奇赫克（D.Hitchock）要他解决如何使计划过程机械化的问题. 具体任务是：寻找一个方法能更快地计算出分时间段的调度、训练和后勤供给的方案.当时计算这些问题，都是依靠经验总结出的优先准则，而不是当成一个大系统来考虑，也没有一个明确的目标函数.丹兹格深入研究了这个问题以后，提出了目标函数的概念，并提出了单纯形求解方法(1947年).这个方法在线性规划领域沿用多年，至今还在发挥作用.1952年他在兰德公司任研究数学家，在公司电脑上实行线性规划.1960年他被母校聘任教授计算机科学，当上运筹学中心主任. 1966年他在斯坦福大学当类似职位，留在那里直到1990年代退休. 他除了线性规划和单纯形法的杰出工作，还推进很多领域的发展，有分解论、灵敏度分析、互补主元法、大系统最优化、非线性规划和不确定规划. 从1982年开始，为表彰丹兹格，国际数学规划协会设立丹兹格奖，1982年起每三年颁给一至两位在数学规划有突出贡献的人. 几个重大历史事件 1939年，苏联数学家康托洛维奇出版《生产组织和计划中的数学方法》一书. 1947年，美国数学家丹兹格提出了线性规划问题的单纯形求解方法. 1951年，美国经济学家库普曼斯（J.C.Koopmans,1910—1985）出版《生产与配置的活动分析》一书. 1950～1956年，线性规划的对偶理论出现. 1960年，丹兹格与沃尔夫（P.Wolfe）建立大规模线性规划问题的分解算法. 1975年，康托洛维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖. 1978年，苏联数学家哈奇扬（L.G.Khachian）提出求解线性规划问题的多项式时间算法（内点算法），具有重要理论意义. 1984年，在美国贝尔实验室工作的印度裔数学家卡玛卡（N.Karmarkar）提出可以有效求解实际线性规划问题的多项式时间算法——Karmarkar算法. 第1节 线性规划及其单纯形求解方法 线性规划的数学模型 线性规划的标准形式及方法 线性规划的解及其性质 线性规划问题的求解方法——单纯形法 应用实例: 农场种植计划模型 一、线性规划的数学模型 （一）线性规划模型 线性规划研究的两类问题： 某项任务确定后，如何统筹安排，以最少的人力、物力和财力去完成该项任务； 面对一定数量的人力、物力和财力资源，如何安排使用，使得完成的任务最多。它们都属于最优规划的范畴。 以下为一些实例。 设xij表示由产地i供给销地j