《运筹学与系统分析：第3章 整数规划》由会员分享，可在线阅读，更多相关《运筹学与系统分析：第3章 整数规划（43页珍藏版）》请在金锄头文库上搜索。
1、第三章 整数规划主要内容主要内容整数规划的数学模型及解的特点分枝定界法0-1型整数规划指派问题一、整数规划数学模型的一般形式一、整数规划数学模型的一般形式整数整数线性性规划可分划可分为：（1）纯整数整数线性性规划：全部划：全部变量必量必须取整数的取整数的线性性规划；划；（2）混合整数）混合整数线性性规划：部分划：部分变量必量必须取整数的取整数的线性性规划；划；（3）0-1整数整数线性性规划：划：变量只能取量只能取0或或1的整数的整数线性性规划。划。Max(或 Min)整数规划的整数规划的松弛问题松弛问题：不考虑整数条件的线性规划问题。：不考虑整数条件的线性规划问题。二、整数规划的例子二、整数规
2、划的例子例1：某服务部门各时段（每2h为一个时段）需要的服务员人数如下表，按规定，服务员连续工作8h（4个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。时段12345678服务员最少人数10891113853解：设在第 j时段开始时上班的服务员人数为 xj。由于第 j时段开始时上班的服务员在第(j+3)时段结束时下班，故决策变量只需要考虑x1x5。问题的数学模型为：例例2：现有有资金金总额为B。可供。可供选择的投的投资项目有目有n个，个，项目目j所所需投需投资额和和预期收益分期收益分别为 aj和和 cj（j=1,2,n）。由于某些）。由于某些原因，有三个附加条件，第一，若
3、原因，有三个附加条件，第一，若选择项目目1，就必，就必须同同时选择项目目2，反之，反之则不一定；第二，不一定；第二，项目目3和和项目目4中至少中至少选择一一个；第三，个；第三，项目目5，6，7中恰好中恰好选择2个。个。问应如何如何选择投投资项目，使得目，使得总预期收益最大？期收益最大？解：每个投资项目都有被选择和不被选择的可能，因此令该整数规划数学模型可表示为此为0-1整数规划问题。例例3：工厂：工厂A1和和A2生生产某种物某种物资。由于。由于该种物种物资供不供不应求，求，故故计划再建一家工厂。划再建一家工厂。现有有A3，A4两个建厂方案，只能两个建厂方案，只能选择一个方案。一个方案。这种物种
4、物资的需求地有的需求地有B1，B2，B3，B4四个。各工四个。各工厂年生厂年生产能力、各地年需求量、各厂至各需求地的能力、各地年需求量、各厂至各需求地的单位物位物资运运费cij（i, j=1,2,3,4）见下表。工厂下表。工厂A3，A4每年的生每年的生产费用用估估计分分别为1200万元和万元和1500万元。万元。问应建工厂建工厂A3还是是A4，使，使每年每年总费用（全部物用（全部物资运运费与新工厂生与新工厂生产费用）最少？用）最少？cij(万万/kt)B1B2B3B4生产能力生产能力ktA12934400A28357600A37612200A44525200需求量需求量kt3504003001
5、50解：解：设xij为由由Ai工厂运往工厂运往Bj需求地的物需求地的物资数量数量(单位位kt)，A3和和A4只能只能选择一个方案，引入一个方案，引入0-1变量量则问题的数学模型为：则问题的数学模型为：三、整数规划解的特点三、整数规划解的特点(1)整数规划问题的可行解集合是它的松弛问题可行整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集；解集合的一个子集；(2)整数规划问题的可行解一定也是它的松弛问题的整数规划问题的可行解一定也是它的松弛问题的可行解，反之则不一定，因此整数规划最优解的可行解，反之则不一定，因此整数规划最优解的目标函数值不会优于其松弛问题最优解的目标函目标函数值不会优于
6、其松弛问题最优解的目标函数值。数值。(3)松弛问题的最优解一般不会刚好满足整数约束条松弛问题的最优解一般不会刚好满足整数约束条件，因此对松弛问题最优解简单地取整，所得到件，因此对松弛问题最优解简单地取整，所得到的解不一定是整数规划的最优解，甚至也不一定的解不一定是整数规划的最优解，甚至也不一定是整数规划的可行解。是整数规划的可行解。例例4：用：用图解法求解下面整数解法求解下面整数规划划问题解：画图，四边形解：画图，四边形OBPC及其内部为松弛问题的可行域，及其内部为松弛问题的可行域，整数格点为整数规划问题的可行解。整数格点为整数规划问题的可行解。 根据目标函数等值线优化方向，知根据目标函数等值
7、线优化方向，知P点（点（x1=18/7, x2=19/7）为其松弛问题的最优解，对应目标函数值）为其松弛问题的最优解，对应目标函数值z=94/7。在在P点附近对点附近对x1，x2简单取整，得四点简单取整，得四点A1,A2,A3,A4,其中其中A1,A2为非可行解，为非可行解，A3,A4虽可行，但不是最优解。本例最优虽可行，但不是最优解。本例最优解为解为A*(x1=4, x2=2),目标函数值目标函数值z=12。x1x212345678234maxBA1A2PCOA*A3A4对松弛问题最优解简单取整不是求整数规划的有效方法！对松弛问题最优解简单取整不是求整数规划的有效方法！3.2 分支定界法分支
8、定界法分支定界法分支定界法：一种部分枚举法，不是一种高效的算法。：一种部分枚举法，不是一种高效的算法。分支分支：设整数规划的松弛问题的最优解：设整数规划的松弛问题的最优解xi=bi不符合整数不符合整数要求，若要求，若bi是不超过是不超过bi的最大整数，构造两个约束条件的最大整数，构造两个约束条件xibi 和和xibi+1，将其并入松弛问题中，形成两个分，将其并入松弛问题中，形成两个分支（后继问题）。每个后继问题又可以产生自己的两个支（后继问题）。每个后继问题又可以产生自己的两个分支，这样不断按分支搜索最优解。分支，这样不断按分支搜索最优解。定界定界：在分支过程中，若某后继问题恰巧获得整数规划：
9、在分支过程中，若某后继问题恰巧获得整数规划问题的一个可行解，它的目标值就是一个问题的一个可行解，它的目标值就是一个“界限界限”，用，用作衡量处理其它分支的依据。对于最优解目标函数值低作衡量处理其它分支的依据。对于最优解目标函数值低于已知于已知“界限界限”的后继问题（分支），可以不用分析。的后继问题（分支），可以不用分析。分支缩减了最优解搜索范围，定界提高了搜索效率。分支缩减了最优解搜索范围，定界提高了搜索效率。例：求解整数规划问题例：求解整数规划问题x1x212323maxSA(3/2,10/3)01解：设松弛问题为解：设松弛问题为LP，整数规，整数规划问题为划问题为IP。图中。图中S为为LP
10、可行可行域，黑点为域，黑点为IP可行解。用单纯可行解。用单纯形法求得形法求得LP最优解为最优解为A点点(x1=3/2, x2=10/3), max z=29/6。此时此时LP最优解不符合整数要求。最优解不符合整数要求。分支：任选一变量。设选分支：任选一变量。设选x13/2进行分支，可构造两个分支：进行分支，可构造两个分支： x12 () 对应对应LP1 x11 () 对应对应LP2x1x212323maxS201S1CBS1与与S2是是LP1与与LP2的可行域。的可行域。解解LP1分支，最优解为分支，最优解为B点（点（x1=2, x2=23/9），），Z41/9；解解LP2分支，最优解为分支，
11、最优解为C点（点（x1=1, x2=7/3），），Z=10/3；两个解都不符合整数要求，需继续分支。两个解都不符合整数要求，需继续分支。由于由于B点目标函数值大于点目标函数值大于C点，点，优先选择优先选择LP1分支进行再分支。分支进行再分支。B点点x2=23/9不符合整数要求，可不符合整数要求，可构造两个分支：构造两个分支： x23 对应对应LP11 x22 对应对应LP12LP11无可行域（不用分析），无可行域（不用分析），LP12的可行域为的可行域为S12。解解LP12分支，最优解为分支，最优解为D点（点（x1=33/14, x2=2），），Z61/14；最优解不符合整数要求，需继续分支。
12、最优解不符合整数要求，需继续分支。x1x212323max01S12DS11CB由于由于D点目标函数值大于点目标函数值大于C点，点，优先选择优先选择LP12分支进行再分支。分支进行再分支。D点点x1=33/14不符合整数要求，不符合整数要求，可构造两个分支：可构造两个分支： x13 对应对应LP121 x12 对应对应LP122x1x212323max01S121DEBCS122FGS121是是LP121的可行域，的可行域，S122是线段是线段FG，是，是LP122的可行域；的可行域；解解LP121，最优解为，最优解为E点（点（x1=3, x2=1），），Z4；解解LP122，最优解为，最优解
13、为F点（点（x1=2, x2=2 ），），Z4这两个解同时符合整数要求，目标函数值相等，这两个解同时符合整数要求，目标函数值相等，Z4可作为该可作为该整数规划问题目标函数值的一个界限（下界）。因为它大于整数规划问题目标函数值的一个界限（下界）。因为它大于C点点Z值（值（10/3），故），故LP2不用再分析，所有分支分析结束。不用再分析，所有分支分析结束。原整数规划问题最优解为原整数规划问题最优解为x1=3, x2=1，或，或x1=2, x2=2。上述分支定界法的过程可用图表示为：上述分支定界法的过程可用图表示为：A: x1=3/2, x2=10/3,z=29/6SC: x1=1, x2=7/3
14、,Z=10/3S2B: x1=2, x2=23/9,Z41/9S1D: x1=33/14, x2=2,Z61/14S12无可行解无可行解S11F: x1=2, x2=2 ,Z4S122E: x1=3, x2=1,Z4S121x11x12x22x23x12x13总结：分枝定界法的解题步骤总结：分枝定界法的解题步骤 （1）不考虑整数约束，解相应）不考虑整数约束，解相应LP问题问题（2）检查是否符合整数要求，是则得最优解，完毕。）检查是否符合整数要求，是则得最优解，完毕。否则，转下一步否则，转下一步（3）任取一个非整数变量）任取一个非整数变量xi=bi，构造两个新的约，构造两个新的约束条件：束条件：
15、xibi，xibi+1,分别加入到上一个分别加入到上一个LP问问题，形成两个新的分枝问题。题，形成两个新的分枝问题。（4）不考虑整数要求，解分枝问题，若其最优解为）不考虑整数要求，解分枝问题，若其最优解为整数且此整数解的整数且此整数解的Z值值大于大于所有分枝最优解的所有分枝最优解的Z值，值，则得最优解。否则取则得最优解。否则取Z值最大的非整数解，继续分解，值最大的非整数解，继续分解，转第转第 3步。步。3.3 0-1型整数规划型整数规划一、一、0-1变量及其量及其应用用 若变量只能取若变量只能取0或或1，称为，称为0-1变量。通常用来表示决策变量。通常用来表示决策时是否采取了某个特定方案，例如
16、时是否采取了某个特定方案，例如 0-1变量也可用于含有相互排斥约束条件的问题中，变量也可用于含有相互排斥约束条件的问题中，例：设工序例：设工序B原工时约束条件为原工时约束条件为 且设且设B还有一种新加工方式，对应的工时约束条件为还有一种新加工方式，对应的工时约束条件为 若若B只能采用一种加工方式，如何将两种工时约束条只能采用一种加工方式，如何将两种工时约束条件统一起来写入模型中？设：件统一起来写入模型中？设：则工时约束条件可统一写为：则工时约束条件可统一写为： M是充分大的数，是充分大的数，y1、y2必有一个为必有一个为1另一个为另一个为0。当采用原加工方式，当采用原加工方式，y1=0，条件，
17、条件成立，条件成立，条件多余。多余。反之亦然。反之亦然。例：固定费用问题。有三种资源例：固定费用问题。有三种资源(A,B,C)被用于生产三被用于生产三种产品种产品(I,II,III)，资源量、产品单件可变费用及售价、，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用如下表。资源单耗量及组织三种产品生产的固定费用如下表。请制订生产计划使总收益最大，试写出整数规划模型。请制订生产计划使总收益最大，试写出整数规划模型。单耗量单耗量IIIIII资源量资源量248500234300123100单件可变费用单件可变费用456固定费用固定费用100150200单件售价单件售价81012
18、 解：总收益等于销售收入减去生产上述产品的固定解：总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。事先不确定某种产品是否生产费用和可变费用之和。事先不确定某种产品是否生产，相应固定费用不能确定。，相应固定费用不能确定。 设设xj是第是第j种产品的产量，且设种产品的产量，且设则则0-1整数规划模型为：整数规划模型为： 其中：其中：Mj为为xj的某个上界，根据前三约束条件可取的某个上界，根据前三约束条件可取M1=100, M2=50, M3=34。当生产第。当生产第j种产品，种产品，yj1, xj0, 否则否则yj0，xj0。例：工件排序问题。用例：工件排序问题。用4台机床加工台机床加
19、工3件产品，各产品件产品，各产品的机床加工顺序、以及产品的机床加工顺序、以及产品i在机床在机床j上的加工工时上的加工工时aij如下表，已知产品如下表，已知产品2加工总时间不得超过加工总时间不得超过d。若要求最。若要求最短时间内加工完所有产品，请写出整数规划模型。短时间内加工完所有产品，请写出整数规划模型。产品产品1机床机床1(a11)-机床机床3(a13)-机床机床4（a14）产品产品2机床机床1(a21)-机床机床2(a22)-机床机床4（a24）产品产品3 机床机床2(a32)-机床机床3（a33） 解：设解：设xij为产品为产品i在机床在机床j上开始加工的时间上开始加工的时间（1）产品加
20、工顺序约束产品加工顺序约束：同一产品在下一机床开始时间不早同一产品在下一机床开始时间不早于上一机床结束时间于上一机床结束时间（2）机床对产品的加工顺序约束：已开始的加工还没结束不机床对产品的加工顺序约束：已开始的加工还没结束不能开始另一产品的加工。由于能开始另一产品的加工。由于4台机床都只加工两个产品，引台机床都只加工两个产品，引入入0-1变量变量则则其中其中M是足够大的数是足够大的数（3）产品产品2的总加工时间约束的总加工时间约束 （4）目标函数的建立目标函数的建立 三件产品的加工结束时间的最大值为全部产品加工时三件产品的加工结束时间的最大值为全部产品加工时间间 ，即全部产品实际加工时间为，
21、即全部产品实际加工时间为 而目标函数可以表示为而目标函数可以表示为 最后，整数规划模型可表示为：最后，整数规划模型可表示为：一、一、0-1整数整数规划的解法划的解法 0-1整数规划若有整数规划若有n个变量，则有个变量，则有2n个可能变量组合，个可能变量组合，完全枚举法几乎不可能，一般用隐枚举法。因为完全枚举法几乎不可能，一般用隐枚举法。因为2n个组个组合中往往只有部分是可行解，只要发现一个组合不满足合中往往只有部分是可行解，只要发现一个组合不满足某一条件，即可放弃分析该组合，同时针对目标函数可某一条件，即可放弃分析该组合，同时针对目标函数可以设置过滤条件。以设置过滤条件。例：求解例：求解0-1
22、整数规划整数规划max(a)(b)(c)(d)解：隐枚举法求解过程如下表解：隐枚举法求解过程如下表16Z8833-2Z55（1，1，0）（1，1，1）（1，0，1）（1，0，0）（0，1，1）（0，1，0）（0，0，1）Z00（0，0，0）dcba过滤条件约束条件Z值（x1,x2,x3)最优解最优解=(1,0,1),max z=8。上述算法只用了。上述算法只用了20次运算。次运算。3.4 指派问题指派问题一、指派问题的标准形式及其数学模型一、指派问题的标准形式及其数学模型 有有n个人和个人和n件事，已知第件事，已知第i人做第人做第j事的费用为事的费用为cij，请，请确定人和事之间的一一对应指派
23、方案，使完成确定人和事之间的一一对应指派方案，使完成n件事的件事的总费用最少。总费用最少。 称矩阵称矩阵C=(cij)nn为指派指派问题的系数矩的系数矩阵。在。在实际问题中，中，cij可以是可以是费用、成本、用、成本、时间等。等。 建立指派建立指派问题的数学模型的数学模型时可引入可引入n2个个0-1变量：量：问题的数学模型可写为：问题的数学模型可写为：（）（ ）（） 约束条件约束条件表示每件事必须有且只能由一个人去表示每件事必须有且只能由一个人去做；约束条件做；约束条件表示每个人必做且只做一件事。表示每个人必做且只做一件事。例：某商业公司计划开例：某商业公司计划开5家新商店，指派家新商店，指派
24、5家建筑公司分家建筑公司分别承建。已知建筑公司别承建。已知建筑公司Ai对新商店对新商店Bj的建造费用报价为的建造费用报价为cij,如下表，写出指派问题的数学模型，使总费用最少。如下表，写出指派问题的数学模型，使总费用最少。cijB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106解：设解：设0-1变量变量指派问题的数学模型可写为：指派问题的数学模型可写为：二、匈牙利解法二、匈牙利解法 1955年，库恩利用匈牙利数学家康尼格的关于矩阵年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，中独立零元素的定理
25、，提出了解指派问题的一种算法，称为匈牙利解法。称为匈牙利解法。 指派问题最优解的性质：若从指派问题的系数矩阵指派问题最优解的性质：若从指派问题的系数矩阵C=(cij)nn的某行（或某列）各元素分别减去一个常数的某行（或某列）各元素分别减去一个常数k，得到新的系数矩阵得到新的系数矩阵C=(cij)nn。C与与C为系数矩阵的两为系数矩阵的两个指派问题有相同的最优解。个指派问题有相同的最优解。 这种变化并不影响数学模型的约束方程组，只是使这种变化并不影响数学模型的约束方程组，只是使目标函数值减少了目标函数值减少了k，所以最优解不变。，所以最优解不变。匈牙利解法的一般步骤：匈牙利解法的一般步骤：（1）
26、变换系数矩阵）变换系数矩阵(n阶阶)。先对各行元素减去本行。先对各行元素减去本行最小元素，再对各列元素减去本列最小元素。各行最小元素，再对各列元素减去本列最小元素。各行各列至少有一个各列至少有一个0元素，且不出现负元素；元素，且不出现负元素；（2）确定独立零元素。先在只有）确定独立零元素。先在只有1个个0的行（或列）的行（或列）将该将该0圈中圈中()，同时这个，同时这个所在的列（或行）上所所在的列（或行）上所有其它有其它0划去划去()， (圈完圈完1个零的个零的行或列后，行或列后，2个个0以以上的行或列任选上的行或列任选1个个0加圈再加圈再 ） ，直至所有，直至所有0被圈被圈或被划去，被圈的即
27、为独立零元素或被划去，被圈的即为独立零元素。若有。若有n个独立个独立零元素，令它们都为零元素，令它们都为1，其它元素为，其它元素为0，即得最优解，即得最优解矩阵。若少于矩阵。若少于n个独立零元素，则做能覆盖所有零个独立零元素，则做能覆盖所有零元素的最少直线数目的直线集合，方法如下：元素的最少直线数目的直线集合，方法如下： 对没有对没有 的行打的行打“”; 在已打在已打“”的行中，对的行中，对 所在列打所在列打“”; 在已打在已打“”的列中，对的列中，对 所在行打所在行打“”; 重复重复 步，直到不能找到打步，直到不能找到打“”的行和列的行和列; 对没有打对没有打“”的行划横线，对打的行划横线，
28、对打“”的列划垂的列划垂线线 。（3）继续变换系数矩阵。）继续变换系数矩阵。 方法方法:在未被直线覆盖的元素中找出一个最小元素，对在未被直线覆盖的元素中找出一个最小元素，对未被直线覆盖的元素所在行（或列）都减去这一最小元未被直线覆盖的元素所在行（或列）都减去这一最小元素，这样未被直线覆盖的元素出现素，这样未被直线覆盖的元素出现0元素，同时已被直元素，同时已被直线覆盖的元素会出现负元素，为消除负元素，对它所在线覆盖的元素会出现负元素，为消除负元素，对它所在列（或行）中各元素都加上这一最小元素即可。返回步列（或行）中各元素都加上这一最小元素即可。返回步骤（骤（2）。如此重复直到找到最优解矩阵。）。
29、如此重复直到找到最优解矩阵。例：用匈牙利解法求解上一例指派问题。其系数矩阵为例：用匈牙利解法求解上一例指派问题。其系数矩阵为解：解：(1)先对各行元素减去本行最小元素，然后各列也如此得：先对各行元素减去本行最小元素，然后各列也如此得：（2）确定独立零元素，对）确定独立零元素，对C加圈加圈 只有只有4个独立零元素，少于矩阵阶数个独立零元素，少于矩阵阶数5，则做能覆盖所，则做能覆盖所有零元素的最少直线数的直线集合。有零元素的最少直线数的直线集合。（3）为使未被直线覆盖的元素中出现零元素，将第）为使未被直线覆盖的元素中出现零元素，将第2和和第第3行元素减去未覆盖元素的最小元素行元素减去未覆盖元素的最
30、小元素1，第，第1列出现负列出现负元素，将第元素，将第1列所有元素加列所有元素加1，得到，得到（4）回到步骤）回到步骤2，对，对C”重新加圈确定独立零元素重新加圈确定独立零元素（5）已有）已有5个独立零元素，可确定最优解绝阵：个独立零元素，可确定最优解绝阵：即最优指派方案为：即最优指派方案为：A1承建承建B3，A2承建承建B2，A3承建承建B1，A4承建承建B4，A5承建承建B5，总费用，总费用34万元。万元。三、非标准形式指派问题三、非标准形式指派问题 非标准形式的指派问题通常先转换成标准形式，再非标准形式的指派问题通常先转换成标准形式，再用匈牙利法求解。用匈牙利法求解。（1）最大化指派问题
31、）最大化指派问题 设最大化指派问题的系数矩阵为设最大化指派问题的系数矩阵为C=(cij)nn ，其中最，其中最大元素为大元素为m，令矩阵，令矩阵B=(bij)nn =(m-cij) nn，则以，则以B为系为系数矩阵的最小化指派问题和以数矩阵的最小化指派问题和以C为系数矩阵的原最大为系数矩阵的原最大化指派问题有相同最优解。化指派问题有相同最优解。（2）人数和事件数不相等的指派问题）人数和事件数不相等的指派问题 若人少事多，则添上一些虚拟的人，虚拟人做事的若人少事多，则添上一些虚拟的人，虚拟人做事的费用系数取费用系数取0；若人多事少，添上一些虚拟的事，它们；若人多事少，添上一些虚拟的事，它们被人做
32、的费用系数也取被人做的费用系数也取0。（3）一个人可以做几件事的指派问题）一个人可以做几件事的指派问题 某人可做几件事，则将该人化作相同的几个人来接某人可做几件事，则将该人化作相同的几个人来接受指派，这几个相同的人的做事费用系数都相同。受指派，这几个相同的人的做事费用系数都相同。（4）某事一定不能由某人做的指派问题）某事一定不能由某人做的指派问题 若某事一定不能由某人做，则可将相应的费用系数若某事一定不能由某人做，则可将相应的费用系数取做够大的数取做够大的数M。例：上例中，经研究决定舍弃建筑公司例：上例中，经研究决定舍弃建筑公司A4、A5，让技术力量雄，让技术力量雄厚的厚的A1、A2、A3承建，每家公司可承建承建，每家公司可承建1至至2家商店。费用系数家商店。费用系数矩阵如下，求总费用最少的指派方案。矩阵如下，求总费用最少的指派方案。B1 B2 B3 B4 B5A1A2A3解：把每家公司化作相同的解：把每家公司化作相同的2家公司，再加入虚商店家公司，再加入虚商店B6B1 B2 B3 B4 B5 B6A1A1A2A2A3A3匈牙利法求得匈牙利法求得A1承建承建B1,B3,A2承建承建B2,A3承建承建B4,B5,总费用总费用35万。万。
