第一章线性规划课件.ppt

《第一章线性规划课件.ppt》由会员分享，可在线阅读，更多相关《第一章线性规划课件.ppt（259页珍藏版）》请在三一办公上搜索。

1、第一章 线性规划,1.1 线性规划的模型与图解法 1.2 单纯形法 1.3 对偶问题与灵敏度分析 1.4 线性整数规划 1.5 运输问题,1.1 线性规划的模型与图解法一、线性规划问题及其数学模型,在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。,例1.1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产计划方案。,1）决策变量：需决策的量，即待求的未知数；,2）目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；,3）约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。,线性规划模型的

2、三要素,例1.1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产计划方案。,在本例中,约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为,决策变量：甲、乙产品的计划产量，记为；,目标函数：总收入记为,则,为体现对其追求极大化，在 的前面冠以极大号Max；,解：设安排甲、乙产量分别为,总收入为，则模型为：,线性规划模型的一个基本特点：目标和约束均为变量的线性表达式。,如果模型中出现如的非线性表达式，则不属于线性规划。,例1.2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：,要求在

3、充分利用各种资源条件下使建造住宅的总面积为最大，求建造方案。,解:设今年计划修建砖混、壁板、大模住宅各为,为总面积,则本问题的数学模型为:,前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。,练习：某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有M、N两种。有关数据如下：,试决定买M与N二种饲料各多少公斤而使支出的总费用为最少？,解：设购买M、N饲料各为，则,线性规划模型的一般形式：以MAX型、约束为例,决策变量：目标函数：约束条件：,模型一般式的矩阵形式,则模型可表示为,记,回顾例1.1的模型其中 表示决策变量的向量；表示

4、产品的价格向量；表示资源限制向量；表示产品对资源的单耗系数矩阵。,一般地中 称为决策变量向量，称为价格系数向量,称为技术系数矩阵,称为资源限制向量。,问题：为什么 称为技术系数矩阵？,图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。,二、线性规划问题的图解法,1.做约束的图形 先做非负约束的图形；再做资源约束的图形。,以例1.1为例，其约束为,图解法步骤,问题：不等式的几何意义是什么？怎样做图？,1.做约束的图形 先做非负约束的图形；再做资源约束的图形。,以例1.1为例，其约束为,图解

5、法步骤,各约束的公共部分即模型的约束，称可行域。,3.求出最优解 将目标直线向使目标 优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点 即最优解。,练习：用图解法求解下面的线性规划。,-最优解在什么位置获得？,-线性规划的可行域是一个什么形状？,问题：在上两例中,多边形，而且是“凸”形的多边形。,在边界，而且是在某个顶点获得。,（1）线性规划的约束集（即可行域）是一个凸多面体。,凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：,凸集中的“极点”，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。,由图解法得到线

6、性规划解的一些特性,因为，由图解法可知，只有当目标直线平移到边界时，才能使目标 z 达到最大限度的优化。,问题：本性质有何重要意义？,（2）线性规划的最优解（若存在的话）必能在可行域的顶点获得。,它使得在可行域中寻优的工作由“无限”上升为“有限”，从而为线性规划的算法设计提供了重要基础。,（3）线性规划解的几种情形,内容回顾与思考1.线性规划解决的是一类什么问题？2.线性规划模型构成的三要素？3.线性规划模型的一般式？4.图解法的一般步骤？5.图解法得到线性规划哪些性质？,单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。尽管在其后的几十年中，

7、又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。,1.2 单纯形法,早在二战期间，在美国空军服役的科学家丹捷格就提出了“单纯形方法”。这个方法当时曾经保密，直到战后的1947年，当丹捷格离开军队，转任斯坦福大学教授之后，才公开发表。丹捷格不仅提出了单纯形法，而且在线性规划相关研究领域做出了一系列杰出的贡献。他被人们誉为“线性规划之父”，以他的名字命名的“丹捷格奖”成为运筹学界的最高奖项之一。,（1914-2005）,一、单纯形法的预备知识,1.线性规划的标准型 来自实际问题的线性规划模型形式各异，在用单纯形法求解之前，先要将模型化为统一的形式标准型：,标准型的特征

