管理运筹学(B)课程教材
主用教材: 运筹学教程(第二版) 胡运权 清华出版社 主要内容: 目标规划, 非线性规划, 排队论, 存储论, 决策论等
主要参考: 运筹学(第三版) (清华大学出版社) 运筹学习题集(第三版) 胡运权 清华出版 运筹学习题集(修订版) 重要网站:中国科学院数学与系统科学研究院
www.amss.ac.cn/amss/amsscn.html 4个研究所, 4个实验室, 等机构, 相应的各学会
第1讲 线性规划概要
§1线性规划(LP)基本概念
1. 线性规划(LP)的一般形式和标准形 目标函数:max(min)z =c 1x 1+c 2x 2++c n x n
⎧a 11x 1+a 12x 2+ +a 1n x n ⎪a x +a x + +a x 2112222n n ⎪⎪
约束条件:⎨
⎪a x +a x + +a x
m 22mn n
⎪m 11
x 1, x 2 , x n ⎪⎩
≤(=, ≥)
b 1
≤(=, ≥) b 2
≤(=, ≥) b m
≥
注1 标准形为max, ’=’, b i ≥0, x j ≥0;
注2 总能通过
min z = C x → max z’= -C x
……= -b i , 两边乘 (-1) → …… = b i ; …… b , 左减剩余变量→…… - xi +1 = b i ; 无约束变量x → x =x’-x”, x’ > 0, x” > 0 注3 标准形在单纯形法中用.
2. 可行域和可行解 最优解和最优值
(1)集合D ={x |Ax ≤b , x ≥0}, 称为线性规划(LP)的可行域.
(或=,≥)
若 x ∈D , 则称x 为(LP)的可行解.
*
(2)若x *∈D 且对任意x ∈D 有cx ≥ cx ，
则称x *为(LP)的最优解，cx *为最优值.
§2 线性规划图解法(适用两个变量)
可行域T
1
1. 唯一最优解的例子
例 1 用图解法解下列线性规划 max z=2x1+5x2
s.t. x 1 ≤ 4 x 2 ≤ 3 x 1+2x2 ≤ 8 x 1≥0, x2≥0 解:
(1) 作出可行域ABCD.
(2) 作目标函数z=2x1
的梯度方向(变大) (3) 最优解为通过 C(2,3), 最优值19.
2. 无穷多个最优解的例子 例2 max z=x1+x2 s.t. 2x1+5x2 ≤ 20 2x 1+x2 ≤ 8 x 1+x2 ≤ 5 x 1, x2≥0
解临界线x 1+x2=5，最优解为PQ 最优值为5. x *1=3(1-λ) +3x *2=3(1-λ) +2x 1
3. 无最优解的例子
例 3
min z= -2x 1+x2 s.t. -x 1+x2 ≤ 2 x 1-4x 2 ≤ 2 x 1,x 2≥0 解
1) 可行域无界(图3)
T
2) 目标函数的梯度方向(-2,1)3) 目标函数的等值线沿负
梯度方向可一直推下去故此问题目标值无下界, 无最优解.
注1若目标函数改为求最大值 max z= - 2x1+x2 , 则临界等值线为
-2x 1+x2=2 ,
T
最优解为(0,2)， 最优值为 2.
注2若目标函数改为 min z=x1-x 2, 结果将是什么?
4. 可行域为空的例子
例4 用图解法解下列线性规划 min z =x1-x 2 s.t. -x 1+2x2 ≤ 2 x 1-4x 2 ≤ 2 x 2≥3 x 1, x 2≥0 解
此题的可行域(右图
可见D=Φ， 此题无可行解
⇒无最优解
5. 线性规划最优解的几种情况
(1). 存在时 ① 唯一最优解, 在(唯) 一顶点上取到
② 无穷多最优解, 在(唯) 一边上取到(含顶
点)
总能在某一顶点上取到.
单纯形法: 找这样的顶点.
(2) 不存在 ① 可行域为空集，
② 目标函数值无界.
6. 其它标准形
max z =CX ,
⎧n
⎪∑P j x j =b , i =1,2, , m (
st ⎨j =1
⎪x ≥0, j =1,2, , n . ⎩j
或
⎧AX =b , st ⎨ ⎩X ≥0,
§2 线性规划(LP)单纯形法回顾
1. 标准形进一步的标准
max z =c 1x 1+c 2x 2++c n x n
⎧x 1+a 1, m +1x m +1+ +a 1n x n
⎪x +a
22, m +1x m +1+ +a 2n x n ⎪⎪
s.t ⎨
⎪x +a
m , m +1x m +1+ +a mn x n
⎪m ⎪⎩b j ≥0, j =1..., m , x 1, x 2 , x n
2. 一个自然可行解
==... ≥
b 1b 2
... (*) 0
=b m
(x 1,..., x m , x m +1,..., x n ) T =(b 1,..., b m ,0,...,0) T (一顶点)
3. 讨论当x m +1,..., x n ≥0时,z 是否还可增值? 只需将由(*)解出的基变量
⎡x 1⎤⎡x m +1⎤⎢ ⎥=b -⎢ ⎥
B ⎢⎢⎥⎥
⎢⎢⎣x m ⎥⎦⎣x n ⎥⎦
代入z =CX 后, 若x m +1,..., x n 前系数>0, 则仍可增. 4. 设法找下一个顶点.
(假设存在最优, 必在某顶点上取到) 5. 单纯形法
(1)建初始单纯形表, 找出初始可行基;(如下表)
(2) 检验数 若σj =c j -
∑c a
i =1
m
i i , j
≤0, m +1≤j ≤n , 则停,
否则转下一步
(3) 若某σk >0的P k ≤0, 则停, 无界解; 否则转下步;
(4) 根据max(σj >0) =σk , 确定x k 为换入变量, 并计算
⎛b i ⎫b l
θ=min a i , k >0⎪=
i a ⎪a l , k ⎝i , k ⎭
确定x l 为换出变量, 并转下步; (5) 以a lk 为主元进行迭代, 使
⎡ ⎤⎡ ⎤P k =⎢a lk ⎥化成第l 行→⎢1⎥
⎢⎥⎢⎥⎢⎢⎣ ⎥⎦⎣ ⎥⎦
将X B 列中的x l 换为x k ， 得到新单纯形表, 重复(2)~(5).
6. 例子
解: 设 I, II 的产量为x 1, x 2, 则目标函数为
⎧x 1+2x 2⎪4x ⎪1
max z =2x 1+3x 2, s.t ⎨
⎪4x 2⎪⎩x 1, x 2
化成标准形为
≤8
≤16≤12≥
max z =2x 1+3x 2+0x 3+0x 4+0x 5
⎧x 1+2x 2+x 3
⎪4x +x 4⎪1st ⎨
4x 2+x 5
⎪⎪⎩x 1, x 2, x 3, x 4, x 5
=8=16=12≥0
用单纯形法 初始可行解:X
(0)
(0,0,8,16,12)T , 表如下
最优解X *=X (3)=(4,2,0,0,4)T , 最大值z *=14.
求解下列线性规划问题
⎧x 1+2x 2
⎪4x ⎪1
1+2x 2, s.t ⎨
⎪4x 2⎪⎩x 1, x 2
1.2 用图解法解下列线性规划问题
≤8
≤16≤12≥
⎧2x 1+x 2≥1⎪
min z =6x 1+4x 2, s.t. ⎨3x 1+4x 2≥1.5
⎪x , x ≥0⎩12
管理运筹学(B)课程教材
主用教材: 运筹学教程(第二版) 胡运权 清华出版社 主要内容: 目标规划, 非线性规划, 排队论, 存储论, 决策论等
主要参考: 运筹学(第三版) (清华大学出版社) 运筹学习题集(第三版) 胡运权 清华出版 运筹学习题集(修订版) 重要网站:中国科学院数学与系统科学研究院
www.amss.ac.cn/amss/amsscn.html 4个研究所, 4个实验室, 等机构, 相应的各学会
第1讲 线性规划概要
§1线性规划(LP)基本概念
1. 线性规划(LP)的一般形式和标准形 目标函数:max(min)z =c 1x 1+c 2x 2++c n x n
⎧a 11x 1+a 12x 2+ +a 1n x n ⎪a x +a x + +a x 2112222n n ⎪⎪
约束条件:⎨
⎪a x +a x + +a x
m 22mn n
⎪m 11
x 1, x 2 , x n ⎪⎩
≤(=, ≥)
b 1
≤(=, ≥) b 2
≤(=, ≥) b m
≥
注1 标准形为max, ’=’, b i ≥0, x j ≥0;
注2 总能通过
min z = C x → max z’= -C x
……= -b i , 两边乘 (-1) → …… = b i ; …… b , 左减剩余变量→…… - xi +1 = b i ; 无约束变量x → x =x’-x”, x’ > 0, x” > 0 注3 标准形在单纯形法中用.
2. 可行域和可行解 最优解和最优值
(1)集合D ={x |Ax ≤b , x ≥0}, 称为线性规划(LP)的可行域.
(或=,≥)
若 x ∈D , 则称x 为(LP)的可行解.
*
(2)若x *∈D 且对任意x ∈D 有cx ≥ cx ，
则称x *为(LP)的最优解，cx *为最优值.
§2 线性规划图解法(适用两个变量)
可行域T
1
1. 唯一最优解的例子
例 1 用图解法解下列线性规划 max z=2x1+5x2
s.t. x 1 ≤ 4 x 2 ≤ 3 x 1+2x2 ≤ 8 x 1≥0, x2≥0 解:
(1) 作出可行域ABCD.
(2) 作目标函数z=2x1
的梯度方向(变大) (3) 最优解为通过 C(2,3), 最优值19.
2. 无穷多个最优解的例子 例2 max z=x1+x2 s.t. 2x1+5x2 ≤ 20 2x 1+x2 ≤ 8 x 1+x2 ≤ 5 x 1, x2≥0
解临界线x 1+x2=5，最优解为PQ 最优值为5. x *1=3(1-λ) +3x *2=3(1-λ) +2x 1
3. 无最优解的例子
例 3
min z= -2x 1+x2 s.t. -x 1+x2 ≤ 2 x 1-4x 2 ≤ 2 x 1,x 2≥0 解
1) 可行域无界(图3)
T
2) 目标函数的梯度方向(-2,1)3) 目标函数的等值线沿负
梯度方向可一直推下去故此问题目标值无下界, 无最优解.
注1若目标函数改为求最大值 max z= - 2x1+x2 , 则临界等值线为
-2x 1+x2=2 ,
T
最优解为(0,2)， 最优值为 2.
注2若目标函数改为 min z=x1-x 2, 结果将是什么?
4. 可行域为空的例子
例4 用图解法解下列线性规划 min z =x1-x 2 s.t. -x 1+2x2 ≤ 2 x 1-4x 2 ≤ 2 x 2≥3 x 1, x 2≥0 解
此题的可行域(右图
可见D=Φ， 此题无可行解
⇒无最优解
5. 线性规划最优解的几种情况
(1). 存在时 ① 唯一最优解, 在(唯) 一顶点上取到
② 无穷多最优解, 在(唯) 一边上取到(含顶
点)
总能在某一顶点上取到.
单纯形法: 找这样的顶点.
(2) 不存在 ① 可行域为空集，
② 目标函数值无界.
6. 其它标准形
max z =CX ,
⎧n
⎪∑P j x j =b , i =1,2, , m (
st ⎨j =1
⎪x ≥0, j =1,2, , n . ⎩j
或
⎧AX =b , st ⎨ ⎩X ≥0,
§2 线性规划(LP)单纯形法回顾
1. 标准形进一步的标准
max z =c 1x 1+c 2x 2++c n x n
⎧x 1+a 1, m +1x m +1+ +a 1n x n
⎪x +a
22, m +1x m +1+ +a 2n x n ⎪⎪
s.t ⎨
⎪x +a
m , m +1x m +1+ +a mn x n
⎪m ⎪⎩b j ≥0, j =1..., m , x 1, x 2 , x n
2. 一个自然可行解
==... ≥
b 1b 2
... (*) 0
=b m
(x 1,..., x m , x m +1,..., x n ) T =(b 1,..., b m ,0,...,0) T (一顶点)
3. 讨论当x m +1,..., x n ≥0时,z 是否还可增值? 只需将由(*)解出的基变量
⎡x 1⎤⎡x m +1⎤⎢ ⎥=b -⎢ ⎥
B ⎢⎢⎥⎥
⎢⎢⎣x m ⎥⎦⎣x n ⎥⎦
代入z =CX 后, 若x m +1,..., x n 前系数>0, 则仍可增. 4. 设法找下一个顶点.
(假设存在最优, 必在某顶点上取到) 5. 单纯形法
(1)建初始单纯形表, 找出初始可行基;(如下表)
(2) 检验数 若σj =c j -
∑c a
i =1
m
i i , j
≤0, m +1≤j ≤n , 则停,
否则转下一步
(3) 若某σk >0的P k ≤0, 则停, 无界解; 否则转下步;
(4) 根据max(σj >0) =σk , 确定x k 为换入变量, 并计算
⎛b i ⎫b l
θ=min a i , k >0⎪=
i a ⎪a l , k ⎝i , k ⎭
确定x l 为换出变量, 并转下步; (5) 以a lk 为主元进行迭代, 使
⎡ ⎤⎡ ⎤P k =⎢a lk ⎥化成第l 行→⎢1⎥
⎢⎥⎢⎥⎢⎢⎣ ⎥⎦⎣ ⎥⎦
将X B 列中的x l 换为x k ， 得到新单纯形表, 重复(2)~(5).
6. 例子
解: 设 I, II 的产量为x 1, x 2, 则目标函数为
⎧x 1+2x 2⎪4x ⎪1
max z =2x 1+3x 2, s.t ⎨
⎪4x 2⎪⎩x 1, x 2
化成标准形为
≤8
≤16≤12≥
max z =2x 1+3x 2+0x 3+0x 4+0x 5
⎧x 1+2x 2+x 3
⎪4x +x 4⎪1st ⎨
4x 2+x 5
⎪⎪⎩x 1, x 2, x 3, x 4, x 5
=8=16=12≥0
用单纯形法 初始可行解:X
(0)
(0,0,8,16,12)T , 表如下
最优解X *=X (3)=(4,2,0,0,4)T , 最大值z *=14.
求解下列线性规划问题
⎧x 1+2x 2
⎪4x ⎪1
1+2x 2, s.t ⎨
⎪4x 2⎪⎩x 1, x 2
1.2 用图解法解下列线性规划问题
≤8
≤16≤12≥
⎧2x 1+x 2≥1⎪
min z =6x 1+4x 2, s.t. ⎨3x 1+4x 2≥1.5
⎪x , x ≥0⎩12