线性规划数学模型课件

目标规划本章内容重点目标规划模型目标规划的几何意义目标规划的单纯形方法目标规划本章内容重点问题的提出线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度(即优先顺序)也不相同，有些目标之间往往相互发生矛盾。线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。问题的提出线性规划只研究在满足一定条件下，单一目标函数取得线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。问题的提出线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符目标规划与线性规划的比较线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。线性规划求最优解；目标规划是找到一个满意解。线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要(或更能满足需要)。目标规划与线性规划的比较线性规划只讨论一个线性目标函数在一组目标规划与线性规划的比较例5-1：某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源消耗目标规划与线性规划的比较例5-1：某厂计划在下一个生产周期内目标规划数学模型设：甲产品x1

，乙产品x2根据市场预测：maxZ=70x1

+120x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0maxZ1=70x1

+120x2

minZ2=x1

maxZ3=x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0目标规划数学模型设：甲产品x1，乙产品x2根据市场预测目标规划的数学模型1.目标值和偏差变量目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。偏差变量(事先无法确定的未知数)：是指实现值和目标值之间的差异,记为d。正偏差变量:表示实现值超过目标值的部分，记为d＋。负偏差变量:表示实现值未达到目标值的部分，记为d－。目标规划的数学模型1.目标值和偏差变量目标规划的数学模型在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0,d－≥0当完成或超额完成规定的指标则表示：d＋≥0,d－＝0当未完成规定的指标则表示：d＋＝0,d－≥0当恰好完成指标时则表示：d＋＝0,d－＝0目标规划的数学模型在一次决策中，实现值不可能既超过目标值又未目标规划的数学模型2.目标约束和绝对约束引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。绝对约束(系统约束)是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。目标规划的数学模型2.目标约束和绝对约束目标规划的数学模型例如：在例一中，规定Z1的目标值为50000,正、负偏差为d＋、d－,则目标函数可以转换为目标约束，既:50000120701121=-+++-ddxx若规定3600的钢材必须用完，原式9x1+4x2≤3600变为3600494421=-+++-ddxx目标规划的数学模型例如：在例一中，规定Z1的目标值为500目标规划的数学模型3.优先因子(优先等级)与优先权系数目标等级化:将目标按重要性程度不同依次分成一级目标、二级目标…..。最次要的目标放在次要的等级中。(1)对同一目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。(2)不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别目标上的收获不可弥补。故在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。(3)同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。目标规划的数学模型3.优先因子(优先等级)与优先权系数目标规划的数学模型3.优先因子(优先等级)与优先权系数优先因子Pk是将决策目标按其重要程度排序并表示出来。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1,2…,K。表示Pk比Pk+1有更大的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数ωj,这些都由决策者按具体情况而定。目标规划的数学模型3.优先因子(优先等级)与优先权系数目标规划的数学模型4.达成函数(即目标规划中的目标函数)目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是minZ=f(d＋、d－)。一般说来，有以下三种情况，但只能出现其中之一：(1)要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f(d＋＋d－)。(2)要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ=f(d＋)。(3)要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ=f(d－)。对由绝对约束转化而来的目标函数，也照上述处理即可。目标规划的数学模型4.达成函数(即目标规划中的目标函数)目标规划的数学模型5.多目标规划的解(1)若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；(2)若解只能满足部分目标，就称该解为多目标规划的次优解；(3)若找不到满足任何一个目标的解，就称该问题为无解。(4)前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现，就称该解为多目标规划的满意解(具有层次意义的解)目标规划的数学模型5.多目标规划的解单目标规划例5-2:某工厂生产A，B两种产品，有关数据如下。实现目标利润为140万元的最优生产方案AB可用量设备(台时)4260原材料(KG)2448利润(万元)86从决策者的角度看，他希望超过利润目标值，若达不到，也希望尽可能接近，即负偏差最小³³-+0,,0,21ddxx£+484221xx£+602421xx=+-+-+1406821ddxxïïîïïíìst=-mindZ单目标规划例5-2:某工厂生产A，B两种产品，有关数据如下。级别相等的多目标规划例5-3：若上例中假设决策者根据市场预测，产品A的销售量有下降的趋势，故考虑实现下列两个目标：(1)实现利润目标122万元(2)产品A的产量不多于10分析:两个目标级别相等，即两个目标的重要程度一样，不存在谁优先的问题设d＋，d-分别为超过目标值的部分，以及未完成目标值的部分，于是两个目标可以等价表示为：10122681211121=-+=-+++-+-ddxddxx级别相等的多目标规划例5-3：若上例中假设决策者根据市场预测级别相等的多目标规划x1=10，x2=7，d－1＝0，d+2＝0，利润为122，两个目标均已经实现ïïîïïíì³£+£+=-+=-+++=+-+-+-+-+-0,,,,,4842602410122682211212121221112121ddddxxxxxxddxddxxstddMinZ级别相等的多目标规划x1=10，x2=7，d－1＝0，d+2具有优先级别的多目标规划对于多个目标，如果有一定的优先顺序，即第一位重要的目标，其优先因子为P1，第二位重要的目标，其优先因子为P2，并规定P1>>P2优先保证P1级目标的实现，此时不考虑次级目标；次级目标P2在实现了P1级目标的基础上再予以考虑。如果无法实现P1目标，则不考虑P2目标能否取得最优若有k个不同优先顺序的目标，则有P1>>P2>>…>>Pk将权重与偏差相乘构成目标函数，这样，权重越大，越先迫使相应的偏差等于零，这样可保证优先级高的目标首先实现。具有优先级别的多目标规划对于多个目标，如果有一定的优先顺序，具有优先级别的多目标规划例5-4：若上例中决策者拟订下列经营目标，并确定了目标之间的优先顺序P1级目标：充分利用设备有效台时，不加班；P2级目标：产品B的产量不多于4；P3级目标：实现利润值130万元分析：题目有三个目标层次，包含三个目标值。第一目标：P1(d1＋+d1-)第二目标：P2d2＋第二目标：P3d3-ïïîïïíì³£+=-++=-+=-+++++=+-+-+-+--++-0,,,48421306846024)(2121332122211213322111iiddxxxxddxxddxddxxstdPdPddPMinZ具有优先级别的多目标规划例5-4：若上例中决策者拟订下列经营具有优先级别的多目标规划例5-5：某厂计划下一个生产周期内生产甲、乙两种产品，已知资料如表所示。制定生产计划，满足下列目标：P1级目标：完成或超额完成利润指标50000元；P2级目标：产品甲不超过200件，产品乙不低于250件；P3级目标：现有钢材3600吨必须用完12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源消耗具有优先级别的多目标规划例5-5：某厂计划下一个生产周期内生具有优先级别的多目标规划分析：题目有三个目标层次，包含四个目标值。第一目标：P1d1＋第二目标：有两个要求即甲d2＋，乙d3-，但两个具有相同的优先因子，需要确定权系数。本题可用单件利润比作为权系数即70:120，化简为7:12，P2(7d2＋+12d2-)第二目标：P3(d4＋+d4-)ïïïïîïïïïíì³£+£+=-++=-+=-+=-++++++=+-+-+-+-+-+--+-0,,,30001032000543600492502005000012070)()127(2121214421332221112144332211iiddxxxxxxddxxddxddxddxxstddPddPdPMinZ具有优先级别的多目标规划分析：题目有三个目标层次，包含四个目数学模型的一般形式ïïïïîïïïïíì-=³-=³-=³=£-==-+-+=+-=+-=++-=-=åååå)55(3,2,1,0,)45(,,1,0)35(,,1,),()25(,,1,)15()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLllLLL满足约束条件：目标函数：ww其中Pl为优先因子，w-lk，w+lk为优先系数数学模型的一般形式ïïïïîïïïïíì-=³-=³-=³=建模的步骤根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。给各目标赋予相应的优先因子

