资源描述
目目 标标 规规 划划(Goal programming)目标规划的图解法目标规划的图解法目标规划的单纯形法目标规划的单纯形法目标规划应用举例目标规划应用举例目标规划问题及其数学模型目标规划问题及其数学模型7/15/20241目标规划的方法是在目标规划的方法是在19611961年由查恩斯年由查恩斯(A.Charnes)(A.Charnes)和和库伯库伯(W.W.Cooper)(W.W.Cooper)提出提出的的它是在线性规划的基础上,适应企业经它是在线性规划的基础上,适应企业经营管理中多目标决策的需要而逐步发展营管理中多目标决策的需要而逐步发展起来的。起来的。目标规划是在企业决策者所规定的若干目标规划是在企业决策者所规定的若干指标值及要求实现这些指标的先后顺序指标值及要求实现这些指标的先后顺序后,并在给定有限资源条件下,求得总后,并在给定有限资源条件下,求得总的偏离指标值为最小的方案,称这方案的偏离指标值为最小的方案,称这方案为满意方案。为满意方案。目标规划目标规划7/15/20242目标规划目标规划与与线性规划线性规划相比,有以下优点:相比,有以下优点:线性规划线性规划只能只能处理一个目标处理一个目标,而现实问题往往,而现实问题往往要处理多种目标。要处理多种目标。目标规划目标规划能统筹兼顾地能统筹兼顾地处理处理多种目标多种目标的关系,求得更切合实际要求的解。的关系,求得更切合实际要求的解。线性规划线性规划立足于满足所有约束条件的立足于满足所有约束条件的可行解可行解,而在实际问题中可能存在相互矛盾的约束条件。而在实际问题中可能存在相互矛盾的约束条件。目标规划目标规划可以在相互矛盾的约束条件下可以在相互矛盾的约束条件下找到满找到满意解意解,即满意方案。,即满意方案。目标规划目标规划找到的最优解是指尽可能地达到或接找到的最优解是指尽可能地达到或接近一个或若干个已给定的指标值。近一个或若干个已给定的指标值。线性规划线性规划的约束条件是的约束条件是同等重要同等重要的,而的,而目标规目标规划划可根据实际需要给予可根据实际需要给予轻重缓急或主次之分轻重缓急或主次之分的的考虑。考虑。7/15/20243v 可以认为可以认为目标规划目标规划更能确切地描述和更能确切地描述和解决经营管理中的许多实际问题解决经营管理中的许多实际问题 一种简单、实用的处理多目标决策问一种简单、实用的处理多目标决策问题的方法。题的方法。v在经济计划、生产管理、经营管理、市在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应场分析、财务管理等方面得到了广泛的应用。用。7/15/20244一、目标规划问题及其数学模型一、目标规划问题及其数学模型(一)目标规划问题的提出(一)目标规划问题的提出 单一目标问题单一目标问题例例1 1 解:可用线性规划的模型来描述解:可用线性规划的模型来描述产品产品限量限量原材料(原材料(kg/kg/件)件)51060设备工时(设备工时(h/h/件)件)4440利润(元利润(元/件)件)687/15/20245 目标函数:目标函数:max z=6x1+8x2约束条件:约束条件:5x1+10 x2 60 4x1+4x2 40 x1,x20 最优解:最优解:x1=8件,件,x2=2件,件,max z=64元元 7/15/20246 (二)目标规划的数学模型二)目标规划的数学模型 实际上工厂在做决策时,要考虑市场等其他条件:实际上工厂在做决策时,要考虑市场等其他条件:1 1、根据市场信息,产品、根据市场信息,产品的销售量已有下降的趋势,的销售量已有下降的趋势,故考虑产品故考虑产品的产量最好不大于产品的产量最好不大于产品的一半;的一半;2 2、由于原材料严重短缺,生产中应避免过量消耗;、由于原材料严重短缺,生产中应避免过量消耗;3 3、最好能节约设备工时(、最好能节约设备工时(4h4h););4 4、应尽可能达到并超过预计利润指标(应尽可能达到并超过预计利润指标(4848元)。元)。工厂现在的生产、经营问题工厂现在的生产、经营问题多目标决策问题。多目标决策问题。引入与建立目标规划数学模型有关的概念:引入与建立目标规划数学模型有关的概念:7/15/20247 1 1、引入一种、引入一种新的变量新的变量正、负偏差变量正、负偏差变量d d+、d d-,d d+:可能实现值超过规定目标值的偏差量,可能实现值超过规定目标值的偏差量,d d+00。d d-:可能实现值未达到规定目标值的偏差量可能实现值未达到规定目标值的偏差量,d d-00 d d+d d-=0 =0 2 2、约束条件约束条件 绝对(硬)约束、目标(软)约束绝对(硬)约束、目标(软)约束3 3、优先因子优先因子(优先等级)(优先等级)P P1 1,P P2 2,规定规定 P Pl l P Pl l+1+1,l l=1=1,2 2,。表示表示P Pl l比比P Pl l+1+1有更大的优先权有更大的优先权。这意。这意味着当目标与目标之间发生冲突时应按其优先等级来味着当目标与目标之间发生冲突时应按其优先等级来实现。具有实现。具有相同优先因子的目标相同优先因子的目标,其重要程度用不同,其重要程度用不同的的权系数权系数表示表示4 4、目标规划的目标函数目标规划的目标函数7/15/20248 当完成或超额完成规定的指标则表示:当完成或超额完成规定的指标则表示:d d0,d d0 当未完成规定的指标则表示:当未完成规定的指标则表示:d d0,d d0 当恰好完成指标时则表示:当恰好完成指标时则表示:d d0,d d0 d d d d 0 0 成立。成立。在一次决策中,实现值不可能既超过目标值又未在一次决策中,实现值不可能既超过目标值又未达到目标值,故有达到目标值,故有 d d d d 0,0,并规定并规定d d0,d0,d0 01 1、引入一种、引入一种新的变量新的变量正、负偏差变量正、负偏差变量d d+、d d-7/15/20249 引入了目标值和正、负偏差变量后,就对某一引入了目标值和正、负偏差变量后,就对某一问题有了新的限制,既问题有了新的限制,既目标约束目标约束。目标约束是目标规划中特有的目标约束是目标规划中特有的,是软约束。,是软约束。2 2、约束条件约束条件 绝对(硬)约束、目标(软)约束绝对(硬)约束、目标(软)约束 绝对约束绝对约束是指必须严格满足的等式或不等式约束。是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束,否则无如线性规划中的所有约束条件都是绝对约束,否则无可行解。所以,绝对约束是硬约束。可行解。所以,绝对约束是硬约束。7/15/202410 由各目标约束的正、负偏差变量及相应的优先由各目标约束的正、负偏差变量及相应的优先因子和权系数构成因子和权系数构成。从决策者的要求来分析,总。从决策者的要求来分析,总希望得到的结果与规定的指标值之间的偏差量愈希望得到的结果与规定的指标值之间的偏差量愈小愈好。由此可构造一个小愈好。由此可构造一个使总偏差量为最小化的使总偏差量为最小化的目标函数,目标函数,min Z=f(d+,d-)其基本形式有其基本形式有三三种:种:4 4、目标规划的、目标规划的目标函数目标函数7/15/202411(1 1)要求要求恰好达到目标值恰好达到目标值,即正、负偏差变量,即正、负偏差变量都要尽可能地小都要尽可能地小 。构造的目标函数是。构造的目标函数是 min Z=f(d+d-)(2 2)要求要求不超过目标值不超过目标值,但允许达不到目标值,但允许达不到目标值,即只有使正偏差量要尽可能地小(实现最少或为即只有使正偏差量要尽可能地小(实现最少或为零)零)min Z=f(d+)(3 3)要求要求超过目标值超过目标值,即超过量不限。要求超,即超过量不限。要求超额完成规定目标,要实现负偏差量为零或为最小额完成规定目标,要实现负偏差量为零或为最小 min Z=f(d-)7/15/202412 对于这种解来说,前面的目标可以保证实现或部对于这种解来说,前面的目标可以保证实现或部分实现,而后面的目标就不一定能保证实现或部分分实现,而后面的目标就不一定能保证实现或部分实现,有些可能就不能实现。实现,有些可能就不能实现。5 5、满意解满意解 7/15/202413 归纳上面的分析:归纳上面的分析:由于原材料严重短缺,生产中应避免过量消由于原材料严重短缺,生产中应避免过量消耗受到严格限制的基础上按顺序考虑其他目标的耗受到严格限制的基础上按顺序考虑其他目标的实现实现目标优先等级:目标优先等级:1 1、P P1 1 产品产品的产量最好不大于产品的产量最好不大于产品的一半的一半2 2、P P2 2 最好能节约设备工时最好能节约设备工时4h4h。3 3、P P3 3 总利润尽可能达到并超过总利润尽可能达到并超过 48 48 元。元。由此,可以如下建立该问题的由此,可以如下建立该问题的最优化模型最优化模型 7/15/202414 决策变量:决策变量:x x1 1 产品产品的产量,的产量,x x2 2 产品产品的产量。的产量。偏差变量偏差变量:P P1 1 等级:正、负偏差变量等级:正、负偏差变量d1+、d1-P P2 2 等级:正、负偏差变量等级:正、负偏差变量d2+、d2-P P3 3 等级:正、负偏差变量等级:正、负偏差变量d3+、d3-x1、x2、d1+、d1-、d2+、d2-、d3+、d3-07/15/202415 约束条件约束条件:绝对约束:绝对约束:5x1+10 x2 60 目标约束:目标约束:x1-2x2+d1-d1+=0 (P1)4x1+4x2+d2-d2+=36 (P2)6x1+8x2+d3-d3+=48(P3)目标函数目标函数:min Z=P1 d1-+P2 d2+P3 d3-7/15/202416 某厂生产某厂生产、两种两种产品,有关数据如表所产品,有关数据如表所示。试求获利最大的生示。试求获利最大的生产方案?产方案?拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 在此基础上考虑:在此基础上考虑:1、产品、产品的产量不低于产品的产量不低于产品的产量;的产量;2、充分利用设备有效台时,不加班;、充分利用设备有效台时,不加班;3、利润不小于、利润不小于 56 元。元。解解:分析分析 第一目标:第一目标:即产品即产品的产量不大于的产量不大于的产量。的产量。第二目标:第二目标:例例2:7/15/202417第三目标:第三目标:规划模型:规划模型:7/15/202418目标规划数学模型的一般形式目标规划数学模型的一般形式7/15/202419 建模的步骤建模的步骤 1 1、根据要研究的问题所提出的各目标与条件,确定、根据要研究的问题所提出的各目标与条件,确定目标值,列出目标约束与绝对约束;目标值,列出目标约束与绝对约束;4 4、对同一优先等级中的各偏差变量,若需要可按其对同一优先等级中的各偏差变量,若需要可按其重要程度的不同,赋予相应的权系数重要程度的不同,赋予相应的权系数 。3 3、给各目标赋予相应的优先因子、给各目标赋予相应的优先因子 P Pl l(l=1.2Ll=1.2L)。)。2 2、可根据决策者的需要,将某些或全部绝对约束、可根据决策者的需要,将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。变量和减去正偏差变量即可。7/15/202420 5 5、根据决策者的要求,按下列情况之一:、根据决策者的要求,按下列情况之一:恰好达到目标值,取恰好达到目标值,取 。允许超过目标值,取允许超过目标值,取 。不允许超过目标值,取不允许超过目标值,取 。构造一个由优先因子和权系数相对应的偏差变量构造一个由优先因子和权系数相对应的偏差变量组成的,要求实现极小化的目标函数。组成的,要求实现极小化的目标函数。7/15/202421 小结小结线性规划线性规划LPLP目标规划目标规划GPGP目标函数目标函数min ,max系数可正负系数可正负min ,偏差变量偏差变量系数系数0 0变量变量x xi,i,x xs s x xa a x xi i x xs s x xa a d d约束条件约束条件绝对约束绝对约束目标约束、绝对约束目标约束、绝对约束解解最优最优最满意最满意7/15/202422 图解法同样图解法同样适用两个变量的目标规划问题适用两个变量的目标规划问题,但其操,但其操作简单,原理一目了然。同时,也有助于理解一般目作简单,原理一目了然。同时,也有助于理解一般目标规划的求解原理和过程。标规划的求解原理和过程。图解法解题步骤图解法解题步骤如下:如下:1、确定各约束条件的可行域,即将所有约束条件、确定各约束条件的可行域,即将所有约束条件(包括目标约束和绝对约束,暂不考虑正负偏差变量)(包括目标约束和绝对约束,暂不考虑正负偏差变量)在坐标平面上表示出来;在坐标平面上表示出来;2、在目标约束所代表的边界线上,用箭头标出正、在目标约束所代表的边界线上,用箭头标出正、负偏差变量值增大的方向;负偏差变量值增大的方向;二、目标规划的图解法二、目标规划的图解法7/15/202423 3、求满足最高优先等级目标的解;、求满足最高优先等级目标的解;4、转到下一个优先等级的目标,在不破坏所有较、转到下一个优先等级的目标,在不破坏所有较高优先等级目标的前提下,求出该优先等级目标的高优先等级目标的前提下,求出该优先等级目标的解;解;5、重复、重复4,直到所有优先等级的目标都已审查完,直到所有优先等级的目标都已审查完毕为止;毕为止;6、确定最优解和满意解。、确定最优解和满意解。例例3 3:用图解法解例:用图解法解例1 1的目标规划模型的目标规划模型7/15/202424 min Z=P1 d1-+P2d2+P3 d3-s.t.5x1+10 x2 60 x1-2x2+d1-d1+=0 4x1+4x2+d2-d2+=36 6x1+8x2+d3-d3+=48 x1、x2、di-、di+、0 i=1,2,34x1+4x2=36 x1-2x2=0 5x1+10 x2=606x1+8x2=48 d3-d2+d1-AFCDE Bo7/15/202425 例例4 4 电视机厂装配彩色和黑白两种电视机,每装配一电视机厂装配彩色和黑白两种电视机,每装配一台电视机需占用装配线台电视机需占用装配线1 1小时,装配线每周计划开动小时,装配线每周计划开动4040小时。预计市场每周彩色电视机的销量是小时。预计市场每周彩色电视机的销量是2424台,每台,每台可获利台可获利8080元;每周黑白电视机的销量是元;每周黑白电视机的销量是3030台,每台台,每台可获利可获利4040元。决策者的目标为:元。决策者的目标为:第一优先级目标:充分利用装配线每周计划开动第一优先级目标:充分利用装配线每周计划开动的的4040小时;小时;第二优先级目标:允许装配线加班;但加班时间第二优先级目标:允许装配线加班;但加班时间每周尽量不超过每周尽量不超过1010小时;小时;第三优先级目标:装配电视机的数量尽量满足市第三优先级目标:装配电视机的数量尽量满足市场需求。因为彩色电视机的利润更高(是黑白电视机场需求。因为彩色电视机的利润更高(是黑白电视机利润的利润的2 2倍),取其市场需求满足权系数为倍),取其市场需求满足权系数为2 2。7/15/202426 模型:模型:x x1 1、x x2 2 彩色、黑白电视机的生产量彩色、黑白电视机的生产量 min Z=P1 d1-+P2 d2+P3(2d3-+1d4-)x1+x2+d1-d1+=40 x1+x2+d2-d2+=40+10=50 x1 +d3-d3+=24 x2+d4-d4+=30 x1、x2、di-、di+-0 i=1,2,3,47/15/202427 d3-d1-d3+d4+d2+d1+d4-d2-x2x1x1+x2=40 x1+x2=50 x1=24x2=30 满意解(满意解(24,26)min Z=P1 d1-+P2 d2+P3(2d3-+1d4-)s.t.x1+x2+d1-d1+=40 x1+x2+d2-d2+=40+10=50 x1 +d3-d3+=24 x2+d4-d4+=30 x1、x2、di-、di+-0 i=1,2,3,47/15/202428例例5、用图解法求解目标规划问题、用图解法求解目标规划问题7/15/20242901 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1BC B(0.6250,4.6875)C(0,5.2083),B、C 线段上的线段上的所有点均是该问题的解(无穷多最优解)。所有点均是该问题的解(无穷多最优解)。7/15/202430 例例6、已知一个生产计划的线性规划模型为、已知一个生产计划的线性规划模型为 其中目标函数为总利润,其中目标函数为总利润,x1,x2 为产品为产品A、B产量。现产量。现有下列目标:有下列目标:1、要求总利润必须超过、要求总利润必须超过 2500 元;元;2、考虑产品受市场影响,为避免积压,、考虑产品受市场影响,为避免积压,A、B的生产生产量不超过量不超过 60 件和件和 100 件;件;3、由于甲资源供应比较紧张,不要超过现有量、由于甲资源供应比较紧张,不要超过现有量140。试建立目标规划模型,并用图解法求解。试建立目标规划模型,并用图解法求解。7/15/202431 解:以产品解:以产品 A A、B B 的单件利润比的单件利润比 2.5 2.5:1 1 为权系数,为权系数,模型如下:模型如下:7/15/2024320 x2 0 x11401201008060402020 40 60 80 100ABCD 结论:结论:C(60,58.3)C(60,58.3)为所求的满意解。为所求的满意解。作图:作图:7/15/202433 检验:将上述结果带入模型,因检验:将上述结果带入模型,因 0;0;0,存在;存在;0,存在。所以,存在。所以,有下式:有下式:minZ=P3 将将 x160,x2 58.3 带入约束条件,得带入约束条件,得30601258.32499.62500;260+58.3=178.3 140;16060158.358.3 100 由上可知:若由上可知:若A A、B B的计划产量为的计划产量为6060件和件和58.358.3件时,件时,所需甲资源数量将超过现有库存。在现有条件下,此所需甲资源数量将超过现有库存。在现有条件下,此解为非可行解。为此,企业必须采取措施降低解为非可行解。为此,企业必须采取措施降低A A、B B产产品对甲资源的消耗量,由原来的品对甲资源的消耗量,由原来的100100降至降至78.578.5(140178.3140178.30.7850.785),才能使生产方案(),才能使生产方案(6060,58.358.3)成为可行方案。)成为可行方案。7/15/202434用图解法求解下列目标规划问题用图解法求解下列目标规划问题7/15/202435CD结论:有无穷多最优解结论:有无穷多最优解 C(2,4)D(10/3,10/3)7/15/202436例:例:用单纯形法求解下列目标规划问题用单纯形法求解下列目标规划问题三、目标规划的单纯形法三、目标规划的单纯形法7/15/202437Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001jP1 000100000P2 120002000P3 8100000010=min,10/2,56/10,11/1=5换出变量换出变量进基变量进基变量7/15/202438Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 053/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001jP1 000100000P2 000011000P3 30005-5010=min10/3,10,6/3,12/3=2,进基变量进基变量换出变量换出变量7/15/202439Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21jP1 000100000P2 000011000P3 000000100 最优解为最优解为x12 2,x2 4 4。但非基变量但非基变量 的检验的检验数为零,故此题有无穷多最优解。数为零,故此题有无穷多最优解。=min4,24,6=4,故故 为换出变量。为换出变量。7/15/202440Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 04002-26-6-1100 x210/301-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-11001jP1 000100000P2 000011000P3 000000100 最优解为最优解为x110/3,,x2=10/3。7/15/202441例:某车间计划生产例:某车间计划生产A A、B B两种产品。决策者首先两种产品。决策者首先考虑要充分利用供电部门分配的电量限额指标考虑要充分利用供电部门分配的电量限额指标62.5kw/62.5kw/日,然后考虑完成与超额完成利润指日,然后考虑完成与超额完成利润指标标1010元元/日。每日可给车间供应所需原料日。每日可给车间供应所需原料8t8t。其他有关数据汇总于下表。应当如何确定产品其他有关数据汇总于下表。应当如何确定产品A A、B B的产量。的产量。产品产品耗电量耗电量(kwkw/单位产品)单位产品)材料消耗材料消耗(t/t/单位产品)单位产品)利润利润(元(元/单位产品)单位产品)A AB B101012122 21 11 12 2试用单纯形法求解。试用单纯形法求解。7/15/202442 解:目标规划问题的数学模型解:目标规划问题的数学模型 min Z=P1(d1-+d1+)+P2 d2-10 x1+12x2+d1-d1+=62.5 x1+2x2+d2-d2+=10 2x1+x2 8 x1,x2,0,d1-,d1+,d2-,d2+07/15/202443(1)确定初始解,建立初始计算表确定初始解,建立初始计算表初始基变量初始基变量:d1-,d2-,x3min Z=P1(d1-+d1+)+P2 d2-10 x1+12x2+d1-d1+=62.5 x1+2x2 +d2-d2+=10 2x1+x2 +x3=8 x1,x2,x3 0,d1-,d1+,d2-,d2+07/15/202444 cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+P1P20d1-d2-x362.510810121221001100-1000100-10cj-zjP1P2检验数检验数j=cj zj 1=0 10P1 1P2 02=10P1 P2-10-1-12-221 7/15/202445 cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+P1P20d1-d2-x362.510810121221001100-1000100-10cj-zjP1P2-10-1-12-221(2)先从检验数先从检验数P1行中,选择行中,选择 min(j0)=min(-10,-12)=-12 进基变量:进基变量:x x2 262.5/1210/28/1出基变量出基变量:d2-再按再按=min(8/1,10/2,62.5/12)=57/15/202446 cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+P100d1-x2x32.55341/2-3/2010001100100-61/2-1/26-1/21/2cj-zjP1P2 -4261-6(3)(3)用用x x2 2替换替换基变量基变量d d2 2-,进行迭代运算,得到下表进行迭代运算,得到下表:(4)重复重复(1)的工作的工作7/15/202447 cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+P100d1-x2x32.55341/2-3/2010001100100-61/2-1/26-1/21/2cj-zjP1P2-4 261-62.5/63/0.5(5)重复重复(2)的工作的工作 检查检查P P1 1行所有系数,行所有系数,P1行还有负数,选行还有负数,选d d2 2+进基变进基变量量,计算计算得得d d1 1-出基变量出基变量7/15/202448用用d d2 2+替换替换基变量基变量d d1 1-,进行迭代运算,得到下表进行迭代运算,得到下表cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+000d2+x2x35/12125/2467/242/35/67/6010 0011/61/12-1/12-1/6-1/121/12-100100cj-zjP1P2 111检验数都为正,得满意解检验数都为正,得满意解:x1=0,x2=5.208,x3=2.79,d2+=0.4177/15/202449 cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+000d2+x2x35/12125/2467/242/35/67/6010 0011/61/12-1/12-1/6-1/121/12-100100cj-zjP1P2 1115/8125/2067/28 非基变量非基变量x x1 1 的的检验数是零检验数是零,用用x x1 1替换替换基变量基变量d d2 2+,进行迭代运算,得下表进行迭代运算,得下表表示有表示有多重解多重解。7/15/202450 cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+000 x1x2x35/8225/4833/16100010 0011/4-1/8-3/8-1/41/83/8-3/25/47/43/2-5/4-7/4cj-zjP1P2 111另一个满意解另一个满意解:x1=0.625,x2=4.6375,x3=2.06257/15/202451例、用单纯形法求解下列目标规划问题例、用单纯形法求解下列目标规划问题7/15/202452Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011jP1 301201000000P2 00000002.501P3 0000010000=min2500/30,140/2,60/1=60,故故 为换出变量。为换出变量。7/15/202453Cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011jP1 0120100303000P2 00000002.501P3 0000010000=min700/30,20/2,=10,故故 为换出变量。为换出变量。7/15/202454Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1jP1 030115-150000P2 0-5/400-5/45/45/2001P3 0000010000=min400/15,=10,故故 为换出变量。为换出变量。7/15/202455Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011jP1 0010000000P2 0-1-1/121/12002/5001P3 01/5-1/151/15100000=min,350/6,1250/6,100/1=75,故故 为换出变为换出变量。量。7/15/202456Cj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211jP1 0010000000P2 00000005/201P3 00-1/121/12101/2-1/200 P3 优先等级目标没有实现,但已无法改进,得到满意解优先等级目标没有实现,但已无法改进,得到满意解 x1 60,x2 175/3,115/3,125/37/15/202457 结果分析:计算结果表明,工厂应生产结果分析:计算结果表明,工厂应生产A产品产品60件,件,B产品产品175/3件,件,2500元的利润目标刚好达到。元的利润目标刚好达到。125/3,表明产品比最高限额少,表明产品比最高限额少125/3件,满足要求。件,满足要求。115/3 表明甲资源超过库存表明甲资源超过库存115/3公斤,该目标没有达公斤,该目标没有达到。到。从表中还可以看到,从表中还可以看到,P3 的检验数还有负数,但其高的检验数还有负数,但其高等级的检验数却是正数,要保证等级的检验数却是正数,要保证 P1目标实现,目标实现,P3等级等级目标则无法实现。所以,按现有消耗水平和资源库存目标则无法实现。所以,按现有消耗水平和资源库存量,无法实现量,无法实现25002500元的利润目标。元的利润目标。可考虑如下措施:降低可考虑如下措施:降低A、B产品对甲资源的消耗量,产品对甲资源的消耗量,以满足现有甲资源库存量的目标;或改变以满足现有甲资源库存量的目标;或改变P3等级目标的等级目标的指标值,增加甲资源指标值,增加甲资源115/3115/3公斤。公斤。若很难实现上述措施,则需改变现有目标的优先等若很难实现上述措施,则需改变现有目标的优先等级,以取得可行的满意解果。级,以取得可行的满意解果。7/15/202458 目标规划建模 1 1、某厂生产、某厂生产A、B、C三种产品,装配工作在同一三种产品,装配工作在同一生产线上完成,三种产品时的工时消耗分别为生产线上完成,三种产品时的工时消耗分别为6 6、8 8、1010小时,生产线每月正常工作时间为小时,生产线每月正常工作时间为200200小时;三种产小时;三种产品销售后,每台可获利分别为品销售后,每台可获利分别为500500、650650和和800800元;每月元;每月销售量预计为销售量预计为1212、1010和和6 6台。台。该厂经营目标如下:该厂经营目标如下:1 1、利润指标为每月、利润指标为每月1600016000元,元,争取超额完成;争取超额完成;2 2、充分利用现有生产能力;、充分利用现有生产能力;3 3、可以、可以适当加班,但加班时间不得超过适当加班,但加班时间不得超过2424小时;小时;4 4、产量以预、产量以预计销售量为准。试建立目标规划模型。计销售量为准。试建立目标规划模型。7/15/2024597/15/2024602.2.已知条件如表所示已知条件如表所示工序工序型号型号每周最大每周最大加工能力加工能力AB(小时(小时/台)台)(小时(小时/台)台)436215070利润(元利润(元/台)台)300450如果工厂经营目标的期望值和优先等级如下:如果工厂经营目标的期望值和优先等级如下:p p1 1:每周总利润不得低于每周总利润不得低于1000010000元;元;p p2 2:因合同要求,因合同要求,A A型机每周至少生产型机每周至少生产1010台,台,B B型机每周至少型机每周至少 生产生产1515台;台;p p3 3:希望工序希望工序的每周生产时间正好为的每周生产时间正好为150150小时,工序小时,工序的的生产时间最好用足,甚至可适当加班。生产时间最好用足,甚至可适当加班。试建立这个问题的目标规划模型。试建立这个问题的目标规划模型。7/15/2024617/15/202462 3.在上题中,如果工序在上题中,如果工序在加班时间内生产在加班时间内生产出来的产品,每台出来的产品,每台A型机减少利润型机减少利润10元,每台元,每台B型机减少利润型机减少利润25元,并且工序元,并且工序的加班时间的加班时间每周最多不超过每周最多不超过30小时,这是小时,这是p4级目标,试建级目标,试建立这个问题的目标规划模型。立这个问题的目标规划模型。7/15/202463 设设x1,x2分别为在正常时间和加班时间生产分别为在正常时间和加班时间生产A型机台数,型机台数,x3,x4分别为在正常时间和加班时间生产分别为在正常时间和加班时间生产B型机台数,目标规划型机台数,目标规划数学模型为:数学模型为:7/15/2024644 4 某某单单位位领领导导在在考考虑虑本本单单位位职职工工的的升升级级调调资资方方案案时时,依依次遵守以下规定:次遵守以下规定:(1)(1)不超过年工资总额不超过年工资总额6000060000元;元;(2)(2)每级的人数不超过定编规定的人数;每级的人数不超过定编规定的人数;(3)(3),级级的的升升级级面面尽尽可可能能达达到到现现有有人人数数的的20%20%,且且无越级提升;无越级提升;(4)(4)级级不不足足编编制制的的人人数数可可录录用用新新职职工工,又又级级的的职职工工中有中有10%10%要退休。要退休。有有关关资资料料汇汇总总于于下下表表中中,问问该该领领导导应应如如何何拟拟订订一一个个满满意的方案。意的方案。7/15/202465解解 设x1、x2、x3分别表示提升到、级和录用到级的新职工人数。对各目标确定的优先因子为:P1不超过年工资总额60000元;P2每级的人数不超过定编规定的人数;P3、级的升级面尽可能达到现有人数的20%。7/15/202466 先分别建立各目标约束。年工资总额不超过60000元 2000(10-100.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1-d1+=600007/15/202467每级的人数不超过定编规定的人数:对级有 10(1-0.1)+x1+d2-d2+=12对级有 12-x1+x2+d3-d3+=15对级有 15-x2+x3+d4-d4+=15,级的升级面不大于现有人数的20%,但尽可能多提;对级有 x1+d5-d5+=120.2对级有 x2+d6-d6+=150.2目标函数:min z=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-)7/15/2024685 已知有三个产地给四个销地供应某种产品,产销地之间的供需量和单位运价见下表。有关部门在研究调运方案时依次考虑以下七项目标,并规定其相应的优先等级:P1B4是重点保证单位,必须全部满足其需要;P2A3向B1提供的产量不少于100;P3每个销地的供应量不小于其需要量的80%;P4所定调运方案的总运费不超过最小运费调运方案的10%;P5因路段的问题,尽量避免安排将A2的产品往B4;P6给B1和B3的供应率要相同;P7力求总运费最省。试求满意的调运方案。7/15/2024697/15/202470解解 上作业法求得最小运费的调运方案见表4-11。这时得最小运费为2950元,再根据提出的各项目标的要求建立目标规划的模型。表4-117/15/202471供应约束 x11+x12+x13+x14300 x21+x22+x23+x24200 x31+x32+x33+x34400需求约束:x11+x21+x31+d1-d1+=200 x12+x22+x32+d2-d2+=100 x13+x23+x33+d3-d3+=450 x14+x24+x34+d4-d4+=250A3向B1提供的产品量不少于100 x31+d5-d5+=1007/15/202472每个销地的供应量不小于其需要量的80%x11+x21+x31+d6-d6+=2000.8x12+x22+x32+d7-d7+=1000.8x13+x23+x33+d8-d8+=4500.8x14+x24+x34+d9-d9+=2500.87/15/202473调运方案的总运费不超过最小运费调运方案的10%7/15/202474因路段的问题,尽量避免安排将A2的产品运往B4x24+d11-d11+=0给B1和B3的供应率要相同(x11+x21+x31)-(200/450)(x13+x23+x33)+d12-d12+=07/15/202475力求总运费最省7/15/202476目标函数为:7/15/2024776.已知条件如表所示已知条件如表所示工序工序型号型号每周最大每周最大加工能力加工能力AB(小时(小时/台)台)(小时(小时/台)台)436215070利润(元利润(元/台)台)300450如果工厂经营目标的期望值和优先等级如下:如果工厂经营目标的期望值和优先等级如下:p p1 1:每周总利润不得低于每周总利润不得低于1000010000元;元;p p2 2:因合同要求,因合同要求,A A型机每周至少生产型机每周至少生产1010台,台,B B型机每周至少型机每周至少 生产生产1515台;台;p p3 3:希望工序希望工序的每周生产时间正好为的每周生产时间正好为150150小时,工序小时,工序的的生产时间最好用足,甚至可适当加班。生产时间最好用足,甚至可适当加班。试建立这个问题的目标规划模型。试建立这个问题的目标规划模型。7/15/2024787/15/202479 7.在上题中,如果工序在上题中,如果工序在加班时间内生产在加班时间内生产出来的产品,每台出来的产品,每台A型机减少利润型机减少利润10元,每台元,每台B型机减少利润型机减少利润25元,并且工序元,并且工序的加班时间的加班时间每周最多不超过每周最多不超过30小时,这是小时,这是p4级目标,试建级目标,试建立这个问题的目标规划模型。立这个问题的目标规划模型。7/15/202480 设设x1,x2分别为在正常时间和加班时间生产分别为在正常时间和加班时间生产A型机台数,型机台数,x3,x4分别为在正常时间和加班时间生产分别为在正常时间和加班时间生产B型机台数,目标规划型机台数,目标规划数学模型为:数学模型为:7/15/202481 8.8.某纺织厂生产两种布料,一种用来做服装,另某纺织厂生产两种布料,一种用来做服装,另一种用来做窗帘。该厂实行两班生产,每周生产时间一种用来做窗帘。该厂实行两班生产,每周生产时间定为定为8080小时。这两种布料每小时都生产小时。这两种布料每小时都生产10001000米。假定米。假定每周窗帘布可销售每周窗帘布可销售7000070000米,每米的利润为米,每米的利润为2.52.5元;衣元;衣料布可销售料布可销售4500045000米,每米的利润为米,每米的利润为1.51.5元。元。该厂在制定生产计划时有以下各级目标:该厂在制定生产计划时有以下各级目标:p1p1:每周必须用足:每周必须用足8080小时的生产时间;小时的生产时间;p2p2:每周加班时数不超过:每周加班时数不超过1010小时;小时;p3p3:每周销售窗帘布:每周销售窗帘布7000070000米,衣料布米,衣料布4500045000米;米;p4p4:加班时间尽可能减少。:加班时间尽可能减少。试建立这个问题的目标规划模型。试建立这个问题的目标规划模型。7/15/202482设设x1,x2分别为每周生产窗帘布和医疗布的小分别为每周生产窗帘布和医疗布的小时数,目标规划数学模型为:时数,目标规划数学模型为:7/15/202483
展开阅读全文