11月5日运筹学讲义第5章目标规划ppt课件

1、管理运筹学-管文科学方法中山大学南方学院工商管理系演讲：王甜源.2第5 章 目的规划Sub title学习要点 了解目的规划与线性规划的异同 了解目的约束中的正负偏向变量 思索目的约束与系统约束的差别 了解目的的优先级和目的权系数 了解目的规划图解法和单纯形法.3第一节 多目的规划问题一、线性规划的局限性线性规划的局限性只能处理一组线性约束条件下，某一目的而且只能是一个目的的最大或最小值的问题实践决策中，衡量方案优劣思索多个目的消费方案决策，通常思索产值、利润、满足市场需求等消费规划决策，思索运费、投资、供应、市场、污染等 这些目的中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性

2、的；有相互补充的，有相互对立的，LP那么无能为力目的规划Goal Programming 多目的线性规划含有多个优化目的的线性规划.4问题的提出：目的规划是在线性规划的根底上，为顺应经济管理多目的决策的需求而由线性规划逐渐开展起来的一个分支。由于现代化企业内专业分工越来越细，组织机构日益复杂，为了一致协调企业各部门围绕一个整体的目的任务，产生了目的管理这种先进的管理技术。目的规划是实行目的管理的有效工具，它根据企业制定的运营目的以及这些目的的轻重缓急次序，思索现有资源情况，分析如何到达规定目的或从总体上离规定目的的差距为最小。第5 章 目的规划.5第一节 多目的规划问题二、多目的规划的提出例：

3、甲乙产品的最优消费方案。产品资源甲乙现有资源 设备A2016设备B0210设备C3432单位利润 35解：线规划模型： maxZ=3x1+5x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0根据市场需求/合同规定：希望尽量扩展甲产品减少乙产品产量。又添加二个目的： maxZ1=3x1+5x2 maxZ2=x1minZ3=x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0 这些目的之间相互矛盾，普通的线性规划方法不能求解 .6第一节 多目的规划问题二、多目的规划的提出多目的线性规划模型的原始普通方式如下： n个决策变量，m个约束条件，L个目的函数。当L=1

4、时，即为我们熟习的单目的线性规划模型。.7例： 某企业方案消费甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。ABCD单件利润甲11402乙22043最大负荷1281612问该企业应如何安排方案，使得方案期内的总利润收入为最大？第一节 多目的规划问题.8解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：其最优解为x14，x22，z14元第一节 多目的规划问题.9但企业的运营目的不仅仅是利润，而且要思索多个方面，如：力求使利润目的不低于12元；思索到市场需求，甲、乙两种产品的消费量需坚持1:1的比例；C和D为贵重设备，严厉制止超时运用；设备B必

5、要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽能够不加班。要思索上述多方面的目的，需求借助目的规划的方法。第一节 多目的规划问题.10线性规划模型存在的局限性：1要求问题的解必需满足全部约束条件，实践问题中并非一切约束都需求严厉满足。2只能处置单目的的优化问题。实践问题中，目的和约束可以相互转化。3线性规划中各个约束条件都处于同等重要位置，但现实问题中，各目的的重要性即有层次上的差别，同一层次中又可以有权重上的区分。4线性规划寻求最优解，但很多实践问题中只需找出称心解就可以。第一节 多目的规划问题.11第一节 多目的规划问题三、多目的规划的解法加权系数法：为每一目的赋一权数，把多目

6、的转化成单目的。但权系数难以科学确定。 优先等级法：各目的按重要性归不同优先级而化为单目的。 有效解法：寻求能照顾到各目的而使决策者感到称心的解。但可行域大时难以列出一切有效解的组合。 目的规划法： 对每一个目的函数引入正的或负的偏向变量；引入目的的优先等级和加权系数。.12目的规划怎样处理前例线性规划模型建模中的局限性？1. 设置偏向变量，用来阐明实践值同目的值之间的差别。偏向变量用以下符号表示：d+超出目的的偏向，称正偏向变量d-未到达目的的偏向，称负偏向变量正负偏向变量两者必有一个为0。 当实践值超出目的值时： d+0, d-=0; 当实践值未到达目的值时： d+=0, d-0; 当实践

