线性规划图解法几何意义
59页1、第1章 线性规划及其扩展,第1节 线性规划问题及其数学模型 第2节 线性规划问题的几何意义 第3节 单纯形法 第4节 单纯形法的计算步骤 第5节 单纯形法的进一步讨论 第6节 应用举例,1.3线性规划问题的标准形式,(其中bi0(i=1,2,.,m),称下列形式为线性规划问题的标准形式:,目标函数求极大,约束条件为等式,决策变量及右边常数项为非负,线性规划问题的几种表示形式,用向量表示为:,则标准形式的矩阵表示:,若令,A称为系数矩阵,b称为资源向量,C称为价值向量,X称为决策变量向量,用矩阵表示为:,非标准形式化为标准形式的方法,1.当目标函数为求极小值,即 min z=c1x1+c2x2+.+cnxn,因为求min z 等价于max (-z),故可令,则目标函数化为:,2.当右端项 bi0时,只需将等式或不等式两端同乘(-1),则右端项必大于0,3.当约束条件为 ai1x1+ai2x2+.+ainxnbi,引入一个变量xn+i0,可使成为等式即 ai1x1+ai2x2+.+ainxnxn+ibi,变量xn+i称为松弛变量,4. 当约束条件为ai1x1+ai2x2+.+ainxnbi
2、时,则引入一个变量xn+i0,可使不等式成为等式,即 ai1x1+ai2x2+.+ainxnxn+ibi,变量xn+i称为剩余变量,5.当变量xi为无约束的变量时,则我们引入两个变量,令:,将其代入线性规划模型中,6.当变量xi0时,则令,再代入线性规划模型中,例3 将例1的数学模型化为标准形,该线性规划问题加入三个松驰变量x3,x4,x50后:,例4 将下述线性规划问题化为标准形,解:分以下步骤进行处理,(1)令z= -z,把求min z 改为求max z; (2) 在第一个约束不等式号的左端加入松弛变量x4; (3) 在第二个约束不等式号的左端减去剩余变量x5; (4)用x6-x7替换x3,其中x6,x70,即可得到该问题的标准形.,得原问题的标准形为:,1.4 线性规划问题的解的概念,1.可行解 2.基 3.基可行解 4.可行基,一. 线性规划问题解的概念,线性规划问题,1.可行解:,满足线性规划问题的约束条件的解X=(x1,x2,.,xn ) T称为线性规划问题的可行解。,2.可行域:,全部可行解构成的集合称为可行域。,3.最优解:,使目标函数达到最优的可行解称为最优解。,4.
3、基:,设系数矩阵Amn(nm)其秩为m,B是矩阵A中的一个mm阶的满秩子矩阵,称B是线性规划问题的一个基。,一. 线性规划问题解的概念(2),=(P1,P2,.,Pm),B中的每一列向量Pj(j=1,2,.m)称为基向量,基向量:,与基向量Pj的对应的变量xj 称为基变量,基变量:,非基变量:,线性规划中的其余变量称为非基向量,5.基解,设X是(LP)的约束方程AX=b的一个解,B是一个基,若X中对应基B的非基变量取值全为零,则称X为(LP)关于基B的基解,记作X(B),不妨设基为,基解的个数不会超过 个,一. 线性规划问题解的概念(3),可证明:一个基可以而且唯一地确定一个基解.,6.基可行解:,若基解X(B)满足非负条件X(B)0,则称基解X(B)为基可行解,7.基最优解:,若基可行解X(B)是(LP)的最优解,则称X(B)为(LP)的基最优解.,最优基:,基最优解对应的可行基B称为最优基.,可行基:,基可行解对应的基B称为可行基.,注:基解没有X0的限制,故基解不一定是可行解.,X(B)=,一. 线性规划问题解的概念(4),8.退化解:,若基本可行解X的所有基变量的值均大于0,则
4、称X是非退化的,否则称X为退化的。,若(LP)的所有基本可行解都是非退化的, 则称线性规划问题是非退化的.,二. 例题,考虑线性规划问题:,约束方程的系数矩阵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,若|B|0,可行基B,当B-1b0,最优基B,若基变量取非负,若对应目标函数 值最优,非可行解,三. 线性规划问题解的关系图(2),可行解,基可行解,基解,基,可行基,最优基,第2节 线性规划问题的几何意义,2.1 基本概念 2.2 几个定理,一.凸集与顶点,凸集:,如果集合K中任意两个点X(1),X(2),其连线上的所有点也都是集合K中的点,则称集合K为凸集.,
《线性规划图解法几何意义》由会员san****019分享,可在线阅读,更多相关《线性规划图解法几何意义》请在金锄头文库上搜索。
高中化学实验方案的设计第一节制备实验方案设计
高中生物实验室配置
高中体育与健康课程田径必修模块单元教学方案
高中通用技术方案的构思方法-设计分析教案苏教版必修
高中生物室配置
高中信息技术网络技术应用选修模块教学评价方案
骆小学教师戏曲知识培训方案(I)
麻村小学阳光体育活动计划及实施方案
高桥小学幼小衔接活动方案
马摆小学控辍保学实施方案
金阳街道中心小学未成年人思想道德建设实施方案
龙扬小学第32个爱国卫生月活动方案
魏家井联小学度控辍保学工作方案
高区第九届初中骨干教师课堂教学能力展示活动
长沙县2018年度小学生课外阅读知识竞赛及书目
阳江中心小学一月一事之五月主题活动方案
长营小学校园体育活动实施方案
高考历史备考方案-陈军
高考语文第5课父亲课前预案苏教版选修现代散文选读
高考语文第9课铃兰花课前预案苏教版选修现代散文选读
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页