数学规划模型实验

1、1/22数学规划模型实验数学规划模型实验 数学教研组数学教研组 卢鹏卢鹏 2015.7.23 2/22优化问题及其一般模型： 引引 言言 优化问题是人们在工程技术、经济管理和科学研究等领域中最常遇到的问题之一。例如：l 设计师要在满足强度要求等条件下选择材料的尺寸， 使 结构总重量最轻；l 公司经理要根据生产成本和市场需求确定产品价格，使所获 利润最高；l 调度人员要在满足物质需求和装载条件下安排从各供应点 到需求点的运量和路线，使运输总费用最低；l 投资者要选择一些股票,债券下注,使收益最大,而风险最小l 3/22一般地，优化模型可以表述下： min( ). .( )01 2izf xs t

2、g xim , , = = , , , , , 这是一个多元函数的条件极值问题，其中这是一个多元函数的条件极值问题，其中 . 许多实际问题归结出的这种优化模型，若决策变量个数许多实际问题归结出的这种优化模型，若决策变量个数较少可用较少可用微分法微分法求解求解; ;但是其决策变量个数但是其决策变量个数 n n 和约束条件个和约束条件个数数 m m 较大，并且最优解往往在可行域的边界上取得，较大，并且最优解往往在可行域的边界上取得，数学规数学规划划就是解决这类问题的有效方法。就是解决这类问题的有效方法。 12,nxxxx 4/22数学规划模型分类数学规划模型分类： “数学规划是运筹学和管理科学中应

3、用及其数学规划是运筹学和管理科学中应用及其广泛的分支。数学规划包括广泛的分支。数学规划包括线性规划线性规划、非线性规非线性规划划、整数规划整数规划、几何规划、多目标规划等，用数、几何规划、多目标规划等，用数学规划方法解决实际问题，就要将实际问题经过学规划方法解决实际问题，就要将实际问题经过抽象、简化、假设，确定变量与参数，建立适当抽象、简化、假设，确定变量与参数，建立适当层次上的数学模型，并求解。层次上的数学模型，并求解。 5/22建立数学规划模型的步骤建立数学规划模型的步骤: :Step 1. Step 1. 寻求决策，即回答什么？必须清楚，无歧义。寻求决策，即回答什么？必须清楚，无歧义。

4、阅读完题目的第一步不是寻找答案或者解法，而是阅读完题目的第一步不是寻找答案或者解法，而是Step 2. Step 2. 确定决策变量确定决策变量 第一来源：第一来源：Step 1Step 1的结果，用变量固定需要回答的决策的结果，用变量固定需要回答的决策 第二来源：由决策导出的变量（具有派生结构）第二来源：由决策导出的变量（具有派生结构） 其它来源：辅助变量（联合完成更清楚的回答）其它来源：辅助变量（联合完成更清楚的回答）Step 3. Step 3. 确定优化目标确定优化目标 用决策变量表示的利润、成本等。用决策变量表示的利润、成本等。Step 4. Step 4. 寻找约束条件寻找约束条件

5、 决策变量之间、决策变量与常量之间的联系。决策变量之间、决策变量与常量之间的联系。 第一来源：需求；第一来源：需求； 第二来源：供给；第二来源：供给； 其它来源：辅助以及常识。其它来源：辅助以及常识。Step 5. Step 5. 构成数学模型构成数学模型 将目标以及约束放在一起，写成数学表达式。将目标以及约束放在一起，写成数学表达式。 6/22目目 录录 线性规划线性规划非线性规划非线性规划二次规划二次规划整数规划整数规划7/22例例1：加工奶制品的生产计划：加工奶制品的生产计划 一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产A1，A2两种奶制两种奶制品，一桶牛奶可以在设备甲上用品，一桶牛

6、奶可以在设备甲上用12小时加工成小时加工成3公公斤斤A1，或者在设备乙上用，或者在设备乙上用8小时加工成小时加工成4公斤公斤A2。根。根据市场需求，生产的据市场需求，生产的A1、A2全部能够售出，且每公全部能够售出，且每公斤斤A1获利获利24元，每公斤元，每公斤A2获利获利16元。现在加工厂每元。现在加工厂每天能够得到天能够得到50桶牛奶的供应，每天正式工人总的劳桶牛奶的供应，每天正式工人总的劳动时间为动时间为480小时，并且设备甲每天至多能加工小时，并且设备甲每天至多能加工100公斤公斤A1，设备乙的加工能力没有限制。试为该厂制，设备乙的加工能力没有限制。试为该厂制定一个生产计划，使每天获利

