《管理运筹学第四章整数规划与指派问题.ppt》由会员分享，可在线阅读，更多相关《管理运筹学第四章整数规划与指派问题.ppt（76页珍藏版）》请在三一办公上搜索。
1、第四章 整数规划与指派问题,2017年4月,北京物资学院运筹学课件,线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划(Integer Programming)。,第一节 整数线性规划问题的数学模型第二节 整数规划的求解方法*第三节 指派问题及匈牙利解法,本章内容的安排,第一节 整数线性规划问题的数学模型,引例逻辑变量在整数规划建模中的作用整数规划问题的特征与性质整数规划模型的分类
2、,例1（装载问题）有一辆卡车的最大载重量为b 吨,现有n 种货物可供装载。设第j 种货物每件重aj 吨,每件的装载费用为cj 元(j=1,n)。问应该采用怎样的装载方案才能使卡车一次装载货物的收入最大?,解:设xj为卡车装载第j 种货物的件数(j=1,2,n),z表示卡车一次装载的收入,则该问题的数学模型为max z=c1x1+c2x2+c n x ns.t.a1x1+a2x2+a n x n b x j 0 且为整数(j=1,2,n),1.引例,例2.（选址问题相互排斥的计划）某公司准备投资100万元在甲、乙两座城市修建健身中心，经过多方考察，最后选定A1,A2,A3,A4和A5五个位置，并
3、且决定在甲城市的A1、A2、A3三个位置中最多投建两个；在乙城市的A4、A5两个位置中最少投建一个。如果已知各点的投资金额和年利润如下表。问：健身中心投建在哪些位置才会使总的年利润最大？,解：设,则该问题的数学模型为,例 3 工厂选址问题：某商品有n 个销地，各销地的需求量为bj 吨/天；现拟在m个地点中选址建生产厂，一个地点最多只能建一个工厂；若选i 地建厂，生产能力为ai吨/天，固定费用为di元/天；已知i 地至第j 销地的单位运费为cij元/吨。问如何选址和安排调运，才能使总费用最小？,设：yi=1，表示选择第i 地建厂，yi=0，表示不选择第i 地建厂；从厂址i 至销地j 运量为xij
4、，总费用为z。,该问题的数学模型为,例4 某公司制造小、中、大3种尺寸的金属容器，所用的资源为金属板、劳动力和机时。制造一只容器所需的各种资源数量如下表所示，不考虑固定费用，每售出一只小、中、大号容器所得的利润分别为4元、5元、6元，可使用的金属板有500张，劳动力有300个，机时有100小时，如果生产某种容器，不管生产数量多少，都要支付一笔固定费用，小、中、大号容器的固定费用分别为100元、150元、200元，现要制订一生产计划，使获得的利润最大。,解：设x1,x2,x3分别表示小、中、大号容器的生产数量，M为很大的正数，z表示总利润,引入逻辑变量,若xj=0时，yj=0,若xj0时，yj=
5、1。,2.逻辑变量在整数规划建模中的作用,(1)m个约束条件中只有k个起作用。,定义,则上述条件可以表示成,(2)约束条件的右端可能是 r个值中的某一个,定义,则上述条件可以表示成,(3)两组条件中满足其中的一组,定义,则问题可以表示为,4 用以表示含固定费用的函数,总费用,目标函数是总费用最小,定义,则目标函数可以表示成,3.整数规划问题的特征与性质,特征变量整数性要求来源 问题本身的要求 引入的逻辑变量的需要性质可行域是离散集合,4.整数规划的分类,纯整数规划 要求全部决策变量的取值都为整数,则称为纯整数规划(All IP)；混合整数规划仅要求部分决策变量的取值为整数，则称为混合整数规划(
6、Mixed IP)；0-1整数规划要求决策变量只能取0或1值，则称为0-1规划(0-1 Programming)。,第二节 整数规划的求解方法,分支定界法割平面法,1.分支定界法,整数规划ILP,放松的线性规划LP,分枝定界法是本世纪60年代初由Land Doig和Dakin等人提出的，可用于解纯整数规划或混合整数规划。,整数规划问题的最优目标函数等值线,放松问题的最优目标函数等值线,整数规划的最优解不一定在顶点上达到；整数规划的最优解不一定是放松问题最优解的邻近整数解；整数可行解的个数远多于顶点个数，枚举法不可取。,整数规划ILP和放松问题LP的关系 ILP的可行区域是LP的可行区域的子集；
7、如果LP无可行解，则ILP无可行解；LP的最优值是ILP的最优值的一个上界；若LP的最优解为整数向量，则它也是ILP的最优解。,整数规划ILP,放松的线性规划LP,分枝定界法的基本思想,先求放松的LP的最优解，若放松LP问题无解，则原ILP问题也无解。若放松LP问题的最优解符合整数要求，则是原ILP的最优解；若放松LP问题的最优解含非整数分量，则将ILP问题分为几个子问题，试图做到：要么找到某个子问题的最优解，要么判断原问题ILP的最优解一定不在子问题的可行区域内。,分枝定界法的算法流程：,解LP,无可行解,问题无界,ILP无解或无界,解x0为整数向量,x0为ILP的解,x0有非整分量,将原问
8、题分解为两个子问题，使得非整分量恰好排除在外而又没有去掉原问题的可行解，再分别判断两个子问题。,如果最优解x i中某个分量 非整,分枝定界法的两个要点：分枝和定界如何分枝？,分枝定界法的两个要点：分枝和定界如何定界？,整数规划ILP的最优解不会优于松弛LP的最优解；对极大化问题来说，松弛 LP 的目标函数最优值是原整数规划ILP目标函数值的上界；如果当前的ILP最好的整数解的目标函数值不小于某一 子问题的目标函数值，则可剪枝。,例5：求解下列整数线性规划问题,解：先求与之对应的线性规划问题（放松问题）,(18/11,40/11)z 0=218/11,B:(1,3),z 1=16C:(2,10/
9、3),z2=56/3,分枝 x1 1,x1 2,(LP0)的解不是(ILP0)的解,（LP0）z0=218/11x 1=18/11,x 2=40/11,（LP1）z1=16x 1=1,x 2=3,（LP2）z2=18.66x 1=2,x 2=10/3,x 11,x 1 2,LP1有整数解,已探明,剪枝,定下界z1=16LP2:z2=18.66 z1=16,可能有比z1更优的解分枝:在LP2 中加入x2 3 x2 4 分成(LP3),(LP4),(LP3)max z=x1+5x2 s.t.x1+x2 2 5x1+6x2 30 2 x1 4 x2 3 x1 0,x2 0,(LP4)max z=x1
10、+5x2 s.t.x1+x2 2 5x1+6x2 30 2 x1 4 x2 4 x1 0,x2 0,（LP0）z0=218/11x 1=18/11,x 2=40/11,（LP1）z1=16x 1=1,x 2=3,（LP2）z2=18.66x 1=2,x 2=10/3,x 11,x 1 2,（LP3）z3=17.4x 1=2.4,x 2=3,LP4 无可行解,(LP5)z 5=17x 1=2,x 2=3,(LP6)z 6=15.5x 1=3,x 2=5/2,分枝的方法,定界的方法,当前得到的最好整数解的目标函数值分枝后计算放松的线性规划的最优解,整数解,非整数解,目标值大于原有最好的目标值：替代
11、原有目标值目标值小于原有最好的目标值：删除该分枝,目标值大于原有最好的目标值：继续分支目标值小于等于原有最好的目标值：删除该分枝,2.割平面解法,（ILP）,（LP0）,割平面法的基本思想：,如果放松问题(LP0)无解，则(ILP)无解；如果(LP0)的最优解为整数向量，则也是(ILP)的最优解；如果(LP0)的解含有非整数分量，则对(LP0)增加割平面条件：即对(LP0)增加一个线性约束，将(LP0)的可行区域割掉一块，使得非整数解恰好在割掉的一块中，但又没有割掉原问题(ILP)的可行解，得到问题(LP1)，重复上述的过程。,割平面法的算法流程：,解LP0,无可行解,问题无界,ILP无解或无
12、界,解x0为整数向量,x0为ILP的解,x0有非整分量,对LP0增加线性约束将LP0的可行区域割掉一块,使得x0在割掉的区域中,而原问题ILP的任意可行解都没有割去,得到LP1,例6：求解下列整数规划问题,1、去掉整数约束，得到松弛问题，化成标准形,初始单纯形表,最终单纯形表,最优解（3/4，7/4）不是整数向量，需要引入割平面以得到改进的松弛问题。如何引入割平面？,由最终的单纯形表得到变量间的关系：,将系数和常数项分解成整数和非负真分数之和，移项得,由于x1,x2是整数，由原问题可知，x3,x4也是整数，因此，上式左端必为整数。右端()内是正数，所以等式右端必为非正数，即,切割方程,引入松弛
13、变量x5，得到等式,将这个新的约束加到最优单纯形表中，得到,用对偶单纯形法迭代得,割平面方程等价于:,即,可见，割平面就是结合松弛问题的最优表和原问题的整数约束，而增加的线性约束。,割平面割掉了包含非整数解的一块可行区域，但没有割掉任何整数格点。,求割平面的步骤：把线性规划最优解中取值为非整数的基变量找出来。将该基变量在最优单纯形表中对应的约束的常数和变量系数分解成整数和非负真分数之和。提出变量为整数的条件构成切割方程。,第三节 指派问题及匈牙利解法,问题的提出及数学模型匈牙利解法两点说明指派问题的求解软件,1.问题的提出及数学模型,例7：设某工程有B1,B2,B3,B4 四项任务，需由四个工
14、人A1,A2,A3,A4去完成，由于任务性质和每个工人的技术水平不相同，他们完成各项任务所需的时间也不一样（见下表）。问应当如何指派，即哪个人去完成哪项任务，才能使完成四项任务的总时间最少？,设,该问题的解为,用矩阵形式表示为:,解矩阵,设有n 项任务，需有n 个人去完成，每个人只能完成一项任务，每项任务只能由一个人去完成，设第i 人完成第j 项任务需要的时间是aij,问如何指派才能使完成任务的总时间最少？,设,一般指派问题,指派问题是一种特殊的运输问题，特殊在哪里？高度退化！因而一般不使用表上作业法求解。,2.匈牙利解法,定义 1 效率矩阵,其中aij0表示第i 人完成第j项任务的效率（时间
15、、费用等）。,定义 2 任务的一种分配方法称为一个匹配。（指派问题的一个解），使目标函数取得最小值的匹配称为最优匹配（最优解）,特点：每行恰有一个1；每列恰有一个1。,匈牙利方法的基本思想,如果效率矩阵的所有元素aij0,而其中存在一组位于不同行不同列的0元素,则只要令对应于这些位置的xij=1，其余xij=0，就可以得到指派问题的最优解。,效率矩阵：,最优解,问题：如何产生这组独立0元素？,定义 3 位于效率矩阵的不同行不同列的0元素称为独立0元素。,定理 1：如果从效率矩阵A的每一行元素中分别减去（或加上）一个常数ui，从每一列元素中分别减去（或加上）一个常数vj，得到一个新的效率矩阵B，
16、其中bij=aij-ui-vj,则B对应的指派问题与A对应的指派问题同解。,定理 2 效率矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。,独立0元最多两个；至少需用两条直线覆盖所有0元素。,证明:将B中的数据代入目标函数,有:,匈牙利解法的基本步骤,第一步：初始变换获得0元素。从效率矩阵的每行减去该行的最小元素；然后从所得矩阵的每列减去该列的最小元素，令所得矩阵为B.第二步：在B中寻找位于不同行、不同列的0元素。（1）检查B的每行每列，从中找出未加标记的0元素最少的一排（即行列的统称），在该排用()标出一个0元，若该排有多个0元，则任意标出一个即可；（2）把刚得到()号标记的0元
17、所在的行、列中的其余0元划去，用表示；（3）凡是(0)，就成为加了标记的0元，返回（1）重复（1）、（2）、（3），直到所有0元都加上标记为止。若得到的加()号的0元素个数等于n，则结束；否则转第三步,第三步：找出能覆盖矩阵中所有0元素的最少直线集合。（1）对没有(0)的行打；（2）对已经打的行中所有元素所在的列打；（3）再对打的列中所有(0)元素所在的行打；（4）重复（2）（3）直到得不出新的打的行、列为至；（5）对没有打 的行和打的列划线，即为覆盖所有0元素的最少直线。第四步：修改矩阵B以增加独立0元素的个数。（1）在未被直线覆盖的所有元素中，找出最小元素；（2）所有打的行都减去此最小元素
18、，然后所有打的列都加上此最小元素，令这个新矩阵为B，返回第二步。,例8：用匈牙利解法解例7,效率矩阵,第一步：初始变换,得解矩阵,找独立0元素,总时间为:4+4+9+11=28,例3：用匈牙利解法解下列指派问题,效率矩阵,第一步：初始变换,第二步：寻找独立0元素,最小元素为 min10,5,7,2,6,3,6,5=2,-2,-2,+2,它有5个独立0元，得到最优解相应的解矩阵为,最优目标值：7+6+9+6+4=32,课堂练习：求解下列指派问题,效率矩阵,-1,-1,+1,第一组最优解,第二组最优解,两点说明,1.效率矩阵不是方阵的情况。（即人员与工作数不相等）处理方法：增加虚拟人或工作，使两者
19、相等。虚拟人或工作对应的效率矩阵中元素为0。2.最大化指派问题的处理。如果给出的效率矩阵中的数字表示每个人完成各项任务的收益，则问题变成了如何指派任务才能使总收益最大？处理方法：用效率矩阵中的最大元减去矩阵中的各个元素得到一个新的矩阵，对这个新的矩阵用匈牙利方法求解。,例9：有四项工作分配给六个人去完成，每个人分别完成各项工作的时间如下表所示，仍然规定每个人只能完成一项工作，每项工作只交给一个人去完成，问挑选哪四个人去完成工作，花费的总时间最少？,例10 指派甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人完成各项任务的时间如下表，由于任务数多于人数，故考虑：,（1）任务E必须完成
20、，其他4项中任选3项完成；（2）其中有一人完成两项，其他每人完成一项；（3）任务A由甲或丙完成，任务C由丙或丁完成，任务E 由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项；试分别确定最优指派方案，使完成任务的总时间最少。,（1）任务E必须完成，其他4项中任选3项完成；,（2）其中有一人完成两项，其他每人完成一项；,由于虚拟人完成的工作需要转给甲乙丙丁，因此，虚拟人完成各项工作的时间等于四个人完成该工作的最短时间。,（3）任务A由甲或丙完成，任务C由丙或丁完成，任务E 由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项；,虚拟人完成某项工作的时间等于丙、丁完成
21、该工作的时间中较小者。,例11：假设有3项工作A,B,C需要指派给3个工人甲、乙、丙去做，由于每个人的工作能力和技术水平不同，因而完成各项工作的收益也不同，3个人的工作收益如下表所示，问如何安排工作才能使总收益达到最大？,效率矩阵,10-各元素,解矩阵,指派甲完成工作A，乙完成工作C，丙完成工作B，总收益为10+7+9=26。,指派问题的求解软件（WINQSB）,进入WINQSB选择Network Modeling模块选取Assignment Problem；输入问题名称、人员数、工作数，选择目标函数类型，数据输入方式，按OK进入数据输入窗口；输入效率矩阵；按Solve Problem求解。,P144 必做：4（1）选做：7、8,作业：,
