A动画管理系统工程教学课件第六章线性规划.ppt

1、管理系统工程管理系统工程第六章第六章 管理系统决策定量分析模型：线性规划管理系统决策定量分析模型：线性规划 第一节第一节 线性规划模型、实例及求解线性规划模型、实例及求解 第二节第二节 线性规划模型求解的一般方法：单纯形法线性规划模型求解的一般方法：单纯形法 第三节第三节 线性规划问题的对偶问题，对偶单纯形法线性规划问题的对偶问题，对偶单纯形法 第四节第四节 线性规划问题的灵敏性分析线性规划问题的灵敏性分析 第五节第五节 多目标规划法中的目的规划法简介多目标规划法中的目的规划法简介（六）（六）10/23/20221第一节第一节 线性规划模型、实例及求解线性规划模型、实例及求解一、线性规划予以解

2、决的实际问题一、线性规划予以解决的实际问题 1、资源给定，如何对给定资源予以充分地、合理地运用，使之完成的、资源给定，如何对给定资源予以充分地、合理地运用，使之完成的任务尽可能地多。任务尽可能地多。2、任务给定，如何以尽可能少的资源消耗来完成给定的任务。、任务给定，如何以尽可能少的资源消耗来完成给定的任务。可见，上述两类问题都是寻求利润最大。第一类，是以最大收益扣除定可见，上述两类问题都是寻求利润最大。第一类，是以最大收益扣除定 量成本；第二类，是以定量收益扣除最小成本。量成本；第二类，是以定量收益扣除最小成本。10/23/20222二、线性规划的定义：二、线性规划的定义：当收益和消耗均与计划

3、指标成正比时，一个规划问题所列出的数学表达当收益和消耗均与计划指标成正比时，一个规划问题所列出的数学表达 式都是关于计划指标的线性关系式，称此类型规划问题为线性规划问题。式都是关于计划指标的线性关系式，称此类型规划问题为线性规划问题。线性规划问题是：在一组线性约束条件下，求一组非负变量得值，使一线性规划问题是：在一组线性约束条件下，求一组非负变量得值，使一 个线性目标函数达到最大或者是最小。个线性目标函数达到最大或者是最小。10/23/20223三、线性规划的数学模型三、线性规划的数学模型 例例1：某厂拟定利用三种资源：铸件、锻件、加工人时生产某厂拟定利用三种资源：铸件、锻件、加工人时生产A、

4、B两种型号的设两种型号的设 备。已知资料如下表所示：备。已知资料如下表所示：求总销售额最大的生产计划方案。求总销售额最大的生产计划方案。4万元万元/台台6万元万元/台台设备售价设备售价120（百人时）（百人时）24加工人时加工人时100（吨）（吨）32锻件锻件270（吨）（吨）93铸件铸件资源量资源量BA10/23/20224 例例1的模型（的模型（LP）根据以上资料，建立（根据以上资料，建立（LP）模型如下：）模型如下：（设（设A设备生产设备生产x1台；台；B设备生产设备生产x2台）台）2146maxxxZ012024100322709321212121xxxxxxxx、1目标函数目标函数2

5、约束条件约束条件该模型的解为生产计划该模型的解为生产计划10/23/20225 （LP）模型的形式：）模型的形式：1、矩阵形式矩阵形式 记：记：C=（c1、c2、c3、cn）X=（x1、x2、x3、xn）T A=（aij）mn b=（b1、b2、b3、bm）T 则（则（LP）模型的矩阵形式为：）模型的矩阵形式为：价值系数行向量价值系数行向量决策变量列向量决策变量列向量技术系数矩阵技术系数矩阵资源限定列向量资源限定列向量CXZ max0XbAX）（10/23/202262、极大化典型形式（实际问题一）极大化典型形式（实际问题一）3、极小化典型形式（实际问题二）极小化典型形式（实际问题二）CXZ

6、max0XbAXCXZmin0XbAX10/23/20227 4、标准型形式（模型求解的基础）标准型形式（模型求解的基础）CXZ max0XbAX10/23/20228（LP）问题的基本术语）问题的基本术语 1、变量、变量 决策变量：对需要优化的经济量所设置的变量称之。决策变量：对需要优化的经济量所设置的变量称之。附加变量：为求解（附加变量：为求解（LP）模型所引入的变量称之。）模型所引入的变量称之。（1）松弛变量：为处理约束条件所引入，又分为不）松弛变量：为处理约束条件所引入，又分为不 足足 变量和剩余变量变量和剩余变量 （2）人工变量：为人为地制造一个基而引入的变量）人工变量：为人为地制造

