运筹学基础-目标规划

《运筹学基础-目标规划》由会员分享，可在线阅读，更多相关《运筹学基础-目标规划（29页珍藏版）》请在金锄头文库上搜索。

1、第五章、目标规划目标规划(Goal programming)是在线性规划基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个运筹 学分支。目前研究较多的有线性目标规划、非线性目标规划 、线性整数目标规划和0-1目标规划等。本章主要讨论线性目 标规划，简称目标规划。 5.15.1 目标规划问题的提出与目标规划模型 目标规划问题的提出与目标规划模型引例引例1 1某生物药厂需在市场上采购某种原料，现市场上有甲、乙 两个等级，单价分别为2千元/kg和1千元/kg，要求采购的总费用不得 超过20万元，购得原料的总重量不少于100kg，而甲级原料又不得少 于50kg，问如何确定最好的采购方案（即用

2、最少的钱、采购最多数量的原料）。目标函数为：目标函数为：一、问题的提出一、问题的提出分析：这是一个含有两个目标的数学规划问题 设x x1 1、x x2 2分别为采 购甲级、乙级原材料的数量（单位：kg）， y y1 1为花掉的资金， y y2 2为 所购原料总量则：约束条件为：约束条件为：注：此规划模型是一个多目标规划模型引例引例2 2某企业生产、两种产品。这两种产品都要分别在A、B、C、D 四各不同设备上加工。生产每件产品需占用各设备为2、1、4、0小时 ，生产每件产品 需占用各设备为2、2、0、4小时，各设备用于生产 这两种产品的能力分别为12、8、16、12小时，又知生产一件产品获 得2

3、元，生产一件产品 获得3元，问如何安排生产，使总的利润最大 。则该问题的数学模型表示为则该问题的数学模型表示为maxZ= 2x1 +3x22x1+2x2 12x1 +2x2 84x1 164x2 12x1 0, x2 0但企业通常的经营目标会更实际、更多样！但企业通常的经营目标会更实际、更多样！这是一个线性规划模型这是一个线性规划模型企业的新目标：企业的新目标：力求使利润指标不低于12元； 考虑到市场需求，, 两种产品的生产量需保持1:1的比例； C和D为贵重设备，严格禁止超时使用；设备B必要时可以加班，但加班时间要控制，设备A既要求充 分利用，又尽可能不加班。等等这些目标通过线性规划无法实现

4、 这些目标通过线性规划无法实现引例引例3 3表4-1 产品的资源、技术消耗定额、单位利润表甲（每件）乙（每件）现有资源钢 材 （kg）9.243600木 材 (m3)452000设备负荷（台小时）3103000单位产品利润 (元)70120某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产 品的技术消耗定额、单位利润如下表所示试确定计划期内的生产计 划，使利润最大。分析:设x x1 1、x x2 2分别是计划期内甲、乙产品的产量则该问题的 数学模型为同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙 产品的生产，同时考虑这些问题，就形成多目标规划问题分析：分析：对于这样的多目标问题

5、，线性规划很难为其找到最优方案 极有可能出现：第一个方案使第一目标的结果优于第二方案，而对于第二 目标，第二方案优于第一方案就是说很难找到一个方案使所 有目标同时达到最优，特别当约束条件中有矛盾方程时，线性 规划方法是无法解决的。实践中，人们转而采取“不求最好，但求满意”的策略，在 线性规划的基础上建立一种新的数学规划方法目标规划目标规划与线性规划相比，有以下优点：目标规划与线性规划相比，有以下优点：1.1.线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题2.2.线性规划是在满足所有约束条件的可行解中求得最优解。线性规划是

6、在满足所有约束条件的可行解中求得最优解。 实际问题中，往往要考虑多个目标的决策问题，这些目标可能 互相矛盾，也可能没有统一的度量单位，很难比较。目标规划就能 够兼顾地处理多种目标的关系，求得更切合实际的解。 而在实际问题中往往存在一些相互矛盾的约束条件，如何在这 些相互矛盾的约束条件下，找到一个满意解就是目标规划所要讨论 的问题。 3.3.线性规划问题中的约束条件是不分主次、同等对待的线性规划问题中的约束条件是不分主次、同等对待的线性规划问题是一律要满足的“硬约束”。而在实际问题中， 多个目标和多个约束条件不一定是同等重要的，而是有轻重缓急和 主次之分的，如何根据实际情况确定模型和求解，使其更

