资源描述:
《线性规划的图解法课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第二章线性规划的图解法在管理中一些典型的线性规划应用合理利用线材问题:如何在保证生产的条件下,下料最少配料问题:在原料供应量的限制下如何获取最大利润投资问题:从投资项目中选取方案,使投资回报最大产品生产计划:合理利用人力、物力、财力等,使获利最大劳动力安排:用最少的劳动力来满足工作的需要运输问题:如何制定调运方案,使总运费最小线性规划模型的组成:决策变量用符号来表示可控制的因素目标函数MaxF或MinF约束条件s.t.(subjectto)满足于1§1问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限
2、制,如下表:问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?线性规划模型:目标函数:Maxz=50x1+100x2约束条件:s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥02一家工厂制造三种产品,需要三种资源:技术服务、劳动力、行政管理。下表列出了三种单位产品对每种资源的需要量。今有100h的技术服务,600h的劳动力和300h的行政管理时间可供使用。试确定能使总利润最大的产品生产量的线性规划模型。3解:设三种产品的生产量分别为x1、x2、x3。线性规划模型为:Maxz=10x1+6x2+4x3S.t.x1+x2+x3≤10010x1+4x
3、2+5x3≤6002x1+2x2+6x3≤300x1,x2,x3≥04例2M&D公司生产两种产品A和B,基于对现有的存储水平和下一个月的市场潜力的分析,M&D公司管理层决定A和B的总产量至少要达到350千克,此外,公司的一个客户订了125千克的A产品必须首先满足。每千克A、B产品的制造时间分别为2小时和1小时,总工作时间为600小时。每千克A、B产品的原材料成本分别为2$和3$。确定在满足客户要求的前提下,原材料成本最小的生产计划。56§1问题的提出建模过程1.理解要解决的问题,了解解题的目标和条件;2.定义决策变量(x1,x2,…,xn),每一组值表示一个方案;3.用决策
4、变量的线性函数形式写出目标函数,确定最大化或最小化目标;4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件一般形式目标函数:Max(Min)z=c1x1+c2x2+…+cnxn约束条件:s.t.a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2…………am1x1+am2x2+…+amnxn≤(=,≥)bmx1,x2,…,xn≥07max(min)z=c1x1+c2x2+……+cnxnx1,x2,……,xn≥0st.a11x1+a12x2+……+a1nxn≤(或=,≥)b1a21x1+a22x2+……
5、+a2nxn≤(或=,≥)b2an1x1+a2nx2+……+annxn≤(或=,≥)bm……目标函数约束条件决策变量xj称为该问题的决策变量。资源拥有量价值系数在目标函数中xj的系数cj称为该决策变量的价值系数。技术系数或工艺系数aij称为该问题的技术系数或工艺系数。由所有aij组成的矩阵称为约束方程的系数矩阵。在问题中,xj的取值受m项资源的约束,bi称为第i项资源的拥有量。8其它表示方式xj≥0(j=1,2,……,n)st.max(min)z=cjxjaijxj≤(或=,≥)bi(i=1,2,……,m)max(min)z=X≥0st.CXC=(c1,c2,…,cn)Pj
6、xj≤(或=,≥)b用向量表达Pj=(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)9例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
7、§2 图解法对于只有两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示线性规划问题的有关概念,并求解。下面通过例1详细讲解其方法:10图解线性规划问题步骤第一步,画直角坐标系第二步,根据约束条件画可行域第三步,画过坐标原点的目标函数线,斜率为-c1/c2第四步,确定目标函数值的增大(减小)方向第五步,让目标函数沿着增大(减小)方向平行移动,与可行域相交且有最大(最小)目标函数值的顶点,即为线性规划问题的最优解,然后根据最优解求最优值。11x1x2z=20000=50x1+100x2图z=27500=50x1