7、一个基而引入的变量10/23/202292、目标函数；约束条件、目标函数；约束条件 3、（、（LP）模型的解的概念）模型的解的概念 可行解：称满足约束条件的解为可行解。可行解：称满足约束条件的解为可行解。最优解：能使目标函数得以满足的可行解称之为最优解。最优解：能使目标函数得以满足的可行解称之为最优解。10/23/202210（LP）模型图解法）模型图解法2146maxxxZ012024100322709321212121xxxxxxxx、（）（）（）x*1=20（台）、（台）、x*2=20（台）（台）Z*=200（万元）（万元）10/23/202211图形放大图形放大10/23/202212

8、（LP）模型图解法之步骤）模型图解法之步骤在负法线方向找在法线方向找，注：离最远的可行解点、找出离目标函数线距线、作目标函数线及其法、确定可行解域、作各等式对应的直线minZmaxZ432110/23/202213 图解法之结论：图解法之结论：（1）（）（LP）模型的可行解域为一个凸多边形或凸多面体，它们的极）模型的可行解域为一个凸多边形或凸多面体，它们的极 点为有限多个。点为有限多个。（2）（）（LP）模型的最优解如果存在，一定可以在凸集合的极点上得）模型的最优解如果存在，一定可以在凸集合的极点上得 到。到。（3）若（）若（LP）模型的最优解在一个极点上得到，则该模型最优解唯）模型的最优解在

9、一个极点上得到，则该模型最优解唯 一；若在两个极点上同时取得，则该模型有多重最优解。一；若在两个极点上同时取得，则该模型有多重最优解。（4）若作图以后；满足各约束条件的共同部分不存在，则该模型无可）若作图以后；满足各约束条件的共同部分不存在，则该模型无可 行解。行解。（5）若找不到离目标函数线距离最远的可行解点，则该模型无有限最）若找不到离目标函数线距离最远的可行解点，则该模型无有限最 优解。（开区域时发生）优解。（开区域时发生）10/23/2022141、线性规划模型的一般形式、线性规划模型的一般形式nnjjxcxcxcxcZ2211min)max(0),(),(),(),(.2122112

10、211222222121111212111njmnmnjmjmmininjijiinnjjnnjjxxxxbxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxats、10/23/202215（LP）模型间相互转换的规则）模型间相互转换的规则1、2、3、4、5、)(maxmin22112211ZZxcxcxcZxcxcxcZnnnnininiiininiibxaxaxabxaxaxa22112211为不足变量lilniniiininiixbxxaxaxabxaxaxa 22112211为剩余变量lilniniiininiixbxxaxaxabxaxaxa 221122110 j

11、jjjjjxxxxxx，则为自由变量，设10/23/202216第二节第二节 （LP）模型求解的单纯形法）模型求解的单纯形法一、单纯形法的基本思想：一、单纯形法的基本思想：单纯形法的基本思想是从有限个基本可行解中选择几个予以比较，从单纯形法的基本思想是从有限个基本可行解中选择几个予以比较，从 而得到最优解。而得到最优解。二、单纯形法的求解步骤：二、单纯形法的求解步骤：1、以最简单的方法确定第一个基本可行解、以最简单的方法确定第一个基本可行解 2、判断该解是否最优，若是最优则最优解得到，若不是最优解则进行下一、判断该解是否最优，若是最优则最优解得到，若不是最优解则进行下一步步 3、在保证目标函数

12、至少不减（目标函数求最大值模型）的前提下，转换到、在保证目标函数至少不减（目标函数求最大值模型）的前提下，转换到另另 一个基本可行解上一个基本可行解上 4、重复判断步骤，直至寻找到最优解、重复判断步骤，直至寻找到最优解10/23/202217三、三、（LP）模型解的概念的扩充）模型解的概念的扩充 基矩阵、非基矩阵、基向量、非基向量基矩阵、非基矩阵、基向量、非基向量（口述）（口述）基变量、非基变量基变量、非基变量 基向量对应的变量称之为基变量，非基向量对应的变量称之为非基变量。基向量对应的变量称之为基变量，非基向量对应的变量称之为非基变量。基本解基本解 当取定一个基以后，令全部的非基变量等于零，

13、从方程组中解出基变量得值，当取定一个基以后，令全部的非基变量等于零，从方程组中解出基变量得值，由它们构成的解：由它们构成的解：X=（x1、x2、xj、xn)T称之为一个基本解。称之为一个基本解。显然，基本解的个数为有限多个，最多为显然，基本解的个数为有限多个，最多为 个。个。基本可行解基本可行解 满足非负要求的基本解称之为基本可行解。满足非负要求的基本解称之为基本可行解。mnC10/23/202218四、单纯形法求解步骤及单纯形表结构特征四、单纯形法求解步骤及单纯形表结构特征 求解步骤：求解步骤：1、将模型变为标准型，列初表、将模型变为标准型，列初表 2、判断解是否最优（判断准则：全部的、判断

