在用单纯型法求解线性规划问题之前，必须先把线性规划问题转换成增广矩阵形式。增广矩阵形式引入非负松弛变量将不等式约束变成等式约束。问题就可以写成以下形式：

Maximize

例子

以上例子的转换成增广矩阵：

maximize

subjuct to

写成矩阵形式：

Maximize Z in:

每个线性规划问题，称为原问题，都可以变换为一个对偶问题。我们可将“原问题”表达成矩阵形式：

maximize

subject to

而相应的对偶问题就可以表达成以下矩阵形式：

maximize

subject to

这里用

例子

上述线性规划例子的对偶问题：

假如有一个种植园主缺少肥料和农药，他希望同这个农夫谈判付给农夫肥料和农药的价格。可以构造一个数学模型来研究如何既使得农夫觉得有利可图肯把肥料和农药的资源卖给他，又使得自己支付的金额最少？

问题可以表述如下

假设

线性规划是最优化问题中的一个重要领域。在作业研究中所面临的许多实际问题都可以用线性规划来处理，特别是某些特殊情况，例如：网络流、多商品流量等问题，都被认为非常重要。现阶段已有大量针对线性规划算法的研究。很多最优化问题算法都可以分解为线性规划子问题，然后逐一求解。在线性规划的历史发展过程中所衍伸出的诸多概念，建立了最优化理论的核心思维，例如“对偶”、“分解”、“凸集”的重要性及其一般化等。在微观经济学和商业管理领域中，线性规划亦被大量应用于例如降低生产过程的成本等手段，最终提升产值与营收。乔治·丹齐格被认为是线性规划之父。

描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分：

一个需要极大化的线性函数，例如：

以下形式的问题约束，例如：

和非负变量，例如：

线性规划问题通常可以用矩阵形式表达成：

maximize

subject to

其他类型的问题，例如极小化问题，不同形式的约束问题，和有负变量的问题，都可以改写成其等价问题的标准型。

例子

以下是一个线性规划的例子。假设一个农夫有一块 A平方千米的农地，打算种植小麦或大麦，或是两者依某一比例混合种植。该农夫只可以使用有限数量的肥料 F 和农药 P，而单位面积的小麦和大麦都需要不同数量的肥料和农药，小麦以

max

几何上，线性约束条件的集合相当于一个凸包或凸集，叫做可行域。因为目标函数亦是线性的，所以其极值点会自动成为最值点。线性目标函数亦暗示其最优解只会在其可行域的边界点中出现。

在两种情况下线性规划问题没有最优解。其中一种是在约束条件相互矛盾的情况下（例如

另一种情况是，约束条件的多面体可以在目标函数的方向无界（例如：

除了以上两种病态的情况以外（问题通常都会受到资源的限制，如上面的例子），最优解永远都能够在多面体的顶点中取得。但最优解未必只有一个：有可能出现一组最优解，覆盖多面体的一条边、一个面、甚至是整个多面体（最后一种情况会在目标函数只能等于0的情况下出现）。

单纯形算法利用多面体的顶点构造一个可能的解，然后沿着多面体的边走到目标函数值更高的另一个顶点，直至到达最优解为止。虽然这个算法在实际上很有效率，在小心处理可能出现的“循环”的情况下，可以保证找到最优解，但它的最坏情况可以很坏：可以构筑一个线性规划问题，单纯形算法需要问题大小的指数倍的运行时间才能将之解出。事实上，有一段时期内人们曾不能确定线性规划问题是NP完全问题还是可以在多项式时间里解出的问题。

第一个在最坏情况具有多项式时间复杂度的线性规划算法在1979年由前苏联数学家Leonid Khachiyan提出。这个算法建基于非线性规划中Naum Shor发明的椭球法 (ellip-soid method)，该法又是Arkadi Nemirovski（2003年冯‧诺伊曼运筹学理论奖得主）和 D. Yudin的凸集最优化椭球法的一般化。

理论上，“椭球法”在最恶劣的情况下所需要的计算量要比“单形法”增长的缓慢，有希望用之解决超大型线性规划问题。但在实际应用上，Khachiyan的算法令人失望：一般来说，单纯形算法比它更有效率。它的重要性在于鼓励了对内点算法的研究。内点算法是针对单形法的“边界趋近”观念而改采“内部逼近”的路线，相对于只沿着可行域的边沿进行移动的单纯形算法，内点算法能够在可行域内移动。

1984年，贝尔实验室印度裔数学家卡马卡（Narendra Karmarkar）提出了投影尺度法（又名Karmarkar's algorithm）。这是第一个在理论上和实际上都表现良好的算法：它的最坏情况仅为多项式时间，且在实际问题中它比单纯形算法有显著的效率提升。自此之后，很多内点算法被提出来并进行分析。一个常见的内点算法为Mehrotra predictor-corrector method。尽管在理论上对它所知甚少，在实际应用中它却表现出色。

