几个优化问题的数学建模

1、 几个优化问题的数学建模、一个开放式基金投资问题问题某开放式基金现有总额为财的资金可用于投资，目前共有E个项目可供投资者选择。项目投资额的上限为弘，下限为凤险率为USo在投资这些项目时，实际上还会出现项目之间互相影响的情况：若不同时投资项目去堆，则耳利润率分别为gS，否则分别为L鸽；若不同时投资项目已，右则耳利润率分别为磚，%否则分别为%,如;若不同时投资项目冬，冬，堆，则耳利润率分别为,s%,否则分别为為,b6?b7?b3o如果投资项目总体凤险可以用投资项目中最大的凤险来衡量，应该如何投资，使得收益尽可能大，而风险尽可能小.2、假设不考虑投资过程中的交易费该基金中无庄家”或“金融大鳄”之类恶

2、意操纵.设对项目百的投资额为和21，肌引入0-1变量廿严投资孑目川|0,否则1=1,2,，8；z=:maxR=(y1+y3-l)(Vi+咲)+(2-儿-儿)(仪込】+卒)+(y4+儿l)(b血+h5x5)3、模型标规划模型。+(2-y4-y5)(j4x4+a5x5)+z(b2x2+b6x6+b7x7+bsx)+(1-z)(t72x2+a6x6+禺冷+t2sXg)ciyixtrf.y.(=1,2,8y2+%+升+必一3z0,z=1,2，:8必忆=0或1,/=1,2,，84、求解通过线性加权和法可以将上述双目标规划模型转化为单目标规划模型，目标为maxw/?-（l-w）g苴中评为凤险偏好系数，约束

3、条件不变。为了便于利用1indoxlingo或matlab软件包编程计算，令u=maxJgx则目标变换成XvVvVvVvVvVvX-XvVvVvVvVvVvVvVvV-玄8（?/max|w/?-（l-w）u,增加约束条件ufi=lf2,，8,即可5、进一步讨论考虑到开放式基金一般要保留适当的现金，以降低客户随时赎回而无法兌现的风险，应该调查分析客户的凤险偏好和投资心理，凤险偏好可以分为高度冒险、比较冒险、中度冒险、比较保守、高度保守这五种类型。通过经验公式可以估计出保留现金占总资金的比例，从上述模型的M中减去保留现金金额既可。当然保留现金可以用活期存款的方式存入银行，这比闲置更有利。6、模型的

4、评价模型的主要优点是采用较为成熟的数学理论建立模型，利用数学软件计算，可信度比较高，便于推广。主要缺点是建立的模型是确定的而不是更符合实际情况的随机型模型。二、结合人员分配的生产规划问题1、问题某公司要对四种产品（P1,P2,P3,P4）在五条生产线（L1到L5）上的生产进行规划。产品P1和P4的单位纯利润为7元，产品P2的单位纯利润为8元，产品P3的单位纯利润为9元。在规划期内这五条生产线各自可以进行生产的时间长度各不相同。L1到L5的最大可用生产时间分别为4500小时，5000小时，4500小时，1500小时和2500小时。表1列出了在每条生产线上生产每种产品一个单位所需要的时间。（1）、

5、假设生产是流水线作业，产品P1到P4各应生产多少才能使总利润最大？（2）、如果在生产过程中允许在生产线之间进行人员转移（从而使工时也相应转移），如表2所示，则最大利润是多少？应转移多少个工时，如何转移？3）、如果生产不是流水线作业，模型应如何修改？表1单位生产时间生产线产品L1L2L3L4L5P11.30.92.00.30.9P21.81.71.40.61.1P31.31.21.31.01.4P40.91.11.00.91.0表2可以进行的人员转移目的地最大可转移来源地L1L2L3L4L5总工时数L1-yesyesyesno400L2no-yesnoyes800L3yesyes-yesno50

6、0L4nonono-yes200L5yesyesyesno-3002、假设（1）每条生产线可生产各种产品；（2）每个生产人员的工作效率相同，且熟练各条生产线的操作，可在各条生产线之间转移。3、建模3.1、问题（1）设每种产品必须经过5条生产线才能生产出来，产品P的产i量为x,单位纯利润为r,在生产线L上的单位生产时间为d。生产线L的可用总工iijijj时数为c,则可得模型1：j男maxrxii厂V1乙dxWc,j=1,2,3,4,5ijijS.t.jX0,i=1,2,3,43.2、问题(2)设y为从生产线L转移到生产线L的工时数，生产线L的最jkjkj大可转移总工时数为b,j,k=l,2,3,

7、4,5,jHk,则可得模型2：jmaxfrxiii=1i=1dxWc+乙y-fijijkjk=1k=1yjk,j=1，2,3,4,yjkWbj，j=1，2，3，4,5k=1s.t.y，y,y,y,y,y,y,y=01521243541424354y=0,j=1,2,3,4,5xj,i=1,2,3,4iy0,j,k=l,2,3,4,5jk3.3、问题(3)设每种产品只需在任意一条生产线上即可生产出来，产品P.在生产线L上的产量为x,i=1,2,3,4；j=1,2,3,4,5,则只需在上述两个jij模型中，将目标函数修改为maxffrx,将fdx修改为fdx,其余不变。iijijiijiji=1j

8、=1i=1i=14、求解利用Lindo软件包，根据题目所给数据编程求解线性规划模型1,2,得如下结果。4.1、模型1的结果最大利润为18882.97元,产品P,P的产量分别为121542.55,1010.64,其他两种产品不生产，只有生产线L和L用尽了所有可用工时。35这表明可通过转移工时来增加利润。4.2、模型2的结果最大利润为23431.10元，产品P,P,P,P的产量1234分别为702.35,942.82,554.83,854.84.L上总计用了4100个工时，有400个工时1转移到L上；L上用了3840个工时，有800个工时转移到L上；L上用了4300个4253工时，有200个工时转

9、移到L上;L上用完了原有工时，还用了转移来的600个工44时；L上用完了原有工时，还用了转移来的800个工时。55、进一步讨论若假设xeN,i=1,2,3,4,则模型为整数线性规划，可类似i求解。三、网络最大流问题1、问题在单源单汇具有容量上限的网络N=(V,E,C)中求从源到汇的流量最大的可行流。2、模型maxv(f)I厂工f二工f,V丰v,vijkiistjks,td工f二工f二v(f)sjktjkL0fc,vveEijijij3、算法(1)Ford-Fulkerson算法，计算复杂性与容量有关，而与点数和边数无关；(2)Edmonds-Karp算法，计算复杂性为O(m2n),其中n=|V

10、|，m=|E|；(3)单纯形法，非多项式算法，可利用Lindo、Lingo或Matlab软件编程计算。4、应用(1)最小割集；(2)最小流；(3)多端最大流；(4)增益流；(5)点具有容量的最小流；(6)最小费用流，其模型只要在最大流模型中将目标改为min工bf即可得。ijijvveEij5、进一步讨论约束条件0fc,vveE中的容量值若为整数，求解上述线ijijij性规划，必得整数最大流，即各条边上的流量为整数。四、图的独立集、覆盖集与支配集问题1、匹配(边独立集)问题求图中边数最多的不相邻边之集，即最大匹配。2）算法zzmaxxijijx1,i=1,2,nij1）求非偶图最大匹配的“开花”

11、算法，计算复杂性为X3）。或引入0-1变量x，当v.iji与v配对时，x二1;否则，x二0,建立如下模型，利用软件编程计算。jijijvjeN(vi)、x=0或1，i,j=1,2,，n,i丰jij2）求偶图g=（x,y,E）最大匹配的匈牙利算法，计算复杂性为O（mn）。或引入0-1变x二1；否则，x二0，建立如下模型，利用软件编程计ijij量x，当xeX与yeY配对时，ij算。maxzzxijij厂工x1,xeXiji3）应用1）问题2）s.t.xijx1,i=1,2,ijx=0或1,i,j=1；2,ij3、点覆盖集1)问题求图中点数最少的覆盖所有边的点之集，即最小点覆盖集。(2)算法求所有极

