2019/1/17,1,运筹学总复习,主讲：陆际恩 Tel：13592990256 Email：lujien163.com,运筹帷幄之中 决胜千里之外,第四、五章,2019/1/17,2,第四章 目标规划,本章学习要求,掌握目标规划的图解法求解模型,掌握目标规划的单纯形法的求解模型。,主要概念及算法,1、目标函数,多目标的情况下，要用偏差变量限定成目标约束。,多目标的重要程度不同，用优先因子Pi可以认为是一个大的常数，计算不同目标的优先顺序，确定P1P2P3Pn。,2019/1/17,3,将所有的目标偏差总和在一起，组成一个新的目标函数，求极小。,难点：在进行目标约束的转换过程中，要有较好的应用题分析能力，或者说是语文逻辑分析能力。,即，当目标要求准确完成时，使,当目标允许超额完成（如利润、产值）时，使,2019/1/17,4,当目标允许不完成（如能源、原材料）时，使,2、约束条件,当把目标函数变成目标约束时，有,当把原问题中的资源约束标准化后，有,上述两式就是目标规划中的约束方程。,2019/1/17,5,3、模型,列出全部约束条件。,4、建模步骤,把要达到的约束不等式加上正、负偏差变量后，化为目标约束等式。,2019/1/17,6,对目标赋予相应的优先因子。,对同一级优先因子中的各偏差变量，若重要程度不同时，可赋予不同（根据题意）的加权系数。,构造一个按优先因子及加权系数和对应的目标偏差量所要实现最小化的目标函数。,5、解目标规划的单纯形法,目标规划的数学模型结构与线性规划的数学模型结构没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型的一些特点，故有以下规定：,因目标规划问题的目标函数都是求最小化，所以，以j=cj-zj0（j=1，2，n）为最优准则。,2019/1/17,7,因非基变量的检验数中含有不同等级的优先因子，即：cj-zj=akjPk，（j=1,2,n k=1,2,K）,因P1P2Pk；从每一个检验数的整体来看，检验数的正负首先决定于P1的系数a1j的正负；若a1j=0，这时此检验数的正负就决定于P2的系数a2j的正负，下面可依此类推。,解目标规划问题的单纯形法的计算步骤：,建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1；,检验该行中是否存在负数，且对应的前k-1行的系数是零。若有负数，取其中最小者对应的变量为换入变量，转步骤，若无负数，则转步骤。,2019/1/17,8,按最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高级别的变量为换出变量。,按单纯形法进行基变换运算，建立新的计算表，返回步骤。,当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回步骤。,2019/1/17,9,第四章复习思考题,1、试述目标规划的数学模型同一般线性规划数学模型异同。,两种类型的数学模型都有目标函数；,目标规划与一般线性规划问题数学模型的共同点：,两种类型的数学模型都有约束条件；,两种类型的数学模型其决策变量都要求是连续的；,两种类型的数学模型的右端常数项都要求非负；,2019/1/17,10,LP问题的目标函数是求最大化，而目标规划的目标函数是求极小化；,目标规划与一般线性规划问题数学模型的不同点：,LP问题的约束条件都是绝对约束，目标规划的约束条件既有目标约束，有时同时存在绝对约束。,目标规划的目标函数是按各目标约束的正、负偏差变量和赋予相应的优先因子及系数而构造，而LP问题的目标函数是按一个单一目标（即利润最大）构造。,2、解释下列概念,什么是正负偏差变量；什么是绝对约束和目标约束；什么是优先因子与权系数。,LP问题没有优先因子和权系数，而IP中有这两个。,2019/1/17,11,偏差变量,用来表示实际值与目标值之间的差异。,d + 超出目标的差值，称为正偏差变量。,d - 未达到目标的差值，称为负偏差变量。,因实际决策值不可能既超过目标值又低于目标值，故最终结果中恒有 d + d - =0 (即两者至少有一个为0)。,目标规划中，一般有多个目标值，每个目标值都相应有一对偏差变量 。,绝对约束和目标约束,绝对约束是指必须严格满足的等式约束或不等式约束；如线性规划问题的所有约束条件，不能满足这些条件的解称为非可行解，所以绝对约束是硬约束。,2019/1/17,12,目标约束是目标规划所特有的一种约束，它把要追求的目标值作为右端常数项，在追求此目标值时允许发生正偏差和负偏差。因此，目标约束是由决策变量，正、负偏差变量和要追求的目标值组成的软约束。,目标约束不会不满足，但可能偏差过大。,优先因子和权系数,目标规划中，当决策者要求实现多个目标时，这些目标之间是有主次区别的。,2019/1/17,13,凡要求第一位达到的目标，赋于优先因子 p1，要求第二位达到的目标，赋于优先因子 p2 并规定 pk+1pk，表示 pk 比 pk+1 有绝对优先权。因此，不同的优先因子代表着不同的优先等级。,若要区别具有相同优先因子的多个目标，可分别赋予它们不同的权系数 k 。越重要的目标，其权系数的值越大。,在实现多个目标时，首先保证 p1 级目标的实现，这时可不考虑其它级目标，而 p2 级目标是在保证 p1 级目标值不变的前提下考虑的，以此类推。,2019/1/17,14,3、为什么求解目标规划时要提出满意解的概念，它同最优解有什么区别。,因为在目标规划求解时，首先保证上级目标的实现，这时可不考虑其它级目标，而下级目标是在保证上级目标值不变的前提下考虑的，在大多数情况下，上级目标实现了，但下级目标的某些约束得不到满足，但这已经是保证上级目标得以实现的最满意结果，故称这一结果为满足解。实际上，目标规划的满意解就是目标规划问题的最优解。,2019/1/17,15,4、试述求解目标规划的单纯形法与求解线性规划的单纯形的相同点和不同点。,解目标规划问题的单纯形法的计算步骤：,建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1；,检验该行中是否存在负数，且对应的前k-1行的系数是零。若有负数，取其中最小者对应的变量为换入变量，转步骤，若无负数，则转步骤。,按最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高级别的变量为换出变量。,2019/1/17,16,按单纯形法进行基变换运算，建立新的计算表，返回步骤。,当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回步骤。,解线性规划问题的单纯形法的计算步骤：,建立初始单纯形表，计算出所有变量的检验数。,在非基变量检验数中找到最大的正数 j，它所对应的 变量 xj 作为换入基的变量。,对于所有 aij 0 计算 bi /aij ，其中最小的元素 所对 应的基变量 xi 作为换出基的变量。,建立新单纯形表，重复上述步骤、，直到所有 检验数都小于等于零。,2019/1/17,17,5、判断下列说法是否正确,线性规划问题是目标规划问题的一种特殊形式；,正偏差变量应取正值，负偏差变量应负值；,目标规划模型中，应同时包含系统约束（绝对约束）与目标约束；,当目标规划问题模型中存在x1+x2+d-=4的约束条件，则该约束为系统约束。,目标规划模型中，应同时包含系统约束（绝对约束）与目标约束；,2019/1/17,18,第五章 整数规划,本章学习要求,熟悉分支定界法和割平面法的原理及其应用；,掌握求解0-1规划问题的隐枚举法；,主要概念及算法,1、求解整数规划的常用方法,掌握求解指派问题的匈牙利法。,分支定界法：设有最大化的整数规划问题A，与它相应的线性规划问题为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作 ，而A的任意可行解的目,2019/1/17,19,标函数值将是 的一个下界 ，分支定界法就是将B的可行域分成子区域的方法，逐步缩小 和增大 ，最终求得 。,用分支定界法求解最大化整数规划问题的步骤如下：,解与整数规划问题A相应的线性规划问题B，可能得到以下几种情况之一：,a）B没有可行解，A也没有可行解，停止计算。,b）B有可行解，并符合问题A的整数条件，则此最优解为A的最优解，停止计算。,c）B有可行解，但不符合问题A的整数条件，把它的目标函数记为,2019/1/17,20,用观察法找问题A的一个整数可行解，求得其目标函数值，并记作 ，以 表示问题A的最优目标函数值，则 。,然后进行迭代：,a）分支，在B的最优解中选取一个不符合整数条件的变量xj，其值为bj。,2019/1/17,21,将这两个约束条件分别加入问题B，求两个后继规划问题B1和B2。不考虑整数整数约束条件求解这两个后继问题,b）定界，以每个后继问题为一分支标明求解的结果。,第一步：先不考虑整数约束，变成一般的线性规划问题，用图解法或单纯形法求解其最优解X(0)*；,第二步：若求得的最优解X(0)*,刚好就是整数解，则该整数就是原整数规划的最优解，否则转下步；,第三步：对原问题进行分支寻求整数最优解。,选取非整数解 的一个非整数分量 ，其小数部分为 ，以该非整数部分的相邻整数 和 的为边界将原问题分支为两个子问题，并抛弃这两个整数之间的非整数区域；,2019/1/17,22,i）在原线性规划模型中添加分支约束 ，构成第一个子问题。,ii）在原线性规划模型中添加分支约束 ，构成第二个子问题。,第四步：对上面两个子问题按照线性规划方法求最优解。若某个子问题的解是整数解，则停止该子问题的分支，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍；否则，对该子问题继续进行分支。,第五步：重复第三、四步直到获得原问题最优整数解为止。,2019/1/17,23,割平面法：分支定界法是对原问题可行解域进行切割，但子问题却由于分支的增多而呈指数增长。为了克服这个缺点，割平面法采用另一种分割可行解域的办法，既要切割掉非整数解域，又不希望对问题进行分支。步骤如下：,第一步：先不考虑整数约束，变成一般的线性规划规划问题，用单纯形法求其最优解，记为,第二步：若求得的最优解 刚好就是整数解，则该整数解就是原整数规划的最优解；否则，转下步。,第三步：寻求附加约束，即割平面方程,从最优化表中抄下非整数解的约束方程。,2019/1/17,24,其中bi是基变量xi的非整数解。,将该约束方程所有系数和常数分解为整数N和正真分数之和。,将整数项写于方程左边，真分数项写于右边。,考虑整数条件约束。以上方程左边为整数，右边的内是正数。所以方程右边必是非正数。即：,2019/1/17,25,上述就是所求的割平面方程。,第四步：引入松弛变量xi,k+1,将割平面方程规范化,将规范化后的割平面方程最后一个单纯形表,然后用对偶单纯形法解之。,2、01规划与隐枚举法,01规划的概念,决策变量只取0，1两个数的整数规划，1，0表示方案的取舍。,隐枚举法,不需要列出所有组合，只需关心目标函数值的最优可,2019/1/17,26,行组合，按目标值从优到劣依次列出组合，逐个检验其可行性；最先满足所有约束条件的组合为最优解，劣于最优解的组合即使可行，也不列出检验而舍去。用隐枚举法求解01规划的步骤如下：,第一步：变换目标函数和约束方程组。,按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解有可能较早出现。如本章的例11。,第二步：用目标函数值探索法求最优解。,以z的最大值为上界逐步向上搜索，直至获得可行解，此即为最优解。,2019/1/17,27,3、指派问题和匈牙利法,指派问题的特点,把m项工作指派给n个人去做，既发挥各人特长又使效率最高。这是一类特殊的01规划