下载文档原格式
数模常⽤算法系列--整数线性规划（分枝定界法）、整数⾮线性规划（蒙特卡洛法）整数线性规划求解----分枝定界法什么是整数规划?线性规划中的变量（部分或全部）限制为整数时，称为整数规划。
若在线性规划模型中,变量限制为整数，则称为整数线性规划。
⽬前所流⾏的求解整数规划的⽅法，往往只适⽤于整数线性规划。
⽬前还没有⼀种⽅法能有效地求解⼀切整数规划。
整数规划的分类- 变量全限制为整数时，称(完全)整数规划- 变量部分限制为整数时，称混合整数规划什么是分枝定界法原理如下：设有最⼤化的整数规划问题A,与它相应的线性规划为问题B,从解问题B开始,若其最优解不符合A的整数条件,那么B的最优⽬标函数必是A的最优⽬标函数z^*的上界\overline{z}；⽽A的任意可⾏解的⽬标函数值将是z^*的⼀个下界\underline z ,分枝定界法就是将B的可⾏域分成⼦区域的⽅法。
逐步减⼩\overline z和增⼤\underline z最终求到z^*本质就是个分治回溯,逼近最⼤值的算法。
Matlab算法如下：（强烈警告，（不会验证）由于⽐较懒，并未对算法正确性验证，思路上验证了⼀下没问题就码上来了，如果有错，请⼀定联系~~）% c,A,Aeq,Beq,LB,UB,是linprog函数的相关参数，知道了它们就可以求出对应的线性规划最优解，% now是⽬前已经知道的整数解的最⼤值function y = control(c,A,Aeq,Beq,LB,UB,now)ret = 0;[x,fval] = linprog(c,A,Aeq,Beq,LB,UB); % x是最优解的解向量，fval是对应的函数值if fval < nowy = fval;return;end % 如果得到的当前最优解fval⼩于已知的now,那说明最优整数解不在这个区间，则剪枝返回。
for i = 1 : length(x)if rem(x(i),1) ~= 0 % rem(x,1)如果返回值不为0,则表⽰是⼩数。
⾮线性整数规划模型（LINGO代码实现）⾮线性整数规划模型LINGO讲解分析：第⼀步：确定决策变量问题是确定调运⽅案，使得总运输费⽤最⼩。
⽽总运输费⽤=货物运量*货物单价，题⽬给了货物单价了，我们求货物运量即可，这⾥的货物运量则是我们的决策变量。
第⼆步：确定⽬标函数和约束条件上图第⼀⾏就是我们的⽬标函数，下⾯三⾏是我们的约束条件，在满⾜约束条件的前提下，软件会不断遍历Xij所有可能的值，然后z也会根据Xij的变化⽽产⽣不同的值，这个时候⽤⼀个min函数取所有可能值当中的最⼩值，即可。
第三步：⽤LINGO代码实现model:title 最少运费问题;sets:!集合的定义，WH是集合的名字，W1..W6是集合的长度，⼀般写成1..6,相当于创建了⼀个能放六个元素的容器WH，是抽象的，是虚⽆的，是⼀种声明，告诉我们“：”后⾯的变量是⼀个什么类型的变量，显然，后⾯的AI是⼀个确确实实有六个数的数组，是具体的，是实在WH/W1..W6/:AI;!集合的名称、集合内的成员、集合的属性（可以看成是与改集合有关的变量或常量，相当与数组）;VD/V1..V8/:DJ;links(WH,VD):C,X;!以WH和VD为基础，衍⽣集合。
相当于把两个向量结合在⼀起，形成⼀个⼆维数组，有⾏和列，C和X这两个变量是实在的具体的⼆维数组，只不过后⾯C我们赋值了，X是通过系统根据约束条件和⽬标函数⾃⼰赋值的;endsetsdata:!数据段;AI=60,55,51,43,41,52;DJ=35,37,22,32,41,32,43,38;C=6,2,6,7,4,2,5,94,9,5,3,8,5,8,25,2,1,9,7,4,3,37,6,7,3,9,2,7,12,3,9,5,7,2,6,55,5,2,2,8,1,4,3;enddatamin=@sum(links(I,J):c(i,j)*x(i,j)); !⽬标函数.links我们上线提到了，是⼀个6X8的集合名;@for(WH(i):@sum(VD(j):x(i,j))<=AI(I));!约束条件.@for⼀出，你就要知道这⼀⾏写的就是约束条件了;@for(vd(j):@sum(WH(i):x(i,j))=DJ(j));!约束条件.;end。
运筹学模型的类型运筹学模型是指通过数学方法来描述和解决复杂问题的一种工具。
根据问题的性质和要求，运筹学模型可以分为以下几种类型：1. 线性规划模型（Linear Programming Model，简称LP）：线性规划是一种优化问题，它的目标是在满足一些约束条件下，使某个线性函数取得最大或最小值。
线性规划模型广泛应用于生产调度、资源分配、物流运输等领域。
2. 整数规划模型（Integer Programming Model，简称IP）：整数规划是线性规划的扩展，它要求决策变量只能取整数值。
整数规划模型常用于生产调度、排产计划、网络设计等问题。
3. 非线性规划模型（Nonlinear Programming Model，简称NLP）：非线性规划是一种优化问题，它的目标函数和约束条件都可以是非线性的。
非线性规划模型广泛应用于经济学、金融学、工程学等领域。
4. 动态规划模型（Dynamic Programming Model，简称DP）：动态规划是一种优化方法，它将一个复杂问题分解为若干个子问题，并逐步求解这些子问题。
动态规划模型常用于生产调度、资源分配、投资决策等问题。
5. 排队论模型（Queuing Theory Model，简称QT）：排队论是一种研究等待线性的数学理论，它可以用来描述和分析顾客到达、服务时间、系统容量等因素对系统性能的影响。
排队论模型广泛应用于交通运输、通信网络、医疗卫生等领域。
6. 决策树模型（Decision Tree Model，简称DT）：决策树是一种分类和回归的方法，它可以将一个问题分解为若干个子问题，并逐步求解这些子问题。
决策树模型常用于金融风险评估、医学诊断、市场营销等领域。
总之，不同类型的运筹学模型适用于不同的问题领域和求解目标，选择合适的模型可以帮助我们更好地解决实际问题。
常见数学建模模型一、线性规划模型线性规划是一种常用的数学建模方法，它通过建立线性函数和约束条件，寻找最优解。
线性规划可以应用于各种实际问题，如生产调度、资源分配、运输问题等。
通过确定决策变量、目标函数和约束条件，可以建立数学模型，并利用线性规划算法求解最优解。
二、整数规划模型整数规划是线性规划的一种扩展形式，它要求决策变量为整数。
整数规划模型常用于一些离散决策问题，如旅行商问题、装箱问题等。
通过引入整数变量和相应的约束条件，可以将问题转化为整数规划模型，并利用整数规划算法求解最优解。
三、非线性规划模型非线性规划是一类目标函数或约束条件中存在非线性项的优化问题。
非线性规划模型常见于工程设计、经济优化等领域。
通过建立非线性函数和约束条件，可以将问题转化为非线性规划模型，并利用非线性规划算法求解最优解。
四、动态规划模型动态规划是一种通过将问题分解为子问题并以递归方式求解的数学建模方法。
动态规划常用于求解具有最优子结构性质的问题，如背包问题、最短路径问题等。
通过定义状态变量、状态转移方程和边界条件，可以建立动态规划模型，并利用动态规划算法求解最优解。
五、排队论模型排队论是一种研究队列系统的数学理论，可以用于描述和优化各种排队系统，如交通流、生产线、客户服务等。
排队论模型通常包括到达过程、服务过程、队列长度等要素，并通过概率和统计方法分析系统性能，如平均等待时间、系统利用率等。
六、图论模型图论是一种研究图结构和图算法的数学理论，可以用于描述和优化各种实际问题，如网络优化、路径规划、社交网络等。
图论模型通过定义节点、边和权重，以及相应的约束条件，可以建立图论模型，并利用图算法求解最优解。
七、随机模型随机模型是一种考虑不确定性因素的数学建模方法，常用于风险评估、金融建模等领域。
随机模型通过引入随机变量和概率分布，描述不确定性因素，并利用概率和统计方法分析系统行为和性能。
八、模糊模型模糊模型是一种用于处理模糊信息的数学建模方法，常用于模糊推理、模糊控制等领域。
整数规划的数学模型及解的特点整数规划IP (integer programming ）:在许多规划问题中,如果要求一部分或全部决策变量必须取整数。
例如,所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。
松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。
一、整数线性规划数学模型的一般形式∑==nj jj x c Z 1min)max(或中部分或全部取整数n j nj i jij x x x mj ni x b xa ts ,...,,...2,1,...,2,10),(.211==≥=≥≤∑=整数线性规划问题可以分为以下几种类型1、纯整数线性规划（pure integer linear programming ）:指全部决策变量都必须取整数值的整数线性规划。
有时,也称为全整数规划.2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。
3、0—1型整数线性规划（zero —one integer liner programming ）：指决策变量只能取值0或1的整数线性规划。
1 解整数规划问题0—1型整数规划0-1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的变量xi 称为0-1变量，或称为二进制变量.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z0—1型整数规划中0—1变量作为逻辑变量(logical variable ），常被用来表示系统是否处于某一特定状态,或者决策时是否取某个方案。
数学建模常用模型及代码
一.规划模型
1.线性规划
线性规划与非线性规划问题一般都是求最大值和最小值，都是利用最小的有限资源来求最大利益等，一般都利用lingo工具进行求解。
点击进入传送门
2.整数规划
求解方式类似于线性规划，但是其决策变量x1,x2等限定都是整数的最优化问题。
传送门
3. 0-1规划
决策变量只能为0或者为1的一类特殊的整数规划。
n个人指派n项工作的问题。
传送门
４.非线性规划
目标函数或者存在约束条件函数是决策变量的非线性函数的最优化问题。
传送门
５.多目标规划
研究多于一个的目标函数在给定区域上的最优化。
把求一个单目标，在此单目标最优的情况下将其作为约束条件再求另外一个目标。
传送门
6.动态规划
运筹学的一个分支。
求解决策过程最优化的过程。
传送门
二. 层次分析法
是一种将定性和定量相结合的，系统化的，层次化的分析方法，主要有机理分析法和统计分析法。
传送门
三.主成分分析
指标之间的相关性比较高，不利于建立指标遵循的独立性原则，指标之间应该互相独立，彼此之间不存在联系。
传送门。
