目标规划GoalProgramming

1、第四章 目标规划(goal programming)引言:1961美国学者a.charnes和w.cooper首次在管理模型及线性规划的工业应用一书中首次提出目标规划的概念,1965年以后逐渐形成独立分支.目标规划是在线性规划的基楚上,为适应企业经营管理中多目标决策的需要而发展起来的.它是在决策者所规定的若干目标值,及实现目标的先后顺序,并在给定资源条件下,求得偏离目标值最小的方案的一种数学方法.第一节 目标规划产生的背景n教学目的与要求:使学生学会用目标规划的方法建立解决实际问题的数学模型及求解方法.n重点与难点:重点是偏差量及优先因子的概念,难点是建模和求解方法.n教学方法,手段:结合实际

2、问题讲解数学概念,配合图解法理解目标规划的内涵.n思考题,讨论题,作业:本章建模作业及简单的图解法习题.n参考资料:见前言.n学时分配:4学时.目标规划(gp)比线性规划(lp)有如下优点: lp只能处理单目标的优化问题,gp可以统筹兼顾处理多种目标要求; lp立足于可行解上,而gp可在相互矛盾的约束条件中求得满意解; gp的满意解是指,尽可能达到或接近一个或多个目标值; lp的约束条件不分主次,而gp对约束条件可给予轻重缓急 的处理.例1 某工厂在一个计划期内,生产a,b两种产品,有关数据如下:消耗系数 产 品原料a b库存量(吨)甲乙0.4 0.50.2 0.3180100产值(万元/吨)

3、3 2确定一个总产值最大生产方案.解:1000max2002000,1003 . 02 . 01805 . 04 . 023max:,212121212121sxxxxxxxxxxsbaxx求得最优解则数学模型如下的产量表示产品设现在提出新问题:如果消耗系数不变,原料可以补给,求一个总产值为2000万元及a产品产量为400个单位的生产计划,并给出原料的补充方案.问题的特点:决策者提出了两个明确的目标要求,即.400,200021gg这个问题不是极值问题,而是在若干个目标要求及原来的线性约束下,确定能否实现这些目标以及实现这些目标要求的具体条件.为此,引入目标规划的两个重要概念第二节 目标规划的

4、基本概念及数学模型的建立一.基本概念偏差量:. 0,; 0, 0,; 0, 0,:.dddddddd时当实际值与目标值相等且值时而当实际值未达到目标且当实际值超过目标值时约定未达到目标值的差距令超出目标值的差距令. 0,:dddd即至少有一个为零中注意在例1中,根据目标要求a,b的产量为新的由目标要求产生的”目标约束”如下:.,21xx4002000232211121ddxddxx资源现有量与产量间的关系如下:1003 . 02 . 01805 . 04 . 044213321ddxxddxxgp的目标函数如何表示?为达到目标要求的指标值,显然应使 尽可能地小,于是可表为21,dd.)(min

5、21dddf例1的目标规划数学模型为0,1003 . 02 . 01805 . 04 . 0400200023)(min2144213321221112121iiddxxddxxddxxddxddxxdddf由偏差量构成的目标函数目标约束系统约束非负限制2. 优先因子在目标规划中,目标要求在两个以上时,可通过赋予优先权系数表达不同的重要性程度,优先权系数称为优先因子.,1是一个充分大的正数时并且当规定nnppjippppjinji优先因子是一个定性的概念,表示不同的优先级别在数量上不能比较,它不是数.在例1中,如果认为a产品的产量首先要达到目标要求,其次再达到产值的目标要求,则gp的目标函数可

6、表为1221)(mindpdpdf还应注意的是,在同一优先级别中,为区分不同目标要求的重要程度,可在它们前边增加权系数,它们是数字,数越大表明该目标越重要.如.)34()(min4332211dpddpdpdf二.建立数学模型llddnjxllgddxcmibxadwdwpdfgplljnjllljljnjijijlkllllklkkk, 2 , 1, 0, 10, 2 , 1, 2 , 1,),()()(min1111数学模型可表为例2 某工厂生产a,b两种产品,有关数据如下表 产品 消耗系数资源a b生产资源的现有量原料劳动力设备4 107 616 640吨42人小时80台时利润4 9万元

7、/件如果资源可以补充,而且a,b的计划产量分别是4,5.确定一个生产方案,使其依次满足下列目标要求.:;:;:;:4321指标设备利用率不超过最高利润达到最高指标加班时间最少划指标产品的数量不得超过计pppp6 , 10,40104806166194426754)()(min216621552144213321222111544332211iddxxddxxddxxddxxddxxddxddxdpdpdpddpdfii例3 设有一个供销不平衡的运输问题,有关数据如下表: 运价 需方供方供应量 5 8 7需求量 8 6 10 2024321aaa321bbb312111xxx322212xxx3

8、32313xxx312111ccc322212ccc332313ccc制定一个调运方案,满足下列目标要求:.:;5:%;80:;66:;:3151343231的调运量到尽量减少由万吨的调运量不少于到从量的至少满足三家客户需求万元总运费不超过预算额的要求满足重点客户bapbapppbp, 0, 010687850588 . 44 . 666000010)()()()(min332313322212312111333231232221131211771366315533231344322212333121113131221133231377564543322111iiijijijijddxxxxx

9、xxxxxxxxxxxxxxddxddxddxxxddxxxddxxxddxcddxxxddpdpdddpdpddpdf第三节 目标规划的图解法对于两个变量的目标规划问题,可用图解法求出满意解,具体过程如下: 建立直角坐标系,确定单位; 画出各约束条件方程表示的直线,其中画目标约束直线时,不考虑偏差量; 找出偏差量大于零的方向,并用箭头标出; 按目标函数中的优先序,求出目标规划的满意解.例4 图解法求目标规划的满意解. 2 , 1, 0,821025 .621210)()(min21212221112122111iddxxxxddxxddxxdpddpdfii1d1d2d2dab1x2xo00

10、0068. 4628. 0221121ddddxx4 . 00002 . 50221121ddddxxab例5 图解法求目标规划的满意解4 , 10,4040602105 . 1234)(min21442331221112143332211iddxxddxddxddxddxxdpdpdpdpdfii1x2xo1d1d2d2d3d3d4d4dab其余偏差量为零47208740:4221ddxxa其余偏差量为零20206060:4321ddxxb第四节 目标规划的单纯形解法 (只介绍整体判据法)例6 用单纯形法求解目标规划3 . 2 , 10,3002404002)(min213322211121

11、13322211iddxxddxddxddxxdpdpdpdpdfii4002403001 1 1 -1 0 0 0 01 0 0 0 1 -1 0 00 1 0 0 0 0 1 -108404000 0 0 -1 0 0 0 01 2 0 0 0 -1 0 -21 1 0 -1 0 0 0 0321ddd123ppp33221121ddddddxx.,3001300,1400min32出基入基dx1002403001 0 1 -1 0 0 -1 11 0 0 0 1 -1 0 00 1 0 0 0 0 1 -102401000 0 0 -1 0 0 0 01 0 0 0 0 -1 -2 01 0 0 -1 0 0 -1 1221xdd123ppp33221121ddddddxx.,1001240,1100min11出基入基dx1001403001 0 1 -1 0 0 -1 10 0 -1 1 1 -1 1 -10 1 0 0 0 0 1 -1024000 0 0 -1 0 0 0 00 0 -1 1 0 -1 -1 -10 0 -1 0 0 0 0 0221xdx123ppp33221121ddddddxx.,. 2;,. 12121出基入基进行优化对优化完毕ddpp2401403001 0 0 0 1 -1 0 00 0 -1 1 1 -1 1 -10 1