运筹(第四章整数规划)

1、2022-6-51运筹学运筹学OPERATIONS RESEARCH2022-6-52第四章第四章 整数规划与分配问题整数规划与分配问题n整数规划的有关概念及特点整数规划的有关概念及特点 n整数规划的应用整数规划的应用n指派问题及匈牙利解法指派问题及匈牙利解法 n整数规划的求解方法：分枝定界法、割平面法整数规划的求解方法：分枝定界法、割平面法 2022-6-53纯整数规划：纯整数规划：在整数规划中，如果所有的变量都为在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；非负整数，则称为纯整数规划问题；混合整数规划：混合整数规划：如果有一部分变量为非负整数，则如果有一部分变量为非负整数

2、，则称之为混合整数规划问题。称之为混合整数规划问题。0-10-1变量：变量：在整数规划中，如果变量的取值只限于在整数规划中，如果变量的取值只限于0 0和和1 1，这样的变量我们称之为，这样的变量我们称之为0-10-1变量。变量。0-10-1规划：规划：在整数规划问题中，如果所有的变量都在整数规划问题中，如果所有的变量都为为0-10-1变量，则称之为变量，则称之为0-10-1规划。规划。1 1 整数规划的有关概念及特点整数规划的有关概念及特点1 1.1 .1 概念概念整数规划：整数规划： 要求决策变量取整数值的规划问题。要求决策变量取整数值的规划问题。 （线性整数规划、非线性整数规划等）（线性整

3、数规划、非线性整数规划等）2022-6-54求整数解的线性规划问题，不是用求整数解的线性规划问题，不是用四舍五入四舍五入法或法或去尾法去尾法对性规划的非整数解加以处理就能解决的，对性规划的非整数解加以处理就能解决的，用用枚举法枚举法又往往会计算量太大，所以要用整数规又往往会计算量太大，所以要用整数规划的特定方法加以解决。划的特定方法加以解决。例：例： 求解下列整数规划：求解下列整数规划：1 1.2 .2 整数规划的求解特点整数规划的求解特点并取整数并取整数, 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz2022-6-551x2x143221 xx5 . 4

