运筹学02-线性规划的图解法.ppt

1
建立线性规划模型的步骤:
1)根据管理层的要求确定决策目标和收集相关数据。
2)确定要做出的决策,引入决策变量。
3)确定对这些决策的约束条件和目标函数。
2
例2 合理配料问题
求:最低成本的原料混合方案
原料 A B C 每单位成本
1 4 1 0 2
2 6 1 2 5
3 1 7 1 6
4 2 5 3 8
每单位添
加剂中维生 12 14 8
素最低含量
3
例3、运输问题
工厂
1 2 3 库存
仓 1 2 1 3 50
2 2 2 4 30
库 3 3 4 2 10
需求 40 15 35
运输
单价
求:运输费用最小的运输方案。
4
(2) 线性规划问题的特征:
决策变量: 每个问题都用一组决策变量(X1 …Xn)表示,这组决策变量的值都代表一个具体方案。
目标函数:衡量决策方案优劣的函数,它是决策变量的线性函数,根据问题不同,目标函数实现最大化或最小化。
约束条件:分为两类1)函数约束,一组决策变量的线性函数>=/<=/=一个给定的数(右端项)。2)决策变量约束。
具备以上三个要素的问题就称为线性规划问题。
5
目标函数
约束条件
(3) 线性规划模型一般形式
6
隐含的假设
比例性:决策变量变化引起目标的改变量与决策变量改变量成正比
可加性:每个决策变量对目标和约束的影响独立于其它变量
连续性:每个决策变量取连续值
确定性:线性规划中的参数aij , bi , cj为确定值
7
线性规划问题的图解法
定义1:满足约束(2)的X=(X1 …Xn)称为线性规划问题的可行解,全部可行解的集合称为可行域。
定义2:满足(1)的可行解称为线性规划问题的最优解。
8
x1
x2
z=20000=50x1+100x2
z=27500=50x1+100x2
z=0=50x1+100x2
z=10000=50x1+100x2
C
B
A
D
E
:
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
9
直观结论
若线性规划问题有解,则可行域是一个凸多边形(或凸多面体);
若线性规划问题有最优解,则
唯一最优解对应于可行域的一个顶点;
无穷多个最优解对应于可行域的一条边;
若线性规划问题有可行解,但无有限最优解,则可行域必然是无界的;
若线性规划问题无可行解,则可行域必为空集。
10
线性规划问题的标准形式
目标函数
约束条件
(1) 线性规划模型一般形式