金融学院管理运筹学线性规划与单纯型法

管理运筹学,线性规划与单纯型法,第二讲,5/20/2020,3,由实际问题引出数学模形。,1.确定决策变量:设生产A,B分别为x1,x2,2.确定目标函数:,3.确定约束条件:,一、LP问题的基本概念,5/20/2020,4,典型的LP问题:,一、LP问题的基本概念,5/20/2020,5,用向量符号表示为:,用向量和矩阵表示为:,一、LP问题的基本概念,5/20/2020,6,1.基、基向量、基变量、非基变量,设A为约束方程组的mn阶系数矩阵，其秩为m，B是A中的一个m阶满秩子矩阵，称B为LP问题的一个基。B中每一个列向量称为基向量，对于的变量xj为基变量，其余的变量称为非基变量。,一、LP问题的基本概念,5/20/2020,7,1.基、基向量、基变量、非基变量,一、LP问题的基本概念,5/20/2020,8,满足约束方程(包括非负约束)的所有解，称为可行解。对于某组选定的基，令非基变量为0，与约束方程求得的唯一解，称为基解。,2.可行解、基解、基可行解、可行基,一、LP问题的基本概念,5/20/2020,9,基解中满足所有变量非负约束的解，称为基可行解。,2.可行解、基解、基可行解、可行基,与基可行解对应的基称为可行基。,一、LP问题的基本概念,5/20/2020,10,概念练习:找出下列LP问题的全部基解。,一、LP问题的基本概念,5/20/2020,11,一、LP问题的基本概念,5/20/2020,12,1.连线:,二、重要定理与引理,在n维Euclid空间中，点X与Y连线上的点，是指如下形式的点T:,当跑遍区间0,1时,相应的点T的集合就构成点X与Y之间的连线。,5/20/2020,13,2.凸集:,一个由n维点所构成的集合K，如果对于K中任意两点X,YK，恒有:,则n维点集K称为凸集，即K中任意两点的连线上的点也在K中。,3.凸组合:,假定有k个n维Euclid空间的点,它们的凸组合是指如下形式的点X:,特别，两个点X与Y的凸组合，叫做它们连线上的点。,二、重要定理与引理,5/20/2020,14,4.顶点:,设K是凸集，点XK；若对K中任何两个不同的点X,Y，以下等式恒不成立:,就称X为凸集K的顶点。换句话说，凸集的顶点，就是不在凸集中任意两点连线上的点。,二、重要定理与引理,5/20/2020,15,定理1.若LP问题的可行域非空,则可行域为凸集,定理2.LP问题的基可行解X对应LP问题可行域的顶点,定理3.若LP问题有最优解，则一定存在至少一个基可行解为最优解,二、重要定理与引理,LP问题的标准型，见P20,5/20/2020,16,(1)列初始单纯形表,三、单纯形法的计算步骤,5/20/2020,17,(2)从一个基可行解转换为相邻的另一个基可行解,不失一般性，设初始基可行解中的前m个为基变量，,设单位矩阵的列向量为Pi，增广矩阵中单位矩阵以外的某个列向量为Pj，则Pj可以成为Pi的线性表达：,三、单纯形法的计算步骤,5/20/2020,18,两式相加：,三、单纯形法的计算步骤,对于一个正数：,5/20/2020,19,除了X(0)，还有其他解吗？,只需：,问题：X(1)是基可行解吗？,三、单纯形法的计算步骤,5/20/2020,20,要使X(1)成为基可行解，必须满足：,且，至少一个等式成立！,显然，对于小于等于0的aij，上述不等式无条件成立；对于大于0的aij，则令：,三、单纯形法的计算步骤,5/20/2020,21,以上的系数矩阵的初等行变换，成为换基变换；如果仅且变换一个基变量，称对应的两个基可行解为相邻的基可行解。对应的顶点称为相邻的顶点，简称邻点。,三、单纯形法的计算步骤,5/20/2020,22,将X(0),X(1)分别代入目标函数：,(3)最优性判断,三、单纯形法的计算步骤,5/20/2020,23,三、单纯形法的计算步骤,5/20/2020,24,【例】用单纯型法解下列LP问题：,用矩阵形式表示为：,四、应用举例,5/20/2020,25,首先构造初始单纯型表如下：,2,1,四、应用举例,5/20/2020,26,2,1,四、应用举例,5/20/2020,27,2,1,四、应用举例,5/20/2020,28,-1/3,1/3,第一次迭代结束,四、应用举例,5/20/2020,29,-1/3,1/3,四、应用举例,5/20/2020,30,-1/2,-1/4,四、应用举例,5/20/2020,31,化为标准形式：,五、单纯型法的进一步讨论人工变量法(大M法),【例】用单纯型法求解下列LP问题：,5/20/2020,32,构造初始单纯型表：,-3-2M,4M,-M,1,五、单纯型法的进一步讨论人工变量法(大M法),5/20/2020,33,第1次迭代：,-3+6M,-4M,3M,1+4M,五、单纯型法的进一步讨论人工变量法(大M法),5/20/2020,34,第2次迭代：,-M-3/2,-M+1/2,3/2,3,五、单纯型法的进一步讨论人工变量法(大M法),5/20/2020,35,第3次迭代：,-M+3/4,-M+1/4,-9/2,-3/4,五、单纯型法的进一步讨论人工变量法(大M法),5/20/2020,36,同样题目,六、单纯型法的进一步讨论两阶段法,为了保证人工变量为0，可讲目标函数设为：,5/20/2020,37,构造初始单纯型表：,-2,4,-1,1,六、单纯型法的进一步讨论两阶段法,5/20/2020,38,第1次迭代：,6,-4,3,4,六、单纯型法的进一步讨论两阶段法,5/20/2020,39,第2次迭代：,-1,-1,0,0,即，当X(1)=(1,3,0,0,0,0,0)时，可使目标函数x6+x7取得最小，当x6=x7=0时,六、单纯型法的进一步讨论两阶段法,5/20/2020,40,上述取得最优的单纯型迭代中止的表，等价于一个约束方程组I：,而约束方程组I又等价于约束方程组II：,故，构造新的初始单纯型表如下：,六、单纯型法的进一步讨论两阶段法,5/20/2020,41,六、单纯型法的进一步讨论两阶段法,5/20/2020,42,第1次迭代：,3/2,3,六、单纯型法的进一步讨论两阶段法,5/20/2020,43,第1次迭代：,-9/2,-3/4,六、单纯型法的进一步讨论两阶段法,5/20/2020,44,七、单纯型法解的讨论,补充定理1.如果LP问题有最优解，则基可行解中必有最优解。,补充定理2.若X(1),X(2),.,X(K)皆为某LP问题的最优解，那么它们的凸组合也是该LP问题的最优解。,补充定理3.若LP问题的可行域有界，而它的基可行解中的所有最优解为:X(1),X(2),.,X(K),那么它们的所有凸组合包括了该LP问题的所有最优解。(证明略),以下给出三个补充定理，可看作是求解线性规划问题的基本依据。,5/20/2020,45,情况1:唯一最优解,只需非基变量的检验数全为负，且基变量中不含人工变量，该解即为唯一最优解。,情况2:无解,1.当非基变量的检验数全为负，且基变量中含有人工变量，则该LP问题无解。2.可行域为空集。,七、单纯型法解的讨论,5/20/2020,46,情况3:解无界,对于某个正检验数，其对应的Pj有非正的分量，该LP问题的解无界。,七、单纯型法解的讨论,5/20/2020,47,看以下例子:,请同学们用图解加以验证，加深印象。,七、单纯型法解的讨论,5/20/2020,48,情况4:多重最优解-无穷最优解,存在非基变量的检验数为0，该LP问题存在多重最优解。,七、单纯型法解的讨论,5/20/2020