12、小点覆盖集的逻辑算法：H(v+ii=1属于(点)覆盖集时，x=】；否则x=0，建立如下模型，ii.yminxiix+x1,vvgE,1ijnij、ijx=0或1，i=1,2,n,is.t.口Vj)。或引入0-1变量x，当VvjGN(vi)利用软件编程计算。ii4、点独立集当v属于i1)问题求图中点数最多的不相邻点之集，即最大点独之集。算法求出最小点覆盖集，其补集即为最大点独立集。或引入0-1变量x,i点)独立集时，x=1；否则；x=0，建立如下模型，利用软件编程计算。max工xi工x1,i=1,2,nijs.vv.gN(vi) HYPERLINK l bookmark60 x=0或1，i=1,

13、2,n,i五、中国邮路问题（CPP）1、问题求Euler图中的Euler回路。2、算法Fleury算法，计算复杂性为0（m）。3、应用（1）问题在加权连通图中求经过每条边至少一次的权和最小的回路，即中国邮路（2）模型设x为经过边vv的次数，则得如下模型。ijijmax工wxijijvvgEijs.t.工x=工x,vgVTOC o 1-5 h zijkiivvgEvvgEijki1xgN,vvgEijij（3）算法1）奇偶点图上作业法；2）最小权匹配算法，计算复杂性为O（n3）4、推广多邮递员中国邮路问题（k-CPP）六、旅行推销商问题（TSP）1、问题求Hamilton图中的Hamilton回

