第3章-整数规划课件

第三章整数规划第三章整数规划1目录3.1整数规划问题的提出3.2整数规划概述3.3分枝定界法3.4隐枚举法与0-1规划问题3.5匈牙利法与指派问题3.6整数规划问题的应用目录3.1整数规划问题的提出23.1整数规划问题的提出在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情形(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等，分数或小数的解答就不合要求。为了满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数线性规划(integerlinearprogramming)，简称ILP，整数线性规划是最近几十年来发展起来的规划论中的一个分支。3.1整数规划问题的提出在前面讨论的线性规划问题中，有些3问题举例某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？maxZ=2000x1+1000x25x1+4x2≤242x1+5x2

≤13x1.x2

≥0且为整数解此LP问题，得：X1=4.8，X2=0显然不是可行解和一般线性规划问题的区别问题举例某集装箱运输公司，箱型标准体积24m3，重量13T,4x1=4.8，x2=0，maxz=96若考虑用“四舍五入”的方法化整，能得到整数最优解吗？取x1=5，x2=0，不满足约束条件5x1+4x2≤24取x1=4，x2=0，满足约束条件，maxz=80取x1=4，x2=1，也满足约束条件，maxz=90可见，仅用四舍五入的取整法，不一定能求到最优解。因此，需要采用其他方法来求解。x1=4.8，x2=0，maxz=96若考虑用“四舍五入”5图解法：x1x243210124.8①2.6②(4,1)

∴x1*=4x2*=1zI*=90图解法：x1x243210124.8①2.6②(4,1)63.2整数规划概述整数规划是线性规划的延伸，指全部或者一部分决策变量要求取整数值的线性问题。分类：纯整数规划：全部决策变量都要求取整数混合整数规划：仅部分决策变量取整数0-1整数规划：全部决策变量只能取值0或1的整数规划（指派问题）求解方法：分枝定界法、割平面法、隐枚举法、匈牙利法3.2整数规划概述整数规划是线性规划的延伸，指全部或者一部73.3分枝定界法在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，就如图解法中画出所有“×”号的点那样，然后比较它们的目标函数值以定出最优解。对于小型的问题，变量数很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。对于大型的问题，可行的整数组合数是很大的。例如指派问题(这也是整数线性规划)中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10，这个数就超过300万；当n=20，这个数就超过2×1018，如果一一计算，就是用每秒百万次的计算机，也要几万年的功夫，很明显，解这样的题，穷举法是不可取的。所以我们的方法一般应是仅检查可行的整数组合的一部分，就能定出最优的整数解。分枝定界法(branchandboundmethod)就是其中的一个.3.3分枝定界法在求解整数线性规划时，如果可行域是有界的，8分枝定界法可用于解纯整数或混合的整数线性规划问题。在20世纪60年代初由LandDoig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数线性规划的重要方法。第3章-整数规划课件93.3.1基本思路根据某种策略将原问题对应的、不考虑整数要求的线性规划问题（松弛问题）的可行域分解为越来越小的子域，并检查每个子域内整数解的情况，直到找到最优的整数解或证明整数解不存在。3.3.1基本思路根据某种策略将原问题对应的、不考虑整数要10分枝：分解可行域在松弛问题的最优解中任选一个不符合整数条件的变量xj，其值为bj，以［bj］表示小于bj的最大整数。并构造两个约束条件xj≤［bj］和xj≥［bj］+1定界：不断寻找更好的整数解来修正问题的上下界分枝：分解可行域113.3.2求解步骤设整数规划问题对应的松弛问题为A，用单纯形法求出其最优解。可能有如下情况：问题A没有可行解，则整数规划问题无解，停止计算问题A有最优整数解，且同为整数规划问题的解，停止计算问题A有最优解，但非整数解。则分枝，不考虑整数条件求解这两个后继问题A1和A2。以每个后继问题为一分枝标明求解结果，若无整数解，则继续分枝，直到至少得到一个最优目标函数整数值。以此最优目标函数整数值为界（定界）若各分枝的值劣于界，则剪掉不再计算，否则继续分枝，定界。3.3.2求解步骤设整数规划问题对应的松弛问题为A，用单纯12例：分枝定界法求解思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解例maxZ=20x1+10x25x1+4x2≤242x1+5x2

≤13x1.x2

≥0且为整数解：先不考虑整数要求，解相应的LP问题，得：x1=4.8x2=0Z=96不是可行解Z=96是IP问题的上界，记为：Z=96例：分枝定界法求解思路：切割可行域，去掉非整数点。一次分枝变13分枝定界法（续）X1=4.8不符合要求，切掉4—5之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x1

≤4和x1≥5原问题分解为两个maxZ=20x1+10x2maxZ=20x1+10x25x1+4x2≤245x1+4x2≤242x1+5x2

≤13(IP1)2x1+5x2

≤13(IP2)x1

≤4x1≥5x1.x2

≥0且为整数x1.x2

≥0且为整数分枝定界法（续）X1=4.8不符合要求，切掉4—514分枝定界法（续）不考虑整数要求，解相应LP问题。解IP1得：x1=4,x2=1z=90解IP2得：无可行解此时可以断定IP问题的下界为90，记为Z=90

由于目前的分枝末梢最大值是90，故IP问题的上界便是90。由于Z=Z，此时已得IP问题的最优解，即x1=4,x2=1,Z=90分枝定界法（续）不考虑整数要求，解相应LP问题。15分枝定界法的解题步骤1、不考虑整数约束，解相应LP问题2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步3、任取一个非整数变量xi=bi，构造两个新的约束条件：xi

≤[bi],xi

≥[bi]+1,分别加入到上一个LP问题，形成两个新的分枝问题。4、不考虑整数要求，解分枝问题。若整数解的Z值>所有分枝末梢的Z值，则得最优解。否则，取Z值最大的非整数解，继续分解，Goto3分枝定界法的解题步骤1、不考虑整数约束，解相应LP问题16思考题：求下面的整数规划问题maxz=3x1+2x22x1+3x2≤142x1+x2

≤9x1.x2

≥0且为整数思考题：求下面的整数规划问题maxz=3x1+2x217分枝定界法:L0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L3：z3=13L4：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x2≤2x2≥3x1≤3x1≥4分枝定界法:L0：z0=14.75x1=3.25，x2=2.183.4隐枚举法与0-1规划问题3.4隐枚举法与0-1规划问题193.4.10-1规划问题及模型1、0-1规划问题的概念在整数规划问题中，若变量取值为0或者1，则为0-1规划问题。

0-1变量通常用来表示逻辑性选择的决策。3.4.10-1规划问题及模型1、0-1规划问题的概念202、0-1变量的应用例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设xj=10---选择开采第j个构造---不选择开采第j个构造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年总收益----投资额限制（1）表示选择性决策（投资场所的选定——相互排斥的计划）2、0-1变量的应用例1：某油田在10个有油气21例2某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai(i=1，2，…，7)可供选择。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?例2某公司拟在市东、西、南三区建立门市部。拟议中有7个位22解题时先引入0-1变量xi

(=1,2，…，7)

于是问题可列成：

解题时先引入0-1变量xi(=1,2，…，7)

于是问题23例3.在本章开始的集装箱运输中，关于运货的体积限制为5x1+4x2≤24(3-1)今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为7x1+3x2≤45(3-2)这两条件是互相排斥的。为统一在一个问题中，引入0-1变量y，令（2）表示选择性约束例3.在本章开始的集装箱运输中，关于运货的体积（2）表示选24

于是(3-1)式和(3-2)式可由下述的条件

(3-3)式和(3-4)式来代替：

5x1+4x2≤24+yM(3-3)

7x1+3x2≤45+(1-y)M(3-4)

其中M是充分大的数。可验证，当y=0时，(3-3)式就是(3-1)式，而(3-14)式自然成立，因而是多余的。当y=1时(3-4)式就是(3-2)式，而(3-3)式是多余的。引入的变量y不必出现在目标函数内，即认为在目标函数式内y的系数为0。如果有m个互相排斥的约束条件(≤型)：αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m

于是(3-1)式和(3-2)式可由下述的条件

(3-3)式25为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,…，m)和一个充分大的常数M，而下面这一组m+1个约束条件αi1x１+αi2x2+…+αinxn≤bi+yiM，i=1,2,…，m(3-5)y1+y2+…+ym=m-1(3-6)就合于上述要求。这是因为，由于(3-6)式，m个yi中只有一个能取0值，设yi*=0，代入(3-5)式，就只有i=i*的约束条件起作用，而别的式子都是多余的。为了保证这m个约束条件只有一个起作用，我们引入m个0-1变26例4：例1中，如果在开采中需用电力，解决的方案或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f度。当使用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。采用电网供电：∑djxjf采用自备柴油机发电：∑0.3djxjpj=110j=110+(1－y1)M+(1－y2)My1+y2=1y1,y2=0或1M-----非常大的正数例4：例1中，如果在开采中需用电力，解决的方案或由电网供电27(3)关于固定费用的问题

