《运筹学》教案-目标规划数学模型课件.ppt

1、1第六章 目标规划2目标规划 线性规划的缺陷 目标规划的数学模型 目标规划的求解方法 目标规划的图解法 目标规划的单纯形法 目标规划的练习 返回3线性规划的缺陷 线性规划只研究在满足一定的条件下，单一的目标函数取最优的问题，但实际应用中经常遇到多目标决策问题，而且这些指标之间的重要程度也不一定相同，有些指标之间又往往互相发生矛盾。当约束条件之间存在矛盾时，用线性规划得不到问题的可行解，使实际问题无法解决。线性规划模型是实际问题的抽象，实际问题在决策过程中总有一定的灵活性。决策目标一般是满意决策而不是最优决策。线性规划把各个约束条件的重要性等同看待，这也往往不符合实际情况。线性规划问题是”刚性”

2、的，而实际决策问题是”软性”的。返回示例示例4线性规划的缺陷示例某厂生产A、B两种产品，情况如下表所示。如何安排，可使利润值最大？返回产品需要劳动力（人工）需要设备（台时）单位利润A91800B1311000每月可用11780,1171398100080021212121xxxxxxxxMaxzv约束条件相互矛盾，无可行约束条件相互矛盾，无可行解，因而无法进行生产；解，因而无法进行生产；v关于人工的约束条件不必严关于人工的约束条件不必严格遵守，因此其重要性不如格遵守，因此其重要性不如关于设备台时的约束。关于设备台时的约束。5目标规划数学模型目标规划数学模型 甲甲 乙乙 有效工时有效工时金工金工

3、 4 2 400装配装配 2 4 500收益收益 100 80 LP：maxZ=100X1+80X2 2X1+4X2 5004X1+2X2 400X1,X2 0 X*=(50,100)Z*=13000 目标规划：去年总收益目标规划：去年总收益9000，增长要求，增长要求11.1%，即：今年希望总收益不低于即：今年希望总收益不低于100006引入引入 d+：决策超过目标值部分：决策超过目标值部分(正偏差变量正偏差变量)d-：决策不足目标值部分：决策不足目标值部分(负偏差变量负偏差变量)目标约束：目标约束：100X1+80X2-d+d-=10000 d+。d-=0 d+,d-0 minZ=d-10

4、0X1+80X2-d+d-=100004X1+2X2 4002X1+4X2 500X1,X2,d-,d+0 d+.d-=07例例2 资源拥有量资源拥有量原材料原材料(公斤公斤)2 1 11设备设备(小时小时)1 2 10利润利润(千元千元/件件)8 10 1.原材料价格上涨，超计划要高价购买，所以要严原材料价格上涨，超计划要高价购买，所以要严格控制。格控制。2.市场情况，产品市场情况，产品销售量下降，产品销售量下降，产品的产量不的产量不大于产品大于产品的产量。的产量。3.充分利用设备，不希望加班充分利用设备，不希望加班4.尽可能达到并超过利润计划指标尽可能达到并超过利润计划指标56千元。千元。

5、8建模：建模：(1)、设定约束条件。、设定约束条件。(目标约束、绝对约束目标约束、绝对约束)(2)、规定目标约束优先级、规定目标约束优先级(3)、建立模型、建立模型设设X1，X2为产品为产品，产品，产品产量。产量。2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0 di-.di+=0d1-:X1产量不足产量不足X2 部分部分d1+:X1产量超过产量超过X2 部分部分d2-:设备使用不足设备使用不足10 部分部分d2+:设备使用超过设备使用超过10 部分部分d3-:利润不足利润不足56 部分部分d3+:利

6、润超过利润超过56 部分部分9目标函数目标函数 minZ1=d1+minZ2=d2-+d2+minZ3=d3-或或 minZ=P1d1+P2(d2-+d2+)+P3(d3-)minP1d1+,P2(d2-+d2+),P3(d3-)10例例3、电视机厂装配、电视机厂装配25寸和寸和21寸两种彩电，每台电视寸两种彩电，每台电视机需装备时间机需装备时间1小时，每周装配线计划开动小时，每周装配线计划开动40小时，小时，预计每周预计每周25寸彩电销售寸彩电销售24台，每台可获利台，每台可获利80元，每元，每周周14寸彩电销售寸彩电销售30台，每台可获利台，每台可获利40元。元。该厂目标：该厂目标：1、充

7、分利用装配线，避免开工不足。、充分利用装配线，避免开工不足。2、允许装配线加班，但尽量不超过、允许装配线加班，但尽量不超过10小时。小时。3、尽量满足市场需求。、尽量满足市场需求。11解：设解：设X1,X2 分别表示分别表示25寸，寸，21寸彩电产量寸彩电产量minZ=P1d1-+P2d2+P3(2d3-+d4-)X1+X2+d1-d1+=40X1+X2+d2-d2+=50X1+d3-d3+=24X2+d4-d4+=30X1,X2,di-,di+0(i=1,2,3,4)12目标规划数学模型小结：目标规划数学模型小结：1、约束条件：、约束条件：硬约束硬约束(绝对约束绝对约束)软约束软约束(目标约

8、束目标约束)，引入，引入d-,d+2、目标优先级：、目标优先级：P1 P2 PL 同一级中可以有若干个目标：同一级中可以有若干个目标：P21,P22,P23 其重要程度用权重系数其重要程度用权重系数W21,W22,W23 表示表示133、目标函数：、目标函数：(1)、恰好达到目标：、恰好达到目标：minZ=f(d-+d+)(2)、超过目标：、超过目标：minZ=f(d-)(3)、不超过目标：、不超过目标：minZ=f(d+)14一般模型：一般模型：1111111min,1101,01kkkkkkLLkkLkkkknijjijnjjkkkjjkkZPw dw dPw dw da xb imCk

