一章六节-线性目标规划

线性目标规划(Goalprogramming)目标规划的图解法目标规划的单纯形法目标规划概述及其模型

目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。

2、线性规划求最优解；目标规划是找到一个满意解。1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。第一节目标规划概述及其模型（一）目标规划与线性规划的比较4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。目前，目标规划已经在经济计划、生产管理、物流管理、市场分析、财务管理等方面得到了广泛的应用。

例1:某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲

单位产品资源消耗（二）目标规划的基本概念设：甲产品x1

，乙产品

x2

一般有：maxZ=70x1

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

x1，

x2≥0同时：maxZ1=70x1

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

x1，

x2≥0

显然，这是一个多目标规划问题，用线性规划方法很难找到最优解。

目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj

选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为d。正偏差变量：表示实现值超过目标值的部分，记为d＋。负偏差变量：表示实现值未达到目标值的部分，记为d－。1、目标值和偏差变量

当完成或超额完成规定的指标则表示：d＋≥0,d－＝0

当未完成规定的指标则表示：d＋＝0,d－≥0

当恰好完成指标时则表示：d＋＝0,d－＝0∴d＋×d－

＝0成立。

引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束既可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－

＝0,并规定d＋≥0,d－≥02、目标约束和绝对约束

绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。

例如：在例一中，规定Z1

的目标值为50000,正、负偏差为d＋、d－

,则目标函数可以转换为目标约束，既70x1

+120x2＋＝50000，

同样，若规定Z2＝200，Z3＝250

则有

若规定3600的钢材必须用完，原式9x1+4x2≤3600则变为

达成函数是一个使总偏差量为最小的目标函数，记为minZ=f（d＋、d－）。

一般说来，有以下三种情况，但只能出现其中之一：⑴.要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f（d＋＋d－）。⑵.要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ=f（d＋）。⑶.要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ=f（d－）。

3、达成函数（即目标规划中的目标函数）

优先因子Pk

是将决策目标按其重要程度排序并表示出来。P1>>P2>>…>>Pk>>Pk+1>>…>>PK

，k=1.2…K。权系数ωk

区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。

对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。4、优先因子（优先等级）与优先权系数5、满意解（具有层次意义的解）若在例一中中提出下列列要求：1、超额完成成利润指标标50000元；2、产品甲不不超过200件，产品乙乙不低于250件；3、现有钢材材3600吨必须用完完。试建立目标标规划模型型。分析：题目目有三个目目标层次，，包含四个个目标值。。第一目标：：第二目标：：有两个要要求即甲，，乙，，两者具具有相同的的优先因子子，为区分分两者的差差别（或重重要程度）），需要确确定权系数数。本题可可用单件利利润比作为为权系数即即70:120，化简为7:12。例2:第三目标：：目标规划模模型为：某厂生产Ⅰ、Ⅱ两种产品，，有关数据据如表所示示。试求获获利最大的的生产方案案？ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810在此此基基础础上上考考虑虑：：1、产产品品Ⅱ的产产量量不不低低于于产产品品Ⅰ的产产量量；；2、充充分分利利用用设设备备有有效效台台时时，，不不加加班班；；3、利利润润不不小小于于56元。。解:分析析第第一一目目标标：：即产产品品Ⅰ的产产量量不不大大于于Ⅱ的产产量量。。第二二目目标标：：例3：第三三目目标标：：规划划模模型型：：（三三））目目标标规规划划数数学学模模型型1、目目标标规规划划数数学学模模型型的的一一般般形形式式达成成函函数数目标标约约束束其中中：：gk为第第k个目目标标约约束束的的预预期期目目标标值值，，和和为为pl优先先因因子子对对应应各各目目标标的的权权系系数数。。2、建建模模的的步步骤骤（1）根根据据要要研研究究的的问问题题所所提提出出的的各各目目标标与与条条件件，，确确定定目目标标值值，，列列出出目目标标约约束束与与绝绝对对约约束束。。（4）对对同同一一优优先先等等级级中中的的各各偏偏差差变变量量，，若若需需要要可可按按其其重重要要程程度度的的不不同同，，赋赋予予相相应应的的权权系系数数。。（3）给给各各目目标标赋赋予予相相应应的的优优先先因因子子Pk（k=1.2…K）。。（2）可可根根据据决决策策者者的的需需要要，，将将某某些些或或全全部部绝绝对对约约束束转转化化为为目目标标约约束束。。这这时时只只需需要要给给绝绝对对约约束束加加上上负负偏偏差差变变量量和和减减去去正正偏偏差差变变量量即即可可。。（5）根根据据决决策策者者的的要要求求，，按按下下列列情情况况之之一一构构造造一一个个由由优优先先因因子子和和权权系系数数相相对对应应的的偏偏差差变变量量组组成成的的，，要要求求实实现极小化的目目标函数，即即达成函数。。1.恰好达到目标标值，即取正正、负偏差变变量都要尽可可能地小，这这时2.要求超过目标标值，即超过过量不限，但但必须是负偏偏量要尽可能能小，这时3.要求不超过目目标值，即允允许达不到目目标函数值，，即正偏量要要尽可能小，，这时3、小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xsxa

