线性规划及单纯形法

线性规划及单纯形法第1页，课件共152页，创作于2023年2月绪论1、运筹学的定义及名称的由来2、运筹学在工商管理中的应用3、运筹学的主要内容4、应用运筹学解决问题的过程第2页，课件共152页，创作于2023年2月运筹学的定义运筹学（OperationsResearch） 系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(ManagementScience)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术。《中国企业管理百科全书》：“运筹学应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。”第3页，课件共152页，创作于2023年2月运筹学名称的由来英文原名:OperationsResearch（缩写为O.R.）直译为“运用研究”、“作业研究”据研究内容取名为“管理数学”：运筹学涉及的主要领域是管理问题，研究的基本手段是建立数学模型，并比较多地运用各种数学工具。1957年取名“运筹学”：《史记.高祖本纪》“夫运筹帷幄之中，决胜于千里之外”第4页，课件共152页，创作于2023年2月运筹学在工商管理中的应用生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。库存管理：多种物资库存量的管理，库存方式、库存量等。运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。第5页，课件共152页，创作于2023年2月运筹学在工商管理中的应用市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。其他：设备维修、更新，项目选择、评价，工程优化设计与管理等。第6页，课件共152页，创作于2023年2月运筹学的主要内容（1）数学规划线性规划、非线性规划、整数规划、动态规划、目标规划（2）组合优化最优计数问题、网络优化、排序问题、统筹图（3）随机优化对策论、排队论、库存论、决策分析、可靠性分析先修课：高等数学，基础概率、线性代数特点：系统整体优化；多学科的配合；模型方法的应用第7页，课件共152页，创作于2023年2月应用运筹学解决问题的过程运筹学技术与方法的应用可以让决策者在面临较为复杂且不确定的决策环境时，在保持自身判断及偏好一致的条件下，进行辅助决策，但注意，不是代替决策者进行决策。规定目标和明确问题收集数据和建立模型求解模型和优化方案检验模型和评价方案方案实施和不断改进解决问题制定决策第8页，课件共152页，创作于2023年2月第1章线性规划与单纯形法第9页，课件共152页，创作于2023年2月运筹学的一个主要的分支是数学规划。数学规划研究：在一些给定的条件（约束条件）下，求所考察函数（目标函数）在某种意义下的极值（极小或极大）问题。例如：在经济决策中，经常会遇到诸如在有限的资源（人、原材料、资金等）情况下，如何合理安排生产，使效益达到最大；或者给定具体的任务，如何统筹安排现有资源，能够完成给定的任务，使花费最小这类问题。在这章，我们重点介绍的是应用最为广泛的线性规划问题。第10页，课件共152页，创作于2023年2月第一章线性规划与单纯形法一、线性规划模型实例二、线性规划问题的数学模型三、求解线性规划模型的图解法四、单纯形法五、单纯形法的进一步讨论六、作业第11页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）例1-1（生产计划问题）某企业计划生产I、II两种产品。这两种产品都要分别在A、B、C、D四个不同设备上加工。按工艺资料规定，生产每件产品I需占用各设备分别为2、1、4、0h，生产每件产品II需占用设备分别为2、2、0、4h。已知各设备计划期内用于生产两种产品的能力分别为12、8、16、12h。又知每生产一件I企业能获得2元利润，每生产一件产品II企业能获得3元利润。问该企业应如何安排生产，才能使总的利润最大。第12页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）设备产品ABCD利润（元/件）I21402II22043生产能力（h）1281612表1-1问题分析：（1）问题的目标是什么？合理安排生产，实现利润最大化（2）利润与哪些因素有关？产量和单位产量的利润第13页，课件共152页，创作于2023年2月问题分析：（1）问题的目标是什么？（2）利润与哪些因素有关？（3）单位利润最大的II产品，那么我们就仅生产II产品，是否可行？不可行，原因是各设备生产II产品的能力是有限的，仅仅生产II产品，设备的生产能力还有剩余。结论是两种产品都要进行生产。（4）两种产品的产量会受到什么限制条件呢？各种设备的生产能力，即占用各种设备的工时。（5）要决策的问题是：I产品生产多少？II产品生产多少？才能实现利润最大化呢？第14页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）例1-1【解】：设x1和x2分别表示I、II两种产品在计划期内的产量。因设备A在计划期内的有效时间为12h，不允许超过，因此建立不等式方程：2x1+2x2≦12同理对设备B、C、D也可以列出类似的不等式方程

x1+2x2≦84x1≦164x2≦12建立各种设备允许的情况下，企业总的利润收入方程：

