绪 论 学习目标与要求 1.了解运筹学发展简史。 2.了解运筹学的特点以及数学模型的有关概念。 3.了解运筹学的工作步骤以及算法的有关概念。 运筹学发展简史 运筹学(Operations Research或Operational Research,OR)作为现代意义下的一门 独立的学科，一般认为起源于第二次世界大战。第二次世界大战早期，德国空军对英国 本土的轰炸对英国造成了极大的破坏。虽然当时已经出现了雷达，但由于有来自不同雷 达站的信息以及雷达站同整个防空系统的配合不够好，英国本土仍然遭受了德国空军对 其轰炸的重创。当时，Bawdsey雷达站的负责人A.P.Rowe提出在现有技术装备情况下对 整个防空作战系统的运行进行研究。为保密的需要，他们将这项研究称为“Operational Rresearch”(运用研究)。研究小组是一支综合的队伍，包括数学家、物理学家甚至还有心 理学家等。由于其成员构成的复杂性，人们称之为“布莱克特马戏团”。他们研究的具体 问题有设计将雷达信息传送给指挥系统及武器系统的最佳方式和雷达与防空武器的最佳 配置等。他们的研究成果极大地提高了英国本土的防空能力。他们的研究工作主要是考 虑立足当时己有的技术装备，如何进行不同的配置使其发挥最大的功效。按照后来被称 为运筹学的主要思想，这些研究不仅是现代运筹学的发端，也是运筹学解决实际问题的
运筹学发展简史 运筹学 (Operations Research 或 Operational Research, OR) 作为现代意义下的一门 独立的学科，一般认为起源于第二次世界大战。第二次世界大战早期，德国空军对英国 本土的轰炸对英国造成了极大的破坏。虽然当时已经出现了雷达，但由于有来自不同雷 达站的信息以及雷达站同整个防空系统的配合不够好，英国本土仍然遭受了德国空军对 其轰炸的重创。当时，Bawdsey 雷达站的负责人 A.P.Rowe 提出在现有技术装备情况下对 整个防空作战系统的运行进行研究。为保密的需要，他们将这项研究称为“Operational Rresearch”(运用研究)。研究小组是一支综合的队伍，包括数学家、物理学家甚至还有心 理学家等。由于其成员构成的复杂性，人们称之为“布莱克特马戏团”。他们研究的具体 问题有设计将雷达信息传送给指挥系统及武器系统的最佳方式和雷达与防空武器的最佳 配置等。他们的研究成果极大地提高了英国本土的防空能力。他们的研究工作主要是考 虑立足当时已有的技术装备，如何进行不同的配置使其发挥最大的功效。按照后来被称 为运筹学的主要思想，这些研究不仅是现代运筹学的发端，也是运筹学解决实际问题的
运筹学基础及其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)。一个问题通过它 的所有实例表现。算法常常是针对一个问题来设计的，它可以求解任何一个该问题的实 例。比如，线性规划问题是指：