第1章线性规划标准型和图解法精.ppt

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