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