运筹学第五章整数规划.ppt

《运筹学第五章整数规划.ppt》由会员分享，可在线阅读，更多相关《运筹学第五章整数规划.ppt（77页珍藏版）》请在三一文库上搜索。

1、第五章 整数规划,5.1 整数规划问题的提出,例5-1 某厂拟用集装箱托运甲、乙两种货物。每箱的体积、重量、可获利润以及托运所受限制如下表所示：,问两种货物各托运多少箱，可使获得的利润最大？,解：,设x1 , x2 分别为甲、乙两种货物的托运箱数，则模型为：,Max z = 20x1 +10x2,St. 5x1 +4x2 24,2x1 +5 x2 13,x1 ，x2 0,x1 ，x2 整数,暂不考虑整数约束，求得最优解为,x1 = 4.8 ，x2 = 0， Max z = 96,（1）若,x1 = 4.8 ，x2 = 0,x1 = 5 ，x2 = 0,不是可行解；,（2）若,x1 = 4.8

2、，x2 = 0,x1 = 4，x2 = 0,是可行解，但不是最优解,因为,x1 = 4，x2 = 0时，z = 80,而可行解,x1 = 4，x2 = 1时，z = 90,5.2 整数规划的类型,整数规划按变量取值的不同，可以分为以下几类：,1. 纯整数规划：所有的变量都取整数值；,2. 混合整数规划：部分变量取整数值；,3. 01规划：所有变量只取0，1两个值；,4. 01混合规划：部分变量只取0，1两个值。,整数规划（Integer Programming）问题的一般形式,整数规划与其松弛问题,当放弃整数约束时得到的线性规划称为整数规划的松弛问题。,整数规划的可行域是松弛问题的可行域，反之

3、不成立。,5.3.1 混合整数规划的求解-分枝定界方法,分枝：当 不符合整数要求时，构造两个约束条件：,加入松弛问题分别形成两个子问题（分枝）,定界：当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限,5.3 整数规划的解法,分枝定界法基本思想：,首先不考虑变量的整数约束，求解相应的线性规划问题：,O,A,C,D,xr,Ir,Ir+1,.,.,.,.,分枝,每一次分枝得到的子问题的最优目标函数值都要比上一层问题的最优目标函数值小，或者相等。,z0,z11,z12,z21,z22,z23,z24,整数解,下界,若z21 z11，z22 z11，则无须继续分枝,定界,利用定界，可以终

4、止许多不必要的分枝过程。,如果在分枝过程中得到新的整数解且该整数解的目标函数值大于已记录的下界，则应将较大的整数解的目标函数值代替原来的下界。,当所有最低一层子问题出现以下三种情况时，分枝定界法终止：,1. 子问题无可行解；,2. 子问题已获得整数解；,3. 子问题的目标函数值未达到下界。,例,S,解S得：,S2,对S分枝：,构造约束：,和,形成分枝问题S1和S2，得解B和C,S1,1,3,2,X,2,5,4,S2,对S1分枝：,构造约束：,和,形成分枝问题S11和S12，得解D,S12,S11无可行解,1,3,2,X,2,5,4,S2,对S12分枝：,构造约束：,和,形成分枝问题S121和S

5、122，得解E和F,S121,S122,首先求解整数规划（IP）对应的松弛问题（LP），如果（LP）的最优解不是整数解，则逐次增加一个新约束（即割平面），它能割去松弛问题可行域中不含整数解的区域.逐次切割，直到得到一个整数最优极点（即整数解）为止。,5.3.2 纯整数规划的求解-Gomory割平面方法,基本思想：,（1）首先放弃变量的整数要求，求得线性规划的最优解；,（2）如果最优解是一个非整数解，则构造一个新的约束，对线性规划问题的可行域进行切割，切除已得到的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题；,（3）如果最优解仍不是整数解，再以增加附加约束的方法将其切除，但仍保持最

6、初可行域中所有的整数解，直至求得一个整数最优解为止。,整数规划的求解-Gomory割平面方法,松弛问题的最优解,Gomory定理,在松弛问题的最优单纯形表中，假如有一常数项 不是整数，且对应的方程为：,分解 和 成最大整数与正分数之和：,则,包含了整数规划的所有整数可行解，但不包括松弛问题的最优解。,例题求解,选择第一个方程：,分解为：,在原松弛问题中加入约束：,即,形成松弛问题2,整数点,松弛问题2的最优解,割平面,选择第四个方程（具有最大分数部分）：,分解为：,在松弛问题2中加入约束：,即,形成松弛问题3,得到最优解,割平面：,如果选择第二个方程：,分解为：,在松弛问题2中加入约束：,即,

