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

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章线性规划及单纯形法