XK上海交大运筹学期末考试考研复习珍贵资料适合全国高校考研 和期末【策划稿】

1、 第五章 目标规划第一节 目标规划的数学模型具 体 案 例例1 某工厂生产，两种产品，已知有关数据见下表。试求获利最大的生产方案。解： 这是求获利最大的单目标的规划问题，用x1，x2分别表示，产品的产量，其线性规划模型表述为： 用图解法求得最优决策方案为：x1*=4, x2*=3, z*=62(元)。 (4,3)实际上工厂在作决策时，要考虑市场等一系列其他条件 （1) 根据市场信息，产品的销售量有下降的趋势，故考虑产品的产量不大于产品。(2) 超过计划供应的原材料时，需用高价采购，会使成本大幅度增加。(3) 应尽可能充分利用设备台时，但不希望加班。 (4) 应尽可能达到并超过计划利润指标56元

2、。 这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。 1.设x1，x2为决策变量，此外，引进正、负偏差变量d+，d- 。正偏差变量d表示决策值超过目标值的部分；负偏差变量d-表示决策值未达到目标值的部分。因决策值不可能既超过目标值同时又未达到目标值，即恒有d+d-=0。2.绝对约束和目标约束绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负偏差，因

3、此在这些约束中加入正、负偏差变量，它们是软约束。线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束。如：例1的目标函数z=8x1+10 x2可变换为目标约束8x1+10 x2+d1-d1+=56。约束条件2x1+x211可变换为目标约束2x1+x2+d2-d2+=11。3.优先因子(优先等级)与权系数一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是有主次或轻重缓急的不同。要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2，并规定PkPk+1,k=1,2,，K。表示Pk比Pk+1有更大的优先权。即首先保

4、证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数j,这些都由决策者按具体情况而定。 4.目标规划的目标函数目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是min z=f(d+,d-)。其基本形式有三种： (1) 要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时 min z=f(d+d-)(2) 要求不超过目标值，即允许达不到目标值，就

5、是正偏差变量要尽可能地小。这时min z=f(d+)(3) 要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时min z=f(d-)对每一个具体目标规划问题，可根据决策者的要求和赋予各目标的优先因子来构造目标函数，以下用例子说明。 例2 ： 例1的决策者在原材料供应受严格限制的基础上考虑：首先：产品的产量不低于产品的产量；其次：充分利用设备有效台时，不加班；再次：利润额不小于56元。求决策方案 。解 按决策者所要求的，分别赋予这三个目标P1，P2，P3优先因子。这问题的数学模型是： 目标规划的一般数学模型为 为权系数。 第二节 目标规划的图解法例 某电视机厂装配黑白和彩色两种电

6、视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为：第一优先级：充分利用装配线每周计划开动40小时；第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时；第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权系数为2。试建立这问题的目标规划模型，并求解黑白和彩色电视机的产量。 解 设x1，x2分别表示黑白和彩色电视机的产量。这个问题的目标规划模型为(d)0102030405060102030405060(a)(b)(c)(24, 2

7、6)满足P1, P2的可行域满足P1, P2, P3(c)的可行域目标规划的最优解d1+d2+d4+资源甲乙资源限制设备台时2412材料3312利润（万元/单位）43.2消耗定额产品443363.75212340 x1x2硬约束围成区域内，满足第一等级目标的区域。5满足第一、二等级目标的区域内，能尽可能地满足第三等级目标的区域。这个区域仅包含点(2.4, 1.6 ).满足第一等级目标的区域内，还满足第二等级目标的区域。这个区域是一条线段。例：前面的例2：满意解为线段DG第3节 解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考

8、虑目标规划的数学模型一些特点，作以下规定：(1) 因目标规划问题的目标函数都是求最小化，所以以cj-zj0，j=1,2,，n为最优准则。(2) 因非基变量的检验数中含有不同等级的优先因子，即因P1P2PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数1j的正、负。若1j=0，这时此检验数的正、负就决定于P2的系数2j的正、负，下面可依此类推。 解目标规划问题的单纯形法的计算步骤：(1) 建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1。(2) 检查该行中是否存在负数，且对应的前k-1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转(3)。若无负数，

9、则转(5)。(3) 按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。(4) 按单纯形法进行基变换运算，建立新的计算表，返回(2)。(5) 当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回到(2)。例:试用单纯形法来求解例2。将例2的数学模型化为标准型： 取xs，d1-，d2-，d3-为初始基变量，列初始单纯形表，见表。 取k=1，检查P1行的检验数，因该行无负检验数， 故转(5)。 因k(=1)K(=3)，置k=k+1=2，返回到(2)。 当k=2时,查出P2行检验数中有-1、-2； 取min(-1,-2)=-2。 它对应

