问题一汽车厂月度生产计划 汽车厂生产小、中、大三种类型的汽车,各 种类型的汽车对钢材以及劳动时间的需求如下 表试制订月生产计划使该工厂的利润最大 小型车中型车大型车现有量 钢材 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;
5)的最优解为(80,150.4,0), z6112;工时为紧约束; (6)的最优解为(80,0,94), (645,1677 536;工时为紧约束; 结论:此时最优解为 (80,150.4,0),利润为612 3 75,975) 可行域 5x1+3x2+5x3≤600, 280x1+250x,+400x2≤60000
(5)的最优解为(80,150.4,0), z=611.2;工时为紧约束; (6)的最优解为(80,0,94), z=536;工时为紧约束; + + + + 280 250 400 60000, 1.5 3 5 600, . . 1 2 3 1 2 3 x x x x x x s t 结论:此时最优解为 (80,150.4,0), 利润为611.2 1 x x2 （64.5,167.7) • (75,97.5) ∙ 可行域 1 x 3 x
方法二引入0-1变量 要么x2=0要么x,≥80等价于 x1≤M1,X1≥80y1,y∈{0,1}, 这里M为充分大正数本例可以取1000 x1SM的作用是当y=0时,必有x=0 本例中,≤M1,x≥80y,=1 →x1≥80(x≤1000然满足 max R= 2x,+3x+4x 3 1.5x1+3x,+5x3≤600 280x1+250x,+400x3≤60000
方法二 引入0-1变量 , 1000. , 80 , {0,1}, 0 80 这 里 为充分大正数 本例可以取 要 么 要 么 等价于 M x My x y y x x i i i i i i i = + + + + = + + 280 250 400 60000, 1.5 3 5 600, . . max 2 3 4 1 2 3 1 2 3 1 2 3 x x x x x x s t R x x x xi Myi 的作用是当yi=0时,必有xi=0. 本例中, 80( 1000 ) , 80 , 1 自然满足 = i i i i i i i x x x My x y y
方法三从数学上讲, 要么x;=0要么x;≥80等价于 对非负变量满足x(x;-80)≥0. 不过这个式子对变量而言,出现了非线性函数,因 此就变成了非线性规划问题,其求解往往比较困难, 即使用软件求解(如 LINGO, Matlab),也往往依赖 于初值的选择 评注:若能用线性规划处理,则尽量不要用非线性 规划
方法三 从数学上讲, ( ) . : 80 0 0 80 − = i i i i i x x x x x 对非负变量 满 足 要 么 要 么 等价于 不过,这个式子对变量而言,出现了非线性函数,因 此就变成了非线性规划问题,其求解往往比较困难, 即使用软件求解(如:LINGO,Matlab),也往往依赖 于初值的选择. 评注:若能用线性规划处理,则尽量不要用非线性 规划
例2原油的采购与加工 问题某公司用两种原油(A和B混合加工成两 种汽油(甲和乙)甲乙两种汽油含原油A的最低 比例分别是50%和60%每吨售价分别为4800 元和5600元该公司现有原油A和B的库存量分 别为500吨和1000,还可以从市场上买到不超 过1500吨的原油A原油A的市场价为购买量不 超过500吨时的单价为10000吨;购买量超过 50吨但不超过1000吨时,超过500吨的部分 8000元/吨;购买量超过1000吨时,超过1000吨的 部分6000元/吨该公司应如何安排原油的采购 和加工?
例2 原油的采购与加工 问题 某公司用两种原油(A和B)混合加工成两 种汽油(甲和乙).甲乙两种汽油含原油A的最低 比例分别是50%和60%,每吨售价分别为4800 元和5600元.该公司现有原油A和B的库存量分 别为500吨和1000吨,还可以从市场上买到不超 过1500吨的原油A.原油A的市场价为:购买量不 超过500吨时的单价为10000元/吨;购买量超过 500吨但不超过1000吨时,超过500吨的部分 8000元/吨;购买量超过1000吨时,超过1000吨的 部分6000元/吨.该公司应如何安排原油的采购 和加工?
模型的建立 设购买原油Ax吨生产汽油甲所用的原油A和B 分别为x1和x21吨;乙的分别为x12和x2吨公司销 售生产的汽油收入为P千元纯收入为R千元则 P=4.8(x1+x21)+56(x12+x22) x21+x22≤1000,x≤1500,x1+x12≤500+x; i11≥0.5(x1+x21);x12≥0.6(x12+x2) 购买原油A的成本为 10x, 0≤x≤500 c(x)={5000+8(x-500, 500≤x≤1000 5000+40006(x-1000),100≤x≤1500
模型的建立 设购买原油A x吨,生产汽油甲所用的原油A和B 分别为x11和x21吨;乙的分别为x12和x22吨.公司销 售生产的汽油收入为P千元,纯收入为R千元.则 4.8( ) 5.6( ) P = x1 1 + x2 1 + x1 2 + x2 2 1000, 1500, 500 ; x2 1 + x2 2 x x1 1 + x1 2 + x 0.5( ); 0.6( ). x1 1 x1 1 + x2 1 x1 2 x1 2 + x2 2 购买原油A的成本为 + + − + − = 5000 4000 6( 1000), 1000 1500 5000 8( 500), 500 1000 10 , 0 500 ( ) x x x x x x c x