7、值同目的值恰好一致时： d+=0, d-=0;故恒有d+d-=0第一节 多目的规划问题.132. 一致处置目的和约束。 对有严厉限制的资源运用建立系统约束，数学方式同线性规划中的约束条件。如C和D设备的运用限制。 对不严厉限制的约束，连同原线性规划建模时的目的，均经过目的约束来表达。1例如要求甲、乙两种产品坚持1:1的比例，系统约束表达为：x1=x2。由于这个比例允许有偏向，当x1x2时，出现正偏向d+，即： x1-d+ =x2或x1x2-d+ =0第一节 多目的规划问题.14正负偏向不能够同时出现，故总有：x1x2+d-d+ =0 假设希望甲的产量不低于乙的产量，即不希望d-0,用目的约束可

8、表为: 假设希望甲的产量低于乙的产量，即不希望d0,用目的约束可表为: 假设希望甲的产量恰好等于乙的产量，即不希望d0,也不希望d-0用目的约束可表为:第一节 多目的规划问题.153设备B必要时可加班及加班时间要控制，目的约束表示为：2力求使利润目的不低于12元，目的约束表示为：4设备A既要求充分利用，又尽能够不加班，目的约束表示为：第一节 多目的规划问题.163. 目的的优先级与权系数在一个目的规划的模型中，为到达某一目的可牺牲其他一些目的，称这些目的是属于不同层次的优先级。优先级层次的高低可分别经过优先因子P1,P2,表示。对于同一层次优先级的不同目的，按其重要程度可分别乘上不同的权系数。

9、权系数是一个个详细数字，乘上的权系数越大，阐明该目的越重要。现假定： 第1优先级P1企业利润； 第2优先级P2甲乙产品的产量坚持1:1的比例 第3优先级P3设备A充分利用但尽量不超负荷任务,设备B尽量不超负荷任务。其中设备A的重要性比设备B大三倍。第一节 多目的规划问题.17上述目的规划模型可以表示为：第一节 多目的规划问题.18目的规划数学模型的普通方式达成函数目的约束其中：gk为第k个目的约束的预期目的值， 和 为pl 优先因子对应各目的的权系数。第一节 多目的规划问题.19目的规划问题及其数学模型总结：用目的规划求解问题的过程：明确问题，列出目的的优先级和权系数构造目的规划模型求出称心解

