第一章线性规划与单纯形法.ppt

《第一章线性规划与单纯形法.ppt》由会员分享，可在线阅读，更多相关《第一章线性规划与单纯形法.ppt（61页珍藏版）》请在三一文库上搜索。

1、第一章 线性规划与单纯形法,第一节 线性规划的基本概念 第二节 线性规划的标准形式和解的性质 第三节 单纯形法 第四节 人工变量法 第五节 线性规划应用举例,本章学习目的和要求,通过本章的学习，要求学生掌握线性规划的图解法，深刻理解单纯形法的解题思路，熟练掌握其运算步骤，并能在实际问题中加以运用。,主要研究目的,1已有一定数量的人力、物力、财力资源，研究如何充分合理地使用才能使完成的任务量最大。（如：利润、产值等最大。 maximum） 2当一项任务量确定以后，研究如何统筹安排，才能使完成任务耗费的资源量为最小。（如：成本最小。minimum）,第一节 线性规划的基本概念,一、线性规划的数学模

2、型 【例1-1】 某厂生产P、Q两种产品，主要消耗A、B、C三种原料，已知单位产品的原料消耗数量等资料如表1-1所示。,表11,要求确定P、Q的产量，使产值最大。,解：设P、Q的产量分别为x1，x2，则问题的模型为,【例1-2】 某公司打算利用甲、乙、丙3种原料配置一种新型保健饮料，已知每千克原料中两种主要保健成分A，B的含量及原料单价如表1-2所示。,产品质量标准规定每千克饮料中，营养成分A，B的含量不低于10个与8个单位。如何制定饮料配方，既满足质量标准又使成本最低？,解：设每千克饮料中原料甲，乙，丙的投入量分为x1，x2，x3千克，则问题的模型为：,【例1-3】 A1，A2是两个粮库，每

3、月分别可调出粮食30吨与40吨，三个粮店B1，B2，B3每月的需求量分别为20吨，25吨与18吨。粮库与粮店之间每吨粮食的运费如下表1-3所示（单位：元/吨）。,粮店,运费,粮库,要求安排粮食调运方案，在满足需求的前提下，使总运费最低。,解：设从粮库Ai到粮店Bj的调运量为xij，i=1，2，j=1，2，3，则问题的模型为：,上述三个问题属于同一类型的决策优化问题，它们具有下列共同特点： （1）每个行动方案可用一组变量（x1，xn）的值表示，这些变量一般取非负值； （2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示； （3）有一个需要优化的目标，它也是变量的线性函数。 具备以

4、上三个特点的数学模型称为线性规划（Linear Programming，简记为LP）。,实际问题中线性的含义,一是严格的比例性，如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例。 二是可叠加性，如生产多种产品时对某项资源的消耗量应等于各产品对该项资源的消耗量之和。,线性规划的一般形式为：,变量x1，x2，xn称为决策变量，目标函数中变量系数cj，称为价值系数，bi称为右端常数，约束条件（1-3）称为非负约束，（1-2）称为技术约束，系数aij称为技术系数。满足全部约束条件的变量值（x1，xn）称为可行解，可行解的集合称为可行域，记为R；使目标函数取得最大（最小）值的可行解（x1

5、，xn）称为最优解。,（1-3）,（1-2）,（1-1）,采用求和符号，线性规划的一般形式可以简写为：,用向量形式可表示为：,用矩阵和向量形式表示为：,式中：X=（x1，x2，xn）T C=（c1，c2，cn） b=（b1，b2，bm）T A=（aij）mn Pj=（a1j，a2j，amj）T,二、图解法,当决策变量个数n=2时，LP问题可以通过在平面上作图的方法求解，称为图解法。 图解法求解的目的： 1.判别线性规划问题的求解结局。 2.在存在最优解的条件下，把问题的最优解找出来。,【例1-4】 求下列问题的最优解。,（1）确定问题的可行域R。,可行域R是凸多角形OQ1Q2Q3Q4,（2）分

6、析目标函数Z的等值线平行移动与Z值的关系，确定最优解的位置。,当z取定值时，方程z=2x1+5x2或x2=2/5x1+z/5表示一条斜率为2/5的直线 l ， 称为z的等值线，它在x2轴上的截距为z/5。当l向右上方平行移动且保持与R有共同部分时，z值不断上升，由于l的斜率为2/5，因此当l向右上方平移的过程中，与R最后的公共点是Q3，z在Q3达到最大值。,（3）计算最优解。,点Q3是直线l1与l3的交点，它的坐标由方程组,决定，从中解得x1=2，x2=3。这就是问题的最优解，相应的目标函数值z=2253=19。最优产量计划是P，Q分别生产2个与3个单位，最大产值为19万元。这时原料A与C用完

