《理学第三运筹学总复习.pptx》由会员分享，可在线阅读，更多相关《理学第三运筹学总复习.pptx（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、际恩陆2023/2/231第四章第四章 目标规划目标规划本章学习要求本章学习要求 掌握目标规划的图解法求解模型掌握目标规划的单纯形法的求解模型。主要概念及算法主要概念及算法1 1、目标函数、目标函数多目标的情况下，要用偏差变量限定成目标约束。多目标的情况下，要用偏差变量限定成目标约束。多目标的重要程度不同，用优先因子多目标的重要程度不同，用优先因子P Pi i可以认为是一可以认为是一个大的常数，计算不同目标的优先顺序，确定个大的常数，计算不同目标的优先顺序，确定P P1 1P P2 2P P3 3P Pn n。第1页/共41页际恩陆2023/2/232 将所有的目标偏差总和在一起，组成一个新的
2、目标函将所有的目标偏差总和在一起，组成一个新的目标函数，求极小。数，求极小。难点：在进行目标约束的转换过程中，要有较好的应用难点：在进行目标约束的转换过程中，要有较好的应用题分析能力，或者说是语文逻辑分析能力。题分析能力，或者说是语文逻辑分析能力。即，当目标要求准确完成时，使即，当目标要求准确完成时，使 当目标允许超额完成（如利润、产值）时，使当目标允许超额完成（如利润、产值）时，使第2页/共41页际恩陆2023/2/233 当目标允许不完成（如能源、原材料）时，使当目标允许不完成（如能源、原材料）时，使2 2、约束条件、约束条件当把目标函数变成目标约束时，有当把目标函数变成目标约束时，有当把
3、原问题中的资源约束标准化后，有当把原问题中的资源约束标准化后，有上述两式就是目标规划中的约束方程。上述两式就是目标规划中的约束方程。第3页/共41页际恩陆2023/2/2343 3、模型、模型列出全部约束条件。列出全部约束条件。4 4、建模步骤、建模步骤 把要达到的约束不等式加上正、负偏差变量后，化把要达到的约束不等式加上正、负偏差变量后，化为目标约束等式。为目标约束等式。第4页/共41页际恩陆2023/2/235对目标赋予相应的优先因子。对目标赋予相应的优先因子。对同一级优先因子中的各偏差变量，若重要程度不对同一级优先因子中的各偏差变量，若重要程度不同时，可赋予不同（根据题意）的加权系数。同
4、时，可赋予不同（根据题意）的加权系数。构造一个按优先因子及加权系数和对应的目标偏差构造一个按优先因子及加权系数和对应的目标偏差量所要实现最小化的目标函数。量所要实现最小化的目标函数。5 5、解目标规划的单纯形法、解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构目标规划的数学模型结构与线性规划的数学模型结构没有本质的区别，所以可用单纯形法求解。但要考虑目标没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型的一些特点，故有以下规定：规划的数学模型的一些特点，故有以下规定：因目标规划问题的目标函数都是求最小化，所以，因目标规划问题的目标函数都是求最小化，所以，以以j
5、 j=c=cj j-z-zj j00（j=1j=1，2 2，n n）为最优准则。）为最优准则。第5页/共41页际恩陆2023/2/236 因非基变量的检验数中含有不同等级的优先因子，因非基变量的检验数中含有不同等级的优先因子，即：即：c cj j-z-zj j=a=akjkjP Pk k，（，（j=1,2,n k=1,2,Kj=1,2,n k=1,2,K）因因P P1 1P P2 2P Pk k；从每一个检验数的整体来看，检验；从每一个检验数的整体来看，检验数的正负首先决定于数的正负首先决定于P P1 1的系数的系数a a1j1j的正负；若的正负；若a a1j1j=0=0，这时此，这时此检验数
6、的正负就决定于检验数的正负就决定于P P2 2的系数的系数a a2j2j的正负，下面可依此类的正负，下面可依此类推。推。解目标规划问题的单纯形法的计算步骤：解目标规划问题的单纯形法的计算步骤：建立初始单纯形表，在表中将检验数行按优先因子建立初始单纯形表，在表中将检验数行按优先因子个数分别列成个数分别列成K K行，置行，置k=1k=1；检验该行中是否存在负数，且对应的前检验该行中是否存在负数，且对应的前k-1k-1行的系数行的系数是零。若有负数，取其中最小者对应的变量为换入变量，是零。若有负数，取其中最小者对应的变量为换入变量，转步骤转步骤，若无负数，则转步骤，若无负数，则转步骤。第6页/共41
7、页际恩陆2023/2/237 按最小比值规则确定换出变量，当存在两个或两个按最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高级别的变量为换出以上相同的最小比值时，选取具有较高级别的变量为换出变量。变量。按单纯形法进行基变换运算，建立新的计算表，返按单纯形法进行基变换运算，建立新的计算表，返回步骤回步骤。当当k=Kk=K时，计算结束。表中的解即为满意解。否则置时，计算结束。表中的解即为满意解。否则置k=k+1k=k+1，返回步骤，返回步骤。第7页/共41页际恩陆2023/2/238第四章复习思考题 1 1、试述目标规划的数学模型同一般线性规、试述目标规划的数学模型同一
8、般线性规划数学模型异同。划数学模型异同。两种类型的数学模型都有目标函数；两种类型的数学模型都有目标函数；目标规划与一般线性规划问题数学模型的共同点：目标规划与一般线性规划问题数学模型的共同点：两种类型的数学模型都有约束条件；两种类型的数学模型都有约束条件；两种类型的数学模型其决策变量都要求是连续的；两种类型的数学模型其决策变量都要求是连续的；两种类型的数学模型的右端常数项都要求非负；两种类型的数学模型的右端常数项都要求非负；第8页/共41页际恩陆2023/2/239 LP问题的目标函数是求最大化，而目标规划的目问题的目标函数是求最大化，而目标规划的目标函数是求极小化；标函数是求极小化；目标规划
9、与一般线性规划问题数学模型的不同点：目标规划与一般线性规划问题数学模型的不同点：LP问题的约束条件都是绝对约束，目标规划的约问题的约束条件都是绝对约束，目标规划的约束条件既有目标约束，有时同时存在绝对约束。束条件既有目标约束，有时同时存在绝对约束。目标规划的目标函数是按各目标约束的正、负偏差目标规划的目标函数是按各目标约束的正、负偏差变量和赋予相应的优先因子及系数而构造，而变量和赋予相应的优先因子及系数而构造，而LP问题的问题的目标函数是按一个单一目标（即利润最大）构造。目标函数是按一个单一目标（即利润最大）构造。2 2、解释下列概念、解释下列概念 什么是正负偏差变量；什么是正负偏差变量；什么
10、是绝对约束和目标约什么是绝对约束和目标约束；束；什么是优先因子与权系数。什么是优先因子与权系数。LP问题没有优先因子和权系数，而问题没有优先因子和权系数，而IP中有这两个。中有这两个。第9页/共41页际恩陆2023/2/2310 偏差变量偏差变量 用来表示实际值与目标值之间的差异。用来表示实际值与目标值之间的差异。d+超出目标的差值，称为超出目标的差值，称为正偏差变量正偏差变量。d-未达到目标的差值，称为未达到目标的差值，称为负偏差变量负偏差变量。因实际决策值不可能既超过目标值又低于目标值，故最因实际决策值不可能既超过目标值又低于目标值，故最终结果中恒有终结果中恒有 d+d-=0(即两者至少有
11、一个为即两者至少有一个为0)。目标规划中，一般有多个目标值，每个目标值都相应目标规划中，一般有多个目标值，每个目标值都相应有一对偏差变量有一对偏差变量。绝对约束和目标约束绝对约束和目标约束 绝对约束绝对约束是指必须严格满足的等式约束或不等式约束；是指必须严格满足的等式约束或不等式约束；如线性规划问题的所有约束条件，不能满足这些条件的解称如线性规划问题的所有约束条件，不能满足这些条件的解称为非可行解，所以绝对约束是为非可行解，所以绝对约束是硬约束硬约束。第10页/共41页际恩陆2023/2/2311 目标约束目标约束是目标规划所特有的一种约束，它把要追求是目标规划所特有的一种约束，它把要追求的目
12、标值作为右端常数项，在追求此目标值时允许发生正的目标值作为右端常数项，在追求此目标值时允许发生正偏差和负偏差。因此，目标约束是由决策变量，正、负偏偏差和负偏差。因此，目标约束是由决策变量，正、负偏差变量和要追求的目标值组成的差变量和要追求的目标值组成的软约束软约束。目标约束不会不满足，但可能偏差过大目标约束不会不满足，但可能偏差过大。优先因子和权系数优先因子和权系数 目标规划中，当决策者要求实现多个目标时，这些目目标规划中，当决策者要求实现多个目标时，这些目标之间是有主次区别的。标之间是有主次区别的。第11页/共41页际恩陆2023/2/2312 凡要求第一位达到的目标，赋于凡要求第一位达到的
13、目标，赋于优先因子优先因子 p1，要求，要求第二位达到的目标，赋于优先因子第二位达到的目标，赋于优先因子 p2 并规定并规定 pk+1pk，表示，表示 pk 比比 pk+1 有绝对优先权。因此，不同的优先因子有绝对优先权。因此，不同的优先因子代表着不同的优先等级。代表着不同的优先等级。若要区别具有相同优先因子的多个目标，可分别赋予若要区别具有相同优先因子的多个目标，可分别赋予它们不同的它们不同的权系数权系数 k。越重要的目标，其权系数的值越大。越重要的目标，其权系数的值越大。在实现多个目标时，首先保证在实现多个目标时，首先保证 p1 级目标的实现，这时级目标的实现，这时可不考虑其它级目标，而可
14、不考虑其它级目标，而 p2 级目标是在保证级目标是在保证 p1 级目标值级目标值不变的前提下考虑的，以此类推。不变的前提下考虑的，以此类推。第12页/共41页际恩陆2023/2/2313 3 3、为什么求解目标规划时要提出满意解的、为什么求解目标规划时要提出满意解的概念，它同最优解有什么区别。概念，它同最优解有什么区别。因为在目标规划求解时，因为在目标规划求解时，首先保证上级目标的实现，首先保证上级目标的实现，这时可不考虑其它级目标，而下级目标是在保证上级目标这时可不考虑其它级目标，而下级目标是在保证上级目标值不变的前提下考虑的，在大多数情况下，上级目标实现值不变的前提下考虑的，在大多数情况下
15、，上级目标实现了，但下级目标的某些约束得不到满足，但这已经是保证了，但下级目标的某些约束得不到满足，但这已经是保证上级目标得以实现的最满意结果，故称这一结果为满足解。上级目标得以实现的最满意结果，故称这一结果为满足解。实际上，目标规划的满意解就是目标规划问题的最优解。实际上，目标规划的满意解就是目标规划问题的最优解。第13页/共41页际恩陆2023/2/2314 4 4、试述求解目标规划的单纯形法与求解线、试述求解目标规划的单纯形法与求解线性规划的单纯形的相同点和不同点。性规划的单纯形的相同点和不同点。解目标规划问题的单纯形法的计算步骤：解目标规划问题的单纯形法的计算步骤：建立初始单纯形表，在
16、表中将检验数行按优先因子建立初始单纯形表，在表中将检验数行按优先因子个数分别列成个数分别列成K K行，置行，置k=1k=1；检验该行中是否存在负数，且对应的前检验该行中是否存在负数，且对应的前k-1k-1行的系数行的系数是零。若有负数，取其中最小者对应的变量为换入变量，是零。若有负数，取其中最小者对应的变量为换入变量，转步骤转步骤，若无负数，则转步骤，若无负数，则转步骤。按最小比值规则确定换出变量，当存在两个或两个按最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高级别的变量为换出以上相同的最小比值时，选取具有较高级别的变量为换出变量。变量。第14页/共41页际恩陆2
17、023/2/2315 按单纯形法进行基变换运算，建立新的计算表，返按单纯形法进行基变换运算，建立新的计算表，返回步骤回步骤。当当k=Kk=K时，计算结束。表中的解即为满意解。否则置时，计算结束。表中的解即为满意解。否则置k=k+1k=k+1，返回步骤，返回步骤。解线性规划问题的单纯形法的计算步骤：解线性规划问题的单纯形法的计算步骤：建立初始单纯形表，计算出所有变量的检验数。建立初始单纯形表，计算出所有变量的检验数。在非基变量检验数中找到最大的正数在非基变量检验数中找到最大的正数 j，它所对应的，它所对应的变量变量 xj 作为换入基的变量。作为换入基的变量。对于所有对于所有 aij 0 计算计算
18、 bi/aij，其中最小的元素，其中最小的元素 所对所对应的基变量应的基变量 xi 作为换出基的变量。作为换出基的变量。建立新单纯形表，重复上述步骤建立新单纯形表，重复上述步骤、，直到所有，直到所有检验数都小于等于零。检验数都小于等于零。第15页/共41页际恩陆2023/2/2316 5 5、判断下列说法是否正确、判断下列说法是否正确 线性规划问题是目标规划问题的一种特殊形式；线性规划问题是目标规划问题的一种特殊形式；正偏差变量应取正值，负偏差变量应负值；正偏差变量应取正值，负偏差变量应负值；目标规划模型中，应同时包含系统约束（绝对约束）目标规划模型中，应同时包含系统约束（绝对约束）与目标约束
19、；与目标约束；当目标规划问题模型中存在当目标规划问题模型中存在x x1 1+x+x2 2+d-=4+d-=4的约束条件，的约束条件，则该约束为系统约束。则该约束为系统约束。目标规划模型中，应同时包含系统约束（绝对约束）目标规划模型中，应同时包含系统约束（绝对约束）与目标约束；与目标约束；第16页/共41页际恩陆2023/2/2317第五章第五章 整数规划整数规划本章学习要求本章学习要求 熟悉分支定界法和割平面法的原理及其应用；掌握求解0-1规划问题的隐枚举法；主要概念及算法主要概念及算法1 1、求解整数规划的常用方法、求解整数规划的常用方法掌握求解指派问题的匈牙利法。分支定界法：分支定界法：设
20、有最大化的整数规划问题设有最大化的整数规划问题A A，与它，与它相应的线性规划问题为问题相应的线性规划问题为问题B B，从解问题，从解问题B B开始，若其最优开始，若其最优解不符合解不符合A A的整数条件，那么的整数条件，那么B B的最优目标函数必是的最优目标函数必是A A的最的最优目标函数优目标函数z z*的上界，记作的上界，记作 ，而，而A A的任意可行解的目的任意可行解的目第17页/共41页际恩陆2023/2/2318标函数值将是标函数值将是 的一个下界的一个下界 ，分支定界法就是将，分支定界法就是将B B的的可行域分成子区域的方法，逐步缩小可行域分成子区域的方法，逐步缩小 和增大和增大
21、 ，最，最终求得终求得 。用分支定界法求解最大化整数规划问题的步骤如下：用分支定界法求解最大化整数规划问题的步骤如下：解与整数规划问题解与整数规划问题A A相应的线性规划问题相应的线性规划问题B B，可能得，可能得到以下几种情况之一：到以下几种情况之一：a a）B B没有可行解，没有可行解，A A也没有可行解，停止计算。也没有可行解，停止计算。b b）B B有可行解，并符合问题有可行解，并符合问题A A的整数条件，则此最优解的整数条件，则此最优解为为A A的最优解，停止计算。的最优解，停止计算。c c）B B有可行解，但不符合问题有可行解，但不符合问题A A的整数条件，把它的目的整数条件，把它
22、的目标函数记为标函数记为第18页/共41页际恩陆2023/2/2319 用观察法找问题用观察法找问题A A的一个整数可行解，求得其目标函的一个整数可行解，求得其目标函数值，并记作数值，并记作 ，以，以 表示问题表示问题A A的最优目标函数值，的最优目标函数值，则则 。然后进行迭代：然后进行迭代：a a）分支，在）分支，在B B的最优解中选取一个不符合整数条件的的最优解中选取一个不符合整数条件的变量变量x xj j，其值为，其值为b bj j。构造两个约束条件：构造两个约束条件：其中其中 为不超过为不超过 的最大整数。的最大整数。第19页/共41页际恩陆2023/2/2320 将这两个约束条件分
23、别加入问题将这两个约束条件分别加入问题B B，求两个后继规划问，求两个后继规划问题题B1B1和和B2B2。不考虑整数整数约束条件求解这两个后继问题。不考虑整数整数约束条件求解这两个后继问题 b b）定界，以每个后继问题为一分支标明求解的结果。）定界，以每个后继问题为一分支标明求解的结果。第一步：先不考虑整数约束，变成一般的线性规划问第一步：先不考虑整数约束，变成一般的线性规划问题，用图解法或单纯形法求解其最优解题，用图解法或单纯形法求解其最优解X X(0)(0)*；第二步：若求得的最优解第二步：若求得的最优解X X(0)(0)*,刚好就是整数解，则该刚好就是整数解，则该整数就是原整数规划的最优
24、解，否则转下步；整数就是原整数规划的最优解，否则转下步；第三步：对原问题进行分支寻求整数最优解。第三步：对原问题进行分支寻求整数最优解。选取非整数解选取非整数解 的一个非整数分量的一个非整数分量 ，其，其小数部分为小数部分为 ，以该非整数部分的相邻整数，以该非整数部分的相邻整数 和和 的为边界将原问题分支为两个子问题，并抛的为边界将原问题分支为两个子问题，并抛弃这两个整数之间的非整数区域；弃这两个整数之间的非整数区域；第20页/共41页际恩陆2023/2/2321 i i）在原线性规划模型中添加分支约束）在原线性规划模型中添加分支约束 ，构成第一个子问题。，构成第一个子问题。ii ii）在原线
25、性规划模型中添加分支约束）在原线性规划模型中添加分支约束 ，构成第二个子问题。，构成第二个子问题。第四步：对上面两个子问题按照线性规划方法求最优第四步：对上面两个子问题按照线性规划方法求最优解。若某个子问题的解是整数解，则停止该子问题的分支，解。若某个子问题的解是整数解，则停止该子问题的分支，并且把它的目标值与上一步求出的最优整数解相比较以决并且把它的目标值与上一步求出的最优整数解相比较以决定取舍；否则，对该子问题继续进行分支。定取舍；否则，对该子问题继续进行分支。第五步：重复第三、四步直到获得原问题最优整数解第五步：重复第三、四步直到获得原问题最优整数解为止。为止。第21页/共41页际恩陆2
26、023/2/2322 割平面法：割平面法：分支定界法是对原问题可行解域进行切分支定界法是对原问题可行解域进行切割，但子问题却由于分支的增多而呈指数增长。为了克服割，但子问题却由于分支的增多而呈指数增长。为了克服这个缺点，割平面法采用另一种分割可行解域的办法，既这个缺点，割平面法采用另一种分割可行解域的办法，既要切割掉非整数解域，又不希望对问题进行分支。步骤如要切割掉非整数解域，又不希望对问题进行分支。步骤如下：下：第一步：先不考虑整数约束，变成一般的线性规划规第一步：先不考虑整数约束，变成一般的线性规划规划问题，用单纯形法求其最优解，记为划问题，用单纯形法求其最优解，记为 第二步：若求得的最优
27、解第二步：若求得的最优解 刚好就是整数解，则该刚好就是整数解，则该整数解就是原整数规划的最优解；否则，转下步。整数解就是原整数规划的最优解；否则，转下步。第三步：寻求附加约束，即割平面方程第三步：寻求附加约束，即割平面方程 从最优化表中抄下非整数解的约束方程。从最优化表中抄下非整数解的约束方程。第22页/共41页际恩陆2023/2/2323 其中其中b bi i是基变量是基变量x xi i的非整数解。的非整数解。将该约束方程所有系数和常数分解为整数将该约束方程所有系数和常数分解为整数N N和正真分和正真分数之和。数之和。将整数项写于方程左边，真分数项写于右边。将整数项写于方程左边，真分数项写于
28、右边。考虑整数条件约束。以上方程左边为整数，右边的考虑整数条件约束。以上方程左边为整数，右边的内是正数。所以方程右边必是非正数。即：内是正数。所以方程右边必是非正数。即：第23页/共41页际恩陆2023/2/2324 上述就是所求的割平面方程。上述就是所求的割平面方程。第四步：引入松弛变量第四步：引入松弛变量x xi,k+1i,k+1,将割平面方程规范化将割平面方程规范化 将规范化后的割平面方程最后一个单纯形表将规范化后的割平面方程最后一个单纯形表,然后用对然后用对偶单纯形法解之。偶单纯形法解之。2 2、0101规划与隐枚举法规划与隐枚举法 01 01规划的概念规划的概念 决策变量只取决策变量
29、只取0 0，1 1两个数的整数规划，两个数的整数规划，1 1，0 0表示方案表示方案的取舍。的取舍。隐枚举法隐枚举法 不需要列出所有组合，只需关心目标函数值的最优可不需要列出所有组合，只需关心目标函数值的最优可第24页/共41页际恩陆2023/2/2325行组合，按目标值从优到劣依次列出组合，逐个检验其可行组合，按目标值从优到劣依次列出组合，逐个检验其可行性；最先满足所有约束条件的组合为最优解，劣于最优行性；最先满足所有约束条件的组合为最优解，劣于最优解的组合即使可行，也不列出检验而舍去。用隐枚举法求解的组合即使可行，也不列出检验而舍去。用隐枚举法求解解0101规划的步骤如下：规划的步骤如下：
30、第一步：变换目标函数和约束方程组。第一步：变换目标函数和约束方程组。按目标函数中各变量系数的大小顺序重新排列各变量，按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解有可能较早出现。如本章的例以使最优解有可能较早出现。如本章的例1111。第二步：用目标函数值探索法求最优解。第二步：用目标函数值探索法求最优解。以以z z的最大值为上界逐步向上搜索，直至获得可行解，的最大值为上界逐步向上搜索，直至获得可行解，此即为最优解。此即为最优解。第25页/共41页际恩陆2023/2/23263 3、指派问题和匈牙利法、指派问题和匈牙利法 指派问题的特点指派问题的特点 把把m m项工作指派给项工作指派
31、给n n个人去做，既发挥各人特长又使效个人去做，既发挥各人特长又使效率最高。这是一类特殊的率最高。这是一类特殊的0101规划问题。规划问题。匈牙利法匈牙利法 该方法由匈牙利数学家该方法由匈牙利数学家KoningKoning发明，也叫画圈法。发明，也叫画圈法。指派问题的标准型指派问题的标准型 目标函数为求目标函数为求minmin；系数矩阵为方阵（即每项工作只能；系数矩阵为方阵（即每项工作只能有一人来做，每个人只能做一项工作），且其所有元素均有一人来做，每个人只能做一项工作），且其所有元素均为非负。满足这两个条件的指派问题叫做标准型指派问题。为非负。满足这两个条件的指派问题叫做标准型指派问题。第2
32、6页/共41页际恩陆2023/2/2327 标准型指派问题的求解标准型指派问题的求解 求解原理：找出一组位于系数矩阵中不同行、不同求解原理：找出一组位于系数矩阵中不同行、不同列的零元素，对其画圈，对应的列的零元素，对其画圈，对应的x xijij=1=1，未画圈的元素，对，未画圈的元素，对应的应的x xijij=0=0，此时，目标函数最优。，此时，目标函数最优。求解步骤求解步骤 第一步：变换系数矩阵，使其每行每列都出现第一步：变换系数矩阵，使其每行每列都出现0 0元素。元素。首先：每行减该行中的最小数，再每列减去该列中的首先：每行减该行中的最小数，再每列减去该列中的最小数。匈牙利解法的关键是利用
33、了指派问题最优解的以最小数。匈牙利解法的关键是利用了指派问题最优解的以下性质：若从指派问题的系数矩阵下性质：若从指派问题的系数矩阵C=(cC=(cijij)nnnn的某行的某行(或某列或某列)各元素分别减去一个常数各元素分别减去一个常数k k，得到的一个新的矩阵，得到的一个新的矩阵C=(cC=(cijij)nnnn。则以。则以CC求得的最优解和以求得的最优解和以C C求得的最优解求得的最优解相同。相同。第27页/共41页际恩陆2023/2/2328 第二步：画圈第二步：画圈 a a）从只有一个）从只有一个0 0元素的行开始，给这个元素的行开始，给这个0 0元素加圈，记元素加圈，记作作，表示该行
34、所代表的人只有一种任务可分派。然后，表示该行所代表的人只有一种任务可分派。然后，划去该划去该所在列的其他所在列的其他0 0元素，记作元素，记作表示该列所代表的任表示该列所代表的任务已分派完，不必再考虑别人了。务已分派完，不必再考虑别人了。b b）给只有一个）给只有一个0 0元素列的元素列的0 0元素加圈元素加圈,记作记作。然后，。然后，划去该划去该所在行的其他所在行的其他0元素，记作元素，记作。c c）反复进行）反复进行a a）、）、b b）操作，直到所有）操作，直到所有0 0元素都被圈出元素都被圈出和划掉为止。若每行每列均只有一个和划掉为止。若每行每列均只有一个时（对应的时（对应的x xij
35、ij=1=1，其余的其余的x xijij=0=0），即），即的个数等于方阵阶数，得到最优解，的个数等于方阵阶数，得到最优解，否则，转到下一步。否则，转到下一步。第三步：第三步：的个数少于方阵的阶数。的个数少于方阵的阶数。第28页/共41页际恩陆2023/2/2329 a a）若出现）若出现0 0元素闭回路，则任选一个元素闭回路，则任选一个0 0画画破闭回路，破闭回路，并划去同行与同列其他并划去同行与同列其他0 0元素，得到最优解。元素，得到最优解。b b）若无）若无0 0元素闭回路，则用覆盖理论解决。元素闭回路，则用覆盖理论解决。）若无）若无0 0元素闭回路，则用直线覆盖理论解决。元素闭回路，
36、则用直线覆盖理论解决。）对未被直线覆盖的一类区所有元素减去它们中的）对未被直线覆盖的一类区所有元素减去它们中的最小数；而对被直线交叉覆盖的三类元素加上刚才的最小最小数；而对被直线交叉覆盖的三类元素加上刚才的最小数，其余元素不变。转第二步，循环执行到数，其余元素不变。转第二步，循环执行到的个数等于的个数等于方阵阶数为止。方阵阶数为止。非标准型的指派问题非标准型的指派问题 略。略。第29页/共41页际恩陆2023/2/2330 第五章第五章 复习思考题复习思考题 1 1、整数规划的意义，举出整数规划的例子。（略）、整数规划的意义，举出整数规划的例子。（略）2 2、有人提出，求解整数规划时，可先不考
37、虑变量的整、有人提出，求解整数规划时，可先不考虑变量的整数约束，而去求解相应的线性规划问题，然后对求解结果数约束，而去求解相应的线性规划问题，然后对求解结果为非整数的变量凑整。试问这种方法是否可行，为什么？为非整数的变量凑整。试问这种方法是否可行，为什么？这种方法对于整数规划问题存在有有限个整数可行解这种方法对于整数规划问题存在有有限个整数可行解时，是可行的。因为只要整数规划问题中存在有有限个整时，是可行的。因为只要整数规划问题中存在有有限个整数可行解，而又可求得相应的线性规划问题的最优解，就数可行解，而又可求得相应的线性规划问题的最优解，就一定可以用凑整和比较的办法求得整数规划问题的最优解，
38、一定可以用凑整和比较的办法求得整数规划问题的最优解，其实，隐枚举法和分支定解法就是根据这一原理来求解的。其实，隐枚举法和分支定解法就是根据这一原理来求解的。第30页/共41页际恩陆2023/2/2331 3 3、试述用分支定支定界法求解整数规划问题的主要思、试述用分支定支定界法求解整数规划问题的主要思想及主要步骤及此种方法的优缺点。想及主要步骤及此种方法的优缺点。见教材见教材P137P141P137P141。5 5、0-10-1变量的作用和举例。变量的作用和举例。略。略。4 4、试述用割平面法求解整数规划问题的主要思想，在、试述用割平面法求解整数规划问题的主要思想，在构造割平面时如何做到从原可
39、行域中只切去变量的非整数构造割平面时如何做到从原可行域中只切去变量的非整数解。解。见教材见教材P133P137P133P137。6 6、什么是隐枚举法？为什么说分支定界法也是一种隐、什么是隐枚举法？为什么说分支定界法也是一种隐枚举法？枚举法？第31页/共41页际恩陆2023/2/2332 把一个整数规划问题的所有整数可行解都一一列出，把一个整数规划问题的所有整数可行解都一一列出，然后比较它们的目标函数值，从中选出目标函数值最优的然后比较它们的目标函数值，从中选出目标函数值最优的整数解的方法叫完全枚举法。而去掉部分不可能是最优解整数解的方法叫完全枚举法。而去掉部分不可能是最优解的整数可行解，只在
40、有限个整数可行解中求解最优整数解的整数可行解，只在有限个整数可行解中求解最优整数解的方法叫隐枚举法。分支定界法正是应用这一原理，利用的方法叫隐枚举法。分支定界法正是应用这一原理，利用分支和定界去掉部分非整数解，而使求解过程得以简化。分支和定界去掉部分非整数解，而使求解过程得以简化。整数规划解的目标函数值一般优于其相应的线性规整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值；划问题的解的目标函数值；8 8、判断下列说法是否正确、判断下列说法是否正确 用分支定界法求解一个极大化的整数规划问题时，用分支定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数
41、值的下界。任何一个可行解的目标函数值是该问题目标函数值的下界。第32页/共41页际恩陆2023/2/2333 用分支定界法求解一个极大化的整数规划问题时，用分支定界法求解一个极大化的整数规划问题时，当得到多于一个可行解，通常可任取其中一个为下界值，当得到多于一个可行解，通常可任取其中一个为下界值，再进行比较剪支；再进行比较剪支；用割平面法求解整数规划时，构造的割平面有可能用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解；切去一些不属于最优解的整数解；用割平面法求解纯整数规划时，要求包括松弛变量用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值；在内的
42、全部变量必须取整数值；指派问题效率矩阵的每个元素都乘以同一常数指派问题效率矩阵的每个元素都乘以同一常数k k，将，将不影响最优指派方案；不影响最优指派方案；指派问题数学模型的形式同运输问题十分相似，故指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解；也可以用表上作业法求解；第33页/共41页际恩陆2023/2/2334 求解求解0-10-1规划的隐枚举法是分支定界法的物例。规划的隐枚举法是分支定界法的物例。分支定界法在需要分支时必须满足：一是分支后的分支定界法在需要分支时必须满足：一是分支后的各子问题必须容易求解；二是各子问题解的集合必须覆盖各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解。原问题的解。第34页/共41页际恩陆2023/2/2335第35页/共41页际恩陆2023/2/2336第36页/共41页际恩陆2023/2/2337第37页/共41页际恩陆2023/2/2338第38页/共41页际恩陆2023/2/2339第39页/共41页际恩陆2023/2/2340第40页/共41页际恩陆2023/2/2341感谢观看！感谢观看！第41页/共41页