xixsxad约束条件绝对约束目标约束绝对约束解最优最满意第二节目标标规划图解法法目标规划的图图解法：适用两个变量量的目标规划划问题，但其其操作简单，，原理一目了了然。同时，，也有助于理理解一般目标标规划的求解解原理和过程程。图解法解题步步骤：1.将所有约束条条件（包括目目标约束和绝绝对约束，暂暂不考虑正负负偏差变量，，令其等于0）的直线方程程分别标示于于坐标平面上上。2.确定系统约束束的可行域。。3.在目标约束所所代表的边界界线上，用箭箭头标出正、、负偏差变量量值增大的方方向。目标规划的图图解法4.求满足最高优优先等级目标标的解5.转到下一个优优先等级的目目标，再不破破坏所有较高高优先等级目目标的前提下下，求出该优优先等级目标标的解6.重复5，直到所有优优先等级的目目标都已审查查完毕为止，，确定最优解解和满意解。。目标规划的图图解法例4用图解法求解解下列目标规规划问题目标规划的图图解法(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解(3,3)046834622目标规划的图图解法x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD满意意解解是是线线段段GD上任任意意点点其中中G点X＝(2,4),D点X＝(10/3,10/3)05.51055.6112,410/3,10/35107例5目标标规规划划的的图图解解分分析析法法Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)满意意解解X=(24，26)例6目标标规规划划应应用用举举例例例7已知知一一个个生生产产计计划划的的线线性性规规划划模模型型如如下下，，其其中中目目标标函函数数为为总总利利润润，，x1,x2为产产品品A、B产量量。。现有有下下列列目目标标：：1.要求求总总利利润润必必须须超超过过2500元；；2.考虑虑产产品品受受市市场场影影响响，，为为避避免免积积压压，，A、B的生产产量量不不超超过过60件和和100件；；3.由于于甲甲资资源源供供应应比比较较紧紧张张，，不不要要超超过过现现有有量量140。试建建立立目目标标规规划划模模型型，，并并用用图图解解法法求求解解。。目标标规规划划应应用用举举例例解：：以以产产品品A,B的单单件件利利润润比比2.5:1为权权系系数数，，模模型型如如下下：：目标标规规划划应应用用举举例例0x20⑴x11401201008060402020406080100⑵⑶⑷ABCDC(60,58.3)为所求求的满满意解解。(24,26)1、建立立初始始单纯纯形表表。一般假假定初初始解解在原原点，，即以以约束束条件件中的的所有有负偏偏差变变量或或松弛弛变量量为初初始基基变量量，按按目标标优先先等级级从左左至右右分别别计算算出各各列的的检验验数（（有几几个优优先因因子，，检验验数就就有几几行）），填填入表表的下下半部部。。2、检验验是否否为满满意解解。判判别准准则如如下：：⑴按优优先级级顺序序依次次检查查P1,P2,...Pk行的检检验数数（cj-zj）,如果全全部为为非负负，则则表示示目标标均已已全部部达到到，获获得满满意解解，停停止计计算转转到第第6步；否则转转入⑵。（一）、单单纯形法的的计算步骤骤⑵.如果Pk行有负的检检验数。说说明第k个优先等级级的目标尚尚未达到,必须检查Pk这一行的检检验数。若若Pk这一行某些些负检验数数的同列上上面（较高高优先等级级）没有正正检验数，，说明未得得到满意解解，应继续续改进，转转到第3步；若Pk这一行全部部负检验数数的同列上上面（较高高优先等级级）都有正正检验数，，说明第K个目标虽没没达到，但但已不能改改进，故得得满意解，转到第6步。3、确定进基基变量。在Pk行，从那些些上面没有有正检验数数的负检验验数中，选选绝对值最最大者，对对应的变量量xs就是进基变变量。若Pk行中绝对值值最大的负负检验数有有多个（相相等），则则选最左边边的变量（（变量下标标小者）为为进基变量量。4、确定出基基变量其方法同线线性规划，，即依据最最小比值法法则故确定xr为出基变量量，ers为主元素。。若有几个个相同的行行可供选择择时，选最最上面那一一行所对应应得变量为为xr。5、旋转变换换（变量迭迭代）。以以为主主元素进行行变换，得得到新的单单纯形表，，获得一组组新解，返返回到第2步。6、对求得的的解进行分分析若计算结果果满意，停停止运算；；若不满意意，需修改改模型，即即调整目标标优先等级级和权系数数，或者改改变目标值值，重新进进行第1步。第一步，列列出初始单单纯形表，，目标约束束中负偏差差变量系数数均为单位位向量，故故它们的系系数列向量量构成初始始基。目标标函数中偏偏差变量分分别乘以不不同的优先先因子，因因此表中的的检验数（（cj-zj）按优先因因子P1，P2分成两行，，分别计算算。按优先先级依次检检查，确定定入基、出出基变量用换入变量量替换基变变量中的换换出变量，，进行迭代代运算，得得下表。因检验数中中p2行中仍有负负数，可以以继续优化化，重复迭迭代，得最最终单纯形形表P2行中虽有负负检验数，，但负检验验数同列较较高优先级级的行中存存在正检验验数，计算算应停止，，得到满意意解。说明：对目标函数数的优化是是按优先等等级顺序逐逐级进行的的。当P1行所有检验验数均为非非负时，再再考察P2行的检验数数是否存在在负值，依依次类推。。判断迭代计计算是否应应停止的准准则为：（1）检验数P1，P2,...,Pk行的所有值值均为非负负。（2）若P1,,...,Pi行所有检验验数为非负负，第Pi+1行存在负检检验数，但但在负检验验数所在列列的上面行行中有正检检验数。如如上题中，，P2行中虽有负负检验数，，但负检验验数同列较较高优先级级的行中存存在正检验验数，计算算应停止。。例9.用单纯形法法求解已知一个生生产计划的的线性规划划模型为其中目标函函数为总利利润，x1,x2为产品A、B产量。现有有下列目标标：1、要求总利利润必须超超过2500元；2、考虑产品品受市场影影响，为避避免积压，，A、B的生产量不超超过60件和100件；3、由于甲资资源供应比比较紧张，，不要超过过现有量140。解：以产品品A、B的单件利润润比2.5：1为A、B产品产量权权系数，模模型如下：：Cj00P100P302.5P20P2CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σjP1

