数学建模线性规划及单纯型法课件.ppt

目录,一.线性规划问题及其模型二.线性规划的基本算法单纯形法三.线性规划数学软件求解四.线性规划应用举例,线性规划问题的提出 线性规划的基本概念 线性规划的数学模型,一 线性规划问题及其数学模型,问题的提出,例:生产计划问题,决策变量（Decision variables）目标函数（Objective function）约束条件（Constraint conditions）可行域（Feasible region)最优解（Optimal solution),基本概念,问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,它是决策变量的函数,指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。,满足约束条件的决策变量的取值范围,可行域中使目标函数达到最优的决策变量的值,是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,第1步-确定决策变量,设 I的产量 II的产量 利润,第2步-定义目标函数,Max Z=x1+x2,Max Z=2 x1+3 x2,第2步-定义目标函数,第3步-表示约束条件,x1+2 x2 8 4 x1 16 4 x2 12 x1、x2 0,该计划的数学模型,目标函数 Max Z=2x1+3x2 约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0,x1,x2,线性规划问题的共同特征,一组决策变量X表示一个方案,一般X大于等于零。约束条件是线性等式或不等式。目标函数是线性的。求目标函数最大化或最小化,线性规划模型的一般形式,线性规划模型建立步骤,从实际问题中建立数学模型一般有以下三个步骤；1.根据影响所要达到目的的因素找到决策变量；2.由决策变量和所在达到目的之间的函数关系确定目标函数；3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。,1.线性规划的标准形式：,用单纯法求解时，常将标准形式化为：,2.线性规划的基本算法单纯形法,二.线性规划的基本算法单纯形法,引入松弛变量x3,x4,x5,将不等式化为等式,即单纯形标准形:,显然A的秩ran(A)=3,任取3个线性无关的列向量,如P3 P4 P5称为一组基,记为B.其余列向量称为非基,记为N.,于是 f=cBxB+cNxN,Ax=BxB+NxN=b,则 xB=B-1b-B-1NxN,f=cBB-1b+(cN cBB-1N)xN,若可行基进一步满足:cN cBB-1N0,即:cBB-1N-cN0则对一切可行解x,必有f(x)cBB-1b,此时称基可行解x=(B-1b,0)T为最优解.,3.最优解的存在性定理,将A的列向量重排次序成A=(B,N),相应x=(xB,xN)T,c=(cB,cN)基对应的变量xB称为基变量,非基对应的变量xN称为非基变量.,定理1 如果线性规划(1)有可行解，那么一定有基可行解.,定理2 如果线性规划(1)有最优解，那么一定存在一个基可行解 是最优解.,4.基可行解是最优解的判定准则,因为 f=cBB-1b+(cN cBB-1N)xN，即 f-0 xB+(cBB-1N-cN)xN=cBB-1b,检验数,5.基可行解的改进,改进方法：,返 回,练习建立LP数学模型一、有两个煤厂A、B，每月分别供应三个居民区X、Y、Z。求运费最少的方案。,供需平衡,1、LINGO使用简介 LINGO软件是美国的LINDO系统公司（Lindo System Inc）开发的一套用于求解最优化问题的软件包.LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解.LINGO软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快.LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果，这里简单介绍LINGO的使用方法.,LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等.一个LINGO程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分，每一部分有其独特的作用和语法规则，读者可以通过查阅相关的参考书或者LINGO的HELP文件详细了解，这里就不展开介绍了.,三.线性规划软件求解,LINGO的主要功能特色为：既能求解线性规划问题，也有较强的求解非线性规划问题的能力；输入模型简练直观；运算速度快、计算能力强；内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式描述大规模的优化模型；将集合的概念引入编程语言，很容易将实际问题转换为LINGO模型；并且能方便地与Excel、数据库等其他软件交换数据.,第一步：启动Lingo,屏幕显示如下：标记LINGO的外窗口是主框架窗口，主框架窗口的上面包含所有的命令菜单和命令工具栏；标记LINGO MODEL-LINGO1的子窗口是一个新的、空白的模型窗口。,第二步：在模型窗口中输入模型,model:max=2*x1+3*x2;4*x1+3*x210;3*x1+5*x212;end,Max 2x1+3x2 St.4x1+3x2=10 3x1+5x2=12 x10 x20,第三步：求解模型,1)选择菜单 LINGO|Solve 或者按工具栏的,2)LINGO开始编译模型，如有语法错误将返回一个错误的消息并指明错误出现的位置；如果通过编译,LINGO将激活 Solver运算器 寻求模型的最优解；,3)首先出现solver status 窗口，其作用是监控solver的进展和显示模型的维数等信息；,4)计算完成后出现Solution Report窗口显示模型解的详细信息；,Solution Report 窗口,Global optimal solution found at iteration:2Objective value:7.454545Variable Value Reduced Cost x1 1.272727 0.000000 x2 1.636364 0.000000Row Slack or Surplus Dual Price 1 7.454545 1.000000 2 0.000000 0.9090909E-01 3 0.000000 0.5454545,LINGO的语法规定、运算符及函数：（1）求目标函数的最大值或最小值分别用MAX=或MIN=来表示；（2）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；（3）变量名称必须以字母（AZ）开头，由字母、数字（09）和下划线所组成，长度不超过32个字符，不区分大小写；（4）可以给语句加上标号，例如OBJ MAX=200*X1+300*X2；（5）以惊叹号“！”开头，以分号“；”结束的语句是注释语句；（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；（7）LINGO模型以语句“MODEL：”开头，以“END”结束，对于比较简单的模型，这两个语句可以省略.,(8)可以用表示=；,Lingo无严格小于，欲使ab，可以适当选取小的正常数e 表示成a+eb，,(9)LINGO编辑器用 蓝色显示LINGO关键字;绿色显示注释;其他文本用黑色 匹配的括号用红色高亮度显示,(10)标准运算符,算术运算符：*/+-,逻辑运算符：#EQ#NE#(相等，不等）为真#GE#GT#（左边大于或等于，左边大于）为真#LE#LT#（左边小于或等于，左边小于）为真#NOT#AND#OR#（取反，取交（积），取并（和）),(11).变量界定函数,lingo变量默认域为非负实数free(variable)取消默认域，使变量可以取任意实数gin(variable)限制变量取整数值bin(variable)限制变量取值为0，1bnd(low,variable,up)限制变量于一个有限的范围,例题1：某工厂在计划期内要安排生产A、B两种产品，已知生产单位产品所需设备台时及对甲、乙两种原材料的消耗，有关数据如表1.1.问：应如何安排生产计划，使工厂获利最大？,建立线性规划问题的数学模型，用LINGO求出最优解并做相应的分析.,问题1.1设计划生产A,B两种产品分别为x1,x2，则建立线性规划问题数学模型,模型：max S=2x1+3x2,在LINGO的MODEL窗口内输入如下模型：model:max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=12;end,选菜单Lingo|Solve(或按Ctrl+S),或用鼠标点击“求解”按纽，如果模型有语法错误，则弹出一个标题为“LINGO Error Message”(错误信息)的窗口，指出在哪一行有怎样的错误，每一种错误都有一个编号（具体含义可查阅相关文献或LINGO的Help）.改正错误以后再求解，如果语法通过，LINGO用内部所带的求解程序求出模型的解，然后弹出一个标题为“LINGO Solver Status”（求解状态）的窗口，其内容为变量个数、约束条件个数、优化状态、耗费内存、所花时间等信息，点击Close关闭窗口，屏幕上出现标题为“Solution Report”（解的报告）的信息窗口，显示优化计算（线性规划中换基迭代）的步数、优化后的目标函数值、列出各变量的计算结果.求解结果：,Global optimal solution found at iteration:5Objective value:14.00000Variable Value Reduced CostX1 4.000000 0.000000X2 2.000000 0.000000Row Slack or Surplus Dual Price1 14.00000 1.0000002 0.000000 1.5000003 0.000000 0.12500004 4.000000 0.000000,该报告说明：运行5步找到全局最优解，目标函数值为14，变量值分别为x1=4,x2=2.“Reduced Cost”的含义是需缩减成本系数或需增加利润系数（最优解中取值非零的决策变量的Reduced Cost值等于零）.“Row”是输入模型中的行号，目标函数是第一行；“Slack or Surplus”的意思是松弛或剩余，即约束条件左边与右边的差值，对于“”的不等式，右边减左边的差值为Slack（松弛），对于“=”的不等式，左边减右边的差值为Surplus（剩余），当约束条件两边相等时，松弛或剩余的值等于零.“Dual Price”的意思是对偶价格（或称为影子价格），上述报告中Row2的松弛值为0，表明生产甲产品4单位、乙产品2单位，所需设备8台时已经饱和，对偶价格1.5的含义是：如果设备增加1台时，能使目标函数值增加1.5.报告中Row4的松弛值为4，表明生产甲产品4单位、乙产品2单位，所需原材料乙8公斤还剩余4公斤，因此增加原材料乙不会使目标函数值增加，所以对偶价格为0.,用MATLAB优化工具箱解线性规划,命令：x=linprog（c，A，b）,2、模型：min z=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若没有不等式：存在，则令A=，b=.,命令：1 x=linprog（c，A，b，Aeq,beq,VLB，VUB）2 x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）,注意：1 若没有等式约束:,则令Aeq=,beq=.2其中X0表示初始点,4、命令：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;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.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n,4.模型简化：,(四)、模型1的求解,由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：,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(Q),To Matlab（xxgh5）,计算结果：,(五)、结果分析,返 回,4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和 收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212,3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。,2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。,1.风险大，收益也大。,实验作业,某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.,返 回,图解法 线性规划问题求解的 几种可能结果 由图解法得到的启示,2 线性规划的图解法,例1的数学模型,目标函数 Max Z=2x1+3x2 约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0,x1,x2,9 8 7 6 5 4 3 2 1 0,|123456789,x1,x2,x1+2x2=8,目标函数 Max Z=2x1+3x2 约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0,4x1=16,4 x2=12,图解法,9 8 7 6 5 4 3 2 1 0,x2,目标函数 Max Z=2x1+3x2 约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0,可行域,图解法,9 8 7 6 5 4 3 2 1 0,|123456789,x1,x2,目标函数 Max Z=2x1+3x2 约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0,可行域,图解法,9 8 7 6 5 4 3 2 1 0,x2,目标函数 Max Z=2x1+3x2 约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0,2x1+3x2=6,图解法,9 8 7 6 5 4 3 2 1 0,x2,目标函数 Max Z=2x1+3x2 约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0,x1+2x2=8 4x1=16,图解法,图解法求解步骤,由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。,线性规划问题求解的 几种可能结果,(a)唯一最优解,(b)无穷多最优解,线性规划问题求解的 几种可能结果,(c)无界解 Max Z=x1+x2-2x1+x2 4 x1-x2 2 x1、x2 0,x1,线性规划问题求解的 几种可能结果,(d)无可行解 Max Z=2x1+3x2 x1+2 x2 8 4 x1 16 4x2 12-2x1+x2 4 x1、x2 0可行域为空集,线性规划问题求解的 几种可能结果,图解法的几点结论:（由图解法得到的启示）,可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。,练习：用图解法求解LP问题,图解法（练习）,18 16 14 12 10 8 6 4 2 0,|24681012141618,x1,x2,4x1+6x2=48,2x1+2x2=18,2x1+x2=16,图解法（练习）,18 16 14 12 10 8 6 4 2 0,|24681012141618,x1,x2,4x1+6x2=48,2x1+2x2=18,2x1+x2=16,可行域,A,B,C,D,E,图解法（练习）,18 16 14 12 10 8 6 4 2 0,|24681012141618,x1,x2,4x1+6x2 48,2x1+2x2=18,2x1+x2=16,A,B,C,D,E(8,0),(0,6.8),34x1+40 x2=272,图解法（练习）,18 16 14 12 10 8 6 4 2 0,|24681012141618,x1,x2,4x1+6x2 48,2x1+2x2=18,2x1+x2=16,A,B,C,D,E(8,0),(0,6.8),图解法（练习）,x2,18 16 14 12 10 8 6 4 2 0,|24681012141618,x1,4x1+6x2 48,2x1+2x2=18,2x1+x2=16,A,B,C,D,E(8,0),(0,6.8),最优解(3,6),4x1+6x2=48 2x1+2x2=18,2 线性规划的图解法,结束,