《aa动画 管理系统工程教学课件第六章：线性规划》由会员分享，可在线阅读，更多相关《aa动画 管理系统工程教学课件第六章：线性规划（74页珍藏版）》请在金锄头文库上搜索。
1、2019/4/22,【第六章：线性规划*48*】 有动画,1,管理系统工程,第六章 管理系统决策定量分析模型：线性规划 第一节 线性规划模型、实例及求解 第二节 线性规划模型求解的一般方法：单纯形法 第三节 线性规划问题的对偶问题，对偶单纯形法 第四节 线性规划问题的灵敏性分析 第五节 多目标规划法中的目的规划法简介,（六）,2019/4/22,【第六章：线性规划*48*】 有动画,2,第一节 线性规划模型、实例及求解 一、线性规划予以解决的实际问题 1、资源给定，如何对给定资源予以充分地、合理地运用，使之完成的任务尽可能地多。 2、任务给定，如何以尽可能少的资源消耗来完成给定的任务。 可见，
2、上述两类问题都是寻求利润最大。第一类，是以最大收益扣除定 量成本；第二类，是以定量收益扣除最小成本。,2019/4/22,【第六章：线性规划*48*】 有动画,3,二、线性规划的定义： 当收益和消耗均与计划指标成正比时，一个规划问题所列出的数学表达 式都是关于计划指标的线性关系式，称此类型规划问题为线性规划问题。 线性规划问题是：在一组线性约束条件下，求一组非负变量得值，使一 个线性目标函数达到最大或者是最小。,2019/4/22,【第六章：线性规划*48*】 有动画,4,三、线性规划的数学模型 例1： 某厂拟定利用三种资源：铸件、锻件、加工人时生产A、B两种型号的设 备。已知资料如下表所示：
3、 求总销售额最大的生产计划方案。,2019/4/22,【第六章：线性规划*48*】 有动画,5,例1的模型（LP） 根据以上资料，建立（LP）模型如下： （设A设备生产x1台；B设备生产x2台）,2019/4/22,【第六章：线性规划*48*】 有动画,6,（LP）模型的形式： 1、矩阵形式 记： C =（c1、c2、c3、cn） X =（x1、x2、x3、xn）T A =（aij）mn b =（b1、b2、b3、bm）T 则（LP）模型的矩阵形式为：,2019/4/22,【第六章：线性规划*48*】 有动画,7,2、极大化典型形式（实际问题一） 3、极小化典型形式（实际问题二）,2019/4
4、/22,【第六章：线性规划*48*】 有动画,8,4、标准型形式（模型求解的基础）,2019/4/22,【第六章：线性规划*48*】 有动画,9,（LP）问题的基本术语 1、变量 决策变量：对需要优化的经济量所设置的变量称之。 附加变量：为求解（LP）模型所引入的变量称之。 （1）松弛变量：为处理约束条件所引入，又分为不 足 变量和剩余变量 （2）人工变量：为人为地制造一个基而引入的变量,2019/4/22,【第六章：线性规划*48*】 有动画,10,2、目标函数；约束条件 3、（LP）模型的解的概念 可行解：称满足约束条件的解为可行解。 最优解：能使目标函数得以满足的可行解称之为最优解。,2
5、019/4/22,【第六章：线性规划*48*】 有动画,11,（LP）模型图解法,x*1=20（台）、x*2=20（台） Z*=200（万元）,2019/4/22,【第六章：线性规划*48*】 有动画,12,图形放大,2019/4/22,【第六章：线性规划*48*】 有动画,13,（LP）模型图解法之步骤,2019/4/22,【第六章：线性规划*48*】 有动画,14,图解法之结论： （1）（LP）模型的可行解域为一个凸多边形或凸多面体，它们的极 点为有限多个。 （2）（LP）模型的最优解如果存在，一定可以在凸集合的极点上得 到。 （ 3）若（LP）模型的最优解在一个极点上得到，则该模型最优解
6、唯 一；若在两个极点上同时取得，则该模型有多重最优解。 （4）若作图以后；满足各约束条件的共同部分不存在，则该模型无可 行解。 （5）若找不到离目标函数线距离最远的可行解点，则该模型无有限最 优解。（开区域时发生）,2019/4/22,【第六章：线性规划*48*】 有动画,15,1、线性规划模型的一般形式,2019/4/22,【第六章：线性规划*48*】 有动画,16,（LP）模型间相互转换的规则 1、 2、 3、 4、 5、,2019/4/22,【第六章：线性规划*48*】 有动画,17,第二节 （LP）模型求解的单纯形法 一、单纯形法的基本思想： 单纯形法的基本思想是从有限个基本可行解中选
7、择几个予以比较，从 而得到最优解。 二、单纯形法的求解步骤： 1、以最简单的方法确定第一个基本可行解 2、判断该解是否最优，若是最优则最优解得到，若不是最优解则进行下一步 3、在保证目标函数至少不减（目标函数求最大值模型）的前提下，转换到另 一个基本可行解上 4、重复判断步骤，直至寻找到最优解,2019/4/22,【第六章：线性规划*48*】 有动画,18,三、 （LP）模型解的概念的扩充 基矩阵、非基矩阵、基向量、非基向量 （口述） 基变量、非基变量 基向量对应的变量称之为基变量，非基向量对应的变量称之为非基变量。 基本解 当取定一个基以后，令全部的非基变量等于零，从方程组中解出基变量得值，
8、由它们构成的解： X=（x1、x2、xj、xn)T称之为一个基本解。 显然，基本解的个数为有限多个，最多为 个。 基本可行解 满足非负要求的基本解称之为基本可行解。,2019/4/22,【第六章：线性规划*48*】 有动画,19,四、单纯形法求解步骤及单纯形表结构特征 求解步骤： 1、将模型变为标准型，列初表 2、判断解是否最优（判断准则：全部的j0则达优），若不是最优则 进行下一步 3、进行解的转换 （1）确定基准列第k列（确定进基变量） k=maxj （j0） （2）确定基准行第l行（确定退基变量） l=mini i=bi/aik （aik0） （3）确定主元素：基准行与基准列交叉处的元素
9、 （4）进行矩阵的初等行变换，变换的目标是： “ 基准列的主元素变为1；其余的元素变为0” 4、重复判断步骤，直至寻求到最优解,2019/4/22,【第六章：线性规划*48*】 有动画,20,一、利用铸件、锻件、加工人时生产AB设备之例求解单纯形表,2019/4/22,【第六章：线性规划*48*】 有动画,21,例1求解的结论,共搜索了三个基本可行解 X（1）=（0、0、270、100、120） X（2）=（30、0、180 、40、0） X（3）=（20、20、30、0、0） 最优解为： X*= （20、20、30、0、0） 即：A、B设备各自生产20台 最大销售收入为： Z*=200（万元
10、）,2019/4/22,【第六章：线性规划*48*】 有动画,22,单纯形表的结构特征 1、所有单纯形表共有特征 （1）基变量的列系数均为单位向量 （2）基变量的检验数均为零 （3）最右边的常量均大于等于零 2、最终单纯形表的特征（要会识别最终表） （1）基变量的列系数均为单位向量 （2）基变量的检验数均为零 （3）最右边的常量均大于等于零 （4）检验数行全部小于等于零,2019/4/22,【第六章：线性规划*48*】 有动画,23,学生练习题1,用单纯形法求解,2019/4/22,【第六章：线性规划*48*】 有动画,24,2019/4/22,【第六章：线性规划*48*】 有动画,25,学生
11、练习题2,用单纯形法求解,2019/4/22,【第六章：线性规划*48*】 有动画,26,2019/4/22,【第六章：线性规划*48*】 有动画,27,五、用矩阵形式表出的单纯形表 公式（1）某非基变量检验数计算公式： j=Cj-CBB-1Pj （2）某非基变量列系数计算公式： Pj*=B-1Pj,2019/4/22,【第六章：线性规划*48*】 有动画,28,一、利用铸件、锻件、加工人时生产AB设备之例求解单纯形表,2019/4/22,【第六章：线性规划*48*】 有动画,29,六、利用Excel Solver对线性规划模型求解 步骤： 1、在电子表格中确定目标单元格、活动单元格，输入所有
12、参数 （aij、bi、cj） 2、利用数据组相乘公式（常用函数里SUMPRODUCT）确定好约束条件的左边对应的单元格 3、打开工具（T）栏里的规划求解 （1）给定目标单元格、活动单元格，求最大 （2）添加约束条件 （3）选项栏里：线性、非负，确定 （4）求解得下表,链接,2019/4/22,【第六章：线性规划*48*】 有动画,30,利用Excel Solver对（LP）模型例1求解,链接,2019/4/22,【第六章：线性规划*48*】 有动画,31,物质配送问题之例,例3： 两个工厂生产同一种新产品，配送公司将该产品送到两个仓库。运送情况如 下： 1、工厂1的产品通过铁路只能送到仓库1，
13、产品的数量不限，单位运输成本为700元/单位。 2、工厂2的产品通过铁路只能送到仓库2，产品的数量不限，单位运输成本为900元/单位。 3、卡车可将多达50个单位的产品由工厂送到配送中心，再从配送中心以最多50个单位的载运量运到各仓库，其单位运费如图所示。 4、各厂的生产量、各仓库的所需量如图所示。 求最低运输成本对应的运输方案。,2019/4/22,【第六章：线性规划*48*】 有动画,32,例3的配送网络示意图,2019/4/22,【第六章：线性规划*48*】 有动画,33,例3的变量设置,设： x1工厂1至仓库1的运输量 x2工厂2至仓库2的运输量 x3工厂1至配送中心的运输量 x4工厂
14、2至配送中心的运输量 x5配送中心至仓库1的运输量 x6配送中心至仓库2的运输量 根据条件分析建立模型如下：,2019/4/22,【第六章：线性规划*48*】 有动画,34,例3的配送网络示意图,2019/4/22,【第六章：线性规划*48*】 有动画,35,例3的（LP）模型,2019/4/22,【第六章：线性规划*48*】 有动画,36,例3Excel Solver求解,2019/4/22,【第六章：线性规划*48*】 有动画,37,例3求解结果：运输方案,x1 工厂1仓库1：x*1=30 x2 工厂2仓库2：x*2=40 x3 工厂1配送中心：x*3=50 x4 工厂2配送中心：x*4=
15、30 x5 配送中心仓库1：x*5=30 x6 配送中心仓库2：x*6=50 Z 总运费 最小总运费为： Zmin=110000（费用单位）,2019/4/22,【第六章：线性规划*48*】 有动画,38,第三节 线性规划问题的对偶问题，对偶单纯形法 一、线性规划问题的对偶问题的提出 1、原问题（LP） 例1中的铸件、锻件、加工人时用于生产A、B两种设备，出让 设备以后获得销售收入，将这样考虑的问题称之为原问题。 2、对偶问题（LD） 将例1中的铸件、锻件、加工人时制定相应的价格y1、y2、y3， 直接出让资源获得收入，将这样考虑的问题称之为原问题的对偶问 题。,2019/4/22,【第六章：线性规划*48*】 有动画,39,二、对偶模型及对偶模型的建立 该模型称之为原模型（LP）的对偶模型，记为：（LD） （y1 、y2 、y3的设置及含义解释一下）,201
