数学建模.运筹学部分

全国大学生数学建模竞赛ChinaUndergraduateMathematicalContestinModeling(CUMCM)(MCM)往年数模试题1993年A题非线性交调的频率设计1993年B题球队排名问题1994年A题逢山开路1994年B题锁具装箱1995年A题一个飞行管理模型1995年B题天车与冶炼炉的作业调度1996年A题最优捕鱼策略1996年B题节水洗衣机1997年A题零件的参数设计1997年B题截断切割1998年A题投资的收益和风险1998年B题灾情巡视路线1999年A题自动化车床管理1999年B题钻井布局2000年A题DNA序列分类2000年B题钢管定购和运输2001年A题血管的三维重建2001年B题公交车调度2002年A题车灯线光源的优化设计2002年B题彩票中的数学2003年A题SARS的传播2003年B题露天矿生产的车辆安排2004年A题奥运会临时超市网点设计2004年B题电力市场的输电阻塞管理2005年A题长江水质的评价和预测2005年B题DVD在线租赁2006年A题出版社的资源配置2006年B题艾滋病疗法评价及疗效预测2007年A题人口预测2007年B题乘公交看奥运2008年A题高校学费标准2008年B题电子眼定位2009年A题制动器试验台的控制方法分析2009年B题眼科病床的合理安排运筹学中的优化模型及辅助软件求解数学建模步骤示意图模型准备模型假设模型检验模型应用模型分析模型求解模型构成优化问题与规划模型解决最优化问题的数学方法：运筹学运筹学主要分支：线性规划、非线性规划、动态规划、图与网络分析、存贮论、排队伦、对策论、决策论。它们的特点就是：在若干可能的方案中寻求某种意义下的最优方案。数学上称为最优化问题,而研究处理这种问题的方法叫最优化的方法。优化模型是一类既重要又特殊的数学模型，而优化建模方法是也一种特殊的数学建模方法。优化模型一般有下面三个要素：（1）决策变量，它通常是该问题要求解的那些未知量。（2）目标函数，通常是该问题要优化（最大或最小）的那个目标的数学表达式，它是决策变量的函数。（3）约束条件，由该问题对决策变量的限制条件给出。主要内容：1.优化引例及辅助软件求解；2.运筹学中一些基本模型；3.建模实例；实例：家具生产的安排家具公司生产桌子和椅子，用于生产的劳力共计450个工时，木材共有4立方米,每张桌子要使用15个工时、0.2立方木材，售价80元。每张椅子使用10个工时、0.05立方木材，售价45元。问为达到最大的收益，应如何安排生产？分析：1.求什么？生产多少桌子？x1生产多少椅子？x22.优化什么？收益最大Maxf=80x1+45x23.限制条件？原料总量0.2x1+0.05x2≤4劳力总数15x1+10x2≤450模型：以产值为目标取得最大收益.设：生产桌子x1张,椅子x2张,(决策变量)将目标优化为：maxf=80x1+45x2对决策变量的约束：0.2x1+0.05x2≤4（Ⅰ）15x1+10x2≤450,（Ⅱ）x1≥0,x2≥0,模型求解：（1）图解法（用于决策变量是二维）15x1+10x2=450x1x20.2x1+0.05x2=4线性规划问题的目标函数(关于不同的目标值是一族平行直线)目标值的大小描述了直线离原点的远近,并且最优解一定在可行解集的某个极点上达到(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).（2）用EXCEL—Solver实现①模型中的数据直接输入EXCEL工作表中。其中决策变量初始的值可以任意给出，它们是可变的，软件最后将给出最优解的值。SUMPRODUCT是EXCEL的一个内置函数，表示两个向量或矩阵对应元素乘积的和。引用工具——规划求解（需要工具—加载宏安装）混合线性规划的EXCEL求解432110432103210104100004100004100004100035000210003000025000.5028355545524232252737285440433248432335min432143424143332313232221213121113020103433323130242322212014131211104321343332313024232221201413121110),,,(j,y),,,,;j,,(ixyyyyy-xxxy-xxxy-xxxy-xxxxxxxxxxxxxxxxxxxxxt.syyyyxxxxxxxxxxxxxxxfjij求解模型步骤：打开MicrosoftExcel的一个工作表；把模型的目标函数系数矩阵置于A1至E4区域，约束常数25000、30000和21000分别置于G6、G7和G8单元格；选择A6至E9范围作可变单元，并输入初值1。其中A6至E8区域对应变量xij(i=1,2,3;j=0,1,2,3,4)，而B9至E9则分别对应变量y1,y2,y3,和y4,A9则恒为1；在F6、F7、F8和F9处分别输入“=SUM（A6：E6）”、“=SUM（A7：E7）”、“=SUM（A8：E8）”、“=SUM（B9：E9）”,再在A10至E10处分别输入“=A6+A7+A8”、“=B6+B7+B8-41000*B9”、“=C6+C7+C8-41000*C9”、“=D6+D7+D8-41000*D9”、“=E6+E7+E8-41000*E9”表示约束等式的左边；选择单元格A11,输入“=A1*A6”,再把其引用至单元格E14;即用鼠标按着单元格A11的右下角，先拖至A14,再拖至E14;以单元格F14作目标单元格，输入“=SUM(A11:E14)”结果如图所示：进入“规划求解”界面。“设置目标单元格”处输入“F14”,然后选“最小值”，再在“可变单元格”处输入“A6:E9”,在“约束”处添加12个约束：⑴“A6：E8=0”、⑵“A9=1”、⑶“B9：E9＝二进制”、⑷“A10=35000”、⑸“B10=0”、⑹“C10=0”、⑺“D10=0”、⑻“E10=0”、⑼“F6=G6”、⑽“F7=G7”、⑾“F8=G8”、⑿“F9=1”。最后，规划求解参数界面如图8。再在“选项”中选择“采用线性模型”。单击求解，即可得到此问题的解。结果：目录（3）用Matlab实现-------lp线性优化函数线性优化问题即目标函数和约束条件均为线性函数的问题。其标准形式为：xcfminUBxLBbeqxAeqbxAtosub:.化为5,0,012224463..2max321321321321321xxxxxxxxxxxxtsxxxz5,0,012224463..2min321321321321321xxxxxxxxxxxxtsxxxz程序如下：c=[-2，-1,1];A=[1，4，-1；2，-2，1];b=[4,12];Aeq=[1，1，2];beq=6;LB＝[0,0,-inf];UB=[inf,inf,5];[x,z]=linprog(c,A,b,Aeq,beq,LB,UB)运行结果：x=4.66670.00000.6667z=-8.6667说明：x解为最优解，目标最大为8.6667。（4）用LINDO/LINGO实现我们可以直接在下面的窗口输入LP模型输入后，用鼠标单击LINDO软件工具栏中的图标，或从菜单中选择Solve│Solve(Ctrsl+S)命令，则LINDO开始编译这个模型，编译没错误马上开始求解，求解时会显示如图（4）—2所示LINDO求解器运行状态窗口（里面的“Objective”就是最优解，即：2200）。图（4）—2“LPOPTIMUMFOUNDATSTEP2”表示单纯形法在两次迭代后得到最优解。“OBJECTIVEFUNCTIONVALUE1)2200.000”表示最优目标值为2200.000（在LINDO中目标函数所在的行总是被认为是第1行，这就是这里“1）”的含义）。返回一般模型的建立某机器厂生产Ⅰ、Ⅱ两种产品，需在A、B、C三中不同的设备上加工。具体耗时如下表：问：如何生产使得利润最大？ABC利润Ⅰ产品2h402Ⅱ产品2053能力时限121615建立模型模型假设：设和分别表示І、П两种产品在计划期内的产量，利润收入为。模型建立：目标函数：约束条件：目标规划1x2xz2132maxxxz0,1551641222212121xxxxxx线性规划问题的一般模型：nnxcxcxcz2211min)max(或0,,,),(),(),(21212112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa或或或s.t.例某部门有资金200万元，今后5年内考虑给以下的项目投资。已知项目A：从第一年到第五年每年年初都可投资，当年年末可收回本利110％；项目B：从第一年到第四年年初都可投资，次年末可收回本利125％，投资额30万；项目C：第三年初投资，第五年末能收回本利140％，投资额80万；项目D：第二年初投资，第五年末能收回本利155％，投资额100万；问：如何投资使得第五年末资金额最大？1.模型假设设为第i年年初投入第j种方案的资金数。2.模型分析ijxi年初12345本利限量ABCD110%125%140%155%308010033x24x42322212xxxx5141312111xxxxx3.模型建立目标函数：约束条件：第一年年初：第二年年初：第三年年初：第四年年初：第五年年初：各变量都要大于等于零，且在各方案投资限量范围内。目标函数其实就是第五年的收益。2433425155.14.125.11.1maxxxxxz20000001211xx112422211.1xxxx122133323125.11.1xxxxx2231423125.11.1xxxx32415125.11.1xxx求解方法方法：图解法（只能求解两个变量的问题）单纯形法大M法两阶段法结合对偶单纯形法可以对线性规划问题进行灵敏度分析及参数规划。运输问题某糖果公司下面设有三个分工厂，每天的糖果生产量分别为：A1－7t，A2－4t，A3－9t。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：B1－3t，B2－6t，B3－5t，B4－6t。已知从每个加工厂到各销售门市部每吨糖果的运价如下表所示，问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少。销地产地B1B2B3B4产量A1A2A3311310192874105749销量3656模型假设：设代表从第i个产地调运给第j个销地的物资的单位数量。模型建立：目标函数约束条件ijx3141minijijijxcz04,,13,,13141ijjiijijijxjbxiaxs.t.一般模型方法：表上作业法（找初始解：最小元素法、Vogel法;调整：闭回路法、位势法）minjijijxcz11min0,,1,,111ijjmiijinjijxnjbxmiaxs.t.整数规划特点：在线性规划问题中加一个约束——变量取整数解。求解的方法有：匈牙利法、分枝定界法、割平面法动态规划模型的分类以“时间