10、的变量x2为换入变量，转入(3)。 在表上计算最小比值它对应的变量d2-为换出变量，转入(4) 即进行基变换运算，计算结果见表 返回到(2)，得到最终表最终表所示的解x1*=2，x2*=4为例1的满意解。此解相当于图解中的G点。检查最终表的检验数行，发现非基变量d3+的检验数为0，这表示存在多重解。以非基变量d3+为换入变量，d1-为换出变量，经迭代得到下表。由上表得到解x1*=10/3，x2*=10/3，此解相当于图解中的D点，G、D两点的凸线性组合都是例2的满意解初始单纯形表x1x2x3d1d1+d2d2+d3d3+检验数P11P210122P35681010000基变量x31121100

11、0000d10110110000d210120001100d3568100000011解:最终单纯形表x1x2x3d1d1+d2d2+d3d3+P11P2111P31100000 x3300100221/21/2d1200011331/21/2x24010004/34/31/61/6x12100005/35/31/31/3第4节 灵敏度分析 目标规划的灵敏度分析方法与线性规划相似，只是除分析各项系数的变化外，还有优先因子的变化问题，下面举例说明。 改变目标优先等级的分析。例 已知目标规划问题得到最终表表1。目标函数的优先等级变化为：(1) min z=P1(2d1+3d2+)+P2d4+P3d

12、3-(2) min z= P1d3-+P2(2d1+3d3+)+P3d4+试分析原解有什么变化。表1解 分析(1)，实际是将原目标函数中d4+，d3-的优先因子对换了一下。这时将表1的检验数中的P2、P3和cj行的P2、P3对换即可。这时可见原解仍满足最优解条件 (见表2)。表2分析(2)，将变化了的优先等级直接反映到表1上。再计算检验数，得表3。然后进行迭代（表4，5），直到求得新的满意解（表6）x1*=4，x2*=12为止。表3表4表5表6第5节 应 用 举 例例 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：(1) 不超过年工资总额60000元；(2) 每级的人数不超过定

13、编规定的人数；(3) ，级的升级面尽可能达到现有人数的20%，且无越级提升；(4) 级不足编制的人数可录用新职工，又级的职工中有10%要退休。有关资料汇总于表中，问该领导应如何拟订一个满意的方案。表解 设x1、x2、x3分别表示提升到、级和录用到级的新职工人数。对各目标确定的优先因子为：P1不超过年工资总额60000元；P2每级的人数不超过定编规定的人数；P3、级的升级面尽可能达到现有人数的20%。先分别建立各目标约束。P1:年工资总额不超过60000元 2000(10-100.1+x1)+ 1500(12-x1+x2)+1000(15-x2+x3)+ d1-d1+ =60000P2：每级的人

14、数不超过定编规定的人数：对级有 10(1-0.1)+x1+d2-d2+=12对级有 12-x1+x2+d3-d3+=15对级有 15-x2+x3+d4-d4+=15P3：，级的升级面不大于现有人数的20%，但尽可能多提；对级有 x1+d5-d5+对级有 x2+d6-d6+目标函数：min z=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-)以上目标规划模型可用单纯形法求解，得到多重解。现将这些解汇总于表，这单位的领导再按具体情况，从表中选一个执行方案 表例 已知三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表。有关部门在研究调运方案时依次考虑以下七项目标，规定其相应

15、的优先等级：P1B4是重点保证单位，必须全部满足其需要；P2A3向B1提供的产量不少于100；P3每个销地的供应量不小于其需要量的80%；P4所定调运方案的总运费不超过最小运费调运方案的10%；P5因路段的问题，尽量避免安排将A2的产品往B4；P6给B1和B3的供应率要相同；P7力求总运费最省。试求满意的调运方案。表解 表上作业法求得最小运费的调运方案见表。这时得最小运费为2950元，再根据提出的各项目标的要求建立目标规划的模型。表供应约束（硬约束） x11+x12+x13+x14300 x21+x22+x23+x24200 x31+x32+x33+x34400需求约束：x11+x21+x31+d1-d1+=200 x12+x22+x32+d2-d2+=100 x13+x23+x33+d3-d3+=450P1：x14+x24+x34+d4-d4+=250P2：A3向B1提供的产品量不少于100 x31+d5-d5+=100P3：每个销地的供应量不小于其需要量的80%