4运筹学目标规划讲义

目标规规划GoalProgramming2本章主主讲内内容目标规规划问问题及及其数数学模模型（（重点点掌握握）求解GP的的思路路目标规规划的的图解解法目标规规划的的单纯纯形法法★★目标规规划问问题及及其数数学模模型线性规规划的的局限限性只能解解决一一组线线性约约束条条件下下，某某一目目标而而且只只能是是一个个目标标的最最大或或最小小值的的问题题。线性规规划只只研究究在满满足一一定条条件下下，单单一目目标函函数取取得最最优解解，而而在企企业管管理中中，经经常遇遇到多多目标标决策策问题题，如如拟订订生产产计划划时，，不仅仅考虑虑总产产值，，同时时要考考虑利利润，，产品品质量量和设设备利利用率率等。。这些些指标标之间间的重重要程程度（（即优优先顺顺序））也不不相同同，有有些目目标之之间往往往相相互发发生矛矛盾。。线性规规划致致力于于某个个目标标函数数的最最优解解，这这个最最优解解若是是超过过了实实际的的需要要，很很可能能是以以过分分地消消耗了了约束束条件件中的的某些些资源源作为为代价价。线性规规划把把各个个约束束条件件的重重要性性都不不分主主次地地等同同看待待，这这也不不符合合实际际情况况。实际决决策中中，衡衡量方方案优优劣考考虑多多个目目标生产计计划决决策中中，通通常要要考虑虑产值值、利利润、、满足足市场场需求求、降降低消消耗、、提高高质量量、提提高劳劳动生生产率率等；；生产布布局决决策中中，除除了要要考虑虑运输输费用用、投投资、、原料料供应应、产产品需需求量量等经经济指指标外外，还还要考考虑到到污染染和其其它社社会因因素等等。。这些目目标中中，有有主要要的，，也有有次要要的；；有最最大的的，也也有最最小的的；有有定量量的，，也有有定性性的；；有互互相补补充的的，也也有互互相对对立的的，LP则无能能为力力。求解线线性规规划问问题，，首先先要求求约束束条件件必须须相容容，如如果约约束条条件中中，由由于人人力，，设备备等资资源条条件的的限制制，使使约束束条件件之间间出现现了矛矛盾，，就得得不到到问题题的可可行解解，但但生产产还得得继续续进行行，这这将给给人们们进一一步应应用线线性规规划方方法带带来困困难。。在实实际际问问题题中中，，可可能能会会同同时时考考虑虑几几个个方方面面都都达达到到最最优优：：产产量量最最高高，，成成本本最最低低，，质质量量最最好好，，利利润润最最大大，，环环境境达达标标，，运运输输满满足足等等。。多多目目标标规规划划能能更更好好地地兼兼顾顾统统筹筹处处理理多多种种目目标标的的关关系系，，求求得得更更切切合合实实际际要要求求的的解解。。目标标规规划划（（GoalProgramming）目标标规规划划可可根根据据实实际际情情况况，，分分主主次次地地、、轻轻重重缓缓急急地地考考虑虑问问题题。。在LP的基基础础上上发发展展起起来来的的解解决决多多目目标标规规划划问问题题的的最最有有效效的的方方法法之之一一。。美国国经经济济学学家家查查恩恩斯斯(A.Charnes)和和库库柏柏(W.W.Cooper)在在1961年年出出版版的的《《管管理理模模型型及及线线性性规规划划的的工工业业应应用用》》一一书书中中，，首首先先提提出出的的。。多目目标标线线性性规规划划含有有多多个个优优化化目目标标的的线线性性规规划划。。线性性规规划划模模型型只只能能有有一一个个目目标标函函数数，，可可称称为为单单目目标标线线性性规规划划。。多目目标标线线性性规规划划模模型型具具有有两两个个或或两两个个以以上上的的目目标标函函数数。。引例例1某工工厂厂计计划划生生产产甲甲、、乙乙两两种种产产品品，，现现有有的的设设备备资资源源、、每每种种产产品品的的技技术术消消耗耗定定额额及及单单位位产产品品的的利利润润如如表表所所示示。。试试确确定定计计划划期期内内的的生生产产计计划划，，使使获获得得的的利利润润最最大大。。产品资源甲乙现有资源

设备4324单位产品利润

