第十章非线性规划 §101问题提出—公交公司的营运策略 个大型的公交公司: (1)年预算2亿元 (2)营业额与全部营运车辆的总里程M成正比, 总里程M与车辆数B、员工总人数W、撚油总量F 的关系(统计分析而得的经验公式)是 M=15.7.B0W032F056 (其中,M单位千公里;F单位立方米); (3)初始:B=700,W=2200 (4)各项费用:购新车21万元每辆,卖车得75 万元每辆,维护费08万元每辆,雇佣新员工08万元 每个,解雇旧员工0.6万元每个,年薪3万元每个员 工,油价0.3万元每立方米; (5)每辆车:至少配备3个员工,至多燃50立方 米油。 请提供营运策略,使营业额最大 §10-2问题分析与模型建立 这是优化问题,优化问题的三个要素是决策变量、约束 条件和目标函数。 决策变量:购买车数x;出售车数x,;新雇员工 数x3;解雇员工数x;每车年燃油量x 约束条件:年预算约束;车数与员工数:每车的 最大燃油量:非负性。 目标函数:总里程M的最大化 根据题给数据,建立如下优化模型: maxM=15.7·(700+x1-x2)(2200+x3-x2)32 (700+x1-x2)x)36, S1.21.8x1-8.3x2+38x3-24x4+210x5+ 0.3(x1-x2)x5≤12840 3x1-3x2-x3+x4≤100 x≥0(=1,234,5),x5≤50 (注意到,在目标函数、约束条件的表达式中,决策变 量不是以线性形式出现的) §103数学知识:非线性规划 1.无约束优化问题 mnf(x),其中向量x的n个分量x都是决策变量,称 f(x)目标函数。 用 Matlab求解:先建立函数文件 mbhs. m,内容
第十章 非线性规划 §10—1 问题提出----公交公司的营运策略 一个大型的公交公司： （1）年预算 2 亿元； （2）营业额与全部营运车辆的总里程 M 成正比， 总里程 M 与车辆数 B、员工总人数 W、燃油总量 F 的关系（统计分析而得的经验公式）是 0.06 0.32 0.56 M =15.7 B W F ， （其中，M 单位千公里；F 单位立方米）； （3）初始：B=700，W=2200 ； （4）各项费用：购新车 21 万元每辆，卖车得 7.5 万元每辆，维护费 0.8 万元每辆，雇佣新员工 0.8 万元 每个，解雇旧员工 0.6 万元每个，年薪 3 万元每个员 工，油价 0.3 万元每立方米； （5）每辆车：至少配备 3 个员工，至多燃 50 立方 米油。 请提供营运策略，使营业额最大。 §10—2 问题分析与模型建立 这是优化问题，优化问题的三个要素是决策变量、约束 条件和目标函数。 决策变量：购买车数 1 x ；出售车数 2 x ；新雇员工 数 3 x ；解雇员工数 4 x ；每车年燃油量 5 x 。 约束条件：年预算约束；车数与员工数；每车的 最大燃油量；非负性。 目标函数：总里程 M 的最大化。 根据题给数据，建立如下优化模型： 0( 1,2,3,4,5), 50 . 3 3 100, 0.3( ) 12840, . . 21.8 8.3 3.8 2.4 210 ((700 ) ) , max 15.7 (700 ) (2200 ) 5 1 2 3 4 1 2 5 1 2 3 4 5 0.56 1 2 5 0.32 3 4 0.06 1 2 = − − + − − + − + + + − = + − + − x i x x x x x x x x st x x x x x x x x M x x x x i （注意到，在目标函数、约束条件的表达式中，决策变 量不是以线性形式出现的） §10—3 数学知识：非线性规划 1．无约束优化问题 min f (x) n xR ，其中向量 x 的 n 个分量 i x 都是决策变量，称 f (x) 目标函数。 用 Matlab 求解：先建立函数文件 mbhs.m，内容
是f(x)的表达式;再回到 Matlab命令区,输入决策变 量初值数据x0,执行命令 Ix, fmin]=fminunc(@mbhs, xO) 如:mn(2x2+3x2)的最优解是x=(0) 用 Matlab计算,函数文件为 function f-mbhs(> f=2*x(1)2+3*x(2)2 再输入初值x0=[1l并执行上述命令,结果输出为 10e008 0.1253 0.3817 fmin= 4.6849e-017 2.约束优化问题 min f(x) s1.g;(x)≤0,(=12,…,p) h,(x)=0,(=1,2,…,m L≤x≤U 其中:向量x的n个分量x都是决策变量,称f(x)目标函数、 g(x)等式约束函数、h(x)不等式约束函数、L下界、U上 用 Matlab求解:先把模型写成适用于 Matlab的 标准形式 min f(x) L.Ax≤b, g(x)≤0, h(x)=0, L≤x<U 约束条件中:把线性的式子提炼出来得前两个式子;后三个 式子都是列向量。 (n: A,x6,b,, Aeq=0, beg=l g(x) 再建立两个函数文件:目标函数 mbhs m;约束函数 shs. m 再回到 Matlab命令区,输入各项数据及决策变量初值 数据x0,执行命令 [x, fmin]=fmincon(@mbhs, x0, A, b, Aeq, beq, L, U, @yshs) 例:单位球x2+y2+2≤1内, 曲面z=x2+y2-05-0.1xy的上方
是 f (x) 的表达式；再回到 Matlab 命令区，输入决策变 量初值数据 x0，执行命令 [x,fmin]=fminunc(@mbhs,x0) 如：min (2 3 ) 2 2 2 1 2 x x x R + 的最优解是 (0,0) . T x = 用 Matlab 计算，函数文件为 function f=mbhs(x) f=2*x(1)^2+3*x(2)^2; 再输入初值 x0=[1;1]; 并执行上述命令，结果输出为 x = 1.0e-008 * 0.1253 0.3817 fmin = 4.6849e-017 2．约束优化问题 . ( ) 0, ( 1,2,..., ), . . ( ) 0, ( 1,2,..., ), min ( ) L x U h x i m st g x i p f x i i x R n = = = 其中：向量 x 的 n 个分量 i x 都是决策变量，称 f (x) 目标函数、 g (x) i 等式约束函数、 h (x) i 不等式约束函数、L 下界、U 上 界。 用 Matlab 求解：先把模型写成适用于 Matlab 的 标准形式 . ( ) 0, ( ) 0, , . . , min ( ) L x U h x g x Aeq x beq st Ax b f x n x R = = 约束条件中：把线性的式子提炼出来得前两个式子；后三个 式子都是列向量。 （如： = = = ( ) ( ) , , [], [], ( ) 1 2 6 2 1 g x g x A b Aeq beq g x p ） 再建立两个函数文件：目标函数 mbhs.m；约束函数 yshs.m 再回到 Matlab 命令区，输入各项数据及决策变量初值 数据 x0，执行命令 [x,fmin]=fmincon(@mbhs,x0,A,b,Aeq,beq,L,U,@yshs) 例：单位球 1 2 2 2 x + y + z 内， 曲面 z x y 0.5 0.1xy 2 2 = + − − 的上方
平面x+y+z-008=0之中(不是上面), 满足上述三个条件的区域记为D,求函数 在D上的最大值、最大值点。 解: (1)目标函数 mbhs. m function f=mbhs(x) f=exp(x(1)*x(2)*x(3)sinx(1)+x(2)X(3)-exp(-X(1)*x( 2)°cos(x(3)^2-1); (2)约束函数 shs. m function [g, h]=shs(x) g=x(1)2+x(2)2+x(3)2-1x(1)2+x(2)20.5-0.1*x(1) x(2)}x(3 h=[ (3)数据准备 x0=[0.00.020.02]A=[b=Aeq=[,,1]beq=008, =-1;-1;-1]U=[1;1;1; (4)执行命令 [x, fmin]=fmincon(@mbhs, xO, A, b, Aeq, beq, L, U, @yshs) (5)结果 X=0.2367 0.2368 -0.3935 fmin=-1.3732 答:最大值点(02367,0.2368-03935),最大值13732 §104模型求解 maxM=157(700+x1-x2)(2200+x3-x) (700+x-x2)x5)6 S.21.8x1-83x2+3.8x3-24x4+2l0x5+ 0.3(x1-x2)x5≤12840 +x1≤100 x1≥0(=1,2,34,5),x5≤ (1)目标函数 mbhs. m function f=mbhs(x) f=157*(700+x(1)X(2)^0.06°(2200+ x(3)}x(4)0.32*(700+x(1)-x(2)*x(5)^0.56; (2)约束函数 shs. m function g, h]Fyshs(x) g=21.8*x(1)-8.3*x(2)+3.8*x(3)-24*x(4)+210*x(5)+0.3* (x(1)x(2)*x(512840; (3)数据准备 x0=[000025]A=[3,-3,-1,1,O]b=100Aeq=ubeq=[ L=[0; 0; 0; 0; 0]: U=[Inf; Inf; Inf; Inf, 50] (4)执行命令 [x, fmin=fmincon(@mbhs, XO, A, b, Aeq, beq, L, U, @yshs) (5)结果
平面 x + y + z − 0.08 = 0 之中（不是上面）， 满足上述三个条件的区域记为 D，求函数 sin( ) cos( 1) 2 + − + − − e x y z e z xyz xy 在 D 上的最大值、最大值点。 解： （1）目标函数 mbhs.m function f=mbhs(x) f=-exp(x(1)*x(2)*x(3))*sin(x(1)+x(2)-x(3))-exp(-x(1)*x( 2))*cos(x(3)^2-1); （2）约束函数 yshs.m function [g,h]=yshs(x) g=[x(1)^2+x(2)^2+x(3)^2-1;x(1)^2+x(2)^2-0.5-0.1*x(1) *x(2)-x(3)]; h=[]; （3）数据准备 x0=[0.0;0.02;0.02];A=[];b=[];Aeq=[1,1,1];beq=0.08; L=[-1;-1;-1];U=[1;1;1]; （4）执行命令 [x,fmin]=fmincon(@mbhs,x0,A,b,Aeq,beq,L,U,@yshs) （5）结果 x = 0.2367 0.2368 -0.3935 fmin = -1.3732 答：最大值点(0.2367,0.2368,-0.3935)，最大值 1.3732 §10—4 模型求解 0( 1,2,3,4,5), 50 . 3 3 100, 0.3( ) 12840, . . 21.8 8.3 3.8 2.4 210 ((700 ) ) , max 15.7 (700 ) (2200 ) 5 1 2 3 4 1 2 5 1 2 3 4 5 0.56 1 2 5 0.32 3 4 0.06 1 2 = − − + − − + − + + + − = + − + − x i x x x x x x x x st x x x x x x x x M x x x x i （1）目标函数 mbhs.m function f=mbhs(x) f=-15.7*(700+x(1)-x(2))^0.06*(2200+ x(3)-x(4))^0.32*((700+x(1)-x(2))*x(5))^0.56; （2）约束函数 yshs.m function [g,h]=yshs(x) g=21.8*x(1)-8.3*x(2)+3.8*x(3)-2.4*x(4)+210*x(5)+0.3* (x(1)-x(2))*x(5)-12840; h=[]; （3）数据准备 x0=[0;0;0;0;25];A=[3,-3,-1,1,0];b=100;Aeq=[];beq=[]; L=[0;0;0;0;0];U=[Inf; Inf; Inf; Inf;50]; （4）执行命令 [x,fmin]=fmincon(@mbhs,x0,A,b,Aeq,beq,L,U,@yshs) （5）结果 x =
-0.0000 615.7895 50.0000 min 10355e+005 生产与销售计划问题 某公司用两种原油(A和B)混合加工成两种汽油(甲和 乙)。甲、乙两种汽油含原油A的最低比例分别为50%和60% 每吨售价分别为4800元和5600元。该公司现有原油A和B 的库存量分别为500吨和1000吨,还可以从市场上买到不超 过1500吨的原油A.原油A的市场价为:购买量不超过500 吨时的单价为10000元/吨;购买量超过500吨但不超过1000 吨时,超过500吨的部分单价为8000元/吨;购买量超过1000 吨时,超过1000吨的部分单价为6000元/吨。该公司应怎样 安排原油的采购和加工? 问题分析 安排原油采购、加工的目的是:利润最大 题中给出的是:甲乙两种汽油的售价,原油A的进价 利润=“销售汽油的收入”一“购进原油A的支出 难点:原油A的采购价与购买量的关系复杂,是分段 函数关系。能否用、如何用线性规划、整数规划模型加以 处理? 模型建立 以下约定:货币单位是“千元”:价格单位是“千元/吨”。 设原油A的购买量为x,采购支出记为c(x),则有如下 的分段线性函数: 0≤x≤500 c(x)={1000+8x,500 3000+6x,1000<x≤1500 设原油A用于生产甲、乙两种汽油的数量分别为x,x2 原油B用于生产甲、乙两种汽油的数量分别为x3,x4, 则总的销售收入为48(x1+x3)+56(x2+x4), 优化目标函数(利润)为 maxz=48(x1+x3)+56(x2+x4)-c(x) 约束条件: 原油A的数量 x1+x2≤500+x 原油B的数量 x2+x4≤1000 原油A的采购量 x≤1500
0 -0.0000 615.7895 0 50.0000 fmin = -1.0355e+005 生产与销售计划问题 某公司用两种原油(A 和 B)混合加工成两种汽油(甲和 乙)。甲、乙两种汽油含原油 A 的最低比例分别为 50%和 60%， 每吨售价分别为 4800 元和 5600 元。该公司现有原油 A 和 B 的库存量分别为 500 吨和 1000 吨，还可以从市场上买到不超 过 1500 吨的原油 A. 原油 A 的市场价为：购买量不超过 500 吨时的单价为 10000 元/吨；购买量超过 500 吨但不超过 1000 吨时，超过 500 吨的部分单价为 8000 元/吨；购买量超过 1000 吨时，超过 1000 吨的部分单价为 6000 元/吨。该公司应怎样 安排原油的采购和加工？ 问题分析 安排原油采购、加工的目的是：利润最大 题中给出的是：甲乙两种汽油的售价，原油 A 的进价. 利润==“销售汽油的收入”—“购进原油 A 的支出” 难点：原油 A 的采购价与购买量的关系复杂，是分段 函数关系。能否用、如何用线性规划、整数规划模型加以 处理？ 模型建立 以下约定：货币单位是“千元”；价格单位是“千元/吨”。 设原油 A 的购买量为 x ，采购支出记为 c(x) ，则有如下 的分段线性函数： + = + 1000 1500. 500 1000, 0 500, 3000 6 , 1000 8 , 10 , ( ) x x x x x x c x 设 原油 A 用于生产甲、乙两种汽油的数量分别为 1 2 x , x ， 原油 B 用于生产甲、乙两种汽油的数量分别为 3 4 x , x ， 则 总的销售收入为 4.8( ) 5.6( ) 1 3 2 4 x + x + x + x ， 优化目标函数（利润）为 max 4.8( ) 5.6( ) ( ) 1 3 2 4 z = x + x + x + x −c x . 约束条件： 原油 A 的数量 x + x 500+ x 1 2 ； 原油 B 的数量 x3 + x4 1000 ； 原油 A 的采购量 x 1500；
原油A在汽油甲中的比例 ≥50% 原油A在汽油乙中的比例 ≥60 非负性 ≥0 模型求解 1.目标函数中,分段函数c(x)必须处理掉:记 x=x +x+x 其中x5x6,x分别是以价格10、8、6购进的原油A的量,则 模型中的目标函数变成线性函数 maxz=4.8(x1+x3)+56(x2+x4)-(10x5+8x6+6x) 2.那么,x53x6,x应该满足什么样的约束条件呢? 显然有0≤x5,x,x≤500; 只有以价格10购买了500吨之后,才有资格以价格8购 买,即只有当x5=500时才有x6>0,该约束条件可用如 下式子代表 500 同理,只有以价格8购买了500吨之后,才有资格以价 格6购买,得 (500-x6)x7=0 3.得到如下“非线性规划”模型 48(x1+x3)+56(x2+x4)-(10x5+8x6+6x7) s.x1+x2≤500+x5+x6+x x3+x4≤1000 3x4≥0 (500-x5)x6=0 (500-x6)x7=0 < < 用 LINGO软件编程计算,得最优解 (x1x2,x3,x4,x5,x6,x)=(0.1500,0,1000.500,5000) max ==5000 谷:采购1000吨原油A,不生产汽油甲,用全部的1500 吨原油A、1000吨原油B投入生产汽油乙:此时,利润达到 最大值5000千元
原油 A 在汽油甲中的比例 50% 1 3 1 x + x x ； 原油 A 在汽油乙中的比例 60% 2 4 2 x + x x ； 非负性 x1 , x2 , x3 , x4 , x 0 . 模型求解 1．目标函数中，分段函数 c(x) 必须处理掉：记 5 6 7 x = x + x + x ， 其中 5 6 7 x , x , x 分别是以价格 10、8、6 购进的原油 A 的量，则 模型中的目标函数变成线性函数 max 4.8( ) 5.6( ) (10 8 6 ) 1 3 2 4 5 6 7 z = x + x + x + x − x + x + x . 2．那么， 5 6 7 x , x , x 应该满足什么样的约束条件呢？ 显然有 0 x5 , x6 , x7 500 ； 只有以价格 10 购买了 500 吨之后，才有资格以价格 8 购 买，即只有当 x5 = 500 时才有 x6 0 ，该约束条件可用如 下式子代表 (500− x5 )x6 = 0 ； 同理，只有以价格 8 购买了 500 吨之后，才有资格以价 格 6 购买，得 (500 − x6 )x7 = 0 . 3．得到如下“非线性规划”模型 , , , 0, 0 , , 500 . (500 ) 0 (500 ) 0 2 3 0 0 1000 . . 500 max 4.8( ) 5.6( ) (10 8 6 ) 1 2 3 4 5 6 7 6 7 5 6 2 4 1 3 3 4 1 2 5 6 7 1 3 2 4 5 6 7 − = − = − − + + + + + = + + + − + + x x x x x x x x x x x x x x x x x st x x x x x z x x x x x x x 用 LINGO 软件编程计算，得最优解 max 5000 . ( , , , , , , ) (0,1500,0,1000,500,500,0) 1 2 3 4 5 6 7 = = z x x x x x x x 答：采购 1000 吨原油 A，不生产汽油甲，用全部的 1500 吨原油 A、1000 吨原油 B 投入生产汽油乙；此时，利润达到 最大值 5000 千元