7、形成松弛问题3,没有找到整数解，继续做下去,5.3.3 整数规划的图解法,x1,x2,6,4.8,2.6,6.5,*,*,*,*,*,*,*,5.3.4 整数规划的计算机求解,LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE = 96.0000000 NEW INTEGER SOLUTION OF 90.0000076 AT BRANCH 0 PIVOT 3 BOUND ON OPTIMUM: 90.00001 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 3 LAST INTEGER SOLUTION IS THE B

8、EST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 90.00000 VARIABLE VALUE REDUCED COST X1 4.000000 -16.000000 X2 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 2.000000 NO. ITERATIONS= 3 BRANCHES= 0 DETERM.= 1.000E 0,Max 20x1 +10x2 st 5x1 +4x2 24

9、 2x1 +5x2 13 end gin x1 x2 (或gin 2),5.4 整数规划的应用,例5-2 投资场所的选择,某公司拟在城市的东、南、西、北四区建立门市部，拟议中有10个位置Ai （i = 1,2, , 10）可供选择，并规定： 在东区，由A1 、A2 、A3 三个点中至多选两个； 在西区，由A4 、A5 两个点中至少选一个； 在南区，由A6 、A7 两个点中至少选一个； 在北区，由A8 、A9 、A10 三个点中至少选两个。 Ai 各点的设备投资及每年可获利润如下表所示：,但投资总额不能超过720万元。问应选择哪几个点可使年利润为最大？,解：,设,(i = 1,2, , 10),

10、Z = 36 x1,+ 40 x2,+ 50 x3,Max,100x1,+ 120x2,+ 150x3,720,x4 + x5 1,x1 + x2 + x3 2,x6 + x7 1,xi = 0或1,+ 22 x4,+ 20 x5,+ 30 x6,+ 25 x7,+ 48 x8,+ 58 x9,+ 61 x10,+ 80x4,+ 70x5,+ 90x6,+ 80x7,+ 140x8,+ 160x9,+ 180x10,x8 + x9 + x10 2,在东区，由A1 、A2 、A3 三个点中至多选两个,在西区，由A4 、A5 两个点中至少选一个,在南区，由A6 、A7 两个点中至少选一个,在北区，

11、由A8 、A9 、A10 三个点中至少选两个,例5-3 资金分配问题,某集团公司计划新建五个工厂A1 、A2 、A3 、A4 、A5 ，所需投资分别为100、150、125、200、250万元。现仅有资金总额750万元，又据估计，工厂建成后每年可获利润分别为20、25、20、40、45万元。试决定应建哪些工厂，使投资总额不超过现有资金总额，并使工厂建成后每年获得的总利润最大？,解：,对于工厂Ai （i = 1,2, , 5）来说，只有建或不建两种情况，因此，可设,xi =,1 当建工厂Ai 时，（i = 1,2, , 5）,0 相反,则模型为,Max z = 20x1 + 25x2 + 20x

12、3 +40 x4 +45 x5,st. 100x1 + 150x2 + 125x3 +200 x4 +250 x5 750,xi = 0或1 （i = 1,2, , 5）,例5-4 固定成本问题,高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示：,资源,金属板（吨）,劳动力（人月）,机器设备（台月）,小号容器,中号容器,大号容器,2 4 8,2 3 4,1 2 3,不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器有100台月。此外，不管每种容器制

13、造的数量是多少，都要支付一笔固定费用：小号是100万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。,解：分析问题,设x1 、x2 、x3 分别为小号容器、中号容器、大号容器的生产数量；,各种容器的固定费用只有在生产该种容器时才投入，故设：,yi =,1 当生产第 i 种容器，即 xi 0,0 当不生产第 i 种容器，即 xi =0,目标函数：为扣除了固定费用后的利润,约束条件：金属板、劳动力、机器设备的限制,为避免出现某种容器不投入固定费用就生产这样一种不合理情况，必须加上如下约束：,x1 y1 M,x2 y2 M,x3 y3 M,M是充分大的数，例如，此

