管理运筹学第一章线性规划ppt课件.ppt

管理运筹学 1 参考书目 运筹学基础及应用 第四版 清华大学出版社胡运权主编2006 5运筹学实用教程宁宣熙编著科学出版社2002 8运筹学沈荣芳主编机械工业出版社2002 1运筹学简明教程秦裕瑗主编高等教育出版社2002 7运筹学汤代焱主编中南大学出版社2002 3运筹学 第三版 清华大学出版社 运筹学 教材编写组编2005 6运筹学基础与运用哈工大胡运权主编2004 6运筹学余克艰主编中国商务出版社2006 3 2 绪论 3 运筹学 OperationsResearchOR 由于运筹学研究的广泛性和复杂性 人们至今没有形成一个统一的定义 以下给出几种定义 运筹学是一种科学决策的方法 运筹学是依据给定目标和条件从众多方案中选择最优方案的最优化技术 运筹学是一门寻求在给定资源条件下 如何设计和运行一个系统的科学决策的方法 4 运筹学与其他学科的关系运筹学与管理科学 ManagementScienceMS 关系 管理科学涵盖的领域比运筹学更宽一些 可以说 运筹学是管理科学最重要的组成部分 5 运筹学与其他学科的关系运筹学与系统科学 系统分析 工业工程的关系 系统科学 系统分析 工业工程等学科研究的内容比运筹学窄一些 6 运筹学研究的特点科学性 1 它是在科学方法论的指导下通过一系列规范化步骤进行的 2 它是广泛利用多种学科的科学技术知识进行的研究 运筹学研究不仅仅涉及数学 还要涉及经济科学 系统科学 工程物理科学等其他学科 7 运筹学研究的特点实践性运筹学以实际问题为分析对象 通过鉴别问题的性质 系统的目标以及系统内主要变量之间的关系 利用数学方法达到对系统进行最优化的目的 更为重要的是分析获得的结果要能被实践检验 并被用来指导实际系统的运行 8 运筹学研究的特点系统性运筹学用系统的观点来分析一个组织 或系统 它着眼于整个系统而不是一个局部 通过协调各组成部分之间的关系和利害冲突 使整个系统达到最优状态 9 运筹学研究的特点综合性运筹学研究是一种综合性的研究 它涉及问题的方方面面 应用多学科的知识 因此 要由一个各方面的专家组成的小组来完成 10 运筹学模型运筹学研究的模型主要是抽象模型 数学模型 数学模型的基本特点是用一些数学关系 数学方程 逻辑关系等 来描述被研究对象的实际关系 技术关系 物理定律 外部环境等 11 模型的分类按呈现和表达的方式可以分成 实物模型 规模缩小和放大的由实物制成的模型 如建筑模型 飞机模型 原子模型等 符号模型 用数学符号表示的模型 12 模型的分类按呈现和表达的方式可以分成 计算机模型 模型表现为可以在计算机上执行的由计算机语言表达的程序 13 模型的分类按描述方法的特点可以分成 描述性模型 这类模型仅仅描述实际发生的具体过程而不探讨过程背后的原因 许多统计模型 模拟模型和排队模型都是这类描述性模型 14 模型的分类按描述方法的特点可以分成 规范化模型 这类模型使用规范化的方法 对影响系统的内在规律进行探索 并详细描述系统的变量 目标和约束 大部分最优化模型属于这类模型 15 模型的分类按描述方法的特点可以分成 启发式模型 这类模型是一种经验模型 它主要由一些直观的经验和规则构成 16 模型的分类按模型变量和参数性质可以分成 确定性模型 模型的变量和参数都是确定的 如线性规划 整数规划 网络规划等模型 随机性模型 模型的变量和参数都是随机的 如排队模型 决策模型和对策模型等 17 模型的分类按模型是否考虑时间因素可分成 静态模型 模型只反映某一个固定时间点的系统状态 变量 参数与时间无关 动态模型 模型反映一段时间内系统变化的状态 变量 参数与时间有关 如动态规划模型等 18 运筹学模型的一个显著特点是它们大部分为最优化模型 一般来说 运筹学模型都有一个目标函数和一系列的约束条件 模型的目标是在满足约束条件的前提下使目标函数最大化或最小化 19 运筹学分析的主要步骤运筹学分析的主要步骤包括 发现和定义待研究的问题 构造数学模型 寻找经过模型优化的结果 并通过应用这些结果来改善系统的运行效率 20 真实系统 系统分析问题描述 模型建立与修改 模型求解与检验 结果分析与实施 数据准备 运筹学分析的步骤 21 运筹学包含的分支数学规划 线性规划 整数规划 目标规划 动态规划 网络规划等 图论与网络流决策分析 22 运筹学包含的分支排队论可靠性数学理论库存论对策论搜索论计算机仿真模拟等 23 运筹学的历史 都江堰水利工程战国时期 大约公元前250年 川西太守李冰父子主持修建 其目标是 利用岷江上游的水资源灌溉川西平原 追求的效益还有防洪与航运 其总体构思是系统思想的杰出运用 24 运筹学的历史 都江堰由三大工程及120多项配套工程组成 1 鱼嘴 岷江分水工程 将岷江水有控制地引入内江 2 飞沙堰 分洪排沙工程 将泥沙排入外江 3 宝瓶口 引水工程 除沙后的江水引入水网干道 25 运筹学的历史 它们巧妙结合 完整而严密 相得益彰 两千多年来 这项工程一直发挥着巨大的效益 是我国最成功的水利工程 26 运筹学的历史 丁谓的皇宫修复工程北宋年间 丁谓负责修复火毁的开封皇宫 他的施工工程方案是 先将皇宫前的一条大街挖成一条大沟 将大沟与汴水相通 使用挖出的土就地制砖 令与汴水相连形成的河道承担繁重的运输任务 修复工程完成后 实施大沟排水 并将原废墟物回填 修复成原来的大街 丁谓将取材 生产 运输及废墟物的处理用 一沟三用 巧妙地解决了 27 早期的军事运筹学特拉法加尔 Trafalgar 海战和纳尔森 Nelson 秘诀19世纪中叶 法国拿破伦统帅大军要与英国争夺海上霸主地位 而实施这一战略的最主要的关键是消灭英国的舰队 英国海军统帅 海军中将纳尔森亲自制定了周密的战术方案 运筹学的历史 28 1805年10月21日 这场海上大战爆发了 英国是纳尔森亲自统帅的地中海舰队 由27艘战舰组成 另外一方是由费伦纽夫 Villenuve 率领的法国 西班牙联合舰队 共有33艘战舰 特拉法加尔 Trafalgar 大海战的概况是 费伦纽夫 Villenuve 率领的法国 西班牙联合舰队采用常规的一字横列 以利炮火充分展开 而纳尔森的战术使费伦纽夫大出意外 29 英国的舰队分成两个纵列 前卫上风纵列由12艘战舰组成 由纳尔森亲自指挥 拦腰将法国 西班牙联合舰队切为两段 后卫下风纵列由英国海军中将科林伍德 Collingwood 指挥 由15艘战舰组成 在一场海战后 法国 西班牙联合舰队以惨败告终 联合舰队司令费伦纽夫连同12艘战舰被俘 8艘沉没 仅13艘逃走 人员伤亡7000人 而英国战舰没有沉没 人员伤亡1663人 可惜的是 作为统帅的纳尔森阵亡 30 秘密备忘录中的英国统帅纳尔森 Nelson 的秘诀 预期参加战斗的英国舰队 40艘 法国 西班牙联合舰队 46艘 预计联合舰队战斗队形一字横列 英国舰队的战斗队形与任务 分成两个主纵列及一个小纵列 运筹学的历史 31 主纵列1 16艘 由纳尔森亲自指挥 拦腰将法国 西班牙联合舰队切为两段 并攻击联合舰队的中间部分 主纵列2 16艘 由英国海军中将科林伍德指挥 从联合舰队后半部再切断 分割并攻击后部12艘 小纵列 8艘 在中心部分附近攻击其先头部分的3 4艘 运筹学的历史 32 英舰进攻方向 运筹学的历史 33 兰彻斯特 F W Lanchester 作战分析兰彻斯特方程 设两军对抗中一方有x个战斗单位 战舰 战车 战机 步兵单位等 另外一方有y个战斗单位 基本假设 每一方战斗单位的损失率与对方战斗单位的数量成正比 运筹学的历史 34 于是 双方战斗损失的微分方程为 dy dt ax dx dt by 其中 a 0与b 0表示双方的平均战斗力 因此可以得到 ax2 by2上式称为兰彻斯特N2定律 运筹学的历史 35 用兰彻斯特N2定律可以对 纳尔森 Nelson 秘诀 进行分析 整体战斗实力 设双方单个战斗单位的战斗力相同 则有 英国舰队 402 1600联合舰队 462 2116此时联合舰队占优势 设想联合舰队全歼英国舰队后 联合舰队还有5161 2 23艘 2116 1600 1 2 36 将联合舰队拦腰切断 23 23 46 是将联合舰队实力减弱的最小分割法 此时 联合舰队的实力为 232 232 1058而英国舰队的实力为 16 16 2 82 1088 已略占有优势 运筹学的历史 37 在英国舰队两个主纵列共32艘 攻击联合舰队的后一半23艘 此时 英国舰队实力 16 16 2 322 1064联合舰队的实力为 232 529 运筹学的历史 38 英国舰队已占有绝对优势 在全歼联合舰队后部后 英国舰队两个主纵列还可以保留 1064 529 1 2 5161 2 23艘再与小纵列中舰队联合对联合舰队前部作战还占有优势 即在最坏情况下 纳尔森 Nelson 秘诀 也可以使英国舰队获得胜利 运筹学的历史 39 运筹学的历史 232 82 593 232 529回马枪也占优势 运筹学的历史 40 第一章线性规划 41 第一章线性规划 1 1线性规划问题及其数学模型一 线性规划问题的性质线性规划问题是运筹学的重要分支 它表现为给出一线性数学模型 在一定的约束条件下求最佳值 进行优化处理 线性规划研究的问题主要有两类 一类是资源有限 如何安排使利润最大 另一类是当一项任务确定后 如何统筹安排 用最少的人力 物力 财力资源去完成该项任务 这类寻求整个问题的某个整体指标最优的问题在经济领域最为普遍 42 第一章线性规划 下述问题称为线性规划求X1 X2 Xn一组决策变量 使得f X1 X2 Xn 取极大或极小 且满足 gi X1 X2 Xn 0i 1 2 mhj X1 X2 Xn 0j 1 2 n且g h皆为线性函数 43 第一章线性规划 二 线性规划模型例1 某厂用原料1 2制作产品A B 有关资料如下 又知 B产品超过30件部分盈利打九折 A产品不得低于5件 求最佳生产安排 44 第一章线性规划 解 1 设决策变量设产品A B各应生产X1件 X2件可获最大利润 2 建模目标函数 一 maxP 4X1 6X22X1 5X2 250约束条件3X1 4X2 200X1 5X2 30变量条件X1 0 X2 0且为整数 B产品不超过30件条件下的最优规划 45 第一章线性规划 目标函数 二 maxP 4X1 5 4X2 6 302X1 5X2 100 B产品已耗原料1 约束条件3X1 4X2 80 B产品已耗原料2 X1 5X2 0变量条件X1 0 X2 0且为整数 B产品超过30件条件下的最优规划 以上两模型可合二为一 46 第一章线性规划 合二为一 maxP 4X1 6X2 5 4X32X1 5 X2 X3 250S t3X1 4 X2 X3 200X1 5X2 30X1 0 X2 0 X3 0且为整数式中X3为B产品超过30件部份 X3 0即为模型 一 线性规划求解 结论 产品A应生产5件 产品B应生产46件 最大利润为286 4百元 47 第一章线性规划 例2 某厂生产甲 乙 丙三种产品 有关资料如下 48 第一章线性规划 1 求利润最大的线性规划设甲 乙 丙三产品各应生产X1 X2 X3件可获最大利润 maxP 2X1 3X2 4X33X1 5X2 4X3 150S t5X1 X2 6X3 100X1 0 X2 0 X3 0 49 50 第一章线性规划 2 求利润不少于100百元 动用原材料最省的线性规划minZ 5X1 X2 6X32X1 3X2 4X3 100S t3X1 5X2 4X3 150X1 0 X2 0 X3 0 51 52 第一章线性规划 例3 某车间用10米钢管截4米 3米两种规格零件各100根 问如何截法使材料最省 解 设X 为第i种方案用料根数 53 第一章线性规划 建模 minZ X2 2X3 余料总数最省 X1 2X3 100s t2X1 3X2 100X1 0 X2 0 X3 0且为整数或 minZ X1 X2 X3 用料总根数最少 X1 2X3 100s t2X1 3X2 100X1 0 X2 0 X3 0且为整数 落料问题 54 第一章线性规划 1 2两变量图解法例4 某公司生产A B两种产品 有关消耗及盈利资料如下 55 问 如何安排生产可使利润总额最大 设A B两种产品各应生产X1件和X2件可获最大利润 maxP 5X1 3X24X1 3X2 18S t4X1 2X2 16X1 0 X2 0因为是两变量 可用图解法求解 第一章线性规划 56 第一章线性规划 X2L1 4X1 3X2 188L2 4X1 2X2 166 0 6 L3 X1 0 L4 X2 042可行域 3 2 0 0 0123456X1 4 0 4X1 3X2 184X1 2X2 16 57 P 0 0 0 P 4 0 20百元 P 3 2 21百元 P 0 6 18百元 maxP P 3 2 21百元所以X X1 X2 T 3 2 TP 2100元也可将目标函数直线切割可行域 所交最远顶点座标即为最优解 代入目标函数为最优值 结论 A产品生产3件 B产品生产2件可获最大利润2100元 也可用目标函数直线沿其法矢线向外推至可行域最远 高 点 该点座标即为最优解 代入P得最优值 第一章线性规划 58 第一章线性规划 X2L1 4X1 3X2 188L2 4X1 2X2 166 0 6 L3 X1 0 L4 X2 05x1 3x2 212可行域 3 2 0 0 0123456X1 4 0 4X1 3X2 185x1 3x2 k4X1 2X2 16 4 59 第一章线性规划 如果目标函数改为maxP 4X1 2X2 切割线外推将与约束方程直线4X1 2X2 16重合 此时可行域边界上任一点都是最优解 有无穷多组最优解 注意 凡目标函数与约束方程相同或成比例 有多重最优解 如果约束不等式的不等号改为大于等于 可行域不封闭 切割线向外切割的边界在无穷远处 此时称为无界最优解 俗称无界解 即无限最优 但将目标函数改为min则存在最优解X 3 2 T Z 21百元 60 第一章线性规划 如果约束方程右端常数改为 4X1 3X2 18 1 4X1 2X2 16 2 由 1 2 4X1 3X2 2因决策变量为负 本问题无解 即本问题不可行 61 线性规划可行域和最优解的几种情况 1 可行域封闭唯一最优解 2 可行域封闭多重最优解 3 可行域开放唯一最优解 4 可行域开放多重最优解 5 可行域开放目标函数无界 6 无可行解 62 maxz x1 2x2s t x1 x2 3x2 1x1 x2 0 maxz x1 2x2s t x1 x2 x3 3x2 x4 1x1 x2 x3 x4 0 x1 0 x2 0 x3 3 x4 1基础可行解 x1 0 x4 0 x2 1 x3 2基础可行解 x2 0 x3 0 x1 3 x4 1基础可行解 x3 0 x4 0 x1 2 x2 1基础可行解 x1 0 x3 0 x2 3 x4 2是基础解 但不是可行解 O A B x3 0 x4 0 x2 0 x1 0 C D 可行域 63 x2 0 x1 0 x3 0 x4 0 O A B C 单纯形法原理 叠代过程回顾 第一次叠代x2进基 x4离基 第二次叠代x1进基 x3离基 x1 x2 x3 x4 0 0 3 1 z 0 x1 x2 x3 x4 0 1 2 0 z 2 x1 x2 x3 x4 2 1 0 0 z 4最优解 64 第一章线性规划 1 3线性规划问题的标准形式一般线性规划问题可写成下列形式 Max min Z C1X1 C2X2 CnXn 65 第一章线性规划 式中aij bi Cj均为实常数 bi 0 反之两端乘以 1 为了将不等式化为等式约束 可引进松弛变量 如果第i个约束方程为 ai1X1 ainXn bi或ai1X1 ainXn bi 1 i m 则可添加一个松弛变量Xn i 0 使之成为等式 ai1X1 ainXn Xn i biai1X1 ainXn Xn i bi 66 松驰变量与线性规划的标准式 化标准形式maxz x1 2x2s t x1 x2 x3 3x2 x4 1x1 3x2 x5 x6 2Xj 0 j 1 6 maxz x1 2x2s t x1 x2 3x2 1x1 3x2 2x1 x2 0 增加的变量x3 x4 x5称为松驰变量 X6称为剩余变量 67 第一章线性规划 Max min Z S t 从而使线性规划问题化为标准形式 68 第一章线性规划 其矩阵向量表述形式 69 第一章线性规划 以上方程组中m个方程 n个变量 且n m 有个基本解 将X分为两部分 基本变量XB 非基本变量XN 则有X XBXN T其中 XB x1 x2 xm T XN xm 1 xm 2 xn T同理 C CBCN CB c1 c2 cm CN cm 1 cm 2 cn A BN 70 第一章线性规划 N Pm 1Pm 2 Pn Pj为非基变量Xj的系数向量 原式 maxZ CX CBCN XBXN Ts tAX BN XBXN T bX 0即maxZ CBXB CNXNs tBXB NXN bX 0 71 第一章线性规划 由约束 XB B 1b B 1NXN代回目标函数maxZ CBB 1b CBB 1NXN CNXN CBB 1b CN CBB 1N XN Z0 72 第一章线性规划 因为XN 0 欲使Z值得到改进 只有希望 若目标函数是MaxZ 则希望CN CBB 1N 相对收益系数 当所有非基变量相对收益系数都小于等于 时 获最优解 若目标函数是minZ 则希望CN CBB 1N 相对支付系数 这样Z值才可能得到改进 当所有的非基变量的相对支付系数都大于0时 获得最优解 73 第一章线性规划 目标函数 MaxZ MinZ 相对收益系数CN CBB 1N 相对支付系数CN CBB 1N 目标函数改进条件 相对收益系数CN CBB 1N 相对支付系数CN CBB 1N 最优性条件 74 第一章线性规划 有些线性规划问题并非所有的决策变量都取非负值 于是产生自由变量 可正可负 此时可作如下处理 例5 minZ X1 3X2 4X3X1 2X2 X3 5 s t2X1 3X2 X3 6 X1不定 X2 0 X3 0解 由式 X1 5 2X2 X3代入 及目标函数 得等价问题 minZ X2 3X3 常数去除 s tX2 X3 4 2 X2 0 X3 0将自由变量X1消去 75 第五章线性规划 通过观察 解得X2 4 X3 0代入 式X1 5 2 4 0 3原问题minZ X2 3X3 4X 3 4 0 TZ 4满足约束 3 2 4 0 5 2 3 3 4 0 6 76 第一章线性规划 例6 maxZ 50X1 19X2 3X3S t10X1 4X2 X3 182X1 1 2X2 3X1 0 X2 0 X3不定令X3 X4 X5 X4 0 X5 0原式 maxZ 50X1 19X2 3 X4 X5 10X1 4X2 X4 X5 X6 18s t2X1 1 2X2 X7 3Xj 0j 1 2 4 5 6 7X6 X7为松弛变量 77 第一章线性规划 例7 MinZ 3X1 4X3 50X5s t3X1 4X2 3X3 6X4 123X1 6X2 4X5 12X1 0 X2 0 X3 0 6 X4 10 8 X5 15解 令X6 X4 6 0 X4 X6 6 0 X6 16X7 X5 8 0 X5 X7 8 0 X7 7则 78 第一章线性规划 minZ 3X1 4X3 50 X7 8 3X1 4X2 3X3 6 X6 6 12S t3X1 6X2 4 X7 8 12X6 16X7 7Xj 0 j 1 2 3 6 7化标准形 minZ 3X1 4X3 50X7S t3X1 4X2 3X3 6X6 483X1 6X2 4X7 44X6 X8 16X7 X9 7Xj 0 j 1 2 3 6 7 8 9 79 第一章线性规划 1 4线性规划问题解的性质一 几个基本概念 一 可行解 基本解 最优解 基本最优解设L P问题 Max Min Z CXs tAX bX 0我们把满足约束条件的X 0 称为线性规划问题的可行解 可行域内任意一点或一组解 约束方程交点称为基本解 位于可行域角点的解称为基本可行解 80 第一章线性规划 若X 0 0或X 0 的非零分量所对应的系数向量线性无关时 称可行解X 0 为基本可行解 使目标函数取最大值或最小值的解称为最优解 使目标函数取最大值或最小值的基本可行解称基本最优解 81 第一章线性规划 D A B C A 可行解 B 基本解 C 最优解 D 全部解 A B 基本可行解 D A 不可行解 A B C 基本可行最优解 82 第一章线性规划 二 凸集若连接n维点集D中任意两点X 1 X 2 的线段仍然D内 则称D为凸集 其数学表达式为 X X X 1 1 X 2 0 1 X 1 D X 2 D D D凸凸集又分为闭凸集和开凸集 闭凸集为封闭集 开凸集为开放集 83 第一章线性规划 三 极点 隅点 若凸集D中的点X不能成为D中任何线段的内点 则称X为D的极点 其数学表达式 点X X 1 X 2 D 当且仅当X X 1 X 2 时成立 X X 1 1 X 2 0 1称X为D的极点 84 第一章线性规划 例8 画出集合 X1X2 X1 X2 2 X1 0 X2 0 X221X1 2 1012X1 X2 2 可行域 开凸集 85 第一章线性规划 在可行域中任取两点 X 1 0 X 2 0显然有 AX 1 X1 1 X2 1 2 AX 2 X1 2 X2 2 2令X X 1 1 X 2 0AX AX 1 1 AX 2 X1 1 X2 1 1 X1 2 X2 2 2 1 2 2 X D D凸 86 第一章线性规划 二 线性规划问题解的性质定理1线性规划问题的可行解集为凸集即连接线性规划问题任意两个可行解的线段上的点仍是可行解 证 设L P问题的可行解集为D X AX b X 0 其中任意两个可行解 X 1 D X 2 D X 1 X 2 因为X 1 0 X 2 0所以X X 1 1 X 2 00 1若能得证X D 则得证D凸 87 第一章线性规划 因为AX 1 b AX 2 b所以 AX AX 1 1 AX 2 b 1 b b即X作为X 1 X 2 两可行解连线上任一点仍是可行解 所以X D 即得证D凸 88 第一章线性规划 定理2可行解集D中的点X是极点的充分必要条件X是基本可行解 证 不失一般性 假设基本可行解X的m个分量为正X1P1 X2P2 XmPm b1 1 89 第一章线性规划 现分两部分来证明 1 若X是可行域S的顶点 则一定是基本可行解 反证法 若X不是基本可行解 则其分量所对应的系数向量P1P2 Pm必线性相关 即存在一组不全为零的数 ii 1 2 m使 1P1 2P2 mPm 0用 0 乘上式 1P1 2P2 mPm 0 2 90 第一章线性规划 1 2 X1 1P1 X2 2P2 Xm mPm b 1 2 X1 1P1 X2 2P2 Xm mPm b取 X 1 X1 1 X2 2 Xm m 0 0 X 2 X1 1 X2 2 Xm m 0 0 当 足够小时 有X 1 0 X 2 0分别代入 1 式 有 91 第一章线性规划 所以X 1 X 2 为可行解 并且X 1 2X 1 1 2X 2 X1X2 Xm 0 0 因此 X不是可行解集的极点 与假设矛盾 从而得证X为S的极点时 P1P2 Pm线性无关 即X为基本可行解 92 第一章线性规划 2 再证充分性若X是基本可行解 则一定是可行域S的顶点反证法 当X 0 显然X必为极点 所以只需证当X 0时 若X的非零分量对应的列向量P1P2 Pm线性无关 则X一定为极点 假设X不是可行域的顶点 则在可行域S中可找到不同的两个点 X 1 X1 1 X2 1 Xm 1 T X 2 X1 2 X2 2 Xm 2 TX 1 X 2 使X X 1 1 X 2 0 1 93 第一章线性规划 因X是基本可行解 故当j m时 有Xj Xj 1 Xj 2 0 于是有 与两者相减 94 第一章线性规划 由于X 1 X 2 所以上式Xj 1 Xj 2 中至少有些分量不为零 故向量组P1P2 Pm线性相关 即X不是基本可行解 也就不可能位于可行域顶点 与假设矛盾 所以X是基本可行解 且在可行域顶点 定理3最优解可以在闭凸集极点上达到 证 设X 1 X 2 X K 是可行域S的顶点 若X 0 不是顶点 且目标函数在X 0 处达到最大值Z CX 0 因为X 0 不是顶点 所以它可以用可行域S的上述K个顶点线性组合为 95 第一章线性规划 我们在所有的顶点中必然能找到某一顶点X m 使得CX m 是所有CX i 中的最大者 并且将X m 代替上式中X i 则有 96 第一章线性规划 所以有CX 0 CX m 由假设CX 0 是最大值 所以只有CX 0 CX m 得证X 0 也是极点 即最优解只能在极点上达到 定理3使我们可从有限极点中找到最优解而不必遍寻可行域 97 第一章线性规划 1 5线性规划建模应用例9 某厂的机修车间有A B C三种机床 为使机床能尽量得到运用 车间承接了一项小规模制造任务 共生产两种产品 产品1的产值为每件11元 产品2的产值为每件5元 每件产品所需要的机床加工时间见下表 试制定这项生产任务的最优产量计划 98 第一章线性规划 情况一 使产值最大的规划 解 设产品1生产了X1件 产品2生产了X2件可获最大产值 maxZ 11X1 5X21 2X1 1 4X2 40S t1 2X1 1 2X2 50X2 80X1 X2 0且为整数 99 第一章线性规划 情况二 使机床时间利用率最大的规划解 设产品1生产了X1件 产品2生产了X2件可使机床利用率最大 MaxZ 1 2X1 1 2X1 1 4X2 1 2X2 X2 X1 7 4X21 2X1 1 4X2 40S t1 2X1 1 2X2 50X2 80X1 X2 0且为整数 100 第一章线性规划 例10 某企业现有资金1000万 有两种投资途径可供选择 A 贷给其他企业 每年可获息8 而且第二年即可收回 B 自己投资扩大生产 但第二年还需继续投入第一年投资额的60 而第三年可有等于第二年总投资数1 8倍的收入 为使第三年 第二年末 时该企业有最大的资金额 试确定资金使用方案 101 第一章线性规划 解 设第1年贷款X1万元 投资X2万元 可知第二年尚需投资0 6X2元 MaxZ 1 8 1 0 6 X2X1 X2 1000S t1 08X1 1000 X1 X2 0 6X2X1 X2 0 投资题计算结果 第1年放贷与投资总额不得超过1000万元 第2年放贷收益加剩余现金全用于投资 但必须为第1年投资额的60 102 103 第一章线性规划 配料问题设n种原料B1B2 Bn制成具有m种成份A1 A2 Am的产品 其所含各成份需要量分别不低于a1 a2 am 各种原料的单价以及各种原料所含的数量如下表所示 问如何配料使满足最低成份需求下产品总成本最低 104 第一章线性规划 105 第一章线性规划 设从原材料Bj中取Xj单位 j 1 2 n 目标函数minS 产品总成本最低 约束条件 106 第一章线性规划 例11 某医院为病人合理安排营养 每天摄入VA VB VC VE分别不得少于45克 58克 90克 38克 每公斤水果 蔬菜 肉类 鱼类中所含上述维生素成份如下 107 第一章线性规划 问如何配料使满足最低成份需求下产品总成本最低 设病人从食品Bj中取用Xj单位 j 1 2 3 4 目标函数minS 10X1 7X2 15X3 18X420X1 50X2 90X3 32X4 45约束条件60X1 25X2 16X3 24X4 58120X1 88X2 24X3 18X4 9030X1 12X2 50X3 8X4 38Xj 0 j 1 2 3 4 108 第一章线性规划 例12某糖果厂用原料A B C加工三种不同牌号的糖果甲 乙 丙 已知各种牌号的糖果中A B C含量 原料成本 各种原料的每月限制用量 3种牌号的糖果的加工费及售价如下 109 第一章线性规划 问 该厂每月应生产这3种糖果各多少公斤 可使该厂获利最大 试建立数学模型 110 第一章线性规划 解 设甲 乙 丙产品的编号为i i 1 2 3 原料A B C编号为j j 1 2 3 Xij表示产品i中含有原料j的量 于是有 maxP 3 40 0 5 X11 X12 X13 2 85 0 4 X21 X22 X23 2 25 0 3 X31 X32 X33 2 X11 X21 X31 1 5 X12 X22 X32 X13 X23 X33 2 9X11 1 4X12 1 9X13 0 45X21 0 95X22 1 45X23 0 05X31 0 45X32 0 95X33 111 第一章线性规划 X11 X21 X31 2000 公斤 每月A原料限制 X12 X22 X32 2500 公斤 每月B原料限制 X13 X23 X33 1200 公斤 每月C原料限制 X11 0 6 X11 X12 X13 产品甲中原料A下限 X21 0 15 X21 X22 X23 产品乙中原料A下限 S tX13 0 20 X11 X12 X13 产品甲中原料C上限 X23 0 60 X21 X22 X23 产品乙中原料C上限 X33 0 50 X31 X32 X33 产品丙中原料C上限 Xij 0ij 1 2 3 变量非负条件 糖果生产例子 112 第一章线性规划 1 6单纯型法表格计算 极大化 一 基本思路 根据问题的标准 从可行解域中某个基本解 可行域中某一顶点 开始 转换到另一个基本可行解 顶点 并且使目标函数达到最大值时 问题获最优解 例11 maxZ 5X1 3X2 0X3 0X4S t4X1 3X2 X3 18 4X1 2X2 X4 16 Xj 0j 1 2 3 4 113 第一章线性规划 X3 18 4X1 3X2 X4 16 4X1 2X2 初始基变量XB0 X3 X4 T 18 16 T初始解X0 0 0 18 16 T 初始值Z0 0CN C1 C2 5 3 maxCj max 5 3 5 C1即X1每增加1 Z增加5 让X1进基 由式 知X1的最大增量为4 min 18 4 16 4 4 最小比值 以 X1 X2 T 4 0 T代入式 得 X3 2 X4 0X4出基 114 第一章线性规划 从式 X3 2 X2 X4 从式 X1 4 1 2X2 1 4X4 式代入Z Z 20 5 2X2 5 4X4 3X2 20 1 2X2 5 4X4maxCj C2 1 2 即X2每增加1 Z增加1 2 X2的最大增量 min 2 1 4 1 2 2以 X2 X4 T 2 0 T代入式 式 X3 0 即X3出基 改进基变量XB1 X3 X1 T 2 4 T改进值Z1 5 4 0 2 20 115 第一章线性规划 X1 3 1 4X4 X2 2 X3 X4 代入Z Z 21 3X3 17 4X4CN C3 C4 0 优化结束 最优解X X1 X2 T 3 2 T最优值Z 21 改进基变量XB2 X2 X1 T 2 3 T改进值Z2 5 3 3 2 15 6 21由式 116 第一章线性规划 分析解法 4X1 3X2 18 X3X1 3 1 2X3 3 4X4 4X1 2X2 16 X4X2 2 X3 X4 将 两式代入目标函数Z Z 21 1 2X3 3 4X4欲ZZmax令X3 X4 0得 X X1 X2 T 3 2 TZ 21 117 第一章线性规划 二 初始可行解的确定对于方程组 a11x1 a12x12 a1nxn b1a21x1 a22x12 a2nxn b2 am1x1 am2x12 amnxn bm可取出最大线性无关组 从而得到基础解系 以非基本变量来线性组合基本变量 由 1 118 第一章线性规划 2 119 第一章线性规划 XB X1 X2 Xm T XN Xm 1 Xm 2 Xn T当Am n的秩r A m满秩时 我们可得到一组基本可行解 当 2 式中a1 a2 am全部非负时 符合线性规划约束的解称为基本可行解 120 第一章线性规划 三 基变换若初始基可行解X 0 不是最优解 又不能证明是无界解时 需找一个新的基本可行解 在原可行解基矩阵中换一个列向量Pj 线性独立 得到一个新的基本可行解