流的费用.ppt

算法设计与分析 授课教师：王秋芬 办公地点：7307 Email: w_qiufen@163.com 学习要点 理解线性规划算法模型 掌握解线性规划问题的单纯形算法 理解网络与网络流的基本概念 掌握网络最大流的增广路算法 掌握网络最小费用流的消圈算法 线性规划问题和单纯形算法 线性规划问题及其表示 一般线性规划问题可表示为如下形式： s.t. 变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解。 所有可行解构成的集合称为线性规划问题的可行区域。 使目标函数取得极值的可行解称为最优解。 在最优解处目标函数的值称为最优值。 有些情况下可能不存在最优解。 根本没有可行解，可行区域为空集； 目标函数没有极值，目标函数值无界。 标准线性规划问题描述 将一般线性规划问题转化为标准型规划问题的方法 一般线性规划形式中目标函数如果是求极小值的，即 那么，令 ，则， 。 右端常数项如果小于零，则不等式两边同乘以（-1），将其变成大于零；同时改变不等号的方向，保证恒等变形。如2x1+x2≥－6，－2x1－x2≤6。 约束条件为大于等于约束时，则在不等式左边减去一个新的非负变量将不等式约束改为等式约束。如3x1－2x2≥12，3x1－2x2－x3＝12，x3≥0； 约束条件为小于等于约束时，则在左边加上一个新的非负变量将不等式约束改为等式约束。如x1－2x2≤8，x1－2x2＋x3＝8，x3≥0； 无约束的决策变量x，即可正可负的变量，则引入两个新的非负变量x’和x”，令x=-x’-x”，其中x’≥0，x”≥0，将x代入线性规划模型。 决策变量x小于等于0时，令x’＝－x，显然x’≥0，将x代入线性规划模型。 在(3)~(6)中引入的新的非负变量称为松弛变量。 标准型线性规划问题的单纯形算法 单纯形法 是指1947年数学家George Dantzing(乔治·丹捷格)发明的一种求解线性规划模型的一般性方法。 约束标准型线性规划问题 为了便于讨论，先考察一类特殊的标准形式的线性规划问题。在这类问题中，每个等式约束条件中均至少含有一个正系数的变量，且这个变量只出现在一个约束条件中。将每个约束条件中这样的变量作为非0变量来求解该约束方程。这类特殊的标准形式线性规划问题称为约束标准型线性规划问题。 基本概念： 基本变量：每个约束条件中的系数为正且只出现在一个约束条件中的变量。 非基本变量：除基本变量外的变量全部为非基本变量。 基本可行解：满足标准形式约束条件的可行解称为基本可行解。由此可知，如果令n-m个非基本变量等于0，那么根据约束条件求出m个基本变量的值，它们组成的一组可行解为一个基本可行解。 线性规划基本定理 定理1（最优解判别定理）若目标函数中关于非基本变量的所有系数（以下称检验数）小于等于0，则当前基本可行解就是最优解。 定理2（无穷多最优解判别定理）若目标函数中关于非基本变量的所有检验数小于等于0，同时存在某个非基本变量的检验数等于0，则线性规划问题有无穷多个最优解。 定理3（无界解定理）如果某个检验数cj大于0，而xj对应的列向量中所有基本变量的系数a1j,a2j,…,amj都小于等于0，则该线性规划问题有无界解。 约束标准型线性规划问题的单纯形算法 步骤1：找出基本变量和非基本变量，将目标函数由非基本变量表示，建立初始单纯形表如表7-1所示。 表7-1 初始单纯形表1 步骤2；判别、检查目标函数的所有系数，即检验数cj(j=1,2,…,n)。 （1）如果所有的cj≤0，则已获得最优解，算法结束。 （2）若在检验数cj中，有些为正数，但其中某一正的检验数所对应的列向量的各分量均小于等于0，则线性规划问题无界，算法结束。 （3）若在检验数cj中，有些为正数且它们所对应的列向量中有正的分量，则转步骤3。 （3）若在检验数cj中，有些为正数且它们所对应的列向量中有正的分量，则转步骤3。 步骤3：选入基变量。在所有cj＞0的检验数中选取值最大的一个，记为ce，其对应的非基变量为xe，对应的列向量为[a1e,a2e,…,ame]T，称为入基列。 步骤4：选离基变量。选取“常数列元素/入基列元素”正比值的最小者所对应的基本变量为离基变量，即 ，选取基本变量xk为离基变量。 步骤5：换基变换（转轴变换）。在单纯形表上将入基变量和离基变量互换位置，并按照式如下公式进行各元素的变换后得到一张新的单纯形表。转步骤2。 对应入基列位置元素=-原入基列元素/交叉位置元素（不包括交叉位置）。 对应离基行位置元素=原离基行元素/交叉