7、合实际是 目标规划的任务。 4.4.线性规划的最优解可以说是绝对意义下的最优线性规划的最优解可以说是绝对意义下的最优为求得这个最优解，往往要花去大量的人力、物力和才力。而 在实际问题中，却并不一定需要去找这种最优解。目标规划所求的 满意解是指尽可能地达到或接近一个或几个已给定的指标值，这种 满意解更能够满足实际的需要。目标规划更能够确切描述和解决经济管理中的许多实际问题。目前 目标规划的理论和方法已经在经济计划、生产管理、经营管理、市场分 析、财务管理等方面得到广泛的应用。二、目标规划的基本概念二、目标规划的基本概念1.1.目标值和正、负偏差变量 目标值和正、负偏差变量 目标规划通过引入目标值

8、和正、负偏差变量，可将目标函数转化 为目标约束。所谓目标值是预先给定的某个目标的一个期望值。实现值（或决 策值）是当决策变量x1、x2、xn选定以后目标函数的对应值。显 然，实现值和目标值之间会有一定的差异，这种差异称为偏差变量( 事先无法确定的未知量)，用d d和d d表示。 当实际值超出目标值时，有d0， d0；当实际值未达到目标值时，有d0， d0 ；当实际值同目标值恰好一致时， d d 0 。因为在一次决策中，实现值不可能既超过目标值，同时又未达到目标 值，所以有 d与d两者中必有一个为零。故恒有d d 0 d d超出目标的差值，称正偏差变量超出目标的差值，称正偏差变量； d d未达到

9、目标的差值，称负偏差变量未达到目标的差值，称负偏差变量； 2.2.绝对约束与目标约束绝对约束与目标约束绝对约束绝对约束又称系统约束，是指必须严格满足的等式和不等 式约束，如线性规划问题的所有约束都是绝对约束，不满足这 些约束条件的解称为非可行解，所以它们是硬约束。以例2为例，如设备C和D严格禁止超时，故有：对那些不严格限定的约束，连同原线性规划建模时的目标 函数转化为的约束，均可通过目标约束目标约束来表达。 下面是如何形成目标约束目标约束 (1)(1) 将将目标函数目标函数转化为目标约束转化为目标约束在引入了目标值和正、负偏差变量后，可以将原目标函数加上 负偏差变量 ，减去正偏差变量 ，并令其

10、等于目标值，这样形成一个新的函数方程，把它作为一个新的约束条件，加入到原问题中去， 称这种新的约束条件为目标约束。目标约束是一种将约束和目标结合在一起的表达式，是目标规 划所特有的，它把约束右端项看作要求的目标值。比如：在实际计划工作中，利润指标往往是上级主管部门或工 厂计划部门预先规定并要求实现的数值。以例2为例，力求利润指标 不低于12元，这就是目标值。而工厂在安排了甲、乙两种产品的产 量（决策）后，可能实现的利润额与规定的利润指标12元之间会有 一定差距，这个差距就是偏差变量。 这样就将目标函数目标函数则转化为目标约束目标约束 (2) (2) 将将系统约束系统约束转化为目标约束转化为目标

11、约束有时也可以根据需要将绝对约束转化为目标约束，这时只 须将该约束的右端项看作目标值，再引入正、负偏差变量即可 。如在例2中，考虑到市场需求，, 两种产品的生产量需 保持1:1的比例；或此为系统约束在达到此目标值时允许发生正或负偏差，因此在这些约束 中加入正、负偏差变量，它们是软约束，在给定目标值和加入 正、负偏差变量之后，可以将系统约束系统约束转化为目标约束目标约束。转化方法： x x1 1 x x2 2 d d 0 0当产品 产量多于产品 ，有x1x2，即出现正偏差量d ，若将x1减去这个正偏差量d ，就有x x1 1x x2 2 d d 0 0因正负偏差不可能同时出现，故合在有一起设为x

