第五讲-整数规划及指派问题.ppt

1、运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳华东理工大学East China University of Science And Technology整整 数数 规规 划划 与与 指派指派 问问 题题一、整数规划的应用一、整数规划的应用二、整数规划的求解方法概述二、整数规划的求解方法概述四、匈牙利解法四、匈牙利解法三、指派问题三、指派问题运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-52一、整数规划的案例一、整数规划的案例案例案例1：集装箱托运问题：集装箱托运问题 公司拟用集装箱托运甲、乙两种货物，这两公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可

2、获利润以及托运所种货物每件的体积、重量，可获利润以及托运所受限制如下表所示受限制如下表所示:甲种货物至多托运甲种货物至多托运4 4件，问两种货物各托运多件，问两种货物各托运多少件，可使获得利润最大？少件，可使获得利润最大？货物货物每件体积每件体积/立方英尺立方英尺每件重量每件重量/百千克百千克每件利润每件利润/百元百元甲19542乙273403托运限制1365140运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-53 设设 分别为甲、乙两种货物托运的件数，其数学分别为甲、乙两种货物托运的件数，其数学规划模型如下：规划模型如下：121211219527313654401404,

3、xxxxxxx整 为数12,xx12 23Max zxx运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-54一、整数规划的案例（续）一、整数规划的案例（续）案例案例2：固定成本问题：固定成本问题 高压容器公司制造小、中、大三种尺寸的金属容高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表：一个容器所需的各种资源的数量如下表：不考虑固定费用，每种容器售出一只所得的利润不考虑固定费用，每种容器售出一只所得的利润分别为分别为4 4万元，万元，5 5万元，万元，6 6万元

4、，可使用的金属板有万元，可使用的金属板有500500，劳动力有，劳动力有300300人月，机器有人月，机器有100100台月。台月。资源资源小号容器小号容器中号容器中号容器大号容器大号容器金属板248劳动力234机器设备123运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-55 此外，不管每种容器制造的数量是多少，都要支付一此外，不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号为笔固定的费用：小号为100100万元，中号为万元，中号为150150万元，大号万元，大号为为200200万元。现在要制定生产计划，使获得利润最大。万元。现在要制定生产计划，使获得利润最大。设

5、设 分别为小号容器、中号容器和大号容器的分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时生产数量。各种容器的固定费用只有在生产该种容器时才投入，故设才投入，故设 扣除了固定费用的最大利润的目标函数为扣除了固定费用的最大利润的目标函数为 约束条件约束条件1 1（资源限制）：（资源限制）：123,xxx1i0iiy生第 种容器不生第 种容器产产123123 45+6100150200Max zxxxyyy12312312324850023430023100 xxxxxxxxx运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-56 约束条件约束条件

6、2 2（固定费用逻辑约束）（固定费用逻辑约束）约束条件约束条件3 3：112233xy Mxy Mxy M可简化可简化123123,0,0-1xxxyyy量为变运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-57一、整数规划的案例（续）一、整数规划的案例（续）案例案例3：分布系统设计问题：分布系统设计问题 企业在企业在A1A1地已有一个工厂，其生产能力为地已有一个工厂，其生产能力为3030千箱，千箱，为了扩大生产，打算在为了扩大生产，打算在A2A2，A3A3，A4A4，A5A5地中再选择地中再选择几个地方建厂，建厂的固定成本分别为几个地方建厂，建厂的固定成本分别为175175

7、千元，千元，300300千元，千元，375375千元，千元，500500千元。其他信息见下表：千元。其他信息见下表：B1B2B3产量/千箱A184330A252310A343420A497530A5104240销量302020运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-58（1）应该在哪几个地方建厂，在满足销量前提下，使得其总固定成本和总运输费用之和最小？（2）由于政策要求必须在A2，A3 地建一个厂，应在哪几个地方建厂？解：设 为从 运往 的运输量，固定成本及总运输费用最小的目标为ijxiAjB10iiiAyA厂址被中厂址被中当选时当没选时234511121321222

8、3313233414243515253 175+300+375y+500y+8+4+35+234349751042Min zyyxxxxxxxxxxxxxxx运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-59产量限制约束条件：产量限制约束条件：销量限制约束条件：销量限制约束条件：（2）增加约束条件）增加约束条件11121321222323132333414243451525353010203040 xxxxxxyxxxyxxxyxxxy112131415112223242521323334353+302020 xxxxxxxxxxxxxxx运筹学（整数规划问题）运筹学（整数