8、：Max型、等式约束、非负约束,非标准形式如何化为标准？（1）Min型化为Max型 因为，求一个函数的极小点，等价于求该函数的负函数的极大点。,注意：Min化为Max后，最优解不变，最优值差负号。,（2）不等式约束化为等式约束 分析：以例1.1中煤的约束为例,x3 称为松弛变量。问题：它的实际意义是什么？,煤资源的“剩余”。,之所以“不等”是因为左右两边有一个差额，可称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为x3，则有,练习：请将例1.1的约束 化为标准型,解：增加松弛变量,则约束化为,可见：松弛变量的系数恰构成单位阵,问题：松弛变量在目标中的系数为何？,问

9、题：标准型与原来模型解的关系？,例如,可化为,X2为自由变量,2.基本概念（1）可行解与最优解,（2）基矩阵与基变量,基矩阵(简称基)：系数阵A中的m阶可逆子阵，记为B；其余部分称为非基矩阵，记为N。,基向量：基B中的列；其余称非基向量。,基变量：与基向量Pj对应的决策变量xj，记其组成的向量为XB；与非基向量对应的变量称非基变量，记其组成的向量为XN。,如 指出A中的基。,记A中的列为Pj，则每个Pj 对应于一个xj，即。,6个。,一般地，mn 阶矩阵A中基的个数最多有多少个？,问题：本例的 中一共有几个基？,（3）基本解与基本可行解,可见：一个基本解是由一个基决定的。注意：基本解仅是资源约

10、束的解，并未要求其非负，因此其未必可行。,称非负的基本解为基本可行解（简称基可行解）。,例1.4 在例1.3的模型,中，求相应于基B1和B2的基本解，它们是否基本可行解？,上二组概念间的联系：,几种解之间的关系：,可行解,基本解,非可行解,基本可行解,问题：基本可行解是可行域中的哪些点？,3.基本定理,（1）线性规划的可行域是一个凸多面体。,（2）线性规划可行域的顶点与基本可行解一 一对应。,（3）线性规划的最优解（若存在的话）必能 在可行域的顶点获得。,二、单纯形法的步骤,确定初始基本可行解,寻找更好的基本可行解,否,是,stop,单纯形法是一种迭代的算法，它的思想是在可行域的顶点基本可行解

11、中寻优。由于顶点是有限个（为什么？）,因此，算法经有限步可终止。,方法前提：模型化为标准型,1.确定初始基可行解,由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。,方法：若A中含I，则B0=I；若A中不含I，则要用人工变量法构造一 个I。,问题：若B0=I，则X0=？,2.最优性检验,分析：用什么检验？,目标。,记为，当 0时，当前解为最优。称检验数向量。,而目标,所以,方法：,（1）计算每个xj的检验数,（2）若所有j 0，则当前解为最优；,否则，非最优，转3。,问题：非最优的特征为何？,3.寻找更好的基可行解,由于基可行解与基对应，即寻找一个新的基

12、可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。,换基后，转2。即再检验，直至满足最优性条件。,以例1.1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。,（1）先将模型化为标准型,A中含I（P3，P4，P5），可以用单纯形法求解。,(2)确定初始基可行解、检验,计算检验数,确定进基向量为P2,再计算检验比,确定出基向量为P5。,（3）换基、计算下一个基可行解、再检验，直 至最优,练习：对于下面的线性规划,（1）先用图解法求解；（2）将模型化为标准型；（3）再用单纯形法步骤求出其最优解，并指出求解过程中每一个基可行解相当于可行域的哪一个角点。,解：（1

13、）图解法求解,（2）将模型化为标准型,A中含I（P3，P4），可以用单纯形法求解。,（3）用单纯形法求解,确定初始基可行解、检验,求解过程中每一个基可行解相当于可行域的哪一个角点？,问题：当模型规模较大时，计算量很大。,事实上，单纯形法的实现是在单纯形表上完成的。,总结上述过程：,三、单纯形表,单纯形表是基于单纯形法的步骤设计的计算表格，是单纯形法的具体实现。,回顾单纯形法步骤,而相邻两个 之间只有一列不同，可分析其逆阵间关系：,即每个 可由上一个 经以 为主元的初等行变换得到，基于此设计了单纯形表。,用单纯形表计算的主要过程：,（2）计算检验数 判断最优：,（3）计算检验比换基：,例1.5

