优化模型特殊的整数规划课件

在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型从徐州到宿迁怎么走最快到达Find the optimal solution寻找最优解Jiang数学建模优化模型从徐州到宿迁怎么走最快到达？Find t1在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型points1、什么是优化模型什么是优化模型 1.1 优化模型的问题及方法优化模型的问题及方法 1.2 引例及优化模型的解题步骤引例及优化模型的解题步骤2、无约束和有约束的优化模型无约束和有约束的优化模型3、优化问题的常用方法优化问题的常用方法 3.1 线性规划线性规划 3.2 整数规划整数规划3.2.1 01规划规划 3.3 非线性规划非线性规划 3.4 多目标规划多目标规划数学建模优化模型points2在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型什么是优化模型？什么是优化模型？优化模型优化模型主要用来解决主要用来解决决策问题决策问题的模型，决策是有目的的模型，决策是有目的的选择行为，即是从一系列可选择的方案中选择能达到自的选择行为，即是从一系列可选择的方案中选择能达到自己目的的方案。己目的的方案。将这个目的定量成一个函数表达式，这个函数表达式称将这个目的定量成一个函数表达式，这个函数表达式称为为目标函数目标函数。决策通常考虑一定的限制，这些限制称为决策通常考虑一定的限制，这些限制称为约束条件。约束条件。最优化已经广泛的渗透到工程、经济、电子技术等领域最优化已经广泛的渗透到工程、经济、电子技术等领域 计算机技术的出现，使得数学家研究出了许多最优化方法计算机技术的出现，使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问题。和算法用以解决以前难以解决的问题。数学建模优化模型什么是优化模型？3在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型优化问题主要讨论的问题无约束极值问题一元与多元函数无约束优化线性与非线性有约束优化静态与动态优化优化问题的方法1、函数极值（微积分）2、线性规划3、整数规划（01规划）4、非线性规划5、动态规划6、多目标规划 7、对策论有约束无约束数学建模优化模型优化问题主要讨论的问题优化问题的方法有约4在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型引例引例 某机床厂生产甲、乙两种机床，每台销售后的利润分别为某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与元与3000元。元。生产甲机床需用机器生产甲机床需用机器A,B加工，加工时间分别为每台加工，加工时间分别为每台2小时和小时和1小时；生产乙机小时；生产乙机床需用三种机器床需用三种机器A,B,C加工，加工时间为每台各一小时。若每天可用于加工的加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为机器机器时数分别为机器10小时、机器小时、机器8小时和机器小时和机器7小时，问该厂应生产甲、乙机小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？床各几台，才能使总利润最大？机床机床机器机器甲甲乙乙工作时数工作时数A2110B118C17利润利润40003000数学建模优化模型引例 某机床厂生产甲、乙两种机床，每台5在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型解：解：设该厂生产甲、乙机床设该厂生产甲、乙机床x1,x2台时利润最大。台时利润最大。使利润最大，建立目标函数使利润最大，建立目标函数各机床工作时长有限制，列出约束条件各机床工作时长有限制，列出约束条件 上面由目标函数和约束条件确定的即是一个简单的优化模型，由于目上面由目标函数和约束条件确定的即是一个简单的优化模型，由于目标函数和约束条件均是线性的，所以称为标函数和约束条件均是线性的，所以称为线性规划线性规划问题。问题。数学建模优化模型解：设该厂生产甲、乙机床x1,x2台时利6在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型 目标函数为一组平行直线，其在可目标函数为一组平行直线，其在可行域（黄色部分）内有最大值时，行域（黄色部分）内有最大值时，取点（取点（2,6），最大值为），最大值为2600001、图解法图解法2、Matlab编程编程f=4000;3000;A=2 1;1 1;0 1;b=10;8;7;lb=zeros(2,1);x,fval,exitflag,output,lambda=linprog(f,A,b,lb)数学建模优化模型 目标函数为一组平行直线，其在7在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型 由引例可以总结由引例可以总结运用最优化方法解决最优化问题的一般方法步骤如下：运用最优化方法解决最优化问题的一般方法步骤如下：前期分析：分析问题，找出要解决的目标，约束条件，并前期分析：分析问题，找出要解决的目标，约束条件，并 确立最优化的目标。确立最优化的目标。定义变量，建立最优化问题的数学模型，列出目标函数和定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。约束条件。针对建立的模型，选择合适的求解方法或数学软件。针对建立的模型，选择合适的求解方法或数学软件。编写程序，利用计算机求解。编写程序，利用计算机求解。对结果进行分析，讨论诸如：结果的合理性、正确性，算对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。法的收敛性，模型的适用性和通用性，算法效率与误差等。数学建模优化模型 由引例可以总结8在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型无约束的优化问题无约束的优化问题Eg.有边长为有边长为3m的正方形铁板，在四个角剪去相等的正方形的正方形铁板，在四个角剪去相等的正方形 以制成方形无盖水槽，问如何剪法使水槽的容积最大？以制成方形无盖水槽，问如何剪法使水槽的容积最大？解：设减去正方形的边长为解：设减去正方形的边长为x，则水槽容积为，则水槽容积为：建立无约束优化模型建立无约束优化模型 无约束优化模型通常用无约束优化模型通常用求导求极值求导求极值的方法，由于人工计算的方法，由于人工计算较为复杂，这里我们用较为复杂，这里我们用软件软件进行求解：进行求解：数学建模优化模型无约束的优化问题建立无约束优化模型 9在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型先编写先编写M文件文件fun0.m如下如下:function f=fun0(x)f=-(3-2*x).2*x;主程序为主程序为wliti2.m:x,fval=fminbnd(fun0,0,1.5);xmax=x fmax=-fval运算结果为运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边即剪掉的正方形的边长为长为0.5m时水槽的容积最大时水槽的容积最大,最大容积为最大容积为2m3.数学建模优化模型先编写M文件fun0.m如下:运算结果为10在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型有约束的优化问题的数学模型有约束的优化问题的数学模型一般形式为：为目标函数，即是对目标函数的约束条件数学建模优化模型有约束的优化问题的数学模型 为目标11在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型下面介绍有约束优化问题的几种常用方法下面介绍有约束优化问题的几种常用方法线性规划线性规划1、概念概念 线性规划是研究目标函数与约束条件均为线性的一类优化线性规划是研究目标函数与约束条件均为线性的一类优化 问题的数问题的数学方法学方法。2、基本结构基本结构2.1决决策策变变量量 未未知知数数。它它是是通通过过模模型型计计算算来来确确定定的的决决策策因因素素。又又分分为为实实际际变变量量求求解解的的变变量量和和计计算算变变量量，计计算算变变量量又又分分松松弛弛变变量（上限）和人工变量（下限）。量（上限）和人工变量（下限）。2.2目目标标函函数数目目标标的的数数学学表表达达式式。目目标标函函数数是是求求变变量量的的线线性性函函数数的极大值和极小值这样一个极值问题。的极大值和极小值这样一个极值问题。2.3约束条件约束条件实现目标的制约因素。它包括：客观约束条件、主实现目标的制约因素。它包括：客观约束条件、主观约束条件和非负限制观约束条件和非负限制数学建模优化模型下面介绍有约束优化问题的几种常用方法12在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型线性规划线性规划3、标准模型、标准模型左式的决策变量为左式的决策变量为x；目标函数为极大值函数，也可是极小值即目标函数为极大值函数，也可是极小值即min；约束；约束条件不止一个且均为线性，这个基本的线性规划模型包含了这三个要条件不止一个且均为线性，这个基本的线性规划模型包含了这三个要素。素。单从模型的形式上不容易理解，下面结合实例加深记忆和理解。单从模型的形式上不容易理解，下面结合实例加深记忆和理解。求和求和符号符号展开展开数学建模优化模型线性规划左式的决策变量为x；目标函数为极13在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型4、例子例子 设某工厂有甲、乙、丙、丁四个车间，生产设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品。根据机床性能和以前的生产情况，得知每六种产品。根据机床性能和以前的生产情况，得知每单位产品所需车间的工作小时数、每个车间在一个季度工单位产品所需车间的工作小时数、每个车间在一个季度工作小时的上限以及单位产品的利润，如下表所示作小时的上限以及单位产品的利润，如下表所示(例如，例如，生产一个单位的生产一个单位的A产品，需要甲、乙、丙三个车间分别工产品，需要甲、乙、丙三个车间分别工作作1小时、小时、2小时和小时和4小时小时)问：每种产品各应该每季度生产多少，才能使这个工厂每问：每种产品各应该每季度生产多少，才能使这个工厂每季度生产利润达到最大季度生产利润达到最大。数学建模优化模型4、例子14在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型生产单位生产单位产品所需产品所需车间的工车间的工作小时数作小时数 ABCDEF每个车间每个车间一个季度一个季度工作小时工作小时的上限的上限甲甲111323500乙乙255500丙丙425500丁丁138500利润利润(百元百元)4.02.45.55.04.58.5数学建模优化模型生产单位产品所需车间的工作小时数 ABC15在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型这是一个典型的最优化问题，属线性规划。这是一个典型的最优化问题，属线性规划。假设：产品合格且能及时销售出去；工作无等待情况等假设：产品合格且能及时销售出去；工作无等待情况等 变量说明：变量说明：xj：第：第j种产品的生产量（种产品的生产量（j=1,2,6）aij：第：第i车间生产单位第车间生产单位第j种产品所需工作小时数种产品所需工作小时数 （i=1,2,3,4;j=1,2,6）bi：第：第i车间的最大工作上限车间的最大工作上限 cj：第：第j种产品的单位利润种产品的单位利润 则：则：cjxj为第为第j种产品的利润总额；种产品的利润总额；aijxj表示第表示第i车间生产第车间生产第j种产品所花时间总数；种产品所花时间总数；数学建模优化模型这是一个典型的最优化问题，属线性规划。16在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型为使总利润最大，可根据上面的决策变量确定其目标函数为：s.t.每个车间一季度的工作时长有上限：s.t.对于第j个车间，每种产品均不能大于其生产上限：数学建模优化模型为使总利润最大，可根据上面的决策变量确定17在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型整数规划整数规划1、概述、概述最优化问题中的所有变量均为整数时，这类问题称最优化问题中的所有变量均为整数时，这类问题称为整数规划问题。为整数规划问题。如果线性规划中的所有变量均为整数时，称这类问如果线性规划中的所有变量均为整数时，称这类问题为线性整数规划问题。题为线性整数规划问题。整数规划可分为线性整数规划和非线性整数规划整数规划可分为线性整数规划和非线性整数规划，以及混合整数规划等。以及混合整数规划等。如果决策变量的取值要么为如果决策变量的取值要么为0，要么为，要么为1，则这样的，则这样的规划问题称为规划问题称为01规划。规划。数学建模优化模型整数规划18在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型2、基本模型、基本模型 整数规划要求所有的变量均为整数，所以目标函数形式与优化类问题的模型相同，只是在约束条件上添加条件：决策变量为整数，具体形式如下：数学建模优化模型2、基本模型19在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型3、通常用整数规划方法求解的问题、通常用整数规划方法求解的问题 集装箱运货问题集装箱运货问题 资源分配问题资源分配问题 产品生产问题产品生产问题 等等等等变量为整数变量为整数4、整数规划的特点、整数规划的特点（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。整数规划无可行解。有可行解（当然就存在最优解），但最优解值变差。有可行解（当然就存在最优解），但最优解值变差。（ii）整数规划最优解不能按照实数最优解简单取整而获得。整数规划最优解不能按照实数最优解简单取整而获得。数学建模优化模型3、通常用整数规划方法求解的问题变量为整20在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型特殊的整数规划特殊的整数规划01规划规划1、模型介绍、模型介绍 型整数规划是整数规划中的特殊情形，它的变量仅取型整数规划是整数规划中的特殊情形，它的变量仅取值值0或或1。这时称为。这时称为 变量，或称二进制变量。仅取值变量，或称二进制变量。仅取值0或或1这个条件可由下述约束条件：这个条件可由下述约束条件：x取取0或或1.2、基本模型、基本模型限制变量取0和1数学建模优化模型特殊的整数规划01规划2、基本模型21在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型3、问题举例、问题举例背包问题背包问题将下列物品装入包中，使包的利用价值最大。将下列物品装入包中，使包的利用价值最大。背包可再装入背包可再装入8单位重量，单位重量，10单位体积物品。单位体积物品。物品名称重量体积价值1书52202摄像头31303枕头14104休闲食品23185衣物4515数学建模优化模型3、问题举例物品名称重量体积价值1书5222在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型分析分析：显然，从多种不同的装包方案中选择使包的利用价值最大的方案，显然，从多种不同的装包方案中选择使包的利用价值最大的方案，这是一个优化类问题，目标函数即装入价值最大，但是装入哪种物品这是一个优化类问题，目标函数即装入价值最大，但是装入哪种物品需要讨论，为避免这种讨论，我们引进需要讨论，为避免这种讨论，我们引进01变量进行约束，具体如下：变量进行约束，具体如下：为方便表示，我们再引入变量，为方便表示，我们再引入变量，ai表示第表示第i种物品的价值，种物品的价值，bi表示第表示第i种物种物品的质量，品的质量，ci表示第表示第i种物品的体积，种物品的体积，k表示最大质量，表示最大质量，m表示最大体积。表示最大体积。这样，我们便可列出以总价值最大的目标函数：这样，我们便可列出以总价值最大的目标函数：数学建模优化模型分析：显然，从多种不同的装包方案中选择使23在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型下面是对目标函数的约束：装入质量不大于最大质量，装入质量不大于最大质量，装入体积不大于最大体积，装入体积不大于最大体积，则约束条件表示为则约束条件表示为：上面便是一个简单的上面便是一个简单的01规划规划实例。实例。01规划其最大的好处规划其最大的好处就是避免了分类讨论，将多种就是避免了分类讨论，将多种情况用情况用0和和1来约束，统一起来来约束，统一起来讨论。讨论。01规划中规划中0和和1应是对应是对立关系的变量，其所表示量可立关系的变量，其所表示量可以自己定义，如一张纸上有两以自己定义，如一张纸上有两种颜色红和黄，可以定义红色种颜色红和黄，可以定义红色为为0黄色为黄色为1，同样可以定义黄，同样可以定义黄色为色为0，黄色为，黄色为1进行讨论。进行讨论。在在优化问题中适当的选取优化问题中适当的选取01变变量可以大大减小讨论的情况，量可以大大减小讨论的情况，使模型变得简洁。使模型变得简洁。数学建模优化模型下面是对目标函数的约束：上面便是24在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型非线性规划非线性规划如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。性规划问题。对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：几点：a.确定供选方案确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。示它们。b.提出追求目标提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。数学关系式。c.给出价值标准给出价值标准：在提出要追求的目标之后，要确立所考虑目标的：在提出要追求的目标之后，要确立所考虑目标的“好好”或或“坏坏”的价值标准，并用某种数量形式来描述它。的价值标准，并用某种数量形式来描述它。d.寻求限制条件寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。通常用变量之间的一些不等式或等式来表示。数学建模优化模型非线性规划25在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型非线性规划非线性规划线性规划与非线性规划的区别线性规划与非线性规划的区别如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。解存在）则可能在其可行域的任意一点达到。在引例中，该线性规划在（在引例中，该线性规划在（2,6）处去到最值，（）处去到最值，（2,6）为其边界点，而）为其边界点，而在非线性规划中，比如一元三次函数对自变量和因变量均有限制，来在非线性规划中，比如一元三次函数对自变量和因变量均有限制，来讨论极值问题，此时最优解可能在驻点处取得。讨论极值问题，此时最优解可能在驻点处取得。由于这种不确定性，非线性规划问题还没有一种系统的解法，往往认为由于这种不确定性，非线性规划问题还没有一种系统的解法，往往认为得到满意解就算得到结果，一般说来，解非线性规划要比解线性规划得到满意解就算得到结果，一般说来，解非线性规划要比解线性规划问题困难得多。问题困难得多。非线性规划目前还没有适于各种问题的一般算法，非线性规划目前还没有适于各种问题的一般算法，各各个方法都有自己特定的适用范围，线性规划问题解法已经比较成熟了。个方法都有自己特定的适用范围，线性规划问题解法已经比较成熟了。单纯形法单纯形法数学建模优化模型非线性规划单纯形法26在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型多目标规划多目标规划1、概述、概述 在决策过程中，决策者想同时达到多个目标而选择最佳在决策过程中，决策者想同时达到多个目标而选择最佳方案，属于优化范畴，我们称这个过程称为方案，属于优化范畴，我们称这个过程称为多目标规划多目标规划，直观来讲，即目标函数有多个（一般两个）的优化问题。直观来讲，即目标函数有多个（一般两个）的优化问题。现实生活中，常用到多目标规划的问题很多，比如在投资现实生活中，常用到多目标规划的问题很多，比如在投资问题中，要求投资尽量少且获利尽量多；生产问题中，要问题中，要求投资尽量少且获利尽量多；生产问题中，要求工作量较少而产量尽量大；又如在前面的背包问题中，求工作量较少而产量尽量大；又如在前面的背包问题中，如果加上使占包的空间尽量小（即体积）且价值量尽量大，如果加上使占包的空间尽量小（即体积）且价值量尽量大，就也是一个多目标规划问题。就也是一个多目标规划问题。多目标规划的目标函数往往是对立的关系，所以在解答时多目标规划的目标函数往往是对立的关系，所以在解答时也往往得到满意解而非最优解。也往往得到满意解而非最优解。数学建模优化模型多目标规划27在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型2、例子、例子投资问题投资问题 某公司在一段时间内有某公司在一段时间内有a(亿元亿元)的资金可的资金可用于建厂投资。若可供选择的项目记为用于建厂投资。若可供选择的项目记为1,2,m。而且一旦对第。而且一旦对第i个项目投资就用个项目投资就用去去ai亿元；而这段时间内可得收益亿元；而这段时间内可得收益ci亿元。亿元。问如何确定问如何确定最佳的投资方案最佳的投资方案？最佳投资方案：最佳投资方案：投资尽量少，投资尽量少，收益尽量多收益尽量多数学建模优化模型2、例子最佳投资方案：28在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型分析分析：这里引进这里引进01变量用来变量用来标记是否投资第标记是否投资第i个项目，具体个项目，具体如下：如下：使总收益最大建立目标函数：使总收益最大建立目标函数：总资金不超过总资金不超过a确定约束条件：确定约束条件：使总投资最少建立目标函数：使总投资最少建立目标函数：数学建模优化模型分析：这里引进01变量用来标记是否投资29在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型说明说明优化模型通常有基本模型和基本问题，在解决问优化模型通常有基本模型和基本问题，在解决问题时要说明选用模型的原因，且要具体问题具体题时要说明选用模型的原因，且要具体问题具体分析。分析。灵活选择决策变量并列出目标函数，在解决相同灵活选择决策变量并列出目标函数，在解决相同问题时，模型越简洁越好，以降低运算复杂度。问题时，模型越简洁越好，以降低运算复杂度。优化模型的关键在于确定约束条件，要充分挖掘优化模型的关键在于确定约束条件，要充分挖掘题目中的信息，缺少一个约束，模型都是不成功题目中的信息，缺少一个约束，模型都是不成功的。的。数学建模优化模型说明30在生活中竞赛，在竞赛中生活在生活中竞赛，在竞赛中生活数学建模优化模型谢谢观看谢谢观看数学建模优化模型31