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