运筹学讲义 max ==x, +x2 sL.-2x1+2x2≥1 8x1+10x,≤13 x1,x2≥0,整数 其松弛线性规划问题为 max ==x +x2 x+2x2≥1 (LP) 8x1+10x2≤13 x1,x2≥0 利用图解法 1 易见,(LP)的最优解为(4,)2,最优值为取整后,得(P)的“最优解”为(4,5),“最优 值”为9但实际上,(P)的最优解为(1,2),最优值为3.显然,二者差别甚大! 于是,求解整数规划的新算法的引入成为必要 然而,遗憾的是,迄今为止,还没有一种方法能有效地求解一切整数规划!§6.3.1和§6.3.2 将介绍求解整数规划的两种特殊方法-—割平面法和分支定界法 但是,也确有一些线性规划问题,其本身的结构就决定了它必然存在整数解 单(幺)模阵( unimodular matrix):行列式的值为0,-1,1的整数方阵运 筹 学 讲 义 2         − +  − +  = + , 0,整数 8 10 13 . . 2 2 1 max ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x IP ， 其松弛线性规划问题为         − +  − +  = + , 0 8 10 13 . . 2 2 1 max ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x LP . 利用图解法解之： 易见， (LP) 的最优解为 T ) 2 9 (4, ，最优值为 2 17 .取整后，得 (IP) 的“最优解”为 T (4,5) ，“最优 值”为 9.但实际上， (IP) 的最优解为 T (1,2) ，最优值为 3 .显然，二者差别甚大！ 于是，求解整数规划的新算法的引入成为必要. 然而，遗憾的是，迄今为止，还没有一种方法能有效地求解一切整数规划！§6.3.1 和§6.3.2 将介绍求解整数规划的两种特殊方法---割平面法和分支定界法. 但是，也确有一些线性规划问题，其本身的结构就决定了它必然存在整数解. 单（幺）模阵（unimodular matrix）：行列式的值为 0，-1，1 的整数方阵