文档介绍：?线性规划的简介和应用举例?线性规划的数学模型和图解法?线性规划的基本概念和基本性质?单纯形法?关于单纯形法的说明和补充?线性规划的对偶理论与对偶单纯形法第第5 5章章线性规划线性规划?线性规划就是一个线性函数在线性等式或不等式约束条件下的极值问题, 是最简单的约束优化问题?理论最为成熟、应用最为广泛的一种数学规划方法?运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支?广泛应用于军事作战、经济分析、经营管理和工程技术等方面?为合理地利用有限的人力、物力、财力等资源作出最优决策,提供科学的依据。线性规划的概述线性规划的概述?法国数学家傅里叶和瓦莱-普森分别于 1832 和1911 年独立地提出线性规划的想法,但未引起注意。?1939 年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视。?1947 年美国数学家 . 丹齐格提出线性规划的一般数学模型和求解线性规划问题的通用方法--单纯形法,为这门学科奠定了基础。?1947 年美国数学家 诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力。?1951 年美国经济学家 . 库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获 1975 年诺贝尔经济学奖。线性规划的发展线性规划的发展 50 年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法。例如?1954 年, ?1954 年, ?1956 年, ?1960 年 . 丹齐格和 1979 年苏联数学家哈奇扬提出解线性规划问题的椭球算法,并证明它是多项式时间算法。线性规划的发展线性规划的发展 1984 年美国贝尔电话实验室的印度数学家卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为 5000 时只要单纯形法所用时间的 1/50 。现已形成线性规划多项式算法理论。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展,出现了许多线性规划软件,如 MPSX , OPHEIE , UMPIRE 等,可以很方便地求解几千个变量的线性规划问题。线性规划的发展线性规划的发展线性规划通常解决下列两类问题: 线性规划通常解决下列两类问题: ⑴当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标(2) 在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大) 线性规划问题的数学模型线性规划问题的数学模型例例某企业计划生产甲、乙两种产品。这些产品分别要在 A、 B、C、D四种不同的设备上加工。按工艺资料规定,单件产品在不同设备上加工所需要的台时如下表所示,企业决策者应如何安排生产计划,使企业总的利润最大? 设备产品 A B C D 利润(元) 甲 2 1 4 0 2 乙 2 2 0 4 3 有效台时 12 8 16 12 线性规划问题的应用线性规划问题的应用??解: 解: 设x 1、x 2分别为甲、乙两种产品的产量,则数学模型为: 线性规划问题的应用线性规划问题的应用 1 2 1 2 1 2 12 1 2 2 3 . . 2 2 12 2 8 4 16 4 12 , 0 max z x x s t x x x x xx x x ? ?? ?? ????目标函数: 约束条件: 线性规划数学模型的一般形式? ???? ???????? ?????????? ????????? 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1 2 ( ) ... (1) ... ( , ) ... ( , ) ... (2) ... ( , ) , , ..., 0 n n n n n n m m mn n m n min max z c x c x c x a x a x a x b a x a x a x b a x a x a x b x x x 线性规划问题的数学模型线性规划问题的数学模型目标函数: 约束