数学建模-运筹学模型(一)

运筹学模型 一 本章重点本章重点 线性规划基础模型 目标规划模型 运输模型及其应用 图论模型 最小树问题 最短路问题 复习要求 复习要求 1 进一步理解基本建模过程 掌握类比法 图示法以及问题分析 合理假设的内涵 2 进一步理解数学模型的作用与特点 本章复习重点是线性规划基础模型 运输问题模型和目标规划模型 具体说来 要求大家会建立简单 的线性规划模型 把实际问题转化为线性规划模型的方法要掌握 当然比较简单 运输问题模型主要要求 善于将非线性规划模型转化为运输规化模型 这种转化后求解相当简单 你至少把一个很实际的问题转化 为用表格形式写出的模型 至于求解是另外一回事 一般不要求 目标模型一般是比较简单的线性规模模 型在提出新的要求之后转化为目标规划模型 另外 关于图论模型的问题涉及到最短路问题 具体说来用 双标号法来求解一个最短路模型 这之前恐怕要善于将一个实际问题转化为图论模型 还有一个最小数的问 题 该如何把一个网络中的最小数找到 另外在个别场合可能会涉及一笔划问题 1 1 营养配餐问题的数学模型营养配餐问题的数学模型 nnx CxCxCZ 211 min 2 1 0 2211 22222121 11212111 njx bxaxaxa bxaxaxa bxaxaxa ts j mnmnmm nn nn 或更简洁地表为 n j jjx CZ 1 min 2 1 2 1 0 1 nj mi x bxa ts j n j ijij 其中的常数C j 表示第 j 种食品的市场价格 aij表示第 j 种食品含第 i 种营养的数量 bi表示人或 动物对第 i 种营养的最低需求量 2 2 合理配料问题的数学模型合理配料问题的数学模型 有m种资源B1 B2 Bm 可用于生产n种代号为A1 A2 An的产品 单位产品Aj需用资源Bi 的数量为aij 获利为Cj单位 第i种资源可供给总量为bi个单位 问如何安排生产 使总利润达到最大 设生产第j种产品xj个单位 j 1 2 n 则有 nnx CxCxCZ 2211 max 2 1 0 2211 2222121 11212111 njx bxaxaxa bxaxaxa bxaxaxa ts j mnmnmm lnn nn 或更简单地写为 n j jjx Cz 1 max nj mi x bxa ts j n j ijij 2 1 2 1 0 1 3 3 运输问题模型运输问题模型 运输问题也是一种线性规划问题 只是决策变量设置为双下标变量 假如问题具有m个产地和n个销 地 第i个产地用Ai表示 其产量为ai i 1 2 m 第j个销地用Bj表示 其销量为bj j 1 2 n 从Ai运往Bj的运价为cij 而 m i n j ji ba 11 表示产销平衡 那么产销平衡运输问 题的一般模型可以写成为 m i n j ijijx cZ 11 min nj mi x bx ax ts ij m i jij n j iij 2 1 2 1 0 1 1 4 4 目标规划模型目标规划模型 某工厂生产代号为 的两种产品 这两种产品都要经甲 乙两个车间加工 并经检验与销售两部 门处理 已知甲 乙两车间每月可用生产工时分别为 120 小时和 150 小时 每小时费用分别为 80 元和 20 元 其它数据如下表 表 4 1 项目 数据 产品 甲车间加工 时 件 乙车间加工 时 件 检验销售 元 件 利 润 元 件 2150100 133075 工厂领导希望给出一个可行性生产方案 使生产销售及检验等方面都能达标 问题分析与模型假设问题分析与模型假设 经与工厂总经理交谈 确定下列几条 p1 检验和销售费每月不超过 4600 元 p2 每月售出产品 I 不少于 50 件 p3 两车间的生产工时充分利用 重要性权系数按两车间每小时费用比确定 p4 甲车间加班不超过 20 小时 p5 每月售出产品 不少于 80 件 p6 两车间加班总时数要有控制 对权系数分配参照第三优先级 模型建立模型建立 设x1 x2分别为产品 和 的月产量 先建立一般约束条件组 依题设 46003050 21 xx检验销售费用 50 1 x 80 2 x 1202 21 xx 1503 21 xx 设d1表检验销售费偏差 则希望 1 d达最小 有 11 dp相应的目标约束为 1121 305ddxx 4600 2 d表产品 I 售量偏差 则希望 2 d达最小 有 22 dp相应的目标约束 50 221 ddx 以d3 d4表两车间生产工时偏差 则由于充分利用 故希望 43 d d达最小 考虑到费用比例为 80 20 4 1 有 4 433 ddp 相应的目标约束应为 1202 3321 ddxx和 4421 3ddxx 150 以d5表甲车间加班偏差 则有 54 dp相应目标约束为 20 553 ddd 以d6表产品 售量偏差 则希望 6 d达最小 有相应约束为 80 662 ddx 最后优先级p6可利用 43 dd表示 考虑到权系数 有 4 436 ddp其目标约束由于利用超 售出量 两车间总工时 生产工时 已在工时限制中体现 于是得到该问题的目标规划模型为 65544332211 4 mindpdpddpdpdpz 4 436 ddp 6 2 1 0 0 80 20 1503 1202 50 46003050 21 662 553 4421 3321 221 1121 lddxx ddx ddd ddxx ddxx ddx ddxx ts ll 5 5 最小树问题最小树问题 一个图中若有几个顶点及其边的交替序列形成闭回路 我们就说这个图有圈 若图中所有连顶点间都 有边相接 就称该图是连通的 若两个顶点间有不止一条边连接 则称该图具有多重边 一个图被称为是树意味着该图是连通的无圈的简单图 在具有相同顶点的树中 总赋权数最小的树称为最小树 最小树的求法有两种 一种称为 避圈法 一种是 破圈法 两法各具优缺点 它们具有共同的特 征 去掉图中的圈并且每次都是去掉圈中边权较大的边 6 6 最短路问题的数学模型最短路问题的数学模型 最短路问题一般描述如下 在一个图 或者说网络 中 给定一个始点vs和一个终点vt 求vs到vt 的一条路 使路长最短 即路的各边权数之和最小 狄克斯屈 狄克斯屈 E D DijkstraE D Dijkstra 双标号法 双标号法 该法亦称双标号法 适用于所有权数均为非负 即一切0 ij w wij表示顶点vi与vj的边的权数 的网络 能够求出网络的任一点vs到其它各点的最短路 为目前求这类网络最短路的最好算法 该法在施行中 对每一个点vj都要赋予一个标号 并分为固定标号P vj 和临时标号T vj 两种 其含义如下 P vj 从始点vs到vj的最短路长 T vj 从始点vs到vj的最短路长上界 一个点vj的标号只能是上述两种标号之一 若为T标号 则需视情况修改 而一旦成为 P 标号 就固 定不变了 开始先给始点vs标上P标号 0 然后检查点vs 对其一切关联边 vs vj 的终点vj 给出vj的T 标号wij 再在网络的已有T标号中选取最小者 把它改为P标号 以后每次都检查刚得到P标号那点 按 一定规则修改其一切关联边终点的T标号 再在网络的所有T标号中选取最小者并把它改为P标号 这样 每次都把一个T标号点改为P标号点 因为网络中总共有n个结点 故最多只需n 1 次就能把终点vt改 为P标号 这意味着已求得了vs到vt的最短路 狄克斯屈标号法的计算步骤如下 1 令S vs 为固定标号点集 s vVS 为临时标号点集 再令0 i vP Svt 2 检查点vi 对其一切关联边 vi vj 的终点Svj 计算并令 min jijij vTwvPvT 3 从一切Svj 中选取并令 min rrj vTvTvT 选取相应的弧 vi vr 再令 SvSSv