西安网站建设工程,昆山移动网站建设,浙江网站建设网,网业协同心得体会运营商文章目录 1 图论应用1.1 最小生成树1.2 最短路径1.3 网络与最大流量 2 运筹方法2.1 线性规划2.2 动态规划2.2.1 供需平衡问题2.2.2 任务指派问题 3 预测与决策3.1 不确定型决策分析3.2 风险型决策3.2.1 决策树3.2.2 决策表 4 随机函数5 数学建模 1 图论应用
①最小生成树
连接… 文章目录 1 图论应用1.1 最小生成树1.2 最短路径1.3 网络与最大流量 2 运筹方法2.1 线性规划2.2 动态规划2.2.1 供需平衡问题2.2.2 任务指派问题 3 预测与决策3.1 不确定型决策分析3.2 风险型决策3.2.1 决策树3.2.2 决策表 4 随机函数5 数学建模 1 图论应用
①最小生成树
连接所有顶点无环路权值之和最小。
②最短路径
起点终点只要有1条通路就可以了权值之和最小。
③网路与最大流量
起点终点多条路径合并。
1.1 最小生成树
例题 某小区有七栋楼房①~⑦(见下图),各楼房之间可修燃气管道路线的长度单位:百米)已标记在连线旁。为修建连通各个楼房的燃气管道该小区内部煤气管道的总长度至少为多少百米? 分析 克鲁斯卡尔算法最短边 普利姆算法最近顶点 故煤气管道的总长度至少为23345623百米 注意最小生成树可以有多种但是最小权值只有一个。 1.2 最短路径
例题 有一批货物要从城市s发送到城市t线条上的数字代表通过这条路的费用(单位为万元)。那么运送这批货物至少需要花费多少万元? 分析 最短路径S-2-3-5-6-t需要花费21202081281万元
1.3 网络与最大流量
例题 下图标出了某地区的运输网各节点之间的运输能力如下表所示。那么从节点①到节点⑥的最大运输能力(流量)可以达到多少万吨/小时? 分析 多段流量分析时流量由瓶颈决定以抽取的方式分析剩余流量 先根据表在图中标上数据 步骤11最大流量路径1-3-5-6最大运输能力10步骤2抽取对应路径重复步骤1、步骤2直到没有路径为止。21-2-5-6最大运输能力631-4-6最大运输能力541-4-2-5-6或1-4-3-5-6最大运输能力11故从节点①到节点⑥的最大运输能力(流量)可以达到10651123万吨/小时
例2 在军事演习中张司令希望将部队尽快从A地通过公路网(见下图)运送到F地:
图中标出了各路段上的最大运量单位:千人/小时)。根据该图可以算出从A地到F地的最大运量是千人/小时。 A 20 B 21 C 22 D 23
分析 1A-B-F最大运输能力8 2A-B-E-F或A-D-E-F最大运输能力44 3A-D-C-E-F最大运输能力3 4A-C-E-F最大运输能力2 5A-B-C-E-F最大运输能力1 故最大运量是84432122千人/小时
2 运筹方法
2.1 线性规划
线性规划的一些特点:
线性规划的可行解域是由一组线性约束条件形成的从几何意义来说就是由一些线性解面围割形成的区域不一定是封闭的多边形或多面体。如果存在两个最优解则连接这两点的线段内所有的点都是最优解而线段两端延长线上可能会超出可行解区。增加一个约束条件时要么缩小可行解域(新的约束条件分割了原来的可行解域)要么可行解域不变(新的约束条件与原来的可行解域不相交)如果最优解在可行解域边界某个非顶点处达到则随着等值域向某个方向移动目标函数的值会增加或减少(与最优解矛盾)或没有变化(在此段边界上都达到最优解)从而仍会在可行解域的某个顶点处达到最优解。若最优解存在且唯一则可以从可行解区顶点处比较目标函数值来求解。
线性规划的标准型(standard form of linear programrmng)是线性规划模型的标准形式。其主要特征为: (1目标函数为极大化类型; (2所有的约束条件都是等式; (3所有约束方程右端的常数都是非负的; (4所有决策变量都是非负的。
例题 线性规划问题由线性的目标函数和线性的约束条件包括变量非负条件)组成。满足约束条件的所有解的集合称为可行解区。既满足约束条件又使目标函数达到极值的解称为最优解。以下关于可行解区和最优解的叙述中正确的是 )。 A 可行解区一定是封闭的多边形或多面体 B 若增加一个线性约束条件则可行解区可能会扩大 C 若存在两个最优解则它们的所有线性组合都是最优解 D 若最优解存在且唯一则可以从可行解区顶点处比较目标函数值来求解
分析
由一些线性解面围割形成的区域不一定是封闭的多边形或多面体增加一个约束条件时要么缩小可行解域要么可行解域不变如果存在两个最优解则连接这两点的线段内所有的点都是最优解而线段两端延长线上可能会超出可行解区若最优解存在且唯一则可以从可行解区顶点处比较目标函数值来求解故答案D
例2 某企业需要采用甲、乙、丙三种原材料生产l、I两种产品。生产两种产品所需原材料数量、单位产品可获得利润以及企业现有原材料数如下表所示则公司可以获得的最大利润是(1万元。取得最大利润时原材料2尚有剩余。
(1) A.21 B.34 C.39 D.48
(2) A.甲 B.乙 C.丙 D.乙和丙
分析 设生产Ⅰ与Ⅱ产品的数量分别为︰X和Y。 则有: (1)XY 4 (2)4X3Y12 (3) X3Y6 (4)X 0Y0 目标函数 9X12Y
图解法 找顶点代入 联立方程求解 例2 某公司现有400万元用于投资甲、乙、丙三个项目投资额以百万元为单位已知甲、乙、丙三项投资的可能方案及相应获得的收益如下表所示则该公司能够获得的最大收益值是)百万元。 A 17 B 18 C 20 D 21 分析 穷举法
甲1乙2丙1收益值18故答案B。
2.2 动态规划
2.2.1 供需平衡问题
例题 设三个煤场A、B、C分别能供应煤12、14、10万吨三个工厂x、Y、Z分别需要煤11、12、13万吨从各煤场到各工厂运煤的单价百元/吨)见下表方框内的数字。只要选择最优的运输方案总的运输成本就能降到百万元。
A 83 B 91 C113 D 153
贪心策略分析 找单价最低的 煤场A到工厂Y的单价最低 煤场B到工厂X的单价最多 煤场C到工厂X的单价最低。 由于工厂Z没有单价最低的就需要考虑分配一些产量给工厂C 分配一些产量给工厂C 对于煤场A工厂Y分配产量给工厂X单价成本增加4分配产量给工厂Z单价成本增加5 对于煤场B工厂X分配产量给工厂Y单价成本增加2分配产量给工厂Z单价成本增加1 对于煤场C工厂X分配产量给工厂Y单价成本增加3分配产量给工厂Z单价成本增加4
现在想要成本越少越好所以成本增长越少越好所以把煤场B的产量分配给工厂Z又工厂Z的需求量为13煤场B最大供煤量14所以工厂X分配产量为1工厂Z分配产量为13。煤场C的最大供煤量10全部都分配给工厂X。煤场A的最大供煤量12全部都分配给工厂Y。最终得到最优方案。
运输成本最低为2131011231383百万元答案A
伏格尔法求解供需平衡问题 伏格尔法的步骤是: 1、算出各行各列中最小元素和次小元素的差额,并标出差额最大的(若几个差额同为最大则可任取其一)。 2、在差额最大的行或列中的最小元素处填上尽可能大的数。 3、对未划去的行列重复以上步骤,直到得到一个初始解。 2.2.2 任务指派问题
例题 某企业准备将四个工人甲、乙、丙、丁分配在A、B、C、D四个岗位。每个工人由于技术水平不同在不同岗位上每天完成任务所需的工时见下表。适当安排岗位可使四个工人以最短的总工时( 全部完成每天的任务。 A 13 B 14 C 15 D 16
贪心策略分析
匈牙利算法分析
例2 某工厂分配四个工人甲、乙、丙、丁同时去操作四台机床A、B、C、D,每人分配其中的一台。已知每个工人操作每台机床每小时的效益值如下表所示则总效益最高的最优分配方案共有个。 A 1 B 2 C 3 D 4
匈牙利算法分析 按行减 按列减
故正确答案C
3 预测与决策
3.1 不确定型决策分析 例题 分析 乐观主义者500300300积极型 悲观主义者50100200保守型 平均值决策法700/3600/3750/3保守型 后悔值250200300稳健型
例2 某公司为经营业务的需要决定要在现有生产条件歹变的情况下生产一种新产品现可供生产的产品有甲、乙、丙、丁四种类型。由于缺少相关资料背景对新产品的市场需求只能估计为大、中、小三种状态在不同的市场需求条件下新产品的收益值如表所示。如果决策者采用后悔值方法进行决策该公司应生产 ) 。
A 甲 B 乙 C 丙 D 丁
分析 答案B
3.2 风险型决策
3.2.1 决策树
例1 某电子商务公司要从A地向B地的用户发送一批价值为90000元的货物。从A地到B地有水、陆两条路线。走陆路时比较安全其运输成本为10000元;走水路时一般情况下的运输成本只要7000元不过一旦遇到暴风雨天气则会造成相当于这批货物总价值的10%的损失。根据历年情况这期间出现暴风雨天气的概率为1/4那么该电子商务公司该如何选择呢? 分析 水路 好天气70000.755250 坏天气70009000010%0.254000 总计70000.75700090000*10%*0.259250
陆路10000
水路的成本低些故选择水路
例2 某企业拟进行电子商务系统的建设有四种方式可以选择:①企业自行从头开发;②复用已有的构件来构造;③购买现成的软件产品;④承包给专业公司开发。针对这几种方式项目经理提供了如图所示的决策树根据此图管理者选择建设方式的最佳决策是 。 A企业自行从头开发 B复用已有的构件来构造 C购买现成的软件产品 D承包给专业公司开发 分析 自行从头开发0.3380.74542.9 复用0.427.50.60.2310.60.84938.24 购买0.7210.33023.7 承包0.6350.4*5041 故最佳决策为购买现成的软件产品 答案C。
例3 生产某种产品有两个建厂方案:(1)建大厂需要初期投资500万元。如果产品销路好每年可以获利200万元;如果销路不好每年会亏损20万元。(2)建小厂需要初期投资200万元。如果产品销路好每年可以获利100万元;如果销路不好每年只能获利20万元。 市场调研表明未来2年这种产品销路好的概率为70%。如果这2年销路好则后续5年销路好的概率上升为80%;如果这2年销路不好则后续5年销路好的概率仅为10%.为取得7年最大总收益决策者应) 。
A 建大厂总收益超500万元 B 建大厂总收益略多于300万元 C 建小厂总收益超500万元 D 建小厂总收益略多于300万元
分析 首先画决策树 求平均收益值 建大厂的平均收益高总收益略高于300万。 故答案选A。
3.2.2 决策表
案例 评估和选择最佳系统设计方案时甲认为可以采用点值评估方法即根据每一个价值因素的重要性综合打分来选择最佳的方案。乙根据甲的提议对如表所示的系统A和B进行评估那么乙认为( ) 。
A最佳方案是A B最佳方案是B c条件不足不能得出结论 D只能用成本/效益分析方法做出判断
分析 系统A9535%7040%8525%82.5 系统B7535%9540%9025%86.75 故最佳方案是B 答案B
4 随机函数
例1 根据历史数据和理论推导可知某应用中随机变量s的分布密度函数为f (x)2x(0x1)。这意味着当Δx充分小时随机变量s落在区间xxΔx内的概率约等于f (x) Δx。为此开发该应用的仿真系统时可用来模拟该随机变量其中r1和r2为计算机逐个产生的、均匀分布在(01)区间内的互相独立的伪随机数。
A max (r1r2) B min (r1r2) C r1*r2 D (r1r2)/2
分析 假设随机变量s的分布密度函数为f (x)2x 这意味着当△x充分小时随机变量s落在区间(xxAx)内的概率约等于f (x)Ax。r1和r2为计算机逐个产生的、均匀分布在(01区间内的互相独立的伪随机数。
–随机数即约等于密度函数的结果 密度函数为上升趋势则随机数应该满足上升趋势。此处采用模拟函数max (r1, r2)随机产生随机数r1和r2。
法二 f(x)近似等于命中率则 假设r1 0.1r2 0.2 Amax(r1r20.2f(x)0.4 Bmin(r1r20.1f(x)0.2 Cr1*r20.02f(x)0.04 D(r1r2)/20.15f(x)0.3 f(x)越大命中率越高故max(r1,r2)命中率最高
答案A
例2 根据历史数据和理论推导可知某应用中随机变量s的分布密度函数为f (x)3x^2(0x1)。这意味着当Ax充分小时随机变量s落在区间(xx△x)内的概率约等于f (x)Ax。为此开发该应用的仿真系统时可用来模拟该随机变量其中r1、r2、r3…为计算机逐个产生的、均匀分布在(01区间内的互相独立的伪随机数。
A max (r1r2r3) B min (r1r2r3) C r1r2r3 D (r1r2r3)/3
分析 假设r10.1r20.2r30.3 Amax(r1r2r30.3f(x)0.18 Bmin(r1r2r30.1f(x)0.02 Cr1r2r30.006f(x)0.000072 D(r1r2r3)/30.2f(x)0.08 f(x)越大命中率越高故max(r1,r2,r3)命中率最高 答案A。
5 数学建模
数学建模是一种数学的思考方法是运用数学的语言和方法通过抽象和简化建立能近似刻画并解决实际问题的模型的一种强有力的数学手段。
数学建模过程
模型准备了解问题的实际背景,用数学语言来描述问题。模型假设根据实际对象的特征和建模的目的对问题进行必要的简化并用精确的语言提出一些恰当的假设。模型建立在假设的基础上建立相应的数学结构。模型求解利用获取的数据资料对模型的所有参数做出计算(估计)。模型分析:对所得的结果进行数学上的分析。模型检验将模型分析结果与实际情形进行比较以此来验证模型的准 确性、合理性和适用性。模型应用应用方式因问题的性质和建模的目的而异。
模型分析
模型的合理性分析:最佳、适中、满意等。 利用实际案例数据对模型进行检验可以请专家来分析模型是否合理利用计算机来模拟实际问题再在计算机上检验该数学模型。 模型的误差分析:模型误差、观测误差、截断误差、舍入误差、过失误差、绝对误差、相对误差等。参数的灵敏性分析∶变量数据是否敏感在最优方案不变的条件下这些变量允许变化的范围。
例1 面对复杂的实际问题常需要建立数学模型来求解但根据数学模型求出的解答可能不符合实际情况故还需分析模型参数和输入数据的微小变化是否会引起输出结果的很大变化。这种分析常称为 ) 。
A 准确度分析 B 敏感度分析 C 可靠性分析 D 风险分析
分析 答案敏感度分析
