运筹学目标规划讲义课件

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

在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成5多目标线性规划含有多个优化目标的线性规划。线性规划模型只能有一个目标函数，可称为单目标线性规划。多目标线性规划模型具有两个或两个以上的目标函数。多目标线性规划6引例1某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品的技术消耗定额及单位产品的利润如表所示。试确定计划期内的生产计划，使获得的利润最大。

产品资源甲乙现有资源

设备4324单位产品利润

54引例1某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品7解：设x1、x2分别表示甲、乙两种产品的产量，则可建立线规划模型如下：

maxZ=5x1+4x2

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

maxZ1=5x1+4x2

maxZ2=x1minZ3=x24x1+3x2≤24x1，x2≥0 这些目标之间相互矛盾，一般的线性规划方法不能求解

解：设x1、x2分别表示甲、乙两种产品的产量，则可建立线规划8引例2某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见下表产品III资源限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）68引例2产品III资源限量原材料（kg/件）51060设备工时9设产品I和II的产量分别为X1和X2，当用线性规划来描述和解决这个问题时，其数学模型为：其最优解，即最优生产计划为X1=8，X2=2，maxz=64设产品I和II的产量分别为X1和X2，当用线性规划来描述和解10假设计划人员还被要求考虑如下意见：（1）由于产品II销售疲软，故希望产品II的产量不超过产品I的一半。（2）原材料严重短缺，生产中应避免过量消耗。（3）最好能节约4小时设备工时；（4）计划利润不少于48元。面对这些意见，计划人员作出如下意见，首先原材料使用额不得突破；产品II产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。假设计划人员还被要求考虑如下意见：11求解GP的思路加权系数法为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。

优先等级法将各目标按其重要程度分成不同的优先等级，转化为单目标模型。

有效解法寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。求解GP的思路加权系数法12目标规划法加权系数法和优先等级法的结合对每个目标函数确定一个希望达到的期望值(目标值或理想值)；由于各种条件的限制，这些目标值往往不可能全部都达到；对每一个目标函数引入正的或负的偏差变量，分别表示超过或未达到目标值的情况；为区别各目标的重要程度，引入目标的优先等级和加权系数；对所有的目标函数建立约束方程，并入原来的约束条件中，组成新的约束条件；从这组新的约束条件，寻找使组合偏差最小的方案。目标规划法加权系数法和优先等级法的结合13目标函数的期望值每一个目标函数希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。偏差变量每个目标函数的期望值确定之后，目标的实际值和它的期望值之间就有正的或负的偏差。正偏差变量dk+表示第k个目标超过期望值的数值；负偏差变量dk-表示第k个目标未达到期望值的数值。同一目标，它的取值不可能在超过期望值的同时，又没有达到期望值，所以在dk+和dk-中至少有一个必须为零。☀☀目标规划的基本概念

目标函数的期望值☀☀目标规划的基本概念14目标约束引入正、负偏差变量后，对各个目标建立的目标函数方程。原来的目标函数变成了约束条件的一部分，即目标约束(软约束)原来的约束条件称为系统约束(硬约束)。在引例题中，计划人员提出新要求(1)由于产品II销售疲软，故希望产品II的产量不超过产品I的一半。（2）原材料严重短缺，生产中应避免过量消耗。（3）最好能节约4小时设备工时；（4）计划利润不少于48元。

1/2x1>=x2

x1-2x2+d1--d1+=0

4x1+4x2<=40-44x1+4x2+d2--d2+=36

6x1+8x2>=48