14、用单纯形法解例1.1,标准模型的A中是否含I？,松弛变量系数恰好构成I。,中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换（也称高斯消去）。方法是：先将主元消成1，再用此1将其所在列的其余元消成0。,（请解释其实际意义）,甲乙产品产量的最优计划、相应的最大收入和资源剩余,基变量的检验数和系数列有何特征？,检验数均为0，,系数列均为单位向量列,练习：用单纯形法求解下面的线性规划,前面曾用图解法和单纯形法步骤求解过：,注：1.表上每一列的含义：,2.每张表上B-1的位置在哪？对应于初表中I 的位置。,例1.6：填出下面表中的空白,L,练习：用单纯形法求解下面的线性规划,直观上有什

15、么特点？,目标与某约束斜率相同,问题：本题的单纯形终表检验数有何特点？,非基变量x2 的检验数等于零。,四、大M法设模型已经化为标准型但A中不含I。,添加人工变量，将模型（1）化为（2）,用单纯形法求解（2）的结果：-最优解基变量中不含，则（2）的最 优解的前n个分量即（1）的最优解；-最优解基变量中含有，则（1）无解。,M称为罚因子，其作用是迫使 出基。,例1.7：用单纯形法求解下面的线性规划,模型已经是标准型，但A中不含I。,解：增加人工变量 将模型化为,注：（1）解的几种情况在单纯形表上的体现-唯一最优：终表非基检验数均小于零；-多重最优：终表非基检验数有等于零；-无界解：有正检验数相应

16、系数列均非正；-无解：最优基中含有人工变量。,（2）Min型单纯形表与Max型的区别仅在于：检验数反号，即-令负检验数中最小的对应的变量进基；-当检验数均大于等于零时为最优。,问题：Min型模型的大M法人工变量模型是什么？,内容回顾与思考1.基本可行解的概念和几何意义？2.单纯形法的原理步骤？3.单纯形表的原理和结构？4.大M法的原理和步骤？5.Min型单纯形表计算方法？,1.3 对偶问题与灵敏度分析,一、对偶问题及其模型 对偶理论是线性规划的重要基础理论，它揭示了：每一个线性规划都存在与它对偶的一个线性规划，二者之间有密切的联系，以至于把二者放在一起研究往往比单独研究一个问题更有意义。,这时

17、有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。,分析模型的三要素：购买者的决策变量、目标函数、约束条件,（D）称为（P）的对偶问题，（P）称为（D）的原始问题,对偶模型的一般式（对偶定义）,这是最常见的对称式对偶模型。例1.8已经显示了二者间具有十分对称的对应关系。,二、对偶性质1.对称性：对偶的对偶就是原始问题。,即（P）和（D）互为对偶，是对称的。,如果模型中含有等式约束或自由变量，则可转化为不等式约束和非负变量的形式分析。,练习：写出下面线性规划的对偶模型,解：既然模型是Min型，可按（D）整理，令,然后按（P）写出其对偶：,设对偶变量为,证：

18、由（P），（D）的约束可得,图示：,问题：若(P),(D)有一为无界解，则另一为何？,证：对任可行解，由弱对偶性，,故，同理，。,图示：,（）与（）的约束相同，故（）的最优解Y*是（）的可行解。由弱对偶性，而由解的最优性，故,证：对（P）增加松弛变量Xs，化为,其检验数为,，由解的最优性，。,取，,由对偶定理的证明过程可知，原始问题（P）的单纯形终表可同时得到（P）和（D）的最优解,例如，在 1.2 的练习中已知,xjym+j=0，yixn+i=0（i=1,2,m;j=1,2,n），在一对变量中，一个大于0，另一个一定等于0。,解：先写出其对偶,将 代入约束，第二至四约束为严格不等式，由互补松

19、弛性，,又，故,解得,三、对偶的经济意义,1.对偶最优解的经济解释：资源的影子价格（Shadow Price）,对偶问题的最优解：买主最低出价；原问题资源的影子价格：当该资源 增加1单位时引起的总收入的增量：卖主的内控价格。,注意：影子价格是在最优解前提下，并且其他资源不变。,解：（1）煤、电、油的影子价格分别是0，1.36，0.52；其经济意义是当煤、电、油分别增加1单位时可使总收入分别增加0、1.36、0.52。,增量恰好为1.36。,（2）由影子价格的定义，在最优解前提下，电再增加1单位引起总收入由 变化为：,2.对偶约束的经济解释 产品的机会成本,机会成本表示减少一件产品所节省的资源可

