北邮运筹学ch线性规划解的概念.ppt

§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 1 of 13 设线性规划的标准型max Z=CX （1.1）AX=b （1.2）X≥0 （1.3）式中A是m×n矩阵，m≤n并且r（A）=m，显然A中至少有一个m×mB，使得r（B）=m基基 A中m×mB并且有r（B）=m，则称B是线性规划的一个基基（或基基矩矩阵阵 ）当m=n时，基矩阵唯一，当m

当矩阵B的行列式等式零即|B|=0时就不是基 当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基基向量向量，其余列向量称为非基向量非基向量 基向量对应的变量称为基变量基变量，非基向量对应的变量称为非基变量非基变量 在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 4 of 13可行解可行解 满足式（1.2）及（1.3）的解X=（x1,x2…，xn)T 称为可行解 基基本本可可行行解解，若基本解是可行解则称为是基本可行解（也称基可行解） 例如， 与X=（0，0，0，3，2，）都是例1 的可行解 基本解基本解 对某一确定的基B，令非基变量等于零，利用式（1.２） 解出基变量，则这组解称为基Ｂ的基本解 最最优优解解 满足式 （1 .1）的可行解称为最优解，即是使得目标函数达到最大值的可行解就是最优解，例如可行解 是例2的最优解。

9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 5 of 13显然，只要基本解中的基变量的解满足式（1.３）的非负要求，那么这个基本解就是基本可行解 在例1中，对Ｂ１来说，x1,x2是基变量，x3,x4，x5是非基变量，令x3=x4=x5=0，则式（1.２）为因|Ｂ１|≠０，由克菜姆法则知，x1,x2有唯一解x2=1则基本解为对B2来说，x1,x4,为基变量，令非变量x2,x3,x5为零，由式（1.2）得到 ，x4=4，9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 6 of 13由于 是基本解，从而它是基本可行解，在 中x1<0,因此不是可行解，也就不是基本可行解 反之，可行解不一定是基本可行解例如 满足式（1.2）～（1.3），但不是任何基矩阵的基本解。

基本解为9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 7 of 13最最优优基基 基可行解对应的基称为可可行行基基；基本最优解对应的基称为最优基，如上述B3就是最优基，最优基也是可行基当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解例如右图中线段 的点为最优 解时，Q1点及Q2点是基本最优解,线段 的内点是最优解而不是基本最优解 基本最优解基本最优解 最优解是基本解称为基本最优解例如，满足式（1.1）~(1.3)是最优解,又是B3的基本解,因此它是基本最优解.9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 8 of 13基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示：基本最优解基本可行解可行解最 优 解基本解例如,B点和D点是可行解,不是基本解;C点是基本可行解;A点是基本最优解,同时也是最优解、基本可行解、基本解和可行解。

9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 9 of 13凸集凸集设K是n维空间的一个点集，对任意两点 时，则 称K为凸集 就是以X（1）、X（2）为端点的线段方程，点X的位置由α的值确定，当α=0时，X=X（2），当α=1时X=X（1）凸组合凸组合 设 是Rn中的点若存在 使得 成立， 则称X为 的凸组合。

9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 10 of 13极点极点 设K是凸集， ，若X不能用K中两个不同的 点 的凸组合表示为则称X是K的一个极点或顶点 X是凸集K的极点即X不可能是K中某一线段的内点，只能是K中某一线段的端点 9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 11 of 13【定理定理1.1】 若线性规划可行解K非空,则K是凸集. 【定定理理1.2】线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解.【定定理理1.3】若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上到达,最优解就是极点的坐标向量.定理1.2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一 对应 ，有可能两个或几个基本可行解对应于同一极点（退化基本可行解时）。

线性规划的基本定理线性规划的基本定理9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 12 of 13 定理1.3描述了最优解在可行解集中的位置，若最优解唯一，则最优解只能在某一极点上达到，若具有多重最优解，则最优解是某些极点的凸组合，从而最优解是可行解集的极点或界点，不可能是可行解集的内点 若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解 定理1.2及1.3还给了我们一个启示，寻求最优解不是在无限个可行解中去找，而是在有限个基本可行解中去寻求下一节将介绍一种有效地寻找最优解的方法9/3/2024§1.4 线性规划解的概念线性规划解的概念Basic Concepts of solution Ch1 Linear Programming Page 13 of 131. 线性规划常用的概念：可行解、基本解、基本 可行解、最优解、基本最优解、基、可行基、最优基、凸集、凸组合2.线性规划的三个基本定理。

本节内容MBA学员只作一般掌握作业：P45 T1.3(2)单纯形法Exit9/3/2024。