6x1+8x2+d3--d3+=48目标约束原来的目标函数变成了约束条件的一部分，即目标约束(15目标达成函数

各个目标函数引入正、负偏差变量，而被列入了目标约束条件。如何使各目标的实际值最接近于各自的期望值，构造一个新的目标函数以求得有关偏差变量的最小值。这个新的目标函数反映了各目标函数的期望值达到或实现的情况，故把这个新的目标函数称为目标达成函数。若要求尽可能达到规定的目标值，则正、负偏差变量dk+、dk-都尽可能最小，将dk+和dk-都列入目标函数中，即minSk=dk++dk-；若希望尽可能不低于期望值(允许超过)，则负偏差变量dk-尽可能的小，而不关心超出量dk+，故只需将dk-列入目标函数，minSk=

dk-；若允许某个目标低于期望值，但希望不得超过期望值，则正偏差变量dk+

尽可能地小，而不关心低于量dk-，故只需将dk+列入目标函数，minSk=

dk+。目标达成函数16优先等级和权数

目标的重要程度不同，用优先等级因子Pk来表示第k等级目标。优先等级因子Pk是正的常数，Pk>>Pk+1。同一优先等级下的目标的相对重要性，赋以不同的加权系数w。例如第一个目标:由于产品II销售疲软，故希望产品II的产量不超过产品I的一半。其优先级为P1；（4）。第二个目标:最好能节约4小时设备工时是其优先级为P2；第三个目标：计划利润不少于48元,优先级为P3。

minZ=P1d1-+P2d2++P3d3-优先等级和权数17所以，引例2的目标规划模型如下：minZ=P1d1-+P2d2++P3d3-5x1+10x2<=60x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48所以，引例2的目标规划模型如下：minZ=P1d1-+18引例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引例1：目标达成函数minZ=P1d1-+P2(d219目标规划的数学模型目标规划的数学模型20课堂练习：电视机厂装配25寸和21寸两种彩电，每台电视机需装备时间1小时，每周装配线计划开动40小时，预计每周25寸彩电销售24台，每台可获利80元，每周21寸彩电销售30台，每台可获利40元。该厂目标：1、充分利用装配线，避免开工不足。2、允许装配线加班，但尽量不超过10小时。3、尽量满足市场需求（产品25寸的两倍重要于21寸的电视机）。课堂练习：该厂目标：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)解：设X1,X2分别表示25寸，21寸彩电产量minZ22目标规划的解法目标规划的图解法只含有两个决策变量的目标规划模型

线性规划是在可行域中寻找一点，使单个目标极大或极小；目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的折衷方案。目标规划的图解法的思路首先是在可行域内寻找一个使P1级各目标均满足的区域R1；然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2R1)；接着再在R2中寻找一个满足P3级各目标的区域R3(R3R2

R1)；如此继续，直到寻找到一个区域RK(RKRK-1…R3

R2

R1)，满足PK级各目标，这时RK即为这个目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。

