数学模型培训讲稿1-线性规划

运筹学中各类优化模型主讲:刘小华运筹学是一门新兴的应用学科.由于它所研究的对象极其广泛有着许多不同的定义.1978年联邦德国的科学词典上定义:“运筹学是从事决策模型的数学解法的一门学科”.1976年美国运筹学会定义:“运筹学是研究用科学方法来决定在资源不充分的情况下如何最好地设计人一机系统,并使之最好地运行的一门学科”.前者着重于处理实际问题,而对于“科学方法”则未加说明,后者强调数字解,而注重数学方法.运筹学简介运筹学一词的英文名词为operationsresearch可直译为“运用研究”和“作用研究”.早在1938年英国空军就有了飞机定位和控制系统,并在沿海有几个雷达站,可以用来发现敌机,但在一次防空大演习中发现,由这些雷达送来的(常常是互相矛盾的)信息,需要加以协调和关联,以改进作战效果,这一任务的提出即产生“运筹学”一词,英国空军成立了运筹学小组,主要从事警报和控制系统的研究.运筹学简介我国运筹学的先驱者从《史记.高祖本记》:“夫运筹帷幄之中,决胜于千里之外”一语摘取“运筹”二字作为这门科学的名称,既显示其军事的起源,也表明其萌芽早已出现在我国.释义筹：计谋、谋划；帷幄：古代军中帐幕。指拟定作战策略。引申为筹划、指挥。运筹学简介运筹学研究的基本特征是：系统的整体观念、多学科的综合、应用模型技术。数学模型是最为抽象的模型，当你看到数学模型时，往往看不出它所代表的现实是什么，如Y=kX。正是由于数学模型的抽象性，所以数学模型有其广泛的适应性。数学模型中的参数和变量最容易改变，运用起来也最为方便。如：参数k:m、v、R、P；变量Y:F、S、V、C；变量X:a、t、I、Q运筹学中用的模型主要是数学模型，数学模型是运筹学的核心，可以说，没有数学模型，就没有运筹学。运筹学简介运筹学应用的步骤示意图：分析与表述问题建立模型对模型和由模型导出的解进行检验建立起对解的有效控制对问题求解方案实施不满意满意运筹学简介运筹学的主要分支：1.线性规划2.非线性规划3.动态规划4.图论与网络分析5.存贮论6.排队论7.对策论8.决策论运筹学简介一.线性规划模型的建立线性规划模型建立数学模型：线性规划模型模型的特点：线性规划模型线性规划模型线性规划模型线性规划模型线性规划模型的求解----图解法在此讨论线性规划问题的解，以下面的LP问题为例：课题的来源及意义线性规划模型的求解----图解法用Matlab求解线性规划问题命令:simpleMthd调用格式：[x,minf]=simpleMthd(A,c,b,baseVector)其中,A:约束矩阵c:目标函数系数向量b:约束右端向量baseVector:初始基向量x:目标函数取最小值时的自变量值minf:目标函数的最小值线性规划模型的求解----计算机的实现12min4zxx12121212242312.3,0xxxxstxxxx例1：用单纯形法求解线性规划问题线性规划模型的求解----计算机的实现12312412512345242312.3,,,,0xxxxxxstxxxxxxxx12min4zxx化成标准型：线性规划模型的求解----计算机的实现输入命令：A=[-12100;23010;1-1001];C=[-4-1000];b=[4;12;3];[x,minf]=simpleMthd(A,c,b,[345])所得结果：X=4.20001.20000Minf=-18线性规划模型的求解----计算机的实现例2：用大M法求解线性规划问题123min3zxxx12312313123211423.21,,0xxxxxxstxxxxx线性规划模型的求解----计算机的实现12367min3()zxxxMxx1234123561371237211423.21,,0xxxxxxxxxstxxxxxx化成标准型：线性规划模型的求解----计算机的实现输入命令：A=[1-211000;-4120-110;-2010001];C=[-3110010001000];b=[11;3;1];[x,mf]=simpleMthd(A,c,b,[467])所得结果：X=4.00001.00009.0000mf=-2线性规划模型的求解----计算机的实现其中,A:不等式约束的系数矩阵，Aeq：等式约束的系数矩阵beq:等式约束右端向量b:不等式约束右端向量Lb，ub:自变量的上下范围在MatlabR2008b求解线性规划问题的函数:linprog求解对象是：min,.TAxbfxstAeqxbeqlbxub线性规划模型的求解----计算机的实现调用格式：1）x=linprog(f,A,b),要求线性规划只存在不等式约束。2）x=linprog(f,A,b，Aeq,beq),要求线性规划存在不等式和等式约束。3）x=linprog(f,A,b，Aeq,beq,lb,ub),一般格式4）x=linprog(f,A,b，Aeq,beq,lb,ub，x0),x0为设定的初始值。5）x=linprog(f,A,b，Aeq,beq,lb,ub，x0，options),x0为设定的初始值,options来指定优化参数线性规划模型的求解----计算机的实现例3：linprog函数求解线性规划问题12min4fxx12121212242312.3,0xxxxstxxxx线性规划模型的求解----计算机的实现输入命令：f=[-4;-1];A=[-12；23；1-1；];b=[4;12;3];[x,fval,exitflag,output,lamda]=linprog(f,A,b,[],[],zeros(2,1))所得结果：Optimizationterminated.X=4.20001.20000fval=-18.0000exitflag=1output=iterations:5algorithm:`large-scale`:interiorpointcgiterations:0message：’Optimizationterminated‘线性规划模型的求解----计算机的实现线性规划建模举例线性规划建模举例线性规划建模举例线性规划建模举例线性规划建模举例线性规划建模举例线性规划建模举例灵敏度分析举例灵敏度分析举例灵敏度分析举例灵敏度分析举例课题的来源及意义特殊的线性规划模型----运输问题11x12x1nx21x22x2nx1mx2mxmnx•表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：(1)找出初始基可行解。即初始调运方案(2)进行最优检验，判别是否最优(3)若不是最优，对方案进行调整和改进，直到最优。运输问题的求解----表上作业法例1某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为8吨，A2为5吨，A3为11吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为4吨，B2为7吨，B3为6吨，B4为7吨。已知从各工厂到各销售点的单位产品的运价为表3-2所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。运输问题的求解----表上作业法问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。运输问题的求解----表上作业法运输问题的求解----表上作业法P2求解（P2）：1.给出初始调运方案两种方法来确定初始方案（1）最小元素法和沃格尔法这方法的基本思想是按单位运价的大小决定供应的先后，优先满足单价运价最小者的供销要求(1)找出初始基可行解。即初始调运方案(2)进行最优检验，判别是否最优(3)若不是最优，对方案进行调整和改进，直到最优。运输问题的求解----表上作业法运输问题的求解----表上作业法运输问题的求解----表上作业法用最小元素法给出的初始解是运输问题的基可行解，其理由为：(1)用最小元素法给出的初始解，是从单位运价表中逐次地挑选最小元素.并比较产量和销量。•当产大于销，划去该元素所在列。•当产小于销，划去该元素所在行。•然后在未划去的元素中再找最小元素，再确定供应关系。运输问题的求解----表上作业法用最小元素法给出的初始解是运输问题的基可行解，其理由为：•这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。•表中共有m行n列，总共可划(n+m)条直线。•但当表中只剩一个元素时，这时当在产销平衡表上填这个数字时，而在运价表上同时划去一行和一列。此时把单价表上所有元素都划去了，相应地在产销平衡表上填了(m+n-1)个数字。•即给出了(m+n-1)个基变量的值。•用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列。这时就出现退化。关于退化时的处理将后面加以讲述。运输问题的求解----表上作业法2.方案的最优检验和改进---闭回路法和位势法（1）闭回路法在给出调运方案的计算表上，如表1，•从每一空格出发找一条闭回路。它是以某空格为起点。用水平或垂直线向前划，当碰到一数字格时可以转90°后，继续前进，直到回到起始空格为止。闭回路如图的(a),(b),(c)等所示。•闭回路法的特点：1.闭回路的其余三个顶点均应由填有数字的格组成2.每一个空格都存在唯一一条这样的闭回路3.闭回路的形状不一定是简单的矩形最优检验标准：1.观察各个空格的检验数，若存在负检验数，说明运费还可以减少。2.若同时存在几个负检验数时，通常以绝对值最大者对应的变量为引入变量3.若存在非基变量的检验数为零，则说明最优方案不唯一。4.确定引入变量后，对其闭回路上各顶点的运量作尽可能多的调整，使其中某个数字格的运量变为0，这个格对应的变量就是退出变量。4.当同时有几个变量为0时，就发生退化，选取其中一个为退出变量，其余的需在对应格中填入0，以保持填有数字的格的个数为m+n-1个。新方案的总运费为：122元对这一方案进行最优检验。最优方案•前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。•1.当产大于销minjjiba11产销不平衡的运输问题及其求解方法•前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。•1.当产大于销minjjiba11产销不平衡的运输问题及其求解方法运输问题的数学模型可写成(P4)11(4)minmnijijijPzcx11,(1,2,,),(1,2,,)..0nijijmijjiijxaimxbjnstxnjjmiiba11增加一个假想的销地j=n+1(实际上是储存)，该销地总需要量为而在单位运价表中从各产地到假想销地的单位运为，就转化成一个产销平衡的运输问题',10inc所以这是一个产销平衡的运输问题。此时数学模型为：2.当销大于产时，可以在产销平衡表中增加一个假想的产地i=m+1，该地产量为njmijjab11在单位运价表上令从该假想产地到各销地的运价，同样可以转化为一个产销平衡的运输问题.。'1,0mjc产销平衡的运输问题•例3某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产(包括储存、维护)费用最小的决策产销不平衡的运输问题应用举例解由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足