线性规划 课件.ppt
线性规划线性规划 第1页，此课件共28页哦教学目标与要求教学目标与要求n【教学目标教学目标】n通过对本章的学习，理解线性规划的含义、解、可行解、可行域、基解、通过对本章的学习，理解线性规划的含义、解、可行解、可行域、基解、基可行解、最优解的定义；掌握图解法、单纯形法（包括大基可行解、最优解的定义；掌握图解法、单纯形法（包括大M法）；会建法）；会建立线性规划数学模型；至少掌握一种软件求解立线性规划数学模型；至少掌握一种软件求解LPn【知识结构知识结构】第2页，此课件共28页哦2022/10/10导入案例导入案例最优生产计划最优生产计划第3页，此课件共28页哦2022/10/10本章主要内容本章主要内容 n2.1 线性规划问题与模型线性规划问题与模型n2.1.1 线性规划问题的提出线性规划问题的提出n2.1.2 线性规划的数学模型线性规划的数学模型n2.1.3 线性规划标准模型线性规划标准模型n2.2 图解法图解法n2.2.1 线性规划几何解的有关概念线性规划几何解的有关概念n2.2.2 图解法基本步骤图解法基本步骤n2.2.3 线性规划几何解的讨论线性规划几何解的讨论n2.3 单纯形法单纯形法n2.3.1 线性规划解的有关概念及性质线性规划解的有关概念及性质n2.3.2 单纯形法单纯形法n2.4 人工变量法人工变量法n2.5 线性规划应用举例线性规划应用举例n案例案例2-1 媒体选择问题媒体选择问题n案例案例2-2 投资计划问题投资计划问题n案例案例2-3 自制自制/外购决策问题外购决策问题n案例案例2-4 合理下料问题合理下料问题n本章小结本章小结第4页，此课件共28页哦2022/10/102.1.1 线性规划问题的提出产品甲 产品乙生产能力设备A设备B2111108单位利润32承导入案例承导入案例设两种产品产量为设两种产品产量为x1,x2,则有则有:总利润表达式总利润表达式最大化最大化设备设备A台时占用台时占用设备设备B台时占用台时占用生产能力生产能力,不不允许超过允许超过产量非负产量非负决策变量决策变量（decision variable）目标函数目标函数（objective function）约束条件约束条件（subject to）三要素三要素当目标函数与约束条件均为决策变量当目标函数与约束条件均为决策变量的线性函数，且变量取连续值时，称的线性函数，且变量取连续值时，称为线性规划为线性规划LP；变量取整称为整数线；变量取整称为整数线性规划性规划ILP；变量取二进制为；变量取二进制为0-1规划规划BLP。第5页，此课件共28页哦2022/10/102.1.2 线性规划的数学模型线性规划的数学模型【例例2.1】（合理配料问题）由下表建立一个（合理配料问题）由下表建立一个LP模型求解满足动物成长需要又使成本模型求解满足动物成长需要又使成本最低的饲料配方。最低的饲料配方。饲料营养甲(g/kg)营养乙(g/kg)营养丙(g/kg)成本(g/kg)10.50.10.082220.060.76330.040.35541.50.150.25450.80.20.023解解 设设xi为第为第i种饲料的用量，有：种饲料的用量，有：满足营养甲需求满足营养甲需求满足营养乙需求满足营养乙需求满足营养丙需求满足营养丙需求变量非负限制变量非负限制目标是总成本最低目标是总成本最低第6页，此课件共28页哦2022/10/102.1.2 线性规划的数学模型线性规划的数学模型线性规划的一般形式：线性规划的一般形式：线性规划的集合形式线性规划的集合形式：线性规划的向量形式线性规划的向量形式：线性规划的矩阵形式线性规划的矩阵形式：第7页，此课件共28页哦2022/10/102.1.3 线性规划的标准模型线性规划的标准模型标准形式标准形式:目标函数最大化、约束条件为等式、决策变量均非负、右端项非负目标函数最大化、约束条件为等式、决策变量均非负、右端项非负.非标准形式进行如下转化非标准形式进行如下转化:第8页，此课件共28页哦2022/10/102.1.3 线性规划的标准模型线性规划的标准模型【例【例2.2】将】将LP模型转化为标准式模型转化为标准式解解 （1）决策变量变为非负）决策变量变为非负（2）目标函数最大化）目标函数最大化（3）右端项变为非负）右端项变为非负（4）约束一、三添加松弛变量；约束）约束一、三添加松弛变量；约束二减剩余变量。二减剩余变量。第9页，此课件共28页哦2022/10/102.2.1 线性规划几何解的有关概念线性规划几何解的有关概念第10页，此课件共28页哦2022/10/10可行域可行域2.2.2 图解法基本步骤图解法基本步骤n建立直角坐标系；建立直角坐标系；n图示约束条件，确定右行域；图示约束条件，确定右行域；n图示目标函数一根基线，按目标要求图示目标函数一根基线，按目标要求平行移动，与可行域相切，切点即为平行移动，与可行域相切，切点即为最优解；最优解；n求出切点坐标，并代入目标函数求得求出切点坐标，并代入目标函数求得最优值。最优值。【例【例2.3】用图解法求】用图解法求LP最优解最优解ox1x22x1+x2=10 x1+x2=8令3x1+2x2=121058864(2,6)z=32+26=18最优解：x1=2,x2=6最优值：z=18第11页，此课件共28页哦2022/10/102.2.3 线性规划几何解的讨论线性规划几何解的讨论n线性规划几何解存在四种情况：唯一最优解、无穷多最优线性规划几何解存在四种情况：唯一最优解、无穷多最优解、无界解、无可行解。解、无界解、无可行解。可行域为封闭有界区域时，可能存在唯一最优解，无穷多可行域为封闭有界区域时，可能存在唯一最优解，无穷多最优解两种情况；最优解两种情况；可行域为非封闭无界区域时，可能存在唯一最优解，无穷可行域为非封闭无界区域时，可能存在唯一最优解，无穷多最优解，无界解三种情况；多最优解，无界解三种情况；可行域为空集时，没有可行解，原问题没有最优解。可行域为空集时，没有可行解，原问题没有最优解。n若线性规划存在最优解，则最优解或最优解之一肯定能若线性规划存在最优解，则最优解或最优解之一肯定能够在可行域（凸集）的某个极点找到（所谓凸集是指集够在可行域（凸集）的某个极点找到（所谓凸集是指集合中任何两点的连线上的点仍在集合中）。合中任何两点的连线上的点仍在集合中）。第12页，此课件共28页哦2022/10/102.3.1 线性规划解的有关概念及性质线性规划解的有关概念及性质承导入案例承导入案例LP模型：模型：ACXbCNCBXNXBNBb基基基变量基变量非基非基 非基变量非基变量B-1b基解基解;若满足若满足XB0,称基称基可行解可行解.第13页，此课件共28页哦2022/10/102.3.2 单纯形法单纯形法一般而言，一般而言，B为为A中任一中任一mm阶使阶使XB非非负、负、XN为为0的可逆矩阵，由：的可逆矩阵，由：约束条件两端左乘约束条件两端左乘B-1得基变量的非基变得基变量的非基变量表达：量表达：代入目标函数，得：代入目标函数，得：常数常数考察该项考察该项可见目标函数为非基变量的线性函可见目标函数为非基变量的线性函数。数。当当N所有元素非正时，目标函数值达所有元素非正时，目标函数值达到最大，得到了最优解。因为任何一到最大，得到了最优解。因为任何一个非基变量入基后，不会使目标函数个非基变量入基后，不会使目标函数值增大。值增大。若若N某元素（假设第某元素（假设第k个元素）个元素）0，则该非基变量入基，会使目标函数则该非基变量入基，会使目标函数值增大。值增大。N中若有多个元素中若有多个元素0，选择其，选择其中最大的（假设第中最大的（假设第k个元素）非基变量个元素）非基变量xk入基，会使目标函数值增加的更快，入基，会使目标函数值增加的更快，于是确定于是确定xk为入基变量，为入基变量，N称为检验称为检验数。数。第14页，此课件共28页哦2022/10/102.3.2 单纯形法单纯形法由于基变量为由于基变量为m个，有一个入基，必然有个，有一个入基，必然有一个出基，哪个出基呢？在确定初始基时，一个出基，哪个出基呢？在确定初始基时，选择选择B为单位矩阵，则下式为单位矩阵，则下式可简化为：可简化为：即：即：xk入基入基,其余仍为其余仍为0，故有，故有当当xk的值由的值由0增加到增加到时，原来的基变量时，原来的基变量xl取值取值首先变成零，选择其为出基变量。称首先变成零，选择其为出基变量。称的表的表达式为最小比值原则。达式为最小比值原则。如果所有如果所有aik 0,xk的值可以由的值可以由0增加到无穷，增加到无穷，表示可行域是不封闭的，且目标函数值表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时随进基变量的增加可以无限增加，此时不存在有限最优解。不存在有限最优解。下面对以上讨论进行总结下面对以上讨论进行总结.第15页，此课件共28页哦2022/10/102.3.2 单纯形法单纯形法单纯形法解题步骤单纯形法解题步骤:1.使使LP模型右端项非负、约束符取模型右端项非负、约束符取“=”、目标函数、目标函数max（即标准化），并设法（即标准化），并设法在约束系数中构造一个单位矩阵在约束系数中构造一个单位矩阵,令其为初始基令其为初始基,该基必为可行基，右端项即该基必为可行基，右端项即为基可行解。为基可行解。2.求检验数求检验数.若所有检验数均不大于若所有检验数均不大于0，找到最优解，计算结束；若存在大于，找到最优解，计算结束；若存在大于0的检的检验数，找出最大者验数，找出最大者k，对应的变量，对应的变量xk为入基变量。为入基变量。3.若若alk均不大于均不大于0，则解无界，计算结束，否则找出最小比值：，则解无界，计算结束，否则找出最小比值：对应的变量对应的变量xl为出基变量。为出基变量。4.用入基变量替换出基变量，并通过行初等变换将基变成单位矩阵，右端项即用入基变量替换出基变量，并通过行初等变换将基变成单位矩阵，右端项即为基可行解，转第为基可行解，转第2步。步。第16页，此课件共28页哦2022/10/102.3.2 单纯形法单纯形法第17页，此课件共28页哦2022/10/102.3.2 单纯形法单纯形法例：承导入案例例：承导入案例x1x2x3x4基cj3200bx3x40021111001108cj-zjB标准化标准化基可基可行解行解3210/2=58/1=8 第18页，此课件共28页哦2022/10/102.3.2 单纯形法单纯形法x1x2x3x4基cj3200bx3x4002111100110858cj-zj320 x1x2x3x4基cj3200bx1x430101/21/21/2-1/20153106cj-zj1/2-3/215将入基变量替换出基变量，列出新的单纯形表，并通过初等变换将将入基变量替换出基变量，列出新的单纯形表，并通过初等变换将新基变成单元阵：新基变成单元阵：x1x2x3x4基cj3200bx1x23210011-1-1226cj-zj-1-118最优解最优解最优值最优值第19页，此课件共28页哦2022/10/102.4 工人变量法工人变量法用单纯形法求解用单纯形法求解LP要求能找出一个单位阵作为初始基。因此，当约束符均要求能找出一个单位阵作为初始基。因此，当约束符均为为“”时，把松弛变量作为初始基变量，则可直接列出单纯形表；若存在时，把松弛变量作为初始基变量，则可直接列出单纯形表；若存在约束符为约束符为“”或或“=”，则不一定能找出一个单位阵，这种情况通常，则不一定能找出一个单位阵，这种情况通常要添加人工变量（要添加人工变量（artificial variable），将所有松弛变量和人工变），将所有松弛变量和人工变量作为初始基变量，则可列出单纯形表。但原本约束已经取量作为初始基变量，则可列出单纯形表。但原本约束已经取“=”，因此，必须使人工变量为，因此，必须使人工变量为0才是可行解。故在迭代过程中如果最终才是可行解。故在迭代过程中如果最终单纯形表中含有人工变量，则该单纯形表中含有人工变量，则该LP无可行解。采取的办法是设目标无可行解。采取的办法是设目标函数中人工变量的系数为函数中人工变量的系数为“-M”（M为任意大的有界正数），如果最终为任意大的有界正数），如果最终单纯形表中含有人工变量，则目标函数不会实现最大化。这种通过添加单纯形表中含有人工变量，则目标函数不会实现最大化。这种通过添加人工变量来找初始基的方法称为人工变量法。求解具有人工变量的人工变量来找初始基的方法称为人工变量法。求解具有人工变量的LP，通常用通常用“两阶段法两阶段法”或或“大大M法法”来解决。下面通过例来解决。下面通过例2.3为例，说为例，说明明“大大M法法”的应用。的应用。第20页，此课件共28页哦2022/10/102.4 工人变量法工人变量法【例【例2.4】求解】求解LP问题问题标准化标准化添加人工变量添加人工变量X1X2X3X4基cj320-MB-1b比值X4X3-M02111011010858j=cj-zj32*M21X1X2X3X4基cj320-MB-1b比值X1X2321001-111-126j=cj-zj-1-118*M-1X1X2X3X4基cj320-MB-1b比值X1X330101/21/2011/2-1/25358j=cj-zj1/2-3/2*M-1第21页，此课件共28页哦2022/10/102.5 应用举例应用举例第22页，此课件共28页哦2022/10/10案例案例2-1 广告媒体选择广告媒体选择2400000102300000180000max目标函数目标函数可达消费者人数可达消费者人数总费用限制总费用限制电视广告费限制电视广告费限制第23页，此课件共28页哦2022/10/10案例案例2-2 公司投资计划公司投资计划 A、B、C、D四个产品项目投资四个产品项目投资6000万元。万元。产品项目产品项目A:15年每年年初投资，当年年末收回本利年每年年初投资，当年年末收回本利110%。产品项目产品项目B：14年每年年初投资，次年年末收回本利年每年年初投资，次年年末收回本利125%。产品项目产品项目C：第：第3年年初投资，第年年初投资，第5年年末收回本利年年末收回本利140%。产品项目产品项目D：第：第2年年初进行，第年年初进行，第5年年末收回本利年年末收回本利155%。每年投资额限制：项目每年投资额限制：项目B900万元，项目万元，项目C2400万元，项目万元，项目D3000万元。万元。在满足各个投资项目的限制条件下，使企业在五年内获得最大的收益。在满足各个投资项目的限制条件下，使企业在五年内获得最大的收益。第24页，此课件共28页哦2022/10/10案例案例2-2 公司投资计划公司投资计划 第25页，此课件共28页哦2022/10/10案例案例2-3 自制自制/外购计划外购计划 设设 x1,x2,x3自制甲自制甲,乙乙,丙数量丙数量;x4,x5外购甲外购甲,乙数量乙数量单位利润：单位利润：自制甲：自制甲：23-(3+2+3)=15自制乙：自制乙：18-(5+1+2)=10自制丙：自制丙：16-(4+3+2)=7外购甲：外购甲：23-(5+2+3)=13外购乙：外购乙：18-(6+1+2)=9最优方案：最优方案：自制甲自制甲1600，外购丙，外购丙600，总利润总利润29400第26页，此课件共28页哦2022/10/10案例案例2-4 合理下料问题合理下料问题7.4米条材米条材,截截2.9,2.1,1.5米米100套套,如何下料所用钢材最省如何下料所用钢材最省?优化结果：第优化结果：第1种方式截取10根，第2种方式截取50根，第4种方式截取30根，各种规格圆钢正好100根。第27页，此课件共28页哦2022/10/10本章小结本章小结n本本章章主主要要内内容容包包括括线线性性规规划划问问题题，线线性性规规划划模模型型的的特特性性与与结结构构；线线性性规规划划模模型型的的图图解解法法和和单单纯纯形形法法；注注重重于于利利用用应应用用案案例例的的分分析析实实现现对对实实际际系系统统进进行行描描述述与与建建模模，并运用计算机求解。并运用计算机求解。n线线性性规规划划问问题题是是指指可可以以建建构构线线性性规规划划模模型型的的一一类类实实际际问问题题。许许多多实实际际经经济济管管理理问问题可以归为线性规划问题，通过线性规划模型实现资源的优化配置。题可以归为线性规划问题，通过线性规划模型实现资源的优化配置。n线线性性规规划划模模型型具具有有如如下下特特点点：决决策策变变量量表表示示要要寻寻求求的的方方案案，每每一一组组值值就就是是一一个个方方案案；约约束束条条件件是是用用等等式式或或不不等等式式表表示示的的限限制制条条件件；一一定定有有一一个个最最优优的的目目标标，最最大大或或最最小小；所有函数都是线性的。所有函数都是线性的。n线线性性规规划划模模型型具具有有一一般般表表达达式式的的结结构构。为为了了便便于于线线性性规规划划模模型型的的求求解解，将将模模型型一一般般表表达式转化为标准形式。达式转化为标准形式。n线线性性规规划划模模型型的的求求解解方方法法包包括括几几何何学学的的图图解解法法和和代代数数学学的的单单纯纯形形法法。要要求熟练掌握求熟练掌握.n建建立立线线性性规规划划模模型型是是线线性性规规划划的的关关键键，利利用用经经济济管管理理中中的的媒媒体体选选择择问问题题、投投资资计计划划问问题题、自自制制与与外外购购问问题题、合合理理下下料料问问题题详详细细阐阐述述了了线线性性规规划划模模型型的的建建立，计算机求解和解的分析。立，计算机求解和解的分析。第28页，此课件共28页哦2022/10/10
