1.1线性规划问题及其数学模型.ppt

约 束 转 换 不等式变等式 不等式变不等式 等式变不等式 不 等 式 变 等 式 松弛变量 剩余变量 不等式变不等式 例1 把问题转化为标准形式 例1 把问题转化为标准形式 练习 将下列问题转化为标准形式 * * * * * * * 第*页 第*页 运 筹 帷 幄 之 中 决 胜 千 里 之 外 线 性 规 划 Linear Programming 运 筹 学 课 件 线 性 规 划 线性规划问题及其数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论 数据包络 其他应用例子 案例分析 线性规划概述 线性规划（Linear Programming，简记为LP）是运筹学中的一个最重要、应用最广泛的分支。 线性规划及其通用解法--单纯形法一般认为是美国学者丹捷格（G.Dantzig）在1947年研究美国空军军事规划时提出的。 苏联学者康托洛维奇在1939年解决工业生产组织与计划问题时就提出类似线性规划的模型及解法；康托洛维奇的工作当时没有被重视，但直到1960年康托洛维奇再次发表《最佳资源利用的经济计算》一书后，才受到重视。 一些常见的带有Spreadsheet的软件，如：Excel、Lotus1-2-3等，均有内置的线性规划求解功能。 最优化问题求解软件，如：Lindo、Lingo、Matlab等。 线性规划问题提出 在生产管理和经营活动中经常会提出这样一类问题：如何利用有限的人力、物力、财力等资源，取得最好的效果。例如： 配载问题 一交通工具，运输几种不同体积、重量的物资，如何装配， 所运的物资最多？ 下料问题 用圆钢制造长度不等的机轴，如何下料，所剩的余料最少？ 生产计划问题 企业生产A、B两种电器产品，两种产品的市场需求状况可以确定，按当前的定价可确保所有产品均能销售出去。 企业可提供的两种原材料和劳动时间的数量是有限的。产品A与产品B各应生产多少，可使企业总利润最大? 线性规划问题提出 上述这些问题有如下共同特点： 问题解决要满足一定条件，称为约束条件； 问题有多个满足条件的解决方案； 问题解决有明确的目标要求，对应不同方案有不同目标值，可表示成目标函数。 线 性 规 划 问 题 及 其 数 学 模 型 问题提出与建模 生产计划问题 运输问题 线性规划模型 一般形式 规范形式 标准形式 形式转换 常山机械厂制造Ⅰ、Ⅱ两种产品。已知各制造一件时分别占用的设备A、B、C的台时，每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该企业应制造两种产品各多少件，可使获取的利润最大。 项目 Ⅰ Ⅱ 每天可用量 设备A（h） 2 2 12 设备B（h） 4 0 16 设备C（h） 0 5 15 利润（元） 2 3 生 产 计 划 问 题 问 题 分 析 模 型 运 输 问 题 问 题 分 析 模 型 线性规划问题的三个要素 决策变量 决策问题待定的量值称为决策变量。 决策变量的取值有时要求非负。 约束条件 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。 约束条件是决策方案可行的保障。 LP的约束条件，都是决策变量的线性函数。 目标函数 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。 目标函数是决策变量的线性函数。 有的目标要实现极大，有的则要求极小。 何谓线性规划问题 最优化问题 我们称如下一般问题：“在一定约束条件下，求目标函数的最大或最小值”为最优化问题，用数学模型描述的最优化问题，称为数学规划问题。 线性规划问题 在最优化问题中，如果约束条件与目标函数均是线性的，我们就称之为线性规划问题。 线性规划的数学模型 如果规划问题的数学模型中，决策变量的取值是连续的，既可以为整数，也可以为分数、小数或实数，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该规划问题的数学模型为线性规划的数学模型。 线性规划数学模型 建立线性规划问题数学模型的步骤： Step1 分析实际问题； Step2 确定决策变量； Step3 找出约束条件； Step4 确定目标函数； Step5 整理、写出数学模型。 【例1.1】某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表： 要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。 水泥 (公斤/m2) 400