第9章线性规划方法及其应用讲解课件

第第9章章 线性规划方法及其应用线性规划方法及其应用7/5/20241第9章 线性规划方法及其应用8/13/20231线性规划（Linear Programming）作为运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现有资源条件下进行组织和安排，以产生最大收益。因此，线性规划是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者做出科学决策的重要手段。7/5/20242线性规划（Linear Programming）作为运筹学的 1、康托洛维奇康托洛维奇生产组织与计划中的数学方法生产组织与计划中的数学方法,一一本小册子，本小册子，1939;2、康托洛维奇、康托洛维奇“最佳资源利用的经济计算最佳资源利用的经济计算”1942完成、完成、1959发表的著作发表的著作；3、自、自1947年年丹兹格丹兹格（G.B.Dantzing）提出求解）提出求解线性规划问题的一般方法线性规划问题的一般方法-单纯形法之后，线性规划单纯形法之后，线性规划在理论上趋于成熟，应用日益广泛与深入；在理论上趋于成熟，应用日益广泛与深入；随着电子计算机的发展和计算速度的不断提高，随着电子计算机的发展和计算速度的不断提高，其适用的领域更加广泛，它已成为必不可少的重要手其适用的领域更加广泛，它已成为必不可少的重要手段之一。段之一。7/5/20243 1、康托洛维奇生产组织与计划中的数学方法,一 4、1975年库伯曼斯年库伯曼斯(Koopmans)因对资源最优因对资源最优分配理论的贡献而获诺贝尔经济学奖；分配理论的贡献而获诺贝尔经济学奖；5、冯、冯诺伊曼和摩根斯坦诺伊曼和摩根斯坦1944年发表的年发表的 对对策论与经济行为策论与经济行为涉及与线性规划等价的对策问题涉及与线性规划等价的对策问题及线性规划对偶理论。及线性规划对偶理论。7/5/20244 4、1975年库伯曼斯(Koopmans)因l线性规划方法是数学规划中发展较快、线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分支。应用较广和比较成熟的一个分支。l最优化最优化/运筹学运筹学的最基本的方法之一，网的最基本的方法之一，网络规划，整数规划，目标规划和多目标络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。规划都是以线性规划为基础的。l解决稀缺资源最优分配的有效方法，使解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。付出的费用最小或获得的收益最大。l线性规划的基础是线性变换。线性规划的基础是线性变换。7/5/20245线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分数数学学规规划划非线性规划非线性规划整数规划整数规划动态规划动态规划学学科科内内容容多目标规划多目标规划双层规划双层规划组组合合优优化化最优计数问题最优计数问题网络优化网络优化排序问题排序问题统筹图统筹图随随机机优优化化对策论对策论排队论排队论库存论库存论决策分析决策分析可靠性分析可靠性分析运筹学的主要内容7/5/20246数非线性规划整数规划动态规划学多目标规划双层规划组最优计数问9.1 线性规划是什么9.2 建立线性规划模型的一般步骤9.3 线性规划问题的图解法9.4 线性规划问题解的性质 9.5 解线性规划问题的单纯形法 9.6 线性规划的应用7/5/202479.1 线性规划是什么8/13/202379.1 线性规划是什么线性规划是什么7/5/202489.1 线性规划是什么8/13/202389.1 线性规划是什么线性规划是什么我们先通过几个实际问题来认识什么是线性规划.【例【例9.1】某企业生产 三种产品，这些产品分别需要甲、乙两种原料.生产每种产品一吨所需原料和每天原料总限量及每吨不同产品可获利润情况如表9.1所示.表9.1 企业生产数据表1.利润最大化问题利润最大化问题7/5/202499.1 线性规划是什么我们先通过几个实际问题来认识什么是线9.1 线性规划是什么线性规划是什么试问：该企业怎样安排生产才会使每天的利润最大？试问：该企业怎样安排生产才会使每天的利润最大？解解 设该企业每天生产产品 的数量分别为 （单位：吨），则总利润的表达式为我们希望在现有资源条件下总利润最大.现有资源的限制为（原料甲的限制）（原料乙的限制）此外，由于未知数（我们称之为决策变量决策变量）是计划产量，应有为非负的限制，即 7/5/2024109.1 线性规划是什么试问：该企业怎样安排生产才会使每天的9.1 线性规划是什么线性规划是什么由此得到问题的数学模型为其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.7/5/2024119.1 线性规划是什么由此得到问题的数学模型为其中 9.1 线性规划是什么线性规划是什么类似于例9.1的这类问题称为最优生产计划问题.其一般描述是利用 种资源 组织生产 种产品 .以 表示资源 的限制，表示产品 的单位利润，表示单位产品 消耗资源 的数量（代表该企业当前的技术水平），情况如表9.2所示.现在的问题是：如果该企业生产的这 种产品 都可以卖出，如何合理充分地利用现有的资源，给出一个使总利润达到最大的产品生产计划？7/5/2024129.1 线性规划是什么类似于例9.1的这类问题称为最优生产有了解决上述问题的经验，我们可以假设产品 的计划产量分别为 单位，则问题的数学模型为 9.1 线性规划是什么线性规划是什么7/5/202413有了解决上述问题的经验，我们可以假设产品 的模型中 的都是实际问题给定的常数；未知量 为决策变量.这类决策问题的应用领域非常广泛.注注 本章的数学模型均可用软件求解。2.成本最小化问题成本最小化问题【例例9.29.2】某钢铁厂熔炼一种新型不锈钢，需要4种合金 为原料经测定这4种原料关于元素铬（Cr）、锰（Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬、锰和镍的最低质量分数，情况如表9.3所示.假设熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选用原料 各多少吨，能够使成本最小？9.1 线性规划是什么线性规划是什么7/5/202414模型中 9.1 线性规划是什么线性规划是什么下料问题的一般描述：已知有一批原材料，每根长度为L，由于生产的需要，要求截出规格分别为 的零件 根.问：如何截取使得总用料最省？即要求制定一个既能满足生产的需要，又使得使用的原材料数量最少的下料方案.同样可以仿照例9.4的建模过程列出此一般问题的数学模型.总之，类似例9.1、9.2的实际问题很多，而且形式多种多样.通过这些问题，我们可以看到上述各种问题的共同点，共同点，即每一个问题都用一组决策变量即每一个问题都用一组决策变量 来表示某一来表示某一方案，追求的目标可以用关于决策变量方案，追求的目标可以用关于决策变量 的线的线性函数刻画，或是最大化或是最小化，而要达到目标的条性函数刻画，或是最大化或是最小化，而要达到目标的条件又都有一定的限制，每个限制条件均可由关于决策变量件又都有一定的限制，每个限制条件均可由关于决策变量 的线性等式或不等式表示的线性等式或不等式表示.7/5/2024159.1 线性规划是什么下料问题的一般描述：已知有一批原材料9.1 线性规划是什么线性规划是什么这类问题所构成的数学模型,称为线性规划线性规划模型.有时也直接将线性规划模型称为线性规划问题.针对这类模型,可以用根据数学理论设计的计算机软件，如软件求解，得出实际问题需要的答案。7/5/2024169.1 线性规划是什么这类问题所构成的数学模型,称为线性规9.2 建立线性规划模型的建立线性规划模型的 一般步骤一般步骤7/5/2024179.2 建立线性规划模型的8/13/2023179.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤从9.1节中对实际问题建立数学模型的过程，可以得到一般线性规划问题建模过程如下：第第1 1步步 理解要解决的问题.搞清在什么条件下追求什么目标.第第2 2步步 定义决策变量决策变量.每一个问题都用一组决策变量 来表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的是非负的.第第3 3步步 确定约束条件约束条件.用一组决策变量的线性等式或不等式来表示在解决问题过程中所必须遵循的约束条件.第第4 4步步 列出目标函数目标函数.按实际问题的不同，用决策变量的线性函数最大化或最小化形式写出所要追求的目标，称之为目标函数.7/5/2024189.2 建立线性规划模型的一般步骤从9.1节中对实际问题9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤对于一些比较复杂的线性规划问题，为了便于建立其数学模型，常需要把反映问题的背景数据资料用表格形式归类综合，以揭示各个量之间的内在联系.线性规划的一般形式可表示为：7/5/2024199.2 建立线性规划模型的一般步骤对于一些比较复杂的线性规9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤其中称 为目标函数，为决策变量，为约束常数，后面的式子为约束条件.这里的 为常数.当要求决策变量 均为整数时，称（9.1）为纯整数线性规划问题纯整数线性规划问题；当要求决策变量 均取0或1时，称（9.1）为 整数线性规划问题整数线性规划问题.当要求决策变量 既取实数又取整数时，称（9.1）为混合整数线性规划问题.我们把满足所有约束条件的解称为线性规划问题（9.1）的可行解可行解.全体可行解的集合称为问题（9.1）的可行域可行域,记为.使目标函数值最大（或最小）的可行解称为该线性7/5/2024209.2 建立线性规划模型的一般步骤其中称 9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤 规划问题的最优解最优解，与此最优解相应的目标函数值称为最优最优目标函数值目标函数值，简称最优值最优值.因此，若记 ，求解线性规划问题（9.1），本质上就是寻找一点 ，使得 均满足不等式【例例9.39.3】某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备（台时），A、B两种原材料的消耗以及资源的限制情况如表2.11所示.问：该工厂应分别生产多少甲产品和乙产品才能使工厂获利最大？7/5/2024219.2 建立线性规划模型的一般步骤 规划问题的最优解，与9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤解解 首先，确定决策变量.工厂目前要决策的是甲产品和乙产品的生产量，可以分别用变量 来表示.由于它们表示产品产量，所以只取非负数.其次，根据问题的限制条件，列出表示约束条件的线性不等式：7/5/2024229.2 建立线性规划模型的一般步骤解 首先，确定决策变量9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤，（非负限制），（台时数限制），（原材料 限制），（原材料 限制）最后，根据实际问题所追求的目标，列出其线性函数表达式.由于问题的目标是工厂获利最大，假如产品都能销售，则总利润可表示为 ，最大利润记为7/5/2024239.2 建立线性规划模型的一般步骤，（非负限制），（台时9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤综上所述，就得到了描述该问题的线性规划模型：7/5/2024249.2 建立线性规划模型的一般步骤综上所述，就得到了描述该计算最优解为：计算最优解为：即在现有资源条件下，该企业在计划期内生即在现有资源条件下，该企业在计划期内生产的最优计划是：产的最优计划是：产品甲生产产品甲生产100单位，单位，产品乙生产产品乙生产200单位，单位，可实现最大利润可实现最大利润130000元元.9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤7/5/202425计算最优解为：9.2 建立线性规划模型的一般步骤8/13/9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤 【例9.4】某医院护士24小时值班，每次值班8小时.不同时段需要的护士人数不等.据统计，各时段所需护士的最少人数如表2.9所示.如何安排才能做到安排最少的护士就能满足工作的需要？7/5/2024269.2 建立线性规划模型的一般步骤 【例9.4】某医院9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤解 设 为时段 开始上班的人数，.目标是要求护士的总数最少.因为每个护士都工作8小时，即连续工作2个时段后休息，所以问题的线性规划模型为：7/5/2024279.2 建立线性规划模型的一般步骤解 设 为时段 开9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤计算最优解为：故该医院需雇用150名护士，最佳安排见表9.10所示.7/5/2024289.2 建立线性规划模型的一般步骤计算最优解为：9.2 建立线性规划模型的一般步骤建立线性规划模型的一般步骤线性规划的一般形式，可行解、最优解等概念线性规划问题建模过程：第第1 1步步 理解要解决的问题。第第2 2步步 定义决策变量。第第3 3步步 确定约束条件。第第4 4步步 列出目标函数。7/5/2024299.2 建立线性规划模型的一般步骤线性规划的一般形式，可行9.3 线性规划问题的图解法线性规划问题的图解法7/5/2024309.3 线性规划问题的图解法8/13/2023309.3 线性规划问题的图解法线性规划问题的图解法1.图解法图解法 对一个线性规划问题建立数学模型之后，就面临着如何求解的问题.这里先介绍含有两个决策变量 的线性规划问题的图解法.它简单直观，有助于了解线性规划问题求解的基本原理.7/5/2024319.3 线性规划问题的图解法1.图解法8/13/202图解法的步骤可概括为：（1）在平面上建立直角坐标系 ；（2）图示约束条件，找出可行域（由于 ，可行域必位于第一象限）；（3）图示目标函数，即画出目标函数等值线；（4）对 （或 ）问题朝着增大（或减少）纵截距的方向平行移动目标函数等值线，至与可行域的边界相切时为止.切点（即某个边界点）就是代表最优解的点；（5）寻找该点的坐标得到最优解.以下结合实例来具体说明.7/5/202432图解法的步骤可概括为：8/13/2023329.3 线性规划问题的图解法线性规划问题的图解法【例9.5】用图解法求解线性规划问题 7/5/2024339.3 线性规划问题的图解法 8/13/2023339.3 线性规划问题的图解法线性规划问题的图解法解 先画出线性规划的可行域如图9.1阴影部分.再画出目标函数等值线，朝着增大纵截距的方向平行移动等值线至点 .最后求解线性方程组 求解得到点 的坐标，从而得到最优解 ，最大值7/5/2024349.3 线性规划问题的图解法解 先画出线性规划的可行域如9.3 线性规划问题的图解法线性规划问题的图解法7/5/2024359.3 线性规划问题的图解法8/13/2023359.3 线性规划问题的图解法线性规划问题的图解法【例9.6】用图解法求解线性规划问题 解解 先画出线性规划的可行域，如图先画出线性规划的可行域，如图9.2阴影部分阴影部分.7/5/2024369.3 线性规划问题的图解法【例9.6】用图解法求解线性规9.3 线性规划问题的图解法线性规划问题的图解法7/5/2024379.3 线性规划问题的图解法8/13/2023379.3 线性规划问题的图解法线性规划问题的图解法再画出目标函数等值线，朝着增大纵截距的方向平行移动等值线至点B.最后求解线性方程组 得到解出点B的坐标 ，从而得到最优解 ，最大值 例9.5与例9.6中求解得到的问题的最优解是惟一的，但对一般线性规划问题，求解结果还可能出现其他情况.7/5/2024389.3 线性规划问题的图解法再画出目标函数等值线，朝着增大9.3 线性规划问题的图解法线性规划问题的图解法2.线性规划解的其他情况线性规划解的其他情况（1）多重最优解的情况 【例9.9】若将例9.5中的目标函数变为 ，则代表目标函数的直线平移到最优位置后将和直线 重合.此时，不仅顶点A，B都代表了最优解，而且线段上AB的所有点都代表了最优解.这个线性规划问题有无穷多最优解，这些最优解都对应着相同的最大值 7/5/2024399.3 线性规划问题的图解法2.线性规划解的其他情况8/MAX7/5/202440MAX8/13/2023409.3 线性规划问题的图解法线性规划问题的图解法（2）无界解的情况）无界解的情况（3）无可行解的情况）无可行解的情况7/5/2024419.3 线性规划问题的图解法（2）无界解的情况（3）无可行9.3 线性规划问题的图解法线性规划问题的图解法（2）无界解的情况）无界解的情况 【例9.10】对下述线性规划问题 用图解法求解结果如图2.3(a)所示.从图中可以看出，由于可行域是无界区域，当目标函数等值线沿箭头方向平行移动时，始终与该无界区域相交.此时，目标函数值无上界，因此无最优解，也称最优解无界最优解无界.7/5/2024429.3 线性规划问题的图解法（2）无界解的情况8/13/29.3 线性规划问题的图解法线性规划问题的图解法（3 3）无可行解的情况）无可行解的情况 【例9.11】对线性规划问题由图2.3(b)可以看出，同时满足所有约束条件的点不存在，即可行域为空集，也就是没有可行解，故不存在最优解.7/5/2024439.3 线性规划问题的图解法（3）无可行解的情况由图2.39.3 线性规划问题的图解法线性规划问题的图解法当根据实际问题建立的线性规划模型的求解结果出现（2）,（3）两种情况时，一般说明建模有错误.前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意.下面再给出一个求目标函数最小化的线性规划问题.【例【例9.129.12】求解线性规划求解线性规划7/5/2024449.3 线性规划问题的图解法当根据实际问题建立的线性规划模9.3 线性规划问题的图解法线性规划问题的图解法解 画出此线性规划问题的可行域，如图中的阴影部分.目标函数 ，它在坐标平面上可表示为以f为参数，以-2/4为斜率的一组等值线.当等值线移动到B点时，目标函数在可行域中取最小值.B点的坐标可以从线性方程组中求出，为 .这就是所求线性规划问题的最优解，且 .7/5/2024459.3 线性规划问题的图解法解 画出此线性规划问题的可行9.3 线性规划问题的图解法线性规划问题的图解法7/5/2024469.3 线性规划问题的图解法8/13/2023469.3 线性规划问题的图解法线性规划问题的图解法1.通过图解法了解线性规划有几种解的形式2.作图的关键有三点 (1)可行解区域要画正确 (2)目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动7/5/2024479.3 线性规划问题的图解法1.通过图解法了解线性规划有几9.4 线性规划问题解的性质线性规划问题解的性质7/5/2024489.4 线性规划问题解的性质8/13/2023481.线性规划问题的标准形线性规划问题的标准形前面曾给出了线性规划问题的一般形式，可以看出，其中有的要求目标函数最大化，有的要求目标函数最小化；约束条件可以是“”或“”形式的不等式，也可以是等式；决策变量一般是非负约束，但也允许在 范围内取值，即无约束。为了进一步研究和讨论，就需要把线性规划问题的一般形式化为统一的标准形式。9.4 线性规划问题解的性质线性规划问题解的性质7/5/2024491.线性规划问题的标准形前面曾给出了线性规划问题的一般形线性规划的一般形式可表示为：线性规划的一般形式可表示为：7/5/202450线性规划的一般形式可表示为：8/13/202350这里的标准形式有以下规定：这里的标准形式有以下规定：（1）目标函数是求最大值；（2）所有约束条件均用等式表示；（3）所有决策变量均取非负数；（4）所有约束常数均为非负数.9.4 线性规划问题解的性质线性规划问题解的性质7/5/202451这里的标准形式有以下规定：9.4 线性规划问题解的性质8 于是，具有个约束条件和个决策变量的线性于是，具有个约束条件和个决策变量的线性规划问题的规划问题的标准形标准形为：为：9.4 线性规划问题解的性质线性规划问题解的性质7/5/202452 于是，具有个约束条件和个决策变量的线性在约束条件 0（j=1，2，n）下，求一组未知变量（j=1，2，n）的值，使得 。常记为如下更为紧凑的形式 或其缩写形式为：其缩写形式为：7/5/202453在约束条件 其中其中 b b和和C C为已知非负常数，为已知非负常数，A A为已知常数矩阵，且为已知常数矩阵，且rank(A)=mrank(A)=m。一般可以通过以下方法，把。一般可以通过以下方法，把非标准形线性规划非标准形线性规划问题化为标准形：问题化为标准形：（1）目标函数的标准化）目标函数的标准化如果线性规划问题是求目标函数的最小值，即如果线性规划问题是求目标函数的最小值，即则令则令 ，得，得 ，这就同，这就同标准形的目标函数的形式一致了标准形的目标函数的形式一致了.但要注意，如果要求原但要注意，如果要求原问题的最优值，应取最优值的相反数问题的最优值，应取最优值的相反数.9.4 线性规划问题解的性质线性规划问题解的性质7/5/202454 其中 b和C为已知非负常数，A为已知常数矩阵，（2）约束条件的标准化）约束条件的标准化当约束条件为当约束条件为形式的不等式时，可在不等式左边加上一形式的不等式时，可在不等式左边加上一个非负的新变量（称为个非负的新变量（称为松弛变量松弛变量(slack variables)），把），把不等号变为等号；不等号变为等号；当约束条件为当约束条件为形式的不等式时，可在不等式左边减去一形式的不等式时，可在不等式左边减去一个非负的新变量（称为个非负的新变量（称为剩余变量剩余变量），把不等号变为等号），把不等号变为等号.9.4 线性规划问题解的性质线性规划问题解的性质7/5/202455（2）约束条件的标准化 9.4 线性规划问题解的性质8/1（3）决策变量的标准化）决策变量的标准化 如果某一决策变量是一个符号不受限制的“自由变量”，可以引入两个非负的新变量 和 ，并作变换 ，将决策变量标准化。9.4 线性规划问题解的性质线性规划问题解的性质7/5/202456（3）决策变量的标准化 9.4 线性规划问题解的性质8/1（4）约束常数的标准化）约束常数的标准化 如果有某约束常数为负数，可在等如果有某约束常数为负数，可在等式（或不等式）两边同时乘以，把约束常式（或不等式）两边同时乘以，把约束常数变为正数数变为正数.9.4 线性规划问题解的性质线性规划问题解的性质7/5/202457（4）约束常数的标准化 9.4 线性规划问题解的性质8/1【例【例9.13】把下面的线性规划问题化为标准形：把下面的线性规划问题化为标准形：【解】【解】此例只有约束条件不符合标准形，为此引入非负的松此例只有约束条件不符合标准形，为此引入非负的松弛变量弛变量 ，并分别把它们加到第，并分别把它们加到第1个和第个和第2个不等式的左个不等式的左边，即得标准形：边，即得标准形：注意，所加松弛变量注意，所加松弛变量 表示没有被利用的资源，当然也表示没有被利用的资源，当然也没有利润，所以在目标函数没有利润，所以在目标函数 中的系数应为零中的系数应为零.9.4 线性规划问题解的性质线性规划问题解的性质7/5/202458【例9.13】把下面的线性规划问题化为标准形：9.4 线9.4 线性规划问题解的性质线性规划问题解的性质【例【例9.14】将下面线性规划问题化为标准形将下面线性规划问题化为标准形【解【解】令】令 ，把求，把求 改为求改为求 ；用；用 替换替换 ，其中，其中 ；在第；在第1个约束不等式的左边加入松弛变量个约束不等式的左边加入松弛变量 ，在第，在第2个约束不等式的左边减去剩余变量个约束不等式的左边减去剩余变量 ，这样即可得，这样即可得到该问题的标准形为到该问题的标准形为7/5/2024599.4 线性规划问题解的性质【例9.14】将下面线性规划问，9.4 线性规划问题解的性质线性规划问题解的性质标准形标准形原问题原问题7/5/202460，9.4 线性规划问题解的性质标准形原问题8/13/202.线性规划的解线性规划的解 可行解与最优解可行解与最优解 满足约束条件（即满足线性约束和非负约束）的一组变量为可行解。所有可行解组成的集合称为可行域。使目标函数最大或最小化的可行解称为最优解。7/5/2024612.线性规划的解 8/13/202361基本解与基本可行解基本解与基本可行解 在线性规划问题中，将约束方程组的mn阶矩阵A写成由n个列向量组成的分块矩阵7/5/202462基本解与基本可行解 8/13/202362 如果B是A中的一个m阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设则称 为基向量，与基向量相对应的向量 为基变量，而其余的变量为 非基变量。7/5/202463 如果B是A中的一个m阶的非奇异子阵，则称B为 如果 是方程组 的解,则 就是方程组 的一个解，它称之为对应于基B的基本解，简称基解。满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。7/5/202464 如果 线性规划问题的以上几个解的关系，可用下图来描述：7/5/202465线性规划问题的以上几个解的关系，可用下图来描述：8/13/2【定义定义9.1】如果集合如果集合K中任意两点中任意两点s,t之间连线上所有的之间连线上所有的点都是集合点都是集合K中的点，即对于任意的中的点，即对于任意的 ，都有，都有 ，则称，则称K为凸集为凸集.例如图例如图9.5中（中（a）,（b）,（c）为凸集，而（）为凸集，而（d）,（e）不是凸集）不是凸集.3.线性规划问题解的基本性质线性规划问题解的基本性质(a)(b)(c)(d)(e)图图9.5 凸集与非凸集示例凸集与非凸集示例 9.4 线性规划问题解的性质线性规划问题解的性质7/5/202466【定义9.1】如果集合K中任意两点s,t之间连线上所有的【定理定理9.1】线性规划问题的可行域线性规划问题的可行域 是一个凸集是一个凸集.这两个定理我们不给予数学证明这两个定理我们不给予数学证明.结合图解法，我们可以清晰结合图解法，我们可以清晰地了解到线性规划问题解的有关性质地了解到线性规划问题解的有关性质.定理定理9.1说明：联结线说明：联结线性规划问题任意两个可行解的线段上的点（坐标）仍是可行性规划问题任意两个可行解的线段上的点（坐标）仍是可行解解.定理定理9.2则告诉我们：如果一个线性规划问题有最优解，则告诉我们：如果一个线性规划问题有最优解，则一定可以从可行域的有限个顶点中找到则一定可以从可行域的有限个顶点中找到.【定理定理9.2】若可行域非空有界，则线性规划问题的最优值一若可行域非空有界，则线性规划问题的最优值一定可以在可行域的某个顶点上达到定可以在可行域的某个顶点上达到.9.4 线性规划问题解的性质线性规划问题解的性质7/5/202467【定理9.1】线性规划问题的可行域是一个凸集.这两个定理【定义定义9.2】如果凸集如果凸集K中的点中的点x不能成为任何线段的内不能成为任何线段的内点，即对任意点，即对任意 ，都不存在，都不存在 ，使，使得得 ，则称，则称x 为为K 的一个顶点的一个顶点.例如三角形、正方形、凸多边形、凸无界区域的顶点及例如三角形、正方形、凸多边形、凸无界区域的顶点及圆周上的点，都是相应凸集的顶点圆周上的点，都是相应凸集的顶点.从图解法的例子中知道线性规划问题的可行域是一个凸集，从图解法的例子中知道线性规划问题的可行域是一个凸集，且如果问题有最优值，都是在顶点上达到且如果问题有最优值，都是在顶点上达到.这些性质推广到一般，就是下面几个重要定理这些性质推广到一般，就是下面几个重要定理.9.4 线性规划问题解的性质线性规划问题解的性质7/5/202468【定义9.2】如果凸集K中的点x不能成为任何线段的内点，9.4 线性规划问题解的性质线性规划问题解的性质 1.将非标准形化为标准形的方法 2.线性规划问题的解 3.线性规划问题解的性质 （1）线性规划问题的可行域是一个凸集。（2）若可行域非空有界，则线性规划问题的最优值一定可以在可行域的某个顶点上达到。7/5/2024699.4 线性规划问题解的性质 1.将非标准形化为标准形的方9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法 7/5/2024709.5 解线性规划问题的单纯形法 8/13/202370 单纯形法是求解线性规划的一种通用方法，单纯形法是求解线性规划的一种通用方法，1947年由美国年由美国数学家丹兹格（数学家丹兹格（G.B.Dantzig）给出）给出.下面结合下面结合9.1中的利润最中的利润最大化问题介绍单纯形法的基本内容大化问题介绍单纯形法的基本内容.由由9.1中的例中的例9.1提供的提供的数数学模型学模型为为:9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法7/5/202471 单纯形法是求解线性规划的一种通用方法，1947（1）先化为标准形）先化为标准形.引入松弛变量引入松弛变量 得到得到标准形标准形9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法7/5/202472（1）先化为标准形.引入松弛变量 （2 2）再把目）再把目标函数函数改写成改写成并把它加入到并把它加入到约束方程束方程组中去，即得到方程中去，即得到方程组9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法7/5/202473（2）再把目标函数改写成并把它加入到约束方程组中去，即得到方将此方程将此方程组的系数及常数的系数及常数项b b列成一个数表，即列成一个数表，即.9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法 称此表称此表为初始初始单纯形表形表.表中的数字被分成了表中的数字被分成了4 4部分，位于左部分，位于左下角的每个数字称下角的每个数字称为检验数数.此此时与与 对应的的检验数都是数都是负数，因此，若不令数，因此，若不令，只要有一个，只要有一个是正数，是正数，则它与它与负数相乘后仍是数相乘后仍是负数，移数，移项到右到右边，函数函数值值就会增大，为此转到下一步就会增大，为此转到下一步.7/5/202474将此方程组的系数及常数项b列成一个数表，即.9.5 解线性（3 3）在）在负检验数中数中选绝对值最大的最大的负数（即数（即 7 7），在），在对应的的列中，将列中，将该列中的正数分列中的正数分别去除去除对应的常数的常数项，选择比比值最小最小者所者所对应的元素的元素为主元（称主元（称为最小比最小比值原原则）.在在这里里然后用矩然后用矩阵的初等行的初等行变换，将主元化，将主元化为1 1，把同列的其他元，把同列的其他元素化素化为0.0.这一一过程如下：程如下：将矩将矩阵 可知位于第可知位于第2 2行、第行、第3 3列的元素列的元素3 3为主元，主元，标为 ,9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法7/5/202475（3）在负检验数中选绝对值最大的负数（即7），在对应的列中的第的第2 2行乘以行乘以1/31/3，得，得 再将矩再将矩阵的第的第2 2行乘以（行乘以（2 2）加到第）加到第1 1行，第行，第2 2行乘以行乘以7 7加加到第到第3 3行，得行，得 此此时的目的目标函数函数值已已经由原来的由原来的0增加到增加到700/3.由于由于检验数中仍数中仍有有负数，按照最小比数，按照最小比值原原则，可知位于第，可知位于第1行、第行、第2列的元素列的元素4/3为主元主元.同同样用矩用矩阵的初等行的初等行变换，将主元化，将主元化为1，把同列的其，把同列的其他元素化他元素化为0，9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法7/5/202476的第2行乘以1/3，得 再将矩阵的第2行乘以（2）加到过程如下：程如下：将矩将矩阵A A的第的第1行乘以行乘以3/4，得，得 这时表中已表中已经没有没有负检验数，表明目数，表明目标函数已函数已经达到最大达到最大值.最后最后这张表称表称为最最优单纯形表形表.易知最易知最优解解为最最优值为250.从而原从而原线性性规划划问题的最的最优解解为对应的目的目标函数最函数最优值为250.9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法再将矩阵的第再将矩阵的第2行乘以（行乘以（2）加到第）加到第1行，第行，第2行乘以行乘以7加到加到第第3行，得行，得7/5/202477过程如下：将矩阵A的第1行乘以3/4，得 这时表中已经没有 上述求解线性规划问题的方法称为上述求解线性规划问题的方法称为单纯形法单纯形法.单纯形法步骤如下单纯形法步骤如下：第第1步，将线性规划化成标准形；步，将线性规划化成标准形；第第2步，写出初始单纯形表；步，写出初始单纯形表；第第3步，对检验数进行检验步，对检验数进行检验.若检验数均为非负数，则得到若检验数均为非负数，则得到最优单纯形表最优单纯形表.若有负数，则在检验数绝对值最大的负数所对若有负数，则在检验数绝对值最大的负数所对应的列中，按最小比值原则选主元，用初等行变换化主元为应的列中，按最小比值原则选主元，用初等行变换化主元为1，主元所在列其余元素化为，主元所在列其余元素化为0，得到一张新单纯形表，得到一张新单纯形表.再检验该再检验该表是否为最优单纯形表，若不是，重复上述过程，直到得出最表是否为最优单纯形表，若不是，重复上述过程，直到得出最优单纯形表优单纯形表.第第4步，从最优单纯形表直接写出最优解和最优值步，从最优单纯形表直接写出最优解和最优值.9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法7/5/202478 上述求解线性规划问题的方法称为单纯形法.9.5 解从上例求解从上例求解过程看到，程看到，单纯形表中形表中 所对应的列始终不变，故所对应的列始终不变，故在实际计算中可省去不写在实际计算中可省去不写.上例的求解过程本质上是矩阵的初上例的求解过程本质上是矩阵的初等行变换过程，我们可以把此例的单纯形法求解过程简化为等行变换过程，我们可以把此例的单纯形法求解过程简化为9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法7/5/202479从上例求解过程看到，单纯形表中 所对应的列始终不变，故在实9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法所以最优解及最优值分别为【注注1 1】若在若在计算算过程中，程中，单纯形表出形表出现某某检验数数为负，但其，但其所在的列无正元素的情况，所在的列无正元素的情况，则可以可以证明明该问题无最无最优解解.7/5/2024809.5 解线性规划问题的单纯形法所以最优解及最优值分别为【解【解 】引入松弛】引入松弛变量，化量，化为标准形准形 9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法【例9.15】解线性规划问题 7/5/202481【解】引入松弛变量，化为标准形9.5 解线性规划问题的单初始单纯形表为初始单纯形表为由于由于检验数数 1所在列无正数元素，故此所在列无正数元素，故此问题无最无最优解解.9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法7/5/202482初始单纯形表为由于检验数1所在列无正数元素，故此问题无最优【注注2 2】在上例的初始】在上例的初始单纯形表中，由虚形表中，由虚线隔开的左上部分，隔开的左上部分，所在列的元素构成一个二所在列的元素构成一个二阶单位矩位矩阵我我们称称 为基变量为基变量.一般地，一般地，对含有含有n个个变量、量、m个个约束的束的线性性规划划问题，当，当把它化把它化为标准形后，若恰有一个准形后，若恰有一个m阶单位矩位矩阵，就可以用前面，就可以用前面的的单纯形法求出最形法求出最优解（若最解（若最优解存在）；若基解存在）；若基变量不足量不足m个，个，则用改用改进单纯形法或形法或对偶偶单纯形法求解形法求解.由于由于这两种方法用到两种方法用到较多的数学知多的数学知识，这里不再介里不再介绍，但，但WinQSB软件中的件中的线性性规划程序已划程序已经包含了改包含了改进单纯形法和形法和对偶偶单纯形法形法.9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法7/5/202483【注2】在上例的初始单纯形表中，由虚线隔开的左上部分，所在列9.5 解线性规划问题的单纯形法解线性规划问题的单纯形法1.判断基本可行解.有3种情形：已是最优解，是无界解，不能确定.前2种情形计算结束，第3种情形需要继续迭代，先进基后出基，初等变换求下一个基本可行解，直到出现最优解或无界解为止。2.判定方法唯一最优解的判定唯一最优解的判定：所有非基变量的检验数非零：所有非基变量的检验数非零,则线则线 规划具有唯一最优解。规划具有唯一最优解。多重最优解的判断多重最优解的判断:最优表中存在非基变量的检验数为零最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。则线则性规划具有多重最优解。无界解的判断无界解的判断:某个检验数大于某个检验数大于0 0且该检验数所在列中所且该检验数所在列中所有元素小或等于，则线性规划具有无界解。有元素小或等于，则线性规划具有无界解。7/5/2024849.5 解线性规划问题的单纯形法1.判断基本可行解.有3种9.6 线性规划的应用线性规划的应用7/5/2024859.6 线性规划的应用8/13/2023859.6 线性规划的应用线性规划的应用 线性规划在国内外很多部门的规划、管理、决策过程中有大线性规划在国内外很多部门的规划、管理、决策过程中有大量成功的应用，并收到了良好的效果量成功的应用，并收到了良好的效果.但是，应用线性规划来解但是，应用线性规划来解决某一类实际问题时，由于问题的复杂性和情况的多变性，要决某一类实际问题时，由于问题的复杂性和情况的多变性，要真正建立一个反映实际问题的、能得出正确结论的理想模型，真正建立一个反映实际问题的、能得出正确结论的理想模型，并不是一件容易的事情并不是一件容易的事情.它要求建模者具有丰富的经验、较强的它要求建模者具有丰富的经验、较强的创造力和比较熟练的技巧创造力和比较熟练的技巧.本节通过一些被简化了的问题，介绍本节通过一些被简化了的问题，介绍建立线性规划模型的基本思路和基本技巧建立线性规划模型的基本思路和基本技巧.7/5/2024869.6 线性规划的应用 线性规划在国内外很多部门1.1.办学学规模模问题【例【例9.169.16】某人准某人准备投投资12001200万元万元办一所中学，一所中学，为了考了考虑社会效益和社会效益和经济效益，效益，对该地区教育市地区教育市场进行行调查，得出一，得出一组数据，如表数据，如表9.12所示所示.表表9.12 9.12 市市场调查表表9.6 线性规划的应用线性规划的应用班级班级班级学生数班级学生数配备教师数配备教师数硬件建设费（万元）硬件建设费（万元）教师年薪（万元）教师年薪（万元）初中初中50502.02.028281.21.2高中高中40402.52.558581.61.6 根据物价部根据物价部门的有关文件，初中是的有关文件，初中是义务教育教育阶段，收段，收费标准适当控制，准适当控制，预计除除书费、办公公费外，初中每个学生每年可收取外，初中每个学生每年可收取600600元，而高中每个学生元，而高中每个学生每年可收取每年可收取15001500元元.因生源和因生源和环境等条件限制，境等条件限制，办学学规模以模以20203030个（含个（含2020与与3030）班）班为宜宜.教教师实行聘任制行聘任制.初、高中的教育周期均初、高中的教育周期均为3 3年年.请你合理地安排你合理地安排招生招生计划，使年利划，使年利润最大最大.问：大：大约经过多少年可以收回全部投多少年可以收回全部投资？7/5/2024871.办学规模问题9.6 线性规划的应用班级班级学生数配备教解解 设初中编制班数为设初中编制班数为x,高中编制班数为高中编制班数为y,又设年利润为又设年利润为 f,（单位：万元），那么（单位：万元），那么 即即.于是此于是此问题的的线性性规划模型划模型为解得最优解解得最优解代入代入 中得中得9.6 线性规划的应用线性规划的应用7/5/202488解 设初中编制班数为x,高中编制班数为y,又设年利润为 f 故学校的最优规模和招生计划分别为故学校的最优规模和招生计划分别为最优规模：初中最优规模：初中18个班，高中个班，高中12个班；个班；招生计划：第招生计划：第1年初中招生年初中招生6个班约个班约300人，高中招生人，高中招生4个班约个班约160人人.以后每年按此计划招生以后每年按此计划招生.设经过设经过n年可收回投年可收回投资.第第1 1年利年利润为第第2 2年利年利润为 211.6=23.2(万元万元);以后每年的利以后每年的利润均均为34.834.8万元万元.故依故依题意意应有有解得解得 (年年).).即即约经过3636年可以收回全部投年可以收回全部投资.9.6 线性规划的应用线性规划的应用7/5/202489故学校的最优规模和招生计划分别为 设经过n年可收回投资.2.投资问题投资问题【例【例9.17】某投资人在今后】某投资人在今后3年内有年内有A,B,C,D共共 4个投资项目，个投资项目，项目项目A在在3年内每年初投资，年底可获利润年内每年初投资，年底可获利润20%，并可将本金收，并可将本金收回；项目回；项目B在第在第1年年初投资，第年年初投资，第2年年底可获利润年年底可获利润60%，并将，并将本金收回，但该项目投资不得超过本金收回，但该项目投资不得超过5万元；项目万元；项目C在第在第2年初投年初投资，第资，第3年底收回本金，并获利润年底收回本金，并获利润40%，但该项目投资不得超，但该项目投资不得超过过3万元；项目万元；项目D在第在第3年初投资，于该年底收回本金，且获利年初投资，于该年底收回本金，且获利润润30%，但该项目投资不得超过，但该项目投资不得超过2万元万元.该投资人准备拿出该投资人准备拿出6万万元资金，问如何制订投资计划，使该企业在第元资金，问如何制订投资计划，使该企业在第3年底，投资的年底，投资的本利之和最大？本利之和最大？9.6 线性规划的应用线性规划的应用7/5/2024902.投资问题9.6 线性规划的应用8/13/202390【解】【解】这是一个连续投资问题这是一个连续投资问题.设决策变量设决策变量xij为第为第j年投资到第年投资到第i 个个项目的资金项目的资金(i=1,2,3,4,1,2,3,4,分别对应于项目分别对应于项目A,B,C,D；分分别对应于投资年份别对应于投资年份),见列表见列表9.13.表表9.13 投资项目投资项目投投资机会机会项目名称项目名称 第第1 1年年初年年初 第第2 2年年初年年初 第第3 3年年初年年初A AB BC CD D9.6 线性规划的应用线性规划的应用7/5/202491【解】这是一个连续投资问题.设决策变量xij为第j年投资下面分析每年资金的使用情况并建立线性规划模型下面分析每年资金的使用情况并建立线性规划模型.第第1年初，年初，有有A,B两个项目，企业只能提供两个项目，企业只能提供6万元资金，故有万元资金，故有:.项目项目B不得超过不得超过5万元，有万元，有 第第2年初年初，有，有A,C两个投资项目两个投资项目.此时第此时第1年初投资到项目年初投资到项目A的资的资金已全部收回，本利和为金已全部收回，本利和为.这些资金可用于第这些资金可用于第2年的投资，年的投资，而且要求，而且要求 9.6 线性规划的应用线性规划的应用于是于是；7/5/202492下面分析每年资金的使用情况并建立线性规划模型.项目B不得超9.6 线性规划的应用线性规划的应用第3年初，第1年初投资到项目B的资金全部收回，本利和为 ;第第2年初投资于项目年初投资于项目A的资金也全部收回，本利和为的资金也全部收回，本利和为以上两笔资金可供该年继续投资以上两笔资金可供该年继续投资.第第3年内还有年内还有A,D两个项两个项目的投资，可得目的投资，可得，而且要求，而且要求 第第3年底年底，到期把所有本利和收回，到期把所有本利和收回.所能收回的资金有第所能收回的资金有第2年年初投资到项目初投资到项目C的本利和的本利和，第，第3年初投资到项目年初投资到项目A的的本利和本利和 及投资到项目及投资到项目D的本利和的本利和，则第，则第3年底获年底获得的本利和为得的本利和为;7/5/2024939.6 线性规划的应用第3年初，第1年初投资到项目B的资金将上述目标函数和约束条件整理后即可得出该问题完整的将上述目标函数和约束条件整理后即可得出该问题完整的线线性规划模型性规划模型:求解得到最优投资方案如表求解得到最优投资方案如表9.14所示，且在第所示，且在第3年底收回投年底收回投资的本利和最大为资的本利和最大为11.528万元万元.9.6 线性规划的应用线性规划的应用7/5/202494将上述目标函数和约束条件整理后即可得出该问题完整的线性规划模表表9.14 最优投资方案最优投资方案 投资机会投资机会 项目名称项目名称 第第1 1年年初年年初 第第2 2年年初年年初 第第3 3年年初年年初A AX X1111=1=1X X1212=1.2=1.2X X1313=7.44=7.44B BX X2121=5=5C CX X3232=0=0D DX X4343=2=29.6 线性规划的应用线性规划的应用7/5/202495表9.14 最优投资方案 投资机会3.人力资源分配问题人力资源分配问题【例【例9.19】某百货商场售货员的需求经过统计分析如表】某百货商场售货员的需求经过统计分析如表9.16所示所示.为了保证售货员充分休息，售货员每周工作为了保证售货员充分休息，售货员每周工作5天，天，休息休息2天，并要求休息的天，并要求休息的2天是连续的，问：应该如何安排售天是连续的，问：应该如何安排售货员的作息时间，既满足工作需要，又使配备的售货员人数货员的作息时间，既满足工作需要，又使配备的售货员人数最少？最少？表表9.16 售货人员需求统计表售货人员需求统计表时间时间所需售货员人数所需售货员人数星期日星期日2828星期一星期一1515星期二星期二2424星期三星期三2525星期四星期四1919星期五星期五3131星期六星期六28289.6 线性规划的应用线性规划的应用7/5/202