运筹整数规划素材.pptx

2024/3/26 周二周二1运筹学运筹学OPERATIONS RESEARCH2024/3/26 周二周二2第四章第四章 整数规划与分配问题整数规划与分配问题n整数规划的有关概念及特点整数规划的有关概念及特点 n整数规划的应用整数规划的应用n指派问题及匈牙利解法指派问题及匈牙利解法 n整数规划的求解方法：分枝定界法、割平面法整数规划的求解方法：分枝定界法、割平面法 2024/3/26 周二周二3纯整数规划：纯整数规划：在整数规划中，如果所有的变量都为在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；非负整数，则称为纯整数规划问题；混合整数规划：混合整数规划：如果有一部分变量为非负整数，则如果有一部分变量为非负整数，则称之为混合整数规划问题。称之为混合整数规划问题。0-10-1变量：变量：在整数规划中，如果变量的取值只限于在整数规划中，如果变量的取值只限于0 0和和1 1，这样的变量我们称之为，这样的变量我们称之为0-10-1变量。变量。0-10-1规划：规划：在整数规划问题中，如果所有的变量都在整数规划问题中，如果所有的变量都为为0-10-1变量，则称之为变量，则称之为0-10-1规划。规划。1 1 整数规划的有关概念及特点整数规划的有关概念及特点11.1 .1 概念概念整数规划：整数规划：要求决策变量取整数值的规划问题。要求决策变量取整数值的规划问题。（线性整数规划、非线性整数规划等）（线性整数规划、非线性整数规划等）2024/3/26 周二周二4求整数解的线性规划问题，不是用求整数解的线性规划问题，不是用四舍五入四舍五入法或法或去尾法去尾法对性规划的非整数解加以处理就能解决的，对性规划的非整数解加以处理就能解决的，用用枚举法枚举法又往往会计算量太大，所以要用整数规又往往会计算量太大，所以要用整数规划的特定方法加以解决。划的特定方法加以解决。例：例：求解下列整数规划：求解下列整数规划：11.2.2 整数规划的求解特点整数规划的求解特点2024/3/26 周二周二5分析：分析：若当作一般线性规划求解，若当作一般线性规划求解，图解法的结果如下。图解法的结果如下。1、非整数规划、非整数规划最优解最优解 显然不是整数规划的可行解。显然不是整数规划的可行解。2、四舍五入后的结果四舍五入后的结果 也不是整数规划的可行解。也不是整数规划的可行解。3、可行解是阴影区可行解是阴影区域交叉点，可比较这域交叉点，可比较这些点对应的函数值，些点对应的函数值，找出最优。找出最优。2024/3/26 周二周二622 应用举例应用举例22.1.1 逻辑变量在数学模型中的应用逻辑变量在数学模型中的应用1 1、m m个约束条件中只有个约束条件中只有k k个起作用个起作用设有设有m m个约束条件个约束条件定义定义0-10-1整型变量：整型变量：第第i i个约束起作用个约束起作用第第i i个约束不起作用个约束不起作用2024/3/26 周二周二7设设M M是任意大正数，则原约束中只有是任意大正数，则原约束中只有k k个真正个真正起作用的情况可表示为：起作用的情况可表示为：2024/3/26 周二周二82 2、约束条件右端项是、约束条件右端项是r r个可能值中的一个个可能值中的一个则通过定义则通过定义约束条件右端项不是约束条件右端项不是b bi i约束条件右端项是约束条件右端项是b bi i可将上述条件表示为可将上述条件表示为 2024/3/26 周二周二93 3、两组条件中满足其中一组、两组条件中满足其中一组例如表示条件：若例如表示条件：若 ，则，则 ；否则否则 时时则通过定义则通过定义第第i i组条件起作用，组条件起作用，i=1i=1，2 2第第i i组条件不起作用组条件不起作用可将上述条件表示为可将上述条件表示为 其中：其中：M M是任意大正数是任意大正数2024/3/26 周二周二10定义定义4 4、表示含有固定费用的函数、表示含有固定费用的函数例如：例如：表示产品表示产品 的生产数量，其生产费用函数的生产数量，其生产费用函数为：为：目标函数：目标函数：其中其中 是与产量无关是与产量无关的生产准备费用的生产准备费用 则原问题可表示为则原问题可表示为2024/3/26 周二周二1122.2.2 应用举例应用举例例例1 1 东方大学计算机实验室聘用东方大学计算机实验室聘用4 4名大学生（代号名大学生（代号1,2,3,41,2,3,4）和）和2 2名研究生（代号名研究生（代号5,65,6）值班。已知各学生从）值班。已知各学生从周一至周五每天可安排的值班时间及每人每小时报酬见下周一至周五每天可安排的值班时间及每人每小时报酬见下表所示。表所示。学生学生代号代号酬金酬金(元元/h)每天可安排的值班时间每天可安排的值班时间(h)周一周一周二周二周三周三周四周四周五周五110.060607210.00606339.94830549.855640510.830460611.3062442024/3/26 周二周二12实验室每天开放时间为实验室每天开放时间为8:00AM10:00PM,8:00AM10:00PM,共共1414小时。开放小时。开放时间内需要有一名学生值班。规定大学生每周值班时间是时间内需要有一名学生值班。规定大学生每周值班时间是815815小时，研究生是小时，研究生是712712小时，每次值班不小于小时，每次值班不小于2 2小时。小时。又每名学生每周值班次数不得多于三次，每天值班人员中又每名学生每周值班次数不得多于三次，每天值班人员中至少有一名研究生，每天值班人数不超过至少有一名研究生，每天值班人数不超过3 3人。试为该实人。试为该实验室安排一张人员值班表，使得总酬金支出为最少。验室安排一张人员值班表，使得总酬金支出为最少。解：解设设 表示学生表示学生i i在周在周j j的值班时间。的值班时间。学生学生i i在周在周j j不值班不值班学生学生i i在周在周j j值班值班 表示学生表示学生i i在周在周j j的最多可值班时间。的最多可值班时间。则则目标函数目标函数：2024/3/26 周二周二13研究生值班研究生值班7-127-12小时小时每周不超过每周不超过3 3次次每天不超过每天不超过3 3人人每天有一研究生每天有一研究生值班不超过每人可安排的时间值班不超过每人可安排的时间每天开放每天开放1414小时小时大学生值班大学生值班8-158-15小时小时约约束束条条件件2024/3/26 周二周二14例例2 2 红星日用化工厂为发运产品，下一年度需要红星日用化工厂为发运产品，下一年度需要6 6种不同容积的包装箱，每种包装箱的需求量及生产种不同容积的包装箱，每种包装箱的需求量及生产一个的可变费用如下表所示。一个的可变费用如下表所示。包装箱代号包装箱代号123456容积（容积（m3）0.080.100.120.150.200.25需求量（个）需求量（个）500550700900450400可变费用（元可变费用（元/个）个）5.08.010.012.116.318.2由于生产不同容积包装箱时需进行专门的准备、下由于生产不同容积包装箱时需进行专门的准备、下料等，生产每一种包装箱的固定费用都是料等，生产每一种包装箱的固定费用都是12001200元。元。又若某容积的包装箱数量不够时，可用比它大的代又若某容积的包装箱数量不够时，可用比它大的代替。试问该厂应订做哪几种代号的包装箱各多少个，替。试问该厂应订做哪几种代号的包装箱各多少个，可使得费用最省？可使得费用最省？2024/3/26 周二周二15解：解：设设 表示代号为表示代号为j j的包装箱的订做数量的包装箱的订做数量。不订不订j j包装箱包装箱订订j j包装箱包装箱目标函数目标函数约束条件约束条件2024/3/26 周二周二162024/3/26 周二周二17例例3 3（固定成本问题）（固定成本问题）高压容器公司制造小、中、大三种尺寸的金属容器，高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。每种容器售容器所需的各种资源的数量如表所示。每种容器售出一只所得的利润分别为出一只所得的利润分别为 4 4万元、万元、5 5万元、万元、6 6万元，万元，可使用的金属板有可使用的金属板有500500吨，劳动力有吨，劳动力有300300人人/月，机月，机器有器有100100台台/月，此外不管每种容器制造的数量是多月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是少，都要支付一笔固定的费用：小号是l00l00万元，万元，中号为中号为 150 150 万元，大号为万元，大号为200200万元。现在要制定一万元。现在要制定一个生产计划，使获得的利润为最大。个生产计划，使获得的利润为最大。2024/3/26 周二周二18解解：设设 分别为小号容器、中号容器和大号容分别为小号容器、中号容器和大号容器的生产数量。器的生产数量。建立如下的数学模型：建立如下的数学模型：资源资源小号容器小号容器中号容器中号容器大号容器大号容器金属板（吨）金属板（吨）248劳动力（人月）劳动力（人月）234机器设备（台月）机器设备（台月）123不生产不生产j j型号容器型号容器生产生产j j型号容器型号容器2024/3/26 周二周二192024/3/26 周二周二2033 指派问题及匈牙利解法指派问题及匈牙利解法 33.1.1 指派问题与模型指派问题与模型 m m项任务分配给项任务分配给m m个人去完成，每人只能完成其中个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配一项，每项任务只能分给一人完成，应如何分配使得效率最高？使得效率最高？a aijij是第是第j j个人完成第个人完成第i i项任务的效率项任务的效率(如如 时间）。时间）。人人任务任务12 m1a11a12a1m2a21a22a2mmam1am2amm2024/3/26 周二周二21设设于是建立模型如下：于是建立模型如下：2024/3/26 周二周二2233.1.1 指派问题的匈牙利解法指派问题的匈牙利解法该指派问题可当作运输问题解决，但匈牙利解法更该指派问题可当作运输问题解决，但匈牙利解法更有效。有效。解法思想：解法思想：效率矩阵的元素效率矩阵的元素 ，若有一组位于，若有一组位于不同行不同列的零元素，则令这些位置的决策变量不同行不同列的零元素，则令这些位置的决策变量取值为取值为1 1，其余均为，其余均为0 0，这显然就是最优解。，这显然就是最优解。2024/3/26 周二周二23定理定理2 2：若矩阵若矩阵A A的元素可分为的元素可分为“0”0”元和元和“非非0”0”元，元，则覆盖则覆盖“0”0”元的最少直线数等于位于不同行、不元的最少直线数等于位于不同行、不同列的同列的“0”0”元的最大个数。元的最大个数。定理定理1 1：效率矩阵效率矩阵 的每一行元素分别减去（加的每一行元素分别减去（加上）一个常数上）一个常数 ，每一列元素分别减去（加上），每一列元素分别减去（加上）一个元素一个元素 ，得新效率矩阵，得新效率矩阵 ，则则 的最优解等价于的最优解等价于 的最优解。的最优解。2024/3/26 周二周二24例：例：有一份说明书，要分别译成英、日、德、俄四种语言，有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高。分配任务，可使总效率最高。表中数据为完成任务所需时间（单位：小时）。表中数据为完成任务所需时间（单位：小时）。人任务甲乙丙丁英文21097日文154148德文13141611俄文4151392024/3/26 周二周二25匈牙利解法匈牙利解法步骤：步骤：1 1、在效率矩阵每行减去该行最小元素；、在效率矩阵每行减去该行最小元素；2 2、在效率矩阵每列减去该列最小元素；、在效率矩阵每列减去该列最小元素；2024/3/26 周二周二263 3、寻找独立、寻找独立“0”0”元素元素(不同行不同列）不同行不同列）（1 1）从第一行开始，若该行只有一个）从第一行开始，若该行只有一个“0”0”元素，元素，则对该则对该“0”0”元素打括号（元素打括号（）（表示这一行的人只（表示这一行的人只有这一个任务可指派），有这一个任务可指派），并划去该并划去该“0”0”元素所在元素所在的列的列（表示该项任务不能再指派给别人）（表示该项任务不能再指派给别人）；若该；若该行无行无“0”0”元素或有两个以上的元素或有两个以上的“0”0”元素（不含划元素（不含划去的去的0 0），则转下一行；），则转下一行；（2 2）从第一列开始，若该列只有一个）从第一列开始，若该列只有一个“0”0”元素，元素，则对该则对该“0”0”元素打括号（元素打括号（），并划去该），并划去该“0”0”元元素所在的行；若该列无素所在的行；若该列无“0”0”元素或有两个以上的元素或有两个以上的“0”0”元素（不含划去的元素（不含划去的0 0），则转下一列；），则转下一列；2024/3/26 周二周二27（0）82511（0）5423（0）001145完成上述步骤后可能出现下列情况：完成上述步骤后可能出现下列情况：）效率矩阵的每一行都有一个打括号的效率矩阵的每一行都有一个打括号的0 0元素，元素，则按照打括号的则按照打括号的0 0元素位置指派任务，即是最优解；元素位置指派任务，即是最优解；2024/3/26 周二周二28）打括号的打括号的0 0元素个数小于元素个数小于m m，但未被划去的，但未被划去的0 0元元素之间存在闭回路，则沿此闭回路，每隔一个素之间存在闭回路，则沿此闭回路，每隔一个0 0元元打一括号，然后对打括号的打一括号，然后对打括号的0 0元素所在行或所在列元素所在行或所在列画直线；画直线；）矩阵中所有矩阵中所有0 0元素或被打括号，或被划去，但打元素或被打括号，或被划去，但打括号的括号的0 0元素个数元素个数 ，则进入下一步；，则进入下一步；2024/3/26 周二周二29（3 3）设法使每一行都有一个打括号的）设法使每一行都有一个打括号的“0”0”元素。元素。按按定理定理1 1继续对矩阵进行变换：继续对矩阵进行变换：）从矩阵未被直线覆盖的元素中找出最小者从矩阵未被直线覆盖的元素中找出最小者k k，）对矩阵中无直线覆盖的行，令对矩阵中无直线覆盖的行，令 ，有直，有直线覆盖的列，令线覆盖的列，令 。其余为。其余为0 0。）对矩阵的每个元素计算对矩阵的每个元素计算 ，得到，得到一个新矩阵，转第三步重复进行，直至每一行都有一个新矩阵，转第三步重复进行，直至每一行都有一打括号的一打括号的0 0元素。元素。2024/3/26 周二周二30（0）82511（0）5423（0）001145根据上图，根据上图，k=2k=2，最优解：最优解：2024/3/26 周二周二31两点说明：两点说明：1 1、任务数、任务数 人数人数 时如何处理时如何处理增加虚拟的人或虚拟的任务增加虚拟的人或虚拟的任务 2 2、指派问题中目标函数变为、指派问题中目标函数变为MAXMAX时如何处理时如何处理 。每行每列找最大者，用此最大元素减去相应各行各每行每列找最大者，用此最大元素减去相应各行各列的元素，得到同解矩阵。列的元素，得到同解矩阵。2024/3/26 周二周二3244 分枝定界法分枝定界法 分枝定界法分枝定界法是求解整数规划的一种常用的有效的是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定大多数求解整数规划的商用软件就是基于分枝定界法编制而成的。界法编制而成的。下面举例来说明分枝定界法的思想和步骤。下面举例来说明分枝定界法的思想和步骤。2024/3/26 周二周二331 1、求解整数规划相应的一般线性规划问题（即先去、求解整数规划相应的一般线性规划问题（即先去掉整数约束）。掉整数约束）。易知：整数规划的可行域（小）包含于线性规划的易知：整数规划的可行域（小）包含于线性规划的可行域可行域 (大）。大）。若线性规划的最优解恰是整数解，则其就是整若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。解的上界或下界。例例 求解下列整数规划：求解下列整数规划：2024/3/26 周二周二34解：解：1 1、解对应的线性规划：、解对应的线性规划：其最优解为其最优解为 ，显然不是整数规划的可行解。显然不是整数规划的可行解。L0：2024/3/26 周二周二35性质性质 求求MAXMAX的问题的问题：整数规划的最优目标函数值整数规划的最优目标函数值小小于或等于于或等于相应的线性规划的最优目标函数值；相应的线性规划的最优目标函数值；求求MINMIN的问题：整数规划的最优目标函数值的问题：整数规划的最优目标函数值大大于或等于于或等于相应的线性规划的最优目标函数值。相应的线性规划的最优目标函数值。2 2、分枝与定界：、分枝与定界：将对应的线性规划问题分解成几个子问题，每将对应的线性规划问题分解成几个子问题，每个子问题就是一分枝，而所有子问题的解集之和个子问题就是一分枝，而所有子问题的解集之和要包含原整数规划的解集。要包含原整数规划的解集。2024/3/26 周二周二36求解每一分枝子问题：求解每一分枝子问题：若其最优解满足整数约束，则它就是原问题的若其最优解满足整数约束，则它就是原问题的一个可行解（不一定是最优）；否则，就是该枝的一个可行解（不一定是最优）；否则，就是该枝的上界或下界。上界或下界。若所有分支的最优解都不满足整数条件（即不若所有分支的最优解都不满足整数条件（即不是原问题的可行解），则选取一个边界值最优的分是原问题的可行解），则选取一个边界值最优的分支继续分解，直至找到一个原问题的可行解。支继续分解，直至找到一个原问题的可行解。若在同一级分枝中同时出现两个以上的原问题若在同一级分枝中同时出现两个以上的原问题可行解，则保留目标值最优的一个，其余不再考虑。可行解，则保留目标值最优的一个，其余不再考虑。从各分枝中找原问题可行解的目的是为下一步的比从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。较与剪枝。2024/3/26 周二周二37将上述线性规划问题分为两枝，并求解。将上述线性规划问题分为两枝，并求解。解得解得解得解得L1：L2：显然两个分枝均非整数可行解，选边界值较大的显然两个分枝均非整数可行解，选边界值较大的L L1 1继续分枝。继续分枝2024/3/26 周二周二38将将L1L1分为两枝，并求解。分为两枝，并求解。解得解得解得解得L11：L12：两个分枝均是整数可行解，保留目标值较大的两个分枝均是整数可行解，保留目标值较大的L L1212。2024/3/26 周二周二393 3、比较与剪枝比较与剪枝 将各子问题的边界值与保留下的整数可行解对将各子问题的边界值与保留下的整数可行解对应的目标值比较，将边界值劣于可行行解的分支减应的目标值比较，将边界值劣于可行行解的分支减剪去。剪去。若比较剪枝后，只剩下所保留的整数可行解，则若比较剪枝后，只剩下所保留的整数可行解，则该解就是原整数规划的最优解；否则选取边界值最该解就是原整数规划的最优解；否则选取边界值最大的一个分枝继续分解，在其后的过程中出现新的大的一个分枝继续分解，在其后的过程中出现新的整数可行解时，则与原可行解比较，保留较优的一整数可行解时，则与原可行解比较，保留较优的一个，重复第三步。个，重复第三步。2024/3/26 周二周二40L0：X22X23X13X14用图表示上例的求解过程与求解结果用图表示上例的求解过程与求解结果2024/3/26 周二周二4155 割平面法割平面法 55.1.1 基本思想基本思想 在整数规划的松弛问题中，依次引进新的约束条在整数规划的松弛问题中，依次引进新的约束条件（割平面），使问题的可行域逐步减小，但每件（割平面），使问题的可行域逐步减小，但每次割去的只是部分非整数解，直到使问题的目标次割去的只是部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后的可行域的函数值达到最优的整数点成为缩小后的可行域的一个顶点，这样就可以用线性规划的方法求得整一个顶点，这样就可以用线性规划的方法求得整数最优解。数最优解。2024/3/26 周二周二42例例 求解下列整数规划：求解下列整数规划：解：解：1 1、解对应的线性规划（松弛问题），并将约、解对应的线性规划（松弛问题），并将约束条件的系数均化为整数：束条件的系数均化为整数：2024/3/26 周二周二43加入松弛变量后求解，得最终单纯形表：加入松弛变量后求解，得最终单纯形表25/2011/2-1/2313/410-1/43/400-1/4-5/4如果上述求解结果是整数解，则结束；否则转下如果上述求解结果是整数解，则结束；否则转下一步；一步；2 2、找出非整数解中分数部分最大的一个基变量，并、找出非整数解中分数部分最大的一个基变量，并将该行对应的约束方程所有常数（系数及常数项）将该行对应的约束方程所有常数（系数及常数项）分解成一个整数与一个正分数之和；将所有分式项分解成一个整数与一个正分数之和；将所有分式项移到等式右端。移到等式右端。例如上例，取第一行约束例如上例，取第一行约束.2024/3/26 周二周二44易知，左端为整数，要是等式成立，右端也必为整易知，左端为整数，要是等式成立，右端也必为整数，且数，且将将 代入上式，得代入上式，得2024/3/26 周二周二45这就是一个割平面。将这就是一个割平面。将其添加到原约束中，得其添加到原约束中，得到新的可行域如图所示。到新的可行域如图所示。割去的只是部分非整数割去的只是部分非整数解。解。2024/3/26 周二周二463 3、将新的约束添加到原问题中，得到一个新的线性、将新的约束添加到原问题中，得到一个新的线性规划问题，求解此问题，可用灵敏度分析的方法。规划问题，求解此问题，可用灵敏度分析的方法。4 4、重复上述的、重复上述的1-31-3步，直至求出整数最优解。步，直至求出整数最优解。25/2011/2-1/20313/410-1/43/400-1/200-1/2-1/2100-1/4-5/40将将 反应到最终表中，得反应到最终表中，得2024/3/26 周二周二47运用对偶单纯形法，解得运用对偶单纯形法，解得22010-11/231001-1/2010011-2000-1-1/2此解仍非整数解，将基变量此解仍非整数解，将基变量 对应的约束分解为：对应的约束分解为：得到新的约束得到新的约束 2024/3/26 周二周二4822010-11/2031001-1/20010011-200-1/20000-1/21000-1-1/2021010-1023410010-10300110-40100001-2000-10-1此时已得整数最优解此时已得整数最优解 。2024/3/26 周二周二49约束约束即为即为最优解最优解人有了知识，就会具备各种分析能力，人有了知识，就会具备各种分析能力，明辨是非的能力。明辨是非的能力。所以我们要勤恳读书，广泛阅读，所以我们要勤恳读书，广泛阅读，古人说古人说“书中自有黄金屋。书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，给我们巨大的精神力量，鼓舞我们前进鼓舞我们前进。