《优化问题离散模型(本科)》由会员分享，可在线阅读，更多相关《优化问题离散模型(本科)（46页珍藏版）》请在金锄头文库上搜索。
1、2006年上海市数学建模竞赛培训讲座：2006.09.09优化问题优化问题- -离散模型离散模型 一.一. 几个常见的离散优化模型几个常见的离散优化模型 二.二.二二. .非线性整数规划模型非线性整数规划模型- -选址模型选址模型三三.三三. 混合混合整数规划模型整数规划模型- -工厂选址问工厂选址问题题四四. 0-1. 0-1规划（布尔规划规划（布尔规划)-)-课程表问题课程表问题 华东理工大学华东理工大学 鲁习文鲁习文2006年上海市数学建模竞赛培训讲座：2006.09.091. 1. 线性整数规划模型（整数规划）线性整数规划模型（整数规划）2. 2. 运输模型运输模型3. 3. 非线性整
2、数规划模型非线性整数规划模型4. 0-14. 0-1规划模型（布尔规划模型）规划模型（布尔规划模型）5. 5. 混合整数规划模型混合整数规划模型一一. . 几个常见的离散优化模型几个常见的离散优化模型2006年上海市数学建模竞赛培训讲座：2006.09.091. 1. 线性整数规划模型（整数规划）线性整数规划模型（整数规划）2006年上海市数学建模竞赛培训讲座：2006.09.092. 2. 运输模型运输模型2006年上海市数学建模竞赛培训讲座：2006.09.093. 3. 非线性整数规划模型非线性整数规划模型（1 1）（2 2）2006年上海市数学建模竞赛培训讲座：2006.09.094.
3、 0-14. 0-1规划模型（布尔规划模型）规划模型（布尔规划模型）（1 1）（2 2）2006年上海市数学建模竞赛培训讲座：2006.09.095. 5. 混合整数规划模型混合整数规划模型（1 1）（2 2）2006年上海市数学建模竞赛培训讲座：2006.09.09二二. .非线性整数规划模型非线性整数规划模型q 选址模型选址模型 1. 1. 引言引言 2. 2. 选址问题的类型选址问题的类型3. 3. 单源连续型选址问题的模型及求解单源连续型选址问题的模型及求解 4. 4. 多源连续型选址问题多源连续型选址问题 5. 5. 推广与讨论推广与讨论2006年上海市数学建模竞赛培训讲座：2006
4、.09.091. 1. 引引 言言 这类问题很实际意义，例如这类问题很实际意义，例如 仓库选址：给定一个公司的生产工厂和仓库选址：给定一个公司的生产工厂和 用户的位置，为一个新仓库用户的位置，为一个新仓库 选择一个最优地址。选择一个最优地址。 我们要考虑的最优选址问题的主要是指：我们要考虑的最优选址问题的主要是指：已知一些现有设施的位置，要求确定一个或已知一些现有设施的位置，要求确定一个或几个新设施的地址。几个新设施的地址。2006年上海市数学建模竞赛培训讲座：2006.09.09 图书馆选址图书馆选址 ：某市要造一个新的图书馆：某市要造一个新的图书馆或其它民用设施，为某一特定地区服务，或其它
5、民用设施，为某一特定地区服务，试为该图书馆选择最优地址等等试为该图书馆选择最优地址等等 电厂选址：一座新的发电厂（变电所）要向电厂选址：一座新的发电厂（变电所）要向一特定地区供电，如何选择发电厂的最优地址。一特定地区供电，如何选择发电厂的最优地址。现有设施：终点，新设施：源现有设施：终点，新设施：源2006年上海市数学建模竞赛培训讲座：2006.09.092. 2. 选址问题的类型选址问题的类型 （2 2）从设施（源）的可能位置来分）从设施（源）的可能位置来分 连续型选址问题连续型选址问题 离散型选址问题离散型选址问题（1 1） 从新设施的个数来分从新设施的个数来分 单单源选址问题：源选址问题
6、：单单设施选址问题设施选址问题 多多源选址问题：源选址问题：多多设施选址问题设施选址问题 选址选址分配问题分配问题2006年上海市数学建模竞赛培训讲座：2006.09.09 单源连续型单源连续型选址问题选址问题 多源连续型多源连续型选址问题选址问题 单源离散型单源离散型选址问题选址问题 多元离散型多元离散型选址问题选址问题（3 3） 从新设施的个数和位置分从新设施的个数和位置分2006年上海市数学建模竞赛培训讲座：2006.09.093.单源连续型选址问题单源连续型选址问题某公司要建立一个产品加工厂为十家零售店服务某公司要建立一个产品加工厂为十家零售店服务（提供产品），已有下列基本数据：（提供
7、产品），已有下列基本数据： 问题的提出：问题的提出：店号店号 位置位置 单位货物通过单单位货物通过单 需求量需求量 位距离的运价位距离的运价 1（10，40） 0.025 10 2（50，100） 0.030 202006年上海市数学建模竞赛培训讲座：2006.09.093. （20，80） 0.030 254.（60，20） 0.040 155.（90，70） 0.040 306.（50，10） 0.020 257.（60，40） 0.020 258.（70，70） 0.025 209.（30，10） 0.035 1010.（40，90） 0.030 20要求确定工厂（源）应建在何处，使得从
8、工厂向要求确定工厂（源）应建在何处，使得从工厂向十个零售店运货的总运费最小十个零售店运货的总运费最小2006年上海市数学建模竞赛培训讲座：2006.09.09 建立模型建立模型 关于上述问题的求解已有研究：关于上述问题的求解已有研究：定理：定理： 为为 问题（问题（A）的最优的最优 模型模型求解求解需建工厂（仓库）的位置坐标。需建工厂（仓库）的位置坐标。2006年上海市数学建模竞赛培训讲座：2006.09.09因为因为 这里这里 , 所以所以 2006年上海市数学建模竞赛培训讲座：2006.09.09形式上解出形式上解出 x x 和和 y y，这提示我们有如下的迭代算法这提示我们有如下的迭代算
9、法 解此方程组可得：解此方程组可得： 2006年上海市数学建模竞赛培训讲座：2006.09.09其中其中 为初始点，通常取为为初始点，通常取为 的的加权重心：加权重心： 2006年上海市数学建模竞赛培训讲座：2006.09.09已有研究表明采用上述迭代方法能迅速收敛已有研究表明采用上述迭代方法能迅速收敛于最优解于最优解 。将该方法应用于上述问题。将该方法应用于上述问题即可求出其近似最优解（迭代即可求出其近似最优解（迭代7 7次）次） 讨论：讨论： 若零售店的需求量发生改变，例如若零售店的需求量发生改变，例如 则则2006年上海市数学建模竞赛培训讲座：2006.09.09 若单位运价若单位运价
10、发生改变，例如发生改变，例如 则则不管规模多大的单源选址问题不管规模多大的单源选址问题 ，求解都，求解都十分容易。十分容易。 2006年上海市数学建模竞赛培训讲座：2006.09.094. 多源连续型选址问题多源连续型选址问题 一般形式：将已知设施（位置）称为一般形式：将已知设施（位置）称为“终点终点” 已知：已知： 各个终点的位置各个终点的位置 各个终点的需要量各个终点的需要量 有关区域内的运价有关区域内的运价 确定：确定： 源（新设施）的个数源（新设施）的个数 各个源的位置各个源的位置 问题的提出：问题的提出：2006年上海市数学建模竞赛培训讲座：2006.09.09注：注： 这个问题不再
11、容易，可以说相当棘手，这个问题不再容易，可以说相当棘手， 这是因为既要求出源的个数和位置还要这是因为既要求出源的个数和位置还要 对终点进行分配。对终点进行分配。 可以先假定源的个数已知，再求最优选址。可以先假定源的个数已知，再求最优选址。 将终点（已知设施）划分给各个源（新将终点（已知设施）划分给各个源（新 设施）的情况设施）的情况 各个源（新设施）的容量各个源（新设施）的容量 （例如：某地区变压器的选址与分配问题）（例如：某地区变压器的选址与分配问题） 2006年上海市数学建模竞赛培训讲座：2006.09.09 建立数学模型建立数学模型 和分配问题，然后对源的不同数目进行和分配问题，然后对源
12、的不同数目进行考察，再从中选取最好的，即使这样做，考察，再从中选取最好的，即使这样做，精确求解也很困难，尽管如此，目前有精确求解也很困难，尽管如此，目前有些启发式算法。些启发式算法。 在建立模型之前，还是以前述例子来说明在建立模型之前，还是以前述例子来说明现在要建现在要建m m个工厂（仓库）来为个工厂（仓库）来为1010个零售点服个零售点服务，为了方便起见，对建模做如下假设：务，为了方便起见，对建模做如下假设：2006年上海市数学建模竞赛培训讲座：2006.09.09H H1 1：各源许可的容量不受限制各源许可的容量不受限制H H2 2：单位运价与源的总输出量无关单位运价与源的总输出量无关H
13、H3 3：每个终点的需求量由一个源向其供应每个终点的需求量由一个源向其供应 这三个假设是比较合情合理这三个假设是比较合情合理的。的。假定源的个数为假定源的个数为m，此时总费用为此时总费用为: 2006年上海市数学建模竞赛培训讲座：2006.09.09其中其中 个源的资本折旧费和经费管理费，个源的资本折旧费和经费管理费， 个源向给定的终点供货的最低费用。个源向给定的终点供货的最低费用。一般情形一般情形： 2006年上海市数学建模竞赛培训讲座：2006.09.09模型检验模型检验 是容易得到的，一般多为线性是容易得到的，一般多为线性 情形，并且情形，并且下面主要讨论计算下面主要讨论计算 ，假设，假
14、设 这样，计算这样，计算 的模型如下：的模型如下： 2006年上海市数学建模竞赛培训讲座：2006.09.09模型（模型（B B）约束根据假设约束根据假设H H3 3而来。因为每个源而来。因为每个源的容量是不受限制的，所以每个终点的需求量的容量是不受限制的，所以每个终点的需求量应由一个可使总费用最小的源来供应。应由一个可使总费用最小的源来供应。2006年上海市数学建模竞赛培训讲座：2006.09.09 模型求解模型求解 分析：对于满足模型（分析：对于满足模型（B）约束的一组固定值，我们约束的一组固定值，我们 总可得到一组迭代方程，它在形式上与单源选总可得到一组迭代方程，它在形式上与单源选 址问
15、题一样，此时有：址问题一样，此时有： 2006年上海市数学建模竞赛培训讲座：2006.09.09其中其中 初始点一般如下选取：初始点一般如下选取： 2006年上海市数学建模竞赛培训讲座：2006.09.09对对于于一一组组给给定定的的 之之值值，可可以以根根据据式式（I I）和（和（）求出）求出为了取得上述模型的最小值，就要讨论为了取得上述模型的最小值，就要讨论 的各种取值分别进行求解，这样做可行吗？的各种取值分别进行求解，这样做可行吗？ 的取值有多少组：的取值有多少组：S(n,m) 是第二类是第二类Stirling 数，数，例如当例如当 m2, n=10 时，时，S(10,2)=511, 此
16、时此时我们我们 要解要解511个单源选址问题，个单源选址问题，有了计算机，有了计算机，2006年上海市数学建模竞赛培训讲座：2006.09.09还还比较可行，但是比较可行，但是 当当 m3, n=25 时，时，S(25 , 3)=141,197,991,025, 此时计算量此时计算量明显增加，这样做显然行不通。因此明显增加，这样做显然行不通。因此我们有必要讨论近似算法。我们有必要讨论近似算法。 近似算法近似算法 算法一：交替选址算法一：交替选址分配法分配法step 1step 1：将将 n n 个终点组成的集合划分成元素个数大致个终点组成的集合划分成元素个数大致 相等的相等的 m m 个子集。
17、个子集。 2 2：对这：对这 m m 个子集中的每一个个子集中的每一个, ,解一个单源选址问题。解一个单源选址问题。 3 3：检查每一个终点，看它离：检查每一个终点，看它离step2step2中求出的某个源中求出的某个源 是否比离目前分配中的那个源靠得更近。如有这是否比离目前分配中的那个源靠得更近。如有这 种情况，重新分配各终点。种情况，重新分配各终点。 4 4：如果重新进行了分配：如果重新进行了分配, ,则转则转step2step2。否则否则, ,输出结果输出结果。2006年上海市数学建模竞赛培训讲座：2006.09.09例如：对前述问题，我们有例如：对前述问题，我们有 m=2,n=10m=
18、2,n=10。此时将此时将零售店标号为零售店标号为1 1，2 2，5 5 分为一组，解对应分为一组，解对应的单源选址问题可得的单源选址问题可得将标号为将标号为6 6，7 7，10 10 分为另一组，解对应的分为另一组，解对应的单源选址问题可得单源选址问题可得这样得到的这样得到的2006年上海市数学建模竞赛培训讲座：2006.09.09观上表，终点观上表，终点1 1和和4 4由源由源2 2供货比由源供货比由源1 1供货更好供货更好同样终点同样终点8 8和和1010由源由源1 1供货比由源供货比由源2 2供货更好。供货更好。店号店号( (终点终点) ) 1 1* * 60.118 46.758 6
19、0.118 46.758 2 32.221 57.556 2 32.221 57.556 3 43.182 52.214 3 43.182 52.214 4 4* * 50.152 23.073 50.152 23.073 5 27.996 42.998 5 27.996 42.998 6 61.304 33.503 6 61.304 33.503 7 30.182 4.370 7 30.182 4.370 8 8* * 7.967 30.261 7.967 30.261 9 68.114 42.301 9 68.114 42.301 10 10* * 29.683 50.028 29.683
20、 50.028 的计算结果列表如下：的计算结果列表如下：2006年上海市数学建模竞赛培训讲座：2006.09.09将将1010个零售店重新分为个零售店重新分为2 2组：组： 此时解对应的两个单源选址此时解对应的两个单源选址问题得到：问题得到： 再重复上述过程即可得到再重复上述过程即可得到 的的具体具体计算结果如下表：计算结果如下表：2006年上海市数学建模竞赛培训讲座：2006.09.09从上表中可从上表中可看出：看出：店号店号( (终点终点) ) 2 18.674 81.411 2 18.674 81.411 3 36.531 69.609 3 36.531 69.609 5 35.797
21、63.377 5 35.797 63.377 8 18.420 54.142 8 18.420 54.142 10 18.087 72.511 10 18.087 72.511 1 62.939 47.895 1 62.939 47.895 4 62.575 7.261 4 62.575 7.261 6 72.760 9.104 6 72.760 9.104 7 46.622 22.519 7 46.622 22.519 9 77.149 24.446 9 77.149 24.446 2006年上海市数学建模竞赛培训讲座：2006.09.09这样，计算终止，此时得到近似最优解这样，计算终止，此
22、时得到近似最优解 事实上它也是真正的最优解事实上它也是真正的最优解注：此时建二个工厂（仓库）的供货费用为注：此时建二个工厂（仓库）的供货费用为140.07前面对单源选址问题（前面对单源选址问题（m=1)，其供货费用为其供货费用为215.79到底是建一个工厂，还是建二个甚至是到底是建一个工厂，还是建二个甚至是3个个，这主要看这主要看 ，不能仅考虑供货的费用，不能仅考虑供货的费用 2006年上海市数学建模竞赛培训讲座：2006.09.09算法二：算法二：随机终点法随机终点法Step1：根据根据1，2，n 各个整数的均匀分布产生各个整数的均匀分布产生m个个 随机整数随机整数 2：将标号为这：将标号为
23、这m 个整数的终点看作源，而把其余个整数的终点看作源，而把其余 n-m 个终点分配给费用最小的源。个终点分配给费用最小的源。 3：重复上述步骤：重复上述步骤1和和2，直到满足某一终止准则。每直到满足某一终止准则。每 次重复都应保留总费用最小的解次重复都应保留总费用最小的解。为了求出最优解，求解为了求出最优解，求解 m个单源选址问题，看一看结果个单源选址问题，看一看结果有无改进。有无改进。终止准则终止准则 ：可以事先确定一个数，重复次数不超过该数可以事先确定一个数，重复次数不超过该数 计算目标函数值的平均值和标准差，最优值应计算目标函数值的平均值和标准差，最优值应 介于与平均值相距介于与平均值相
24、距1.5到到2个标准差之间，若达个标准差之间，若达 到该标准，则计算停止。到该标准，则计算停止。2006年上海市数学建模竞赛培训讲座：2006.09.09算法算法三、可行集合法三、可行集合法 1 1、m m 个源（仓库）向个源（仓库）向n n个终点（零售店或地区）供货个终点（零售店或地区）供货2 2、有一个或者、有一个或者 L L 个生产性设施向这个生产性设施向这m m个源（仓库）个源（仓库） 供货，生产性设施和供货，生产性设施和 n n 个终点的位置已知个终点的位置已知希望确定希望确定 n n 个源的位置满足：个源的位置满足：1 1、从、从 m m 个源到各终点的总运费最小个源到各终点的总运
25、费最小2 2、从、从 L L 个生产性设施到个生产性设施到 m m 个个源的运费最小源的运费最小3 3、源的位置是离散的或有限制的、源的位置是离散的或有限制的5. 推广与讨论推广与讨论2006年上海市数学建模竞赛培训讲座：2006.09.09三三. 混合混合整数规划模型整数规划模型q 工厂选址问题工厂选址问题 问题提出问题提出 有有 n n个城市，单位时间的需要物资量：个城市，单位时间的需要物资量：现要在其中选现要在其中选 m m个城市生产这中物资的工厂，个城市生产这中物资的工厂， ：No.j No.j 城市所在工厂最多所能生产的数量城市所在工厂最多所能生产的数量 ：No.i No.i 工厂的
26、建厂投资工厂的建厂投资 ：No.i No.i 工厂到工厂到 No.j No.j 工厂的单位物资的运价工厂的单位物资的运价问如何建厂，既能满足要求也能使成本最低？问如何建厂，既能满足要求也能使成本最低？2006年上海市数学建模竞赛培训讲座：2006.09.09 建立模型建立模型 No.i No.i 工厂到工厂到 No.j No.j 工厂的运输量工厂的运输量 数学模型如下：数学模型如下： 2006年上海市数学建模竞赛培训讲座：2006.09.09四四. 0-1. 0-1规划（布尔规划）规划（布尔规划） 1.1.课程表安排问题课程表安排问题 问题的提出：问题的提出：考虑某校的课程安排问题，假设每天有
27、考虑某校的课程安排问题，假设每天有L L节课节课, , 一周有一周有T T节课节课. .全校有全校有m m 门课程，门课程，n n位教师，位教师， s s个教室，个教室， : : 一周内第一周内第 i i位教师在第位教师在第 j j 课程课程的教学时数。由于设备上的原因，有些课程只的教学时数。由于设备上的原因，有些课程只能在某些教室上课，并且有些教师对上课时间能在某些教室上课，并且有些教师对上课时间提出要求。请建立课程安排的数学模型。提出要求。请建立课程安排的数学模型。2006年上海市数学建模竞赛培训讲座：2006.09.09 建立模型建立模型 建立的数学模型如下：建立的数学模型如下： 200
28、6年上海市数学建模竞赛培训讲座：2006.09.09 模型求解模型求解 这是一个这是一个 0-10-1规划规划- -布尔规划布尔规划2006年上海市数学建模竞赛培训讲座：2006.09.092.2.工件排序加工问题工件排序加工问题 问题的提出问题的提出：有有m m台同型机器，有台同型机器，有n n个零件要在这类机器个零件要在这类机器上进行加工，假如各个零件的加工时间分上进行加工，假如各个零件的加工时间分别为：别为： 试建立使加工任务均衡试建立使加工任务均衡的数学模型。的数学模型。2006年上海市数学建模竞赛培训讲座：2006.09.09 建立模型建立模型 这也是一个这也是一个 0-10-1整数规划整数规划2006年上海市数学建模竞赛培训讲座：2006.09.09 祝大家在竞赛中取得优异成绩！祝大家在竞赛中取得优异成绩！再再 见！见！