目标规划的解法目标规划的图解法23目标规划的图解法的步骤首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。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-+P2d224minZ=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/7minZ=P1d1-+P2(d2-+d2+)+P3(3d325第三节目标规划的单纯形法目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型：将优先等级Pk视为正常数(大Ｍ法)正负偏差变量dk+、dk-视为松弛变量以负偏差变量dk-为初始基变量，建立初始单纯形表检验数的计算与LP单纯形表检验数的计算完全相同，即j=cj–CBB-1Pj最优性判别准则类似于LP的单纯形算法：检验数一般是各优先等级因子的代数和判断检验数的正负和大小第三节目标规划的单纯形法目标规划与线性规划的数学模型的结构26minZ=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+≥0minZ=P1d1-+P2(d2-+d2+)+27cj值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--cjCBXBbx1x2d1-d1+d2-d2+d3-d3+28cj00-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-5P2029cj00-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/7P3cj00-P10-P2-P2-3P20-5P2030极小化线性规划求解方法极小化问题与极大化问题的解法，主要有一点区别，那就是进基变量的选取。由式可知，若以极大化为目标，则当所有非基变量的检验数σj≤0时，Z值达到最大。反之，若以极小化为目标，则当某个非基变量检验数σj＜0时，若取xj＞0，将使Z值进一步变小，即使目标进一步优化；极小化线性规划求解方法极小化问题与极大化问题的解法，主要有一31当所有非基变量检验数σj≥0时，若使任意非基变量xj＞0都会导致目标函数的增加从而偏离了极小化目标，于是可以认定此时的解为最优解。总而言之，极小化问题的判别准则是：σj≥0(j=1，2，…，n)时为最优，进基变量的选取是在负检验数中选取最小的一个σk，它所对应的变量xk为换入变量。当所有非基变量检验数σj≥0时，若使任意非基变量xj＞0都会32举例：举例：33Cj比值CBXBb检验数jx1x2x3x4x51-400033-11006-41010811001x3x4x500001-4000-68填入初始单纯形表Cj比CBXBb检验数jx1x2x3x4x51-4000334Cj比值CBXBb检验数jx1x2x3x4x51-400033-11006-41010811001x3x4x500001-4000-68检验数j9-101006-410102500-11x3x2x50-40-150040--2/5Cj比CBXBb检验数jx1x2x3x4x51-4000335Cj比值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=-30Cj比CBXBb检验数jx1x2x3x4x51-4000936经营目标P1：总利润不低于40，P2：充分利用设备能力，且尽量不超过140如何安排生产？

在目标管理中的应用

产品资源甲乙现有资源设备2010140售价108成本56最大需求量610经营目标在目标管理中的应用产品甲乙现有资源设备2010137x1x2x1=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+≥0x1x2x1=6x2=10③④d1+d1-d2+d2-C38满意解：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生产部目标技术39某副食品批发店预测某商品今后4月的购进与售出价格如表：

在库存管理中的应用

月份1234成本(购价+库存)2.8售价3.3假设：该商品供不应求，最大销量受仓库容量限制；

正常库容3吨，机动库容2吨；月初批发销货，月中采购进货，进货所需资金完全来销售收入；1月初库存量2吨，成本2.5千元/吨，该月初无现金。某副食品批发店预测某商品今后4月的购进与售出价格如表：在库40经营目标：(1)每月都使用正常库容，尽量不超容；(2)每月下旬都应储备1千元以备急用；(3)4个月总盈利最大。决策变量：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)每月都使用正常库容，尽量不超容；决策变量：x41各月采购量约束：每月采购量依赖月初的售货收入。1月2.6x1

≤2.9y1→–

2.9y1+

2.6x1

≤02月–

2.9y1–2.7y2

+

2.6x1+2.5x2

≤03月–

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目标约束条件正常库容约束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各月采购量约束：每月采购量依赖月初的售货收入。目标约束条件42各月储备金约束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-

各月储备金约束43作业

4.2(1)

4.6

4.7作业

4.2(1)

4.6

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

在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成51多目标线性规划含有多个优化目标的线性规划。线性规划模型只能有一个目标函数，可称为单目标线性规划。多目标线性规划模型具有两个或两个以上的目标函数。多目标线性规划52引例1某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品的技术消耗定额及单位产品的利润如表所示。试确定计划期内的生产计划，使获得的利润最大。

产品资源甲乙现有资源

设备4324单位产品利润

54引例1某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品53解：设x1、x2分别表示甲、乙两种产品的产量，则可建立线规划模型如下：

maxZ=5x1+4x2

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

maxZ1=5x1+4x2

maxZ2=x1minZ3=x24x1+3x2≤24x1，x2≥0 这些目标之间相互矛盾，一般的线性规划方法不能求解

解：设x1、x2分别表示甲、乙两种产品的产量，则可建立线规划54引例2某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见下表产品III资源限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）68引例2产品III资源限量原材料（kg/件）51060设备工时55设产品I和II的产量分别为X1和X2，当用线性规划来描述和解决这个问题时，其数学模型为：其最优解，即最优生产计划为X1=8，X2=2，maxz=64设产品I和II的产量分别为X1和X2，当用线性规划来描述和解56假设计划人员还被要求考虑如下意见：（1）由于产品II销售疲软，故希望产品II的产量不超过产品I的一半。（2）原材料严重短缺，生产中应避免过量消耗。（3）最好能节约4小时设备工时；（4）计划利润不少于48元。面对这些意见，计划人员作出如下意见，首先原材料使用额不得突破；产品II产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。假设计划人员还被要求考虑如下意见：57求解GP的思路加权系数法为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。

