第二章 线性规划模型(上 线性规划)08-2.ppt
1第二章第二章 线性规划模型线性规划模型2.1 2.1 引言引言例2.1 多产品生产问题（Max,）设x1,x2 分别代表甲、乙两种产品的产量(件)，约束条件：甲 乙限额材料2324工时3226利润(元/件)432例例2.22.2、配料问题（、配料问题（min,min,)某制药厂要生产一种新药，其原料为甲、乙两种，要求成品的每粒胶丸中必须有一定含量的VA、VB1、VB2和VD，则应怎样安排原料甲乙的用量，使总成本最低？解：设 x1,x2分别代表每粒胶丸中甲、乙两种原料的用量原料甲原料乙最低含量VA0.50.52.0VB11.00.33.0VB20.20.61.2VD0.50.22.0单价0.30.5思考：药片重量有无限制？32.2.2 线性规划的数学模型2.2.1 2.2.1 线性规划问题线性规划问题标准型标准型线性规划的数学模型的线性规划的数学模型的一般形式一般形式.思考：为什么叫思考：为什么叫“线性规划线性规划”？41 1 和式和式52 2 向量式向量式 b5b5思考：和式表示中，几组求和？向量式中，几组求和？n组和1组63 3 矩阵式（最简洁，最常用）矩阵式（最简洁，最常用）74 4 标准型标准型 8化例2.2中数学模型为标准型b992.2.2 线性规划问题的解1.标准型有 n个变量，m 个约束行2.“基”的概念在标准型中，资源消耗（技术）系数矩阵有 n列，即 A=(P1,P2 ,Pn)A中线性独立的 m 列，构成该标准型的一个基，即 B=(P1,P2 ,Pm)，|B|0 P1,P2 ,Pm 称为基向量与基向量对应的变量称为基变量，记 XB=(x1,x2 ,xm )T，其余的变量称为非基变量，记 XN=(xm+1,xm+2,xn )T，故有 X=(XB T,XN T)T最多有 个基(n个列向量中任选m个均为基)103.关于标准型解的若干基本概念：可行解满足约束条件（1）和非负条件（2）的解 X 称为可行解.（不需使性能指标最优）基解令非基变量 XN=0，求得满足约束条件（1）的解称为基解.（不需满足非负条件(2)，基解未必是可行解，基解中分量个数为n）XB=B1 b b11基可行解分量都 0的基解称为基可行解，否则为基非可行解基可行解的非零分量个数 m 时，称为退化解最优解 使目标函数最大的可行解基本最优解 使目标函数最大的基可行解114.线性规划标准型问题解的关系基解基解可行解可行解非可行解非可行解基可行解基可行解退化解退化解最优解最优解基本最优解基本最优解12132.2.2.3 线性规划的图解f(x)=3614图解法的结论线性规划问题的解：唯一，多重，无界，无可行解.最优解若存在，可在某顶点（极点，基可行解）上达到.思考：图解法适用范围？从一个基可行解向另一个基可行解迭代，使目标函数不断改善，求出最优基可行解 -单纯形法.152.3 单纯型方法单纯型法的基本思路161.标准型 172.单纯型表18192021223.判断定理2324254.单纯型法的计算步骤 262728293031325.用人工变量法找初始可行基33342.4 利用MATLAB求解线性规划问题2.4.1 2.4.1 优化工具箱优化工具箱(optim)(optim)简介简介1.1.概述概述置于MATLAB的toolbox目录下的optim子目录中常用的最优化问题求解函数问 题模 型函数名无约束多变量函数极小Min f(x)xR nfminunc、fminsearch约束极小Min f(t)s.t.Ax B、A1x=B1C(x)0、C1(x)=0LB x UBfmincon线性规划Min fxs.t.Ax B、A1x=B1LB x UBlinprog35常用的最优化问题求解函数问题模型函数名二次规划Min(xHx/2+cx)s.t.Ax B、A1x=B1LB x UBquadprog非负线性最小二乘法Min|Ax-B|s.t.x 0Lsqnonneg约束线性最小二乘法Min|Ax-b|2/2s.t.Ax B、A1x=B1LB x UBlsqlin非线性最小二乘法lsqnonlin36常用的最优化问题求解函数问题模型函数名非线性最小二乘拟合lsqcurvefit最小最大极值fminmax单变量方程求解F(x)=0fzero非线性方程组求解F(x)=0fsolve372.控制算法的选项通过optimset函数进行设置格式为options=optimset(para1,value1,para2,value2,)其内容可在optimset.m中查找名称功能可取值缺省值Diagnostics打印求解的诊断信息on,offoffDiffMaxChange有限差分梯度计算中变量的最大变化正数1e-1DiffMinChange有限差分梯度计算中变量的最小变化正数1e-8382.控制算法的选项名称功能可取值缺省值Display显示计算过程的等级off,iter,finalfinalLargeScale如果可能，使用大规模算法on,offoffMaxFunEvals函数计算的最大次数正整数MaxIter迭代的最大次数正整数TolCon计算结束时满足约束条件的精度正数TolFun计算结束时函数值应达到的精度正数TolX计算结束时x应达到的精度正数392.4 利用MATLAB求解线性规划问题2.4.2 2.4.2 标准形式标准形式 MATLAB6.0解决的线性规划问题的标准形式为：其中f、x、b、beq、lb、ub为向量，A、Aeq为矩阵402.4 利用MATLAB求解线性规划问题例2.4.1：对线性规划问题要用MATLAB求解，需先将它化为如下形式：其中412.4 利用MATLAB求解线性规划问题例2.4.2：对线性规划问题要用MATLAB求解，需先将它化为如下形式：其中422.4 利用MATLAB求解线性规划问题2.4.3 linprog2.4.3 linprog函数函数1.格式 x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)说明 A,b为不等式约束，若没有，则A=，b=；Aeq，beq为等式约束，若没有，则Aeq=,beq=；lb,ub为x的下、上界；x0为求解的初值；options为指定的优化参数；参见optimset函数可选项有：Display(final或off)、Diagnostics、TolFun、LargeScale和MaxIterx为目标函数最优时的变量值；fval为目标函数最优值，fval=f*x；exitflag为终止迭代的错误条件；output为关于优化的一些信息。lambda为解x的Lagrange乘子；432.4 利用MATLAB求解线性规划问题2.2.说明说明在输入参数中，可只提供f,A,b三个；若要提供Aeq,beq，则若没有不等式约束，也必须提供A，b（均为即可）;lb，ub可不提供，则对x的范围不作要求，若提供lb，则前面的Aeq，beq也必须提供；要提供ub，则必须提供lb；即所有的输入参数中，若要提供右边的，则必须提供左边的。在输出参数中，类似地，要使用右边的输出参数，必须使用左边的输出参数。理论中标准型为max，而MATLAB中的标准型为min，可将理论中的标准型加负号得到min。同理，若是约束条件中是大于等于，则对aij加负号变为小于等于。442.4 利用MATLAB求解线性规划问题2.2.格式示例：格式示例：x=linprog(f,A,b)求min fx st.Ax=b的最优解x=linprog(f,A,b,Aeq,beq)加上等式约束Aeq x=beq，若没有不等式约束，则A=,b=x=linprog(f,A,b,Aeq,beq,lb,ub)指定x的范围为lb=x0函数收敛于解x=0超过函数估计值或迭代的最大次数0函数不收敛于解xOutput关于优化的一些信息iterations迭代次数algorithm使用的运算规则cgiterations PCG(共轭梯度)迭代次数firstorderropt 一阶最优性的度量462.4 利用MATLAB求解线性规划问题5.示例例2.5.3 求解线性规划问题解：见ch2_1.m可得：X=6;4Z=3647Matlab 程序ch2_1.m和运行结果482.4 利用MATLAB求解线性规划问题例2.4.4 求解线性规划问题解：见ch2_2.m可得X=2.9890;0.0331Z=949Matlab 程序ch2_2.m和运行结果502.4 利用MATLAB求解线性规划问题例2.4.5 求解下面的线性规划问题解：见ch2_3.m可得X=4;1;9Z=-251Matlab 程序ch2_3.m和运行结果522.4 利用MATLAB求解线性规划问题例2.4.6 求解下面的线性规划问题解：见ch2_4.m可得 无界解（Z可到负无穷）53Matlab 程序ch2_4.m54运行结果55练习分别用图解法、单纯形法求解下列问题，最后编写MATLAB程序检验。
