数学建模整数规划

数学建模整数规划2023/5/31第一页，共七十八页，编辑于2023年，星期六数学建模2023/5/31第二页，共七十八页，编辑于2023年，星期六第三部分整数规划应用实例分析整数规划问题的几种求解方法分枝界定法隐枚举法匈牙利法

蒙特卡洛法实验准备2023/5/31第三页，共七十八页，编辑于2023年，星期六例1整数规划问题某厂拟购进甲、乙两类机床生产新产品。已知甲、乙机床进价分别为2万元和3万元；安装占地面积分别为4m2和2m2；投后的收益分别为300元/日和200元/日。厂方目前仅有资金14万元，安装面积18m2。为使收益最大，厂方应购进甲、乙机床各多少台？实例一整数规划问题甲型乙型现有量进价（万元）2315占地面积（m2）4218利润（百元）32第四页，共七十八页，编辑于2023年，星期六设设应购进甲、乙机床台数分别为x1和x2，工厂的收益为z。整数规划(IP)1.模型建立s.t.实例一整数规划问题第五页，共七十八页，编辑于2023年，星期六formatshortc=[-3;-2];a=[2,3;4,2];b=[14;18];lb=[0;0];[x,Fval]=linprog(c,a,b,[],[],lb)先不考虑解的整数限制，问题B的最优解：x1=3.25，x2=2.5，

最优值：z=14.75。2.模型求解设整数规划问题为A，与它相应的线性规划为问题B，先来求解问题B。1）舍去小数：取x1=3，x2=2，算出目标函数值z=13。2）试探：如取x1=4，x2=1时，z=14，如取x1=3，x2=3时，不满足约束条件，通过比较得到模型的最优整数解。解法一：实例一整数规划问题第六页，共七十八页，编辑于2023年，星期六1）不考虑解的整数限制，问题B的最优解：x1=3.25，x2=2.5，

最优值：z=14.752.模型求解

解法二：设整数规划问题为A，与它相应的线性规划为问题B实例一整数规划问题第七页，共七十八页，编辑于2023年，星期六

2.模型求解因为2与3之间无整数，故这两个子集的整数解必与原可行集合整数解一致，这一步骤称为分枝。对问题A分枝构成两个子问题称为B1和B2。问题B1数学模型：s.t.问题B2数学模型：s.t.实例一整数规划问题第八页，共七十八页，编辑于2023年，星期六2.模型求解B2最优解：

x1=4，x2=1，z2=14

B1最优解：

x1=3，x2=8/3，z1=43/3图解法（单纯形法）求得的最优解分别为：实例一整数规划问题第九页，共七十八页，编辑于2023年，星期六4）对问题B1在进行分枝，得问题B11和B122.模型求解

问题B11数学模型：s.t.问题B12数学模型：s.t.实例一整数规划问题第十页，共七十八页，编辑于2023年，星期六求解问题B11和B12

得到：2.模型求解

5）此时由于所有子问题的目标值均小于或等于z2，故问题A的目标函数最优值z*=z2=14，最优解为x1=4，x2=1。B11最优解：

x1=3，x2=2，z11=13B12最优解：

x1=2.5，x2=3，z12=13.5实例一整数规划问题第十一页，共七十八页，编辑于2023年，星期六整数规划整数规划（IntegerProgramming）数学规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。整数规划分类：（1）变量全限制为整数时，称纯（完全）整数规划。（2）

变量部分限制为整数的，称混合整数规划。2023/5/31第十二页，共七十八页，编辑于2023年，星期六整数规划整数规划特点（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。②整数规划无可行解。③有可行解（当然就存在最优解），但最优解值变差。（ii）整数规划最优解不能按照实数最优解简单取整而获得。2023/5/31第十三页，共七十八页，编辑于2023年，星期六整数规划整数规划求解方法分类（1）分枝定界法—可求纯或混合整数线性规划。（2）割平面法—可求纯或混合整数线性规划。（3）隐枚举法—求解“0-1”整数规划：①过滤隐枚举法；②分枝隐枚举法。（4）匈牙利法—解决指派问题（特殊“0-1”规划）。（5）蒙特卡洛法—求解各种类型规划。2023/5/31第十四页，共七十八页，编辑于2023年，星期六分枝定界法（1）分枝：通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；（2）定界：并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。（3）剪枝：在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题。分枝定界法2023/5/31第十五页，共七十八页，编辑于2023年，星期六分枝定界法步骤（1）求解整数规划问题A对应的线性规划问题B（松弛问题）；（2）分枝，在松弛问题B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以[bj]表示小于bj的最大整数，构造两个约束条件