优先等级法将各目标按其重要程度分成不同的优先等级，转化为单目标模型。

有效解法寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。求解GP的思路加权系数法58目标规划法加权系数法和优先等级法的结合对每个目标函数确定一个希望达到的期望值(目标值或理想值)；由于各种条件的限制，这些目标值往往不可能全部都达到；对每一个目标函数引入正的或负的偏差变量，分别表示超过或未达到目标值的情况；为区别各目标的重要程度，引入目标的优先等级和加权系数；对所有的目标函数建立约束方程，并入原来的约束条件中，组成新的约束条件；从这组新的约束条件，寻找使组合偏差最小的方案。目标规划法加权系数法和优先等级法的结合59目标函数的期望值每一个目标函数希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。偏差变量每个目标函数的期望值确定之后，目标的实际值和它的期望值之间就有正的或负的偏差。正偏差变量dk+表示第k个目标超过期望值的数值；负偏差变量dk-表示第k个目标未达到期望值的数值。同一目标，它的取值不可能在超过期望值的同时，又没有达到期望值，所以在dk+和dk-中至少有一个必须为零。☀☀目标规划的基本概念

目标函数的期望值☀☀目标规划的基本概念60目标约束引入正、负偏差变量后，对各个目标建立的目标函数方程。原来的目标函数变成了约束条件的一部分，即目标约束(软约束)原来的约束条件称为系统约束(硬约束)。在引例题中，计划人员提出新要求(1)由于产品II销售疲软，故希望产品II的产量不超过产品I的一半。（2）原材料严重短缺，生产中应避免过量消耗。（3）最好能节约4小时设备工时；（4）计划利润不少于48元。

1/2x1>=x2

x1-2x2+d1--d1+=0

4x1+4x2<=40-44x1+4x2+d2--d2+=36

6x1+8x2>=48

6x1+8x2+d3--d3+=48目标约束原来的目标函数变成了约束条件的一部分，即目标约束(61目标达成函数

各个目标函数引入正、负偏差变量，而被列入了目标约束条件。如何使各目标的实际值最接近于各自的期望值，构造一个新的目标函数以求得有关偏差变量的最小值。这个新的目标函数反映了各目标函数的期望值达到或实现的情况，故把这个新的目标函数称为目标达成函数。若要求尽可能达到规定的目标值，则正、负偏差变量dk+、dk-都尽可能最小，将dk+和dk-都列入目标函数中，即minSk=dk++dk-；若希望尽可能不低于期望值(允许超过)，则负偏差变量dk-尽可能的小，而不关心超出量dk+，故只需将dk-列入目标函数，minSk=

dk-；若允许某个目标低于期望值，但希望不得超过期望值，则正偏差变量dk+

尽可能地小，而不关心低于量dk-，故只需将dk+列入目标函数，minSk=

dk+。目标达成函数62优先等级和权数

目标的重要程度不同，用优先等级因子Pk来表示第k等级目标。优先等级因子Pk是正的常数，Pk>>Pk+1。同一优先等级下的目标的相对重要性，赋以不同的加权系数w。例如第一个目标:由于产品II销售疲软，故希望产品II的产量不超过产品I的一半。其优先级为P1；（4）。第二个目标:最好能节约4小时设备工时是其优先级为P2；第三个目标：计划利润不少于48元,优先级为P3。

minZ=P1d1-+P2d2++P3d3-优先等级和权数63所以，引例2的目标规划模型如下：minZ=P1d1-+P2d2++P3d3-5x1+10x2<=60x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48所以，引例2的目标规划模型如下：minZ=P1d1-+64引例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引例1：目标达成函数minZ=P1d1-+P2(d265目标规划的数学模型目标规划的数学模型66课堂练习：电视机厂装配25寸和21寸两种彩电，每台电视机需装备时间1小时，每周装配线计划开动40小时，预计每周25寸彩电销售24台，每台可获利80元，每周21寸彩电销售30台，每台可获利40元。该厂目标：1、充分利用装配线，避免开工不足。2、允许装配线加班，但尽量不超过10小时。3、尽量满足市场需求（产品25寸的两倍重要于21寸的电视机）。课堂练习：该厂目标：67解：设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)解：设X1,X2分别表示25寸，21寸彩电产量minZ68目标规划的解法目标规划的图解法只含有两个决策变量的目标规划模型

线性规划是在可行域中寻找一点，使单个目标极大或极小；目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的折衷方案。目标规划的图解法的思路首先是在可行域内寻找一个使P1级各目标均满足的区域R1；然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2R1)；接着再在R2中寻找一个满足P3级各目标的区域R3(R3R2

R1)；如此继续，直到寻找到一个区域RK(RKRK-1…R3

R2

R1)，满足PK级各目标，这时RK即为这个目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。

