金融学院-管理运筹学-02-线性规划与单纯型法.pptx
- 文档编号:14607153
- 上传时间:2023-06-25
- 格式:PPTX
- 页数:50
- 大小:424.47KB
金融学院-管理运筹学-02-线性规划与单纯型法.pptx
《金融学院-管理运筹学-02-线性规划与单纯型法.pptx》由会员分享,可在线阅读,更多相关《金融学院-管理运筹学-02-线性规划与单纯型法.pptx(50页珍藏版)》请在冰点文库上搜索。
管理运筹学,6/25/2023,1,线性规划与单纯型法,第二讲,6/25/2023,2,由实际问题引出数学模形。
1.确定决策变量:
设生产A,B分别为x1,x2,2.确定目标函数:
3.确定约束条件:
一、LP问题的基本概念,6/25/2023,3,典型的LP问题:
一、LP问题的基本概念,6/25/2023,4,用向量符号表示为:
用向量和矩阵表示为:
一、LP问题的基本概念,6/25/2023,5,1.基、基向量、基变量、非基变量,设A为约束方程组的mn阶系数矩阵,其秩为m,B是A中的一个m阶满秩子矩阵,称B为LP问题的一个基。
B中每一个列向量称为基向量,对于的变量xj为基变量,其余的变量称为非基变量。
一、LP问题的基本概念,6/25/2023,6,1.基、基向量、基变量、非基变量,一、LP问题的基本概念,6/25/2023,7,满足约束方程(包括非负约束)的所有解,称为可行解。
对于某组选定的基,令非基变量为0,与约束方程求得的唯一解,称为基解。
2.可行解、基解、基可行解、可行基,一、LP问题的基本概念,6/25/2023,8,基解中满足所有变量非负约束的解,称为基可行解。
2.可行解、基解、基可行解、可行基,与基可行解对应的基称为可行基。
一、LP问题的基本概念,6/25/2023,9,概念练习:
找出下列LP问题的全部基解。
一、LP问题的基本概念,6/25/2023,10,一、LP问题的基本概念,6/25/2023,11,1.连线:
二、重要定理与引理,在n维Euclid空间中,点X与Y连线上的点,是指如下形式的点T:
当跑遍区间0,1时,相应的点T的集合就构成点X与Y之间的连线。
6/25/2023,12,2.凸集:
一个由n维点所构成的集合K,如果对于K中任意两点X,YK,恒有:
则n维点集K称为凸集,即K中任意两点的连线上的点也在K中。
3.凸组合:
假定有k个n维Euclid空间的点,它们的凸组合是指如下形式的点X:
特别,两个点X与Y的凸组合,叫做它们连线上的点。
二、重要定理与引理,6/25/2023,13,4.顶点:
设K是凸集,点XK;若对K中任何两个不同的点X,Y,以下等式恒不成立:
就称X为凸集K的顶点。
换句话说,凸集的顶点,就是不在凸集中任意两点连线上的点。
二、重要定理与引理,6/25/2023,14,定理1.若LP问题的可行域非空,则可行域为凸集,定理2.LP问题的基可行解X对应LP问题可行域的顶点,定理3.若LP问题有最优解,则一定存在至少一个基可行解为最优解,二、重要定理与引理,LP问题的标准型,见P20,6/25/2023,15,
(1)列初始单纯形表,三、单纯形法的计算步骤,6/25/2023,16,
(2)从一个基可行解转换为相邻的另一个基可行解,不失一般性,设初始基可行解中的前m个为基变量,,设单位矩阵的列向量为Pi,增广矩阵中单位矩阵以外的某个列向量为Pj,则Pj可以成为Pi的线性表达:
三、单纯形法的计算步骤,6/25/2023,17,两式相加:
三、单纯形法的计算步骤,对于一个正数:
6/25/2023,18,除了X(0),还有其他解吗?
只需:
问题:
X
(1)是基可行解吗?
三、单纯形法的计算步骤,6/25/2023,19,要使X
(1)成为基可行解,必须满足:
且,至少一个等式成立!
显然,对于小于等于0的aij,上述不等式无条件成立;对于大于0的aij,则令:
三、单纯形法的计算步骤,6/25/2023,20,以上的系数矩阵的初等行变换,成为换基变换;如果仅且变换一个基变量,称对应的两个基可行解为相邻的基可行解。
对应的顶点称为相邻的顶点,简称邻点。
三、单纯形法的计算步骤,6/25/2023,21,将X(0),X
(1)分别代入目标函数:
(3)最优性判断,三、单纯形法的计算步骤,6/25/2023,22,三、单纯形法的计算步骤,6/25/2023,23,【例】用单纯型法解下列LP问题:
用矩阵形式表示为:
四、应用举例,6/25/2023,24,首先构造初始单纯型表如下:
2,1,四、应用举例,6/25/2023,25,2,1,x1,四、应用举例,6/25/2023,26,2,1,x1,四、应用举例,6/25/2023,27,-1/3,1/3,第一次迭代结束,四、应用举例,6/25/2023,28,-1/3,1/3,x2,四、应用举例,6/25/2023,29,-1/2,-1/4,四、应用举例,6/25/2023,30,化为标准形式:
五、单纯型法的进一步讨论人工变量法(大M法),【例】用单纯型法求解下列LP问题:
6/25/2023,31,构造初始单纯型表:
-3-2M,4M,-M,1,五、单纯型法的进一步讨论人工变量法(大M法),6/25/2023,32,第1次迭代:
-3+6M,-4M,3M,1+4M,五、单纯型法的进一步讨论人工变量法(大M法),6/25/2023,33,第2次迭代:
-M-3/2,-M+1/2,3/2,3,五、单纯型法的进一步讨论人工变量法(大M法),6/25/2023,34,第3次迭代:
-M+3/4,-M+1/4,-9/2,-3/4,五、单纯型法的进一步讨论人工变量法(大M法),6/25/2023,35,同样题目,六、单纯型法的进一步讨论两阶段法,为了保证人工变量为0,可讲目标函数设为:
6/25/2023,36,构造初始单纯型表:
-2,4,-1,1,六、单纯型法的进一步讨论两阶段法,6/25/2023,37,第1次迭代:
6,-4,3,4,六、单纯型法的进一步讨论两阶段法,6/25/2023,38,第2次迭代:
-1,-1,0,0,即,当X
(1)=(1,3,0,0,0,0,0)时,可使目标函数x6+x7取得最小,当x6=x7=0时,六、单纯型法的进一步讨论两阶段法,6/25/2023,39,上述取得最优的单纯型迭代中止的表,等价于一个约束方程组I:
而约束方程组I又等价于约束方程组II:
故,构造新的初始单纯型表如下:
六、单纯型法的进一步讨论两阶段法,6/25/2023,40,六、单纯型法的进一步讨论两阶段法,6/25/2023,41,第1次迭代:
3/2,3,六、单纯型法的进一步讨论两阶段法,6/25/2023,42,第1次迭代:
-9/2,-3/4,六、单纯型法的进一步讨论两阶段法,6/25/2023,43,七、单纯型法解的讨论,补充定理1.如果LP问题有最优解,则基可行解中必有最优解。
补充定理2.若X
(1),X
(2),.,X(K)皆为某LP问题的最优解,那么它们的凸组合也是该LP问题的最优解。
补充定理3.若LP问题的可行域有界,而它的基可行解中的所有最优解为:
X
(1),X
(2),.,X(K),那么它们的所有凸组合包括了该LP问题的所有最优解。
(证明略),以下给出三个补充定理,可看作是求解线性规划问题的基本依据。
6/25/2023,44,情况1:
唯一最优解,只需非基变量的检验数全为负,且基变量中不含人工变量,该解即为唯一最优解。
情况2:
无解,1.当非基变量的检验数全为负,且基变量中含有人工变量,则该LP问题无解。
2.可行域为空集。
七、单纯型法解的讨论,6/25/2023,45,情况3:
解无界,对于某个正检验数,其对应的Pj有非正的分量,该LP问题的解无界。
七、单纯型法解的讨论,6/25/2023,46,看以下例子:
请同学们用图解加以验证,加深印象。
七、单纯型法解的讨论,6/25/2023,47,情况4:
多重最优解-无穷最优解,存在非基变量的检验数为0,该LP问题存在多重最优解。
七、单纯型法解的讨论,6/25/2023,48,八、算法的有限步中止,特别地,指迭代循环的中止。
按最小比值来确定出基变量时,有时会出现多个相同的最小值-,从而有下一轮迭代中,基可行解会出现一个或多个基变量=0解,这种情况称为解的退化。
退化解的出现,是因为模型中存在多余的约束。
当存在退化解时,就可能出现迭代循环,尽管可能性很小。
6/25/2023,49,本章结束,6/25/2023,50,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 金融学院 管理 运筹学 02 线性规划 单纯