将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。分枝定界法2023/5/31第十六页，共七十八页，编辑于2023年，星期六

分枝定界法2023/5/31第十七页，共七十八页，编辑于2023年，星期六···············1234567·松弛问题的可行域增加x1≤3增加x1≥4L1L2分枝定界法例2第十八页，共七十八页，编辑于2023年，星期六x1≤3x1≥4父问题子问题结论1：（IP）的最优解一定在某个子问题中父问题的最优值≤3：子问题中的整数解都是（IP）的可行解子问题的最优解2：子问题的可行域父问题的可行域∩第十九页，共七十八页，编辑于2023年，星期六x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3···············1234567·4x1+x2=16.52x1+3x2=14.5z=30x1+20x2第二十页，共七十八页，编辑于2023年，星期六某公司拟在市东、西、南三区建立门市部，拟议中有7个位置Ai(i=1,2,…,7)可供选择。规定在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪些点可使年利润最大？0-1变量例3投资场所的选定—0-1变量第二十一页，共七十八页，编辑于2023年，星期六s.t.1.模型建立目标函数：约束条件：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。0-1变量第二十二页，共七十八页，编辑于2023年，星期六0-1型整数规划0-1型整数规划决策变量只能取0或1的整数规划，叫做0-1整数规划。决策变量称为0-1变量(二进制变量、逻辑变量)。0-1变量作为逻辑变量，常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。在实际问题中引入0-1变量，可以把各种情况需要分别讨论的数学规划问题统一在一个问题中讨论了。2023/5/31第二十三页，共七十八页，编辑于2023年，星期六

某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表格所示。问两种货物各托运多少箱，可使获得利润为最大?货物甲乙托运限制体积每箱（米3）5424重量每箱（百公斤）2513利润每箱（百元）20100-1型整数规划例4—互相排斥的计划第二十四页，共七十八页，编辑于2023年，星期六0-1型整数规划

1.模型建立+(1-y)M+yM假设现在有车运和船运两种运输方式，但只能选择一种运输方式，如用车运时关于体积的限制条件为5x1+4x2≤24(车)。如用船运时关于体积的限制条件为7x1+3x2≤45(船)。（这两条件互相排斥）。设甲、乙两种货物的托运箱数分别为x1，x2，可获得的利润为z。设变量y表示运货的方式，当y为1时，用车运，y为0时，用船运。M是充分大的数2023/5/31第二十五页，共七十八页，编辑于2023年，星期六0-1型整数规划

模型分析有多个相互排斥的约束条件2023/5/31第二十六页，共七十八页，编辑于2023年，星期六相互排斥的约束条件如果有m个互相排斥的约束条件（<=型）：为了保证这个约束条件只有一个起作用，我们引入m个0-1变量和一个充分大的常数M，下面这一组m+1个约束条件符合上述要求。0-1型整数规划第二十七页，共七十八页，编辑于2023年，星期六有三种自然资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单位消耗量及组织三种产品生产的固定费用如下表。要求制订一个生产计划，使总收益最大。－12108单位售价－200150100固定费用－654

单位可变费用100321C300432B500842A资源量IIIIII

单耗量资源产品例5—固定费用问题0-1型整数规划第二十八页，共七十八页，编辑于2023年，星期六解：设xj是第j种产品的产量，j=1，2，3；再设若生产第j种产品（即xj>0）若不生产第j种产品（即xj=0）j=1，2，3则问题的模型为s.t.

如果生产第j种产品，则其产量xj＞0，由xj≤Mjyj知，yj＝1。因此，相应的固定费用在目标函数中将被考虑。

同理，如果不生产第j种产品，则其产量xj=0，只有yj为0才有意义，因此，相应的固定费用不应在目标函数中被考虑。0-1型整数规划2023/5/31第二十九页，共七十八页，编辑于2023年，星期六0-1型整数规划解法只检查变量取值的组合的一部分的方法。

