第四章目标规划.

•第四章目标规划•重点：•1、目标规划的数学模型及建模•2、目标规划的解法：–图解法–单纯形法•难点：目标规划的数学模型及建模•§1目标规划的数学模型例1某工厂生产Ⅰ、Ⅱ两种产品，有关数据见下表,试求获利最大的生产方案。ⅠⅡ拥有量原材料㎏设备21121110利润元/件810目标规划的概念•一般来说,一个计划问题要满足多方面的要求.•线性规划有最优解得必要条件是其可行解集非空,即各约束条件彼此相容.多目标可能带来约束条件冲突.•目标规划承认各项决策要求的合理性,不强调绝对意义上的最优,得到的通常是满意解.解•这是一个单目标的规划问题，设产品Ⅰ、Ⅱ的产量分别为x1和x2，用线性规划问题表述为•maxz=8x1+10x2•2x1+x2≤11•x1+2x2≤10•x1,x2≥0•用图解法(或单纯形法）求得最优决策方案为：x1=4,x2=3,z=62元。多目标决策•实际上工厂在决策时，要考虑市场等一系列其它条件。如•（1）根据市场信息，产品Ⅰ的销售量有下降的趋势，故考虑产品Ⅰ的产量不大于产品Ⅱ。•（2）应尽可能利用设备，但不希望加班。•（3）应尽可能达到并超过计划的56元的利润指标。目标规划数学模型有关的概念。这样考虑问题时，便为多目标决策问题。目标规划方法是解决这类决策问题的方法之一。下面引入建立目标规划数学模型有关的概念。1、正、负偏差变量d+,d-.2、绝对约束和目标约束。3、优先因子（优先等级Pk）与权系数。4、目标规划的目标函数。•minz=f(d+,d-).基本形式有三种：•（1）恰好达到minz=d++d-•（2）不超过目标值minz=d+•（3）要求超过目标值minz=d-•对于每一个具体目标规划问题，可根据决策人的要求和赋予各目标的优先因子来构造目标函数，以下用例子来说明。例2目标规划的数学模型•例1的决策者在原材料供应受严格限制的基础上考虑：•首先是产品Ⅱ的产量不低于产品Ⅰ的产量；•其次是充分利用设备有效台时,但不加班；•再次是利润不小于56元。•求决策方案。解•设两种产品的产量分别为x1,x2,按决策者所要求的，分别赋予这三个目标P1,P2,P3优先因子，这问题的数学模型是：•minz=P1d1++P2(d2-+d2+)+P3d3-•2x1+x2≤11•x1-x2+d1--d1+=0•x1+2x2+d2—d2+=10•8x1+10x2+d3—d3+=56•x1，x2，di-，di+≥0，i=1,2,3.目标规划的一般数学模型为)(min11klkkLlKklklddPz(4.1)KkddnjxbxaKkgddxckkjnjijijkkknjjkj,,1,0,,,1,0),(,,2,1,11某工厂生产两种产品，受到原材料供应和设备工时的限制，单件利润等有关数据已知的条件下，要求制订其生产计划，具体数据如下：产品AB限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）68例21、线性规划模型设生产产品A、B的数量分别为x1，x2，并且要求利润极大化，有生产计划的LP规划如下：很容易解得：x1＝8，x2＝2，最优目标函数为64元。0,404460105St.86Max21212121xxxxxxxx目标规划的数学模型回到上面的例子。计划人员征求各方的意见，确定在生产计划中应该考虑如下的因素：1首先由于产品B销售疲软，因此产品B的生产数量最好不超过产品A的一半。2其次由于原材料严重短缺，生产中应该避免过量消耗。3第三最好能够节约4小时的工时。4最后计划利润不少于48元。四级目标44332211mindPdPdPdPz目标上面四个因素，即是提出了四个目标，用数学的形式表示如下：•x1－2x2＝0•5x1＋10x2＝60•4x1＋4x2＝36•6x1＋8x2＝48前面已经讨论过，目标规划的目的，在于评估在现有环境下（资源和约束）对多个目标实现的可能程度。这种实现的可能程度，我们用离要求目标的偏离值或来描述，i代表了第i个目标，＋代表了正向偏离该目标值的数值，－代表了负向该偏离目标值的数值。因此四个目标可以表示为如下形式：488648863644364460105601050202442121332121222121112121ddxxxxddxxxxddxxxxddxxxx目标规划数学模型44332211mindPdPdPdPz4,3,2,1,0,,,488636446010502214421332122211121iddxxddxxddxxddxxddxxii【例3】P113习题4.6•某种牌号的鸡尾酒酒系由三种等级的酒兑制而成。已知各种等级酒的每天供应量和单位成本如下：•等级ⅰ：供应量1500单位/天，成本6元/单位；•等级ⅱ：供应量2000单位/天，成本4.5元/单位；•等级ⅲ：供应量1000单位/天，成本3元/单位；•该种牌号的酒有三种商标（红、黄、蓝），各种商标酒的混合及售价如表7-17所示。表4-17商标兑制要求单位售价/元红ⅲ少于10%ⅰ多于50%5.5黄ⅲ少于70%ⅰ少于20%5.0蓝ⅲ少于50%ⅰ多于10%4.8要求•为保持声誉，确定经营目标为：•p1兑制要求配比必须严格满足；•p2企业获取尽可能多的利润；•p3红色商标酒每天量不低于2000单位。•试对该问题建立目标规划模型；解•设j=1,2,3分别代表红、黄、蓝三种商标的离序号，则•Xij——第i等级酒在第j种商标酒中所占数量；•yj——第j等商标酒的生产数量•可建立目标规划数学模型如下：•minz=p1(d1-+d1++d2-+d2++d3-+d3++d4-+d4++d5-+d5++d6-+d6+)+p2d7-+p3d8-•y1=X11+X21+X31•y2=X12+X22+X32（产量关系约束）•y3=X13+X23+X33•X11+X12+X13≤1500•X21+X22+X23≤2000（原料限制约束）•X31+X32+X33≤1000•P1•X31+d1--d1+=10%y1•X11+d2--d2+=50%y1•X32+d3--d3+=70%y2•X12+d4--d4+=20%y2（配比限制）•X33+d5--d5+=50%y3•X13+d6--d6+=10%y3•P2•5.5y1+5.0y2+4.8y3+d7--d7+=5.5×4500(利润限制)•P3•y1+d8--d8+=2000(红色商标酒产量限制)•yj≥0,Xij≥0,dk-,dk+≥0,(i=1,2,3;j=1,2,3;k=1,2,3,…8)建立目标规划的数学模型•建立目标规划的数学模型时，需要确定目标值、优先等级、权系数，绝对约束和目标约束等。•§2目标规划的图解法•§3解目标规划的单纯形法•§4灵敏度分析•§5应用举例【例1】判断下述说法是否正确？•（a）线性规划模型是目标规划模型的一种特殊形式；•（b）正偏差变量应取正值、负偏差变量应取负值；•（c）目标规划模型中，若不含系统（绝对）约束，则一定有解；•（d）目标规划的数学模型应同时包括系统约束和目标约束。•答：•（a）正确。模型结构完全一致，可以将线性规划模型改写成单一目标形式的目标规划。•（b）错误。正负变量都定义取非负的值。•（c）正确。目标规划的解是一种相对满意的解。•（d）错误。可以没有系统约束。§2目标规划的图解法•minz=P1d1++P2(d2-+d2+)+P3d3-•2x1+x2≤11•x1-x2+d1--d1+=0•x1+2x2+d2-—d2+=10•8x1+10x2+d3-—d3+=56•x1，x2，di-，di+≥0，i=1,2,3.目标规划图解法的步骤：•1画出绝对约束（与线性规划相同）；•2画出目标约束：–画出正负偏差为零的直线；–用箭头画出有正偏差和负偏差的区域；•3按优先级别的高低依次找到最优解（满意解）。图解法x2BEFCGDJAx1d1-d1+d2+d2-d3-d3+例3•某电视机厂装配黑白和彩色电视机，每装一台需占用装配线1小时，装配线每周计划开动40小时。预计每周彩色电视机的销售量是24台，每台可获利80元，黑白电视机的销售量是30台，每台可获利40元。该厂确定的目标为：•第一优先级：充分利用装配线每周计划开动40小时；•第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时；•第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权数为2。•试建立目标规划的数学模型，并求解。解•首先建立目标规划的数学模型：设x1,x2分别表示黑白电视机的产量分别为,按决策者所要求的，分别赋予这三个目标P1,P2,P3优先因子，这问题的数学模型是：•minz=P1d1-+P2d2++P3（2d3-+d4-）•x1+x2+d1--d1+=40•x1+x2+d2--d2+=50•x1+d3--d3+=24•x2+d4—d4+=30•x1，x2，di-，di+≥0，i=1,2,3,4.例3的图解法•X2•o•x1FEBACDHGd4-d3-d2-d1+d1-d2+d4+d3+§3解目标规划的单纯形法•例4试用单纯形法求解例2•minz=P1d1++P2(d2-+d2+)+P3d3-•2x1+x2+xs=11•x1-x2+d1--d1+=0•x1+2x2+d2—d2+=10•8x1+10x2+d3—d3+=56•x1，x2，xs,di-，di+≥0，i=1,2,3.表4-1（1）取xs,d1-,d2-,d3-为基变量，cj0000P1P2P2P3θCBXBbx1x2Xsd1-d1+d2-d2+d3-d3+P2p3Xsd1-d2-d3-110105621181-121011-11-11-1zP1P2p3-1-8-2-10121表4-2cj0000P1P2P2P3θCBXBbx1x2Xsd1-d1+d2-d2+d3-d3+p3Xsd1-x2d3-65563/23/21/23111-1-1/21/21/2-51/2-1/2-1/251-16/3zP1P2p3-31151表4-3cj0000P1P2P2P3θCBXBbx1x2Xsd1-d1+d2-d2+d3-d3+p3Xsd1-x2x132421111-1234/3-5/3-2-3-4/35/3-1/2-1/2-1/61/31/21/21/6-1/3zP1P2p31111表4-4cj0000P1P2P2P3θCBXBbx1x2Xsd1-d1+d2-d2+d3-d3+p3Xsd3+x2x11410/310/3111-12-1/32/31-21/3-2/3-161/31/31-6-1/3-1/3-11zP1P2p31111例4•minz=P1d1++P2d2++P3(5d3-+3d4-)+P3d1+•x1+2x2+d1--d1+=6•x1+2x2+d2--d2+=9•X1-2x2+d3--d3+=4•x2+d4--d4+=2cj00P1P40P25P303P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P105p33p3d1-d2-d3-d4-6942111022-211-101000-100001000-100001000-1zP1P2P3P4-10-50-20701001010000500030初始单纯形表cj00P1P40P25P303P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0P43p30x1d1+d4-x213/233/45/4100000010-10001001/21-1/41/4-1/2-1¼-1/4½0¼-1/4-1/20-1/41/4001000-10zP1P2P3P4100100¾-101-3/410017/40003/4000000030最终单纯形表第4节目标规划的灵敏度分析•目标规划建模时，目标优先