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