运筹(第四章整数规划)

2023/1/111运筹学

OPERATIONSRESEARCH

2023/1/112第四章整数规划与分配问题

整数规划的有关概念及特点整数规划的应用指派问题及匈牙利解法整数规划的求解方法：分枝定界法、割平面法2023/1/113纯整数规划：在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；混合整数规划：如果有一部分变量为非负整数，则称之为混合整数规划问题。0-1变量：在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。0-1规划：在整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。§1整数规划的有关概念及特点§1.1概念整数规划：要求决策变量取整数值的规划问题。（线性整数规划、非线性整数规划等）2023/1/114求整数解的线性规划问题，不是用四舍五入法或去尾法对性规划的非整数解加以处理就能解决的，用枚举法又往往会计算量太大，所以要用整数规划的特定方法加以解决。例：求解下列整数规划：§1.2整数规划的求解特点2023/1/115分析：

若当作一般线性规划求解，图解法的结果如下。1、非整数规划最优解显然不是整数规划的可行解。2、四舍五入后的结果也不是整数规划的可行解。3、可行解是阴影区域交叉点，可比较这些点对应的函数值，找出最优。2023/1/116§2

应用举例

§2.1

逻辑变量在数学模型中的应用1、m个约束条件中只有k个起作用设有m个约束条件定义0-1整型变量：第i个约束起作用第i个约束不起作用2023/1/117设M是任意大正数，则原约束中只有k个真正起作用的情况可表示为：2023/1/1182、约束条件右端项是r个可能值中的一个则通过定义约束条件右端项不是bi约束条件右端项是bi可将上述条件表示为2023/1/1193、两组条件中满足其中一组例如表示条件：若，则；否则时则通过定义第i组条件起作用，i=1，2第i组条件不起作用可将上述条件表示为其中：M是任意大正数2023/1/1110定义4、表示含有固定费用的函数例如：表示产品的生产数量，其生产费用函数为：目标函数：其中是与产量无关的生产准备费用

则原问题可表示为2023/1/1111§2.2应用举例例1

东方大学计算机实验室聘用4名大学生（代号1,2,3,4）和2名研究生（代号5,6）值班。已知各学生从周一至周五每天可安排的值班时间及每人每小时报酬见下表所示。学生代号酬金(元/h)每天可安排的值班时间(h)周一周二周三周四周五110.060607210.00606339.94830549.855640510.830460611.3062442023/1/1112实验室每天开放时间为8:00AM—10:00PM,共14小时。开放时间内需要有一名学生值班。规定大学生每周值班时间是8—15小时，研究生是7—12小时，每次值班不小于2小时。又每名学生每周值班次数不得多于三次，每天值班人员中至少有一名研究生，每天值班人数不超过3人。试为该实验室安排一张人员值班表，使得总酬金支出为最少。解：设表示学生i在周j的值班时间。学生i在周j不值班学生i在周j值班

表示学生i在周j的最多可值班时间。则目标函数：2023/1/1113研究生值班7-12小时每周不超过3次每天不超过3人每天有一研究生值班不超过每人可安排的时间每天开放14小时大学生值班8-15小时约束条件2023/1/1114例2红星日用化工厂为发运产品，下一年度需要6种不同容积的包装箱，每种包装箱的需求量及生产一个的可变费用如下表所示。包装箱代号123456容积（m3）0.080.100.120.150.200.25需求量（个）500550700900450400可变费用（元/个）5.08.010.012.116.318.2由于生产不同容积包装箱时需进行专门的准备、下料等，生产每一种包装箱的固定费用都是1200元。又若某容积的包装箱数量不够时，可用比它大的代替。试问该厂应订做哪几种代号的包装箱各多少个，可使得费用最省？2023/1/1115解：设表示代号为j的包装箱的订做数量。不订j包装箱订j包装箱目标函数约束条件2023/1/11162023/1/1117例3（固定成本问题）高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。

2023/1/1118解：设分别为小号容器、中号容器和大号容器的生产数量。

建立如下的数学模型：资源小号容器中号容器大号容器金属板（吨）248劳动力（人月）234机器设备（台月）123不生产j型号容器生产j型号容器2023/1/11192023/1/1120§3

指派问题及匈牙利解法

§3.1指派问题与模型m项任务分配给m个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配使得效率最高？

