运筹学目标规划

第5章目的规划(Goalprogramming)第1节目的规划的数学模型第2节目的规划的图解法第3节目的规划的单纯形法目的规划是在线性规划的根底上，为顺应经济管理中多目的决策的需求而逐渐开展起来的一个分支。线性规划只研讨在满足一定条件下，单一目的函数获得最优解，在实践问题中，能够会同时思索几个方面都到达最优：产量最高，本钱最低，质量最好，利润最大，环境达标，运输满足等。目的规划能更好地兼顾统筹处置多种目的的关系，求得更切合实践要求的解。第1节目的规划的数学模型一、目的规划概述目的规划举例例1.某工厂消费I、II两种产品，知有关数据如表。试求获利最大的消费方案。产品I产品II拥有量原材料(kg)2111设备(hr)1210利润(元/件)810实践上，工厂在作决策时，要思索一系列要素：(1)产品I的产量不大于产品II；(2)原资料超越时，采购本钱添加；(3)设备台时尽量用完；(4)尽能够到达并超越方案利润目的56元。1)线性规划只讨论一个线性目的函数在一组线性约束条件下的极值问题；而目的规划是多个目的决策，可求得更切合实践的解。2)线性规划求最优解；目的规划是找到一个称心解。〔一〕、目的规划与线性规划的比较4)线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才干得到；实践过程中，只求得称心解，就能满足需求〔或更能满足需求〕。3)线性规划中的约束条件是同等重要的，是硬约束；而目的规划中有轻重缓急和主次之分，即有优先权。〔二〕、目的规划的根本概念例1.某工厂消费I、II两种产品，知有关数据如表。试求获利最大的消费方案。产品I产品II拥有量原材料(kg)2111设备(hr)1210利润(元/件)810实践上，工厂在作决策时，要思索一系列要素：(1)产品I的产量不大于产品II；(2)原资料超越时，采购本钱添加；(3)设备台时充分用完，不加班；(4)尽能够到达并超越方案利润目的56元。x1≤x2，即x1-x2≤0；2x1+x2≤11；x1+2x2=10；8x1+10x2≥56；目的规划经过引入目的值g和偏向变量d，可以将目的函数转化为目的约束。目的值gk：是指预先给定的某个目的的一个期望值。实现值或决策值fk(xj)：是指当决策变量xj选定以后，目的函数的对应值。偏向变量〔事先无法确定的未知数〕：是指实现值和目的值之间的差别，记为d。单词deviation的首字母。正偏向变量，记为d+：表示实现值超越目的值的部分。负偏向变量，记为d-：表示实现值未到达目的值的部分。1、决策变量xj和正、负偏向变量d+，d-在一次决策中，实现值不能够既超越目的值又未到达目的值，故有d＋×d－＝0，并规定d＋≥0，d－≥0绝对约束〔系统约束〕是指必需严厉满足的等式或不等式约束。如线性规划中的一切约束条件都是绝对约束，否那么无可行解。所以，绝对约束是硬约束。引入目的值g、正偏向变量d+、负偏向变量d-后，就对某一问题有了新的限制，即目的约束。目的约束既可对原目的函数起作用，也可对原约束起作用。目的约束是目的规划中特有的，是软约束。2、目的约束和绝对约束普通表示为：f(xj)=g+d+-d-思索：以下三种情形下，如何才算到达目的？假设决策目的中规定f(xj)g，那么目的中d+=0；假设决策目的中规定f(xj)g，那么目的中d-=0；假设决策目的中规定f(xj)=g，那么目的中d+=d-=0.

准那么函数是一个使总偏向量为最小的目的函数，记为minz=f(d＋,d-)。对应一个目的约束，有以下三种情况，但只能出现其中之一：⑴.恰好到达规定的目的值，即f(xj)=g，正、负偏向变量d＋、d-都要尽能够小，那么minz=f(d＋＋d-)。⑵.不超越目的值，即f(xj)g，正偏向变量d＋尽能够小，那么minz=f(d＋)。⑶.超越目的值，即f(xj)g，负偏向变量d-尽能够小，那么minz=f(d-)。3、准那么函数〔即目的规划中的目的函数〕为了将不同级别的目的的重要性用数量表示，引进P1,P2,….，用它表示一级目的，二级目的，….的重要程度，规定P1>>P2>>P3>>…，称P1，P2，….,为级别系数。优先因子Pk是将决策目的按其重要程度排序并表示出来。P1>>P2>>…>>Pk>>Pk+1，k=1,2,…,K。例如，四个决策目的用四个优先因子排序的准那么函数：