在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用(固定成本)的问题不能用一般线性规划来描述，但可改变为混合整数线性规划来解决，见下例。

(3)关于固定费用的问题

在讨论线性规划时，有些问题是要求28例5某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定投资高的生产方式(选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令xj表示采用第j种方式时的产量；cj表示采用第j种方式时每件产品的变动成本；kj表示采用第j种方式时的固定成本。为了说明成本的特点，暂不考虑其他约束条件。采用各种生产方式的总成本分别为例5某工厂为了生产某种产品，有几种不同的生产方式可供选择29在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量yj，令于是目标函数minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量30(3-7)式这个规定可由以下3个线性约束条件表示：xj≤yjM，j=1,2,3(3-8)其中M是个充分大的常数。(3-8)式说明，当xj＞0时yj必须为1；当xj=0时只有yj为0时才有意义，所以(3-8)式完全可以代替(3-7)式

因此，该整数规划的数学模型为：minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)xj≤yjM，st.xj≥0且为整数，j=1,2,3yj=0或1，j=1,2,3其中M是个充分大的常数。(3-7)式这个规定可由以下3个线性约束条件表示：xj≤yj313.4.2隐枚举法隐枚举法是求解0-1规划问题的一种简便方法本质也是分枝定界法隐枚举法类似于穷举法，区别在于：隐枚举法不需要把全部可行解一一列举，而是通过分析判断，排除一些变量组合，从而得出最优方案。3.4.2隐枚举法隐枚举法是求解0-1规划问题的一种简32计算步骤①化标准形(隐枚举法)：1)目标函数极小化2)约束条件化成 3)使目标函数系数皆为非负,若xj系数为负值,则令xj=1-xj 4)使目标函数按变量系数由小→大顺序排列，约束条件变 量排列的顺序要与之对应。（能减少运算量，让最优解较早出现）②令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约束条件，若满足，即为最优解；否则，分枝计算。③分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后检查是否满足所有约束，若满足，转下步；否则继续分枝。④剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a)对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b)>zmin分枝，剪掉； (c)能判断出为无可行解的分枝，剪掉； (d)非上述情况，继续分枝。 计算步骤①化标准形(隐枚举法)：1)目标函数极小化33例：求解下述0-1规划问题：Maxz=8x1+2x2-4x3-7x4-5x5 st.3x1+3x2+x3+2x4+3x5

