运筹学 课程复习.ppt

运筹学
重点复****内容
11/11/2017
1
第一章线性规划及单纯形法
§1-1 线性规划问题及其数学模型
§1-2 图解法
§1-3 单纯形法原理
§1-4 单纯形法计算步骤
§1-5 单纯形法的进一步讨论
11/11/2017
2
组成线性规划模型的三个要素
max Z=2x1+x2
5x2≤15
6x1+2x2≤24
x1+x2≤5
x1,x2≥0
目标函数:
约束条件
(1)变量(决策变量):
它是规划中要确定的未知量,是用数量方式来表示的方案或措施,可由决策者决定和控制。
(2)目标函数:
它是决策变量的函数,是决策者在一定的限制条件下希望得到的结果。
(3)约束条件:
指决策变量取值时受到的各种资源条件的限制,通常用等式或不等式来表达。
其中,xij≥0叫做非负约束。
由于目标函数是决策变量的线性函数,约束条件是含决策变量的线性等式或不等式,所以此类模型称为线性规划的数学模型。
11/11/2017
3
二、线性规划模型的一般形式
假设线性规划问题中含有n个变量,m个约束方程。则线性规划模型的一般形式为:
max(或min)z=c1x1+c2x2+…+cnxn
a11x1+a12x2+…+a1nxn≤(或=,≥)b1
a21x1+a22x2+…+a2nxn≤(或=,≥)b2
…………………………………………
am1x1+am2x2+…+amnxn≤(或=,≥)bm
x1,x2,…,xn≥0
简写为:
向量形式:
矩阵形式:
11/11/2017
4
三、线性规划问题的标准形式
本教材规定,线性规划模型的标准形式为:
其特点是:
(1)目标函数求极大;
(2)约束条件取等式;
(3)变量非负;
(4)约束条件右边常数为正值。
11/11/2017
5
Q1
Q3
Q2
Q4
O
x1
5x2=15
6x1+2x2=24
x1+x2=5
(,)
11/11/2017
6
线性规划问题求解的几种可能结局
1. 线性规划有唯一最优解。
2. 线性规划问题有无穷多最优解
3. 线性规划问题的最优解无界
4. 线性规划问题无解,或无可行解
Q1
Q4
Q3
Q2
O
x1
x2
x1
x2
O
x1
x2
有无穷多最优解
目标函数求极大时,最优解无界
无可行域,所以无解。
11/11/2017
7
§1-3 单纯形法原理
可行解:满足(2)、(3)式的解称为可行解。
全部可行解的集合称为可行域。
最优解:使目标函数(1)达到最大值的可行解称为最优解。
一、线性规划问题的解的概念
有线性规划问题:
基:设A为约束方程(2)的m×n阶系数矩阵(设n>m),其秩为m,B是矩阵A中的一个m×m阶的满秩子矩阵,称B是线性规划问题的一个基。
系数矩阵:
基:
11/11/2017
8
基B中的每一个列向量Pj(j=1,2,…,m)称为基向量,与基向量Pj对应的变量xj称为基变量;除基变量以外的变量称为非基变量。
基解:在约束方程中,将非基变量移到等式右边:
P1
P2
Pm
令非基变量xm+1=xm+2=…=xn=0,得
可解得m个基变量的唯一解为:
XB=(x1,x2,…,xm)T。
加上非基变量取0的值,得
X=( x1,x2,…,xm,0,…,0)T。
这就是线性规划问题的基解。
11/11/2017
9
单纯形法小结
1. 一般线性规划模型化为标准形式的方法
线性规划模型
化为标准形式
变量
xj≥0
不变
xj≤0
令xjˊ=- xj ,则 xj≥0
xj无约束
令xj= xjˊ- xj〞; xjˊ≥0, xj〞≥0
约束条件
右端项
bi≥0
不变
bi<0
约束条件两端乘“-1”
形式
≤bi
+xsi=bi
=bi
+xai=bi
≥bi
-xsi+xai=bi
目标函数
极大或极小
max z =
不变
min z =
令z′=z,化为求max z′
变量前的系数
加松弛变量xs时
max z=
+0xsi
加人工变量xa时
max z=
-Mxai
11/11/2017
10