aij是第j个人完成第i项任务的效率(如时间）。人任务12…

m1a11a12…a1m2a21a22…a2m……………mam1am2amm2023/1/1121设于是建立模型如下：2023/1/1122§3.1指派问题的匈牙利解法该指派问题可当作运输问题解决，但匈牙利解法更有效。解法思想：效率矩阵的元素，若有一组位于不同行不同列的零元素，则令这些位置的决策变量取值为1，其余均为0，这显然就是最优解。2023/1/1123定理2：若矩阵A的元素可分为“0”元和“非0”元，则覆盖“0”元的最少直线数等于位于不同行、不同列的“0”元的最大个数。定理1：效率矩阵的每一行元素分别减去（加上）一个常数，每一列元素分别减去（加上）一个元素，得新效率矩阵，，则的最优解等价于的最优解。2023/1/1124例：有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高。表中数据为完成任务所需时间（单位：小时）。人任务甲乙丙丁英文21097日文154148德文13141611俄文4151392023/1/1125匈牙利解法步骤：1、在效率矩阵每行减去该行最小元素；2、在效率矩阵每列减去该列最小元素；2023/1/11263、寻找独立“0”元素(不同行不同列）（1）从第一行开始，若该行只有一个“0”元素，则对该“0”元素打括号（）（表示这一行的人只有这一个任务可指派），并划去该“0”元素所在的列（表示该项任务不能再指派给别人）；若该行无“0”元素或有两个以上的“0”元素（不含划去的0），则转下一行；（2）从第一列开始，若该列只有一个“0”元素，则对该“0”元素打括号（），并划去该“0”元素所在的行；若该列无“0”元素或有两个以上的“0”元素（不含划去的0），则转下一列；2023/1/1127（0）82511（0）5423（0）001145完成上述步骤后可能出现下列情况：ⅰ）效率矩阵的每一行都有一个打括号的0元素，则按照打括号的0元素位置指派任务，即是最优解；2023/1/1128ⅱ）打括号的0元素个数小于m，但未被划去的0元素之间存在闭回路，则沿此闭回路，每隔一个0元打一括号，然后对打括号的0元素所在行或所在列画直线；ⅲ）矩阵中所有0元素或被打括号，或被划去，但打括号的0元素个数，则进入下一步；2023/1/1129（3）设法使每一行都有一个打括号的“0”元素。按定理1继续对矩阵进行变换：ⅰ）从矩阵未被直线覆盖的元素中找出最小者k，ⅱ）对矩阵中无直线覆盖的行，令，有直线覆盖的列，令。其余为0。ⅲ）对矩阵的每个元素计算，得到一个新矩阵，转第三步重复进行，直至每一行都有一打括号的0元素。2023/1/1130（0）82511（0）5423（0）001145根据上图，k=2，最优解：2023/1/1131两点说明：1、任务数人数时如何处理增加虚拟的人或虚拟的任务

2、指派问题中目标函数变为MAX时如何处理。每行每列找最大者，用此最大元素减去相应各行各列的元素，得到同解矩阵。2023/1/1132§4

分枝定界法

分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法编制而成的。下面举例来说明分枝定界法的思想和步骤。2023/1/11331、求解整数规划相应的一般线性规划问题（即先去掉整数约束）。易知：整数规划的可行域（小）包含于线性规划的可行域(大）。若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。例求解下列整数规划：2023/1/1134解：1、解对应的线性规划：其最优解为，显然不是整数规划的可行解。L0：2023/1/1135性质

求MAX的问题：整数规划的最优目标函数值小于或等于相应的线性规划的最优目标函数值；

求MIN的问题：整数规划的最优目标函数值大于或等于相应的线性规划的最优目标函数值。2、分枝与定界：将对应的线性规划问题分解成几个子问题，每个子问题就是一分枝，而所有子问题的解集之和要包含原整数规划的解集。2023/1/1136求解每一分枝子问题：若其最优解满足整数约束，则它就是原问题的一个可行解（不一定是最优）；否则，就是该枝的上界或下界。

若所有分支的最优解都不满足整数条件（即不是原问题的可行解），则选取一个边界值最优的分支继续分解，直至找到一个原问题的可行解。若在同一级分枝中同时出现两个以上的原问题可行解，则保留目标值最优的一个，其余不再考虑。从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。2023/1/1137将上述线性规划问题分为两枝，并求解。解得解得L1：L2：显然两个分枝均非整数可行解，选边界值较大的L1继续分枝。2023/1/1138将L1分为两枝，并求解。解得解得L11：L12：两个分枝均是整数可行解，保留目标值较大的L12。2023/1/11393、比较与剪枝将各子问题的边界值与保留下的整数可行解对应的目标值比较，将边界值劣于可行行解的分支减剪去。

若比较剪枝后，只剩下所保留的整数可行解，则该解就是原整数规划的最优解；否则选取边界值最大的一个分枝继续分解，在其后的过程中出现新的整数可行解时，则与原可行解比较，保留较优的一个，重复第三步。2023/1/1140L0：X2≤2X2≥3X1≤3X1≥4用图表示上例的求解过程与求解结果2023/1/1141§5

割平面法

§5.1

基本思想

在整数规划的松弛问题中，依次引进新的约束条件（割平面），使问题的可行域逐步减小，但每次割去的只是部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后的可行域的一个顶点，这样就可以用线性规划的方法求得整数最优解。2023/1/1142例求解下列整数规划：解：1、解对应的线性规划（松弛问题），并将约束条件的系数均化为整数：2023/1/1143加入松弛变量后求解，得最终单纯形表：25/2011/2-1/2313/410-1/43/400-1/4-5/4如果上述求解结果是整数解，则结束；否则转下一步；2、找出非整数解中分数部分最大的一个基变量，并将该行对应的约束方程所有常数（系数及常数项）分解成一个整数与一个正分数之和；将所有分式项移到等式右端。例如上例，取第一行约束.2023/1/11