第三章目標规划和整数规划.pptVIP

第三章目标规划和整数规划; 第三章目标规划和整数规划;3．1目标规划 3．1．1单目标规划 ; (2)利润目标为140（百元） 此目标称之为预定目标，实际完成的量与预定目标 之间可能出现偏差，通常用d+、d-（d+、d-≥0）表示， 称为偏差变量。 其中： d+表示超过预定指标的部分， d-表示未达到预定指标的部分 在客观条件下，最终完成的结果可能出现以下三种情况： ① d+0,d-=0 表明超额完成预定指标 ② d-0,d+=0 表明未达到预定指标 ③ d+ =d- = 0 表明恰好完成预定指标 上述三种情况可用模型表示; 8x1 + 6x2;3．1．1．2 单目标规划解 ;[; 由此可得：x1=12，x2=6，d+=0，d-=8 完成利润132（百元） 3．1．2 级别相同的多目标规划 3．1．2．1数学模型 （1）实现利润目标122（百元） （2）产品A的产量不多于10 设：di+,di-(i=1,2)分别为??过目标值的部分，及未完成目标值的部分。; 8x1 + 6x2 + d1- - d1+ = 122 x1 +d2- - d2+ = 10 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1，x2，d1+,d1-，d2+,d2-≥0 ;3．1．2．2单纯形表;x1=10、x2=7 x3=6 x4=0 d1+=d1-=d2+=d2-=0，完成利润122，两个目标均已实现。; 3．1．3具有优先级的多目标规划 3．1．3．1数学模型 例：P1: 充分利用设备有效台时，不加班； P2: 产品B的产量不多于4； P3: 实现利润130（百元）;3．1．3．2目标规划图解法 仍以例3为例 （1）根据系统约束④，确定可行域，如图 多边形OAB为该目标规划的可行域； （2）不考虑偏差，即：di+=di-=0（i=1,2,3)，然后按 顺序作出目标约束相应的直线，并标出di+0,di-0的方向 。（3）按优先顺序找出该目标的满意解：;F;F;3．1．3．3单纯形法;[;[;x1* =13，x2* =4， Z=128（百元）。 3．1．4 目标规划的目标 （1）决策人希望恰好实现预定的第i个目标 Min Z= di+ + di- （2）决策人不希望超过预定的第i个目标 Min Z= di+ （3）决策人希望超过预定的第i个目标 min Z= di- ;3.2整数规划 3．2．1整数规划数学模型 Max Z（X）= c1x1+c2x2+…+cnxn ai1x1 + ai2x2+…+ain xn≤(=,≥)bi x1，x2，…，xn ≥0 ;3.2.2分枝限界法 例 Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 （A）： 2x1 + x2 ≤ 9 x1，x2 ≥ 0 且为整数 ;C; Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 （B1）： 2x1 + x2 ≤9 x1 ≤3 x1，x2 ≥0 ;C;C; Z3=13和Z4=131/2均小于界值Z2，不可能成为最优值，将被剪掉（剪枝）。 由此可得出问题（A）的最优解就是问题（B2）的最优解。即： X*=（4，1）；Z（X*）=14;树状图:;3.2.3割平面法 例： Max Z（X）=3x1+2x2 2x1 + 3x2 ≤14 （A）： 2x1 + x2 ≤9 x1，x2 ≥0 且为整数;（2）构造Gomory约束（割平面） 在最终单纯形表中，任意选择一个非整数变量（如x2），写出该变量所在行的方程式： x2 + 1/2x3 –1/2x4=5/2 将各变量的系数及常数项分解为整数与非负真分数之和；再将系数为整数的变量移到方程式左端，系数为分数的变量移到方程式右端 x2 –x4-2=1/2-（1/2x3+1