第一章 线性规划模型
??③若变量xj?0??xj?0；若变量xj无限制?令xj?x?j?xj
④若右边常数bi?0?等式两边同乘以(?1)。 例5 化下述问题为标准型
minz??x1?2x2?3x3
?x1?2x2?3x3?7??x?x?x??2?s..t?123
?3x?x?2x?53?12??x1,x3?0,x2无约束??x2??，其中x2?,x2???0；解：（1）首先考察变量：令x2?x2（2）在第一个约束不等式的左
端加入松弛变量x4；（3）对第二个约束不等式两边同时乘以(?1)并减去剩余变量x5；（4）令
z???z，则原问题化为如下标准型：
??x2??)?3x3 maxz??x1?2(x2?x1?2(x2??x2??)?3x3?x4?7???x2??)?x3?x5?2?x1?(x2s..t?
?????3x1?(x2?x2)?2x3?5?x1,x2?,x2??,x3,x4,x5?0?第二节 LP问题解的概念和性质
一、几个概念
1.可行解、最优解、基、基变量、基础解、基础可行解、退化解、基础最优解
设线性规划问题
maxz?CX (1-1)
?AX?b (1-2) s..t??X?0我们称满足约束条件(1-2)的X?(x1,x2,,xn)T为可行解。所有可行解构成可行解集，即
可行域。
使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。
设A为m?n矩阵，r(A)?m，B是A中的m?m阶非奇异子矩阵（即B?0），则称B是LP问题的一个基。
若B是LP问题的一个基，则B由m个线性无关的列向量组成，即
B?(Pr1,Pr2,
Prm)，其中Prj?(a1rj,a2rj,amrj)T，(j?1,2,6
,m)称为基向量。
第一章 线性规划模型
与基向量Prj相对应的变量xrj称为基变量，其它变量称为非基变量。显然，对应于每个基总有m个基变量，n?m个非基变量。
设B是LP问题的一个基，令其n?m个非基变量均为零，所得方程AX?b的解称为该
mLP问题的一个基础解。显然，基B与基础解是一一对应的，基础解的个数?Cn。
在基础解中，称满足非负条件的基础解为基础可行解，对应的基称为可行基。
如果基础解中非零分量的个数小于m，则称此基础解为退化的，否则是非退化的。
如果对应于基B的基础可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基础最优解。
LP问题解之间的关系如图所示：
可行解 最优解 基解 基最优解
2.凸集
若连接n维点集S中任意两点x,x的线段仍在S内，则称S为凸集。即?x,x?S，都有x??x?(1??)x?S,???[0,1]，则称S为凸集。
例如，矩形、三角形、圆、四面体等都是凸集。圆环、空心球等都不是凸集。
3.极点
若凸集S中的点x不能成为任何线段的内点，则称x为S的极点。即?x,x?S，都有
12121212x??x1?(1??)x2?S,???(0,1),则称x为S的极点。
例如，矩形、三角形、四面体的顶点，圆周上的点等都是极点。
二、线性规划问题解的性质
定理1 线性规划问题的可行域是凸集。
定理2 可行域S中的点x是极点的充分必要条件是x为基础可行解。 定理3 LP问题最优解若存在，则必可在可行域的极点上达到。
第三节 LP问题的解法
一、两个变量LP问题的图解法
LP问题图解法的步骤： （1）画出直角坐标系；
7
第一章 线性规划模型
（2）依次做每条约束直线，标出可行域的方向，并找出它们共同的可行域；
（3）任取一目标函数值作一条目标函数线（称等值线）,根据目标函数（最大或最小）类型，移该直线即将离开可行域处，则与目标函数线接触的最终点即表示最优解。
例1：用图解法求解如下线性规划问题
maxz?4x1?3x2?2x1?3x2?24 ?s..t?3x1?2x2?26?x,x?0?12最优解为 x1?6,x2?4 最优值为 maxz?36 解的几种情况：
（1）此例有唯一解Q2，即x1?6,x2?4，z?36 3x1?2x2?26 B(0,13) Q3(0,8) Q2(6,4) Q1(26/3,0) 2x1?3x2?24
A(12,0) （2）有无穷多最优解（多重解），若将目标函数改为z?4x1?6x2，则线段Q2，Q3上的点均为最优解。 （3）无界解 x2
x1 0
求max无界
但求min有唯一解 x2 (4)无可行解
x1 0
图解法只适用于两个变量（最多含三个变量）的LP问题。
二、单纯形法
m 虽然线性规划问题的可行域（凸集）的顶点数目是有限的（?Cn），在理论上，可以通过
枚举法找出所有的基可行解，然后一一进行比较，最终找出最优解，但在实际上，当n和m的值较大时，这种方法是行不通的，需要用更有效、更简便的、适合于在计算机上用通用软件求解的方法来确定最优解。单纯形法是一种既简便又有效，也适合用计算机通用软件求解线性规划问题最优解的方法。
8
第一章 线性规划模型
1. 单纯形法的基本思路：
LP问题的标准形 求出一个初始基可行解
Y 停 判别此基可行解是否 最 优 解 换基迭代 N 求出使目标函数值得到 改善的基可行解 2. 单纯形法的计算步骤（表格形式） （1）建立初始单纯形表，假定B?I,b?0 设 maxz?c1x1?c2x2??cnxn
?x1?a1m?1xm?1?...a1nxn?b1?x2?a2m?1xm?1?...a2nxn?b2?? ......?xm?amm?1xm?1?...amnxn?bm??xj?0(j?1,2,...,n)?将目标函数改写为：z?c1x1?c2x2??cnxn?0
把上述方程组和目标函数方程构成n?1个变量，m?1个方程的方程组，并写成增广矩阵的形
式：
zx1?01??00???00?1?c1?x2010?c2xm001?cmnxm?1a1,m?1a2,m?1am,m?1?cm?1xnba1nb1??a2nb2???
amnbm??cn0??m.代入z中的基变量,有
n以非基变量表示基变量xi?bi?j?m?1?amijxj，i?1,2,mnz??ci(bi?i?1mj?m?1?ax)??cxijjjj?m?1nnj??cibi??i?1i?1j?m?1?(caiij)xj?j?m?1?cxjj
9
第一章 线性规划模型
??cibi?i?1mj?m?1i?1m?(?caiinmiij?cj)xj
m令z0??cb,i?1zj??ciaij
i?1 于是z?z0?j?m?1?(zx1x210010000nj?cj)xj
因此，上述的增广矩阵就可写成：
z?0??0???0??1??xm001mxm?1a1,m?1a2,m?1am,m?10m?cai?1iim?1?cm?1??b2???
amnbm?mm?ciain?cn?cibi???i?1i?1?xna1na2nbb1再令?j?zj?cj?（B）
?cai?1iij?cj则上述增广矩阵可写成下面表格形式：即初始单纯形表T
cj XB b c1x110cm xm 0 0 cm?1cn ?i CB c1 xm?1a1m?1a2m?1xn a1n a2n x1 x2 b1 b2 c2 cm xm bm z0 01 amm?1amn z 00 ?m?1?n ,0)T
??j检验数行 上述初始单纯形表可确定初始可行基和初始基可行解：
B?(P1,P2,,Pm)?I，x?(b1,b2,,bm,0,从初始单纯形表建立的过程可以看到以下事实：
① 凡LP模型中约束条件为“≤”型，在化为标准型后必有B?I，如果b?0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数中非基变量的系数则以相反数填入检验数行各相应位置。
② 在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。
10