管理运筹学讲义第5章目标规划

石家庄经济学院管理科学与工程学院1第5章目标规划Subtitle学习要点了解目标规划与线性规划的异同理解目标约束中的正负偏差变量思考目标约束与系统约束的差异理解目标的优先级和目标权系数了解目标规划图解法和单纯形法石家庄经济学院管理科学与工程学院2第一节多目标规划问题一、线性规划的局限性•线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题•实际决策中，衡量方案优劣考虑多个目标生产计划决策，通常考虑产值、利润、满足市场需求等生产布局决策，考虑运费、投资、供应、市场、污染等•这些目标中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性的；有互相补充的，有互相对立的，LP则无能为力。•目标规划（GoalProgramming）：多目标线性规划，含有多个优化目标的线性规划。石家庄经济学院管理科学与工程学院3第一节多目标规划问题二、多目标规划的提出例：甲乙产品的最优生产计划。产品资源甲乙现有资源设备A2016设备B0210设备C3432单位利润35解：线规划模型：maxZ=3x1+5x22x1≤162x2≤103x1+4x2≤32x1，x2≥0•根据市场需求：希望尽量扩大甲产品减少乙产品产量。•又增加二个目标：maxZ1=3x1+5x2maxZ2=x1minZ3=x22x1≤162x2≤103x1+4x2≤32x1，x2≥0这些目标之间相互矛盾，一般的线性规划方法不能求解石家庄经济学院管理科学与工程学院4第一节多目标规划问题二、多目标规划的提出11111221221122221122ln11112211211222221122max(min)max(min)max(min)(,)(,)s.t.nnnnlllnnnnnmmGcxcxcxGcxcxcxGcxcxcxaxaxaxbaxaxaxbaxax12(,),,0mnnmnaxbxxx多目标线性规划模型的原始一般形式如下：n个决策变量，m个约束条件，L个目标函数。当L=1时，即为我们熟悉的单目标线性规划模型。石家庄经济学院管理科学与工程学院5例1某工厂生产Ⅰ、Ⅱ两种产品，已知有关数据见下表。试求获利最大的生产方案。ⅠⅡ拥有量原材料(kg)设备(hr)21121110利润(元/件)810为了具体说明目标规划与线性规划在处理问题方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。第二节目标规划的数学模型石家庄经济学院管理科学与工程学院6解：这是求获利最大的单目标的规划问题，用x1，x2分别表示Ⅰ、Ⅱ产品的产量，其线性规划模型表述为：0,102112108max21212121xxxxxxxxz满足约束条件：目标函数：石家庄经济学院管理科学与工程学院7用图解法求得最优决策方案为：x1*=4,x2*=3,z*=62(元)。(4,3)0,102112108max21212121xxxxxxxxz满足约束条件：目标函数：石家庄经济学院管理科学与工程学院8对于例一，计划人员被要求考虑以下意见：•（1）超过计划供应原材料时，需用高价采购，会使成本大幅度增加。因此，原材料供应受严格限制。•（2）根据市场信息，产品Ⅰ的销售量有下降的趋势，故考虑产品Ⅰ的产量不超过产品Ⅱ的产量。•（3）应尽可能充分利用设备台时。•（4）应尽可能实现利润总额不小于56元。石家庄经济学院管理科学与工程学院9这样在考虑产品决策时，便成为多目标决策问题。目标规划方法是解这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。1.设x1，x2为决策变量，此外，引进正、负偏差变量d+，d-。正偏差变量d＋表示决策值超过目标值的部分；负偏差变量d-表示决策值未达到目标值的部分。石家庄经济学院管理科学与工程学院102.绝对约束和目标约束绝对约束是指必须严格满足的约束条件，不能满足这些约束条件的解称为非可行解，它们是硬约束。石家庄经济学院管理科学与工程学院11目标约束是目标规划特有的，可把约束右端项看作要追求的目标值，在达到此目标值时允许发生偏差，因此是软约束。8x1+10x2+d1--d1+=562x1+x2+d2--d2+=11。石家庄经济学院管理科学与工程学院123.优先因子(优先等级)与权系数一个规划问题常常有若干目标，要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2…，并规定PkPk+1,k=1,2,…，K。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数ωj。石家庄经济学院管理科学与工程学院134.目标规划的目标函数当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是minz=f(d+,d-)。石家庄经济学院管理科学与工程学院14其基本形式有三种：•(1)要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时minz=f(d++d-)•(2)要求不超过目标值，但允许达不到目标值。这时不希望决策值超过目标值。这时minz=f(d+)•(3)要求不低于目标值，但允许超过目标值。这时，不希望决策值低于目标值。这时minz=f(d-)•对每一个具体目标规划问题，可根据决策者的要求和赋予各目标的优先因子来构造目标函数，以下用例子说明。石家庄经济学院管理科学与工程学院15例2例1的决策者在原材料供应受严格限制的基础上考虑：首先是产品Ⅰ的产量不超过产品Ⅱ的产量；其次是充分利用设备有效台时；再次是利润额不小于56元。求决策方案。石家庄经济学院管理科学与工程学院16解按决策者所要求的，分别赋予这三个目标P1，P2，P3优先因子。这问题的数学模型是：3,2,1,0,,,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii满足约束条件：目标函数：石家庄经济学院管理科学与工程学院17目标规划的一般数学模型为1111min()(51),1,,(52)(,),1,,(53)0,1,,(54),0,1,2,3(55)LKllkklkklknkjjkkkjnijjijjkkzPddcxddgkKaxbimxjnddk目标函数：满足约束条件：为权系数。lklk,石家庄经济学院管理科学与工程学院18课堂练习：某公司经销两种货物，售出每吨甲货物可盈利202元，乙货物可盈利175元，各种货物每吨所占用的流动资金为683元，公司现有流动资金1200万元，货物经销中有8.48%的损耗。公司的决策者希望下月能达到以下目标。（1）第一目标：盈利5030000元以上；（2）第二目标：经销甲货物5000吨以上；（3）第三目标：经销乙货物18000吨以上；（4）第四目标：经销损耗在1950吨以下。试问应怎样决策？石家庄经济学院管理科学与工程学院19s.t.44332211mindPdPdPdPZ50300001752021121ddxx5000221ddx18000332ddx19500848.00848.04421ddxx)5,4,3,2,1(0,,,21iddxxii解:设分别表示下月经销甲、乙货物的吨数。21,xx1268368312000000xx石家庄经济学院管理科学与工程学院20•对只具有两个决策变量的目标规划的数学模型，可以用图解法来分析求解。用例2来说明（图5-1)。解为线段GD(G(2,4),D(10/3,10/3))3,2,1,0,,,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii回本章目录第三节目标规划的图解法石家庄经济学院管理科学与工程学院21注意目标规划问题求解时，把绝对约束作最高优先级考虑。在本例中能依先后次序都满足d1+=0，d2++d2-=0，d-3=0，因而z*=0。但在大多数问题中并非如此，会出现某些约束得不到满足，故将目标规划问题的最优解称为满意解。石家庄经济学院管理科学与工程学院22例3某电视机厂装配彩色和黑白两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为：•第一优先级：装配线每周开动时间不低于40小时；•第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时；•第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权系数为2。•试建立这问题的目标规划模型，并求解彩色和黑白电视机的产量。石家庄经济学院管理科学与工程学院23解设x1，x2分别表示彩色和黑白电视机的产量。这个问题的目标规划模型为4,3,2,1,0,,,30245040)2(min21442331222111214332211iddxxddxddxddxxddxxddPdPdPzii满足约束条件：目标函数：石家庄经济学院管理科学与工程学院24用图解法求解，见图5.2石家庄经济学院管理科学与工程学院25从图5.2中看到在考虑具有P1、P2的目标实现后，x1、x2的取值范围为ABCD。考虑P3的目标要求时，因d3—的权系数大于d4—，故先考虑mind3—；这时x1、x2的取值范围缩小为ABEF区域。然后考虑d4—。在ABEF中无法满足d4—=0，因此只能在ABEF中取一点，使d4—尽可能小，这就是E点。故E点为满意解。其坐标为(24，26)，即该厂每周应装配彩色电视机24台，黑白电视机26台。石家庄经济学院管理科学与工程学院26目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定：(1)因目标规划问题的目标函数都是求最小化，因此以j≥0，j=1,2,…，n为最优准则。(2)各非基变量的检验数是各优先因子的线性组合，必须注意P1P2…PK。回本章目录第四节目标规划的单纯形法石家庄经济学院管理科学与工程学院27因P1P2…PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数α1j的正、负。若α1j=0，这时此检验数的正、负就决定于P2的系数α2j的正、负，下面可依此类推。石家庄经济学院管理科学与工程学院28解目标规划问题的单纯形法的计算步骤：•(1)建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行。•(2)检查检验数是否存在负数，若有负数取其中最小者对应的变量为换入变量，转(3)。若无负数，则转(5)。•(3)按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。•(4)按单纯形法进行基变换运算，建立新的计算表，返回(2)。•(5)当所有检验数j≥0时，计算结束。表中的解即为满意解。石家庄经济学院管理科学与工程学院29例4试用单纯形法来求解例2。将例2的数学模型化为标准型：3,2,1,0,,,,561081020112)(min21332122211121213322211iddxxxddxxddxxddxxxxxdPddPdPziiss满足约束条件：目标函数：石家庄经济学院管理科学与工程学院30①取xs，d1-，d2-，d3-为初始基变量，列初始单纯形表，见表5-