Pk对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数

ωkl+和ωkl-。根据决策者的要求，构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。建模的步骤根据要研究的问题所提出的各目标与条件，确定目标值，线性规划与目标规划线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xs,xa

xi,xs,xa

,

d约束条件系统约束(绝对约束)目标约束系统约束解最优满意线性规划与目标规划线性规划LP目标规划GP目标函数min,目标规划的图解法图解法解题步骤如下：1.确定各约束条件的可行域，即将所有约束条件(包括目标约束和绝对约束，暂不考虑正负偏差变量)在坐标平面上表示出来；2.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；3.求满足最高优先等级目标的解；4.转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；5.重复4，直到所有优先等级目标都已审查完毕为止；6.确定最优解和满意解。目标规划的图解法图解法解题步骤如下：目标规划的图解法ïïîïïíì=³³£+=-++=-++++=-+-+-+---+)2.1(0,08

2

102

5.621210)(min21212221112122111lddxxxddxxddxxdPddPZll012345678123456⑴⑵⑶Ax2

x1BCB(0.6250,4.6875)C(0,5.2083)，B、C线段上的所有点均是该问题的解(无穷多最优解)。目标规划的图解法ïïîïïíì=³³£+=-++=-++++ïïïîïïïíì=³³=-+=-+=-++=-+++++=-+-+-+-+-+-+++-)4.3.2.1(0,,010060140225001230)5.2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll

0x2

0(1)x11401201008060402020406080100(2)(3)(4)ABCD结论：C(60,58.3)为所求的满意解。目标规划的图解法ïïïîïïïíì=³³=-+=-+=-++=-+++++=目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定：(1)因目标规划问题的目标函数都是求最小化，所以以cj-zj≥0，j=1,2,…，n为最优准则。(2)因非基变量的检验数中含有不同等级的优先因子，即KknjPazckkjjj,,2,1;,,2,1LL===-å因P1>>P2>>…>>PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数α1j的正、负。若α1j=0，这时此检验数的正、负就决定于P2的系数α2j的正、负。目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型目标规划的单纯形法(1)建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1。(2)检查该行中是否存在负数，且对应的前k-1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转(3)。若无负数，则转(5)。(3)按最小比值规则确定换出变量，当存在两个或以上相同的最小比值时，选取具有较高优先级别变量为换出变量。(4)按单纯形法进行基变换运算，建立新的计算表，返回(2)。(5)当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回到(2)。目标规划的单纯形法(1)建立初始单纯形表，在表中将检验数行按目标规划的单纯形法例5-8：用单纯形法求解下列目标规划问题

MinZ=P1

d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2

+d1--d1+=204x1+3x2

+d2--d2+=24x1

+d3--d3+=3-x1

+x2

+d4--d4+=2x1

,x2

,dk-,dk+≥0目标规划的单纯形法例5-8：用单纯形法求解下列目标规划问题目标规划的单纯形法cj值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数λjP1P2P300P10P2P23P305P3020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4--5-401000-4-322-535463-检验数λjP1P2P3d1-d2-x1d4-P1P205P331000001-1005041-100-55001203001-1-440050100001-11-10-40105-50-324-4-5-25513--P1P23P35P3目标规划的单纯形法cjCBXBbx1x2d1-d1+d2-目标规划的单纯形法cj00P10P2P23P305P30值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数λjP1P2P3d3+d2-x1d4-0P205P3104/51/5-1/500-110080-1/5-4/54/51-10000414/51/5-1/5000000609/51/5-1/500001-1010001/54/5-4/52-9-1135-10--检验数λjP1P2P3d3+d1+x1d4-0005P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-10100011-35/4-5/45/4354-832/7目标规划的单纯形法cj00P10P2P23P305P30目标规划的单纯形法cj00P10P2P23P305P30值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数λjP1P2P3x2d1+x1d4-0005P3401001/3-1/3-4/34/3001100-114/3-4/3-1/31/3003100000-110010000-1/31/37/3-7/31-100100115/3-5/3-26/335/35---3检验数λjP1P2P3x2d1+x1d3-0003P33/70000-1/71/71-13/7-3/732/701001/7-1/7004/7-4/778/700-119/7-9/7001/7-1/718/710001/7-1/700-3/73/7001000113/7-3/7326/79/7目标规划的单纯形法cj00P10P2P23P305P30目标规划的单纯形法例5-9：用单纯形法求解下列目标规划问题