：求解下列问题隐枚举法(a)(b)(c)(d)例62023/5/31第三十页，共七十八页，编辑于2023年，星期六0-1型整数规划解法解法一：隐枚举法(x1,x2,x3)z值abcd过滤条件(0,0,0)0√√√√Z≥0(0,0,1)5√√√√Z≥5(0,1,0)-2(0,1,1)3(1,0,0)3Z≥8(1,0,1)√√√√(1,1,0)81(1,1,1)6所以，最优解(x1，x2，x3)T=(1，0，1)T，maxz=8。2023/5/31第三十一页，共七十八页，编辑于2023年，星期六0-1型整数规划解法为了使最优解尽可能早出现，可先将目标函数中各变量的顺序按其系数大小重新排列，这样可进一步减少计算量。隐枚举法按目标函数中各变量系数的大小重新排列各变量最大化问题：由小到大最小化问题：由大到小2023/5/31第三十二页，共七十八页，编辑于2023年，星期六解法二（优化）：重新排列xj的顺序(系数递减)0-1型整数规划解法第三十三页，共七十八页，编辑于2023年，星期六0-1型整数规划计算表目标函数z＝3x1－2x2＋5x3＝5x3＋3x1－2x2

最大值的上限是8，第二大的值是5…5x3＋3x1－2x2≥8⑤点(x3,x1,x2)约束条件满足条件?是∨否×z值⑤①②③④(1,1,0)8∨∨∨∨∨8隐枚举法：共计算5次(均满足约束条件)。（最优解为1，0，1，最优值8）可根据计算逐渐改变过滤条件(该例因最大值的点满足其他四个约束，即找到最大化问题的最好的整数解。就不需验证计算第二大值的点是否满足约束条件)0-1型整数规划解法过滤隐枚举法第三十四页，共七十八页，编辑于2023年，星期六步骤1：将问题转化为如下标准形式：其中cj≥0，且c1≤c2≤…≤cn。例7求解0-1整数规划（选学-分枝隐枚举法）0-1型整数规划解法第三十五页，共七十八页，编辑于2023年，星期六⑵如约束条件为≤，两边同乘(-1)；如约束条件为等式，可令变量，代入目标函数和其它约束条件中，将xn消掉。⑶按目标函数中系数由小到大的顺序重新排列变量，并将约束条件中的排列顺序做相应改变。

⑴如目标函数为maxz，令，可化为。如某个变量的系数为负，令，使系数变正。0-1型整数规划解法步骤1：将问题转化为标准形式：第三十六页，共七十八页，编辑于2023年，星期六调整后的0-1规划问题变为：(a)(b)

步骤2：令所有变量取0，求出目标函数值，并代入约束条件中检查是否可行，如果可行即为问题的最优解；否则转下一步。

令，得＝-10，但不满足两个约束条件。0-1型整数规划解法第三十七页，共七十八页，编辑于2023年，星期六

步骤3：分支和定界。依次令各变量分别取0或1，将问题划分为两个子问题，分别检查解是否可行，如不可行继续对边界值较小的子问题分支，直到找出一个可行解为止，这时得到值的一个上界。分支过程见下图所示：0-1型整数规划解法第三十八页，共七十八页，编辑于2023年，星期六步骤4：考察所有子问题，有以下四种情况：

⑴若某个子问题的边界值对应原问题的可行解，则将它的边界值与保留的值作比较，并取较优的一个作为新的值。如所有子问题都已考察完毕，则保留下来的值及其对应的解即为0-1整数规划问题的最优解。⑵若某个子问题的边界值大于保留下来的值，不管其是否可行，则将这一分支剪掉。⑶若某个子问题不可行（在该分支中的上级变量的值已经确定的情况下，其余变量不管取什么值都无法满足所有约束时，该枝的分枝已无可行解），则将这一分支剪掉。⑷若某个子问题可行且边界值优于值，但该边界值对应的解不是可行解，则该问题待考察。如有多个问题待考察，优先对其中最优值最大的一个子问题进行考察，转步骤3。0-1型整数规划解法第三十九页，共七十八页，编辑于2023年，星期六

分支③边界值=-6＜-4，但相应的解不可行，需继续分支。过程如上图所示。0-1型整数规划解法第四十页，共七十八页，编辑于2023年，星期六上述求解过程也可用表格表示：(0，1，0，1，0)(0，1，1，0，0)(0，0，1，0，0)(1，0，1，0，0)(1，1，0，0，0)(0，1，0，0，0)(1，0，0，0，0)(0，0，0，0，0)

＞-4，剪枝1⑨

＞-4，剪枝-1⑧不可行，剪枝×-5⑦

