《数学建模线性规划及单纯型法课件.ppt》由会员分享，可在线阅读，更多相关《数学建模线性规划及单纯型法课件.ppt（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目录 例: 生产计划问题III资资源源限限量量设设备备原原材材料料 A原原材材料料 B1402048 台台时时16kg12kg利利润润23产品产品I产品产品2x1x2x1x2zIII资资源源限限量量设设备备原原材材料料A原原材材料料B1402048台台时时16kg12kg利利润润23 0,.,),(.),(.),(.)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax线性规划模型建立步骤 从实际问题中建立数学模型一般有以下三个步骤；从实际问题中建立数学模型一般有以下三个步骤； 1.根据影响所
2、要达到目的的因素找到决策变量；根据影响所要达到目的的因素找到决策变量； 2.由决策变量和所在达到目的之间的由决策变量和所在达到目的之间的函数函数关系确定目标函数；关系确定目标函数； 3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。由决策变量所受的限制条件确定决策变量所要满足的约束条件。 1.1.线性规划的标准形式：线性规划的标准形式：xmin z=)(xf. .ts )(xgi0 （), 2 , 1mi其中目标函数)(xf和约束条件中)(xgi都是线性函数min min f = = c xs.t. s.t. Ax = = b （1 1） x 0 0这里 A = (ija)m,n ,
3、 x = T 21nxxx b= T 21nbbb, c= nccc21用单纯法求解时，常将标准形式化为：用单纯法求解时，常将标准形式化为：2. 线性规划的基本算法线性规划的基本算法单纯形法单纯形法二二.线性规划的基本算法线性规划的基本算法单纯形法单纯形法例例 min z = 10 x1 + 9x2st6x1 + 5x2 60 10 x1 + 20 x2 150 x1 8 x1, x2 0引入松弛变量引入松弛变量x3, x4, x5, 将不等式化为等式将不等式化为等式, 即单纯形标准形即单纯形标准形: min z = 10 x1 + 9x2st6x1 + 5x2 + x3 = 60 10 x1
4、 + 20 x2 - x4 = 150 x1 + x5 = 8 xi 0 (i = 1,2,3,4,5)系数矩阵为: 6 5 1 0 0 A = 10 20 0 -1 0 = (P1 P2 P3 P4 P5) 1 0 0 0 1 b = (60, 150, 8 ) T 显然显然A的秩的秩ran(A)=3, 任取任取3个线性无关的列向量个线性无关的列向量,如如P3 P4 P5称为称为一组基一组基, 记为记为B. 其余列向量称为非基其余列向量称为非基, 记为记为N .于是于是 f = cBxB + cNxN , Ax = BxB + NxN = b, 则则 xB = B-1b-B-1NxN , f
5、 = cBB-1b + (cN cBB-1N)xN 令非基变量 xN = 0, 解得基变量 xB = B1b, 称(xB, xN)为基解基解.基解的所有变量的值都非负，则称为基可行解基可行解，此时的基称为可行基可行基. 若可行基进一步满足若可行基进一步满足: : cN cBB-1N0, 即即: cBB-1N - cN0则对一切可行解则对一切可行解x, 必有必有f(x) cBB-1b, 此时称基可行解此时称基可行解x = (B-1b, 0) T为最优解为最优解. 3. 最优解的存在性定理最优解的存在性定理将将A的列向量重排次序成的列向量重排次序成A = (B, N), 相应相应x = (xB,
6、xN) T, c = (cB, cN)基对应的变量基对应的变量xB称为基变量称为基变量, 非基对应的变量非基对应的变量xN称为非基变量称为非基变量.定理定理1 1 如果线性规划如果线性规划(1)(1)有可行解，那么一定有基可行解有可行解，那么一定有基可行解. .定理定理2 2 如果线性规划如果线性规划(1)(1)有最优解，那么一定存在一个基可行解有最优解，那么一定存在一个基可行解 是最优解是最优解. .4. 4. 基可行解是最优解的判定准则基可行解是最优解的判定准则因为因为 f = cBB-1b + (cN cBB-1N)xN，即即 f - 0 xB + (cBB-1N- cN )xN = c
7、BB-1b定理定理 3 3 设（1x,2x,mx）是规划 (1) 的一个可行基，B是对应的基阵,如果典式中的1,2,m都不大于零,即对应的1m0,2m0,n0,则基（1x,2x,mx）对应的基可行解0X = 01bB 是最优解.检验数检验数令1Bb = m21，1BN= nmmmmmnmmnmm,2,1, 22, 21, 2, 12, 11, 15.5.基可行解的改进基可行解的改进定理定理 4 4 设（1x,2x,mx）是规划 (1) 的一个可行基，B是对应的基阵,如果存在km0，使1) km, 1,km, 2,kmm,中至少有一个大于零；2) 所有的i0，i=1,2, ,m则一定存在另一个可
8、行基，它对应的基可行解使目标函数值更小.令0=kmiikmi,0,min = kmll,则把lx从原有的基中取出来，把kmx加进后得到的（1x,2x,lx ,kmx,1lx,mx）仍是基，即是所要找的新基.改进方法：改进方法：返返 回回距离AB需求量X10445Y5875Z61540供应量60100供需平衡供需平衡1、LINGO使用简介使用简介 LINGO软件是美国的软件是美国的LINDO系统公司（系统公司（Lindo System Inc）开）开发的一套用于求解最优化问题的软件包发的一套用于求解最优化问题的软件包.LINGO除了能用于求解除了能用于求解线性规划和二次规划外，还可以用于非线性规
9、划求解以及一些线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解线性和非线性方程（组）的求解.LINGO软件的最大特色在于它软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快允许优化模型中的决策变量为整数，而且执行速度快.LINGO内内置了一种建立最优化模型的语言，可以简便地表达大规模问题置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用，利用LINGO高效的求解器可快速求解并分析结果，这里简单高效的求解器可快速求解并分析结果，这里简单介绍介绍LINGO的使用方法的使用方法. LINGO可以求解线性规划、二次规划、非线性规划、整数规划可
10、以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等、图论及网络优化和排队论模型中的最优化问题等. 一个一个LINGO程序一般会包含集合段、数据输入段、优化目标和程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分，每一部分有其独特的作约束段、初始段和数据预处理段等部分，每一部分有其独特的作用和语法规则，读者可以通过查阅相关的参考书或者用和语法规则，读者可以通过查阅相关的参考书或者LINGO的的HELP文件详细了解，这里就不展开介绍了文件详细了解，这里就不展开介绍了. 三.线性规划软件求解LINGO的主要功能特色为：既能求解线性规
11、划问题，也有较的主要功能特色为：既能求解线性规划问题，也有较强的求解非线性规划问题的能力；输入模型简练直观；运算强的求解非线性规划问题的能力；输入模型简练直观；运算速度快、计算能力强；内置建模语言，提供几十个内部函数速度快、计算能力强；内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式描述大规模的优化模型，从而能以较少语句，较直观的方式描述大规模的优化模型；将集合的概念引入编程语言，很容易将实际问题转换为；将集合的概念引入编程语言，很容易将实际问题转换为LINGO模型；并且能方便地与模型；并且能方便地与Excel、数据库等其他软件交、数据库等其他软件交换数据换数据. 1)选择菜单
12、选择菜单 LINGO|Solve 或者按工具栏的或者按工具栏的 4)计算完成后出现计算完成后出现Solution Report 窗口显示模型解的详细信息；窗口显示模型解的详细信息；Solution Report 窗口窗口 Global optimal solution found at iteration: 2 Objective value: 7.454545 Variable Value Reduced Cost x1 1.272727 0.000000 x2 1.636364 0.000000 Row Slack or Surplus Dual Price 1 7.454545 1.00
13、0000 2 0.000000 0.9090909E-01 3 0.000000 0.5454545LINGO的语法规定、运算符及函数：的语法规定、运算符及函数：（1）求目标函数的最大值或最小值分别用）求目标函数的最大值或最小值分别用MAX=或或MIN=来表来表示；示；（2）每个语句必须以分号）每个语句必须以分号“；”结束，每行可以有许多语句，语结束，每行可以有许多语句，语句可以跨行；句可以跨行；（3）变量名称必须以字母（）变量名称必须以字母（AZ）开头，由字母、数字（）开头，由字母、数字（09）和）和下划线所组成，长度不超过下划线所组成，长度不超过32个字符，不区分大小写；个字符，不区分大小
14、写；（4）可以给语句加上标号，例如）可以给语句加上标号，例如OBJ MAX=200*X1+300*X2；（5）以惊叹号）以惊叹号“！”开头，以分号开头，以分号“；”结束的语句是注释语句结束的语句是注释语句；（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；量都非负；（7）LINGO模型以语句模型以语句“MODEL：”开头，以开头，以“END”结束，对结束，对于比较简单的模型，这两个语句可以省略于比较简单的模型，这两个语句可以省略.(8)可以用可以用表示表示表示表示= Lingo无严格小于，欲使无严格小于，欲使ab， 可以适
15、当选取小的正常数可以适当选取小的正常数e 表示成表示成a+eb，例题例题1： 某工厂在计划期内要安排生产某工厂在计划期内要安排生产A、B两种产品，已知生两种产品，已知生产单位产品所需设备台时及对甲、乙两种原材料的消耗，有关数产单位产品所需设备台时及对甲、乙两种原材料的消耗，有关数据如表据如表1.1.问：应如何安排生产计划，使工厂获利最大？问：应如何安排生产计划，使工厂获利最大？ 产品 资源AB可利用资源设备128台时甲4016公斤乙0412公斤单位利润2元3元建立线性规划问题的数学模型，用建立线性规划问题的数学模型，用LINGO求出最优解并做相求出最优解并做相应的分析应的分析.问题问题1.1设
16、计划生产设计划生产A,B两种产品分别为两种产品分别为x1,x2，则建立线性规划，则建立线性规划问题数学模型问题数学模型12121228416. .412,0 xxxstxx x模型：模型：max S=2x1+ 3x2在在LINGO的的MODEL窗口内输入如下模型：窗口内输入如下模型：model:max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=”的不等式，左边减右边的差值为的不等式，左边减右边的差值为Surplus（剩余（剩余），当约束条件两边相等时，松弛或剩余的值等于零），当约束条件两边相等时，松弛或剩余的值等于零.“Dual Price”的意思是对偶价格（或称为影子
17、价格），上述报告中的意思是对偶价格（或称为影子价格），上述报告中Row2的松弛值为的松弛值为0，表明生产甲产品，表明生产甲产品4单位、乙产品单位、乙产品2单位，所需设备单位，所需设备8台时已经饱和，对偶价格台时已经饱和，对偶价格1.5的含义是：如果设备增加的含义是：如果设备增加1台时，能台时，能使目标函数值增加使目标函数值增加1.5.报告中报告中Row4的松弛值为的松弛值为4，表明生产甲产，表明生产甲产品品4单位、乙产品单位、乙产品2单位，所需原材料乙单位，所需原材料乙8公斤还剩余公斤还剩余4公斤，因此公斤，因此增加原材料乙不会使目标函数值增加，所以对偶价格为增加原材料乙不会使目标函数值增加，
18、所以对偶价格为0.用用MATLAB优化工具箱解线性规划优化工具箱解线性规划min z=cX bAXts. .1、模型：、模型：命令：命令：x=linprog（c，A，b） 2、模型、模型：min z=cX . .stAXbbeqXAeq命令：命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：注意：若没有不等式： 存在，则令存在，则令A= ，b= .bAX 3、模型、模型：min z=cX bAXts. .beqXAeqVLBXVUB命令：命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, V
19、LB，VUB, X0） 注意：注意：1 若没有等式约束若没有等式约束: , 则令则令Aeq= , beq= . 2其中其中X0表示初始点表示初始点 beqXAeq4、命令：、命令：x,fval=linprog()返回最优解及处的目标函数值返回最优解及处的目标函数值fval.解解 编写编写M文件文件xxgh1.m如下：如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;
20、900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) To Matlab (xxgh1) 投资的收益和风险投资的收益和风险基本假设：基本假设：1. 投资数额 M 相当大,为了便于计算，假设 M=1；2投资越分散，总的风险越小；3总体风险用投资项目is中最大的一个风险来度量；4n 种资产 Si之间是相互独立的；5在投资的这一时期内, ri,pi,qi，r0为定值，不受意外因素影响；6净收益和总体风险只受 ri,pi,qi影响，不受其他因素干扰。( (二二) )、基本假设和符号规定、基本假设和符号规
21、定符符号号规规定定：Si 第 i 种投资项目，如股票，债券ri,pi,qi -分别为 Si的平均收益率,风险损失率，交易费率ui -Si的交易定额 0r -同期银行利率xi -投资项目 Si的资金 a -投资风险度Q -总体收益 Q -总体收益的增量( (三三) )、模型的建立与分析、模型的建立与分析1.总体风险用所投资的总体风险用所投资的Si中最大的一个风险来衡量中最大的一个风险来衡量,即即max qixi|i=1，2,n2购买 Si所付交易费是一个分段函数,即 pixi xiui 交易费 = piui xiui而题目所给定的定值 ui(单位:元)相对总投资 M 很小, piui更小,可以忽
22、略不计,这样购买 Si的净收益为(ri-pi)xi 3要使净收益尽可能大，总体风险尽可能小,这是一个多目标规划模型: 目标函数 MAXniiiixpr0)( MINmax qixi 约束条件 niiixp0)1 (=M xi0 i=0,1,n4. 模型简化：模型简化：c投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重 s（0s1)，s 称为投资偏好系数.模型模型 3 目标函数：min smaxqixi -（1-s）niiiixpr0)( 约束条件 niiixp0)1 (=M， xi0 i=0,1,2,nb若投资者希望总盈利至少达到水平 k 以上
23、，在风险最小的情况下寻找相应的投资组合。模型模型 2 固定盈利水平，极小化风险 目标函数： R= minmax qixi 约束条件：niiiixpr0)(k， Mxpii)1 ( ， xi 0 i=0，1，na 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限 a，使最大的一个风险 qixi/Ma，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。模型模型 1 1 固定风险水平，优化收益 目标函数： Q=MAX11)(niiiixpr 约束条件： Mxqiia Mxpii)1 (， xi 0 i=0，1，n( (四四) )、模型、模型1 1的求解的求解 模型1为: mi
24、nf = (-0.05, -0.27, -0.19, -0.185, -0.185) (x0 x1 x2 x3 x 4 ) T x0 + 1.01x1 + 1.02x2 +1.045x3 +1.065x4 =1s.t. 0.025x1 a 0.015x2 a 0.055x3 a 0.026x4a xi 0 (i = 0,1,.4) 由于由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从资者有不同的风险度。我们从a=0开始，以步长开始，以步长a=0.001进行循环搜索，进行循环搜索，编制程序如下：编制程序如
25、下：a=0;while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel
26、(Q)To Matlab（xxgh5）计算结果：计算结果：(五五)、 结果分析结果分析返返 回回4.4.在在a=0.006a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和 收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合， 大约是大约是a a* *=0.6%=0.6%，Q Q* *=20% =20% ，所
27、对应投资方案为，所对应投资方案为: : 风险度风险度 收益收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2.2.当投资越分散时，投资者承担的风险越小，这与题意一致。即当投资越分散时，投资者承担的风险越小，这与题意一致。即: : 冒险的投资者会出现集中投资的情况，保守
28、的投资者则尽量分散投资。冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。风险大，收益也大。实验作业实验作业 某厂生产甲乙两种口味的饮料某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料每百箱甲饮料需用原料6千克千克,工人工人10名名,可获利可获利10万元万元;每百箱乙饮料需用原料每百箱乙饮料需用原料5千克千克,工人工人20名名,可获利可获利9万元万元.今工厂共有原料今工厂共有原料60千克千克,工人工人150名名,又由于其又由于其他条件所限甲饮料产量不超过他条件所限甲饮料产量不超过8百箱百箱.问如何安排生产计划问如何安排生产计划,即即两种饮料各生产多少使获利
29、最大两种饮料各生产多少使获利最大.进一步讨论进一步讨论: 1)若投资若投资0.8万元可增加原料万元可增加原料1千克千克,问应否作这项投资问应否作这项投资. 2)若每百箱甲饮料获利可增加若每百箱甲饮料获利可增加1万元万元,问应否改变生产计划问应否改变生产计划.返返 回回9 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 8(0, 4)(8, 0)4x1 164 x2 129 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 12可行域可行域9 8 7 6 5 4 3 2 1 0 |123456789x1x2
30、x1 + 2x2 84x1 164 x2 12可行域可行域BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 12BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 12BCDEAx1+ 2x2=8 4x1 =16x26 5 4 3 2 1 0 |123456789x16 5 4 3 2 1 0 x2|123456789x1 x2x118 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x
31、2 182x1 + x2 1618 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16可行域可行域ABCDE18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)x218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)4x1+ 6x2=48 2x1+ 2x2 =18