运筹(第五章目标规划)

2023/2/41运筹学

OPERATIONSRESEARCH

2023/2/42第五章目标规划

目标规划的数学模型目标规划的图解法目标规划的单纯形解法目标规划的层次算法目标规划的应用2023/2/43§1目标规划的提出与数学模型

§1.1引例例1生产计划问题

Ⅰ

Ⅱ能力设备A2212设备B4

016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?2023/2/44解:设产品Ⅰ,Ⅱ产量分别为变量最优解：这里的目标只有一个！2023/2/45有时目标不只一个，例如考虑下列要求：1、力求利润指标不低于15元；2、Ⅰ、Ⅱ两种产品的产量保持1：2；3、A为贵重设备，严格禁止超时使用；4、设备C可适当加班，但要控制；5、设备B既要充分利用，又要尽量不加班，在重要性上，设备B是设备C的3倍。

要解决这样的问题，将上述的要求都加以考虑，就要用目标规划的方法解决。2023/2/46目标规划是在线性规划的基础上，为适应企业经营管理中多目标决策的需要而逐步发展起来的。目标规划是一种数学方法。基本含义：在一定约束条件下，要求多个目标达到或尽可能接近于给定的对应目标值。特点：既保持了线性规划易于计算的特点，又克服了线性规划只能解决单一目标优化问题的局限性。2023/2/47目标规划产生与发展目标规划的有关概念和数学模型是在1961年由美国学者查恩斯(A.Charnes)和库伯(W.W.Cooper)首次在《管理模型及线性规划的工业应用》一书中提出。当时是作为解一个没有可行解的线性规划而引入的一种方法。这种方法把规划问题表达为尽可能地接近预期的目标。1965年，尤吉·艾吉里(Yuji·Ijiri)在处理多目标问题，分析各类目标的重要性时，引入了赋予各目标一个优先因子及加权系数的概念；并进一步完善了目标规划的数学模型。表达和求解目标规划问题的方法是由杰斯基莱恩(Jashekilaineu)和桑李(SangLi)给出并加以改进的。2023/2/48§1.2

目标规划的有关概念1、正、负偏差变量：

等是决策变量；

是正偏差变量，表决策值超过目标值的部分；是负偏差变量，表决策值未达目标值的部分。

且有。2、绝对约束和目标约束

：

绝对约束：必须满足的等式约束或不等式约束。

如：A设备严格禁止超时使用，则

2023/2/49目标约束：对于不严格限定的约束，在达到此目标时允许发生正或负的偏差，可在这些约束中加入正负偏差变量，成为目标约束。如：（1）“Ⅰ、Ⅱ两种产品的产量保持1：2”可表示为●当允许此比例时，即，则引入负偏差，则该条件可表示为：●类似地有，表示允许此比例。●表示“力求Ⅰ、Ⅱ两种产品的产量比例不”2023/2/410（2）目标函数也可转化为目标约束：如：“力求利润指标不低于15元”可表示为（3）“设备C可适当加班，但要控制”可表示为（4）“设备B既要充分利用，又要尽量不加班”可表示为2023/2/4113、目标的优先级和权系数

