第1章 线性规划
Chapter 1 Linear Programming 本章内容提要
线性规划是运筹学的重要内容。本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法。
学习本章要求掌握以下内容： ? 线性规划模型的结构
? 线性规划的标准形式，非标准形式转化为标准形式
? 线性规划的图解以及相应的概念。包括：约束直线，可行半空间，可行解，
可行域，凸集，极点，目标函数等值线，最优解
? 线性规划的基本概念。包括：基，基础解，基础可行解，基变量，非基变
量，进基变量，离基变量，基变换
? 单纯形法原理。包括：基变量和目标函数用非基变量表出，检验数，选择
进基变量的原则，确定离基变量的方法，主元，旋转运算 ? 单纯形表。包括初始单纯形表的构成，单纯形表运算方法 ? 初始基础可行解，两阶段法 ? 退化的基础可行解
§1.1 运筹学和线性规划
1.1.1 运筹学
运筹学（Operations Research）是二十世纪三十年代二次大战期间由于战争的需要发展起来的一门学科。当时，英国组织了一批自然科学和工程科学的学者，和军队指挥员一起，研究大规模战争提出的一些问题。如轰炸战术的评价和改进、反潜艇作战研究等，研究结果在战争实践中取得了明显得效果。这些研究当时在英国称为Operational Research，直译为作战研究。战争结束以后，这些研究方法不断发展完善，并逐步形成学科理论体系，其中一些主要的理论和方法包括：线性规划，网
1
第一章 线性规划
络流，整数规划，动态规划，非线性规划，排队论，决策分析，对策论，计算机模拟等。这些理论和方法在经济管理领域也得到了广泛应用，Operations Research也转义成为“作业研究”。我国将Operations Research译成“运筹学”，非常贴切地将Operations Research这一英文术语所包含的作战研究和作业研究两方面的涵义都体现了出来。
现在，运筹学已经成为管理科学重要的基础理论和应用方法，是管理科学专业基本的必修课程之一。
1.1.2 线性规划
线性规划是运筹学中最重要的一种系统优化方法。它的理论和算法已十分成熟，应用领域十分广泛，包括生产计划，物资调运，资源优化配置，物料配方，任务分配，经济规划等问题。随着计算机硬件和软件技术的发展，目前用微型计算机就可以求解变量个数达106，约束个数达104的巨大规模的问题，并且计算时间也不太长。
线性规划问题最早是前苏联学者康德洛维奇（L.V. Kantorovich）于1939年提出的，但他的工作当时并未广为人知。第二次世界大战中，美国空军的一个研究小组SCOOP（Scientific Computation of Optimum Programs）在研究战时稀缺资源的最优化分配这一问题时，提出了线性规划问题。并且由丹泽（G.B.Dantzig）于1947年提出了求解线性规划问题的单纯形法。单纯形法至今还是求解线性规划最有效的方法。50年代初，电子计算机研制成功，较大规模的线性规划问题的计算已经成为可能。因此，线性规划和单纯形法受到数学家、经济学家和计算机工作者的重视，得到迅速发展，很快发展成一门完整的学科并得到广泛的应用。1952年，美国国家标准局（NBS）在当时的SEAC电子计算机上首次实现单纯形算法。1976年IBM研制成功功能十分强大、计算效率极高的线性规划软件MPS，后来又发展成为更为完善的MPSX。这些软件的研制成功，为线性规划的实际应用提供了强有力的工具。
在本章中，我们将介绍线性规划的基本概念，单纯形法的基本原理及线性规划在经济分析中的应用。对计算方法和计算机软件应用方面的问题，可参阅有关文献及讲义后面的附录。
2
第一章 线性规划
§1.2 线性规划问题
根据实际问题的要求，可以建立线性规划问题数学模型。线性规划问题由目标函数、约束条件以及变量的非负约束三部分组成。下面列举五种最常见的线性规划问题的类型。
1.2.1 生产计划问题
例1.1 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：
表 1-1
每件产品占用的 产品甲 机时数（小时/件） 设备A 设备B 设备C 利润（元/件） 1.5 1.0 1.5 5.24 产品乙 1.0 5.0 3.0 7.30 产品丙 2.4 1.0 3.5 8.34 产品丁 1.0 3.5 1.0 4.18 设备能力 （小时） 2000 8000 5000 用线性规划制订使总利润最大的生产计划。
设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：
max z= 5.24x1 +7.30x2 +8.34x3 +4.18x4
s.t.
利润最大化
设备的利用 时间不超过 设备能力
1.5x1 +1.0x2 +2.4x3 +1.0x4 ≤2000 1.0x1 +5.0x2 +1.0x3 +3.5x4 ≤8000 1.5x1 +3.0x2 +3.5x3 +1.0x4 ≤5000
x1,
x2,
x3,
x4
≥0 产品产量非负
这是一个典型的利润最大化的生产计划问题。其中max表示极大化（maximize），s.t.是subject to的缩写。求解这个线性规划，可以得到最优解为：
x1=294.12
x2=1500
x3=0
x4=58.82 （件）
最大利润为
z=12737.06（元）
请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很
3
第一章 线性规划
多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。
1.2.2 配料问题
例1.2 某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：
表 1-2
Cr Mn Ni 单价(元/公斤) T1 3.21 2.04 5.82 115 T2 4.53 1.12 3.06 97 T3 2.19 3.57 4.27 82 T4 1.76 4.33 2.73 76 G 3.20 2.10 4.30 设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，使成本最小。
设选用原料T1，T2，T3和T4分别为x1，x2，x3，x4公斤，根据条件，可建立相应的线性规划模型如下：
min z= s.t.
115x1
+97x2
+82x3
+76x4
0.0321x1 +0.0453x2 +0.0219x3 +0.0176x4 ≥3.20 0.0204x1 +0.0112x2 +0.0357x3 +0.0433x4 ≥2.10 0.0582x1 +0.0306x2 +0.0427x3 +0.0273x4 ≥4.30
x1 x1,
+x2 x2,
+x3 x3,
+x4 =100 x4
≥0
这是一个典型的成本最小化的问题。其中min表示极小化（minimize）。这个线性规划问题的最优解是
x1=26.58
x2=31.57
x3=41.84
x4=0
（公斤）
最低成本为 z=9549.87（元）
1.2.3 背包问题
例1.3 一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：
4
第一章 线性规划
表 1-3
重量（公斤/件） 价值（元/件） 物品1 物品2 物品3 10 17 41 72 20 35 要在背包中装入这三种物品各多少件，使背包中的物品价值最高。
设装入物品1，物品2和物品3各为x1，x2，x3件，由于物品的件数必须是整数，因此背包问题的线性规划模型是一个整数规划问题：
max s.t.
z=17x1 10x1
+72x2 +41x2
+35x3
+20x3 ≤50
x1, x2, x3 ≥0, x1, x2, x3是整数
这个问题的最优解是：x1=1件, x2=0件, x3=2件, 最高价值为：z=87元
1.2.4 运输问题
例1.4 设某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地的单位物资运价如下表所示。
表 1-4
运价（元/吨） A1 A2 需求量（吨） B1 B2 B3 供应量（吨） 2 4 10 3 7 30 5 8 20 35 25 这个问题也可以用图解表示如下，其中节点A1、A2表示发地，节点B1、B2、
B110吨 2 35吨 A1 3 5 4 25吨 A2 7 8 B3 20吨 B2 30吨
图 1.1 B3表示收地，从每一发地到每一收地都有相应的运输路线，共有6条不同的运输路线。
5