4 5x1+3x2-2x3-x4+x54 xj=0或1(j=1,2,3,4,5)1)目标函数极小化:minz=-8x1-2x2+4x3+7x4+5x5①化标准形：2)约束条件：-3x1-3x2-x3-2x4-3x5

-4 -5x1-3x2+2x3+x4-x5-4 xj=0或1(j=1,2,3,4,5)例：求解下述0-1规划问题：Maxz=8x1+2x2343)使目标函数系数皆为正：令x1=1-x1，x2=1-x2

minz=-8+8x1-2+2x2+4x3+7x4+5x5st.-3+3x1-3+3x2-x3-2x4-3x5

-4-5+5x1-3+3x2+2x3+x4-x5-4x1,x2,xj=0或1(j=3,4,5)4)变量按顺序排列：minz=2x2+4x3+5x5+7x4+8x1-10st.3x2-x3-3x5-2x4+3x1

23x2+2x3-x5+x4+5x14x1,x2,xj=0或1(j=3,4,5)xj=0或13)使目标函数系数皆为正：令x1=1-x135求解图示：1234567891011z=-10z

=-8z=-4z=-6z=-5z=-1z=1z=-5z=-3z=-6x2=1x2=0x3=1x3=0x3=1x3=1x5=1x5=0x5=1x5=0z=-3√×××××求解图示：1234567891011z=-10z=-836例6：某公司欲对三个项目投资，投资金额与收益如下表所示，问应对哪几个项目投资，获利最大？投资年度项目投资金额IIIIII10425251273403745136纯利润20816例6：某公司欲对三个项目投资，投资金额与收益如下表所示，问应37例6解：

0当项目未被选中投资1当项目被选中投资maxZ=20x1+8x2+16x3

4x2+2x3≤

5st.5x1+x2+2x3

≤

7

4x1+3x3≤

7

5x1+x2+3x3≤

6

xj=0或1j=1，2,…,3建模：设xj=例6解：建模：设x38第一步：将决策变量按系数从小到大的顺序排列（若求最小化，则从大到小排列）maxZ=8x2+16x3+20x1

4x1+2x2+0x1≤

5st.x2+2x3+5x1

≤

7

0x2+3x3+

4x1≤

7

x2+3x3+5x1≤

6

xj=0或1

j=1，2,…,3第一步：将决策变量按系数从小到大的顺序排列（若求最小化，则从39求解第二步：求解过程如下表所示（x2,x3,x1）Z值（1，1，1）X

XX44（0，1，1）X36（1，0，1）28（1，1，0）X24（1，0，0）

8（0，1，0）

16（0，0，1）

20（0，0，0）

0求解第二步：求解过程如下表所示（x2,x3,x1）403.5匈牙利法与指派问题3.5匈牙利法与指派问题413.5.1指派问题在物流活动中经常遇到这样的问题：需完成n项运输任务，恰好有n辆车可承担这些任务。由于车型、载重以及司机对道路熟悉程度等方面的不同，效率也不同。于是产生应指派哪辆车去完成哪项运输任务，使完成总效率最高(或所需费用最小)。这类问题称为指派问题或分派问题(assignmentproblem)。3.5.1指派问题在物流活动中经常遇到这样的问题：需完成42例7：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、丙、丁四辆车，他们完成任务所需时间如表所示。问应指派何人去完成何工作，使所需总时间最少？完成任务所需时间表任务人员ABCD甲215134乙1041415丙9141613丁78119类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题；有n条航线，怎样指定n艘船去航行问题……。例7：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、43对应每个指派问题，需有类似表1那样的数表，称为效率矩阵或系数矩阵，其元素cij＞0(i,j=1,2，…，n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)。解题时需引入变量xij；其取值只能是1或0。并令

