优化类数学模型课件

优化类数学模型

线性规划模型

非线性规划模型

整数规划模型优化类数学模型

线性规划模型

非线性规划模型

整数规划§1最优化问题1．1最优化问题概念（1）最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。

最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。§1最优化问题（2）变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。设问题中涉及的变量为x1,x2......xn；我们常常也用X=(x1,x2......xn)表示。（2）变量（3）约束条件在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。用数学语言描述约束条件一般来说有两种：等式约束条件不等式约束条件

注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件。这两种约束条件最优化问题最优解的存在性较复杂。（3）约束条件（4）目标函数在最优化问题中，与变量有关的待求其极值（或最大值最小值）的函数称为目标函数。目标函数常用表示F(x)=f(x1,x2......xn)表示。当目标函数为某问题的效益函数时，问题即为求极大值；当目标函数为某问题的费用函数时，问题即为求极小值等等。求极大值和极小值问题实际上没有原则上的区别，因为求的极小值，也就是要求的极大值，两者的最优值在同一点取到。（4）目标函数1．2最优化问题分类

最优化问题种类繁多，因而分类的方法也有许多。可以按变量的性质分类，按有无约束条件分类，按目标函数的个数分类等等。一般来说，变量可以分为确定性变量，随机变量和系统变量等等，相对应的最优化问题分别称为：普通最优化问题，统计最优化问题和系统最优化问题。

(1)按有无约束条件分类：无约束最优化问题，有约束最优化问题。

(2)按目标函数的个数分类：单目标最优化问题，多目标最优化问题。

(3)按约束条件和目标函数是否是线性函数分类：线性最优化问题（线性规划），非线性最优化问题（非线性规划）。

(4)按约束条件和目标函数是否是时间的函数分类：静态最优化问题和动态最优化问题（动态规划）。

1．2最优化问题分类

最优化问题种类繁多，因而．

3最优化问题的求解步骤和数学模型

（1）最优化问题的求解步骤

最优化问题的求解涉及到应用数学，计算机科学以及各专业领域等等，是一个十分复杂的问题，然而它却是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢？其中最关键的是建立数学模型和求解数学模型。一般来说，应用最优化方法解决实际问题可分为四个步骤进行：．

3最优化问题的求解步骤和数学模型

求解步骤

步骤1：建立模型提出最优化问题，变量是什么？约束条件有那些？目标函数是什么？建立最优化问题数学模型：确定变量，建立目标函数，列出约束条件——建立模型。步骤2：确定求解方法分析模型，根据数学模型的性质，选择优化求解方法——确定求解方法。步骤3：计算机求解编程序（或使用数学计算软件），应用计算机求最优解——计算机求解。步骤4：结果分析对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出评价——结果分析。求解步骤

步骤1：建立模型线性规划（LinearProgramming）运筹学的一个分支，主要用于生产计划、物资运输、库存、劳动力分配以及最优设计问题等。类似于条件极值问题，只是其目标函数和约束条件都是线性函数。线性规划模型的特点1.比例性:每个决策变量对目标函数和每个约束条件右端项的“贡献”与该变量的取值成比例；2.可加性:每个决策变量对目标函数和每个约束条件右端项的“贡献”与其他变量的取值无关；3.连续性:每个决策变量的取值是连续的。线性规划模型的三个要素决策变量：根据实际问题所选择的可以控制的因素；目标函数：以线性函数形式表示所追求的目标；约束条件：决策变量需要满足的限定条件，一般是一组线性等式或不等式。线性规划（LinearProgramming）二、线性规划模型的求解（一）图解法（n<=3时）（二）单纯形法（三）数学软件：如LINDO软件二、线性规划模型的求解（一）图解法（n<=3时）（二）单纯形例1某公司生产甲、乙两种产品，每吨销售后的利润分别为4000元与3000元。生产甲产品需要用A、B机器加工，加工时间分别为每吨2小时和1小时；生产乙产品需要用A、B、C三种机器加工，加工时间为每吨各1小时。若每天用于加工的机器时数分别为A机器10小时、B机器8小时、C机器7小时，问该厂每天应该生产甲、乙两种产品各多少吨才能使利润最大？例1某公司生产甲、乙两种产品，每吨销售后的利润分别为400例2某工厂在计划期内安排生产甲、乙两种产品。已知生产单位产品所需的设备台数、A、B两种原料的消耗以及单位利润如下表所示，问应该如何安排生产计划使该工厂获利最多？答案：生产甲4个，乙3个，获利为17例2某工厂在计划期内安排生产甲、乙两种产品。已知生产单位产自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求例1

