运筹学目标规划

1、目标规划Goal Programming1本章主讲内容目标规划问题及其数学模型（重点掌握）求解目标规划的思路目标规划的图解法目标规划的单纯形法2目标规划问题及其数学模型线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题。线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）也不相同，有些目标之间往往相互发生矛盾。线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束

2、条件中的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。3实际决策中，衡量方案优劣考虑多个目标生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、提高质量、提高劳动生产率等；生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求量等经济指标外，还要考虑到污染和其它社会因素等 。这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，LP则无能为力。求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，

3、但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。4无解（或无可行解）：若约束条件相互矛盾，则可行域为空集。例如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 0, x2 0-2x1 + x2 =2x1 -3 x2 =3x2123-1x1123-1S.t.5在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。目标规划（Goal Programming）目标规划可根据实际情况，分主次地、轻重缓急地考虑问题。在LP的基础上

4、发展起来的解决多目标规划问题的最有效的方法之一。美国经济学家查恩斯(A.Charnes)和库柏(W.W.Cooper)在1961年出版的管理模型及线性规划的工业应用一书中，首先提出的。 6多目标线性规划含有多个优化目标的线性规划。线性规划模型只能有一个目标函数，可称为单目标线性规划。多目标线性规划模型具有两个或两个以上的目标函数。7例1某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品的技术消耗定额及单位产品的利润如表所示。试确定计划期内的生产计划，使获得的利润最大。 8解：设x1、x2分别表示甲、乙两种产品的产量，则可建立线规划模型如下： maxZ=5x1+4x2 4x1+3x2 24

5、x1，x2 0假设：该工厂根据市场需求或合同规定，希望尽量扩大甲产品的生产；减少乙产品的产量。这时又增加了二个目标，则可建立如下的模型： maxZ1=5x1+4x2 maxZ2=x1 minZ3=x2 4x1+3x2 24 x1，x2 0这些目标之间相互矛盾，一般的线性规划方法不能求解 9目标规划的基本概念1.优先等级：将各目标按其重要程度分成不同的优先等级。P1P2P32.加权系数：在同一优先级下为每一目标赋一个权系数。3.正负偏差变量对每个目标函数确定一个希望达到的期望值；由于各种条件的限制，这些目标值往往不可能全部都达到；正偏差变量dk+ 表示第k个目标超过期望值的部分；负偏差变量dk-

6、 表示第k个目标不足期望值的部分；4.软约束和硬约束原来的目标函数变成了约束条件的一部分，即软约束（目标约束）原来的约束条件称为硬约束(系统约束)。10例2某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见下表11设产品I和II的产量分别为X1和X2，当用线性规划来描述和解决这个问题时，其数学模型为：其最优解，即最优生产计划为X1=8，X2=2，maxz=6412假设计划人员还被要求考虑如下意见：（1）由于产品II销售疲软，故希望产品II的产量不超过产品I的一半。（2）原材料严重短缺，生产中决不允许超额使用。（3）最

7、好能节约4小时设备工时；（4）计划利润最好不少于48元。面对这些意见，计划人员作出如下意见，首先原材料使用额不得突破；产品II产量要求优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。13所以，引例2的目标规划模型如下：minZ= P1 d1- + P2d2+ + P3d3-5x1+10 x2=60 x1-2x2 +d1- d1+ = 04x1+4x2 +d2- - d2+ = 366x1 +8x2 +d3- - d3+ = 4814对每一个目标函数引入正的或负的偏差变量，分别表示超过或未达到目标值的情况；为区别各目标的重要程度，引入目标的优先等级和加权系数；对所有的目标函数建立约束方程

8、作为软约束，并入原来的硬约束条件中，组成新的约束条件；从这组新的约束条件，寻找使组合偏差最小的方案。目标规划建模思路15例3：管理部门提出新要求：第一个目标是实现利润最大，计划部门规定利润目标是20；第二个目标是充分利用设备台时，但尽量少加班；第三个目标做如下规定，甲产品产量希望不少于3单位，乙产品产量比甲产品至少多2单位。对各目标函数引入正、负偏差变量，则目标约束为： 目标达成函数第一个目标是实现利润最大，其优先级为P1 ；第二个目标是充分利用设备台时，但尽量少加班，其优先级为P2 ；第三个目标：甲的产量不少于3，乙的产量比甲多2，优先级为P3 。 假设：甲产品产量希望不少于3单位的权数为3

