下载文档原格式
分配问题知识点总结一、问题引入在日常生活和工作中，分配问题是一个十分常见的问题。
无论是在家庭中分配家务，还是在工作中分配资源和任务，都可能存在分配问题。
在数学中，分配问题也是一个常见的问题，它涉及到如何有效地分配资源或任务给一组个体或单位，以使得整体效益最大化或个体满意度最高。
分配问题常常涉及到资源有限、需求有限、利益最大化等方面的考虑。
二、基本概念1. 分配问题的定义分配问题是指将有限资源或任务分配给若干个个体或单位，使得各个个体或单位获得最大的效益或满意度的问题。
这类问题在生产、经济、管理等领域都有很大的应用。
2. 分配问题的基本性质分配问题通常涉及到资源有限、需求有限、效益最大化等方面的考虑。
基本性质包括资源限制、需求限制、效益目标和分配方式等。
在求解分配问题时，需要考虑到这些基本性质。
三、分配问题的分类根据不同的背景和目标，分配问题可以分为多种类型，主要包括以下几类：1. 资源分配问题资源分配问题主要涉及到如何将有限的资源分配给不同的个体或单位，以满足各方的需求或实现最大的效益。
典型的资源分配问题包括资金分配、人力分配、物资分配等。
2. 任务分配问题任务分配问题主要涉及到如何将一组任务分配给不同的个体或单位，以使得任务完成效率最高或效益最大。
典型的任务分配问题包括项目任务分配、工作任务分配等。
3. 效益最大化问题效益最大化问题主要涉及到如何通过正确的分配方式，使得整体效益最大化。
这类问题通常包括资源有限、需求量有限、成本最小化等因素的考虑。
4. 最优分配问题最优分配问题主要涉及到如何找到最优的分配方案，使得各方的需求得到最大满足。
这类问题通常是在资源分配、任务分配等方面展开讨论。
四、常见的分配问题模型在实际应用中，分配问题通常可以通过数学模型来描述和求解。
常见的分配问题模型包括以下几种：1. 线性规划模型线性规划模型是一种常用的数学模型，可以用来描述资源分配、任务分配、成本最小化等问题。
数学建模分类
一、基于数学规划的建模方法
1. 线性规划模型
2. 整数规划模型
3. 二次规划模型
4. 非线性规划模型
5. 动态规划模型
6. 最优化问题建模
二、基于统计分析的建模方法
1. 线性回归模型
2. 逻辑回归模型
3. 主成分分析模型
4. 马尔可夫模型
5. 时间序列模型
6. 方差分析模型
三、基于图论的建模方法
1. 最短路径模型
2. 最小生成树模型
3. 拓扑排序模型
4. 最大流模型
5. 最小费用流模型
6. 图着色问题建模
四、基于优化方法的建模方法
1. 遗传算法模型
2. 蚁群算法模型
3. 粒子群优化模型
4. 模拟退火模型
5. 遗传规划模型
6. 蚁群优化模型
五、基于随机过程的建模方法
1. 马尔可夫链模型
2. 随机游走模型
3. 泊松过程模型
4. 随机差分方程模型
5. 随机微分方程模型
6. 随机优化问题建模
六、基于决策分析的建模方法
1. 决策树模型
2. 神经网络模型
3. 支持向量机模型
4. 贝叶斯网络模型
5. 人工智能模型
6. 多目标决策问题建模。
第5讲整数规划、非线性规划、多目标规划一、整数规划1、概念数学规划中的变量（部分或全部）限制为整数时，称为整数规划。
若在线性规划模型中，变量限制为整数，则称为整数线性规划。
整数规划的分类:如不加特殊说明，一般指整数线性规划。
对于整数线性规划模型大致可分为两类：1）变量全限制为整数时，称纯（完全）整数规划。
2）变量部分限制为整数的，称混合整数规划。
2、整数规划特点(i)原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例1原线性规划为21min x x z +=s.t.⎩⎨⎧≥≥=+0,05422121x x x x 其最优实数解为：01=x ，452=x ，45min =z ③有可行解（当然就存在最优解），但最优值变差。
例2原线性规划为21min x x Z +=s.t.⎩⎨⎧≥≥=+0,06422121x x x x 其最优实数解为：01=x ，232=x ，23min =z 若限制整数得：11=x ，12=x ，2min =z 。
（ii ）整数规划最优解不能按照实数最优解简单取整而获得。
3、0-1整数规划0−1型整数规划是整数规划中的特殊情形，它的变量j x 仅取值0或1。
这时j x 称为0−1变量，或称二进制变量。
j x 仅取值0或1这个条件可由下述约束条件：10≤≤j x ，且为整数所代替，是和一般整数规划的约束条件形式一致的。
在实际问题中，如果引入0−1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。
引入10-变量的实际问题：（1）投资场所的选定——相互排斥的计划例3某公司拟在市东、西、南三区建立门市部。
拟议中有7个位置（点）)7,,2,1( =i A i 可供选择。
规定在东区：由321,,A A A 三个点中至多选两个；在西区：由54,A A 两个点中至少选一个；在南区：由76,A A 两个点中至少选一个。
运筹学在物流中心选址规划问题中的应用随着全球物流业的快速发展，物流中心的选址规划变得日益重要。
合理的物流中心选址可以有效降低运输成本，提高物流效率，从而增强企业的竞争力。
在这个过程中，运筹学作为一种决策科学方法，发挥着重要的作用。
本文将介绍运筹学在物流中心选址规划问题中的应用，并探讨其优势和局限性。
一、问题描述物流中心选址规划问题的目标是确定最优的物流中心位置，使得总运输成本最小化。
在实际情况中，物流中心的位置不仅仅受到运输成本的影响，还受到市场需求、基础设施、地理环境等多种因素的制约。
因此，该问题是一个复杂的多因素决策问题。
二、运筹学模型为了解决物流中心选址规划问题，可以利用运筹学模型进行建模和求解。
常用的模型包括整数规划模型、线性规划模型和网络模型等。
这些模型都能够根据不同的约束条件和目标函数，给出最优的物流中心选址方案。
三、整数规划模型整数规划模型是一种最常用的运筹学模型，它能够将物流中心选址问题转化为一个离散的决策问题。
在整数规划模型中，物流中心的位置被限制在候选地点集合中，以保证最优解的可行性。
该模型的优点是简单易懂，计算效率高。
然而，整数规划模型的局限性在于无法处理大规模问题，且不能考虑到实际情况中的各种约束条件。
四、线性规划模型线性规划模型是一种优化模型，它能够在给定约束条件下，最大化或最小化一个线性目标函数。
在物流中心选址规划问题中，线性规划模型可以根据不同的目标函数，如最小化总运输成本、最大化服务覆盖范围等，给出最优的选址方案。
线性规划模型的优点是适用范围广，计算效率高。
然而，线性规划模型的局限性在于无法处理非线性问题，并忽略了一些实际情况中的细节因素。
五、网络模型网络模型是一种图论模型，用于描述不同地点之间的关系和连接。
在物流中心选址规划问题中，网络模型可以将各个地点表示为节点，将运输线路表示为边，从而形成一个有向图。
通过网络模型，可以计算出最短路径、最小生成树等，并据此确定最优的物流中心选址方案。
多目标整数规划数学模型设计
池春姬
【期刊名称】《鸡西大学学报》
【年(卷),期】2007(007)003
【摘要】就三维合班问题,建立了多目标整数规划的数学模型,避免了人工排课的随意性和盲目性.
【总页数】2页(P58,49)
【作者】池春姬
【作者单位】鸡西大学,黑龙江·鸡西,158100
【正文语种】中文
【中图分类】G642.42
【相关文献】
1.模糊非线性规划数学模型在多目标综合利用水库规划中的应用 [J], 唐幼林;曾佑澄
2.基于多目标整数规划模型的拍照任务定价 [J], 黄艳华;李莉
3.模糊带权非线性规划数学模型在多目标综合利用水库规划中的应用 [J], 唐幼林;曾佑澄
4.不确定性条件下经济开发区环境规划方法与应用研究(Ⅰ)——不确定性多目标混合整数规划模型及算法研究 [J], 邹锐;郭怀成;刘磊
5.混合整数非线性规划与化学工程系统最优化计设——(Ⅰ)一个用于工程系统最优设计的混合整数非线性规划方法 [J], 袁希钢
因版权原因，仅展示原文概要，查看原文内容请购买。
数学建模常用模型及代码
一.规划模型
1.线性规划
线性规划与非线性规划问题一般都是求最大值和最小值，都是利用最小的有限资源来求最大利益等，一般都利用lingo工具进行求解。
点击进入传送门
2.整数规划
求解方式类似于线性规划，但是其决策变量x1,x2等限定都是整数的最优化问题。
传送门
3. 0-1规划
决策变量只能为0或者为1的一类特殊的整数规划。
n个人指派n项工作的问题。
传送门
４.非线性规划
目标函数或者存在约束条件函数是决策变量的非线性函数的最优化问题。
传送门
５.多目标规划
研究多于一个的目标函数在给定区域上的最优化。
把求一个单目标，在此单目标最优的情况下将其作为约束条件再求另外一个目标。
传送门
6.动态规划
运筹学的一个分支。
求解决策过程最优化的过程。
传送门
二. 层次分析法
是一种将定性和定量相结合的，系统化的，层次化的分析方法，主要有机理分析法和统计分析法。
传送门
三.主成分分析
指标之间的相关性比较高，不利于建立指标遵循的独立性原则，指标之间应该互相独立，彼此之间不存在联系。
传送门。
1 整数规划的MATLAB 求解方法（一） 用MATLAB 求解一般混合整数规划问题由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。
现在有许多用户发布的工具箱可以解决该类问题。
这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。
intprog 函数的调用格式如下：[x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧∈=≥≤≤=≤=）取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ),,2,1(0..min在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ⨯1维矩阵，eq A 为n m ⨯2维矩阵。
在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。
其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。
Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。
lb 和ub 为设计变量对应的上界和下界。
M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。
TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。
在该函数中，输出参数有x, fval 和exitflag 。
其中x 为整数规划问题的最优解向量，fval 为整数规划问题的目标函数在最优解向量x 处的函数值，exitflag 为函数计算终止时的状态指示变量。
例1 求解整数规划问题：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≤+≥-+=0,12 1124 124 ..max212212121，且取整数值x x x x x x x t s x x f 算法：c=[-1;-1]; A=[-4 2;4 2;0 -2]; b=[-1;11;-1]; lb=[0;0]; M=[1;2]; %均要求为整数变量 Tol=1e-8;%判断是否整数的误差限[x,fval]=linprog(c,A,b,[],[],lb,[])%求解原问题松弛线性规划[x1,fval1]=intprog(c,A,b,[],[],lb,[],M,Tol) %求最优解整数解 结果：x =%松弛线性规划问题的最优解1.50002.5000 fval = -4.0000 x1 =%整数规划的最优解2 1 fval2 = -3.0000（二） 用MATLAB 求解0-1规划问题在MATLAB 优化工具箱中，提供了专门用于求解0-1规划问题的函数bintprog ，其算法基础即为分枝界定法，在MATLAB 中调用bintprog 函数求解0-1规划时，需要遵循MATLAB 中对0-1规划标准性的要求。
0-1规划问题的MATLAB 标准型⎪⎪⎩⎪⎪⎨⎧==≤=1,0..min x b x A b Ax t s x c f eq eq T在上述模型中，目标函数f 需要极小化，以及需要满足的约束条件，不等式约束一定要化为形式为“≤”。
假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ⨯1维矩阵，eq A 为n m ⨯2维矩阵。
如果不满足标准型的要求，则需要对原问题进行转化，化为标准型之后才能使用相关函数，标准化的方法和线性规划中的类似。
0-1规划问题的MATLAB 求解函数MATLAB 优化工具箱中求解0-1规划问题的命令为bintprog bintprog 的调用格式x = bintprog(f) x = bintprog(f,A,b) x = bintprog(f,A,b,Aeq,beq) x = bintprog(f,A,b,Aeq,beq,x0) x = bintprog(f,A,b,Aeq,Beq,x0,options) [x,fval] = bintprog(...) [x,fval,exitflag] = bintprog(...) [x,fval,exitflag,output] = bintprog(...)命令详解1）x = bintprog(f)该函数调用格式求解如下形式的0-1规划问题⎩⎨⎧==1,0..min x t s x c f T2）x = bintprog(c,A,b)该函数调用格式求解如下形式的0-1规划问题⎪⎩⎪⎨⎧=≤=1,0..min x b Ax t s x c f T3）x = bintprog (c,A,b,Aeq,beq)该函数调用格式求解如下形式的0-1规划问题：⎪⎪⎩⎪⎪⎨⎧==≤=1,0..min x b x A b Ax t s x c f eq eq T4）x = bintprog (c,A,b,Aeq,beq,x0)该函数调用格式求解如下形式的0-1规划问题⎪⎪⎩⎪⎪⎨⎧==≤=1,0..min x b x A b Ax t s x c f eq eq T在前一个调用格式的基础上同时设置求解算法的初始解为x0，如果初始解x0不在0-1规划问题的可行域中，算法将采用默认的初始解 5）x = bintprog (c,A,b,Aeq,beq,x0,options)用options 指定的优化参数进行最小化。
可以使用optimset 来设置这些参数上面的函数调用格式仅设置了最优解这一输出参数，如果需要更多的输出参数，则可以参照下面的调用格式：[x,fval] = bintprog(...)在优化计算结束之时返回整数规划问题在解x 处的目标函数值fval[x,fval,exitflag] = bintprog(...)在优化计算结束之时返回exitflag 值，描述函数计算的退出条件。
[x,fval,exitflag,output] = bintprog(...) 在优化计算结束之时返回结构变量output 例2：求解0-1规划问题()()()⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧========∑∑∑∑==== 21;21 4,3,21 10 21 1 21 1 ..max1111,n ,,j ,n ,,i x ,n ,,j x ,n ,,i x t s x E f ij ni ij n j ij n i nj ijij ），（或⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=23321622243113212329152226331220E 为了程序的可读性，我们用一维下标来表示设计变量，即用41~x x 表示1411~x x ，用85~x x 表示2421~x x ，用129~x x 表示3431~x x ，用1613~x x 表示4441~x x ，于是约束条件和目标函数分别为：⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧===+++=+++=+++=+++=+++=+++=+++=+++)16,,2,1( 1,0111111111612841511731410621395116151413121110987654321 i x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x i 1644622521414313212111x E x E x E x E x E x E x E f +++++++=算法：c=[20;12;33;26;22;15;29;23;21;13;31;24;22;16;32;23]; Aeq=[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1; 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1;];beq=ones(1,8);[x,fval]=bintprog(c,[],[],Aeq,beq);B=reshape(x,4,4); %由于x是一列元素，为了使结果更加直观，故排成与效率矩阵E相对应的形式B'fval结果：Optimization terminated.ans =0 1 0 00 0 1 01 0 0 00 0 0 1fval =85整数规划的应用——组件配套问题某机械产品需要由三个工厂开工一起生产后组装完成。
每件机械需要4个组件1和3个组件2。
生产这两种组件需要消耗两种原材料A和B。
已知这两种原材料的供应量分别为400kg和600kg。
由于三个工厂的生产条件和拥有设备工艺条件不同，每个工厂生产组件的能力和原材料的消耗也不尽相同，且每个工厂开工一次都是配套生产一定数量的组件1和组件2，其具体的数据如表所示。
表11-2 各工厂生产能力和消耗原材料的数据表现在的最优化问题是，这三个工厂应当如何安排生产，才能使该产品的配套数达到最大？（Ⅰ）组件配套问题的建模设21x x 、和3x 是三个工厂分别开工的次数，将其作为该问题的设计变量。
由于每个工厂开工一次都是配套生产，故每次开工消耗的原材料一定，且生产的组件数也是一定的。
在这个假设的前提之下，我们可以得出该问题的目标函数和约束条件。
因为原材料的总量是有限的，根据工厂的开工次数，可得工厂１将消耗A 材料19x ，工厂２将消耗A 材料26x ，工厂３将消耗A 材料34x ，故有约束条件：400469321≤++x x x同理，对于材料B 的总量约束条件可以表达为：6009107321≤++x x x 然后再来分析三个工厂零件生产的情况，三个工厂生产的组件1的数量分别为2178x x 、和39x ，故组件1的总数为：3211978x x x Q ++=同理，组件2的总数为：3212596x x x Q ++=下一步是分析目标函数，该问题要求的不是生产的各种组件总数最多，而是要求产品的配套数量最大，即能组成的机械数目最多。
