《运筹学》课程教学资源（电子教材）绪论、第1章线性规划及单纯形法.pdf_大学文库

运筹学基础及其MATLAB应用成功范例。此外，盟军的反潜艇战运筹研究小组针对德军潜艇的作战研究也卓有成效。他们通过对以往攻击德军潜艇的相关数据的分析，提出了两条重要建议：一是将反潜攻击由潜艇投掷水雷改为飞机投掷深水炸弹：二是将起爆时间改为德军潜艇刚下潜时。事实证明，这样的效果是最佳的。类似成功的例子在第二次世界大战期间还有很多。据统计，在第二次世界大战期间，英国、美国和加拿大等国军队里的运筹学工作人员一度超过了 700人。这些运筹学工作人员研究的问题还包括战斗机炮弹的合理载荷量问题和如何用一定数量的战斗机封锁给定的海面海域的问题等。第二次世界大战时期军事运筹学的特点表现在：在采集实际数据的基础上，通过多学科的密切协作，用定量化、系统化的方法研究立足现有技术装备如何达到最佳的作战效果。追根溯源，如上所述的思想和方法在古代人们的生活和生产活动中就己经出现。例如，中国古代著名的“田忌赛马”“赵括运粮”“丁谓修宫”等故事，李冰父子主持修建的由“鱼嘴”岷江分洪工程、“飞沙堰”分洪排沙工程和“宝瓶口”引水工程巧妙结合而成的都江堰水利工程，《梦溪笔谈》所记录的军粮供应与用兵进退的关系等事例，无不闪耀着现代所称的运筹学思想，即体现了立足现有技术装备整体优化的朴素思想。进入20 世纪后，现代运筹学的思想已经在很多方面有所体现，比如1914年英国工程师兰彻斯特 (Lanchester)提出的战斗方程，l917年丹麦工程师研究电话通信时提出的排队论的一些著名公式，20世纪20年代初提出的存储论的最优批量公式，以及20世纪30年代苏联数学家康托洛维奇在解决工业生产组织和计划问题时提出的类似线性规划的模型，等等。由于运筹学主要是采用定量分析手段，研究如何最佳利用现有技术装备问题，以求达到最佳效果，所以第二次世界大战以后在美国等发达国家开始将运筹学的思想和方法运用到工业和经济管理领域，并取得了非常好的效果。到20世纪五六十年代，从事运筹学的工作者队伍开始迅速壮大，纷纷成立学会、创办刊物并开始在高校开设运筹学课程。也正是在这段时期，现代运筹学由钱学森、徐国志先生从美国归国时引入中国，并且在两位先生的推动下于1956年在中国科学院力学研究所成立了中国第一个运筹学研究小组。1959年，第二个运筹学研究部门在中国科学院数学研究所成立，这是数学家们投身于国家建设的一个产物。力学所小组与数学所小组于1960年合并成为数学研究所的一个研究室，当时的主要研究方向为排队论、非线性规划和图论，还有人专门研究运输理论、动态规划和经济分析（如投入产出方法）。50年代后期，运筹学在中国的应用集中在运输问题上，其中一个广为流传且容易明白的例子就是“打麦场的选址问题”。研究该问题的目的在于解决当时在以手工收割为主的情况下如何节省人力、物力。著名的“中国邮递员问题”也是在那个时期由管梅谷教授提出的。特别值得一提的是，华罗庚先生在 “文化大革命”那种特殊历史时期在全国推广的“优选法”。华罗庚先生将一些基本的优化方法，如0.618法，用朴素的语言编写成册，用于解决纺织女工查找布匹疵点的最佳时机等实际问题，并亲自下工厂、到农村进行推广，为在那种特殊历史时期提高生产效率起到了很好的效果。但是，由于运筹学在解决经济问题时常常要讲到利润最大、成本最