minZ=P1d1++P2(d2-+d2+)+P3d3-2x1+x2

+x3=11x1-x2+d1-

-d1+=0x1+2x2

+d2-

-d2+=108x1

+10x2+d3-

-d3+=56xi,dk-,dk+

≥0目标规划的单纯形法例5-9：用单纯形法求解下列目标规划问题目标规划的应用例5-10：已知一个生产计划的线性规划模型，经营目标：P1：总利润不低于40P2：充分利用设备能力，且尽量不超过140如何安排生产？产品资源甲乙现有资源设备2010140售价108成本56最大需求量610minZ=P1d1-+P2(d2-+d2+)x1≤6x2≤105x1+2x2+d1--d1+=4020x1+10x2+d2--d2+=140x1,x2,d1-,d1+,d2-,d2+≥0x1x2x1=6x2=10③④d1+d1-d2+d2-CBD(6,5)目标规划的应用例5-10：已知一个生产计划的线性规划模型，经满意解:x1=6，x2=5设备能力:需求206+105=170，实际140实现目标P1和P2，降低甲乙产品的设备消耗:降低率(170-140)/170=18%，甲产品的设备消耗降为20(1-18%)=16.4，乙产品的设备消耗降为10(1-18%)=8.2。总利润：40单位甲：5单位乙：2生产部目标甲产品的产量：6，成本：5乙产品的产量：5，成本：6技术部目标甲产品的设备单耗：16.4乙产品的设备单耗：8.2销售部目标甲产品的销量：6，单价：10乙产品的销量：5，单价：8目标规划的应用满意解:x1=6，x2=5总利润：40生产部目标技术部降低设备消耗很困难，则调整经营目标的次序P1：充分利用设备能力，且尽量不超过140，P2：总利润不低于40如何安排生产？产品资源甲乙现有资源设备2010140售价108成本56最大需求量610minZ=P2d1-+P1(d2-+d2+)x1≤6①x2≤10②5x1+2x2+d1--d1+=40③20x1+10x2+d2--d2+=140④x1,x2,d1-,d1+,d2-,d2+≥0x1x2x1=6x2=10④A(6,2)③d1+d1-d2+d2-E目标规划的应用降低设备消耗很困难，则调整经营目标的次序产品甲乙现有资源设备满意解：x1=6,x2=2利润指标：实际5×6+2×2=34，期望40实现目标P1和P2，增加甲乙产品的单位利润:增长率(40-34)/34=18%产品售价由市场决定，为提高利润，应从降低成本入手：甲产品的成本由5降为10-5(1+18%)=4.12,乙产品的成本由6降为8-2(1+18%)=5.63。总利润：40单位甲：5.88单位乙：2.36生产部目标甲产品的产量：6，成本：4.12乙产品的产量：2，成本：5.63技术部目标甲产品的设备单耗：20乙产品的设备单耗：10销售部目标甲产品的销量：6，单价：10乙产品的销量：2，单价：8目标规划的应用满意解：x1=6,x2=2总利润：40生产部目标技术某副食品批发店预测某商品今后4月的购进与售出价格如表。假设:(1)该商品供不应求，最大销量受仓库容量限制；(2)正常库容3吨，机动库容2吨；(3)月初批发销货，月中采购进货，进货所需资金完全来销售收入；(4)1月初库存量2吨，成本2.5千元/吨，该月初无现金。经营目标：(1)每月都使用正常库容，尽量不超容；(2)每月下旬都应储备1千元以备急用；(3)4个月总盈利最大。月份1234成本(购价+库存)2.62.52.72.8售价2.92.73.13.3目标规划的应用某副食品批发店预测某商品今后4月的购进与售出价格如表。月份1决策变量：xj

