0
2
x1
x2
4
(4)无可行解（约束条件有矛盾） 如：
0 x1 x2
结论： ①约束集合一定是凸条边形（二维）； ②若有最优解，则一定可在多边形顶点获得。
§3单纯形法
单纯形法的基本思路是：根据问题的标准，从可行域中某个基本可行 解（一个顶点）开始，转换到另一个基本可行解（顶点）；并且使目标 函数达到最大值时，问题就得到了最优解。即 初始顶点(可行域一顶点)…
那么，约束方程 即 --------有无穷解
令则 那么，约束方程组的解 ，将其称为问题的基本解。 注意：基本解不一定是可行解，若,则称为问题的基本可行解，对应于 基本可行解的基矩阵，称为可行基。
4、最优解：对应于某一可行基，使目标函数获得最优值的基本可行 解，称为最优解。最优解所对应的基矩阵称为最优基。
最优解，最优值 2、两阶段法 前面介绍了大M法，但在电子计算机求解含有人工变量的线性规划 问题时，只能用很大的数代替M，这就可能造成计算上的错误。故再介 绍两阶段法。 第一阶段：不考虑原问题是否存在基可行解；给原问题加入人工变 量，并构成仅含人工变量的目标函数和要求实现最小化，然后用单纯形 法求解上述模型，若得到，这说明原问题存在基可行解，可以进行第二 阶段计算。否则，原问题无可行解，应停止计算。 第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标 函数行的系数换为原问题的目标函数系数，作为第二阶段计算的初始 表。 例6 试用两阶段法求解。
如果为最优解，则最优值为 判断定理：（对标准型maxZ来讲） （1）若所有，则为最优解。 （2）若所有,且有某个，则LP问题有无穷多个最优解。 （3）若有某个，则不是最优解。 （4）当时，若有一个，且对一切都有,则有无界解(或无最优解)。
3、基变换：确定新的基矩阵的过程
（1）换入变量的确定 选择中的最大者所对应的变量作为换入变量，即
为（-M）（M为任意大的正数），这样目标函数实现最大化时，必需把
人工变量换出。 例5 试用大M法求解 解：化为标准型
CB XB b
3 -1 -1 0 0 -M -M x1 x2 x3 x4 x5 x6 x7
0 x4 11
1 -2 1 1 0 0 0
11
-M x6 3
-4 1 2 0 -1 1 0
3/2
单纯形法计算中用规划确定换出变量时，有时存在两个以上相同的 最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出 现了退化解，当出现退化时，进行多次迭代，而基从，又返回到，即出 现计算过程的循环，使永远达不到最优解。为解决这个问题我们介绍勃 兰特规则：
（1）当存在两个或两个以上最大检验数时，选取中下标最小的非基
0 x4 12
3 0 0 1 -2
4
-1 x2 1
0 1 0 0 -1
-
-1 x3 1
-2 0 1 0 0
-
1
-1
3 x1 4
1 0 0 1/3 -2/3
-
-1 x2 1
0 1 0 0 -1
1
-1 x3 1
0 0 1 2/3 -4/3
-
-1/3 -1/3 原问题的最优解为：,最优值为
二、退化（极少出现）
§1 线性规划的数学模型及解的性质
一、数学模型（一般形式）
例1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及 可用的资源限量如下表，问不同体系的面积应各建多少，才能使提供的 住宅面积总数达到最大？
造价
钢材
水源
砖(块/m2) 人工（工
（元/m2） （kg/m2） （kg/m2）
日/m2）
砖混结 构 大板结 构 大模结 构 资源限 量
解：第一阶段：
CB XB b
00 000 1 1 x1 x2 x3 x4 x5 x6 x7
0 x4 11
1 -2 1 1 0 0 0
11
1 x6 3
-4 1 2 0 -1 1 0
3/2
1 x7 1
-2 0 [1] 0 0 0 1
1
6 -1 -3 1
0 x4 10
3 -2 0 0 0 0 -1
-
1 x6 1
举例说明：
约束矩阵 若取基矩阵 则非基矩阵 基变量,非基变量
∴基本解为 是基本可行解 若取基矩阵 则
-----基本可行解 注意：基本可行解与可行域的顶点坐标是一一对应的。
§2 图解法---主要解决二维线性规划问题
一、按约束条件，绘出解的可行域图形
(20,24) 0
90
40 50
100 x1
40 x2
二、标准型
（一）问题的标准形式：
其中 注意：任何一个一般型都可转化为一个标准型。
（二）标准型的表示方法：
1、和式形式：
2、矩阵形式：
其中 -------价格系数向量 -------资源向量（限定系数向量） -----------约束条件系数矩阵 --------决策变量
3、向量形式：
其中 为约束条件系数矩阵A的第j列。
变量为换入变量，即； （2）当按规则计算时，存在两个或两个以上最小比值时，选取下标
最小的基变量为换出变量。
三、单纯形法小结
类型
Max
min
检验数
判别
一切，最优
一切，最优
确定进基变量
确定出基变量
有唯一最优解
一切
一切
则 注意：松驰变量、剩余变量的价值系数取为0，而人工变量的价值系数 取值为大M。
2、检验 基本可行解 对应的目标函数值
对任意可行解 变化为 即 将其代入目标函数得：
非基变量价值系数 基变量价值系数
当时，的最大值是 即为最优解。 这里，我们称每个为检验数。 当 检验数
第个基变量的价格系数 第个非基变量的价格系数
（三）一般型化为标准型的方法
1、 引进新的目标函数, 则可化为
2、不等式约束
① 引进新的非负决策变量, 使得
称为松弛变量，在目标函数中，其价格系数为0。 ② 引进新的非负决策变量,使得 称为剩余变量，在目标函数中，其价格系数为0。 3、若，即
可变为 4、若某个变量无非负限制，称为自由变量。 令
例3 将下列问题化为标准型 解：标准型为
3.4
–1.2
0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16
-1.36 -0.52
90 40 30
30.77 20 100
§4单纯形法的进一步讨论
一、人工变量法
1、大M法
在一个线性规划问题的约束条件中加入人工变量后，要求人工变量
对结目标函数值不受影响，为此我们假定人工变量在目标函数中的系数
例：（按上例） 解：
7 12 0 0 0
0 360 0 200 0 300
0 240 0 50 12 30
0 84 7 20 12 24
最优解为 最优值为
9 4 10 0 4 5 01 0 3 [10] 0 0 1
7 12
7.8 0 1 0 -0.4 [2.5] 0 0 1 -0.5 0.3 1 0 0 0.1
②存在一定的约束条件，这些约束条件可以用一组线性等式或不等 式来表示。
③都有一个要求达到的目标，它可用决策变量的线性函数（称为目 标函数）来表示；按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为线性规划的数学模型。其一般形 式为：
目标函数 约束条件 可行解：满足约束条件的一组决策变量，称为可行解。 最优解：使目标函数取得最大（小）值的可行解，称为最优解。 最优值：目标函数的最大（小）值，称为最优值。
二、单纯形表：（将上述过程列成表格,便于理解）
对每一个可行基，作一个单纯形表，包括①基可行解②检验数③和 主元素。
…… …… 10 … 0 … 0 1 …0 …
0 0…0 …
列中填入基变量，这里是 列中填入基变量的价值系数，与基变量一一对应，这里是 列中填入约束方程组右端的常数； 行中填入各变量的价值系数 列的数字是在确定换入变量后，按规则计算出来的比值； 行为检验数行，对应各非基变量的检验数。
0 [1] 0 0 -1 1 -2
1
0 x3 1
-2 0 1 0 0 0 1
-
0 -1
13
0 x4 12 0 x2 1 0 x3 1
[3] 0 0 1 -2 2 -5 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 1
0
01 1
最优解为 第二阶段：
CB XB b
3 -1 -1 0 0 x1 x2 x3 x4 x5
≤ ≤≤ ≤
一、单纯形法的求解步骤
（1）寻找初始可行基,并计算初始基本可行解； （2）检验基本可行解是否最优； （3）寻找更好的可得基； （4）重复（2），（3）。
1、初始可行基的确定 i)若A中含有阶单位矩阵,则取。此时， 是可行基
ii)若中不含有m阶单位矩阵，就采用人造基的方法。即增加人工变 量把原问题化为含有的等价问题。（下一节重点讲） 例： 因为系数数阵A中不含有单位矩阵，需增加人工变量化为
（2）换出变量的确定：用最小比值规则（θ规则）
设
则取为换出变量 当时， 则取为换出变量，称为主元素 （3）新基矩阵的确定
如： 解： 取初始基矩阵 那么 基可行解 检验数： 不是最优解，换入变量为
换出变量为（基变量中的第3个变量），主元素为 增广矩阵变换：
新的基矩阵 新基可行解 检验数：
不是最优解。
105
12
110
210
137
30
190
122
25
180
11000万元 2000万千克 15000万块 14700万块