1、线性规划 Linear Programming（ LP）基本理论u 线性规划的标准型u 定义： max z = c1x1 + c2x2 + + cnxnu a11x1 + a12x2 + a 1nxn = b1u a21x1 + a22x2 + a 2nxn = b2u s. t. 其中 bj 0， j =（ 1， 2， n ） u am1x1 + am2x2 + amnxn = bmu xj 0 （ j=1， 2 n ）u 将一般线性规划问题化为标准型u 1、 maxminu 2、 不等式约束 等式约束u 3、自由变量（无非负约束） xj0 （ 非负约束）u 注意：以上转化是等价的，即转化后
2、的标准型与原线性规划问题同 解1线性规划 Linear Programming（ LP）基本理论u 可行解 满足所有约束条件的向量 X =（ x1， x2， ， xn） T u 可行域 全部可行解的集合u 最优解 使目标函数达到极值的可行解u 唯一最优解 有唯一可行解使目标函数达到极值u 无穷多最优解 有无穷多可行解使目标函数达到极值u 无界最优解 存在可行解使目标函数值 Z M（ M是任意 大 u 的正数 ）u 有界最优解 存在可行解使目标函数值 Z M（ M是任意 大u 的正数 ）u 基矩阵 B 满秩系数矩阵 A（ n m） 的任一个 m m满秩子矩阵u 即由矩阵 A的任意 m列线性无关的
3、列向量构成的矩阵u 非基矩阵 N 即由矩阵 A去掉 B的 m列所余下的 n-m列向量构成的u 矩阵2线性规划 Linear Programming（ LP）基本理论u 基向量 基矩阵 B的向量 pi=（ a1i， a2i， ， ami） T i =1， 2， ， mu 非基向量 非基矩阵 N的向量 pj=（ a1j， a2j， ， amj ） T j = m+1， ，u n-mu 基变量 与基向量 pi对应的变量 xi xB=（ x1， x2， ， xm） T u 非基变量 与非基向量 pj对应的变量 xj xN=（ xm+1， ， xn-m） Tu 基本解 在约束条件 AX = b中不妨设基
4、矩阵 B是 A的前 m个列向u 量。于是 AX = b可改写为： B xB + N xN = b， 然后令u xN =0， 即可解得 xB= B -1 b，u 则 X=（ xB ， xN ） T=（ B -1 b， 0） T ， 称为对应基矩u 阵 B的 基本解u 基本可行解 若基本解中 B -1 b0， 则 称其为对应 B的 基本可行解u 凸集 这样的点集合 -其集合中任意两点的连线上的全部点u 都在该点集合内3线性规划 Linear Programming（ LP）基本理论u 极点（顶点） 凸集上不在两个不同点的连线上的点u 线性规划基本定理 1 线性规划所有可行解组成的集合 S=X| A
5、X = b，u X 0是 凸集u 线性规划基本定理 2 X是线性规划问题的 基本可行解的充要条件是u X为 凸集 S=X| AX = b， X 0的极点u 线性规划基本定理 3 给定线性规划问题， A是秩为 m的 m n矩阵，u （ i） 若线性规划问题存在 可行解，则必 存在 基本可行解u （ ii） 若线性规划问题存在有界最优解 ，则必 存在有界最u 优 基 本可行解4线性规划 Linear Programming（ LP）基本理论u 线性规划的标准型的向量和矩阵表达形式u 向量式： 矩阵式：u max Z=c1x1+c2x2+ cnxn max Z=CX u s.t. p1x1+p2x2
6、+ pnxn=b s.t. AX = bu xj0 （ j=1， 2， n ） X 0u 式中： pj=（ a1j， a2j， ， amj） T C =（ c1， c2， ， cn）u u a11 a12 a 1n X =（ x1， x2， ， xn） T u A= a21 a22 a 2n b =（ b1， b2， ， bm） T u u am1 am2 amn 5u 单纯形方法是 Dantzig于 1947年首先发明的。近 50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本算法。u 单纯形法的初步讨论u 例 1.8 求解 LP问题u
7、Max Z=50X1+30X2u s.t. 4X1+3X2 120u 2X1+ X2 50u X1， X2 0 （ 1. 17）线性规划 Linear Programming（ LP）单纯形法、单纯形表6线性规划 Linear Programming（ LP）单纯形法、单纯形表u 单纯形方法由以下步骤构成：u 将原问题转化为标准型模型：u Max Z=50X1+30X2u s.t. 4X1+3X2+X3 =120u 2X1+ X2+ X4= 50u X1， X2， X3， X40 （ 1.18）u 此线性规划问题 转化为了一个含有四个变量的线性规划问题， X3， X4为松弛变量（或剩余变量）。
8、为求解上面的 LP问题，我们要考虑满足约束条件 s.t.并使 Z 取得 Max的 X1， X2， X3， X4的值，由此分析如下-7线性规划 Linear Programming（ LP）单纯形法、单纯形表u 确定初始基可行解：u 通过观察可以发现，松弛变量 X3和 X4对应的等式 约束条件中的系数矩阵为单位矩阵可以作为初始 可行基 矩阵。因此u 取： X3， X4为基变量； X1， X2为非基变量。则 （ 1.18） 可变为u Max Z =50X1+30X2u s.t. X3 = 120 - 4X1- 3X2u X4= 50 - 2X1- X2 （ 1.19）u X1， X2， X3， X
9、40 u （ 1.19） 称为关于基的 典式 u 1、 等式 约束条件中显含 基可行解u 2、目标函数中不 含 基 变量8线性规划 Linear Programming（ LP）单纯形法、单纯形表u 在典式 （ 1.19） 中令： X1=X2 =0，u 我们得到一个基本可行解 X1 =（ X1， X2， X3， X4 ） T=（ 0， 0， 120，50） T ， 其对应的目标函数值 Z1 = 50X1 + 30X2 = 0u 最优性检验：u 基本可行解 X0是最优解吗？显然不是。应寻找更好的解。从问题的数学角度分析，在典式 （ 1.19） 的目标函数中， 非基变量 X1， X2前的系数都为正
10、，表明 目标函数值有增加的可了可能。只要将目标函数中 系数为正的某非基变量与某一基变量地位对换。u 换基迭代：u 进行 换基就是要从非基变量中选一个变量 入基 ，再从基变量中选一个变量 出基 。并且换基后仍需满足：u 1、 新的解仍是基本 可行解；u 2、 目标函数值将得到改善。9线性规划 Linear Programming（ LP）单纯形法、单纯形表u 选择入基变量： 由于在目标函数 Z1=50X1+30X2 中 X1， X2的系数都为u 正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化u 的问题，我们希望目标值增加得越快越好，因此系数最大的 X1入基。u 选择出基变量： X1
11、入基后，其值从零增加并由于 约束条件的原因会引u 起其他变量的变化。由 典式 （ 1.19） 以及变量必须取正值的条件，我u 们可以得到下列不等式关系：u X3 = 120 - 4X1- 3X2 0u X4= 50 - 2X1- X2 0u 因为迭代后 X2仍为 非基变量 （ 仍会令其取值为零 ） ，则上式可简化为：u 120 - 4X1 0 由此可以看出，虽然我们希望 X1入基后取正值，且u 50 - 2X1 0 取值越大目标值增加越大，但是， X1又得受到 约束。u 显然，只有 取 X1 =min（ 120/4， 50/2） =25时，才能使上述不等式成立u 并且恰使 基变量 X4变为零，这正好满足非基变量必须取 值 零的条件， 10