对应每个指派问题，需有类似表1那样的数表，称为效率矩阵或系数44给例7建立模型：设xij=10A：x11+x12+x13+x14=1B：x21+x22+x23+x24=1C：x31+x32+x33+x34=1D：x41+x42+x43+x44=1甲：x11+x21+x31+x41=1乙：x12+x22+x32+x42=1丙：x13+x23+x33+x43=1丁：x14+x24+x34+x44=1xij=0或1(i=1,2,3,4;j=1,2,3,4)minz=cijxij (cij---效率)i=1j=144若第i项工作交与第j个人完成若第i项工作不交与第j个人完成给例7建立模型：设xij=10A：x11+x12+x45指派问题一般数学模型结构：设有m项工作要交与m个人完成，其中第i项工作交与第j个人完成时所需花费的时间为cij。规定每项工作只能交与其中的一个人完成，而每个人只能完成其中的一项工作。问：如何分配，可使所需的总时间最少？①②③④指派问题一般数学模型结构：设有m项工作要交与m个人46显然，解矩阵(xij)中各行各列的元素之和都是1。但这不是最优。约束条件②说明第j项任务只能由1人去完成；约束条件③说明第i人只能完成1项任务。满足约束条件②～④的可行解xij也可写成表格或矩阵形式，称为解矩阵。如例7的一个可行解矩

