《理学整数规划》PPT课件.ppt

运筹学 OPERATIONAL RESEARCH,广东培正学院 迟彦惠,“四舍五入”取x1=2,x2=7.,3,第五章 整数规划,引例：某厂利用集装箱托运甲、乙两种货物，每箱体积重量 、可获利润及托运限制如下：,两种货物各托运多少箱使利润最大？,Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20,x2,x1,0,A,x1 , x2 为整数,ZA=96,A(4.8, 0 ),Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20,x2,x1,(4.8, 0 ) A ZA=96,x1 , x2 为整数,(4,0) Z=80 (5,0) (4,1) max Z=90,第一节 整数规划的数学模型,一、整数规划问题 整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。 松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。 重点研究：整数线性规划问题,二、整数线性规划问题的模型,j=1,2,n,三、整数规划问题的类型： 纯整数规划问题,minZ= x1 + x2 +x3+x4+x5+x6 +x7+x8,x1 8 x1 + x2 8 x1 + x2+ x3 7 x1+x2+ x3 + x4 1 x2+ x3 + x4 + x5 2 x3+ x4 + x5 +x6 1 x4 + x5 +x6 + x7 5 x5+ x6 + x7 +x8 10 x6 + x7 +x8 10 x7 +x8 6 x8 6 xi 0 (i =1,8)且为整数,2. 0-1型整数线性规划 例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj,此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之，不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？,Max Z=cjxj ajxjB x2 x1 x3+ x4 1 x5+ x6 +x7=2 xj=0或1（j=1,2,n）,3. 混合整数规划 例3 工厂A1和A2生产某种物资，由于该种物资供不应求，还需要建一家工厂。由两个待选方案A3和A4。物资需求地为Bj(j=1,2,3,4)。工厂A3和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小。,y 0-1变量,y=,1 若建工厂A3,0 若建工厂A4,设xij为由Ai送往Bj 的物资数量。,则总费用为:,min Z=cijxij +1200y+1500(1-y),x11+ x21+ x31+ x41=350 x12+ x22+ x32+ x42=400 x13+ x23+ x33+ x43=300 x14+ x24+ x34+ x44=150 x11+ x12+ x13+ x14=400 x21+ x22+ x23+ x24=600 x31+ x32+ x33+ x34=200y x41+ x42+ x43+ x44=200(1-y) xij0, y=0或1,第二节 解纯整数规划的割平面法,一、基本思想 找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。,二、割平面求解举例,松弛问题,-x1+x2+x3 =1 3x1+x2 +x4=4 x1 , x20,不考虑整数解约束，解松弛问题的最优单纯形表为：,x2+3/4x3+1/4x4=7/4,x2-1=3/4-3/4x3-1/4x4,将 -3x3-x4+x5= -3（切割方程） 代入最优表,x2-1=3/4-3/4x3-1/4x4,3/4-3/4x3-1/4x40,3-3x3-x40,3-3x3-x4+x5=0,x1+1/7x3 + 2/7x5=13/7 x1+1/7x3 + 2/7x5=1+6/7 x1- 1 = 6/7 -（1/7x3 + 2/7x5） 6/7 -（1/7x3 + 2/7x5）0 -1/7x3 - 2/7x5- 6/7,-1/7x3 - 2/7x5- 6/7 -1/7x3 - 2/7x5+x6=- 6/7,-1/4x4 + 1/4x6-3/4 余下略,第三节 分支定界法,一、基本思想 定界：为求解纯整数规划和混合整数规划问题(A)，先求出其松弛问题（B）的最优解，作为问题A的最优目标函数值的上界，同时选择任意整数可行解作为A的最优目标函数值的下界。 分支：将应为整数解，但尚是非整数解之一的决策变量取值分区，并入松弛问题中，形成两个分支松弛问题，分别求解。依结果来调整上下界。,二、举例 例1：A问题为 B问题为,问题B x1=4.81 ,x2=1.82 Z=356,Z=356 Z=0,问题B1 x1=4,x2=2.1 Z=349,问题B 2 x1=5 ,x2=1.57 Z=341,Z=349 Z=0,问题B3 x1=4, x2=2 Z=340,问题B4 x1=1.42 x2=3 Z=327,Z=349 Z=340,问题B5 x1=5.44 x2=1 Z=308,Z*=340,问题B6 无可行解,第四节 0-1型整数规划,一、0-1变量的概念 0-1变量：一种逻辑变量，常用来表示系统处于某个特定状态，或者决策时是否取某个特定方案。,二、0-1变量的实际应用 1. 制定相互排斥的计划 例1：投资场所的选定 某公司拟在市东、西、南三区建立门市部，拟议中有7个位置Ai 可供选择，规定： 在东区，由A1， A2 ，A3三个点中至多选两个； 在西区，由A4， A5 两点中至少选择1个； 在南区，由 A6， A7 两点中至少选择1个。 若选择Ai 点，估计设备投资为bi 元，获利ci ,但投资不能超过B元，如何投资获利最大？,解：,2. 相互排斥的约束条件问题,例：集装箱运货（用车运或用船运）,两种货物各托运多少箱可以使利润最大？,解：,5x1+4x224+yM,7x1+3x245+(1-y)M,Max Z=20x1+10x2 5x1+4x224+yM 7x1+3x245 +(1-y)M 2x1+5x213 x1, x20 ，y=0或1 x1, x2为整数,解：,x1 ，x2 分别为甲乙两种货物的托运数量,3. 固定费用问题 例：有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划使总收益为最大。,设xj 为生产第 j 种产品的产量。y为0-1变量 Max Z=4x1+5x2+6x3-100y1-150y2-200y3,2x1+4x2+8x3500 2x1+3x2+4x3300 x1+2x2+3x3100 x1 M1y1 x2 M2y2 x3 M3y3 xj 0且为整数，j=1,2,3 yj=0或1，j=1,2,3,三、0-1型整数规划的解法 隐枚举法 隐枚举法：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优解。解题关键是寻找可行解，产生过滤条件。 过滤条件：目标函数值优于计算过的可行解目标函数值。,第五节 指派问题,一、典型的指派问题 某单位需完成n项任务，恰有n个人可以承担，由于每个人的专长不同，各人完成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分配任务会使所需的时间最小或成本最低。,例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？,指派问题的标准形式 n个人，n件事，第i个人做第j件事的费用为cij,确定人和事之间一一对应的指派方案，使完成n件事的总费用最小。,效率矩阵 或 系数矩阵,C=(cij )nn=,2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9,二、标准指派问题的数学模型,解矩阵：满足约束条件的可行解也可以写成表格或矩阵的形式，称为解矩阵。 例：,三、匈牙利解法 （1）关键性质： 若从指派问题的系数矩阵(cij)nn的某行或某列各元素中分别减一个常数k, 得到的新矩阵与原矩阵有相同的最优解。,C=(cij )nn=,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,匈牙利法的步骤 1.变换系数矩阵,每行减最小数，,没0的列，减最小数,C=(cij )nn=,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,匈牙利法的步骤 2.寻找独立“0”元素,C=(cij )nn=, 13 7 6 6 9 5 3 2 1 ,匈牙利法的步骤 2.寻找独立“0”元素,C=(cij )nn=,2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9,Min Z=c31+c22+c43+c14=4+4+9+11=28,2.寻找独立“0”元素,C=(cij )nn=,4 8 7 15 12 7 9 17 14 10 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6,行减最小数,匈牙利法的步骤,2.寻找独立“0”元素,C=(cij )nn=,0 4 3 11 8 0 2 10 7 3 0 3 6 2 1 0 1 8 0 4 0 3 6 4 0,匈牙利法的步骤,没有零的列减最小数,2.寻找独立“0”元素,C=(cij )nn=,0 3 0 11 8 0 1 7 7 3 0 2 3 2 1 0 0 5 0 4 0 2 3 4 0,匈牙利法的步骤,是否找到最优指派,35,34,3.寻找最少覆盖“0”的直线,0 3 0 11 8 0 1 7 7 3 0 2 3 2 1 0 0 5 0 4 1 2 3 4 0,（1）行或列中只有一个“0”的元，作标记，如果其所在列或行有其它“0”的，则划去。 （2）如此反复直到所有行的“0”被直线覆盖,匈牙利法的步骤,（1）对所有不含0元素的行打,匈牙利法的步骤,（2）对已打的行中所有含0元素的列打,（3）在对已打的列中含0元素的行打,直到无法打为止,3.寻找最少覆盖“0”的直线,0 3 11 8 1 7 7 3 0 2 3 2 1 0 5 0 4 1 2 3 4 ,匈牙利法的步骤,（4）没打的行画直线，,对打的列画直线,3.寻找最少覆盖“0”的直线,0 3 11 8 1 7 7 3 0 2 3 2 1 0 5 0 4 1 2 3 4 ,0 3 11 8 1 7 7 3 0 2 3 2 1 0 5 0 4 1 2 3 4 ,4.继续变换系数矩阵,（1）未被覆盖的元素中减去最小元素，出现新的0元素,匈牙利法的步骤,（2）打列中各元素都加上最小元素。,其余元素不变,4.继续变换系数矩阵,1 3 11 8 0 6 6 2 0 1 2 1 0 1 5 0 4 1 2 3 4 ,（1）未被覆盖的元素中减去最小元素，出现新的0元素,匈牙利法的步骤,（2）打列中各元素都加上最小元素。,其余元素不变,4.继续变换系数矩阵,1 3 11 8 0 6 6 2 0 1 2 1 0 1 5 0 4 2 2 3 4 ,（1）未被覆盖的元素中减去最小元素，出现新的0元素 （2）打列中各元素都加上最小元素。,其余元素不变,匈牙利法的步骤,5.重新寻找独立0元素,1 3 0 11 8 0 0 6 6 2 0 1 2 1 0 1 0 5 0 4 2 2 3 4 0,匈牙利法的步骤,匈牙利法的步骤,1 3 11 8 6 6 2 1 2 1 1 5 4 2