第一章线性规划——《运筹学》教案.pptVIP

第一章 线性规划LP;线性规划教学大纲;第一讲：绪论、LP问题的数学模型与图解法;一、LP问题的数学模型;例1：数学模型;例1：数学模型;求解的误区;二、LP问题求解－－图解法;例2：家电问题（课堂练习）;例2：数学模型;例2：数学模型;例2：图解法;作业;第二讲：LP问题的标准型SLP及基的相关概念;例3：污水处理厂问题;例3：数学模型;例3：数学模型;例3：图解法;小结：线性规划的数学模型;1、一般形式;2、紧缩形式：;3、矩阵形式;4、向量矩阵形式;小结：线性规划的图解法;小结：解的可能性;小结：几个基本概念;两个几何概念;LP解的性质;三、LP的标准型（SLP） ;三、LP的标准型（SLP） ;三、LP的标准型（SLP） ;三、LP的标准型（SLP） ;三、LP的标准型（SLP） ;续例1：将LP问题化为SLP; SLP: Opt： Max Z’ = －900x1 －1000x2 　 x1 　 – x3 　 = 1 0.8x1+ x2 – x4 = 1.6 st x1 + x5 = 2 0.8x1 + x2 + x6 =3 x1，x2，x3，x4，x5，x6 ≥0;例：写出SLP（课堂练习）;小结：LP标准型（SLP）的特点;SLP的数学表达式;;松驰变量的经济意义;作业;第三讲：基的进一步理解与图解LP解的性质;四、基及其相关概念 ;基;基向量，基变量;非基向量，非基变量; x1 　 x2　 　x3 　 x4 　 x5 9　　4　　1　　0　　0 A ＝ 4　　5　　0　　1　　0 3　　10　 0　　0　　1;基解，基可行解，可行基 ;［例］Opt：Max Z = 7x1 +12x2 　　 9x1 + x3　　　　　 ＝360 s.t 4x1+ 5x2 　　　+ x4　　 ＝150 8x1+10x2 　　　　　+ x5 ＝300 x1， x2， x3， x4， x5 ≥0;基解的特征;例：基的概念;⑧找出例2的全部基解，指出其中的基可行解，确定最优解;⑦ 找出例2的全部基解，指出其中的基可行解，确定最优解;⑧用作图法求解该问题，指出上题中的基解各对应于图中哪些点？ ;所以：我们从某一个基可行解出发，沿边界有哪些信誉好的足球投注网站下一个顶点，判断目标函数值是否最优，若否，继续，直到最优－－这就是单纯形法求解的基本思想， 所以：单纯形法求解的基本条件是找到一个基可行解（可行基）。 而：最显然易见的一个可行基就是一个单位矩阵。;作???;第四讲：单纯形法;O;两个几何概念;LP解的性质;五、单纯形法－－基本思路;单纯形法原理－－代数法;Ｏ;（2）确定离基变量 　　从经济意义来看，x2的增大能使Z值增大，但x2的增大将消耗资源，水电煤，某一种资源消耗完后x2就不能再增大了。 　　从变量的定义来看，x2的增大受s.t.的限制的，它必须满足x3，x4，x5?0， 　　所以，将基变量用非基变量表示，并且保持x1=0（x1是非基变量）不变，有;（3）求出新的基可行解： 把x1、x5作为常数，将基变量用非基变量表示， ;令非基变量x1=x5=0，得到新基可行解 X(1)=（0，30，240，50，0）T Z(1)=360 此时，基可行解对应图中的A点。;STEP4：继续迭代优化 x1入基，x5为非基变量=0保持不变;同样，把x4、x5作为常数，将基变量用非基变量表示， 解得：;此时，基可行解对应图中的B点 ;代数法思路;单纯形表;二、找出初始可行基 　找出单位子矩阵。填入XB（基变量），填入对应的CB ;;;;作业;第五讲：单纯形法的进一步讨论;解读单纯形表;单纯形法例2;;;;结论：迭代的结果不是一个可行解（但它是一个基解），因此用单纯形法无法继续。错误。;;;;单纯形法解的几种情况;;三、如果在确定入基、离基变量时， 　　存在?j0，有入基变量 　　但找不到?i ≥ 0（注： ?i 可以＝0），即找不到离基变量，则该LP具有 　　无界解； 解释原因： 存在?j0，说明增大变量可使函数值增加； ? i ＜0，说明入基变量由0增大时不受约束； 因此，目标函数值无界。 ;;四、无解 　　简单单纯形法，使用的前提是找出一个初始可行解（单位矩阵），因此，目前不会无解； 五、退化现象（退化解）： 　 在确定xk为换入变量时，?max不止一个； 　?? 在确定xl为换出变量时，?min不止一个；