显然，解矩阵(xij)中各行各列的元素之和都是1。但这不是最47指派问题解的特点指派问题的最优解有这样性质，若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。指派问题解的特点指派问题的最优解有这样性质，若从系数矩阵(c483.5.2匈牙利法以下用例7来说明指派问题的解法——匈牙利法。

第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。

(1)从系数矩阵的每行元素减去该行的最小元素；

(2)再从所得系数矩阵的每列元素中减去该列的最小元素。

若某行(列)已有0元素，那就不必再减了。

例7的计算为

3.5.2匈牙利法以下用例7来说明指派问题的解法——匈牙利49行列都有零元素行列都有零元素50第二步：进行试指派，以寻求最优解。为此，按以下步骤进行。经第一步变换后，系数矩阵中每行每列都已有了0元素；但需找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。当n较小时，可用观察法、试探法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找，常用的步骤为：

第二步：进行试指派，以寻求最优解。为此，按以下步骤进行。51(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。这表示对这行所代表的人，只有一种任务可指派。然后划去◎所在列(行)的其他0元素，记作Φ。这表示这列所代表的任务已指派完，不必再考虑别人了。(2)给只有一个0元素列(行)的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Φ。(3)反复进行(1)，(2)两步，直到所有0元素都被圈出和划掉为止。

(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记52(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个(表示对这个可以从两项任务中指派其一)。这可用不同的方案去试探。从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。(5)若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m＜n，则转入下一步。(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两53现用例7的(bij)矩阵，按上述步骤进行运算。按步骤(1)，先给b22加圈，然后给b31加圈，划掉b11，b41；按步骤(2)，给b43加圈，划掉b44，最后给b14加圈，得到01370606905320100这表明：指定甲完成任务D，乙完成任务B，丙完成任务A，丁完成任务C。所需总时间最少minz=28ABCD甲乙丙丁现用例7的(bij)矩阵，按上述步骤进行运算。按步骤(1)，543.6整数规划模型的应用例1：在未来四个月中，某制鞋厂必须按时完成下述合同要求，第一个月300双，第二个月500双，第三个月100双，第四个月100双。在一月初，工厂已有50双鞋（以前的存货）和3名工人，每名工人的月薪为1500元，每月可工作160小时（正常工作时间）。一名工人最多还可有20小时的加班工作时间（规定），在加班工作时，每小时需付25元的加班费用。制作一双鞋需耗费4个工时和5元的原料费。在每月的开始，可以租用和解雇工人。每雇用一名工人需支付1600元的费用，每解雇一名工人需支付2000元的解雇费用。在每月末，要为留在仓库里未交货的每双鞋支付30元的保管维护费用。一个月生产的产品可用于满足多个月的需求。试用ILP方法确定最佳的生产计划和用工政策。3.6整数规划模型的应用例1：在未来55问题分析：需要解决的问题：每月租进、解雇、使用的工人数每月所需的加班时间每月在正常时间、加班时间生产的鞋子的数量每月开始和结束时库存鞋子的数量费用明细：雇工费、解雇费、用工费、加班费、原料费问题分析：需要解决的问题：56月初人数本月雇用本月解雇本月使用用工过程图示：生产过程图示：正常生产加班生产月初库存月末库存交货数量工人数鞋子数月初人数本月雇用本月解雇本月使用用工过程图示：生产过程图示57建模思路：每月可用工人≥0每月库存鞋子≥0可用工人数=月初数+租进数-解雇数=月末数月末库存量=月初库存+正常生产+加班生产-交货量目标函数=总费用 =月薪+雇用费+解雇费+加班费+原料费+库存费建模思路：每月可用工人≥0每月库存鞋子≥0可用工人数58例2：某海军部队在三个征兵中心征招新兵。新兵必须送到三个海军训练基地中的一个进行训练，从每个征兵中心运送一个新兵至某一个训练基地的费用如表1所示（单位：元）。每年在中心1征招1000名士兵，中心2征召600名，中心3征召700名。基地1可训练1000名，基地2可训练800名，基地3可训练700名。fromtoBase1Base2Base3Center1Center2Center3240200300300400220300400250新兵受训后，要送到海军部队。运送时可采用小船或大船两种工具，共有7条小船和3条大船可供使用。若使用小船，则每条船要花费5000元加上每海里2元的费用；使用大船要花费10000元加上每海里3元的费用。一条小船可运送200人，沿途最多可经过2个训练基地；一条大船可运送500人，最多可经过3个训练基地。可能的航线如表2中所示。现问，应怎样决策，能使发生的总费用最少？表1例2：某海军部队在三个征兵中心征招新兵。新兵59途径训练基地航程（海里）航线1234567

B—1—B370B—1—2—B515B—2—3—B665B—2—B460B—3—B600B—1—3—B640B—1—2—3—B720表2需要解决的问题：(1)Centeri→Basej运送的人数(2)Basej实际训练人数(3)第i航线运送第j基地人数(4)第i航线使用小船数量(5)第i航线使用大船数量(6)征兵中心至训练基地运送费用(7)训练基地至海军部队运送费用(8)总费用途径训练基地航程（海里）航线1B—1—B60例3：仓库位置问题韩德公司有五个生产番茄酱的工厂，每个工厂的生产能力如表1所示。生产出来的番茄酱可储存在三个成品库中，从各工厂运送一吨产品到各成品库的费用如表2所示。由于某些因素，公司销售看淡，现只有四家客户，其需求量如表3所示。从各成品库运送成品到各客户的需求地的单位费用如表4所示。每个工厂和每个成品库运营的年固定费用如表5所示。公司想确定关闭那些工厂和仓库，会使总费用最低。表1生产能力工厂12345能力(吨)300200300200400表3客户需求客户1234需求(吨)200300150250表2工厂—成品库运费表工厂仓库成品库1成品库2成品库31234580010001200700500700800600500500600700700600500(元/吨)例3：仓库位置问题韩德公司有五个生产番茄酱的61表4成品库—客户运输费用（元/吨）成品库客户成品库1成品库2成品库3123440

8090507040608080305060表5年运营固定费用（元）工厂1工厂2工厂3工厂4工厂5成品库1成品库2成品库33500045000400004200040000400002000060000表4成品库—客户运输费用（元/吨）成品库客户成品库162建模思路xi——0-1变量，第i厂是否开；yj——0-1变量，第j库是否开。0-1规划与运输问题的混合模型。费用：工厂——成品库运输费用+开工费； 成品库——客户运输费用+成品库运营费。建模思路xi——0-1变量，第i厂是否开；yj——0-163例4：资产运作滚动计划某养殖场饲养6头黑熊（资产），在未来三年内对该6头黑熊的预期收入如表中所示（以千元计）。为维持养殖场的正常的资金周转，该厂必须在第一年获取20000元的收入，第二年获取30000元的收入，第三年获取35000元的收入。试确定，该养殖场应采取怎样的销售计划，可使三年中获得的总收入最大？123456year1year2year315 20 2416 18 2122 30 3610 20 3017 19 2219 25 29黑熊建模提示：⑴利用0-1变量表示在某年出售与否的关系；⑵三年内熊必须出售且只能出售一次；⑶每年的销售收入必须能保证需求；⑷每年的剩余资金可移作第二年使用。例4：资产运作滚动计划某养殖场饲养6头黑熊（64本章小结整数规划问题与分枝定界法（定义、建模及求解的基本思路）隐枚举法与0-1规划问题（定义、建模，会用隐枚举法求解0-1规划问题）匈牙利法与指派问题（定义、建模）本章小结整数规划问题与分枝定界法（定义、建模及求解的基本思路65第三章整数规划第三章整数规划66目录3.1整数规划问题的提出3.2整数规划概述3.3分枝定界法3.4隐枚举法与0-1规划问题3.5匈牙利法与指派问题3.6整数规划问题的应用目录3.1整数规划问题的提出673.1整数规划问题的提出在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情形(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等，分数或小数的解答就不合要求。为了满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数线性规划(integerlinearprogramming)，简称ILP，整数线性规划是最近几十年来发展起来的规划论中的一个分支。3.1整数规划问题的提出在前面讨论的线性规划问题中，有些68问题举例某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？maxZ=2000x1+1000x25x1+4x2≤242x1+5x2

≤13x1.x2

≥0且为整数解此LP问题，得：X1=4.8，X2=0显然不是可行解和一般线性规划问题的区别问题举例某集装箱运输公司，箱型标准体积24m3，重量13T,69x1=4.8，x2=0，maxz=96若考虑用“四舍五入”的方法化整，能得到整数最优解吗？取x1=5，x2=0，不满足约束条件5x1+4x2≤24取x1=4，x2=0，满足约束条件，maxz=80取x1=4，x2=1，也满足约束条件，maxz=90可见，仅用四舍五入的取整法，不一定能求到最优解。因此，需要采用其他方法来求解。x1=4.8，x2=0，maxz=96若考虑用“四舍五入”70图解法：x1x243210124.8①2.6②(4,1)

∴x1*=4x2*=1zI*=90图解法：x1x243210124.8①2.6②(4,1)713.2整数规划概述整数规划是线性规划的延伸，指全部或者一部分决策变量要求取整数值的线性问题。分类：纯整数规划：全部决策变量都要求取整数混合整数规划：仅部分决策变量取整数0-1整数规划：全部决策变量只能取值0或1的整数规划（指派问题）求解方法：分枝定界法、割平面法、隐枚举法、匈牙利法3.2整数规划概述整数规划是线性规划的延伸，指全部或者一部723.3分枝定界法在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，就如图解法中画出所有“×”号的点那样，然后比较它们的目标函数值以定出最优解。对于小型的问题，变量数很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。对于大型的问题，可行的整数组合数是很大的。例如指派问题(这也是整数线性规划)中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10，这个数就超过300万；当n=20，这个数就超过2×1018，如果一一计算，就是用每秒百万次的计算机，也要几万年的功夫，很明显，解这样的题，穷举法是不可取的。所以我们的方法一般应是仅检查可行的整数组合的一部分，就能定出最优的整数解。分枝定界法(branchandboundmethod)就是其中的一个.3.3分枝定界法在求解整数线性规划时，如果可行域是有界的，73分枝定界法可用于解纯整数或混合的整数线性规划问题。在20世纪60年代初由LandDoig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数线性规划的重要方法。第3章-整数规划课件743.3.1基本思路根据某种策略将原问题对应的、不考虑整数要求的线性规划问题（松弛问题）的可行域分解为越来越小的子域，并检查每个子域内整数解的情况，直到找到最优的整数解或证明整数解不存在。3.3.1基本思路根据某种策略将原问题对应的、不考虑整数要75分枝：分解可行域在松弛问题的最优解中任选一个不符合整数条件的变量xj，其值为bj，以［bj］表示小于bj的最大整数。并构造两个约束条件xj≤［bj］和xj≥［bj］+1定界：不断寻找更好的整数解来修正问题的上下界分枝：分解可行域763.3.2求解步骤设整数规划问题对应的松弛问题为A，用单纯形法求出其最优解。可能有如下情况：问题A没有可行解，则整数规划问题无解，停止计算问题A有最优整数解，且同为整数规划问题的解，停止计算问题A有最优解，但非整数解。则分枝，不考虑整数条件求解这两个后继问题A1和A2。以每个后继问题为一分枝标明求解结果，若无整数解，则继续分枝，直到至少得到一个最优目标函数整数值。以此最优目标函数整数值为界（定界）若各分枝的值劣于界，则剪掉不再计算，否则继续分枝，定界。3.3.2求解步骤设整数规划问题对应的松弛问题为A，用单纯77例：分枝定界法求解思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解例maxZ=20x1+10x25x1+4x2≤242x1+5x2

≤13x1.x2

≥0且为整数解：先不考虑整数要求，解相应的LP问题，得：x1=4.8x2=0Z=96不是可行解Z=96是IP问题的上界，记为：Z=96例：分枝定界法求解思路：切割可行域，去掉非整数点。一次分枝变78分枝定界法（续）X1=4.8不符合要求，切掉4—5之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x1

≤4和x1≥5原问题分解为两个maxZ=20x1+10x2maxZ=20x1+10x25x1+4x2≤245x1+4x2≤242x1+5x2

≤13(IP1)2x1+5x2

≤13(IP2)x1

≤4x1≥5x1.x2

≥0且为整数x1.x2

≥0且为整数分枝定界法（续）X1=4.8不符合要求，切掉4—579分枝定界法（续）不考虑整数要求，解相应LP问题。解IP1得：x1=4,x2=1z=90解IP2得：无可行解此时可以断定IP问题的下界为90，记为Z=90

由于目前的分枝末梢最大值是90，故IP问题的上界便是90。由于Z=Z，此时已得IP问题的最优解，即x1=4,x2=1,Z=90分枝定界法（续）不考虑整数要求，解相应LP问题。80分枝定界法的解题步骤1、不考虑整数约束，解相应LP问题2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步3、任取一个非整数变量xi=bi，构造两个新的约束条件：xi

≤[bi],xi

≥[bi]+1,分别加入到上一个LP问题，形成两个新的分枝问题。4、不考虑整数要求，解分枝问题。若整数解的Z值>所有分枝末梢的Z值，则得最优解。否则，取Z值最大的非整数解，继续分解，Goto3分枝定界法的解题步骤1、不考虑整数约束，解相应LP问题81思考题：求下面的整数规划问题maxz=3x1+2x22x1+3x2≤142x1+x2

≤9x1.x2

≥0且为整数思考题：求下面的整数规划问题maxz=3x1+2x282分枝定界法:L0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L3：z3=13L4：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x2≤2x2≥3x1≤3x1≥4分枝定界法:L0：z0=14.75x1=3.25，x2=2.833.4隐枚举法与0-1规划问题3.4隐枚举法与0-1规划问题843.4.10-1规划问题及模型1、0-1规划问题的概念在整数规划问题中，若变量取值为0或者1，则为0-1规划问题。

0-1变量通常用来表示逻辑性选择的决策。3.4.10-1规划问题及模型1、0-1规划问题的概念852、0-1变量的应用例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设xj=10---选择开采第j个构造---不选择开采第j个构造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年总收益----投资额限制（1）表示选择性决策（投资场所的选定——相互排斥的计划）2、0-1变量的应用例1：某油田在10个有油气86例2某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai(i=1，2，…，7)可供选择。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?例2某公司拟在市东、西、南三区建立门市部。拟议中有7个位87解题时先引入0-1变量xi

(=1,2，…，7)

于是问题可列成：

解题时先引入0-1变量xi(=1,2，…，7)

于是问题88例3.在本章开始的集装箱运输中，关于运货的体积限制为5x1+4x2≤24(3-1)今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为7x1+3x2≤45(3-2)这两条件是互相排斥的。为统一在一个问题中，引入0-1变量y，令（2）表示选择性约束例3.在本章开始的集装箱运输中，关于运货的体积（2）表示选89

于是(3-1)式和(3-2)式可由下述的条件

(3-3)式和(3-4)式来代替：

5x1+4x2≤24+yM(3-3)

7x1+3x2≤45+(1-y)M(3-4)

其中M是充分大的数。可验证，当y=0时，(3-3)式就是(3-1)式，而(3-14)式自然成立，因而是多余的。当y=1时(3-4)式就是(3-2)式，而(3-3)式是多余的。引入的变量y不必出现在目标函数内，即认为在目标函数式内y的系数为0。如果有m个互相排斥的约束条件(≤型)：αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m

于是(3-1)式和(3-2)式可由下述的条件

(3-3)式90为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,…，m)和一个充分大的常数M，而下面这一组m+1个约束条件αi1x１+αi2x2+…+αinxn≤bi+yiM，i=1,2,…，m(3-5)y1+y2+…+ym=m-1(3-6)就合于上述要求。这是因为，由于(3-6)式，m个yi中只有一个能取0值，设yi*=0，代入(3-5)式，就只有i=i*的约束条件起作用，而别的式子都是多余的。为了保证这m个约束条件只有一个起作用，我们引入m个0-1变91例4：例1中，如果在开采中需用电力，解决的方案或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f度。当使用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。采用电网供电：∑djxjf采用自备柴油机发电：∑0.3djxjpj=110j=110+(1－y1)M+(1－y2)My1+y2=1y1,y2=0或1M-----非常大的正数例4：例1中，如果在开采中需用电力，解决的方案或由电网供电92(3)关于固定费用的问题

在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用(固定成本)的问题不能用一般线性规划来描述，但可改变为混合整数线性规划来解决，见下例。

(3)关于固定费用的问题

在讨论线性规划时，有些问题是要求93例5某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定投资高的生产方式(选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令xj表示采用第j种方式时的产量；cj表示采用第j种方式时每件产品的变动成本；kj表示采用第j种方式时的固定成本。为了说明成本的特点，暂不考虑其他约束条件。采用各种生产方式的总成本分别为例5某工厂为了生产某种产品，有几种不同的生产方式可供选择94在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量yj，令于是目标函数minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量95(3-7)式这个规定可由以下3个线性约束条件表示：xj≤yjM，j=1,2,3(3-8)其中M是个充分大的常数。(3-8)式说明，当xj＞0时yj必须为1；当xj=0时只有yj为0时才有意义，所以(3-8)式完全可以代替(3-7)式

因此，该整数规划的数学模型为：minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)xj≤yjM，st.xj≥0且为整数，j=1,2,3yj=0或1，j=1,2,3其中M是个充分大的常数。(3-7)式这个规定可由以下3个线性约束条件表示：xj≤yj963.4.2隐枚举法隐枚举法是求解0-1规划问题的一种简便方法本质也是分枝定界法隐枚举法类似于穷举法，区别在于：隐枚举法不需要把全部可行解一一列举，而是通过分析判断，排除一些变量组合，从而得出最优方案。3.4.2隐枚举法隐枚举法是求解0-1规划问题的一种简97计算步骤①化标准形(隐枚举法)：1)目标函数极小化2)约束条件化成 3)使目标函数系数皆为非负,若xj系数为负值,则令xj=1-xj 4)使目标函数按变量系数由小→大顺序排列，约束条件变 量排列的顺序要与之对应。（能减少运算量，让最优解较早出现）②令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约束条件，若满足，即为最优解；否则，分枝计算。③分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后检查是否满足所有约束，若满足，转下步；否则继续分枝。④剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a)对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b)>zmin分枝，剪掉； (c)能判断出为无可行解的分枝，剪掉； (d)非上述情况，继续分枝。 计算步骤①化标准形(隐枚举法)：1)目标函数极小化98例：求解下述0-1规划问题：Maxz=8x1+2x2-4x3-7x4-5x5 st.3x1+3x2+x3+2x4+3x5

