第3章整数规划
线性规划模型: maXz=C1x1+C,X2+∴c孓 1x1+a12x2+…+a1nxn=b1 s t anx+anx2+…+amxn=bn 0 1:2 °n 实际问题要求x为整数! 如机器的台数,人数等
n n z = c x + c x ++ c x max 1 1 2 2 + + + = + + + = + + + = m m mn n m n n n n a x a x a x b a x a x a x b a x a x a x b st 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 . , , 0 x1 x2 xn 线性规划模型： 实际问题要求xi为整数！ 如机器的台数，人数等
线性整数规划 整数规划 简称整数规划 非线性整数规划
整数规划 线性整数规划 非线性整数规划 简称整数规划
3.1整数规划问题 实例
一、实例
例21胜利家具厂生产桌子和椅子两种家具。桌子售价50元/ 个,椅子售价30元/个,生产桌子和椅子需要木工和油漆工两 种工种。生产一个桌子需要木工4个小时,油漆工2小时。生 产一个椅子需要木工3个小时,油漆工1小时。该厂每月可用 木工工时为120小时,油漆工工时为50小时。问该厂如何组 织生产才能使每月的销售收入最大? 解:设x1=生产桌子的数量x2=生产椅子的数量 每月的销售收入 求maxZ=50x1+30x2 4x,+3x2<120 纯整数 s2x,+x,≤50 规划 x1,x2≥0 x1,x2为整数
例2.1 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/ 个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两 种工种。生产一个桌子需要木工4个小时，油漆工2小时。生 产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用 木工工时为120小时，油漆工工时为50小时。问该厂如何组 织生产才能使每月的销售收入最大？ 每月的销售收入 解：设 生产桌子的数量 生产椅子的数量 = = = Z x x 1 2 , 1 2 求max Z = 50x +30x 4 + 3 120 . 1 2 x x st 2x1 + x2 50 , 0 x1 x2 x1 , x2 为整数 纯整数 规划