运筹学第2章 线性规划的图解法

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

第二章

线性规划的图解法

1

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

§1

问题的提出

例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已 知生产单位产品所需的设备台时及A、B两种原材料的消耗、 资源的限制，如下表：

Ⅰ设备 原料 A 原料 B 单位产品获利 1 2 0 50 元

Ⅱ1 1 1 100 元

资源限制 300 台时 400 千克 250 千克

问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利 最多？

2

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

线性规划模型： 目标函数：Max 约束条件：s.t. z = 50 x1 + 100 x2 x1 + 2 x1 + x2 ≤ 300 x2 ≤ 400

x2 ≤ 250x1 , x2 ≥ 0

3

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

建模过程

1. 理解要解决的问题，了解解题的目标和条件；

2. 定义决策变量( x1 ,x2 ,… ,xn ),每一组值表示一个方案； 3. 用决策变量的线性函数形式写出目标函数，确定最大化或 最小化目标； 4. 用一组决策变量的等式或不等式表示解决问题过程中必须 遵循的约束条件

4

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

一般形式

目标函数：

Max (Min) z = c1 x1 + c2 x2 + … + cn xn

约束条件: s.t. a11 x1 + a12 x2 + … + a1n xn ≤ ( =, ≥ )b1 a21 x1 + a22 x2 + … + a2n xn ≤ ( =, ≥ )b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ ( =, ≥ )bm x1 ,x2 ,… ,xn ≥ 05

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

相关术语决策变量的一组取值便构成了线性规划问题的一个解； 满足约束条件(包括资源约束和非负约束)的解称为可行解； 所有可行解构成的集合称为可行域； 使目标函数达到所追求极值的可行解称为最优解； 最优解所对应的目标函数值称为最优值。

6

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

§2对于只有两个决 策变量的线性规划问 题，可以在平面直角

图解法例1.目标函数：

Max

z = 50 x1 + 100 x2

约束条件： s.t. x1 + x2 ≤ 300 (A)

坐标系上作图表示线性规划问题的有关概

念，并求解。

2 x1 +

x2 ≤ 400x2 ≤ 250

(B)(C)

x1 ≥ 0x2 ≥ 0管 理 运 筹 学

(D)(E)7

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

§2 图 解 法(1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。取 各约束条件的公共部分x2 2x1+x2=400 x2=250

x1+x2=300

x2=0

x1=0

x1

图2-18

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

§2 图 解 法(2)目标函数z=50x1+100x2,当z取某一固定值时得到一条直 线，直线上的每一点都具有相同的目标函数值，称之为“等 值线”。平行移动等值线，当移动到B点时，z在可行域内实 x2 现了最大化。A,B,C,D,E是可行域的顶点，对有限个 约束条件则其可行域的顶点也是有限的。A

BC z=27500=50x1+100x2 z=20000=50x1+100x2 D

z=10000=50x1+100x2

z=0=50x1+100x2

E

x1

图2-2管 理 运 筹 学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

§2 图 解 法 重要结论： 当线性规划问题的可行域非空时，它是有界或无界的凸

多边形(凸集); 如果线性

规划有最优解，则一定有一个可行域的顶点对 应一个最优解； 无穷多个最优解。若将例1中的目标函数变为max z=50x1+50x2,则线段BC上的所有点都代表了最优解； 无界解。即可行域的范围延伸到无穷远，目标函数值可 以无穷大或无穷小。一般来说，这说明模型有错，忽略 了一些必要的约束条件； 无可行解。若在例1的数学模型中再增加一个约束条件 4x1+3x2≥1200,则可行域为空域，不存在满足约束条件 的解，当然也就不存在最优解了。管 理 运 筹 学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

进一步讨论例2 某公司由于生产需要，共需要A,B两种原料至少350 吨(A,B两种材料有一定替代性),其中A原料至少购进125 吨。但由于A,B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需 要1小时，而公司总共有600个加工小时。又知道每吨A原料的

价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A,B两种 原料，使得购进成本最低？11

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

解：目标函数： Min f = 2x1 + 3 x2 约束条件： s.t. x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0 采用图解法。如下图：得Q点坐标(250,100)为最优解。x2 600 x1 =125

500400 300 200 100

2x1+3x2 =1200 2x1+x2 =600 2x1+3x2 =900 x1+x2 =350 Q 100 200管

2x1+3x2 =800

300 400 500 600理 运 筹 学

x1

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

§3 一般形式

线性规划的标准形式

线性规划的标准化目标函数： 约束条件： Max (Min) z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn ≤ ( =, ≥ )b1 a21 x1 + a22 x2 + … + a2n xn ≤ ( =, ≥ )b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ ( =, ≥ )bm x1 ,x2 ,… ,xn ≥ 0z = c1 x1 + c2 x2 + … + cn xna11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… …… am1 x1 + am2 x2 + … + amn xn = bm x1 ,x2 ,… ,xn ≥ 0,bi ≥0管 理 运 筹 学

标准形式目标函数：约束条件：

Maxs.t.

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

可以看出，线性规划的标准形式有如下四个特点： 目标最大化； 约束为等式； 决策变量均非负；

右端项非负。

对于各种非标准形式的线性规划问题，我们总可 以通过以下变换，将其转化为标准形式:14

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

1.极小化目标函数的问题：

设目标函数为Min f = c1x1 + c2x2 + … + cnxn (可以)令 z = -f , 则该极小化问题与下面的极大化问题有相同的最优解， 即 Max z = - c1x1 - c2x2 - … - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们 最优解的目标函数值却相差一个符号，即

Min f = - Max z

15

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

2、约束条件不是等式的问题： 设约束条件

为

ai1 x1+ai2 x2+ … +ain xn ≤ bi可以引进一个新的变量s ,使它等于约束右边与左

边之差

s=bi–(ai1 x1 + ai2 x2 + … + ain xn )显然，s 也具有非负约束，即s≥0, 这时新的约束条件成为

ai1 x1+ai2 x2+ … +ain xn+s = bi

16

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

当约束条件为

ai1 x1+ai2 x2+ … +ain xn ≥ bi 时，类似地令

s=(ai1 x1+ai2 x2+ … +ain xn)- bi显然，s 也具有非负约束，即s≥0,这时新的约 束条件成为

ai1 x1+ai2 x2+ … +ain xn-s = bi

17

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

为了使约束由不等式成为等式而引进的变量s,当 不等式为“小于等于”时称为“松弛变量”;当不等 式 为“大于等于”时称为“剩余变量”。如果原问题中

有若干个非等式约束，则将其转化为标准形式时，必须

对各个约束引进不同的松弛变量。

18

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

例1 中引入 s1, s2, s3 模型化为 目标函数：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 ≥ 0 对于最优解 x1 =50 x2 = 250 , s1 = 0 s2 =50 s3 = 0 说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗 完所有可能的设备台时数及原料B,但对原料A则还 19 剩余50千克。管 理 运 筹 学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

3.右端项有负值的问题：

在标准形式中，要求右端项必须每一个分量非 负。当某一个右端项系数为负时，如 bi<0,则把该 等式约束两端同时乘以-1,得到：-ai1 x1-ai2 x2… -ain xn = -bi。

20

管

理

运

筹

学

运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

例：将以下线性规划问题转化为标准形式 Min f = s. t. 2.3 4.1 x1 + 3.6 x1 - 5.2 x2 + 1.8 x3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 x1 + 3.3 x3 ≥8.9 x2 + x3 = 38

x1 , x2 , x3 ≥ 0解：首先,将目标函数转换成极大化： 令 z= -f = -3.6x1+5.2x2-1.8x321

管

理

运

筹

学