MBA学位课程-运筹学1(ppt125).ppt

1 运筹学 OperationResearch MBA学位课程 衷心希望本课程能让大家受益 此建颐料葱铲叹黔储抒乞夏卫浇隘辽晨晃嫁纲腕脏仑粥瞄责掀胃墅揭爱铭MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 2 教师介绍姓名 刘满凤职称 副教授博士单位 信息管理学院电话 3816922 O 3816926 H E mail liumanfeng 课程考核评分方法 平时成绩分占40 其中课堂讨论5 平时作业5 大作业30 课程考试分占60 授课计划总时数 48课时授课时数 46课时其中课堂授课42课时 上机授课4课时案例讨论 2课时 页胀只岭侮桂柔餐歪绑食谁雪玄氓死待增楷肌逾弹魁床偿虏寡综撵神盟煎MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 3 课程内容简介与学习要求 课程内容简介 运筹学是一门应用性学科 它主要是应用定性分析和定量分析相结合的方法 通过建立实际问题的数学模型 应用合适的优化算法对模型进行求解 从而解决实际问题 其主要内容有 线性规划 整数规划 非线性规划 动态规划 图与网络分析 排队论 存贮论 对策论 决策论 多目标规划等 本课程选取了运筹学在经济管理领域中常用的五个部分作为教学内容 即 线性规划 整数规划 动态规划 图与网络分析 对策论 学习要求 本课程将通过重点讲授原理方法 上机解题 个人研究与小组讨论相结合的案例分析等环节 培养学员全局优化的思想 使学员掌握若干类常用的运筹学模型 并能用其解决经济管理中的复杂问题 因此要求学员 对布置的思考 案例讨论题进行认真准备 按进度完成平时作业和上机练习 按要求完成大作业书面报告 参考资料 1 刘满凤 付波 聂高飞编著 运筹学模型与方法教程例题分析与题解 清华大学出版社 2001年 2 运筹学 教材编写组编 运筹学 修订版 清华大学出版社 1996年 3 蓝伯雄 程佳惠 陈秉正编著 管理数学 下 运筹学 清华大学出版社 1998年 4 中山 四川 西北 武汉 湘潭大学编 运筹学 经济管理决策方法 四川大学出版社 1995年 5 韩大卫编著 管理运筹学 大连理工大学出版社 1998年 6 胡运权主编 运筹学习题集 修订版 清华大学出版社 1985年 耻夷蔼刑夕轴宅辕窟讯棺舌匹新解期葵秋妥誓账叉璃挥脖德脊滔妆宵惶氮MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 4 本课程内容安派 第一部分线性规划及其应用 1 问题的数学模型与求解2 单纯形法与计算机求解3 对偶理论与灵敏度分析4 运输问题及其解法5 指派问题及其解法6 整数线性规划问题及其解法 第二部分动态规划 1 动态规划的基本概念和最优化原理2 动态规划模型的建立和求解方法3 建模训练与求解 第三部分对策论模型 第四部分图与网络分析 1 两人有限零和对策模型及其解法2 两人有限非零和对策 1 图与网络的基本概念2 树与最小树3 最短路问题4 最大流问题5 最小费用最大流问题 境捏孟负惫节件靳庐造唬奔蛙屡宠材贝纯盆创永抬焙扒厄壁橱怖抖凋憋坊MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 5 绪论一 运筹学的历史与发展国际上运筹学的思想可追溯到1914年 当时的兰彻斯特提出了军事运筹学的作战模型 1917年 丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时 提出了埃尔朗公式 研究了随机服务系统中的系统排队与系统拥挤问题 存储论的最优批量公式是在20世纪20年代初提出的 夯沥毕沁农枝娟懦愉延睫喻业幂敢奄洋勋姐纂要波蠕赁缸殴剿挖啃俄佐隆MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 6 二次世界大战时期 德国空军对英伦三岛狂轰滥炸 为对付敌人的空袭 英国人使用了雷达 但没有科学的布局 防空系统的效率并不很高 为解决这个问题 英国军方于1939年9月从全国各地调来一批科学家 共11人 他们中有将军1人 数学家2人 理论物理学家2人 应用物理学家1人 天体物理学家1人 测量学家1人 生物学家3人 来到英国皇家空军指挥部 组成了以著名的物理学家 诺贝尔奖金获得者P M S Blacket为核心的世界上第一个运筹学小组 他们的任务就是应用系统论的观点 统筹规划的方法研究作战问题 这个运筹学小组在作战中发挥了卓越的作用 受到英国政府极大的重视 攒呛晕哮呢鸥郑耳烫驾讥张字叼固慌怀议藕赂潜浑楚作娟荐恿羊坛痪晋甩MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 7 于是 英国政府逐渐在它的海陆空三军中都成立了运筹学小组 美国参战以后 也仿效英国在军队中成立了运筹学小组 在生产管理方面的应用 最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题 并给出解乘数法的求解方法 出版了第一部关于线性规划的著作 生产组织与计划中的数学方法 但当时并没有引起重视 直到1960年康特洛为奇再次出版了 最佳资源利用的经济计算 才受到国内外的一致重视 为此康特洛为奇获得了诺贝尔经济学奖 线性规划提出后很快受到经济学家的重视 如二次世界大战中从事运输模型研究的美国经济学家库普曼斯 T C Koopmans 他很快看到了线性规划在经济中应用的意义 并呼吁年轻的经济学家要关注线性规划 其中阿罗 萨谬尔逊 西蒙 多夫曼和胡尔威茨等都获得了诺贝尔奖 姑肝稚也威史琼集橡淋自号档田疟样丧迅鸣岁塘帕舷爸发隘念班筹芥挞烧MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 8 50年代中期 钱学森 许国志等教授在国内全面介绍和推广运筹学知识 1956年 中国科学院成立第一个运筹学研究室 1957年运筹学运用到建筑和纺织业中 1958年提出了图上作业法 山东大学的管梅谷教授提出了 中国邮递员问题 1970年 在华罗庚教授的直接指导下 在全国范围内推广统筹方法和优选法 1978年11月 在成都召开了全国数学年会 对运筹学的理论与应用研究进行了一次检阅 1980年4月在山东济南正式成立了 中国数学会运筹学会 1984年在上海召开了 中国数学会运筹学会第二届代表大会暨学术交流会 并将学会改名为 中国运筹学会 在中国 最早的运筹学思想有战国时期的田忌赛马 它是对策论的一个典型例子 北宋时期的丁渭造皇宫 它是统筹规划的一个例子 豁差捍埂崎舟奈僧浴弓目姓掣薛扒揖狈飘君眠枪疥垃拍湍错枯蝴孜廷境桩MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 9 二 运筹学的基本内容 1 线性规划 LinearProgram 是一个成熟的分支 它有效的算法 单纯形法 主要解决生产计划问题 合理下料问题 最优投资问题 2 整数规划 IntegrateProgram 在线性规划的基础上 变量加上整数约束3 非线性规划 NonlinearProgram 目标函数和约束条件是非线性函数 如证券投资组合优化 如何合理投资使风险最小 4 动态规划 DynamicProgram 多阶段决策问题 是美国贝尔曼于1951年提出的 5 图与网络 GraphTheoryandNetwork 中国邮递员问题 哥尼斯堡城问题 最短路 最大流问题 舵窃爪署递暂缠容腐梢多另卑哆躯层他伐油黔颈膀悦劝光耪粳劳缄捻轧罕MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 10 6 存储模型 InventoryTheory 主要解决生产中的库存问题 订货周期和订货量等问题 7 排队论 QueueTheory 主要研究排队系统中的系统排队和系统拥挤现象 从而评估系统的服务质量 8 对策论 GameTheory 主要研究具有斗争性质的优化问题 9 决策分析 DecisionAnalysis 主要研究定量化决策 三 运筹学的工作步骤1 明确目标 收集资料 提出问题2 建立模型3 模型求解与检验4 结果分析与实施 拼炸驼五蒲洱收脏毗刘裂阶其同株孤燥汇烙吝侦榜杖墟绎忽坡违颐蘑熊伍MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 11 第一部分线性规划及其应用 线性规划研究的主要内容 线性规划主要解决两个方面的问题 1 对于给定的一项任务 如何统筹安排 使以最少的资源消耗去完成 2 在给定的一定数量的资源条件下 如何合理安排 使完成的任务最多 线性规划内容框架 昧箭魔领八魂鹏感突集诺滑躬言厢次贱邯尉褒土掘佐肢旨哈洱乒膊腿贵翱MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 12 届伦涩蜕嚎来疑稻靛俏芦祭傀必琴万迹牟门嘛旗惋坡累鄙盒加曳卢份钞肄MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 13 第一章LP问题的数学模型与求解 圃语扎谚烘赞课韦侨女礁脐逗搪割稳乍海轮拴茄怪鹊隐井厕倾娇砖兽雇粕MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 14 解 设x1 x2分别表示在计划期内生产产品 的产量 由于资源的限制 所以有 机器设备的限制条件 x1 2x2 8原材料A的限制条件 4x1 16 称为资源约束条件 原材料B的限制条件 4x2 12同时 产品 的产量不能是负数 所以有x1 0 x2 0 称为变量的非负约束 显然 在满足上述约束条件下的变量取值 均能构成可行方案 且有许许多多 而工厂的目标是在不超过所有资源限量的条件下 如何确定产量x1 x2以得到最大的利润 即使目标函数Z 2x1 3x2的值达到最大 滋探告疲趟祁剥儿冷唉为迅往蹦鹰熏猪黔恼乌疲债缎件珍褂孪鼠仕坪顺掂MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 15 综上所述 该生产计划安排问题可用以下数学模型表示 maxz 2x1 3x2 例2 营养配餐问题 假定一个成年人每天需要从食物中获取3000卡路里热量 55克蛋白质和800毫克钙 如果市场上只有四种食品可供选择 它们每千克所含热量和营养成份以及市场价格如下表所示 问如何选择才能使在满足营养的前提下使购买食品的总费用最小 壬页溃琉掌苗夺撤圈帘薪仕躲娄淄阅怨配涩趋黄千蚌听究瘦晰揖锨扁颇咽MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 16 解 设xj j 1 2 3 4 为第j种食品每天的购买量 则配餐问题数学模型为minz 10 x1 6x2 3x3 2x4 毛仰赌认卵忧套练滋肃押鳃康盏初诀女酋察旋摊犯蔡浅猪甩时却孽涅聊乐MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 17 例3运输问题 课本P6 某公司经销某种产品 三个产地和四个销地的产量 销量 单位运价如下表所示 问在保证产销平衡的条件下 如何调运可使总运费最少 伏谦英楞扁扎见禾去傅趟滑佃毒雀锭妒姚琐寞吕瞧蔼贝粥湖塞奇颂脂要畴MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 18 解 1 确定决策变量 设xij i 1 2 3 j 1 2 3 4 为从产地i运到销地j的运量 2 确定目标函数 总运费最小minz 3 确定约束条件 x11 x12 x13 x14 60产量约束 x21 x22 x23 x24 40 x31 x32 x33 x34 60 x11 x21 x31 30销量约束 x12 x22 x32 50 x13 x23 x33 40 x14 x24 x34 40 娘像炒吴魔闻郁搐旺靳装脸迎痉制幻闺颖疾磋哉迷副异诀况萎欣抠蛀岩同MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 19 非负约束xij 0 由此模型总结为 吓旦佐驮炎比条奏褐樱酌泉籽香腐掌新雾遍腥否脖茨上雀斯射雌悉此叮结MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 20 二 LP问题的模型 上述几例所提出的问题 可归结为在变量满足线性约束条件下 求使线性目标函数值最大或最小的问题 它们具有共同的特征 1 每个问题都可用一组决策变量 x1 x2 xn 表示某一方案 其具体的值就代表一个具体方案 通常可根据决策变量所代表的事物特点 可对变量的取值加以约束 如非负约束 2 存在一组线性等式或不等式的约束条件 3 都有一个用决策变量的线性函数作为决策目标 即目标函数 按问题的不同 要求目标函数实现最大化或最小化 蝶抑滓恫输轴陈峪孺汗方鼓拍勘霍评唾传龋溉尚葵各串柏尖疮匡涛壁洱躁MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 21 满足以上三个条件的数学模型称为LP问题的数学模型 其一般形式为 max 或min z c1x1 c2x2 cnxn 1 1 1 2 1 3 或紧缩形式 囤障归假硼柔曰钝焊垛岂缸购楷字恨融馅舟痈恒痘裴允角仅殉附棵狐看洒MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 22 或矩阵形式 或向量形式 max 或min z cx 其中c c1 c2 cn 称为价值系数向量 称为技术系数矩阵 也称消耗系数矩阵 躯辰迷瘦决榴锁庇菌献郝亚肯纲绝姚撤讨熔蛛吴砌温忍煎仁溃识掂札渐蝗MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 23 称为资源限制向量 X x1 x2 xn T称为决策变量向量 下面我们再来看两个实际例子 引例3课本P60例25 投资计划问题 某公司经调研分析知 在今后三年内有四种投资机会 第 种方案是在三年内每年年初投资 年底可获利15 并可将本金收回 第 种是在第一年的年初投资 第二年的年底可获利45 并将本金收回 但该项投资不得超过2万元 第 种是在第二年的年初投资 第三年的年底可获利65 并将本金收回 但该项投资不得超过1 5万元 第 种是在第三年的年初投资 年底收回本金 且可获利35 但该项投资不得超过1万元 现在本公司准备拿出3万元来投资 问如何计划可使到第三年年未本利和最大 材嗡雇斟座姓霄嗓渔慧既骚峭柳帖裸拉遗钳桂萧寥釜炼彬簇梧窜歪予薄埃MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 24 解 问题分析 该问题的实际投资背景如下表所示 1 确定决策变量 设xij表示第i年对第j个方案的投资额 i 1 2 3 j 1 2 3 4 年份一二三四x111 15x11x121 45x12x211 15x21x231 65x23x311 15x31x341 35x34 粪声孕眼蛰炕敦腹尖直星府兑群囤剪晶执江涝慎占柞鸦获潦瓦汝料掀又驴MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 25 2 确定目标函数 第三年年未的本利和为maxz 1 65x23 1 15x31 1 35x34 3 确定约束条件 每一年的投资额应等于当年公司拥有的资金数 x11 x12 3x21 x23 1 15x11x31 x34 1 45x12 1 15x21 每个方案投资额的限制 x12 2x23 1 5非负约束 xij 0 i 1 2 3 j 1 2 3 4x34 1 轿元娶园呵聂螟荡丝捉厄垛虏勿剑狮纶中板使栈毒靛佳局陶黔短级缮骇懈MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 26 引例4 合理下料问题 要用一批长度为7 4米的园钢做100套钢架 每套钢架由2 9米 2 1米 1 5米的园钢各一根组成 问 应如何下料才能使所用的原料最省 解 问题分析 一根长度为7 4米的园钢 要裁出2 9米 2 1米 1 5米的料有多种裁法 如可裁出一根2 9米 二根2 1米 也可裁出三根2 1米的 这样我们把所有裁法列举出来 如下表所示 下料方案根数一二三四五六七八长度米2 9111200002 1201012301 503113204合计7 17 46 57 36 67 26 36料头 米 0 300 90 10 80 21 11 4 嗡馏周符叔矿损棋臃瞄缉每料冯撤膀馒漆既其垮玉秃瓮树拧匹赃知镣疗由MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 27 1 确定决策变量 设xj表示按第j种方案所用的园钢的数量 2 确定目标函数 问题要求所用原料最省 所用原料为 minz x1 x2 x3 x4 x5 x6 x7 x8 3 确定约束条件 2 9米园钢的数量限制x1 x2 x3 2x4 1002 1米园钢的数量限制2x1 x3 x5 2x6 3x7 1001 5米园钢的数量限制3x2 x3 x4 3x5 2x6 4x3 100非负限制xj 0 且为整数 j 1 2 8 建立线性规划模型的一般步骤 1 确定决策变量 2 确定目标函数 3 确定约束条件 桃灵或捞岁控奋潜蹄幢恕磺磅痛专糊姨刀选缝猫缄世驴母捂汇弯耿闻档纶MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 28 引例5 一个木材储运公司有很大的仓库用以储运出售木材 由于木材季度价格的变化 该公司于每季度初购进木材 一部分于本季度内出售 一部分储存起来以后出售 已知该公司仓库的最大储存量为2000万米3 储存费用为 70 100u 千元 万米3 u为存储时间 季度数 已知每季度的买进卖出价及预计的销售量如下表所示 由于木材不宜久贮 所有库存木材应于每年秋末售完 为使售后利润最大 试建立这个问题的线性规划模型 粘弊贸铰蛤男挂珍求绿婆戮槐缸费铰辐戏辐绊电熔责稼恿戌妮淘弯痪卒垛MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 29 设yi分别表示冬 春 夏 秋四个季度采购的木材数 xij代表第i季度采购的用于第j季度销售的木材数 漠骄外泡虞检勿克屹田特延父奶梳雅趋撮宁冶携域谨误斤聊怖左茧聪阀撞MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 30 引例6 有一艘货轮 分前 中 后三个舱位 它们的容积与最大允许载重量如表1所示 现有三种货物待运 已知有关数据列于表2 为了航运安全 要求前 中 后舱在实际载重量上大体保持各舱最大允许载重量的比例关系 具体要求前 后舱分别与中舱之间载重量比例上偏差不超过15 前 后舱之间不超过10 问该货轮应装载A B C各多少件 运费收入为最大 试建立这个问题的线性规划模型 表1 绪葛挖镇鸵罢听富萝淀顾椒詹洛优租夺睬索典宰梢既缚琼霸毡致驱哉党至MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 31 设表示xij装于第j j 1 2 3 舱位的第i i 1 2 3 种商品的数量 舱位载重限制 舱位体积限制 商品数量限制 平衡条件 呕郡针窃萌赞徐匝织胆臼旋歪袖白沏冉挨氨侩固惭杭脐才驱掺专们挤最坯MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 32 三 LP问题的标准型 1 为了讨论LP问题解的概念和解的性质以及对LP问题求解方便 必须把LP问题的一般形式化为统一的标准型 或 maxz cx 标准型的特点 目标函数是最大化类型 约束条件均由等式组成 决策变量均为非负 bi i 1 2 n 0 受攘当诵翁旬际鬃约锄逻为鼓炳柿喊哪奈位臼撇冒狱擦毕篷漳羹倚寸滇讶MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 33 2 化一般形式为标准型 目标函数 minz max z cx 若约束为 型 左边 松驰变量 若约束为 型 左边 松驰变量 若变量xj 0 xj 0变量 若变量xj无限制 令xj xj xj 若右边常数bi 0 等式两边同乘以 1 例4课本P9化下述问题为标准型minz x1 2x2 3x3x1 2x2 3x3 7s t x1 x2 x3 2 3x1 x2 2x3 5x1 x3 0 x2无约束 奴哆哺铃氖讶状彝贝羽荫斟岸述煌嘘仪萤臻蛾烂晨厌恃衅惋窗夺渡深怯陇MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 34 解 首先考察变量 令 并加入松驰变量x4 x5化为如下标准型 练习 课本P642 2 3 那湾寐间木粟诵袜疗随揭睡蜕钻轨屎茹焊擎寻栅裹碍变憨宙配箕特爪鞠落MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 35 解 令 则 加入松驰变量s w 得到标准型如下 汕坐瓜翅埔屑讳蒂炕漂养王阑拧烷猩蒲节单瞄昂丁轧塔缕狮站忆施汽支侦MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 36 四 LP问题解的概念 1 从代数的角度看 可行解 FeasibleSolution 满足约束条件 1 8 和 1 9 的解X x1 x2 xn T称为可行解 所有可行解构成可行解集 即可行域 最优解 OptimalSolution 而使目标函数达到最大值的可行解称为最优解 对应的目标函数值称为最优值 求解LP问题就是求其最优解和最优值 但从代数的角度去求是困难的 设LP问题 嗓浦介殴鲍料污永钱丑忘抒钩昭盗肤驭隧胆伐彝稀瓦杂沤顾林贿撅籍眩粹MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 37 2 从LP角度看 基 Basis 设A为mxn矩阵 r A m B是A中的mxn阶非奇异子矩阵 即 B 0 则称B是LP问题的一个基 若B是LP问题的一个基 则B由m个线性独立的列向量组成 即B Pr1 Pr2 Prm 其中Prj a1rj a2rj amrj T j 1 2 m 称为基向量 基变量 BasicVariables 与非基变量 Non basicVariable 与基向量Prj相对应的变量xrj称为基变量 其它变量称为非基变量 显然 对应于每个基总有m个基变量 n m个非基变量 基本解 BasicSolution 设B是LP问题的一个基 令其n m个非基变量均为零 所得方程的解称为该LP问题的一个基本解 显然 基B与基本解是一一对应的 基本解的个数 Cmn 基可行解 在基本解中 称满足非负条件的基本解为基可行解 对应的基称为可行基 沼卿乍废证昂多肿慌诛冲亮危良韦革姜渤吵韧寸们脾免益姨布浅扯嘱甚网MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 38 退化解 DegenerateSolution 如果基解中非零分量的个数小于m 则称此基本解为退化的 否则是非退化的 最优基解 OptimalBasicSolution 如果对应于基B的基可行解是LP问题的最优解 则称B为LP问题的最优基 相应的解又称基本最优解 3 LP问题解之间的关系如图所示 可行解 基解 最优解 基最优解 巡鸳乳猫舷塘梗乡喷粒剁桅尿打光汛霸敲橙畅宏酥聘枝链矿裸唯莉棋售穴MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 39 五 两个变量LP问题的图解法 1 LP问题图解法的步骤 1 画出直角坐标系 2 依次做每条约束直线 标出可行域的方向 并找出它们共同的可行域 3 任取一目标函数值作一条目标函数线 称等值线 根据目标函数 最大或最小 类型 平移该直线即将离开可行域处 则与目标函数线接触的最终点即表示最优解 例1 用图解法求解如下线性规划问题 最优解为x1 6 x2 4最优值为maxz 36 恃尖辽诗世闻泊酶豫坤见途闲侄崖淋仲豫展娶乒弓漳按揪汹冯吴巍赠氯航MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 40 例2 用图解法求解下列线性规划 Q3 Q 4 B x 1 3 2 1 01234 Q2 4 2 Q1 Q2 4 2 为最优解 化族杜郎哀伯苇积劝盟杜镍尽怖篆咱露涅暗悬爵禹衡粗约吮赂增丧蜡缉硫MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 41 解的几种情况 1 此例有唯一解Q2 即x1 4 x2 2 z 14 2 有无穷多最优解 多重解 若将目标函数改为z 2x1 4x2则线段Q2 Q3上的点均为最优解 3 无界解 援撂皇嫁燎忙挖壳苗乙彭涟讯击结怒左鸽赵曾庄逢尖织上龄奇惟毯圈镀肩MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 42 4 无可行解 衣察控鸣绪排奢爷含获诡聘冬侈镇县焉赠券韦靶虞改搂捞希此磨项珊念苞MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 43 结论 1 LP问题的可行域是凸集 凸多边形 凸多面体 2 LP问题最优解若存在 则必可在可行域的顶点上达到 3 LP问题的可行域的顶点个数是有限的 4 若LP问题若有两个最优解 则其连线上的点都是最优解 因此 求解LP问题可转化为 如何在可行域的顶点上求出使目标函数值达到最优的点的问题 爹糯枉奴竟彦征膘省固崇门则峨奈某涅暮压较锗署汝打巷妊怯悠廉或捂求MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 44 2 基可行解的几何意义对例1LP问题标准化为maxZ 2x1 3x2 可求得它的所有的基本解 x 1 0 0 8 16 12 T 0点 x 2 4 0 4 0 12 T Q1点 x 3 4 2 0 0 4 T Q2点 x 4 2 3 0 8 0 T Q3点 x 5 0 3 2 16 0 T Q4点 x 6 4 3 2 0 0 T C点 x 7 8 0 0 16 12 T A点 x 8 0 4 0 16 4 T B点 但A B C三点是非可行域上的点 即非可行解 因此 x 1 x 2 x 3 x 4 x 5 才是基可行解 它们与可行域的顶点相对应 于是还有 棠剃垦铝详吨捂灼怯屏村母哨榨醚续矫灰忽腮湛划督著喘咳馁塔油甸迫一MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 45 结论 5 对于标准型的LP问题 X是基可行解的充要条件是X为可行域的顶点 6 LP问题可行域顶点的个数 基可行解的个数 基的个数 Cmn 3 图解法只适用于两个变量 最多含三个变量 的LP问题 4 求解LP问题方法的思考 完全枚举法 对m n较大时 Cmn是一个很大的数 几乎不可能 从可行域的一个顶点 基可行解 迭代到另一个顶点 基可行解 洼庚黎智淑徘齿檄突纵印赛搏砚治统酬滁骗陇映绎巴检警赐亡足备越展敛MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 46 2单纯形法与计算机求解 袄冀旗期宣嗅店重校巾竞掳狭站赴蹿梧燕怠赫茄申淳歉焕闽折墟爷拇腋窟MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 47 将目标函数改写为 Z c1x1 c2x2 cnxn 0把上述方程组和目标函数方程构成n 1个变量 m 1个方程的方程组 并写成增广矩阵的形式 2 单纯形法的计算步骤 表格形式 1 建立初始单纯形表 假定B I b 0设maxZ c1x1 c2x2 cnxn 臭蛙委驰浚作惨万舟允窍簇赘孔檬氖壳残刮励诛写牛驱茶玉膨蒂檄尚涡爹MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 48 脑妻露认伏苗缩阐是腻七右禾太痒端蓑听蛮娘灯首磕贼侧崖着匡圣俊男苫MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 49 肖岔法匿余前熬遏骑卑稠录抿记菩捷湍瘟僵塔冬戮卸蚜游锣挛服畦娇为灯MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 50 靳累彭铺单做警鹿秉抹边饭烽握温恭枝煮写楔轧那枚扇户魂千洁委陵薄岁MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 51 上述初始单纯形表可确定初始可行基和初始基可行解 B P1 P2 Pm I x b1 b2 bm 0 0 T从初始单纯形表建立的过程可以看到以下事实 1 凡LP模型中约束条件为 型 在化为标准型后必有B I 如果b 0 则模型中约束方程的各数据不改变符号照抄在表中相应的位置 目标函数中非基变量的系数则以相反数填入检验数行各相应位置 2 在单纯形表中 凡基变量所在的列向量必是单位列向量 其相应的检验数均为零 绪准焚马妒顶甸晰盗横蔡闽碳崔危摈绘茸估光韧拳约琵课赦廷塘俩囚渺碑MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 52 2 判别最优解1 在T B 中 若所有的检验数 j 0 j 1 2 n 则B为最优基 相应的基可行解为最优解 停止计算 2 在T B 中 若有 k 0 1 k n 且xk的系数列向量Pk 0 则该问题无界 停止计算 否则转入 3 3 换基迭代 基变换 1 先确定进基变量Xk k min j j 0 即检验数行从左至右选择负数所对应的变量进基 2 按最小比值原则确定出基变量xL 3 以为主元 进行初等行变换 又称旋转变换 即将列向量变换为单位列向量 栏纹侗天醋藏崖扒苇夯苛芳肮动吐割镣娃女卸橡钱窄魔巢盗盆围蔡况罢茬MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 53 靖睹攘亿迹挠违紧通舱跪亨踢迁析傅橡镶篆伶佳毖沟饥次而眯男姿墅完亚MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 54 例5求解下列线性规划问题 解 引进松驰变量x3 x4 化为标准形得 从标准形中可看出存在可行基B P3 P4 I 基变量为X3 X4 非基变量为X1 X2 建立初始单纯形表得 侄古绿哆召狸谅忱盛章灯梨始伸物垦隆辐仓密奏闽拂乓卷丛滦底邢桶新元MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 55 由于X1 X2的检验数均为负 且X1的检验数绝对值最大 选取X1为进基变量 再按最小比值 min 24 2 26 3 26 3 因此选取X4为出基变量 进行换基迭代 隔际钒憨啪救韵喷同龙田柄屹醋丫熊衅思泉匠疲庄典示拯棱扎颗衙侵编憾MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 56 表中最后一行的所有检验数均为非负数 表明目标函数已达到最大值 上述表为最优表 从表中可得到最优解为X x1 x2 x3 x4 6 4 0 0 最优值为Z 36 例2 求解下列线性规划问题 见课本P17 面刃懈递隙酷阳协侦沈袁甜敖路拈扼祥势窗拟验葬沏批潘煞才侥遍眯霄怠MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 57 练习 1 已知某线性规划用单纯形法求得的某两步迭代表如下 请将表中空白处填上适当的数字 妒室陕制狙澈免蔬酉菱龄兜劫稽修驶沥娠弊赵浇喧盾历跨侯淑朗皇袱猖倾MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 58 2 用单纯形法求解某极大化问题的单纯形表如下 问表中参数a1 a2 a3 d 1 2为何取值范围时 下列结论成立 1 表中解为惟一最优解 2 表中解为多重最优解之一 3 该问题有无界解 4 表中解为退化的基解 5 表中解为不可行解 6 尚未得到最优解 以x1代换x6 1 0 2 0 d 0 1 2 0 1 0 2 0 d 0 2 0 a1 0 d 0 d 0 13 a3 a3 0 异阉鳖煽企井源册妨钎款赦却咆况美太陈宣哉爹婚炕脓啃毅涝激翻扬护蛰MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 59 3 设有线性规划问题 其中b1 b2是常数 且已知此规划的最终表为 确定表中所有的参数 e 0 d 5 b 5 c 10 a 23 b1 30 b2 40 郡岭碘拥沥运硼伎释蛤彪辕悉丰揣憨踪坷谚蔗绍耗沈每醒缝楔秦醇专某疵MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 60 3 单纯形法的进一步讨论 用人工变量法求初始基可行解 一 人工变量法若对LP模型标准化后 不具有B I时 如何办 此时可采用人工变量法得到初始基可行解 所谓人工变量法是在原问题不含有初始可行基B I的情况下 人为的对约束条件增加虚拟的非负变量 即人工变量 构造出含有B I的另一个LP问题后求解 当增加的人工变量全部取值为0时 才与原问题等价 这样 新问题将有一个初始基可行解 以人工变量为基变量 可用单纯形法进行迭代 经迭代后 若人工变量全部被换成非基变量 即人工变量全部出基 则得到原问题的一个基可行解 在最终表中若人工变量不能全部被换出 则说明原问题无可行解 因此 该法的关键在于将人工变量全部换出 屑析狠在煽广宴料咀只秃秃胶绦梦仔僳他缕屯钦话喉识卑劝兄收莆渠郧串MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 61 人工变量法常见的有大M法和两阶段法 姐贝餐柄盐滩种把认驴语太之傈需票怜颜咸蹲颠嚼椅驱忙可蛛合左滚播川MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 62 注意到 分别在约束条件中增加人工变量x5 x6是为了构成 人工基 对于Min的目标函数采用 M 而对于Max的目标函数则采用 M 作为人工变量的系数 是强加于人工变量的一种惩罚 其目的是为了强制人工变量由基变量转为非基变量 使之恢复原问题 或与原问题等价 对于minZ判别最优性准则应是Cj Zj 0 大M法适合于计算机计算 不适用于手工求解 所以本题求解过程略 奈偷柿伏锭不徘韦宠壤慎久绒软诵学鬃胸傣脉跑淹逗企辅吊直镭绰恰棠晦MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 63 2 两阶段法第一阶段 不考虑原问题是否存在基可行解 给原LP问题的约束条件加入人工变量 构造仅含人工变量的目标函数并要求实现最小化 即使原LP问题目标函数是求最大化 的辅助问题 MinW xn 1 xn m 然后用单纯形法求解 1 若W 0 则原问题无可行解 停止计算 若W 0 且所有的人工变量均为非基变量 则去掉人工变量后可得到原问题的基可行解 如果人工变量中含有为0的基变量时 即退化解 则可再进行初等行变换将其换出 从而获得原问题的基可行解 1 找晚褪彤襟返媚雇迫描粳篙永岂腹抹殴坷烷工几川钎棕碎巨泼添吉涨郁乍MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 64 第二阶段 在第一阶段所得的基可行解的基础上 将最终表中的人工变量列删去 同时将人工目标函数行换为原问题的目标函数作为第二阶段计算的初始表 仍以上例为例用两阶段法求解 MinZ x1 1 5x2 0 x3 0 x4 MinW x5 x6辅助问题 原问题 用单纯形法求解的迭代表如下 精朔遵碗短连爱鳖靳肥择疟谱避佯瞪激涛捐砷敝茅宰席搏产涛缎切似耀挚MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 65 承缨溉遍圾爆涪唤涡甩钓哑良纠省憎肾圈形同荔宅匠盯贸图抚影诵渗测醇MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 66 上述表中目标函数值W 0 且人工变量已全部出基 得到原问题的一个可行基B P2 P1 和一个基可行解X X2 X1 1 2 3 2 去掉人工变量列 并将目标函数行换为原目标函数行得 爆眉赖暮巫筛帚狈戳淹黑讨彼窘异蹭芜扯腆群送能鳞更屡袖臆比丽胡汛利MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 67 上表中最后一行所有检验数均非正 因为是求极小化问题 所以上述表已是原问题的最优表 从表中可知原问题的最优解为X1 1 2 X2 3 2 最优目标函数值为Z 9 4 注意 第二阶段在填单纯形表时 检验数行的值是将原目标函数中的基变量用非基变量表示 x1 3 2 1 2x3 3 2x4 x2 1 2 1 2x3 1 2x4 后所得结果填入 或直接通过表中数字关系计算而得 肌旋琳伦黄览渴蝴象其纬田业则哺憎劝析享滔氏式筹诞哄三欧奴稽吹守磨MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 68 总结一 线性规划模型的建立1 确定决策变量2 确定目标函数3 确定约束条件二 线性规划模型的求解 1 找到初始可行基解 建立初始单纯形表2 判断最优 所有检验数大于等于0时最优3 换基迭代 以负检验数对应的变量进基 按最小元素法确定出基变量 1 普通单纯形法 2 人工变量法 1 在原问题上加入人工变量化为辅助问题 用单纯形法求解辅助问题2 删去人工变量和改换目标函数 求解原问题 汛毙恤撵瘟氧考蜕丹邵渍射槛期爷新债师攻装雨搞报顺蓑殆各展瓶敷紧遮MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 69 练习 求解下列线性规划问题 其最优表为 夫缸效忿诊殃舟佩坪窟呜瓢氧噶描杆郡稿缠辣巷庸睁李咒蜕涯霖激枉茵凡MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 70 补充 矩阵形式的单纯形表 设C CB CN A B N 代入 2 得 2 盼指冗珐餐痛均朔姑浴豺怠盖镊要瑶亿墩词脾恕隅蜂于生墅主七禁钡逗国MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 71 将基变量从目标函数中消除 建立对应于基B的矩阵形式的单纯形表T B 孺剧维店霄饯峙邢聂忽留兵残腑缆亚嚣邓警岩畜鼎茄他涤袒翱逆倘斯轧旧MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 72 B 1ACBB 1A C 化简为如下简单的表格形式 谗海耗德辨粗帖皆懈最手浪僚旺仑软逆班惯髓懒构给辨钞吝跋舷捻球杀邮MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 73 2 4对偶理论与灵敏度分析 一 LP的对偶问题 1 引例课本P6的生产计划问题是一个在有限资源的条件下 求使利润最大的生产计划安排问题 其数学模型为 现从另一角度考虑此问题 假设有客户提出要求 租赁工厂的工时和购买工厂的材料 为其加工生产别的产品 由客户支付工时费和材料费 此时工厂应考虑如何为每种资源定价 同样使其获得的利润最大 埂圾券毡汇稀初噶崇勤均错傅苗继钒桨拱踪害尔裙酒玫豆渣相患游团瞬翌MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 74 解 1 决策变量 设y1 y2分别表示出售单位原材料的价格 含附加值 和出租设备单位工时的租金 3 约束条件 工厂决策者考虑 1 出售原材料和出租设备应不少于自己生产产品的获利 否则不如自己生产为好 因此有 2 目标函数 此时工厂的总收入为W 24y1 26y2 这也是租赁方需要付出的成本 而在这个问题中 是企业不生产 将自己的资源出售或出租 因此 此时 起决定作用的是租赁方 所以此时的目标函数为MinW 24y1 26y2 能树胜臼乱虑拣另坦铅诺苦愈何贼葵畴玩妥片油霉阁枝馋噬庆唤湖便误抛MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 75 2 价格应尽量低 否则没有竞争力 此价格可成为与客户谈判的底价租赁者考虑 希望价格越低越好 否则另找他人 于是 能够使双方共同接受的是 上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的 且是同一个问题从不同角度考虑所产生的 因此两者密切相关 称这两个LP问题是互为对偶的两个LP问题 其中一个是另一个问题的对偶问题 迪加粹钞送鼎态漫壮痢国考氖面篷劲征村剖致蜒同傻钱钮驼烈境储边咐蕊MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 76 一般地对于任何一个线性规划问题都有一个与之相对应的对偶问题 原问题与对偶问题的一般形式为 原问题 LP 对偶问题 DP 相应的矩阵形式为 碰媒软姆妥详厂登蛊淹拙耶舌徐冗牢苍匆吊据抑坠迅铰橡趟均撞崩戍颁搔MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 77 对称形式的对偶问题为 LP DP 二 对偶理论 1 原问题与对偶问题的关系 由以上两式可知 原问题与对偶问题之间具有如下关系 1 一个问题中的约束条件个数等于它的对偶问题中的变量数 2 一个问题中目标函数的系数是其对偶问题中约束条件的右端项 3 约束条件在一个问题中为 则在其对偶问题中为 4 目标函数在一个问题中为求最大值 在其对偶问题中则为求最小值 督逃仲毫背热截寄剿伴蛀船趋庙谷僧争从烹勘锹辣秸宜奔钦笋吵焚证此蹿MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 78 例1 写出下列线性规划问题的对偶问题 P27 非对称形式的对偶问题为 LP DP 饶况漓售页喻碳锅闷块瓣龋芹溃肺靳殊稍判腊箔戚靡樱许撂虑娥温茧扣聊MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 79 归纳对称形式与非对称形式的对偶 原问题与对偶问题之间的关系如下表所示 疮挫板劣酣朵腹驶伊赶奠迫砌仍兰迪怎拔搓奠炔宦拒醉剧序惮叹氢供大蝶MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 80 2 设 1 对称性 对偶问题的对偶是原问题 2 弱对偶定理 若X 0 是原问题的可行解 Y 0 是对偶问题的可行解 则有 3 无界性 若原问题 对偶问题 为无界解 则其对偶问题 原问题 无可行解 4 最优性定理 若X 0 Y 0 分别是互为对偶问题的可行解 且CX 0 Y 0 b 则X 0 Y 0 分别是它们的最优解 5 强对偶定理 若互为对偶问题之一有最优解 则另一问题必有最优解 且它们的目标函数值相等 者芯喊定钙淫拇缠甄忿煤娟糕郧扭随擦棱羞瘸卿叔硅忻删睹掏逻激凑鸿疟MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 81 汰影下春洱抽溶攀右味泳弊隅筷扭枕肺矮虞羌阁镐酷侧泥舒捉记唇护掷瞳MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 82 P29思考题 已知如下线性规划问题的对偶问题的最优解为y1 4 5 y2 3 5 z 5 试用对偶理论找出原问题的最优解 解 其对偶问题为 应用互补松驰性定理 将y1 4 5 y2 3 5代入对偶问题的约束条件得 x1 0又由于y1 y2 0 原问题x2 0的两个约束为紧约束 所以x3 0 x4 0 x5 0 解得 x1 1 x5 1 x2 x3 x4 0 仆闷妈颜诧汾迄希玻哮穴哩养进崖铂轨锐菜赘沥民饰筛轩蜘什贤逼朴丽外MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 83 三 对偶单纯形法 1 单纯形法的重新解释X 是最大化LP问题最优解的充要条件是同时满足 因此 单纯形法是在保持原始可行下 经过迭代 逐步实现对偶可行 达到求出最优解的过程 根据对偶问题的对称性 也可以在保持对偶可行下 经过迭代 逐步实现原始可行 以求得最优解 对偶单纯形法就是根据这种思想所设计的 补黔惹品胀剥尘凡虽后静序焚白居津东十橱勃瓷弦唤缄穿礁拆婉铃症例忧MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 84 例14用对偶单纯形法求解下列线性规划问题 解 化为标准形后 用对偶单纯形法求解过程如下表所示 2 对偶单纯形法的计算步骤 夕炬进遮毖秒亲烂华呆奎娄碍朽邮矣检弛歹泽桌卑她铀妆壕橡检染坛春特MBA学位课程 运筹学1 ppt125 MBA学位课程 运筹学1 ppt125 85 竖藐秒号贩樱约兢姑算酚退煤办蜂武伤苗毛殖镇嫡只泳轴昼恰垃袱坏纤柑MBA学位课程 运筹学1