单形法沿着边界由一个顶点移动到“相邻”的顶点，内点算法每一步的移动考量较周详，“跨过可行解集合的内部”去逼近最佳解。当今的观点是：对于线性规划的日常应用问题而言，如果算法的实现良好，基于单纯形法和内点法的算法之间的效率没有太大差别，只有在超大型线性规划中，顶点几成天文数字，内点法有机会领先单形法。

线性规划的求解程式在各种各样的工业最优化问题里被广泛使用，例如运输网络的流量的最优化问题，其中很多都可以不太困难地被转换成线性规划问题。

线性规划理论中存在几个尚未解决的问题，这些开放问题的答案将会是数学运算中的根本突破，并且很可能是我们解决大规模线性规划问题的主要进展。

• LP存在强多项式时间算法吗？

• LP存在多项式时间算法以得到一个严格互补解吗"list-dot list-dot-paddingleft">

  LP在实数（单位成本）模型下存在多项式时间算法吗"para" label-module="para">

  这些问题已经由斯蒂芬·斯梅尔在二十一世纪十八个尚未解决的最伟大的问题中应用。用斯梅尔的话来说，“第三个问题是线性规划理论中最主要的尚未解决的问题”。然而，对于线性规划问题存在弱多项式时间算法，比如椭球算法和内点算法，尚未发现限制在约束条件个数和变量个数的强多项式时间算法，此算法的发展将会带来理论上重大意义，或者是解决大规模线性规划上的实际收益。

  线性规划问题整数规划

  要求所有的未知量都为整数的线性规划问题叫做整数规划（integer programming, IP）或整数线性规划（integer linear programming, ILP）问题。相对于即使在最坏情况下也能有效率地解出的线性规划问题，整数规划问题的最坏情况是不确定的，在某些实际情况中（有约束变量的那些）为NP困难问题。

  0-1整数规划是整数规划的特殊情况，所有的变量都要是0或1（而非任意整数）。这类问题亦被分类为NP困难问题 。

  只要求当中某几个未知数为整数的线性规划问题叫做混合整数规划（mixed integer programming, MIP）问题。这类问题通常亦被分类为NP困难问题。

  存在着几类IP和MIP的子问题，它们可以被有效率地解出，最值得注意的一类是具有完全单位模约束矩阵，和约束条件的右边全为整数的一类。

  一个解决大型整数线性规划问题的先进算法为delayed column generation。2100433B

第1章线性规划问题的数学模型

1.1线性规划问题的提出

1.2线性规划问题的标准形式与典则形式

1.3线性规划问题的解

1.4线性规划问题的对偶理论

第2章求解线性规划问题的一般方法

2.1枚举法

2.2两个变量线性规划问题的图解法

2.3单纯形法

2.4对偶单纯形法

2.5有界变量的线性规划问题求解方法

2.6其他方法

第3章定界对偶算法

3.1定界对偶算法的提出

3.2定界对偶算法的迭代方法描述

3.3定界对偶算法的正确性证明

3.4定界对偶算法求解示例

第4章特殊线性规划问题的定界对偶算法

4.1运输问题

4.2分派问题

4.3有向图的最短路问题

4.4最大流问题

4.5最小费用流问题

4.6最小树权下界问题

4.7博弈问题

4.8最大权匹配问题

4.9最大基数匹配问题

4.10计划网络图的关键路线问题

4.11装载问题

第5章定界对偶算法的灵敏度分析

5.1目标函数中常数c发生变化

5.2变量的上、下界u，v发生变化

5.3增加新约束条件的分析

第6章经典的线性规划对偶问题

6.1原材料与产品的对偶

6.2运输与贩卖的对偶

6.3关键路径与里程碑结点的对偶

6.4二人零和博弈的局中人策略的对偶

第7章整数规划问题

7.1整数规划问题的提出

7.2化为0—1型整数规划求解

7.3割平面法

7.4分枝定界法

第8章多目标规划问题

8.1多目标规划问题的提出

8.2目标规划的图解法

8.3目标规划的定界对偶算法求解示例

8.4多目标规划化为单目标规划求解

参考文献

后记2100433B

《线性规划问题的统一建模与快速算法》可作为运筹学、管理学、系统工程等专业的线性规划课程研究生教材，也可供有关专业的院校教师、研究生和大学高年级学生以及从事经济管理研究的相关人员作为参考用书。

线性规划理论在工程设计、生产管理、交通运输、国防等领域以及自然科学的很多学科中都有着广泛的应用。线性规划问题虽然是一个古老的问题，但求解线性规划问题的方法在不断发展：从单纯形法、对偶单纯形法、椭圆方法到内点方法等等。虽然线性规划有这么多解法，但是单纯形方法在其中的统治地位始终没变。对于退化线性规划问题，用单纯形方法求解时有可能产生循环，因此，研究退化线性规划问题成为人们研究线性规划问题的一个重要方面。1952年A. Charnes和W. W. Cooper给出了求解退化线性规划问题的摄动法，1954年G. B. Dantzig, A. Orden和P. Wolfe提出了求解退化线性规划问题的字典序法，1976年G. G. Bland提出了求解退化线性规划问题的Bland法则，这些方法都能避免循环发生。