问题一汽车厂月度生产计划 汽车厂生产小、中、大三种类型的汽车,各 种类型的汽车对钢材以及劳动时间的需求如下 表试制订月生产计划使该工厂的利润最大 小型车中型车大型车现有量 钢材 1.5 3 5 600 劳动时间280250 40060000 利润 2 3
问题一 汽车厂月度生产计划 一汽车厂生产小、中、大三种类型的汽车,各 种类型的汽车对钢材以及劳动时间的需求如下 表.试制订月生产计划,使该工厂的利润最大. 小型车 中型车 大型车 现有量 钢材 1.5 3 5 600 劳动时间 280 250 400 60000 利润 2 3 4
分析 小型车中型车大型车现有量 钢材 1.5 3 5 600 劳动时间28025040060000 利润 2 3 从收益率来看,比较中型车和大型车得出结论, 生产大型车不经济因此若允许车辆数量为实 数,则不生产大型车但是现在车辆为整数因此 模型为
分析 小型车 中型车 大型车 现有量 钢材 1.5 3 5 600 劳动时间 280 250 400 60000 利润 2 3 4 从收益率来看,比较中型车和大型车得出结论, 生产大型车不经济.因此,若允许车辆数量为实 数,则不生产大型车.但是现在车辆为整数,因此 模型为
1模型的建立 记月生产的小、中、大型车的数量分别为x1, x2x3,模型为 max = 2x,+3x+4x 1.5x1+3x2+5x3≤600, st x为非负整数() 280x1+250x2+400x3≤60000 这是个整数线性规划问题有三个决策变量,要 用软件来求IP但是本题比较特殊我们可以发 现
1 模型的建立 记月生产的小、中、大型车的数量分别为 x1 , x2 , x3 ,模型为 . (*) 280 250 400 60000, 1.5 3 5 600, . . max 2 3 4 1 2 3 1 2 3 1 2 3 xi 为非负整数 x x x x x x s t R x x x + + + + = + + 这是个整数线性规划问题,有三个决策变量, 要 用软件来求ILP.但是本题比较特殊,我们可以发 现
max R=2x,+3x 2LP图解法 1.5x1+3x2≤600, st 我们先得到实数型的最优 280x1+250x2≤60000 解为(64.5,1677),利润的x2 最大值为6323 (645,1677 但是遗憾的是,这个解不是 整数解,因此不合要求解决 方法: 1)由于解的数字都比较大我们可以简单地舍去小 数,即取(64,167)此时利润为629,可以接受同时定界 (2)在最优解附近试探:(64,168);(65,167);(66,167, (65,166,1)等等利润分别为632,631,后两个不满足约 束由于最大利润为632,故最优解为64,168
2 LP图解法 我们先得到实数型的最优 解为（64.5,167.7),利润的 最大值为632.3. x1 x2 （64.5,167.7) • 但是,遗憾的是,这个解不是 整数解,因此不合要求.解决 方法: (1) 由于解的数字都比较大,我们可以简单地舍去小 数,即取(64,167),此时利润为629,可以接受.同时定界. (2) 在最优解附近试探:(64,168);(65,167); (66,167), (65,166,1)等等.利润分别为632,631,后两个不满足约 束.由于最大利润为632,故最优解为(64,168). + + = + 280 250 60000, 1.5 3 600, . . max 2 3 1 2 1 2 1 2 x x x x s t R x x
3进一步讨论 由于各种原因(比如,工艺,若生产某种汽车,则至少生 产80辆问生产计划有何改变? 分析:要么x=0,要么x≥80组合起来,共有八种情形 (1)x1=x2=x3=0; (2)x1≥80,x2=x3=0; (3)x2≥80,x1=x3=0 (4)x3≥80,x1=x2=0; (5)x1≥80,x2≥80,x3=0;(6)x1≥80,x3≥80,x2=0; (7)x2≥80,x3≥80,x1=0;(8)x1≥80,x2≥80,x3≥80; 方法一:让它们分别与模型()一起来求解新的LP 逐一得到它们的最优解其中(1)不用解;(7,8)无 解;(2)的解为(2143,0,0),z4285:3)的解为 (0,200,0),=600;;(4)的解为(0,0,120,z=480;
3 进一步讨论 由于各种原因(比如,工艺),若生产某种汽车,则至少生 产80辆,问生产计划有何改变? 分析:要么xi=0,要么xi≥80,组合起来,共有八种情形: (7) 80, 80, 0; (8) 80, 80, 80; (5) 80, 80, 0; (6) 80, 80, 0; (3) 80, 0; (4) 80, 0; (1) 0; (2) 80, 0; 2 3 1 1 2 3 1 2 3 1 3 2 2 1 3 3 1 2 1 2 3 1 2 3 = = = = = = = = = = = = x x x x x x x x x x x x x x x x x x x x x x x x 方法一: 让它们分别与模型(*)一起来求解新的LP, 逐一得到它们的最优解.其中(1)不用解;(7),(8)无 解;(2)的解为(214.3,0,0),z=428.5;(3)的解为 (0,200,0),z=600; ;(4)的解为(0,0,120),z=480;