线性规划及其基本理论.pptx

1线性规划及其基本理论线性规划概述线性规划问题线性规划数学模型 一般模型 标准模型线性规划解的概念 可行解、最优解 基阵、基解、基可行解线性规划的基本性质第1页/共44页2线性规划概述线性规划（Linear Programming，简记为LP）是运筹学中的一个最重要、应用最广泛的分支。线性规划及其通用解法-单纯形法一般认为是美国学者丹捷格（G.Dantzig）在1947年研究美国空军军事规划时提出的。苏联学者康托洛维奇在1939年解决工业生产组织与计划问题时就提出类似线性规划的模型及解法；康托洛维奇的工作当时没有被重视，但直到1960年康托洛维奇再次发表最佳资源利用的经济计算一书后，才受到重视。一些常见的带有Spreadsheet的软件，如：Excel、Lotus1-2-3等，均有内置的线性规划求解功能。最优化问题求解软件，如：Lindo、Lingo、Matlab等。第2页/共44页3线性规划问题提出 在生产管理和经营活动中经常会提出这样一类问题：如何利用有限的人力、物力、财力等资源，取得最好的效果。例如：配载问题 一交通工具，运输几种不同体积、重量的物资，如何装配，所运的物资最多？下料问题 用圆钢制造长度不等的机轴，如何下料，所剩的余料最少？生产计划问题 企业生产A、B两种电器产品，两种产品的市场需求状况可以确定，按当前的定价可确保所有产品均能销售出去。企业可提供的两种原材料和劳动时间的数量是有限的。产品A与产品B各应生产多少，可使企业总利润最大?第3页/共44页4线性规划问题提出上述这些问题有如下共同特点：问题解决要满足一定条件，称为约束条件；问题有多个满足条件的解决方案；问题解决有明确的目标要求，对应不同方案有不同目标值，可表示成目标函数。第4页/共44页5何谓线性规划问题最优化问题 我们称如下一般问题：“在一定约束条件下，求目标函数的最大或最小值”为最优化问题，用数学模型描述的最优化问题，称为数学规划问题。线性规划问题 在最优化问题中，如果约束条件与目标函数均是线性的，我们就称之为线性规划问题。第5页/共44页6线性规划问题的三个要素决策变量决策问题待定的量值称为决策变量。决策变量的取值有时要求非负。约束条件任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。第6页/共44页7线性规划数学模型 例例 生产计划问题生产计划问题 某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。3 5单位产品获利8 1236 1 2 3 2 3 4ABC生产能力工时单耗甲 乙 产品车间第7页/共44页8线性规划数学模型建立数学模型的步骤：Step1 分析实际问题；Step2 确定决策变量；Step3 找出约束条件；Step4 确定目标函数；Step5 整理、写出数学模型。第8页/共44页9【例1.1】某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。水泥(公斤/m2)4000(千工日)147000(千块)150000(吨)20000(吨)110000(千元)资源限量3.518025120大模住宅3.019030135壁板住宅4.521011012105砖混住宅人工(工日/m2)砖(块/m2)钢材(公斤/m2)造价(元/m2)资源住宅体系线性规划问题举例第9页/共44页10【例1.2】最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表1.1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？线性规划问题举例 产品产品 资源资源 甲甲 乙乙 丙丙现有资源现有资源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利润（元利润（元/件）件）40 30 50 产品资源消耗表第10页/共44页11【例1.3】某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表1.2所示。表1.2 营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。星期星期需要人数需要人数星期星期需要人数需要人数一一300五五480二二300六六600三三350日日550四四400线性规划问题举例第11页/共44页12【例1.4】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？线性规划问题举例第12页/共44页13【解】这是一个条材下料问题，设切口宽度为零。设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式1.5y1+y2+0.7y34表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解共有10组，也就是有10种下料方式，如表1.3所示。表13 下料方案 方案方案规格规格 1234 5678910需求量需求量y1(根根)221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.5第13页/共44页14设xj(j=1,2,10)为第j种下料方案所用圆钢的根数。则用料最少数学模型为为:注意：（）求下料方案时应注意，余料不能超过最短毛坯的长度；（）最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案。（）如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。第14页/共44页15【例1.5】配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于35%55%之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表1.4所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。表1.4 矿石的金属含量 合金合金矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质%费用（元费用（元/t）125101025303402400030302603015520601804202004020230585151755190线性规划问题举例第15页/共44页16解:设xj（j=1,2，5）是第j 种矿石数量，得到下列线性规划模型 注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种变化考虑进去，有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题，在许多行业生产中都能遇到。第16页/共44页17【例1.6】投资问题。某投资公司在第一年有200万元资金，每年都有如下的投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继续投入此资金的50%，那么到第三年就可回收第一年投入资金的一倍金额”。投资公司决定最优的投资策略使第六年所掌握的资金最多。线性规划问题举例第17页/共44页18【例1.7】均衡配套生产问题。某产品由2件甲、3件乙零件组装而成。两种零件必须经过设备A、B上加工，每件甲零件在A、B上的加工时间分别为5分钟和9分钟，每件乙零件在A、B上的加工时间分别为4分钟和10分钟。现有2台设备A和3台设备B，每天可供加工时间为8小时。为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间1小时。怎样安排设备的加工时间使每天产品的产量最大。线性规划问题举例第18页/共44页19线性规划数学模型一般形式假定线性规划问题有n个决策变量，m个约束条件。一般地，线性规划问题数学模型中可表示成如下形式：第19页/共44页20线性规划数学模型标准形式线性规划问题的数学模型有各种不同的形式，如目标函数有极大化和极小化；约束条件有“”、“”和“”三种情况；决策变量一般有非负性要求，有的则没有。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为：目标函数极大化，约束条件为等式，右端常数项bi0，决策变量非负。第20页/共44页21线性规划数学模型标准形式第21页/共44页22线性规划数学模型标准形式第22页/共44页23线性规划数学模型标准形式第23页/共44页24线性规划数学模型标准形式第24页/共44页25如何化线性规划标准形式第25页/共44页26如何化线性规划标准形式 例 1.8 min z=x1+2 x2-3 x3 x1+2 x2-x3 5 2x1+3 x2-x3 6 -x1 -x2 +x3 -2 x1 0,x3 0第26页/共44页27【例1.9】将下列线性规划化为标准型 如何化线性规划标准形式第27页/共44页28如何化线性规划标准形式第28页/共44页29 当某个变量xj0时,令x/j=xj。当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束 将其化为两个不等式 再加入松驰变量化为等式。如何化线性规划标准形式第29页/共44页30线性规划解的概念可行解与可行域 满足约束条件（AX=b,X0）的X称为线性规划问题的可行解 所有可行解的集合称为可行域，记D=X|AX=b,X0。最优解 使目标函数值达最大的可行解称为线性规划问题的最优解。若X*是最优解，则对任意的XD，恒有 C X*C X。第30页/共44页31线性规划解的概念基（基阵、基础矩阵）为mn维系数矩阵，秩为m。称系数矩阵A中m个线性独立的列向量构成的矩阵B为线性规划问题的一个基。矩阵B非奇异，|B|0，存在逆阵。|B|0,B为非奇异子矩阵；当m=n时，基矩阵唯一，当mn时，基矩阵就可能有多个，但数目不超过A中最多有第31页/共44页32【例1.11】线性规划 求所有基矩阵。第32页/共44页33线性规划基解的概念基向量与非基向量 系数矩阵A中构成基B的列向量称为基向量。系数矩阵A中除基向量之外的列向量称为基向量。A=(B,N)基变量与非基变量 与基向量对应的变量称为基变量。与非基向量对应的变量称为非基变量。第33页/共44页34在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。线性规划基解的概念第34页/共44页35线性规划基解的概念基(础)解基(础)可行解 满足变量非负约束条件的基解，称为线性规划问题的基可行解。可行基 与基可行解对应的基称为可行基。第35页/共44页36线性规划解的关系第36页/共44页37线性规划的退化与非退化一个基可行解，若其中所有基变量都取正值，则称它是非退化的。一个基可行解，若其中有某一个基变量取零值，则称它是退化的。一个线性规划问题，若它的所有基可行解都是非退化的，则称这个线性规划问题是非退化的。第37页/共44页38线性规划基解求取基解与基可行解是线性规划的重要概念，求线性规划的基解与基可行解是各类运筹学考试中的常考题。求线性规划的基解与基可行解时，首先要先化标准形，然后根据概念求解。例 选择不同基，求如下LP的基解和基可行解：max z=x1+4x2 x1+x2+x3=4 -x1+x2+x4=2 x1，x2，x3，x40 第38页/共44页39凸集、凸组合、顶点（极点）凸集 凸组合第39页/共44页40顶点(极点)设K是凸集，若X不能用K中两个不同的 点 的凸组合表示为 )10()1()2()1(-+=a aa aa aXXX则称X是K的一个顶点或极点。X是凸集K的极点即X不可能是K中某一线段的内点，只能是K中某一线段的端点。O凸集、凸组合、顶点（极点）第40页/共44页41线性规划的基本性质 定理定理1 1 若线性规划问题存在可行域，则其可行域一定是凸集。引理 线性规划问题的可行解X=(x1,x2,xn)T为基可行解的充要条件是X的正分量对应的系数列向量是线性独立的。定理定理2 2 线性规划问题的基可行解对应可行域的顶点。定理定理3 3 若线性规划问题有最优解，一定存在一个基可行解是最优解。第41页/共44页42线性规划的基本定理（性质）为便于记忆，我们可将上述线性规划的主要性质简略地归纳如下：若存在可行解，其可行域为凸集。（定理1）基可行解对应可行域顶点。（定理2）若有最优解，一定存在基可行解为最优解。（定理3）可行解为基可行解的充要条件是正分量对应系数向量线性独立。（引理）第42页/共44页43复习举例最优解是否一定是基可行解？求下列线性规划问题的基解 第43页/共44页44感谢您的观看！第44页/共44页