＞-4，剪枝-3⑤可行≤-4√√-4④×-6③×√-8②×-10①ba备注约束条件z值序号0-1型整数规划解法第四十一页，共七十八页，编辑于2023年，星期六所以，最优解：即原问题的最优解为：分枝隐枚举法0-1型整数规划解法第四十二页，共七十八页，编辑于2023年，星期六指派问题（0-1型）一、指派问题拟派n人去做n项工作，由于每人的专长不同，各人完成不同任务效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高的问题，这类问题称为指派问题(分派问题、分配问题)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人任务cij表示第i个人完成第j项任务的效率。第四十三页，共七十八页，编辑于2023年，星期六二、指派问题的数学模型=(Cij)指派问题系数矩阵B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人任务解：设指派问题（0-1型）第四十四页，共七十八页，编辑于2023年，星期六某单位现在Ａ、Ｂ、Ｃ、Ｄ四项工作需完成，现在甲、乙、丙、丁四个人均可完成这四项任务。每人完成各项任务所用的时间如右表所示，问应指派何人去完成何项任务，使所需时间最少？甲215134乙1041415丙9141613丁78119ABCD任务人员满足所有约束条件的可行解xij也可写成表格或矩阵形式，称为解矩阵(xij)=本例的一个可行解矩阵(cij)=例8指派问题指派问题（0-1型）第四十五页，共七十八页，编辑于2023年，星期六指派问题数学模型的性质：若从指派问题的系数的系数矩阵（cij）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（bij），那么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。独立的0元素：位于不同行不同列的0元素称为独立的0元素。结论：若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素取值为1，其它元素取值为0。将其代入目标函数中得到zk=0，它一定是最小。这就是以(bij)为系数矩阵的指派问题的最优解，也就得到了问题的最优解。指派问题（0-1型）第四十六页，共七十八页，编辑于2023年，星期六三、指派问题的解法（匈牙利法）第一步:使指派问题的系数矩阵经变换，在各行各列都出现０元素。（１）从系数矩阵的每行元素减去该行的最小元素；（２）再从所得系数矩阵的每列元素中减去该列的最小元素。2497min24min指派问题（0-1型）第四十七页，共七十八页，编辑于2023年，星期六经第一步变换后，系数矩阵中每行每列都已有了0元素；只需找出n个独立的0元素，若能找出，就以这些独立的0元素对应解矩阵中的元素为1，其它作为0，这就得到最优解。找独立0元素的步骤如下：第二步：进行试指派，以寻求最优解。0（1）从只有一个0元素的行开始，给这个0元素加圈，记作◎.然后再划去◎所在列的其它0元素，记作。（2）给只有一个0元素的列的0元素加圈，记作◎；然后划去◎所在行的0元素，记作。0指派问题（0-1型）第四十八页，共七十八页，编辑于2023年，星期六（3）反复(1),(2)两步，直到所有0元素都被圈出和划掉为止。（4）若各行各列均有多于2个的0元素未被圈出或划掉，任选其中任意一个0元素加圈。（5）若◎元素的数目m等于矩阵的阶数n，那么指派问题的最优解已得到，若m<n，则转入下一步。第二步：进行试指派，以寻求最优解。指派问题（0-1型）第四十九页，共七十八页，编辑于2023年，星期六min76746指派问题（0-1型）第五十页，共七十八页，编辑于2023年，星期六第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立0元素数。（5）对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线。（1）对没有◎的行打√号；（2）对已打√号的行中所有含划0元素的列打√号；（3）再对打有√号的列中含◎元素的行打√号；（4）重复(2)、(3)直到得不出新的打√号的行、列为止；√√√指派问题（0-1型）第五十一页，共七十八页，编辑于2023年，星期六第四步：对第三步所得矩阵进行变换，目的是增加0元素。在没有被直线覆盖的部分中找出最小元素。然后在打√行各元素中都减去该最小元素，而在打√列的各元素都加上该最小元素（以保证原来的0元素不变）。这样得到新系数矩阵。重复第二步。指派问题（0-1型）√√√第五十二页，共七十八页，编辑于2023年，星期六第五步：系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素取值为1，其它元素取值为0。∵独立0元素的个数等于系数矩阵的阶数∴得到了最优解最优解矩阵为：指派问题（0-1型）第五十三页，共七十八页，编辑于2023年，星期六练习：有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表：ABCD甲乙丙丁15192619182317212122162324181917工作工人指派问题（0-1型）第五十四页，共七十八页，编辑于2023年，星期六解：用匈牙利法求解过程如下：min15181617√√√min1√√√√√指派问题（0-1型）第五十五页，共七十八页，编辑于2023年，星期六四、非标准形式的指派问题（选学）1、最大化指派问题2、人数和事数不等的指派问题3、一个人可做几件事的指派问题4、某事一定不能由某人做的指派问题指派问题（0-1型）第五十六页，共七十八页，编辑于2023年，星期六1、求最大化的指派问题令bij=M-cij其中：M是足够大的常数（cij中最大元素）用匈牙利法求解（bij）即可。所得最小解就是原问题的最大解。指派问题（0-1型）第五十七页，共七十八页，编辑于2023年，星期六2、人数和任务数不等的指派问题若人少任务多，则添上一些虚拟的“人”。这些虚拟的“人”完成各任务的费用系数可取0，理解为这些费用实际上不会发生。若人多任务少，则添上一些虚拟的“任务”，这些虚拟的“任务”由各人完成的费用系数同样也取0。指派问题（0-1型）第五十八页，共七十八页，编辑于2023年，星期六3、一个人可做几件事的指派问题若某个人可完成几项任务，则可将人化作相同的几个“人”，来接受指派，这几个“人”完成同一项任务的费用系数都一样。4、某项任务一定不能由某人完成的指派问题若某项任务一定不能由某个人完成，则可将相应的费用系数取作足够大的数M。指派问题（0-1型）第五十九页，共七十八页，编辑于2023年，星期六例9：分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。ABCDE甲2529314237乙3938262033丙3427284032丁2442362345指派问题（0-1型）第六十页，共七十八页，编辑于2023年，星期六1、m约束条件中只有k个起作用设m个约束条件可表示为：定义又M为任意大的正数，得指派问题（0-1型）第六十一页，共七十八页，编辑于2023年，星期六2、约束条件的右端项可能是r个值中的某一个即定义指派问题（0-1型）第六十二页，共七十八页，编辑于2023年，星期六3、两组条件中满足其中一组若x1≤4，则x2≥1；否则（即x1>4）,x2≤3又M为任意大正数，则问题可表达为：指派问题（0-1型）第六十三页，共七十八页，编辑于2023年，星期六4、用以表示固定费用的函数生产费用函数：引入变量yj指派问题（0-1型）第六十四页，共七十八页，编辑于2023年，星期六例10东方大学计算机实验室聘用4名大学生（代号1、2、3、4）和2名研究生（代号5、6）值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每h值班的报酬如下表学生代号报酬（元/h)每天最多可安排的值班时间周一周二周三周四周五12345610109.99.810.811.306070606083055604048006063应用举例第六十五页，共七十八页，编辑于2023年，星期六该实验室开放时间是上午8点至晚上10点，开放时间内须有且仅需一名学生值班，规定大学生每周值班不少于8h，研究生每周不少于7h，每名学生每周值班不超过3次，每次值班不少于2h，每天安排值班的学生不超过3人且其中必须有一名研究生，试为该实验室安排一张人员的值班表，使总支付的报酬最少解：设xij为学生i在周j的值班时间，安排学生i在周j值班否则用aij代表学生i在周j最多可安排的值班时间，ci为学生i的每h的报酬，则其数学模型为应用举例第六十六页，共七十八页，编辑于2023年，星期六不超过可安排时间大学生每周值班不少于8h研究生每周值班不少于7h实验室每天开放14h每名学生一周值班不超过3次每天值班不超过3人每天有一名研究生值班应用举例第六十七页，共七十八页，编辑于2023年，星期六学生代号一二三四五123456674685622263最优结果为总支付报酬每周727.5元值班方案为：应用举例第六十八页，共七十八页，编辑于2023年，星期六蒙特卡洛法—整数规划蒙特卡洛法(MonteCarlomethod)也称为随机取样法，进行大统计量（N→∞）的统计实验方法或计算机随机模拟方法。当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。大数定理：均匀分布的算术平均收敛于真值中心极限定理：置信水平下的统计误差

2023/5/31第六十九页，共七十八页，编辑于2023年，星期六MonteCarlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。19世纪人们用投针试验的方法来决定圆周率π。本世纪40年代计算机的出现、特别是近年来高速计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。使用蒙特卡罗方法估算π值.放置30000个随机点后,π的估算值与真实值相差0.07%.蒙特卡洛法—整数规划第七十页，共七十八页，编辑于2023年，星期六蒙特卡洛法—整数规划求解问题可以分为两类:确定性问题和随机性问题。

解题步骤：

1.根据提出的问题构造一个简单、适用的概率模型或随机模型，使问题的解对应于该模型中随机变量的某些特征（如概率、均值和方差等），所构造的模型在主要特征参量方面要与实际问题或系统相一致

2.根