理学整数规划PPT学习教案

1、会计学1理学整数规划理学整数规划2第五章第五章 整数规划整数规划第1页/共64页引例：某厂利用集装箱托运甲、乙两种货物，引例：某厂利用集装箱托运甲、乙两种货物，每箱体积重量每箱体积重量 、可获利润及托运限制如下：、可获利润及托运限制如下：体积体积重量重量利润利润甲甲5220乙乙4510托运限制托运限制2413两种货物各托运多少箱使利润最大？两种货物各托运多少箱使利润最大？第2页/共64页Max Z= 20 x1 +10 x25x1 +4x2242x1 +5x213x1 , x20 x2x1244521 xx135221 xx0Ax1 , x2 为整数为整数ZA=96A(4.8, 0 )第3页/

2、共64页Max Z= 20 x1 +10 x25x1 +4x2242x1 +5x213x1 , x20 x2x1(4.8, 0 ) AZA=96x1 , x2 为整数为整数(4,0) Z=80(5,0)(4,1) max Z=90第4页/共64页第一节第一节 整数规划的数学模型整数规划的数学模型一、整数规划问题一、整数规划问题 整数规划问题（整数规划问题（IP）:是指要求部分是指要求部分或全部决策变量的取值为整数的规划问或全部决策变量的取值为整数的规划问题。题。 松弛问题：松弛问题：不考虑整数条件，由余不考虑整数条件，由余下的目标函数和约束条件构成的规划问下的目标函数和约束条件构成的规划问题。

