数学建模-线性规划

数学建模--线性规划第1页，课件共70页，创作于2023年2月

线性规划问题的提出线性规划的基本概念线性规划的数学模型继续返回一线性规划问题及其数学模型第2页，课件共70页，创作于2023年2月问题的提出例:生产计划问题第3页，课件共70页，创作于2023年2月产品I产品2如何安排生产使利润最大？第4页，课件共70页，创作于2023年2月决策变量（Decisionvariables）目标函数（Objectivefunction）约束条件（Constraintconditions）可行域（Feasibleregion)最优解（Optimalsolution)基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足约束条件的决策变量的取值范围可行域中使目标函数达到最优的决策变量的值第5页，课件共70页，创作于2023年2月是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。第1步-确定决策变量设——I的产量——II的产量——利润第6页，课件共70页，创作于2023年2月第2步--定义目标函数MaxZ=x1+x2决策变量第7页，课件共70页，创作于2023年2月

MaxZ=2x1+3x2系数第2步--定义目标函数第8页，课件共70页，创作于2023年2月对我们有何限制?第9页，课件共70页，创作于2023年2月第3步--表示约束条件

x1+2x2

84x1

164x2

12x1、x2

0第10页，课件共70页，创作于2023年2月该计划的数学模型

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第11页，课件共70页，创作于2023年2月线性规划问题的共同特征一组决策变量X表示一个方案,一般X大于等于零。约束条件是线性等式或不等式。目标函数是线性的。求目标函数最大化或最小化第12页，课件共70页，创作于2023年2月

线性规划模型的一般形式第13页，课件共70页，创作于2023年2月线性规划模型建立步骤从实际问题中建立数学模型一般有以下三个步骤；1.根据影响所要达到目的的因素找到决策变量；

2.由决策变量和所在达到目的之间的函数关系确定目标函数；

3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。第14页，课件共70页，创作于2023年2月1.线性规划的标准形式：用单纯法求解时，常将标准形式化为：2.线性规划的基本算法——单纯形法二.线性规划的基本算法——单纯形法第15页，课件共70页，创作于2023年2月引入松弛变量x3,x4,x5,将不等式化为等式,即单纯形标准形:显然A的秩ran(A)=3,任取3个线性无关的列向量,如P3P4P5称为一组基,记为B.其余列向量称为非基,记为N.第16页，课件共70页，创作于2023年2月于是f=cBxB+cNxN,Ax=BxB+NxN=b,则xB=B-1b-B-1NxN,f=cBB-1b+(cN–cBB-1N)xN

若可行基进一步满足:cN–cBB-1N≥0,即:cBB-1N-cN≤0则对一切可行解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)有最优解，那么一定存在一个基可行解是最优解.第17页，课件共70页，创作于2023年2月4.基可行解是最优解的判定准则检验数因为Ax=BxB+NxN=b,得xB=B-1b-B-1NxN,而f=cBxB+cNxN,故f=cBB-1b+(cN–cBB-1N)xN

第18页，课件共70页，创作于2023年2月5.基可行解的改进第19页，课件共70页，创作于2023年2月改进方法：返回第20页，课件共70页，创作于2023年2月练习建立LP数学模型一、有两个煤厂A、B，每月分别供应三个居民区X、Y、Z。求运费最少的方案。供需平衡第21页，课件共70页，创作于2023年2月1、LINGO使用简介LINGO软件是美国的LINDO系统公司（LindoSystemInc）开发的一套用于求解最优化问题的软件包.LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解.LINGO软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快.LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果，这里简单介绍LINGO的使用方法.

LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等.一个LINGO程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分，每一部分有其独特的作用和语法规则，读者可以通过查阅相关的参考书或者LINGO的HELP文件详细了解，这里就不展开介绍了.

三.线性规划软件求解第22页，课件共70页，创作于2023年2月LINGO的主要功能特色为：既能求解线性规划问题，也有较强的求解非线性规划问题的能力；输入模型简练直观；运算速度快、计算能力强；内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式描述大规模的优化模型；将集合的概念引入编程语言，很容易将实际问题转换为LINGO模型；并且能方便地与Excel、数据库等其他软件交换数据.