14、解是否最优（判断准则：全部的j0则达优），若不是最优则则达优），若不是最优则 进行下一步进行下一步 3、进行解的转换、进行解的转换 （1）确定基准列第）确定基准列第k列（确定进基变量）列（确定进基变量）k=maxj （j0）（2）确定基准行第）确定基准行第l行（确定退基变量）行（确定退基变量）l=mini i=bi/aik （aik0）（3）确定主元素：基准行与基准列交叉处的元素）确定主元素：基准行与基准列交叉处的元素 （4）进行矩阵的初等行变换，变换的目标是：）进行矩阵的初等行变换，变换的目标是：“基准列的主元素变为基准列的主元素变为1；其余的元素变为；其余的元素变为0”4、重复判断步骤，直

15、至寻求到最优解、重复判断步骤，直至寻求到最优解10/23/202219一、利用铸件、锻件、加工人时生产一、利用铸件、锻件、加工人时生产AB设备之例求解单纯形表设备之例求解单纯形表10/23/202220例例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/23/202221单纯形表的结构特征

16、单纯形表的结构特征 1、所有单纯形表共有特征、所有单纯形表共有特征 （1）基变量的列系数均为单位向量）基变量的列系数均为单位向量 （2）基变量的检验数均为零）基变量的检验数均为零 （3）最右边的常量均大于等于零）最右边的常量均大于等于零 2、最终单纯形表的特征（要会识别最终表）、最终单纯形表的特征（要会识别最终表）（1）基变量的列系数均为单位向量）基变量的列系数均为单位向量 （2）基变量的检验数均为零）基变量的检验数均为零 （3）最右边的常量均大于等于零）最右边的常量均大于等于零 （4）检验数行全部小于等于零）检验数行全部小于等于零10/23/202222学生练习题学生练习题1 用单纯形法求解

17、用单纯形法求解01823122453max21212121xxxxxxxxZ、12345132412515max3500042123218_0Zxxxxxxxxxxxxx10/23/20222310/23/202224学生练习题学生练习题2用单纯形法求解用单纯形法求解060422425.013146max321321321321xxxxxxxxxxxxZ、10/23/20222510/23/202226五、用矩阵形式表出的单纯形表五、用矩阵形式表出的单纯形表 公式公式（1）某非基变量检验数计算公式：）某非基变量检验数计算公式：j=Cj-CBB-1Pj （2）某非基变量列系数计算公式：）某非基变

18、量列系数计算公式：Pj*=B-1Pj10/23/202227一、利用铸件、锻件、加工人时生产一、利用铸件、锻件、加工人时生产AB设备之例求解单纯形表设备之例求解单纯形表10/23/202228六、利用六、利用Excel Solver对线性规划模型求解对线性规划模型求解 步骤：步骤：1、在电子表格中确定目标单元格、活动单元格，输入所有参数、在电子表格中确定目标单元格、活动单元格，输入所有参数 （aij、bi、cj）2、利用数据组相乘公式（常用函数里、利用数据组相乘公式（常用函数里SUMPRODUCT）确定好约束条）确定好约束条件的左边对应的单元格件的左边对应的单元格 3、打开工具（、打开工具（T

19、）栏里的规划求解）栏里的规划求解 （1）给定目标单元格、活动单元格，求最大）给定目标单元格、活动单元格，求最大 （2）添加约束条件）添加约束条件 （3）选项栏里：线性、非负，确定）选项栏里：线性、非负，确定 （4）求解得下表）求解得下表链接10/23/202229利用利用Excel Solver对（对（LP）模型例）模型例1求解求解链接10/23/202230物质配送问题之例物质配送问题之例例例3：两个工厂生产同一种新产品，配送公司将该产品送到两个仓库。运送情况如两个工厂生产同一种新产品，配送公司将该产品送到两个仓库。运送情况如 下：下：1、工厂、工厂1的产品通过铁路只能送到仓库的产品通过铁路

