(ppt)第5章 目标规划.ppt

一、问题的提出与目标规划的数学模型 例1、（背景材料）常山机器厂基本生产资料如下： 该厂过去一直以如何计划两种产品的生产量才能获得最大总利润为其生产、经营的唯一目标。然而，市场经济环境下新的问题出现了，它迫使该厂老板不得不考虑…... （1）力求使利润指标不低于15元； （2）考虑到市场需求，I，II两种产品的生产量需保持 1：2的比例； （3） A为贵重设备，严格禁止超时使用； （4）设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，又在重要性上设备B是设备C的3倍。 基本概念：1、目标值和偏差变量 3、优先因子（优先等级）与优先权系数 4、达成函数（即目标规划中的目标函数） 例1、分析： 二、目标规划的图解法 四、目标规划的单纯形法 （一） 单纯形法的计算步骤 例4：用单纯形法求解下列目标规划问题 小结 目标规划与线性规划的比较 练习1： 练习3：用图解法求解下列目标规划问题 练习4、用单纯形法求解下列目标规划问题 作业 x1 x2 0 4 6 8 10 2 1 3 4 2 x1+2x2+d1- = 10 d1- = 7 5 d1- A B (2,2) 有无穷多解：点（1，1）和点（0，3/2） （3，0）连线上的点都是最优解。 (0,3) (4,0) (1,1) x1 x2 0 4 6 8 10 2 1 3 4 2 5 A B (2,2) 有无穷多解：凸多边形区域内的点都是最优解。 (0,3) (4,0) d1- 例3、用图解法求解例1中的目标规划模型 目标约束 刚性约束 x2 x1 因为EF上的点都不能使 故 F 点为最优解。 故需对 E 点和 F 点进行比较。 E (1.875 , 3.75) ： F (2 , 4) ： 目标规划的模型实际上是求 min 型的线性规划，因此，也可以用单纯形法求解。 在采用单纯形法求解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，关键是要注意到优先因子的级别。当检验数按优先级别从高到低已满足最优性条件时，且无法进一步优化时，从单纯形表上就可以得到目标规划的最优解或满意解。 1、建立初始单纯形表 一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部 。 2、确定换入基变量 在Pk行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量xs就是换入基变量。若Pk行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为换入变量。 3、确定换出基变量 其方法同线性规划，即依据最小比值法则 故确定xr为换出基变量，ers为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为xr 。 4、用换入基变量替换基变量中的换出基变量，然后施行行初等变换。 5、重复以上第2步至第4步的运算，直到找到最优解（满意解）。 ★ 判断的标准： P2 P1 σkj －1 1 0 0 0 0 2 3 100 P2 0 0 －1 1 0 0 1 2 40 0 0 0 0 0 －1 1 0 1 10 P1 x2 x1 b XB CB 0 P2 P1 0 0 P1 0 0 Cj 1 0 0 0 0 0 －2 －3 P2 0 0 1 0 1 0 0 －1 P1 σkj －1 1 0 0 0 0 2 3 100 P2 0 0 －1 1 0 0 1 2 40 0 0 0 0 0 －1 1 0 1 10 P1 x2 x1 b XB CB 0 P2 P1 0 0 P1 0 0 Cj θ= min｛10,20,100/3｝= 10,故 为换出变量。 为换入基变量 1 0 0 0 －3 3 －2 0 P2 0 0 1 0 0 1 0 0 P1 σkj －1 1 0 0 3 －3 2 0 70 P2 0 0 －1 1 2 －2 1 0 20 0 0 0 0 0 －1 1 0 1 10 x1 0 x2 x1 b XB CB 0 P2 P1 0 0 P1 0 0 Cj θ= min｛—,10,70/3｝= 10,故 为换出变量。 1 0 -3/2 0 0 0 -1/2 0 P2 0 0 1 0 0 1 0 0 P1 σkj －1 1 3/2 -3/2 0 0 1/2 0 40 P2 0 0 -1/2 1/2 1 －1 1/2 0 10 0 0 0 -1/2 1/2 0 0 1/2 1 20 x1 0 x2 x1 b XB CB 0 P2