运筹整数规划素材PPT课件

1、2022-7-21第四章 整数规划与分配问题 整数规划的有关概念及特点 整数规划的应用 指派问题及匈牙利解法 整数规划的求解方法：分枝定界法、割平面法 第1页/共51页2022-7-22纯整数规划：在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；混合整数规划：如果有一部分变量为非负整数，则称之为混合整数规划问题。0-1变量：在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。0-1规划：在整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。1 整数规划的有关概念及特点1.1 概念整数规划：整数规划： 要求决策变量取整数值的规划问题。要求决策变

2、量取整数值的规划问题。 （线性整数规划、非线性整数规划等）（线性整数规划、非线性整数规划等）第2页/共51页2022-7-23求整数解的线性规划问题，不是用四舍五入法或去尾法对性规划的非整数解加以处理就能解决的，用枚举法又往往会计算量太大，所以要用整数规划的特定方法加以解决。例： 求解下列整数规划：1.2 整数规划的求解特点并取整数并取整数, 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz第3页/共51页2022-7-241x2x143221 xx5 . 45 . 021xx2123xxz)5 . 2,25. 3(分析：分析： 若当作一般线性规划求若当作一般

3、线性规划求解，图解法的结果如下。解，图解法的结果如下。1、非整数规划、非整数规划最优解最优解 显然不是整数规划的可行解。显然不是整数规划的可行解。2、四舍五入后的结果四舍五入后的结果 也不是整数规划的可行解。也不是整数规划的可行解。)5 . 2,25. 3()3, 3(3、可行解是阴影区可行解是阴影区域交叉点，可比较这域交叉点，可比较这些点对应的函数值，些点对应的函数值，找出最优。找出最优。) 1, 4(第4页/共51页2022-7-252 应用举例2.1 逻辑变量在数学模型中的应用1 1、m m个约束条件中只有个约束条件中只有k k个起作用个起作用设有设有m m个约束条件个约束条件mibxa

4、njiijij,.,2 , 1,1定义定义0-10-1整型变量：整型变量：，10iy第第i i个约束起作用个约束起作用第第i i个约束不起作用个约束不起作用第5页/共51页2022-7-26设设M M是任意大正数，则原约束中只有是任意大正数，则原约束中只有k k个真正个真正起作用的情况可表示为：起作用的情况可表示为：kmyyymiMybxamnjiiijij.,.,2 , 1,211第6页/共51页2022-7-272 2、约束条件右端项是、约束条件右端项是r r个可能值中的一个个可能值中的一个rnjijijbbbxa或或或或,.,211则通过定义则通过定义，10iy约束条件右端项不是约束条件

5、右端项不是b bi i约束条件右端项是约束条件右端项是b bi i可将上述条件表示为可将上述条件表示为 1.,2111rnjriiiijijyyyybxa第7页/共51页2022-7-283 3、两组条件中满足其中一组、两组条件中满足其中一组例如表示条件：若例如表示条件：若 ，则，则 ； 否则否则 时时则通过定义则通过定义10iy第第i i组条件起作用，组条件起作用，i=1i=1，2 2第第i i组条件不起作用组条件不起作用可将上述条件表示为可将上述条件表示为 41x, 32x, 41x, 12x其中：M是任意大正数134142122211211yyMyxMyxMyxMyx第8页/共51页20

6、22-7-29定义定义4 4、表示含有固定费用的函数、表示含有固定费用的函数例如：例如： 表示产品表示产品 的生产数量，其生产费用函数的生产数量，其生产费用函数为：为： jx目标函数：00, 0,)(jjjjjjjxxxcKxC其中其中 是与产量无关是与产量无关的生产准备费用的生产准备费用 jKnjjjxCz1)(min10jy0jx0jx则原问题可表示为则原问题可表示为)(min1njjjjjyKxcz100.或jjjyMyxtsj第9页/共51页2022-7-2102.2 应用举例例例1 1 东方大学计算机实验室聘用东方大学计算机实验室聘用4 4名大学生（代号名大学生（代号1,2,3,41

7、,2,3,4）和）和2 2名研究生（代号名研究生（代号5,65,6）值班。已知各学生从）值班。已知各学生从周一至周五每天可安排的值班时间及每人每小时报酬见下周一至周五每天可安排的值班时间及每人每小时报酬见下表所示。表所示。学生学生代号代号酬金酬金(元元/h)每天可安排的值班时间每天可安排的值班时间(h)周一周一周二周二周三周三周四周四周五周五110.060607210.00606339.94830549.855640510.830460611.306244第10页/共51页2022-7-211实验室每天开放时间为实验室每天开放时间为8:00AM10:00PM,8:00AM10:00PM,共共1

8、414小时。开放小时。开放时间内需要有一名学生值班。规定大学生每周值班时间是时间内需要有一名学生值班。规定大学生每周值班时间是815815小时，研究生是小时，研究生是712712小时，每次值班不小于小时，每次值班不小于2 2小时。小时。又每名学生每周值班次数不得多于三次，每天值班人员中又每名学生每周值班次数不得多于三次，每天值班人员中至少有一名研究生，每天值班人数不超过至少有一名研究生，每天值班人数不超过3 3人。试为该实人。试为该实验室安排一张人员值班表，使得总酬金支出为最少。验室安排一张人员值班表，使得总酬金支出为最少。解：解：设设 表示学生表示学生i i在周在周j j的值班时间。的值班时

9、间。ijx, 1, 0ijy学生学生i i在周在周j j不值班不值班学生学生i i在周在周j j值班值班 表示学生表示学生i i在周在周j j的最多可值班时间。的最多可值班时间。则则目标函数目标函数：ija61i51jijixczmin第11页/共51页2022-7-2126 , 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(jiyaxyijiji

10、jij值班不超过每人可安排的时间值班不超过每人可安排的时间5,.1,14) 1 (61jxiij每天开放每天开放1414小时小时4,.1,158)2(51ixjij大学生值班大学生值班8-158-15小时小时约束条件第12页/共51页2022-7-213例例2 2 红星日用化工厂为发运产品，下一年度需要红星日用化工厂为发运产品，下一年度需要6 6种不同容积的包装箱，每种包装箱的需求量及生产种不同容积的包装箱，每种包装箱的需求量及生产一个的可变费用如下表所示。一个的可变费用如下表所示。包装箱代号包装箱代号123456容积（容积（m3）0.080.100.120.150.200.25需求量（个）需

11、求量（个）500550700900450400可变费用（元可变费用（元/个）个）5.08.010.012.116.318.2由于生产不同容积包装箱时需进行专门的准备、下由于生产不同容积包装箱时需进行专门的准备、下料等，生产每一种包装箱的固定费用都是料等，生产每一种包装箱的固定费用都是12001200元。元。又若某容积的包装箱数量不够时，可用比它大的代又若某容积的包装箱数量不够时，可用比它大的代替。试问该厂应订做哪几种代号的包装箱各多少个，替。试问该厂应订做哪几种代号的包装箱各多少个，可使得费用最省？可使得费用最省？第13页/共51页2022-7-214解：解：设设 表示代号为表示代号为j j的

12、包装箱的订做数量的包装箱的订做数量。jx，10jy不订不订j j包装箱包装箱订订j j包装箱包装箱目标函数654326112 .183 .161 .1210851200minxxxxxxyzjj约束条件6,.1,jMyxjj第14页/共51页2022-7-21585065 xx1750654xxx24506543xxxx300065432xxxxx3500654321xxxxxx4006x6,.1, 0jxj第15页/共51页2022-7-216例3 3（固定成本问题）高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。每

13、种容器售出一只所得的利润分别为 4 4万元、5 5万元、6 6万元，可使用的金属板有500500吨，劳动力有300300人/ /月，机器有100100台/ /月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00l00万元，中号为 150 150 万元，大号为200200万元。现在要制定一个生产计划，使获得的利润为最大。 第16页/共51页2022-7-217解：设 分别为小号容器、中号容器和大号容器的生产数量。 建立如下的数学模型：资源资源小号容器小号容器中号容器中号容器大号容器大号容器金属板（吨）金属板（吨）248劳动力（人月）劳动力（人月）234机器设备（台月）机器设

14、备（台月）123321,xxx，10jy不生产不生产j j型号容器型号容器生产生产j j型号容器型号容器第17页/共51页2022-7-218321321200150100654maxyyyxxxZ3 , 2 , 11-0, 010032300432500842321321321jyxMyxxxxxxxxxxjjjj变量，变量，是是第18页/共51页2022-7-2193 指派问题及匈牙利解法 3.1 指派问题与模型 m m项任务分配给项任务分配给m m个人去完成，每人只能完成其中个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配一项，每项任务只能分给一人完成，应如何分配使

15、得效率最高？使得效率最高？ a aijij是第是第j j个人完成第个人完成第i i项任务的效率项任务的效率( (如如 时间）。时间）。 人人任务任务12 m1a11a12a1m2a21a22a2mmam1am2amm第19页/共51页2022-7-220设设于是建立模型如下：于是建立模型如下： 否则项任务个人完成第第01ijxijmimjijijxaz11min1,.mji,1,01,.mj, 11,.mi, 111或ijmiijmjijxxx第20页/共51页2022-7-2213.1 指派问题的匈牙利解法该指派问题可当作运输问题解决，但匈牙利解法更该指派问题可当作运输问题解决，但匈牙利解法

16、更有效。有效。解法思想：解法思想：效率矩阵的元素效率矩阵的元素 ，若有一组位于，若有一组位于不同行不同列的零元素，则令这些位置的决策变量不同行不同列的零元素，则令这些位置的决策变量取值为取值为1 1，其余均为，其余均为0 0，这显然就是最优解。，这显然就是最优解。0ija第21页/共51页2022-7-222定理定理2 2：若矩阵若矩阵A A的元素可分为的元素可分为“0”0”元和元和“非非0”0”元，元，则覆盖则覆盖“0”0”元的最少直线数等于位于不同行、不元的最少直线数等于位于不同行、不同列的同列的“0”0”元的最大个数。元的最大个数。定理定理1 1：效率矩阵效率矩阵 的每一行元素分别减去（

17、加的每一行元素分别减去（加上）一个常数上）一个常数 ，每一列元素分别减去（加上），每一列元素分别减去（加上）一个元素一个元素 ，得新效率矩阵，得新效率矩阵 ， ，则则 的最优解等价于的最优解等价于 的最优解。的最优解。ijaiujvjiijijvuabijbijaijb第22页/共51页2022-7-223例：例：有一份说明书，要分别译成英、日、德、俄四种语言，有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高。分配任务，可使总效率最高。表中数据为完成任务所需时间（单位：小

18、时）。表中数据为完成任务所需时间（单位：小时）。 人任务甲乙丙丁英文21097日文154148德文13141611俄文415139第23页/共51页2022-7-224匈牙利解法匈牙利解法步骤：步骤：1 1、在效率矩阵每行减去该行最小元素；、在效率矩阵每行减去该行最小元素；2 2、在效率矩阵每列减去该列最小元素；、在效率矩阵每列减去该列最小元素；41142913154111614138144157910259110053241001157800500541100032450115280第24页/共51页2022-7-2253、寻找独立“0”元素(不同行不同列）（1）从第一行开始，若该行只有一个

19、“0”元素，则对该“0”元素打括号（ ）（表示这一行的人只有这一个任务可指派），并划去该“0”元素所在的列（表示该项任务不能再指派给别人） ；若该行无“0”元素或有两个以上的“0”元素（不含划去的0），则转下一行；（2）从第一列开始，若该列只有一个“0”元素，则对该“0”元素打括号（ ），并划去该“0”元素所在的行；若该列无“0”元素或有两个以上的“0”元素（不含划去的0），则转下一列；第25页/共51页2022-7-226（0）82511（0）5423（0）001145完成上述步骤后可能出现下列情况：）效率矩阵的每一行都有一个打括号的0元素，则按照打括号的0元素位置指派任务，即是最优解；第2

20、6页/共51页2022-7-227）打括号的0元素个数小于m，但未被划去的0元素之间存在闭回路，则沿此闭回路，每隔一个0元打一括号，然后对打括号的0元素所在行或所在列画直线；）矩阵中所有0元素或被打括号，或被划去，但打括号的0元素个数 ，则进入下一步；m0000000)0()0(00)0(第27页/共51页2022-7-228（3）设法使每一行都有一个打括号的“0”元素。按定理1继续对矩阵进行变换：）从矩阵未被直线覆盖的元素中找出最小者k，）对矩阵中无直线覆盖的行，令 ，有直线覆盖的列，令 。其余为0。）对矩阵的每个元素计算 ，得到一个新矩阵，转第三步重复进行，直至每一行都有一打括号的0元素。

21、kuikvjjiijvua第28页/共51页2022-7-229（0）82511（0）5423（0）001145根据上图，k=2，002254110003245011528020223211000542301130803211)0()0(05423)0(113)0(80最优解：2811944, 1, 1, 1, 134132241zxxxx第29页/共51页2022-7-230两点说明：1、任务数 人数 时如何处理增加虚拟的人或虚拟的任务 2、指派问题中目标函数变为MAX时如何处理 。每行每列找最大者，用此最大元素减去相应各行各列的元素，得到同解矩阵。第30页/共51页2022-7-2314

22、分枝定界法 分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法编制而成的。下面举例来说明分枝定界法的思想和步骤。第31页/共51页2022-7-2321、求解整数规划相应的一般线性规划问题（即先去掉整数约束）。易知：整数规划的可行域（小）包含于线性规划的可行域 (大）。 若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。例 求解下列整数规划：并取整数并取整数, 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz第3

23、2页/共51页2022-7-2330,5 . 45 . 01432.23max21212121xxxxxxtsxxz解：1、解对应的线性规划：其最优解为 ，显然不是整数规划的可行解。L0：75.140z)5 . 2,25. 3(第33页/共51页2022-7-234性质 求MAX的问题：整数规划的最优目标函数值小于或等于相应的线性规划的最优目标函数值； 求MIN的问题：整数规划的最优目标函数值大于或等于相应的线性规划的最优目标函数值。2、分枝与定界： 将对应的线性规划问题分解成几个子问题，每个子问题就是一分枝，而所有子问题的解集之和要包含原整数规划的解集。第34页/共51页2022-7-235

24、求解每一分枝子问题： 若其最优解满足整数约束，则它就是原问题的一个可行解（不一定是最优）；否则，就是该枝的上界或下界。 若所有分支的最优解都不满足整数条件（即不是原问题的可行解），则选取一个边界值最优的分支继续分解，直至找到一个原问题的可行解。 若在同一级分枝中同时出现两个以上的原问题可行解，则保留目标值最优的一个，其余不再考虑。从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。第35页/共51页2022-7-236将上述线性规划问题分为两枝，并求解。5 .14, 2, 5 . 3121zxx解得5 .13, 3, 5 . 2221zxx解得L1：L2：0,25 . 45 . 01432.

25、23max212212121xxxxxxxtsxxz0,35 . 45 . 01432.23max212212121xxxxxxxtsxxz显然两个分枝均非整数可行解，选边界值较大的显然两个分枝均非整数可行解，选边界值较大的L L1 1继续分枝。继续分枝。 第36页/共51页2022-7-237将L1L1分为两枝，并求解。13, 2, 3121zxx解得14, 1, 4221zxx解得L11：L12：0,325 . 45 . 01432.23max2112212121xxxxxxxxtsxxz两个分枝均是整数可行解，保留目标值较大的两个分枝均是整数可行解，保留目标值较大的L L1212。 0,

26、425 . 45 . 01432.23max2112212121xxxxxxxxtsxxz第37页/共51页2022-7-2383、比较与剪枝 将各子问题的边界值与保留下的整数可行解对应的目标值比较，将边界值劣于可行行解的分支减剪去。 若比较剪枝后，只剩下所保留的整数可行解，则该解就是原整数规划的最优解；否则选取边界值最大的一个分枝继续分解，在其后的过程中出现新的整数可行解时，则与原可行解比较，保留较优的一个，重复第三步。第38页/共51页2022-7-239L0：X22X23X13X14用图表示上例的求解过程与求解结果75.14, 5 . 2,25. 3121zxx5 .14, 2, 5 .

27、 3121zxx5 .13, 3, 5 . 2221zxx13, 2, 3121zxx14, 1, 4221zxx第39页/共51页2022-7-2405 割平面法 5.1 基本思想 在整数规划的松弛问题中，依次引进新的约束条在整数规划的松弛问题中，依次引进新的约束条件（割平面），使问题的可行域逐步减小，但每件（割平面），使问题的可行域逐步减小，但每次割去的只是部分非整数解，直到使问题的目标次割去的只是部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后的可行域的函数值达到最优的整数点成为缩小后的可行域的一个顶点，这样就可以用线性规划的方法求得整一个顶点，这样就可以用线性规划的方法求

28、得整数最优解。数最优解。第40页/共51页2022-7-241例 求解下列整数规划：并取整数并取整数, 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz0,921432.23max21212121xxxxxxtsxxz解：1、解对应的线性规划（松弛问题），并将约束条件的系数均化为整数：第41页/共51页2022-7-242加入松弛变量后求解，得最终单纯形表：25/2011/2-1/2313/410-1/43/400-1/4-5/41x4x3x1x2x2xj如果上述求解结果是整数解，则结束；否则转下一步；2、找出非整数解中分数部分最大的一个基变量，并将该行对应的约束方程所有常数（系数及常数项）分解成一个整数与一个正分数之和；将所有分式项移到等式右端。例如上例，取第一行约束. 第42页/共51页2022-7-24343424324322121212212)211(21252121xxxxxxxxxx易知，左端为整数，要是等式成立，右端也必为整数，且02121211212121214343xxxx将 代入上式，得214213293214xxxxxx112221 xx第