第23页，课件共70页，创作于2023年2月第一步：启动Lingo屏幕显示如下：标记LINGO的外窗口是主框架窗口，主框架窗口的上面包含所有的命令菜单和命令工具栏；标记LINGOMODEL-LINGO1的子窗口是一个新的、空白的模型窗口。第24页，课件共70页，创作于2023年2月第二步：在模型窗口中输入模型model:max=2*x1+3*x2;4*x1+3*x2<10;3*x1+5*x2<12;endMax2x1+3x2St.4x1+3x2<=103x1+5x2<=12x1≥0x2≥0第25页，课件共70页，创作于2023年2月第三步：求解模型

1)选择菜单

LINGO|Solve

或者按工具栏的

第26页，课件共70页，创作于2023年2月

2)LINGO开始编译模型，如有语法错误将返回一个错误的消息并指明错误出现的位置；如果通过编译,LINGO将激活Solver运算器寻求模型的最优解；3)首先出现solverstatus窗口，其作用是监控solver的进展和显示模型的维数等信息；第27页，课件共70页，创作于2023年2月第28页，课件共70页，创作于2023年2月4)计算完成后出现SolutionReport窗口显示模型解的详细信息；第29页，课件共70页，创作于2023年2月SolutionReport窗口Globaloptimalsolutionfoundatiteration:2Objectivevalue:7.454545VariableValueReducedCostx11.2727270.000000x21.6363640.000000RowSlackorSurplusDualPrice17.4545451.00000020.0000000.9090909E-0130.0000000.5454545（对目标函数而言）第30页，课件共70页，创作于2023年2月LINGO的语法规定、运算符及函数：（1）求目标函数的最大值或最小值分别用MAX=…或MIN=…来表示；（2）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；（3）变量名称必须以字母（A~Z）开头，由字母、数字（0~9）和下划线所组成，长度不超过32个字符，不区分大小写；（4）可以给语句加上标号，例如[OBJ]MAX=200*X1+300*X2；（5）以惊叹号“！”开头，以分号“；”结束的语句是注释语句；（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；（7）LINGO模型以语句“MODEL：”开头，以“END”结束，对于比较简单的模型，这两个语句可以省略.(8)可以用<表示<=；用>表示>=；

Lingo无严格小于，欲使a<b，可以适当选取小的正常数e表示成a+e<b，第31页，课件共70页，创作于2023年2月(9)LINGO编辑器用蓝色显示LINGO关键字;

绿色显示注释

;其他文本用黑色

匹配的括号用红色高亮度显示(10)标准运算符算术运算符：^*/+-逻辑运算符：

#EQ##NE#(相等，不等）为真

#GE##GT#（左边大于或等于，左边大于）为真

#LE##LT#（左边小于或等于，左边小于）为真

#NOT##AND##OR#（取反，取交（积），取并（和）)第32页，课件共70页，创作于2023年2月(11).变量界定函数lingo变量默认域为非负实数@free(variable)

取消默认域，使变量可以取任意实数@gin(variable)限制变量取整数值@bin(variable)限制变量取值为0，1@bnd(low,variable,up)限制变量于一个有限的范围第33页，课件共70页，创作于2023年2月例题1：某工厂在计划期内要安排生产A、B两种产品，已知生产单位产品所需设备台时及对甲、乙两种原材料的消耗，有关数据如表1.1.问：应如何安排生产计划，使工厂获利最大？产品资源AB可利用资源设备128台时甲4016公斤乙0412公斤单位利润2元3元建立线性规划问题的数学模型，用LINGO求出最优解并做相应的分析.第34页，课件共70页，创作于2023年2月问题1.1设计划生产A,B两种产品分别为x1,x2，则建立线性规划问题数学模型模型：maxS=2x1+

