绪 论 学习目标与要求 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)。一个问题通过它 的所有实例表现。算法常常是针对一个问题来设计的，它可以求解任何一个该问题的实 例。比如，线性规划问题是指：
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 来进行相关讨论的。几乎对于每个算法我们都编写了相关的程序并附在每章的适当位置。 编者也认为掌握相关算法的手工计算也是很有必要的。因为这会有助于学习者真正理解 和掌握相关的算法。因此传统的手工计算我们并没有放弃。另外，本书在选材时是从运 筹学模型的数学特点进行划分的。即分成线性模型、非线性模型和随机模型三种
NHAPTER 1 第1章 线性规划及单纯形法 学习目标与要求 1.掌握线性规划的有关概念，会化非标准型线性规划为标准型线性规划。 2.初步建立数学模型的概念。 3.掌握求解线性规划的单纯形法并会用MATLAB求解线性规划问题。 1.1线性规划问题及其标准型 线性规划(Linear Programming,LP)是运筹学中一个基础而重要的分支。很多其他 运筹学问题的求解都以线性规划问题为基础。线性规划开创性的工作可以追溯到1939年 苏联数学家、经济学家康托洛维奇(L.V.Kantorovich,1912-1986)的著作《生产组织 和计划中的数学方法》。他把资源最优利用这一传统的经济学问题，由定性研究和一般 的定量分析推进到现实计量阶段，对于在企业范围内如何科学地组织生产和在国民经济 范围内怎样最优地利用资源等问题做出了独创性的研究。此外，美国经济学家库普曼斯 (T.C.Koopmans)和美国数学家丹兹格(G.B.Dantzig)在线性规划的发展历史中也作 出了开创性的卓越贡献。前者在第二次世界大战期间重新独立地研究了运输问题，后者 则发明了20世纪最伟大的算法之一，即用于求解线性规划问题的单纯形法。从理论上来 说，单纯形法不是多项式时间算法，而后来出现的椭球算法和内点算法才是求解线性规 划问题的多项式时间算法，但在实际计算中，特别是对中小规模的线性规划问题，单纯形 法的表现仍然很好。因此，对于现在学习运筹学的人来说，单纯形法仍然是必须掌握的算
1.1 线性规划问题及其标准型 线性规划 (Linear Programming, LP) 是运筹学中一个基础而重要的分支。很多其他 运筹学问题的求解都以线性规划问题为基础。线性规划开创性的工作可以追溯到 1939 年 苏联数学家、经济学家康托洛维奇 (L. V. Kantorovich, 1912—1986) 的著作《生产组织 和计划中的数学方法》。他把资源最优利用这一传统的经济学问题，由定性研究和一般 的定量分析推进到现实计量阶段，对于在企业范围内如何科学地组织生产和在国民经济 范围内怎样最优地利用资源等问题做出了独创性的研究。此外，美国经济学家库普曼斯 (T. C. Koopmans) 和美国数学家丹兹格 (G. B. Dantzig) 在线性规划的发展历史中也作 出了开创性的卓越贡献。前者在第二次世界大战期间重新独立地研究了运输问题，后者 则发明了 20 世纪最伟大的算法之一，即用于求解线性规划问题的单纯形法。从理论上来 说，单纯形法不是多项式时间算法，而后来出现的椭球算法和内点算法才是求解线性规 划问题的多项式时间算法，但在实际计算中，特别是对中小规模的线性规划问题，单纯形 法的表现仍然很好。因此，对于现在学习运筹学的人来说，单纯形法仍然是必须掌握的算
第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
10 运筹学基础及其MATLAB应用 的钢轴各1000根就行了。于是，可以按照这样的思路来考虑：假设在圆钢上的切口厚度 忽略不计，那么，若在一根圆钢上截取2根1.5m、1根1m的钢轴，则没有任何余料，若 在一根圆钢上截取2根1.5m、1根0.7m的钢轴，则只有0.3m的余料把这些方案列 举出来（见表1-1）。只要余料小于0.8m,那么都是比原始想法好的截取方案。这样，通过 各种截取方案获得的1.5m、1m和0.7m的钢轴只要都有1000根，这项任务就完成了。这 样做的目的当然是让产生的余料之和达到最小。于是，可以设x,(亿=1,2，·，10)表示采 用第i种方案时圆钢的数目，则将得到规格为1.5m,1m和0.7m的钢轴分别为： 2x1+2x2+E3+x4+工5 (1.5m钢轴) x1+2x3+I4+4x6+3x7+2x8+xg (1m钢轴) x2+2x4+3x5+x7+2z8+4xg+5x10(0.7m钢轴) 表1-1优于原始方案的下料方案 方案 1 2 3 4 5 67 8 9 10 需求量 钢轴规格/根 1.5m 2 2 1 100000 1000 1m 0 2 1 0 43210 1000 0.7m 0 1 0 2 3 0 1 5 1000 余料/m 00.30.50.10.400.30.60.20.51000 按照这样的做法，将会产生的余料表达式为： 0.3z2+0.5x3+0.1x4+0.4r5+0.3x7+0.6z8+0.2xg+0.5z10 于是，得到该问题的数学模型： minz=0x1+0.3x2+0.5x3+0.1x4+0.4z5+0x6+0.3x7+0.6x8+0.2xg+0.5x10 s.t. 2x1+2x2+ =1000 E1十 2x3十x十 4x6+3x7+2x8+xg =1000 x2十 2z4十3x5十 x7+2x8+4xg十5x10=1000 x≥0(i=1,2,·,10) (1-1-2) 以上两个问题都是求一组决策变量使得某线性函数（称为目标函数）达到最大或最 小的优化问题。这些决策变量满足一定的线性函数，这些函数称为约束条件。这样的问 题就是所谓的线性规划问题。将其推广就得到如下线性规划的一般数学表达：
10 运筹学基础及其 MATLAB 应用 的钢轴各 1000 根就行了。于是，可以按照这样的思路来考虑：假设在圆钢上的切口厚度 忽略不计，那么，若在一根圆钢上截取 2 根 1.5m、1 根 1m 的钢轴，则没有任何余料，若 在一根圆钢上截取 2 根 1.5m、1 根 0.7m 的钢轴，则只有 0.3m 的余料……把这些方案列 举出来 (见表 1-1)。只要余料小于 0.8m，那么都是比原始想法好的截取方案。这样，通过 各种截取方案获得的 1.5m、1m 和 0.7m 的钢轴只要都有 1000 根，这项任务就完成了。这 样做的目的当然是让产生的余料之和达到最小。于是，可以设 xi(i = 1, 2, · · · , 10) 表示采 用第 i 种方案时圆钢的数目，则将得到规格为 1.5m，1m 和 0.7m 的钢轴分别为： 2x1 + 2x2 + x3 + x4 + x5 (1.5m 钢轴) x1 + 2x3 + x4 + 4x6 + 3x7 + 2x8 + x9 (1m 钢轴) x2 + 2x4 + 3x5 + x7 + 2x8 + 4x9 + 5x10 (0.7m 钢轴) 表 1-1 优于原始方案的下料方案 ❳ 钢 ❳ 轴 ❳ 规 ❳ 格 ❳ /根 ❳❳❳❳❳ 方案 1 2 3 4 5 6 7 8 9 10 需求量 1.5m 2 2 1 1 1 0 0 0 0 0 1000 1m 1 0 2 1 0 4 3 2 1 0 1000 0.7m 0 1 0 2 3 0 1 2 4 5 1000 余料/m 0 0.3 0.5 0.1 0.4 0 0.3 0.6 0.2 0.5 1000 按照这样的做法，将会产生的余料表达式为： 0.3x2 + 0.5x3 + 0.1x4 + 0.4x5 + 0.3x7 + 0.6x8 + 0.2x9 + 0.5x10 于是，得到该问题的数学模型： min z= 0x1+0.3x2+0.5x3+0.1x4+0.4x5+0x6+0.3x7+0.6x8+0.2x9+0.5x10 s.t. 2x1+ 2x2+ x3+ x4+ x5 = 1000 x1+ 2x3+ x4+ 4x6+ 3x7+ 2x8+ x9 = 1000 x2+ 2x4+ 3x5+ x7+ 2x8+ 4x9+ 5x10 = 1000 xi > 0(i = 1, 2, · · · , 10) (1-1-2) 以上两个问题都是求一组决策变量使得某线性函数 (称为目标函数) 达到最大或最 小的优化问题。这些决策变量满足一定的线性函数，这些函数称为约束条件。这样的问 题就是所谓的线性规划问题。将其推广就得到如下线性规划的一般数学表达：
