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

管理运筹学朱晓辉 管理科学与工程

管

理

运

筹

学

2-1

第二章 线性规划的图解法教学目标： 掌握线性规划的数学模型，能够结合问 题列出模型 理解图解法求解 了解图解法的灵敏度分析

管

理

运

筹

学

2-2

第二章 线性规划的图解法 §1 §2 §3 问题的提出 图解法 图解法的灵敏度分析

管

理

运

筹

学

2-3

第二章

线性规划的图解法

在管理中一些典型的线性规划应用: 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最 大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小

线性规划的组成： 目标函数 约束条件 Max F 或 Min F 满足于学2-4

s.t. (subject to)管 理 运 筹

决策变量

用符号来表示可控制的因素

§1

问题的提出

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

问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型： 目标函数：Max 约束条件：s.t. z = 50 x1 + 100 x2 x1 + 2 x1 + x2 ≤ 300 x2 ≤ 400 x2 ≤ 250 x1 , x2管

≥ 02-5

理

运

筹

学

把满足所有约束条件的解称为该线性规划的 可行解。 把使得目标函数值最大(即利润最大)的可 行解称为该线性规划的最优解，此目标函数值称 为最优目标函数值，简称最优值。

管

理

运

筹

学

2-6

§1

问题的提出

建模过程 1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量( x1 ,x2 ,… ,xn ),每一组值表示一个方 案； 3.用决策变量的线性函数形式写出目标函数，确定最大化或最小 化目标； 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循 的约束条件 一般形式:目标函数： 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 ≥ 0

管

理

运

筹

学

2-7

练习题： 某公司由于生产需要，共需要A,B两种原料至少 350 吨(A,B两种原料有一定替代性),其中原料A至 少购进125 t.但由于A,B两种原料的规格不同，各 自所需的加工时间也是不同的

,加工每吨原料A需要2 小时，加工每吨原料B需要1小时，而公司总共有600 个加工时数.又知道每吨原料A的价格为2万元，每吨 原料B的价格为3万元，试问在满足生产需要的前提下， 在公司加工能力的范围内，如何购买A,B两种原料， 使得购进成本最低?管 理 运 筹 学2-8

§2对于只有两个决 策变量的线性规划问 题，可以在平面直角 坐标系上作图表示线 性规划问题的有关概 念，并求解。 下面通过例1详细 讲解其方法：

图解法例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + 2 x1 +

x2 ≤ x2 ≤ x2 ≤ x1 ≥ x2 ≥

300 400 250 0 0

(A) (B) (C) (D) (E)

得到最优解： x1 = 50, x2 = 250 最优目标值 z = 27500

管

理

运

筹

学

2-9

§2 图 解 法(1)分别取决策变量X1 , X2 为坐标向量建立直角坐标 系。在直角坐标系里，图上任意一点的坐标代表了决策变

量的一组值，例1的每个约束条件都代表一个半平面。x2X2≥0

x2X1≥0

X1=0

X2=0

x1管 理 运 筹 学

x1

2-10

§2

图解法

(2)对每个不等式(约束条件),先取其等式在坐标系 中作直线，然后确定不等式所决定的半平面。

400 300 200 100 100 200 300 300

x1+x2=300

200 100

2x1+x2=400

2x1+x2≤400

100

200

300

x1+x2≤300

管

理

运

筹

学

2-11

§2 图 解 法(3)把五个图合并成一个图，取各约束条件的公共部分 (包括五条边界线),如图2-1所示。x2300200

x2=250

2x1+x2=400 x2=250

100100 200 300

x2≤250

x1+x2=300

x2=0

x1=0

x1

图2-1管 理 运 筹 学2-12

可行域可行域的几何形状由于问题不同可以千变 万化，但可行域的几何结构是凸集 要求集合中的任何两点的连线段落在这个 集合中

管

理

运

筹

学

2-13

§2

图解法

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

A

z=10000=50x1+100x2

x1

图2-2管 理 运 筹 学

2-14

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

然也就不存在最优解了。管 理 运 筹 学2-15

练习题 2. 用图解法求解下列线性规划问题，并指出 哪个问题具有惟一最优解、无穷多最优解、无界 解或无可行解. (1) min f=6x1+4x2; 约束条件： 2x1+x2≥1, 3x1+4x2≥3, x1,x2≥0. (2) max z=4x1+8x2; 约束条件： 2x1+2x2≤10, -x1+x2≥8, x1, x2≥0.

管

理

运

筹

学

2-16