4 5x1+3x2-2x3-x4+x54 xj=0或1(j=1,2,3,4,5)1)目标函数极小化:minz=-8x1-2x2+4x3+7x4+5x5①化标准形：2)约束条件：-3x1-3x2-x3-2x4-3x5

-4 -5x1-3x2+2x3+x4-x5-4 xj=0或1(j=1,2,3,4,5)例：求解下述0-1规划问题：Maxz=8x1+2x2993)使目标函数系数皆为正：令x1=1-x1，x2=1-x2

minz=-8+8x1-2+2x2+4x3+7x4+5x5st.-3+3x1-3+3x2-x3-2x4-3x5

-4-5+5x1-3+3x2+2x3+x4-x5-4x1,x2,xj=0或1(j=3,4,5)4)变量按顺序排列：minz=2x2+4x3+5x5+7x4+8x1-10st.3x2-x3-3x5-2x4+3x1

23x2+2x3-x5+x4+5x14x1,x2,xj=0或1(j=3,4,5)xj=0或13)使目标函数系数皆为正：令x1=1-x1100求解图示：1234567891011z=-10z

=-8z=-4z=-6z=-5z=-1z=1z=-5z=-3z=-6x2=1x2=0x3=1x3=0x3=1x3=1x5=1x5=0x5=1x5=0z=-3√×××××求解图示：1234567891011z=-10z=-8101例6：某公司欲对三个项目投资，投资金额与收益如下表所示，问应对哪几个项目投资，获利最大？投资年度项目投资金额IIIIII10425251273403745136纯利润20816例6：某公司欲对三个项目投资，投资金额与收益如下表所示，问应102例6解：

