(1)的可行解.因为它不满足（1)中的约束条件，若取X,=(4.0,0)TX2是（1)的可行解，但它却不是(1)的最优解，因为当X2=(4.0,0)时,Z2=80,但当X3=（4,1)T时,Z3=90>Z2即伴随规划的最优解通过“舍零取整”得到的X1,X，都不是（1)的最优解.因此通过伴随规划最优解的“舍零取整”的办法，一般得不到原整数规划问题的最优解：若伴随规划(2)的可行域K是有界的,则原整数规划(1)的可行域K。应是K中有限个格点(整数点）的集合.见图1,图中“*"为整数点(格点)
(1)的可行解.因为它不满足 (1) 中的约束条件, 若取X2=(4.0,0)T . X2是 (1) 的可行解, 但它却不是(1) 的最优解, 因为当X2=(4.0,0)T 时,Z2 = 80, 但当X3 = (4,1)T 时,Z3 = 90 > Z2 ·即伴随规划的最优 解通过 “ 舍零取整 ” 得到的X1 ,X2 都不是 (1) 的最优解 .因此通 过伴随规划最优解的 “ 舍零取 整 ” 的办法 , 一般得不到原整数 规划问题的最优解 . 若伴随规划(2)的可行域 K 是有界的,则原整数规划(1)的可行 域 K 0应是K中有限个格点(整数点）的集合.见图1, 图中“*" 为整数点(格点)
t图1中四边形OABC是伴随AS2规划（2）的可行域.它的最优解B****1为 C 点(4.8,0), 而(1)的可0324.84x行域为k =(0,0),(0,1), (0,2), (1,0),(1, 1),(1,2), (2,0), (2,1),(3,0),(3,1),(4,0)(4,1)}.将C点“舍零取整"后得到的X,=(5.0,0)T不在K.中,而X,=(4,0)T在K.中,但不是(1)的最优解,最优解在B点当然，我们也会想到能否用“穷举法”来求解整数规划.如（1）问题，将K，中所有整数点的目标函数值都计算出来，然后逐一比较找出最优解.这种方法对变量所能取的整数值个数较少时，勉强可以应用如本例可取0,1,2,3,4
1 1 2 3 4 4.8 2 1 x 2 x A C B 图1 中四边形 OABC 是伴随 规划(2)的可行域.它的最优解 为 C 点(4.8, 0), 而 (1) 的可 O 行域为k0 ={(0,0),(0,1), (0,2), (1,0),(1, l),(1,2), (2,0), (2,1),(3,0), (3,1),(4,0),(4, l)}. 将C点“舍零取整”后得到的X1=(5.0,0)T不在 K0中,而X2=(4,0)T在K0中,但不是(1)的最优解,最优解在B点. 当然, 我们也会想到能否用“穷举法”来求解整数规划.如(1) 问题,将 K0 中所有整数点的目标函数值都计算出来,然后逐 一比较找出最优解.这种方法对变量所能取的整数值个数较少 时,勉强可以应用.如本例 可取x1 0,1,2,3,4
共5个数值.而x只能取01,2共三个数值，因此其组合最多为15个(其中有不可行的点).但对大型问题这种组合数的个数可能大得惊人！如在指派问题中，有n项任务指派n个人去完成，不同的指派方案共有n！种当n=20时，这个数超过2×1018.如果用穷举法每一个方案都计算一遍就是用每秒百万次的计算机，也要几万年显然“穷举法”并不是一种普遍有效的方法.因此研究求解整数规划的一般方法是有实际意义的.自20世纪60年代以来已发展了一些常用的解整数规划的算法如各种类型的割平面法、分枝定界法、解0-1规划的隐枚举法
共5个数值.而 只能取0,1,2共三个数值,因此其组合最多 为15个(其中有不可行的点).但对大型问题,这种组合数的 个数可能大得惊人! 如在指派问题中,有n 项任务指派n个 人去完成,不同的指派方案共有n! 种 .当 n=20 时 ,这个 数超过2×1018 . 如果用穷举法每一个方案都计算一遍 , 就是用每秒百万次的计算机,也要几万年 . 2 x 显然 “穷举法” 并不是一种普遍有效的方法.因此研究求解 整数规划的一般方法是有实际意义的.自20世纪60年代以来, 已发展了一些常用的解整数规划的算法,如各种类型的割平 面法、分枝定界法、解 0-1 规划的隐枚举法
分解方法、群论方法、动态规划方法等等。近十年来有人发展了一些近似算法及用计算机模拟法，也取得了较好的效果分枝定界法在20世纪60年代初LandDoig和Dakin等人提出了分枝定界法.由于该方法灵活且便于用计算机求解，所以自前已成为解整数规划的重要方法之一.分枝定界法既可用来解纯整数规划，也可用来解混合整数规划分枝定界法的主要思路是首先求解整数规划的伴随规划如果求得的最优解不符合整数条件，则增加新约
分解方法、群论方法、动态规划方法等等。近十年来有人 发展了一些近似算法及用计算机模拟法,也取得了较好的效 果 . 分枝定界法 在20世纪60年代初 Land Doig 和 Dakin 等人提出了分枝 定界法.由于该方法灵活且便于用计算机求解,所以目前已 成为解整数规划的重要方法之一.分枝定界法既可用来解纯 整数规划,也可用来解混合整数规划. 分枝定界法的主要思路是首先求解整数规划的伴随规划 , 如果求得的最优解不符合整数条件,则增加新约
束一缩小可行域;将原整数规划问题分枝一一分为两个子规划,再解子规划的伴随规划.....通过求解一系列子规划的伴随规划及不断地定界.最后得到原整数规划问题的整数最优解下面结合一个极大化例题来介绍分枝定界法的主要思路例2某公司计划建筑两种类型的宿舍.甲种每幢占地0.25×103m2，乙种每幢地0.4×103m2.该公司拥有士地3×103m2计划甲种宿舍不超过8幢，乙种宿舍不超过4幢.甲种宿舍每幢利润为10万元，乙种宿舍利润为每幢20万元.问该公司应计划甲、、乙两种类型宿舍各建多少幢时,能使
束——缩小可行域;将原整数规划问题分枝——分为两个子 规划,再解子规划的伴随规划.通过求解一系列子规划的 伴随规划及不断地定界 .最后得到原整数规划问题的整数最 优解 . 下面结合一个极大化例题来介绍分枝定界法的主要思路 . 例2 某公司计划建筑两种类型的宿舍.甲种每幢占地0.25 ×103m2 , 乙种每幢地0.4×103m2 .该公司拥有土地3×103m2 . 计划甲种宿舍不超过 8 幢,乙种宿舍不超过4幢.甲种宿舍每 幢利润为10万元，乙种宿舍利润为每幢20万元.问该公司应 计划甲、乙两种类型宿舍各建多少幢时,能使