第1章线性规划与单纯形法

（本科版 ）运筹学 运筹学 教材编写组 编清华大学出版社第 1章 线性规划与单纯形法第 2章 对偶理论与灵敏度分析第 3章 运输问题第 4章 目标规划二 . 线性规划与目标规划第 1章 线性规划与单纯形法第 1节 线性规划问题及其数学模型第 2节 线性规划问题的几何意义第 3节 单纯形法第 4节 单纯形法的计算步骤第 5节 单纯形法的进一步讨论第 6节 应用举例第 1节 线性规划问题及其数学模型 1.1 问题的提出 1.2 图解法 1.3 线性规划问题的标准形式 1.4 线性规划问题的解的概念第 1节 线性规划问题及其数学模型线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法 。1.1 问题的提出从一个简化的生产计划安排问题开始例 1某工厂在计划期内要安排生产 、 两种产品，已知生产单位产品所需的设备台时及 A、 B两种原材料的消耗，如表 1-1所示。资源 产 品 拥有量设 备 1 2 8台时原材料 A 4 0 16 kg原材料 B 0 4 12 kg续例 1该工厂 每生产一件产品 可获利 2元， 每生产一件产品 可获利 3元， 问应如何安排计划使该工厂获利最多 ? 如何用数学关系式描述这问题，必须考虑数学模型例 2. 简化的环境保护问题靠近某河流有两个化工厂(见图 1-1)，流经第一化工厂的河流流量为每天 500万立方米，在两个工厂之间有一条流量为每天 200万立方米的支流。 图 1-1续例 2 第一 化工厂每天排放含有某种有害物质的工业污水 2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有 20%可自然净化。根据环保要求，河流中工业污水的含量应不大于 0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是 1000元 /万立方米。 第二 化工厂处理工业污水的成本是 800元 /万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。建模型之前的分析和计算设 ：第一化工厂每天处理工业污水量为 x1万立方米，第二化工厂每天处理工业污水量为 x2万立方米 数学模型 补充例补充例 1. 生产计划问题生产计划问题 某厂生产甲 乙 两种产品，各自的零部件分别在 A、 B车间生产，最后都需在 C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。 产 品车间工 时单 耗甲 乙生 产 能力ABC1 00 23 48 1236单 位 产 品 获 利 3 5(1)决策变量决策变量 。 要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设 x1为甲产品产量， x2为乙产品产量。 (2)约束条件约束条件 。 生产这两种产品受到现有生产能力的制约，用量不能突破。 生产单位甲产品的零部件需耗用 A车间的生产能力 1工时， 生产单位乙产品不需耗用 A车间的生产能力， A车间的能力总量为 8工时 ，则 A车间能力约束条件表述为x1 8 同理， B和 C车间能力约束条件为2x2 123x1 +4 x2 36 建立模型(3)目标函数目标函数 。 目标是利润最大化，用 Z表示利润，则maxZ= 3x1 +5 x2 (4)非负约束非负约束 。 甲乙产品的产量不应是负数，否则没有实际意义，这个要求表述为 x1 0， x2 0 综上所述，该问题的数学模型表示为 maxZ= 3x1 +5 x2x1 82x2 123x1 +4 x2 36x1 0, x2 0S.t.共同的特征 每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的；(2)要有各种资源和使用有关资源的技术数据，创造新价值的数据；共同的特征（继续）(3) 存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示 ;(4) 要有一个达到目标的要求，它可用决策变量的线性函数 (称为目标函数 )来表示。按问题的不同，要求目标函数实现最大化或最小化。它们的对应关系可用表格表示： 用一组非负决策变量表示一个决策问题， 存在一定的等式或不等式的线性约束条件， 有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。线性规划的一般形式 线性规划的一般模型形式1.2 图解法一个 二维 的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。例 1是二维空间（平面）线性规划问题，可用作图法直观地来表述它的求解。因存在必须在直角坐标的第 1象限内作图，求解。图 1-2图 1-3 目标值在（ 4， 2）点，达到最大值14目标函数可能出现的几种情况（ 1） 无穷多最优解 (多重最优解 )，见图 1-4（ 2） 无界解，见图 1-5-1（ 3） 无可行解，见图 1-5-2图 1-4 无穷多最优解 (多重最优解 )