9、规划问题）李琳李琳2022-8-510二、整数规划的求解方法概述二、整数规划的求解方法概述 整数线性规划，是要求整数解的线性规划，整数线性规划，是要求整数解的线性规划，包括上班的人数、设备的台数、材料的件数等。包括上班的人数、设备的台数、材料的件数等。问题：问题：最优整数解是否可以对非整数最优整数解是否可以对非整数解进行四舍五入法或者去尾法呢？解进行四舍五入法或者去尾法呢？运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-511*2x1+3x2=14.662x1+3x2=142x1+3x2=6121211219527313654401404,xxxxxxx整 为数12 23Ma

10、x zxx线性规划的最优解为：122.44,3.26xx整数规划的最优解为：124,2xx运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-512 TBATBA航空公司是一家地区性公司，从事小型飞航空公司是一家地区性公司，从事小型飞机的短途运输。公司运营状况良好，目前正考虑机的短途运输。公司运营状况良好，目前正考虑扩展业务。扩展业务。公司管理层面临的主要问题是要在两种决策公司管理层面临的主要问题是要在两种决策中作出选择：是购买新一飞机增加短途航班，还中作出选择：是购买新一飞机增加短途航班，还是购买一些大型机提供跨省市航班，从而将市场是购买一些大型机提供跨省市航班，从而将市场扩大

11、到整个国家，或同时采取两种措施。许多因扩大到整个国家，或同时采取两种措施。许多因素都影响着管理层的最终决策，但其中最重要的素都影响着管理层的最终决策，但其中最重要的一点是哪种措施可能会带来最大的利润。一点是哪种措施可能会带来最大的利润。例：例：TBA航空公司航空公司运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳max z=x1+5x2 s.t.5x1+50 x2 100 x1 2 x1,x2,0 运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳TBA航空公司航空公司(无整数约束无整数约束)O12211x最优解最优解2x(2,1.8)运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳

12、TBA航空公司航空公司(整数约束整数约束)O12211x最优解最优解2x(0,2)运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-516舍入化整法舍入化整法l化整后的解可能超出可行域，或者虽是化整后的解可能超出可行域，或者虽是可行解，却不是最优解；可行解，却不是最优解；l 适用情况：适用情况：决策变量取值非常大；决策变量取值非常大；决策变量的价值系数非常小；决策变量的价值系数非常小；运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-517整数规划的分类：整数规划的分类：纯整数规划；纯整数规划；混合整数规划；混合整数规划；0-1规划规划运筹学（整数规划问题）运筹

13、学（整数规划问题）李琳李琳2022-8-518整数规划的求解方法：整数规划的求解方法：割平面法（割平面法（cutting plane algorithm）纯整数规划纯整数规划 分支定界法（分支定界法（branch and bound method）混合整数规划混合整数规划 隐枚举法（隐枚举法（implicit enumeration method）0-1规划规划运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-519分支定界法分支定界法（Branch bound method）l20世纪世纪60年代初由兰德年代初由兰德多伊格和戴金多伊格和戴金等人提出等人提出l原理原理l分支为整

14、数规划最优解的出现创造了条件分支为整数规划最优解的出现创造了条件，缩小了求解范围，而定界则可以提高求，缩小了求解范围，而定界则可以提高求解的效率。解的效率。首先求出整数规划相应的松弛问题的最优解，若求得的最优解符合整数要求，则这个解就是原整数规划的最优解；若不满足，则任选一个不满足整数条件的变量来构造两个新的约束，使原问题分成两个问题，在原可行域中剔除部分非整数解，如此不断重复。运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳分支定界法举例分支定界法举例取整数2121212121,0,3121451149x.xz maxxxxxxxxtsx132X254X1 231)310,23(AS解S

15、得：941 310,23 :21zxxA运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳132X254X1 231)310,23(AS2对S分枝：构造约束：21x和11x形成分枝问题S1和S2，得解B和CS1)37,1(C)923,2(B941923);(2,:zB31037);(1,:zC运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/911x21x运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳132X254X1 231)310,23(AS2对S1分

16、枝：构造约束：32x和22x形成分枝问题S11和S12，得解DS12)2,(1433D14611433);,2(:zDS11无可行解运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21x运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳132X254X1 231)310,23(AS2对S12分枝：构造约束：31x和21x形成分枝问题S121和S122，得解E和FS121)1,3

