第六讲 线性规划与非线性规划[讲课适用]

1、第六讲 线性规划与 非线性规划 1优选课堂 线性规划与非线性规划 v最优化是人们在工程技术、科学研究和经济管理等领域常 见的问题。要表述一个最优化问题，一般需要确定三个要 素：一是决策变量，通常是要求解的未知量 ；二是目标 函数，通常是要优化(最小或最大)的那个目标的数学表达 式，是决策变量的函数 ；三是约束条件，对决策变量 的限制条件，即 允许取值的范围，称为可行域。 v一般地，优化模型可表述为 v只满足(2)的解 称为可行解，同满足(1)(2)的解 称最 优解。 x x ( )f x min( )(1) . .( )0,1,2,(2) x i zf x stg xim x * xx 2优选

2、课堂 v优化模型的分类 数学规划 线性规划(LP) 二次规划(QP) 非线性规划(NLP) 0-1整数规划 一般整数规划 纯整数规划(PIP) 混合整数规划(MIP) 整数规划(IP) 连续规划 3优选课堂 一、线性规划 1、引例 v问题一：任务分配问题：某车间有甲、乙两台机床，可用 于加工三种工件.假定这两台车床的可用台时数分别为800 和900，三种工件的数量分别为400、600和500，且已知用 三种不同车床加工单位数量不同工件所需的台时数和加工 费用如下表.问怎样分配车床的加工任务，才能既满足加工 工件的要求，又使加工费用最低？ 单位工件所需加工台时数 单位工件的加工费用 车床 类 型

3、 工件 1 工件 2 工件 3 工件 1 工件 2 工件 3 可用台 时数 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 4优选课堂 v模型 设在甲车床上加工工件1、2、3的数量分别为 在乙车床上加工工件1、2、3的数量分别为 123 ,x x x 456 ,.x x x 123456 14 25 36 123 456 min1391011128 . .400 600 500 0.41.1800 0.51.21.3900 0,1,2,6 i zxxxxxx stxx xx xx xxx xxx xi 5优选课堂 v问题二：某厂每日8小时

4、的产量不低于1800件.为了进行质 量控制，计划聘请两种不同水平的检验员.一级检验员的标 准为：速度25件/小时，正确率98%，计时工资4元/小时； 二级检验员的标准为：速度15件/小时，正确率95%，计时 工资3元/小时.检验员每错检一次，工厂要损失2元.为使总 检验费用最省，该工厂应聘一级、二级检验员各几名？ v模型 设需要一级、二级检验员的人数分别为 人， 应付检验员工资为 因检验员错检而造成的损失为 12 ,x x 1212 8 48 33224,xxxx 1212 (8 25 2%8 15 5%) 2812xxxx 121212 1212 11 22 1212 min(3224)(8

5、12)4036 . .8 258 1518005345 8 2518009 8 15180015 0,00,0 zxxxxxx stxxxx xx xx xxxx 6优选课堂 2、线性规划模型的标准形式 v 或矩阵形式 v其中 是决策变量， 是约束 矩阵， ， 3、线性规划模型的实用形式 (1) (2) 1 1 min . .,1,2, 0,1,2, n ii i n ikki k i zc x sta xb in xin min . . 0 T zc x stAxb x 12 ()T n xx xx 1 2 () . T n cc cc ij m n Aamn 1 2 ()T m bbbb

6、11 22 12 min . . T zc x stAxb A xb vxv 11 223 12 min . . T zc x stAxb bA xb vxv 注；当前 MATLAB只 支持第一种 形式。 7优选课堂 4、用MATLAB优化工具箱解线性规划 (1) 模型1： v命令：x=linprog(c,A,b) (2) 模型2： v命令： x=linprog(c,A1,b1,A2,b2) v注：1若没有不等式 存在，则令 2 输出的x为最优解。 min . . T zc x stAxb 11 22 min . . T zc x stAxb A xb 11 Axb 11 ,.Ab 8优选课堂