54解：设x1、x2分别别表示示甲甲、、乙乙两两种种产产品品的的产产量量，，则则可可建建立立线线规规划划模模型型如如下下：：maxZ=5x1+4x24x1+3x2≤24x1，x2≥0假设设：该工工厂厂根根据据市市场场需需求求或或合合同同规规定定，，希希望望尽尽量量扩扩大大甲甲产产品品的的生生产产；；减减少少乙乙产产品品的的产产量量。。这这时时又又增增加加了了二二个个目目标标，，则则可可建建立立如如下下的的模模型型：：maxZ1=5x1+4x2maxZ2=x1minZ3=x24x1+3x2≤24x1，x2≥0这些目标标之间相相互矛盾盾，一般的线线性规划划方法不不能求解解引例2某工厂生生产两种种产品，，受到原原材料供供应和设设备工时时的限制制。在单单件利润润等有关关数据已已知的条条件下，，要求制制订一个个获利最最大的生生产计划划。具体体数据见见下表产品III资源限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）68设产品I和II的产量量分别为为X1和X2，当用线线性规划划来描述述和解决决这个问问题时，，其数学学模型为为：其最优解解，即最最优生产产计划为为X1=8，X2=2，maxz=64假设计划划人员还还被要求求考虑如如下意见见：（1）由由于产品品II销销售疲软软，故希希望产品品II的的产量不不超过产产品I的的一半。。（2）原原材料严严重短缺缺，生产产中应避避免过量量消耗。。（3）最最好能节节约4小小时设备备工时；；（4）计计划利润润不少于于48元元。面对这些些意见，，计划人人员作出出如下意意见，首先原材材料使用用额不得得突破；；产品II产量量要求必必须优先先考虑；；设备工工时问题题其次考考虑；最最后考虑虑计划利利润的要要求。求解GP的思路路加权系数数法为每一目目标赋一一个权系系数，把把多目标标模型转转化成单单一目标标的模型型。但困困难是要要确定合合理的权权系数，，以反映映不同目目标之间间的重要要程度。。优先等级级法将各目标标按其重重要程度度分成不不同的优优先等级级，转化化为单目目标模型型。有效解法法寻求能够够照顾到到各个目目标，并并使决策策者感到到满意的的解。由由决策者者来确定定选取哪哪一个解解，即得得到一个个满意解解。但有有效解的的数目太太多而难难以将其其一一求求出。目标规划划法加权系数数法和优优先等级级法的结结合对每个目目标函数数确定一一个希望望达到的的期望值值(目标值值或理想想值)；；由于各种种条件的的限制，，这些目目标值往往往不可可能全部部都达到到；对每一个个目标函函数引入入正的或或负的偏偏差变量量，分别别表示超超过或未未达到目目标值的的情况；；为区别各各目标的的重要程程度，引引入目标标的优先先等级和和加权系系数；对所有的的目标函函数建立立约束方方程，并并入原来来的约束束条件中中，组成成新的约约束条件件；从这组新新的约束束条件，，寻找使使组合偏偏差最小小的方案案。目标函数数的期望望值每一个目目标函数数希望达达到的期期望值(或目标标值、理理想值)。根据历史史资料、、市场需需求或上上级部门门的布置置等来确确定。偏差变量量每个目标标函数的的期望值值确定之之后，目目标的实实际值和和它的期期望值之之间就有有正的或或负的偏偏差。正偏差差变量量dk+表示第第k个目标标超过过期望望值的的数值值；负偏差差变量量dk-表示第第k个目标标未达达到期期望值值的数数值。。同一目目标，，它的的取值值不可可能在在超过过期望望值的的同时时，又又没有有达到到期望望值，，所以以在dk+和dk-中至少少有一一个必必须为为零。。☀☀目目标规规划的的基本本概念念目标约约束引入正正、负负偏差差变量量后，，对各各个目目标建建立的的目标标函数数方程程。原来的的目标标函数数变成成了约约束条条件的的一部部分，，即目目标约约束(软约约束)原来的的约束束条件件称为为系统统约束束(硬硬约束束)。。在引例例题中中，计计划人人员提提出新新要求求(1)由于产产品II销销售疲疲软，，故希希望产产品II的的产量量不超超过产产品I的一一半。。（2）原原材料料严重重短缺缺，生生产中中应避避免过过量消消耗。。（3）最最好能能节约约4小小时设设备工工时；；（4）计计划利利润不不少于于48元。。1/2x1>=x2x1-2x2+d1--d1+=04x1+4x2<=40-44x1+4x2+d2--d2+=366x1+8x2>=486x1+8x2+d3--d3+=48目标达达成函函数各个目目标函函数引引入正正、负负偏差差变量量，而而被列列入了了目标标约束束条件件。如何使使各目目标的的实际际值最最接近近于各各自的的期望望值，，构造造一个个新的的目标标函数数以求求得有有关偏偏差变变量的的最小小值。。这个新新的目目标函函数反反映了了各目目标函函数的的期望望值达达到或或实现现的情情况，，故把把这个个新的的目标标函数数称为为目标标达成成函数数。若要求求尽可可能达达到规规定的的目标标值，，则正正、负负偏差差变量量dk+、dk-都尽可可能最最小，，将dk+和dk-都列入入目标标函数数中，，即minSk=dk++dk-；若希望望尽可可能不不低于于期望望值(允许许超过过)，，则负负偏差差变量量dk-尽可能能的小小，而而不关关心超超出量量dk+，故只只需将将dk-列入目目标函函数，，minSk=dk-；若允许许某个个目标标低于于期望望值，，但希希望不不得超超过期期望值值，则则正偏偏差变变量dk+尽可能地小小，而不关关心低于量量dk-，故只需将将dk+列入目标函函数，minSk=dk+。优先等级和和权数目标的重要要程度不同同，用优先先等级因子子Pk来表示第k等级目标。。优先等级因因子Pk是正的常数数，Pk>>Pk+1。同一优先等等级下的目目标的相对对重要性，，赋以不同同的加权系系数w。例如第一个目标标:由于产产品II销销售疲软，，故希望产产品II的的产量不超超过产品I的一半。。其优先级级为P1；（4）。。第二个目标标:最好能能节约4小小时设备工工时是其优优先级为P2；第三个目标标：计划利利润不少于于48元,优先级为为P3。minZ=P1d1-+P2d2++P3d3-所以，引例例2的目标标规划模型型如下：minZ=P1d1-+P2d2++P3d3-5x1+10x2<=60x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48引例1：管理部门提提出新要求求：第一个个目标是实实现利润最最大，计划划部门规定定利润目标标是20；；第二个目目标是充分分利用设备备台时，但但尽量少加加班；第三三个目标做做如下规定定，甲产品品产量希望望不少于3单位，乙乙产品产量量比甲产品多2单位。。对各目标标函数引入入正、负偏偏差变量，，则目标约约束为：5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1+d3--d3+=3-x1+x2+d4--d4+=2目标达成函函数第一个目标标是实现利利润最大，，其优先级级为P1；第二个目标标是充分利利用设备台台时，但尽尽量少加班班，其优先先级为P2；第三个目标标：甲的产产量不少于于3，乙的的产量比甲甲多2，优优先级为P3。假设设：甲产品品产量量希希望望不不少少于于3单单位位的的权权数数为为3，，乙产产品品产产量量比比甲甲产品品多2单单位位的的权权数数为为5。。minZ=P1d1-+P2(d2-+d2+)+P3(3d3-+5d4-)minZ=P1d1-+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目标标规规划划的的数数学学模模型型课堂堂练练习习：：电视视机机厂厂装装配配25寸寸和和21寸寸两两种种彩彩电电，，每每台台电电视视机机需需装装备备时时间间1小小时时，，每每周周装装配配线线计计划划开开动动40小小时时，，预预计计每每周周25寸寸彩彩电电销销售售24台台，，每每台台可可获获利利80元元，，每每周周21寸寸彩彩电电销销售售30台台，，每每台台可可获获利利40元元。。该厂厂目目标标：：1、、充充分分利利用用装装配配线线，，避避免免开开工工不不足足。。2、、允允许许装装配配线线加加班班，，但但尽尽量量不不超超过过10小小时时。。3、尽量满足足市场需求（（产品25寸寸的两倍重要要于21寸的的电视机）。。解：设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)目标规划的解解法目标规划的图图解法只含有两个决决策变量的目目标规划模型型线性规划是在在可行域中寻寻找一点，使使单个目标极极大或极小；；目标规划则则是寻找一个个区域，这个个区域提供了了相互矛盾的的目标集的折折衷方案。目标规划的图图解法的思路路首先是在可行行域内寻找一一个使P1级各目标均满满足的区域R1；然后再在R1中寻找一个使使P2级各目标均满满足的区域R2(R2R1)；接着再在R2中寻找一个满满足P3级各目标的区区域R3(R3R2R1)；如此继续，直直到寻找到一一个区域RK(RKRK-1…R3R2R1)，满足PK级各目标，这这时RK即为这个目标标规划的最优优解空间，其其中的任一点点均为这个目目标规划的满满意解。目标规划的图图解法的步骤骤首先，按照绝绝对约束画出出可行域，其次，不考虑虑正负偏差变变量，画出目目标约束的边边界线，最后。按优先先级别和权重重依次分析各各级目标。minZ=P1d1-+P2d2++P3d3-5x1+10x2<=60(1)x1-2x2+d1--d1+=0(2)4x1+4x2+d2--d2+=36(3)6x1+8x2+d3--d3+=48(4)x1x20123456789101112131110987654321(1)(2)d1-(4)d3-(3)d2+可行域minZ=P1d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2+d1--d1+=20①4x1+3x2+d2--d2+=24②x1+d3--d3+=3③-x1+x2+d4--d4+=2④x1,x2,dk-,dk+≥0⑤x1x2①d1+d1-②d2+d2-③d3+d3-④d4-d4+DABC满意解：x1=16/7,x2=32/7第三节目标规规划的单纯形形法目标规划与线线性规划的数数学模型的结结构相似可用前述单纯纯形算法求解解目标规划模模型：将优先等级Pk视为正常数(大Ｍ法)正负偏差变量量dk+、dk-视为松弛变量量以负偏差变量量dk-为初始基变量量，建立初始始单纯形表检验数的计算算与LP单纯形表检验验数的计算完完全相同，即即j=cj–CBB-1Pj最优性判别准准则类似于LP的单纯形算法法：检验数一般是是各优先等级级因子的代数数和判断检验数的的正负和大小小minZ=P1d1-+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划为标标准型型maxZ=-P1d1--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+≥0cj值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数j00-P10-P2-P2-3P20-5P2020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4--P1-P2-3P3-5P3+5P1+4P2-2P3+4P1+3P2+5P30-P10-2P20-3P30-5P3453-检验数jd1-d2-x1d4--P1-P20-5P331000001-1005041-100-55001203001-1-440050100001-11-10+4P1+3P2+5P30-P10-2P2-5P1-4P2+2P3+5P1+4P2-5P30-5P313--cj00-P10-P2-P2-3P20-5P20值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数jd3+d2-x1d4-0-P20-5P3104/51/5-1/500-110080-1/5-4/54/51-10000414/51/5-1/5000000609/51/5-1/500001-10-P1000-1/5P2-4/5P2+4/5P2-2P2+9P3+P3-P3-3P3-5P3-10--检验数jd3+d1+x1d4-000-5P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-10-P1000-P2-P235/4P3+5/4P3-5/4P3-3P3-5P34-832/7cj00-P10-P2-P2-3P20-5P20值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数jx2d1+x1d4-000-5P3401001/3-1/3-4/34/3001100-114/3-4/3-1/31/3003100000-110010000-1/31/37/3-7/31-100-P100-P2-P2-5/3P3+5/3P326/3P3-35/3P3-5P3---3检验数jx2d1+x1d3-000-3P33/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/700-P1000-P2-P2-3/7P3+3/7P3-3P3-26/7P3-9/7P3极小化化线性性规划划求解解方法法极小化化问题题与极极大化化问题题的解解法，，主要要有一一点区区别，，那就就是进进基变变量的的选取取。由由式可可知知，若若以极极大化化为目目标，，则当当所有有非基基变量量的检检验数数σj≤0时时，Z值达达到最最大。。反之之，若若以极极小化化为目目标，，则当当某个个非基基变量量检验验数σσj＜0时时，若若取xj＞0，，将使使Z值值进一一步变变小，，即使使目标标进一一步优优化；；当所有有非基基变量量检验验数σσj≥≥0时时，若若使任任意非非基变变量xj＞＞0都都会导导致目目标函函数的的增加加从而而偏离离了极极小化化目标标，于于是可可以认认定此此时的的解为为最优优解。。总而言言之，，极小小化问问题的的判别别准则则是：：σj≥0(j=1，2，……，n)时时为最最优，，进基基变量量的选选取是是在负负检验验数中中选取取最小小的一一个σσk，它所所对应应的变变量xk为换入入变量量。举例：：Cj比值CBXBb检验数jx1x2x3x4x51-400033-11006-41010811001x3x4x500001-4000-68填入初初始单单纯形形表Cj比值CBXBb检验数jx1x2x3x4x51-400033-11006-41010811001x3x4x500001-4000-68检验数j9-101006-410102500-11x3x2x50-40-150040--2/5Cj比值CBXBb检验数jx1x2x3x4x51-40009-101006-410102500-11x3x2x50-40-150040--2/5检验数j47/5001-1/51/52/5100-1/51/538/50101/54/5x3x2x10-4100013所有的的检验验数大大于得到最最优解解X1=2/5X2=38/5Z=-30经营目目标P1：总利利润不不低于于40，P2：充分分利用用设备备能力力，且且尽量量不超超过140如何安安排生生产？？在目标标管理理中的的应用用产品资源甲乙现有资源设备2010140售价108成本56最大需求量610x1x2x1=6x2=10③④d1+d1-d2+d2-CBD(6,5)minZ=P1d1-+P2(d2-+d2+)x1≤6①x2≤10②5x1+2x2+d1--d1+=40③20x1+10x2+d2--d2+=140④x1,x2,d1-,d1+,d2-,d2+≥0满意解：：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某副食品品批发店店预测某某商品今今后4月月的购进进与售出出价格如如表：在库存管管理中的的应用月份1234成本(购价+库存)2.8售价3.3假设：该该商品供供不应求求，最大大销量受受仓库容容量限制制；正常库容容3吨，，机动库库容2