9、，乙产品产量比甲产品多2单位的权数为5。 minZ= P1 d1- + P2(d2- + d2+ ) + P3(3d3- +5 d4- )minZ= P1 d1- + P2(d2- + d2+ ) + P3(3d3- +5 d4- ) 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+ = 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ 05x1+4x2 +d1-d1+ = 204x1+3x2 +d2- - d2+ = 24x1 +d3- -d3+ = 3- x1 + x2 +d4-

10、d4+ = 216目标规划的数学模型 17课堂练习：电视机厂装配25寸和21寸两种彩电，每台电视机需装备时间1小时，每周装配线计划开动50小时，预计每周25寸彩电销售24台，每台可获利80元，每周21寸彩电销售30台，每台可获利40元。该厂目标：1、充分利用装配线，避免开工不足。2、允许装配线加班，但尽量不超过10小时。3、尽量满足市场需求（产品25寸的两倍重要于21寸的电视机）。18解：设X1 , X2 分别表示25寸，21寸彩电产量minZ=P1d1-+P2d2+P3(2d3-+d4-)X1+X2 +d1- -d1+=50X1 +X2+d2- -d2+=60X1+d3- -d3+=24X2

11、 +d4- -d4+=30X1 , X2 , di- , di+ 0 (i=1,2,3,4)19目标规划的解法 目标规划的图解法只含有两个决策变量的目标规划模型 线性规划是在可行域中寻找一点，使单个目标极大或极小；目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的折衷方案。目标规划的图解法的思路首先是在可行域内寻找一个使P1级各目标均满足的区域R1；然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2R1)；接着再在R2中寻找一个满足P3级各目标的区域R3(R3 R2 R1)；如此继续，直到寻找到一个区域RK(RK RK-1 R3 R2 R1)，满足PK级各目标，这时RK即为这个

12、目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。 20目标规划的图解法的步骤首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。minZ= P1 d1- + P2d2+ + P3d3-5x1+10 x2=60(1)x1-2x2 +d1- d1+ = 0(2)4x1+4x2 +d2- - d2+ = 36(3)6x1 +8x2 +d3- - d3+ = 48(4)x1x20 1 2 3 4 5 6 7 8 9 10 11 12 131110987654321(1)(2)d1-(4)d3-(3)d2+可行域21minZ=

13、P1d1-+P2d2+P3(2d3-+d4-)X1+X2 +d1- -d1+=50X1 +X2+d2- -d2+=60X1+d3- -d3+=24X2 +d4- -d4+=30X1 , X2 , di- , di+ 0 (i=1,2,3,4)22第三节目标规划的单纯形法 目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型： 将优先等级Pk视为正常数(大法 )正负偏差变量dk+、dk-视为松弛变量以负偏差变量dk-为初始基变量，建立初始单纯形表检验数的计算与LP单纯形表检验数的计算完全相同，即j= cj CBB-1Pj 最优性判别准则类似于LP的单纯形算法：检验数一般是各优

14、先等级因子的代数和判断检验数的正负和大小 23 minZ=P1 d1-+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转为标准型 maxZ=-P1 d1-P2(d2-+d2+)-P3(3d3-+5d4-) 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+ = 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4- - d4+ =

15、 2 x1 , x2 ,dk- , dk+ 02400- P10- P2- P2- 3P20- 5P2020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4- P1- P2- 3P3- 5P3+5 P1 +4 P2 -2 P3+4 P1 +3 P2 +5 P30-P10-2P20-3P30-5P3463-d1-d2-x1d4- P1- P20- 5P331000001-1005041-100-55001203001-1-440050100001-11-10+4 P1 +3 P2 +5 P30-P10-2P2-5 P1 -4

16、 P2 +2 P3+5 P1 +4 P2 -5 P30-5P313-25d3+d2-x1d4-0- P20- 5P3104/51/5-1/500-110080-1/5-4/54/51-10000414/51/5-1/5000000609/51/5-1/500001-1-10-d3+d1+x1d4-000- 5P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-14-832/726x2d1+x1d4-000- 5P3401001/3-1/3-4/34/3001100-114/3-4/3-1/3

17、1/3003100000-110010000-1/31/37/3-7/31-1-3x2d1+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/727经营目标P1：总利润不低于40，P2：充分利用设备能力，且尽量不超过140如何安排生产？ 在目标管理中的应用 28x1x2x1 =6x2 =10d1+d1-d2+d2-CBD(6,5)minZ= P1 d1- + P2 (d2-+d2+ ) x1 6 x2 10 5x1 + 2x2 +d1- -d1+ =40 20 x1 +10 x2 +d2- -d2+ = 140 x1 , x2, d1-, d1+ , d2-,