9、xddqkKxjnddkK 154、目标规划：求一组决策变量的满意值，使、目标规划：求一组决策变量的满意值，使决策结果与给定目标总偏差最小。决策结果与给定目标总偏差最小。Z=0：各级目标均已达到：各级目标均已达到 Z0：部分目标未达到。部分目标未达到。目标函数中只有偏差变量。目标函数中只有偏差变量。目标函数总是求偏差变量最小。目标函数总是求偏差变量最小。返回返回16目标规划的数学模型 决策变量和偏差变量 绝对约束和目标约束某厂生产两种产品、，已知有关数据如下表所示。工厂在考虑到市场等一系列因素后，提出以下目标：产品拥有量原材料2111设备1210单位利润810鉴于产品的销售量持续下降，考虑产品

10、的产量不大于产品；原材料的使用量超过拥有量时，需要高价采购，因此应坚决避免；尽可能充分利用设备台时，但不希望加班；尽可能达到并超过计划利润指标 56元。据此制订生产计划。.3,2,1,0,0,561081021120)(min21332122212111213322211iddddxxddxxddxxxxddxxdPddPdPziiii继续继续目标值目标值实实际际值值idid17目标规划的图解法.3,2,1,0,0,0,561081021120)(min21332122212111213322211iddddxxddxxddxxxxddxxdPddPdPziiii返回返回继续继续2468102

11、46810 x2x1d1-d1+d2-d2+d3+d3-BA18目标规划的图解法(续）.4,3,2,1,0,0,0,30245040)2(min21442331222111214332211iddddxxddxddxddxxddxxddPdPdPziiii返回返回10203040 501020304050 x2x1d1-d1+d2-d2+d3+d3-Ad4-d4+19目标规划的单纯形法.3,2,1,0,0,0,561081020112)(min21332122211121213322211iddddxxddxxddxxddxxxxxdPddPdPziiiis返回返回P1P2P2P3CBXBx1

12、x2xsd1d+dd+dd+bxs2111111d11-11-1P2d121-1105P3d8101-15628/5P11P2-1-22jP3-8-101继续继续20目标规划的单纯形法返回返回P1P2P2P3CBXBx1x2xsd1d+dd+dd+bxs3/21-1/21/264d13/21-11/2-1/2510/3x21/211/2-1/2510P3d3-551-162P11P211jP3-35-51P1P2P2P3CBXBx1x2xsd1d+dd+dd+bxs12-2-1/21/23d11-13-3-1/21/22x214/3-4/3-1/61/64x11-5/35/31/3-1/32P

13、11P211jP31继续继续21目标规划的单纯形法返回返回继续继续.4,3,2,1,0,0,0,30245040)2(min21442331222111214332211iddddxxddxddxddxxddxxddPdPdPziiiiP1P22P3P3CBXBx1x2d1d+dd+dd+d4d4+bP1d1111-140d111-1502P3d11-124P3d411-130P1-1-11P21P3-2-121j22目标规划的单纯形法返回返回继续继续P1P22P3P3CBXBx1x2d1d+dd+dd+d4d4+bP1d111-1-1116d11-1-11262P3x111-124P3d41

14、1-130jP1-111-1P21P3-121P1P22P3P3CBXBx1x2d1d+dd+dd+d4d4+bP1x211-1-1116d-111-1102P3x111-124P3d4-111-11-114jP11P21P31-111123目标规划的单纯形法P1P22P3P3CBXBx1x2d1d+dd+dd+d4d4+bP1x211-1-1126d+-111-1102P3x111-124P3d4-111-11-14jP11P21P31-1111返回返回24目 标 规 划 的 练 习 收点发点甲乙丙供量10412300081034000需求量2000 1500 5000 70008500 某

15、运输问题如下表所示。在尽量满足各点需求的前提下，按重要程度提出下列目标：总运费尽量控制在40000元以下；保证对乙点的供应；甲与丙尽可能按其需求的比例压缩供应；发点尽可能供给甲1000个单位，履行合同；尽量减少对丙的供应量。试制定调运方案。要求：模型部分占总分的60%，求解部分占总分的40%；以寝室为单位完成，并注明每人承担的部分。返回返回25目标规划的单纯形解法 目标规划使用单纯形法求解，di-，di+视为普通变量，P1P2 PL 例题3加工方式 单产耗时工时费用优质率资源量正常生产 2.01000.99 100加班生产 2.01500.98 转承包2.5800.95 临时工3.0800.9

16、0 26例题3建模 要求：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,327例题3 求解.Cj00000P10P200P3CBXBbx1x2x3x4x5d1-d1+d2-d2+d3-d3+j0P1P20X5d1-

17、d2-d3-10010002200021(1)20001030001320001-8204100001000-100001000-100001000-1501000110jP1P2P3-1-10-100-1-30-18000000010000001000000128例4 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：尽量减少加班时间29 例6：多目标运输问题如下表。目标要求：P1：产地不存货，且销

18、量至少满足一半 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/30030 解：设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+X23+X33+X43+d7-d7+=140/2X11+X21+X31+X41+d8-d8+=120X42 +d9-d9+=0 Cij Xij +d10-d10+=0Xij,dL-dL+0 i=1,2,3,4 j=1,2,3 L=1,2,10 minZ=P1(d1-+d1+d7+)+P2(d8-+d8+d9+)+P3 d10+