线性规划的发展：从傅里叶到卡玛卡(2).docx

单位代码：11414
学 号：201 472
题目
线性计划发展：从傅立叶到卡玛卡ka卡
学院名称
专业名称
学生姓名
指导老师
起止时间： 年 月 日 至 年 月 日
摘 要
线性计划是运筹学一个关键分支，简称（LP）。它辅助大家进行科学管理，是国际应用数学、经济、计算机科学界所关注关键研究领域。
本文以时间为线，事件为体，从多个方面分析了线性计划问题及解法发展过程，具体以下：
1
2
3

关键词：线性计划；历史；单纯形法；椭球法；内点法
Linear programming of development：
from Fourier to Karmarkar
ABSTRACT
Linear programming is an important branch of operational research， referred to as "（LP）。 It assist people to scientific management， is the international applied mathematics， economics， computer science concerns one of the important research fields。
Key Words：Linear programming; History; Simplex method; Ellipsoid method; Interior-point method
目 录
摘 要 I
ABSTRACT III
前 言 3
1. 线性计划概述 3
2. 线性计划历史研究现实状况 4
3. 本文关键内容 4
第1章 线性计划问题提出及早期研究 5
傅里叶和瓦莱－普森工作 5
5
傅里叶算法线性算法提出 5
傅里叶算法线性算法和正确性 7
Fourier-Motzkin消元法及其对偶 8
Fourier-Motzkin消元法整数计划问题推广 10
康托洛维奇 11
列奥尼德·康托罗维奇介绍 11
13
丹齐克和冯·洛伊曼 14
丹齐克介绍 14
冯·洛伊曼介绍 15
1。 丹齐克和冯·洛伊曼相识 16
第2章 单纯形法提出和发展 18
2。1 图解法 18
单纯形算法发展 20
单纯形算法 20
丹齐克单纯形法运输问题应用 22
2。5 50年代后对线性计划进行大量理论研究，一大批新算法 24
对偶单纯形法 24
灵敏度分析和参数计划问题 24
互补松弛定理 25
分解算法 25
其它学科研究 25
第3章 椭球法和内点法发展 26
Klee例子 26
哈奇杨算法（椭球法） 26
Smale 对单纯法提出新见解： 29
卡玛卡（N·Karmarkar）多项式算法（内点法） 29
三种解法比较 31
第4章 线性计划在经济分析中应用 33
生产和优化 33
平衡和互补松弛 36
线性计划发展和经济学家作用 36
线性计划在经济计划使用 38
计划模型和信息传输 40
均衡模型 41
附言 42
结 论 43
参 考 文 献 44
前 言
1. 线性计划概述
线性计划关键研究有限资源最好分配问题，即怎样对有限资源进行最好地调配和最有利地使用，方便最充足发挥资源效能来获取最好经济效益。
线性计划利用数学语言描述一些经济活动过程，形成数学模型，以一定算法对模型进行计算，为制订最优计划方案提供依据。其处理问题关键是建立符合实际情况数学模型，即线性计划模型。在多种经济活动中，常采取线性计划模型进行科学、定量分析，安排生产组织和计划，实现人力物力资源最优配置，取得最好经济效益。现在，线性计划模型被广泛应用和经济管理、交通运输、工农业生产等领域。
简单说，线性计划是研究线性最优化问题。通常地，线性计划数学模型以下：
其中、是维向量，是维向量，是矩阵。上式表明，线性计划就是在满足线性不等式范围内