运筹学之目标规划（胡运权版）

第七章目标规划1提交目标计划线性规划问题是考虑给定线性目标函数的线性约束集中的最大值或最小值问题。 针对实际问题，管理科学家根据管理层决策目标的要求，首先决定目标函数来衡量不同决策的优劣，根据实际问题的资源、资金和环境等因素提出决策约束来构建线性规划模型，然后利用计算机软件寻求最佳方案，为管理层决策提供灵敏度分析在一些问题中，决策目标往往也可能存在与模型相冲突的限制，而现有线性规划的理论和方法无法解决。 为此，1961年美国学者查尔斯(A.Charnes )和库珀(W.W.Coopor )提出了目标规划的概念和数学模型，解决了经济管理中的多目标决策问题。通过一些实例说明实际应用程序中线性规划存在一系列限制。例1在某工厂生产a、b两种产品所需劳动力分别为4人和6人，所需设备单位台均为1人。 如果知道这个工厂有10个机台，制造这两种产品，至少能提供70人工。 另外，a、b产品的利润分别为300元和500元。 问：这个工厂要分别生产几个a、b产品，才能使利润值达到最大？如果把这个工厂能够生产a、b产品的数量分别作为零部件的话解法如下解决由以上图可知，满足制约条件的可执行解集由于时序制约与人工制约之间产生矛盾，因此无法解决此问题。 但是，实际上，这个工厂为了增加利润，不能不生产a、b两种产品。 线性规划模型找不到适合它的方案。例2某厂为了生产需要购买a和b两种原材料，单价分别为70元/公斤和50元/公斤。 目前，采购资金要求在5000元以下，总采购量在80公斤以上，a原材料要求在20公斤以上。 如何决定最佳采购方案(即费用最高，购买总量最多)解这是一道包含两个目标的数学规划题。 作为购买2种原材料的公里数，作为消费资金购买的总量。 建立此问题的数学模型的格式如下：对于这样的多目标问题，线性规划很难找到最佳方案。 尽可能的结果是，第一种情形或者第一目标的结果值可以比第二种情形好，第二种情形或者第二目标的结果值可以比第一种情形好。 也就是说，很难找到使两个目标的函数值同时最佳化的最佳方案。 另外，在多目标问题中，存在多个目标不同的重要度因素，这也是线性计划所不能解决的。根据线性规划，确立新的数学规划方法的目标规划法，以补偿上述线性规划的界限。 目标规划与定线规划的差异通常反映在以下方面1 .线性规划只能处理一个目标，但现实问题存在很多目标。 目标规划可以综合考虑和处理多个目标的关系，求出符合实际需求的解。2 .线性规划求满足所有约束条件的最优解。 在实际问题上，存在矛盾的制约条件，有可能没有可行的解，但在此时生产必须继续。 即使有可能的解，在实际问题上也不一定要求最佳解。 目标计划是通过找到满意的解，即使在相互矛盾的制约条件下，也尽量找到满足制约的满意的解，即满意的方案。3、线性规划的制约条件主要是同等处理，这也不符合实际情况。 目标计划可以根据实际需要排列优先顺序。二目标规划的基本概念与数学模型2.1基本概念本节介绍有关目标规划的基本概念。1 .偏差变量在例1中，没有解的关键是制约条件不灵活。 假设“放松”约束条件，例如，如果占用的人数不足70人，时序约束和人工约束就不会矛盾。 在此基础上，导入正负偏差的概念，表示决策值和目标值的差异。正偏差变量指示决策值超过目标值的一部分并在目标规划中规定在目标规划中规定负偏差变量，其指代决策值尚未达到目标值的部分。事实上，如果确定了目标值(即计划利润值)，可能会发生以下三种情况之一(一)决策值超过目标值(即达到或超过计划利润)的；(2)表示决策值未达到目标值(即计划利润值未完成)(3)决策值表现为与目标值正好相等(即正确完成了计划利益指标)。在以上的三种情况下，任意一种情况下=0。2 .绝对约束和目标约束绝对约束也称为系统约束，是指必须严格满足线性规划模型约束的等式约束和不等式约束。目标约束是目标计划所固有的。 确定目标值并作出决策后，允许与目标值有正或负偏差。 因此，目标约束加上了正、负偏差变量。例如，在示例1中，假定企业的计划收益值为5000元，并且对目标函数求解的双曲馀弦值的双曲馀弦值。此表达式表示决策值与目标值5000之间可能存在正偏差或负偏差(请从上述三种情况了解)。如果需要，也可以将绝对约束转换为目标约束。 此时，将求出制约右端项的目标值视为。 例如，示例1的绝对约束可以转换为目标约束。3 .目标规划的目标函数对于满足绝对制约和目标制约的所有解，从决策者的观点出发，判断优劣的依据是决策值和目标值的偏差越小越好。 因此，目标计划的目标函数是与正、负偏差变量密切相关的函数，我们表示如下。 有三种基本形式：(1)要求正好达到目标值，即正、负偏差变量尽可能小。 在这种情况下，构建目标函数如下所示(2)要求不超过目标值，即不达到目标值，正偏差变量尽可能小。 在这种情况下，构建目标函数如下所示(3)超过目标值，即超过量没有限定，要求负的偏差变量尽可能小。 在这种情况下，构建目标函数如下所示4 .优先级系数和权重系数一个计划问题有很多目标。 决策者在实现这些目标时，有主要优先顺序和优先顺序的不同。 对于阶级目标问题，根据优先级分别提供不同大小的系数：和无穷大的正数(符号意味着“远大”)，这意味着在达到某一级别的目标后，即只有在目标值为0时才忽略大的影响，否则由于很大的原因导致目标偏移量而且，必须在考虑忽视影响(实现一级目标)之后再考虑一级目标。 实际上，这里的大小是偏离目标值的处罚系数，优先度越高处罚系数越大。加权因子用于区分具有相同优先级的若干目标。 如果多个目标可被包括在相同的优先级中并且这些正负偏差变量之间存在重要性差，则可以给正负偏差变量提供不同的加权因子和。决策者在具体情况下给出各级目标的优先顺序和权重系数的决定。2.2目标规划的数学模型如上所述，目标规划模型由目标函数、目标约束、绝对约束以及变量非负约束等几个部分构成。 目标规划的一般数学模型如下：目标函数目标约束绝对约束非负约束例3例1中，目标利润在15000元以上，假设是第一目标占有的人员不足70人，可以作为第二目标。 征求决策草案。解根据决策者的要求给两个目标提供较大的系数。 模型包括：例4某纺织厂生产a、b两种面料，平均生产能力为1公里/小时，工厂正常生产能力为80小时/周。 此外，a面料每千米利润2500元，b面料每千米利润1500元。 已知a、b两种面料每周的市场需求量分别为70公斤和45公斤。 现在这家工厂已经确定了一周内的目标第一优先级：避免生产开始不足第二优先级：加班时间不超过10小时第三优先级：根据市场需求达到最大销售量第四优先级：尽量减少加班时间。试试这个问题的最佳方案吧。解分别为甲、乙生产面料的时数。 对于第三优先目标，从a、b的生产利润的比率来看，两者达到最大销售量的权重系数分别为5和3。 该问题的目标规划模型如下：如上所述，目标计划要创建模型，请执行以下操作1 .根据问题提出的各项目标和条件，确定目标值，列举目标约束和绝对约束2 .根据决策者的需要，将一些或所有绝对约束转换为目标约束的方法是将负偏差变量添加到绝对约束的左表达式中，然后减去正偏差变量3、给每个级别的目标提供相应的惩罚系数()，无穷大的正数，并且4 .对于相同优先级的各目标，根据其重要度，给出相应的权重系数5、根据决策者的要求，各目标在三种情况下取值。 正确达到目标值时，允许超过目标值时，允许不超过目标值时，取出处罚系数、加权系数和偏差变量，构建要求最小化的目标函数。3解决目标计划3.1图式解法只有两个决策变量的目标规划数学模型可用简单直观的解法求解。 该方法类似于线性规划解法，首先在平面直角坐标系的第一象限中制作各约束式或不等式的图像，根据绝对约束决定可行区域，根据目标约束和目标函数决定最佳解和满意解。绝对约束与线性规划中的约束绘制法完全相同。 对于目标约束方程，除了建立直线之外，还需要在直线上指示正负偏差变量的方向，其可能区域的方向依赖于目标函数中的对应目标。 而且，考虑到下一级目标(如果满足了先前级别的目标)，目标计划很可能折衷将来获得的最佳解的满意解，而不是可执行解(即，不是可执行解)。 因此，目标计划中求得的解称为满足解。求解时，请注意将绝对约束作为最高层来考虑。例5用图解法求解目标规划问题解在平面正交坐标系的第一象限中制作各约束的图像，目标约束必须在直线的旁边加上di。首先，绝对约束决定了可能的解的范围在三角形OEF内根据一级目标，由于要求实现，可能实现的解的范围被缩小到线段OC对于次级目标，要求实现，在线段OC上获得的点a将在那时的可能解的范围缩小到线段AC上根据第三层次的目标，为了实现该目标，在线段a-c上，取得的点b，此时解的范围缩小至线段a-b上。因此，线段AB上的所有点都是满意解。 可以求出a (15/8，15/8 )、b (24/7，24/7 )。用图解法求解例6例4的目标规划模型。解在平面正交坐标系的第一象限中创建对应于各约束条件的图像，并在目标约束直线的旁边加和。根据第一级目标，目标函数要求实现，解的范围是线段AC的右上区域根据二级目标，目标函数要求实现，并且解的范围被缩小到四边形ABDC中的区域根据第三级目标，目标函数要求实现并且首先考虑，将解的范围缩小到四边形ABFE内的区域，并且进一步考虑，不能满足四边形ABFE内的所有点。 在该情况下，认为在可能的区域ABFE内达到最小的满足点f，不满足f点，但那是最满足第三级目标的满足解根据第四目标，由于目标函数要求实现，解的范围已经缩小到点f，唯一的点f也是最满足第四目标的满足解。由此，将该问题的满足解作为点f，能够求出f (70，20 )。图形化解决步骤如下1、在直角坐标系的第一象限中制作绝对约束和目标约束的图像，确定绝对约束可解的区域，在目标约束直线上用箭头表示正负偏差变量值增大的方向(正负偏差变量增大的方向相反)。2 .在可能解的领域，寻求满足最高优先级目标的解3 .向下一个优先顺序的目标转移，在满足上一个优先顺序的目标的前提下，求出满足该顺序的目标的解4、重复3，直到所有优先级目标得到审查5 .确定最优解或满意解。3.2单纯型法目标规划是线性规划的推进和发展，其数学模型结构和线性规划的数学模型结构没有本质差异，求解线性规划的简单形式也同样是目标规划的解决方法。 目标计划加上大的m罚系数，用大的m法求解。 这里不举例。要用简单的形式求解目标计划，迭代结束有两种情况。 当一个检验常数都不为负时，得到的解将所有的目标偏差量设为0，该解为最佳解。 另一个是，在所有的检验常数都为非负的情况下，所有的目标都达不到最佳值，但是达到最佳目标值的必然是优先顺序较高，此时得到的解是满足解。 例如，可知用4单纯形法求出的满足解，求出的解没有优化第三级和第四级的目标，但优化第一、第二级的目标与先前用图式法求出的结果一致。3.3 EXCEL电子表格法目标计划也可以通过EXCEL求得满意解。 重要的是如何创建电子表格模型。例7例4的目标计划模型用EXCEL求解。让我们看一下如何为示例4中的目标规划问题创建电子表格模型。 参见图7-4。图7图4小区(B5:C8)实际上是决策变量在目标规划数学模型中的系数，并且可以被理解为对每个对应元素的贡献。 如果小区B5对产品1的开工时间有贡献，则生产1公斤的a坯料，使开工时间增加1。d列计算决策变量对每个元素的贡献度总和。 在单元格D5为总开始时间的情况下，根据公式SUMPRODUCT(B5:C5，B9:C9)进行计算。(B9:C9)是可变单元，(G5:H8)是额外的可变单元。g、h、I、k列是该模型的微妙位置。 g列和h列分别表示实际正负偏差的值。 I列是根据数学模型的目标约束方程式计算出的左端的值。 如果单元格I5是第一个目标约束方程的最左边的值，则从D5-G5 H5计算。单元格G10是目标单元格，是每个元素未达到目标的总偏差(总处罚数)。 然而应当注意的是，例如，仅当负偏差大于0时才出现处罚。 只有当正偏差大于0时，相同级别2的目标才会受到处罚。 这样类推。 在此，决策者根据情况给出各级目标的处罚系数，本问题给出的假定处罚系数参照小区G10的计算公式。 请注意，目标级别越高，处罚因子越大。 目标是最小化总罚款数。在“计划计算参数”对话框中，指定目标单元格、可变单元格和约束条件。 约束是使目标约束表达式的两端相等。由于线性规划仍然存在问题，因此必