不同的目标重要程度不同，优先级不同；同一层次优先级的不同目标，重要程度不同，权重不同优先级因子：，且权重系数：，数值的大小决定目标的重要程度。假设：第一优先级：利润不低于15元；第二优先级：Ⅰ、Ⅱ产品的数量尽量保持1:2；第三优先级：C、B的工作时间控制，且B的重要性是C的3倍。4、目标函数：目标函数是要尽量缩小偏离目标值2023/2/412于是按照上例中的有关要求，该目标规划的目标函数约束条件：2023/2/413目标规划特点：可以同时考虑多个目标；可以区分不同目标的优先程度及重要程度；更加切合实际，更加灵活目标规划中的优先级及权重系数的确定往往需要靠人的主观判断，是定性的，常常是模糊的，不是一个确定的数值，但现在也有很多将其定量化的方法，如层次分析法等这是处理目标规划时的一个难点。2023/2/414一般的目标规划数学模型刚性约束柔性约束2023/2/415§2目标规划的图解分析法求解目标规划的思路：刚性约束必须严格满足；按优先级次序，从高层到低层逐层优化；在不增加高层偏差值的情况下，使本层的偏差达到最小。只有两个决策变量的目标规划可用图解法分析。以上例为例，图解分析如下。2023/2/416满意解F2023/2/417§3目标规划的单纯形解法单纯形法求解目标规划的思路：1.求解步骤与一般线性规划问题的单纯形法基本相同；2.根据目标函数中的优先级次序，从高层到低层逐层优化；3.单纯形表中，检验数按优先级次序分行表示。例：2023/2/41800P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+P1d1-10[1]01-10d2-40211-1P2d3-100321-1P1-111P2-3-21第一步：列初始单纯形表2023/2/419第二步：确定进基变量。按照优先级次序，检查P1，P2，…,Pk行检验数是否仍有负值（<0）若有，找优先级最高一行的负值最小检验数对应变量作为进基变量。此例中选x1第三步：确定出基变量。按照最小比值规则确定出基变量，此例中选d1-第四步：迭代运算，得到新的基可行解，判断是否最优。本例中，P2行仍有负检验数，转到第二步。2023/2/42000P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x110[1]01-10d2-2001-2[2]1-1P2d3-7002-331-1P111P2-23-3100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x12011/2001/2-1/20d1+100[1/2]-111/2-1/2P2d3-4001/200-3/23/21-1P111P2-1/23/2-3/212023/2/42100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x110101-1000X22001-221-1P2d3-30001-1-221-1P111P2-112-21注意：此时，P2行仍有负检验数，要选X2进基，因为d2+的检验数是。此时，已达最优。2023/2/422说明：1、进行优化是按照优先级进行的，当高一级的目标行的检验数全部非负时，可进行下一级的优化；2、判别迭代终止的准则：

（1）所有级别的检验数行均非负，迭代终止；（2）若行检验数均非负，而行有负检验数，但这些负检验数对应的上面行中有正检验数，迭代终止。2023/2/423§4目标规划的层次算法（思想同前）第一步：先对目标函数中的层次进行优化。建立第一层次的线性规划模型，记为LP1.目标函数：由第一优先级的偏差变量构成约束条件：由原约束构成。设第一级优化的最优目标值是2023/2/424第二步：对目标函数中的层次进行优化。建立第二层次的线性规划模型，记为LP2.目标函数：由第二优先级的偏差变量构成约束条件：在原约束基础上增加新约束：设第二级优化的最优目标值是。以此类推。2023/2/425§5目标规划应用举例例1：某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间生产。已知除外构件外，生产一台录音机需甲车间加工2h，乙车间装配1h；生产一台电视机需甲车间加工1h，乙车间装配3h；检验销售环节：一台录音机检验销售费用50元；一台电视机检验销售费用30元；2023/2/426工时及管理费用：甲车间每月可用生产工时120h，车间管理费用80元/h;乙车间每月可用生产工时150h，车间管理费用20元/h;利润及销量：每台录音机利润100元，平均每月可销售50台；每台电视机利润75元，平均每月可销售80台；月度计划的目标如下：2023/2/4271、第一优先级：检验和销售费用每月不超过4600元；2、第二优先级：每月销售录音机不少于50台；3、第三优先级：两车间的工时得到充分利用（重要性权系数按每小时的管理费用比）；4、第四优先级：甲车间加班不超过20小时；5、第五优先级：每月销售电视机不少于80台；6、第六优先级：两车间的加班总时间要控制（权系数分配如3）试确定该厂为达到上述目标的最优月度生产计划。2023/2/428解：假设每月生产录音机台，电视机台。1、两车间可用工时:2、检验和销售费用:3、每月销售量:4、加班限制:于是模型如下2023/2/429约束：目标函数2023/2/430例2：书P143例5解：设是i工厂调配给j用户的产品数量。约束如下1、供应量约束:2、需求量约束:3、用户1需要量中工厂3的产品数量不少于100:2023/2/4314、各用户满足率不低于80%：5、运费限制：6、道路通过限制：7、用户1和3的满足率保持平衡：2023/2/4328、力求总运费减小：目标函数：2023/2/433例3：某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：1、年工资总额不超过120万元；2、每级的人数不超过定编规定的人数；3、Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%；4、Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工中有10%要退休。有关资料汇总于下表，请为该单位领导制定一个满意的方案。2023/2/434等级工资额（元/年）现有人数编制人数Ⅰ400001012Ⅱ300001215Ⅲ200001515合计3742解：设分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的职工人数。则模型如下：目标函数各目标约束：2023/2/435（1）年工资总额不超过120万元；（2）每级的人数不超过编制规定的人数；（3）Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%；例4：某农场有3万亩农田，欲种植玉米、大豆和小麦。各种作物每亩需施化肥分别为0.12,0.20,0.15吨。预