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

管理运筹学
4
§2 图 解 法
对于只有两个决 策变量的线性规划问 题，可以在平面直角
例1.目标函数： max z = 50 x1 + 100 x2
约束条件：
坐标系上作图表示线 性规划问题的有关概 念，并求解。
下面通过例1详细 讲解其方法：
s.t.
x1 + 2 x1 +
x2 ≤ 300 (A) x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E)
x1
管理运筹学
7
§2 图 解 法
（3）把五个图合并成一个图，取各约束条件的公共部分，如 图2-1所示。
x2
300
x2=250
200
100
x2≤250
100 200 300 x1
x2=0
x2 2x1+x2=400
x2=250
x1+x2=300
x1=0
x1
图2-1
管理运筹学
8
§2 图 解 法
（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直 线，直线上的每一点都具有相同的目标函数值，称之为“等 值线”。平行移动等值线，当移动到B点时，z在可行域内实 现了最大化。A，B，C，D，E是可行域的顶点，对有限个 约束条件则其可行域的顶点也是有限的。
划的一个或多个参数（系数）ci , aij , bj 变化时，对最优解产
生的影响。
3.1 目标函数中的系数 ci 的灵敏度分析 考虑例1的情况，ci 的变化只影响目标函数等值线的斜率，
目标函数 z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜
问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？
线性规划模型：
目标函数：max 约束条件：s.t.
z = 50 x1 + 100 x2 x1 + x2 ≤ 300
2 x1 + x2 ≤ 400 x2 ≤ 250
x1 , x2 ≥ 0
管理运筹学
3
§1 问题的提出
• 建模过程
1.理解要解决的问题，明确在什么条件下，要追求什么目标；
得到最优解：
x1 = 50， x2 = 250 最优目标值 z = 27500
管理运筹学
5
§2 图 解 法
(1)分别取决策变量X1, X2 为坐标向量建立直角坐标系。在 直角坐标系里，图上任意一点的坐标代表了决策变量的一 组值，例1的每个约束条件都代表一个半平面。
x2
X2≥0
x2
X1≥0
X2=0
X1=0
min f = c1x1 + c2x2 + … + cnxn (可以)令 z ＝ -f ，
则该极小化问题与下面的极大化问题有相同的最优解，
即 max z = - c1x1 - c2x2 - … - cnxn
但必须注意，尽管以上两个问题的最优解相同，但它们 最优解的目标函数值却相差一个符号，即
min f ＝ - max z
第二章 线性规划的图解法
• §1 问题的提出 • §2 图解法 • §3 图解法的灵敏度分析
管理运筹学
1
第二章 线性规划的图解法
在管理中一些典型的线性规划应用 • 合理利用线材问题：如何在保证生产的条件下，下料最少 • 配料问题：在原料供应量的限制下如何获取最大利润 • 投资问题：从投资项目中选取方案，使投资回报最大 • 产品生产计划：合理利用人力、物力、财力等，使获利最
• 线性规划存在无界解，即无最优解的情况。 对下述线性规划问题：
• 约束条件： max z=x1+x2； x1-x2 ≤1 -3x1+2x2 ≤6 x1 ≥0, x2 ≥0
管理运筹学
12
图解法 –无界解
• 用图解法求解结果，如图所示，可以看到， 该问题可行域无界，目标函数值可以增大到 无穷大，成为无界解，即为无最优解。
管理运筹学
16
§3 图解法的灵敏度分析
可以看出，线性规划的标准形式有如下四个特 点：
–目标最大化； –约束为等式； –决策变量均非负； –右端项非负。
对于各种非标准形式的线性规划问题，我们总可 以通过以下变换，将其转化为标准形式:
管理运筹学
17
§3 图解法的灵敏度分析
1.极小化目标函数的问题： 设目标函数为
2.定义决策变量（ x1 ，x2 ，… ，xn ），每一组值表示一个方 案；
3.用决策变量的线性函数形式写出目标函数，确定最大化或最 小化目标；
4.用一组决策变量的等式或不等式表示解决问题过程中必须遵 循的约束条件
• 一般形式
目标函数： 约束条件：
max （min） z = c1 x1 + c2 x2 + … + cn xn
3.右端项有负值的问题：
在标准形式中，要求右端项必须每一个分量非
负。当某一个右端项系数为负时，如 bi<0，则把该 等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2… -ain xn = -bi。
管理运筹学
21
§3 图解法的灵敏度分析
例：将以下线性规划问题转化为标准形式
min f = 2 x1 -3x2 + 4 x3
管理运筹学
14
进一步讨论
解：目标函数： min f = 2x1 + 3 x2 约束条件：
s.t.
x1 + x2 ≥ 350
x1 ≥ 125
2 x1 + x2 ≤ 600
x1 , x2 ≥ 0
采用图解法。如下图：得Q点坐标（250，100）为最优解。
x2
x1 =125
600
500
2x1+3x2 =1200
管理运筹学
18
§3 图解法的灵敏度分析
2、约束条件不是等式的问题：
设约束条件为
ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量s ，使它等于约束右边与左
边之差
s=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，s 也具有非负约束，即s≥0，
目标函数：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
x2
4
3 2 1
-2
-1
x2=0 -1
1
2
x1=0
z3=3=x1+4 x2 x1
z=1=x1+x2
z=0=x1+x2 图2-1
管理运筹学
13
进一步讨论
例2 某公司由于生产需要，共需要A，B两种原料至少350 吨（A，B两种材料有一定替代性），其中A原料至少购进125 吨。但由于A，B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需 要1小时，而公司总共有600个加工小时。又知道每吨A原料的 价格为2万元，每吨B原料的价格为3万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买A，B两种 原料，使得购进成本最低？
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
在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没 有非负约束时，可以令 xj = xj’- xj”
其中 xj’≥0，xj”≥0
取决即于用xj’两和个xj”非的负大变小量。之差来表示一个无符号限制的变量，当然xj的符号
管理运筹学
23
§3 图解法的灵敏度分析
灵敏度分析：建立数学模型和求得最优解后，研究线性规
x2
z=10000=50x1+100x2
AB C
z=0=50x1+100x2
E
z=27500=50x1+100x2
z=20000=50x1+100x2
D
x1
图2-2
管理运筹学
9
§2 图 解 法
• 线性规划的标准化内容之一：——引入松驰变量（含义是
资源的剩余量）
例1 中引入 s1， s2， s3 模型化为
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
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn+s = bi
管理运筹学