10、称心否？分析各工程标完成情况据此制定出决策方案NY.20第二节 目的规划的数学模型一、目的期望值每一个目的希望到达的期望值(或目的值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。二、偏向变量目的约束目的的实践值和期望值之间能够存在正的或负的偏向。 正偏向变量dk+ 表示第k个目的超越期望值的数值；负偏向变量dk- 表示第k个目的未到达期望值的数值。同一目的的dk+ 和dk- 中至少有一个必需为零。引入正负偏向变量，对各个目的建立目的约束(软约束)总结：用目的规划求解问题的过程：.21第二节 目的规划的数学模型 假设对PPT第5页例题做出如下要求：目的一是利润最大，拟定利润目的是3

11、0；目的二是减少乙产品产量但希望不低于4件；目的三是甲产品产量希望不少于6件 ；对各目的引入正、负偏向变量： 3x1+5x2 +d1- d1+ = 30 x2 +d2- - d2+ =4 x1 +d3 -d3+ = 6.22第二节 目的规划的数学模型三、目的达成函数目的达成函数：偏向变量之和为最小值。假设要求尽能够到达规定的目的值正负偏向变量dk+ , dk- 都尽能够小，即minSk=dk+dk- 假设希望尽能够不低于期望值(允许超越)负偏向变量dk- 尽能够小,不关怀超出量dk+ ：minSk= dk- 假设允许某个目的低于期望值，但希望不超越正偏向变量dk+尽能够小,不关怀低于量dk-

12、：minSk= dk+ 四、优先等级权数目的重要度不同，用优先等级因子Pk 表示第k等级目的。优先等级因子Pk 是正的常数， Pk Pk+1 。同一优先等级下目的的相对重要性赋以不同权数w。总结：用目的规划求解问题的过程：.23第二节 目的规划的数学模型对PPT第五页例题而言，假设：P1 级目的实现利润至少30元； P2级目的是甲乙产品的产量 假设：乙产品产量不少于4件比甲产品产量不少于6件更重要，取其权重为2 目的规划为：minG= P1 d1- + P2(2d2- + d3- ) 3x1+5x2 +d1- d1+ = 30 x2 +d2- - d2+ = 4 x1 + d3- - d3+

13、= 6 x1 , x2 ,dk- , dk+ 0(k=1,2,3).24目的规划的图解法：适用两个变量的目的规划问题，但其操作简单，原理一目了然。同时，也有助于了解普通目的规划的求解原理和过程。图解法解题步骤：1. 将一切约束条件包括目的约束和绝对约束，暂不思索正负偏向变量的直线方程分别标示于坐标平面上。2. 确定系统约束的可行域。3. 在目的约束所代表的边境限上，用箭头标出正、负偏向变量值增大的方向第三节 目的规划的图解法.253. 求满足最高优先等级目的的解4. 转到下一个优先等级的目的，再不破坏一切较高优先等级目的的前提下，求出该优先等级目的的解5. 反复4，直到一切优先等级的目的都已审

14、查终了为止6. 确定最优解和称心解。第三节 目的规划的图解法.26 例2：装配两种型号的笔记本，每台需配备时间1小时，每周任务5天，方案开动8小时/天。 估计每周销售型号I24台,利润80元/台，型号II30台,利润40元/台。该厂目的如下：充分利用装配线，防止开工缺乏允许装配线加班，但加班时间尽能够短，但不超越10小时尽量满足市场需求，重要性和利润成正比每周的利润5000以上 请合理安排任务义务建立目的规划的模型：第三节 目的规划的图解法.27第三节 目的规划的图解法目的规划的图解法首先，按照绝对约束画出可行域，其次，不思索正负偏向变量，画出目的约束的边境限，最后。按优先级别和权重依次分析各

15、级目的。F2x1 =162x2 =10BCx14A103x1 +4 x2 =326x20D2642EGH称心解：x1=5, x2=4.28补充例1： 用图解法求解以下目的规划问题第三节 目的规划的图解法.29(a)(b)(c)(d )x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+称心解(3,3)04683462 2第三节 目的规划的图解法.30 x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD称心解是线段GD上恣意点其中G点X(2,4),D点X(10/3,10/3)05.51055.6112,410/3,10/35107课堂练习：第三节 目的规划的

16、图解法.称心解X=(24，26)作业：第三节 目的规划的图解法.32目的规划运用举例补充例2： 知一个消费方案的线性规划模型如下，其中目的函数为总利润，x1,x2 为产品A、B产量。其中乙资源和丙资源为稀缺资源现有以下目的：1. 要求总利润必需超越 2500 元；2. 思索产品受市场影响，为防止积压，A、B的消费量不超越 60 件和 100 件；产品 A,B 的单件利润比 2.5 :1 为权系数3. 由于甲资源供应比较紧张，尽量不要超越现有量140。试建立目的规划模型，并用图解法求解。.33目的规划运用举例解：以产品 A,B 的单件利润比 2.5 :1 为权系数，模型如下：.34目的规划运用举

17、例0 x2 0 x114012010080604020 20 40 60 80 100ABCDC(60 ,58.3)为所求的称心解。(24,26).35第四节 目的规划的单纯形法了解目的规划与线性规划的数学模型的构造类似可用前述单纯形算法求解目的规划模型： 将优先等级Pk视为正常数(大法 )正负偏向变量dk+、dk-视为松弛变量以负偏向变量dk-为初始基变量，建立初始单纯形表检验数的计算与LP单纯形法一样，即j= cj - CBi Pj 最优性判别准那么类似于LP的单纯形算法：检验数普通是各优先等级因子的代数和判别检验数的正负和大小 .36第五节 目的规划的运用案例一、无穷多称心解解：设x1,

18、x2表示A、B产品的产量。两个等级的目的：P1：充分利用电量限额，正负偏向之和为最小 目的达成函数 目的约束条件 P2 ：利润额希望不能低于100元，负偏向最小 目的达成函数 目的约束条件 方案消费两种产品，首先要充分利用设备工时而不加班；然后思索利润不低于100元。问应如何制定产品A、B的产量。.372A24BDx26810 x1第五节 目的规划的运用案例一、无穷多称心解由于资料供应限量为8单位，所以有系统约束条件，如下该问题的目的规划模型如下，图解法求解如图CG.38第五节 目的规划的运用案例二、加班时间问题例：某音像店有5名全职售货员和4名兼职售货员，全职售货员每月任务160小时，兼职售

19、货员每月任务80小时。根据记录，全职每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元。如今预测下月CD销售量为27500张，商店每周开门营业6天，所以能够要加班。每出卖一张CD盈利1.5元。 商店经理以为，坚持稳定的就业程度加上必要的加班，比不加班就业程度要好，但全职销售员假设加班过多，就会由于疲劳过度而呵斥效率下降，因此不允许每月加班超越100小时，建立相应的目的规划模型。.39第五节 目的规划的运用案例二、加班时间问题首先，确定目的约束的优先级。如下：P1：下月的CD销售量到达27500张；P2：全职售货员加