线性规划问题的基本解

1、整理课件3.2 线性规划问题的基本解整理课件基本概念基本概念： 可行解、可行域、最优解、基、基变量、基阵、基本可可行解、可行域、最优解、基、基变量、基阵、基本可行解行解整理课件给定一个线性规划问题给定一个线性规划问题LP 11221 1 max.nnzc xc xc x 1111221121122222112212.1.2.0,0,01.3nnnnmnnmmmns taxaxaxbaxaxaxbaxaxaxbxxx 一、基本概念一、基本概念：整理课件1、可行解、可行解 (a feasible solution)满足约束条件的满足约束条件的X称为线性规划问题的称为线性规划问题的可行解可行解;Tn

2、xxxX,21所有可行解的集合称为所有可行解的集合称为可行域可行域 (feasible region),使目标函数使目标函数(1.1)达到最大值的可行解称为达到最大值的可行解称为最优解最优解(an optimal solution)。 1122nnmaxz = c x +c x +c x1.1 11112211211222221122121.2. .0,0,01.3nnnnmmmnnmnaxaxaxbaxaxaxbs taxaxaxbxxx 整理课件2、基、基(base)nPPP,21即即,21nPPPA是是A的的m个列向量个列向量,设设12,mjjjPPP是线性无关的是线性无关的，如果如果j

3、mjjPPP,21则称则称jmjjPPP,211 . 1max2211nnxcxcxcz11112211211222221122121.2. .0,0,01.3nnnnmmmnnmna xa xa xba xaxaxbs taxaxaxbxxx为基向量。为基向量。记约束方程系数矩阵记约束方程系数矩阵A的列向量是的列向量是整理课件3、基变量、基变量(basic variables)构成线性规划问题的一组基向量构成线性规划问题的一组基向量,设设12,jjjmPPP则对应的变量则对应的变量 12,jjjmxxx称为称为基变量基变量，其余的向量称为其余的向量称为非基向量非基向量，其余的变量称为其余的变

4、量称为非基变量非基变量(non-basic-variable)，称为称为基基或或基阵基阵(basic matrix)。矩阵矩阵 12 ,jjjmBPPP整理课件约束方程约束方程A的系数矩阵为：的系数矩阵为：321001001002001 A12345321001001002001 其其 列列 向向 量量 ：，PPPPP分别是变量分别是变量54321,xxxxx的系数向量。的系数向量。例例12153maxxxz12314525123432184212,0 xxxxxxxxxxxx 整理课件543,PPP向量组向量组 是线性无关组是线性无关组 1345 ,BP P P是此问题的一个基是此问题的一个

5、基其中其中 为基变量，而为基变量，而 是非基变量。是非基变量。345,xxx12,xx2153maxxxz0,12241823543215241321xxxxxxxxxxxx321001001002001 A整理课件向量组向量组 是线性无关组是线性无关组542,PPP321001001002001 A2153maxxxz0,12241823543215241321xxxxxxxxxxxx245,xxx 是基变量，是基变量， 2245 ,BP P P是此问题的一个基是此问题的一个基31,xx而而 是非基变量。是非基变量。整理课件（2）设）设B是是A的一个的一个m阶子矩阵，则阶子矩阵，则B是线性规

6、划问题是线性规划问题的基阵，当且仅当的基阵，当且仅当B是可逆阵是可逆阵 。0B（3）基的个数）基的个数Cnm注：注：（1）基不一定唯一）基不一定唯一100200100100123A2153maxxxz0,12241823543215241321xxxxxxxxxxxx整理课件4、基解、基解 jmjjPPPB,21 12 ,BjjjmXxxxNX现令所有的非基变量都等于现令所有的非基变量都等于0，即，即0 NX设设 是线性规划问题是线性规划问题LP的一基阵，的一基阵，表示基变量向量，表示基变量向量，表示非基变量向量。表示非基变量向量。整理课件则约束方程则约束方程(1.2)可化为：可化为： 112

7、21 4 .jjjjjmjmBPxPxPxbBXb1 BXB b100 B bX它是一个它是一个m个变量个变量m个方程组成的线性方程组，个方程组成的线性方程组，B又是可逆又是可逆阵，从而得出阵，从而得出(1.4)的唯一解的唯一解得出约束方程得出约束方程(1.2)至少含有至少含有n-m个个0元的解元的解 称之为相应于基称之为相应于基B的一个的一个基本解或基解基本解或基解(a basic solution)。整理课件5、基可行解、基可行解设设 是对应于基阵是对应于基阵B的一个基解，的一个基解，100 B bX0010bBX010bBX如果如果 则称则称 为一个为一个基本可行解或基可行基本可行解或基

8、可行解解.(a basic feasible solution)；相应的基相应的基B也称为也称为可行基可行基(feasible base)。整理课件在上例在上例1中，中，对应于对应于 的基解为的基解为是一个基可行解，是一个基可行解，对应于对应于 的基解为的基解为而不是基可行解。而不是基可行解。 10 0 18 4 12 ,TX1B2B 20 9 0 46 。,X思考题：试列出例思考题：试列出例1中问题的所有基解、基可行解。中问题的所有基解、基可行解。2153maxxxz0,12241823543215241321xxxxxxxxxxxx100200100100123A整理课件 注：给定线性规划

9、问题注：给定线性规划问题LP，其基可行，其基可行解的数目是有限个，不会超过解的数目是有限个，不会超过 。 图图1给出了线性规划问题的解的关系。给出了线性规划问题的解的关系。mnC可行解基解基可行解图图1非可行解整理课件121231245223504260014 max,jZxxxxxxxxxj11322120(P)4041BB ，P P、，12BB和和12BB、1.设线性规划设线性规划取基取基分别指出分别指出对应的基变量和非基变量，对应的基变量和非基变量，是不是可行基是不是可行基求出基本解，并说明求出基本解，并说明整理课件1若线性规划无最优解则其可行域无界。若线性规划无最优解则其可行域无界。（ ）2凡基本解一定是可行解。凡基本解一定是可行解。 （ ）2判断题（你认为下列命题是否正确，判断题（你认为下列命题是否正确，对正确的打对正确的打“”；错误的打；错误的打“”。）。）3线性规划的最优解一定是基本最优解。（线性规划的最优解一定是基本最优解。（ ）4线性规划的最优解是可行解。（线性规划的最优解是可行解。（ ）5可行解是基本解。（可行解是基本解。（ ）整理课件3.线性规划可行域的顶点一定是（线性规划可行域的顶点一定是（ ）。）。A.基本可行解基本可行解B.非基本解非基本解C.非可行解非可行解D.最优解最优解4. X是线性规划的基本可行