03 目标规划

第1页运筹帷幄之中决胜千里之外运筹学课件目标规划GoalProgramming第2页目标规划线性目标规划的基本概念与数学模型线性目标规划的图解法线性目标规划的序贯式算法线性目标规划的单纯形算法第3页引例：某厂生产甲、乙两种产品，生产单位产品所需原材料及占用设备台时、可获利润如下：甲乙拥有量原材料2111设备1210利润8001000工厂在安排生产计划时，有如下考虑：第4页1.尽可能不超计划使用原材料；2.甲的生产量不超过乙的生产量；3.尽可能充分利用设备，但不希望加班；4.尽可能超过计划利润5600元。设x1、x2表示甲乙两种产品的生产量，则2x1+x2≤11;x1-x2≤0;x1+2x2≤10;8x1+10x2≥56第5页1.理想值（期望值）2.正负偏差变量d+与d-3.绝对约束与目标约束4.优先级与权因子5.目标规划的目标函数（1）要求恰好达到目标值min(d-+d+)（2）要求不超过目标值min(d+)（3）要求不低于目标值min(d-)目标规划的基本概念与特点第6页2x1+x211x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1,x2,di-,di+0di-×di+=0d1-:x1产量不足x2部分d1+:x1产量超过x2部分d2-:设备使用不足10部分d2+:设备使用超过10部分d3-:利润不足56部分d3+:利润超过56部分第7页目标函数minZ1=d1+minZ2=d2-+d2+minZ3=d3-或minZ=p1d1++p2(d2-+d2+)+p3(d3-)min{p1d1+,p2(d2-+d2+),p3(d3-)}第8页mkddnjxmigddxCLtbxadwdwpkkjnjiiijijnjtjtjklmkklkklkl10,1011,}min{11110第9页8.2线性目标规划的图解法例1min{p1d1-,p2d2+,p3d3-}5x1+10x2≤60x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48x1,x2,di-,di+≥0第10页x1x2O0x1x2O0①BAd1-d1+②Cd2+d2-③Dd3-d3+FE④min{p1d1-,p2d2+,p3d3-}第11页CFED围成的区域为目标规划的解空间。C(6,3)F(4.8,2.4)E(8,0)D(9,0)第12页根据优先级的先后次序，将原多目标问题分解为一系列传统的单目标线性规划问题，然后依次求解。注：需把每一优先级求得的目标值作为新的约束加到优先级在它之后的每一个单目标问题中。8.3线性目标规划的序贯式算法第13页8.4线性目标规划的单纯形法minp1(d1++d2+)+p2d3-+p3d4++p4(d1-+1.5d2-)s.t.x1+d1--d1+=30x2+d2--d2+=158x1+12x2+d3--d3+=1000x1+2x2+d4--d4+=40x1,x2,di-,di+≥0(i=1,2,3,4)第14页00p41.5p4p20p1p10p3CBXBbx1x2d1-d2-d3-d4-d1+d2+d3+d4+p4d1-30101000-10001.5p4d2-150[1]01000-100p2d3-1000812001000-100d4-40120001000-1σp10000001100p2-8-1200000010p30000000001p4-1-1.5000011.500第15页00p41.5p4p20p1p10p3CBXBbx1x2d1-d2-d3-d4-d1+d2+d3+d4+p4d1-30101000-10000x2150101000-100p2d3-820800-1210012-100d4-10[1]00-201020-1σp10000001100p2-80012000-1210p30000000001p4-1001.5001000第16页00p41.5p4p20p1p10p3CBXBbx1x2d1-d2-d3-d4-d1+d2+d3+d4+p4d1-2000120-1-1-20[1]0x2150101000-100p2d3-74000041-80-4-180x110100-201020-1σp10000001100p2000-408041-8p30000000001p4000-0.501120-1第17页00p41.5p4p20p1p10p3CBXBbx1x2d1-d2-d3-d4-d1+d2+d3+d4+p3d4+2000120-1-1-2010x2150101000-100p2d3-580008-1210812-100x13010-1000-1000σp10000001100p20081200-8-1210p300-1-2011200p40011.5000000