权系数ωk区别具有同一个优先因子的两个目的的差别的情况。例如，目的i和目的j具有一样的优先因子Pk准那么函数：4、优先因子(优先等级)Pk与优先权系数ωk对于这种解来说，前面的目的可以保证明现或部分实现，而后面的目的就不一定能保证明现或部分实现，有些能够就不能实现。5、称心解〔具有层次意义的解〕例1.产品I产品II拥有量原材料(kg)2111设备(hr)1210利润(元/件)810(1)产品I的产量不大于产品II；(2)原资料超越时，采购本钱添加；(3)设备台时充分用完，不加班；(4)尽能够到达并超越方案利润目的56元。x1≤x2，即x1-x2≤0；2x1+x2≤11；x1+2x2=10；8x1+10x2≥56；引入优先因子P1：x1-x2≤0；P2：2x1+x2≤11；P3：x1+2x2=10；P4：8x1+10x2≥56；目的约束：x1-x2=0+d1+-d1-；2x1+x2=11+d2+-d2-；x1+2x2=10+d3+-d3-；8x1+10x2=56+d4+-d4-；例1.产品I产品II拥有量原材料(kg)2111设备(hr)1210利润(元/件)810(1)产品I的产量不大于产品II；(2)原资料超越时，采购本钱添加；(3)设备台时尽量用完；(4)尽能够到达并超越方案利润目的56元。x1≤x2，即x1-x2≤0；2x1+x2≤11；x1+2x2=10；8x1+10x2≥56；目的函数minP1d1+；minP2d2+；minP3(d3++d3-)；minP4d4-；minz=P1d1++P2d2++P3(d3++d3-)+P4d4- 目的约束：x1-x2=0+d1+-d1-；2x1+x2=11+d2+-d2-；x1+2x2=10+d3+-d3-；8x1+10x2=56+d4+-d4-；例a.某厂方案在下一个消费周期内消费甲、乙两种产品，知资料如表所示。试制定消费方案，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽能够少消费；乙的销路较好，可以扩展消费。试建立此问题的目的规划模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源耗费假设在例a中提出以下要求：(1)首先完成或超额完成利润目的50000元；(2)其次，产品甲不超越200件，产品乙不低于250件；(3)再次，现有钢材3600吨必需用完。假设在例a中提出以下要求：(1)首先，完成或超额完成利润目的50000元；(2)其次，产品甲不超越200件，产品乙不低于250件；(3)再次，现有钢材3600吨必需用完。试建立目的规划模型。分析：本例引入3个优先因子P1,P2,P3；分析：标题有三个目的层次，包含四个目的值。第一目的：第二目的：有两个要求即甲，乙，但两个具有一样的优先因子P2，因此需求确定权系数。此题可用单件利润比作为权系数即70:120，化简为7:12。第三目的：目的规划模型为：12070利润3000103台时200054煤炭360049钢材资源乙甲

某厂消费Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的消费方案？ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810在此根底上思索：(1)产品Ⅱ的产量不低于产品Ⅰ的产量；(2)充分利用设备有效台时，不加班；(3)利润不小于56元。解:分析第一目的：minz1=第二目的：minz2=例2：第三目的：minz3=x1≤x2，即x1-x2≤0；x1+2x2=10；8x1+10x2≥56；规划模型：〔一〕、模型的普通方式二、目的规划的数学模型其中，gk为目的约束的目的值；bi为绝对约束的资源值。约束目的函数目的约束资源约束〔二〕、建模的步骤1、根据要研讨的问题所提出的各目的与条件，确定目的值，列出目的约束与绝对约束；4、对同一优先等级中的各偏向变量，假设需求可按其重要程度的不同，赋予相应的权系数。3、给各目的赋予相应的优先因子Pl(l=1,2,…,L)。2、可根据决策者的需求，将某些或全部绝对约束转化为目的约束。这时只需求给绝对约束加上负偏向变量和减去正偏向变量即可。5、根据决策者的要求，按以下情况之一

