线性规划大学毕业论文.doc

佳木斯大学教务处佳木斯大学教务处 第第 1 页页 线性规划大学毕业论文线性规划大学毕业论文 目目 录录 摘摘 要要 AbstractAbstract 第第 1 1 章章 绪论绪论 1 1 线性规划的基本概念 1 1 1 线性规划简介 1 1 2 线性规划由来的时间简史 1 2 线性规划的研究目的及意义 第第 2 2 章章 线性规划问题的数学模型线性规划问题的数学模型 2 1 线性规划模型的建立 2 2 线性规划模型的求解方法 2 2 1 图解法 2 2 2 单纯形法 第第 3 3 章章 线性规划在实际问题中的应用线性规划在实际问题中的应用 3 1 线性规划在企业管理中的应用 3 1 1 线性规划在企业管理中的应用范围 3 1 2 如何实现线性规划在企业管理中的应用 3 2 线性规划在企业生产计划中的应用 3 3 线性规划在运输问题中的应用 结论结论 参考文献参考文献 佳木斯大学教务处佳木斯大学教务处 第第 2 页页 第第 1 1 章章 绪论绪论 1 11 1 线性规划的基本概念线性规划的基本概念 1 1 11 1 1 线性规划简介线性规划简介 线性规划是运筹学中研究较早 发展较快 应用广泛 方法较成熟的一个重要分支 它是辅助人们进行科学管理的一种数学方法 在经济管理 交通运输 工农业生产等经济 活动中 提高经济效果是人们不可缺少的要求 而提高经济效果一般通过两种途径 一 是技术方面的改进 例如改善生产工艺 使用新设备和新型原材料 二是生产组织与计划 的改进 即合理安排人力物力资源 线性规划所研究的是 在一定条件下 合理安排人力 物力等资源 使经济效果达到最好 一般地 求线性目标函数在线性约束条件下的最大值 或最小值的问题 统称为线性规划问题 满足线性约束条件的解叫做可行解 由所有可行 解组成的集合叫做可行域 决策变量 约束条件 目标函数是线性规划的三要素 1 1 21 1 2 线性规划由来的时间简史线性规划由来的时间简史 法国数学家 J B J 傅里叶和 C 瓦莱 普森分别于 1832 和 1911 年独立地提出 线性规划的想法 但未引起注意 1939 年苏联数学家 康托罗维奇在 生产组织与计划中的数学方法 一书中提 出线性规划问题 也未引起重视 1947 年美国数学家 G B Dantzing 提出求解线性规划的单纯型法 为这门学科奠定了 基础 佳木斯大学教务处佳木斯大学教务处 第第 3 页页 1947 年美国数学家 J von 诺伊曼提出对偶理论 开创了线性规划的许多新的研究领域 扩大了它的应用范围和解题能力 1951 年美国经济学家 T C 库普曼斯把线性规划应用到经济领域 为此与康托罗维奇 一起获 1975 年诺贝尔经济学奖 50 年代后对线性规划进行大量的理论研究 并涌现出一大批新的算法 例如 1954 年 C 莱姆基提出对偶单纯形法 1954 年 S 加斯和 T 萨迪等人解决了线性规划的灵敏度 分析和参数规划问题 1956 年 A 塔克提出互补松弛定理 1960 年 G B 丹齐克和 P 沃尔 夫提出分解算法等 线性规划的研究成果还直接推动了其他数学规划问题包括整数规划 随机规划和非 线性规划的算法研究 由于数字电子计算机的发展 出现了许多线性规划软件 如 MPSX OPHEIE UMPIRE 等 可以很方便地求解几千个变量的线性规划问题 1979 年苏联数学家 L G Khachian 提出解线性规划问题的椭球算法 并证明它是多 项式时间算法 1984 年美国贝尔电话实验室的印度数学家 N 卡马卡提出解线性规划问题的新的多项式时间算法 用这种方法求解线性规划问题在变量个数为 5000 时只要单纯形法所用时间的 1 50 现已形成线性规划 多项式算法理论 50 年代后线性规划的应用范围不断扩大 建立线性规划模型的方法 佳木斯大学教务处佳木斯大学教务处 第第 4 页页 第第 2 2 章章 线性规划问题的数学模型线性规划问题的数学模型 2 12 1 线性规划模型的建立线性规划模型的建立 线性规划是合理利用 调配资源的一种应用数学的方法 它的基本思路是在满足一定 的约束条件下 使预定的目标达到最优 它的研究内容可归纳为两个方面 一是系统的任 务资源数量已定 精细安排 用最少的资源去实现这个任务 二是资源数量已定 如何 合理利用 调配 使任务完成的最多 前者是求极小 后者是求极大 线性规划的一般定义如下 对于求取一组变量 Xj j 1 2 n 使之既满足线性约束条件 又使具有线性特征的 目标函数取得极值的一类最优化问题称为线性规划问题 线性规划模型建立需具备以下条 件 一是最优目标 问题所要达到的目标能用线性函数来描述 且能够使用极值 最大 或最小 来表示 二是约束条件 达到目标的条件是有一定限制的 这些限制可以用决策 变量的线性等式或线性不等式来表示 三是选择条件 有多种方案可以供选择 以便从中 找出最优方案 线性规划问题的一般数学模型如下 1 max 或 1 1 2 2 a11x1 a12x2 a1nxn 1 a 21 x1 a 22 x2 a 2n xn 2 s t 2 am1x1 a 2 x2 a n xn 1x2 0 0 称为决策变量 j j 1 2 称为目标函数系数 j j 1 2 佳木斯大学教务处佳木斯大学教务处 第第 5 页页 称为约束右端系数 j 1 2 称为约束系数 j 1 2 1 2 其中式 1 为目标函数 式 2 称为约束条件 由于目标函数和约束条件内容和形式上的差别 线性规划问题有多种表达式 为了 便于讨论和制定统一的算法 规定标准形式如下 1 标准形式 1 0 max 2211 22222121 11212111 2211 njx bxaxaxa bxaxaxa bxaxaxa xcxcxcz j mnmnmm nn nn nn 2 记号简写式 2 1 0 2 1 max 1 1 njx mibxa xcz j n j ijij n j jj 3 矩阵形式 0 max X bAX CXz 式中 1 1 0 0 0 0 3 2 1 21 22221 11211 b b b b aaa aaa aaa A mnmm n n 4 向量形式 佳木斯大学教务处佳木斯大学教务处 第第 6 页页 0 max 1 X bxp CXz n j jj 式中 C X b 0 的含义与矩阵的表达式相同 而 2 1 2 即 A 1 2 将非标准形式化为标准形式的情况 3 种基本情况 1 目标函数为求极小值 minZ CX 则作 Z CX 即 maxZ CX 2 右端项小于 0 只需要将两端同乘 1 不等号改变方向 然后再将 不等式改为等式 3 约束条件为不等式 若约束条件为 则在不等式左侧增加一个非负松驰变量 使其转化为 若约束条件为 则在不等式左侧减去一个非负剩余变量 也称松驰变量 使其转化 为 2 22 2 线性规划模型的求解方法线性规划模型的求解方法 2 2 12 2 1 图解法图解法 线性规划可以在一定条件下合理安排人力 物力等资源 使经济效果达到最好 一 般来说 求线性目标函数在线性约束条件下的最大值或最小值的问题 统称为线性规划 问题 满足线性约束条件的解叫做可行解 由所有可行解组成的集合叫做可行域 决策变 量 约束条件 目标函数是线性规划的三要素 然而图解法不适合解大规模的线性规划 的问题 局限性比较大 但对于只有两个或者三个变量的线性规划问题 可以用图解法求 最优解 也就是作出约束条件的可行域 利用图解的方法求出最优解 其特点是过程简 洁 图形清晰 简单易懂 下面仅做只有两个变量的线性规划问题 只含两个变量的线性规划问题 可以通过在平面上作图的方法求解 步骤如下 1 以变量 x1为横坐标轴 x2为纵坐标轴 适当选取单位坐标长度建立平面坐标直角坐 标系 由变量的非负性约束性可知 满足该约束条件的解均在第一象限内 2 图示约束条件 找出可行域 所有约束条件共同构成的图形 佳木斯大学教务处佳木斯大学教务处 第第 7 页页 3 画出目标函数等值线 并确定函数增大 或减小 的方向 4 可行域中使目标函数达到最优的点即为最优解 下面举出一个实例来说明 例 1 某木器厂生产圆桌和衣柜两种产品 现有两种木料 第一种有 72 第二种有 56 3 m 假设生产每种产品都需要用两种木料 生产一张圆桌和一个衣柜分别所需木 3 m 料如下表所示 每生产一张圆桌可获利 60 元 生产一个衣柜可获利 100 元 木器厂 在现有木料条件下 圆桌和衣柜各生产多少 才使获得利润最多 木料 单位 3 m 产 品第 一 种第 二 种 圆 桌 0 180 08 衣 柜 0 090 28 解 设生产圆桌张 生产衣柜个 利润总额为元 则由已知条件得到的线性规划模xyz 型为 max 60 100 72 0 18 0 009 0 0 5628 0 08 0 yx yx 图 2 1 佳木斯大学教务处佳木斯大学教务处 第第 8 页页 这是二维线性规划 可用图解法解 先在 xy 坐标平面上作出满足约束条件的平面区 域 即可行域 S 如上图所示 再作直线 即 把直线 平移至010060 yxl053 yxll 的位置时 直线经过可行域上点 且与原点距离最远 此时取最大值 为 1 lMyxz10060 了得到 M 点坐标 解方程组 得 5628 0 08 0 7209 0 18 0 yx yx 于是知点坐标为 350 100 从而得到使利润总额最大的生产计划 即生产圆桌M 350 张 生产衣柜 100 个 能使利润总额达到最大值 31000 元 这表明 当资源数量已知 经过合理制定生产计划 可使效益最好 这就是用图解法解 线性规划来解决生产计划安排的问题之一 2 2 22 2 2 单纯形法单纯形法 单纯形是美国数学家 G B 丹齐克于 1947 年首先提出来的 它的理论根据是 线性规 划问题的可行域是 n 维向量空间 Rn 中的多面凸集 其最优值如果存在必在该凸集的某顶 点处达到 顶点所对应的可行解称为基本可行解 单纯形法的基本思想是 先找出一个基 本可行解 对它进行鉴别 看是否是最优解 若不是 则按照一定法则转换到另一改进 的基本可行解 再鉴别 若仍不是 则再转换 按此重复进行 因基本可行解的个数有限 故经有限次转换必能得出问题的最优解 如果问题无最优解也可用此法判别 1953 年美国数学家 G B 丹齐克为了改进单纯形法每次迭代中积累起来的进位误差 提 出改进单纯形法 其基本步骤和单纯形法大致相同 主要区别是在逐次迭代中不再以高斯 消去法为基础 而是由旧基阵的逆去直接计算新基阵的逆 再由此确定检验数 这样做可 以减少迭代中的累积误差 提高计算精度 同时也减少了在计算机上的存储量 1954 年美国数学家 C 莱姆基提出对偶单纯形法 单纯形法是从原始问题的一个可行解通 过迭代转到另一个可行解 直到检验数满足最优性条件为止 对偶单纯形法则是从满足对 偶可行性条件出发通过迭代逐步搜索原始问题的最优解 在迭代过程中始终保持基解的对 佳木斯大学教务处佳木斯大学教务处 第第 9 页页 偶可行性 而使不可行性逐步消失 本节内容只对一般单形法的进行探讨 下面举出一个实际例子来做介绍 例 求下列线性规划问题的最优解 00 4 155 1602030 25max 21 1 21 21 21 xx x xx xx xxz 解 化为标准形式 1 0 4 155 1602030 00025max 51 51 421 321 54321 x xx xxx xxx xxxxxz 第一步 确定一个初始基可行解 基可行解就是满足非负条件的基本解 因此要在约束 矩阵 A 中找出一个可逆的基矩阵 2 10001 01015 0012030 A 这里 m 3 3 阶可逆方阵 可以看出 x3 x4 x5的系数列向量是线性独立的 这些向量构成 一个基 对应的基变量为x3 x4 x5 x1 x2为非基变量 543 0 100 010 001 pppB 将基变量用非基变量表示 由 2 得 x3 160 30 x1 20 x2 x4 15 5x1 x2 3 x5 4 x1 佳木斯大学教务处佳木斯大学教务处 第第 10 页页 将 3 代入目标函数得 Z 5x1 2x2 0 令非基变量 x1 x2 0 代入 3 得到一个基可行解 X 0 X 0 0 0 160 15 4 第二步 从当前基可行解转换为更好的基可行解 从数学角度看 x1 x2的增加将会增加目标函数值 从目标函数值中 x1 x2前的系数看 x1 前的系数大于 x2前的系数 所以让 x1从非基变量转为基变量 称为进基变量 怎样确定 离基变量 因为 x2仍为非基变量 故 x2 0 则 3 式变为 x3 160 30 x1 160 30 16 3 x4 15 5x1 15 5 3 x5 4 x1 4 1 4 min 3 所以当 x1 3 时 x4第一个减少到 0 所以 x4出基 则 X 1 3 0 70 0 1 531 1 pppB Z 1 15 此时非基变量为 x2 x4 用非基变量表示基变量 代入 3 x3 70 14x2 6x4 x1 3 1 5x2 1 5x4 4 x5 1 1 5x2 1 5x4 将 4 代入目标函数得 Z 15 x2 x4 第三步 继续迭代 x2进基 x4仍为非基变量 令 x4 0 则 4 式表示为 x3 70 14x2 70 14 5 x1 3 1 5x2 3 1 5 15 x5 1 1 5x2 佳木斯大学教务处佳木斯大学教务处 第第 11 页页 min 5 所以当 x2 5 时 x3首先减少到 0 所以 x3出基 则 X 2 2 5 0 0 2 521 2 pppB Z 2 20 此时非基变量为 x3 x4 用非基变量表示基变量 代入 4 x2 5 1 14x3 3 7x4 x1 2 1 70 x3 2 7x4 5 x5 2 1 70 x3 2 7x4 将 5 代入目标函数得 Z 20 1 14x3 4 7x4 此时若非基变量 x3 x4的值增加 只能使 Z 值下降 所以 X 2 为最优解 Z 20 X 2 5 0 0 2 第三章第三章 线性规划模型在实际问题中的应用线性规划模型在实际问题中的应用 3 13 1 线性规划在企业管理中的应用线性规划在企业管理中的应用 3 1 13 1 1 线性规划在企业管理中的应用范围线性规划在企业管理中的应用范围 佳木斯大学教务处佳木斯大学教务处 第第 12 页页 线性规划在企业管理中的应用广泛 主要有以下八种形式 1 产品生产计划 合理利用人力 物力 财力等 是获利最大 2 劳动力安排 用最少的劳动力来满足工作的需要 3 运输问题 如何制定运输方案 使总运费最少 4 合理利用线材问题 如何下料 使用料最少 5 配料问题 在原料供应的限制下如何获得最大利润 6 投资问题 从投资项目中选取方案 是投资回报最大 7 库存问题 在市场需求和生产实际之间 如何控制库存量从而获得更高利益 8 最有经济计划问题 在投资和生产计划中如何是风险最小 3 1 23 1 2 如何实现线性规划在企业管理中的应用如何实现线性规划在企业管理中的应用 在线性规划应用前要建立经济与金融体系的评价标准及企业的计量体系 摸清企业的资源 首先通 过建网 建库 查询 数据采集 文件转换等 把整个系统的各有关部分的特征进行量化 建立数学 模型 即把组成系统的有关因素与系统目标的关系 用数学关系和逻辑关系描述出来 然后白较好的 数学模型编制成计算机语言 输入数据 进行计算 不同参数获取的不同结果与实际进行分析对比 进行定量 定性分析 最终作出决策 3 23 2 线性规划在企业生产计划中的应用线性规划在企业生产计划中的应用 一 应用线性规划来进行生产计划问题分析 首先需要弄清楚以下几点 1 必须明确目标函数 生产计划的经济分析是一种定量分析方法 它以企业利润作为 评价目标值 所寻求的目标是使企业利润最大化的生产计划决策 因此 企业利润最大 化应是生产计划决策分析的目标函数 2 必须明确约束条件 企业的生产能力 原材料 设备使用 市场需求状况等诸多制 约因素与生产计划分析密切相关 称为生产计划分析中目标函数的约束条件 约束条件对 生产计划分析的影响较大 在不同条件下 决策分析的结论则会不同 比如 就市场需求 和企业生产能力之间的关系而言 企业所处状态可有三种类型 能力不足状态 即市场 对产品的需求超过了企业的生产能力 能力过剩状态 即企业生产能力超过了市场需要 中间状态 即供求平衡的状态 或者有时处于不足状态 有时又处于过剩状态 3 必须明确单件利润 单件利润不仅牵扯到产品的单件收入 还要牵扯到生产所耗费 的各项成本及费用 佳木斯大学教务处佳木斯大学教务处 第第 13 页页 二 建立生产计划决策分析的线性规划模型 生产计划决策分析的基本方法是以利润最大化作为优化目标 明确未知变量 确定 约束条件 建立线性规划模型 最终实现企业效益最大化的生产计划 其一般模式 目标函数为利润 P P 销售收入 R R 成本 费用 C C 在各种约束条件下 使目标函数达到最大 值 分析企业实际生产过程中的日产量情况 设模型的未知变量为企业生产的产品种类日 产量建立生产计划决策分析线性规划模型的过程如下 1 2 1 目标函数 企业进行生产计划决策的目标值是企业利润最大化 现假设生产各种产品所获得的销 售收入 R 与所耗费的产品成本和费用 C 均已知 则可以得出生产计划问题的目标函数为 1 1 1 2 2 2 2 原材料约束 无论是生产何种产品都需要消耗一定的原材料 在企业实际中若需耗用多种原材料 则可根据原材料的种类 增添相应约束条件即可 建立约束不等式 11 1 12 2 1 1 上式中 分别为生产第 1 2 n 种产品的单件原材料消耗 11 12 1 为企业每可用的原材料总量 1 3 生产能力约束 此约束具体表现为企业的可用工作时间或可用设备 而企业在一定时期内的可用工 作是有限的 所以可建立如下的约束不等式 21 1 22 2 2 2 上式中 分别为生产第 1 2 种产品的单件消耗工时 为企 21 22 2 2 业的日可用的工时 料总量 4 市场需求约束 为了说明问题的方便 假设企业生产的产品市场都有需求 即 1 2 0 无上限约束 若第 j 种产品市场需求有限 最大需求为 则可增加约束 5 非负约束 因为生产实际中最多即为不生产产品 所以所有变量 0 1 2 综上所述 建立生产计划决策分析的线性规划模型如下 佳木斯大学教务处佳木斯大学教务处 第第 14 页页 1 1 1 2 2 2 11 1 12 2 1 1 21 1 22 2 2 2 s t 1 1 2 2 0 1 2 3 33 3 线性规划在运输问题中的应用线性规划在运输问题中的应用 运输是物流活动的核心环节 线性规划是运输问题的常用数学模型 利用数学知识可 以得到优化的运输方案 运输问题的提出源于如何物流活动中的运输路线或配送方案是最经济或最低成本的 运输问题解决的是已知产地的供应量 销地的需求量及运输单价 如何寻找总配送成本 最低的方案 运输问题包含产销平衡运输问题和产销不平衡运输问题 通常将产销不平 衡问题转化为产销平衡问题来处理 运输问题的条件包括需求假设和成本假设 需求假设 指每一个产地都有一个固定的供应量所有的供应量都必须配送到目的地 与之类似 每一 个目的地都有一个固定的需求量 整个需求量都必须有出发地满足 成本假设指从任何 一个产地到任何一个销地的配送成本和所配送的数量的线性比例关系 产销平衡运输问题 的一般提法是 假设某物资有 m 个产地 各地产量分别为物资从产 1 2 1 2 地运往销地的单位运价为 满足 其数学模型为 n j j m i i ba 11 Min Z m i n j ijijx c 11 产地约束 n j ij x 1 1 2 佳木斯大学教务处佳木斯大学教务处 第第 15 页页 s t 销地约束 a m i ij x 1 1 2 非负约束 0 1 2 1 2 1 产销不平衡运输问题分两种情况 1 总产量大于总销量 既满足 此时其数学模型与表达式 a 基本相同 n j j m i i ba 11 只需将表达式 a 中的产地约束条件 改为 n j ij x 1 n j ij x 1 2 总产量小于总销量 既满足 此时其数学模型与表达式 a 也基本相同 n j j m i i ba 11 只需将表达式 a 中的产地约束条件 改为 n j ij x 1 n j ij x 1 2 运输问题的解决策略 现实生产的情况往往比较复杂 许多实际问题不一定完全符合运输问题的假设 可 能一些特征近似但其中的一个或者几个特征却并不符合运输问题条件 一般来说 如果一 个问题中涉及两大类对象之间的联系或往来 且该问题能提供运输问题所需要的三类数 据 供应量 需求量 单位运价 那么这个问题 不管其中是否涉及运输 经适当约束条件 的处理后 基木都可以应用运输问题模型来解决 例如 1 追求的目标是效益最大而非成木最低 此时仅将表达式 a 中目标函数中的 Min Z 改为 Max Z 即可 2 部分 或全部 的供应量 产量 代表的是从产地提供的最大数量 而不是一个固定的 数值 此时只需将表达式 a 中的产地约束中部分 或全部 的 改成 n j ij x 1 即可 n j ij x 1 3 部分 或全部 的需求量 销量 代表的是销地接收的最大数量 而不是一个固定的数值 佳木斯大学教务处佳木斯大学教务处 第第 16 页页 此时只需将表达式 a 中的销地约束条件中的 部分 或全部 改成 m i ij x 1 即可 m i ij x 1 4 某些