运筹学目标规划讲义

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

多目标线性规划含有多个优化目标的线性规划。线性规划模型只能有一个目标函数，可称为单目标线性规划。多目标线性规划模型具有两个或两个以上的目标函数。引例1某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品的技术消耗定额及单位产品的利润如表所示。试确定计划期内的生产计划，使获得的利润最大。

产品资源甲乙现有资源

设备4324单位产品利润

54解：设x1、x2分别表示甲、乙两种产品的产量，则可建立线规划模型如下：

maxZ=5x1+4x2

4x1+3x2≤24x1，x2≥0假设：该工厂根据市场需求或合同规定，希望尽量扩大甲产品的生产；减少乙产品的产量。这时又增加了二个目标，则可建立如下的模型：

maxZ1=5x1+4x2

maxZ2=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吨吨；月初批发发销货，，月中采采购进货货，进货货所需资资金完全全来销售售收入；；1月初库库存量2吨，成成本2.5千元元/吨，，该月初初无现金金。经营目标标：(1)每每月都使使用正常常库容，，尽量不不超容；；(2)每每月下下旬都应应储备1千元以以备急用用；(3)4个月总总盈利最最大。决策变量量：