7、，B剩余4吨。,线性规划问题求解的几种可能结局：,1.唯一最优解：如上例。 2.无穷多最优解：如Z换成maxZ=2X1+4X2,，此时最优解在线段Q2Q3 上达到，有无穷多最优解。 已求得Q3的坐标为（2，3）；Q2坐标由方程组,决定，从中解得x1=3，x2=5/2。 设 ， ，线段Q2Q3上的点可用 X1+（1）X2（01）表示。因此，X1+（1）X2（01）是问题的全部最优解。,3.无界解,如约束条件只保留第3个，即4X212，这时可行域无界，Z值可无限上升，无最优解，简称无界解，即有可行解，但目标函数值无解。 产生原因：是由于在建立实际问题的数学模型中遗漏了某些必要的资源约束条件。,4.

8、无解或无可行解,O,x2,D,A,2,4,x1,B,C,l1,l2,l,可行域是空集，问题无可行解，当然更无最优解。 注意：考试中如出现3、4两种情况，一定自己搞错了，必须重新解。,图解法得到的启示,1.求解线性规划问题时，解的情况有：唯一最优解、无穷多最优解、无界解和无可行解。 2.若线性规划问题的可行域存在，则可行域是一凸集。 3.若线性规划问题的最优解存在，则最优解一定在某个顶点可达到。 4.解题思路是：先找出凸集的任一顶点，计算Z值，比较相邻顶点Z值，如大，转到相邻顶点，一直到找出使Z值最大的顶点为止。,第二节 线性规划的标准形式和解的性质,一、 LP的标准形式,称为线性规划问题的标准

9、形式（其中右端常数b1，b2，bm0）。,线性规划标准形式的特点： 1. 技术约束条件全部是等式约束 2. 目标函数限定求最大值,变换一般LP为标准形式的方法： （1）如果原问题目标函数求极小值：,令z1=z，转化为求 。 （2）若某个右端常数bi0，则以1乘该约束两端。 （3）若某约束为“”型的不等式约束，则在左端加上一个非负变量，称为松弛变量，使不等式化为等式；若某约束为“”型，则在左端减去一个非负变量，称为剩余变量，或者仍然称为松弛变量，使不等式转化为等式。（目标函数不变） （4）若某个xj的符号约束为xj0；那么令xj=xj，则xj0；若某个xj无符号限制，令xj=xjxj，其中xj0

10、，xj0。（目标函数变）,例：把LP问题,化为标准形式 在三个技术约束中，分别加入松弛变量x3，x4，x5，问题化为标准形式：,化为标准形式,【例1-9】 把LP问题,二、 LP的基可行解的概念 对于标准形式的线性规划，利用向量矩阵记号，令X=（x1，x2，xn）T，C=（c1，c2，cn），b=（b1，b2，bm）T，A=（aij）mn。 X，C，b分别称为决策变量向量，价值向量，资源向量（右端常数向量），A称为系数矩阵。Pj=（a1j，a2j，amj）T是xj的系数列向量，它是A的第j列，A=（P1，P2，Pn）。 利用这些记号，标准形线性规划可表示为：,或者写成：,设系数矩阵A的秩是m，

11、即A的m个行向量是线 性无关的。若B是A的m阶满秩子阵，称B为问题的 一个基。设B=（ ， ， ），称对应的 变量 ， ， 为基变量，其它的变量称为 非基变量。令非基变量等于0，从方程组可以唯一 解出基变量的值，从而得到方程组的一个解，称 为基本解；如果它的各个分量非负，即它同时又 是可行解，则称之为基可行解，对应的基称为可行基。 可行解是约束方程组的解并且满足非负条件； 基本解是约束方程组具有特定性质的解，它至多有m 个非0分量，但未必满足非负性。基可行解同时具有 两者的性质。,【例】,它的系数矩阵为：,A的子矩阵（P3，P4，P5）正好是单位矩阵，这种形式的方程组称为典式，或称为对x3，x

12、4，x5的解出形式。以（P3，P4，P5）为基，令非基变量x1=x2=0，则基变量正好等于右端常数值，得到基可行解X=（0，0，8，20，12）T。,所有基本解见表1-4,三、 LP解的性质,定理1 线性规划的可行域R是凸集。 定理2 X是线性规划基可行解的充分必要 条件是X是可行域的极点。 定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。 基可行解至多有 个,第三节 单纯形法 （重点）,一、 单纯形法的解题思路,【例】,约束方程组已经是对于x3，x4，x5的解出形式，以它们作为第一组（初始）基变量，得基可行解X1=(0,0,8,20,12)T，目标函数

