第一章 运筹学简介及线性规划.ppt

* （2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。 100 200 300 100 200 300 x1+x2≤300 x1+x2=300 100 100 200 2x1+x2≤400 2x1+x2=400 300 200 300 400 * （3）把五个图合并成一个图，取各约束条件的公共部分，如P7图1-2所示。 100 100 x2≤250 x2=250 200 300 200 300 x1 x2 x2=0 x1=0 x2=250 x1+x2=300 2x1+x2=400 图1-2 * （4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。 x1 x2 z=20000=50x1+100x2 图1-3 z=27500=50x1+100x2 z=0=50x1+100x2 z=10000=50x1+100x2 C B A D E * 得到最优解： x1 = 50，x2=250 最优目标值z=27500 练习：P311. (1) (3) * 在例1.3（P7)模型中中引入松弛变量s1 s2 s3模型化为： Max z = 50x1 +100x2+0s1+0s2+0s3 s.t. x1 +x2+s1 = 300 2x1 +x2 +s2= 400 x2 +s3 = 250 x1,x2,s1 ,s2,s3≥0 可求解得其最优解为： x1=50 x2= 250 s1 = 0 s2=50 s3 = 0 说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有资源1和3，但资源2还剩余50。 * 重要结论： 如果线性规划有最优解，则一定与可行域的一个顶点相对应； 无穷多个最优解。若将例1.3中的目标函数变为max z=50x1+50x2，则线段BC上的所有点都代表了最优解； 无界解。当可行域的范围延伸到无穷远使目标函数值成为无穷大或无穷小时，就称为无界解。如图1-3（P8） 无可行解。若在例1.3的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了（如下页图1-4）。 * x1 x2 z=20000=50x1+100x2 图1-4 z=27500=50x1+100x2 z=0=50x1+100x2 z=10000=50x1+100x2 C B A D E 4x1+3x2=1200 * 可行解——满足约束条件和非负条件的解 X 称为可行解. 最优解——使z达到最优的可行解就是最优解 1.3 线性规划问题的求解 1.3.1 LP问题解的几个基本概念 * 基、基变量、非基变量——技术系数矩阵A（标准线性规划模型）中m个线性无关的列向量，构成该LP问题的一个基B，相应的向量称为基向量，与之对应的变量称为基变量,记为XB。其余的变量即为非基变量,记为XN 。 如： Max z = 50 x1 + 100 x2 s.t. x1 +x2+ s1 = 300 2x1 +x2 + s2 = 400 x2 + s3 = 250 x1,x2,s1 ,s2,s3≥0 基解:令非基变量 XN = 0，求得基变量XB的值称为基解.基可行解：若基解中所有的XB 都≥0 时，称为基可行解.  * 只要存在可行解，就一定存在基可行解；基可行解的个数是有限的；若LP问题有最优解，则最优解一定可以在基可行解中找到。 LP问题解的基本性质： * 1.3.2 单纯形法的基本思路（在有限的基可行解中寻找最优解） 确定初始基可行解 是否为最优 确定改善方向 求新的基可行解 求最优解的目标函数值 是 否 * (1) 单纯形表的组成及形式 设 B 是初始可行基向量，则目标函数可写为两部分(1) 约束条件也写为两部分，经整理得 XB 的表达式(2)，注意 XB中含有非基变量作参数 把 XB 代入目标函数，整理得到(3)式 若所有非基变量的检验数σi ?0, 则达到最优 * 单纯形表 * 例1.1