运筹学基础目标规划

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

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

3、2 x1 +2x2 8 4x1 164x2 12 x1 0, x2 0但企业通常的经营目标会更实际、更多样！这是一个线性规划模型3企业的新目标：力求使利润指标不低于12千元； 考虑到市场需求，, 两种产品的生产量需保持1:1的比例；C和D为贵重设备，严格禁止超时使用；设备B必要时可以加班，但加班时间要控制，设备A既要求充分利用，又尽可能不加班。等等这些目标通过线性规划无法实现4【引例3】某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如下表所示试确定计划期内的生产计划，使利润最大。分析:设x1、x2分别是计划期内甲、乙产品的产量则该问题的数学模型为 同时厂领导

4、为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产，同时考虑这些问题，就形成多目标规划问题5分析：对于这样的多目标问题，线性规划很难为其找到最优方案极有可能出现： 第一个方案使第一目标的结果优于第二方案，而对于第二目标，第二方案优于第一方案就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的。 实践中，人们转而采取“不求最好，但求满意”的策略，在线性规划的基础上建立一种新的数学规划方法目标规划6目标规划与线性规划相比，有以下优点：1.线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题2.线性规划是在满足所有约束条件的可行解中求得最

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

6、要花去大量的人力、物力和才力。而在实际问题中，却并不一定需要去找这种最优解。目标规划所求的满意解是指尽可能地达到或接近一个或几个已给定的指标值，这种满意解更能够满足实际的需要。 目标规划更能够确切描述和解决经济管理中的许多实际问题。目前目标规划的理论和方法已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到广泛的应用。8二、目标规划的基本概念1.目标值和正、负偏差变量 目标规划通过引入目标值和正、负偏差变量，可将目标函数转化为目标约束。 所谓目标值是预先给定的某个目标的一个期望值。实现值（或决策值）是当决策变量x1、x2、xn选定以后目标函数的对应值。显然，实现值和目标值之间会有一

7、定的差异，这种差异称为偏差变量(事先无法确定的未知量)，用d和d表示。 当实际值超出目标值时，有d0， d0；当实际值未达到目标值时，有d0， d0 ；当实际值同目标值恰好一致时， d d 0 。因为在一次决策中，实现值不可能既超过目标值，同时又未达到目标值，所以有 d与d两者中必有一个为零。故恒有d d 0 d超出目标的差值，称正偏差变量；d未达到目标的差值，称负偏差变量；92.绝对约束与目标约束绝对约束又称系统约束，是指必须严格满足的等式和不等式约束，如线性规划问题的所有约束都是绝对约束，不满足这些约束条件的解称为非可行解，所以它们是硬约束。 以例2为例，如设备C和D严格禁止超时，故有：对

8、那些不严格限定的约束，连同原线性规划建模时的目标函数转化为的约束，均可通过目标约束来表达。下面是如何形成目标约束10(1) 将目标函数转化为目标约束在引入了目标值和正、负偏差变量后，可以将原目标函数加上负偏差变量 ，减去正偏差变量 ，并令其等于目标值，这样形成一个新的函数方程，把它作为一个新的约束条件，加入到原问题中去，称这种新的约束条件为目标约束。目标约束是一种将约束和目标结合在一起的表达式，是目标规划所特有的，它把约束右端项看作要求的目标值。比如：在实际计划工作中，利润指标往往是上级主管部门或工厂计划部门预先规定并要求实现的数值。以例2为例，力求利润指标不低于12千元，这就是目标值。而工厂

9、在安排了甲、乙两种产品的产量（决策）后，可能实现的利润额与规定的利润指标12千元之间会有一定差距，这个差距就是偏差变量。 这样就将目标函数则转化为目标约束11（2） 将系统约束转化为目标约束有时也可以根据需要将绝对约束转化为目标约束，这时只须将该约束的右端项看作目标值，再引入正、负偏差变量即可。如在例2中，考虑到市场需求，, 两种产品的生产量需保持1:1的比例；或此为系统约束在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束，在给定目标值和加入正、负偏差变量之后，可以将系统约束转化为目标约束。12（3）转化方法x1 x2 d 0当产品 产量多于产品 ，有x1x

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

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

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