运筹学基础及应用PPT课件

《运筹学基础及应用PPT课件》由会员分享，可在线阅读，更多相关《运筹学基础及应用PPT课件（119页珍藏版）》请在金锄头文库上搜索。

1、运 筹 学( Operations Research )夫运筹策帷幄之中，决胜于千里之外夫运筹策帷幄之中，决胜于千里之外 史记史记 高祖本纪高祖本纪绪 论（1）运筹学简述）运筹学简述（2）运筹学的主要内容）运筹学的主要内容（3）本课程的主要学习内容）本课程的主要学习内容（4）运筹学的应用）运筹学的应用（5）本课程的教材及参考书）本课程的教材及参考书（6）本课程授课方式与考核）本课程授课方式与考核 本章主要内容：本章主要内容：一、古代朴素的运筹学思想一、古代朴素的运筹学思想国外国外英文原名英文原名 Operations Research 简称称“O.R.”直直译为：运用研究或作：运用研究或作业研

2、究研究正式出正式出现于于19381938年年7 7月英国一份关于防空作月英国一份关于防空作战系系统运运行的研究行的研究报告中告中中国古代运筹学案例中国古代运筹学案例二、运筹学的起源二、运筹学的起源（一）运筹学简述（一）运筹学简述运作研究运作研究(Operational Research)小小组”:二二战期期间解决解决复复杂的的战略和略和战术问题。例如：。例如：1.1.如何合理运用雷达有效地如何合理运用雷达有效地对付德付德军空空袭2.2.对商船如何商船如何进行行编队护航，使船航，使船队遭受德国潜艇攻遭受德国潜艇攻击时损失最少；失最少；3.3.在各种情况下如何在各种情况下如何调整反潜深水炸整反潜深

3、水炸弹的爆炸深度，才能的爆炸深度，才能增加增加对德国潜艇的德国潜艇的杀伤力等。力等。-二二战后运筹学的后运筹学的发展展经历了三个了三个阶段段 （1 1）19451945年到年到2020世世纪5050年代初年代初创建建时期期 （2 2）20 20 世世纪5050年代初到年代初到2020世世纪5050年代末年代末成成长时期期 （3 3） 20 20 世世纪6060年代以来年代以来迅速迅速发展和普及的展和普及的时期期国内国内19561956年成立第一个运筹学小组年成立第一个运筹学小组19571957年从年从“夫运筹策帷幄之中，决胜于千里之外夫运筹策帷幄之中，决胜于千里之外”中中摘取摘取“运筹运筹”二

4、字，将二字，将O.R.正式翻译为正式翻译为“运筹学运筹学”三、运筹学的定义三、运筹学的定义研究工具：数学，计算机科学及其他相关科学研究工具：数学，计算机科学及其他相关科学研究目的：对有限资源进行合理规划、使用，并提供研究目的：对有限资源进行合理规划、使用，并提供 优化决策方案。优化决策方案。研究对象：复杂系统的组织和管理研究对象：复杂系统的组织和管理参考参考大英百科全书大英百科全书、辞海辞海、中国企业管理百科全书中国企业管理百科全书等。等。四、运筹学研究的基本特点四、运筹学研究的基本特点 系统的整体优化系统的整体优化 多学科的配合多学科的配合 模型方法的应用模型方法的应用五、运筹学研究的基本步

5、骤五、运筹学研究的基本步骤 分析与表述问题分析与表述问题 建立数学模型建立数学模型 对问题求解对问题求解 对模型和模型导出的解进行检验对模型和模型导出的解进行检验 建立对解的有效控制建立对解的有效控制 方案的实施方案的实施（二）运筹学的主要内容（二）运筹学的主要内容数学数学规划（划（线性性规划、整数划、整数规划、目划、目标规划划、动态规划等）划等）图论存存贮论排排队论对策策论（博弈（博弈论）决策决策论（三）运筹学的应用（三）运筹学的应用运筹学方法运筹学方法应用例用例线性性规划划生生产结构构优化化非非线性性规划划投投资组合合优化化整数整数规划划选址址问题动态规划划资源分配源分配问题网网络分析分析