12、 x1 1x x2 2 d d d d 0 0由于允许有偏差，当产品 产量小于产品 ，有x1x2 ，即出现负偏差量d ，若将x1加上这个负偏差量d ，就有3 3目标规划的目标函数达成函数目标规划的目标函数达成函数凡满足目标约束和绝对约束的解，应如何判别它的优劣 呢？从决策者的要求分析它总希望得到的结果与规定的目标 值之间的偏差愈小愈好，由此决策者可根据自己的要求构造 一个使总偏差量为最小的目标函数，这种函数就是目标规划 的目标函数称为达成函数，记为即达成函数是正、负偏变量的函数。 一般来说，可能提出的要求只能是以下三种情况之一，对应每 种要求，可分别构造的达成函数是： 构造达成函数的方法构造达

13、成函数的方法如希望产品 产量恰好等于产品的产量 ，即正、负偏变量都要尽可能地小，这时函数是：如希望产品 产量低于产品的产量 ，即允许达不到目标值, 就是正偏差变量要尽可能地小,即不希望上式中的d d0，这时达成函数是：如希望产品 产量不低于产品的产量 ，即要求超过目标值，但不得低于目标值，即必须是负偏差变量尽可能地小，不希望上式 中的d d0，这时达成函数是：又如 中力求利润指标不低于12元，达 成函数为：设备B限制 中必要时可以加班可表为：设备A限制 中既要求充分利用，又尽可 能不加班可表为：4.4. 目标的优先级与权系数目标的优先级与权系数 在一个多目标决策问题中，要找出使所有目标都达到最

14、优的 解是很不容易的；在有些情况下，这样 的解根本不存在(当这些 目标是互相矛盾时)。实际 作法是：决策者将这些目标分出主次 ，或根据这些目标的轻重缓急不同，区别对 待。 在一个目标规划的模型中，如果两个不同目标重要程度相差悬殊 ，为达到某一目标可牺牲其它一些目标，称这些目标是属于不同层次不同层次 的优先级的优先级。优先级层次的高低可分别通过优先因子P1，P2，表示，并 规定Pk Pk1，符号“”表示“远大于”，表示Pk与Pk1，不 是同一各级别的量，即Pk与Pk1有更大的优先权。对属于同一层次优先级的不同目标，按其重要程度可分别乘上 不同的权数。权系数是一个个具体数字，乘上的权系数越大，表明

15、 该目标越重要。5.5. 满意解满意解 目标规划问题的求解是分级进行的，首先要求满足P1级目 标的解；然后再保证 P1级目标不被破坏的前提下，再要求满足 P2级目标的解；依次类推。总之，是在不破坏上一级目标的 前提下，实现下一级目标的最优。因此，这样最后求出的解就 不是通常意义下的最优解，我们称它为满意解。之所以叫满意解，是因为对于这种来说，前面的目标是可 以保证实现或部分实现的，后面的目标就不一定能保证实现。满意解这一概念的提出是对最优化概念的一种突破，显然 它更切合实际，更便于运用，因而受到广大实际工作者的欢迎 而被广泛采用。 三、目标规划的数学模型及建模步骤三、目标规划的数学模型及建模步骤以上介绍的几个基本概念，实际 上就是建立目标规 划模型时必 须分析的几个要素，把这些要素分析清楚了，目标规 划的模型也就建 立起来了。 设有L个目标，K个优先等级(KL)的一般目标规划问题。再同一个优先级别的不同目标，它们的正负偏差变量的重要程度还可以 有差别。这时还可以给同一优先级别的正负偏差变量赋予不同的权 系数和 。则目标规划问题的一般数学模型可表述为 目标约束绝对约束目标规划问题建立模型的步骤为：目标规划问题建立模型的步骤为：1. 根据要研究的问题所提出的各目标与条件，确定目标值，列出目 标约束与绝对约束； 2.可根据决策者的需要将某