多目标规划课件.ppt

第四章是多目标规划，即考虑多个决策目标时的多目标规划。从线性规划问题可以看出，线性规划只研究在一定条件下单个目标函数的最优解。然而，在企业管理中，经常会遇到多目标决策问题，如在制定生产计划时不仅要考虑总产量，还要考虑利润、产品质量和设备利用率。这些指标的重要性(即优先次序)也不同，一些目标往往相互矛盾。线性规划致力于目标函数的最优解。如果这个最优解超过了实际需要，它很可能以过度消耗约束条件中的一些资源为代价。线性规划对每个约束条件的重要性一视同仁，不分主次，这不符合实际情况。为了解决线性规划问题，第一个要求是约束条件必须相容。如果由于人力、设备和其他资源的限制而在约束条件之间存在矛盾，则无法获得问题的可行解决方案，但生产必须继续，这将给线性规划方法的进一步应用带来困难。为了弥补线性规划的局限性，解决有限的资源与规划指标之间的矛盾，在线性规划的基础上建立了目标规划方法，从而可以很好地解决一些线性规划无法解决的问题。在实际问题中，可以同时考虑几个方面来达到最优：最高产量、最低成本、最佳质量、最大利润、环境标准、运输满意度等。多目标规划可以更好地考虑多个目标之间的关系，获得更现实的解决方案。根据实际情况，目标规划可以根据优先级和优先级考虑问题。例4-1:一个企业生产甲、乙两种产品需要相同的原材料，其单位产品所消耗的原材料数量和加工时间不同，因此所获得的利润也不同(见下表)。那么，企业应该如何安排生产计划以实现利润最大化呢？如何安排生产以实现利润最大化？用单纯形法求得最优解=(20，20)最优值=200 (100元)。问题是：工厂提出了以下目标：(1)利润达到280元；(2)钢材不得超过100吨，工作时间不得超过120小时；如何安排生产？例4-2:一个车间有两条生产线，设备相同，生产相同的产品。生产线A每小时可以生产2种产品，生产线B每小时可以生产1.5种产品。如果每周正常工作时间为45小时，则需要一个生产计划来实现以下目标：(1)产量达到210件/周；(2)生产线加班时间限制为15小时；(3)充分利用工时指标，根据甲、乙产出比例确定重要性。由电器公司操作的唱机和录音机在车间a和b组装。数据如下表所示。要求按以下目标制定月度生产计划：(1)库存成本不超过4600元；(二)每月销售不低于80台留声机；(3)不要关闭车间A和B(重量由生产成本决定)；(4)车间A的加班时间限制为20小时；(5)每月销售100台录音机；(6)两个车间加班时间的总和应尽可能小(重量由生产成本决定)；多目标优化的首要任务是对目标进行优先排序：根据重要程度将目标分为一级目标和二级目标。次要目标位于次要级别。目标的优先级约定如下：对于同一个目标，如果可以实现多个决策方案，这些方案可以被认为是该目标的最优方案；如果没有，与目标的差距越小越好。目标的优先次序商定如下：不同级别目标的重要性不可比较。也就是损失它们之间的重要性可以用数量(重量)来描述。因此，相同水平的目标之一的损失可以通过其他目标的适当收获来补偿。多目标规划解的概念：如果多目标规划问题的解能够达到所有的目标，那么这个解就叫做多目标规划的最优解；如果该解只能满足某些目标，则称之为多目标规划的次优解。如果找不到满足任何一个目标的解决方案，这个问题就是无法解决的。(例4-1)一个企业需要相同的原料生产两种产品，甲方和乙方，其单位产品所需的原料数量和加工时间不同，因此获得的利润也不同(见下表)。那么，企业应该如何安排生产计划以实现利润最大化呢？如何安排生产以实现利润最大化？我们已经得到了最优解=(20，20)最优值=200 (100元)。问题：工厂提出了以下目标：(1)利润达到280元；(2)钢材不得超过100吨，工作时间不得超过120小时；如何安排生产？对于例4-1中的问题，损失一吨以上的钢等于损失五个以上的工作时间。现有四个方案的优缺点是什么？(1)利润达到280元；(2)钢材不得超过100吨，工作时间不得超过120小时；对于(1)，只有方案4尚未完成。不包括选项4。对于(2)，仅实现方案2，因此方案2是最佳的。(1)利润达到280元；(2)钢材不得超过100吨，工作时间不得超过120小时；方案1和3都达到(1)但没有达到(2)方案1和(2)之间的差距：工时损失=(110-100)*5 (130-120)*1=60，方案3和(2)之间的差距：工时损失=0*5 (190-120)*1=70。方案1比方案3好。方案2优于方案1优于方案3优于方案4，示例4-4:继续前面的示例，目标是：(1)利润达到280元；(2)钢材不得超过100吨，工作时间不得超过120小时；对于(1)，三个计划都没有完成。然而，方案3离目标最远，方案3最差。方案1和方案2的区别：工时损失=(108-100)*5 (130-120)*1=50，方案2和方案2的区别：工时损失=0*5 (160-120)*1=40方案2优于方案1方案2优于方案1方案3，4-2多目标规划数学模型多目标处理为了量化不同层次目标的重要性，引入P1，P2，用它来表示主要目标、次要目标、指定P1“p2”P3“P1，p2，称为等级系数。约束方程的处理差异变量：决策变量x超过目标值b的部分被记录为d，决策变量x不足目标值b的部分被记录为d-d0、d-0和x-d-=b，如果在决策目标中指定了XB，则当d=0时，将认为达到了目标。如果决策目标中指定了XB，则当y=0时将达到该目标。如果在决策目标中指定了XB，则只有当d-=0时才达到目标。如果决策目标中指定了XB，则当y=0时将达到该目标。如果在决策目标中指定了XB，则只有当y-=0时才能达到目标。如果在决策目标中指定了x=b，则只有当d=d-=0时才能达到目标。案例4-5(案例4-4)解决方案：进口等级系数P1: (1)利润达到280元；P2: (2)钢材不得超过100吨，工作时间不得超过120小时；(重量比：5: 1)，数学模型：目标函数：MinS=P1d1- P2(5d2 d3)约束方程：6x 14 2d 1-D1=2802 x 13 x2 D2-D2=1004 x 12 x2 D3=120 x 1，x2，di-，di0 (I=1，2，3)，例4-6(例4-2)一个车间有两条生产线，它们具有相同的设备a和b，生产相同的产品。生产线A每小时可以生产2种产品，生产线B每小时可以生产1.5种产品。如果每周正常工作时间为45小时，则需要一个生产计划来实现以下目标：(1)产量达到210件/周；(2)生产线加班时间限制为15小时；(3)充分利用工时指标，根据甲、乙产出比例确定重要性。解决方案：将生产线A和生产线B的每周工作时间设置为X1和X2。a和b的输出比为2: 1.5=4:3目标函数：MinS=P1d1- P2d2 4P3d3- 3P3d4-约束方程：2x11.5x2d1-D1=210(输出达到210件/周)x1d2-D2=60(生产线超时限制为15小时)。X1 d3 - d3=45(充分利用A的工时指数)X2 d4 - d4=45(充分利用B的工时指数)X1，X2，DI-，DI 0 (I=1，2，3，4)，A，B的输出比为2: 1.5=4:3目标函数：MinS=P1d1- P2d2 4P3d3- 3P3d4-约束方程：2x 11.5 x2d 1-D1=210 x1d 2-D2=60 x1d 3-D3=45x 3d 4(二)每月销售不低于80台留声机；(3)不要关闭车间A和B(重量由生产成本决定)；(4)车间A的加班时间限制为20小时；(5)每月销售100台录音机；(6)两个车间加班时间的总和应尽可能小(重量由生产成本决定)；解决方案：设置X1和X2电唱机和录音机，每月生产。甲与乙的生产成本比为10050=21。目标函数：mins=p1d 1 p2d 2-2p 3d 4-p3d 5-p4d 41p 5d 3-p5d 32p 6 d4p 5d 5约束方程：50x130x2d1-D1=4600(库存成本不超过4600元)x1d2-D2=80(每月销售留声机不少于80台)。X2 d3 - d3=100(每月销售100台录音机)2x1X2D4-D4=180(车间a不会关闭)x13x2d5-D5=200(车间b不会关闭)D4d41-D41=20(车间a的加班时间将限制为20小时)x1，x2，di-，di，D41-，D410 (I=1，2，3，4，5)，目标函数：min=p1d1p 2d 2-2p 3d 4-p3d 5-p4d 4d 4 d41-，d41-d41 0 (I=1，2，3，4，5)，4-3求解多目标规划问题的图解法4-8分钟=d1x12x2d1-d1=10x12x26x1x24x1，x2，d1-，d10，x1，x1，x2，0，4，6，8，10，2，1，3，4，2，x1 2x26,x1,x2,0,4,6,8,10,2,1,3,4,2,x1 x24,x1,x2,0,4,6,8,10,2,1,3,4,2，x1，x2，0，4，6，8，10，2 当MinS=d1达到时，D1=0、x1、x2、0、4、6、8、10、2、1、3、4、2、x1 2x2d1-=10d1-=2、5、d1-，a、b、(2、2)，D1=0当MinS=d1达到、x1、X2、0、4、6、8、10、2、1、3、4、2、x12x2d1-=10d1-=4、5、d1-，a、b、(2、2)，有(0，3)，X1，X2，0，4，6，8，10，2，1，3，4，2，X1，2x2D1-=10D1-=6，5，D1-，A，B，(2，2)，有无穷多个解：点(4，0)和点(0，2)线上的点是最优解。(0，3)，(4，0)，(0，2)，X1，X2，0，4，6，8，10，2，1，3，4，2，X1，2x2D1-=10D1-=7，5，D1-，A，B，(2，2)，有无穷多个解：直线上的点(1，1)和点(0，3/2) (3，0)都是最优解。(0，3)、(4，0)、(1，1)，实施例4-9分钟=P1 d1-p2d 25p 3d 3-p3d 1 x1x 2d 1-d1=40 x1x 2d 2-D2=50 x1d 3-=30 x2d 4-=30x 1，x2，di-，di0 (i=1，2，3，4)，x1，x2，0，20，30，40，50，10，10，30，40，20，50，D1-，D1，X1 X2=40，1 10、10、30、40、20、50、D1、D2、D4-、