6、工程工程计划划优化化排排队论服服务系系统优化化 存存贮论订货库存管理存管理决策分析决策分析机会机会选择运筹学的广泛运筹学的广泛实际背景促使其不断背景促使其不断发展并展并 在在经济管管理和系理和系统工程等多工程等多领域中域中发挥着令着令 人瞩目的重要作用。人瞩目的重要作用。 诺贝尔经济学学奖从从1969年首年首发至今的至今的57 位位获奖者中者中就有多位是运筹学家。就有多位是运筹学家。 1975年年诺贝尔经济学学奖授授给了了库普曼和康脱普曼和康脱罗维 奇，以表奇，以表彰首先将彰首先将线性性规划与划与经济问题相相联系而系而 做出的做出的贡献；献； 1994年年诺贝尔经济学学奖授授给了三位博弈了三位

7、博弈论专家：家： 纳什、什、泽尔腾、海、海萨尼。博弈尼。博弈论已已经成成为当代当代经 济学的基石。学的基石。 2005年以色列年以色列经济学家学家罗伯特伯特-奥曼和美国奥曼和美国经济 学家托学家托马斯斯-斯切林，因斯切林，因“通通过博弈博弈论分析加分析加强了了 我我们对冲突和合作的冲突和合作的理解理解”所作出的所作出的贡献而献而获奖。 发表的部分获奖项目组织组织应用应用效果效果联合航空公司联合航空公司在满足乘客需求的前提下，以最低在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排成本进行订票及机场工作班次安排每年节约成本每年节约成本600600万美元万美元CitgoCitgo石油公司

8、石油公司优化炼油程序及产品供应、配送和优化炼油程序及产品供应、配送和营销营销每年节约成本每年节约成本70007000万万AT&TAT&T优化商业用户的电话销售中心选址优化商业用户的电话销售中心选址每年节约成本每年节约成本4.064.06亿美亿美元，销售额大幅增加元，销售额大幅增加标准品牌公司标准品牌公司控制成本库存（制定最优再定购点控制成本库存（制定最优再定购点和定购量确保安全库存）和定购量确保安全库存）每年节约成本每年节约成本380380万美元万美元法国国家铁路公司法国国家铁路公司制定最优铁路时刻表并调整铁路日制定最优铁路时刻表并调整铁路日运营量运营量每年节约成本每年节约成本15001500

9、万美万美元，年收入大幅增加。元，年收入大幅增加。Taco BellTaco Bell优化员工安排，以最低成本服务客优化员工安排，以最低成本服务客户户每年节约成本每年节约成本13001300万美万美元元DeltaDelta航空公司航空公司优化配置上千个国内航线航班来实优化配置上千个国内航线航班来实现利润最大化现利润最大化每年节约成本每年节约成本1 1亿美元亿美元（四）本课程的教材及参考书（四）本课程的教材及参考书选用教材用教材 运筹学基运筹学基础及及应用用胡运胡运权主主编 （第五版）高等教（第五版）高等教育出版社育出版社参考教材参考教材运筹学教程运筹学教程胡运胡运权主主编 （第（第4 4版）清版

10、）清华出版社出版社管理运筹学管理运筹学韩伯棠主伯棠主编 （第（第2 2版）高等教育出版版）高等教育出版社社运筹学运筹学( (修修订版版) ) 钱颂迪主迪主编 清清华出版社出版社 （五）本课程的主要学习内容（五）本课程的主要学习内容 第一章第一章 线性规划及单纯形法线性规划及单纯形法 第二章第二章 线性规划的对偶理论线性规划的对偶理论 第三章第三章 运输问题运输问题 第四章第四章 整数规划与分配问题整数规划与分配问题 （六）本课程授课方式与考核（六）本课程授课方式与考核学科总成绩学科总成绩平时成绩平时成绩（3030）课堂考勤课堂考勤（1212）平时作业平时作业（1818）期末成绩期末成绩（707

11、0）讲授为主，结合讨论、习题作业讲授为主，结合讨论、习题作业第一章第一章 线性规划及单纯形法线性规划及单纯形法Linear Programming and Simplex Method线性规划-发展简史法国数学家J.-B.-J.傅里叶和C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年年苏联数学家数学家.康托康托罗维奇奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。1947年美国数学家年美国数学家G.B.丹丹齐克克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法形法，为这门学科奠定了基础。1947年美国数学家年美国数学家J