z=2x1+3x2按工艺资料规定，生产每件产品I需占用各设备分别为2、1、4、0h；生产每件产品II需占用设备分别为2、2、0、4h；已知各设备计划期内用于生产两种产品的能力分别为12、8、16、12h第15页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）因此，该实例的问题可以归结为如下的数学模型。回忆：数学规划研究：在一些给定的条件（约束条件）下，求所考察函数（目标函数）在某种意义下的极值（极小或极大）问题。如何理解“线性规划”？第16页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）例1-2（能源利用问题）假设某电厂以甲、乙、丙三种煤作为燃料煤，已知这三种煤的含硫量、发热量及价格，见表1-2。现在要将上述三种煤混合燃烧，按锅炉要求，发热量不能低于17000kJ/t；按环保要求，含硫量不能超过0.025%。问应按什么比例将煤混合，才能使混合煤的价格最低？建立其数学模型。第17页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）电厂含硫量（%）发热量（kJ/t）价格（元/t）甲0.011600080乙0.052000070丙0.031800076表1-2分析：问题的目标是什么？通过三种煤的组合实现混合煤的价格最低问题目标实现的约束条件是什么？含硫量和发热量第18页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）例1-2求解：设单位混合煤中甲、乙、丙三种煤的组合比例为x1：x2：x3因为是组合比例，所以有x1+x2+x3=1，且为非负。考虑约束条件：含硫量和发热量有16000x1+20000x2+18000x3≧170000.01x1+0.05x2+0.03x3≦0.025该问题的目标是在满足上述约束条件下使每吨混合煤的价格最低，用z来表示价格，则：z=80x1+70x2+76x3第19页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）例1-2求解：因此，该问题的数学模型为：目标函数约束条件第20页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）例1-3（运输问题）假设某电力系统有三个火电厂B1、B2、B3，它们每月需燃料煤分别为10、20、25万t。供应这三个电厂燃料煤的煤矿有三个，即A1、A2、A3，它们每月分别可供该电力系统燃料煤15、25、15万t。已知各煤矿到各电厂的运输距离（单位km），如表1-3所示。问如何确定调运方案，使总的运输量（总万吨公里数）最少？建立数学模型。第21页，课件共152页，创作于2023年2月一、线性规划模型实例（问题的提出）

