清华大学：《优化建模与LINDO/LINGO软件》课程教学资源（PPT课件）第5章 生产与服务运作管理中的优化问题

优化建檩 优化建模与LIN0/LING0软件 第5章 生产与服务运作管理中的优化问题

优化建模 生产与服务运作管理中的优化问题 优化建模与LINDO/LINGO软件 第5章

优化建檩 内容提要 §5.1生产与销售计划问题 s5.2有瓶颈设备的多级生产计划问题 s5.3下料问题 §5.4面试顺序与消防车调度问题 §5.5飞机定位和飞行计划问题

优化建模 内容提要 §5.1 生产与销售计划问题 §5.2 有瓶颈设备的多级生产计划问题 §5.3 下料问题 §5.4 面试顺序与消防车调度问题 §5.5 飞机定位和飞行计划问题

优化建檩 §51生产与销售计划问题

优化建模 §5.1 生产与销售计划问题

优化建檩 §5.1.1问题实例 例5.1某公司用两种原油(A和B)混合加工成两种 汽油(甲和乙)。甲、乙两种汽油含原油A的最低 比例分别为50%和60%,每吨售价分别为4800元和 5600元。该公司现有原油A和B的库存量分别为500 吨和1000吨,还可以从市场上买到不超过1500吨 的原油A。原油A的市场价为:购买量不超过500吨 时的单价为10000元/吨;购买量超过500吨但不超 过1000吨时,超过500吨的部分8000元/吨;购买 量超过1000吨时,超过1000吨的部分6000元/吨 该公司应如何安排原油的采购和加工

优化建模 §5.1.1问题实例 • 例5.1某公司用两种原油（A和B）混合加工成两种 汽油（甲和乙）。甲、乙两种汽油含原油A的最低 比例分别为50%和60%，每吨售价分别为4800元和 5600元。该公司现有原油A和B的库存量分别为500 吨和1000吨，还可以从市场上买到不超过1500吨 的原油A。原油A的市场价为：购买量不超过500吨 时的单价为10000元/吨；购买量超过500吨但不超 过1000吨时，超过500吨的部分8000元/吨；购买 量超过1000吨时，超过1000吨的部分6000元/吨。 该公司应如何安排原油的采购和加工

优化建檩 §5.1.2建立模型 问题分析 安排原油采购、加工的目标是利润最大,题目中给 出的是两种汽油的售价和原油A的采购价,利润为 销售汽油的收入与购买原油A的支出之差。这里的 难点在于原油A的采购价与购买量的关系比较复杂, 是分段函数关系,能否及如何用线性规划、整数规 划模型加以处理是关键所在

优化建模 §5.1.2建立模型 问题分析 安排原油采购、加工的目标是利润最大，题目中给 出的是两种汽油的售价和原油A的采购价，利润为 销售汽油的收入与购买原油A的支出之差。这里的 难点在于原油A的采购价与购买量的关系比较复杂， 是分段函数关系，能否及如何用线性规划、整数规 划模型加以处理是关键所在

