文档介绍：第五章单纯形法
线性规划求解的相关概念
一、相关定理
定理1 线性规划问题的可行解集S是凸集。
定理2 线性规划问题的基本可行解X对应于可行域S的顶点。也就是说,可行域的顶点就是线性规划问题的基本可行解。
定理3 若线性规划问题有最优解,它一定在其可行域的顶点上达到。
二、基本概念
单纯形法的基本思路:单纯形法也可以说是一种找凸集极点的计算方法,但它并不是要求去计算所有的极点,而是从凸集的一个初始解出发,沿凸集的边缘逐个验算所遇到的极点,直到找到使目标函数最优的极点为止。
初始可行解:第一个找到的可行域的顶点。
三、单纯形法试算程序框图(见图5—1)
开始
转变为标准型[增加额外变量(松弛、剩余、人工变量)]
建立初始单纯形表
最优
停
找出“换入”“换出”变量
修正单纯形表
是
否
图5—1
线性规划模型的变换
一、线性规划模型标准型的特点
⑴目标函数是求极大值或极小值;
⑵所有的变量都是非负的;
⑶除变量的非负约束外,其余的约束条件都是等式约束;
⑷每个约束方程右边的常数都是非负的。
除变量的非负约束
等式约束
思考:若右边的常数不是非负怎么办?
二、线性规划模型的变换
根据线性规划模型约束条件的不同,将其划分为三种类型:
1.“≤”类型的约束条件的变换
变换的方法:在不等式中增加一个额外的变量,称为松弛变量,以S表示之。松弛变量在约束方程中的系数为1,在目标函数中的系数为0,所以它的引入并不影响目标函数值。
松弛变量即表示作为决策限制条件的某种有限资源未被利用的部分。
2.“≥”类型的约束条件的变换
变换的方法:引入剩入变量及人工变量,以S和A表示。
剩余变量在约束方程中的系数为-1,在目标函数中的系数为0,人工变量在约束方程中的系数为1,在目标函数中的系数为是一任意大正数,以M表示之。在求最大值的目标函数中,M取负号;在求最小值的目标函数中,M取正号。
剩余变量一般用来表示决策要求的某一最低标准超过要求的量,人工变量仅为了单纯形法在运算上方便,无其它特殊意义。
3.“=”类型的约束条件
变换的方法:引入人工变量,人工变量在约束方程中的系数为1,在目标函数中的系数为任意大的正数M。在求最大值的目标函数中,M取负号;在求最小值的目标函数中,M取正号。
三、模型变换方法归纳
约束条件类型
变换方法
对于约束条件
对于目标函数
≤
+S
+0·S
≥
-S+A
求max时,+0·S-MA
求min时,+0·S+MA
=
+A
求max时,-MA
求min时,+MA
表中,S为松弛变量或剩余变量,A为人工变量,M为一任意大的正数。
单纯形法
从一个初始的基本可行解出发,沿着不断改进目标函数值的方向进行迭代,经过若干基本可行解,直到得出最优解。
计算顺利进行的保证条件:
最优性条件:它保证每次变动不会得到更差的解
可行性条件:它保证每次变动仍是基本可行解
可行域是不变的