《运筹学4整数规划课件》由会员分享，可在线阅读，更多相关《运筹学4整数规划课件（77页珍藏版）》请在金锄头文库上搜索。
1、运筹学运筹学OperationsResearch1.整数规划的数学模型整数规划的数学模型MathematicalModelofIP2.分枝定界法分枝定界法BranchandBoundMethod3.割平面法割平面法cutting-planeMethod4.01规划规划BinaryIntegerProgramming5.指派问题指派问题AssignmentProblemChapter5整数规划整数规划IntegerProgramming运筹学4整数规划【引例例】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。问两种物品各装多少
2、件，所装物品的总价值最大？物品重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80.0020.002543【解解】设甲、乙两种物品各装x1、x2件，则数学模型为：运筹学4整数规划一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。5.1 整数规划的数学模型运筹学4整数规划很多实际规划问题都属于整数规划问题.例如1.变量是人数、机器设备台数或产品件数等都要求是整数2.对某一个项目要不要投资的决策问题，可选用一个逻辑变
3、量x，当x=1表示投资，x=0表示不投资；3.人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。5.1 整数规划的数学模型运筹学4整数规划【例例5.1】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表51所示。问两种物品各装多少件，所装物品的总价值最大？物品重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80.0020.002543【解解】设甲、乙两种物品各装x1、x2件，则数学模型为：猜想:能否用前述的LP方法直接求解?运筹学
4、4整数规划如果不考虑x1、x2取整数的约束（称为（5.1）的松弛问题）：运筹学4整数规划图图51线性规划的可行域如图51中的阴影部分所示。运筹学4整数规划用图解法求得点B为松弛问题最优解：X(3.57，7.14)，Z35.7。由于x1，x2必须取整数值，整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33,并非最优。实际上问题的最优解是（5，5），Z=35。即两种物品各装5件，总价值35元。运筹学4整数规划由图51知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法
5、都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。结论:猜想不成立!运筹学4整数规划【例例5.2】在例5.1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。所装物品不变，背包和旅行箱只能选择其一，建立数学模型，使所装物品价值最大。解：此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入01变量（或称逻辑变量）yi，令i=1,2分别是采用背包及旅行箱装载。运筹学4整数规划由于所装物品不变，约束条件左边不变，整数规划数学模型为例5.1中的数学模型为：
6、运筹学4整数规划【例例5.3】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位只能一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。工作人员ABCD甲85927390乙95877895丙82837990丁86908088如果问题的所有变量取0或1，此问题称为01整数规划问题，简称01规划。运筹学4整数规划【解】【解】此工作分配问题可以采用枚举法求解，即将所有分配方案求出，总分最大的方案就是最优解。本例的方案有4！432124种，当人数和工作数较多时，方案数是人数的阶乘，计算量非常大。用01规划模型求解此类分配问题显得非常简单。设:数学模型如
7、下：目标函数为工作人员ABCD甲85927390乙95877895丙82837990丁86908088运筹学4整数规划每项工作只能安排一人，约束条件为变量约束：要求每人做一项工作，约束条件为工作人员ABCD甲85927390乙95877895丙82837990丁86908088运筹学4整数规划数学模型如下：运筹学4整数规划5.2分枝定界法分枝定界法的基本思路：分解可行域凸现整数顶点运筹学4整数规划分枝定界法的步骤：1.求整数规划的松弛问题最优解；2.若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；3.任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组
8、成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界，称为定界；4.检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。5.2分枝定界法运筹学4整数规划【例【例5.4】用分枝定界法求解例5.1【解】【解】先求对应的松弛问题（记为LP0）：用图解法得到最优解X（3.57,7.14）,Z0=35.7,如下图所示。运筹学4整数规划1010松弛问题L
9、P0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC运筹学4整数规划1010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5运筹学4整数规划1010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336运筹学4整数规划1010x1x2oACLP1346LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP3运筹学4整数规划尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解就是原整数规划的最优解。上述分枝过程可用下图表示：LP0:X=(3.57,7.14),Z
10、0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13x14LP3:X=(4.33,6)Z3=35.33x26LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x14x15无可行解x27运筹学4整数规划LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13x14LP3:X=(4.33,6)Z3=35.33x26LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x14x15无可行解x27x11010oAC3465运筹学4整数规划割平面法1.理解
11、分枝分枝与定界定界的含义2.选择合适的“枝”生“枝”3.掌握何时停止生“枝”4.掌握混合整数规划的分枝定界法求解整数规划的方法还有割平面法。作业：教材P1365.7（1）01规划指派问题运筹学4整数规划1010x1x2oABC5.3割平面法原理：寻找切割可行域的直线运筹学4整数规划设纯整数规划松弛问题的最优解5.3割平面法运筹学4整数规划设xi不为整数，将分离成一个整数与一个非负真分数之和：运筹学4整数规划则有等式两边都为整数并且有左边是一个整数，右边是一个小于1的数。运筹学4整数规划加入松弛变量si得此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫瑞)约束
12、方程。将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。则运筹学4整数规划例如，x1行：移项：令加入松弛变量s1得同理，对于x2行有：运筹学4整数规划【例】已知整数规划【解】不考虑整数约束，松弛问题的最优表如下运筹学4整数规划c cj j3 32 20 00 0b bC CB BX XB Bx x1 1x x2 2x x3 3x x4 42 2x x2 20 01 11/21/21/21/25/25/23 3x x1 11 10 01/41/43/43/413/413/4 j j0 00 01/41/45/45/4最优表最优解
13、X=(13/4，5/2，0，0)T可见，x1、x2不满足整数要求，选择第一行（任意）进行分割，产生割平面约束。运筹学4整数规划得到割平面约束：添加到最优表中，得分解成一个整数与一个非负真分数之和左边是一个整数，右边是一个小于1的数。加入松弛变量X5，运筹学4整数规划c cj j3 32 20 00 00 0b bC CB BX XB Bx x1 1x x2 2x x3 3x x4 4x x5 52 2x x2 20 01 11/21/21/21/20 05/25/23 3x x1 11 10 01/41/43/43/40 013/413/40 0x x5 50 00 01/21/21/21/2
14、1 11/21/2 j j0 00 01/41/45/45/40 02 2x x2 20 01 10 01 1 2 23 3x x1 11 10 00 01 11/21/27/27/20 0x x3 30 00 01 11 12 21 1 j j0 00 00 01 11/21/2最优解X=(7/2，2，1，0，)T可见，x1不满足整数要求，选择第一行进行分割，产生割平面约束。运筹学4整数规划x1行：Gomory约束添加到最优表中，得2 2x x2 20 01 10 01 1 2 23 3x x1 11 10 00 01 11/21/27/27/20 0x x3 30 00 01 11 12
15、21 1 j j0 00 00 01 11/21/2运筹学4整数规划2 2x x2 20 01 10 01 10 02 21 13 3x x1 11 10 00 01 10 01 14 40 0x x3 30 00 01 11 10 04 43 30 0x x6 60 00 00 00 01 12 21 1 j j0 00 00 01 10 01 1c cj j3 32 20 00 00 00 0b bC CB BX XB Bx x1 1x x2 2x x3 3x x4 4x x5 5x x6 62 2x x2 20 01 10 01 1 0 02 23 3x x1 11 10 00 01 1
16、1/41/40 07/37/30 0x x3 30 00 01 11 11 10 01 10 0x x6 60 00 00 00 01/21/21 11/21/2 j j0 00 00 01 11/21/20 0运筹学4整数规划得到整数最优解：X(4，1)，Z14注：Gomory约束只是割去线性规划可行域的一部分，保留了全部整数解。用图解法表示：运筹学4整数规划第一次切割4,1第二次切割13/4,5/2松弛问题运筹学4整数规划01规划指派问题1.领会割平面法的基本原理1.分离源行，求出Gomory约束2.在最优表中增加Gomory约束，用对偶单纯形法迭代运筹学4整数规划一、0-1变量若变量只能
17、取值若变量只能取值0 0或或1 1，则称其为，则称其为0-10-1变量。变量。5.40-1规划1.对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资；2.人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。运筹学4整数规划【例例5.1】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表51所示。问两种物品各装多少件，所装物品的总价值最大？物品重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80
18、.0020.002543【解解】设甲、乙两种物品各装x1、x2件，则数学模型为：运筹学4整数规划【例例5.2】在例5.1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。所装物品不变，背包和旅行箱只能选择其一，建立数学模型，使所装物品价值最大。解：此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入01变量（或称逻辑变量）yi，令i=1,2分别是采用背包及旅行箱装载。运筹学4整数规划由于所装物品不变，约束条件左边不变，整数规划数学模型为例5.1中的数学模型为：运筹学4整数规划二、二、求解求解01整数规划的隐枚举法整数规划的隐枚举法(ImplicitEnumerat
19、ionMethod)隐枚举法的步骤：1.找出任意一可行解，目标函数值为Z0；2.原问题求最大值时，则增加一个约束当求最小值时，上式改为小于等于约束；3.列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值；4.目标函数值最大（最小）的解就是最优解。(*)5.40-1规划运筹学4整数规划【例【例5.6】用隐枚举法求下列01整数规划的最优解【解】容易求得X(1,0,0)是一可行解，Z06。加一个约束(0)由于3个变量每个变量取0或1，共有8种组合，用列表的方法检验每种组合解是否可行解，满足约束打上记号“”
20、，不满足约束打上记号“”，计算如表所示。运筹学4整数规划表变量组合约束(0)约束(1)约束(2)约束(3)Z（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）由表知，X（1，0，1）是最优解，最优值Z9。69运筹学4整数规划【例【例5.】用隐枚举法求下列01整数规划的最优解【解】容易求得X(,0,)是一可行解，Z0。加一个约束(0)运筹学4整数规划表53变量组合约束(0)约束(1)约束(2)约束(3)约束（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）由表53知，X（1
21、，0，1）是最优解，最优值Z。运筹学4整数规划【例例5.】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位只能一个人。经考核四人在不同工作岗位完成的时间如下表所示，如何安排他们的工作使总时间最少。工作人员ABCD甲85927390乙95877895丙82837990丁869080885.5指派问题指派问题及其数学模型运筹学4整数规划数学模型如下：工作人员ABCD甲85927390乙95877895丙82837990丁86908088运筹学4整数规划指派问题:n个人恰好做n项工作，第i个人做第j项工作的效率为cij，效率矩阵为cij,假设问题求最小值。运筹学4整数规划求解指派问
22、题的方法：匈牙利算法匈牙利算法匈牙利算法是匈牙利数学家克尼格（Konig）证明了下面两个基本定理，为计算分配问题奠定了基础。因此，基于两个定理基础上建立起来的解分配问题的计算方法被称为匈牙利法。运筹学4整数规划【定定理理5.2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立元素）的最大个数。如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，得到最优解。定理5.1告诉我们如何将效率表中的元素转换为有零元素，定理5.2告诉我们效率表中有多少个独立的“0”元素。【定定理理5.1】如果从
23、分配问题效率矩阵cij的每一行元素中分别减去（或加上）一个常数ui（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵bij，若其中bij=cijuivj,则bij的最优解等价于cij的最优解。这里cij、bij均非负。运筹学4整数规划【例例】已知四人分别完成四项工作所需时间如下表，求最优分配方案。运筹学4整数规划【解解】最优分配方案是怎样安排四人的工作，使得完成工作总时间最少，是求最小值问题。第一步：使各行各列中都出现元素找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有Min0042找出矩阵每列的最小元素，再分别从每列中减去，有Min
24、运筹学4整数规划从只有一个元素的行开始，给该元素加圈，同时划去该元素所在列的其它元素；从只有一个元素的列开始，给该元素加圈，同时划去该元素所在行的其它元素；第二步：在各行各列中找出独立的元素最优解：最优解：运筹学4整数规划【例例5.8】已知四人分别完成四项工作所需时间如下表，求最优分配方案。运筹学4整数规划【解解】最优分配方案是怎样安排四人的工作，使得完成工作总时间最少，是求最小值问题。第一步：使各行各列中都出现元素找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有Min3408找出矩阵每列的最小元素，再分别从每列中减去，有Min运筹学4整数规划从只有一个元素的行开始，给该元素加圈，同
25、时划去该元素所在列的其它元素；从只有一个元素的列开始，给该元素加圈，同时划去该元素所在行的其它元素；第二步：在各行各列中找出独立的元素运筹学4整数规划第三步：用最少的直线覆盖所有“0”，对没有的行打“”在已打“”的行中，对所有所在列打“”在已打“”的列中，对所在行打“”重复运筹学4整数规划第三步：用最少的直线覆盖所有“0”，对没有打“”的行画一横线，对打“”的列画一垂线运筹学4整数规划第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算。（1）从矩阵未被直线覆盖的数字中找出一个最小的数a，表中a。(2)直线相交处的元素加上a，未被直线覆盖的元素减去a，被直线覆盖而没有相交的元素不变，
26、得到下列矩阵运筹学4整数规划重复第二步:在各行各列中找出独立的元素运筹学4整数规划第五步：最优分配第五步：最优分配最优解：最优解：最优值最优值Z73878288330运筹学4整数规划工作人员ABCD甲85927390乙95877895丙82837990丁86908088甲C乙B丙A丁D最优分配最优分配运筹学4整数规划不平衡的指派问题不平衡的指派问题1当人数m小于工作数n时，加上nm个人，例如Min94100 运筹学4整数规划2当人数m大于工作数n时，加上mn项工作，例如运筹学4整数规划求最大值的指派问题求最大值的指派问题匈牙利法的条件是：模型求最小值、效率cij0令则与的最优解相同。设C=(c
27、ij)mm 对应的模型是求最大值将其变换为求最小值运筹学4整数规划【例例.9】某人事部门拟招聘4人任职4项工作，对他们综合考评的得分如下表（满分100分），如何安排工作使总分最高。【解】【解】M95，令，令运筹学4整数规划用匈牙利法求解：最优解：最优解：即甲安排做第二项工作、乙做第一项、丙做第四项、丁做第三项。总分为：总分为：Z92959080357运筹学4整数规划 其它其它某工厂订购了3台机器(A、B、C），有4个位置可供机器安装，但B机器不能安装在第二号位置。由于这4个安装位置离工厂中心的远近不同，所需要的运送费用也就不同，见下表。问这些机器安装在哪几个位置合适，可使总的运送费用达到最小。
28、位置位置机器机器一一二二三三四四A A1313101012121111B B1515- -13132020C C5 57 710106 6运筹学4整数规划解：1）在（B，二）处添上一个很大的数M，以排除机器B安装在二号位置的可能。2）在第四行虚设一行。运筹学4整数规划运筹学4整数规划本章介绍了整数规划的数学模型的特征及其应用；1整数规划的最优解是先求相应的线性规划的最优解然后取整得到.2部分变量要求是整数的规划问题称为纯整数规划.3求最大值问题的目标函数值是各分枝函数值的上界.4求最小值问题的目标函数值是各分枝函数值的下界.5变量取0或1的规划是整数规划.求解方法有：解一般整数规划用分枝定界法、割平面法；解01规划用隐枚举法；解指派问题用匈牙利法。试一试，下例结论是否正确：运筹学4整数规划6整数规划的可行解集合是离散型集合.7将指派（分配）问题的效率矩阵每行分别加上一个数后最优解不变.8匈牙利法求解指派问题的条件是效率矩阵的元素非负.9匈牙利法可直接求解极大化的指派问题.10高莫雷（R.E.Gomory）约束是将可行域中一部分非整数解切割掉.11指派问题也是一个特殊的运输问题.12指派问题也可用运输问题求其最优解.13在用隐枚举求解具有n个变量的0-1规划时需枚举2的n次幂个可能.作业：教材作业：教材PTheEndofChapter5运筹学4整数规划运筹学4整数规划
