文档介绍：第三节线性规划求解方法
一、计算机求解方法
1、基本思想:迭代的思想方法。
2、适用范围:一般线性规划问题。
3、例:生产计划问题
二、图解法
1、基本理论:凸集基本理论。
2、基本思想:在目标函数直线族中找一条满足可行域,
且取值最大(最小)的直线。
3、适用范围:两个变量的线性规划问题。
重庆大学经济与工商管理学院肖智
1
*§ 线性规划求解方法
4、作用:线性规划理论的几何意义,并说明线性规划解
的四种情况(唯一最优解、无穷最优解、有可
行解而无最优解、无可行解)。
5、举例说明。
三、单纯形法
1、单纯形法的概述
1)适用范围:线性规划标准形问题。
2)基本原理:
(1)目标:使Z=CX最大,在AX=b,X≥0条件下;
(2)理论:线性规划基本理论
(3)结论:
重庆大学经济与工商管理学院肖智
2
*§ 线性规划求解方法
(-1)
(-2)
(-3)
重庆大学经济与工商管理学院肖智
3
*§ 线性规划求解方法
要使Z=CX达到最大,由(-3)知只需去寻找一恰当
的基B使得(称为检验数向量)
3)基本思路:
基于线性规划问题的标准形,先确定一初始基可行解
X0,并由此开始在保证目标函数值不下降的情况下逐次施
行从一个基可行解到另一个基可行解的转换。如此进行下
去,直到取得最优解或判明问题无最优解为止。
4)基本步骤:
(1)对一般线性规划问题标准化;
(2)确定一初始基可行解X0;
(3)若所有检验数σj≤0( σj为的第j个分量),
则X0是线性规划问题的最优解,停止计算;否则转(4)
重庆大学经济与工商管理学院肖智
4
*§ 线性规划求解方法
(4)若存在σt<0所对应的系数列向量pt≤O,则线性规划问题无最优解,停止计算;否则转(5)。
(5)按最大检验数规则:
确定进基变量xk和主列pk;再按最小比值规则:
确定出基变量xl和主元alk。
(6)以主元alk进行换基迭代得一新的基可行解x1,将x1 记为x0返回到(3)。
5)基本工具:计算机或单纯形表。
重庆大学经济与工商管理学院肖智
5
*§ 线性规划求解方法
2、单纯形法应用举例: (-4)
重庆大学经济与工商管理学院肖智
6
*§ 线性规划求解方法
第一步标准化 (-5) 第二步建立初始单纯形表
重庆大学经济与工商管理学院肖智
7
*§ 线性规划求解方法
目标函数系数
25
10
0
0
0
资源拥
有量
决策变量
x1
x2
x3
x4
x5
0
( x3 的目标系数)
x3
1
0
0
12000
0
( x4 的目标系数)
x4
0
1
0
4000
0
( x5 的目标系数)
x5
0
0
1
6000
最优性检验数
25
10
0
0
0
0
-1
重庆大学经济与工商管理学院肖智
8
*§ 线性规划求解方法
此表对应一个可行方案和该方案最优检验结果。
可行方案:
x1=x2=0, x3=12000, x4=4000, x5=6000.
最优性检验结果:检验值全部非负(若全部非正,则可行
方案是最优方案)
重庆大学经济与工商管理学院肖智
9
*§ 线性规划求解方法
目标函数系数
25
10
0
0
0
可行方案
决策变量
x1
x2
x3
x4
x5
0
x3
0
1
-
0
6000
25
x1
1
0
0
10000
0
x5
0
0
0
1
6000
最优性检验数
0
0
-
0
250000
第三步:改进当前可行方案,计算下一张单纯形表。
-2
重庆大学经济与工商管理学院肖智
10
*§ 线性规划求解方法