电厂运距(km)煤矿B1B2B3A180100120A27012090A310080150表1-3第22页，课件共152页，创作于2023年2月分析：问题是什么？如何确定调运方案，使总的运输量（总万吨公里数）最少！调运方案如何理解？A1分别向B1、B2、B3三个电厂输送多少万t煤炭？A2分别向B1、B2、B3三个电厂输送多少万t煤炭？A3分别向B1、B2、B3三个电厂输送多少万t煤炭？总的运输量（总万吨公里数）如何计算？各个煤矿向各个电厂输送的煤的吨数×输送的距离之和。有哪些约束条件？各火电厂的煤炭需要量和各煤矿的煤炭供给量第23页，课件共152页，创作于2023年2月例1-3【解】：设煤矿Ai（i=1，2，3）每月供给电厂Bj（j=1，2，3）燃料煤xij万t。该问题的目标是在满足供需平衡的条件下使总运输量最少。设z表示总运输量，则该运输问题的数学模型为：第24页，课件共152页，创作于2023年2月自己动手试一试：某工厂要生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时，车间3为18小时。已知每扇门的利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的这两种产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂如何安排这两种产品的生产计划，才能使总利润最大？第25页，课件共152页，创作于2023年2月自己动手试一试【解】两种新产品的有关数据如表：车间单位产品的生产时间（小时）每周可获得的生产时间（小时）门窗11042021233218单位利润（元）300500第26页，课件共152页，创作于2023年2月自己动手试一试【解】设x1为每周门的产量（扇），x2为每周窗的产量（扇）。线性规划模型如下：第27页，课件共152页，创作于2023年2月二、线性规划问题的数据模型规划问题的数学模型包含三个组成要素：（1）决策变量，指问题中要确定的未知量（2）目标函数，指问题所要达到的目标要求，表示为决策变量的函数（3）约束条件，指决策变量取值时应满足的一些限制条件，表示为含决策变量的等式或不等式如果在规划问题的模型中，决策变量为可控变量，且取值是连续的，目标函数及约束条件都是线性的，这类模型叫做线性规划模型。第28页，课件共152页，创作于2023年2月二、线性规划问题的数据模型1、线性规划模型的一般表达形式（1）一般形式第29页，课件共152页，创作于2023年2月决策变量及各类系数之间的对应关系第30页，课件共152页，创作于2023年2月二、线性规划问题的数据模型1、线性规划模型的一般表达形式（1）一般形式模型的简写形式为：第31页，课件共152页，创作于2023年2月二、线性规划问题的数据模型1、线性规划模型的一般表达形式（1）一般形式（2）向量形式第32页，课件共152页，创作于2023年2月二、线性规划问题的数据模型1、线性规划模型的一般表达形式（1）一般形式（2）向量形式（3）矩阵形式A为约束方程组（约束条件）的系数矩阵。第33页，课件共152页，创作于2023年2月二、线性规划问题的数据模型2、线性规划模型的标准形式为了研究问题的方便，规定线性规划问题的标准形式为：第34页，课件共152页，创作于2023年2月2、线性规划模型的标准形式对标准形式的说明：（1）标准形式的线性规划模型中的要求①目标函数为求最大值（有些文献规定是求最小值）；②约束条件全为等式，约束条件右端常数项bi全为非负值；③变量xj的取值全为非负值。第35页，课件共152页，创作于2023年2月2、线性规划模型的标准形式（2）非标准形式的线性规划问题转化为标准形式的方法①目标函数为求最小值只需令z’=-z，则目标函数转化为②约束条件为不等式当约束条件为“≦”时，例如2x1+2x2≦12可令x3=12-2x1-2x2或者2x1+2x2+x3=12。显然，x3≧0，称x3为松弛变量。第36页，课件共152页，创作于2023年2月2、线性规划模型的标准形式（2）非标准形式的线性规划问题转化为标准形式的方法②约束条件为不等式当约束条件为“≧”时，例如10x1+12x2≧18可令x4=10x1+12x2-18或者10x1+12x2-x4=18。显然，x4≧0，称x4为剩余变量。松弛变量和剩余变量在实际问题中分别表示未被利用的资源数和短缺的资源数，均未转化为价值和利润。因此在目标函数中，松弛变量和剩余变量的系数均为零。第37页，课件共152页，创作于2023年2月2、线性规划模型的标准形式（2）非标准形式的线性规划问题转化为标准形式的方法①目标函数为求最小值②约束条件为不等式③无约束变量。设x为无约束变量，则令无约束变量的实际含义：若变量x代表某产品当年计划数与上一年计划数之差，则x的取值可正可负。第38页，课件共152页，创作于2023年2月二、线性规划问题的数据模型例如1-4将下述线性规划模型化为标准形式第39页，课件共152页，创作于2023年2月二、线性规划问题的数据模型例如1-4【解】：按规则将问题转化为：X4为松弛变量X5为剩余变量第40页，课件共152页，创作于2023年2月二、线性规划问题的数据模型2、线性规划模型的标准形式自己动手试一试：将下列线性规划模型转化为标准型。第41页，课件共152页，创作于2023年2月二、线性规划问题的数据模型2、线性规划模型的标准形式自己动手试一试：将下列线性规划模型转化为标准型第42页，课件共152页，创作于2023年2月参考答案:第43页，课件共152页，创作于2023年2月三、求解线性规划模型的图解法线性规划模型的基本求解方法有：图解法和单纯形法。图解法直观明了，但是只适用于两个变量的问题，目前常用的方法是单纯形法。1、图解法的步骤：第1步：建立坐标系，画出由约束条件所确定的区域第2步：对任意确定的z，画出目标函数所代表的直线第3步：平移目标函数直线，确定最优解。第44页，课件共152页，创作于2023年2月三、求解线性规划模型的图解法2、图解法的实例例1-5用图解法求最优解第45页，课件共152页，创作于2023年2月2、图解法的实例例1-5用图解法求最优解（1）先分析约束条件是如何图示的。x1x2Q4Q3Q2Q1第46页，课件共152页，创作于2023年2月2、图解法的实例例1-5用图解法求最优解（1）先分析约束条件是如何图示的。x1x2Q4Q3(3,3)Q2(4,2)Q1从图形中我们看到阴影部分的图形是凸的，以后我们要证明，如果线性规划问题存在可行域，则可行域一定是一个凸集。第47页，课件共152页，创作于2023年2月2、图解法的实例例1-5用图解法求最优解（2）目标函数的几何意义。目标函数maxz=2x1+3x2，z是待定的值，将函数改写为x2=-2/3x1+z/3，由解析几何知，这是变量为z、斜率为-2/3的一族平行的直线。如图！这族平行线中，离原点越远的直线，z的直线越大。若对x1、x2的取值无限制，z的值可以无限增大。但在线性规划问题中，对x1、x2的取值范围是有限制。第48页，课件共152页，创作于2023年2月2、图解法的实例例1-5用图解法求最优解（2）目标函数的几何意义。x1x2Z=6第49页，课件共152页，创作于2023年2月2、图解法的实例例1-5用图解法求最优解（3）最优解的确定。最优解必须满足约束条件的要求，并使目标函数达到最优值。因此x1、x2的取值范围只能从凸多边形OQ1Q2Q3Q4中去寻找。从图中看到，当代表目标函数的直线和约束条件包围成的凸多边形相切时为止，切点就代表最优解的点。思考：为什么z直线不能继续向右上方移动？第50页，课件共152页，创作于2023年2月x1x2Q4Q3(3,3)Q2(4,2)Q12、图解法的实例例1-5用图解法求最优解（3）最优解的确定。例1-5中目标函数直线与凸多边形的切点是Q3，该点的坐标（3，3），将其代入到目标函数得z=15。第51页，课件共152页，创作于2023年2月2、图解法的实例例1-6将例1-5中的目标函数maxz=2x1+3x2改为maxz=3x1+3x2，则线性规划问题的最优解为？最优解为Q3Q2上的所有点，因此此问题有无穷多个最优解。x1x2Q4Q3(3,3)Q2(4,2)Q1第52页，课件共152页，创作于2023年2月2、图解法的实例例1-6我们看到目标函数的图形恰好与约束条件（1）平行。当目标函数直线向右上方移动时，他与凸多边形相切时不是一个点，而是在整个线段Q2Q3上相切。这时在Q2点、Q3点及Q2Q3线段上的任意点都是目标函数值z达到最大，即该线性规划问题有无穷多最优解，也称具有多重最优解。第53页，课件共152页，创作于2023年2月2、图解法的实例例1-7用图解法求下列线性规划问题的最优解x1x2如图：此问题有可行域，但为无界解（无最优解）其原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束。第54页，课件共152页，创作于2023年2月2、图解法的实例例1-8用图解法求下列线性规划问题的最优解x1x2用图解法求解时找不到满足所有约束条件的公共范围，这时此问题无可行解。原因是模型本身有错误，约束条件相互矛盾，应检查修正。第55页，课件共152页，创作于2023年2月图解法的解题思路和几何上直观得到的一些概念判断，对求解一般线性规划问题的单纯形法有很大的启示：（1）求解线性规划问题时，解的情况有：惟一最优解、无穷多最优解、无界解、无可行解；（2）若线性规划问题的可行域存在，则可行域是一个凸集（凸多边形，稍后介绍）；（3）若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多的话）一定能够在可行域（凸集）的某个顶点找到；第56页，课件共152页，创作于2023年2月三、求解线性规划模型的图解法（4）解题思路是：先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值更优，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更优的另一个顶点，重复上述过程，一直到找出使目标函数值达到最优的顶点为止。图解法虽然直观、简便，但是当变量数大于两个时，它就无能为力了。引入单纯形法！第57页，课件共152页，创作于2023年2月四、单纯形法1、预备知识：凸集和顶点2、线性规划问题的解3、几个基本定理（不要求证明）4、单纯形法求解线性规划5、单纯形法的计算步骤第58页，课件共152页，创作于2023年2月四、单纯形法单纯形法是求解一般线性规划问题的基本方法，是1947年由丹齐格（G.B.Dantzig）提出。1、预备知识：凸集和顶点①凸集：对一个给定的几何图形，通常可从直观上判断其凹凸性。但容易产生错误。凸集的严格定义：如果集合C中任意两个点X1、X2，其连线上的所有的点也都是集合C中的点，称C为凸集。第59页，课件共152页，创作于2023年2月四、单纯形法1、预备知识：凸集和顶点①凸集：因为X1、X2的连线可表示为：

aX1+（1-a）X2（0<a<1）所以凸集定义用数学语言表示为：对任何X1∈C，X2∈C，有aX1+（1-a）X2∈C（0<a<1），则称C为凸集。第60页，课件共152页，创作于2023年2月1、预备知识：凸集和顶点①凸集判断下列几何图形是否是凸集？（a）（b）（c）（d）第61页，课件共152页，创作于2023年2月四、单纯形法1、预备知识：凸集和顶点①凸集：②顶点凸集C中满足下述条件的点X称为顶点：如果C中不存在任何两个不同的点X1、X2，使X成为这两个点连线上的一个点。对任何X1∈C，X2∈C，不存在X=aX1+（1-a）X2（0<a<1），则称X是凸集C的顶点。解释：顶点是不会出现在集合C中任意两点之间的连线上。第62页，课件共152页，创作于2023年2月四、单纯形法2、线性规划问题的解假设所要研究的线性规划模型的形式为：求解线性规划问题，就是满足约束条件（b）、（c）的方程组中找出一个解，使目标函数（a）达到最大值。（a）（b）（c）第63页，课件共152页，创作于2023年2月（a）（b）（c）四、单纯形法（1）可行解满足上述约束条件（b）、（c）的解X=（x1，…，xn）T

称为线性规划问题的可行解，全部可行解的集合称为可行域。（2）最优解使目标函数（a）达到最大值的可行解称为最优解。2、线性规划问题的解第64页，课件共152页，创作于2023年2月（3）基设A为约束方程组（b）的m×n阶系数矩阵（设n>m），其秩为m。B是矩阵A中的一个m×m阶的满秩子矩阵，称B是线性规划问题的一个基。不失一般性，设B中的每一个列向量Pj（j=1,…,m）称为基向量，与基向量Pj对应的变量xj称为基变量。线性规划中除基变量以外的其他变量称为非基变量。基基向量第65页，课件共152页，创作于2023年2月回顾：矩阵的秩的定义定义:如果数域F

上的m

n

矩阵存在一个k

阶子式不为零，并且所有的k+1阶子式全为零，则称A

秩为k

，记作r(A)=k.显然，r(A)min(m,n);r(AT)=r(A).第66页，课件共152页，创作于2023年2月例求矩阵A

的秩，其中

解:在A中，容易看出２阶子式而A

的三阶子式只有一个｜Ａ｜因此第67页，课件共152页，创作于2023年2月（3）基例1-9已知线性规划求所有基矩阵。第68页，课件共152页，创作于2023年2月【解】：约束方程的系数矩阵为2×5矩阵：容易看出r（A）=2，2阶子矩阵有C25=10个，其中第1列与第3列构成的2阶矩阵不是一个基，因此基矩阵只有9个，即：由线性代数知道，基矩阵B必为非奇异矩阵，即|B|≠0。当矩阵B的行列式等于零是就不是基。第69页，课件共152页，创作于2023年2月根据：B中的每一个列向量Pj（j=1,…,m）称为基向量，与基向量Pj对应的变量xj称为基变量。线性规划中除基变量以外的其他变量称为非基变量。请指出例1-9中B2的基向量、基变量和非基变量。B2的基向量是A中的第一列和第四列B2的基变量是x1和x4B2的非基变量是x2、x3和x5。基变量和非基变量是针对某一确定的基而言的，不同的基对应的基变量和非基变量是不相同的。第70页，课件共152页，创作于2023年2月（a）（b）（c）四、单纯形法（4）基本解在约束方程组（b）中，令所有非基变量xm+1=xm+2=…=xn=0,又因为有|B|≠0，根据克拉默规则，由m个约束方程可解出m个基变量的惟一解XB=（x1，…，xm）。这个解加上非基变量取0的值有X=（x1，x2，…，xm，0，…，0）T，称为线性规划问题的基解。显然在基解中变量取非零值的个数不大于方程数m，又基解的总数不超过Cnm个。2、线性规划问题的解对某一特定的基B，令非基变量等于零，利用（b）求解出基变量，则这组解成为基B的基本解。第71页，课件共152页，创作于2023年2月定理(克拉默法则)

如果含有n

个方程的n

元线性方程组第72页，课件共152页，创作于2023年2月的系数行列式则方程组(1)有唯一解，并且其中detBj

是将系数行列式detA

的第j

列元a1j,a2j,…,anj,换成常数项b1,b2,…,bn后得到的行列式.第73页，课件共152页，创作于2023年2月（a）（b）（c）四、单纯形法（5）基本可行解满足变量非负约束条件（c）的基解称为基可行解。（6）可行基对应于基可行解的基称为可行基（7）最优基基本最优解对应的基称为最优基2、线性规划问题的解第74页，课件共152页，创作于2023年2月例1-9中对于B1来说，x1、x2是基变量，x3、x4、x5是非基变量，令x3=x4=x5=0，则因|B|≠0，由克莱姆法则知，X1、x2有惟一解，解得x1=2/5，x2=1则基本解为X（1）=第75页，课件共152页，创作于2023年2月例1-9中对于B2来说，x1、x4是基变量，x2、x3、x5是非基变量，令x2=x3=x5=0，则因|B|≠0，由克莱姆法则知，X1、x4有惟一解，解得x1=-1/5，x4=4则基本解为X（2）=第76页，课件共152页，创作于2023年2月满足非负约束条件，所以它是基本可行解；不满足非负约束条件，所以它不是可行解，也不是基本可行解；注意：可行解不一定是基本可行解。例满足约束方程和非负约束，因此是可行解，但它不是任何基矩阵的基本解。对应的基B1称为可行基第77页，课件共152页，创作于2023年2月基本最优解、最优解、基本可行解、基本解和可行解的关系如图表示：基本最优解基本可行解最优解基本解可行解箭尾的解一定是箭头的解，否则不一定成立第78页，课件共152页，创作于2023年2月四、单纯形法1、预备知识：凸集和顶点2、线性规划问题的解3、几个基本定理（不要求证明）定理1：若线性规划问题存在可行解，则问题的可行域是凸集。定理1描述了可行解集的特征。第79页，课件共152页，创作于2023年2月四、单纯形法3、几个基本定理定理2：线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。定理2描述了可行解集的顶点与基本可行解的对应关系，顶点是基本可行解；反之，基本可行解在顶点上。但它们并非一一对应，可能有两个或几个基本可行解对应于同一个顶点。定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。第80页，课件共152页，创作于2023年2月四、单纯形法2、线性规划问题的解例1-10在下述线性规划问题中，列出全部基、基解、基可行解和指出最优解。标准型第81页，课件共152页，创作于2023年2月例1-10解写出约束方程组的系数矩阵P1P2P3P4P5矩阵A的秩≦3。所以只要找出3个列向量组成的矩阵满秩，这3个向量就是线性规划问题的一个基。第82页，课件共152页，创作于2023年2月例1-10解写出约束方程组的系数矩阵P1P2P3P4P5令与基对应的变量为基变量，其余变量为非基变量，令非基变量等于零，求解方程组就可以找出基解。下表中列出本线性规划问题的全部基、基解。第83页，课件共152页，创作于2023年2月基基解基可行解？目标函数值x1x2x3x4x5P1P2P343-200否17P1P2P433040是15P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是0例1-10表第84页，课件共152页，创作于2023年2月基本结论：线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点。若线性规划问题有最优解，必在某顶点上得到。虽然顶点数目是有限的，若采用“枚举法”找所有基可行解，然后一一比较，最终必然能找到最优解。但当n,m较大时，这种办法是行不通的，所以要继续讨论如何有效寻找最优解的方法。我们将主要介绍单纯形法。第85页，课件共152页，创作于2023年2月四、单纯形法4、单纯形法求解线性规划通过示例来了解单纯形法求解线性规划。第86页，课件共152页，创作于2023年2月单纯形法示例：例1-11

某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示。如何用单纯形法求解下列标准线性规化数学模型。每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多?

产品资源III拥有量设备128台时原材料A4016kg原材料B0412kg第87页，课件共152页，创作于2023年2月例1-11【解】设x1和x2分别表示计划生产产品I和产品II的数量。建立的线性规划数学模型如下：第88页，课件共152页，创作于2023年2月约束条件例1-11【解】将上页的线性规划模型转换成标准型如下：第89页，课件共152页，创作于2023年2月约束方程的系数矩阵从式中可以看到x3,x4,x5的系数列向量第90页，课件共152页，创作于2023年2月P3,P4,P5是线性独立的，这些向量构成一个基从(1-2)式中可以得到（1-3）对应于B的变量x3,x4,x5为

基变量，x1、x2为非基变量第91页，课件共152页，创作于2023年2月将(1-3)式代入目标函数(1-1)得到令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0)=(0,0,8,16,12)T

这个基可行解表示：工厂没有安排生产产品Ⅰ、Ⅱ；资源都没有被利用，所以工厂的利润指标z=0。到这里，完成了单纯形法的第一个环节：确定初始基本可行解；然后再确定这个基本可行解是否是最优的，如果不是，则还要继续去寻找最优解！第92页，课件共152页，创作于2023年2月下面进行最优性的检验！从分析目标函数的表达式(1-4)可以看到：非基变量x1,x2(即没有安排生产产品Ⅰ，Ⅱ)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加。所以只要在目标函数(1-4)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，当前的基本可行解还不是最优解。因此，最优解否定后，又要去寻找新的基本可行解，这就需要将非基变量与基变量进行对换。第93页，课件共152页，创作于2023年2月如何确定换入，换出变量？一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。现分析(1-3)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即x3,x4,x5≥0。第94页，课件共152页，创作于2023年2月当x1=0,由(1-3)式得到第95页，课件共152页，创作于2023年2月x2取何值时，才能满足非负要求？从(1-5)式中可以看出，只有选择x2=min(8/2,12/4)=3时，才能使(1-5)式成立。因当x2=3时，基变量x5=0，这就决定用x2去替换x5。以上数学描述说明了每生产一件产品Ⅱ，需要用掉各种资源数为(2，0，4)。由这些资源中的薄弱环节，就确定了产品Ⅱ的产量。这里就是由原材料B的数量确定了产品Ⅱ的产量x2=12/4=3件。第96页，课件共152页，创作于2023年2月为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-3)中x2的位置与x5的位置对换。得到第97页，课件共152页，创作于2023年2月用高斯消去法将(1-6)式中x2的系数列向量变换为单位列向量。其运算步骤是：③′=③/4；①′=①-2×③′;②′=②,并将结果仍按原顺序排列有：第98页，课件共152页，创作于2023年2月再将(1-7)式代入目标函数(1-1)式得到令非基变量x1=x5=0，得到z=9，并得到另一个基可行解X（1）X（1）=（0，3，2，16，0）T第99页，课件共152页，创作于2023年2月从目标函数的表达式(1-8)中可以看到，非基变量x1的系数是正的，说明目标函数值还可以增大，X(1)还不是最优解。于是再用上述方法，确定换入、换出变量，继续迭代，再得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T再经过一次迭代，再得到一个基可行解X(3)X(3)=(4,2,0,0,4)T而这时得到目标函数的表达式是：z=14-1.5x3-0.125x4(1-9)第100页，课件共152页，创作于2023年2月z=14-1.5x3-0.125x4(1-9)再检查(1-9)式，可见到所有非基变量x3,x4的系数都是负数。这说明若要用剩余资源x3,x4，就必须支付附加费用。所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品Ⅰ生产4件，产品Ⅱ生产2件，工厂才能得到最大利润。第101页，课件共152页，创作于2023年2月四、单纯形法4、单纯形法求解线性规划再引入一实例，介绍利用单纯形法求解线性规划时可以使用的一种工具，即单纯形表。例1-12用单纯形法求解下列线性规划的最优解第102页，课件共152页，创作于2023年2月例1-12【解】化为标准型为：约束方程的系数矩阵A为：第103页，课件共152页，创作于2023年2月例1-12【解】确定初始基和基变量、非基变量、初始基本可行解。基变量为：x3，x4非基变量为：x1，x2令非基变量x1=x2=0，代入约束方程中得到：x3=40，x4=30则初始基本可行解为：X（0）=（0，0，40，30）T第104页，课件共152页，创作于2023年2月例1-12【解】以上得到的一组基本可行解是否是最优解?从目标函数z=3x1+4x2中看出：X1和x2的系数大于零，如果x1和x2为一个正数，那么目标值就能够变得更大。因此，只要非基变量的系数大于零，那么目标函数就没有达到最大，即没有找到最优解。判别线性规划问题是否达到最优解的数称为检验数，记作λj（j=1，2，…，n）。在例1-11中λ1=3，λ2=4，λ3=0，λ4=0。检验数：目标函数用非基变量表示，其变量的系数为检验数第105页，课件共152页，创作于2023年2月下面，我们要引入一个工具，来帮助我们利用单纯形法来求解线性规划，这个工具是单纯形表。根据以上得到的结果，我们可以建立初始的单纯形表。cj3400θi(min)CBXBx1x2x3x4b0x32110400x4130130λj(max)34000基变量的检验数为零第106页，课件共152页，创作于2023年2月因为X（0）不是最优解，因此我们就要继续寻找下一个基解，并判断它是否是最优解。所以我们需要对已经得到的基解进行改进，改进的方法是：换基变量。（1）确定换入变量（进基变量）方法：λk=max{λj|λj>0}（2）确定换出变量（出基变量）方法：θk=min{θi=bi/aik|aik>0}第107页，课件共152页，创作于2023年2月cj3400θi(min)CBXBx1x2x3x4b0x32110400x4130130λj(max)34000换入变量为：x2那么换出变量为x3还是x4呢？确定换出变量为x440/130/3第108页，课件共152页，创作于2023年2月cj3400θi(min)CBXBx1x2x3x4b0x32110400x4130130λj(max)34000换入变量为：x2;换出变量为x4初始单纯形表变更为：40/130/3X2希望变成1希望变成0这样，形成的基就是单位矩阵。因此，对增广矩阵进行初等变换！

