《数学规划模型实验》由会员分享，可在线阅读，更多相关《数学规划模型实验（22页珍藏版）》请在金锄头文库上搜索。
1、数学规划模型实验,数学教研组 卢鹏 2015.7.23,优化问题及其一般模型：,引 言,优化问题是人们在工程技术、经济管理和科学研究等领域中最常遇到的问题之一。例如： 设计师要在满足强度要求等条件下选择材料的尺寸， 使 结构总重量最轻； 公司经理要根据生产成本和市场需求确定产品价格，使所获 利润最高； 调度人员要在满足物质需求和装载条件下安排从各供应点 到需求点的运量和路线，使运输总费用最低； 投资者要选择一些股票,债券下注,使收益最大,而风险最小 ,一般地，优化模型可以表述下：,这是一个多元函数的条件极值问题，其中 .,许多实际问题归结出的这种优化模型，若决策变量个数较少可用微分法求解;但是
2、其决策变量个数 n 和约束条件个数 m 较大，并且最优解往往在可行域的边界上取得，数学规划就是解决这类问题的有效方法。,数学规划模型分类：,“数学规划是运筹学和管理科学中应用及其广泛的分支。数学规划包括线性规划、非线性规划、整数规划、几何规划、多目标规划等，用数学规划方法解决实际问题，就要将实际问题经过抽象、简化、假设，确定变量与参数，建立适当层次上的数学模型，并求解。,建立数学规划模型的步骤:,Step 1. 寻求决策，即回答什么？必须清楚，无歧义。 阅读完题目的第一步不是寻找答案或者解法，而是 Step 2. 确定决策变量 第一来源：Step 1的结果，用变量固定需要回答的决策 第二来源：
3、由决策导出的变量（具有派生结构） 其它来源：辅助变量（联合完成更清楚的回答） Step 3. 确定优化目标 用决策变量表示的利润、成本等。 Step 4. 寻找约束条件 决策变量之间、决策变量与常量之间的联系。 第一来源：需求； 第二来源：供给； 其它来源：辅助以及常识。 Step 5. 构成数学模型 将目标以及约束放在一起，写成数学表达式。,目 录,线性规划 非线性规划 二次规划 整数规划, ,例1：加工奶制品的生产计划,一奶制品加工厂用牛奶生产A1，A2两种奶制品，一桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2全部能
4、够售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能够得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。试为该厂制 定一个生产计划，使每天获利最大?,每天,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,问 题 分 析,引入决策变量 x1 桶牛奶生产A1 ，x2桶牛奶生产A2（每天） 目标函数（每天获利） 生产A1获利： 243x1 生产A2获利： 164x2 每天获利总额：z=72x1+64x2 约束条件 原料供应： x1+x250 劳动时间： 12x1+8x248
5、0 加工能力： 3x1100 非负约束： x1 , x2 0,模型构成：,线性规划数学模型：,线性规划求解,标准形式：,其中：,均为列向量，,为矩阵。,调用格式：x,fval=linprog(c,A,b,Aeq,beq,lb,ub,options),其中：x给出极小点，fval给出目标函数极小值， options是控制参数，可用help查询。,Matlab程序如下：,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;30 fval=-3
6、360,例2：求解线性规划问题,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),例3：求解非线性规划问题,非线性规划求解,标准形式：,其中：,调用格式：x,fval,h=fmincon(f,x0,A,b,Aeq,beq,lb,ub,nonlcon),其中： nonlcon是非线性约束函数，x0是迭代初始点。,和,是非线性约束。,Matlab程序如下：,建立非线性约束函数的m文件lpnon.m function c,ceq=lpcon(x)
7、c=(x(1)-1)2-x(2); Ceq= ; 建立目标函数的m文件fun.m function 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,例4：求解二次规划问题,二次规划求解,标准形式：,其中：H是实对称矩阵。,调用格式：x,fval=quadprog(H,c,A,b,Aeq,be
8、q,lb,ub,x0),Matlab程序如下：,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, fval=-8.2222,例5：求解整数规划问题,整数规划求解-随机投点法,编写目标函数和约束条件的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
9、*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;,Matlab程序如下：,p0=0;x0=zeros(5,1); tic for i=1:100000 x1=99*rand(5,1);x=round(x1); f,g=mengte(x); if sum(g=0)=0 if p0=f x0=x;p0=f; end end x0,p0 toc 结果： x0=40;94;3;97;11, p0=47789, toc=7.223 备注：答案不唯一，但误差不应该很大。,
