文档介绍：1 第6章整数规划?整数规划模型及其与线性规划的区别?整数规划的求解——分支定界法、割平面法?0-1 整数规划模型与求解?指派问题模型与求解?整数规划的应用——建模 2 一、整数规划的一般形式例1某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如下表: 货物体积(米 3/箱) 重量(百斤/箱) 利润(百元/箱) 甲乙 54 25 2010 托运限制 2413 问两种货物各托运多少箱,可使获得的利润为最大? 第一节整数规划问题的提出 3 ????????????,且为整数,0 13 52 24 45: 10 20 21 21 21 21xx xx xx ST xx MaxZ :设托运甲、乙两种货物 x 1,x 2箱,用数学式可表示为: :0, j MaxZ CX AX b STx ??????x j部分或全部为整数 4 (1)求解方法方面问题与 LP问题的区别* * ( , ) , 4 1 90 T X Z ? ?在例 1中, IP问题实际上,此 IP问题的最优解为: * * ( . , ) , 4 8 0 96 ? ? T X Z ????????????,且为整数,0 13 52 24 45: 10 20 21 21 21 21xx xx xx ST xx MaxZ 不考虑整数约束的最优解为: (1) X (1) =(5, 0) T不是(1) 的可行解 X (2) =(4, 0) T虽是可行解,但不是最优解 5 例2做图分析例 1的最优解(直观) IP 问题的可行域不是凸集(2)理论方面 x 1 x 24840123567 31 25x 1 +4 x 2 =24 2x 1 +5 x 2 =13 (, 0) T Z=96 (4, 1) T Z=90 6 二、整数规划的分类 (Pure Integer Programming) (All Integer Programming) 在 IP问题( 1)中,还要求 a ij , b i全为整数。:0, j MaxZ CX AX b STx ??????x j全部为整数(1) -1 规划问题在 IP问题( 1)中, 要求 x j =0或1. (Mixed Integer Programming) 在 IP问题( 1)中,只要求部分 x j 为整数. 7 适用范围: 全整数规划问题、纯整数规划问题、混合整数规划问题第二节分支定界法(Branch and Bound Method) 指派问题: n! 仅检查可行的整数组合的一部分隐枚举法穷举变量的所有可行的整数组合× IP:A LP:B Z *Z Z≤≤ 8 一、几何解释例1求解整数规划问题????????????,且为整数,0 70 20 7 56 79: 90 40 21 21 21 21xx xx xx ST xx MaxZ 第二节分支定界法(Branch and Bound Method) (0,0)Z*≥0 9 解:图解法。 x 1 x 20********** 1 2 3 4 5 6 7 8 9x 1 +7 x 2 =56 7x 1 +20 x 2 =70 BC 问题 B 1Z 1 =349 x 1 = x 2 = 问题 B 2Z 2 =341 x 1 = x 2 = x 1 <=[ x 1 (0) ]=4x 1 >=[ x 1 (0) ]+1=5 X (0) =(, ) Z 0 =356 0≤ Z*≤356 0≤ Z*≤349 10 解:图解法。问题 B 1Z 1 =349 x 1 = x 2 = 问题 B 2Z 2 =341 x 1 = x 2 = x 2 <=[ x 2 (0) ]=2 x 1 x 20********** 1 2 3 4 5 6 7 8 9x 1 +7 x 2 =56 7x 1 +20 x 2 =70 BC X (0) =(, ) Z 0 =356 0≤ Z*≤349 x 2 >=[ x 2 (0) ]+1=3 问题 B 3 (, ) 340 问题 B 4 (, ) 327 340 ≤ Z*≤341 B 3B 4