运筹学 第五章 整数规划 2013-01-24.pptx

第五章 整数规划;本章学习要求;5.1整数规划数学模型和解的特点;某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量和可获得的利润及托运所受限制如表，问两种货物各托运多少箱，使得利润最大？ 设甲乙两种货物各托运X1,X2箱;Max z=20x1+10x2 5x1+4x2≤24 2x1+5x2≤13 x1,x2≥0且为整数;现有资金总额B，可供选择的投资项目有m个，项目j所需要的投资额和预期的收益分别为aj和cj，由于各种原因有3个附加条件：①若选项目1，则必选项目2，反之则不一定；②项目3和项目4必须选一个；③项目5，6，7中恰好选2个。应当如何选择投资项目才能使总预期收益为最大？;解：每一个投资项目都有被选择和不被选择两种可能，设 xj=1 对j项目投资 0 对j项目不投资 Max z=∑cjxj ∑ajxj≤B x2≥x1 x3+x4≥1 x5+x6+x7=2 xj=0或1 ;1.整数线性规划（ILP）的类型;线性规划模型 max z=x1+4x2 s.t. 14x1+42x2≤196 -x1+ 2x2≤ 5 x1, x2≥0;线性规划的最优解A(x1, x2)=(2.6, 3.8)不是整数解，目标函数值为z=17.8。整数规划的最优解B(x1, x2)=(5,3)目标函数值为z=17。线性规划最优解A(2.6, 3.8)四舍五入得到的解为(3,4)，不是可行解；舍去尾数取整的解为(2,3)，目标函数值z=14。 因此整数规划的最优解一般不能由线性规划的最优解通过简单的取整得到。;3.整数线性规划（ILP）解的特点;5.2 割平面法和分支定界法;1.割平面法;1.割平面法;1.割平面法;1.割平面法;例（接上）：;2. 分支定界法;步骤： 解整数规划问题（ILP）的松弛问题，结果可能有三种： 松弛问题没有可行解，ILP也没有可行解，停止计算。 松弛问题有最优解，并符合ILP的整数条件，则此最优解即为ILP的最优解，停止计算。 松弛问题有最优解，但不符合ILP的整数条件，记它的目标函数值为 ； 用观察法找问题ILP的一个整数可行解，求得其目标函数值，并记作 ，以Z*表示ILP的最优目标函数值，则 分支，如松弛问题有一个最优解xj为非整数值bj，则可以构造两个分支。 xj≤[bj] xj≥[bj]+1 定界，以每个后继问题为一分支表明求解的结果。;;5.3 0-1整数规划;1.背包问题;设三种物品的件数各为x1，x2，x3件，总价值为z。 max z=17x1+72x2+35x3 s.t. 10x1+41x2+20x3≤50 x1，x2，x3≥0 x1，x2，x3为整数 这是一个整数规划问题（Integer Programming）。这个问题的最优解为： x1=1件，x2=0件，x3=2件，最高价值z=87元;2.厂址选择模型;max z=70x1+55x2+42x3+28x4+11x5 s.t. 320x1+280x2+240x3+210x4+180x5≤800 20x1+ 18x2+ 15x3+ 11x4+ 8x5≤ 60 x1+ x2+ x3+ x4+ x5= 3 x1, x2, x3, x4, x5≥0 x1，x2，x3，x4，x5 为 0－1变量;3.多决策问题;max z=24x1+18x2+21x3+17x4+22x5 s.t. 5.0x1+1.0x2+3.0x3+2.0x4+4.0x5≤ 180 3.0x2+4.0x3+1.0x4+5.0x5≤2500 3.0x1+2.0x2+1.0x3+3.0x4+2.0x5≤2200 x1，x2，x3，x4，x5≥0 x1，x2，x3，x4，x5为整数;max z=24x1+18x2+21x3+17x4+22x5 s.t. 5.0x1+1.0x2+3.0x3+2.0x4+4.0x5≤ 180 3.0x2+4.0x3+1.0x4+5.0x5≤2500 3.0x1+2.0x2+1.0x3+3.0x4+2.0x5≤2200 x1≤10000y1 x2≤10000y2 x3≤10000y3 x4