运筹学基础-目标规划(1)课件

第五章、目标规划目标规划(Goalprogramming)是在线性规划基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个运筹学分支。目前研究较多的有线性目标规划、非线性目标规划、线性整数目标规划和0-1目标规划等。本章主要讨论线性目标规划，简称目标规划。

§5.1目标规划问题的提出与目标规划模型【引例1】某生物药厂需在市场上采购某种原料，现市场上有甲、乙两个等级，单价分别为2千元/kg和1千元/kg，要求采购的总费用不得超过20万元，购得原料的总重量不少于100kg，而甲级原料又不得少于50kg，问如何确定最好的采购方案（即用最少的钱、采购最多数量的原料）。目标函数为：一、问题的提出分析：这是一个含有两个目标的数学规划问题．设x1、x2分别为采购甲级、乙级原材料的数量（单位：kg），y1为花掉的资金，y2为所购原料总量．则：约束条件为：注：此规划模型是一个多目标规划模型【引例2】某企业生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四各不同设备上加工。生产每件产品Ⅰ需占用各设备为2、1、4、0小时，生产每件产品Ⅱ需占用各设备为2、2、0、4小时，各设备用于生产这两种产品的能力分别为12、8、16、12小时，又知生产一件产品Ⅰ获得2千元，生产一件产品Ⅱ获得3千元，问如何安排生产，使总的利润最大。则该问题的数学模型表示为

maxZ=

2x1+3x22x1+2x2≤12

x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0但企业通常的经营目标会更实际、更多样！这是一个线性规划模型企业的新目标：

力求使利润指标不低于12千元；

考虑到市场需求，Ⅰ,Ⅱ

两种产品的生产量需保持1:1的比例；

C和D为贵重设备，严格禁止超时使用；

设备B必要时可以加班，但加班时间要控制，设备A既要求充分利用，又尽可能不加班。等等这些目标通过线性规划无法实现【引例3】表4-1产品的资源、技术消耗定额、单位利润表甲（每件）乙（每件）现有资源钢材（kg）9.243600木材(m3)452000设备负荷（台小时）3103000单位产品利润(元)70120某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如下表所示．试确定计划期内的生产计划，使利润最大。分析:设x1、x2分别是计划期内甲、乙产品的产量．则该问题的数学模型为同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产，同时考虑这些问题，就形成多目标规划问题．分析：对于这样的多目标问题，线性规划很难为其找到最优方案．极有可能出现：第一个方案使第一目标的结果优于第二方案，而对于第二目标，第二方案优于第一方案．就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的。实践中，人们转而采取“不求最好，但求满意”的策略，在线性规划的基础上建立一种新的数学规划方法——目标规划．二、目标规划的基本概念1.目标值和正、负偏差变量

目标规划通过引入目标值和正、负偏差变量，可将目标函数转化为目标约束。所谓目标值是预先给定的某个目标的一个期望值。实现值（或决策值）是当决策变量x1、x2、…、xn选定以后目标函数的对应值。显然，实现值和目标值之间会有一定的差异，这种差异称为偏差变量(事先无法确定的未知量)，用d＋和d－表示。

当实际值超出目标值时，有d－＝0，d＋＞0；当实际值未达到目标值时，有d＋＝0，d－＞0；当实际值同目标值恰好一致时，d＋＝d－＝

0

。

因为在一次决策中，实现值不可能既超过目标值，同时又未达到目标值，所以有d＋与d－两者中必有一个为零。故恒有d＋×d－＝

0

d＋——超出目标的差值，称正偏差变量；

d－——未达到目标的差值，称负偏差变量；

2.绝对约束与目标约束

绝对约束又称系统约束，是指必须严格满足的等式和不等式约束，如线性规划问题的所有约束都是绝对约束，不满足这些约束条件的解称为非可行解，所以它们是硬约束。以例2为例，如设备C和D严格禁止超时，故有：对那些不严格限定的约束，连同原线性规划建模时的目标函数转化为的约束，均可通过目标约束来表达。下面是如何形成目标约束

(1)将目标函数转化为目标约束在引入了目标值和正、负偏差变量后，可以将原目标函数加上负偏差变量

，减去正偏差变量

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

这样就将目标函数则转化为目标约束

（2）将系统约束转化为目标约束

有时也可以根据需要将绝对约束转化为目标约束，这时只须将该约束的右端项看作目标值，再引入正、负偏差变量即可。如在例2中，考虑到市场需求，Ⅰ,Ⅱ两种产品的生产量需保持1:1的比例；或此为系统约束

在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束，在给定目标值和加入正、负偏差变量之后，可以将系统约束转化为目标约束。（3）转化方法

x1－

x2＋d－＝0当产品Ⅰ产量多于产品Ⅱ，有x1＞x2，即出现正偏差量d＋，若将x1减去这个正偏差量d＋，就有x1－x2－d＋＝0因正负偏差不可能同时出现，故合在有一起设为x1－x2＋

d－－d＋＝0由于允许有偏差，当产品Ⅰ产量小于产品Ⅱ，有x1＜x2，即出现负偏差量d－，若将x1加上这个负偏差量d－，就有3．目标规划的目标函数－－达成函数

凡满足目标约束和绝对约束的解，应如何判别它的优劣呢？从决策者的要求分析它总希望得到的结果与规定的目标值之间的偏差愈小愈好，由此决策者可根据自己的要求构造一个使总偏差量为最小的目标函数，这种函数就是目标规划的目标函数称为达成函数，记为

即达成函数是正、负偏变量的函数。

一般来说，可能提出的要求只能是以下三种情况之一，对应每种要求，可分别构造的达成函数是：

构造达成函数的方法如希望产品Ⅰ产量恰好等于产品Ⅱ的产量，即正、负偏变量都要尽可能地小，这时函数是：如希望产品Ⅰ产量低于产品Ⅱ的产量，即允许达不到目标值,就是正偏差变量要尽可能地小,即不希望上式中的d＋＞0，这时达成函数是：如希望产品Ⅰ产量不低于产品Ⅱ的产量，即要求超过目标值，但不得低于目标值，即必须是负偏差变量尽可能地小，不希望上式中的d－＞0，这时达成函数是：

又如中力求利润指标不低于12千元，达成函数为：设备B限制中必要时可以加班可表为：设备A限制中既要求充分利用，又尽可能不加班可表为：4.目标的优先级与权系数

在一个多目标决策问题中，要找出使所有目标都达到最优的解是很不容易的；在有些情况下，这样的解根本不存在(当这些目标是互相矛盾时)。实际作法是：决策者将这些目标分出主次，或根据这些目标的轻重缓急不同，区别对待。

在一个目标规划的模型中，如果两个不同目标重要程度相差悬殊，为达到某一目标可牺牲其它一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1，P2，…表示，并规定Pk＞＞Pk＋1，符号“＞＞”表示“远大于”，表示Pk与Pk＋1，不是同一各级别的量，即Pk与Pk＋1有更大的优先权。对属于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。5.满意解

目标规划问题的求解是分级进行的，首先要求满足P1级目标的解；然后再保证P1级目标不被破坏的