目标规划培训课件

1、和章学勻要点 了解目标规划与线性规划的异同 理解目标约束中的正负偏差变量 思考目标约束与系统约束的差异 理解目标的优先级和目标权系数 了解目标规划图解法和单纯形法冃标魏划本章内彖重点/目标规划栈憂/目标规划的几何意义/目标规划的单纯形方法问龜的提出线性规划的局限性线性规划只研丸在溝足一定条件下，单一目标函数取得最优解，而在企业管理中，经帝遇到多目标决策问 *甲乙资源限制铜材943600煤炭452000演备台对3103000单件利润70120谡：甲产為X,乙产為兀2maxZ=70 x7 + 120 x29 Xj +4 x2 36004 X +5 x2 20003 x2 +10 x2 0 o根据市

2、场预测:minZ2=xlmaxZ3= x29 Xj +4 x2 36004 Xj +5 x2 20003 Xj +10 x2 0第一节多目标规划问题遣、多目标规划的提出多目标线性规划模型的原始一般形式如下:m ax(m in) G)二 + cnx2 + + cnxnm ax(m in) G 2 二 c2ix + c22x2 + + m ax(m in) G l 二 + c门x, + + clnxdg內+仏心+仏儿（二，纣片為内+為2心+ hnXn o,j- =0当未完成规定的指标则表示：+=0，20 当恰好完成福标时则表示：+=0，-=0目标约束和绝对约束引入了目标值和正、负偏差变量后，就对禁

3、一问題有了WJ1标约束。I标约束即可对虑目标出数起作用也可对虑约束起作用。目标约束是目标规划中特有的P是软约束。绝对约隶（糸统釣束）是指必须产格满足的等或或不等龙 约束。如线,性规划中的所有釣隶条件都旻绝对约束，否 则无可行解。所以，绝对釣束旻硬釣束。例如：在例一中p规定Z1的目标值为50000,正、负偏差 为+、-,则目标函数可以转换为目标约束，既：70旺 +120 +一：= 50000若规走3600的铜材必须用完，虑或9兀+4x2 3600变为9xx + 4x2 +； 一： = 3600第二节目标规划的数学模型I标约束表示J=引入正负偏差变量，对各个目标建立目标约束（软约束）例：甲乙产品的

4、最优生产计划。甲乙现有资源设备A2016设备B0210设备C3432单位利润35根据市场需求/合同规定: -希望尽量扩大甲产品减少乙产品产量。maxZ1=3x1+5x2maxZ2=x1 minZ3=x22“ 162x2 10 3兀 1+4兀2 32兀1,-0又增加二个目标:要求：目标一是利润最大，拟定利润目标是30；目标二是减少乙产品产量但希望不低于4件;目标三是甲产品产量希望不少于6件；对各目标引入正、负偏差变量：3x7+5x2 +d-= 30+d2 - d2+ =4X +df .3+ = 6冃标规刻的热曇桟媲三优先因子(优先等级)与优先权糸數目标等级化:将目标按重要性程度不同很次分成一级目

