资源描述：
《线性规划图解法几何意义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第1章线性规划及其扩展第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例1.3．线性规划问题的标准形式(其中bi≥0(i=1,2,...,m)称下列形式为线性规划问题的标准形式:目标函数求极大,约束条件为等式,决策变量及右边常数项为非负线性规划问题的几种表示形式用向量表示为：则标准形式的矩阵表示：若令A－－称为系数矩阵b－－称为资源向量C－－称为价值向量X－－称为决策变量向量用矩阵表示为：非标准形式化为标准形式的方法1.当目标函数为求极小值,即minz=c1x1+c2x2+...+cnx
2、n因为求minz等价于max(-z)故可令则目标函数化为:2.当右端项bi<0时只需将等式或不等式两端同乘(-1),则右端项必大于03.当约束条件为ai1x1+ai2x2+...+ainxn≤bi引入一个变量xn+i≥0可使成为等式即ai1x1+ai2x2+...+ainxn＋xn+i＝bi变量xn+i称为松弛变量4.当约束条件为ai1x1+ai2x2+...+ainxn≥bi时则引入一个变量xn+i≥0可使不等式成为等式,即ai1x1+ai2x2+...+ainxn－xn+i＝bi变量xn+i称为剩余变量5.当变量xi为无约束的变量时则我们引入两个变量令:将其代入线性规
3、划模型中6.当变量xi≤0时则令再代入线性规划模型中例3将例1的数学模型化为标准形该线性规划问题加入三个松驰变量x3,x4,x5≥0后：例4将下述线性规划问题化为标准形解：分以下步骤进行处理(1)令z′=-z，把求minz改为求maxz′;(2)在第一个约束不等式≤号的左端加入松弛变量x4；(3)在第二个约束不等式≥号的左端减去剩余变量x5；(4)用x6-x7替换x3，其中x6，x7≥0,即可得到该问题的标准形.得原问题的标准形为：1.4线性规划问题的解的概念1.可行解2.基3.基可行解4.可行基一.线性规划问题解的概念线性规划问题1.可行解:满足线性规划问题的约束条件的
4、解X=(x1，x2，...，xn)T称为线性规划问题的可行解。2.可行域:全部可行解构成的集合称为可行域。3.最优解:使目标函数达到最优的可行解称为最优解。4.基:设系数矩阵Am×n(n>m)其秩为m,B是矩阵A中的一个m×m阶的满秩子矩阵,称B是线性规划问题的一个基。一.线性规划问题解的概念（2）=(P1,P2,...,Pm)B中的每一列向量Pj(j=1,2,...m)称为基向量基向量：与基向量Pj的对应的变量xj称为基变量基变量：非基变量：线性规划中的其余变量称为非基向量5.基解设X是（LP）的约束方程AX=b的一个解，B是一个基，若X中对应基B的非基变量取值全为零，
5、则称X为(LP)关于基B的基解，记作X(B)不妨设基为基解的个数不会超过个一.线性规划问题解的概念（3）可证明:一个基可以而且唯一地确定一个基解.6.基可行解：若基解X(B)满足非负条件X(B)≥0，则称基解X(B)为基可行解7.基最优解：若基可行解X(B)是(LP)的最优解,则称X(B)为(LP)的基最优解.最优基：基最优解对应的可行基B称为最优基.可行基：基可行解对应的基B称为可行基.注:基解没有X≥0的限制,故基解不一定是可行解.X(B)=一.线性规划问题解的概念（4）8.退化解：若基本可行解X的所有基变量的值均大于0，则称X是非退化的，否则称X为退化的。若(LP)
6、的所有基本可行解都是非退化的,则称线性规划问题是非退化的.二.例题考虑线性规划问题：约束方程的系数矩阵A很显然A中的后3列是线性无关的，它们构成一个基基B1对应的变量x3,x4,x5是基变量,x1,x2是非基变量二.例题（2）若令：得该解是对应B1的基解，它是基可行解，B1是可行基；如取是（LP）的一个基，若令：基B2对应的变量x1,x2,x3是基变量，,x4,x5是非基变量得该解是对应B2的基解，它不是基可行解，B2不是可行基；三.线性规划问题解的关系图AX=b的解基解若非基变量为0基可行解基最优解B是A的m阶子矩阵基B若
7、B
8、0可行基B当B-1b0最优基B若基变量
9、取非负若对应目标函数值最优非可行解三.线性规划问题解的关系图（2）可行解基可行解基解基可行基最优基第2节线性规划问题的几何意义2.1基本概念2.2几个定理一.凸集与顶点凸集:如果集合K中任意两个点X(1),X(2),其连线上的所有点也都是集合K中的点,则称集合K为凸集.或K={X
10、X=αX(1)+(1-α)X(2),X(1)K,X(2)K,0≤α≤1}定理:D＝｛x∈Rn
11、Ax=b,x≥0}是凸集顶点:凸集K中满足下列条件的点X称为顶点:如果K中不存在任何两个不同的点X1,X2,使X成为这两个点连线上的一个点.定理:有限个
