目标规划(运筹学)

1、4.1 4.1 目标规划问题及其建模目标规划问题及其建模4.2 4.2 目标规划的图解法目标规划的图解法4.3 4.3 目标规划的单纯形法目标规划的单纯形法4.4 4.4 目标规划应用目标规划应用第2章 单纯形法2引引例例4-14-1 某企业计划生产甲、乙、丙三种产品，需要在两种设备A、B上加工，消耗C、D两种原料，有关数据见下表。第4章 目标规划3甲甲乙乙丙丙现有资源现有资源A A（设备）（设备）312200B B（设备）（设备）224200C C（原料）（原料）451360D D（原料）（原料）235300利润（元利润（元/件）件）403050设 分别为甲、乙、丙的产量，则利润最大的线性规

2、划模型为：线性规划最优解为X* =（50，30，10） Z*=3400第4章 目标规划4321,xxx0,3005323605420042220023. .503040max321321321321321321xxxxxxxxxxxxxxxtsxxxz决策者考虑以下实际目标：利润不少于3200元产品甲的产量不超过产品乙的产量的1.5倍提高丙的产量达到30以上设备加工能力不足时可以加班，但最好不加班原料只能使用现有的原料。企业如何制定生产计划，才能实现决策者的目标？第4章 目标规划5如果用线性规划求解，模型如下：该线性规划模型无可行解。0,30053236054200422200233005 .

3、 .503040max321321321321321321321321xxxxxxxxxxxxxxxxxxxxxtsxxxz-6-线性规划：单一目标，最优解目标规划：多目标、优先次序、满意解目标规划（目标规划（Goal ProgrammingGoal Programming）研究企业考虑研究企业考虑现有的资源条件下，在多个目标中去寻求满意现有的资源条件下，在多个目标中去寻求满意解，使得完成目标的总体结果与事先制定目标解，使得完成目标的总体结果与事先制定目标的差距最小的差距最小。 目标规划是按事先制定的目标顺序进行检查，尽可能使目标达到预定的目标，即使不能达到目标也要使

4、得偏离目标的差距最小，也就是求得满意解满意解。（1 1） 设置偏差变量，表明实际值同目标值之间的差异设置偏差变量，表明实际值同目标值之间的差异d+, d- 分别为正、负偏差变量, d+表示实际值超过目标值部分； d- 表示实际值未达到目标值部分；d+ 和 d- 两者中必定至少有一个为零。（2 2）绝对约束和目标约束）绝对约束和目标约束绝对约束绝对约束：必须严格满足的等式约束和不等式约束，也称硬约束。目标约束目标约束：允许发生正或负偏差，也称软约束。第4章 目标规划7-第4章 目标规划- 目标值d1-d1+实际值实际值d1- d1+ =0d1- 0， d1+ 0正偏差变量负偏差变量（3 3）优先

5、因子（优先等级）与权系数）优先因子（优先等级）与权系数 一个规划问题常常有若干目标，但决策者在要求达到这些目标时，是有主次和轻重缓急的不同。要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2, 规定PkPk+1，k=1,2, ,K。（4 4）目标规划的目标函数）目标规划的目标函数 每当一目标值确定后，决策者的要求是尽可能缩小偏离目标值，因此目标规划的目标函数只能是min Z=f (d+, d- )。其基本形式有三种：恰好达到目标值，正、负偏差变量都尽可能地小，min Z=f (d+, d- )不超过目标值，正偏差变量要尽可能地小，min Z=f (d+)超过目标值，负偏差变量要尽

6、可能地小，min Z=f (d- )第4章 目标规划9例例4-14-1用目标规划表示的模型为其满意解为X=（28，20，30）， d1+ =20， d2- =2， d4-=36， d5+ =16，其余变量为零。 第4章 目标规划10030053236054200422200233005 . .min32132132155321443213332221113215444332211xxxxxxxxxddxxxddxxxddxddxxddxxxtsdPdPdPdPdPz决策者考虑以下实际目标：利润不少于3200元产品甲的产量不超过产品乙的产量的1.5倍提高丙的产量达到30

7、以上设备加工能力不足时可以加班，但最好不加班原料只能使用现有的原料。企业如何制定生产计划，才能实现决策者的目标？目标规划的数学模型的一般形式为目标规划的数学模型的一般形式为 其中：Pl为第l级优先因子，l=1, ,L; -lk， +lk为分别赋予第l个目标约束的正负偏差变量的权系数。gk为第k个目标的预期目标值，k=1, ,K。第4章 目标规划11KkddnjxKkgddxcmibxatsddPzkkjkkknjjkjinjjijKkklkklkLll, 10, 10, 1, 1. .min1111，第4章 目标规划12 拥有量 原材料(kg) 设备(hr) 2 1 1 2 11 10 利润(

8、元/件) 8 10 （1) 根据市场信息，产品的销售量有下降的趋势，故考虑产品的产量不大于产品。(2) 超过计划供应的原材料时，需用高价采购，会使成本大幅度增加(3) 应尽可能充分利用设备台时，但不希望加班。 (4) 应尽可能达到并超过计划利润指标56元。决策者在原材料供应受严格限制的基础上考虑：首先是产品的产量不低于产品的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于56元。求决策方案 。-第4章 目标规划-13-3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii满