5、 标、二级目标最次要的目标敌在次要的等级中。(1) 对同一目标而言，若有几个决策方亲都能後其达到, 可认为这些方就这个目标而言都是最优方余；若达 不到，则与目标差距越_,、的越好。(2) 不同级别的目标的重要性是不可比的。即较壽级别 的目标没有达到的损夬，任何较低级别目标上的收获不可拆补。故在判靳最优方余对，管先从轶高级别的I标达到的程度来决策，然后再其次级目标的刘斷。(3) 同一级别的目标可以是多个。各旬之间的重要程盛 可用数量(权数丿来描述。因此，同一级别的目标的 其中一个的可有其余目标的适当收获来強补。三优先因子（优先等级）与优先权糸数优先因子巴是将决策目标挨其重要程度排序并表示出 来。

6、P1P2.?+1.P , k=2K。表示耳比耳+1有更大的优先权。即耆先锋证P级目标的卖 现p这时可不考虑次级目标；而卩2级目标旻衣卖現P级I标的基础上考虑的；依此类推。若要区别具有相同优先因子的两个目标的差别，这对 可分别赋予它们不同的权糸数马，这些都由决策者按具 体惜况而定。曲达成函数(即目标规划中的目标由数)目标规划的目标函数(准则因数)是核各目标约束的正、负 偏差吏量和赋予柏应的优先因子及权糸数而构逢的。古毎 一目标值确走后，决策者的要求是尽可能缩小偏窝目标值。因此目标规划的目标由数只能心inZ=f(d+. J)o般说来，有以下三种情况m但只能出现其中之一:(1) 要求恰好达到规定的目

7、标值，印正、负偏盖变量要尽可能小p 则minZ = f(d+ + -)。(2) 要求不Miln标值，即允许达不到目标值，也就旻正 偏差变量尽可能小，则minZ =/(J+)o(3) 要求起过目标值，即起过量不限，但不低于目标值， 也就是负偏盖支量尽可能小，则minZ=/(J-)o对由绝对约束转化而来的目标由数P也照上述处理即可。例：甲乙产品的最优生产计划。甲乙现有资源设备A2016设备B0210设备C3432单位利润35根据市场需求/合同规定: -希望尽量扩大甲产品减少乙产品产量。maxZ1=3x1+5x2maxZ2=x1 minZ3=x22“ 162x2 10 3兀 1+4兀2 型密对于多个

8、目标，如果有一定的优先顺序P和第一住重要的目标，其优先因子为片,第二住重要的目标， 优先因子为卩2，并规定片卩2优先锋证P1级目标的卖现，此对不考虑次级目标； 级目标卩2在卖现了 P级目标的基础上再予以考虑。 果无法卖现P1目标，则不考虑卩2目标能否取得最优 若有氐个不同优先顺序的目标，则有P1P2.Pjt 将权重与偏差相柬构成目标函救，这样，权重趟大， 趟先迪後柏应的偏差等于零，这样可保证优先级高的 目标管先卖现。例54：若上例中决策者拟订下列经營目标，并确走了目 标之间的优先顺序P1级目标：克分利用讼备有效台对，不加班; 卩2级目标：产晶B的产量不多于4；卩3级目标：卖现利润值130万无

9、分析：题目有三个目标属次，包舍三个目标值。第二目标：P22+ 第二目标：卩3”3第一目标：PjCz+Jf)Mini = （+；）+ P2d + P3d；4x1 + 2x2 +d； 一（I： = 60x2 +； 一 d； = 4 st8jq +6x2 +； - d； =1302x1 + 4x2 48例55：禁厂计划下一个生产周期内生产甲、乙两种产品, 巳知资料如表所示。制定生产计划，满足下列目标:Pi级目标：完成或越额完成利润指标50000无;卩2级目标：产為甲不Mil200件，产品乙不低于250件;卩3级目标：现有钢材3600吨必须用完甲乙资源限制触材943600煤炭452000役备台对310

10、3000单件利润70120分析：题目有三个目标属次P包含四个I标值。第一目标：Plf第二目标：有两个要求即甲2十，乙3一，但两个具 有柏同的优先因子，需要确定权糸数。本題可用单件利 润比作为权糸數即70:120,化简为7:12, P2(7J2 + +12J3-)第三目标：p3(J4+i/4)MinZ=Id；+P2(7d +12d；) + P3(d； +；)70旺 +120*2 +i 一 d； = 50000xi +； d； = 200x2 一 d； =250邛 9旺 +4x2一 d： =36004xj + 5x2 S 20003xx +10x2 f.T十 da - rf J =4$（充分利用血

