线性规划

　　线性规划（汉语拼音：Xianxing Guihua；英语：Linear Programming）， 数学规划中理论成熟、方法有效、应用最广的一个分支和基础，它主要研究线性目标函数在线性约束条件下的极值问题。

　　线性规划始于20世纪30年代，1939年苏联数学家L.V.坎托罗维奇为解决生产组织中的一系列问题，如机器负荷分配、原材料的合理利用等等，发表了《生产组织与计划中的数学方法》等论文，这是世界上最早研究线性规划的文章 。从40年代到50年代中期，美国由于军事和生产的需要迅速地发展了这一分支，1947年美国空军数学顾问G.B.丹齐克首次提出线性规划的概念，建立了线性规划的数学模型，并且提出求解线性规划的单纯形法，从而奠定了它的理论基础 ，也为用计算机求解线性规划问题提供了依据。此后 ，冯.诺依曼创立了线性规划的对偶理论，开辟了线性规划的许多新的研究领域，同时也加强并扩大了它的应用范围和解题能力，从此线性规划理论日趋成熟。与此同时由于电子计算机的发展，使用电子计算机处理成千上万个约束条件和决策变量的线性规划取得成功，线性规划的应用范围更加广阔，从解决技术问题的最优设计到工业、农业、商业、交通运输、军事、经济、管理决策等众多领域都可以发挥作用。

　　线性规划的基本假设是对于具有比例性、可加性和非负性的活动现象，都可以归结为线性规划问题来解决。如果使用经济学的语言，比例性是指活动所使用的资源以及对目标函数的作用与活动的水平成比例；可加性表示所有活动使用的资源数是各个活动分别使用资源的总和，对目标函数也有类似的解释；非负性表示没有哪一个活动水平是负的。实际中大量问题基本上都能符合以上的基本假设，因此应用范围是非常广阔的。

　　满足线性规划约束条件的解称为可行解，这些解的存在范围称为可行域；使得目标函数达到最优值的可行解称为最优解。根据线性规划理论，线性规划的可行域是一个凸多面体，如果最优解存在，一定在这个多面体的某些顶点达到。多面体的顶点也称作基本可行解，因为顶点的个数是有限的，这就为求解线性规划提供了一种途径和依据，人们总可以从中找到最优解。单纯形法的基本思路就是首先从可行域中任取一个顶点x作为关注点（基本可行解），再把当前的关注点x与它相邻的顶点作比较，如果某个相邻顶点比x更优，就把关注点从x转移到，使目标函数值得到改善，重复上述步骤直到所关注的顶点x*为最优解为止。1976年进一步证明了只要采取一定的技术措施，就可以避免迭代过程可能出现的死循环现象，从而经有限步迭代计算一定可以求得最优解。

　　对偶理论是线性规划的又一重要内容，每一个线性规划都有一个“影像”，这个影像是一个伴生的线性规划，称作原线性规划（LP）的对偶规划（LD）。例如一个原始规划是求一个生产计划表，使得在一定劳动力和原材料消耗下所用成本最小，则它的对偶问题是要确定一个价格系统，即当平衡了劳动力和原材料的直接成本后，使产品价值最大。考虑原问题和对偶问题给决策者另一自由度，即除了研究怎样使用机器以取得最大利润外，它们还能告诉人们怎样通过安装更多的机器来增加利润。它反映了同一问题的两种不同提法。所以它们应具有相同的最优解。基于对偶理论，创立了对偶单纯形法，从而增强了单纯形法的解题能力。

　　线性规划的另一研究方向是考察模型的某些参数发生变化时对解的影响，这是决策管理人员十分关心的问题，这个问题的讨论涉及灵敏度分析和参数规划的内容。

　　分解算法是分治策略的一种应用，它把一个大型的线性规划问题分解成若干子问题，通过求解子问题导出原问题的解。这一技术在求解整数规划时也有用处。

　　求解线性规划的单纯形算法，虽然在实际应用上一直很成功。但是从运算量角度观看，它还不是一个多项式算法。1979年苏联数学家L.G.哈奇扬和印度数学家N.卡玛卡先后从理论上和实际上证明并提出两种运算次数少于单纯形算法的多项式算法。不过，只有当变量个数足够多时，卡玛卡算法的优点才能体现出来，因此单纯形法仍是求解线性规划最成功的通用算法。