0当项目未被选中投资1当项目被选中投资maxZ=20x1+8x2+16x3

4x2+2x3≤

5st.5x1+x2+2x3

≤

7

4x1+3x3≤

7

5x1+x2+3x3≤

6

xj=0或1j=1，2,…,3建模：设xj=例6解：建模：设x103第一步：将决策变量按系数从小到大的顺序排列（若求最小化，则从大到小排列）maxZ=8x2+16x3+20x1

4x1+2x2+0x1≤

5st.x2+2x3+5x1

≤

7

0x2+3x3+

4x1≤

7

x2+3x3+5x1≤

6

xj=0或1

j=1，2,…,3第一步：将决策变量按系数从小到大的顺序排列（若求最小化，则从104求解第二步：求解过程如下表所示（x2,x3,x1）Z值（1，1，1）X

XX44（0，1，1）X36（1，0，1）28（1，1，0）X24（1，0，0）

8（0，1，0）

16（0，0，1）

20（0，0，0）

0求解第二步：求解过程如下表所示（x2,x3,x1）1053.5匈牙利法与指派问题3.5匈牙利法与指派问题1063.5.1指派问题在物流活动中经常遇到这样的问题：需完成n项运输任务，恰好有n辆车可承担这些任务。由于车型、载重以及司机对道路熟悉程度等方面的不同，效率也不同。于是产生应指派哪辆车去完成哪项运输任务，使完成总效率最高(或所需费用最小)。这类问题称为指派问题或分派问题(assignmentproblem)。3.5.1指派问题在物流活动中经常遇到这样的问题：需完成107例7：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、丙、丁四辆车，他们完成任务所需时间如表所示。问应指派何人去完成何工作，使所需总时间最少？完成任务所需时间表任务人员ABCD甲215134乙1041415丙9141613丁78119类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题；有n条航线，怎样指定n艘船去航行问题……。例7：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、108对应每个指派问题，需有类似表1那样的数表，称为效率矩阵或系数矩阵，其元素cij＞0(i,j=1,2，…，n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)。解题时需引入变量xij；其取值只能是1或0。并令

对应每个指派问题，需有类似表1那样的数表，称为效率矩阵或系数109给例7建立模型：设xij=10A：x11+x12+x13+x14=1B：x21+x22+x23+x24=1C：x31+x32+x33+x34=1D：x41+x42+x43+x44=1甲：x11+x21+x31+x41=1乙：x12+x22+x32+x42=1丙：x13+x23+x33+x43=1丁：x14+x24+x34+x44=1xij=0或1(i=1,2,3,4;j=1,2,3,4)minz=cijxij (cij---效率)i=1j=144若第i项工作交与第j个人完成若第i项工作不交与第j个人完成给例7建立模型：设xij=10A：x11+x12+x110指派问题一般数学模型结构：设有m项工作要交与m个人完成，其中第i项工作交与第j个人完成时所需花费的时间为cij。