构造一个由优先因子和权系数相对应的偏向变量组成的，要务虚现极小化的目的函数，即准那么函数。⑴.恰好到达目的值，取。⑵.允许超越目的值，取。⑶.不允许超越目的值，取。练习1：1.知条件如表所示工序型号每周最大加工能力ABⅠ（小时/台）Ⅱ（小时/台）436215070利润（元/台）300450假设工厂运营目的的期望值和优先等级如下：P1:每周总利润不得低于10000元；P2:因合同要求，A型机每周至少消费10台，B型机每周至少消费15台；P3:希望工序Ⅰ的每周消费时间正好为150小时，工序Ⅱ的消费时间最好用足，甚至可适当加班。试建立这个问题的目的规划模型。练习2、知一个消费方案的线性规划模型为其中目的函数为总利润，x1,x2为产品A、B产量。现有以下目的：1、要求总利润必需超越2500元；2、由于甲资源供应比较紧张，不要超越现有量140；3、思索产品受市场影响，为防止积压，A、B的消费量不超越60件和100件。试建立目的规划模型。解：以产品A、B的单件利润比2.5：1为权系数，模型如下：〔三〕、小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xsxa

xixsxad约束条件系统约束（绝对约束）目标约束系统约束解最优最满意建立目的规划的数学模型时，需求确定目的值gk、优先因子Pl、权系数ωj等，它都具有一定的客观性和模糊性，可以用专家评定法给以量化。图解法同样适用两个变量的目的规划问题，但其操作简单，原理一目了然。同时，也有助于了解普通目的规划的求解原理和过程。图解法解题步骤如下：(1)确定各约束条件的可行域，即将一切约束条件〔包括目的约束和绝对约束，暂不思索正负偏向变量〕在坐标平面上表示出来；(2)在目的约束所代表的边境限上，用箭头标出正、负偏向变量值增大的方向；第2节目的规划的图解法(3)求满足最高优先等级目的的解；(4)转到下一个优先等级的目的，在不破坏一切较高优先等级目的的前提下，求出该优先等级目的的解；(5)反复4，直到一切优先等级的目的都已审查终了为止；(6)确定最优解和称心解。例2：用图解法求解目的规划问题。⑴⑵⑶⑷GD结论：有无穷多称心解，G(2,4)～D(10/3,10/3)x2x1用图解法求解例2的目的规划012345678123456⑴⑵⑶Ax2x1BCB(0.6250,4.6875)~C(0,5.2083)，B、C线段上的一切点均是该问题的解〔无穷多称心解〕。例b.用图解法求解目的规划问题在例2的图解法求解时，把绝对约束作最高级思索。在例2中依先后次序都能满足d1+=0、d2++d2-=0、d3-=0，因此z*=0。在例b中d1++d1-=0、d2-=0，因此z*=0。但在大多数问题中并非如此，会出现某些约束得不到满足，仅仅得到称心解。例3.彩色电视机黑白电视机拥有量装配线台时1140获利(元/台)8040销量(台)2430该厂目的为：P1：充分利用装配线每周开动超越40小时；P2：加班时间每周尽量不超越10小时；P3：彩色、黑白电视销量尽量超越24、30台。同优先因子下两个目的的权系数可用单件利润比作为权系数即80:40，化简为2:1。设x1，x2分别表示彩色和黑白电视机的产量。以上问题的目的规划模型10203040501020304050x2x1(1)(2)(3)(4)EFBAABEF区域中无法满足d4-=0，只能取一点使d4-尽能够小，即E点。E点为称心解，其坐标(24,26)。

作业：

P127，T5.2〔2〕练习：

P127，T5.2〔1〕

Cj

c1c2cn+2mCBXBb

x1x2xn+2m

cj1xj1bo1e11e12e1n+2mcj2xj2bo2e21e22e2n+2mcjmxjm

bomem1em2emn+2mσkjP1α1σ11σ12σ1n+2mP2

α2σ21σ22σ2n+2mPK

αK