20、以增加的收益,3.对偶松弛变量的经济解释产品的差额成本,差额成本=机会成本 利润,在利润最大化的生产计划中（1）影子价格大于0的资源没有剩余；（2）有剩余的资源影子价格等于0；（3）安排生产的产品机会成本等于利润；（4）机会成本大于利润的产品不安排生产。,4.互补松弛关系的经济解释,练习：填空1.根据线性规划的互补松弛定理，影子价格大于零的资源一定 剩余；安排生产的产品机会成本一定 利润。（）A没有，小于 B没有，大于C没有，等于 D有，等于,C,2.若线性规划的原始问题增加一个变量，则其对偶问题就增加一个；因而对偶的最优目标值将可能变。（）A约束，好 B约束，坏C变量，好 D变量，坏,B,四

21、、对偶单纯形法,能否尝试对称的思路，在保持 下改善可行性？,基变换后再转（2）。效果：出基改善，进基保持。,例1.12：求解下面的线性规划,特点：化为标准型后A中不含I，但能否不用大M法？如果检验数均非正则可。,引入松弛变量，化为标准型,将线性规划与经济问题相关联的研究贡献，使得 T.G.Koopman（库普曼）和 L.V.Kamtorovich（康脱罗维奇）二人共同分享了1975年的第7届诺贝尔经济学奖。,主要讨论C、b和变量结构变化时对解的影响。,对解怎样影响？,只要由 解出 的范围即可。,解：由,解得：，,即油的限量在增加100至减少72范围内变化时，原最优基保持不变。,最优基不变是什么

22、意思？,投产结构不变。,价格 变为 时，因为它只影响最优性，即对检验数 产生影响，故只要其使变化后的 即可。,2.C变化时的分析,当 是非基变量 的价格系数时，只影响自己的检验数，由 一个不等式解得 的范围。,当 是基变量 的价格系数时，要影响所有的检验数，由 一组不等式解得 的范围。,3.增加新变量时的分析 主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产，数学意义是xn+1是否应进基。,方法：计算 的检验数，若，则增加，即投产有利；若，则不增加，即投产无利。,经济意义：,（1）电的影子价格是多少？使最优基仍适用的电的变化范围为何？（2）若有人愿以每度1元的价格向该

23、厂供应25度电，是否值得接受？（3）甲产品的价格在何范围内变化时，现最优解不变？,例1.16 例1.1（煤电油例）的单纯形终表如下：,（4）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为6.5，问该产品是否应投产？,解：（1）电的影子价格是1.36。由解得，即是原最优基B仍适用的电的变化范围。,（2）若有人愿以每度1元的价格向该厂供应25度 电，是否值得接受？,解：（2）值得。因25在B 的适用范围内（即影子价格适用），且。,（3）甲产品的价格在何范围内变化时，现最优解不变？,综合案例：派公司的产品规划,派公司是一个生产高尔夫器材的小型公司，近期推出了高、中价位的高尔夫袋新产品（标准袋

24、和高档袋），经销商对此产品十分感兴趣，并订购了派公司下3个月的全部产品。该高尔夫袋的生产过程主要包括4道工序：切割并印染原材料、缝合、成型（插入支撑架和球棒分离装置等）、检验和包装。有关数据如表1。派公司需决定标准袋和高档袋各生产多少可使公司的总利润最大。,（1）写出此问题的线性规划模型，约束及决策变量依表1中次序；,（2）引入松弛变量（依约束次序）后用单纯形法计算得某单纯形表如表2，请填完表中空白，并判断其是否终表，如果是，请写出最优生产计划、最大利润和资源剩余；,表2,（3）写出此问题的对偶问题的模型，及对偶的最优解与最优值；（4）写出成型时间的影子价格，求使该影子价格不变的成型时间的变化

25、范围；（5）若标准袋的利润可能发生变化，则其在何范围内变化时，可使原最优计划不改变？,解：（1）设标准袋和高档袋的产量分别为，总利润为z,则模型为,是终表，最优生产计划是生产标准袋540个，高档袋252个，最大利润7668美元，缝合时间余120，检验包装余18。,（3）设对偶变量为，对偶目标为w，则对偶模型为,（4）成型时间的影子价格为6.9375；由 解得，从而，即使该影子价格保持不变的成型时间变化范围。,（5）由 和 解得，从而，即使原最优计划不改变的标准袋利润的变化范围。,教材第二章习题和参考书中有很多线性规划的习题，请尽量练习。,线性规划计算软件：CPLEX、LINGO、EXCEL,E

