您好,欢迎访问三七文档
第二章线性规划的图解法在管理中一些典型的线性规划应用•合理利用线材问题:如何在保证生产的条件下,下料最少•配料问题:在原料供应量的限制下如何获取最大利润•投资问题:从投资项目中选取方案,使投资回报最大•产品生产计划:合理利用人力、物力、财力等,使获利最大•劳动力安排:用最少的劳动力来满足工作的需要•运输问题:如何制定调运方案,使总运费最小线性规划模型的组成:•决策变量用符号来表示可控制的因素•目标函数MaxF或MinF•约束条件s.t.(subjectto)满足于§1问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表:问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?ⅠⅡ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元线性规划模型:目标函数:Maxz=50x1+100x2约束条件:s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0•一家工厂制造三种产品,需要三种资源:技术服务、劳动力、行政管理。下表列出了三种单位产品对每种资源的需要量。今有100h的技术服务,600h的劳动力和300h的行政管理时间可供使用。试确定能使总利润最大的产品生产量的线性规划模型。产品资源/h单位利润/元技术服务劳动力行政管理11102102142631564•解:设三种产品的生产量分别为x1、x2、x3。•线性规划模型为:•Maxz=10x1+6x2+4x3•S.t.x1+x2+x3≤100•10x1+4x2+5x3≤600•2x1+2x2+6x3≤300•x1,x2,x3≥0例2M&D公司生产两种产品A和B,基于对现有的存储水平和下一个月的市场潜力的分析,M&D公司管理层决定A和B的总产量至少要达到350千克,此外,公司的一个客户订了125千克的A产品必须首先满足。每千克A、B产品的制造时间分别为2小时和1小时,总工作时间为600小时。每千克A、B产品的原材料成本分别为2$和3$。确定在满足客户要求的前提下,原材料成本最小的生产计划。解:设产品A、B的产量分别为y,x。则,数学模型为:0600235012532y,xyxyxxyxZmin§1问题的提出•建模过程1.理解要解决的问题,了解解题的目标和条件;2.定义决策变量(x1,x2,…,xn),每一组值表示一个方案;3.用决策变量的线性函数形式写出目标函数,确定最大化或最小化目标;4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件•一般形式目标函数:Max(Min)z=c1x1+c2x2+…+cnxn约束条件:s.t.a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2…………am1x1+am2x2+…+amnxn≤(=,≥)bmx1,x2,…,xn≥0max(min)z=c1x1+c2x2+……+cnxnx1,x2,……,xn≥0st.a11x1+a12x2+……+a1nxn≤(或=,≥)b1a21x1+a22x2+……+a2nxn≤(或=,≥)b2an1x1+a2nx2+……+annxn≤(或=,≥)bm……目标函数约束条件决策变量xj称为该问题的决策变量。资源拥有量价值系数在目标函数中xj的系数cj称为该决策变量的价值系数。技术系数或工艺系数aij称为该问题的技术系数或工艺系数。由所有aij组成的矩阵称为约束方程的系数矩阵。在问题中,xj的取值受m项资源的约束,bi称为第i项资源的拥有量。其它表示方式xj≥0(j=1,2,……,n)st.max(min)z=nj1cjxjnj1aijxj≤(或=,≥)bi(i=1,2,……,m)max(min)z=X≥0st.CXC=(c1,c2,…,cn)Pjxj≤(或=,≥)b用向量表达nj1Pj=(a1j,a2j,……,anj)Tb=(b1,b2,……,bm)T简化表示X=(x1,x2,……,xn)T其中X≥0st.AX≤(或=,≥)b用矩阵表达A=a11a12…a1na21a22…a2nam1am2amn………矩阵A称为约束方程组(约束条件)的系数矩阵。max(min)z=CXC=(c1,c2,……,cn)例2-1.目标函数:Maxz=50x1+100x2约束条件:s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解:x1=50,x2=250最优目标值z=27500§2图解法对于只有两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示线性规划问题的有关概念,并求解。下面通过例1详细讲解其方法:图解线性规划问题步骤•第一步,画直角坐标系•第二步,根据约束条件画可行域•第三步,画过坐标原点的目标函数线,斜率为-c1/c2•第四步,确定目标函数值的增大(减小)方向•第五步,让目标函数沿着增大(减小)方向平行移动,与可行域相交且有最大(最小)目标函数值的顶点,即为线性规划问题的最优解,然后根据最优解求最优值。x1x2z=20000=50x1+100x2图z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE二元一次不等式(组)表示的平面区域的确定•怎样判断二元一次不等式表示的是直线哪一侧的平面区域?0CByAx0CByAx可以用“选点法”确定具体区域:任选一个不在直线上的点,检验它的坐标是否满足所给的不等式.若适合,则该点所在的一侧即为不等式所表示的平面区域;否则,直线的另一侧为所求的平面区域.•画出下列不等式所表示的平面区域:•(1)y-2x+1(2)x-y+20•(1)x0(2)6x+5y≤22(3)yx§2图解法(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里,图上任意一点的坐标代表了决策变量的一组值,例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0§2图解法(2)对每个不等式(约束条件),先取其等式在坐标系中作直线,然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400§2图解法(3)把五个图合并成一个图,取各约束条件的公共部分,如图2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1§2图解法(4)目标函数z=50x1+100x2,当z取某一固定值时得到一条直线,直线上的每一点都具有相同的目标函数值,称之为“等值线”。平行移动等值线,当移动到B点时,z在可行域内实现了最大化。A,B,C,D,E是可行域的顶点,对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE21112100xxZ斜截式价值系数的符号与目标函数直线族的平行移动•写成斜截式比较容易弄清楚移动方向•Z=50x1+100x2(+,+)•求最大右上方移动,求最小左下方移动•Z=-50x1-100x2(-,-)•求最大左下方移动,求最小右上方移动•Z=-50x1+100x2(-,+)•求最大左上方移动,求最小右下方移动•Z=50x1-100x2(+,-)•求最大右下方移动,求最小左上方移动21112100xxZ21112100xxZ21112100xxZ21112100xxZ关键在C2,C2为正,则往上平移;C2为负,则往下平移x1x2O1020304010203040(300,400)(15,10)最优解X=(15,10)最优值Z=850040221xx305.121xx0,0305.1402212121xxxxxx例2-212max300400Zxx246x1x2246最优解X=(3,1)最优值Z=5(3,1)006346321212121xxxxxxxx、minZ=x1+2x2例2-3(1,2)246x1x2246X(2)=(3,1)X(1)=(1,3)(5,5)006346321212121xxxxxxxx、minZ=5x1+5x2例2-4有无穷多个最优解即具有多重解,通解为0≤α≤1当α=0.5时X=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)246x1x2246(1,2)006346321212121xxxxxxxx、无界解(无最优解)maxZ=x1+2x2例2-5x1x2O102030401020304050500,050305.140221212121xxxxxxxx无可行解即无最优解maxZ=10x1+4x2例2-6由以上例题可知,线性规划的解有4种形式:1.有唯一最优解(例2-2例2-3)2.有多重最优解(例2-4)3.有无界解(例2-5)4.无可行解(例2-6)1、2情形为有最优解3、4情形为无最优解§2图解法•重要结论:–如果线性规划有最优解,则一定可以在可行域的某个顶点上找到最优解;–无穷多个最优解,在边界上取得。若将例2-1中的目标函数变为maxz=50x1+50x2,则线段BC上的所有点都代表了最优解;–无界解。即可行域的范围延伸到无穷远,目标函数值可以无穷大或无穷小。一般来说,这说明模型有错,忽略了一些必要的约束条件;–无可行解。若在例2-1的数学模型中再增加一个约束条件4x1+3x2≥1200,则可行域为空域,不存在满足约束条件的解,当然也就不存在最优解了。进一步讨论例2某公司由于生产需要,共需要A,B两种原料至少350吨(A,B两种材料有一定替代性),其中A原料至少购进125吨。但由于A,B两种原料的规格不同,各自所需的加工时间也是不同的,加工每吨A原料需要2个小时,加工每吨B原料需要1小时,而公司总共有600个加工小时。又知道每吨A原料的价格为2万元,每吨B原料的价格为3万元,试问在满足生产需要的前提下,在公司加工能力的范围内,如何购买A,B两种原料,使得购进成本最低?进一步讨论解:目标函数:Minf=2x1+3x2约束条件:s.t.x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0采用图解法。如下图:得Q点坐标(250,100)为最优解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q§3线性规划模型的标准化标准化便于代数求解,为后面单纯形法求解作准备。•一般形式目标函数:Max(Min)z=c1x1+c2x2+…+cnxn约束条件:s.t.a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2…………am1x1+am2x2+…+amnxn≤(=,≥)bmx1,x2,…,xn≥0•标准形式目标函数:Maxz=c1x1+c2x2+…+cnxn约束条件:s.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………am1x1+am2x2+…+amnxn=bmx1,x2,…,xn≥0,bi≥0§3线性规划的标准化可以看出,线性规划的标准形式有如下四个特点:–目标最大化;–约束为等式;–决策变量均非负;–右端项非负。对于各种非标准形式的线性规划问题,我们总可以通过以下变换,将其转化为标准形式:§3线性规划的标准化1、决策变量不是非负在标准形式中,必须每一个变量均有非负约
本文标题:线性规划的图解法
链接地址:https://www.777doc.com/doc-4537731 .html