《运筹学》第五章：目标规划培训课件

1第五章目标规划线性规划：单一目标目标规划：多目标、优先次序、综合规划5.1问题的提出和数学模型5.2目标规划模型的图解分析法5.3目标规划的单纯形解法5.4整数规划模型的应用25.1问题的提出和数学模型一、引例：某企业生产Ⅰ、Ⅱ两种产品，其生产的参数如表中所示。在制定生产计划时要考虑如下内容：（1）依据市场反馈信息，Ⅰ产品出现滞销，预测表明，两种产品的生产比例大致保持1:1为宜；（2）设备能力尚有机动的余地，B设备必要时可以加班，但希望加班时间愈少愈好；A设备较为重要，所以既希望能力能够被充分利用，同时又尽量少加班；（3）企业将利润指标定位12元，并力求超过。

企业认为，在上述考虑的目标中，利润要求最为重要；产量比例次之；A设备的重要性是B设备的三倍。试建立该问题的数学模型。3产品设备ABCD利润ⅠⅡ21402204加工能力128161223二、建立模型设x1——Ⅰ产品的产量x2——Ⅱ产品的产量（1）x1-x2=0+d1--d1+min（d1-+d1+

）（2）B：x1+2x2=8A：2x1+2x2=12（3）2x1+3x2=12+d2--d2++d3--d3++d4--d4+mind2+min（d3-+d3+）mind4-C：4x116D：4x2124

目标值d1-d1+实际值实际值∴

d1-·d1+=0∵

d1-0，d1+

0正偏差变量负偏差变量5x1-x2+d1--d1+

=0x1+2x2+d2--d2+

=82x1+2x2+d3--d3+=124x1 164x2

122x1+3x2+d4--d4+

=12Minz=P1d4-+P2(d1-+d1+)+3P3(d3-+d3+)+P3d2+St.x1,x20,di-,di+

0,(i=1,2,3,4)Pi——优先级系数，i越小，则 级别越高。目标规划模型如下：①②③④⑤⑥6⑴引进偏差变量，表示实际值与目标值之间的差距。其中，di-表示负偏差，体现实际值低于目标的大小； di+表示正偏差，体现实际值高于目标的大小。⑵约束分两种形式：系统约束——刚性约束，严格限制；可以不出现；目标约束——柔性约束，弹性限制。必须存在。⑶目标函数只出现偏差变量，而不含决策变量。⑷模型引进优先级系数的概念。三、模型的特点75.2目标规划模型的图解分析①作平面直角坐标系；②作出系统约束所在直线；③作出目标约束所在直线，标出偏差方向；④按优先级次序，确定满意解。8x1x224680246①②③④⑤⑥d1-d2-d3-d4-d1+d2+d3+d4+ABCDEF(3,3)G9x1+2x2+d2--d2+

=82x1+2x2+d1--d1+=124x1 164x2

122x1+3x2

12Minz=P1(d1-+d1+)+P2(d2-+d2+)St.x1,x20,di-,di+

0,(i=1,2,3)例：有目标规划模型如下，用图解分析求解①②③④⑤10x1x224680246①②③④⑤d2-d1-d2+d1+115.3目标规划的单纯形解法

目标规划的单纯形法与线性规划单纯形法类似。例：见下例。最优性判定准则：（1）所有检验数均0，则该表为最优解 表；（2）若某行具有负值检验数，但负检验 数列较高优先级中具有正检验数， 则该表为最优解表。12x1+d1--d1+

=102x1+x2+d2--d2+

=403x1+2x2+d3--d3+=100Minz=P1(d1

+d2+)+P2d3St.x1,x20,di-,di+

0,(i=1,2,3)例：单纯形法求解下述目标规划模型13Cj→XBbCB101-1 000021001 -10032 00001-100p10 0 p1p201040100d1

d2

d3

p10p2cj-zjx1x2 d1

d1+

d2d2+

d3

d3+p1p2-111 -3–21101-1 000001-221 -10002-33001-1102070x1d2

d3

0

0p2cj-zjp1p211 0–23-3114Cj→XBbCB11/200 1/2-1/20001/2-111/2-1/20001/200-3/23/21-100p10 0 p1p20201040x1

d2+

d3

0

0p2cj-zjx1x2 d1

d1+

d2d2+

d3

d3+p1p211 –1/23/2-3/21101-1 000001-221 -10000 1-2-221