26、XCEL使用简介（以例1.1为例）（1）在EXCEL表格输入模型基本数据。,（2）在工具栏规划求解的“规划求解参数”对话框输入模型完整信息：,内容回顾与思考1.对偶问题的定义是什么？2.对偶有哪些性质？3.对偶有哪些经济意义？4.对偶单纯形法的思想和主要步骤？5.灵敏度分析的方法？,线性规划1-3节综合练习,一、知识点,二、综合练习,1建模 问题：某工厂在今后4个月内需租用仓库堆放物资。已知各月份所需仓库面积如表1；仓库租用费用随合同期定，期限越长折扣越大，具体数据如表2。租用仓库的合同每月初都可办理，每份合同将具体规定租用面积数和期限。因此该厂可根据需要在任何一个月初办理租用合同，每次可签一

27、份或多份合同。工厂需决定如何租用可使总的所付租用费用最小。请建立此问题的线性规划模型（不解）。,表1,表2,分析：建模需要确定三要素变量：如何租用（每月租的面积和时间，怎么表示）目标：费用最小约束：不低于所需面积,解答：设第i个月租用j个月期的面积为,2图解法 问题：以下线性规划问题,的图解如下图。在下面各问题中，选择一个或多个正确的答案填入相应的括号中。,（1）这个线性规划的可行域为（）；ABD DEF BDEO FHIFEIG OEGC AEO BFO DIG EHG（2）这个线性规划的最优解位于（），如果变量，则最优解位于（）；A B C D E F G H I O,分析：由图解法可确定

28、约束的图形(DIG)，目标的图形向下移；如果，则可行域EFIG。,解答：（1）DIG；（2）D、E,3解的概念,问题：考虑线性规划问题（P）,证明：（1）若 均为（P）的可行解，则 也是（P）的可行解；（2）若B是A中一个可行基，且，则B为最优基。,分析：（1）考察可行解的概念，证明结果说明可行域是凸集；（2）考察最优性检验的理解，即检验数的证明。,证明：（1）,是（P）的可行解。,(2)（P）的可行解可表示为,目标可表示为,任意（P）的可行解代,入目标，都不大于B相应的基可行解的目标值,，即B为最优基。,4单纯形法（表）,问题：推导单纯形表任一次迭代前后检验数之间的关系，并由此说明变量出基后

29、，在紧邻的下一阶段不会再进基。,分析：考察对单纯形法步骤和单纯形表的熟 练掌握，并用一般式表示。,证明：单纯形表任一迭代前后的关系：,由检验数定义计算得迭代后的检验数,代前的检验数,的关系为,与迭,（说明检验数之间也具有同系数行之间的高斯消去关系）,5对偶理论,问题：设,，,分别为下列两个问题,分析：（I）和（II）的目标相同，因此其,对偶的约束相同，于是,也是问题（II）,的对偶问题的可行解。,证明：（）和（）的对偶分别为和 是 的最优解，则也是 的可行解。因此 有最优解，记为则有，而，得证。,6灵敏度分析,问题：已知线性规划问题,当 时，用单纯形法求得最终表如表3。,表3,要求：（1）确定

30、 的值；（2）当 时，t2在什么范围内变化上述最优基不变；（3）当 时，t1在什么范围内变化上述最优解不变，图示并说明其几何意义。,分析：（1）考察对单纯形表结构的掌握：单纯形表的每一列等于本表的 乘以初表的相应列、检验数公式（2）b变化时的分析（3）c变化时的分析,解：（1）由，解得。,由，解得。同理，解得 由，解得同理，解得,（2）由，解得。（3）由，解得。,几何意义：当 的变化幅度 时，最优目标直线在如图箭头所示范围摆动，这时最优解都不变（图1）。,图1,7综合应用 问题:某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决定进行一次大规模的广告行动。表4给出了公司准备做

