文档介绍：运筹学
Operations Research
第一章线性规划及单纯形法
第一章线性规划及单纯形法
如何转化为标准形式?
1、目标函数为求极小值,即为: 。
因为求 min z 等价于求 max (-z),令 z’= - z,
即化为:
2、约束条件为不等式,
xn+1 ≥ 0
松弛变量
如何处理?
§1 线性规划问题及其数学模型
3、右端项bi < 0时,只需将等式两端同乘(-1)
则右端项必大于零
4、决策变量无非负约束
设 xj 没有非负约束,若 xj ≤0,可令 xj = - xj’,
则 xj’≥0;
又若 xj 为自由变量,即 xj 可为任意实数,
可令 xj = xj’- xj’’,且 xj’, xj’’≥0
第一章线性规划及单纯形法
. 3
试将 LP 问题
min z = -x1+2x2-3x3
. x1+x2+x3 ≤7
x1-x2+x3 ≥2
-3x1+x2+2x3 = -5
x1,x2 ≥0 化为标准形式。
解:
令 x3= x4 - x5 其中x4、x5 ≥0;
对第一个约束条件加上松弛变量 x6 ;
对第二个约束条件减去松弛变量 x7 ;
对第三个约束条件两边乘以“-1”;
令 z’=-z 把求 min z 改为求 max z’
max z’= x1-2x2+3x4- 3x5
. x1+x2+x4-x5+x6=7
x1-x2+x4-x5-x7=2
3x1-x2-2x4+2x5=5
x1,x2,x4,x5,x6,x7≥0
§2 线性规划问题的图解法
max z = 15x1 +25x2
. x1 + 3x2 ≤ 60
x1 + x2 ≤ 40
x1,x2 ≥ 0
(40,0)
(0,0)
B
C
(30,10)
O
(0,20)
A
L1
L2
Z=250
目标函数变形:
x2=-3/5 x1+z/25
x2
x1
最优解:
x1=30 x2 =10
最优值:zmax=700
B点是使z达到最大的唯一可行点
第一章线性规划及单纯形法
LP问题图解法的基本步骤:
1、在平面上建立直角坐标系;
2、图示约束条件,确定可行域和顶点坐标;
3、图示目标函数(等值线)和移动方向;
4、寻找最优解。
§2 线性规划问题的图解法
max z =3x1 +
. x1 + ≥
x1 - ≤
x1 + ≤
x1 - ≥-
x1 ,x2 ≥ 0
x1
x2
o
x1 - x2 =
x1 + x2=
x1 + x2 =
(,2)
D
0=3 x1 + x2
max Z
min Z
(,4)
= 3 x1 + x2
可行域
x1 - x2 = -
(0,2)
(,0)
绿色线段上的所有点
都是最优解,即有无穷多最优解。Zman=
第一章线性规划及单纯形法
max z = 2x1 + 2x2
. 2x1 – x2 ≥ 2
-x1 + 4x2≤ 4
x1,x2 ≥ 0
O
A
(1,0)
x1
x2
Note:
可行域为无界区域,
目标函数值可无限
增大,即解无界。
称为无最优解。
可行域为无界区域一定无最优解吗?
§2 线性规划问题的图解法
由以上两例分析可得如下重要结论:
1、LP 问题从解的角度可分为:
⑴有可行解
⑵无可行解
有唯一最优解
b. 有无穷多最优解
C. 无最优解
2、LP 问题若有最优解,必在可行域的某个顶点上取
到;若有两个顶点上同时取到,则这两点的连线上
任一点都是最优解。
3:差值法(伏格尔法)
最小元素法的缺点是:为了节省一处的费用,有时造成其它处要多花几倍的运费。伏格尔法考虑到,一产地的产品假如不能按最小费用就近供应,就考虑次小费用,这就有一个差额,差额越大,说明不按最小运费调运时,运费增加越多。因而对差额最大处,就应当采用最小调运方案。
基于此,伏格尔法的步骤是:每次从当前运价表上,计算各行各列中最小费用与次小费用这两个运价的差值,优先取最大差值的行或列中最小的运价来确定运输关系,直到求出初始方案。