数学建模大全

【实例简介】
充分了解数学建模的相关知识，其中包括各种算法以及MATLAB在数学建模中的具体应用以及相关的程序代码，综合各方面的知识，方便我们了解
例如线性规划 maxx s.t. Ax>b 的Maab标准型为 min -cx s. Ax<-b 1.3线忙规划问题的解的概念 般线性规划问题的(数学)标准型为 max 2=>cx ∑anx,=bi=12,…,m st ≥ 可行解满足约束条件(4)的解x=(x1,x2,…,xn),称为线性规划问题的可行解, 而使目标函数(3)达到最大值的可行解叫最优解 可行域所有可行解构成的集合称为问题的可行域,记为R 14线性规划的图解法 10 1+x2=10 6 z=12 图1线性规划的图解示意图 图解法简单直观,有助」了解线性规划问题求解的基木原坦。我们先应用图解法来 求解例1。对于每一固定的值z,使目标函数值等于z的点构成的直线称为目标函数等 位线,当z变动时,我们得到一族平行直线。对于例1,显然等位线截趋于右上方,其 上的点具有越大的目标函数值。不难看出,本例的最优解为x*=(2,6),最优目标值 26 从上面的图解过程可以看出并不难证明以下断言: (1)可行域R可能会出现多种情况。R可能是空集也可能是非空集合,当R非空 时,它必定是若干个半平面的交集(除非遇到空间维数的退化)。R既可能是有界区域, 也可能是无界区域 (2)在R非空,线性规划既可以存在有限最优解,也可以不存在有限最优解(其 目标函数值无界)。 (3)若线性规划存在有限最优解,则必可找到具有最优目标函数值的可行域R的 “顶点”。 上述论断可以推广到一般的线性规划问题,区别只在」空问的维数。在一般的n维 空间中,满足一线性等式∑a1x=b的点集被称为一个超平面,而满足一线性不等式 氵=1 ∑ax≤b(或∑a1x,≥b)的点集被称为一个半空间(其中(a1…,an)为一n维行 向量,b为一实数)。若千个半空间的交集被称为多胞形,有界的多胞形又被称为多面 体。易见,线性规划的可行域必为多胞形(为统一起见,空集Φ也被λ为多胞形)。 在一般n维空问中,要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点 可以看成为边界直线的交点,但这一几何概念的推广在一般n维空间中的几何意义并不 十分直观。为此,我们将采用另一途径来定义它。 定义1称n维空间中的区域R为一凸集,若Vx,x2∈R及元∈(01),有 x+(1-4)x2∈R 定义2设R为n维空间中的一个凸集,R中的点x被称为R的一个极点,若不 存在x、x2∈R及∈(0,1),使得x=4x+(1-4)x2。 定义1说明凸集中任意两点的连线必在此凸集中;而定义2说明,若x是凸集R 的个极点,则x不能位于R中任意两点的连线上。不难证明,多胞形必为凸集。同 样也不难证明,维空间中可行域R的顶点均为R的极点(R也没有其它的极点) 1.5求解线性规划的 Matlab解法 单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍 单纯形法,有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的 Matlab 解法 Matlab中线性规划的标准型为 min c r Ax sh s t.Aeq. x=be b<x<ub 基木数形式为 linprog(c,Ab),它的返回值是向量x的值。还有其它的些函数调用形 式(在 Matlab指令窗运行 help linprog可以看到所有的函数调用形式),如: Ix, fval]=linprog(c, A, b, Aeq, beq, LB, UB, XO, OPTIONS 这里al返回目标函数的值,LB和UB分别是变量x的卜界和上界,x是x的初始值, OPTIONS是控制参数。 例2求解下列线性规划问题 maxz=2 x ,+3x2-5x t.x1+x2+x3=7 2x1-5x2+x3210 x+3x2+x3≤12 x,x2,x3≥0 解(i)编写M文件 C=[2;3÷-5]; aeq=[1,1,1] beg=7 x=linprog(-C, a, b, aea, beg, zeros(3, 1)) vale=c!ⅹ (i)将M文件存盘,并命名为 example.m (ii)在 Matlab指令窗运行 cxamplc l即可得所求结果。 例3求解线性规划问题 min z=2x,+3x+x +4x2+2x,≥8 3x1+2x2≥6 解编写 Matlab程序如下: 2;3;1; a=[1,4,2;3,2,0 b=[8;6] Ix, y=linprog(, -, -b,l, I l, zeros(3, 1)) 1.6可以转化为线性规划的问题 很多看起米不是线性规划的问题也可以通过变换变成线性规划的问题米解决。如: 例4规划问题为 min x +x x s. t Ax< b 其中x=[x1…x,A利b为相应维数的矩阵和向量 要把上面的问题变换成线性规划问题,只要注意到事实:对任意的x,存在 l1,yv2>0满足 事实,我们只要期 2就可以满足上面的条件。 这样,记u=[u1…un],v=[v1…vn],从前我们可以把上面的问题 变成 min (u tv A(l-v)≤b 2y≥0 例5min{mnax|;l} 其中 对于这个问题,如果我们取x=maxE;|,这样,上面的问题就变换成 min x 此即我们通常的线性规划问题。 §2运输问题(产销平衡) 例6某品有m个产地、n个销地,各产地的产量分别为a1,…,an,各销地的 需求量分别为h…,b,。若该商品由i产地运到j销地的单位运价为cn,问应该如何调 运才能使总运费最省? 解:引入变量x,其取值为由i产地运往j销地的该商品数量,数学模型为 nIn ∑∑xn S. t b x.≥0 显然是一个线性规划问题,当然可以用单纯形法求解。 对产销平衡的运输问题,由于有以下关系式存在 其约束条件的系数矩阵相当特殊,可用比较简单的计算方法,习惯上称为表上作业法(由 康托洛维奇和希奇柯克两人独立地提出,简称康一希表上作业法)。 §3指派问题 3.I指派问题的数学模型 例7拟分配n人去干n项工作,每人干日仅干一项工作,若分配第i人去干第j 项工作,需花费c单位时间,问应如何分配工作才能使工人花费的总时间最少? 谷易看出,要给出个指派问题的实例,只需给出矩阵C=(cn),C被称为指派 问题的系数矩阵。 引入变量x;若分i十j工作,则取x=1,否则取x;=0。上述指派问题的 数学模型为 mun ∑∑Cnn .t 0或 上述指派问题的可行解可以用个矩阵衣示,其每行每列均有且只有个元素为 1,其余元素均为0:可以用1,…,n中的一个置换表示 问题中的变量只能取0或1,从而是^0-1规划问题。一-般的0-1规划问题求解 极为困难。但指派问题并不难解,其约束方程组的系数矩阵十分特殊(被称为全单位模 矩阵,其各阶非零子式均为±1),其非负可行解的分量只能取0或1,故约束x=0或1 可改写为x≥0而不改变其解。此时,指派问题被转化为一个特殊的运输问题,其中 n-1,a 3.2求解指派问题的匈牙利算法 由于指派问题的特殊性,又存在着由匈牙利数学家Kong提出的更为简便的解法 一匈牙利算法。算法主要依据以下事实:如果系数矩阵C=(c)行(或列)中每 元素都加上或减去同一个数,得到一个新矩阵B=(b),则以C或B为系数矩阵的 指派问题具有相同的最优指派。 例8求解指派问题,其系数矩阵为 16151922 C17211918 24221817 l7192216 解将第一行元素减去此行中的最小元素15,同样,第二行元素减去17,第三行 元素减去17,最后一行的元素减去16,得 47 0453 再将第3刎元索各减去1,得 37 0453 以B3为系数矩阵的指派问题有最优指派 1234 由等价性,它也是例7的最优指派。 有时问题会稍复杂一些。 例9求解系数矩阵C的指派问题 127979 C=717121412 15146610 4107106 解:先作等价变换如下 7|12 689666 2300*0 77171214120*10575V 15146610980*04 -4410710606362y 容易看出,从变换后的矩阵中只能选出四个位」不同行不同列的零元素,但n=5, 最优指派还无法看出。此时等价变换还可进行下去。步骤如下 (1)对未选出0元素的行打v (2)对行中0元素所在列打v (3)对V列中选中的0元素所在行打∨; 重复(2)、(3)直到无法再打为止。 可以证明,若用直线划没有打ⅴ的行与打ⅴ的列,就得到了能够覆盖住矩阵中所 有零元素的最少条数的直线集合,找出未覆盖的元素中的最小者,令ⅴ行元素减去此 数,∨列元素加上此数,则原先选中的0元素不变,而未覆盖元素中至少有一个已转 变为0,且新矩阵的指派问题与原问题也等价。上述过程可反复采用,直到能选取出足 够的0元素为止。例如,对例5变换后的矩阵冉变换,第三行、第五行元素减去2,第 列元素加上2,得 702 430 005 083 118004 4140 12345 现在已可看出,最优指派为 24135 §4对偶理论与灵敏度分析 41原始问题和对偶问题 考虑下列一对线性规划模型: max cx s.t. Ax<6.x>0 (P) 和 n b t.Ay≥c,y≥0 称(P)为原始问题,(D)为它的对偶问题 不太严谨地说,对偶问题可被看作是原始问题的“行列转置” (1)原始问题中的第j列系数与其对偶问题中的第j行的系数相同: (2)原始日标函数的各个系数行与其对偶问题右侧的各常数列相同 (3)原始问题右侧的各常数列与其对偶目标函数的各个系数行相冋 (4)在这·对问题中,不等式方向和优化方向相反 考虑线性规划: Min s.t. Ax b x≥0 把其中的等式约束变成不等式约束,可得 min cx s. x≥0 A b 的对偶问题是 max b-b V1 S t. A 其中y和y2分别表示对应于约束Ax≥b和-Ax≥-b的对偶变量组。令y=y1-y2, 则上式又可写成 max by s.t.Ay≤c 原问题和对偶的对偶约束之间的关系: min max ≥0 ≤0 变量 ≤0 行约束 ≥0 无限制 ≥0 行约束 < 变量 ≤0 无限制 4.2对偶问题的基本性质 °对称性:对偶问题的对偶是原问题。 φ°弱对偶性:若τ是原问题的可行解,ν是对偶问题的可行解。则存在 元≤bP 3°无界性:若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。 4°可行解是最优解时的性质:设￡是原问题的可行解,讠是对偶问题的可行解, 当c7籴=b时,,是最优解。 对偶定理:若原问题有最优解,那么对偶问题也有最优鮮;且目标函数值相同 6°互补松弛性:若x,分别是原问题和对偶问题的最优解,则 (A-b)=0,(A42-c)=0 例10已知线性规划问题 mina=2x1+3x2+5x3+2x4+3x5 t.x1+x2+2x3+x4+3x5≥4 8 2x,-x,+3x,+x,+x≥3 ,2,…5 已知其对偶问题的最优解为y1= 512=;z=5。试用对偶理论找出原问题的最优 解 解先写出它的对偶问题 max z=4v,+3y y1+2y2≤2 y1-y2 2y1+3y3≤5 y1+y2≤2 3y1+y2≤3 将y,y2的值代入约束条件,得②,③,④为严格不等式;由互补松弛性得 x2=x3=x4=0。因y,y2>0;原问题的两个约束条件应取等式,故有 +3x。=4 求解后得到x1=1,x5=1;故原问题的最优解为 X=[10001;O=5 43灵敏度分析 在以前讨论线性规划问题时,假定a,b,C;都是常数。但实际上这些系数往往是估 计值和预测值。如市场条件一变,c,值就会变化;an往是因工艺条什的改变而改变; b是根据资源投入后的经济效果决定的一种决策选择。因此提出这样炳个问题:当这 些系数有一个或几个发生变化时,已求得的线性规划问题的最优解会有什么变化;或者 这些系数在什么范闱内变化时,线性规划问题的最优解或最优基不变。这里我们就不 论了 44参数线性规划 参数线性规划是研究a;,b,cC;这些参数中某一参数连续变化时,使最优解发生变化 的各临界点的值。即把某一参数作为参变量,而日标函数在某区间内是这参变量的线性 区数,含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形 法进行分析参数线性规划问题 §5投瓷的收益和风险 5.1问题提出 市场上有n种资产S;(i=1,2,…,n)可以选择,现用数额为M的相当大的资金 作一个时期的投资。这n种资产在这一时期内购买S的平均收益率为r,风险损失率为 q,投资越分散,总的风险越少,总体风险可用投资的S,中最大的一个风险来度量。 【实例截图】
【核心代码】