《运筹学 一章 线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学 一章 线性规划.ppt（81页珍藏版）》请在金锄头文库上搜索。
1、浙江科技学院经济管理学院管工系 运筹学 管理科学与工程系经济与管理学院 2020 6 17 浙江科技学院经济管理学院管工系 2 课堂要求 1 要求学生上课不迟到 不早退 不得旷课 2 上课认真听讲 要求每位同学都做笔记 3 上课不得讲话 看书 玩手机等与课堂无关的内容 4 课后要求独自完成作业 不得抄袭或不做课后作业 2020 6 17 浙江科技学院经济管理学院管工系 3 参考资料 1 胡运权主编 运筹学教程 第三版 清华大学出版社 2 周华任主编 运筹学解题指导 清华大学出版社 3 运筹学习题集 修订版 清华大学出版社 4 熊伟编著 运筹学 机械工业出版社 5 运筹学 数据 模型 决策 科学
2、出版社 2020 6 17 浙江科技学院经济管理学院管工系 4 前言 运筹学简介 运筹学是管理科学的重要理论基础和应用手段 是管理专业的重要专业基础课程之一 运筹学根据管理问题的环境条件和决策要求 建立相应的数学模型 利用数学模型对实际问题进行分析和求解 经过分析和比较 得到适合实际问题的方案 求解结果 求解结果 建立模型 求解模型 修改模型 求解结果 修改模型 2020 6 17 浙江科技学院经济管理学院管工系 5 运筹学是在第二次世界大战中诞生和发展起来的 由于战争的需要 英国和美国招募了一批年轻的科学家和工程师 在军队将军的领导下研究战争中的问题 例如大规模轰炸的效果 搜索和攻击敌军潜水
3、艇的策略 兵力和军需物质的调运等等 这些研究在战争中取得了很好的效果 当时英国把这些研究成为 作战研究 英文是OperationalResearch 在美国称为OperationsResearch 2020 6 17 浙江科技学院经济管理学院管工系 6 战后这些研究成果逐渐公开发表 这些理论和方法被应用到经济计划 生产管理领域 也产生了很好的效果 这样 OperationsResearch就转义成为 作业研究 我国把OperationsResearch译成 运筹学 非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义 运筹学的内容十分广泛 包括线性规划 整数规划 动态规划 非线性规划 图论与网
4、络优化 排队论 决策理论 库存理论等 在本课程中 结合管理学科的特点 主要介绍线性规划 对偶问题 整数规划 运输问题 动态规划 图与网络分析 2020 6 17 浙江科技学院经济管理学院管工系 7 授课主要内容 目录 绪论 1 第一章线性规划 12 第二章对偶问题 10 第三章运输问题 6 第五章整数规划 6 第七章动态规划 8 第八章图与网络分析 8 上课总课时 51课时课程设计1周 下学期开学前 2020 6 17 浙江科技学院经济管理学院管工系 8 第一章线性规划及单纯形法 1 1线性规划问题及其数学模型1 2图解法1 3单纯形法原理1 4单纯形法计算步骤1 5单纯形法进一步讨论 202
5、0 6 17 浙江科技学院经济管理学院管工系 9 本章学习要求 能建立实际问题的数学规划模型理解线性规划模型的特点 标准型掌握线性规划的图解法及其几何意义掌握单纯形法原理掌握运用单纯形表计算线性规划问题的步骤及解法能用二阶段法和大M法求解线性规划问题 掌握任何基可行解原表及单纯形表的对应关系 2020 6 17 浙江科技学院经济管理学院管工系 10 1 1线性规划问题及其数学模型 举例说明线性规划数学模型的标准形式 2020 6 17 浙江科技学院经济管理学院管工系 11 一 线性规划问题举例说明 生产计划问题配料问题背包问题运输问题指派问题下料问题 2020 6 17 浙江科技学院经济管理学
6、院管工系 12 例1 美佳公司 生产计划问题 1 确定决策变量 通常由目标问题分解设x1代表生产 种家电数量 x2代表生产 种家电数量 2 分析并表达限制条件 包括约束条件 通常由等式或不等式表示 0 x1 5x2 156x1 2x2 24x1 x2 5x1 0 x2 0 3 分析目标 是利润最大化MaxZ 2x1 x2 2020 6 17 浙江科技学院经济管理学院管工系 13 例2 捷运公司 表1 2所需仓库面积 1 确定决策变量 通常由目标问题分解每个月有不同的租用方案 共有4个月需要租用仓库 则 表1 3租金与期限的关系 2020 6 17 浙江科技学院经济管理学院管工系 14 1 生产
7、计划问题 ProductionPlanning 某工厂拥有A B C三种类型的设备 生产甲 乙 丙 丁四种产品 每件产品在生产中需要占有的设备机时数 每件产品可以获得的利润以及三种设备可利用的时数如下表所示 求使得总利润最大的生产计划 设四种产品的产量分别为x1 x2 x3 x4 总利润为z 线性规划模型为 maxz 5 24x1 7 30 x2 8 34x3 4 18x4s t 1 5x1 1 0 x2 2 4x3 1 0 x4 20001 0 x1 5 0 x2 1 0 x3 3 5x4 80001 5x1 3 0 x2 3 5x3 1 0 x4 5000 x1 x2 x3 x4 0 20
8、20 6 17 浙江科技学院经济管理学院管工系 15 2 配料问题 MaterialBlending 某工厂要用四种合金T1 T2 T3 T4为原料 经熔炼成为新的不锈钢G 这四种原料含铬 Cr 锰 Mn 和镍 Ni 的含量 这四种原料的单价以及新的不锈钢G所要求的Cr Mn Ni的最低含量 如下表 要求配100公斤不锈钢G 并假定在配制过程中没有损耗 求使得总成本最低的配料方案 设四种原料分别选取x1 x2 x3 x4公斤 总成本为z minz 115x1 97x2 82x3 76x4s t 3 21x1 4 53x2 2 19x3 1 76x4 3 20Cr的含量下限约束2 04x1 1
9、12x2 3 57x3 4 33x4 2 10Mn的含量下限约束5 82x1 3 06x2 4 27x3 2 73x4 4 30Ni的含量下限约束x1 x2 x3 x4 100物料平衡约束x1 x2 x3 x4 0 2020 6 17 浙江科技学院经济管理学院管工系 16 3 背包问题 KnapsackProblem 一只背包最大装载重量为50公斤 现有三种物品 每种物品数量无限 每种物品每件的重量 价格如下表 求背包中装入每种物品各多少件 使背包中物品总价值最高 设三种物品的件数各为x1 x2 x3件 总价值为z maxz 17x1 72x2 35x3s t 10 x1 41x2 20 x3
10、 50 x1 x2 x3 0 x1 x2 x3为整数这是一个整数规划问题 IntegerProgramming 这个问题的最优解为 x1 1件 x2 0件 x3 2件 最高价值z 87元 2020 6 17 浙江科技学院经济管理学院管工系 17 4 运输问题 Transportation 某种物资从两个供应地A1 A2运往三个需求地B1 B2 B3 各供应地的供应量 各需求地的需求量 每个供应地到每个需求地每吨物资的运输价格如下表 求总运费最低的运输方案 35吨 25吨 10吨 30吨 20吨 2020 6 17 浙江科技学院经济管理学院管工系 18 设从两个供应地到三个需求地的运量 吨 如下
11、表 minz 2x11 3x12 5x13 4x21 7x22 8x23s t x11 x12 x13 35供应地A1x21 x22 x23 25供应地A2x11 x21 10需求地B1x12 x22 30需求地B2x13 x23 20需求地B3x11 x12 x13 x21 x22 x23 0 2020 6 17 浙江科技学院经济管理学院管工系 19 这个问题的最优解表示如下 最小总运费为 z 3 30 5 5 4 10 8 15 275元 30吨 5吨 10吨 15吨 2020 6 17 浙江科技学院经济管理学院管工系 20 5 指派问题 AssignmentProblem 有n项任务由n
12、个人完成 每项任务交给一个人 每人都有一项任务 由i个人完成j项任务的成本 或效益 为cij 求使总成本最小 或总效益最大 的分配方案 设 2020 6 17 浙江科技学院经济管理学院管工系 21 张 王 李 赵四位老师被分配教语文 数学 物理化学四门课程 每位老师教一门课 每门课由一位老师教 根据这四位老师以往教课的情况 他们分别教四这门课程的平均成绩如下表 要求确定哪一位老师上哪一门课 使四门课的平均总成绩最高 设 2020 6 17 浙江科技学院经济管理学院管工系 22 设 maxz 92x11 68x12 85x13 76x14 82x21 91x22 77x23 63x24 83x3
13、1 90 x32 74x33 65x34 93x41 61x42 83x43 75x44s t x11 x12 x13 x14 1 1 x21 x22 x23 x24 1 2 x31 x32 x33 x34 1 3 x41 x42 x43 x44 1 4 x11 x21 x31 x41 1 5 x12 x22 x32 x42 1 6 x13 x23 x33 x43 1 7 x14 x24 x34 x44 1 8 xij 0 1 2020 6 17 浙江科技学院经济管理学院管工系 23 6 下料问题现将1m长的钢切成A 0 4m B 0 3m C 0 2m长的三种钢 其中A B C三种钢分别需要
14、20根 45根和50根 问如何进行切割使得需要的1m钢为最少 解 将1m的钢分别切成A B C三种钢的可能方案如下 设第i种方案进行切割的1m钢的为xi根 minZ 0 1x3 0 1x5 0 1x7s t 2x1 x2 x3 x4 202x2 x3 3x5 2x6 x7 45x1 x3 3x4 2x6 3x7 5x8 50 xi 0 i 1 2 8 2020 6 17 浙江科技学院经济管理学院管工系 24 小结 线性规划问题要求目标函数和约束方程必须是线性函数 隐含如下假定 比例性假定 每个决策变量对目标函数的贡献与决策变量的值成比例 每个变量对约束条件左端的贡献与变量的值成比例 可加性假定
15、 任何变量对目标函数的贡献都与其他决策变量的值无关 一个变量对每个约束条件左端的贡献与该变量的值无关 连续性假定 可除性假定 允许每个决策变量值使用分数值 确定性假定 已经确切知道每个参数 价值系数 工艺系数 右侧常数 线性规划数学模型三个要素 决策变量目标函数约束条件 2020 6 17 浙江科技学院经济管理学院管工系 25 课堂习题P451 131 14 1 课后作业P461 14 2 1 15 2020 6 17 浙江科技学院经济管理学院管工系 26 二 线性规划模型标准形式 min max z c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a2
16、2x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 Free 线性规划模型的目标函数必须是变量的线性函数 约束条件必须是变量的线性等式或不等式 如右的问题就不是线性规划问题 1 一般形式 2020 6 17 浙江科技学院经济管理学院管工系 27 2 线性规划的标准形式 目标函数为极大化 约束条件全部为等号约束 所有变量全部是非负的 这样的线性规划模型称为标准形式maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 2020 6 17 浙江科技学院经济管理学院管工系 28 3 线性规划模型用矩阵和向量表示 maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 价值系数 工艺系数矩阵 资源约束 2020 6 17 浙江科技学院经济管理学院管工系 29 线性规划模型用矩阵和向量表示 续 因