31、广告的三种产品名称、估计每做一单位广告（一个广告标准批量）使每种产品的市场份额增加量、公司拟定的广告后每种产品市场份额增加量的最低目标和两种可选的广告方式的单价。,其中洗衣粉的市场份额出现负值是由于液体洗涤剂的份额增加会造成洗衣粉份额的减少。,现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量（分别记为x1和x2）。（1）请写出此问题的线性规划模型（约束依表4中产品的次序），并将模型化为标准型。（2）用（Min型）单纯形法求解此问题，得单纯形终表如表5。,表5,请填完表中空白；由表指出最优广告计划并求出相应的最低广告费用，此最优计划使每种产品的市场份额最低增量目标达成情况如

32、何？,（3）写出此问题的对偶问题模型，由表5求出对偶最优解Y*，并解释Y*的实际意义。,分析：（1）建立模型，标准型（min型）（2）填表，将解代入约束可得份额增量目标情况（3）对偶模型，对偶解的意义（min型的对偶解 一般含义是什么）,解：（1）,（2）即做电视广告4，印刷媒体3，最低广告费1000，前两种产品正好达到目标，第三种超额4%；,（3）,填表：,实际意义是有另一个承包商来承揽三种产品增加份额的业务，承揽的目标是总收益最大化，约束是以不超过公司自己做广告的成本，即承揽的最优单位收益。,8应用案例,除尘器生产计划 某机器公司可以生产三种不同型号小型的除尘器，一种是政府用，另一种是工业

33、用，还有一种是民用除尘器。但最后一种已经不生产了。政府用除尘器的单价是1500元，工业用除尘器的单价是1400元。为了完成各月订货，生产车间必须制定出一个生产计划以使费用最低。因为政府用和工业用除尘器都分别有两种型号：一种是使用优质的高,碳钢和一些铝；另一种是使用低碳钢和大量铝，而金属价格差别很大，所以制定最优生产计划并非易事。客户并不在意公司为他们生产的除尘器是属于两种型号中的哪一种，公司决定使用线性规划制定最优计划，问题的关键是满足客户的总订货要求，不超过公司的熟练工人与非熟练技术工人以及生产能力的限制，以使生产费用最小。铝的费用：107元/10kg；高碳钢：38元/10kg，低碳钢：29

34、元/10kg，表6给出生产三种除尘器所需的原材料及劳动力工时等。,表6 生产所需资源数据,公司下月的订货为：工业用除尘器300只，政府用除尘器500只，其金属费用为305820元。,由于开工不足，公司决定再次生产民用轻型除尘器，售价为800元/只，数用量不超过100只。技术工人可以加班，费用15元/小时。线性规划模型如表7，模型的变量有9个，前三个为三种金属的购买量，后五个是五种不同除尘器的生产数量；最后一个是熟练工加班小时数。约束也有9个，前三个表明购买的三种金属的数量至少应满足生产需求；后两个表明生产政府用和工业用除尘器的数量要满足订货；再后三个是熟练工、技术工和生产线生产能力的限制，最后

35、一个表明最多可以生产100个民用轻型除尘器。,表7 线性规划模型,问题1：下面各量哪些在目标函数中考虑了，哪些没有考虑？a)金属的费用 有_ 没有_；b)正常劳动成本 有_ 没有_；c)加班劳动成本 有_ 没有_；d)管理费用 有_ 没有_。问题2：为什么在目标函数中没有考虑工业用和政府用除尘器的收益，但却考虑了民用除尘器的收益？,使用Lindo软件对模型计算的结果如下：,案例分析,（固定）,OBJECTIVE FUNCTION VALUE1)263280.000VARIABLE VALUE REDUCED COST X1 240.000000.000000 X2 6600.000000.00

36、0000 X3 2200.000000.000000 X8 100.000000.000000 X9 200.000000.000000 X5.000000 574.400000 X6 100.000000.000000 X7 200.000000.000000 X4 500.000000.000000 ROW SLACK OR SURPLUS DUAL PRICES 2.000000 107.000000 3.000000 38.000000 4.000000 29.000000 5.000000 776.200300 6.000000 852.200300 7.000000 15.0000

37、00 8 1400.000000.000000 9.000000 36.400040 10.000000 296.799700RANGES IN WHICH THE BASIS S UNCHANGED,Lindo计算结果,铝高碳低碳轻型加班政二工一工二政一,铝高碳低碳政订工订技术熟练生产轻型,OBJ COEFFICIENT RANGESVARIABLE CURRENT COEF ALLOWABLE INCREASE ALLOWABLE DECREASE X1 107.000000 45.500050 54.962920 X2 38.000000 3.372724 3.033336 X3 29.

