《理学运筹学基础目标规划复习进程.ppt》由会员分享，可在线阅读，更多相关《理学运筹学基础目标规划复习进程.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、理学运筹学基础目标规划引例2某企业生产、两种产品。这两种产品都要分别在A、B、C、D四各不同设备上加工。生产每件产品需占用各设备为2、1、4、0小时，生产每件产品 需占用各设备为2、2、0、4小时，各设备用于生产这两种产品的能力分别为12、8、16、12小时，又知生产一件产品获得2元，生产一件产品 获得3元，问如何安排生产，使总的利润最大。则该问题的数学模型表示为则该问题的数学模型表示为则该问题的数学模型表示为则该问题的数学模型表示为 maxZ=2x1+3x2 2x1+2x2 12 x1+2x2 8 4x1 164x2 12 x1 0,x2 0但企业通常的经营目标会更实际、更多样！但企业通常的
2、经营目标会更实际、更多样！但企业通常的经营目标会更实际、更多样！但企业通常的经营目标会更实际、更多样！这是一个线性规划模型这是一个线性规划模型企业的新目标：企业的新目标：力求使利润指标不低于12元；考虑到市场需求，,两种产品的生产量需保持1:1的比例；C和D为贵重设备，严格禁止超时使用；设备B必要时可以加班，但加班时间要控制，设备A既要求充分利用，又尽可能不加班。等等这些目标通过线性规划无法实现这些目标通过线性规划无法实现这些目标通过线性规划无法实现这些目标通过线性规划无法实现引例3表表4-1 产品的资源、技术消耗定额、单位利润表产品的资源、技术消耗定额、单位利润表甲（每件）甲（每件）乙（每件
3、）乙（每件）现有资源现有资源钢钢 材材 （kg）9.243600木木 材材 (m3)452000设备负荷（台小时）设备负荷（台小时）3103000单位产品利润单位产品利润(元元)70120某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如下表所示试确定计划期内的生产计划，使利润最大。分析:设x x1 1、x x2 2分别是计划期内甲、乙产品的产量则该问题的数学模型为 同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产，同时考虑这些问题，就形成多目标规划问题分析：对于这样的多目标问题，线性规划很难为其找到最优方案极有可能出现：第一个方案使第一目标
4、的结果优于第二方案，而对于第二目标，第二方案优于第一方案就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的。实践中，人们转而采取“不求最好，但求满意”的策略，在线性规划的基础上建立一种新的数学规划方法目标规划目标规划与线性规划相比，有以下优点：目标规划与线性规划相比，有以下优点：1.1.1.1.线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题2.2.2.2
5、.线性规划是在满足所有约束条件的可行解中求得最优解。线性规划是在满足所有约束条件的可行解中求得最优解。线性规划是在满足所有约束条件的可行解中求得最优解。线性规划是在满足所有约束条件的可行解中求得最优解。实际问题中，往往要考虑多个目标的决策问题，这些目标可能互相矛盾，也可能没有统一的度量单位，很难比较。目标规划就能够兼顾地处理多种目标的关系，求得更切合实际的解。而在实际问题中往往存在一些相互矛盾的约束条件，如何在这些相互矛盾的约束条件下，找到一个满意解就是目标规划所要讨论的问题。3.3.3.3.线性规划问题中的约束条件是不分主次、同等对待的线性规划问题中的约束条件是不分主次、同等对待的线性规划问
6、题中的约束条件是不分主次、同等对待的线性规划问题中的约束条件是不分主次、同等对待的 线性规划问题是一律要满足的“硬约束”。而在实际问题中，多个目标和多个约束条件不一定是同等重要的，而是有轻重缓急和主次之分的，如何根据实际情况确定模型和求解，使其更合实际是目标规划的任务。4.4.4.4.线性规划的最优解可以说是绝对意义下的最优线性规划的最优解可以说是绝对意义下的最优线性规划的最优解可以说是绝对意义下的最优线性规划的最优解可以说是绝对意义下的最优 为求得这个最优解，往往要花去大量的人力、物力和才力。而在实际问题中，却并不一定需要去找这种最优解。目标规划所求的满意解是指尽可能地达到或接近一个或几个已
7、给定的指标值，这种满意解更能够满足实际的需要。目标规划更能够确切描述和解决经济管理中的许多实际问题。目前目标规划的理论和方法已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到广泛的应用。二、目标规划的基本概念二、目标规划的基本概念1.1.目标值和正、负偏差变量目标值和正、负偏差变量目标值和正、负偏差变量目标值和正、负偏差变量 目标规划通过引入目标值目标值和正、负偏差变量正、负偏差变量，可将目标函数目标函数转化为目标约束目标约束。所谓目标值目标值是预先给定的某个目标的一个期望值。实现值实现值（或决策值）是当决策变量x1、x2、xn选定以后目标函数的对应值。显然，实现值实现值和目标值
8、目标值之间会有一定的差异，这种差异称为偏差变量偏差变量(事先无法确定的未知量)，用d d和d d表示。当实际值实际值超出目标值目标值时，有d0，d0；当实际值实际值未达到目标值目标值时，有d0，d0；当实际值实际值同目标值目标值恰好一致时，d d 0。因为在一次决策中，实现值不可能既超过目标值，同时又未达到目标值，所以有 d与d两者中必有一个为零。故恒有d d 0 d d超出目标的差值，称正偏差变量超出目标的差值，称正偏差变量；d d未达到目标的差值，称负偏差变量未达到目标的差值，称负偏差变量；2.2.绝对约束与目标约束绝对约束与目标约束绝对约束绝对约束绝对约束绝对约束又称系统约束，是指必须严
9、格满足的等式和不等式约束，如线性规划问题的所有约束都是绝对约束，不满足这些约束条件的解称为非可行解，所以它们是硬约束。以例2为例，如设备C和D严格禁止超时，故有：对那些不严格限定的约束，连同原线性规划建模时的目标目标函数函数转化为的约束，均可通过目标约束目标约束目标约束目标约束来表达。下面是如何形成目标约束目标约束目标约束目标约束(1)(1)将将目标函数目标函数转化为目标约束转化为目标约束在引入了目标值和正、负偏差变量后，可以将原目标函数加上加上负偏差变量负偏差变量，减去正偏差变量减去正偏差变量，并令其等于目标值，这样形成一个新的函数方程，把它作为一个新的约束条件，加入到原问题中去，称这种新的
10、约束条件为目标约束目标约束。目标约束是一种将约束和目标结合在一起的表达式，是目标规划所特有的，它把约束右端项看作要求的目标值目标值。比如：在实际计划工作中，利润指标往往是上级主管部门或工厂计划部门预先规定并要求实现的数值。以例2为例，力求利润指标不低于12元，这就是目标值。而工厂在安排了甲、乙两种产品的产量（决策）后，可能实现的利润额与规定的利润指标12元之间会有一定差距，这个差距就是偏差变量。这样就将目标函数目标函数目标函数目标函数则转化为目标约束目标约束目标约束目标约束(2)(2)将将系统约束系统约束转化为目标约束转化为目标约束有时也可以根据需要将绝对约束转化为目标约束，这时只须将该约束的
11、右端项看作目标值，再引入正、负偏差变量即可。如在例2中，考虑到市场需求，,两种产品的生产量需保持1:1的比例；或此为系统约束在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束，在给定目标值和加入正、负偏差变量之后，可以将系统约束系统约束系统约束系统约束转化为目标约束目标约束目标约束目标约束。转化方法：转化方法：x x1 1 x x2 2 d d 0 0当产品 产量多于产品，有x1x2，即出现正偏差量d，若将x1减去这个正偏差量d，就有x x1 1x x2 2 d d 0 0因正负偏差不可能同时出现，故合在有一起设为x x1 1x x2 2 d d d d 0
12、0由于允许有偏差，当产品 产量小于产品，有x1x2，即出现负偏差量d，若将x1加上这个负偏差量d，就有3 3目标规划的目标函数达成函数目标规划的目标函数达成函数凡满足目标约束和绝对约束的解，应如何判别它的优劣呢？从决策者的要求分析它总希望得到的结果与规定的目标值之间的偏差愈小愈好，由此决策者可根据自己的要求构造一个使总偏差量为最小的目标函数总偏差量为最小的目标函数，这种函数就是目标规划的目标函数称为达成函数达成函数，记为即达成函数是正、负偏变量的函数。即达成函数是正、负偏变量的函数。一般来说，可能提出的要求只能是以下三种情况之一，对应每种要求，可分别构造的达成函数是：构造达成函数的方法如希望产
13、品 产量恰好等于产品的产量，即正、负偏变量都要尽可能地小，这时函数是：如希望产品 产量低于产品的产量，即允许达不到目标值,就是正偏差变量要尽可能地小,即不希望上式中的d d0，这时达成函数是：如希望产品 产量不低于产品的产量，即要求超过目标值，但不得低于目标值，即必须是负偏差变量尽可能地小，不希望上式中的d d0，这时达成函数是：又如中力求利润指标不低于12元，达成函数为：设备B限制中必要时可以加班可表为：设备A限制中既要求充分利用，又尽可能不加班可表为：4.4.目标的优先级与权系数目标的优先级与权系数 在一个多目标决策问题中，要找出使所有目标都达到最优的解是很不容易的；在有些情况下，这样的解
14、根本不存在(当这些目标是互相矛盾时)。实际作法是：决策者将这些目标分出主次，或根据这些目标的轻重缓急不同，区别对待。在一个目标规划的模型中，如果两个不同目标重要程度相差悬殊，为达到某一目标可牺牲其它一些目标，称这些目标是属于不同层次的不同层次的不同层次的不同层次的优先级优先级优先级优先级。优先级层次的高低可分别通过优先因子P1，P2，表示，并规定Pk Pk1，符号“”表示“远大于”，表示Pk与Pk1，不是同一各级别的量，即Pk与Pk1有更大的优先权。对属于同一层次优先级同一层次优先级的不同目标，按其重要程度可分别乘上不同的权数权数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。5
15、.5.满意解满意解 目标规划问题的求解是分级进行的，首先要求满足P1级目标的解；然后再保证 P1级目标不被破坏的前提下，再要求满足P2级目标的解；依次类推。总之，是在不破坏上一级目标的前提下，实现下一级目标的最优。因此，这样最后求出的解就不是通常意义下的最优解，我们称它为满意解。之所以叫满意解，是因为对于这种来说，前面的目标是可以保证实现或部分实现的，后面的目标就不一定能保证实现。满意解这一概念的提出是对最优化概念的一种突破，显然它更切合实际，更便于运用，因而受到广大实际工作者的欢迎而被广泛采用。三、目标规划的数学模型及建模步骤三、目标规划的数学模型及建模步骤以上介绍的几个基本概念，实际上就是
16、建立目标规划模型时必须分析的几个要素，把这些要素分析清楚了，目标规划的模型也就建立起来了。设有L个目标，K个优先等级(KL)的一般目标规划问题。再同一个优先级别的不同目标，它们的正负偏差变量的重要程度还可以有差别。这时还可以给同一优先级别的正负偏差变量赋予不同的权系数和。则目标规划问题的一般数学模型可表述为 目标约束绝对约束目标规划问题建立模型的步骤为：目标规划问题建立模型的步骤为：1.根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；2.可根据决策者的需要将某些或全部绝对约束转化为目标约束，这时只需要给绝对约束加上加上加上加上负偏差变量负偏差变量和减去正偏差变量减去正
17、偏差变量减去正偏差变量减去正偏差变量即可；3.给各自目标赋予相应的优先因子Pk（k=1,2,K）变量即可；4.对同一优先等级中的各偏差变量，若需要，可按其重要程度不同，赋予相应的权系数。5.根据决策者需求，按下列三种情况：a.恰好达到目标值，取 c.不允许超过目标值，取 b.允许超过目标值，取对于由绝对约束转化而成的目标约束，也可以根据需要，按照上面三种方式，将正、负偏差变量列入达成函数中去。例例 2 2某企业生产、两种产品。这两种产品都要分别在A、B、C、D四各不同设备上加工。生产每件产品需占用各设备为2、1、4、0小时，生产每件产品 需占用各设备为2、2、0、4小时，各设备用于生产这两种产
18、品的能力分别为12、8、16、12小时，又知生产一件产品获得2元，生产一件产品 获得3元，问如何安排生产，使总的利润最大。则该问题的数学模型表示为则该问题的数学模型表示为则该问题的数学模型表示为则该问题的数学模型表示为 maxZ=2x1+3x2 2x1+2x2 12 x1+2x2 8 4x1 164x2 12 x1 0,x2 0这是一个线性规划模型这是一个线性规划模型 4x1 16 4x2 12minZ=P1 d1-maxZ=2x1+3x2 2x1+2x2 12 x1+2x2 8 4x1 164x2 12 x1 0,x2 0线线线线性性性性规规规规划划划划目目目目标标标标规规规规划划划划 x1
19、x2+d2-d2+=0 2x1+2x2+d3-d3+=12+P2(d2-+d2+)x1+2x2+d4-d4+=8+3 P3(d3-+d3+)+P3d4+x1,x2，di-,di+0第一优先级：利润不得低于第一优先级：利润不得低于12第二优先级：生产量保持第二优先级：生产量保持1:1的比例的比例第三优先级：第三优先级：B必要时可以加班，必要时可以加班，A既要求充分利用，又尽可能不加班既要求充分利用，又尽可能不加班2x1+3x2+d1-d1+=12现假定企业最重要的目标是利润，不得低于12，列为第一优先级第一优先级第一优先级第一优先级，其次目标是,产品的生产量尽量保持1:1的比例，列为第二优先级第
20、二优先级第二优先级第二优先级：再次是设备A、B尽量不超负荷工作，设备B必要时可以加班，但加班时间要控制，设备A既要求充分利用，又尽可能不加班。列为第三优先级第三优先级第三优先级第三优先级。在第三级中中设备A的重要性比设备B大三倍，因此目标函数中在设备A的偏差变量前冠以权系数3。对其编号目标规划模型为：绝对约束：绝对约束：C和和D为贵重设备，严格禁止超时使用为贵重设备，严格禁止超时使用例例 2 2某计算机制造厂生产A,B,C三种型号的计算机，它们在同一生产线上装配。三种产品的工时消耗分别为5小时，8小时，12小时。生产线上每月正常运转时间是170小时。这三种产品的利润分别为每台1000元，144
21、0元，2520元。该厂的经营目标为 P P1 1：充分利用现有工时，必要时加班；P P2 2：A,B,C的最低产量分别为5，5，8台，并依单位工时的利润比例确定权系数；P P3 3：生产线的加班时每月不超过20小时；P P4 4：A,B,C的月销售指标分别为10，12，10台，并依单位工时的利润比例确定权系数。试建立其目标规划模型。解 设A,B,C三种产品每月的产量分别为x1,x2,x3；单位工时利润分别为1000/5=200，1440/8=180，2520/12=210。故单位工时利润比例为20：18：21。于是得到目标规划模型为 每月运转时间是每月运转时间是170小时，充分利用现有工时，必
22、要时加班，列为第一优先级小时，充分利用现有工时，必要时加班，列为第一优先级min Z=Pmin Z=P1 1d1-x1 +d2-d2+5 x2+d3-d3+5 x3+d4-d4+85x1+8x2+12x3+d1-d1+170 P P2 2(20(20d2-1818d3-2121d4-)x1 +d6-d6+10 x2+d7-d7+12 x3+d8-d8+10A,B,C的最低产量分别为的最低产量分别为5，5，8台，列为第二优先级台，列为第二优先级d1+d5-d5+20 x1,x2，di-,di+0 P P3 3d5+生产线的加班时每月不超过生产线的加班时每月不超过20小时，列为第三优先级小时，列为
23、第三优先级A,B,C的月销售指标分别为的月销售指标分别为10，12，10台，列为第四优先级台，列为第四优先级 P P4 4(20(20d6-1818d7-2121d8-)例例 3 3 已知一个生产计划的线性规划模型为已知一个生产计划的线性规划模型为 其中目标函数为总利润，则三个约束条件均为甲、乙、丙三种资源限制。x1，x2为产品A、B的产量，现有下列目标 第一，要求总利润必须超过2500元；第二，虑到产品A，B受市场影响，为避免造成产品积压，其生产量不超过60件和100件；第三，由于原料甲供应比较紧张，因此不要超过现有量140。试建立目标规划模型。解解 由于产品A与产品B的单件利润之比为2.5
24、:1，分别以它们为权系数，的目标规划问题 30 x1+12x2+d1-d1+2500第一，要求总利润必须超过2500元；2x1+x2+d2-d2+=140 x1,x2，di-,di+0 x1+d3-d3+=60 x2+d4-d4+=100 min Z=Pmin Z=P1 1d1-第二，考虑到产品A，B受市场影响，为避免造成产品积压，其生产量不超过60件和100件；+P+P2 2(2.5(2.5 d3+d4+)+P+P3 3d2+第三，由于原料甲供应比较紧张，因此不要超过现有量140。练习练习某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如下表所示试确定计划期
25、内的生产计划，使利润最大，同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产，同时考虑这些问题，就形成多目标规划问题表表4-1 产品的资源、技术消耗定额、单位利润表产品的资源、技术消耗定额、单位利润表甲（每件）甲（每件）乙（每件）乙（每件）现有资源现有资源钢钢 材材 （kg）9.243600木木 材材 (m3)452000设备负荷（台小时）设备负荷（台小时）3103000单位产品利润单位产品利润(元元)70120(1)第1级目标是要完成或超额完成利润指标45000元；(2)第2级目标是产品甲的生产件数不得超过200件；产品乙的生产件数不得低于250件；(3)第3级目标是现有钢材
26、3600吨必须用完试建立目标规划模型目标规划模型。(1)第1级目标是要完成或超额完成利润指标45000元；70 x1+120 x2+d1-d1+45000 x1+d2-d2+=200 x1,x2，di-,di+0 x2+d3-d3+250 9.2 9.2x1+4x2+d4-d4+=3600 min Z=Pmin Z=P1 1d1-(2)第2级目标是产品甲的生产件数不得超过200件；产品乙的生产件数不得低于250件；(3)第3级目标是现有钢材3600吨必须用完+P+P2 2(7d2+12d3-)+P+P3 3(d4-+d4+)4 4x1+5x2+d5-d5+=2000 3 3x1+10 x2+d
27、6-d6+=3000小结：目标规划模型与线性规划模型的异同小结：目标规划模型与线性规划模型的异同线性规划线性规划LPLP目标规划目标规划GPGP目标函数目标函数min ,max系数可正负系数可正负min ,偏差变量偏差变量系数系数00变量变量x xi ix xi i d d约束条件约束条件系统约束系统约束（绝对约束）（绝对约束）目标约束目标约束系统约束系统约束解解最优最优最满意最满意5.3目标规划的图解法和线性规划问题一样，图解法虽然只适用于两个决策变量的目标规划问题，但其操作简便，原理一目了然，并且有助于理解一般目标规划问题的求解原理和过程。图解法解题的步骤为：图解法解题的步骤为：1.确定各
28、约束条件的可行域，即将所有约束条件(包括目标约束和绝对约束，暂不考虑正负偏差变量)在坐标平面上表示出来；2.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；3.求满足最高优先等级目标的解；4.转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；5.重复4，直到所有优先等级的目标都已审查完毕为止；6.确定最优解或满意解。下面通过例子来说明目标规划图解法的原理和步骤。例例1 1 用图解法求解目标规划问题：用图解法求解目标规划问题：解 确定各个约束条件的可行域。在x1Ox2坐标平面上，暂不考虑每个约束方程中的正、负偏差变量正、负偏差变量正、负偏差
29、变量正、负偏差变量，将上述每一个约束方程用一条直线表示出来，再用两个箭头分别表示上述目标约束方程中的正、负偏差变量。4x1 16 4x2 12 2x1+3x2+d1-d1+=12 x1x2+d2-d2+=0 2x1+2x2+d3-d3+=12x1+2x2+d4-d4+=8 x1,x2，di-,di+0例例1 1 用图解法求解目标规划问题：用图解法求解目标规划问题：4x1 16 4x2 12 2x1+3x2+d1-d1+=12 3x14x2+d2-d2+=0 2x1+2x2+d3-d3+=12x1+2x2+d4-d4+=8 x1,x2，di-,di+0d1+d1-d2-d2+d3-d3+d4+d
30、4-3x3x1 1-4x-4x2 2=0=0 x x1 1+2x+2x2 2=8 =8 得得得得x x1 1=3.2=3.2，x x2 2=2.4=2.4例例2 2 用图解法求解目标规划问题：用图解法求解目标规划问题：10 x1+12x2+d1-d1+62.5 x1+2x2+d2-d2+=10 2x1+x2 8x1,x2，d1-,d1+,d,2-,d2+0d1-d1+d2+d2-于是，C,D两点及CD线段上的所有点(无穷多个)均是该问题的最优解。其中：C点对应的解为：x1=0，x2=5.2083；D点对应的解为：x1=0.6250，x2=4.6875；例例 3 3、用图解法求解线性规划模型用图
31、解法求解线性规划模型 30 x1+12x2+d1-d1+2500 2x1+x2+d2-d2+=140 x1,x2，di-,di+0 x1+d3-d3+60 x2+d4-d4+100 min Z=Pmin Z=P1 1d1-+P+P2 2(2.5(2.5 d3+d4+)+P+P3 3d2+验算验算 将x1=60，x2=58.3代入约束条件，有 以上验算表明，若A、B的计划生产量分别为60件和58.3件，所需甲种原料的数量超过了现有库存量。这就意味着，在现有资源条件下，求得的为非可行解。为了使这个解能成为可行解，工厂领导必须采取先进的技术手段和有效管理措施降低A、B产品对甲种原料的消耗量。显然，A
32、、B产品每件所需甲种原料量应变为原有消耗量的78.5%(140/178.3=78.5%)，才能使求得的生产方案(x1=60，x2=58.3)成为可行方案。30 x1+12x2+d1-d1+2500 2x1+x2+d2-d2+=140 x1,x2，di-,di+0 x1+d3-d3+60 x2+d4-d4+100 min Z=Pmin Z=P1 1d1-+P+P2 2(2.5(2.5 d3+d4+)+P)+P3 3d2+分析分析 在上述两个例子中，前一个例子求得的结果为可可行行解解，后一个例子求得的结果为非可行解非可行解。这就表明目标规划模型的求解结果可以是非可行解。而这正是目标规划模型与线性规划模型在求解思想上的差别，即线性规划立足于求满意解。目标规划模型的满意解虽然可能是非可行解，但它却有助于了解问题的薄弱环节以便有的放矢改进工作。练习：用图解法求解下列目标规划问题练习：用图解法求解下列目标规划问题 (2)(3)(4)(1)CD结论：有无穷多最优解。结论：有无穷多最优解。C（2，4），），D（10/3，10/3）此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