运筹学课件_第一章_线性规划问题及单纯型解法

线性规划问题及单纯型解法

运筹学 Operational Research运筹帷幄，决胜千里 史记《张良传》

线性规划问题及单纯型解法

目 录绪 论 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 第十章 线性规划问题及单纯型解法 线性规划的对偶理论及其应用 运输问题数学模型及其解法 整数规划 动态规划 图与网路分析 随机服务理论概论 生灭服务系统 特殊随机服务系统 存储理论2

线性规划问题及单纯型解法

绪 论一、运筹学的起源与发展 二、运筹学的特点及研究对象 三、运筹学解决问题的方法步骤 四、运筹学的发展趋势

线性规划问题及单纯型解法

一、运筹学的起源与发展 起源于二次大战的一门新兴交叉学科 与作战问题相关– 如雷达的设置、运输船队的护航、反潜作战中深水炸弹 的深度、飞行员的编组、军事物资的存储等 – 英国称为 Operational Research – 美国称为 Operations Research

战后在经济、管理和机关学校及科研单位继续研究– – – – – 1952年，Morse 和 Kimball出版《运筹学方法》 1948年英国首先成立运筹学会 1952年美国成立运筹学会 1959年成立国际运筹学联合会(IFORS) 我国于1982年加入IFORS,并于1999年8月组织了第15 届大会

线性规划问题及单纯型解法

二、运筹学的特点及研究对象 运筹学的定义– 为决策机构对所控制的业务活动作决策时，提供以数量 为基础的科学方法——Morse 和 Kimball – 运筹学是把科学方法应用在指导人员、工商企业、政府 和国防等方面解决发生的各种问题，其方法是发展一个 科学的系统模式，并运用这种模式预测，比较各种决策 及其产生的后果，以帮助主管人员科学地决定工作方针 和政策——英国运筹学会 – 运筹学是应用分析、试验、量化的方法对经济管理系统 中人力、物力、财力等资源进行统筹安排，为决策者提 供有根据的最优方案，以实现最有效的管理——中国百 科全书 – 现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science5

线性规划问题及单纯型解法

二、运筹学的特点及研究对象 运筹学的分支– 数学规划：线性规划、非线性规划、整数规划、动态规 划、目标规划等 – 图论与网路理论 – 随机服务理论：排队论 – 存储理论 – 决策理论 – 对策论 – 系统仿真：随机模拟技术、系统动力学 – 可靠性理论 – 金融工程6

线性规划问题及单纯型解法

三、运筹学解决问题的方法步骤明确问题

明确问题 建立模型 设计算法 整理数据 求解模型 评价结果

建立模型Yes

设计算法 整理数据 求解模型

简化？No

No

评价结果

满意？7

线性规划问题及单纯型解法

四、运筹学的发展趋势 运筹学的危机– 脱离实际应用，陷入数学陷阱

IT对运筹学的影响– MIS, DSS, MRP-II, CIMS, ERP – OR Dept. --> Dept. Of OR & IS

运筹学与行为科学结合– – – – 群

决策和谈判 对策理论 多层规划 合理性分析

服务行业中的应用– 金融服务业 – 信息、电信服务业 – 医院管理

线性规划问题及单纯型解法

四、运筹学的发展趋势 软计算– 面向强复杂系统的计算、实时控制、知识推理 – 智能算法：模拟退火、遗传算法、人工神经网络、戒律 算法等 – 系统仿真

面向问题 后勤(Logistics)– 全球供应链管理 – 电子商务：集成特性

随机和模糊 OR– 问题本身的不确定性 – 人类知识的局限性9

线性规划问题及单纯型解法

第一章 线性规划问题及单纯型解法1.1 线性规划问题及其一般数学模型1.1.1 线性规划问题举例 例1、多产品生产问题(Max, ) 设x1, x2 分别代表甲、乙两种电缆的生产量，

OBJ : max f ( x ) 6 x1 4 x2 2 x1 x2 10 铜资源约束 x1 x2 8 铅资源约束 s.t. x2 7 产量约束 x1 , x2 0 产量不允许为负值 最优解 : x1 2, x2 6, max f ( x ) 36.

线性规划问题及单纯型解法

例2、配料问题(min, )

VA VB1 VB2 VD 单价

原料甲 原料乙 最低含量 0.5 0.5 2 1.0 0.3 3 0.2 0.6 1.2 0.5 0.2 2 0.3 0.5

设 x1, x2分别代表每粒胶丸中甲、 乙两种原料的用量

线性规划问题及单纯型解法

例3、合理下料问题 设 xj 分别代表采用切割方案1~8的套数，方案 1 2 3 4 5 6 2.9m 2 1 1 1 0 0 2.1m 0 2 1 0 3 2 1.5m 1 0 1 3 0 2 合计 7.3 7.1 6.5 7.4 6.3 7.2 余料 0.1 0.3 0.9 0 1.1 0.2

若目标函数为使购买的 钢筋最少, 则有 若目标函数为使裁剪后 零料最少 min f ( x ) x11x1 .x3 2 4 . x3 0 x 4 1.1x5 0.2 x6 0. x2 0 3x x 0 9 5 x6 2 x1 x2 x3 x 4 100 1 2 3 4 2 x x 3x 2 x 100 2 5 6 3 5 6 s.t. 2 3 1 3 4 6 x1 x3 3x 4 2 x6 100 x1 , x 2 , x3 , x4 , x5 , x6 0 1 2 3 4 5 6 则有最优解为 100 , 10 , 2 , 50 , x4 30 , OBJ 16 最优解为 : x4 : x1 x6 x 50 OBJ 1012

线性规划问题及单纯型解法

1.1.2 线性规划数学模型的一般表示方式

max(min) f ( x ) c1 x1 c2 x2 cn xn a11 x1 a12 x2 a1n xn a x a x a x 22 2 2n n 21 1 s.t. a x a x a x m2 2 mn n m1 1 x1 , x2 , , xn n : 变量个数; m : 约束行数; n m : 线性规划问题的规模 c j : 价值系数; b j : 右端项; aij : 技术系数13

( , )b1 ( , ) …… 此处隐藏：749字，全部文档内容请下载后查看。喜欢就下载吧 ……