－30－1201000000P2

00000002.501P3

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

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

0－12010030－3000P2

00000002.501P3

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

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

030115-150000P2

0-5/400-5/45/45/2001P3

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

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

0010000000P2

0-1-1/121/12002/5001P3

01/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75/3,故为为换出出变量。。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σjP1

0010000000P2

00000005/201P3

00-1/121/12101/2-1/200表中P3行存在负数，说明P3优先等级目标标没有实现，，但已无法改改进，得到满满意解x1＝60，x2＝175/3，＝115/3，＝125/3。结果分析：计计算结果表明明，工厂应生生产A产品60件，B产品175/3件，2500元的利润目标标刚好达到。。＝＝125/3，表明产品比比最高限额少少125/3件，满足要求求。＝＝115/3表明甲资源超超过库存115/3公斤，该目标标没有达到。。从表中还可以以看到，P3的检验数还有有负数，但其其高等级的检检验数却是正正数，要保证证P1目标实现，P3等级目标则无无法实现。可考虑如下措措施：降低A、B产品对甲资源源的消耗量，，以满足现有有甲资源库存存量的目标；；或改变P3等级目标的指指标值，增加加甲资源115/3公斤。若很难实现现上述措施施，则需改改变现有目目标的优先先等级，以以取得可行行的满意结结果。练习：用单纯形法法求解下列列目标规划划问题Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000

P3

56810