2 运筹学基础及其 MATLAB 应用成功范例。此外，盟军的反潜艇战运筹研究小组针对德军潜艇的作战研究也卓有成效。他们通过对以往攻击德军潜艇的相关数据的分析，提出了两条重要建议：一是将反潜攻击由潜艇投掷水雷改为飞机投掷深水炸弹；二是将起爆时间改为德军潜艇刚下潜时。事实证明，这样的效果是最佳的。类似成功的例子在第二次世界大战期间还有很多。据统计，在第二次世界大战期间，英国、美国和加拿大等国军队里的运筹学工作人员一度超过了 700 人。这些运筹学工作人员研究的问题还包括战斗机炮弹的合理载荷量问题和如何用一定数量的战斗机封锁给定的海面海域的问题等。第二次世界大战时期军事运筹学的特点表现在：在采集实际数据的基础上，通过多学科的密切协作，用定量化、系统化的方法研究立足现有技术装备如何达到最佳的作战效果。追根溯源，如上所述的思想和方法在古代人们的生活和生产活动中就已经出现。例如，中国古代著名的“田忌赛马”“赵括运粮”“丁谓修宫”等故事，李冰父子主持修建的由“鱼嘴”岷江分洪工程、“飞沙堰”分洪排沙工程和“宝瓶口”引水工程巧妙结合而成的都江堰水利工程，《梦溪笔谈》所记录的军粮供应与用兵进退的关系等事例，无不闪耀着现代所称的运筹学思想，即体现了立足现有技术装备整体优化的朴素思想。进入 20 世纪后，现代运筹学的思想已经在很多方面有所体现，比如 1914 年英国工程师兰彻斯特 (Lanchester) 提出的战斗方程, 1917 年丹麦工程师研究电话通信时提出的排队论的一些著名公式，20 世纪 20 年代初提出的存储论的最优批量公式，以及 20 世纪 30 年代苏联数学家康托洛维奇在解决工业生产组织和计划问题时提出的类似线性规划的模型，等等。由于运筹学主要是采用定量分析手段，研究如何最佳利用现有技术装备问题，以求达到最佳效果，所以第二次世界大战以后在美国等发达国家开始将运筹学的思想和方法运用到工业和经济管理领域，并取得了非常好的效果。到 20 世纪五六十年代，从事运筹学的工作者队伍开始迅速壮大，纷纷成立学会、创办刊物并开始在高校开设运筹学课程。也正是在这段时期，现代运筹学由钱学森、徐国志先生从美国归国时引入中国，并且在两位先生的推动下于 1956 年在中国科学院力学研究所成立了中国第一个运筹学研究小组。1959 年，第二个运筹学研究部门在中国科学院数学研究所成立，这是数学家们投身于国家建设的一个产物。力学所小组与数学所小组于 1960 年合并成为数学研究所的一个研究室，当时的主要研究方向为排队论、非线性规划和图论，还有人专门研究运输理论、动态规划和经济分析 (如投入产出方法)。50 年代后期，运筹学在中国的应用集中在运输问题上，其中一个广为流传且容易明白的例子就是“打麦场的选址问题”。研究该问题的目的在于解决当时在以手工收割为主的情况下如何节省人力、物力。著名的“中国邮递员问题”也是在那个时期由管梅谷教授提出的。特别值得一提的是，华罗庚先生在 “文化大革命”那种特殊历史时期在全国推广的“优选法”。华罗庚先生将一些基本的优化方法，如 0.618 法，用朴素的语言编写成册，用于解决纺织女工查找布匹疵点的最佳时机等实际问题，并亲自下工厂、到农村进行推广，为在那种特殊历史时期提高生产效率起到了很好的效果。但是，由于运筹学在解决经济问题时常常要讲到利润最大、成本最

绪论 3 低等，这些讨论在“文革”期间是禁区。所以，“文化大革命”开始以后，运筹学的研究和教学出现了停滞。到了“文革”结束后的1980年，中国运筹学会作为中国数学学会的一个分支才成立。运筹学的研究和教学开始恢复。1992年，中国运筹学会从中国数学会独立出来成为国家一级学会是学会发展史上的一个重要事件。这说明了运筹学以数学为基础，但同数学学科有本质的不同。运筹学家除了推动运筹学基本理论的发展，还要对社会负起同数学家不同的责任。事实上，国际上几十年来对运筹学发展的讨论一直没有停止过。1994年，美国运筹学会和管理科学学会合并，成立了NFORMS,是国际运筹学界的一件大事。目前，运筹学和管理科学的结合也引起中国运筹学界的极大关注。近年来，中国运筹学工作者坚持运筹学研究与经济建设等重大问题紧密结合取得了很大的成绩。例如，在山东省与大连市经济发展计划的制订，兰州铁路局铁路运输的优化安排，中外合资经营项目的经济评价，若干国家重大工程中的综合风险分析等方面，我国运筹学者都发挥了积极作用。近二十年来，信息科学、生命科学等现代高科技对人类社会产生了巨大影响，运筹学工作者关注到其中一些运筹学起作用的新的工作方向并积极参与其中。例如，运筹学工作者将全局最优化、图论、神经网络等运筹学理论及方法应用于分子生物信息学中的DNA与蛋白质序列比较、芯片测试、生物进化分析、蛋白质结构预测等问题的研究：在金融管理方面，将优化及决策分析方法，应用于金融风险控制与管理、资产评估与定价分析模型等：在网络管理上，利用随机过程方法，研究排队网络的数量指标分析：在供应链管理问题中，利用随机动态规划模型，研究多重决策最优策略的计算方法等。截至目前，几乎所有高校都在应用数学、经济管理以及金融、工程技术学科等各专业开设了运筹学课程。运筹学正以其解决实际问题的独特性受到人们越来越多的研究和应用。运筹学与数学建模运筹学的特点由运筹学的发展简史可见，在解决某个实际问题时，运筹学的主要特点是利用现有的技术、资源，研究如何才能发挥最佳的效果。在这个过程中，往往需要和多个学科进行合作。可以这么说，运筹学是为决策机构在对其控制下的业务活动进行决策时，提供以数量化为基础的科学方法。它强调以量化分析为基础，就必然要用数学语言描述并解决问题。但任何决策都包含定量分析和定性分析两个方面，而定性分析又不能简单地用数学语言加以描述，如政治、民族、人们的心理等，只有综合多种因素的决策才是全面的。运筹学工作者的职责是为决策者提供量化分析的结果，并指出定性的因素。运筹学的另一个定义是：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优策略提供定量依据。这个定义表明运筹学具有