38、000000 3.309094 3.854542 X8 800.000000 296.799700 INFINITY X9 15.000000 36.400040 15.000000 X5.000000 INFINITY 574.400000 X6.000000 42.399960 36.400040 X7.000000 36.400040 42.399970 X4.000000 574.400000 INFINITYRIGHTHAND SIDE RANGES ROW CURRENT RHS ALLOWABLE INCREASE ALLOWABLE DECREASE 2.000000 240.

39、000000 INFINITY 3.000000 6600.000000 INFINITY 4.000000 2200.000000 INFINITY 5 500.000000 25.000000 12.500000 6 300.000000 28.571430 12.500000 7 6400.000000 200.000000 INFINITY 8 9600.000000 INFINITY 1400.000000 9 7000.000000 100.000000 200.000000 10 100.000000 28.571430 14.285720,铝高碳低碳轻型加班政二工一工二政一,铝

40、高碳低碳政订工订技术熟练生产轻型,问题3：民用轻型除尘器的数量为何，其耗用各种金属的数量是多少？在最优生产计划中，生产_ _台轻型除尘器，用高碳钢_公斤；用低碳钢_公斤；铝_公斤。问题4：技术工人加班费用是15元/小时，当这个费用变为多大时最优计划将改变？问题5：如果不允许加班，那么总费用将如何变化？总费用将：_增加_元。_减少_元。_不能确切得知。,100,400,0,20,问题6：若熟练工的生产能力增加1小时，将会产生什么影响？问题7：若工业用除尘器的订货增加一台，那么它的贡献是什么？问题8：为使民用轻型除尘器市场扩大25台，你愿意再支付多少？问题9：此问题的最优解和最优值各是什么？解释其

41、实际意义。问题10：政府二型在目标中的系数减少_时才可能被生产？,（无）,（减少成本852.2003）,（小于296.7997 25）,574.4,（如计算结果表）,9研究性专题 问题：考虑线性规划问题(P)（1）写出(P)的对偶模型(D)，并用图解法解(D)；（2）将(D)增加松弛变量后化为等式；,（3）由互补松弛定理，本题(P)与(D)的最优解应满足，对所有j，若还满足，则称解是严格互补的。请以本题说明：当(P)与(D)中有多重最优解时，则满足严格互补条件的解是多重最优解中的非顶点解。（提示：可由观察法得到，(P)的最优解为）,分析：互补松弛定理只告诉我们，并没有保证。本例将使我们对严格互

42、补性有一个直观的认识。解：（1）最优解为AB线段的点，其中，,（2）（3）与顶点解A的S：和B的S：点显然不满足严格互补，而与非顶点解 的S：满足。,关于严格互补性的进一步思考（1）如果是唯一解的情形，互补性如何？（2）任何线性规划的互补松弛关系，是否一定 存在严格互补解？（3）请进一步研究并查阅相关文献，获得答案。,第1.4节 线性整数规划,整数规划变量只能取整数的规划问题。当变量只能取0或1两个值，称0-1规划。整数规划分类：纯整数规划全部变量为整数。混合整数规划部分变量为整数。,例13 投资场所选址问题,计划在东、西、南三个区开设若干商业网点，拟在A1，A7 7个地点中选择。规定：东区在

43、A1，A2，A3中至多选2个，西区在A4，A5中至少选1个，南区在A6，A7中至少选1个。已知在Ai建点需投资bi，可获利ci，现共有资金为B。问应如何布局可使总利润最大？,分析：,东区在A1，A2，A3中至多选2个怎样表示？,课堂练习1:某钻井队要从S1S10共10个井位中确定五个钻井探油，如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件：（1）或选择S1和S7，或选择S8;,（2）选择了S3或S4就不能选择S5，反 过来也一样;（3）在S5，S6，S7，S8中最多只能选两个。问如何选择井位使总费用最小？,课堂练习1:某钻井队要从S1S10共10个井位中确定五个钻井探油，如果选