7、 (3) 模型3： v命令： 1 x=linprog(c,A1,b1,A2,b2,v1,v2) 2 x=linprog(c,A1,b1,A2,b2,v1,v2,x0) v注：1 若没有等式约束： ，令 2 x0表示初始解。 (4) 命令： x,fval,ef,out,lambda=linprog(c,A1,b1,A2,b2,v1,v2,x0) 输出x为最优解，fval为最优值，ef为程序停止的标志，out 为个结构变量，包括程序运行的有关信息，lambda也是结 构变量，对应于相应的约束的Lagrange乘子。 11 22 12 min . . T zc x stAxb A xb vxv 22

8、 ,.Ab 22 A xb 9优选课堂 v例1： 123456 123456 14 25 36 max0.40.280.320.720.640.6 . .0.010.010.010.030.030.03850 0.020.05700 0.020.05100 0.030.08900 0,1,2,6 j zxxxxxx stxxxxxx xx xx xx xj 见MATLAB程序 （xianxingguihua1） 10优选课堂 v例2： 1 1232 3 1 2 123 3 1 2 1 3 2 3 min634min(634) 111120 . . .120 01050 30 05030 200

9、 20 x zxxxzx x x stxstxxx xx xx xx x 见MATLAB程序 （xianxingguihua2） 11优选课堂 v例3：问题一的解答 v改写为 1 2 3 4 5 6 min(1391011 128) 0.41.11000800 . . 0000.51.21.3900 100100400 010010600 ,0 001001500 zx stx x x x xx x x x 见MATLAB程序 （xianxingguihua3） 12优选课堂 v结果： 即在甲机床上加工600个工件2,在乙机床上加工400 个工件1、500个工件3，可在满足条件的情况下使 总加

10、工费最小为13800. 13优选课堂 v例4：问题二的解答 v改写为 1 2 1 2 11 22 min(4036) . .5345 109 ,0 0115 x z x x st x xx xx 见MATLAB程序 （xianxingguihua4） 14优选课堂 v结果： v即只需聘用9个一级检验员。 v注：本问题应还有一个约束条件：x1、x2取整数， 故它属于一个整数线性规划问题，这里当成一个线 性规划求解，求得最优解刚好是整数x1=9，x2=0， 故它就是该整数规划的最优解.若用线性规划解法求 得的最优解不是整数，将其取整后不一定是相应整 数规划的最优解，这样的整数规划应用专门的方法 求

11、解. 15优选课堂 二、非线性规划 1、二次规划 v标准形式： vMATLAB调用格式： (1) x=quadprog(H,C,A1,b1); (2)x=quadprog(H,C,A1,b1,A2,b2,v1,v2); (3)x,fval,exitflag,output= quadprog(H,C,A1,b1, A2,b2 ,v1,v2,x0,options); 11 22 12 1 min 2 . . TT zx Hxc x stA xb A xb vxv 16优选课堂 v例1： v改写成标准形式： 22 12112212 12 12 12 12 min( ,)2333 . .23 23 3