σm1σm2σmn+2m第3节目的规划的单纯形法〔一〕、普通方式：〔二〕、单纯形法的计算准那么1)∵minz，∴一切cj-zj≥0为最优准那么。2)检验能否为称心解。∵非基变量的检验数含Pk，即cj-zj=ΣαkjPk，(k=1,2,…,k；j=1,2,…,n)∴首先检查αkj能否全部为零？假设αkj全部为零，那么表示目的均已全部到达，获得称心解，停顿计算转到第(5)步；否那么转入(2)。(1)建立初始单纯形表。普通假定初始解在原点，即以约束条件中的一切负偏向变量或松弛变量为初始基变量，按目的优先等级从左至右分别计算出各列的检验数，填入表的下半部。〔三〕、单纯形法的计算步骤在Pk行，从负检验数中，选绝对值最大者，对应的变量xs就是进基变量。假设Pk行中有几个一样的绝对值最大者，那么依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。假设仍无法确定，那么选最左边的变量〔变量下标小者〕为进基变量。(2)检验能否为称心解。首先检查检验数αkj(k=1,2,…,k)能否全部为零？假设全部为零，那么表示目的均已全部到达，获得称心解，停顿计算转到第(5)步；某一个αkj<0，并且Pk这一行的检验数σkj<0(j=1,2,…,n+2m)，应继续改良，转到第(3)步。

(3)确定出基变量其方法同线性规划，即根据最小比值法那么故确定xr为出基变量，ers为主元素。假设有几个一样的行可供选择时，选最上面那一行所对应得变量为xr。(4)旋转变换〔变量迭代〕。以为主元素进展变换，得到新的单纯形表，获得一组新解，前往到第(2)步。(5)对求得的解进展分析假设计算结果称心，停顿运算；假设不称心，需修正模型，即调整目的优先等级和权系数，或者改动目的值，重新进展第(2)步。例4：用单纯形法求解例2的目的规划问题例4：用单纯形法求解例2的目的规划问题

解：将例2化为规范型θ=min｛－,10/2,56/10,11/1｝=5，故为换出变量。Cj

0000P1

P2

P2P3

0CBXBbx1x2

x3

0

x3

11211000000001－101－10000P210120001－100

P3

56810000001－1σkjP1

0000010000P2

－10－1－20000200P3

－56－8－100000001表4-1θ=min｛10/3,10,6/3,12/3｝=2,故为换出变量。Cj

0000P1

P2

P2P3

0CBXBbx1x2

x3

0

x3

63/20100-1/21/200053/2001－11/2-1/2000x251/210001/2-1/200

P3

630000-551－1σkjP1

0000010000P2

0000001100P3

－6－300005-501表4-2最优解为x1＝2，x2＝4。图4-1的G(2,4)点，但非基变量的检验数为零，故此题有无穷多最优解。θ=min｛4,24,－,6｝=4,故为换出变量。表4-3Cj

0000P1

P2

P2P3

0CBXBbx1x2

x3

0

x3

3001002-2-1/21/2020001－13-3-1/21/20x24010004/3-4/3-1/61/60x1210000-5/35/31/3-1/3σkjP1

0000010000P2

0000001100P3

0000000010⑴⑵⑶⑷GD结论：有无穷多最优解，G(2,4)～D(10/3,10/3)x2x1Cj

0000P1

P2

P2P3

0CBXBbx1x2

x3

0

x3

1001-1－1-1100040002-26-6-110x210/3010-1/31/31/3-1/3000x110/31002/3-2/31/3-1/300σkjP1

0000010000P2

0000001100P3

0000000010最优解为x1＝10/3,，x2=10/3。图4-1的D(10/3,10/3)点。表4-4例d、用单纯形法求解以下目的规划问题

Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σkjP1

-2500－30－1201000000P2

000000002.501P3

00000010000θ=min｛2500/30,140/2,60/1｝=60,故为换出变量。Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σkjP1

－7000－12010030－3000P2

000000002.501P3

00000010000θ=min｛700/30,20/2,－,－｝=10,故为换出变量。Cj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σkjP1

-400030115-150000P2

-250-5/400-5/45/45/2001P3

00000010000θ=min｛400/15,－,－,－｝=10,故为换出变量。Cj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σkjP1

00010000000P2

-175/30-1-1/121/12002/5001P3

-80/301/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75,故为换出变量。Cj

00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000125/300-1/121/12005/2-5/21－1σkjP1

00010000000P2

000000005/201P3

-115/300-1/121/12101/2-1/200表中α3＝115/3≠0，阐明P3优先等级目的没有实现，但已无法改良，得到称心解x1＝60，x2＝175/3，＝115/3，＝125/3。结果分析：计算结果阐明，工厂应消费A产品60件，B产品175/3件，2500元