4、5 . 021xx2123xxz)5 . 2,25. 3(分析：分析： 若当作一般线性规划求若当作一般线性规划求解，图解法的结果如下。解，图解法的结果如下。1、非整数规划、非整数规划最优解最优解 显然不是整数规划的可行解。显然不是整数规划的可行解。2、四舍五入后的结果四舍五入后的结果 也不是整数规划的可行解。也不是整数规划的可行解。)5 . 2,25. 3()3, 3(3、可行解是阴影区可行解是阴影区域交叉点，可比较这域交叉点，可比较这些点对应的函数值，些点对应的函数值，找出最优。找出最优。) 1, 4(2022-6-562 2 应用举例应用举例2 2.1.1 逻辑变量在数学模型中的应用逻辑变

5、量在数学模型中的应用1 1、m m个约束条件中只有个约束条件中只有k k个起作用个起作用设有设有m m个约束条件个约束条件mibxanjiijij,.,2 , 1,1定义定义0-10-1整型变量：整型变量：，10iy第第i i个约束起作用个约束起作用第第i i个约束不起作用个约束不起作用2022-6-57设设M M是任意大正数，则原约束中只有是任意大正数，则原约束中只有k k个真正个真正起作用的情况可表示为：起作用的情况可表示为：kmyyymiMybxamnjiiijij.,.,2 , 1,2112022-6-582 2、约束条件右端项是、约束条件右端项是r r个可能值中的一个个可能值中的一个

6、rnjijijbbbxa或或或或,.,211则通过定义则通过定义，10iy约束条件右端项不是约束条件右端项不是b bi i约束条件右端项是约束条件右端项是b bi i可将上述条件表示为可将上述条件表示为 1.,2111rnjriiiijijyyyybxa2022-6-593 3、两组条件中满足其中一组、两组条件中满足其中一组例如表示条件：若例如表示条件：若 ，则，则 ； 否则否则 时时则通过定义则通过定义10iy第第i i组条件起作用，组条件起作用，i=1i=1，2 2第第i i组条件不起作用组条件不起作用可将上述条件表示为可将上述条件表示为 41x, 32x, 41x, 12x其中：其中：M

7、 M是任意大正数是任意大正数134142122211211yyMyxMyxMyxMyx2022-6-510定义定义4 4、表示含有固定费用的函数、表示含有固定费用的函数例如：例如： 表示产品表示产品 的生产数量，其生产费用函数的生产数量，其生产费用函数为：为： jx目标函数：目标函数：00, 0,)(jjjjjjjxxxcKxC其中其中 是与产量无关是与产量无关的生产准备费用的生产准备费用 jKnjjjxCz1)(min10jy0jx0jx则原问题可表示为则原问题可表示为)(min1njjjjjyKxcz100.或jjjyMyxtsj2022-6-5112 2.2.2 应用举例应用举例例例1

8、1 东方大学计算机实验室聘用东方大学计算机实验室聘用4 4名大学生（代号名大学生（代号1,2,3,41,2,3,4）和）和2 2名研究生（代号名研究生（代号5,65,6）值班。已知各学生从）值班。已知各学生从周一至周五每天可安排的值班时间及每人每小时报酬见下周一至周五每天可安排的值班时间及每人每小时报酬见下表所示。表所示。2022-6-512实验室每天开放时间为实验室每天开放时间为8:00AM10:00PM,8:00AM10:00PM,共共1414小时。开放小时。开放时间内需要有一名学生值班。规定大学生每周值班时间是时间内需要有一名学生值班。规定大学生每周值班时间是815815小时，研究生是小

9、时，研究生是712712小时，每次值班不小于小时，每次值班不小于2 2小时。小时。又每名学生每周值班次数不得多于三次，每天值班人员中又每名学生每周值班次数不得多于三次，每天值班人员中至少有一名研究生，每天值班人数不超过至少有一名研究生，每天值班人数不超过3 3人。试为该实人。试为该实验室安排一张人员值班表，使得总酬金支出为最少。验室安排一张人员值班表，使得总酬金支出为最少。解：解：设设 表示学生表示学生i i在周在周j j的值班时间。的值班时间。ijx, 1, 0ijy学生学生i i在周在周j j不值班不值班学生学生i i在周在周j j值班值班 表示学生表示学生i i在周在周j j的最多可值班

10、时间。的最多可值班时间。则则目标函数目标函数：ija61i51jijixczmin2022-6-5136 , 5,127) 3(51ixjij研究生值班研究生值班7-127-12小时小时6,.,1, 3)4(51iyjij每周不超过每周不超过3 3次次5,.,1, 3)5(61jyiij每天不超过每天不超过3 3人人5,.,11)6(65jyyjj每天有一研究生每天有一研究生5,.,1, 6,.12)7(jiyaxyijijijij值班不超过每人可安排的时间值班不超过每人可安排的时间5,.1,14) 1 (61jxiij每天开放每天开放1414小时小时4,.1,158)2(51ixjij大学生

11、值班大学生值班8-158-15小时小时约约束束条条件件2022-6-514例例2 2 红星日用化工厂为发运产品，下一年度需要红星日用化工厂为发运产品，下一年度需要6 6种不同容积的包装箱，每种包装箱的需求量及生产种不同容积的包装箱，每种包装箱的需求量及生产一个的可变费用如下表所示。一个的可变费用如下表所示。由于生产不同容积包装箱时需进行专门的准备、下由于生产不同容积包装箱时需进行专门的准备、下料等，生产每一种包装箱的固定费用都是料等，生产每一种包装箱的固定费用都是12001200元。元。又若某容积的包装箱数量不够时，可用比它大的代又若某容积的包装箱数量不够时，可用比它大的代替。试问该厂应订做哪

12、几种代号的包装箱各多少个，替。试问该厂应订做哪几种代号的包装箱各多少个，可使得费用最省？可使得费用最省？2022-6-515解：解：设设 表示代号为表示代号为j j的包装箱的订做数量的包装箱的订做数量。jx，10jy不订不订j j包装箱包装箱订订j j包装箱包装箱目标函数目标函数654326112 .183 .161 .1210851200minxxxxxxyzjj约束条件约束条件6,.1,jMyxjj2022-6-51685065 xx1750654xxx24506543xxxx300065432xxxxx3500654321xxxxxx4006x6,.1, 0jxj2022-6-517例例

13、3 3（固定成本问题）（固定成本问题）高压容器公司制造小、中、大三种尺寸的金属容器，高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。每种容器售容器所需的各种资源的数量如表所示。每种容器售出一只所得的利润分别为出一只所得的利润分别为 4 4万元、万元、5 5万元、万元、6 6万元，万元，可使用的金属板有可使用的金属板有500500吨，劳动力有吨，劳动力有300300人人/ /月，机月，机器有器有100100台台/ /月，此外不管每种容器制造的数量是多月，此外不管每种容器制造的数

14、量是多少，都要支付一笔固定的费用：小号是少，都要支付一笔固定的费用：小号是l00l00万元，万元，中号为中号为 150 150 万元，大号为万元，大号为200200万元。现在要制定一万元。现在要制定一个生产计划，使获得的利润为最大。个生产计划，使获得的利润为最大。 2022-6-518解解：设设 分别为小号容器、中号容器和大号容分别为小号容器、中号容器和大号容器的生产数量。器的生产数量。 建立如下的数学模型：建立如下的数学模型：321,xxx，10jy不生产不生产j j型号容器型号容器生产生产j j型号容器型号容器2022-6-519321321200150100654maxyyyxxxZ3

15、, 2 , 11-0, 010032300432500842321321321jyxMyxxxxxxxxxxjjjj变量，变量，是是2022-6-5203 3 指派问题及匈牙利解法指派问题及匈牙利解法 3 3.1 .1 指派问题与模型指派问题与模型 m m项任务分配给项任务分配给m m个人去完成，每人只能完成其中个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配一项，每项任务只能分给一人完成，应如何分配使得效率最高？使得效率最高？ a aijij是第是第j j个人完成第个人完成第i i项任务的效率项任务的效率( (如如 时间）。时间）。2022-6-521设设于是建立模型如

16、下：于是建立模型如下： 否则项任务个人完成第第01ijxijmimjijijxaz11min1,.mji,1,01,.mj, 11,.mi, 111或ijmiijmjijxxx2022-6-5223 3.1 .1 指派问题的匈牙利解法指派问题的匈牙利解法该指派问题可当作运输问题解决，但匈牙利解法更该指派问题可当作运输问题解决，但匈牙利解法更有效。有效。解法思想：解法思想：效率矩阵的元素效率矩阵的元素 ，若有一组位于，若有一组位于不同行不同列的零元素，则令这些位置的决策变量不同行不同列的零元素，则令这些位置的决策变量取值为取值为1 1，其余均为，其余均为0 0，这显然就是最优解。，这显然就是最优

17、解。0ija2022-6-523定理定理2 2：若矩阵若矩阵A A的元素可分为的元素可分为“0”0”元和元和“非非0”0”元，元，则覆盖则覆盖“0”0”元的最少直线数等于位于不同行、不元的最少直线数等于位于不同行、不同列的同列的“0”0”元的最大个数。元的最大个数。定理定理1 1：效率矩阵效率矩阵 的每一行元素分别减去（加的每一行元素分别减去（加上）一个常数上）一个常数 ，每一列元素分别减去（加上），每一列元素分别减去（加上）一个元素一个元素 ，得新效率矩阵，得新效率矩阵 ， ，则则 的最优解等价于的最优解等价于 的最优解。的最优解。ijaiujvjiijijvuabijbijaijb2022

18、-6-524例：例：有一份说明书，要分别译成英、日、德、俄四种语言，有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高。分配任务，可使总效率最高。表中数据为完成任务所需时间（单位：小时）。表中数据为完成任务所需时间（单位：小时）。2022-6-525匈牙利解法匈牙利解法步骤：步骤：1 1、在效率矩阵每行减去该行最小元素；、在效率矩阵每行减去该行最小元素；2 2、在效率矩阵每列减去该列最小元素；、在效率矩阵每列减去该列最小元素；411429131541116141381441

19、579102591100532410011578005005411000324501152802022-6-5263 3、寻找独立、寻找独立“0”0”元素元素( (不同行不同列）不同行不同列）（1 1）从第一行开始，若该行只有一个）从第一行开始，若该行只有一个“0”0”元素，元素，则对该则对该“0”0”元素打括号（元素打括号（ ）（表示这一行的人只（表示这一行的人只有这一个任务可指派），有这一个任务可指派），并划去该并划去该“0”0”元素所在元素所在的列的列（表示该项任务不能再指派给别人）（表示该项任务不能再指派给别人） ；若该；若该行无行无“0”0”元素或有两个以上的元素或有两个以上的“0”

20、0”元素（不含划元素（不含划去的去的0 0），则转下一行；），则转下一行；（2 2）从第一列开始，若该列只有一个）从第一列开始，若该列只有一个“0”0”元素，元素，则对该则对该“0”0”元素打括号（元素打括号（ ），并划去该），并划去该“0”0”元元素所在的行；若该列无素所在的行；若该列无“0”0”元素或有两个以上的元素或有两个以上的“0”0”元素（不含划去的元素（不含划去的0 0），则转下一列；），则转下一列；2022-6-527完成上述步骤后可能出现下列情况：完成上述步骤后可能出现下列情况：）效率矩阵的每一行都有一个打括号的效率矩阵的每一行都有一个打括号的0 0元素，元素，则按照打括号的则

21、按照打括号的0 0元素位置指派任务，即是最优解；元素位置指派任务，即是最优解；2022-6-528）打括号的打括号的0 0元素个数小于元素个数小于m m，但未被划去的，但未被划去的0 0元元素之间存在闭回路，则沿此闭回路，每隔一个素之间存在闭回路，则沿此闭回路，每隔一个0 0元元打一括号，然后对打括号的打一括号，然后对打括号的0 0元素所在行或所在列元素所在行或所在列画直线；画直线；）矩阵中所有矩阵中所有0 0元素或被打括号，或被划去，但打元素或被打括号，或被划去，但打括号的括号的0 0元素个数元素个数 ，则进入下一步；，则进入下一步；m0000000)0()0(00)0(2022-6-529

22、（3 3）设法使每一行都有一个打括号的）设法使每一行都有一个打括号的“0”0”元素。元素。按按定理定理1 1继续对矩阵进行变换：继续对矩阵进行变换：）从矩阵未被直线覆盖的元素中找出最小者从矩阵未被直线覆盖的元素中找出最小者k k，）对矩阵中无直线覆盖的行，令对矩阵中无直线覆盖的行，令 ，有直，有直线覆盖的列，令线覆盖的列，令 。其余为。其余为0 0。）对矩阵的每个元素计算对矩阵的每个元素计算 ，得到，得到一个新矩阵，转第三步重复进行，直至每一行都有一个新矩阵，转第三步重复进行，直至每一行都有一打括号的一打括号的0 0元素。元素。kuikvjjiijvua2022-6-530根据上图，根据上图，

23、k=2k=2，002254110003245011528020223211000542301130803211)0()0(05423)0(113)0(80最优解：最优解：2811944, 1, 1, 1, 134132241zxxxx2022-6-531两点说明：两点说明：1 1、任务数、任务数 人数人数 时如何处理时如何处理增加虚拟的人或虚拟的任务增加虚拟的人或虚拟的任务 2 2、指派问题中目标函数变为、指派问题中目标函数变为MAXMAX时如何处理时如何处理 。每行每列找最大者，用此最大元素减去相应各行各每行每列找最大者，用此最大元素减去相应各行各列的元素，得到同解矩阵。列的元素，得到同解矩

24、阵。2022-6-5324 4 分枝定界法分枝定界法 分枝定界法分枝定界法是求解整数规划的一种常用的有效的是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定大多数求解整数规划的商用软件就是基于分枝定界法编制而成的。界法编制而成的。下面举例来说明分枝定界法的思想和步骤。下面举例来说明分枝定界法的思想和步骤。2022-6-5331 1、求解整数规划相应的一般线性规划问题（即先、求解整数规划相应的一般线性规划问题（即先去掉整数约束）。去掉整数约束）。易知

25、：整数规划的可行域（小）包含于线性规划的易知：整数规划的可行域（小）包含于线性规划的可行域可行域 ( (大）。大）。 若线性规划的最优解恰是整数解，则其就是整若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。解的上界或下界。例例 求解下列整数规划：求解下列整数规划：并取整数并取整数, 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz2022-6-5340,5 . 45 . 01432.23max21212121xxxxxxtsxxz解：解：1 1、解对应的线性规划：、

26、解对应的线性规划：其最优解为其最优解为 ，显然不是整数规划的可行解。显然不是整数规划的可行解。L0：75.140z)5 . 2,25. 3(2022-6-535性质性质 求求MAXMAX的问题的问题：整数规划的最优目标函数值整数规划的最优目标函数值小小于或等于于或等于相应的线性规划的最优目标函数值；相应的线性规划的最优目标函数值； 求求MINMIN的问题：整数规划的最优目标函数值的问题：整数规划的最优目标函数值大大于或等于于或等于相应的线性规划的最优目标函数值。相应的线性规划的最优目标函数值。2 2、分枝与定界：、分枝与定界： 将对应的线性规划问题分解成几个子问题，每将对应的线性规划问题分解成

27、几个子问题，每个子问题就是一分枝，而所有子问题的解集之和个子问题就是一分枝，而所有子问题的解集之和要包含原整数规划的解集。要包含原整数规划的解集。2022-6-536求解每一分枝子问题：求解每一分枝子问题： 若其最优解满足整数约束，则它就是原问题的若其最优解满足整数约束，则它就是原问题的一个可行解（不一定是最优）；否则，就是该枝的一个可行解（不一定是最优）；否则，就是该枝的上界或下界。上界或下界。 若所有分支的最优解都不满足整数条件（即不若所有分支的最优解都不满足整数条件（即不是原问题的可行解），则选取一个边界值最优的分是原问题的可行解），则选取一个边界值最优的分支继续分解，直至找到一个原问题

28、的可行解。支继续分解，直至找到一个原问题的可行解。 若在同一级分枝中同时出现两个以上的原问题若在同一级分枝中同时出现两个以上的原问题可行解，则保留目标值最优的一个，其余不再考虑。可行解，则保留目标值最优的一个，其余不再考虑。从各分枝中找原问题可行解的目的是为下一步的比从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。较与剪枝。2022-6-537将上述线性规划问题分为两枝，并求解。将上述线性规划问题分为两枝，并求解。5 .14, 2, 5 . 3121zxx解得解得5 .13, 3, 5 . 2221zxx解得解得L1：L2：0,25 . 45 . 01432.23max212212121

29、xxxxxxxtsxxz0,35 . 45 . 01432.23max212212121xxxxxxxtsxxz显然两个分枝均非整数可行解，选边界值较大的显然两个分枝均非整数可行解，选边界值较大的L L1 1继续分枝。继续分枝。 2022-6-538将将L1L1分为两枝，并求解。分为两枝，并求解。13, 2, 3121zxx解得解得14, 1, 4221zxx解得解得L11：L12：0,325 . 45 . 01432.23max2112212121xxxxxxxxtsxxz两个分枝均是整数可行解，保留目标值较大的两个分枝均是整数可行解，保留目标值较大的L L1212。 0,425 . 45

30、. 01432.23max2112212121xxxxxxxxtsxxz2022-6-5393 3、比较与剪枝比较与剪枝 将各子问题的边界值与保留下的整数可行解对将各子问题的边界值与保留下的整数可行解对应的目标值比较，将边界值劣于可行行解的分支减应的目标值比较，将边界值劣于可行行解的分支减剪去。剪去。 若比较剪枝后，只剩下所保留的整数可行解，则若比较剪枝后，只剩下所保留的整数可行解，则该解就是原整数规划的最优解；否则选取边界值最该解就是原整数规划的最优解；否则选取边界值最大的一个分枝继续分解，在其后的过程中出现新的大的一个分枝继续分解，在其后的过程中出现新的整数可行解时，则与原可行解比较，保留

31、较优的一整数可行解时，则与原可行解比较，保留较优的一个，重复第三步。个，重复第三步。2022-6-540L0：X22X23X13X14用图表示上例的求解过程与求解结果用图表示上例的求解过程与求解结果75.14, 5 . 2,25. 3121zxx5 .14, 2, 5 . 3121zxx5 .13, 3, 5 . 2221zxx13, 2, 3121zxx14, 1, 4221zxx2022-6-5415 5 割平面法割平面法 5 5.1.1 基本思想基本思想 在整数规划的松弛问题中，依次引进新的约束条在整数规划的松弛问题中，依次引进新的约束条件（割平面），使问题的可行域逐步减小，但每件（割平

32、面），使问题的可行域逐步减小，但每次割去的只是部分非整数解，直到使问题的目标次割去的只是部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后的可行域的函数值达到最优的整数点成为缩小后的可行域的一个顶点，这样就可以用线性规划的方法求得整一个顶点，这样就可以用线性规划的方法求得整数最优解。数最优解。2022-6-542例例 求解下列整数规划：求解下列整数规划：并取整数并取整数, 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz0,921432.23max21212121xxxxxxtsxxz解：解：1 1、解对应的线性规划（松弛问题），并将、解对应的线性规划（松弛问题），并将约束条件的系数均化为整数：约束条件的系数均化为整数：2022-6-543加入松弛变量后求解，得最终单纯形表：加入松弛变量后求解，得最终单纯形表：1x4x3x1x2x