第j月的采购量，yj

第j月的销售量绝对约束条件各月销量约束:月初售货，各月销量不多于其期初库存量。1月y1

≤22月y2

≤2–y1

+x1

→

y1

+y2

–x1

≤23月y3

≤2–y1

+x1

–y2

+x2

→y1+y2+y3

–x1

–x2

≤24月y4≤2–y1

+x1

–y2+x2–y3+x3→y1+y2+y3+y4

–x1

–x2–x3≤2各月采购量约束:每月采购量依赖月初的售货收入。1月2.6x1

≤2.9y1→–

2.9y1+

2.6x1

≤02月–

2.9y1–2.7y2

+

2.6x1+2.5x2

≤0

3月–

2.9y1–2.7y2–3.1y3

+

2.6x1+2.5x2+2.7x3

≤04月–

2.9y1–2.7y2–3.1y3–3.3y4+

2.6x1+2.5x2+2.7x3+2.8x4≤0目标规划的应用决策变量：xj第j月的采购量，yj第j月的销售量目目标约束条件正常库容约束1月2–y1+

x1

≤3→–y1+

x1

+d1-

–d1+=12月–y1–y2+

x1+

x2+d2-

–d2+=1

3月–y1–y2–y3+

x1+

x2+

x3+d3-

–d3+=14月–y1–y2–y3–y4+

x1+

x2+

x3+

x4+d4-

–d4+=1各月储备金约束1月

2.9y1-2.6x1

+d5-

–d5+=12月2.9y1+2.7y2

-

2.6x1-2.5x2+d6-

–d6+=1

3月2.9y1+2.7y2+3.1y3

-

2.6x1-2.5x2-2.7x3+d7-

–d7+=14月

2.9y1+2.7y2+3.1y3+3.3y4-

2.6x1-2.5x2-2.7x3-2.8x4+d8-

–d8+=1总盈利约束：期望利润(3.3-2.5)×(3+2)×4=16

销售收入:2.9y1+2.7y2+3.1y3+3.3y4

销售成本:

2.5×2+2.6x1+2.5x2+2.7x3

2.9y1+2.7y2+3.1y3+3.3y4-2.6x1-2.5x2-2.7x3+d9-

–d9+=21目标达成函数

minZ=P1(d1+

+d2+

+d3+

+d4+

)+P2(d5-

+d6-

+d7-

+d8-

)+P3

d9-

目标规划的应用目标约束条件目标规划的应用目标规划本章内容重点目标规划模型目标规划的几何意义目标规划的单纯形方法目标规划本章内容重点问题的提出线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度(即优先顺序)也不相同，有些目标之间往往相互发生矛盾。线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。问题的提出线性规划只研究在满足一定条件下，单一目标函数取得线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。问题的提出线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符目标规划与线性规划的比较线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。线性规划求最优解；目标规划是找到一个满意解。线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要(或更能满足需要)。目标规划与线性规划的比较线性规划只讨论一个线性目标函数在一组目标规划与线性规划的比较例5-1：某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源消耗目标规划与线性规划的比较例5-1：某厂计划在下一个生产周期内目标规划数学模型设：甲产品x1

，乙产品x2根据市场预测：maxZ=70x1

+120x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0maxZ1=70x1

+120x2

minZ2=x1