44、Si，估计钻探费用为ci元，并且井位选择上要满足下列条件：（1）或选择S1和S7，或选择S8（2）选择了S3或S4就不能选择S5，反过来也一样（3）在S5，S6，S7，S8中最多只能选两个问如何选择井位使总费用最小？,min z=,s.t.,或 1，i=1,10,例14.固定费用问题,最基本的带有固定费用的费用函数一般表示为：,若引入01变量,则带有固定费用的费用函数可表示为：,一般描述：,已知：生产某产品有m种方式，设第j 种生产方式的固定成本为kj，可变成本为cj。问题：应选择哪几种生产方式、分别生产多少产量可使总成本最低？,分析：这是一个混合0-1规划问题：,设第j 种生产方式的产量为x

45、j,于是该问题可表示为：,xj M yj,例15、生产三种型号的防寒服，其消耗资源及单件成本如表。此外，每种防寒服不管生产多少，都要支付一定的固定费用。,今要生产500件防寒服，确定总费用最低的生产方式。,Min Z=13x1+12x2+10 x3+120y1+150y2+180y3,x1+x2+x3=5001.5x1+1.7x2+1.8x315001.3x1+1.5x2+1.6x31000 4x1+4.5x2+5x335002.8x1+3.8x2+4.2x32800 xiMyi(i=1,2,3)；xi0;yi=0或1,例16.背包问题,问题描述,已知：一个背包最大容量为b公斤；有m件物品供选

46、择，每件物品重ai公斤，价值为ci（i=1,m）。,问题：携带哪些物品可使总价值最大？,一般模型,s.t.,1，物品i被选中 0，物品i没被选中,xi=,例：一个徒步旅行者要在背包中选择一些最有价值的物品携带。他最多能带115kg的物品，现有5件物品，分别重54、35、57、46、19kg，其价值依次为7、5、9、6、3。问携带哪些物品可使总价值最大？,解：,模型为：,s.t.,例17 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表所示。问两种货物各托运多少箱，可使获得利润为最大?,整数规划求解:,整数规划解能由单纯形法得到吗?,解：设x1，x2分别为甲、乙两种

47、货物的托运箱数(当然都是非负整数)，这就是一个(纯)整数线性规划问题，用数学模型可表示为：max z=20 x1+10 x2 5x1+4x224 2x1+5x213 x1，x20 x1，x2整数 该问题和线性规划问题的区别仅在于最后一个约束条件。现在我们暂不考虑这一条件，即解由构成的线性规划问题(以后我们称这样的问题为与原问题相应的线性规划问题(松弛问题),容易求得相应的线性规划问题的最优解为 x1=4.8，x2=0，max z=96,是不是可以把所得的非整数最优解经过“化整”就可得到合于条件的整数最优解呢?如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件(关于体积

48、的限制)，因而它不是可行解；如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0)，这当然满足各约束条件，因而是可行解，但不是最优解，因为当x1=4，x2=0,时z=80；而当x1=4，x2=1(这也是可行解)时，z=90。,考虑纯整数问题：,整数问题的松弛问题：,线性整数规划求解方法:分枝定界法,1、先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：.若(LP)没有可行解，则(IP)也没有可行解，停止计算。.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。.若(LP)有最优解，但不符合(IP)的整数条件，转

49、入下一步。为讨论方便，设(LP)的最优解为：,分枝定界法步骤,2、定界：记(IP)的目标函数最优值为Z*,以Z(0)作为Z*的上界，记为 Z(0)。再用观察法找的一个整数可行解 X，并以其相应的目标函数值 Z作为Z*的下界，记为Z Z，也可以令Z，则有:Z Z*,3、分枝：在(LP)的最优解 X(0)中，任选一个不符合整数条件的变量，例如xr=br（不为整数），以br 表示不超过br 的最大整数。构造两个约束条件 xr br 和xr br 1,将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题(LP1)和(LP2)。4、修改上、下界：按照以下两

50、点规则进行。.在各分枝问题中，找出目标函数值最大者作为新的上界；.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。5、比较与剪枝：各分枝的目标函数值中，若有小于 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。,如此反复进行，直到得到ZZ*为止，即得最优解 X*。,例18：用分枝定界法求解整数规划问题,记为（IP）,解：首先去掉整数约束，变成一般线性规划问题,记为（LP）,用图解法求（LP）的最优解，如图所示。,x1,x2,3,3,(18/11,40/11),对于x118/111.64，取值x1 1，x1 2先将（LP）划分为（LP1）和（LP2）,取x1 1,x