11、的工时指标）玉+ l d4. ! W-5r充分利用B的工时指标）XI5X2?df-$df+(l(f=T53/)I?的产量比例2： 了4伯目标函数：Kfin总=卩0严卩川广+4PMJ杉F.d/1A Ai777 巳约束方程：2兀+T/花+右二df- Zj.O:Xj十心二心6C爲+ 5 jm 0 （匸和&免4）舲*（*僚搭诱）韧呼半傍半僚輩雾p 6 nx sxQOjt* 6 “X 6 ?X晏華oeo晏歪藝暂q?%XVIU UllUID陳常辱Bn低僻科第第三节目标规划的图解法Mi前 S = d.t為+2 込 + df-dT = TO 爲+2込(1兀十禺 4XjfjXa 禺 7 心2 0OR:SM024

12、Ixl10024610SM0246JIIxl8 10OR:SM14x2当 Mhi S = df 到时 dj = 0；：1+z7：2=rn0246810)R:SMx2OR:SMx210A54322468当Mfn. S =右十达到 时1432A5有无穷多解点3） 和点（2, 2）连线上的 点都是疑优解。024/6810OR:SM例Tin E=F旳了+聞才 +5 F皿 + P2.rfT sdf-出/=4仆 ；rTH-X2H- rf2!+j =三门叉尹V =釦二比 iorr=i52r3r4j4050OR:SMOR:SMOR:SM010 2030xl4050OR:SM01020304050x2弓i V誓

13、g七可行域如图xl010 20304050OR:SM7LI计xl4050Wn dT；h = 0 P=(2(r,C)唯一 最就解Om in G 二 P+ P?(2d+ d)3x + 5, +- d二 30(1)+ d、- - d二 4(2)H + d- d二 6(3)2 x | 16(4)2.j 10(5)3Xj + 4x? 0满意解：x；=5,224bA1UOR:SM第三节目标规划的图解法目标规划的图解法首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线,最后。按优先级别和权重依次分析各级目标。#OR:SM第三节目标规划的图解法minZ =片(：+d) + P2d10

14、xx +12x2 +d -d： = 62.5 兀i+ 2x2 +d=10 2xj + x20,JzX0(Z=1.2)CoBAd；B (0.6250,4.6875) C (0,5.2083), 是该问题的解(无穷多最优解)。1234562(2)B、C线段上的所有点均I标规刻的團解旗min Z = P&； + 戸2(25； + ；)+ P/； 30xj + 12x2=25002x + x2 +； = 140 x=60x2 +；： = 100X1_20 (Z = 1.2.3.4)结论：C(60,5&3)为所求的满意解。I标规刻的画解旗图解出解題步骤如下：1. 确定各约束条件的可行城，即将所有釣束条件

15、（包括 目标约束和绝对约束，暂不考虑正负偏差变量）衣坐 标年面上表示出来；2. 在目标约束所代表的边界线，上，用爸头标出正、负偏 差麦量值增大的方向；3. 求满足最高优先等级目标的解；4. 转到下一个优先等级的目标，应不破坏所有较壽优先 等级目标的前提下，求出该优先等级目标的解；5. 重复4,直到所有优先等级目标都已申妥完毕为止；6. 确定最优解和满意解。皇 第四节冃标规刻綸草龜形试目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型：将优先等级耳视为正常数（大M法）正负偏差变量如+、必-视为松弛变量以负偏差变量必-为初始基变量，建立初始单纯形表检验数的计算与厶P单纯形法相

16、同,即Cj - CBiPj最优性判别准则类似于厶P的单纯形算法：检验数一般是各优先等级因子的代数和判断检验数的正负和大小79OR:SMI标规刻的車絶形旗I标规划的数学棋燮结构与线性规划的数学模型结构形或上没有本质的区别P所以可用单纯形出求解。但要考虑目 标规划的数学栈型一些特点，作以下规定：(1)因目标规划问题的目标函数都旻求最小化，所以以C厂z0, /=1，2,为最优准则。(2)因非基变量的检验数中含有不同等级的优先因子，聊因PiP2Pk；从每个检玲数的整体来看：检脸数 的正、负督先决走于P的糸数旳丿的正、负。若=0,这对此 检殓数的正、负就决定于卩2的糸数切的正、负。【例4.6】用单纯形法

17、求解下述冃标规划问题min 片+d)+ Pd州 + lx, +d=502*1 4启 + 乩= 402X| + 2x2 +d一打=80xx2,d. J 2 0 (i = 1,23)【解】以d厂、d?二心-为基变量，求出检验数，将检验数中优先因子分离出来，每一优先级做一行，列出初始单纯形表454-51 q0000Pl0bI 5基xlX2吋pld2片11150I 0211-140221-180c严jP-J-211-2-21OR:SM表4T中，件行屮（一2）最小，则勺进基，求最小比值易知右一出 基，将第二列主元素化为其余元素化为零得到表表4一60片00P2b5基X2厂心+01/211/2-1/22S0

18、3/21/21-115p2鸟一111-130片11-1-11UK：BM表中匕行全部检验数非负，表明第一目标已经得到优化.化行存在负数，可的检验 数为一尸选t|进某（也可以选珀+进慕八 则右-出幽 迭祀得到表47表470000P】P20b基心禺0屯12/3-2/31/320011/312/32/3.2/3-1-120鬥112/3-2/32/3-2/31在表本7中，片行的系数全部非饥几行存在负数.时的检验数一2/3P), 选听锻基，则T|出基，迭代得到表4d应出注盍.表47中不能选df进基.检验数鬥一2/3厲应理解为“大于零卯 和 片是优先级别的比辄 而不是“数袖的比较-例如 耳一3几+E巴理解为

19、 小于不十2P.-4P.理舸为大于枣等等.表48A00000bq基可X2d 一%k021114003-112-230p.-2-221-10CZJP11p22221表4书中P?行的(一2)小于零，但(-2)列上面P行存在正数1, 检验数鬥一2心口所有检验数非備 得到满意解X= (0? 40)【例4.7】(1)用单纯形法求解例4.5(2)当目标函数变为min Z = P站 + rf；） + PAd； + 2d；） + PJ；求满意解(D初始单纯形表见表#9,最终单纯形表见表412.意解X=(1(H)/3, 8/3几对应于图46点B.不难看岀有多重解,将心-进基吐出基得到另一满意解X=(60r 0)

20、； 见表43表490(1片0a片0h基升x2dr厂疔疔Pldr1015i-i400*0781-15&02211120Q1231-1100crzj片-1ft-5ii-2-221表4100000py0%bQ基xiXJ *jk心一r牯011/21/10-vio4009/2-7/107/101-1280片1-1/51/5i-i402|-1/101/101一160-*片11-1 tUS-1/521表4_巧Qtt00片p2p20b忙咐J心*吋町uxi15/40-5/4011/41Z4250-1W44I19/401-1-9/4W4145厲-3/2013/20111一 1/211210-(j1-1Z201/2

21、01/2-U230片13Z2O-3/20!21/2-1/21表41200001P20bG基旳时V01SM-5/6-2/32/31W30叭-1-1-1W619/62/32/33W30-12W3咖-IU/31(1/32W3-*xl1-U31/3加-2/380/37-1111q I(i(1片0(1P2(1bQ基旺tfj+dr虻0111/2-1/260ad厂11-1-7/27/214(10rfi45-115-52IMJ03/2-1/21/21-3/440g111片11（2）如果将目标函数mm Z二和畀）4 P2（d； + 2d；） 4曲：改写成min Z = P,+ P/； + 巴d；以表12为基础，

22、计算过程见表4-14-4-16表41490U0a1)bI 5 斗耳d対矿叫15/6_5/6-2/32/31(10/3d21-119/61W6-2/32/3340/3-112/320/3-10/310/3200/3u1-131/32/3-2J380/32-20/320/310/3-10/3广一7P21W6-7/62/3-2Ji11必11表 4-1500片000b基旺xtrfr时妒“4妤0X11-1/8一 1/41/425巧d2-19/4Q19/4014-9/49/41450-3/203/20zrfZ00TV0OR:SM最终表:0000迅0b心x2厂*d2令疔切-18/45-45-1/91/984W2M5-2/452/92/911200/*9/9(119/94/94/911580/91-7/457/452/92/9560/9114/454/455/94/92P,1!/90_W5H-4/94/91满意解龙=(別)/乳 560/9八 d= 2H)/9而厶一=0, 0J 5000PlPl3巴05巴00值CbXbbxi*2右右吋右令如Pid2054110000004di24