第一章 线性规划（重点、难点章节）

1. 本章学习要求

(1) 应熟悉的内容

a. 预备知识：线形代数中的行变换、逆矩阵、秩、线形无关（相关）等基本概念和计算方法。

(2) 应掌握的内容

a. 单纯形法的改进 b. 大M法

(3) 应熟练掌握的内容

a. 线性规划模型（一般形式，标准形式，向量矩阵形式，一般形式转化为标准形式） b. 线性规划解的基本概念（可行解，最优解，基，基向量，基变量，非基变量，基解，基

本可行解和退化的基本可行解，可行基）

c. 基、基向量、基变量、基解之间的一一对应关系 d. 线性规划的图解 e. 单纯形法

(a) 线性规划的几何意义（可行域的凸性，顶点和基本可行解的关系）

(b) 第一判别定理（最优解的判别） (c) 单纯形表的构成 (d) 单纯形法计算

(e) 第二判别定理（无最优解的判别） f. 经济管理中的线性规划建模

g. LINDO软件的使用和EXCEL中线性规划的计算

2. 本章重点难点分析

? 重点：线性规划建模，单纯形法

? 难点：单纯形法中的换基迭代（实质是初等行变换），线性规划建模，Lindo 软件使用。

由于线性规划是运筹学的最重要的内容之一，因此有必要分别就各节的内容进行分析。

(1) 线性规划模型

a. 线性规划的一般形式

特点：目标函数和约束条件都是线性的。

b. 线性规划的标准形式及转化

在将线性规划的一般形式转化为标准形式时，要注意两点：一是某一约束条件为“≤”或“≥”形式的不等式时，应“+”一个非负松弛变量或“－” 非负松弛变量；二是某个变量不满足非负约束时，要用新变量替换，以使标准型中所有的变量均满足非负要求。下面，用一个例子予以说明。

例1 （P8例3） Min Z=x1＋2x2＋3x3

s.t. －2x1＋ x2＋ x3≤ 9

－3x1 ＋ x2＋ 2x3≥ 4 3x1 － 2x2－ 3x3＝－6

x1 ≤0, x2 ≥0, x3任意。

令x1' =－x1，则x1=－x1'（新变量替换），且x1' ≥0； 令x3 = x3' －x3”（两个新变量替换），且x3' ，x3” ≥0；

在第一和第二个不等式约束中分别引入松弛变量：x4，x5 ，且x4，x5 ≥0，

将上述线性规划的一般形式转化为标准形。

Max Z ' =x1' －2x2－3 (x3' －x3\ 2x1'＋ x2＋ (x3' －x3\x4 = 9 3x1'＋ x2＋2( x3' －x3\x5 = 4 3x1'＋ 2x2＋3 ( x3' －x3\

x1', x2 , x3', x3\x4, x5≥0 .

c. 标准形式的向量矩阵表达（P8）

由线性规划的向量矩阵形式，可以清楚地看到，线性规划模型的三要素就是资源向量b，价值向量c，系数矩阵A（一般都假设A是满秩的）。其中，资源向量b表示了稀缺资源的种类和限度；价值向量c反映了单位产品（广义）所创造的收益或形成的成本；而系数矩阵A是现有生产技术、生产工艺、管理