9、足约束条件：目标函数：u当目标规划问题中只包含两个决策变量时，可以用图解法进行求满意解。目标规划图解法的计算步骤如下目标规划图解法的计算步骤如下：（1）对所有目标约束，去掉偏差变量，画出相应直线，然后标出偏差变量变化时直线平移方向。（2）确定第一优先级P1级各目标的解空间R1。（3）转到下一个优先级PJ级个目标，确定它的“最佳”解空间RJ。（4）在求解过程中，若解空间 RJ已缩小为一点，则结束求解过程，因为此时已没有进一步改进的可能。（5）重复第（3）步和第（4）步过程，直到解空间缩小为一点，或者所有L个优先级都已搜索过，求解过程也告结束。第4章 目标规划14例例4-2 4-2 用图解法求解下

10、列目标规划问题第4章 目标规划1511223344112111222123324412min(53)2629242,01 , 2 , 3 , 4iizPdPdPddPdxxddxxddxxddxddxxidd解：所有目标约束，去掉偏差变量，画出相应直线，然后标出偏差变量变化时直线平移方向。P1、P2的目标实现后，x1 , x2 的取值范围为ABCD。考虑P3的目标中 d3- 尽量小的要求后， x1 , x2 的取值范围缩小为ABEF区域；然后考虑 ，在ABEF中无法满足d4- =0,因此只能在ABEF中取一点，使d4- 尽可能小，这就是E点。故E点为满意解。其坐标为（13/2，5/4）。X=X

11、=（ x1 ，x2 ）= =（13/213/2，5/45/4），），Z=9/4 PZ=9/4 P3 3 +3 P+3 P4 4 第4章 目标规划16-第4章 目标规划-17-3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii求解线性规划的单纯形法的过程基本一致，只是在检验数处理时，需要考虑优先次序的影响。而且，目标规划的目标函数是求最小化，所以当检验数均为大于等于零时为满意解。例例4-34-3用单纯形法求解例4-2第4章 目标规划18Step (0):初始单纯初始单纯形表形表第4章

12、 目标规划19Step (1):x x2 2 入基，入基，d d4 4- - 出基出基Step (2):d4d4+ + 入基，入基，d d1 1- - 出基出基第4章 目标规划20Step (3):x x1 1 入基，入基， d d4 4+ +出基出基Step (4):d4d4- - 入基，入基， d d3 3- - 出基出基第第4章 目标规划21Step (5):d1d1+ + 入基，入基， d d2 2- -出基出基这时，所有非基变量的检验数都大于零，所以有唯一最优解。X X* *= =（13/213/2，5/45/4） Z Z* *=9/4P=9/4P3 3+3P+3P4 4例例4-44

13、-4 利用Excel求解目标规划问题。某工厂要生产两种新产品：门和窗。生产所需的时间如下表所示。根据经市场调查得到的该两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂如何安排这两种新产品的生产计划，可使总利润最大？其最优解为：X*=（ x1 ，x2 ）=（2，6） Z*=3600第4章 目标规划22车间车间单位产品的生产时间单位产品的生产时间每周可以获得的每周可以获得的生产时间（小时）生产时间（小时）门门窗窗11042021233218单位利润（元）300500现在工厂领导要考虑市场等一系列其他因素，提出如下目标：（1）根据市场信息，窗的销售量有下降的趋势，

14、故希望窗的产量不超过门的2倍；(希望)（2）由于车间3有另外新的生产任务,因此希望车间3节省4个工时用于新的生产任务;(希望)（3）应尽可能达到并超过计划的每周利润3000元。 （希望）第4章 目标规划23则目标规划模型为：11222331212211112Min z()4 212 3218 s.t.20 32PdP ddPdxxxxxxddxx2212331214 3005003000,0,0 (1,2,3)iiddxxddx xddiExcel电子表格求解目标规划是按照优先级渐进的。假设三个目标优先级依次为（1）（2）（3）。由于有三个目标优先级（P1，P2，P3），所以要分三步完成：第1

15、步：首先保证P1级目标的实现，这时不考虑其他次级目标。优先级1的数学模型为：第4章 目标规划2411121221111222123312112233M in z42123218s.t.2032143005003000,0dxxxxxxddxxddxxddxxdddddd第4章 目标规划25第2步：在保证P1级目标实现的基础上考虑P2级目标。优先级2的数学模型为：第4章 目标规划262221212211112221233112112233M in z4212321820s.t. 321430050030000,0ddxxxxxxddxxddxxdddxxdddddd第4章 目标规划27第3步：在保证P1级和P2级目标实现的基础上考虑P3级目标。优先级3的数学模型为：第4章 目标规划2833121221111222123312212112233M in z421 2321