20、只能送到仓库1，产品的数量不限，单位运输，产品的数量不限，单位运输成本为成本为700元元/单位。单位。2、工厂、工厂2的产品通过铁路只能送到仓库的产品通过铁路只能送到仓库2，产品的数量不限，单位运输，产品的数量不限，单位运输成本为成本为900元元/单位。单位。3、卡车可将多达、卡车可将多达50个单位的产品由工厂送到配送中心，再从配送中心个单位的产品由工厂送到配送中心，再从配送中心以最多以最多50个单位的载运量运到各仓库，其单位运费如图所示。个单位的载运量运到各仓库，其单位运费如图所示。4、各厂的生产量、各仓库的所需量如图所示。、各厂的生产量、各仓库的所需量如图所示。求最低运输成本对应的运输方案

21、。求最低运输成本对应的运输方案。10/23/202231例例3的配送网络示意图的配送网络示意图配送中心配送中心仓库仓库2工厂工厂2仓库仓库1工厂工厂1生产生产70单位单位需要需要90单位单位生产生产80单位单位需要需要60单位单位700/单位单位900/单位单位图三：配送公司配送网络图三：配送公司配送网络300/单位单位200/单位单位400/单位单位400/单位单位最多最多50单位单位最多最多50单位单位最多最多50单位单位最多最多50单位单位10/23/202232例例3的变量设置的变量设置 设：设：x1工厂工厂1至仓库至仓库1的运输量的运输量 x2工厂工厂2至仓库至仓库2的运输量的运输量

22、 x3工厂工厂1至配送中心的运输量至配送中心的运输量 x4工厂工厂2至配送中心的运输量至配送中心的运输量 x5配送中心至仓库配送中心至仓库1的运输量的运输量 x6配送中心至仓库配送中心至仓库2的运输量的运输量 根据条件分析建立模型如下：根据条件分析建立模型如下：10/23/202233例例3的配送网络示意图的配送网络示意图配送中心配送中心仓库仓库2工厂工厂2仓库仓库1工厂工厂1生产生产70单位单位需要需要90单位单位生产生产80单位单位需要需要60单位单位700/单位单位900/单位单位图三：配送公司配送网络图三：配送公司配送网络300/单位单位200/单位单位400/单位单位400/单位单位

23、最多最多50单位单位最多最多50单位单位最多最多50单位单位最多最多50单位单位x1x3x4x2x5x610/23/202234例例3的（的（LP）模型）模型05009060708065432165436543262151242131xxxxxxxxxxxxxxxxxxxxxx、（配送中心）（仓库）（仓库）（工厂）（工厂654321400200400300900700minxxxxxxZ10/23/202235例例3Excel Solver求解求解10/23/202236例例3求解结果：运输方案求解结果：运输方案 x1 工厂工厂1仓库仓库1：x*1=30 x2 工厂工厂2仓库仓库2：x*2=4

24、0 x3 工厂工厂1配送中心：配送中心：x*3=50 x4 工厂工厂2配送中心：配送中心：x*4=30 x5 配送中心配送中心仓库仓库1：x*5=30 x6 配送中心配送中心仓库仓库2：x*6=50 Z 总运费总运费 最小总运费为：最小总运费为：Zmin=110000（费用单位）（费用单位）10/23/202237第三节第三节 线性规划问题的对偶问题，对偶单纯形法线性规划问题的对偶问题，对偶单纯形法 一、线性规划问题的对偶问题的提出一、线性规划问题的对偶问题的提出 1、原问题、原问题（LP）例例1中的铸件、锻件、加工人时用于生产中的铸件、锻件、加工人时用于生产A、B两种设备，出让两种设备，出让

25、 设备以后获得销售收入，将这样考虑的问题称之为原问题。设备以后获得销售收入，将这样考虑的问题称之为原问题。2、对偶问题、对偶问题（LD）将例将例1中的铸件、锻件、加工人时制定相应的价格中的铸件、锻件、加工人时制定相应的价格y1、y2、y3，直接出让资源获得收入，将这样考虑的问题称之为原问题的对偶问直接出让资源获得收入，将这样考虑的问题称之为原问题的对偶问 题。题。10/23/202238二、对偶模型及对偶模型的建立二、对偶模型及对偶模型的建立 该模型称之为原模型（该模型称之为原模型（LP）的对偶模型，记为：（）的对偶模型，记为：（LD）（y1、y2、y3的设置及含义解释一下）的设置及含义解释一