居民用水调度问题某市有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应．四个区每天必须得到保证的基本生活用水分别为30，70，10，10千吨，但由于水源紧张，三个水库每天最多只能分别供应50，60，50千吨自来水．由于地理位置的差别，自来水公司从各水库向各区送水所需付出的引水管理费不同(见下表，其中C水库与丁区之间没有输水管道)，其他管理费用都是450元／千吨．根据公司规定，各区用户按照统一标准900元／千吨收费．此外，四个区都向公司申请了额外用水量，分别为每天50，70，20，40千吨．该公司应如何分配供水量，才能获利最多？例1居民用水调度问题某市有甲、乙、丙、丁四个居民区，自来其他费用:450元/千吨

应如何分配水库供水量，公司才能获利最多？

若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）其他费用:450元/千吨应如何分配水库供水量，公司才能获供应限制约束条件需求限制

线性规划模型(LP)目标函数

水库i向j区的日供水量为xij（x34=0）决策变量

模型建立确定3个水库向4个小区的供水量供应限制约束条件需求限制线性规划模型(LP)目标函数水库模型求解

OBJECTIVEFUNCTIONVALUE1)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费24400(元)模型求解OBJECTIVEFUNCTIONVALUE利目标函数

总供水量(320)>总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其它费用(450)

–引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论

确定送水方案使利润最大需求约束可以不变目标函数总供水量(320)>总需求量(300)每个水库求解OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000

X21

30.0000000.000000X2240.0000000.000000

X230.00000010.000000X2450.0000000.000000

X31

50.0000000.000000X320.00000020.000000X33

30.0000000.000000这类问题一般称为“运输问题”(TransportationProblem)总利润88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030求解OBJECTIVEFUNCTIONVALUE这类问非线性规划模型，可以用LINGO求解非线性规划模型，可以用LINGO求解非线性规划（None-linearProgramming）例4

板材切割问题

某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出．从钢管厂进货时得到的原料钢管都是19m长．(1)现有一个客户需要50根4m、20根6m和15根8m长的钢管．应如何下料最节省?(2)零售商如果采用的切割模式太多，将会导致生产过程的复杂性，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种．此外，该客户除需要上述的三种钢管外，还需要10根5m长的钢管，应如何下料最节省?非线性规划（None-linearProgramming）首先，应当确定哪些切割模式是可行的，所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合．其次，应当确定哪些切割模式是合理的．通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸．在这种合理性假设下，切割模式一共有7种，如下表首先，应当确定哪些切割模式是可行的，所谓一个切割模式，是指按优化类数学模型课件LINGO中@GIN(r);表示变量r为整数LINGO中@GIN(r);表示变量r为整数第三讲整数规划建模方法一、从现实问题到整数规划模型二、整数规划模型的求解三、整数规划的建模实例第三讲整数规划建模方法一、从现实问题到整数规划模型二、整4.1整数规划简介要求所有xj的解为整数，称为纯整数规划要求部分xj的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解4.1整数规划简介要求所有xj的解为整数，称为纯整数规4.2整数规划的分枝定界法3、求解分枝的松弛问题—定界过程设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况

4.2.1思路与解题步骤只解松弛问题1、在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程若松弛问题最优解中某个xk=bk不是整数，令bk为bk

的整数部分构造两个新的约束条件xkbk和xkbk+1，分别加于原松弛问题，形成两个新的整数规划4.2整数规划的分枝定界法3、求解分枝的松弛问题—定界4.2.2分枝定界法举例

例4.1.1

解：松弛问题的最优解为x1=2.5,x2=2,OBJ=23

由x1=2.5得到两个分枝如下：4.2.2分枝定界法举例例4.1.1解表4.2.3分枝问题的松弛解问题II的解即原整数问题的最优解（X1=3，X2=1）

可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题表4.2.3分枝问题的松弛解问题II的解即原整数问例.某厂拟用集装箱托运甲,乙两种货物。已知问：如何安排利润最大？设甲乙分别托运x1,x2箱模型建立

IP(1)-(4)称为与(IP)相对应的线性规划(LP)求解(LP)得x1=4.81,x2=1.82,z=356例.某厂拟用集装箱托运甲,乙两种货物。已知问：如何安排利润最分枝定界法(branchandboundmethod)(IP)x1*,x2*,z*(LP) x1=4.81,x2=1.82,z0=356(LP1)x1=4,x2=2.1,z0=349X1≤4X1≥5(LP2)x1=5,x2=1.57,z0=341(z*≤349定界)(LP3)x1=4,x2=2,z0=340X2≤2X2≥3(LP4)x2=3,x1=1.42,z0=327(z*≥340定界)(LP5)x2=1,x1=5.44,z0=308X2≤1(LP6)无可行解X2≥2X1≤4X1≥5分枝：分枝定界法(branchandboundmethod)设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划,任一型号汽车要生产至少80辆模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽模型求解

3）

模型中增加条件：x1,x2,x3

均为整数，重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226结果为小数，怎么办？？？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。

但必须检验它们是否满足约束条件。为什么？模型求解3）模型中增加条件：x1,x2,x3均为IP可用LINDO直接求解整数规划(IntegerProgramming,简记IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3IP的最优解x1=64