绪论 3 低等，这些讨论在“文革”期间是禁区。所以，“文化大革命”开始以后，运筹学的研究和教学出现了停滞。到了“文革”结束后的 1980 年，中国运筹学会作为中国数学学会的一个分支才成立。运筹学的研究和教学开始恢复。1992 年，中国运筹学会从中国数学会独立出来成为国家一级学会是学会发展史上的一个重要事件。这说明了运筹学以数学为基础，但同数学学科有本质的不同。运筹学家除了推动运筹学基本理论的发展，还要对社会负起同数学家不同的责任。事实上，国际上几十年来对运筹学发展的讨论一直没有停止过。1994 年，美国运筹学会和管理科学学会合并，成立了 INFORMS，是国际运筹学界的一件大事。目前，运筹学和管理科学的结合也引起中国运筹学界的极大关注。近年来，中国运筹学工作者坚持运筹学研究与经济建设等重大问题紧密结合取得了很大的成绩。例如，在山东省与大连市经济发展计划的制订，兰州铁路局铁路运输的优化安排，中外合资经营项目的经济评价，若干国家重大工程中的综合风险分析等方面，我国运筹学者都发挥了积极作用。近二十年来，信息科学、生命科学等现代高科技对人类社会产生了巨大影响，运筹学工作者关注到其中一些运筹学起作用的新的工作方向并积极参与其中。例如，运筹学工作者将全局最优化、图论、神经网络等运筹学理论及方法应用于分子生物信息学中的 DNA 与蛋白质序列比较、芯片测试、生物进化分析、蛋白质结构预测等问题的研究；在金融管理方面，将优化及决策分析方法，应用于金融风险控制与管理、资产评估与定价分析模型等；在网络管理上，利用随机过程方法，研究排队网络的数量指标分析；在供应链管理问题中，利用随机动态规划模型，研究多重决策最优策略的计算方法等。截至目前，几乎所有高校都在应用数学、经济管理以及金融、工程技术学科等各专业开设了运筹学课程。运筹学正以其解决实际问题的独特性受到人们越来越多的研究和应用。运筹学与数学建模运筹学的特点由运筹学的发展简史可见，在解决某个实际问题时，运筹学的主要特点是利用现有的技术、资源，研究如何才能发挥最佳的效果。在这个过程中，往往需要和多个学科进行合作。可以这么说，运筹学是为决策机构在对其控制下的业务活动进行决策时，提供以数量化为基础的科学方法。它强调以量化分析为基础，就必然要用数学语言描述并解决问题。但任何决策都包含定量分析和定性分析两个方面，而定性分析又不能简单地用数学语言加以描述，如政治、民族、人们的心理等，只有综合多种因素的决策才是全面的。运筹学工作者的职责是为决策者提供量化分析的结果，并指出定性的因素。运筹学的另一个定义是：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优策略提供定量依据。这个定义表明运筹学具有

运筹学基础及其MATLAB应用多学科交叉的特点。在解决实际问题时，由于成本以及各种条件的限制，对于运筹学理论上提出的最优，往往无法达到，这时可用次优、满意解来代替。因此也可以说，运筹学为最好的解决实际问题提供一种量化依据，如果不按照运筹学给出的方案进行，则结果可能更糟糕。运筹学与数学模型前面提到，用运筹学解决实际问题必须用数学的语言描述该问题。这种用数学语言描述问题的过程就是建立某个实际问题的数学模型。所谓模型是指，为了一定的目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物。按照描述的方式划分，模型可以分为形象模型、模拟模型以及符号或数学模型。比如，房地产开发商将其开发的房地产用沙盘方式呈现出来就是形象模型，用计算机模拟核武器爆炸以后的效果就是模拟模型。而数学模型则是将拟解决的问题所牵涉的决策变量之间的关系按照物理的、化学的、经济的等规律所必须满足的条件用数学式子写出来，并用相关数学式子将要解决的目标也表示出来的一种描述问题的方式。建立一个问题的数学模型并不是全新的概念。实际上，从小学开始的数学课上解应用题就是简单地建立数学模型并求解的过程。比如，有两艘船相距200km,甲船以20km/h的速度自东向西行驶，同时乙船以30km/h的速度自西向东行驶，问两船经过几小时相遇？这是一个典型的小学数学应用题。我们现在这样重新描述，问题问的是两船经过几小时相遇，这个时间是要我们回答的，是不知道的。因此可以假设两船经过h航行会相遇，根据简单的物理学规律以及题目的假设，显然有：20t+30t=200。这个式子就是我们所说的数学模型（答案当然很简单，即t=4h), 因为这个式子描述了原问题。这个模型虽然简单，但仔细思考，仍然有些建立数学模型的特点。首先，我们在列出上述式子时有意无意地忽略了某些条件。比如，我们在这里实际上假设两船在航行过程中不受诸如海浪、风向等外在因素的影响，并且假设两船一定是在一条直线上相向而行。实际上，建立任何一个问题的数学模型时都必须作出一些假设，有时，一个数学模型的好坏与假设是否合理、得当有很大关系。其次，我们利用了物理学上速度、时间和距离的关系以及题目本身给出的条件，即两船相距200km以及甲、乙两船的速度。这说明，建立数学模型必须根据问题给出的条件，并利用物理的、化学的、经济的、金融的等相关领域的规律才能将决策变量满足的条件或目标表示出来。数学模型可以分为很多种，如初等数学模型、高等数学模型，离散模型、连续模型，确定性模型、随机模型，微分方程模型、差分方程模型，统计回归模型、优化模型，等等。从所使用的数学工具的角度来讨论建立数学模型，则可以说几乎用到了数学的所有分支。由于运筹学的特点，在这门课程里讨论的数学模型都是优化模型。如何建立一个问题的优化模型（运筹学模型）是学习这门课程的一个非常重要的任务。但是，建立一个复杂问题的运筹学模型并不是一件简单的事情。实际上，有人认为建立一个好的数学模型（包括运筹学模型）是一门艺术。这是指，建立数学模型并不能简单地根据某个定理就