3、题。 重点研究：重点研究：整数线性规划问题整数线性规划问题第5页/共64页二、整数线性规划问题的模型二、整数线性规划问题的模型j=1,2,njnjjxcZ1max(min)0),(1jinjjijxbxai=1,2,mxj 中取部分或全部为整数中取部分或全部为整数第6页/共64页三、整数规划问题的类型：三、整数规划问题的类型：1. 纯整数规划问题纯整数规划问题第7页/共64页minZ= x1 + x2 +x3+x4+x5+x6 +x7+x8x1 8x1 + x2 8x1 + x2+ x3 7x1+x2+ x3 + x4 1x2+ x3 + x4 + x5 2x3+ x4 + x5 +x6 1x

4、4 + x5 +x6 + x7 5x5+ x6 + x7 +x8 10 x6 + x7 +x8 10 x7 +x8 6x8 6 xi 0 (i =1,8)且为整数且为整数第8页/共64页2. 0-1型整数线性规划型整数线性规划例例2：现有资金总额为：现有资金总额为B。可供选择的投资项可供选择的投资项目有目有n个，项目个，项目j所需投资额和预期收益分别所需投资额和预期收益分别为为aj和和cj,此外，因种种原因，有此外，因种种原因，有3个附加条件：个附加条件：若选择项目若选择项目1必须同时选择项目必须同时选择项目2，反之，不，反之，不一定；项目一定；项目3和项目和项目4中至少选择一个；第三，中至少

5、选择一个；第三，项目项目5、6、7中恰好选择两个。应当怎样选择中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？投资项目，才能使总预期收益最大？第9页/共64页1 对项目对项目 j 投资投资0 对项目对项目 j 不投资不投资 xj=Max Z=cjxjajxjBx2 x1x3+ x4 1x5+ x6 +x7=2xj=0或或1（j=1,2,n）第10页/共64页3. 混合整数规划混合整数规划 例例3 工厂工厂A1和和A2生产某种物资，由于生产某种物资，由于该种物资供不应求，还需要建一家工厂。由该种物资供不应求，还需要建一家工厂。由两个待选方案两个待选方案A3和和A4。物资需求地为物资需

6、求地为Bj(j=1,2,3,4)。工厂工厂A3和和A4的生产费用估计的生产费用估计为为1200万元或万元或1500万元。选择哪一个方案才万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产能使总费用（包括物资运费和新工厂的生产费用）最小。费用）最小。第11页/共64页B1B2B3B4生产能力生产能力A12934400A28357600A37612200A44525200需求量需求量350400300150第12页/共64页y 0-1变量变量y=1 若建工厂若建工厂A30 若建工厂若建工厂A4设设xij为由为由Ai送往送往Bj 的物资数量。的物资数量。则总费用为则总费用为:min Z=c

7、ijxij +1200y+1500(1-y)第13页/共64页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=200yx41+ x42+ x43+ x44=200(1-y)xij0, y=0或或1第14页/共64页第二节第二节 解纯整数规划的割平面解纯整数规划的割平面法法一、基本思想一、基本思想 找到纯整数线性规划的松弛问题，不考找

8、到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。解在内的非整数解。第15页/共64页二、割平面求解举例二、割平面求解举例Max Z=x1+x2-x1+x213x1+x2 4x1 , x20且为整数且为整数松弛问题松弛问题Max Z=x1+x2-x1+x213x1+x2 4x1 , x20-x1+x2+x3 =13x1+x2 +x4=4x1 , x20第16页/共64页

9、不考虑整数解约束，解松弛问题的最优单纯形表为：不考虑整数解约束，解松弛问题的最优单纯形表为：CBXBb1100 x1x2x3x40 x31-11100 x443101-1-1001x13/410-1/41/41x27/4013/41/4Z=5/2001/21/2x2+3/4x3+1/4x4=7/4x2-1=3/4-3/4x3-1/4x4第17页/共64页将将 -3x3-x4+x5= -3（切割方程切割方程） 代入最优表代入最优表CBXBb11000 x1x2x3x4x51x13/410-1/41/401x27/4013/41/400 x5-300-3-11Z=5/200-1/2-1/201x1

10、11001/31/121x2101001/40 x310011-1/3Z=2000-1/3-1/3x2-1=3/4-3/4x3-1/4x43/4-3/4x3-1/4x403-3x3-x403-3x3-x4+x5=0第18页/共64页MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x1,x20 且为整数且为整数MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x1,x20第19页/共64页CBXBb11000 x1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/7Z=5/200-5/7

11、0-3/7x1+1/7x3 + 2/7x5=13/7x1+1/7x3 + 2/7x5=1+6/7x1- 1 = 6/7 -（1/7x3 + 2/7x5）6/7 -（1/7x3 + 2/7x5）0-1/7x3 - 2/7x5- 6/7 第20页/共64页-1/7x3 - 2/7x5- 6/7-1/7x3 - 2/7x5+x6=- 6/7CBXBb110000 x1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700 x431/700-3/7122/700 x6-6/700-1/70-2/71Z=5/200-5/70-3/70第21页/共64页CBXBb11

12、0000 x1x2x3x4x5x63x11100001-1x24/5010-1/40-5/40 x35/2001-1/20-11/20 x57/40001/41-3/4Z=5/200000-17/4-1/4x4 + 1/4x6-3/4余下略余下略第22页/共64页第三节第三节 分支定界法分支定界法一、基本思想一、基本思想 定界：为求解纯整数规划和混合整数规定界：为求解纯整数规划和混合整数规划问题划问题(A)，先求出其松弛问题（先求出其松弛问题（B）的最优的最优解，作为问题解，作为问题A的最优目标函数值的上界，的最优目标函数值的上界，同时选择任意整数可行解作为同时选择任意整数可行解作为A的最优目

13、标的最优目标函数值的下界。函数值的下界。 分支：将应为整数解，但尚是非整数解分支：将应为整数解，但尚是非整数解之一的决策变量取值分区，并入松弛问题中，之一的决策变量取值分区，并入松弛问题中，形成两个分支松弛问题，分别求解。依结果形成两个分支松弛问题，分别求解。依结果来调整上下界。来调整上下界。 第23页/共64页二、举例二、举例例例1：A问题为问题为 B问题为问题为MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 x1,x2 都为整数都为整数MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 第24页/共64页 问题

14、问题B x1=4.81 ,x2=1.82 Z=356Z=356 Z=0 问题问题B1 x1=4,x2=2.1 Z=349 问题问题B 2 x1=5 ,x2=1.57 Z=341x14x15Z=349 Z=0 x22x23问题问题B3 x1=4, x2=2 Z=340问题问题B4 x1=1.42 x2=3 Z=327Z=349 Z=340 x21x22问题问题B5 x1=5.44 x2=1 Z=308Z*=340问题问题B6 无可无可行解行解第25页/共64页第四节第四节 0-1型整数规划型整数规划一、一、0-1变量的概念变量的概念 0-1变量变量：一种逻辑变量，常用来表：一种逻辑变量，常用来表

15、示系统处于某个特定状态，或者决策时示系统处于某个特定状态，或者决策时是否取某个特定方案。是否取某个特定方案。 x=1 当决策取方案当决策取方案P时时 0 当决策不取方案当决策不取方案P时时第26页/共64页二、二、0-1变量的实际应用变量的实际应用1. 制定相互排斥的计划制定相互排斥的计划例例1：投资场所的选定：投资场所的选定 某公司拟在市东、西、南三区建立门市部，拟某公司拟在市东、西、南三区建立门市部，拟议中有议中有7个位置个位置Ai 可供选择，规定：可供选择，规定： 在东区，由在东区，由A1， A2 ，A3三个点中至多选两个；三个点中至多选两个； 在西区，由在西区，由A4， A5 两点中至

16、少选择两点中至少选择1个；个； 在南区，由在南区，由 A6， A7 两点中至少选择两点中至少选择1个。个。若选择若选择Ai 点，估计设备投资为点，估计设备投资为bi 元，获利元，获利ci ,但投资但投资不能超过不能超过B元，如何投资获利最大？元，如何投资获利最大？第27页/共64页x=1 当当Ai 点被选用时点被选用时 0 当当Ai 点未被选用时点未被选用时解：解：Max Z=cixibixiBx1+ x2 +x32 x4+ x5 1 x6+ x7 1 xj=0或或1（i=1,2,n）第28页/共64页2. 相互排斥的约束条件问题相互排斥的约束条件问题例：集装箱运货（用车运或用船运）例：集装箱

17、运货（用车运或用船运）车运体积车运体积船运体积船运体积重量重量利润利润甲甲57220乙乙43510托运托运限制限制244513两种货物各托运多少箱可以使利润最大？两种货物各托运多少箱可以使利润最大？第29页/共64页y=1 船运船运 0 车运车运解：解：5x1+4x224+yM7x1+3x245+(1-y)M第30页/共64页Max Z=20 x1+10 x25x1+4x224+yM7x1+3x245 +(1-y)M2x1+5x213x1, x20 ，y=0或或1x1, x2为整数为整数y=1 船运船运 0 车运车运解：解：x1 ，x2 分别为甲分别为甲乙两种货物的托乙两种货物的托运数量运数量

18、第31页/共64页3. 固定费用问题固定费用问题 例：例：有三种资源被用于生产三种产品，有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单耗资源量、产品单件可变费用售价、资源单耗量及组织三种产品生产的固定费用见下表。量及组织三种产品生产的固定费用见下表。要求制定一个生产计划使总收益为最大。要求制定一个生产计划使总收益为最大。第32页/共64页 产品产品资源资源资源量资源量A248500B234300C123100单件可变费用单件可变费用456固定费用固定费用100150200单价单价81012第33页/共64页设设xj 为生产第为生产第 j 种产品的产量。种产品的产量。y为为0

19、-1变量变量Max Z=4x1+5x2+6x3-100y1-150y2-200y32x1+4x2+8x35002x1+3x2+4x3300 x1+2x2+3x3100 x1 M1y1x2 M2y2x3 M3y3xj 0且为整数，且为整数，j=1,2,3yj=0或或1，j=1,2,3第34页/共64页三、三、0-1型整数规划的解法型整数规划的解法 隐枚举法隐枚举法 隐枚举法隐枚举法：不同于穷举法，只检查变：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优量取值组合的一部分就能找到问题的最优解。解题关键是寻找可行解，产生过滤条解。解题关键是寻找可行解，产生过滤条件。件。 过滤条件：过滤条

20、件：目标函数值优于计算过的目标函数值优于计算过的可行解目标函数值。可行解目标函数值。第35页/共64页maxZ=3X1 -2X2+5X3X1+ 2X2 - X3 2 X1 + 4X2 +X3 4 X1 + X2 3 4X2 +X3 6 X1 , X2 , X3 = 0 或或 1 第36页/共64页(x1 , x2 , x3)Z值值约束条件约束条件 过滤条件过滤条件（0，0，0）0 Z0（0，0，1）5 Z5（0，1，0）-2（0，1，1）3（1，0，0）3（1，0，1）8 Z8（1，1，0）1（1，1，1）6第37页/共64页第五节第五节 指派问题指派问题 一、典型的指派问题一、典型的指派问题

21、 某单位需完成某单位需完成n项任务，恰有项任务，恰有n个人个人可以承担，由于每个人的专长不同，各人可以承担，由于每个人的专长不同，各人完成任务的效率不同，各人完成一项任务完成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分的同时，不能同时去做其它任务，如何分配任务会使所需的时间最小或成本最低。配任务会使所需的时间最小或成本最低。第38页/共64页 例：有一份中文说明书，需译成英、例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁现有甲、乙、丙、丁4人，他们将中文人，他们将中文说明书翻译成不同语种的说明书

22、所需的时间说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所如下，问应指派何人去完成何种工作，使所需总时间最少？需总时间最少？第39页/共64页 任务任务人员人员EJGR甲甲215134乙乙1041415丙丙9141613丁丁78119第40页/共64页指派问题的标准形式指派问题的标准形式 n个人，个人，n件事，第件事，第i个人做第个人做第j件事的件事的费用为费用为cij,确定人和事之间一一对应的指派确定人和事之间一一对应的指派方案，使完成方案，使完成n件事的总费用最小。件事的总费用最小。效率效率矩阵矩阵或或系数系数矩阵矩阵C=(cij)nn=c11 c12 c1n

23、c21 c22 c2n cn1 cn1 cnn 第41页/共64页C=(cij )nn=2151341041415914161378119第42页/共64页二、标准指派问题的数学模型二、标准指派问题的数学模型xij=1 指派第指派第 i 个人做第个人做第 j 件事件事0 不指派第不指派第 i 个人做第个人做第 j 件事件事ninjijijxcZ11minniijx11njijx11j=1,2,ni=1,2,nxij=1或或0第43页/共64页 解矩阵：解矩阵：满足约束条件的可行解也满足约束条件的可行解也可以写成表格或矩阵的形式，称为解矩可以写成表格或矩阵的形式，称为解矩阵。阵。例：例：X=(x

24、ij )44=010 000011 0 0 00 0 1 0第44页/共64页三、匈牙利解法三、匈牙利解法（1）关键性质关键性质： 若从指派问题的系数矩阵若从指派问题的系数矩阵(cij)nn的某的某行或某列各元素中分别减一个常数行或某列各元素中分别减一个常数k, 得到得到的新矩阵与原矩阵有相同的最优解。的新矩阵与原矩阵有相同的最优解。C=(cij )nn=2151341041415914161378119第45页/共64页C=(cij )nn=2151341041415914161378119ninjijijxcZ11min00102350960607130241047501110062111

25、30第46页/共64页C=(cij )nn=01370606905320100匈牙利法的步骤匈牙利法的步骤1.变换系数矩阵变换系数矩阵00102350960607130每行减最小数，每行减最小数，没没0的列，减最小数的列，减最小数第47页/共64页C=(cij )nn=01370606905320100匈牙利法的步骤匈牙利法的步骤2.寻找独立寻找独立“0”元素元素若有若有n个，计算结个，计算结束束若少于若少于n个，转个，转3第48页/共64页C=(cij )nn= 137669 532 1匈牙利法的步骤匈牙利法的步骤2.寻找独立寻找独立“0”元素元素若有若有n个，计算结个，计算结束束若少于若少

26、于n个，转个，转3第49页/共64页C=(cij )nn=2151341041415914161378119Min Z=c31+c22+c43+c14=4+4+9+11=28第50页/共64页2.寻找独立寻找独立“0”元素元素C=(cij )nn=4 8 7 15 127 9 17 14 106 9 12 8 76 7 14 6 106 9 12 10 6行减最小数行减最小数匈牙利法的步骤匈牙利法的步骤第51页/共64页2.寻找独立寻找独立“0”元素元素C=(cij )nn=0 4 3 11 80 2 10 7 30 3 6 2 10 1 8 0 40 3 6 4 0匈牙利法的步骤匈牙利法的步

27、骤没有零的列减最小数第52页/共64页2.寻找独立寻找独立“0”元素元素若有若有n个，计算结个，计算结束束若少于若少于n个，转个，转3C=(cij )nn=0 3 0 11 80 1 7 7 30 2 3 2 10 0 5 0 40 2 3 4 0匈牙利法的步骤匈牙利法的步骤是否找到最优指派 610129610614767812961014179712157843534第53页/共64页3.寻找最少覆盖寻找最少覆盖“0”的直线的直线0 3 0 11 80 1 7 7 30 2 3 2 10 0 5 0 41 2 3 4 0（1）行或列中只）行或列中只有一个有一个“0”的元，的元，作标记，如果其

28、所作标记，如果其所在列或行有其它在列或行有其它“0”的，则划去的，则划去。（2）如此反复直）如此反复直到所有行的到所有行的“0”被被直线覆盖直线覆盖匈牙利法的步骤匈牙利法的步骤第54页/共64页（1）对所有不含）对所有不含0元素的行打元素的行打匈牙利法的步骤匈牙利法的步骤（2）对已打）对已打的行的行中所有含中所有含0元素的元素的列打列打（3）在对已打）在对已打的列中含的列中含0元素元素的行打的行打直到无法打直到无法打为止为止,3.寻找最少覆盖寻找最少覆盖“0”的直线的直线0 3 11 8 1 7 7 30 2 3 2 10 5 0 41 2 3 4 第55页/共64页匈牙利法的步骤匈牙利法的步骤（4）没打）没打的行画的行画直线，直线，对打对打的列画直线的列画直线,3.寻找最少覆盖寻找最少覆盖“0”的直线的直线0 3 11 8 1 7 7 30 2 3 2 10 5 0 41 2 3 4 第56页/共64页0 3 11 8 1 7 7 30 2 3 2 10 5 0 41 2 3 4 4.继续变换