整数规划

第五章整数规划IntegerProgramming第1节数学模型一、整数规划的含义要求一部分或全部决策变量必须取整数值的规划问题。第1节数学模型整数规划的松弛问题不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。若松弛问题是一个线性规划，则称该整数规划为整数线性规划。第1节数学模型整数线性规划的数学模型1112max(min)()12012njjjnijjijjnzcxaxbimxjnxxx或或，或，，，，，，，，，，，中部分或全部取整数第1节数学模型整数线性规划问题的类型（1）纯（全）整数线性规划：全部决策变量都必须取整数值的整数线性规划（2）混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划（3）0-1型整数线性规划：决策变量只能取值0或1的整数线性规划第1节数学模型二、整数规划的解的特点整数规划问题的可行域是它的松弛问题可行域的子集整数规划问题的可行解是它的松弛问题的可行解整数规划问题最优解的目标函数值不优于它的松弛问题最优解的目标函数值第1节数学模型三、整数规划的解法例1：某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所示。问两种货物各托运多少箱，可使获得利润为最大？货物体积（米3/箱）重量（百公斤/箱）利润（百元/箱）甲5220乙4510托运限制2413第1节数学模型例1：解：设x1，x2分别为甲、乙两种货物的托运箱数maxz=20x1+10x25x1+4x2≤242x1+5x2≤13x1，x2≥0x1，x2整数第1节数学模型A松弛问题的最优解第1节数学模型A整数问题的最优解第1节数学模型完全枚举法对于可行域有界的整数规划问题，整数规划的可行解是一个有限集，将这个集内的每一个点对应的目标函数值都一一计算出来，然后从中找出最优者，则为整数规划的最优解。第1节数学模型小结（1）对整数规划问题的松弛问题的最优解进行取整，所得到的整数解可能不是整数规划问题的最优解，也可能不是可行解（2）对于复杂的模型，完全枚举法费时，甚至不可能实现作业13作业13：对下列整数规划问题，要求先解相应的松弛问题，并求出最优解，然后用完全枚举法求最优整数解。1、maxz=3x1+2x22x1+3x2≤14.54x1+x2≤16.5x1，x2≥0x1，x2整数3、maxz=40x1+90x29x1+7x2≤567x1+20x2≤70x1，x2≥0x1，x2整数2、maxz=7x1+9x2-x1+3x2≤67x1+x2≤35x1，x2≥0x1，x2整数作业13答案1、2、3、15.513zz（3.5，2.5）（3，2）6355zz（4.5，3.5）（4，3）46620131340zz（630131，238131）（4，2）第2节0-1型整数规划一、0-1型变量的含义变量只能取值0或1。第2节0-1型整数规划二、0-1型变量的特点表示是或否表示系统是否处于某个特定状态表示决策时是否取某个特定方案当问题含有多项要素，每项要素都有两种选择第2节0-1型整数规划例2：现有资金总额为B。可供选择的投资项目有7个，项目j所需投资额和预期收益分别为aj和cj(j=1,2,…,7)。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和4中至少选择一个；第三，项目5，6和7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？第2节0-1型整数规划例2：解：1120jjxjnj，对项目投资设（，，，），对项目不投资112134567max120112njjjnjjjjzcxaxBxxxxxxxxjn或（=,,,）第3节指派问题一、指派问题的标准形式含义：将n项工作交给n个人去做，由于每个人做每一项工作所用的时间等成本不同，指派问题的目标是如何安排工作，使总的时间等成本最小。标准形式：有n个人和n件事，已知第i人做第j事的费用为cij(i,j=1,2,…,n)，要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最少。基本要求：在满足特定的指派要求条件下，使指派方案的总体效果最佳。第3节指派问题二、指派问题的假设条件执行工作的人数和要完成的工作数量是相同的每个人只能做一件工作每件工作只能由一个人来完成第i(i=1,2,…,n)个人完成第j(j=1,2,…,n)项工作所需的成本是cij目标是如何分配工作，使总的成本最小第3节指派问题例3：有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表所示。问应指派何人去完成何工作，使所需总时间最少。任务人员EJGR甲乙丙丁2151341041415914161378119第3节指派问题例3：解：10ijijxij，指派第人去完成第项工作设，不指派第人去完成第项工作111243444141min2151191123411234011234ijjijijzxxxxxixjxij（=，，，）（=，，，）或（，=，，，）第3节指派问题三、指派问题的数学模型系数矩阵：C=(cij)n×n（1）矩阵C表示费用、成本、时间等（2）元素cij表示指派第i人去完成第j项任务时的费用（或时间、成本等）第3节指派问题数学模型111110min1(12)1(12)01(12)ijijnnijijijnijjnijiijxijxijzcxxinxjnxijn引入决策变量：，指派第人做第项工作，不指派第人做第项工作数学模型：，，，，，，或，，，，第3节指派问题解矩阵：X=(xij)n×n（1）矩阵每行各元素中都有且只有一个1，表示每个人必做且只做一件事（2）矩阵每列各元素中都有且只有一个1，表示每件事必有且只有一个人去做（3）有n!个可行解第3节指派问题数学模型的特点（1）特殊的0-1型整数规划问题（2）特殊的运输问题第3节指派问题四、指派问题的解题方法—匈牙利法解题思路（1）若从指派问题的系数矩阵（cij）的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵（cij′），则以（cij）和（cij′）为系数矩阵的两个指派问题有相同的最优解（2）独立0元素：位于不同行不同列的0元素（3）若在系数矩阵中找到n个独立0元素，则对应的指派方案总费用（或时间、成本等）为零，即为原指派问题的最优解第3节指派问题匈牙利法的解题步骤1、变换系数矩阵。具体做法：1）从系数矩阵的每行元素减去该行的最小元素。2）再从所得的系数矩阵的每列元素减去该列的最小元素。变换后，指派问题的系数矩阵中每行及每列都出现0元素，同时不出现负元素，得新的系数矩阵。第3节指派问题2、在变换后的系数矩阵中确定独立0元素。具体做法：1）从只有1个0元素的行开始，给这个0元素加圈，记作◎，然后划去◎所在列的其它0元素，记作Φ。2）给只有1个0元素的列的0元素加圈，记作◎，然后划去◎所在行的其它0元素，记作Φ。3）重复1～2，直到所有0元素都被圈出或划掉为止，◎元素即为独立0元素。4）若◎元素有n个，则已得最优解；若◎元素少于n，则转入3。最优解矩阵：独立0元素对应位置上的元素为1，其他元素为0。第3节指派问题例3：解：最优解为z*=284400010100()10000010ijx第3节指派问题3、用最少的直线覆盖所有0元素，以确定该系数矩阵中能找出最多的独立0元素。具体作法：1）对没有◎元素的行打‘√’号。2）对已打‘√’号的行中所有Φ元素所在的列打‘√’号。3）再对打‘√’号的列中所有◎元素所在的行打‘√’号。4）重复2～3，直到得不出新的打‘√’号的行和列为止。5）对没有打‘√’号的行划一横线，对已打‘√’号的列划一竖线，得到覆盖所有0元素的最少直线数。6）若直线数少于n，则转入4；若直线数等于n，而◎元素少于n，则回到2，另行试指派。矩阵中独立0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。第3节指派问题4、继续变换系数矩阵。具体作法：1）在没有被直线覆盖的元素中找出最小元素。2）打‘√’号的行的各元素减去最小元素。3）打‘√’号的列的各元素加上最小元素。4）得新的系数矩阵，重复2，若找出n个独立0元素，则得最优解；否则返回3，重复3～4。第3节指派问题例4：求下表所示系数矩阵的指派问题的最小解。任务人员ABCDE甲乙丙丁戊1279798966671712149151466104107109第3节指派问题例4：解：多重最优解，为z*=325555010000100000000000()()00001001100100000000100001100010ijijxx或第3节指派问题小结（1）当指派问题的系数矩阵经过变换，遇到在所有的行和列中，0元素都不止一个时，可任选其中一个0元素加圈，并同时划去同行和同列中其他0元素。其最优解为多重最优解（2）匈牙利法充分利用指派问题的特殊性质，有效地减少计算量第3节指派问题例5：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai(i=1,2,…,5)对新商店Bj(j=1,2,…,5)的建造费用的报价（万元）为cij(i,j=1,2,…,5)，如下表所示。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？BjAiB1B2B3B4B5A1A2A3A4A548715127917141069128767146106912106第3节指派问题例5：解：最优解为z*=34550010001000()100000001000001ijx第3节指派问题五、非标准形式的指派问题处理方法：将非标准形式转化为标准形式，然后应用匈牙利法求解。最大化指派问题设最大化指派问题系数矩阵C=(cij)n×n，令矩阵B=(bij)n×n=(M-cij)n×n，其中M是足够大的正数（通常选M=max{cij}），则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化指派问题有相同最优解。第3节指派问题例6：某建筑公司所属五个工程队，现有五项工程需要该公司承包。考虑各方面原因，规定每个工程队只能包其中一项工程，由于各队施工质量和技术水平的差异，其承包后各队的报酬不同，如下表所示。试问如何分配任务，使得该建筑公司获得最好的经济效益？项目施工队ABCDEⅠⅡⅢⅣⅤ17797989666717121412151466104107106第3节指派问题例6：解：转化为求极小化问题，系数矩阵为55010810898111111()100535231111713710711ijc第3节指派问题最优解为z*=60551000000100()010000000100010ijx’第3节指派问题人数和事数不等的指派问题若人少事多，则添上一些虚拟的“人”，虚拟的“人”做各事的费用cij取“0”，表示这些费用实际上不会发生；若人多事少，则添上一些虚拟的“事”，虚拟的“事”被各人做的费用cij仍取“0”。第3节指派问题例7：求下列系数矩阵的最小化指派问题。10114287111014125691214131511107第3节指派问题例7：解：转化为平衡指派问题，系数矩阵为551011428711101412()569121000004131511107ijc第3节指派问题最优解为z*=2255000101000