目标规划的解法目标规划的图解法69目标规划的图解法的步骤首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。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-+P2d270minZ=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/7minZ=P1d1-+P2(d2-+d2+)+P3(3d371第三节目标规划的单纯形法目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型：将优先等级Pk视为正常数(大Ｍ法)正负偏差变量dk+、dk-视为松弛变量以负偏差变量dk-为初始基变量，建立初始单纯形表检验数的计算与LP单纯形表检验数的计算完全相同，即j=cj–CBB-1Pj最优性判别准则类似于LP的单纯形算法：检验数一般是各优先等级因子的代数和判断检验数的正负和大小第三节目标规划的单纯形法目标规划与线性规划的数学模型的结构72minZ=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+≥0minZ=P1d1-+P2(d2-+d2+)+73cj值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--cjCBXBbx1x2d1-d1+d2-d2+d3-d3+74cj00-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-5P2075cj00-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/7P3cj00-P10-P2-P2-3P20-5P2076极小化线性规划求解方法极小化问题与极大化问题的解法，主要有一点区别，那就是进基变量的选取。由式可知，若以极大化为目标，则当所有非基变量的检验数σj≤0时，Z值达到最大。反之，若以极小化为目标，则当某个非基变量检验数σj＜0时，若取xj＞0，将使Z值进一步变小，即使目标进一步优化；极小化线性规划求解方法极小化问题与极大化问题的解法，主要有一77当所有非基变量检验数σj≥0时，若使任意非基变量xj＞0都会导致目标函数的增加从而偏离了极小化目标，于是可以认定此时的解为最优解。总而言之，极小化问题的判别准则是：σj≥0(j=1，2，…，n)时为最优，进基变量的选取是在负检验数中选取最小的一个σk，它所对应的变量xk为换入变量。当所有非基变量检验数σj≥0时，若使任意非基变量xj＞0都会78举例：举例：79Cj比值CBXBb检验数jx1x2x3x4x51-400033-11006-41010811001x3x4x500001-4000-68填入初始单纯形表Cj比CBXBb检验数jx1x2x3x4x51-4000380Cj比值CBXBb检验数jx1x2x3x4x51-400033-11006-41010811001x3x4x500001-4000-68检验数j9-101006-410102500-11x3x2x50-40-150040--2/5Cj比CBXBb检验数jx1x2x3x4x51-4000381Cj比值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=-30Cj比CBXBb检验数jx1x2x3x4x51-4000982经营目标P1：总利润不低于40，P2：充分利用设备能力，且尽量不超过140如何安排生产？

在目标管理中的应用

产品资源甲乙现有资源设备2010140售价108成本56最大需求量610经营目标在目标管理中的应用产品甲乙现有资源设备2010183x1x2x1=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+≥0x1x2x1=6x2=10③④d1+d1-d2+d2-C84满意解：x1=6,x2=5设备能力：需求：206+105=170，实际：140实现目标P1和P2，降低甲乙产品的设备消耗:降低率(170-140)/170=18%，甲产品的设备消耗降为20(1-18%)=16.4,