4 运筹学基础及其 MATLAB 应用多学科交叉的特点。在解决实际问题时，由于成本以及各种条件的限制，对于运筹学理论上提出的最优，往往无法达到，这时可用次优、满意解来代替。因此也可以说，运筹学为最好的解决实际问题提供一种量化依据，如果不按照运筹学给出的方案进行，则结果可能更糟糕。运筹学与数学模型前面提到，用运筹学解决实际问题必须用数学的语言描述该问题。这种用数学语言描述问题的过程就是建立某个实际问题的数学模型。所谓模型是指，为了一定的目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物。按照描述的方式划分，模型可以分为形象模型、模拟模型以及符号或数学模型。比如，房地产开发商将其开发的房地产用沙盘方式呈现出来就是形象模型，用计算机模拟核武器爆炸以后的效果就是模拟模型。而数学模型则是将拟解决的问题所牵涉的决策变量之间的关系按照物理的、化学的、经济的等规律所必须满足的条件用数学式子写出来，并用相关数学式子将要解决的目标也表示出来的一种描述问题的方式。建立一个问题的数学模型并不是全新的概念。实际上，从小学开始的数学课上解应用题就是简单地建立数学模型并求解的过程。比如，有两艘船相距 200km，甲船以 20 km/h 的速度自东向西行驶，同时乙船以 30km/h 的速度自西向东行驶，问两船经过几小时相遇？这是一个典型的小学数学应用题。我们现在这样重新描述，问题问的是两船经过几小时相遇，这个时间是要我们回答的，是不知道的。因此可以假设两船经过 th 航行会相遇，根据简单的物理学规律以及题目的假设，显然有：20t + 30t = 200。这个式子就是我们所说的数学模型 (答案当然很简单，即 t = 4h)，因为这个式子描述了原问题。这个模型虽然简单，但仔细思考，仍然有些建立数学模型的特点。首先，我们在列出上述式子时有意无意地忽略了某些条件。比如，我们在这里实际上假设两船在航行过程中不受诸如海浪、风向等外在因素的影响，并且假设两船一定是在一条直线上相向而行。实际上，建立任何一个问题的数学模型时都必须作出一些假设，有时，一个数学模型的好坏与假设是否合理、得当有很大关系。其次，我们利用了物理学上速度、时间和距离的关系以及题目本身给出的条件，即两船相距 200km 以及甲、乙两船的速度。这说明，建立数学模型必须根据问题给出的条件，并利用物理的、化学的、经济的、金融的等相关领域的规律才能将决策变量满足的条件或目标表示出来。数学模型可以分为很多种，如初等数学模型、高等数学模型，离散模型、连续模型，确定性模型、随机模型，微分方程模型、差分方程模型，统计回归模型、优化模型，等等。从所使用的数学工具的角度来讨论建立数学模型，则可以说几乎用到了数学的所有分支。由于运筹学的特点，在这门课程里讨论的数学模型都是优化模型。如何建立一个问题的优化模型 (运筹学模型) 是学习这门课程的一个非常重要的任务。但是，建立一个复杂问题的运筹学模型并不是一件简单的事情。实际上，有人认为建立一个好的数学模型 (包括运筹学模型) 是一门艺术。这是指，建立数学模型并不能简单地根据某个定理就

绪论 5 能立即写出来，而是需要利用问题的假设和相关规律进行反复思考、讨论，进行创造性的工作。当然，任何事情都有一个开始和训练。在运筹学这门课程里，我们除了学习一些运筹学的分支及其相关理论外，有意识地注意数学建模是一项非常重要的任务。虽然建立某个问题的数学模型没有一个统一的模式，但从以下几个方面进行思考是有益的： (1)仔细考虑（阅读）问题的已知和未知条件，反复讨论，找出问题要解决的目标。需要解答者回答的问题往往就是决策变量，用适当的符号表示决策变量。 (2)经过讨论，作出适当与合理的假设。所谓适当与合理的假设主要与该问题所属学科领域的知识有关。 (③)从问题的最后入手，讨论决策变量之间以及与某些公认的或己知的规律或某种量之间的联系，并将这些关系表示出来。 (4)将问题需要回答的目标表达出来。能做到从以上几个方面思考问题，对于学习运筹学来说是足够了，但要提高建立数学模型的能力却不是一朝一夕的事情，只有长期坚持建模训练才有可能建立一个好的数学模型，用于解决复杂的实际问题。算法假设我们针对某个问题建立了数学模型，那么接下来的任务就是求解这个模型。求解数学模型，当然要用到相关的数学理论，从求解的方式来看，不外乎有两种方式：公式的或解析的求解方式以及根据某种算法进行求解。前面一种方式不用讨论，我们着重讨论第二种方式。由于问题本身的结构，很多问题没办法用公式求解。这时，人们往往会根据问题的特点和相关理论提出解决这个问题的一些步骤。即，首先应该怎么做，其次又应该怎么做，在什么情况下应该怎么做，在什么情况应该终止等等。这些解决某个问题的步骤就是算法。作为一个算法应该满足一般性和有限终止性。即只要是同类型的问题就应该能够按照相同的算法得出结果并且一定要在有限次运算后终止（收敛）。除此以外，还需要考虑算法的运算效率，即收敛速度。运筹学模型几乎都是根据某种算法进行求解的。因此，适当了解与算法密切相关的计算复杂性是有必要的。下面对此做一个简单的介绍。所谓问题是指一个抽象的模型或概念，它通过一些具体的数据表现出来。问题是需要回答的一般性提问，通常含有若干个满足已定条件的参数。问题通过描述所有参数的特性和描述答案所满足的条件给定。当问题中的参数赋予了具体值的时候，就称为问题的一个实例(Instance)。一个问题通过它的所有实例表现。算法常常是针对一个问题来设计的，它可以求解任何一个该问题的实例。比如，线性规划问题是指：

