运筹学复习提要.pptVIP

5. 掌握MATLAB求解下列线性规划问题的程序： f=[-3 -2];a=[-1 2;3 2];b=[4 14];aeq=[1 -1;1 1]; beq=[3 5];lb=zeros(2,1); [x,fval,exitflag,output,lambda]=linprog(f,a,b,aeq,beq,lb) 6. 网络分析 （1） 网络最大流问题 现通过一实例来说明网络最大流的定解问题的建立。 例1：网络图上标有各分段的容量，问应如何确定从v0到v6的最大流。 6. 网络分析 （1） 网络最大流问题 （1） 网络最大流问题 内结点流入量等于流出量： x1 -x4-x5 =0 x3 -x6-x7 =0 x2 +x5+x6 -x8-x9 =0 x4 +x9+x10-x11 =0 x7+x8 -x10 -x12=0 (6.5) 下面分析一下上述条件： 不难看到从（6.2）式可推出（6.3）式，所以（6.3）式可不要。将（6.5）式中的几等式都有相加，可得（6.4）式，所以（6.4）式也可不要。 （1） 网络最大流问题 (6.5) 这样约束条件只有（6.1)式、 （6.2）式和（6.5)式，通常将（6.5)式写成矩阵形式：aeq*x=beq，其中： （2） 网络最短距离的Floyd（弗洛伊德）算法 现在给出网络最短路的Froyd算法： (1) d1=w , (w为所给网络的n阶权矩阵) (2) dk=(dkij)n×n ，k=2，3，……，p。 其中dkij=min [d(k-1)is+d(k-1)sj]，i,j＝l，2，…，n 1≤s≤n 计算次数P的确定： (1) 当 wij≥0时，p由下式确定: p ≥ ln(n-1)/ln(2) 这样的dp就确定了网络各点间的最短距离。 （2） 网络最短距离的Floyd（弗洛伊德）算法 (2) 在其他情况下，如果出现dk＝d(k-1)或dk=d(k-1)’时，可取p=k。 按上述终止原则所得到的矩阵dp，就是所给网络的距离矩阵，它确定了网络各点间的最短路长，在出现dk＝d(k-1)’的情况时，要检查一下dk的第一行，是否是点1到各点的最短距离(可参照网络图捡查一点就行)，如果是，就取dp=dk为距离矩阵。 这里只给出了Floyd算法的计算方法和步骤。 具体操作方法将在例题中分别说明。 LP的几个概念 （1）可行解、可行域、最优解 （2）线性规划的解有4种形式： 唯一最优解、多重解、无界解、无可行解 （3）凸集、凸组合、极点 （4）基、基向量、非基向量、基变量、非基变量 （5）基本最优解、可行基 、最优基 （6）几个解的关系 线性规划的基本定理 【定理1.1】 若线性规划可行解K非空,则K是凸集。 【定理1.2】线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解。 【定理1.3】若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上到达,最优解就是极点的坐标向量。 2. LP的求解 （1）图解法 （2）单纯形法 单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表4.1）。 计算步骤： [Step1] 求初始基可行解: 列出初始单纯形表，求出检验数λj （j＝１，２，…，n） 。其中基变量的检验数必为零； [Step2] 判断： （a）若λj≤０（j＝１，２，…，n）得到最解； （b）某个λk0且aik≤０（i=1，2,…,m）则线性规划具有无界。 （c）若存在λk0且aik (i=1,…,m)不全非正，则进行换基； 第Ｌ个比值最小 ，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。aLk为主元素； (c）求新的基可行解：用初等行变换方法将aLk 化为１,k列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。 （b）选出基变量 ，求最小比值： [Step3] 换基： （a）选进基变量 设λk=