下面是小编为大家整理的运筹学完整教案（全文）,供大家参考。
第
一
章
线性规划与单纯形法
1 、教学计划
第
1 次
课
2 学
时
绪论；第一章第
1 节、第
2 节、第
3 节
授课章节
授课方式 □√ 理论课
□ 讨论课
□ 实验课
□ 习题课
□ 其他
了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。
课堂教学 掌握两个决策变量线性规划问题可行域（凸集）、最优解的位置；了解无解（无界解、无可行解）、有解（唯 目的及要求 一解、无穷多个解）的几何意义。
重点：线性规划的数学模型及其标准形。在数学模型中，要求熟悉矩阵形式；在标准形中，要求学生掌握 课堂教学 非标准形式的几种具体情形及其相应的标准化方法；如何用几何的方法求两个决策变量的线性规划问题的 重点及难点 最优解。
难点：线性规划的基本概念，例如基、基变量、基解、基可行解和可行基；多个最优解如何表示。
教学过程 教学方法及手段 引
言
多媒体讲解 运筹学模型，运筹学发展历史与现状，研究方法；考核方法与教学大 纲等。
实例讲解 1.1 线性规划问题及其数学模型
教学过程 线性规划的数学模型：
变量的确定、约束条件与目标函数。
1.2
线性规划问题的标准形式
线性规划的标准形式及非标准形式的标准化处理。
1.3
线性规划问题的解
基、基变量、基解、基可行解和可行基。
第
2 次课
2 学时
授课章节 第一章第
4 节
授课方式 □√ 理论课
□ 讨论课
□ 实验课
□ 习题课
□ 其他
课堂教学 掌握单纯形法思想以及具体操作过程。
目的及要求 课堂教学 重点：
单纯形法迭代过程：（ 1 ）换入基变量的确定；
（ 2 ）换出基变量的确定；（ 3 ）判定当前解已经最优。
重点及难点 难点：单纯形法思想。
教学过程 教学过程 教学方法及手段
2 、课件
1.1
线性规划问题及其数学模型
线性规划模型的建立就是将现实问题用数学的语言表达出来。
例
1 ：某工厂要安排生产 Ⅰ 、 Ⅱ 两种产品，每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产
计划使工厂获利最多？
Ⅰ
Ⅱ
设备
1
2
8 台时
原材料A
4
0
16kg
原材料 B
0
4
12kg
单位产品的利润（元）
2
3
解：设生产产品 Ⅰ 、 Ⅱ 的数量分别为 x 和
x 。
1 2
首先，我们的目标是要获得最大利润，即
m ax z 2x 3x 1 2
其次，该生产计划受到一系列现实条件的约束，
设备台时约束：生产所用的设备台时不得超过所拥有的设备台时，即
1.4 单纯形法
多媒体讲解 单纯形数表的构造，要注意代数形式和表格形式的一一对应性。
实例讲解 单纯形法迭代过程：（ 1 ）换入基变量的确定；
（ 2 ）换出基变量的确定；
（ 3 ）判定当前解已经最优。
第
3 次课
2 学时
授课章节 第一章第
5 节
授课方式 □√ 理论课
□ 讨论课
□ 实验课
□ 习题课
□ 其他
课堂教学 掌握人工变量法的基本思想以及大M 法和两阶段法的求解。
目的及要求 课堂教学 重点：人工变量法的基本思想。
重点及难点 难点：大 M 法和两阶段法的求解。
教学过程 教学方法及手段 多媒体讲解 教学过程 1.5 单纯形法的进一步讨论及小结
人工变量法的思想，大M 法和两阶段法的求解思路和步骤。
实例讲解 单纯形法小结
x 2x 8 1 2
原材料约束：生产所用的两种原材料 A 、 B 不得超过所用有的原材料总数，即
4x
16 1
4x 12 2
非负约束：生产的产品数必然为非负的，即
x ,x 0 1 2
由此可得该问题的数学规划模型：
max z 2x 3x 1 2 x 2x 8 1 2 4x
16 1 4x 12 2 x ,x 0 1 2
总结：
线性规划的一般建模步骤如下：
（ 1 ）
确定决策变量
确定决策变量就是将问题中的未知量用变量来表示，如例
1 中的
x
和 x 2
。确定决策变量是建立数学规划模型的关键所在。
（ 2 ）
确定目标函数
确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。
（ 3 ）
确定约束条件
将现实的约束用数学公式表示出来。
线性规划数学模型的特点
（ 1 ）
有一个追求的目标，该目标可表示为一组变量的线性函数，根据问题的不同，追求的目标可以是最大化，也可以是最
小化。
（ 2 ）
问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。
（ 3 ）
问题用一组决策变量表示一种方案，一般说来，问题有多种不同的备选方案，线性规划模型正式要在这众多的方案中 找到最优的决策方案（使目标函数最大或最小），从选择方案的角度看，这是规划问题，从目标函数最大或最小的角度看，这是 最优化问题。
1.2
线性规划问题的标准形式
根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是 “ ” 或 “ ” 的不等式，也可以是 “=” ；虽然决策变量一般是非负的，但也可是无约束的，即，可以在 (
,
) 取值。为了分析问题的
简化，一般规定如下的标准形式：
1
3
5
6
4
4
max z c x 1 1 c
x
..., c
x
2
2 n n a x 11 1 a x 12 2 ...,a x b 1n n 1 a x a x ...,a x b 21 1 22
2 2n n 2 ......... a x a x ...,a
x b m 1 1 m 2
2 mn n m x ,x 1 2 ,..x .,
0
n 非标准形式转化为标准形式：
（ 1 ）
若目标函数要求实现最小化 min z ，则可令
z" z ，可将原问题的目标函数转化为 max z" 即可。
（ 2 ）
若约束方程为 “
” ，则可在 “
” 的左边加上非负的松弛变量；若约束方程为 “
” ，则可在 “
” 的左边减去非
负的剩余变量。
（ 3 ）
若存在取值无约束的变量 x
，则可令
x
x " x " ，其中， x " ,x " 0 。
k k k k k k
例：将如下问题转化为标准形式：
min z
x 2x
x 0,x 2
无约束
解：
首先，用
x
x 替换 x
2 ，其中， x ,x 0 ；
其次，在第一个约束条件的左端加上非负的松弛变量 x ；
再次，在第二个约束条件的左端减去非负的剩余变量 x ；
最后，令 z" z ，将求 min z 改为求 max z" 。由此，可得标准形如下：
max z"
x
2x 2x 1 3 4 0x 0x 5 6 2x
3x 3x x 6 1 3 4 5 x x x x 4 1 3 4 6 x 1 x ,x x x 3 3 4 ,x ,x ,x 0 1 3 4 5 6
1.3
线性规划问题的解首先，将线性问题的标准形式用矩阵和向量形式表示如下：
3
1 2 2x 3x 6 1 2
x x 4 1 2
x x 3 1 2
n
m2
max z CX AX B X 0
其中， C (c ,c ,..c .,) ；
X (x ,x ,..x .,) T
，
B
b ,b ,..b.,) T
1 2 n
1 2 n
a a 11 12 a a 1 2 m
... a 1n ... a A 21 .. a m 1 22 ... a m 2 2n ... .. ... a mn
1 、可行解和最优解
满足约束条件的所有解
X (x
,x ,..x .,) T
成为线性规划问题的可行解，其中，使目标函数达到最大的可行解成为
最优解。
2 、基和基解
设 A 为约束方程组的 m
n 维矩阵，其秩为 m 。设 B 为矩阵 A 中的 m
m 阶非奇异子矩阵（ B 0 ），则称 B
为线性规划的一个基。
不妨设前 m 个变量的系数矩阵为线性规划的一个基，则 X
(x ,x 1 2
,..x .,) T
为对应于这个基的基变量。用高斯
消去法可求得一个解
X (x ,x 1 2
,..x .,, 0, ... 0, ) T
n
该解得非零分量的数目不大于方程个数 m ，称
X 为基解。
3 、基可行解
若基解
X 满足非负约束，则称其为基可行解。
4 、可行基
对应于基可行解的基，成为可行基。
1.4
单纯形法
一、单纯形表
考察一种最简单的形式：目标函数最大化、所有约束条件均为 “ ” 。利用所有约束条件化为等号的方法，在每个约束条件
的左端加一个松弛变量，并整理，重新对变量及系数矩阵进行编号，得
x a x 1 1,m 1 m 1 ... a x b 1n n 1 x a x 2 2,m 1 m 1 ... a x b 2n n 2 ..... x a x ... a x b m m ,m
1 m 1 mn n m x 0,j 1,2...n, j 1
B
1
1
mmmj
2
BB2
将其与目标函数的变换形式
z c x
c x ...,c x 2
2 m m
c x m 1 m 1
...,c x n n
0 组成 n 1 个
变量、 m
1 个方程的方程组。若将 z 看成不参与基变换的基变量，它与 x
,x
,..x ., 的系数构成一个基，利用初等变换
c ,c 1 2
,..c ., 变为零，则可得
z x x ... x x ... x b
2,m 1 2n 2 ... ... ... ... ... ... .. .. ... 0 0 0
... 1 a m ,m 1 ... a b mn m m m m 1 0 0
... 0
c c a ... c c a c b m 1 i i 1 i,m 1 n1 i i 1 i,n1 i i i 1 据此，可设计如下的数表
c c … c j 1 m
C X b x … x B B 1 m
c … c m 1 n
i
x … x
m 1 n
c x b 1 1 1 1 … 0
a … a 1,m
1 1n 1 c x b 2 2 0 … 0 a … a
2 2,m 1 2n 2 … … … … … … … … … …
c x b 0 … 1 a … a m m m
c z m ,m 1 mn m
0 … m … m
j j c
m 1 c a i i,m 1 i 1 c c a n i in
i 1
X 列表示基变量，在这里为 x
,x
,..x .,
2 m
C 列为基变量 x
,x
,..x ., 对应的价值系数；
b 列为约束方程的右端项；
c 行为所有变量的价值系数；
i 列的数字是在确定换入变量后，按
规则计算后填入；
最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。例，求解
将
1
；
1
1
1 2 m m 1 n
0 1 0 ... 0 a ... a
b
1,m 1 1n 1 0 0 1 ... 0 a ... a
b
j
j j
2
2
3
max z 2x 3x 1 2 x 2x 8 1 2 4x
16 1 4x 12 2
首先将其转换为标准形式，
max z 2x 1 x ,x 0 1 2
3x 0x 0x 0x 2 3 4 5 x 2x x 8 1 2 3 4x x 16 1 4 4x x 12 2 5
构造初始单纯形表如下：
x ,x 1 2 ,x ,x ,x 0 3 4 5
c 2 3 0 0 0
i
C X b x x x x x B B 1 2 3 4 5
0 x 8 1
3
2 1 0 0 4
0 x 16 4 0 0 1 0 -
4
0 x 12 0 [4] 0 0 1 3
5
c z 2 3 0 0 0 由上表可得初始基可行解
X
(0)
(0, 0, 8, 16, 12) T
由于 x
x 的检验数大于零，表明上述解不是最优解，由于 x
的检验数更大，所以，先以 x
为换入变量。根据
规
则，可确定
x
为换出变量，计算得新表如下：
c j 2 3 0 0 0
i
C X b x x x x x B B 1 2 3 4 5
x [1] 0
1 0 -1/2 2
0 x 16 4 0 0 1 0 4
4
3 x 3 0 1 0 0 1/4 -
2
1
和
2
2
5
0
j j
j
j
5
j j
c z 2 0 0 0 -3/4
可得新解
X
(1)
(0, 3, 2, 16, 0) T
，目标函数取值
z
9 。
x 的检验数为
2 ，换入。根据
规则，可确定
x 为换出变量，计算得新表如下：
1 3
c 2 3 0 0 0
i
C X b x x x x x B B 1 2 3 4 5
2 x 2 1
1
0 1 0
-1/2 -
0 x 8 0 0 -4 1 [2] 4
4
3 x 3 0 1 0 0 1/4 12
2
x 的检验数为
1/4 ，换入。根据
规则，可确定
x
为换出变量，计算得：
c 2 3 0 0 0
i
C X b x x x x x B B 1 2 3 4 5
2 x 4 1
1
0 0 1/4 0
0 x 4 0 0 -2 1/2 1
5
3 x 2 0 1 1/2 -1/8 0
2
c z 0 0 -3/2 -1/8 0
得解
X
(3)
(4, 2, 00, 4) T
，目标函数取值
z
14
。由于所有的检验都小于零，达到最优。
PS ：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。
1.5
单纯形法的进一步讨论及小结
一、人工变量法
如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）和初始基可行解，此时必须要构造人工变量。
在迭代结束后，如果最后基变量中不再含有非零的人工变量，表示原问题有解；反之，则表示无可行解。
例：
3
c j
z j
0
0
-2
0
1/4
得新解
X
(2)
(2, 3, 08, 0) T
，目标函数取值
z
13 。
7
min z 3x x x 1 2 3 x 2x 1 2 x 11 3 4x x 2x 3 1 2 3 2x x 1 1 3 x ,x ,x 0 1 2 3
在第一个约束条件中加入松弛变量 x
4 ；在第二个约束条件中加入剩余变量 x
和人工变量
x
；在第三个约束条件中加入
人工变量
x 。
（ 1 ）大 M 法：
在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数值不产生影响，可假定人工变量在目标函数 中的系数为（ -M ）（ M
为很大的正数），这样在目标函数要实现最大化时，必须将人工变量从基变量中换出，否则目标函数不会实 现最大化。
对上例求解，加入人工变量后，规划问题变成
min z 3x 1 x 2 x 3 0x 0x 4
5 Mx
6 Mx 7 x 1 2x 2 x 3 x 11
4x x 2x x x 3 1 2 3 5 6 2x x x 1 1 3 7 x ,x 1 2 ,x ,x 3 4 ,x ,x ,x 0 5 6 7
然后，利用单纯形法求解，详见 P33 。
（ 2 ）两阶段法
第一阶段：不考虑原问题是否有基可行解；给原线性规划问题加上人工变量后，构造仅含人工变量的目标函数和要求实现
最小化；然后用单纯形法求解，若得到该规划的最优解为零，说明原问题存在基可行解，否则原问题无可行解，停止计算。
第二阶段：将第一阶段的最重计算表出去人工变量，换回原目标函数的系数作为第二阶段计算的初始表，利用单纯形法求
解。
前一个例子的两阶段法求解如下：
构造出第一阶段的数学模型如下：
min z
x x 6 7 x 2x 1 2 x x 11 3 4x x 2x x x 3 1 2 3 5 6 2x x x 1 1 3 7 x ,x 1 2
c j ,x ,x 3 4 ,x ,x ,x 0 5 6 7
C X B B 1 2 3 4 i
5 6 7
0 x 11 1 -2 1
4
1 0 0
0 11
5
6
0
0
0
0
0
1
1
b x
x
x
x
x
x
x
6
j
j j
j j
7
1 x 3 -4 1 2 0 -1 1 0 3/2
6
1 x 1 -2 0 [1] 0 0 0 1 1
7
c z 6 -1 -3 0 1 0 0
c j
C X B B 1 2 3 4 i
5 6 7
0 x 10 3 -2 0
4
1 0 0
-1 -
1 x 1 0 [1] 0 0 -1 1 -2 1
6
0 x 1 -2 0 1 0 0 0 1 -
3
c z 0 -1 0 0 1 0 0
c j
C X B B 1 2 3 4 i
5 6 7
0 x 12 3 0 0
4
1 -2
2 -5 -
0 x 1 0 1 0 0 -1 1 -2 1
2
0 x 1 -...
推荐访问:运筹学 教案 完整 运筹学完整教案 运筹学完整教案电子版