17、(E4);(3,1:zES122)2,2(F4);(2,2:zF运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21xS122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=431x21x运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-527分支定界说明分支定界说明l分支定界步骤：分支定界步骤：线性规划问题求解-定界过程-剪枝过程（无可行解或不优于

18、现有下界）-分支过程-循环往复l选择原则选择原则 按目标函数系数按目标函数系数 选系数绝对值最大的变量先分支；选与整数值相差最大的非整数变量先分选与整数值相差最大的非整数变量先分支支运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-528三、指派问题三、指派问题l指派问题（指派问题（Assignment problem）又称分配问题，研究如何给n个人（或单位）分配n项工作，使得完成全部工作所消耗的总资源（时间、费用）最少。0 1否则项工作员工分配做第第jixijn1in1jijijc=zMin xn,1,2,=i 1xn1jijn ,1,2,=j 1xn1iijn,1,=jn;

19、,1,2,=i 1,0 xij或s.t.运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-529任 务人 员 E J G R 甲 乙 丙 丁 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 例：有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表所示。问应指派何人去完成何工作，使所需总时间最少?运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-530 指派问题指派问题的解应对应于的解应对应于成本矩阵成本矩阵的不同行与的不同行与不同列，且

20、总成本不同列，且总成本最小。最小。可行解矩阵的每一行每一列只有一个元素为可行解矩阵的每一行每一列只有一个元素为1，共有，共有n个取个取1，其余取值为零。，其余取值为零。nnnnnnnnccccccccccccccccC321333323122322211131211运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-531同解变化同解变化四、匈牙利解法四、匈牙利解法l 美国数学家美国数学家W.KnhnW.Knhn于于19551955年给出的，由年给出的，由于他的解法运用了匈牙利数学家于他的解法运用了匈牙利数学家D.KonigD.Konig关于矩阵零元素的一个定理，因此被称关于矩阵

21、零元素的一个定理，因此被称为匈牙利解法。为匈牙利解法。l定理：对于指派问题，成本矩阵的任一定理：对于指派问题，成本矩阵的任一行行(或列或列)减去减去(或加上或加上)一个相同的数得一个相同的数得到的新指派问题与原问题同解。到的新指派问题与原问题同解。s)(s)(xcxc xs)(xcxc s)x(cxc=z n1jkjkjnki1in1jijijn1jkjn1jkjkjnki1in1jijijn1jkjkjnki1in1jijijz运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳l定理定理：覆盖一个方阵内所有：覆盖一个方阵内所有0 0元的最小直线数元的最小直线数等于该阵中位于不同行、列的等于

22、该阵中位于不同行、列的0 0元的最多个数；元的最多个数；l基本思想（反复应用同解变换）基本思想（反复应用同解变换）成本矩阵（效益矩阵）的每一行及每一列减去该行或列的成本矩阵（效益矩阵）的每一行及每一列减去该行或列的最小数，使每行每列至少有一个最小数，使每行每列至少有一个0 0，假如能够从中找出，假如能够从中找出n n个位于个位于不同行、列的不同行、列的0 0元，则为最优阵，对应最优解。元，则为最优阵，对应最优解。如果划去这些如果划去这些0 0所需要的直线数不少于所需要的直线数不少于n n（等于（等于n n），则此），则此时就可以求得最优解。时就可以求得最优解。四、匈牙利解法（续）四、匈牙利解法

23、（续）运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳6101296106147678129610141797121578466674310463040810126303710208113400432040500123203771081103004320405001232037710811030运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳043204050012320377108110300432140501012102660081103104321405010121026600811031运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳2022-8-535练习练习464840

24、4735444340344139434745424465050683045750009505035001248000运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳一般指派问题（非标准）：一般指派问题（非标准）：最大化指派问题（效益矩阵）最大化指派问题（效益矩阵）人数和工作数不等的指派问题人数和工作数不等的指派问题一个人可做几项工作的指派问题一个人可做几项工作的指派问题某项工作一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳最大化指派问题最大化指派问题610129610617711781296101429121215784最大

25、化指派问题最大化指派问题最大值最大值617101712179176171017617171771711177178171217917617101714172179171217121715177178174171175811711010610958117315855210913最最小小化化指指派派问问题题运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳人数和工作数不等的指派问题人数和工作数不等的指派问题1012966177118129614291215784101296617711812961429121578400000运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳一个人可做几项工作的指派问题：一个人可做几项工作的指派问题：78329824763195232154321BBBBBAAA 31952319527832982476319525432111321BBBBBAAAAAA1可同时做可同时做三项工作三项工作运筹学（整数规划问题）运筹学（整数规划问题）李琳李琳某项工作一定不能由某人做的指派问题：某项工作一定不能由某人做的指派问题：452782946178298247639525432154321BBBBBAAAAA4 5 2 782 9 4 6178298247639525432154321MMAAAAABBBBBA1不能做不能做B4;A3不能做不能做B3