物流运筹学课件56剖析

《物流运筹学课件56剖析》由会员分享，可在线阅读，更多相关《物流运筹学课件56剖析（148页珍藏版）》请在金锄头文库上搜索。

1、物流运筹学 Logistics Operational Research,物流管理专业基础课程,郭淑红 guoshuhong_1982 13074553453,Chapter5 目标规划 ( Goal programming ),目标规划问题及其数学模型 目标规划的解法 目标规划应用举例,本章主要内容：,第一节 目标规划问题及其数学模型,一、目标规划问题的提出,第一节 目标规划问题及其数学模型,（一）线性规划模型存在的局限性 1.要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。 2.只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。 3.线性规划中各个约束条

2、件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。 4.线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。,第一节 目标规划问题及其数学模型,目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。 由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。,(二）目标

3、规划简介,第一节 目标规划问题及其数学模型,(一）一般多目标规划问题举例,二、目标规划问题的数学模型,第一节 目标规划问题及其数学模型,（二）多目标线性规划模型的原始一般形式,n个决策变量， m个约束条件， L个目标函数。 当L=1时，为我们熟悉的单目标线性规划模型。,第一节 目标规划问题及其数学模型,（三）多目标规划的解法,加权系数法 为每一目标赋一权数，把多目标转化成单目标。 但权系数难以科学确定。 优先等级法 各目标按重要性归不同优先级而化为单目标。 有效解法 寻求能照顾到各目标而使决策者感到满意的解。 但可行域大时难以列出所有有效解的组合。 目标规划法 对每一个目标函数引入正的或负的偏

4、差变量； 引入目标的优先等级和加权系数。,第一节 目标规划问题及其数学模型,第一节 目标规划问题及其数学模型,例5.1 某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。,问该企业应如何安排计划，使得计划期内的总利润收入为最大？,第一节 目标规划问题及其数学模型,解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：,其最优解为x14，x22，z14元,第一节 目标规划问题及其数学模型,但企业的经营目标不仅仅是利润，而且要考虑多个方面，如： 力求使利润指标不低于12元； 考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例； C和

5、D为贵重设备，严格禁止超时使用； 设备B必要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽可能不加班。,要考虑上述多方面的目标，需要借助目标规划的方法。,第一节 目标规划问题及其数学模型,目标规划怎样解决上述线性规划模型建模中的局限性？,1. 设置偏差变量，用来表明实际值同目标值之间的差异,偏差变量用下列符号表示：,d+超出目标的偏差，称正偏差变量 d-未达到目标的偏差，称负偏差变量,正负偏差变量两者必有一个为0。 当实际值超出目标值时： d+0, d-=0; 当实际值未达到目标值时： d+=0, d-0; 当实际值同目标值恰好一致时： d+=0, d-=0; 故恒有d+d-=0,第

6、一节 目标规划问题及其数学模型,2. 统一处理目标和约束,对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如C和D设备的使用限制。,对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。,1）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为： x1=x2。由于这个比例允许有偏差， 当x1x2时，出现正偏差d+，即： x1-d+ =x2或x1x2-d+ =0,第一节 目标规划问题及其数学模型,正负偏差不可能同时出现，故总有： x1x2+d-d+ =0,若希望甲的产量不低于乙的产量，即不希望d-0,用目标约束表示:,若希望甲的产量低于乙的产量，即不希望d0

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

8、的权系数越大，表明该目标越重要。,现假定：,第1优先级P1企业利润； 第2优先级P2甲乙产品的产量保持1:1的比例 第3优先级P3设备A,B尽量不超负荷工作。其中设备A的重要性比设备B大三倍。,第一节 目标规划问题及其数学模型,上述目标规划模型可以表示为：,例5.2：装配两种型号的笔记本，每台需装备时间1小时，每周工作5天，计划开动8小时/天。预计每周销售型号I为24台,利润80元/台，型号II为30台,利润40元/台。该厂目标如下： 充分利用装配线，避免开工不足 允许装配线加班，但加班时间尽可能短 尽量满足市场需求 每周的利润尽可能大 请合理安排工作任务,建立目标规划的模型：,第一节 目标规

9、划问题及其数学模型,第一节 目标规划问题及其数学模型,目标规划数学模型的一般形式,达成函数,目标约束,其中：gk为第k个目标约束的预期目标值， 和 为pl 优先因子对应各目标的权系数。,系统约束,第一节 目标规划问题及其数学模型,用目标规划求解问题的过程：,明确问题，列出目标的优先级和权系数,构造目标规划模型,求出满意解,满意否？,分析各项目标完成情况,据此制定出决策方案,N,Y,第二节 目标规划的解法,一、目标规划的图解法,适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。,（一）图解法解题步骤,1. 将所有约束条件（包括目标约束和绝对约

10、束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。 2. 确定系统约束的可行域。 3. 在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向,第二节 目标规划的解法,3. 求满足最高优先等级目标的解 4. 转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解 5. 重复4，直到所有优先等级的目标都已审查完毕为止 6. 确定最优解和满意解。,对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。 对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。,第二节 目标规划的解法,例5.3 用图解法求解下列目标规划问题

11、,第二节 目标规划的解法,(a),(b),(c),(d ),x2,x1,(e),(f),d1-,d1+,d2+,d2-,d3-,d3+,d4-,d4+,满意解(3,3),0,4,6,8,3,4,6,2,2,第二节 目标规划的解法,x1,x2,(a),(b),d1+,d1-,(c),d2-,d2+,(d),d3-,d3+,G,D,满意解是线段GD上任意点,其中G点X(2,4),D点X(10/3,10/3),0,5.5,10,5,5.6,11,2,4,10/3,10/3,5,10,7,例5.4,第二节 目标规划的解法,O,x1,x2,20,40,60,50,20,40,60,50,a,b,d1-,

12、d1+,d2-,d2+,c,d,d3-,d3+,d4-,d4+,(24,26),满意解X=(24，26),例5.5,F,G,H,满意解：x1=5, x2=4,例5.6 图解法求目标规划的满意解,第二节 目标规划的解法,例5.7 图解法求目标 规划的满意解,第二节 目标规划的解法,例5.8 图解法求目标规划的满意解,第二节 目标规划的解法,二、目标规划的单纯形法,目标规划与线性规划的数学模型的结构相似 可用前述单纯形算法求解目标规划模型： 将优先等级Pk视为正常数(大法 ) 正负偏差变量dk+、dk-视为松弛变量 以负偏差变量dk-为初始基变量，建立初始单纯形表 检验数的计算与LP单纯形法相同，

13、即j= cj - CBi Pj 最优性判别准则类似于LP的单纯形算法： 检验数一般是各优先等级因子的代数和 判断检验数的正负和大小,第二节 目标规划的解法,例5.9： 用单纯形法求解目标规划,第二节 目标规划的解法,第二节 目标规划的解法,第二节 目标规划的解法,第二节 目标规划的解法,第二节 目标规划的解法,第二节 目标规划的解法,第二节 目标规划的解法,第二节 目标规划的解法,第二节 目标规划的解法,第二节 目标规划的解法,计算结果:,第二节 目标规划的解法,第三节 目标规划应用举例,例5.10 已知一个生产计划的线性规划模型如下，其中目标函数为总利润，x1,x2 为产品A、B产量。,现有

14、下列目标： 1. 要求总利润必须超过 2500 元； 2. 考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3. 由于甲资源供应比较紧张，不要超过现有量140。 试建立目标规划模型，并用图解法求解。,第三节 目标规划应用举例,解：以产品 A,B 的单件利润比 2.5 :1 为权系数，模型如下：,第三节 目标规划应用举例,0,x2,0,x1,140 120 100 80 60 40 20,20 40 60 80 100,A,B,C,D,C(60 ,58.3)为所求的满意解。,(24,26),例5.11 无穷多满意解,解：设x1,x2表示A、B产品的产量。两个等级的

15、目标： P1：充分利用电量限额，正负偏差之和为最小 目标达成函数 目标约束条件 P2 ：利润额希望不能低于100元，负偏差最小 目标达成函数 目标约束条件,计划生产两种产品，首先要充分利用设备工时而不加班；然后考虑利润不低于100元。问应如何制定产品A、B的产量。,第三节 目标规划应用举例,由于材料供应限量为8单位，所以有系统约束条件，如下,该问题的目标规划模型如下，图解法求解如图,C,G,目标规划应用举例,加班时间问题,例5.12：某音像店有5名全职售货员和4名兼职售货员，全职售货员每月工作160小时，兼职售货员每月工作80小时。根据记录，全职每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元。现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班。每出售一张CD盈利1.5元。 商店经理认为，保持稳定的就业水平加上必要的加班，比不加班就业水平要好，但全职销售员如果加班过多，就会因为疲劳过度而造成效率下降，因此不允许每月加班超过100小时，建立相应的目标规划模型。,目标规划应用举例,首先，确定目标约束的优先级。如下： P1：下月的CD销售量达到27500张； P