3x2在LINGO的MODEL窗口内输入如下模型：model:max=2*x1+3*x2;x1+2*x2<=8;4*x1<=16;4*x2<=12;end第35页，课件共70页，创作于2023年2月选菜单Lingo|Solve(或按Ctrl+S),或用鼠标点击“求解”按纽，如果模型有语法错误，则弹出一个标题为“LINGOErrorMessage”(错误信息)的窗口，指出在哪一行有怎样的错误，每一种错误都有一个编号（具体含义可查阅相关文献或LINGO的Help）.改正错误以后再求解，如果语法通过，LINGO用内部所带的求解程序求出模型的解，然后弹出一个标题为“LINGOSolverStatus”（求解状态）的窗口，其内容为变量个数、约束条件个数、优化状态、耗费内存、所花时间等信息，点击Close关闭窗口，屏幕上出现标题为“SolutionReport”（解的报告）的信息窗口，显示优化计算（线性规划中换基迭代）的步数、优化后的目标函数值、列出各变量的计算结果.求解结果：第36页，课件共70页，创作于2023年2月Globaloptimalsolutionfoundatiteration:5Objectivevalue:14.00000VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPrice114.000001.00000020.0000001.50000030.0000000.125000044.0000000.000000第37页，课件共70页，创作于2023年2月该报告说明：运行5步找到全局最优解，目标函数值为14，变量值分别为x1=4,x2=2.“ReducedCost”的含义是需缩减成本系数或需增加利润系数（最优解中取值非零的决策变量的ReducedCost值等于零）.“Row”是输入模型中的行号，目标函数是第一行；“SlackorSurplus”的意思是松弛或剩余，即约束条件左边与右边的差值，对于“≤”的不等式，右边减左边的差值为Slack（松弛），对于“>=”的不等式，左边减右边的差值为Surplus（剩余），当约束条件两边相等时，松弛或剩余的值等于零.“DualPrice”的意思是对偶价格（或称为影子价格），上述报告中Row2的松弛值为0，表明生产甲产品4单位、乙产品2单位，所需设备8台时已经饱和，对偶价格1.5的含义是：如果设备增加1台时，能使目标函数值增加1.5.报告中Row4的松弛值为4，表明生产甲产品4单位、乙产品2单位，所需原材料乙8公斤还剩余4公斤，因此增加原材料乙不会使目标函数值增加，所以对偶价格为0.第38页，课件共70页，创作于2023年2月用MATLAB优化工具箱解线性规划minz=cX

1、模型：命令：x=linprog（c，A，b）2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=[]，b=[].第39页，课件共70页，创作于2023年2月3、模型：minz=cX

VLB≤X≤VUB命令：[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.第40页，课件共70页，创作于2023年2月解编写M文件xxgh1.m如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.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)

ToMatlab(xxgh1)第41页，课件共70页，创作于2023年2月

投资的收益和风险四.线性规划应用举例第42页，课件共70页，创作于2023年2月(二)、基本假设和符号规定第43页，课件共70页，创作于2023年2月(三)、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max{qixi|i=1，2,…n}4.模型简化：第44页，课件共70页，创作于2023年2月第45页，课件共70页，创作于2023年2月(四)、模型1的求解

由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长△a=0.001进行循环搜索，编制程序如下：第46页，课件共70页，创作于2023年2月a=0;while(1.1-a)>1c=[-0.05-0.27-0.19-0.185-0.185];Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')ToMatlab（xxgh5）第47页，课件共70页，创作于2023年2月计算结果：第48页，课件共70页，创作于2023年2月(五)、结果分析返回4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:

风险度收益x0x1x2x3x40.00600.201900.24000.40000.10910.22123.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:

冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.风险大，收益也大。第49页，课件共70页，创作于2023年2月实验作业某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.返回第50页，课件共70页，创作于2023年2月图解法线性规划问题求解的几种可能结果由图解法得到的启示2线性规划的图解法继续返回第51页，课件共70页，创作于2023年2月例1的数学模型

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第52页，课件共70页，创作于2023年2月9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2

=8(0,4)(8,0)

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

04x1

=164x2

=12图解法第53页，课件共70页，创作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

=84x1

=164x2

=12可行域图解法第54页，课件共70页，创作于2023年2月9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

=84x1

=164x2

=12可行域BCDEA图解法第55页，课件共70页，创作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

=84x1

=164x2

=12BCDEA2x1+3x2=6图解法第56页，课件共70页，创作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

=164x2

=12BCDEAx1+2x2=84x1=16最优解(4,2)图解法第57页，课件共70页，创作于2023年2月图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。第58页，课件共70页，创作于2023年2月线性规划问题求解的

几种可能结果(a)唯一最优解

x26—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1第59页，课件共70页，创作于2023年2月(b)无穷多最优解6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1线性规划问题求解的

几种可能结果第60页，课件共70页，创作于2023年2月(c)无界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

x2x1线性规划问题求解的

几种可能结果第61页，课件共70页，创作于2023年2月(d)无可行解

MaxZ=2x1+3x2x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

0可行域为空集线性规划问题求解的

几种可能结果第62页，课件共70页，创作于2023年2月图解法的几点结论:

（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。第63页，课件共70页，创作于