13、值z1=0。,（1）,从目标函数z=2x1+5x2来看，如果x1或x2成为基变量（简称入基），变成正值，则z值将会上升。由于x2系数更大，引入x2更有利于z的上升，故首先选择x2入基，x1仍然保持是非基变量。此时约束方程组实际成为：,可知x2min8/2，20/2，12/4=3 这时x5=0，因此，x5退出基，成为非基变量。,把约束方程组（1）转化为对新基变量x2,x3,x4的解出形式：,从中可得基可行解X2=(0,3,2,14,0)T，相应z2=53=15，函数值上升了15个单位。,（2）,由（2）第三式得到x2=3 x5，代入z的表达式，得到 z=2x1+5x2=2x1+5（3 x5）=2

14、x1 x5+15 x1的系数为正，故引入x1，x5保持为0 由 知x1min2/1，14/5，=2 取x1=2，则x3=0，x3退出基。然后把方程组（2）变换为对x1，x2，x4的解出形式：,（3）,新的基可行解X3=(2,3,0,4,0)T，相应z值z3=22+53=19,由（3）的第一式得到x1=2x3+ x5代入（2）中。 z=2（2x3+ x5） x5+15=2x3 x5+19 此式表明z19，而当X=X3时，z=19，因此X3是问题最优解，z的最优值是19万元。 总结： 单纯形法是一种迭代算法，每步迭代包括下列环节： 首先判定当前基可行解是否最优，若是，则结束；否则，先确定换入变量，

15、再确定换出变量，最后把方程组转化为对新基变量的解出形式，得到新的基可行解。,二、 单纯形法要点和单纯形表,1. 检验数的意义和计算公式,假定所有b1，bm0。显然问题有基可行解X1=(b1,b2,bm,0,0)T，相应目标函数值 。 i=（1，2，m）,基变量的检验数永远为0。 非基变量xj的检验数j是引入xj一个单位时目标函数z的改变量，只有j0时，方值得让xj入基。,2.单纯形表,表1-5,总结,从表中可以直接读出基可行解X：xi=bi（i=1，m），其它xj=0； 相应目标函数值 ，是CB列与b列元素乘积之和； 每个变量xj（包括基变量在内）的检验数j，等于cj减去CB列元素与表中xj的

16、系数列向量元素乘积之和。 单纯形法的全部分析和计算过程，可以比较方便地在单纯形表中完成。,3. 单纯形法的基本法则,法则1 最优性判定法则 若对基可行解X1，所有检验数j0，则X1为最优解。,法则2 换入变量确定法则（最大价值系数法则） 设 ，则xk为换入变量。,法则3 换出变量确定法则 （最小比值法则） 设xk为换入变量，并设 则最小比值所在行的原基变量xl为换出变量。,法则4 换基迭代运算法则 对方程组的增广矩阵实施行的初等变换，使主元alk化为1，主元列其它元素化为0。具体地说，第l行乘以1/alk，并将第l行的aik/alk倍加到第i行上去，i=1，2，m，il。,例一 求下列LP问题

17、的最优解,例二 求下列LP问题的最优解,三、 关于单纯形法的补充说明,1. 无穷多最优解与唯一最优解的判别法则 若对某可行解X1， （1）所有检验数j0，且有一个非基变量xk的检验数等于0，则问题有无穷多最优解； （2）所有非基变量的检验数j0，则问题有唯一最优解。,例三 求下列LP问题的最优解,2. 无最优解（无界解）的判定,若对基可行解X1，存在非基变量xk的检验数k0，但aik0，i=1，2，m即xk的系数列向量无正分量，则问题无最优解。 如上例中，,3. 求min z 的情况,这时可以有两种处理方式： 一种方式是令z1=z，转化为求max z1， 另一种是直接计算。 最优性检验条件改为

18、：所有j0； 换入变量确定法则改为：如果 则xk为换入变量。 单纯形法的其它要点完全无须改变。,例：,解：方程组化为：,第四节 初始可行基的求法人工变量法,一、 大M法 【例1-15】 求下列LP问题的最优解,解： 引入松弛变量x4，x5，把问题化为标准形式的LP（简称P1）,给后两个方程分别添加人工变量x6，x7，使约束方程组化为,（P1）,（P2）,设X=(x1，x2，x3，x4，x5)T，XA=(x6，x7)T。 （1）若（P1）有最优解X*，则X*，XA*=0是（P2）的最优解； （2）若（P2）有最优解X*与XA*=0，则X*是（P1）的最优解；如果（P2）最优解中XA*0，则（P1）无可行解。,