运筹学--目标规划分析课件

运筹学运筹学第四章第四章 目标规划目标规划 运筹学第四章运筹学第四章 目标规划目标规划 第四章第四章 目标规划目标规划 目标规划的求解方法目标规划的求解方法本章内容本章内容目标规划的数学模型目标规划的数学模型目标规划的灵敏度分析及应用举例目标规划的灵敏度分析及应用举例目的：目的：掌握掌握目标规划的数学模型及求解目标规划的数学模型及求解 理解理解目标规划的灵敏度分析目标规划的灵敏度分析第四章第四章 目标规划目标规划 目标规划的求解方法本章内容目标规划的数学模目标规划的求解方法本章内容目标规划的数学模例例1、某厂计划在下一个生产周期内生产甲、乙两种产品，、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大，已知资料如表所示。试制定生产计划，使获得的利润最大，试建立数学模型。试建立数学模型。引言：引言：12070单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲 单位单位 产品产品资源资源 消耗消耗例例1、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料例例2、某厂计划在下一个生产周期内生产甲、乙两种产品，、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大。已知资料如表所示。试制定生产计划，使获得的利润最大。试建立数学模型。试建立数学模型。12070单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲 单位单位 产品产品资源资源 消耗消耗要求：要求：1、完成或超额完成利润指标、完成或超额完成利润指标 50000元；元；2、产品甲不超过、产品甲不超过 200件，产品乙不低于件，产品乙不低于 250件；件；3、现有钢材、现有钢材 3600吨用完。吨用完。例例2、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料第一节第一节 目标规划的数学模目标规划的数学模型型第一节第一节 目标规划的数学模型目标规划的数学模型 目标规划是在线性规划的基础上，为适应实际问题中目标规划是在线性规划的基础上，为适应实际问题中多多目标决策目标决策的需要而逐步发展起来的一个分支。的需要而逐步发展起来的一个分支。2 2、线性规划要求问题的解必须严格满足全部约束条件，、线性规划要求问题的解必须严格满足全部约束条件，但实际问题中并非所有约束都需严格满足；目标规划无此要但实际问题中并非所有约束都需严格满足；目标规划无此要求。求。1 1、线性规划只讨论一个线性目标函数在一组线性约束条、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。合实际的解。一、目标规划概述一、目标规划概述（一）目标规划与线性规划的比较（一）目标规划与线性规划的比较 目标规划是在线性规划的基础上，为适应实际问题中多目标规划是在线性规划的基础上，为适应实际问题中多 5 5、线性规划的最优解是绝对意义下的最优，但需花去大、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。满意解，就能满足需要（或更能满足需要）。4 4、线性规划中的约束条件是同等重要的，是、线性规划中的约束条件是同等重要的，是硬约束硬约束；而目；而目标规划中有轻重缓急和主次之分，即有优先权。标规划中有轻重缓急和主次之分，即有优先权。目前，已经在经济计划、生产管理、经营管理、市场分析、目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。财务管理等方面得到了广泛的应用。3 3、线性规划求最优解；目标规划是找到一个满意解。、线性规划求最优解；目标规划是找到一个满意解。5、线性规划的最优解是绝对意义下的最优，但需花去大量的人、线性规划的最优解是绝对意义下的最优，但需花去大量的人目标值目标值：是指预先给定的某个目标的一个期望值。：是指预先给定的某个目标的一个期望值。1 1、目标值和偏差变量、目标值和偏差变量（二）目标规划的基本概念（二）目标规划的基本概念偏差变量偏差变量（事先无法确定的未知数）：是指实现值和（事先无法确定的未知数）：是指实现值和目标值之间的差异目标值之间的差异,记为记为 d d。正偏差变量正偏差变量：表示实现值超过目标值的部分，记为：表示实现值超过目标值的部分，记为 d d。负偏差变量负偏差变量：表示实现值未达到目标值的部分，记为：表示实现值未达到目标值的部分，记为 d d。目标值：是指预先给定的某个目标的一个期望值。目标值：是指预先给定的某个目标的一个期望值。1、目标值和偏差、目标值和偏差 当完成或超额完成规定的指标则表示：当完成或超额完成规定的指标则表示：当未完成规定的指标则表示：当未完成规定的指标则表示：当恰好完成指标时则表示：当恰好完成指标时则表示：在一次决策中，实现值不可能既超过目标值又未达到目在一次决策中，实现值不可能既超过目标值又未达到目标值，故有标值，故有 d d d d 0,0,并规定并规定d d0,d d0注意注意：目标规划中，一般有多个目标值，每个目标值都：目标规划中，一般有多个目标值，每个目标值都相应有一对偏差变量相应有一对偏差变量 。d d0,d d0d d0,d d0d d0,d d0 在一次决策中，实现值不可能既超过目标值又未达在一次决策中，实现值不可能既超过目标值又未达2 2、绝对约束和目标约束、绝对约束和目标约束 绝对约束：绝对约束：是指必须严格满足的等式约束或不等式约束；是指必须严格满足的等式约束或不等式约束；如线性规划问题的所有约束条件，不能满足这些条件的解如线性规划问题的所有约束条件，不能满足这些条件的解称为非可行解，所以绝对约束是称为非可行解，所以绝对约束是硬约束硬约束。目标约束：目标约束：是目标规划所特有的一种约束，它把要追求的是目标规划所特有的一种约束，它把要追求的目标值作为右端常数项，在追求此目标值时允许发生正偏目标值作为右端常数项，在追求此目标值时允许发生正偏差和负偏差。因此，目标约束是由决策变量，正、负偏差差和负偏差。因此，目标约束是由决策变量，正、负偏差变量和要追求的目标值组成的变量和要追求的目标值组成的软约束软约束。2、绝对约束和目标约束、绝对约束和目标约束 绝对约束：是指必须严格满足的等式约束绝对约束：是指必须严格满足的等式约束 优先因子优先因子Pk 是将决策目标按其重要程度排序并表示出是将决策目标按其重要程度排序并表示出来。来。P1P2PkPk+1，k=1.2N。3 3、优先因子（优先等级）与优先权系数、优先因子（优先等级）与优先权系数 权系数权系数k 区别具有相同优先因子的两个目标的差别，区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。决策者可视具体情况而定。解释：解释：表示表示Pk比比Pk+1有更大的优先级。有更大的优先级。优先因子优先因子Pk 是将决策目标按其重要程度排序并表示是将决策目标按其重要程度排序并表示 目标函数是按各目标约束的正、负偏差变量和赋予相应目标函数是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。的优先因子及权系数而构造的。4 4、目标函数、目标函数 要求恰好达到规定的目标值：要求恰好达到规定的目标值：要求不超过目标值：要求不超过目标值：弹性约束基本形式：弹性约束基本形式：要求超过目标值：要求超过目标值：则则min(d d)则则min(d)则则min(d)目标函数是按各目标约束的正、负偏差变量和赋予相应的目标函数是按各目标约束的正、负偏差变量和赋予相应的 对于这种解来说，前面的目标可以保证实现或部分对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。有些可能就不能实现。5 5、满意解（具有层次意义的解）、满意解（具有层次意义的解）对于这种解来说，前面的目标可以保证实现或部分对于这种解来说，前面的目标可以保证实现或部分（三）目标规划的数学模型（三）目标规划的数学模型（三）目标规划的数学模型（三）目标规划的数学模型 例例2、某厂计划在下一个生产周期内生产甲、乙两种产品，、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大已知资料如表所示。试制定生产计划，使获得的利润最大？试建立数学模型。试建立数学模型。12070单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲 单位单位 产品产品资源资源 消耗消耗要求：要求：1、完成或超额完成利润指标、完成或超额完成利润指标 50000元；元；2、产品甲不超过、产品甲不超过 200件，产品乙不低于件，产品乙不低于 250件；件；3、现有钢材、现有钢材 3600吨用完。吨用完。例例2、某厂计划在下一个生产周期内生产甲、乙两种产品，、某厂计划在下一个生产周期内生产甲、乙两种产品，目标规划模型为：目标规划模型为：分析：分析：目标规划模型为：分析：目标规划模型为：分析：例一分析：例一分析：题目有三个目标层次，包含四个目标值。题目有三个目标层次，包含四个目标值。第一目标：第一目标：第二目标：有两个要求即甲第二目标：有两个要求即甲 ，乙，乙 ，但两个具，但两个具有相同的优先因子。有相同的优先因子。本题可用单件利润比作为权系数即本题可用单件利润比作为权系数即 70:120，化简为，化简为7:12。第三目标：第三目标：例一分析：例一分析：题目有三个目标层次，包含四个目标值。第题目有三个目标层次，包含四个目标值。第目标规划模型为：目标规划模型为：目标规划模型为：目标规划模型为：例例3：某厂生产：某厂生产、两种两种产品，有关数据如表所示。产品，有关数据如表所示。试求获利最大的生产方案试求获利最大的生产方案？拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 在此基础上考虑：在此基础上考虑：1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量；2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班；3、利润不小于、利润不小于 56 元。元。例例3：某厂生产：某厂生产、两种产品，有关数据如表所示。试求获利最两种产品，有关数据如表所示。试求获利最 目标：目标：1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量；2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班；3、利润不小于、利润不小于 56 元。元。目标：目标：第一目标：第一目标：即产品即产品的产量不大于的产量不大于的产量。的产量。第二目标：第二目标：第三目标：第三目标：目标：目标：1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量；2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班；3、利润不小于、利润不小于 56 元。元。目标函数：目标函数：+=-+-)(min3322211dPddPdPZ 第一目标：第二目标：第三目标：第一目标：第二目标：第三目标：目标：目标目标：目标目标规划模型为：目标规划模型为：目标规划模型为：目标规划模型为：课堂练习课堂练习 某厂生产某厂生产A、B、C三种产品，装配工作在同一生产线三种产品，装配工作在同一生产线上完成，三种产品的工时消耗分别为上完成，三种产品的工时消耗分别为6 6、8 8、1010小时，生产小时，生产线每月正常工作时间为线每月正常工作时间为200200小时；三种产品销售后，每台可小时；三种产品销售后，每台可获利分别为获利分别为500500、650650和和800800元；每月销售量预计为元；每月销售量预计为1212、1010和和6 6台。台。该厂经营目标如下：该厂经营目标如下：1 1、利润指标为每月、利润指标为每月1600016000元，争取超额完成；元，争取超额完成；2 2、充分利用现有生产能力；、充分利用现有生产能力；3 3、可以适当加班，但加班时间不超过、可以适当加班，但加班时间不超过2424小时；小时；4 4、产量以预计销售量为准。、产量以预计销售量为准。试建立目标规划模型。试建立目标规划模型。课堂练习课堂练习 某厂生产某厂生产A、B、C三种产品，装配工作在同一生三种产品，装配工作在同一生答案：答案：答案：答案：（四（四）小结小结线性规划线性规划LPLP目标规划目标规划GPGP目标函数目标函数min ,max系数可正负系数可正负min ,偏差变量偏差变量系数系数00变量变量决策变量决策变量 决策变量决策变量 d d约束条件约束条件绝对约束绝对约束目标约束目标约束绝对约束绝对约束解解最优最优最满意最满意（四）小结线性规划（四）小结线性规划LP目标规划目标规划GP目标函数目标函数min ,第二节第二节 解目标规划的图解解目标规划的图解法法第二节第二节 解目标规划的图解法解目标规划的图解法 引例：某厂生产引例：某厂生产、两种两种产品，有关数据如表所示。产品，有关数据如表所示。试求获利最大的生产方案试求获利最大的生产方案？拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 在此基础上考虑：在此基础上考虑：1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量；2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班；3、利润不小于、利润不小于 56 元。元。引例：某厂生产引例：某厂生产、两种产品，有关数据如表所示。试求获利最两种产品，有关数据如表所示。试求获利最目标规划模型为：目标规划模型为：目标规划模型为：目标规划模型为：图解法解题步骤如下：图解法解题步骤如下：步骤步骤1 1 建立直角坐标系，令各偏差变量为建立直角坐标系，令各偏差变量为0 0，作出所有的约，作出所有的约束直线束直线 。满足所有。满足所有绝对约束条件绝对约束条件的区域，用阴影标出。的区域，用阴影标出。图解法解题步骤如下：步骤图解法解题步骤如下：步骤1 建立直角坐标系，令各偏差变量为建立直角坐标系，令各偏差变量为步骤步骤2 2 作图表示偏差变量增减对约束直线的影响作图表示偏差变量增减对约束直线的影响 在所有目标约束直线旁在所有目标约束直线旁标上标上 d d+，d d-，步骤步骤2 作图表示偏差变量增减对约束直线的影响作图表示偏差变量增减对约束直线的影响 在所有目标约在所有目标约步骤步骤3 3 根据目标函数中的优先因子次序，逐步分析求解。根据目标函数中的优先因子次序，逐步分析求解。步骤步骤3 根据目标函数中的优先因子次序，逐步分析求解。根据目标函数中的优先因子次序，逐步分析求解。步骤步骤3 3 根据目标函数中的优先因子次序，逐步分析求解。根据目标函数中的优先因子次序，逐步分析求解。根据目标函数中的优先因子次序，首先考虑具有优先根据目标函数中的优先因子次序，首先考虑具有优先因子因子 p p1 1 的目标的实现。目标函数要求实现的目标的实现。目标函数要求实现 min min d d1 1+，从图从图中可见，可以满足中可见，可以满足d d1 1+=0=0，这时，只能在三角形这时，只能在三角形 OBCOBC的区的区域上取值；域上取值；考察具有优先因子考察具有优先因子 p p2 2的目的目标，此时可在线段标，此时可在线段ED ED 上取值；上取值；考察优先因子考察优先因子 p p3 3 的目标，的目标，这就使取值范围缩小到线段这就使取值范围缩小到线段 GD GD 上，该线段上所有点的坐上，该线段上所有点的坐标，都是问题的解，标，都是问题的解，G(2,4)G(2,4)D(10/3,10/3)D(10/3,10/3)。步骤步骤3 根据目标函数中的优先因子次序，逐步分析求解。根据目标函数中的优先因子次序，逐步分析求解。例例1、用图解法求解目标规划问题、用图解法求解目标规划问题例例1、用图解法求解目标规划问题、用图解法求解目标规划问题01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1BC B(0.6250,4.6875)C(0,5.2083)，B、C 线段上的所有线段上的所有点均是该问题的解（无穷多最优解）。点均是该问题的解（无穷多最优解）。01 2 3 4例例2、已知一个生产计划的线性规划模型为、已知一个生产计划的线性规划模型为 其中目标函数为总利润，其中目标函数为总利润，x1，x2 为产品为产品A、B产量。现有下产量。现有下列目标：列目标：1、要求总利润必须超过、要求总利润必须超过 2500 元；元；2、考虑产品受市场影响，为避免积压，、考虑产品受市场影响，为避免积压，A、B的生产量不生产量不超过超过 60 件和件和 100 件；件；3、由于甲资源供应比较紧张，不要超过现有量、由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。试建立目标规划模型，并用图解法求解。例例2、已知一个生产计划的线性规划模型为、已知一个生产计划的线性规划模型为 其中目标函数其中目标函数 解：以产品解：以产品 A A、B B 的单件利润比的单件利润比 2.5 2.5：1 1 为权系数，模为权系数，模型如下：型如下：解：以产品解：以产品 A、B 的单件利润比的单件利润比 2.5：1 为权系数为权系数0 x2 0 x11401201008060402020 40 60 80 1003作图：作图：0 x2 0 x114020 40 60 x2 x11401201008060402020 40 60 80 1000 0ABC 结论：结论：C(60,58.3)C(60,58.3)为所求的满意解。为所求的满意解。作图：作图：x2 x114020 40 60 8第三节第三节 解目标规划的单纯形解目标规划的单纯形法法第三节第三节 解目标规划的单纯形法解目标规划的单纯形法 目标规划的数学模型与线性规划的数学模型基本相目标规划的数学模型与线性规划的数学模型基本相同，因此利用单纯形法求解步骤也基本相同，但是需要同，因此利用单纯形法求解步骤也基本相同，但是需要尤其注意它们之间的区别。尤其注意它们之间的区别。线性规划的单纯形法求解过程线性规划的单纯形法求解过程(目标函数极大化情况下目标函数极大化情况下)：1.1.建立初始单纯形表，计算出所有变量的检验数；建立初始单纯形表，计算出所有变量的检验数；2.2.在非基变量检验数中找到最大的正数在非基变量检验数中找到最大的正数j j，它所对应的它所对应的变量变量x xj j 作为换入基的变量；作为换入基的变量；3.3.对于所有对于所有a aijij0 0 计算计算b bi i/a aij ij 其中最小的元素其中最小的元素所对应所对应的基变量的基变量x xi i 作为换出基的变量；作为换出基的变量；4.4.建立新单纯形表，重复上述步骤建立新单纯形表，重复上述步骤2 2、3 3，直到所有检验，直到所有检验数都小于等于零。数都小于等于零。目标规划的数学模型与线性规划的数学模型基本相目标规划的数学模型与线性规划的数学模型基本相 由于目标规划的目标函数都是求由于目标规划的目标函数都是求极小化极小化问题，而线性问题，而线性规划问题的标准型中目标函数是求规划问题的标准型中目标函数是求极大化极大化问题，因此在用问题，因此在用单纯形法求解时要注意一些重要的的差别。单纯形法求解时要注意一些重要的的差别。例例1 1 用单纯形法求解下述目标规划问题：用单纯形法求解下述目标规划问题：由于目标规划的目标函数都是求极小化问题，而线性规划问由于目标规划的目标函数都是求极小化问题，而线性规划问第一步：第一步：列出初始单纯形表，并计算检验数。列出初始单纯形表，并计算检验数。将表格中最后一行检验数按优先级改写为：将表格中最后一行检验数按优先级改写为：（这是与线性规划单纯形法的（这是与线性规划单纯形法的第一个差别第一个差别）第一步：列出初始单纯形表，并计算检验数。第一步：列出初始单纯形表，并计算检验数。将表将表第二步：第二步：确定换入基的变量。确定换入基的变量。在负检验数中，选择最小的一个在负检验数中，选择最小的一个j j 所对应的变量所对应的变量x xj j作为作为换入基的变量换入基的变量(第二个差别第二个差别)。第三步：第三步：确定换出基的变量（这与线性规划相同）。确定换出基的变量（这与线性规划相同）。第二步：确定换入基的变量。第二步：确定换入基的变量。在负检验数中，选择最小的一个在负检验数中，选择最小的一个 第四步：第四步：用换入变量替换换出变量，进行单纯形法迭代运算，用换入变量替换换出变量，进行单纯形法迭代运算，直至优先级直至优先级 P P1 1 所对应的检验数全为非负。所对应的检验数全为非负。本例中，第本例中，第一优先级计一优先级计算后得：算后得：由于优先级由于优先级 P P2 2 的检验数仍然的检验数仍然有负值，因此有负值，因此可以继续优化，可以继续优化，重复上述步骤重复上述步骤 2-4 2-4。第四步：用换入变量替换换出变量，进行单纯形法迭代运算，直至第四步：用换入变量替换换出变量，进行单纯形法迭代运算，直至 确定换入、换出变量：确定换入、换出变量：第一点说明：第一点说明：目标函数按优先级顺序进行优化，当目标函数按优先级顺序进行优化，当P P1 1 行所有检验数非负行所有检验数非负时，说明第一级已经优化，可以转入下一级，考察时，说明第一级已经优化，可以转入下一级，考察 P P2 2 行检验行检验数，依此类推。数，依此类推。确定换入、换出变量：确定换入、换出变量：第一点说明：第一点说明：第二点说明：第二点说明：从考察从考察P P2 2行检验数开始，注意应把更高级别的优先因子行检验数开始，注意应把更高级别的优先因子考虑在内。如上述问题的进一步单纯形表如下：考虑在内。如上述问题的进一步单纯形表如下：对应的检验数为对应的检验数为P P1 1+(+(3/2)3/2)P P2 200对应的检验数为对应的检验数为P P1 1 P P2 2 00对应的检验数为对应的检验数为P P1 12 2P P2 200 因此上述三种情况都不能因此上述三种情况都不能选为换入基的变量，这其实选为换入基的变量，这其实与线性规划相同。与线性规划相同。第二点说明：第二点说明：从考察从考察P2行检验数开始，注意应把更高行检验数开始，注意应把更高 判别迭代计算停止的准则：判别迭代计算停止的准则：(1)(1)检验数检验数P P1 1,P P2 2,P Pk k行的所有值均为非负；行的所有值均为非负；(2)(2)若若P P1 1,P P2 2,P Pi i行的所有检验数为非负而行的所有检验数为非负而 P Pi i+1+1行存在负检验数，但在负检验数所在列的上面行行存在负检验数，但在负检验数所在列的上面行中有正检验数（不一定是相邻行，只要在其上方中有正检验数（不一定是相邻行，只要在其上方即可）。即可）。判别迭代计算停止的准则：判别迭代计算停止的准则：(1)检验数检验数P1,P例例2 2：用单纯形法求解下列目标规划问题：用单纯形法求解下列目标规划问题：解：解：解：解：例例2：用单纯形法求解下列目标规划问题：用单纯形法求解下列目标规划问题：cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1-2 0 1-1 0 0 0 0 0 36 4 4 0 0 0 1-1 0 0 P3 48 6 8 0 0 0 0 0 1-1 P1-1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3-6-8 0 0 0 0 0 0 1 cj 0 0 0 P1 0 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1-2 0 1-1 0 0 0 0 0 36 4 4 0 0 0 1-1 0 0 P3 48 6 8 0 0 0 0 0 1-1 P1-1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3-6-8 0 0 0 0 0 0 1 cj 0 0 0 P1 0 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1-2 0 1-1 0 0 0 0 0 36 4 4 0 0 0 1-1 0 0 P3 48 6 8 0 0 0 0 0 1-1 P1-1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3-6-8 0 0 0 0 0 0 1 0 x3 60 0 20 1-5 5 0 0 0 0 0 x1 0 1-2 0 1-1 0 0 0 0 0 36 0 12 0-4 4 1-1 0 0 P3 48 020 0-6 6 0 0 1-1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6-6 0 0 0 1 cj 0 0 0 P1 0 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1-5 5 0 0 0 0 0 x1 0 1-2 0 1-1 0 0 0 0 0 36 0 12 0-4 4 1-1 0 0 P3 48 020 0-6 6 0 0 1-1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6-6 0 0 0 1 0 x312 0 0 1 1 -1 0 0 -1 1 0 x124/5 1 0 0 2/5-2/5 0 01/10-1/10 036/5 0 0 0-2/5 2/5 1-1-3/5 3/5 0 x212/5 0 1 0-3/10 3/10 0 01/20-1/20 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 0 cj 0 0 0 P1 0 例例3 3：用单纯形法求解下列目标规划问题：用单纯形法求解下列目标规划问题例例3：用单纯形法求解下列目标规划问题：用单纯形法求解下列目标规划问题Cj00P100002.5P20P2CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1 301201000000P2 00000002.501P3 0000010000=min2500/30,140/2,60/1=60,故故 为换出变量。为换出变量。Cj00P100002.5P20P2CBXBbx1x2P12Cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 0120100303000P2 00000002.501P3 0000010000=min700/30,20/2,=10,故故 为换出变量。为换出变量。Cj 00P100P302.5P20P2CBXBbx1x2PCj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 030115-150000P2 0-5/400-5/45/45/2001P3 0000010000=min400/15,=10,故故 为换出变量。为换出变量。Cj 00P100P302.5P20P2CBXBbx1x2PCj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 0010000000P2 0-1-1/121/12002/5001P3 01/5-1/151/15100000=min,350/6,1250/6,100/1=75,故故 为换出变量。为换出变量。Cj 00P100P302.5P20P2CBXBbx1x2PCj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211kjP1 0010000000P2 00000005/201P3 00-1/121/12101/2-1/200满意解满意解x x1 1*=60=60，x x2 2*=175/3=175/3。Cj 00P100P302.5P20P2CBXBbx1x2P目标规划的灵敏度分析所讨论内容包括：目标规划的灵敏度分析所讨论内容包括：1 1、约束条件（目标约束和硬约束）右端常数的变化；、约束条件（目标约束和硬约束）右端常数的变化；2 2、约束条件中各变量系数的变化；、约束条件中各变量系数的变化；3 3、加入新的变量（决策变量和偏差变量）；、加入新的变量（决策变量和偏差变量）；4 4、加入新的约束条件；、加入新的约束条件；5 5、目标函数中偏差变量的优先等级及权系数的变化；、目标函数中偏差变量的优先等级及权系数的变化；第四节第四节 灵敏度分析灵敏度分析目标规划的灵敏度分析所讨论内容包括：目标规划的灵敏度分析所讨论内容包括：1、约束条件（目标约束和、约束条件（目标约束和已知目标规划问题：已知目标规划问题：已知目标规划问题：已知目标规划问题：XBCjP31P3 1-22-33P2 32P1 kj-1111-112P2-112-23-318-11141-1-1116x1x2x1bx2CBP23P12P1表表1:1:XBCjP31P3 1-22-33P2 32P1-1111目标函数的优先等级变化为：目标函数的优先等级变化为：(1)(1)min z=Pmin z=P1 1(2d(2d1 1+3d+3d2 2+)+P)+P2 2d d4 4+P+P3 3d d3 3-(2)min z=P(2)min z=P1 1d d3 3-+P+P2 2(2d(2d1 1+3d+3d2 2+)+P)+P3 3d d4 4+试分析原解有什么变化。试分析原解有什么变化。目标函数的优先等级变化为：目标函数的优先等级变化为：XBCjP31P3 1-22-33P2 32P1 kj-1111-112P2-112-23-318-11141-1-1116x1x2x1bx2CBP23P12P1原：min z=P1(2d1+3d2+)+P2d3-+P3d4+分析分析(1):(1):XBCjP31P3 1-22-33P2 32P1-1111XBCjP21-22-33P3 1P2 32P1 kj-1111-112P3-112-23-318-11141-1-1116x1x2x1bx2CBP33P12P1新1:min z=P1(2d1+3d2+)+P2d4+P3 d3-将将原原目目标标函函数数中中d d4 4+，d d3 3-的的优优先先因因子子对对换换了了一一下下。只只需对表需对表1 1的检验数中的的检验数中的P P2 2、P P3 3行和行和c cj j行的行的P P2 2、P P3 3对换即可。对换即可。表表1 1:XBCjP21-22-33P3 1P2 32P1-1111XBCjP31P3 32P2 1-22-33P1 kj-1111-12P1-112-23-318-11141-1-1116x1x2x1bx2CBP13P22P2表表2:2:然后继续进行迭代然后继续进行迭代新2:min z=P1 d3-+P2(2d1+3d2+)+P3 d4+分析分析(2):(2):XBCjP31P3 32P2 1-22-33P1-1111XBCjP31/3-1/3-2/32/3P3 32P2 1P1 kj-1/31/32/3-2/31-16P31-1-1/31/32/3-2/34-1114-1/31/35/3-5/3112x1x2x1bx2CBP13P22P2表表3:3:从表从表3 3中得到新的满意解中得到新的满意解x x1 1*=4=4，x x2 2*=12=12。XBCjP31/3-1/3-2/32/3P3 32P2 1PP111 4.2(2)P111 4.2(2)P112 4.4(1)P112 4.4(1)、(2)(2)作业作业P111 4.2(2)例例例例：某某公公司司生生产产A A、B B两两种种药药品品，这这两两种种药药品品每每小小时时的的产产量量均均为为10001000盒盒，该该公公司司每每天天采采用用两两班班制制生生产产，每每周周最最大大工工作作时时间间为为8080小小时时，按按预预测测每每周周市市场场最最大大销销量量分分别别为为7000070000盒盒和和4500045000盒盒A A种种药药每每盒盒的的利利润润为为2.52.5元元，B B种种为为1.51.5元元试试确确定定公公司司每每周周A A、B B两两种种药药品品生生产产量量x x1 1和和x x2 2（单单位位：千千盒盒），使使公公司司的的下下列列目目标标得得以实现：以实现：P P P P1 1 1 1：避免每周避免每周8080小时生产能力的过少使用小时生产能力的过少使用 P P P P2 2 2 2：加班的时间尽量限制在加班的时间尽量限制在1010小时以内小时以内 P P P P3 3 3 3：A A、B B两两种种药药品品的的每每周周产产量量尽尽量量分分别别达达到到7000070000盒盒和和4500045000盒盒，但不得超出，其权系数依它们每盒的利润为准但不得超出，其权系数依它们每盒的利润为准 P P P P4 4 4 4：尽量减少加班时间尽量减少加班时间 应用举例应用举例例：某公司生产例：某公司生产A、B两种药品，这两种药品每小时的产量均为两种药品，这两种药品每小时的产量均为10解解解解：先先建建立立这这个个问问题题的的线线性性规规划划模模型型，依依题题意意分分别别建建立立各各项目标约束项目标约束权系数是指它们在目标函数中的重要程度，由权系数是指它们在目标函数中的重要程度，由 2.51.5=532.51.5=53，故：目标函数为：，故：目标函数为：建立单纯形表建立单纯形表运算运算如下：如下：解：先建立这个问题的线性规划模型，依题意分别建立各项目标约束解：先建立这个问题的线性规划模型，依题意分别建立各项目标约束 cj 0 0 P1 5P3 3P3 0 P4 P2 CB XB b x1 x2 P1 80 1 1 1 0 0 0-1 0 5P3 70 1 0 0 1 0 0 0 0 3P3 45 0 1 0 0 1 0 0 0 0 10 0 0 0 0 0 1 1-1 P1-1-1 0 0 0 0 1 0 P2 0 0 0 0 0 0 0 1 P3-5-3 0 0 0 0 0 0 P4 0 0 0 0 0 0 1 0 P1 10 0 1 1-1 0 0-1 0 0 x1 70 1 0 0 1 0 0 0 0 3P3 45 0 1 0 0 1 0 0 0 0 10 0 0 0 0 0 1 1-1 P1 0-1 0 1 0 0 1 0 P2 0 0 0 0 0 0 0 1 P3 0-3 0 5 0 0 0 0 P4 0 0 0 0 0 0 1 0 cj 0 0 P1 5P3 3P cj 0 0 P1 5P3 3P3 0 P4 P2 CB XB b x1 x2 P1 10 0 1 1-1 0 0-1 0 0 x1 70 1 0 0 1 0 0 0 0 3P3 45 0 1 0 0 1 0 0 0 0 10 0 0 0 0 0 1 1-1 P1 0-1 0 1 0 0 1 0 P2 0 0 0 0 0 0 0 1 P3 0-3 0 5 0 0 0 0 P4 0 0 0 0 0 0 1 0 0 x2 10 0 1 1-1 0 0-1 0 0 x1 70 1 0 0 1 0 0 0 0 3P3 35 0 0-1 1 1 0 1 0 0 10 0 0 0 0 0 1 1-1 P1 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 0 1 P3 0 0 3 2 0 0-3 0 P4 0 0 0 0 0 0 1 0 cj 0 0 P1 5P3 3P cj 0 0 P1 5P33P3 0 P4 P2 CB XB b x1 x2 0 x2 10 0 1 1-1 0 0-1 0 0 x1 70 1 0 0 1 0 0 0 0 3P3 35 0 0-1 1 1 0 1 0 0 10 0 0 0 0 0 1 1-1 P1 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 0 1 P3 0 0 3 2 0 0-3 0 P4 0 0 0 0 0 0 1 0 0 x2 20 0 1 1-1 0 1 0 1 0 x1 70 1 0 0 1 0 0 0 0 3P3 25 0 0-1 1 1-1 0 1 P4 10 0 0 0 0 0 1 1-1 P1 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 0 1 P3 0 0 3 2 0 3 0-3 P4 0 0 0 0 0-1 0 1 cj 0 0 P1 5P33P3从而得最优解为：从而得最优解为：x1=70 =70 x2=20 =20 即生产即生产A种药品种药品7000070000盒，盒，B种药品种药品2000020000盒，盒，P1，P2，P3级目标可完全实现因级目标可完全实现因 ，故每周需加班，故每周需加班1010小时，每周利润为小时，每周利润为:700002.5+200001.5=205000700002.5+200001.5=205000（元）（元）从而得最优解为：从而得最优解为：x1=70 x2=20