14、路。2、算法DFS法，计算复杂性为O（n!）3、应用（1）问题在加权连通图中求经过每个点至少一次的权和最小的回路，即推销商回路（2）模型先将一般加权连通图转化成一个等价的加权完全图，设当从v到v时，ijx=1，否则，x=0，则得如下模型。ijijnnmin乙乙wxijiji=1j=1，x=1,i=1,nijj=1x=1,j=1,，nk=2,n1iji=1-ki,V,IX+XHFXi1i2i2i3iki1x=0或1,i,j=1,，n,i丰jij（3）算法1）分枝定界法，非多项式算法；2）最小生成树法；3）代换法；4）插入法5）最近邻法；6）神经网络法；7）模拟退火法；8）蚂蚁算法，2）8）均为近

15、似算法。4、推广多旅行推销商问题（kTSP）七、图的着色问题1、点着色1）问题求给图的点着色，且使邻点异色的最少颜色数。TOC o 1-5 h z（2）算法1）图收缩法，非多项式算法；2）Welch-Powell算法，为近似算法；3）引入0-1变量x，当v着第k种颜色时，x=1；否则；x=0，设颜色种数为x，建立如下模ikiikik型，利用软件编程计算。minx HYPERLINK l bookmark86 x=1,i=1,2,nikk=1x+xkx,i=1,2,nikk=1x=0或1，i=1,n;k=1,ikx02、边着色求给图的边着色，且使邻边异色的最少颜色数。边着色可转化为点着色。或引入

16、0-1变量x，当vv着第k种颜色时，x=1；否则；x=0，设颜色种数为x，建立ijkijijkijk如下模型，利用软件编程计算。minx (3) 乞x=l,vveEijkijk=1x+x乞kx,vveEijkijk=1x=0或1,vveE,k=1,2,ijkijx03、面着色求给平面图的面着色，且使邻面异色的最少颜色数。面着色也可转化为点着色。八、文件保存问题1、问题在出发去度假之前，你希望将你的一些最重要的文件备份到软盘上。每个空白软盘的容量是1.44MB。你需要备份的16个文件的大小分别为：46KB,55KB,62KB,87KB,108KB,114KB,137KB,164KB,253KB,

17、364KB,372KB,388KB,406KB,432KB,461KB,851KB。假定你无法使用压缩软件,但软盘数量足够,那么应如何将这些文件分配到每一张软盘上才能使使用的软盘数目最少？2、建模这是一个装载问题,它与切割问题统称为放置问题。设保存所有文件的软盘数为x，由于任意两个文件的大小均不超过软盘的容量，故xij0,否则7混合整数规划模型1,第i个文件保存到第j张软盘上i=1,2,16;j=1,2,8,则得如下minx工x=1ijj=1x工jxijj=1瓦ax0式（1）表示一个文件只能保存到一张软盘上；式（2）表示使用的软盘数至少等于所使用的软盘的最大编号，即不比所有软盘的编号小，其中jx表示包含第i个文件的软盘编号；式（3）ij表示软盘的容量有限。不需要对x施加整数性约束，在最优解中将自动取整数值。3、求解由题目所给数据，根据LINDO软件包，编程计算得x=3,x=x=x=x=x=x114171819110,1=x=x=x=x=x=113,214,26315,316,3用3张软盘，第1，4，7，8，9，10，-y*-y*-y*-y*-y*xxxxx12,122325211,2，其余变量均为0。即最少14