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

清华运筹学课件

运筹学(第三版)《运筹学》教材编写组 编

第1章 线性规划与 单纯形法第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所示。拥有量资源 产品

设

备

原材料 A 原材料 B

Ⅰ 1 4 0

Ⅱ 2 0 4

8台时 16 kg 12 kg

清华运筹学课件

续例1该工厂 每生产一件产品Ⅰ可获利2元， 每生产一件产品Ⅱ可获利3元， 问应如何安排计划使该工厂获利 最多?

清华运筹学课件

如何用数学关系式描述这问题， 必须考虑 设 x1 , x 2 分别表示计划生产 I, II产品的数量， 称它们为决策变量。 生产 x1 , x 2的数量多少，受资源拥 有量的限制 , 这是约束条件。即 x1 + 2 x2 ≤ 8;4 x1 ≤ 16 ;4 x 2 ≤ 12

生产的产品不能是负值

,即 x1 , x 2 ≥ 0

如何安排生产，使利润 最大 ,这是目标。

清华运筹学课件

数学模型

目标函数

max z = 2 x1 + 3 x 2

x1 + 2 x 2 ≤ 8 4x ≤ 16 1 约束条件 : 4 x 2 ≤ 12 x1 , x 2 ≥ 0

清华运筹学课件

例2. 简化的环境保护问题 靠近某河流有两个化工厂(见 图1-1),流经第一化工厂的河流 流量为每天500万立方米，在两 个工厂之间有一条流量为每天 200万立方米的支流。

清华运筹学课件

图1-1

清华运筹学课件

续例2 第一 化工厂每天排放含有某种有害物质的工业污 水2万立方米，第二化工厂每天排放这种工业污水 1.4万立方米。从第一化工厂排出的工业污水流到 第二化工厂以前，有20%可自然净化。根据环保要 求，河流中工业污水的含量应不大于0.2%。

这两个 工厂都需各自处理一部分工业污水。第一化工厂处 理工业污水的成本是1000元/万立方米。 第二 化工厂处理工业污水的成本是800元/万立方 米。现在要问在满足环保要求的条件下，每厂各应 处理多少工业污水，使这两个工厂总的处理工业污 水费用最小。

清华运筹学课件

建模型之前的分析和计算设： 第一化工厂每天处理工业污水量为x1万立方米， 第二化工厂每天处理工业污水量为x2万立方米

( 2 x1 ) 2 经第 2 工厂前的水质要求： ≤ 500 1000 经第 2 工厂后的水质要求： [ 0 .8( 2 x1 ) + ( 1 .4 x 2 )] 2 ≤ 700 1000

清华运筹学课件

数学模型

目标函数 约束条件

min z = 1000 x1 + 800 x 2 x1 x1 ≥1 ≤2 x 2 ≤ 1 .4 x1 , x 2 ≥ 0 0.8 x1 + x 2 ≥ 1.6

清华运筹学课件

共同的特征(1)每一个线性规划问题都用一组决策变量 ( x1 , x 2 ,L x n )表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是 非负且连续的；

(2)要有各种资源和使用有关资源的技术数据 ，创造新价值的数据；

aij ; c j ( i = 1,L m; j = 1,L n )

清华运筹学课件

共同的特征(继续)(3) 存在可以量化的约束条件，这些约束条 件可以用一组线性等式或线性不等式来表 示; (4) 要有一个达到目标的要求，它可用决策 变量的线性函数(称为目标函数)来表示。 按问题的不同，要求目标函数实现最大化 或最小化。

清华运筹学课件

它们的对应关系可用表格表示：决策变量

1活

2 M动

x1 a11 a21

x2 a12 a22

L xn L a1n L a2 n

资源

b1 b2 M bm

m价值系数

M M M am1 am 2 L amn c1 c2 L cn

清华运筹学课件

线性规划的一般模型形式目标函数 max(min) z = c1 x1 + c2 x2 + L + cn xn 约束条件 a11x1 + a12 x2 + LL + a1n xn ≤ ( = ,≥ ) b1 a21x1 + a22 x2 + LL + a2 n xn ≤ ( = ,≥ ) b2 L L L L L L L ( 1.2 ) ( 1.3 ) am1 x1 + am 2 x2 + LL + am xn ≤ ( = ,≥ ) bm x1 , x2 ,LL , xn ≥ 0 ( 1.1 )

清华运筹学课件

1.2 图解法例1是二维空间(平面)线性规划问题， 可用作图法直观地来表述它的求解。 因存在 x1 , x2 ≥ 0 必须在直角坐标的第1象限内作图， 求解。

清华运筹学课件

max z = 2 x1 + 3 x 2

图1-2

x1 + 2 x 2 ≤ 2 4x ≤ 16 1 4 x 2 ≤ 12 x1 , x 2 ≥ 0

清华运筹学课件

图1-3 目标值在(4,2)点，达到最大值14目标函数

max z = 2 x1 + 3x22 z x2 = x1 + 3 3 表示一簇平行线

本文来源：https://www.bwwdw.com/article/s8o4.html