14、问题中，M可取200,x1 200y1,x2 200y2,x3 200y3,线性规划模型为：,目标函数,Max z = 4x1 + 5x2 + 6x3 100y1 150y2 200y3,金属板限制,2x1 + 4x2 + 8x3 500,劳动力限制,2x1 + 3x2 + 4x3 300,机器设备限制,x1 + 2x2 + 3x3 100,x1 y1 M,x2 y2 M,x3 y3 M,x1 ，x2 ，x3 0,y1 ，y2 ，y3 为01变量,求解得：,x1 =100，x2 =0，x3 =0,y1 =1，y2 =0，y3 =0,例5-5 分布系统设计,某企业在A1 地已有一个工厂，其产品的

15、生产能力为30千箱。为了扩大生产，打算在A2 、 A3 、 A4 、 A5 地中再选择几个地方建厂。已知在A2 、 A3 、 A4 、 A5 地建厂的固定成本分别为175、300、375、500千元，各产地的产量及各销地的销量及从产地到销地的单位运价如下表所示。,（1）问应该在哪几个地方建厂，在满足销量的前提下，使得总固定成本和总运输费用之和最小；（2）如果由于政策要求必须在A2 、 A3 建一个厂，应在哪几个地方建厂？,解：,设 xij 为从Ai 到Bj 的运输量；,yi =,1 当Ai 厂址被选中；,0 当Ai 厂址没被选中,Min z = 175y2 +300y3 +375y4 + 50

16、0y5 + 8x11 + 4x12 + 3x13 + 5x21 + 2x22 + 3x23 + 4x31 + 3x32 + 4x33 + 9x41 + 7x42 + 5x43 + 10x51 + 4x52 + 2x53,A1 厂的产量限制,x11 + x12 + x13 30,对于A2 、 A3 、 A4 、 A5 ，只有厂址被选中，才会有生产量,x21 + x22 + x23 10 y2,x31 + x32 + x33 20 y3,x41 + x42 + x43 30 y4,x51 + x52 + x53 40 y5,各销地的销量限制,x11 + x21 + x31 +x41 + x51 =

17、 30,x12 + x22 + x32 +x42 + x52 = 20,x13 + x23 + x33 +x43 + x53 = 20,xij 0，为整数， yi 为01变量,（1）,求解得：,y5 =1， x52 = 20， x53 = 20， x11 = 30，其余为0，最优目标函数值=860,（2）,在上述模型上加上约束条件：,y2 + y3 =1,求解得：,y2 =1， y4 =1， x22 = 10， x41 = 30， x12 = 10， x13 = 20，其余为0，最优目标函数值=940,0-1规划的求解隐枚举方法,最优解（x1,x2,x3)=(1,0,1); z=8,隐枚举方法

18、求解过程,n个员工分配做n项工作，已知第i个员工做第j项工作的成本为cij，i=1,n; j=1,n。求最佳分配方案。,4.5 指派问题与匈亚利法,指派问题的数学模型,s.t.,指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小,对于每个指派问题，需要有效率矩阵（cij ）,（cij ）=,c11 c12 c1n,c21 c22 c2n,cn1 cn2 cnn,引入变量,xij =,1 当指派第i 个人完成第j项任务,0 当不指派第i 个人完成第j项任务,则每人的效率及目标为,c11 x11,+c12 x12,+.,+c1n x1n,c21 x21,+c22 x22,+.,+c2n x

19、2n,.,cn1 xn1,+cn2 xn2,+.,+cnn xnn,.,Z=,Min,n项任务，恰好有n个人承担去完成。由于每人的专长不同，各人完成不同的任务效率也不同。于是就产生了应指派哪个人去完成哪项任务，使完成n项任务的总效率最高。,第1项任务只能由1人完成,x11 + x21 + . xn1 = 1,第2项任务只能由1人完成,x12 + x22 + . xn2 = 1,.,第j项任务只能由1人完成,x1j + x2j + . xnj = 1,.,第n项任务只能由1人完成,x1n + x2n + . xnn = 1,.,.,.,.,(j =1, 2, , n),第1个人只能完成1项任务,

