胡运权运筹学第五版第一章习题讲解.ppt

线性规划数学模型的标准形式 一般形式的线性规划数学模型转化为标准形式 几种解的基本概念 LP问题解四种情况的判别 图解法 单纯形法 单纯形法计算的矩阵描述 课后题答案 课后题答案 课后题答案 课后题答案 课后题答案 课后题答案 课后题答案 课后题答案 课后题答案 课后题答案 课后题答案 课后题答案 Company Logo LOGO * Company Logo Company Logo 习题讲解 课程：运筹学 内容：第一章课后习题解 作业分类汇总 1、LP问题解四种情况的判别 习题： 1.1(a)、1.1(b)、1.7(b) 2、LP问题解的基本概念 习题：1.2(b)、1.3(a) 3、LP问题的标准形式转化 习题：1.6(a) 4、单纯形法的计算 (标准型的系数矩阵中不包含单位矩阵的情况） 习题：1.7(b) 5、单纯形法计算的向量矩阵描述及特征应用 习题：1.8、1.12 6、现实问题应用 习题：1.13、1.14 7、证明题 习题：1.16、1.17 END 即：1.目标函数求极大值max z；2.全部是等式约束；3.常数项非负 （b ≥0 ）；4.变量非负 （X ≥0 ) ；5.n＞m。 1.目标函数为求最小值： 作变换，令z=(-z),化为求： max z = -( c1x1 +c2x2 +…+ cnxn ) 2.约束条件为不等式：当约束条件为≤时，加一非负的松弛变量。 当约束条件为≥时，减一非负的剩余变量。 注：松弛变量在目标函数中的系数为0 3.取值无约束的变量：作变换，令xj=xj-xj(xj,xj≥0),即将其化为两个非负变量之差。 4.负变量 (xj0): 作变换,令xj= - xj ,≥0 5.常数项为负： 约束两端同乘（-1）即可。 Return 1.可行解： 满足系统约束条件和非负性约束的解X=(x1 ,x2 ,… xn )T,称为LP问题的可行解。 2.最优解： 满足目标函数值最大的可行解称为LP的最优解。 3.基（本）解： 设B为LP问题的一个基，在系统约束方程组中，令非基变量xm+1= xm+2 … =xn =0, 而B是满秩的，由克莱姆法则，可解出由m个基变量表示的唯一解XB= (x1 ,x2 ,… xm)T 或X= (x1 ,x2 ,… xm，0，…，0)T ，称X为LP问题的一个基解。 4.基（本）可行解： 满足变量非负性约束的基解称为基可行解。 Return 1、LP问题的解总有四种情况： 唯一最优解 无穷多最优解 无界解 无可行解 2、判别方式： 图解法：直观性强，但有其局限性，只适用于问题中有两个变量的情况。 单纯形法。 Return 唯一最优解 无穷多最优解 无界解 无可行解 Return Return Cj CB CN 0 CB XB b XB XN XS 0 XS b B N I σj=cj-zj CB CN 0 Cj CB CN 0 CB XB b XB XN XS CB XB B-1b I B-1N B-1 σj=cj-zj 0 CN - CBB-1N - CBB-1 均左乘矩阵B-1 Return Return 1.1（a）答案： 该问题有无穷多最优解。 取特殊值：(1.5,0) 计算目标函数最优值 得:min z=3。 1.1（a） 1.1（b）答案： 由图可知：该Lp问题没 有可行域，即可得出： 该问题无可行解 1.1(b) 1.2（b）答案： Return 基 基解 x1 x2 是否为基可行解 目标函数值 P