优化类数学模型

优化类数学模型线性规划模型非线性规划模型整数规划模型C语言程序设计（第三版）§1最优化问题•1．1最优化问题概念•（1）最优化问题•在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。•最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。•最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。C语言程序设计（第三版）（2）变量•变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。•设问题中涉及的变量为x1,x2......xn；我们常常也用X=(x1,x2......xn)表示。C语言程序设计（第三版）（3）约束条件•在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。•例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。•用数学语言描述约束条件一般来说有两种：•等式约束条件•不等式约束条件•注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件。这两种约束条件最优化问题最优解的存在性较复杂。C语言程序设计（第三版）（4）目标函数•在最优化问题中，与变量有关的待求其极值（或最大值最小值）的函数称为目标函数。•目标函数常用表示F(x)=f(x1,x2......xn)表示。当目标函数为某问题的效益函数时，问题即为求极大值；当目标函数为某问题的费用函数时，问题即为求极小值等等。•求极大值和极小值问题实际上没有原则上的区别，因为求的极小值，也就是要求的极大值，两者的最优值在同一点取到。C语言程序设计（第三版）．2最优化问题分类•最优化问题种类繁多，因而分类的方法也有许多。可以按变量的性质分类，按有无约束条件分类，按目标函数的个数分类等等。•一般来说，变量可以分为确定性变量，随机变量和系统变量等等，相对应的最优化问题分别称为：普通最优化问题，统计最优化问题和系统最优化问题。•(1)按有无约束条件分类：无约束最优化问题，有约束最优化问题。•(2)按目标函数的个数分类：单目标最优化问题，多目标最优化问题。•(3)按约束条件和目标函数是否是线性函数分类：线性最优化问题（线性规划），非线性最优化问题（非线性规划）。•(4)按约束条件和目标函数是否是时间的函数分类：静态最优化问题和动态最优化问题（动态规划）。•C语言程序设计（第三版）．3最优化问题的求解步骤和数学模型•（1）最优化问题的求解步骤•最优化问题的求解涉及到应用数学，计算机科学以及各专业领域等等，是一个十分复杂的问题，然而它却是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢？其中最关键的是建立数学模型和求解数学模型。一般来说，应用最优化方法解决实际问题可分为四个步骤进行：C语言程序设计（第三版）求解步骤•步骤1：建立模型•提出最优化问题，变量是什么？约束条件有那些？目标函数是什么？建立最优化问题数学模型：确定变量，建立目标函数，列出约束条件——建立模型。•步骤2：确定求解方法•分析模型，根据数学模型的性质，选择优化求解方法——确定求解方法。•步骤3：计算机求解•编程序（或使用数学计算软件），应用计算机求最优解——计算机求解。•步骤4：结果分析•对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出评价——结果分析。线性规划（LinearProgramming）运筹学的一个分支，主要用于生产计划、物资运输、库存、劳动力分配以及最优设计问题等。类似于条件极值问题，只是其目标函数和约束条件都是线性函数。线性规划模型的特点1.比例性:每个决策变量对目标函数和每个约束条件右端项的“贡献”与该变量的取值成比例；2.可加性:每个决策变量对目标函数和每个约束条件右端项的“贡献”与其他变量的取值无关；3.连续性:每个决策变量的取值是连续的。线性规划模型的三个要素决策变量：根据实际问题所选择的可以控制的因素；目标函数：以线性函数形式表示所追求的目标；约束条件：决策变量需要满足的限定条件，一般是一组线性等式或不等式。C语言程序设计（第三版）二、线性规划模型的求解（一）图解法（n=3时）（二）单纯形法（三）数学软件：如LINDO软件例1某公司生产甲、乙两种产品，每吨销售后的利润分别为4000元与3000元。生产甲产品需要用A、B机器加工，加工时间分别为每吨2小时和1小时；生产乙产品需要用A、B、C三种机器加工，加工时间为每吨各1小时。若每天用于加工的机器时数分别为A机器10小时、B机器8小时、C机器7小时，问该厂每天应该生产甲、乙两种产品各多少吨才能使利润最大？划模型，则可建立如下线性规吨，利润为吨，乙设生产甲zxx21.0,0,7,8,102..,30004000max212212121xxxxxxxtsxxz甲乙资源限制设备118原料A4016原料B0412单位利润23例2某工厂在计划期内安排生产甲、乙两种产品。已知生产单位产品所需的设备台数、A、B两种原料的消耗以及单位利润如下表所示，问应该如何安排生产计划使该工厂获利最多？答案：生产甲4个，乙3个，获利为17C语言程序设计（第三版）自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。例1居民用水调度问题某市有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应．四个区每天必须得到保证的基本生活用水分别为30，70，10，10千吨，但由于水源紧张，三个水库每天最多只能分别供应50，60，50千吨自来水．由于地理位置的差别，自来水公司从各水库向各区送水所需付出的引水管理费不同(见下表，其中C水库与丁区之间没有输水管道)，其他管理费用都是450元／千吨．根据公司规定，各区用户按照统一标准900元／千吨收费．此外，四个区都向公司申请了额外用水量，分别为每天50，70，20，40千吨．该公司应如何分配供水量，才能获利最多？C语言程序设计（第三版）其他费用:450元/千吨•应如何分配水库供水量，公司才能获利最多？•若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）C语言程序设计（第三版）供应限制约束条件需求限制线性规划模型(LP)5014131211xxxx506033323124232221xxxxxxx8030312111xxx14070322212xxx3010332313xxx50102414xx目标函数3332312423222114131211230200190150190130140170220130160xxxxxxxxxxxZMin水库i向j区的日供水量为xij（x34=0）决策变量模型建立确定3个水库向4个小区的供水量C语言程序设计（第三版）)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000X2250.0000000.000000X230.00000020.000000X2410.0000000.000000X3140.0000000.000000X320.00000010.000000X3310.0000000.000000利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费24400(元)C语言程序设计（第三版）目标函数总供水量(320)总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其它费用(450)–引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290xxxxxxxxxxxZMax供应限制B,C类似处理50:A14131211xxxx10014131211xxxx问题讨论确定送水方案使利润最大需求约束可以不变C语言程序设计（第三版）)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000X2130.0000000.000000X2240.0000000.000000X230.00000010.000000X2450.0000000.000000X3150.0000000.000000X320.00000020.000000X3330.0000000.000000这类问题一般称为“运输问题”(TransportationProblem)总利润88700（元）A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030C语言程序设计（第三版）•非线性规划模型，可以用LINGO求解非线性规划（None-linearProgramming）例4板材切割问题某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出．从钢管厂进货时得到的原料钢管都是19m长．(1)现有一个客户需要50根4m、20根6m和15根8m长的钢管．应如何下料最节省?(2)零售商如果采用的切割模式太多，将会导致生产过程的复杂性，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种．此外，该客户除需要上述的三种钢管外，还需要10根5m长的钢管，应如何下料最节省?首先，应当