绪论 5 能立即写出来，而是需要利用问题的假设和相关规律进行反复思考、讨论，进行创造性的工作。当然，任何事情都有一个开始和训练。在运筹学这门课程里，我们除了学习一些运筹学的分支及其相关理论外，有意识地注意数学建模是一项非常重要的任务。虽然建立某个问题的数学模型没有一个统一的模式，但从以下几个方面进行思考是有益的： (1) 仔细考虑 (阅读) 问题的已知和未知条件，反复讨论，找出问题要解决的目标。需要解答者回答的问题往往就是决策变量，用适当的符号表示决策变量。 (2) 经过讨论，作出适当与合理的假设。所谓适当与合理的假设主要与该问题所属学科领域的知识有关。 (3) 从问题的最后入手，讨论决策变量之间以及与某些公认的或已知的规律或某种量之间的联系，并将这些关系表示出来。 (4) 将问题需要回答的目标表达出来。能做到从以上几个方面思考问题，对于学习运筹学来说是足够了，但要提高建立数学模型的能力却不是一朝一夕的事情，只有长期坚持建模训练才有可能建立一个好的数学模型，用于解决复杂的实际问题。算法假设我们针对某个问题建立了数学模型，那么接下来的任务就是求解这个模型。求解数学模型，当然要用到相关的数学理论，从求解的方式来看，不外乎有两种方式：公式的或解析的求解方式以及根据某种算法进行求解。前面一种方式不用讨论，我们着重讨论第二种方式。由于问题本身的结构，很多问题没办法用公式求解。这时，人们往往会根据问题的特点和相关理论提出解决这个问题的一些步骤。即，首先应该怎么做，其次又应该怎么做，在什么情况下应该怎么做，在什么情况应该终止等等。这些解决某个问题的步骤就是算法。作为一个算法应该满足一般性和有限终止性。即只要是同类型的问题就应该能够按照相同的算法得出结果并且一定要在有限次运算后终止 (收敛)。除此以外，还需要考虑算法的运算效率，即收敛速度。运筹学模型几乎都是根据某种算法进行求解的。因此，适当了解与算法密切相关的计算复杂性是有必要的。下面对此做一个简单的介绍。所谓问题是指一个抽象的模型或概念，它通过一些具体的数据表现出来。问题是需要回答的一般性提问，通常含有若干个满足已定条件的参数。问题通过描述所有参数的特性和描述答案所满足的条件给定。当问题中的参数赋予了具体值的时候，就称为问题的一个实例 (Instance)。一个问题通过它的所有实例表现。算法常常是针对一个问题来设计的，它可以求解任何一个该问题的实例。比如，线性规划问题是指：

