运筹学课件讲解.pptVIP

一、整数规划的模型 二、分枝定界法 （二） 例题 练习：用分枝定界法求解整数规划问题 （图解法） 例二、用分枝定界法求解整数规划问题（单纯形法） 练习：用分枝定界法求解整数规划问题 （单纯形法） 三、割平面法 四、0－1 整数规划 练习：用隐枚举法求解0—1规划问题 五、指派问题 例一： 例二、 练习： 由上表可知，问题的最优解为 X*=(1,0,1 )T 由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x1－2 x2＋5 x3 ≥5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。 × 4 ( 1. 1. 1 ) × 1 ( 1. 1. 0 ) 8 ∨ 8 0 2 1 1 ( 1. 0. 1 ) × 3 ( 1. 0. 0 ) × 3 ( 0. 1. 1 ) × -2 ( 0. 1. 0 ) 5 ∨ 5 －1 1 0 1 ( 0. 0. 1 ) 0 ∨ 0 0 0 0 0 ( 0. 0. 0 ) 是∨ 否× (0) (1) (2) (3) (4) Z 值 满足条件 约束条件 x1 . x2. x3 例二、求解下列0－1 规划问题 解：由于目标函数中变量x1, x2 , x4 的系数均为负数，可作如下变换： 令 x1 ＝1－ x1′ , x2 =1- x2′, x3= x3′, x4 =1- x4′带入原题中，但需重新调整变量编号。令 x3′ = x1′, x4′ = x2′得到下式。 可以从( 1.1.1.1 )开始试算， x′(3)＝( 1.1.0.1 )T最优解。 ∴ x(3)＝( 1.0.1.0 )T是原问题的最优解，Z* =－2 例三、求解下列0－1 规划问题 令 y1=x5, y2=x4, y3=x2, y4=x3, y5=x1 得到下式 × 3 -2 ( 0. 0. 0. 0. 1 ) 8 ∨ 4 -4 ( 0. 0. 0. 1. 0 ) × -2 1 ( 0. 0. 1. 0. 0 ) × -1 1 ( 0. 1. 0. 0. 0 ) × 1 -1 ( 1. 0. 0. 0. 0 ) × 0 0 ( 0. 0. 0. 0. 0 ) 是 ∨否× (1) (2) Z 值 满足条件 约束条件 y1 . y2. y3 . y4. y5 所以， Y*= （0.0.0.1.0），原问题的最优解为： X* ＝（0.0.1.0.0）T，Z* =8 （0 . 1 . 1 . 0 . 0） 在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。 （一） 指派问题的数学模型 设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j 件工作的的效率（ 时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij ≥0。问应如何分配才能使总效率（ 时间或费用）最高？ 设决策变量 1 分配第i 个人去做第j 件工作 xij = 0 相反 ( i,j=1.2. …n )