12、.von诺伊曼提伊曼提出出对偶理偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国年美国经济学家学家T.C.库普普曼斯把曼斯把线性性规划划应用到用到经济领域域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年年C.莱姆基提出莱姆基提出对偶偶单纯形法形法，1954年年S.加斯和加斯和T.萨迪等人解决了迪等人解决了线性性规划的灵敏度分析划的灵敏度分析和参数和参数规划划问题，1956年年A.塔克提出互塔克提出互补松弛定理，松弛定理，1960年年G.B.丹丹齐克和克和P.沃沃尔夫提出分解

13、算法夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年年苏联数学家数学家.哈奇哈奇扬提出解提出解线性性规划划问题的的椭球算法球算法，并证明它是多项式时间算法。1984年年美国贝尔电话实验室的印度数学家N.卡卡马卡提出解卡提出解线性性规划划问题的新的多的新的多项式式时间算法算法-内点算法内点算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项

14、式算法理论。50年代后线性规划的应用范围不断扩大。1.1939年，前年，前苏联科学家康托洛科学家康托洛维奇奇-生生产组织与管理中的数学方法与管理中的数学方法是是线性性规划划应用于工用于工业生生产问题的开山之作的开山之作；(LEONIDVITALIYEVICHKANTOROV(1912-1986) 2. 1947年，美国数学家年，美国数学家乔治治 伯伯纳德德 丹丹齐格格-单纯形法，被称形法，被称为线性性规划之父。划之父。GeorgeBernardDantzig(19142005)丹丹齐格在格在1946年年获伯克利大学的博士学位。伯克利大学的博士学位。1947年，年，33岁提出了解决一种最提出了解

15、决一种最优化化问题的的单纯形法形法,该方法奠定了方法奠定了线性性规划的基划的基础，使得使得经济学、学、环境科学、境科学、统计学学应用等学科用等学科获得了迅速得了迅速发展。展。Dantzig也因而被誉也因而被誉为“线性性规划之父划之父”。 1952年他在年他在兰德公司任德公司任研究数学家，在公司研究数学家，在公司电脑上上实行行线性性规划。划。1960年他被母校聘任教年他被母校聘任教授授计算机科学，算机科学，终于当上运筹学中心主任。于当上运筹学中心主任。1966年他在史丹福大学年他在史丹福大学当当类似似职位，留在那里直到位，留在那里直到1990年代退休。年代退休。Dantzig在运筹学建在运筹学建

16、树极高，极高，获得了包括得了包括“冯诺伊曼理伊曼理论奖”在在内的内的诸多多奖项。他在。他在Linear programming andextensions一一书中研中研究了究了线性性编程模型，程模型，为计算机算机语言的言的发展做出了不可磨展做出了不可磨灭的的贡献。他献。他除了除了线性性规划和划和单纯形法的杰出工作，形法的杰出工作，还推推进很多很多领域的域的发展，有分展，有分解解论、灵敏度分析、互、灵敏度分析、互补主元法、大系主元法、大系统最最优化、非化、非线性性规划和不确划和不确定定规划。划。SIAM Journal on Optimization1991年年创刊号是献刊号是献给他的。他的。M

17、athematical Programming Society为表彰丹表彰丹齐格，格，设立丹立丹齐格格奖，1982年起每三年年起每三年颁给一至两位在数学一至两位在数学规划有突出划有突出贡献的人。献的人。xa此为无约束的极值问题此为无约束的极值问题1.1 一般线性规划问题的数学模型一般线性规划问题的数学模型1-1 1-1 问题的提出问题的提出例例1 1 用一块边长为用一块边长为a的正方形铁皮做一个无盖长方体容器，的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？应如何裁剪可使做成的容器的容积最大？解：如图设四个角上减去的小正方形边解：如图设四个角上减去的小正方形边长为长为x，

18、则容器体积为：，则容器体积为：时，容积最大时，容积最大 例例2 2 常山机器厂生产常山机器厂生产 I I、IIII 两型产品。这两型产两型产品。这两型产品都分别要在品都分别要在A A、B B、C C三种不同设备上加工。按工三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：的工时以及各种设备工时的限额如下表： 单位产品消耗设单位产品消耗设备工时备工时I IIIII设备工时限量设备工时限量（小时）（小时） 设备设备A A设备设备B B设备设备C C2 24 40 02 20 05 5121216161

19、515单位利润（元）单位利润（元）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 线性规划问题的数学模

20、型线性规划问题的数学模型原型原型模型模型数学模型数学模型提炼提炼数学工具数学工具1 1、原型原型：现实世界中人们关心、研究的实际对象。：现实世界中人们关心、研究的实际对象。 模型模型：将某一部分信息简缩、提炼而构造的原型替代物。：将某一部分信息简缩、提炼而构造的原型替代物。 数学模型数学模型：对现实世界的一个特定对象，为达到一定目的，：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设根据内在规律做出必要的简化假设, ,并运用适当数学工具得到并运用适当数学工具得到的一个数学结构。的一个数学结构。3 3、规划问题数学模型的三要素、规划问题数学模型的三要素（2 2）目标函数目

21、标函数：问题要达到的目标要求，表示为决策变量的：问题要达到的目标要求，表示为决策变量的函数。用函数。用 z= =f( (x1 1，x2 2，xn n) )表示。表示。（1 1）决策变量决策变量：决策者为实现规划目标采取的方案、措施，：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用是问题中要确定的未知量。用x1 1，x2 2，xn n表示。表示。（3 3）约束条件约束条件：决策变量取值时受到的各种可用资源的限制，：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。表示为含决策变量的等式或不等式。2 2、规划问题、规划问题即求目标函数在若干约束条件下的最值。

22、即求目标函数在若干约束条件下的最值。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, ,

23、 xn0（3 3）其他形式其他形式：连加形式连加形式向量形式向量形式其中 称为价值行向量价值行向量；决策列向量决策列向量系数列向量系数列向量右端列向量右端列向量矩阵形式矩阵形式其中 称为价值行向量；称为价值行向量；决策列向量决策列向量右端列向量右端列向量约束矩阵或系数矩阵约束矩阵或系数矩阵1-3 1-3 线性规划问题的标准形式线性规划问题的标准形式1 1、标准形式、标准形式或或2 2、条件、条件目标函数求极大值目标函数求极大值约束条件全是等式（线性方程组）约束条件全是等式（线性方程组）决策变量全非负决策变量全非负右端常数全非负右端常数全非负3 3、标准化方法、标准化方法（1）若目标函数求极小值

24、，即）若目标函数求极小值，即则令则令 转化为转化为（2 2）若约束条件为不等式，）若约束条件为不等式，则依次引入松弛变量或剩余变量（统称为松弛变量），则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。转化为等式约束条件。注意注意：松弛变量在目标函数中系数全为：松弛变量在目标函数中系数全为0。约束为约束为不等式，减去松弛变量，化为等式约束条件；不等式，减去松弛变量，化为等式约束条件；约束为约束为不等式，加上松弛变量，化为等式约束条件。不等式，加上松弛变量，化为等式约束条件。多多退退少少补补例：例：max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 1

25、5x1 0， x2 0 s.t.标准化标准化（3 3）若决策变量）若决策变量xj0，则令，则令（4 4）若决策变量）若决策变量xj取值无限制，则令取值无限制，则令（5 5）若约束等式的右端常数）若约束等式的右端常数bi 0 0，则等式两边同时乘以，则等式两边同时乘以“-1-1”。其中其中（“一分为二一分为二”）例：例：将下列线性规划模型化为标准形式。将下列线性规划模型化为标准形式。则问题化为标准形式：则问题化为标准形式：并引入松弛变量并引入松弛变量x4, x5,课堂练习：将下列线性规划问题化为标准形式线性规划问题的数学模型标准形式如下：1-4 1-4 线性规划问题的解线性规划问题的解已知线性规

26、划的标准形式：已知线性规划的标准形式：或或1 1、求解线性规划问题求解线性规划问题：从满足（从满足（2）、（）、（3）的方程组中找出一个解使目标函）的方程组中找出一个解使目标函数（数（1）达到最大值。）达到最大值。2 2、可行解可行解：所有可行解的集合。所有可行解的集合。可行域可行域：满足约束条件（满足约束条件（2）、（）、（3）的解。）的解。记做记做最优解最优解： 使目标函数达到最大值的可行解。使目标函数达到最大值的可行解。（1 1）基基：设：设A A为线性规划问题约束条件的为线性规划问题约束条件的 m n 系数矩阵系数矩阵（m00， 有如下结论：有如下结论：(1) (1) 若对所有若对所有

27、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） 连线上所有点均为最优解，因此该线性规划连线上所有点均为最优解，因此该线性规划模型具有模型具有无

28、穷多最优解无穷多最优解；(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行：价值行行：价值行 c

29、j第第2行：变量行行：变量行 xj最后一最后一行：检验数行行：检验数行 j第第1列：基价值列列：基价值列 CB第第2列列：基变量列：基变量列 XB第第3列列：基解列：基解列 b最后一最后一列：列：比值比值列列 主体：系数矩阵主体：系数矩阵Amn2 2、单纯形表的结构、单纯形表的结构3 3、初始单纯形表：含初始基可行解的单纯形表、初始单纯形表：含初始基可行解的单纯形表 最优单纯形表：含最优解的单纯形表最优单纯形表：含最优解的单纯形表4 4、单纯形法（、单纯形法（ Simplex MethodSimplex Method ）：）： 利用单纯形表求解线性规划问题的方法。利用单纯形表求解线性规划问题的

30、方法。5 5、单纯形法的计算步骤、单纯形法的计算步骤(1) (1) 化化 L.P.问题为标准形式问题为标准形式, ,建立初始单纯形表；建立初始单纯形表；(3) (3) 计算计算(4)(4) 以以alk为主元素为主元素( (简称主元，用简称主元，用 表示表示) )，进行线性方程组，进行线性方程组 的的初等行变换，将主元列初等行变换，将主元列Pk化为单位向量得到新的单纯形表，化为单位向量得到新的单纯形表，转入转入(2)(2)。（最大正检验数决定换入变量）（最大正检验数决定换入变量）（最小比值（最小比值决定换出变量决定换出变量）例例1：用：用单纯形法求解下列形法求解下列线性性规划划问题.max z=

31、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为主元进为主元进行

32、初等行变换行初等行变换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 X

33、4 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 用单纯形法求解下列线性规划问题用单纯形法求解下列线性规划问题解：先标准化解：先标准化 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 x2x1

34、12 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 单纯形法的进

35、一步讨论 前面讨论了在标准型中系数矩阵有单位矩阵，前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大工变量，构成的可行基称为人工基，用大M M法或法或两阶段法求解，这种用人工变量作桥梁的求解方两阶段法求解，这种用人工变量作桥梁的求解方法称

36、为人工变量法。法称为人工变量法。例例1：用单纯形法求解下列线性规划问题。：用单纯形法求解下列线性规划问题。解：先标准化为解：先标准化为系数矩阵系数矩阵但是但是A中没有单位矩阵，在中没有单位矩阵，在A中人为的增加两列中人为的增加两列此时对应的约束方程组为对应的约束方程组为：该问题新增加了两个变量：x4, x5（称为人工变量）（称为人工变量）A有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。为使 必须保证在可行解中人工变量必须保证在可行解中人工变量x4=x5=0，故令故令x4，x5在目标函数中的系数为在目标函数中的系数为M （其中（其中M表示

37、任意大的正数），表示任意大的正数），这种添加人工变量求解这种添加人工变量求解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/

38、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的值非常接近或相差很大，若用手工计算的值非常接近或相差很大，若用手工计算不会出现问题。但是若利用计算机求解，则容易引起混不会出现问题

39、。但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大淆，使得机器判断出错，从而使大M法失效。法失效。 在这种情况下，可采用下面的两阶段法进行计算。在这种情况下，可采用下面的两阶段法进行计算。5-2 5-2 两阶段法两阶段法( (将将L.P.问题分成两个阶段来考虑问题分成两个阶段来考虑) ) 第一阶段第一阶段: : 判断原判断原L.P.L.P.问题是否存在可行解。问题是否存在可行解。 给原给原L.P.L.P.问题加入人工变量，并构造仅含人工变量的目标问题加入人工变量，并构造仅含人工变量的目标函数函数w（人工变量在人工变量在w中的系数一般取为中的系数一般取为1 1）并求）并求w的最小

40、值；的最小值；然后用单纯形法求解。若求得然后用单纯形法求解。若求得wmin=0=0，则该问题有可行解，进，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。入第二阶段，否则该问题无可行解，结束。 第二阶段：将第第二阶段：将第一一阶段得到的最终表去掉人工变量，并阶段得到的最终表去掉人工变量，并将目标函数还原为原将目标函数还原为原L.P.问题的目标函数（即修改最终表中问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。用单纯形法求解。例：用两阶段法求解下列线性规划问题。例：用两阶段法求解下列线性规

41、划问题。标准化引入人工变量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

42、x50最优解本问题有可行解，进入第二阶段 (2) (2) 第二阶段第二阶段 先在第一阶段的最终单纯形表去掉人工变量，再还原原先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即目标函数，即 max z=-2=-2x1 1-3-3x2 2+0+0x3 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 用单纯形法解下列线性规划用单纯形法解下列线性规划无穷多解当所有

43、的当所有的 ，但某一非基变量检验数，但某一非基变量检验数 ，存，存在无穷多最优解的条件是在无穷多最优解的条件是Ps列向量中至少存在一个元列向量中至少存在一个元素素 ，且能找出最优解，且能找出最优解.例例8 用单纯形法解下列线性规划用单纯形法解下列线性规划无界解无界解 若存在某个若存在某个 j 0 0，但对应的第，但对应的第j列系数全非正，即列系数全非正，即aij 0 0，则问题的解无界，则问题的解无界. .例例9 用单纯形法解下列线性规划用单纯形法解下列线性规划无可行解无可行解若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工变量的人工变量 ，则该模，则该模型无可行解。型无可行

44、解。用最终单纯形表判断线性规划问题解的类型：用最终单纯形表判断线性规划问题解的类型：解的类型解的类型最终表的特征最终表的特征无可行解无可行解有非有非0 0的人工变量的人工变量有有可可行行解解唯一最优解唯一最优解无无非非0 0的人的人工变量，非基变量的检验工变量，非基变量的检验数全为负数数全为负数无穷多最优解无穷多最优解无非无非0 0的人工的人工变量，非基变量的检验变量，非基变量的检验数全非正，且有某个非基变量的检验数全非正，且有某个非基变量的检验数为数为0 0无界解无界解无非无非0 0的的人工变量，有某个非基变量人工变量，有某个非基变量的检验数为正数，但该变量对应的系的检验数为正数，但该变量对

45、应的系数全为非正数数全为非正数已知线性规划问题形如：已知线性规划问题形如：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

46、,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

47、比较得：比较得：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

48、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可以验证：三三要要素素决策变量决策变量约束条件约束条件目标函数目标函数两两个个三个三个以上以上xj0xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa标标准准化化图

49、图解解法法、单单纯纯形形法法单单纯纯形形法法不不处处理理令令xj = xj - xj xj 0xj 0令令 xj =- xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=- Z 0-M根据上表可以列出初始单纯形表根据上表可以列出初始单纯形表5-5 5-5 单纯形法小结单纯形法小结个数取值限制右端常数约束方向要求系数列初始表列初始表1.7 应用举例 一般而言，一个经济、管理问题要满足以下条一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：件，才能建立线性规划模型： . .需要求解问题

50、的目标能用数值指标来反映，需要求解问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；且能用线性函数来描述目标的要求； . .为达到这个目标存在多种方案；为达到这个目标存在多种方案； . .要求达到的目标是在一定条件下实现的，这要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式来描述。些条件可用线性等式或不等式来描述。（一）、混合配料问题例：某糖果厂用原料例：某糖果厂用原料A A、B B、C C加工成三种不同牌号的糖果甲、乙、丙。已知加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中各种原料的含量，原料成本，各种原料的每月限制用量，各种牌号糖果中各种原料的含量，原料

51、成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如下表所示。问该厂每月生产这三三种牌号糖果的单位加工费用及售价如下表所示。问该厂每月生产这三种牌号糖果各多少千克，能使该厂获利最大。请建立这个问题的线性规种牌号糖果各多少千克，能使该厂获利最大。请建立这个问题的线性规划模型。划模型。甲甲乙乙丙丙原料成本（元原料成本（元/kg/kg）每月限制用每月限制用量（量（kgkg）A AB BC C6060202030305050 60602.002.001.501.501.001.00200020002500250012001200加工费（元加工费（元/kg/kg）0.500.500.400.

52、400.300.30售价（元售价（元/kg/kg）3.403.402.852.852.252.25解：用i=1,2,3表示原料A、B、C；用j=1,2,3表示糖果甲、乙、丙；设xij为生产第j种糖果使用的第i种原料的质量，则该问题的数学模型为：s.t.原料供应限制含量要求条件用单纯形法求得：即每月生产甲糖果 kg，乙糖果 kg，不生产丙糖果，可获得最大利润为5450元。（二）、投资项目组合问题例：兴安公司有一笔例：兴安公司有一笔3030万元的资金，考虑今后三年内用于下列万元的资金，考虑今后三年内用于下列项目的投资：项目的投资：1 1、三年内每年年初均可投资，每年获利为投资额的、三年内每年年初均

53、可投资，每年获利为投资额的20%20%，其本，其本利可一起用于下一年投资；利可一起用于下一年投资；2 2、只允许第一年初投入，于第二年末收回，本利合计为投资额、只允许第一年初投入，于第二年末收回，本利合计为投资额的的150%,150%,但此类投资限额不超过但此类投资限额不超过1515万元；万元；3 3、允许于第二年初投入，于第三年末收回，本利合计为投资额、允许于第二年初投入，于第三年末收回，本利合计为投资额的的160%160%，但限额投资，但限额投资2020万元；万元；4 4、允许于第三年初投入，年末收回，可获利、允许于第三年初投入，年末收回，可获利40%40%，但限额为，但限额为1010万元

54、万元. .试为该公司确立一个使第三年末本利和最大的投资组合方案，试为该公司确立一个使第三年末本利和最大的投资组合方案，请建立这个问题的线性规划模型。请建立这个问题的线性规划模型。解：用xij表示第i年初投放到第j个项目的资金数，则建立如下线性规划模型：1234一二三第第i年初年初投入第投入第j个项目个项目1234一一166666.7133333.3二二0200000三三100000100000 第三年末本利和第三年末本利和=580000用单纯形法求得：综上投资组合方案如下：综上投资组合方案如下： ( (三）、人力资源分配问题三）、人力资源分配问题例例 某昼夜服务的公交线路每天各时间段内所需某昼

55、夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：司机和乘务人员人数如下表所示：班次班次时间时间所需人员所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少足工作需要，又使配备司机和乘务人员的人数减少?解：设xi表示第i班次时开始上

56、班的司机和乘务人员人数。此问题最优解：x150，x220，x350，x40，x520，x610，一共需要司机和乘务员150人。（四）、套裁下料问题（四）、套裁下料问题例：现有一批某种型号的圆钢长例：现有一批某种型号的圆钢长8米，需要截取米，需要截取2.5米米长的毛坯长的毛坯100根，长根，长1.3米的毛坯米的毛坯200根。问如何才能根。问如何才能既满足需要，又能使总的用料最少？既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格个下料方案。其次要求这些方案的总

57、体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出的，为此可以设计出4种下料方案以供套裁用。种下料方案以供套裁用。2.5m32101.3m0246料头料头0.50.40.30.2设按方案、下料的原材料根数分别为xj (j=1，2,3,4)，可列出下面的数学模型：Lingo软件LINGO软件是美国的LINDO系统公司（LindoSystemInc）开发的一套用于求解最优化问题的软件包.LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解.LINGO软件

58、的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快.LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果，这里简单介绍LINGO的使用方法.LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等.LINGO的语法规定：的语法规定： （1）求目标函数的最大值或最小值分别用）求目标函数的最大值或最小值分别用MAX=或或MIN=来表示；来表示； （2）每个语句必须以分号）每个语句必须以分号“；”结束，每行可以有许多语结束，每行可以有许多语句，语句可以跨行；句，语句可以跨行； （3

59、）变量名称必须以字母（）变量名称必须以字母（AZ）开头，由字母、数字）开头，由字母、数字（09）和下划线所组成，长度不超过）和下划线所组成，长度不超过32个字符，不区分个字符，不区分大小写；大小写； （4）可以给语句加上标号，例如）可以给语句加上标号，例如MAX=200*X1+300*X2； （5）以惊叹号）以惊叹号“！”开头，以分号开头，以分号“；”结束的语句是注结束的语句是注释语句；释语句；（6）如果对变量的取值范围没有作特殊说明，则默认所有）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；决策变量都非负； （7）LINGO模型以语句模型以语句“MODEL：”开头，以开头，以“END”结束，对于比较简单的模型，这两个语句可以省略结束，对于比较简单的模型，这两个语句可以省略