第4章目标规划

1、OR21第4章 目标规划要求1、理解概念2、学会建模3、学会图解法和单纯形解法4、举一反三，学会应用123OR224.1目标规划的概念及数学模型1多目标问题多目标线性规划例1 产品资源 A B限量原材料设备工时 2 1.5 1 2 50 40单位利润 80 100求利润最大的生产方案OR234.1目标规划的概念及数学模型2例2：例1的要求多元化： 1、B产品不超过10单位 2、利润不低于1600元 3、充分利用车间的生产能力，尽量不加班。解：问题分析：找差别、定概念 1）系统约束：原有约束条件是一种刚性约束，称之为系统约束系统约束：2x1+1.5x250 (1) x1+ 2x2 40 (2)O

2、R244.1目标规划的概念及数学模型3 2）目标约束：新提出的目标要求实际上也是约束条件，称之为目标约束目标约束 3）目标期望值：目标约束的目标一定要明确，给出确切的量值，即目标期望值目标期望值 4）偏差变量：目标约束不是刚性的，而是弹性的，允许在一定范围内有偏差，这更接近于实际。为表达这种灵活性，便引入了偏差变量偏差变量的概念，偏差变量有正负之分，表示为：d+和d-， d+表示超过目标值的部分； d-表示不足目标值的部分.显然有d- d+=0OR25 本题三个目标约束依次表示为： x2+ d1- -d1+=10 80 x1+100 x2+ d2- -d2+ =1600 x1 + 2x2+ d

3、3- -d3+ =40 5）目标的重要程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为P1级，次之者为P2级 P看成实数 P1P24.1目标规划的概念及数学模型4OR264.1目标规划的概念及数学模型56）目标规划的目标函数：要求恰好达到目标值： minf(d+ + d- )要求不超过目标值,但允许不足目标值： minf(d+)要求不低于目标值，但允许超过目标值： minf(d- )OR274.1目标规划的概念及数学模型67）目标规划的目标函数： 目标规划有多个目标，我们已经把它转化为目标约束，整个问题的目标就是使得实施结果与目标期望值的偏差最小 于是本题目标函数表示为： minZ

4、=P1 d1+ +P2 d2- +P3( d3- +d3+) OR284.1目标规划的概念及数学模型7综上所述，本题的数学模型为： minZ=P1 d1+ +P2 d2- +P3( d3- +d3+) 2x1+1.5x2 50 x2+ d1- -d1+=10 80 x1+100 x2+ d2- -d2+ =1600 x1 + 2x2+ d3- -d3+ =40 x1 ，x2 ，di-，di+ 0 ,i=1,2,3OR294.1目标规划的概念及数学模型8说明：1）有时系统约束转化为目标约束，则不再表示为系统约束。2）有时同级别的目标中，其重要程度又有差别，则设置不同的权重。设问题有K个目标，L个

5、优先等级，数学模型为：minZ= PL (WL-i di-+WL+i di+ ) aijxj+ di- - di+ =bi, i=1,2,k aijxj (= ) bi i=k+1,k+m xj ，di-，di+ 0 ,j=1,n;i=1,2,kOR2104.2目标规划的图解法图解例2 x1x2102030 4010 203040d1-d1+d2-d2+d3+d3-OABCOR2114.3 目标规划的单纯形解法目标规划使用单纯形法求解， di-，di+ 视为普通变量， P1P2 PL例题4加工方式 单产耗时工时费用优质率资源量正常生产 2.01000.99100加班生产 2.01500.98转

6、承包2.5800.95临时工3.0800.90OR212例题4建模要求：P1：尽量满足市场需求（100件） P2：优质率不低于98% P3：生产费用不超过22000元解：设四种生产方式依次为x1,x2,x3,x4 则：minZ=P1 d1- +P2 d2- +P3 d3+ 2x1 100 x1+x2+x3+ x4+d1- - d1+ =100 x1- 3x3-8x4+ d2- - d2+ =0 200 x1+300 x2+200 x3+240 x4+ d3- - d3+ =22000 xj, di-,di+ 0 j=1,2,3,4 i=1,2,3OR213例题4 求解.Cj00000P10P2

7、00P3CBXBbx1x2x3x4x5d1-d1+d2-d2+d3- d3+j0P1P20X5d1-d2-d3-10010002200021120001030001-320001-8240100001000-100001000-100001000-1jP1P2P3-1-10-100-130-180000000100000010000001OR214目标规划的灵敏度分析minZ=P1d1+P2d2 P3 (5 d3+3 d4 )+ P4d1+ X1+2 X2 +d1- -d1+= 6 X1+2 X2 +d2-d2+= 9 X1-2 X2 + d3- -d3+= 4 X2 + d4-d4+= 8

8、Xj, di- , di+ 0 ,j=1,2 ; i=1,2,3,4OR215 minZ=P1d1-+P2d2 P3 d1+ + P4 (5 d3+3 d4 )minZ=P1d1-+P2d2 P3 (W1 d3+W2 d4 )+ P4d1+ (W1 ,W2 0)OR216 Cj00P1P30P25P403P40CBXBbx1x2d1-d1+d2-d2+d3- d3+d4-d4+0P33P40 x1d1+d4-x213/233/45/4100000010-10001001/21-1/41/4-1/2-11/4-1/41/20-1/41/40010001000-10jP1P2P3P40000000

9、0-10-100000001-3/400-13/4000-17/4000-3/40000000-3OR217 Cj00P1P40P2W1P30W2P30CBXBbx1x2d1-d1+d2-d2+d3- d3+d4-d4+003P40 x1d1+d4-x213/233/45/4100000010-10001001/21-1/41/4-1/2-11/4-1/41/20-1/41/40010001000-10jP1P2P3P400000000-100-1000000-W2/4100W2/4-100*000-W2/4 0000000-W2 0*=W2/4 -W1OR2184.5 目标规划应用举例之一例

10、5. A B C工时限制工时/件 5 8 12 120利润/件100 140 252要求：P1:充分利用工时 P2：A、B、C分别达到5、5、8件，并按工时利润确定权重 P3：加班时间不要超过16小时 P4：A、B、C月销售量10、12、10件 P5：尽量减少加班时间OR2194.5 目标规划应用举例之一8X1+5X2+12X3 +d1- - d1+ =170 X1+ d2- -d2+= 5 X2+ d3- -d3+= 5 X3+ d4- -d4+= 8 8X1+5X2+12X3 +d5- - d5+ =170+16 X1 + d6- -d6+= 10 Xj, di- , di+ 0 ,j=1

11、,2,3 i=1,2,5minZ=P1d1-+P2(20 d2- +18 d3- +21d4-)+P3 d5+ +P4(d6-+ d7-+ d8-)+P5 d1+OR2204.5 目标规划应用举例之二例7：多目标运输问题如下表。目标要求： P1：产地不存货，且销量至少满足一半 P2：满足B1需求，且A4B2尽量少运 P3：总运费最小 销地产地 B1 B2 B3产量 A1 A2 A3 A4 5 8 3 7 4 5 2 6 9 4 6 61004040120 销量 120 140 140400/300OR2214.5 目标规划应用举例之二解：设Ai到Bj的运输量为xijX11+ X12 + X13 +d1-d1+=100X21+ X22 + X23 +d2-d2+=40X31+ X32 + X33 +d3-d3+=40X41+ X42 + X43 +d4-d4+=120X11+ X21 + X31 + X41+d5-d5+=120/2X12+ X22 + X32+ X42+d6-d6+=140/2X13+