6 运筹学基础及其MATLAB应用 max(min)z=cTX s.t. AX=6 X≥0 这里，X∈R”称为决策向量，c∈R”称为价值系数向量，A∈Rmm称为技术系数矩阵，b∈Rm称为资源系数向量。A,b,c就是描述该问题的参数，当这些矩阵、向量给定具体值后，就对应一个实例。通过一个称为检验数（后面将会详述）的概念对其解进行描述。后面我们将会了解到单纯形法可以求解该问题。并且只要是如上形式的问题，不论 A,b,c是怎样的，通过单纯形法都可以得出有解（唯一解、无穷多组解、无界解）或无解的最终结果。衡量一个算法的好坏有时可以用计算机所耗费的cpu时间来判断，但是，计算机软硬件都在不断变化和提高，所以通常是用算法中的加、减、乘、除和比较等基本运算的总次数同实例在计算机计算时的二进制输入数据的大小关系来度量的。在这里我们不打算进行详细地讨论，我们只是粗略地指出，一个求解实例I的算法的基本计算总次数C() 同实例I的计算机二进制输入长度d()的关系如果能用一个多项式函数进行控制的话，我们就称该算法是求解该问题的一个多项式时间算法。这样的算法我们认为是有效的或者说是好的算法。与此相对的就是所谓指数时间算法，这样的算法我们认为是效率不高的或者说是不好的算法。一个问题如果存在至少一个多项式时间算法，则称为多项式问题，所有多项式问题集记为P(Polynomial)。对于上面提到的线性规划问题，可以证明，单纯形法不是一个多项式时间算法，但这并不能说明线性规划问题不属于多项式问题。Khachian在l979年成功构造了椭球算法并证明了其算法是线性规划问题的多项式时间算法。因此，线性规划问题属于P。并非所有（优化）问题都找到了多项式时间算法，也就是说，还不能肯定某些优化问题是否属于P。我们把迄今为止还没有找到多项式时间算法的最优化问题归为所谓的NP-hard。受人类认识能力的限制，目前人们只能假设这一类难解的最优化问题不存在多项式时间算法。比如，我们将在后面学习的整数规划问题，0-1规划问题即属于此类问题。但是，非多项式时间算法在实际计算中的表现不一定就不好。比如单纯形法，理论上不是多项式时间算法，但其求解实际问题的效果，特别是对于中小规模的线性规划问题而言，其效果往往好于别的算法（如内点算法）。因此，单纯形法以及割平面法、隐枚举法等算法仍然值得我们学习。应用运筹学解决问题运筹学的特点之一是多学科合作。所以，运用运筹学解决实际问题首先需要与问题所属学科领域的专业人士进行合作，深入了解问题的真正含义，搞清问题真正需要解决的目标。其次，在研究问题时要互相引导，改变一些对问题的常规看法。除了强调合作以

6 运筹学基础及其 MATLAB 应用 max(min) z = c TX s.t. AX = b X > 0 这里，X ∈ R n 称为决策向量，c ∈ R n 称为价值系数向量，A ∈ R m·n 称为技术系数矩阵，b ∈ R m 称为资源系数向量。A, b, c 就是描述该问题的参数，当这些矩阵、向量给定具体值后，就对应一个实例。通过一个称为检验数 (后面将会详述) 的概念对其解进行描述。后面我们将会了解到单纯形法可以求解该问题。并且只要是如上形式的问题，不论 A, b, c 是怎样的，通过单纯形法都可以得出有解 (唯一解、无穷多组解、无界解) 或无解的最终结果。衡量一个算法的好坏有时可以用计算机所耗费的 cpu 时间来判断，但是，计算机软硬件都在不断变化和提高，所以通常是用算法中的加、减、乘、除和比较等基本运算的总次数同实例在计算机计算时的二进制输入数据的大小关系来度量的。在这里我们不打算进行详细地讨论，我们只是粗略地指出，一个求解实例 I 的算法的基本计算总次数 C(I) 同实例 I 的计算机二进制输入长度 d(I) 的关系如果能用一个多项式函数进行控制的话，我们就称该算法是求解该问题的一个多项式时间算法。这样的算法我们认为是有效的或者说是好的算法。与此相对的就是所谓指数时间算法，这样的算法我们认为是效率不高的或者说是不好的算法。一个问题如果存在至少一个多项式时间算法，则称为多项式问题，所有多项式问题集记为 P(Polynomial)。对于上面提到的线性规划问题，可以证明，单纯形法不是一个多项式时间算法，但这并不能说明线性规划问题不属于多项式问题。Khachian 在 1979 年成功构造了椭球算法并证明了其算法是线性规划问题的多项式时间算法。因此，线性规划问题属于 P。并非所有 (优化) 问题都找到了多项式时间算法，也就是说，还不能肯定某些优化问题是否属于 P。我们把迄今为止还没有找到多项式时间算法的最优化问题归为所谓的 NP-hard。受人类认识能力的限制，目前人们只能假设这一类难解的最优化问题不存在多项式时间算法。比如，我们将在后面学习的整数规划问题，0-1 规划问题即属于此类问题。但是，非多项式时间算法在实际计算中的表现不一定就不好。比如单纯形法，理论上不是多项式时间算法，但其求解实际问题的效果，特别是对于中小规模的线性规划问题而言，其效果往往好于别的算法 (如内点算法)。因此，单纯形法以及割平面法、隐枚举法等算法仍然值得我们学习。应用运筹学解决问题运筹学的特点之一是多学科合作。所以，运用运筹学解决实际问题首先需要与问题所属学科领域的专业人士进行合作，深入了解问题的真正含义，搞清问题真正需要解决的目标。其次，在研究问题时要互相引导，改变一些对问题的常规看法。除了强调合作以

