管理运筹学02线性规划.ppt

1. 线性规划问题及其数学模型
2. 线性规划的图解法
3. 线性规划问题的标准形式
4. 线性规划的解集特征
5. 线性规划的单纯形法
6. 单纯形法的进一步讨论
第二章线性规划
8/15/2018
1
线性规划问题及其数学模型
资源合理利用问题:第5页例2-1
质量检验问题:第6页例2-2
线性规划数学模型的一般形式
8/15/2018
2
资源合理利用问题:第5页例2-1
1. 决策变量:x1和x2
2. 目标函数:max (2 x1+3 x2)
3. 约束条件:10 x1+20 x2  80
4 x1  16
6 x2  18
x1,x2  0
8/15/2018
3
质量检验问题:第6页例2-2
:x1和x2
:min(40 x1+36 x2)
:5 x1+3 x2  45
x1  8
x2  10
x1,x2  0
8/15/2018
4
线性规划数学模型的一般形式
1. 决策变量是非负变量;
2. 目标函数是线性函数;
3. 约束条件是线性等式或不等式组。
一般形式为:
max(min)(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
8/15/2018
5
线性规划的图解法
:只能求解具有两个变量的线性规划问题。
:图解法只能求解具有两个决策变量的线性规划问题,其应用具有很大的局限性,因此学****图解法的目的并非是要掌握一种线性规划问题的求解方法,而是要通过图解法揭示线性规划问题的内在规律,为学****线性规划问题的一般算法(单纯形法)奠定基础。



8/15/2018
6
线性规划有关解的几个概念
1. 可行解:满足约束条件的一组决策变量的取值;
2. 可行域:可行解所构成的集合;
3. 最优解:使目标函数达到极值的可行解;
4. 最优值:与最优解相对应的目标函数的取值。
8/15/2018
7
图解法的基本步骤
;
,用标号和箭线表明约束条件的顺序和不等号的方向;
;
。
:第7页例2-3:用图解法求解例2-1
:第8页例2-4:用图解法求解例2-2
8/15/2018
8
用图解法求解例2-1
x1
x243210
1 2 3 4 5 6 7 8
8/15/2018
9
用图解法求解例2-1
x1
x243210
1 2 3 4 5 6 7 8
8/15/2018
10