优化建檩 模型建立设原油A的购买量为x(吨),根据题目所给数据, 采购的支出c(x)可表为如下的分段线性函数(以下价格以 千元/吨为单位): 10x (0≤x≤500 (x)=11000+8x(500≤x≤1000 30006x(1000≤x≤1500) 设原油A用于生产甲、乙两种汽油的数量分别为x1和x12(吨), 原油B用于生产甲、乙两种汽油的数量分别为x1和x2(吨), 则总的收入为48(x1+x2)+56(x2+x2)(千元) 于是本例的目标函数(利润)为 Mmxz=48(x1+x21)+56(x12+x2)-c(x)2)

优化建模 模型建立设原油A的购买量为x（吨），根据题目所给数据， 采购的支出c(x)可表为如下的分段线性函数（以下价格以 千元/吨为单位）：      +   +     = 3000 6 (1000 1500) 1000 8 (500 1000) 10 (0 500) ( ) x x x x x x c x (1) 设原油A用于生产甲、乙两种汽油的数量分别为x11和x 12（吨）， 原油B用于生产甲、乙两种汽油的数量分别为x21和x 22（吨）， 则总的收入为4.8(x 11+x 21)+5.6(x 12+x 22)（千元）。 于是本例的目标函数（利润）为 4.8( ) 5.6( ) ( ) 11 21 12 22 Max z = x + x + x + x − c x (2)

优化建檩 约束条件包括加工两种汽油用的原油A、原油B库存量的限制 和原油A购买量的限制,以及两种汽油含原油A的比例限制, 它们表示为 x1+x12≤500+x (3) x21+x2≤1000 (4) x≤1500 (5) x1>0.5 x11+x 11 2>0.6 (7) x+x x12x12x212x2x≥0 由于(1)式中的x不是线性函数,(1)~(8)给出的是 一个非线性规划。而且,对于这样用分段函数定义的以(x), 般的非线性规划软件也难以输入和求解。能不能想办法 将该模型化简,从而用现成的软件求解呢?

优化建模 约束条件包括加工两种汽油用的原油A、原油B库存量的限制， 和原油A购买量的限制，以及两种汽油含原油A的比例限制， 它们表示为 x + x  500 + x 11 12 （3） x21 + x22 1000 （4） x 1500 （5） 0.5 11 21 11  x + x x （6） 0.6 12 22 12  x + x x （7） x11, x12 , x21, x22 , x  0 （8） 由于（1）式中的c(x)不是线性函数，（1）~（8）给出的是 一个非线性规划。而且，对于这样用分段函数定义的c(x)， 一般的非线性规划软件也难以输入和求解。能不能想办法 将该模型化简，从而用现成的软件求解呢？

优化建檩 §5.1.3求解模型3种解法 第1种解法将原油A的采购量x分解为三个量,即用x1 x2,x3分别表示以价格10、8、6千元吨购的原油A的吨 数,总支出为c(x)=10x1+8x2+6x3,且 x=x1+x2+x3(9) 这时目标函数(2)变为线性函数: Max=48(x1+x2)+56(x2+x2)-(10x+8x2+6x)(10) 应该注意到,只有当以10千元吨的价格购买 1=500(吨)时,才能以8千元/吨的价格购买x2 (>0),这个条件可以表示为 (x1-500x2=0(1)

优化建模 §5.1.3 求解模型 3种解法 第1种解法 将原油A的采购量x分解为三个量，即用x1， x2，x3分别表示以价格10、8、6千元/吨采购的原油A的吨 数，总支出为c(x) = 10x1+8x2+6x3，且 1 2 3 x = x + x + x (9) 这时目标函数（2）变为线性函数： 4.8( ) 5.6( ) (10 8 6 ) 11 21 12 22 1 2 3 Max z = x + x + x + x − x + x + x (10) 应该注意到，只有当以10千元/吨的价格购买 x1=500（吨）时，才能以8千元/吨的价格购买x2 （>0），这个条件可以表示为 (x1 −500)x2 = 0 (11)

优化建祺 同理,只有当以8千元/吨的价格购买x2=500(吨)时, 才能以6千元/吨的价格购买x3(>0),于是 (x2-500)x3=0 (12) 此外,x1,x2,x的取值范围是 0≤x1,x2,x2≤500 (13)

优化建模 同理，只有当以8千元/吨的价格购买x2 =500（吨）时， 才能以6千元/吨的价格购买x3（>0），于是 (x2 − 500)x3 = 0 (12) 此外，x 1，x2，x3的取值范围是 0  x1 , x2 , x3  500 (13)

优化建郡 由于有非线性约束(11),(12),(3)~(13)构成非线性 规划模型。LING0程序: Model Max=48*x11+48*x21+5.6*x12+56*x22-10*x1-8*x2-6*x3; xll+x120; 0.4*x12-0.6*x22>0 Xx1+x2+x3; (X1-500)*x2=0 (x2-500)*x3=0 abnd(0,x1,500) abnd(0,x2,500) abnd(,X3,500) end

优化建模 由于有非线性约束(11),(12)，(3)~(13)构成非线性 规划模型。LINGO程序： Model: Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3; x11+x12 0; 0.4*x12 - 0.6*x22 > 0; x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; @bnd(0,x1, 500); @bnd(0,x2, 500); @bnd(0,x3,500); end