maxZ3=x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0目标规划数学模型设：甲产品x1，乙产品x2根据市场预测目标规划的数学模型1.目标值和偏差变量目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。偏差变量(事先无法确定的未知数)：是指实现值和目标值之间的差异,记为d。正偏差变量:表示实现值超过目标值的部分，记为d＋。负偏差变量:表示实现值未达到目标值的部分，记为d－。目标规划的数学模型1.目标值和偏差变量目标规划的数学模型在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0,d－≥0当完成或超额完成规定的指标则表示：d＋≥0,d－＝0当未完成规定的指标则表示：d＋＝0,d－≥0当恰好完成指标时则表示：d＋＝0,d－＝0目标规划的数学模型在一次决策中，实现值不可能既超过目标值又未目标规划的数学模型2.目标约束和绝对约束引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。绝对约束(系统约束)是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。目标规划的数学模型2.目标约束和绝对约束目标规划的数学模型例如：在例一中，规定Z1的目标值为50000,正、负偏差为d＋、d－,则目标函数可以转换为目标约束，既:50000120701121=-+++-ddxx若规定3600的钢材必须用完，原式9x1+4x2≤3600变为3600494421=-+++-ddxx目标规划的数学模型例如：在例一中，规定Z1的目标值为500目标规划的数学模型3.优先因子(优先等级)与优先权系数目标等级化:将目标按重要性程度不同依次分成一级目标、二级目标…..。最次要的目标放在次要的等级中。(1)对同一目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。(2)不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别目标上的收获不可弥补。故在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。(3)同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。目标规划的数学模型3.优先因子(优先等级)与优先权系数目标规划的数学模型3.优先因子(优先等级)与优先权系数优先因子Pk是将决策目标按其重要程度排序并表示出来。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1,2…,K。表示Pk比Pk+1有更大的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数ωj,这些都由决策者按具体情况而定。目标规划的数学模型3.优先因子(优先等级)与优先权系数目标规划的数学模型4.达成函数(即目标规划中的目标函数)目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是minZ=f(d＋、d－)。一般说来，有以下三种情况，但只能出现其中之一：(1)要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f(d＋＋d－)。(2)要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ=f(d＋)。(3)要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ=f(d－)。对由绝对约束转化而来的目标函数，也照上述处理即可。目标规划的数学模型4.达成函数(即目标规划中的目标函数)目标规划的数学模型5.多目标规划的解(1)若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；(2)若解只能满足部分目标，就称该解为多目标规划的次优解；(3)若找不到满足任何一个目标的解，就称该问题为无解。(4)前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现，就称该解为多目标规划的满意解(具有层次意义的解)目标规划的数学模型5.多目标规划的解单目标规划例5-2:某工厂生产A，B两种产品，有关数据如下。实现目标利润为140万元的最优生产方案AB可用量设备(台时)4260原材料(KG)2448利润(万元)86从决策者的角度看，他希望超过利润目标值，若达不到，也希望尽可能接近，即负偏差最小³³-+0,,0,21ddxx£+484221xx£+602421xx=+-+-+1406821ddxxïïîïïíìst=-mindZ单目标规划例5-2:某工厂生产A，B两种产品，有关数据如下。级别相等的多目标规划例5-3：若上例中假设决策者根据市场预测，产品A的销售量有下降的趋势，故考虑实现下列两个目标：(1)实现利润目标122万元(2)产品A的产量不多于10分析:两个目标级别相等，即两个目标的重要程度一样，不存在谁优先的问题设d＋，d-分别为超过目标值的部分，以及未完成目标值的部分，于是两个目标可以等价表示为：10122681211121=-+=-+++-+-ddxddxx级别相等的多目标规划例5-3：若上例中假设决策者根据市场预测级别相等的多目标规划x1=10，x2=7，d－1＝0，d+2＝0，利润为122，两个目标均已经实现ïïîïïíì³£+£+=-+=-+++=+-+-+-+-+-0,,,,,4842602410122682211212121221112121ddddxxxxxxddxddxxstddMinZ级别相等的多目标规划x1=10，x2=7，d－1＝0，d+2具有优先级别的多目标规划对于多个目标，如果有一定的优先顺序，即第一位重要的目标，其优先因子为P1，第二位重要的目标，其优先因子为P2，并规定P1>>P2优先保证P1级目标的实现，此时不考虑次级目标；次级目标P2在实现了P1级目标的基础上再予以考虑。如果无法实现P1目标，则不考虑P2目标能否取得最优若有k个不同优先顺序的目标，则有P1>>P2>>…>>Pk将权重与偏差相乘构成目标函数，这样，权重越大，越先迫使相应的偏差等于零，这样可保证优先级高的目标首先实现。具有优先级别的多目标规划对于多个目标，如果有一定的优先顺序，具有优先级别的多目标规划例5-4：若上例中决策者拟订下列经营目标，并确定了目标之间的优先顺序P1级目标：充分利用设备有效台时，不加班；P2级目标：产品B的产量不多于4；P3级目标：实现利润值130万元分析：题目有三个目标层次，包含三个目标值。第一目标：P1(d1＋+d1-)第二目标：P2d2＋第二目标：P3d3-ïïîïïíì³£+=-++=-+=-+++++=+-+-+-+--++-0,,,48421306846024)(2121332122211213322111iiddxxxxddxxddxddxxstdPdPddPMinZ具有优先级别的多目标规划例5-4：若上例中决策者拟订下列经营具有优先级别的多目标规划例5-5：某厂计划下一个生产周期内生产甲、乙两种产品，已知资料如表所示。制定生产计划，满足下列目标：P1级目标：完成或超额完成利润指标50000元；P2级目标：产品甲不超过200件，产品乙不低于250件；P3级目标：现有钢材3600吨必须用完12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源消耗具有优先级别的多目标规划例5-5：某厂计划下一个生产周期内生具有优先级别的多目标规划分析：题目有三个目标层次，包含四个目标值。第一目标：P1d1＋第二目标：有两个要求即甲d2＋，乙d3-，但两个具有相同的优先因子，需要确定权系数。本题可用单件利润比作为权系数即70:120，化简为7:12，P2(7d2＋+12d2-)第二目标：P3(d4＋+d4-)ïïïïîïïïïíì³£+£+=-++=-+=-+=-++++++=+-+-+-+-+-+--+-0,,,30001032000543600492502005000012070)()127(2121214421332221112144332211iiddxxxxxxddxxddxddxddxxstddPddPdPMinZ具有优先级别的多目标规划分析：题目有三个目标层次，包含四个目数学模型的一般形式ïïïïîïïïïíì-=³-=³-=³=£-==-+-+=+-=+-=++-=-=åååå)55(3,2,1,0,)45(,,1,0)35(,,1,),()25(,,1,)15()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLllLLL满足约束条件：目标函数：ww其中Pl为优先因子，w-lk，w+lk为优先系数数学模型的一般形式ïïïïîïïïïíì-=³-=³-=³=建模的步骤根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。给各目标赋予相应的优先因子

