运筹学第1章ppt线性规划.pptVIP

运筹学;授课教材：党耀国等,《运筹学》,科学出版社 绪论 第一章 线性规划的数学模型与单纯形法 第二章 线性规划的对偶理论与灵敏度分析 第三章 运输问题 第四章 整数规划 第五章 动态规划 第六章 图论与网络计划 第七章 存储论 第八章 决策分析;绪 论;O.R.在工商管理中的应用; 人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。 市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。; 财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。 其他： 设备维修、更新，项目选择、评价，工程优化设计与管理等。 ;;;例1.2 (成本问题);线性规划模型特点:; I II 每天现有工时 搅拌机 3 5 15 成型机 2 1 5 烘 箱 2 2 11 利润(千元/吨） 5 4; 甲 乙 丙 柑橘林产量（千蒲式耳） 柑橘林I 21 50 40 275 柑橘林II 35 30 22 400 柑橘林III 55 20 25 300 加工厂的加工能力 200 600 225 （千蒲式耳）;;二、线性规划问题的标准型 ;解：引进3个新非负变量x3，x4，x5使不等式变为等式，标准型为： max Z=2x1+3x2+0·x3+0·x4+0·x5 3x2+x3=15 4x1+x4 =12 2x1+2x2+x5=14 x1，x2，x3，x4，x5≥0;解：① 令x3 =x4 - x5;;0;(2) 求最优解－“等值线法”; max Z = 2x1 +3x2; 用图解法求解线性规划问题 maxZ=40x1+ 80x2 s.t. x1+2x2 ? 30 3x1+2x2 ? 60 2x2 ? 24 x1 , x2 ?0 ;maxZ=2x1+ 4x2 s.t. 2x1+x2 ? 8 -2 x1+ x2? 2 x1，x2 ?0 ;max S=3x1+2x2 ;通过以上各题图解法所得结论可以看出： （1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域可能是无界的； （2）若存在最优解，则一定在可行域的某顶点得到； （3）若在两个顶点上同时得到最优解，则在这两点的连线上的任一点都是最优解。 （4）若可行域无界，则可能发生最优解无界的情况； （5）若可行域是空集，此时无最优解。 上述理论具有普遍意义，对于两个以上变量的线性规划问题都是成立。 ;;(m n) r(A)=m , 至少有一个m 阶子式不为0 不失一般性,不妨假设P1 … Pm线性无关;; 1. 可行解: 满足约束条件的解 X = ( x1, x2, ···, xn) 称为线性规划问题的可行解；所有可行解的集合称为可行解集或可行域。 2. 最优解: 满足约束条件及目标函数的可行解称为线性规划问题的最优解。 最优值 3. 基阵: 假设 A 是约束方程组的系数矩阵，其秩数为 m ，B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0)，则称 B 是线性规划问题的一个基。这就是说，矩阵 B 是由 m 个线性无关的列向量组成，不失一般性，可假设: 称 Pj ( j = 1,2,···,m )为基向量，与基向量 Pj 相对应的变量xj ( j = 1,2,···,m )称为基变量，否则称为非基变量。; 为了进一步讨论线性规划问题的解，下面研究约束