《线性规划》由会员分享，可在线阅读，更多相关《线性规划（56页珍藏版）》请在金锄头文库上搜索。
1、 运筹学 怎样把事情做到最好 张朝伦 绪论 语翻译 工作、操作、行动、手术、运算 本 运用学 港台 作业研究 中国大陆 运筹学 为军事行动研究 历史渊源 运筹学的历史 军事运筹学阶段 德军空袭 防空系统 输船编队 空袭逃避 深水炸弹 轰炸机编队 运筹学在中国： 50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题 学科性质 应用学科 筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。 筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。 中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、
2、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 运筹学的工作步骤 确定问题 搜集数据建立模型 检验模型 求解模型 结果分析 结果实施 运筹学与计算机 计算机为运筹学提供解题工具。 要学会解题的思路与方法，建立模型很重要。 线性规划 （ 称 线性规划的发展 1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题 1947年， 1950要研究线性规划的对偶理论 1958年，发表整数规划的割平面法 1960年， 定了大规模线性规划问题理论和算法的基础。 1979年， 1984年， 线性规划研究的主要问题 一类是已有一定数量的资源（人力、物质、时间等），研究
3、如 何充分合理地使用它们，才能使完成的任务量为最大。 实际上，上述两类问题是一个问题的两个不同的方面，都是求问 题的最优解（ 。 另一类是当一项任务确定以后，研究如何统筹安排，才能使完成 任务所耗费的资源量为最少。 线性规划 产 品 资 源 I 可 利 用 资 源 设 备 1 2 8 材 料 A 4 0 16 材 料 B 0 4 12 单 位 利 润 （ 元 ） 2 3 例 某厂生产两种产品，下表给 出了单位产品所需资源及单位产品 利润 问：应如何安排生产计划，才能使 总利润最大？ 线性规划的基本概念 一、问题的提出 解： 产品 I、 别为 总运费为 z，则有： z = 2 3 2 8 4 1
4、6 4 12 例 某厂生产三种药物，这些药 物可以从四种不同的原料中提取。 下表给出了单位原料可提取的药物 量 要求：生产 60单位； 00单位， 超过 180单位，且使原料总成本最 小。 解： 四种原料的使用 量分别为： 总成本为 z，则有： z = 5 6 7 8 2 160 2 +4 2 200 3 2 180 药物 原料 A B C 单位成本 （元吨） 甲 1 2 3 5 乙 2 0 1 6 丙 1 4 1 7 丁 1 2 2 8 例 3、合理下料问题 某车间接到制作 100 付钢架的定单，每付钢架要用长 为 2 . 9 m, 2 . 7 m , 1 . 5 m 的圆钢 各 一 根，已
5、 知原料长 7 . 4 m 。 问如何下 料， 可使 所用原料最 省。 例 3、合理下料问题 设 别代表采用切割方案 18的套数， 方案 2 . 9 m 2 . 1 m 1 . 5 m 合计 余料1 2 0 1 7 . 3 0 . 12 1 2 0 7 . 1 0 . 33 1 1 1 6 . 5 0 . 94 1 0 3 7 . 4 05 0 3 0 6 . 3 1 . 16 0 2 2 7 . 2 0 . 210,50,100:0,100231002321002.m i n,64654321643165324321654321O B 0,50,10:0,100231002321002.)(
6、m i n,421654321643165324321654321O B 学模型 X = (x1,.,x n)T = c1 c2 . + c .+ a 1n (=) .+ a 2n (=) .+ a mn (=) x1,x n0 三、模型特点 1 都用一组决策变量 X = (x1,x n)决策变量取值非负； 满足以上三个条件的数学模型称为线性规划 2 都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数； 3 都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等 式来表示。 其它形式 其中： ),2,1(0),2,1(m a x ( m 11 求和形式 矩阵形式 0m a
7、 x ( m 1决策变量 常数项 1系数矩阵 212222111211价值系数 21其中： 线性规划数学模型的建立 一、建模条件 1 优化条件 ：问题所要达到的目标能用线型函数描述，且能够用极值 （ 表示； 2 限定条件 ：达到目标受到一定的限制，且这些限制能够用决策变量的 线性等式或线性不等式表示； 3 选择条件 ：有多种可选择的方案供决策者选择，以便找出最优方案。 线性规划图解法 一、解题步骤 4 将最优解代入目标函数，求出最优值。 1 在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部 分，称为可行域，可行域中的点称为可行解。 2 标出目标函数值增加的方向。 3 若求最大（
8、小）值，则令目标函数等值线沿（逆）目标函数值增加的方向 平行移动，找与可行域最后相交的点，该点就是最优解。 二、建模步骤 1 确定决策变量 ：即需要我们作出决策或选择的量。一般情况下，题目 问什么就设什么为决策变量。 2 找出所有限定条件 ：即决策变量受到的所有的约束； 3 写出目标函数 ：即问题所要达到的目标，并明确是 是 线性规划的图解 z= 0, 可行域 目标函数等值线 最优解 6 4 0 x1 一般的运输问题就是要解决把某种产 品从若干个产地调运到若干个销地，在每 个产地的供应量与每个销地的需求量已知， 并知道各地之间的运输单价的前提下，如 何确定一个使得总的运输费用最小的方案。 (一
9、 )、运输问题 例 1. 某公司从两个产地 2将物品运往三个销地 产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示： 问应如何调运，使得总运输费最小？ B 1 B 2 B 3 产量（件） A 1 6 4 6 2 0 0 A 2 6 5 5 3 0 0 销 量 1 5 0 1 5 0 2 0 0 销 地 运 输 单 价 产 地 解：我们知道 200 + 300 = 500（件）； 的总销量为： 150+150+200=500（件） ,总产量 等于总销量这是一个产销平衡的运输问题。把 产量全部分配给 好 满足这三个销地的需要。 从上表可写出此问题的数学模型。 满足产地产量的约束条件为： 200， 300. 满足销地销量的约束条件为： 200， 300， 200. 所以此运输问题的线性规划的模型如下： 目标函数： 束条件： 200， 300， 150， 150， 200. . (i = 1 ， 2； j = 1， 2， 3) (二 )、分派问题 例 设有工作 员个 ,且一人做一件工作 ,第 i 人做 j 件工作的时间（或费用）为 问如何分派这些人员使总时间（或费用）最少。 解 1， 第 设 0 , 否则
