线性规划-标准型和图解法.ppt

1,第2章 线性规划,宁波大学商学院,2,线性规划应用的典型情况,制造者希望建立一个生产时间表和库存计划以满足未来一段时间的市场需求，最理想的情况是：既满足市场上产品的需求、同时又使生产和库存的成本最低； 金融分析员必须选择一种股票或证券进行投资，金融分析员希望使自己的投资有最大的回报率； 营销经理希望能够从广播、电视、报纸、杂志这几种媒体中选择一种合适的组合，确定广告预算使自己的广告效益最好； 公司的仓库分布于全美各地，现在有一些顾客订单，公司希望确定每个仓库的发货量使成本最低 ,3,问题的提出,例1 （生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品的资源消耗、单位产品利润等数据如表所示，问如何安排生产计划使企业利润最大？,产品,资源,单耗,4,解：设x、y分别代表甲、乙两种产品的生 产数量（件），z表示公司总利润。则有 max z=50x+100y s.t. x+y300 2x+y 400 y 250 x，y0,规划问题的数学模型,5,线性规划应用的典型情况,这类例子的共同特点： 要求目标函数最大化或最小化； 一定存在约束条件，而且这些约束条件会影响目标的实现。,6,基本概念,1、给定有限资源，充分利用资源最大限度地实现目标 2、给定目标，要求完成任务使用的资源最少 目标函数：表示最大目标或是最小资源 约束条件：表示资源的约束或是目标约束 非负条件：往往实际问题中变量不允许为负，而 问题不一定明确指出，需要自己判断。一般定义为 0,7,线性规划问题的数学模型,规划问题的数学模型三要素 决策变量：问题中要确定的未知量，用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制； 目标函数：它是决策变量的函数，按优化目标分别在这个函数前加上max或min； 约束条件：指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。,8,线性规划:是指约束条件和目标函数都是线性时的规划模型。 实际问题中线性的含义：一是严格的比例性；二是可叠加 性。 非线性规划的例子: KT条件、0.618法、梯度法、随机搜索法 等。,规划问题的数学模型,9,10,线性规划数学模型,目标函数,约束条件,决策变量,11,线性规划数学模型,简写形式,12,线性规划数学模型,向量形式,13,线性规划数学模型,用矩阵和向量形式,14,决策变量的取值,变量xj的取值一般为非负，即xj 0 从数学意义上来说，可以有xj 0 xj的取值也可以是(,+ )，即xj取值不受约束或称xj无约束,15,max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2, ,xn0,线性规划问题的标准形式,目标函数极大化,约束条件为等号,变量非负,右端常数项 大于或等于零,16,简写形式 矩阵形式,线性规划问题的标准形式,17,线性规划问题的标准形式,若min f=CX，可令z=f，则max z=min f； 目标函数为 min f=c1x1+c2x2+cnxn 令z=f，变为 max z= c1x1 c2x2- cnxn,18,线性规划问题的标准形式,约束条件为“”时，则约束条件左式加上非负的松弛变量xn+i，将约束条件变为等式约束； 约束条件为 a11x1+a12x2+a1nxnb1 加入非负变量xn+1，称为松弛变量，有 a11x1+a12x2+a1nxn+xn+1=b1,19,线性规划问题的标准形式,约束条件为“”时，则约束条件左式减去非负的剩余变量xn+i，将约束条件变为等式约束； 约束条件为 a11x1+a12x2+a1nxnb1 减去非负变量xn+1，称为剩余变量，有 a11x1+a12x2+a1nxnxn+1=b1,20,线性规划问题的标准形式,若xk无限制时，则令xkxk1xk2，其中xk1、xk2 0； 若bi0。,21,例,化下列线性规划为标准形式 max z=2 x1 +2 x24 x3 s.t. x1 +3 x2 3 x3 30 x1 +2 x2 4 x3 80 x1 、 x2 0, x3无限制,22,解：该线性规划问题的标准形式为 max z=2x1+2x24x31+4x32 x1+3x2 3x31+3x32x4=30 x1+2x24x31+4x32+x5=80 x1、x2、x31、x32、x4、x50,23,例,24,解：令,则,加入松驰变量s,w，得到标准型如下：,25,回顾： 学校准备为学生添加营养餐，每个学生每月至少需要补充60单位的碳水化合物，40单位的蛋白质和35单位的脂肪。已知两种营养品每斤： A B 含量 碳水化合物 5 2 蛋白质 3 2 脂肪 5 1 单价 1.5 0.7 问题：买A和B分别多少斤既满足学生营养需要又省钱？,目标函数： x+ y 取最小值,约束条件： x+ y 60,x+ y 40,x+ y 35,变量： x y,非负条件： x 0,y 0,26,表达式,min S(x,y)=1.5x+0.7y s.t. 5x+2y60 3x+2y40 5x+y 35 x 0 y 0,27,图解法,为了便于建立 n 维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。 如果模型中只含有2个变量的线性规划问题，可以通过在平面上作图的方法求解。,28,图解法,图解法求解的目的：一是判别线性规划问题的求解结局，二是在存在最优解的条件下，把问题的最优解找出来。,29,图解法,求解下述线性规划问题,30,图解法,画出线性规划问题的可行域,31,图解法,目标函数的几何意义：,32,图解法,最优解的确定,33,第一 建立坐标系，将约束条件在图上表示出来 第二 确立满足约束条件的解的范围； 第三 画出两条目标函数等值线； 第四 平行移动目标函数等值线，使目标函数在可行域范围内达到最优。,线性规划图解法,34,图解法,无穷多最优解的情况,目标函数与某个约束 条件恰好平行,35,图解法,无界解（或无最优解）的情况,可行域上方无界,36,图解法,无解的情况,约束条件不存在公共范围,37,例,max z=50x1+100x2 s.t. x1+ x2300 2x1+x2400 x1、 x2 0, x2250,x2,x2250,2x1+x2400,x1 + x2300,38,例,max z=50x1+50x2 s.t. x1+ x2300 2x1+x2400 x1、 x2 0 x2250,39,max z=2x+2y s.t. x y1 x+2y0 x、y 0,A1,例,40,Y,例,X,max z=x+2y s.t. x+2y1 x+y 2 x、y 0, x+2y1,x+y 2,O,41,图解法的启示：,求解线性规划问题时，解的情况有：唯一最优解，无穷多最优解，无界界，无可行解； 若线性规划问题可行域存在，在可行域是一个凸集； 若线性规划问题最优解存在，在最优解或最优解之一一定能够在可行域的某个顶点取得； 解题思路是，先找凸集的任一顶点，计算其目标函数值。比较其相邻顶点函数值，若更优，则逐点转移，直到找到最优解。,42,练习,max S(x,y)=7x+12y 9x+4y 360 4x+5y 200 3x+10y 300 x,y0,F (0,90),G( 0,40),A (0,30),D( 40,0),H (50,0),E (100,0),B,C,O(0,0),9x+4y=360,4x+5y=200,3x+10y=300,答案：最优解为 B(20,24)。,43,练习： min S(x,y)=200x+160y 6x+2y12 2