文档介绍：1
第二章线性规划的图解法
§1 问题的提出
§2 图解法
§3 图解法的灵敏度分析
2
第二章线性规划的图解法
在管理中一些典型的线性规划应用
合理利用线材问题:如何在保证生产的条件下,下料最少
配料问题:在原料供应量的限制下如何获取最大利润
投资问题:从投资项目中选取方案,使投资回报最大
产品生产计划:合理利用人力、物力、财力等,使获利最大
劳动力安排:用最少的劳动力来满足工作的需要
运输问题:如何制定调运方案,使总运费最小
线性规划的组成:
目标函数 Max F 或 Min F
约束条件 . (subject to) 满足于
决策变量用符号来表示可控制的因素;所要决策的问题待
定的量值。
3
§1 问题的提出
例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表:
问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?
线性规划模型:
目标函数:Max z = 50 x1 + 100 x2
约束条件:. x1 + x2 ≤ 300
2 x1 + x2 ≤ 400
x2 ≤ 250
x1 , x2 ≥ 0
4
§1 问题的提出
建模过程以及线性规划的三要素
,了解解题的目标和条件;
( x1 ,x2 ,…,xn ),每一组值表示一个方案;
,确定最大化或最小化目标;
一般形式
目标函数: Max (Min) z = c1 x1 + c2 x2 + …+ cn xn
约束条件: . 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
5
巩固练习:
合理利用线材问题,套裁下料问题
某钢筋车间要用一批长度为10米的钢筋下料,制作长度为3米的钢筋30根和长度为4米的钢筋40根,问怎样下料最省?
省料解法:即余料小于各类轴件中长度最短者的截法。
6
:
Max z = 50 x1 + 100 x2
约束条件:
.
x1 + x2 ≤ 300 (A)
2 x1 + x2 ≤ 400 (B)
x2 ≤ 250 (C)
x1 ≥ 0 (D)
x2 ≥ 0 (E)
得到最优解:
x1 = 50, x2 = 250
最优目标值 z = 27500
§2 图解法
对于只有两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示线性规划问题的有关概念,并求解。
下面通过例1详细讲解其方法:
7
§2 图解法
(1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里,图上任意一点的坐标代表了决策变量的一组值,例1的每个约束条件都代表一个半平面。
x2
x1
X2≥0
X2=0
x2
x1
X1≥0
X1=0
8
§2 图解法
(2)对每个不等式(约束条件),先取其等式在坐标系中作直线,然后确定不等式所决定的半平面。
100
200
300
100
200
300
x1+x2≤300
x1+x2=300
100
100
200
2x1+x2≤400
2x1+x2=400
300
200
300
400
9
§2 图解法
(3)把五个图合并成一个图,取各约束条件的公共部分,如图2-1所示。
100
100
x2≤250
x2=250
200
300
200
300
x1
x2
x2=0
x1=0
x2=250
x1+x2=300
2x1+x2=400
图2-1
10
§2 图解法
(4)目标函数z=50x1+100x2,当z取某一固定值时得到一条直线,直线上的每一点都具有相同的目标函数值,称之为“等值线”。平行移动等值线,当移动到B点时,z在可行域内实现了最大化。A,B,C,D,E是可行域的顶点,对有限个约束条件则其可行域的顶点也是有限的。
x1
x2
z=20000=50x1+100x2
图2-2
z=27500=50x1+100x2
z=0=50x1+100x2
z=10000=50x1+100x2
C
B
A
D
E