华东理工大学工商经济学院:《运筹学》 目标规划与整数规划

目 公 5方 筹 规划 学

Page : 1 QSC 华东理工大学 工商经济学院 运筹学 运筹学 目标规划

多目标决策问题 实际问题决策经常面临的问题: 方案优劣并不以单一准则为目标,而是以多重准则为目标 约束条件并不完全符合严格的刚性条件,具有一定的弹性 可能的弹性约束 最好等于 最好不大于 最好不小于

Page:2 QSC 华东理工大学 工商经济学院 运筹学 多目标决策问题 实际问题决策经常面临的问题： ➢方案优劣并不以单一准则为目标，而是以多重准则为目标 ➢约束条件并不完全符合严格的刚性条件，具有一定的弹性 可能的弹性约束： 最好等于 最好不大于 最好不小于

弹性约束的处理方法 实际量+d-q=目标值 负偏差变量 正偏差变量 最好等于 Min d+d 最好不大于: Min d 最好不小于:

Page:3 QSC 华东理工大学 工商经济学院 运筹学 弹性约束的处理方法 实际量＋ d －－d + = 目标值 负偏差变量 正偏差变量 − + 最好等于： Min d + d + 最好不大于： Min d − 最好不小于： Min d

顾客访问策略 老顾客新顾客正常可用访问时间 访问每一顾客所需时间 2 640小时 平均可获销售利润 250 125 目标: 访问时间最好不超过680小时 访问时间最好不少于600小时 销售收入尽量不少于70,000; 访问老顾客数最好不少于200个; 访问新顾客数最好不少于120个

Page:4 QSC 华东理工大学 工商经济学院 运筹学 顾客访问策略 老顾客 新顾客 正常可用访问时间 访问每一顾客所需时间 2 3 640 小时 平均可获销售利润 250 125 目标： •访问时间最好不超过680小时； •访问时间最好不少于600小时； •销售收入尽量不少于70,000； •访问老顾客数最好不少于200个； •访问新顾客数最好不少于120个

模型一顾客访问策略 Min Z=PdI +P2d2+Pd3+ Pda +psds 2x1+3x2+a1-d+=680 2x1+3x2+d2-d2=600 250x1+125x2+d3-d3=70,000 x1+d4-a4+=200 x+d=-d+=120 所有变量≥0

Page:5 QSC 华东理工大学 工商经济学院 运筹学 模型－顾客访问策略            + − = + − = + + − = + + − = + + − = = + + + + − + − + − + − + − + + − − − − 0 120 200 250 125 70,000 2 3 600 2 3 680 2 5 5 1 4 4 1 2 3 3 1 2 2 2 1 2 1 1 1 1 2 2 3 3 4 4 5 5 所有变量 x d d x d d x x d d x x d d x x d d St Min Z Pd P d P d P d P d

目标规划解的几何分析 600 500 400 300 200 100 1002030~400500 (2

Page:6 QSC 华东理工大学 工商经济学院 运筹学 目标规划解的几何分析 X 100 300 200 600 500 400 X 2 100 200 300 400 500 1 (1) − d1 + d1 (2) − d2 + d2 (3) + d3 − d3 (4) − d4 + d4 (5) + d5 − d5

目标规划的求解—序贯算法 Min z= pdt t pd+p 3+Pd4+P3d5 2x,+3xn+d1-d;+=680 2x1+3x2+d2-d+=600 250x1+125x2+a2-d=70,000 +d-d+=200 +d-d=120 所有变量≥0

Page:7 QSC 华东理工大学 工商经济学院 运筹学            + − = + − = + + − = + + − = + + − = = + + + + − + − + − + − + − + + − − − − 0 120 200 250 125 70,000 2 3 600 2 3 680 2 5 5 1 4 4 1 2 3 3 1 2 2 2 1 2 1 1 1 1 2 2 3 3 4 4 5 5 所有变量 x d d x d d x x d d x x d d x x d d St Min Z Pd P d P d P d P d 目标规划的求解---序贯算法

第一级目标 600 500 Min z=d St 2x1+3x2+d1-d1+=680 200 所有变量≥0 100200300490500 0 2x1+3x,≤680 所有变量≥0

Page:8 QSC 华东理工大学 工商经济学院 运筹学     + + − = = − + + 0 2 3 680 1 2 1 1 1 所有变量 x x d d St Min Z d       +  = + 0 2 3 680 0 1 2 1 所有变量 x x d 第一级目标 X 100 300 200 600 500 400 X 2 100 200 300 400 500 1 (1) − 1 d + 1 d

第二级目标 600 Min Z=d 300 2x1+3x2≤680 d200 S12x+3x2+d2-d2=600 所有变量≥0 100200300~400500 (2)(1) d2=0 2x,+3x<680 2x1+3x,≥600 所有变量≥0

Page:9 QSC 华东理工大学 工商经济学院 运筹学       + + − = +  = − + − 0 2 3 600 2 3 680 1 2 2 2 1 2 2 所有变量 x x d d x x St Min Z d 第二级目标         +  +  = − 0 2 3 600 2 3 680 0 1 2 1 2 2 所有变量 x x x x d X 100 300 200 600 500 400 X 2 100 200 300 400 500 1 (1) − 1 d + 1 d (2) − 2 d + 2 d

10 第三级目标 600 Min Z 2x1+3x2≤680 300 2x1+3x2≥600 d2200 St 250x,+125x+d,-d+=70 所有变量≥0 100203N0400500 d2=0 (3)(2)(1) 2x1+3x2≤680 2x1+3x2≥600 250x1+125x2≥70,000 所有变量≥0

Page:10 QSC 华东理工大学 工商经济学院 运筹学 第三级目标         +  +  +  = − 0 250 125 70,000 2 3 600 2 3 680 0 1 2 1 2 1 2 3 所有变量 x x x x x x d X 100 300 200 600 500 400 X 2 100 200 300 400 500 1 (1) − 1 d + 1 d (2) − 2 d + 2 d (3) + 3 d − 3 d         + + − = +  +  = − + − 0 250 125 70,000 2 3 600 2 3 680 1 2 3 3 1 2 1 2 3 所有变量 x x d d x x x x St Min Z d