绪论外，在研究问题时也需要独立进行，要思路开阔。具体来说，应用运筹学解决问题主要有如下一些步骤： (1)分析问题。首先针对问题做调查研究。这里指的是针对问题提供的己知、未知，做定性研究，讨论问题的属性。要搞清楚问题所属的学科领域，并反复讨论问题需要解答者回答什么。这个说法看似容易，但对比较复杂的问题可能需要解答者反复思考才可能真正清楚问题所在。 (2)构造或选择模型。在清楚决策变量并用适当符号表示以后，针对问题可以选用适当的、己知的模型，也可能需要解答者自己构造模型。所谓构造模型是指，根据相关学科领域的知识和问题的要求，客观地写出决策变量之间必须满足的关系。在此，需要特别强调的是，在构造模型或选择模型以前，必须作出适当的、合理的假设。 (3)模型的求解和检验。模型建立以后，应该根据相关理论对此模型进行求解。对于运筹学模型而言，几乎都是根据相关算法通过计算机求解。在此，需要注意问题的规模和计算复杂性问题。对于某些大型的运筹学模型，如果属于NP-hard的，可能还需要采用某些启发式算法进行求解。在求解过程中必然有检验的问题，这与算法有关。 (④)解的实施和控制。应用运筹学解决问题的根本就是为决策者作出科学决策提供定量依据。因此，得到模型的解以后就需要具体实施。若在实施过程中发现与预期的、理论的或实际的表现不符，则需要回到第一步重新开始。另外，由于任何数学模型都有局限性，所以在可能的情况下作灵敏度分析，即确定最优解保持稳定的参数变化范围也是非常重要的。 (⑤)模型的总结和反馈。最后，针对建立的运筹学模型作出总结，讨论是否可以进一步改善模型。在应用运筹学解决一个复杂的实际问题时，构造或选择模型是最重要的一步。为获得一个好的模型，可能需要重复上述步骤，反复讨论才能成功，从而较好地解决问题。关于本书从应用数学的角度来看，运筹学是一门应用性很强的学科。从管理等学科的角度来看，运筹学又是一门数学味道很浓的学科。因此，学习运筹学不仅要学会相关的数学理论，更要注意建立数学模型解决实际问题。同时，对于处在计算机时代的人来说，必须要学会利用计算机解决运筹学模型。我们在前言己经说过，可以选用一些现成的计算机软件来解决运筹学问题，但编者考虑到MATLAB的重要性和广泛性，本书是基于MATLAB 来进行相关讨论的。几乎对于每个算法我们都编写了相关的程序并附在每章的适当位置。编者也认为掌握相关算法的手工计算也是很有必要的。因为这会有助于学习者真正理解和掌握相关的算法。因此传统的手工计算我们并没有放弃。另外，本书在选材时是从运筹学模型的数学特点进行划分的。即分成线性模型、非线性模型和随机模型三种

绪论 7 外，在研究问题时也需要独立进行，要思路开阔。具体来说，应用运筹学解决问题主要有如下一些步骤： (1) 分析问题。首先针对问题做调查研究。这里指的是针对问题提供的已知、未知，做定性研究，讨论问题的属性。要搞清楚问题所属的学科领域，并反复讨论问题需要解答者回答什么。这个说法看似容易，但对比较复杂的问题可能需要解答者反复思考才可能真正清楚问题所在。 (2) 构造或选择模型。在清楚决策变量并用适当符号表示以后，针对问题可以选用适当的、已知的模型，也可能需要解答者自己构造模型。所谓构造模型是指，根据相关学科领域的知识和问题的要求，客观地写出决策变量之间必须满足的关系。在此，需要特别强调的是，在构造模型或选择模型以前，必须作出适当的、合理的假设。 (3) 模型的求解和检验。模型建立以后，应该根据相关理论对此模型进行求解。对于运筹学模型而言，几乎都是根据相关算法通过计算机求解。在此，需要注意问题的规模和计算复杂性问题。对于某些大型的运筹学模型，如果属于 NP-hard 的，可能还需要采用某些启发式算法进行求解。在求解过程中必然有检验的问题，这与算法有关。 (4) 解的实施和控制。应用运筹学解决问题的根本就是为决策者作出科学决策提供定量依据。因此，得到模型的解以后就需要具体实施。若在实施过程中发现与预期的、理论的或实际的表现不符，则需要回到第一步重新开始。另外，由于任何数学模型都有局限性，所以在可能的情况下作灵敏度分析，即确定最优解保持稳定的参数变化范围也是非常重要的。 (5) 模型的总结和反馈。最后，针对建立的运筹学模型作出总结，讨论是否可以进一步改善模型。在应用运筹学解决一个复杂的实际问题时，构造或选择模型是最重要的一步。为获得一个好的模型，可能需要重复上述步骤，反复讨论才能成功，从而较好地解决问题。关于本书从应用数学的角度来看，运筹学是一门应用性很强的学科。从管理等学科的角度来看，运筹学又是一门数学味道很浓的学科。因此，学习运筹学不仅要学会相关的数学理论，更要注意建立数学模型解决实际问题。同时，对于处在计算机时代的人来说，必须要学会利用计算机解决运筹学模型。我们在前言已经说过，可以选用一些现成的计算机软件来解决运筹学问题，但编者考虑到 MATLAB 的重要性和广泛性，本书是基于 MATLAB 来进行相关讨论的。几乎对于每个算法我们都编写了相关的程序并附在每章的适当位置。编者也认为掌握相关算法的手工计算也是很有必要的。因为这会有助于学习者真正理解和掌握相关的算法。因此传统的手工计算我们并没有放弃。另外，本书在选材时是从运筹学模型的数学特点进行划分的。即分成线性模型、非线性模型和随机模型三种