12、4 2,0 f x xxx xxxx stxx xx xx xx 11 12 22 1 2 1 2 1 2 433 1 min() 3612 213 . . 134 123 2 0 T xx zxx xx x st x x x x x 17优选课堂 v编程(见MATLAB程序(erciguihua1) v结果： 18优选课堂 2、一般非线性规划 v标准形式： v其中 为n维变元向量， 均为非线性函数组 成的向量，其他变量的含义与线性规划、二次规划 中相同 v用MATLAB求解上述问题，基本步骤分三步。 1 2 11 22 12 min( ) . .0 0 zf x stcx cx Axb A

13、xb vxv 12 ( ),c x cxx 19优选课堂 (1)首先建立M文件fun.m,用来定义目标函数f(x)，形 式为 function f=fun(x) f=f(x); (2)若有非线性约束条件： 或 则建立M 文件c.m定义函数 一般形式为 function c1,c2=c(x) c1= c2= (3)建立主程序。求解非线性规划的函数是fmincon, 调用格式为 x=fmincon(fun,x0,A1,b1); x,fv,ef,out,lag,grad,hess=fmincon(fun,x0,A1,b1,A2, b2,v1,v2,c,opt,P1,P2,) 1 0cx 2 0,cx

14、 12 ,cxcx 20优选课堂 v注意： (1) fmincon函数提供了大型优化算法和中型优化算 法。当options参数的GradObj设置为on时必须 给出fun函数的梯度，并且只有上下界约束或只有 等式约束，fmincon函数将选择大型算法。当既有 等式约束又有梯度约束时，使用中型算法。 (2) fmincon函数的中型算法使用的是序列二次规划 法(SQP方法)。在每一步迭代中求解二次规划子问 题，并用BFGS法更新拉格朗日Hesse矩阵。 (3)fmincon函数可能会给出局部最优解，这与初值 x0的选取有关。 21优选课堂 v例2： v改写成标准形式： v建立M文件fun1.m

15、22 1212 12 12 12 11 min2 22 . .236 45 ,0 zxxxx stx xx x x 22 1212 12 12 1 2 11 min2 22 2360 . . 450 0 0 zxxxx xx st xx x x 22优选课堂 v建立主程序(见MATLAB程序(feixianxingguihua1) v结果： 23优选课堂 v例3： v建立M文件fun2.m定义目标函数： v建立M文件c.m定义非线性约束条件： 1 22 12122 12 1212 12 min42421 . .0 1.50 100 x zexxx xx stxx x xxx x x 24优选课

16、堂 v编写主程序(见MATLBA程序(feixianxingguihua2) v结果： 25优选课堂 v例4： v建立M文件fun3.m定义目标函数： v建立M文件c1.m定义非线性约束条件： 12 22 112 22 212 12 min2 . .( )250 70 05,010 zxx stc xxx cxxx xx 26优选课堂 v编写主程序(见MATLBA程序(feixianxingguihua3) v结果： 27优选课堂 补充知识：用LINDO、LINGO优化工具箱 解线性规划 vLINDO、LINGO能求解的优化模型 优化模型 连续优化整数规划(IP) 二次规划 (QP) 非线性规

17、划 (NLP) 线性规划 (LP) LINDO LINGO 28优选课堂 一、LINDO软件包 v引例：加工奶制品的生产计划 v每天：50桶牛奶，时间：480小时，至多加工100 千克 ，制定生产计划，使每天获利最大。 v35元可买到1桶牛奶，买吗？若买，每天最多买多 少？ v可聘用临时工人，付出的工资最多是每小时几元? v 获利增加到 30元/千克，是否应改变生产计划？ 一桶 牛奶 3千克A1 4千克A2 获利24元/千克 获利16元/千克 12小时 8小时 或 1 A 1 A 29优选课堂 v建立模型 桶牛奶生产 桶牛奶生产 获利 获利 50 21 xx 480812 21 xx 1003

18、 1 x 决策变量决策变量 目标函数目标函数 12 max7264zxx 约束条件约束条件 0, 21 xx 线性线性 规划规划 模型模型 (LP) 1 x 1 A2 x 2 A 每天获利 原料供应 劳动时间 加工能力 非负约束 1 24 3x 2 16 4x 30优选课堂 v模型求解： 1 A 2 A 20桶牛奶生产 ， 30桶牛奶生产 ， 利润为3360元。 原料无剩余 时间无剩余 加工能力剩余40 三三 种种 资资 源源 31优选课堂 基变量的reduced cost值为0；对于非基 变量， reduced cost值 表示该非基变量增加 一个单位时（其他非 基变量保持不变）， 目标函数

19、减少量（对 max型问题）。 影子价格 原料增1单位，利润增48 时间增1单位，利润增2 能力增减不影响利润 35元可买到1桶牛奶，要买吗？ 35 ”（或“=”（或“=”）功能相同。 v变量与系数间可有空格(甚至回车), 但无运算符。 v变量名以字母开头，不能超过8个字符。 v变量名不区分大小写(包括LINDO中的关键字)。 v目标函数所在行是第一行，第二行起为约束条件。 v行号(行名)自动产生或人为定义.行名以“）”结束。 v行中注有“!”符号的后面部分为注释。 如： ! Its Comment。 v在模型的任何地方都可以用“TITLE” 对模型命名(最多72 个字符)，如： TITLE This Model is only an Example。 35优选课堂 v变量与系数间可有空格，但不能有任何运算符号(如乘号 *)。 v变量不能出现在一个约束条件的右端。 v表达式中不接受括号“( )”和逗号“,”等任何符号, 例: