第一章 线性规划与单纯形法
1．线性规划问题的数学模型 (1)一般形式
(2)标准型式 ]
2．数学模型化为标准型 (1)若目标函数实现最小化，则 min z=-max z'(令z'=-z) (2)若约束方程为不等式，则 若约束方程为“≤”不等式
左端+松驰变量(≥0)=右端 若约束方程为“≥”不等式 左端-剩余变量(≥0)=右端
(3)若存在取值无约束的变量xk(1≤k≤咒)，则在标准型中 xk=x'k-x\k(其中xk=x'，x\k≥0) 3．线性规划的解 线性规划问题：
(1)可行解：满足约束条件②和③的解X=(x1，x2，…，xn)T。 (2)最优解：使目标函数①达到最大值的可行解。
(3)基：设A为约束方程组②的m×n阶系数矩阵，设n＞m，其秩为m，B为矩阵A中的一个m×m阶的满秩子矩阵，则称B为线性规划问题的一个基。不失一般性，设
B中每一个列向量Pj(j=1，2，…，m)称为基向量，与基向量PJ对应的变量xj称为基变量。除基变量以外的变量为非基变量。
山东大学 期末考试 知识点复习
(4)基本解：在约束方程组②中，令所有非基变量xm+1=xm+2=…=xn=0，此时方程组②有唯一解XB=(x1，x2，…，xm)T，将此解加上非基变量取0的值有X=(x1，x2，…，xm，0，0…，0)T，称X为线性规划问题的基本解。
(5)基本可行解：满足非负条件③的基本解。 (6)可行基：对应于基本可行解的基。 4．初始基可行解的确定
(1)直接从A中观察到存在一个初始可行基。
(2)对所有约束条件是“≤”形式的不等式，可利用化为标准型的方法，在每个约束条件左端加上一个松弛变量，这m个松弛变量就构成一个基变量，则对应的m个向量组成的单位矩阵B就是线性规划问题的一个可行基。
(3)对所有约束条件是“≥”形式的不等式以及等式约束情况，采用人造基的方法。即对不等式约束的左端减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束的左端再加上一个非负的人工变量。这些人工变量就成为基变量，则对应的列向量组成的单位矩阵B就是线性规划问题的一个可行基。
5．最优性检验
在得到初始基本可行解后，要检验一下是否为最优解。若是，则停止迭代，否则，则继续迭代，但每次迭代后都要检查一下当前解是否为最优解。有如下的判别准则：
(1)最优解判别定理：若X(0)=(b'1，b\1，…，b'm，0，0…，0)T为对应于基B的基本可行解，且对于一切j=m+1，m+2，…，n有σj≤0，则X(0)为最优解，其中σj为检验数，
(2)无穷多最优解判定理：若X(0)=(b'1，b\1，…，b'm，0，0…，0)T为一个基