4第109页，课件共152页，创作于2023年2月cj3400θi(min)CBXBx1x2x3x4b0x32110404x2130130λj(max)34000换入变量为：x2;换出变量为x4初始单纯形表变更为：4010增广矩阵的第2行中的每个元素都÷3得：如图所示1/311/310增广矩阵的第1行-第2行得：如图所示5/3

0-1/330经过增广矩阵的初等变换后，基变成了单位矩阵第110页，课件共152页，创作于2023年2月cj3400θi(min)CBXBx1x2x3x4b0x35/301-1/3304x21/3101/310λj(max)340004010确定基可行解X（1）=？令非基变量x1=x4=0，基变量x2=10，x3=30所以X（1）=（0，10，30，0）T基可行解是否是最优解？依据检验数定义：目标函数用非基变量表示，其变量的系数为检验数。因此需要将基变量的λ变换为0因为λ3=0了，所以只需要将λ2变换为0。方法：矩阵的第3行-第2行×4-40

05/3-4/3第111页，课件共152页，创作于2023年2月cj3400θi(min)CBXBx1x2x3x4b0x35/301-1/3304x21/3101/310λj(max)5/300-4/3-40得出：X（1）=（0，10，30，0）T不是最优解下一步：确定换入变量和换出变量请大家自己运算，直到确定最优解。3018x13第112页，课件共152页，创作于2023年2月cj3400θi(min)CBXBx1x2x3x4b3x15/301-1/330184x21/3101/31030λj(max)5/300-4/3-40将基（P1P2）初等变换为单位矩阵方法：①÷5/3②-①×1/3确定基本可行解X（2）=（18，4，0，0）T最优性性判断？③-①×5/3看到所有的检验数都小于0，所以X（2）是最优解同时目标函数值为70

13/5-1/518

0-1/52/54

0

-1

-1

-70-z第113页，课件共152页，创作于2023年2月练习：将例1-11用单纯形表求解。练习：单纯形法求解（1）第114页，课件共152页，创作于2023年2月小结单纯形法是求解线性规划问题的一种极为有效和方便的方法，用单纯形法时一定要注意以下几个问题：第一：要将问题化为标准型第二：迭代过程进行的应是线性变换；第三：判断是否为最优解的标准，即对极大化问题，检验数应为非正；大家思考：对极小化问题，检验数应为什么？对极小化问题，检验数应为非负。第115页，课件共152页，创作于2023年2月例1-13单纯形法求解第116页，课件共152页，创作于2023年2月以上我们讨论的是有惟一最优解的情况，如果最优解有无穷多个，求解的过程是怎样的呢？例1-14第117页，课件共152页，创作于2023年2月例1-14【解】化为标准型为：第118页，课件共152页，创作于2023年2月cj24000θi(min)CBXBx1x2x3x4x5b0x3-1210040x412010100x51-10012λj(max)初始单纯形表如下：X（0）=（0，0，4，10，2）T240000判断是否最优？不是最优！换基方案？换入变量：x2，25换出变量：x3第119页，课件共152页，创作于2023年2月cj24000θi(min)CBXBx1x2x3x4x5b4x2-1210040x412010100x51-10012λj(max)240000经初等变换，将（P2，P4，P5）变换为单位矩阵判断是否最优？-1/2

21/2

1

0

01/2

-11/2基本解为X（1）=（0，2，0，6，4）T

2

6

4不是最优解！

4

0

-2

-8换基方案？换入变量：x1，

3

8换出变量：x4第120页，课件共152页，创作于2023年2月cj24000θi(min)CBXBx1x2x3x4x5b4x2-1/211/20022x120-11060x51/201/2014λj(max)40-200-8经初等变换，将（P1，P2，P5）变换为单位矩阵判断是否最优？基本解为X（2）=（3，7/2，0，0，5/2）T是最优解！

0

1

0

1/4-1/23/4

1/41/2-1/4

7/2

3

5/2

-2-20

0