20、x11 + x12 + . x1n = 1,第2个人只能完成1项任务,x21 + x22 + . x2n = 1,.,.,第i个人只能完成1项任务,xi1 + xi2 + . xin = 1,.,.,第n个人只能完成1项任务,xn1 + xn2 + . xnn = 1,.,.,(i =1, 2, , n),故模型为,(j =1, 2, , n),第j项任务只能由1人完成,(i =1, 2, , n),第i个人只能完成1项任务,xij = 0或1,满足上述约束条件的可行解xij 可写成矩阵形式，称为解矩阵,（xij ）=,0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1,指派问题的

21、求解方法,（1）计算机求解,（2）匈牙利法,（3）隐枚举法,指派问题的性质,定理：对于指派问题，成本矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解。,定理：,系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。,匈牙利法的计算步骤为：,第一步：使系数矩阵出现0元素。,第二步：进行试指派，以寻求最优解。,第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最 多的独立元素数。,第四步：变换矩阵增加0元素，再返回第二步。,第四步说明：调整效益矩阵，使之增加一些零元素： (1) 在没有被直线覆盖的元素中，找出最小元素； (2) 在没有被直线覆盖的元素

22、中，减去最小元素； (3) 在直线交叉处的元素中，加上最小元素； (4) 被一条直线覆盖的元素不变.,例4-6 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需的时间如下表所示：,问应指派何人去完成何工作，使所需总时间最少？,解：用匈牙利法。,第一步：使系数矩阵出现0元素。,（cij ）=,2 15 13 4,10 4 14 15,9 14 16 13,7 8 11 9,2,4,9,7,0 13 11 2,6 0 10 11,0 5 7 4,0 1 4 2,4,2,0 13 7 0,6 0 6 9,0 5

23、 3 2,0 1 0 0,=（bij ）,第二步：进行试指派。,可见，m = n = 4，所以得最优解为,（xij ）=,0 0 0 1,0 1 0 0,1 0 0 0,0 0 1 0,即指定甲译俄文，乙译日文，丙译英文，丁译德文，所需总时间最少。,所需时间为,例4-7 求下表所示效率矩阵的指派问题的最优解。,解：第一轮,第一步：使系数矩阵出现0元素。,12 7 9 7 9,8 9 6 6 6,7 17 12 14 9,15 14 6 6 10,4 10 7 10 9,7,6,7,6,4,5 0 2 0 2,2 3 0 0 0,0 10 5 7 2,9 8 0 0 4,0 6 3 6 5,第二

24、步：进行试指派。,由于m = 4，n = 5，解题没有完成。,第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素（不同行不同列的零元素）数。,由于 l = 4 n = 5，转第四步。,第四步：变换矩阵增加0元素。,最小元素为2,7,0,2,0,2,4,3,0,0,0,0,8,3,5,0,11,8,0,0,4,0,4,1,4,3,第一轮结束。,第二轮：按第二步，得,由于m = n = 5，故得最优解，解矩阵为,（xij ）=,0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0,最优的任务指派为：,甲B；乙C；丙E；丁D；戊

25、A。,Min z = 7+6+9+6+4 = 32,第四步：调整效益矩阵，使之增加一些零元素： (1) 在没有被直线覆盖的元素中，找出最小元素； (2) 在没有被直线覆盖的元素中，减去最小元素； (3) 在直线交叉处的元素中，加上最小元素； (4) 被一条直线覆盖的元素不变.,此问题还有一个最优解,由第二步得：,由于m = n = 5，故得最优解，解矩阵为,（xij ）=,0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0,最优的任务指派为：,甲B；乙D；丙E；丁C；戊A。,Min z = 7+6+9+6+4 = 32,一般指派问题,最大化指派问题 人数和工作数不等的指派问题 一个人可做几项工作的指派问题 某项工作一定不能由某人做的指派问题,最大化指派问题,最大化指派问题,人数和工作数不等的指派问题,一个人可做几项工作的指派问题,A1可同时做三项工作,某项工作一定不能由某人做的指派问题,A1不能做B4; A3不能做B3,例题：0-1规划的应用-项目投资预算,模型,变量假设:,模型:,0-1规划的应用-工厂-销售点配置问题,工厂-销售点配置问题-问题描述,问题: 为使经营成本最低,应开设那些工厂及销售点?,工厂-销售点配置问题-模型参数,工厂-销售点配置问题-模型,指派问题实例,cij,例题求解,