运筹学基础及应用.pptx

运 筹 学(Operations Research)夫运筹策帷幄之中，决胜于千里之外夫运筹策帷幄之中，决胜于千里之外 史记史记 高祖本纪高祖本纪绪 论（1）运筹学简述）运筹学简述（2）运筹学的主要内容）运筹学的主要内容（3）本课程的主要学习内容）本课程的主要学习内容（4）运筹学的应用）运筹学的应用（5）本课程的教材及参考书）本课程的教材及参考书（6）本课程授课方式与考核）本课程授课方式与考核 本章主要内容：本章主要内容：一、古代朴素的运筹学思想一、古代朴素的运筹学思想国外国外英文原名英文原名 Operations Research 简称简称“O.R.”直译为：运用研究或作业研究直译为：运用研究或作业研究正式出现于正式出现于19381938年年7 7月英国一份关于防空作战系统运月英国一份关于防空作战系统运行的研究报告中行的研究报告中中国古代运筹学案例中国古代运筹学案例二、运筹学的起源二、运筹学的起源（一）运筹学简述（一）运筹学简述运作研究运作研究(Operational Research)小组小组”:二战期间解决二战期间解决复杂的战略和战术问题。例如：复杂的战略和战术问题。例如：1.1.如何合理运用雷达有效地对付德军空袭如何合理运用雷达有效地对付德军空袭2.2.对商船如何进行编队护航，使船队遭受德国潜艇攻击时对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；损失最少；3.3.在各种情况下如何调整反潜深水炸弹的爆炸深度，才能在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。增加对德国潜艇的杀伤力等。-二战后运筹学的发展经历了三个阶段二战后运筹学的发展经历了三个阶段 （1 1）19451945年到年到2020世纪世纪5050年代初年代初创建时期创建时期 （2 2）20 20 世纪世纪5050年代初到年代初到2020世纪世纪5050年代末年代末成长时期成长时期 （3 3）20 20 世纪世纪6060年代以来年代以来迅速发展和普及的时期迅速发展和普及的时期国内国内19561956年成立第一个运筹学小组年成立第一个运筹学小组19571957年从年从“夫运筹策帷幄之中，决胜于千里之外夫运筹策帷幄之中，决胜于千里之外”中中摘取摘取“运筹运筹”二字，将二字，将O.R.正式翻译为正式翻译为“运筹学运筹学”三、运筹学的定义三、运筹学的定义研究工具：数学，计算机科学及其他相关科学研究工具：数学，计算机科学及其他相关科学研究目的：对有限资源进行合理规划、使用，并提供研究目的：对有限资源进行合理规划、使用，并提供 优化决策方案。优化决策方案。研究对象：复杂系统的组织和管理研究对象：复杂系统的组织和管理参考参考大英百科全书大英百科全书、辞海辞海、中国企业管理百科全书中国企业管理百科全书等。等。四、运筹学研究的基本特点四、运筹学研究的基本特点 系统的整体优化系统的整体优化 多学科的配合多学科的配合 模型方法的应用模型方法的应用五、运筹学研究的基本步骤五、运筹学研究的基本步骤 分析与表述问题分析与表述问题 建立数学模型建立数学模型 对问题求解对问题求解 对模型和模型导出的解进行检验对模型和模型导出的解进行检验 建立对解的有效控制建立对解的有效控制 方案的实施方案的实施（二）运筹学的主要内容（二）运筹学的主要内容数学规划（数学规划（线性规划、整数规划、目标规划线性规划、整数规划、目标规划、动态规划等）动态规划等）图论图论存贮论存贮论排队论排队论对策论（博弈论）对策论（博弈论）决策论决策论（三）运筹学的应用（三）运筹学的应用 运筹学方法运筹学方法 应用例应用例 线性规划线性规划 生产结构优化生产结构优化 非线性规划非线性规划 投资组合优化投资组合优化 整数规划整数规划 选址问题选址问题 动态规划动态规划 资源分配问题资源分配问题 网络分析网络分析 工程计划优化工程计划优化 排队论排队论 服务系统优化服务系统优化 存贮论存贮论 订货库存管理订货库存管理 决策分析决策分析 机会选择机会选择 运筹学的广泛实际背景促使其不断发展并运筹学的广泛实际背景促使其不断发展并 在经济管理和在经济管理和系统工程等多领域中发挥着令系统工程等多领域中发挥着令 人瞩目的重要作用。人瞩目的重要作用。诺贝尔经济学奖从诺贝尔经济学奖从1969年首发至今的年首发至今的57 位获奖者中就有位获奖者中就有多位是运筹学家。多位是运筹学家。1975年诺贝尔经济学奖授给了库普曼和康脱罗维年诺贝尔经济学奖授给了库普曼和康脱罗维 奇，以表奇，以表彰首先将线性规划与经济问题相联系而彰首先将线性规划与经济问题相联系而 做出的贡献；做出的贡献；1994年诺贝尔经济学奖授给了三位博弈论专家：年诺贝尔经济学奖授给了三位博弈论专家：纳什、泽尔纳什、泽尔腾、海萨尼。博弈论已经成为当代经腾、海萨尼。博弈论已经成为当代经 济学的基石。济学的基石。2005年以色列经济学家罗伯特年以色列经济学家罗伯特-奥曼和美国经济奥曼和美国经济 学家托马学家托马斯斯-斯切林，因斯切林，因“通过博弈论分析加强了通过博弈论分析加强了 我们对冲突和合作的我们对冲突和合作的理解理解”所作出的贡献而获奖。所作出的贡献而获奖。发表的部分获奖项目组织组织应用应用效果效果联合航空公司联合航空公司在满足乘客需求的前提下，以最低在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排成本进行订票及机场工作班次安排每年节约成本每年节约成本600600万美元万美元CitgoCitgo石油公司石油公司优化炼油程序及产品供应、配送和优化炼油程序及产品供应、配送和营销营销每年节约成本每年节约成本70007000万万AT&TAT&T优化商业用户的电话销售中心选址优化商业用户的电话销售中心选址每年节约成本每年节约成本4.064.06亿美亿美元，销售额大幅增加元，销售额大幅增加标准品牌公司标准品牌公司控制成本库存（制定最优再定购点控制成本库存（制定最优再定购点和定购量确保安全库存）和定购量确保安全库存）每年节约成本每年节约成本380380万美元万美元法国国家铁路公司法国国家铁路公司制定最优铁路时刻表并调整铁路日制定最优铁路时刻表并调整铁路日运营量运营量每年节约成本每年节约成本15001500万美万美元，年收入大幅增加。元，年收入大幅增加。Taco BellTaco Bell优化员工安排，以最低成本服务客优化员工安排，以最低成本服务客户户每年节约成本每年节约成本13001300万美万美元元DeltaDelta航空公司航空公司优化配置上千个国内航线航班来实优化配置上千个国内航线航班来实现利润最大化现利润最大化每年节约成本每年节约成本1 1亿美元亿美元（四）本课程的教材及参考书（四）本课程的教材及参考书选用教材选用教材 运筹学基础及应用运筹学基础及应用胡运权主编胡运权主编 （第五版）高等教（第五版）高等教育出版社育出版社参考教材参考教材运筹学教程运筹学教程胡运权主编胡运权主编 （第（第4 4版）清华出版社版）清华出版社管理运筹学管理运筹学韩伯棠主编韩伯棠主编 （第（第2 2版）高等教育出版社版）高等教育出版社运筹学运筹学(修订版修订版)钱颂迪主编钱颂迪主编 清华出版社清华出版社 （五）本课程的主要学习内容（五）本课程的主要学习内容 第一章第一章 线性规划及单纯形法线性规划及单纯形法 第二章第二章 线性规划的对偶理论线性规划的对偶理论 第三章第三章 运输问题运输问题 第四章第四章 整数规划与分配问题整数规划与分配问题 （六）本课程授课方式与考核（六）本课程授课方式与考核学科总成绩学科总成绩平时成绩平时成绩（3030）课堂考勤课堂考勤（1212）平时作业平时作业（1818）期末成绩期末成绩（7070）讲授为主，结合讨论、习题作业讲授为主，结合讨论、习题作业第一章第一章 线性规划及单纯形法线性规划及单纯形法Linear Programming and Simplex Method线性规划-发展简史法国数学家 J.-B.-J.傅里叶和 C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家年苏联数学家.康托罗维奇康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。1947年美国数学家年美国数学家G.B.丹齐克丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法单纯形法，为这门学科奠定了基础。1947年美国数学家年美国数学家J.von诺伊曼提出对诺伊曼提出对偶理论偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家年美国经济学家T.C.库普曼斯库普曼斯把线性规划应用到经济领域把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年年C.莱姆基提出对偶单纯形法莱姆基提出对偶单纯形法，1954年年S.加斯和加斯和T.萨迪等人解决了线性规划的灵敏度分析萨迪等人解决了线性规划的灵敏度分析和参数规划问题，和参数规划问题，1956年年A.塔克提出互补松弛定理，塔克提出互补松弛定理，1960年年G.B.丹齐克和丹齐克和P.沃尔夫提出分解算法沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家年苏联数学家.哈奇扬提出解线性规划问题的椭球哈奇扬提出解线性规划问题的椭球算法算法，并证明它是多项式时间算法。1984年年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新卡马卡提出解线性规划问题的新的多项式时间算法的多项式时间算法-内点算法内点算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。1.1939年，前苏联科学家康托洛维奇年，前苏联科学家康托洛维奇-生产组织与管理中的数学方法生产组织与管理中的数学方法是线性是线性规划应用于工业生产问题的开山之作规划应用于工业生产问题的开山之作；(LEONIDVITALIYEVICHKANTOROV(1912-1986)2.1947年，美国数学家乔治年，美国数学家乔治伯纳德伯纳德丹齐格丹齐格-单纯形法，被称单纯形法，被称为线性规划之父。为线性规划之父。GeorgeBernardDantzig(19142005)丹齐格在丹齐格在1946年获伯克利大学的博士学位。年获伯克利大学的博士学位。1947年，年，33岁提岁提出了解决一种最优化问题的单纯形法出了解决一种最优化问题的单纯形法,该方法奠定了线性规划的该方法奠定了线性规划的基础，使得经济学、环境科学、统计学应用等学科获得了迅速基础，使得经济学、环境科学、统计学应用等学科获得了迅速发展。发展。Dantzig也因而被誉为也因而被誉为“线性规划之父线性规划之父”。1952年他在兰德公司任研究数学家，在公司电脑上实行线性规年他在兰德公司任研究数学家，在公司电脑上实行线性规划。划。1960年他被母校聘任教授计算机科学，终于当上运筹学中年他被母校聘任教授计算机科学，终于当上运筹学中心主任。心主任。1966年他在史丹福大学当类似职位，留在那里直到年他在史丹福大学当类似职位，留在那里直到1990年代退休。年代退休。Dantzig在运筹学建树极高，获得了包括在运筹学建树极高，获得了包括“冯诺伊曼理论奖冯诺伊曼理论奖”在在内的诸多奖项。他在内的诸多奖项。他在Linear programming andextensions一书中研究了线性编程模型，为计算机语言的一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献。他除了线性规划和单纯形法的杰发展做出了不可磨灭的贡献。他除了线性规划和单纯形法的杰出工作，还推进很多领域的发展，有分解论、灵敏度分析、互出工作，还推进很多领域的发展，有分解论、灵敏度分析、互补主元法、大系统最优化、非线性规划和不确定规划。补主元法、大系统最优化、非线性规划和不确定规划。SIAM Journal on Optimization1991年创刊号是献给他的。年创刊号是献给他的。Mathematical Programming Society为表彰丹齐格，设立丹齐格奖，为表彰丹齐格，设立丹齐格奖，1982年起每三年颁给年起每三年颁给一至两位在数学规划有突出贡献的人。一至两位在数学规划有突出贡献的人。xa此为无约束的极值问题此为无约束的极值问题1.1 一般线性规划问题的数学模型一般线性规划问题的数学模型1-1 1-1 问题的提出问题的提出例例1 1 用一块边长为用一块边长为a的正方形铁皮做一个无盖长方体容器，的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？应如何裁剪可使做成的容器的容积最大？解如图设四个角上减去的小正方形边解：如图设四个角上减去的小正方形边长为长为x，则容器体积为：，则容器体积为：时，容积最大时，容积最大 例例2 2 常山机器厂生产常山机器厂生产 I I、IIII 两型产品。这两型两型产品。这两型产品都分别要在产品都分别要在A A、B B、C C三种不同设备上加工。按三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：备的工时以及各种设备工时的限额如下表：单位产品消耗设单位产品消耗设备工时备工时I IIIII设备工时限量设备工时限量（小时）（小时）设备设备A A设备设备B B设备设备C C2 24 40 02 20 05 5121216161515单位利润（元）单位利润（元）2 23 3如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？解：设计划期内两种产品的数量分别为解：设计划期内两种产品的数量分别为x x1 1，x x2 2，则总利润为：，则总利润为：maxz=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0，x2 0简记为：简记为：s.t.（约束于：）（约束于：）z=2 x1+3 x2在满足限制条件下求在满足限制条件下求z的最大值。的最大值。此为有约束极值问题此为有约束极值问题1-2 1-2 线性规划问题的数学模型线性规划问题的数学模型原型原型模型模型数学模型数学模型提炼提炼数学工具数学工具1 1、原型原型：现实世界中人们关心、研究的实际对象。：现实世界中人们关心、研究的实际对象。模型模型：将某一部分信息简缩、提炼而构造的原型替代物。：将某一部分信息简缩、提炼而构造的原型替代物。数学模型数学模型：对现实世界的一个特定对象，为达到一定目的，：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设根据内在规律做出必要的简化假设,并运用适当数学工具得到并运用适当数学工具得到的一个数学结构。的一个数学结构。3 3、规划问题数学模型的三要素、规划问题数学模型的三要素（2 2）目标函数目标函数：问题要达到的目标要求，表示为决策变量的：问题要达到的目标要求，表示为决策变量的函数。用函数。用 z=f(x1 1，x2 2，xn n)表示。表示。（1 1）决策变量决策变量：决策者为实现规划目标采取的方案、措施，：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用是问题中要确定的未知量。用x1 1，x2 2，xn n表示。表示。（3 3）约束条件约束条件：决策变量取值时受到的各种可用资源的限制，：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。表示为含决策变量的等式或不等式。2 2、规划问题、规划问题即求目标函数在若干约束条件下的最值。即求目标函数在若干约束条件下的最值。4 4、线性规划问题（、线性规划问题（Linear ProgrammingLinear Programming）的数学模型）的数学模型（2 2）一般形式一般形式：（1 1）条件条件：决策变量为可控的连续变量，目标函数和约束条：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为件都是线性的。简记为“L.P.”max(或或 min)z=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn （=，）b1 a21x1+a22x2+a2nxn （=，）b2 am1x1+am2x2+amnxn（=，）bm x1,x2,xn0（3 3）其他形式其他形式：连加形式连加形式向量形式向量形式其中 称为价值行向量价值行向量；决策列向量决策列向量系数列向量系数列向量右端列向量右端列向量矩阵形式矩阵形式其中 称为价值行向量；称为价值行向量；决策列向量决策列向量右端列向量右端列向量约束矩阵或系数矩阵约束矩阵或系数矩阵1-3 1-3 线性规划问题的标准形式线性规划问题的标准形式1 1、标准形式、标准形式或或2 2、条件、条件目标函数求极大值目标函数求极大值约束条件全是等式（线性方程组）约束条件全是等式（线性方程组）决策变量全非负决策变量全非负右端常数全非负右端常数全非负3 3、标准化方法、标准化方法（1）若目标函数求极小值，即）若目标函数求极小值，即则令则令 转化为转化为（2 2）若约束条件为不等式，）若约束条件为不等式，则依次引入松弛变量或剩余变量（统称为松弛变量），则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。转化为等式约束条件。注意注意：松弛变量在目标函数中系数全为：松弛变量在目标函数中系数全为0。约束为约束为不等式，减去松弛变量，化为等式约束条件；不等式，减去松弛变量，化为等式约束条件；约束为约束为不等式，加上松弛变量，化为等式约束条件。不等式，加上松弛变量，化为等式约束条件。多多退退少少补补例：例：max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0，x2 0 s.t.标准化标准化（3 3）若决策变量）若决策变量xj0，则令，则令（4 4）若决策变量）若决策变量xj取值无限制，则令取值无限制，则令（5 5）若约束等式的右端常数）若约束等式的右端常数bi 0 0，则等式两边同时乘以，则等式两边同时乘以“-1-1”。其中其中（“一分为二一分为二”）例：例：将下列线性规划模型化为标准形式。将下列线性规划模型化为标准形式。则问题化为标准形式：则问题化为标准形式：并引入松弛变量并引入松弛变量x4,x5,课堂练习：将下列线性规划问题化为标准形式线性规划问题的数学模型标准形式如下：1-4 1-4 线性规划问题的解线性规划问题的解已知线性规划的标准形式：已知线性规划的标准形式：或或1 1、求解线性规划问题求解线性规划问题：从满足（从满足（2）、（）、（3）的方程组中找出一个解使目标函）的方程组中找出一个解使目标函数（数（1）达到最大值。）达到最大值。2 2、可行解可行解：所有可行解的集合。所有可行解的集合。可行域可行域：满足约束条件（满足约束条件（2）、（）、（3）的解。）的解。记做记做最优解最优解：使目标函数达到最大值的可行解。使目标函数达到最大值的可行解。（1 1）基基：设：设A A为线性规划问题约束条件的为线性规划问题约束条件的 m n 系数矩阵系数矩阵（m00，有如下结论：有如下结论：(1)(1)若对所有若对所有jm+1，有，有 j 0 0，则，则z（1）z（0），即，即z（0）为为最优函数值，最优函数值，X（0）为为唯一最优解唯一最优解；(2)(2)若对所有若对所有j m+1，有有 j 0，且，且存在某个非基变量的检验数存在某个非基变量的检验数 k=0，则将，则将Pk作为新的基向量得出新的基可行解作为新的基向量得出新的基可行解X（1 1），满足，满足z（1）=z（0），故，故z（1）也也为最优函数值，从而为最优函数值，从而 X（1）也也为最优解，为最优解，X（0）、X（1）连线上所有点均为最优解，因此该线性规划连线上所有点均为最优解，因此该线性规划模型具有模型具有无穷多最优解无穷多最优解；(3)(3)若存在某个若存在某个 j 0 0，但对应的第，但对应的第j列系数全非正，即列系数全非正，即aij 0 0，则，则当当 +时，有时，有z（1）+，该线性规划模型具有该线性规划模型具有无界解无界解。1.4 1.4 单纯形法的计算步骤单纯形法的计算步骤1 1、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。不妨假设不妨假设A中前中前m列对应的子矩阵是单位列对应的子矩阵是单位矩阵，取其为基矩阵，取其为基B，得到初始基可行解，得到初始基可行解m+3行行n+4列列第第1行：价值行行：价值行 cj第第2行：变量行行：变量行 xj最后一最后一行：检验数行行：检验数行 j第第1列：基价值列列：基价值列 CB第第2列列：基变量列：基变量列 XB第第3列列：基解列：基解列 b最后一最后一列：列：比值比值列列 主体：系数矩阵主体：系数矩阵Amn2 2、单纯形表的结构、单纯形表的结构3 3、初始单纯形表：含初始基可行解的单纯形表、初始单纯形表：含初始基可行解的单纯形表 最优单纯形表：含最优解的单纯形表最优单纯形表：含最优解的单纯形表4 4、单纯形法（、单纯形法（Simplex MethodSimplex Method）：）：利用单纯形表求解线性规划问题的方法。利用单纯形表求解线性规划问题的方法。5 5、单纯形法的计算步骤、单纯形法的计算步骤(1)(1)化化 L.P.问题为标准形式问题为标准形式,建立初始单纯形表；建立初始单纯形表；(3)(3)计算计算(4)(4)以以alk为主元素为主元素(简称主元，用简称主元，用 表示表示)，进行线性方程组，进行线性方程组 的的初等行变换，将主元列初等行变换，将主元列Pk化为单位向量得到新的单纯形表，化为单位向量得到新的单纯形表，转入转入(2)(2)。（最大正检验数决定换入变量）（最大正检验数决定换入变量）（最小比值（最小比值决定换出变量决定换出变量）例例1：用单纯形法求解下列线性规划问题：用单纯形法求解下列线性规划问题.max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0，x2 0 s.t.解：先标准化解：先标准化Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 再列初始单纯形表：再列初始单纯形表：6-32 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 1615 2 2 1 0 0 6 4 0 0 1 0 -0 5 0 0 1 3 2 3 0 0 0以以55为主元进为主元进行初等行变换行初等行变换Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X2 6 16 3 2 0 1 0 -2/5 3 4 0 0 1 0 4 0 1 0 0 1/5 -2 0 0 0 -3/5x1 1为换入变量为换入变量下面开始单纯形法迭代：下面开始单纯形法迭代：x5 5为换出变量为换出变量x2 2为换入变量为换入变量以以22为主元进为主元进行初等行变换行初等行变换x3 3为换出变量为换出变量主元化为主元化为1，主元列，主元列的其他元素化为的其他元素化为0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5此时得到唯一最优解此时得到唯一最优解X*=(3,3)T,Zmax=15=15。例例2 用单纯形法求解下列线性规划问题用单纯形法求解下列线性规划问题解：先标准化解：先标准化 2 1 0 0 54 x3x400 x1 x2 x3 x4bxBcB 2 1 0 0cj 2415351 06201 0 0 x3x102 x1 x2 x3 x4bxBcB 2 1 0 0cj430141 01/3-1/21/61/3-1/33/412 0 0 -1/12 -7/24 x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cj15/43/4011/4-1/810-1/125/24唯一最优解6、单纯形法中存在的问题、单纯形法中存在的问题（1 1）存在两个以上的最大正检验数。存在两个以上的最大正检验数。任取一个最大正检验数对应的变量作为换入变量。任取一个最大正检验数对应的变量作为换入变量。（2 2）出现两个以上相同的最小值。出现两个以上相同的最小值。任取一个最小任取一个最小对应的变量作为换出变量。对应的变量作为换出变量。此时此时L.P.问题出现退化现象。问题出现退化现象。练习：练习：5-1 5-1 人工变量法（大人工变量法（大M法）法）1.5 单纯形法的进一步讨论 前面讨论了在标准型中系数矩阵有单位矩阵，很前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大量，构成的可行基称为人工基，用大MM法或两阶法或两阶段法求解，这种用人工变量作桥梁的求解方法称段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。为人工变量法。例例1：用单纯形法求解下列线性规划问题。：用单纯形法求解下列线性规划问题。解：先标准化为解：先标准化为系数矩阵系数矩阵但是但是A中没有单位矩阵，在中没有单位矩阵，在A中人为的增加两列中人为的增加两列此时对应的约束方程组为对应的约束方程组为：该问题新增加了两个变量：x4,x5（称为人工变量）（称为人工变量）A有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。为使 必须保证在可行解中人工变量必须保证在可行解中人工变量x4=x5=0，故令故令x4，x5在目标函数中的系数为在目标函数中的系数为M（其中（其中M表示任意大的正数），表示任意大的正数），这种添加人工变量求解这种添加人工变量求解LP的方法称为的方法称为人工变量法人工变量法,计算过程中出现了计算过程中出现了M，这种方法也称为，这种方法也称为大大M法法。等价于于是，这个线性规划问题转化为：于是，这个线性规划问题转化为：以下可用单纯形法继续求解。以下可用单纯形法继续求解。Cj x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1-2 -3 0 -M -M34x4 x5-M -Mcj-zj-2+2M-3+3M-M03/1=34/2=21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj-zj-1/2+M/2 0 -M 0 3/2-3M/2-M-3241 0 -2 2 -1 0 1 1 -1 1x1 x221cj-zj 0 0 -1 1-M 1-M-2-3x50唯一最优解故 zmin=7注意：此时人工变量x4=x5=0说明：说明：若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工变量的人工变量 ，则该模，则该模型型无可行解无可行解。采用大采用大M法求解线性规划模型时，如果模型中法求解线性规划模型时，如果模型中各个系数与各个系数与M的值非常接近或相差很大，若用手工计算的值非常接近或相差很大，若用手工计算不会出现问题。但是若利用计算机求解，则容易引起混不会出现问题。但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大淆，使得机器判断出错，从而使大M法失效。法失效。在这种情况下，可采用下面的两阶段法进行计算。在这种情况下，可采用下面的两阶段法进行计算。5-2 5-2 两阶段法两阶段法(将将L.P.问题分成两个阶段来考虑问题分成两个阶段来考虑)第一阶段第一阶段:判断原判断原L.P.L.P.问题是否存在可行解。问题是否存在可行解。给原给原L.P.L.P.问题加入人工变量，并构造仅含人工变量的目标问题加入人工变量，并构造仅含人工变量的目标函数函数w（人工变量在人工变量在w中的系数一般取为中的系数一般取为1 1）并求）并求w的最小值；的最小值；然后用单纯形法求解。若求得然后用单纯形法求解。若求得wmin=0=0，则该问题有可行解，进，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。入第二阶段，否则该问题无可行解，结束。第二阶段：将第第二阶段：将第一一阶段得到的最终表去掉人工变量，并阶段得到的最终表去掉人工变量，并将目标函数还原为原将目标函数还原为原L.P.问题的目标函数（即修改最终表中问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。用单纯形法求解。例：用两阶段法求解下列线性规划问题。例：用两阶段法求解下列线性规划问题。标准化引入人工变量z(1)(1)第一阶段，构造判断是否存在可行解的模型：第一阶段，构造判断是否存在可行解的模型：用单纯形法求解这个问题，先标准化为；用单纯形法求解这个问题，先标准化为；Cj x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1 0 0 0 -1 -134x4 x5-1 -1cj-zj 2 3-103/1=34/2=21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj-zj 1/2 0 -1 0 -3/2-1 0241 0 -2 2 -1 0 1 1 -1 1x1 x221cj-zj 0 0 0 -1 -10 0 x50最优解本问题有可行解，进入第二阶段(2)(2)第二阶段第二阶段 先在第一阶段的最终单纯形表去掉人工变量，再还原原先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即目标函数，即 max z=-2=-2x1 1-3-3x2 2+0+0 x3 3，继续迭代：继续迭代：Cj x1x2x3XBbCB1 0 -2 0 1 1-2 -3 0 21x1 x2-2 -3cj-zj 0 0-1唯一最优解故 zmin=7注意：两阶段法中不再出现大M，但需要解两个线性规划问题，要注意目标函数系数的变化。5-3 关于解的判别例例7 用单纯形法解下列线性规划用单纯形法解下列线性规划无穷多解当所有的当所有的 ，但某一非基变量检验数，但某一非基变量检验数 ，存，存在无穷多最优解的条件是在无穷多最优解的条件是Ps列向量中至少存在一个元列向量中至少存在一个元素素 ，且能找出最优解，且能找出最优解.例例8 用单纯形法解下列线性规划用单纯形法解下列线性规划无界解无界解 若存在某个若存在某个 j 0 0，但对应的第，但对应的第j列系数全非正，即列系数全非正，即aij 0 0，则问题的解无界，则问题的解无界.例例9 用单纯形法解下列线性规划用单纯形法解下列线性规划无可行解无可行解若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工变量的人工变量 ，则该模，则该模型无可行解。型无可行解。用最终单纯形表判断线性规划问题解的类型：用最终单纯形表判断线性规划问题解的类型：解的类型解的类型最终表的特征最终表的特征无可行解无可行解有非有非0 0的人工变量的人工变量有有可可行行解解唯一最优解唯一最优解无无非非0 0的人的人工变量，非基变量的检验工变量，非基变量的检验数全为负数数全为负数无穷多最优解无穷多最优解无非无非0 0的人工的人工变量，非基变量的检验变量，非基变量的检验数全非正，且有某个非基变量的检验数全非正，且有某个非基变量的检验数为数为0 0无界解无界解无非无非0 0的的人工变量，有某个非基变量人工变量，有某个非基变量的检验数为正数，但该变量对应的系的检验数为正数，但该变量对应的系数全为非正数数全为非正数已知线性规划问题形如：已知线性规划问题形如：5-4 单纯形法计算的向量、矩阵描述引入松弛变量xs 记记X=(XB,XN,XS)T其中，其中，XS为松弛变量，在初始表中是基变量；为松弛变量，在初始表中是基变量；XB为为最终表中基变量；最终表中基变量；XN表示表示既不是初始表的基变量又不是最终表的基变量。既不是初始表的基变量又不是最终表的基变量。注意：注意：XS和和XB允许有公共变量。允许有公共变量。（2 2）A=(B,N,I)B,N,I分别为分别为XB、XN、XS在初始表中在初始表中对应对应的矩阵。的矩阵。则（则（1 1）C=(CB,CN,0)CB,CN,0分别为分别为XB、XN、XS在目标函数中的系数。在目标函数中的系数。（3 3）A=(I,N,B-1)I,N,B-1分别为分别为XB、XN、XS在最终表中在最终表中对应对应的矩阵。的矩阵。约束方程组两端同时左乘B-1，则可得如下表达式：初始单纯形表初始单纯形表最终单纯形表最终单纯形表用单纯形表表示如下：用单纯形表表示如下：XS bB N IXB b I N B-1初始表初始表 X XB B X XN N X XS S cj-zj 0,0 N S=（-y1,-y2,-ym）=-YT 最终表最终表 X XB B X XN N X XS S cj-zj B N 0,0 比较得：比较得：b=B-1b N=B-1N 或者或者 Pj=B-1Pj S=-CB B-1=-YT N=CN-CB B-1 N =CN-YT N或者或者 j=Cj-CBB-1 Pj其中其中B B-1-1为初始表中基变量在最终表对应的系数矩阵，为初始表中基变量在最终表对应的系数矩阵，B B为最终表中基变量在初始表对应的系数矩阵。为最终表中基变量在初始表对应的系数矩阵。例：用单纯形法求解下列线性规划问题.max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x10，x2 0 s.t.解：先标准化Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 得到初始单纯形表：6-3 2 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5最终单纯形表：X4010X4010可以验证：三三要要素素决策变量决策变量约束条件约束条件目标函数目标函数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa标标准准化化图图解解法法、单单纯纯形形法法单单纯纯形形法法不不处处理理令令xj=xj-xj xj 0 xj 0令令 xj=-xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=-Z 0-M根据上表可以列出初始单纯形表根据上表可以列出初始单纯形表5-5 5-5 单纯形法小结单纯形法小结个数取值限制右端常数约束方向要求系数列初始表列初始表1.7 应用举例 一般而言，一个经济、管理问题要满足以下条一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：件，才能建立线性规划模型：.需要求解问题的目标能用数值指标来反映，需要求解问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；且能用线性函数来描述目标的要求；.为达到这个目标存在多种方案；为达到这个目标存在多种方案；.要求达到的目标是在一定条件下实现的，这要求达到的目标