第一章 线性规划
为对应于基B5的一个基础解，但不是基础可行解，不是极点，而是约束直线的一个交点。这个交点就是图1.5中的点D。
对于基B6=[a3，a4]，基变量为x3，x4，非基变量为x1，x2。令非基变量x1，x2
等于0，求解线性方程组
x3
得到基变量的值
x3=2，x4=1
（x1，x2，x3，x4）=（0，0，3，1）
基变量全为非负，因而B1是可行基。
为对应于基B6的一个基础解。由于这个基础解的各变量均为非负，故这是一个基础可行解，因而对应于一个极点。这个极点就是图1.5中的极点O。
这样就得到了例1.9线性规划问题可行域的所有四个极点，只要将这四个极点的坐标分别代入目标函数，比较相应目标函数值的大小，就可以得到线性规划的最优解。
定理1.1指出了一种求解线性规划问题的可能途径，这就是先确定线性规划问题的基，如果是可行基，则计算相应的基础可行解以及相应解的目标函数值。由于基的个数是有限的（最多Cmn个），因此必定可以从有限个基础可行解中找到使目标函数为最优（极大或极小）的解。
不幸的是线性规划的基的个数是随着问题规模的增大而很快增加，以至实际上成为不可穷尽的。举例来说，一个有50个变量，20个约束等式的线性规划问题。其最多可能有
个基。
为了说明计算所有基础可行解的计算量有多大，我们假定计算一个基础可行解（即求解一个20×20的线性方程组！）只需要一秒钟，那么计算以上所有的基础可行解需要
20C50? x4
=3 =1
50!?4.7?1013 20!30!4.7?1013?1.5?106年，
3600?24?365即约150万年。
21
第一章 线性规划
很显然，借助于定理1.1来求解线性规划问题，那怕是规模不大的问题，也是不可能的。而下一章介绍的一种算法——单纯形法，可以极为有效地解决大规模的线性规划问题。
22
第一章 线性规划
§1.6 单纯形法原理
1.6.1 用消元法描述单纯形法原理
为了避免搜索可行域的所有极点，我们采用以下搜索策略（见示意图）：首先找到可行域的一个极点A。以这个极点作为起点，检查与这个极点相邻的极点。判断可行解从初始极点到一个相邻的极点移动，目标函数是否减小。如果目标函数减小，就将可行解移动到新的极点B上。继续判断可行解从极点B向与它相邻的极点
A B C D 移动时，目标函数是否减小。如果是，继续移动。依次进行。当可行解移动到某一个极点D，发现从D点向与它相邻的所有极点移动时，目标函数都不会减小，这个最后到达的极点D就是线性规划的最优解。这样的搜索策略可以极大地减少访问极点的数量。这就是单纯形法的基本思想。
单纯形法是描述可行解从可行域的一个极点沿着可行域的边界移到另一个相邻的极点时，目标函数和基变量随之变化的方法。由上一节的讨论可以知道，对于线性规划的一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。因此，可行解从一个极点到相邻极点的移动，以及移动时基变量和目标函数值的变化可以分别由基变量和目标函数用非基变量的表达式来表示。同时，当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中，所有非基变量中只有一个变量的值从0开始增加，而其他非基变量的值都保持0不变。 例1.11 用单纯形法原理求解例1.9的线性规划问题
max z= x1 +2x2 s.t.
x1 +x2 ≤3
x2 ≤1 x2 ≥0
x1,
首先将以上问题转换成标准形式。将目标函数转换成极小化，并在约束中增加松弛变量x3，x4：
min z’= -x1 -2x2 s.t.
x2
x1 +x2 +x3 x1,
x2, x3,
=3 x4 ≥0
23
+x4 =1
第一章 线性规划
第一次叠代：
步骤1、取初始可行基，x3，x4为基变量，x1，x2为非基变量。将基变量和目标函数用非基变量表出：
z’
=
-x1 -2x2
-x2
2 1 C x1=0 O 0 x2=0 1 2 A 3 x1 x3=0 B x4=0 x3
= 3 -x1 -x2
3 x2 D x4 = 1
当非基变量x1，x2=0时，相应的基变量和目标函数值为x3=3，x4=1，z’=0，得到当前的基础可行解
(x1，x2，x3，x4)=(0，0，3，1) z’=0
图 1.6
初始可行解位于极点O。图中的两个箭头分别（定性地）表示当前基变量x3和x4的大小。
步骤2、选择进基变量。在目标函数 z’=-x1-2x2
中，非基变量x1，x2的系数都是负数，因此x1，x2进基都可以使目标函数z’减小，但x2的系数为-2，绝对值比x1的系数-1大，因此x2进基可以使目标函数z’减少更快。选择x2进基，使x2的值从0开始增加，另一个非基变量x1=0保持不变。可行解从极点O向极点C移动。
步骤3、确定离基变量。在约束条件 z’
=
-x1 -2x2
-x2
x3
= 3 -x1 -x2
x4 = 1
中，由于进基变量x2在两个约束条件中的系数都是负数，当x2的值从0开始增加时，基变量x3，x4的值分别从当前的值3和1开始减少，当x2增加到1时，x4首先下降为0成为非基变量。这时，新的基变量为x3，x2，新的非基变量为x1，x4，当前的基础可行解和目标函数值为：
(x1，x2，x3，x4)=(0，1，2，0)，z’=-2
可行解移到极点C。 第二次叠代：
24
第一章 线性规划
步骤1、将当前的基变量x3，x2用当前的非基变量x1，x4表示：
x2 +x3 = 3 -x1 x2
= 1
2 -x4
3 x2 D x3=0 B x4=0 消去第一个约束中的基变量x2，得到
x3 = 2 -x1 +x4 x2
= 1
-x4
图中的两个箭头分别（定性地）表示当前的基变量x2和x3的大小。
将第二个约束x2=1-x4代入目标函数
1 C x1=0 O 0 x2=0 1 2 A 3 x1 图 1.6
z’=-x1-2x2，得到目标函数用当前非基变量表示的形式：
z’=-x1-2(1-x4)=-2-x1+2x4
步骤2、选择进基变量。在目标函数z’=-2-x1+2x4中，只有非基变量x1的值增加可以使目标函数z’减少，选择非基变量x1进基，另一个非基变量x4=0保持不变。可行解从C向B移动。
步骤3、确定离基变量。从约束条件
x3 = 2 -x1 +x4 x2
= 1
-x4
可以看出，当进基变量x1从0开始增加时，基变量x3的值从2开始减少，另一个基变量x2的值不随x1变化。当x1=2时，基变量x3=0离基，这时新的基变量为x1，x2，新的非基变量为x3，x4。当前的基础可行解为：(x1，x2，x3，x4)=(2，1，0，0)，z’=-4
这个解对应于极点B。 第三次叠代：
步骤1、将基变量x1，x2和目标函数z’分别用非基变量x3，x4表示：
x1 +x2 = 3 -x3 x2 = 1 x1
-x4
1 C x1=0 O 0 x2=0 1 2 A 3 x1 B x4=0 3 2 x2 D x3=0 消去第一个约束条件中的x2，得到
= 2 -x3 +x4
-x4
x2 = 1
量x1和x2的大小。
将以上两个基变量x1，x2代入目标函
25
图中的两个箭头分别表示当前的基变
图 1.6