7、最大定一个生产计划，使每天获利最大?8/22每每天天5050桶牛奶桶牛奶 时间时间480480小时小时 至多加工至多加工100100公斤公斤A A1 1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 1 1桶桶牛奶牛奶 3 3公斤公斤A A1 1 1212小时小时 8 8小时小时 4 4公斤公斤A A2 2 或或获利获利2424元元/ /公斤公斤 获利获利1616元元/ /公斤公斤 问问 题题 分分 析析9/22引入决策变量引入决策变量 x1 桶牛奶生产桶牛奶生产A1 ，x2桶牛奶生产桶牛奶生产A2（每天）（每天）目标函数（每天获利）目标函数（每天获利） 生产生产A1获利：获利：

8、243x1 生产生产A2获利：获利： 164x2 每天获利总额：每天获利总额：z=72x1+64x2 约束条件约束条件 原料供应：原料供应： x1+x250 劳动时间：劳动时间： 12x1+8x2480 加工能力：加工能力： 3x1100 非负约束：非负约束： x1 , x2 0模型构成：模型构成：10/22线性规划数学模型：线性规划数学模型：121212112max726450128480. .31000,0fxxxxxxs txxx 11/22线性规划求解线性规划求解标准形式：标准形式： min . . , , .Tfcxs tA xbAeq xbeqlbxub其中：其中： , , ,c

9、x b beq lb ub均为列向量，均为列向量， ,A Aeq为矩阵。为矩阵。 调用格式：调用格式：x,fval=linprog(c,A,b,Aeq,beq,lb,ub,options) 其中：其中：x给出极小点，给出极小点，fval给出目标函数极小值，给出目标函数极小值， options是控制参数，可用是控制参数，可用help查询。查询。12/22Matlab程序如下：程序如下： c=-72,64;A=1,1;12,8;3,0;b=50;480;100;Ib=0;0;ub=1e+10*1;1;x,fval=linprog(c,A,b, , ,lb,ub) 结果如下：结果如下： x=20;3

10、0 fval=-336013/22例例2 2：求解线性规划问题：求解线性规划问题123123123123max2357. . 2510,0zxxxxxxs txxxxxx Matlab程序如下：程序如下： c=2;3;-5; A =-2,5,-1; b=-10; Aeq=1,1,1; beq=7; lb=0;0;0; x,fval=linprog(c,A,b,Aeq,beq,lb) 14/22例例3 3：求解非线性规划问题：求解非线性规划问题2212121221212min25(1)0. .236fxxx xxxxxs txx 15/22非线性规划求解非线性规划求解标准形式：标准形式： min

11、 ( ),. .( )0, ( )0, . f xA xbAeq xbeqs tC xCeq xlbxub 其中：其中： 调用格式：调用格式：x,fval,h=fmincon(f,x0,A,b,Aeq,beq,lb,ub,nonlcon) 其中：其中： nonlcon是非线性约束函数，是非线性约束函数，x0是迭代初始点。是迭代初始点。( )0C x 和和 ( )0Ceq x 是非线性约束。是非线性约束。 16/22Matlab程序如下：程序如下： 建立非线性约束函数的建立非线性约束函数的m文件文件lpnon.mfunction c,ceq=lpcon(x)c=(x(1)-1)2-x(2);Ce

12、q= ;建立目标函数的建立目标函数的m文件文件fun.mfunction f=fun(x)f=x(1)2+x(2)2-x(1)*x(2)-2*x(1)-5*x(2);在命令窗口中输入在命令窗口中输入x0=0;1; A=-2 3; b=6;Aeq= ; beq= ; lb= ; ub= ;x,fval,h=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,lpcon)结果：结果： x=3;4, fval=-13, h=1 17/22例例4 4：求解二次规划问题：求解二次规划问题221212121212121min2622. .2223fxxx xxxxxs txxxx 18/22

13、二次规划求解二次规划求解标准形式：标准形式： 1min 2, . .,. TTx Hxc xA xbs tAeq xbeqlbxub 其中：其中：H是实对称矩阵。是实对称矩阵。调用格式：调用格式：x,fval=quadprog(H,c,A,b,Aeq,beq,lb,ub,x0) 19/22Matlab程序如下：程序如下： H=1,-1;-1,2;c=-2;-6;A=1,1;-1,2;2,1; b=2;2;3;Aeq= ; beq= ;lb=zeros(2,1); ub= ;x,fval=quadprog(H,c,A,b,Aeq,beq,lb,ub)结果：结果： x=0.6667; 1.3333

14、, fval=-8.222220/22例例5 5：求解整数规划问题：求解整数规划问题2222212345123451234512345123345max3428232400226800. . 262005200099,1,2,3,4,5iifxxxxxxxxxxxxxxxxxxxxs txxxxxxxxZ i ，21/22整数规划求解整数规划求解-随机投点法随机投点法编写目标函数和约束条件的编写目标函数和约束条件的m文件：文件： function f,g=mengte(x) f=x(1)2+x(2)2+3*x(3)2+ 4*x(4)2+2*x(5)2- 8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5); g(1)=sum(x)-400; g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800; g(3)=2*x(1)+x(2)+6*x(3)-200; g(4)=x(3)+x(4)+5*x(5)-200;22/2