Pk对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数

ωkl+和ωkl-。根据决策者的要求，构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。建模的步骤根据要研究的问题所提出的各目标与条件，确定目标值，线性规划与目标规划线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xs,xa

xi,xs,xa

,

d约束条件系统约束(绝对约束)目标约束系统约束解最优满意线性规划与目标规划线性规划LP目标规划GP目标函数min,目标规划的图解法图解法解题步骤如下：1.确定各约束条件的可行域，即将所有约束条件(包括目标约束和绝对约束，暂不考虑正负偏差变量)在坐标平面上表示出来；2.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；3.求满足最高优先等级目标的解；4.转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；5.重复4，直到所有优先等级目标都已审查完毕为止；6.确定最优解和满意解。目标规划的图解法图解法解题步骤如下：目标规划的图解法ïïîïïíì=³³£+=-++=-++++=-+-+-+---+)2.1(0,08

2

102

5.621210)(min21212221112122111lddxxxddxxddxxdPddPZll012345678123456⑴⑵⑶Ax2

x1BCB(0.6250,4.6875)C(0,5.2083)，B、C线段上的所有点均是该问题的解(无穷多最优解)。目标规划的图解法ïïîïïíì=³³£+=-++=-++++ïïïîïïïíì=³³=-+=-+=-++=-+++++=-+-+-+-+-+-+++-)4.3.2.1(0,,010060140225001230)5.2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll

0x2

0(1)x11401201008060402020406080100(2)(3)(4)ABCD结论：C(60,58.3)为所求的满意解。目标规划的图解法ïïïîïïïíì=³³=-+=-+=-++=-+++++=目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定：(1)因目标规划问题的目标函数都是求最小化，所以以cj-zj≥0，j=1,2,…，n为最优准则。(2)因非基变量的检验数中含有不同等级的优先因子，即KknjPazckkjjj,,2,1;,,2,1LL===-å因P1>>P2>>…>>PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数α1j的正、负。若α1j=0，这时此检验数的正、负就决定于P2的系数α2j的正、负。目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型目标规划的单纯形法(1)建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1。(2)检查该行中是否存在负数，且对应的前k-1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转(3)。若无负数，则转(5)。(3)按最小比值规则确定换出变量，当存在两个或以上相同的最小比值时，选取具有较高优先级别变量为换出变量。(4)按单纯形法进行基变换运算，建立新的计算表，返回(2)。(5)当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回到(2)。目标规划的单纯形法(1)建立初始单纯形表，在表中将检验数行按目标规划的单纯形法例5-8：用单纯形法求解下列目标规划问题

MinZ=P1

d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2

+d1--d1+=204x1+3x2

+d2--d2+=24x1

+d3--d3+=3-x1

+x2

+d4--d4+=2x1

,x2

,dk-,dk+≥0目标规划的单纯形法例5-8：用单纯形法求解下列目标规划问题目标规划的单纯形法cj值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数λjP1P2P300P10P2P23P305P3020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4--5-401000-4-322-535463-检验数λjP1P2P3d1-d2-x1d4-P1P205P331000001-1005041-100-55001203001-1-440050100001-11-10-40105-50-324-4-5-25513--P1P23P35P3目标规划的单纯形法cjCBXBbx1x2d1-d1+d2-目标规划的单纯形法cj00P10P2P23P305P30值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数λjP1P2P3d3+d2-x1d4-0P205P3104/51/5-1/500-110080-1/5-4/54/51-10000414/51/5-1/5000000609/51/5-1/500001-1010001/54/5-4/52-9-1135-10--检验数λjP1P2P3d3+d1+x1d4-0005P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-10100011-35/4-5/45/4354-832/7目标规划的单纯形法cj00P10P2P23P305P30目标规划的单纯形法cj00P10P2P23P305P30值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数λjP1P2P3x2d1+x1d4-0005P3401001/3-1/3-4/34/3001100-114/3-4/3-1/31/3003100000-110010000-1/31/37/3-7/31-100100115/3-5/3-26/335/35---3检验数λjP1P2P3x2d1+x1d3-0003P33/70000-1/71/71-13/7-3/732/701001/7-1/7004/7-4/778/700-119/7-9/7001/7-1/718/710001/7-1/700-3/73/7001000113/7-3/7326/79/7目标规划的单纯形法cj00P10P2P23P305P30目标规划的单纯形法例5-9：用单纯形法求解下列目标规划问题

minZ=P1d1++P2(d2-+d2+)+P3d3-2x1+x2

+x3=11x1-x2+d1-

-d1+=0x1+2x2

+d2-

-d2+=108x1

+10x2+d3-

-d3+=56xi,dk-,dk+

≥0目标规划的单纯形法例5-9：用单纯形法求解下列目标规划问题目标规划的应用例5-10：已知一个生产计划的线性规划模型，经营目标：P1：总利润不低于40P2：充分利用设备能力，且尽量不超过140如何安排生产？产品资源甲乙现有资源设备2010140售价108成本56最大需求量610minZ=P1d1-+P2(d2-+d2+)x1≤6x2≤105x1+2x2+d1--d1+=4020x1+10x2+d2--d2+=140x1,x2,d1-,d1+,d2-,d2+≥0x1x2x1=6x2=10③④d1+d1-d2+d2-CBD(6,5)目标规划的应用例5-10：已知一个生产计划的线性规划模型，经满意解:x1=6，x2=5设备能力:需求206+105=170，实际140实现目标P1和P2，降低甲乙产品的设备消耗:降低率(170-140)/170=18%，甲产品的设备消耗降为20(1-18%)=16.4，乙产品的设备消耗降为