26、下）321120100270minyyyW042396423321321321yyyyyyyyy、10/23/202239三、原模型（三、原模型（LP）与其对偶模型（）与其对偶模型（LD）模型间的关系）模型间的关系 1、原模型为极大化典型形式，则其对偶模型为极小化典型形式：、原模型为极大化典型形式，则其对偶模型为极小化典型形式：2、（、（LP）与（）与（LD）的系数矩阵互为转置）的系数矩阵互为转置 3、（、（LP）为）为m个约束条件，个约束条件，（LD）有）有m个决策变量个决策变量 4、（、（LP）为）为n个决策变量个决策变量,（LD）有）有n个约束条件个约束条件 5、一个模型的变量非负，则另

27、一模型的约束条件为不等式、一个模型的变量非负，则另一模型的约束条件为不等式 6、一个模型的变量为自由变量，则另一模型的约束条件为等式、一个模型的变量为自由变量，则另一模型的约束条件为等式0 max )(XbAXCXZLP：0 min )(YCYAYbWLD：10/23/202240两个模型对比两个模型对比321120100270minyyyW042396423321321321yyyyyyyyy、2146maxxxZ 0 12024 10032y 2709321321221121xxyxxyxxxx、原模型原模型对偶模型对偶模型10/23/202241 四、对偶问题的性质四、对偶问题的性质 1

28、、对称性：（、对称性：（LP）与（）与（LD）互为对偶）互为对偶 2、弱对偶定理：若、弱对偶定理：若X(0)，Y(0)分别是原问题和其对偶问题的分别是原问题和其对偶问题的任一任一可行解，可行解，则有：则有：CX(0)Y(0)b 该性质说明：两个模型的目标函数值互为界。b C (4)(3)(4)CA (3)bA (2)(1)(2)CA (1)bA (LD)LP)0 0 minW(LD)maxZ(LP)0()0()0()0()0()0()0()0()0()0()0()0()0()0(YXXXYYXYXYYXYXYCYAXbAXYbCX两式得：、比较，得：式两边右乘，式两边左乘，的可行解，分别是（，

29、为为证：设10/23/202242 3、设、设 X*、Y*分别为（分别为（LP）与（）与（LD）的某一可）的某一可 行行 解，解，当当CX*=Y*b时，则时，则 X*、Y*分别为（分别为（LP）与（）与（LD）的最优解。）的最优解。4、检验数与解之间的对应关系：、检验数与解之间的对应关系：（1）原模型单纯形表上检验数的相反数对应着其对偶模型的一个基本）原模型单纯形表上检验数的相反数对应着其对偶模型的一个基本 解。解。（2）原模型最终单纯形表上检验数的相反数对应着其对偶模型的最优）原模型最终单纯形表上检验数的相反数对应着其对偶模型的最优 解。解。10/23/202243具体的对应规则：具体的对应

30、规则：（以最终表为例，其余表规则相同）以最终表为例，其余表规则相同）（a）原模型松弛变量检验数的相反数对应着其对偶模型的决策变量的值；）原模型松弛变量检验数的相反数对应着其对偶模型的决策变量的值；（b）原模型决策变量检验数的相反数对应着其对偶模型的松弛变量的值。）原模型决策变量检验数的相反数对应着其对偶模型的松弛变量的值。由例由例1的最终表可得：的最终表可得：Y*=（0 1/2 5/4 0 0）W*=2700+1001/2+1205/4=200（万元）（万元）最终单纯型表最终单纯型表64000 x1x2x3x4x5bi0 x1001-15/49/8304x20101/2-1/4206x3100

31、-1/43/820zj6401/25/4j000-1/2-5/410/23/20224410/23/202245五、对偶决策变量五、对偶决策变量y*i 的经济含义的经济含义 1、在给定资源最优配置时，、在给定资源最优配置时，y*i为单位第为单位第i种资源的增加给目标函数所带来种资源的增加给目标函数所带来的贡献。（边际贡献）的贡献。（边际贡献）2、y*i称之为在给定资源最优配置时第称之为在给定资源最优配置时第i种资源的影子价格，影子价格是在种资源的影子价格，影子价格是在给定资源最优配置时对第给定资源最优配置时对第i种资源的一种估价。种资源的一种估价。3、y*i可理解为是可以利用的现行市场价格（边

32、际成本）的最高限度。可理解为是可以利用的现行市场价格（边际成本）的最高限度。例如：例如：y*2=1/2，则现行市场价格小于，则现行市场价格小于1/2时，对锻件可以适当予以增时，对锻件可以适当予以增 加；若现行市场价格大于加；若现行市场价格大于1/2时，对锻件不能予以增加。时，对锻件不能予以增加。4、y*i=0的资源称之为富裕资源；的资源称之为富裕资源；y*i0的资源称之为紧缺资源。的资源称之为紧缺资源。5、需注意的问题（口述）、需注意的问题（口述）10/23/202246 五、对偶单纯形法五、对偶单纯形法 单纯形法：保持原问题的解（B-1b）为可行解，让其对偶问题的解 （CBB-1A-C）由非

33、可行解逐步变化到可行解 对偶单纯形法：保持对偶问题的解为可行解（CBB-1A-C0），让原问题 的解（B-1b）由非可行解逐步变化到可行解 CBB-1A-C=（0，CBB-1N-CN，CBB-1）为全部的检验数，即对偶问题的解XBXNXLB-1bIB-1NB-1检验数0CBB-1N-CNCBB-110/23/202247对偶单纯形法的步骤（参看例对偶单纯形法的步骤（参看例14）第一步第一步：列初始单纯形表 第二步第二步：确定基准行（找出(B-1b)r=min(B-1b)i|(B-1b)i0，即bi列中负值中的 最小者，则第r行为基准行，xr为退基变量。若bi列中没有负值，则已得最优解）第三步第

34、三步：确定基准列，先计算：则第s列为基准列，xs为进基变量 若基准行没有负值，则该问题无可行解 第四步第四步：以基准行、基准列交叉处的元素为主元素，进行初等行变换，得新的单 纯形表后返回第二步。rssarjjsaarj0min10/23/202248例14 用对偶单纯形法求解下述线性规划模型 解：将模型化为标准型)4321(03422242 1216812min4213214321，iyyyyyyyyyyyZi12345612351246max128161200242 22430 (12 3 4 5 6)iZyyyyyyyyyyyyyyyi ，Y*=（0，3/2，1/8，0）Z*=83/2+1

35、61/8=14 Z*=Z 用对偶单纯形法求解的最优解：10/23/202249例例14对偶单纯行法求解表对偶单纯行法求解表10/23/202250第四节第四节 线性规划问题灵敏性分析线性规划问题灵敏性分析 一、线性规划问题灵敏性分析的内容一、线性规划问题灵敏性分析的内容 1、参数、参数bi、cj发生改变问题的分析发生改变问题的分析 2、新增加一个约束条件问题的分析、新增加一个约束条件问题的分析 3、新增加一个决策变量问题的分析、新增加一个决策变量问题的分析 二、参数二、参数bi发生改变问题的分析发生改变问题的分析 1、bi参数发生改变的实际原因参数发生改变的实际原因 2、求、求bi的允许范围的

36、前提条件（保持原各资源的影子价格不变）的允许范围的前提条件（保持原各资源的影子价格不变）3、bi的确定过程（参看例子）的确定过程（参看例子）4、对第、对第i种资源考虑予以增减的步骤（口述）种资源考虑予以增减的步骤（口述）10/23/202251参数参数bi发生改变问题的分析发生改变问题的分析bi的确定过程之例：求的确定过程之例：求b2最初单纯型表最初单纯型表64000 x1x2x3x4x5bi0 x3931002700 x4320101000 x524001120zj00000j64000最终单纯型表最终单纯型表64000 x1x2x3x4x5bi0 x3001-15/49/8304x2010

37、1/2-1/4206x1100-1/43/820zj6401/25/4j000-1/2-5/410/23/202252处理如下：最初单纯型表最初单纯型表64000 x1x2x3x4x5bi0 x393100270+0b20 x432010100+1b20 x524001120+0b2zj00000j64000最终单纯型表最终单纯型表64000 x1x2x3x4x5bi0 x3001-15/49/830-15/4b24x20101/2-1/420+1/2b26x1100-1/43/820-1/4b2zj6401/25/4j000-1/2-5/410/23/202253 bi的确定过程之例：求的确

38、定过程之例：求b2（其他资源量不变）（其他资源量不变）1、设法确定出最终表上常量与、设法确定出最终表上常量与b2的关系：的关系：2、要不改变影子价格，则要仍然为最终表，故要求：、要不改变影子价格，则要仍然为最终表，故要求：3、联立上述不等式解之得：、联立上述不等式解之得：2221530b4120b2120b42221530b04120b02120b048b40210/23/202254b2=20b2=20时时0 0 x3x30 0 0 0 1 1 -3 3/4-3 3/41 1/81 1/8-45 -45 4 4 x2x20 0 1 1 0 0 1/21/2-1/4-1/430 30 6 6

39、x1x11 1 0 0 0 0 -1/4-1/4 3/83/815 15 z zi i6 6 4 4 0 0 1/21/21 1/41 1/4j j0 0 0 0 0 0 -1/2-1/2-1 1/4-1 1/40 0 x4x40 0 0 0 -4/15-4/151 1 -3/10-3/1012 12 4 4 x2x20 0 1 1 2/152/150 0 -1/10-1/1024 24 6 6 x1x11 1 0 0 -1/15-1/150 0 3/103/1018 18 z zi i6 6 4 4 2/152/150 0 1 2/5 1 2/5 j j0 0 0 0 -2/15-2/150

40、 0 -1 2/5-1 2/5 当当b2=20时，超范围，右边出现负数，用对偶单纯型法处理一次得：时，超范围，右边出现负数，用对偶单纯型法处理一次得：新的最优解：新的最优解：x1=18，x2=24，Z*=618+424=204 （81/2）x4=12表明：增加的表明：增加的20单位的锻件多出单位的锻件多出12个单位，只能配置个单位，只能配置8个单位。个单位。10/23/202255三、参数三、参数cj发生改变问题的分析发生改变问题的分析 1、cj参数发生改变的实际原因参数发生改变的实际原因 2、求、求cj的允许范围的前提条件（保持原最优解不变）的允许范围的前提条件（保持原最优解不变）3、cj的

41、确定过程（参看例子）的确定过程（参看例子）最终单纯型表最终单纯型表64000 x1x2x3x4x5bi0 x3001-15/49/8304x20101/2-1/4206x1100-1/43/820zj6401/25/4j000-1/2-5/410/23/202256最终单纯型表最终单纯型表6+c14000 x1x2x3x4x5bi0 x3001-15/49/8304x20101/2-1/4206+c1x1100-1/43/820zj6+c1401/2-1/4c15/4+3/8c1j000-1/2+1/4c1-5/4-3/8c110/23/202257 cj的确定过程之例：求的确定过程之例：求c

42、1（余下的（余下的cj不变）不变）1、确定出原终表上、确定出原终表上-1/2、-5/4与与c1的关系：的关系：2、要保持原最优解不变，则要仍然为最终表，故要求检验数行全部小于等于零，即：、要保持原最优解不变，则要仍然为最终表，故要求检验数行全部小于等于零，即：3、联立上述不等式组解之得：、联立上述不等式组解之得：11c8345c41211111c02453c0482c310110/23/202258关于关于bi、cj的确定可用灵敏性分析报告的确定可用灵敏性分析报告10/23/202259四、新增加一个约束条件问题的分析四、新增加一个约束条件问题的分析 1、新增加一个约束条件后原最优解受到影响否

43、的判断、新增加一个约束条件后原最优解受到影响否的判断 2、若原最优解受到影响，新的最优解的确定、若原最优解受到影响，新的最优解的确定 判定方法一：将原最优解带入新增约束条件，若满足，则原解不变；若判定方法一：将原最优解带入新增约束条件，若满足，则原解不变；若 不满足，则原解要变。不满足，则原解要变。判定方法二：在原最终表上加一行、一列后，将基变量的列系数变为单判定方法二：在原最终表上加一行、一列后，将基变量的列系数变为单 位向量，若右边没有出现负数，则原解不变；若右边出行位向量，若右边没有出现负数，则原解不变；若右边出行 负数，则原解要变。负数，则原解要变。当右边出现负数时，用对偶单纯型法处理

44、之，可得新的最优解。当右边出现负数时，用对偶单纯型法处理之，可得新的最优解。10/23/202260例：电力资源约束：单位消耗：例：电力资源约束：单位消耗：5 ，3 电力可用总量：电力可用总量：若为若为180万千瓦小时万千瓦小时 若为若为151万千瓦小时万千瓦小时 当电力总量为当电力总量为180万千瓦小时时，两种方法判定结论：原方案不变；万千瓦小时时，两种方法判定结论：原方案不变；当电力总量为当电力总量为151万千瓦小时时，两种方法判定结论：原方案要变；万千瓦小时时，两种方法判定结论：原方案要变；由方法二判定后，在判定的基础上，用对偶单纯型法处理可得新的最优由方法二判定后，在判定的基础上，用对

45、偶单纯型法处理可得新的最优 解为：解为：x1=17 ，x2=22 ，Z*=19010/23/2022616 64 40 00 00 00 0 x1x1x2x2x3x3x4x4x5x5x6x60 0 x3x30 0 0 0 1 1 -3 3/4-3 3/41 1/81 1/80 0 30 30 4 4 x2x20 0 1 1 0 0 1/21/2-1/4-1/40 0 20 20 6 6 x1x11 1 0 0 0 0 -1/4-1/4 3/83/80 0 20 20 0 0 x6x65 53 30 00 00 01 1 151151z zi i6 6 4 4 0 0 1/21/21 1/41

46、1/4j j0 0 0 0 0 0 -1/2-1/2-1 1/4-1 1/40 0 x3x30 0 0 0 1 1 -3 3/4-3 3/41 1/81 1/80 0 30 30 4 4 x2x20 0 1 1 0 0 1/21/2-1/4-1/40 0 20 20 6 6 x1x11 1 0 0 0 0 -1/4-1/4 3/83/80 0 20 20 0 0 x6x60 0 0 0 0 0 -1/4-1/4-1 1/8-1 1/81 1 -9 -9 1 1、变、变5 5为为0 00 0 3 3 0 0 1 1/41 1/4-1 7/8-1 7/81 1 51 51 z zi i6 6 4

47、4 0 0 1/21/21 1/41 1/40 0 j j0 0 0 0 0 0 -1/2-1/2-1 1/4-1 1/40 0 0 0 x3x30 0 0 0 1 1 -4 -4 0 0 1 1 21 21 4 4 x2x20 0 1 1 0 0 5/95/90 0 -2/9-2/922 22 6 6 x1x11 1 0 0 0 0 -1/3-1/30 0 1/31/317 17 0 0 x5x50 0 0 0 0 0 2/92/91 1 -8/9-8/98 8 z zi i6 6 4 4 0 0 2/92/90 0 1 1/91 1/9j j0 0 0 0 0 0 -2/9-2/90 0

48、-1 1/9-1 1/910/23/202262五、新增加一个决策变量问题的分析五、新增加一个决策变量问题的分析 1、新增加一个决策变量以后原最优解改变否的判断、新增加一个决策变量以后原最优解改变否的判断 通过计算新决策变量（此时为非基变量）的检验数来判定通过计算新决策变量（此时为非基变量）的检验数来判定 2、若原最优解改变，新的最优解的确定、若原最优解改变，新的最优解的确定 用单纯型法来确定用单纯型法来确定10/23/202263P P6 64 48 88 815156 64 40 00 00 01111x1x1x2x2x3x3x4x4x5x5x6x60 0 x3x30 0 0 0 1 1

49、-3 3/4-3 3/41 1/81 1/830 30 4 4 x2x20 0 1 1 0 0 1/21/2-1/4-1/420 20 6 6 x1x11 1 0 0 0 0 -1/4-1/4 3/83/8B B-1-1P P6 620 20 z zi i6 6 4 4 0 0 1/21/21 1/41 1/4j j0 0 0 0 0 0 -1/2-1/2-1 1/4-1 1/46 6=？-3 -3 c c6 6=11=11的的6 6P P6 6（4 48 88 8）1 1 c c6 6=15=15的的6 6 当当c6=11时，新产品不投产，因为时，新产品不投产，因为6=-3；当当c6=15时

50、，新产品要投产，因为时，新产品要投产，因为6=1 新产品新产品 投产多少，用单纯型法予以处理可得出投产多少，用单纯型法予以处理可得出10/23/202264 案例分析案例分析（案例一）李案例一）李P175 某五金厂利用金属薄板等资源生产四种产品，生产过程要经过五个车间，某五金厂利用金属薄板等资源生产四种产品，生产过程要经过五个车间，每个车间能提供的月工时数量和每种产品所需工时定额、各种产品的销售价每个车间能提供的月工时数量和每种产品所需工时定额、各种产品的销售价格和单位成本、销售趋势等资料如下表所示。格和单位成本、销售趋势等资料如下表所示。已知下月制造产品已知下月制造产品B和和D用的金属板供应