0目标函数值为z=20但是这时，非基变量x3的检验数为零，表示原问题还有其他的最优解，也就是说这是多重最优解的情况。还可以进一步迭代！第121页，课件共152页，创作于2023年2月cj24000θi(min)CBXBx1x2x3x4x5b4x2011/41/407/22x110-1/21/2030x5003/4-1/415/2λj(max)000-20-20换基方案？换入变量：x3，换出变量：x5

14

10/3

x3经初等变换，将（P1，P2，P3）变换为单位矩阵基本解为X（3）=（14/3，8/3，10/3，0，0）T

1

0

01/31/3-1/3-1/32/34/38/314/310/3基本解为X（3）是最优解！目标函数值z=20第122页，课件共152页，创作于2023年2月小结该例是有无穷多最优解（多重解）的线性规划问题，单纯形表中的检验数除了基变量的检验数为零外，还有非基变量的检验数也为零。该例的迭代过程中还需注意在用最小比值法则时，要求分母大于0，即当系数矩阵中对应的向量小于等于零时，则不需要计算比值，所以对应的变量也不是出基变量。第123页，课件共152页，创作于2023年2月例1-15第124页，课件共152页，创作于2023年2月cj2200θi(min)CBXBx1x2x3x4b0x3-111010x4-0.51012λj(max)2200因为问题是最大化问题，这时非基变量x1的检验数=2（>0），可以作为进基变量，但是增广矩阵中x1对应的系数都小于0，所以目标函数无上界，问题无最优解！第125页，课件共152页，创作于2023年2月小结本例是无最优解的线性规划问题。在计算过程中，一定要注意：若某个检验数对应的变量的系数都小于等于零，则此问题无界，停止计算。同时要注意：无最优解并不代表无可行解；无界解是有可行解的，但没有最优解。第126页，课件共152页，创作于2023年2月四、单纯形法1、预备知识：凸集和顶点2、线性规划问题的解3、几个基本定理（不要求证明）4、单纯形法求解线性规划5、单纯形法的计算步骤第127页，课件共152页，创作于2023年2月四、单纯形法5、单纯形法的计算步骤（1）将线性规划问题转换为标准型（2）求初始基本可行解（3）通过计算检验数判断基本可行解是否为最优若所有检验数都小于等于零，则得到最优解若某个检验数大于零，但对应变量系数都小于等于零，则线性规划有无界解若存在检验数大于零，而且对应变量的系数不全为负，则进行换基第128页，课件共152页，创作于2023年2月5、单纯形法的计算步骤（1）将线性规划问题转换为标准型（2）求初始基本可行解（3）通过计算检验数判断基本可行解是否为最优（4）换基选进基变量：选择检验数最大的变量选出基变量：最小比值法则（5）求新的基本可行解：用初等变换将aLK化为1，k列其他元素化为零（基向量成单位矩阵），再判断是否得到最优第129页，课件共152页，创作于2023年2月五、单纯形法的进一步讨论在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。1、人工变量法（大M法）2、两阶段法第130页，课件共152页，创作于2023年2月五、单纯形法的进一步讨论1、人工变量法（大M法）（1）人工变量法的思路当线性规划问题的约束条件是等式，而系数矩阵中又不包含有单位矩阵时，采用人工变量法在约束条件左端加上一个人工变量，从而人为地构造一个单位基矩阵。若约束条件是“≧”的情况，先在不等式左端减去一个大于等于零的剩余变量（松弛变量）转化为等式约束。然后，为了构造一个单位矩阵，在约束条件左端再加上一个人工变量。第131页，课件共152页，创作于2023年2月1、人工变量法（大M法）（2）目标函数的变化在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数值没有影响，因此人工变量在目标函数中的系数应为“-M”（M为任意大的正数）。这样，在目标函数要实现最大化时，必须把人工变量从基变量中置换出来，否则，目标函数不可能实现最大化，也即原线性规划问题无可行解。第132页，课件共152页，创作于2023年2月1、人工变量法（大M法）例1-16用大M法求解线性规划问题。（1）将问题化成标准形式。系数矩阵A为：系数矩阵A中不包含单位矩阵，因此增加人工变量去构造单位矩阵，但增加的人工变量不能影响目标函数。第133页，课件共152页，创作于2023年2月1、人工变量法（大M法）例1-16用大M法求解线性规划问题。(1)将问题化成标准形式。(2)增加人工变量。第134页，课件共152页，创作于2023年2月1、人工变量法（大M法）例1-16用大M法求解线性规划问题。系数矩阵A为：有1单位子矩阵系数为负数，我们知道在换基时，会把它们置换出来，这样就不会影响目标函数了第135页，课件共152页，创作于2023年2月五、单纯形法的进一步讨论1、人工变量法（大M法）例1-16用大M法求解线性规划问题。接下来，用单纯形法求解线性规划模型。第136页，课件共152页，创作于2023年2月cj32-100-M-MCBXBx1x2x3x4x5x6x7b-Mx6-431-101040x51-12010010-Mx72-2100011λj(max)32-100-M-M3-4M2+3M-1+M-M03-2M2+M-1+2M-M0换基：换入变