数学建模案例之线性规划--ppt课件

数学建模案例之线性规划奶制品的生产与销售1ppt课件优化问题及其一般模型：引言优化问题是人们在工程技术、经济管理和科学研究等领域中最常遇到的问题之一。例如：设计师要在满足强度要求等条件下选择材料的尺寸，使结构总重量最轻；公司经理要根据生产成本和市场需求确定产品价格，使所获利润最高；调度人员要在满足物质需求和装载条件下安排从各供应点到需求点的运量和路线，使运输总费用最低；投资者要选择一些股票,债券下注,使收益最大,而风险最小…………2ppt课件一般地，优化模型可以表述如下：min()..()0izfxstgx，i=1,2,,m这是一个多元函数的条件极值问题，其中x=[x1,x2,…,xn]。许多实际问题归结出的这种优化模型，但是其决策变量个数n和约束条件个数m一般较大，并且最优解往往在可行域的边界上取得，这样就不能简单地用微分法求解，数学规划就是解决这类问题的有效方法。引言3ppt课件数学规划模型分类:“数学规划是运筹学和管理科学中应用及其广泛的分支。在许多情况下，应用数学规划取得的如此成功，以致它的用途已超出了运筹学的范畴，成为人们日常的规划工具。”[H.P.Williams.数学规划模型的建立]。数学规划包括线性规划、非线性规划、整数规划、几何规划、多目标规划等，用数学规划方法解决实际问题，就要将实际问题经过抽象、简化、假设，确定变量与参数，建立适当层次上的数学模型，并求解。引言4ppt课件建立数学规划模型的步骤:当你打算用数学建模的方法来处理一个优化问题的时候，首先要确定寻求的决策是什么，优化的目标是什么，决策受到那些条件的限制（如果有限制的话），然后用数学工具（变量、常数、函数等）表示它们，最后用合适的方法求解它们并对结果作出一些定性、定量的分析和必要的检验。引言5ppt课件引言Step1.寻求决策，即回答什么？必须清楚，无歧义。阅读完题目的第一步不是寻找答案或者解法，而是……Step2.确定决策变量第一来源：Step1的结果，用变量固定需要回答的决策第二来源：由决策导出的变量（具有派生结构）其它来源：辅助变量（联合完成更清楚的回答）Step3.确定优化目标用决策变量表示的利润、成本等。Step4.寻找约束条件决策变量之间、决策变量与常量之间的联系。第一来源：需求；第二来源：供给；其它来源：辅助以及常识。Step5.构成数学模型将目标以及约束放在一起，写成数学表达式。6ppt课件内容：如何建立线性规划模型举例线性规划模型的求解方法要求：掌握线性规划模型的建立方法掌握利用数学软件LINDO、Matlab等求解线性规划模型的方法理解单纯形法的计算步骤重点、难点：重点：线性规划模型的建立与软件求解难点：线性规划问题的理论求解方法—单纯形法7ppt课件简介线性规划是最简单、应用最广泛的一种数学规划方法，也是应用最早的一种最优化方法；线性规划的数学模型是目标函数和全部约束式都是变量的线性函数；线性规划是学习运筹学的首要课程之一；1947年，丹茨格（Dantzig）提出了单纯形法，使线性规划的算法趋于成熟；在数学上讲，线性规划问题就是研究一类条件极值问题，即在一组线性约束条件（包括等式及不等式约束）下，找出一个线性函数的最大值或最小值。8ppt课件例1：加工奶制品的生产计划一奶制品加工厂用牛奶生产A1，A2两种奶制品，一桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2全部能够售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能够得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。试为该厂制定一个生产计划，使每天获利最大?并进一步讨论以下三个附加问题：1）若用35元可以买到一桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时多少元？3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？9ppt课件问题分析企业内部的生产计划有各种不同的情况。空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划10ppt课件问题分析1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤每天50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大•35元可买到1桶牛奶，买吗？若买，每天最多买多少?•可聘用临时工人，付出的工资最多是每小时几元?•A1的获利增加到30元/公斤，应否改变生产计划?1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤11ppt课件模型构成引入决策变量x1桶牛奶生产A1，x2桶牛奶生产A2（每天）目标函数（每天获利）生产A1获利：24×3x1生产A2获利：16×4x2每天获利总额：z=72x1+64x2约束条件原料供应：x1+x2≤50劳动时间：12x1+8x2≤480加工能力：3x1≤100非负约束：x1,x2≥012ppt课件模型构成数学模型：121212112max7264..5012848031000,0zxxstxxxxxxxLP模型13ppt课件线性规划模型具有的三条性质比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数xi取值连续14ppt课件LP问题的一般概念1.LP模型的一般形式求一组决策变量x1,x2,…,xn的值，使其满足约束条件：并使目标函数取得最大（或最小)值，其中aij,bi,cj为已知量。111(),1,2,...,;(),1,...,;(),1,...,.nijjijnijjijnijjijIaxbilIIaxbiltIIIaxbitm1njjjzcx15ppt课件LP问题的一般概念2.标准形式其中min,..,0.TzcxstAxbx121212(),(,,...,),(,,...,),(,,...,),0,().TTijmnnnTmAaxxxxccccbbbbbrankAmn且16ppt课件LP问题的一般概念3.将一般线性规划模型转化为标准形例题：将下述LP模型转化成标准形式解：转化分为目标函数、大于等于约束、小于等于约束和自由约束变量几个不同部分。12341234123412341234max457..2126334325,,,0zxxxxstxxxxxxxxxxxxxxxx17ppt课件LP问题的一般概念目标函数maxz=4x1+5x2+7x3-x4minz1=-4x1-5x2-7x3+x4约束条件大于等于约束x1+x2+2x3-x4≥1添加剩余变量x5≥0x1+x2+2x3-x4-x5=1小于等于约束2x1-6x2+3x3+x4≤-3添加松弛变量x6≥0-2x1+6x2-3x3-x4-x6=3自由变量（无）12341234123412341234max457..2126334325,,,0zxxxxstxxxxxxxxxxxxxxxx18ppt课件LP问题的一般概念化成标准型为：12341234123412341234max457..2126334325,,,0zxxxxstxxxxxxxxxxxxxxxx原始形式1123412345123461234123456min457..2126334325,,,,,0zxxxxstxxxxxxxxxxxxxxxxxxxx标准形式19ppt课件LP问题的一般概念4.单纯形法G.B.Dantzig的单纯形法（Simplexmethod）是一个顶点迭代算法，即从一个顶点出发，沿着凸多面体的棱迭代到另一个顶点，使目标函数值下降（至少不升），由顶点个数的有限性，可以证明经过有限次迭代一定可以求得最优解或者判定该问题无最优解，这就是单纯形法的基本思想。而几何上一个的顶点对应在代数上的一个基可行解，因此，单纯形法求解线性规划问题只需要关心基可行解。20ppt课件LP问题的一般概念基本理论参见任何一本运筹学教材上的相关内容，下面仅以一个例子说明单纯形法的步骤。利用单纯形法求解下述LP问题。1212121212max10001500..953504520025150,0wxxstxxxxxxxx21ppt课件LP问题的一般概念Step1.将一般的LP问题划成标准形式引入松弛变量x3，x4，x5将原问题化成标准形式3453412121212125min(10001500)..953504520025150,,0,,zxxsxxxxxxtxxxxxxxx22ppt课件LP问题的一般概念Step2.建立初始单纯形表，求出初始的基本可行解x(0)及对应的目标函数值z0建立初始单纯形表求出基本可行解x(0)=(0,0,350,200,150)T，求出目标函数值z0=0cj→-1000-1500000系数基变量x1x2x3x4x5b0x3951003500x4450102000x525001150检验数rj-1000-1500000023ppt课件LP问题的一般概念Step3.判断现行解是否是最优解。若是，计算结束；否则转第4步。判断方法：计算检验数rj=cj-zj，其中zj=cBTaij，j=1,2,…,n.若所有的rj≥0，j=1,2,…,n，则现行解为最优解。检验数中r10，r20，上面的结果x(0)不是最优解。cj→-1000-1500000系数基变量x1x2x3x4x5b0x3951003500x4450102000x525001150检验数rj-1000-1500000024ppt课件LP问题的一般概念Step4.确定进基向量计算min{rj|rj0}=rk，则xk进基；因min{rj|rj0}=r2=-1500，所以进基变量为x2。cj→-1000-1500000系数基变量x1x2↓x3x4x5b0x3951003500x4450102000x525001150检验数rj-1000-1500000025ppt课件LP问题的一般概念Step5.确定主元素和离基向量若aik≤0，i=1,2,…,m，则LP问题的可行域R无界，LP问题没有优先的最优值，计算结束；否则计算min{bi/aik|aik0}=bl/ark，此时主元素为ark，xl应离基。因为150/5200/5350/5，所以min{bi/ai2|ai20}=b3/a32=3，主元素为a32=5，原来的基变量x5离基.cj→-1000-1500000系数基变量x1x2↓x3x4x5b0x3951003500x4450102000←x525001150检验数rj-1000-1500000026ppt课件LP问题的一般概念Step6.以ark为主元素，进行换基计算，即进行一次Gauss消元计算，求得一个新的基本可行解，然后返回Step3。将xk所对应的列向量化为单位向量，使主元素处为1，