第1章线性规划及单纯形法 9 法。 1.1.1线性规划问题的提出线性规划是指求解一组决策变量，该组决策变量在满足一些线性约束条件的基础上，使得某个线性函数的值达到最大或最小。下面通过两个例子加以说明。么模型引入1.1（生产安排问题）某工厂生产甲、乙两种产品，而生产这两种产品需要用到原材料A和原材料B。该厂可以利用的原材料A有16kg,原材料B有12kg。生产一个单位甲产品需要消耗2kg原材料A和4g原材料B,生产一个单位乙产品需要消耗 3kg原材料A和1kg原材料B。经过测算，一个单位的甲产品可以获得6元的利润，一个单位的乙产品可以获得7元的利润。问：该厂应如何安排生产才能获得最大利润？解这个问题问的是如何安排生产才能获得最大利润。什么叫安排生产呢？在这个简化的题目中，所谓安排生产当然指的是生产甲、乙两种产品各多少个单位。所以，这是我们要回答的不知道的量。设生产甲、乙两种产品各为x1和x2个单位，于是按照题目的假设，该厂此时可以获利z=61+7红2。生产不能是随意的，在这里，生产所耗费的原料当然不能超过该厂的拥有量。于是，生产必须在如下约束下进行： 2x1+3x2≤16（原料A的限制） 4x1+x2≤12（原料B的限制）此外，x1,x2是甲、乙产品的计划生产量，所以有x1≥0，x2≥0。用max表示maximize(即最大)，用subject to或such that表示受约束（其缩写为s.t.),于是可以将上面的分析表示为： max z=6x1+7x2 s.t. 2x1+3x2≤16 (1-1-1) 4红1+x2≤12 D1,x2≥0 这就是该问题的数学模型。它将原问题用数学的语言完全表达出来了。么模型引入1.2（最佳下料问题）某汽车制造过程中需要用到1.5m、1m、0.7m的钢轴各一根。用于制造这些钢轴的原料是4m长的圆钢。现在要制造1000辆汽车，问最少需要多少根圆钢。解由于3种规格的钢轴长度之和为3.2m,一个自然的做法是在一根圆钢上截取就可以完成该项任务。但是，这样做将会出现0.8m的料头。制造1000辆汽车将会出现 800m的料头，如果这些料头不能作其他用途，则相当于浪费了200根原材料。那么，有没有什么办法能减少浪费呢？仔细阅读题目不难发现，需要的是1.5m、1m、0.7m的钢轴各一根，并没有要求这些钢轴来自于同一根圆钢。也就是说，只要获得1.5m、1m、0.7m

第 1 章线性规划及单纯形法 9 法。 1.1.1 线性规划问题的提出线性规划是指求解一组决策变量，该组决策变量在满足一些线性约束条件的基础上，使得某个线性函数的值达到最大或最小。下面通过两个例子加以说明。模型引入 1.1 (生产安排问题) 某工厂生产甲、乙两种产品，而生产这两种产品需要用到原材料 A 和原材料 B。该厂可以利用的原材料 A 有 16kg，原材料 B 有 12kg。生产一个单位甲产品需要消耗 2kg 原材料 A 和 4kg 原材料 B，生产一个单位乙产品需要消耗 3kg 原材料 A 和 1kg 原材料 B。经过测算，一个单位的甲产品可以获得 6 元的利润，一个单位的乙产品可以获得 7 元的利润。问：该厂应如何安排生产才能获得最大利润？解这个问题问的是如何安排生产才能获得最大利润。什么叫安排生产呢？在这个简化的题目中，所谓安排生产当然指的是生产甲、乙两种产品各多少个单位。所以，这是我们要回答的不知道的量。设生产甲、乙两种产品各为 x1 和 x2 个单位，于是按照题目的假设，该厂此时可以获利 z = 6x1 + 7x2。生产不能是随意的，在这里，生产所耗费的原料当然不能超过该厂的拥有量。于是，生产必须在如下约束下进行： 2x1 + 3x2 616 (原料 A 的限制) 4x1 + x2 612 (原料 B 的限制) 此外，x1, x2 是甲、乙产品的计划生产量，所以有 x1 > 0, x2 > 0。用 max 表示 maximize(即最大)，用 subject to 或 such that 表示受约束 (其缩写为 s.t.)，于是可以将上面的分析表示为： max z = 6x1 + 7x2 s.t.    2x1 + 3x2 6 16 4x1 + x2 6 12 x1, x2 > 0 (1-1-1) 这就是该问题的数学模型。它将原问题用数学的语言完全表达出来了。模型引入 1.2 (最佳下料问题) 某汽车制造过程中需要用到 1.5m、1m、0.7m 的钢轴各一根。用于制造这些钢轴的原料是 4m 长的圆钢。现在要制造 1000 辆汽车，问最少需要多少根圆钢。解由于 3 种规格的钢轴长度之和为 3.2m，一个自然的做法是在一根圆钢上截取就可以完成该项任务。但是，这样做将会出现 0.8m 的料头。制造 1000 辆汽车将会出现 800m 的料头，如果这些料头不能作其他用途，则相当于浪费了 200 根原材料。那么，有没有什么办法能减少浪费呢？仔细阅读题目不难发现，需要的是 1.5m、1m、0.7m 的钢轴各一根，并没有要求这些钢轴来自于同一根圆钢。也就是说，只要获得 1.5m、1m、0.7m

《运筹学》课程教学资源（电子教材）绪论、第1章 线性规划及单纯形法

《运筹学》课程教学资源（电子教材）绪论、第1章线性规划及单纯形法