线性规划与单纯形法

上传人:沈*** 文档编号:243958887 上传时间:2024-10-01 格式:PPT 页数:71 大小:380KB
收藏 版权申诉 举报 下载
线性规划与单纯形法_第1页
第1页 / 共71页
线性规划与单纯形法_第2页
第2页 / 共71页
线性规划与单纯形法_第3页
第3页 / 共71页
资源描述:

《线性规划与单纯形法》由会员分享,可在线阅读,更多相关《线性规划与单纯形法(71页珍藏版)》请在装配图网上搜索。

1、单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,第一章 线性规划与单纯形法,线性规划是运筹学的一个重要分支。,1947,年丹捷格提出了一般线性规划问题求解的方法,——,单纯形法。,,知识点:,,线性规划问题的有关概念,,LP,(,linear programming,)-,SLP,(,Standard ~,),的转换,,用单纯形法求解线性规划问题,,§1,线性规划问题及其数学模型,,1.1,线性规划问题,,提出:例,1,(,P8,)、,例,2,(,P9,),,例,1【,经典例题,】:,某工厂在计划期内要安排生产,I,、,II,两种产品。已

2、知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗,如,表,1,-,1,所示。该工厂每生产一件产品,I,可获利,2,元,每生产一件产品,II,可获利,3,元。问,I,、,II,两种产品的产量各为多少时,使该工厂获取最大利润?,,,产品,I,产品,II,,设备,1,2,8台时,原材料,A,4,0,16kg,原材料,B,0,4,12kg,表,1-1,,分析,,设,x1,,,x2,分别表示在计划期内产品,I,、,II,的产量。,,I,II,汇总,约束条件,目标,设备,1,2,x,1,+2,x,2,≤,8台时,,原材料,A,4,0,4,x,1,≤,16kg,,原材料,B,0,4,4,x,2,

3、≤,12kg,,产量,x,1,x,2,,,,单位利润,2,3,,,,利润,2,x,1,3,x,2,2,x,1,+3,x,2,,max,,建模,,该生产计划问题可用数学模型表示为:,,目标函数,max z,=,2x,1,+,3x,2,,约束条件,x,1,+,2x,2,≤8,,4x1 ≤16,,4x,2,≤12,,x,1,,,x,2,≥0,,性质:线性规划是一个线性的条件极值问题,可分为两类:,,当一项任务确定后,如何统筹安排尽量做到以最小的人力、财力、物力等资源去完成。,,已知一定数量的人力、物力、财力等资源,如何安排使用它们使完成的任务(或创的价值、实现的利润等)最多。,,定义:

4、对于求取一组变量,X,j,(,j,=,1,,,2,,,3…n),使得它满足线性约束条件的目标函数取得极值的一类最优化问题。,,,特征(,P10,),,每个问题都用一组,决策变量,(,x1,,,x2,,,…,,,xn,,)表示某一方案;这组决策变量的值就代表一个具体方案。一般这些变量取值是,非负的,。,,存在一定的,约束条件,,这些约束条件可以用一组,线性等式或线性不等式,来表示。,,都有一个要求达到的,目标,,它可用决策变量的,线性函数,(称为目标函数)来表示。按问题的不同,要求目标函数实现,最大化或最小化,。,,满足以上三个条件的数学模型称为,线性规划,的数学模型。,,,线性规划数学模型的一

5、般形式,,,目标函数,,,max,(,min,),z,=,c1x1+ c2x2 +…,cnxn,(1.1),,约束条件:,a11x1 + a12x2 + …+ a1nxn ≤(=, ≥)b1,,a21x1 + a22x2 + …+ a2nxn ≤(=, ≥)b2,,… … … … … … … … … … … … … (1.2),,am1x1 +am2x2 + …+,amnxn,≤(=, ≥),bm,,x1, x2, …,xn,≥0 (1.3),,,方程(,1.1,)称为目标函

6、数;,,(,1.2,)、(,1.3,)称为约束条件;,,(,1.3,)也称为变量的非负约束条件。,,1.2,图解法,可行解,可行解集,可行域,,图解法的步骤,,建立平面直角坐标系,,画出可行域,,作出目标函数等值线,求最优解,,唯一最优解、无穷多最优解、无界解、无可行解,,例,1,的图解法,在以,x1,、,x2,为坐标轴的直角坐标系中,非负条件,x1,,,x2 ≥0,是指第一象限。例,1,的每个约束条件都代表一个,半平面,。例,1,的所有约束条件为半平面交成的区域(见图中的阴影部分) 。阴影区域中的每一个点(包括边界点)都是这个线性规划问题的解(称,可行解,)。此阴影区域是例,1,的线性规划问

7、题的解集合,称为,可行域,。,,在这个坐标平面上,目标函数,z,=,2 x1,+,3 x2,可表示以,z,为参数、-,2/3,为斜率的一族平行线:,x2,=-(,2/3,),x1,+,z/3,。位于同一直线上的点,具有相同的目标函数值,因而称它为,“,等值线,”,。当,z,值由小变大时,直线,x2,=-(,2/3,),x1,+,z/3,沿其法线方向向右上方移动。当移动到,Q2,点时,使,z,值在可行域边界上实现最大化。这就得到了例,1,的最优解,Q2,,,Q2,点的坐标是(,4,,,2,)。于是可计算出,z,=,14,。,,习题,1,图解法解下列线性规划问题,(1) MaxZ =3x,1,

8、+4x,2,,S.T,,- 2x,1,+x,2,≤1,,- x,1,+2x,2,≤ 4,,2x,1,+x,2,≤6,,x,1,- x,2,≤1,,X,1,,x,2,≥0,(2) MinZ =5x,1,-6x,2,,S.T,,x,1,+2x,2,≤ 4,,3x,1,+2x,2,≤6,,x,1,-2 x,2,≤0,,X,1,,x,2,≥0,,,1.3,线性规划问题的标准型式,线性规划问题的完整标准型式,,向量和矩阵符号表达式,,矩阵表达式,,线性规划问题的标准化,,目标函数的标准化:,MinZ=CX MaxZ’ =,-,CX ( Z=,-,Z’),,负右端系数的转换:当,b,i,≤0

9、,时,两端同乘(-,1,),,约束条件的标准化:对于“,≤“,型,则在不等式的左端加一非负变量(松弛变量),对于“,≥“,型,则在不等式的左端减一非负变量(剩余变量)。,,决策,变量的转换: 当,x,j,≤0,时,令,x,j,/,=-,x,j,,,则,x,j,/,≥0,; 如,x,j,无符号限制,则令,x,j,=,x,j,/,-,x,j,“,,,x,j,/,,,x,j,“≥ 0,,例,3,:,将下述线性规划模型(例,1,)化为标准型,,目标函数,max,z,=,2,x,1,+,3,x,2,,,约束条件,x,1,+,2,x,2,≤8,,4,x,1,≤16,,4,x,2,≤12,,,x,1,,,x

10、,2,≥0,,解:根据题意,,用,x4,-,x5,,替换,x3,替换,其中,x4,,,x5 ≥0,,在第一个约束不等式,≤,号的左端加入松弛变量,x6,,在第二个约束不等式,≥,号的左端加入剩余变量,x7,,令,z′,=-,z,令,把求,minz,改为求,maxz,′,。,,得标准型,,,目标函数,max z′,=,x1,-,2x2,+,3,(,x4,-,x5,),,约束条件,x,1,+,x,2,,+(,x,4,,-,x,5,,) +,x,6,,=,7,,x,1,-,x,2,,+(,x,4,,-,x,5,,) -,x,7,,=,2,,,-,3x,1,+,x,2,,+,2,(,

11、x,4,,-,x,5,,) =,5,,x,1,,,x,2,,,,x,3,,,,x,4,,,,x,5,,,,x,6,,,,x,7,≥0,,,目标函数,min,z,=-,x,1,+,2,x,2,-,3,x,2,,约束条件,,,x,1,+,x,2,+,x,3,≤7,,x,1,,-,x,2,+,x,3,≥ 2,,,-,3,x,1,,+,x,2,+,2,x,3,,=,5,,,x,1,,,x,2,≥0,,,x,3,,为无约束,,例,4,:,将下述线性规划问题化为标准型,,在各不等式中分别加上一个松弛变量,x,3,,,x,4,,,x,5,,使不等式变为等式,便得到标准型。,,目标

12、函数,max z,=,2x,1,+,3x,2,,约束条件,,,x,1,+,2x,2,,+,x,3,,=,8,,4x,1,,+,x,4,,=,16,,4x,2,,+,x,5,,=,1,,x,1,,,x,2,,,,x,3,,,,x,4,,,,x,5,≥0,,习题,2,将下列模型化成标准型,,minz,=,x,1,-,x,2,+,4x,3,,s.t,,3x,1,-,4x,3,≥-9,,-x,1,+ x,2,≥ 6,,5x,1,+ 2x,3,≤ 16,,x,1,≤ 0,x,2,≥ 0 ,x,3,无符号限制,,习题,3,将下列模型化成标准型,minz,=,x,1,-,x,2,+,3x,3,,s.t,,

13、x,1,+ x,2,,+,x,3,=10,,5x,1,-7x,2,+3 x,3,≤ -8,,X,1,+ X,2,≥,2,,x,3,≤ 18,,x,1,,≥,0,,, x,2,≤,,0, x,3,无符号限制,,习题,4,:,将下列模型化成标准型,min z,=,x,1,-,x,2,+,4x,3,,s.t,3x,1,-,4x,3,≥,-9,,,-,x,1,+x,2,,≥,6,,5x,1,+2x,3,≤ 1,,x,1,≤,,0,x,2,,≥,0,,,x,3,无符号限制,,解:令,z′,=-,z,,,x,1,/,=-,x,,,x,3,=,x,3,′,,-,x,3,“,,,,引入松弛

14、变量,x,4,,,x,6,,,剩余变量,x,5,,,并加以整理得:,,,max z ′,=,x,1,′+x,2,-,4,x,3,′,,+4x,3,″,,,s.t,x,1,′,,+,4,x,3,′,,-,4x,3,″,+,x,4,=,9,,x,1,′ +x,2,,-,x,5,,=,,6,,5x,1,′,,+2,x,3,′,,-,2x,3,“,+,x,6,,=,16,,x1 ′,,,x2,,,x3 ′,,,x3“,,,x4,,,x5,x6 ≥ 0,,习题,5,:,将下列模型化成标准型,,min z,=,x,1,-,x,2,+,3x,3,,s.t,,x,1,+x,2,+,x,3,=10,,5x

15、,1,-7x,2,+3 x,3,≤ -8,,,x,1,+,X,2,≥,2,,x,3,≤ 18,,x,1,,≥,0,,, x,2,≤,,0, x,3,无符号限制,,习题,5,解答,解,:,令,x,2,/,=-,x,2,,,x,3,=,x,3,/,-,x,3,“,,,Z=-Z,/,,,引入剩余变量,x,4,,,x,5,,,松弛变量,x,6,,,并加以整理得:,,,max z,/,= -,x,1,-,x,2,/,-,3,x,3,/,+,3x,3,“,,,s.t,,,x,1,-,x,2,/,+,x,3,/,-,x,3,“,=10,,,-,,5x,1,,-,7x,2,/,-,3 x,3,,/,+,3

16、,x,3,“,,-,x,4,=,8,,,x,1,-,x,2,/,,-,x,5,=,2,,,x,3,/,-,x,3,“,,+,x,6,=18,,x,1,,,,x,2,/,,,x,3,/,,,x,3,“,,,,x,4,,,,x,5,,,,x,6,,≥,0,,1.4,线性规划问题的解的概念,max,(或,min,),z,=,CX,,s.t AX,=,b,,X≥0,,其中,A,爲,m*n,阶矩阵,,m≤n,,,A,的秩为,m,。,,可行解,,基:A中任何一组,m,个,线性无关的列向量构成的子矩阵为B,称为该问题的一个基(,basis),,,与这些列向量对应的变量称为B的基变量(,basic va

17、riable),,,其余变量称为B的非基变量。,,基可行解:对于基B,令非变量为零,求得满足式,AX,=,b,的解,称为B对应的基本解(,basic solution);,若同时又满足式 X,≥,0,这种基本解称为基本可行解,基本可行解所对应的基称为可行基。,,最优基,,退化解,若基本可行解中某基变量为零,称其为退化解,所对应的极点为退化极点。,,例:某一,LP,问题的约束条件为,,,x1,+,x2≤1,,x1,+,2x2≤2,,x1,,,x2≥0,,几种解之间的关系,,,,可行解,基,可行解,基解,非,可行解,,§2,线性规划问题的几何意义,,2.1,基本概念,,凸集,,凸组合,,顶点,,

18、2.2,基本定理,,定理,1,线性规划问题的可行域,S,是,凸集。,,引理,1,,定理,2 X,为线性规划问题可行域,S,上极点的充要条件是,X,的正对应的系数列向量线性无关。,,引理,2,,例,5,,定理,3 X,是可行域,S,上极点的充要条件是它为基本可行解。,,,线性规划问题的所有可行解构成的集合是凸集,也可能为无界域,它们有有限个顶点,线性规划问题的每个基可行解对应可行域的一个顶点;若线性规划问题有最优解,必在某顶点上得到。,,§ 3,单纯形法,,单纯形法的基本思想:根据问题的标准型,从可行域中一个基本可行解(一个极点)开始,转换到另一个新的基本可行解,并且使目标函数值较前有所改善。经

19、过若干次这样的转换,最后得到问题的最优解或判断无最优解。,,3.0,导入单纯形法,分别用几何法与代数法求解下列线性规划问题:,,max(min) z,=,2x,1,+3x,2,,s.t x,1,+x,2,+x,3,=2,,x,2,+x,3,=1,,x,1,,,x,2,,,x,3,≥0,解:用几何法求解:,,max(min) z,=,2x,1,+3x,2,,,s.t x,1,+x,2,+x,3,=2,,x,2,+x,3,=1,,x,1,,,x,2,,,x,3,≥0,,max(min) z=2x,1,+3x,2,,s.t x,1,=1,,x,2,+x,3,=1,

20、,x,1,,x,2,,x,3,≥0,,导入单纯形法(续,1,),,用几何法求解:,,B(1,1,0),A(1,0,1),max z*=5,min z*=2,x,1,x,2,x,3,,导入单纯形法(续,2,),,用,代数法求解:,max(min) z=2x,1,+3x,2,,s.t,x,1,=1,,x,2,+x,3,=1,,x,1,,x,2,,x,3,≥0,max z=5,-3x,3,,s.t,,x,1,,=1,,,x,2,=1- x,3,,x,1,,x,2,,x,3,≥0,min z=2,+3x,2,,s.t,,,x,1,,=1,,,x,3,=1- x,2,,x,1,,x,2,,x,3,≥

21、0,最优解,,X*=(1,0,1) min z*=2,最优解,,X*=(1,1,0) max z*=5,,3.1,举例,:,例,5,求解下列线性规划问题,max z,=,1.5x,1,+2.4x,2,+0x,3,+0x,4,+0x,5,,S.t,.,,x,1,+x,2,+x,3,=100,,3x,1,+2x,2,+x,4,=190,,2x,1,+3x,2,+x,5,=240,,x,j,≥0(j=1,2,3…5),,,例,5,解答,解: 约束方程的系数矩阵为:,1,1,1 0 0,,A=(P,1,,,P,2,,,P,3,,,,P,4,,,,P,5,,)=,3,2,0 1 0,,2

22、,3,0 0 1,,初始可行基为:,1 0 0,,B,=(,P,3,,,P,4,,,,P,5,,)=,0 1 0,,0 0 1,,用非基变量表达基变量,:,,,x,3,=,100,,-,x,1,-,1x,2,,x,4,=,190,,-,3x,1,-,2x,2,(,1,。,7,),,,x,5,=,240,,-,2x,1,-,3x,2,,,,例,5,解答(续,1,),将(,1.7,)式代入目标函数得:,,,z= 0 +,1,.,5,x,1,+2.4x,2,,令非基变量为零,,,即令,x,1,=,0,,,x,2,=,0,得一个基可行解:,,x,(,0,),=(,0,0,,100,19

23、0,240,),,此时得,z,=,0,,非基变量的系数都是正数,因此将非基变量变换成基变量,目标函数的值就可能变大。,,取,x,2,为,入基变量,(一般选择,正价值系数最大的非基变量为入基变量,,而,2.4>1.5,,),,于是还要确定基变量,x,3,,,x,4,,,x,5,中的一个换出来成为非基变量。下面来确定换出变量:,,当,x,1,=0,时(先固定,x,1,是两个非基变量中的一个),,,,x,3,=,100,,-,1,x,2,≥0,,x,4,=,190,,-,2,x,2,≥0,,x,5,=,240,,-,3,x,2,≥0,,要让,x,3,,,x,4,,,x,5,非负,且有一个为,0,,,

24、,只有选择,x,2,≤80,时,,才能使,x,3,,x,4,x,5,同时非负。,(,此时,x,3,≥20>0,,,x,4,≥30>0,,,x,5,≥0),,因此只有,当,x,2,=,min(100/1,190/2,,240/3,),=80,时,,,才能使,x,3,,x,4,x,5,非负的同时,有一个原来的基变量,x,5,取值为,0,,从而可以换出来成为非基变量。其中,x,3,=20,,> 0,,,,x,4,=30,,> 0,,,,X,5,= 0,,取,X,5,为,出基变量,(所谓的,最小比值规则,),例,5,解答(续,2,),,x,2,≤100,,x,2,≤,,95,,x,2,≤,80,x,2

25、,≤80,?,,例,5,解答(续,3,),用非基变量表达基变量:,,,x,3,+x,2,=100 -x,1,x,3,=,20,,-,1/3x,1,+1/3x,5,,x,4,+2x,2,=190-3x,1,x,4,=,30,-,5/3x,1,+2/3x,5,(,1.8,),,,3x,2,=240 -2x,1,-,,x,5,x,2,=,80,,-,2,/,3x,1,- 1/3x,5,,将(,1.8,)式代入目标函数得:,,z=192-0.1x,1,-0.8x,5,,令非基变量为零,,即,x,1,=,0,,,x,5,=,0,得一个基本可行解:,x,(,1,),=(,0,,80,20,30,,0),

26、 z=192,,由于非基变量的价值系数都是负数,而,x,1,≥0,,,x,5,≥0,,,因此当,x,1,=,0,,,x,5,=,0,时,,z,取得最大值,192,。所以,,最优解,,X*= x,(,1,),=(,0,80,20,30,0),,,目标函数值,z*=192,,例,6,求线性规划问题的初始可行基:,,max z=10x,1,+3x,2,+4x,3,,s.T,,3x,1,+6x,2,+2x,3,≤19,,9x,1,+3x,2,+1x,3,≤9,,x,j,≥0(j=1,2,3),,解:引人松驰变量,x,4 ,,x,5,,,3x,1,+6x,2,+2x,3,+,x,4,,,=

27、19,,9x,1,+3x,2,+1x,3,+,x,5,=9,,,取,x,4,,,x,5,为基变量,,,初始可行基:,,,1 0,,,B=,0 1,,,初始基可行解为,:X =(0,0,0,19,9),,3.2,初始基本可行解的确定,直接观察到一个单位矩阵,可当成初始基本可行基,.,,松弛变量:对“,≤”,型,引入松驰变量,,人造基:对“,≥”,或“,=”,型,引入剩余变量和人工变量,,,3.3,最优性检验及判断准则,,用分量形式表达,,,求解的一次迭代结果為,:,,,X,i,=,b,i,/,,-,,,a,ij,/,X,j,,,(,i=1,2, …,m,),,Z=,,,c,

28、i,,,X,i,+ ,,c,j,,,X,j,,=,,,c,i,,b,i,/,-,,(,c,i,,a,ij,/,X,j,),+ ,,c,j,,,X,j,,=,,,c,i,,b,i,/,,+,,(,C,j,-,,c,i,,a,ij,/,,),X,j,,Z=,z,0,,+ ,,,j,,,,X,j,,用矩阵形式表达,标准型,max z=CX,,,s.t,AX=b,,X≥0,,A=(B,N) X=(X,B,,X,N,),T,C=,(C,B,,C,N,),代入,AX=b,得,,,B X,B,+N X,N,=b,,X,B,=,B,-1,b,-,B,-1,N,,X,N,,Z=,(C,B

29、,,C,N,),(X,B,,X,N,),T,=,C,B,,X,B,+,C,N,,X,N,,,Z=,C,B,B,-1,b,+ (,C,N,-,C,B,B,-1,N,),X,N,,,最优解的判别,:,若,x,(0),=(b,1,/,, b,2,/,, ...,b,m,/,, 0..,0,0,),为对应基,B,的一个基可行解,,,并对于一切,j=m+1,…,n,,且有,,j,≤0,(,最优性条件,).,则,x,(0),为最优解,,无穷多最优解判别,:,若,x,(0),=(b,1,/,, b,2,/,, ...,b,n,/,, 0..,0,0,),为对应基,B,的一个基本可行解,,,并对于一切,j=

30、m+1,…,n,有,,j,≤0,,而且又存在非基变量的检验数,,m+k,=0,,则线性规划问题有多重解,.,,无界解判别,:,无最优解判別,:,若,x,(0),=(b,1,/,, b,2,/,, ...,b,n,/,, 0..,0,0,),为对应基,B,的一个基可行解,,,至少有一个,,m+k,>0,,对于,I=1,2,..m,均有,a,/,I,m+k,≤ 0,则线性规划问题无最优解,.,,唯一最优解判别,,无可行解判别,,3.4,基变换,从原可行基中换一个列向量(当然要保持线性独立),得到一个新的可行基,称之为,基变换,。,,换入变量的确定,,从直观上一般选择,,j,>0,中的最大者

31、(可以任选或按最小足码选),即,max(,,j,>0)=,,k,所对应的,x,k,为换入变量。,,换出变量的确定,,Θ,=,min(,b,i,,/,a,ik,,|,a,ik,,>0)=,b,l,/,a,lk,,,这时,x,l,为换出变量。按照最小比值确定,Θ,值,称为,最小比值规则,。,,,3.5,迭代(旋转运算),,确定,x,k,为换入变量、,x,l,为换出变量后,以,a,lk,为主元素进行迭代(即用高斯消元法或称为旋转运算),把,p,k,变换为单位向量(其中第,l,个分量为,0,)。,,例,7,,§4,单纯形法的计算步骤,4.1,单纯形表,,c,j,C,1,c,2…..,c,m,c,m

32、+1,,c,m+2,….,,c,n,,b,C,B,x,B,,x,1,x,2……,x,m,,x,m+1,x,m+2…….,x,n,,C,1,,,x,1,,C,2,,x,2,,…,,…,,c,m,,x,m,1 0 …..0,a,1,m+1,,a,1,m+2,a,1, n,,,0 1 0,a,2,m+1,,a,2,m+2,a,2, n,,……….. . .. ..,,,0 0 … 1,a,m,m+1,,a,m,m+2……,a,m ,n,b,1,,b,2,,…,,..,,b,m,C,j,-z,j,0 0

33、 … 0,C,m+1,-,,,c,i,,a,i,m+1,,…,,C,n,-,,c,i,,a,i,n,,,-,,,c,i,,b,i,,4.2,单纯,形法的计算步骤,1.,找出一个初始基本可行基,建立单纯形表,,2.,检验各非基变量,x,的检验数,,j,=,c,j,-,,c,i,a,ij,,,对最大化问题,若,,j,≤0,,,j=m+1,,,..n,(,对最小化问题,若,,j,≥0,,,j=m+1,,,..n),,,则得到最优解,停止计算。否则,转入下一步,.,,3.,对最大化问题,在,,j,≥0 (,对最小化问题,,,j,≤0 ),,,j=m+1,,,..n,中, 若有一个,

34、,k,,对应的,x,k,的系数列向量,P,k,≤0,,,则问题无最优解,停止计算。否则,转入下一步,.,,4.,根据,max(,,j,≥0 )=,,k,(,对最小化问题, 按,min (,,j,≤0 )=,,k,),,,确定,x,k,为 入基变量,按最小比值判断法计算,,,Θ,=,min(,b,i,,/,a,ik,,|,a,ik,,>0)=,b,l,/,a,lk,,,,确定,x,l,为 出基变量。转下一步。,i=1,m,,单纯,形法的计算步骤(续),5.,以,a,lk,为主元素进行迭代运算。,,,a,1k,0,,,,a,2k,0,,P,K,= .

35、 .,,,a,lk,1,,. .,,,a,nk,0,,,,同时将,X,B,列中,x,l,的换为,x,k,,,,得到新的单纯形表。重复第,2~5,步,,,走到终止。,第,l,行,,§5,单纯形法的进一步讨论,5.1,人工变量法:人为地构造一个单位矩阵来充当初始可行基,再通过单纯形迭代逐步地用矩阵,A,的列向量取代这个人造基或证明原问题无最优解。,,大,M,法:在人工变量相应的一个绝对值很大,-M(M>>0,,,对于极小化问题用,+M),,,这样只要基变量中还存在人工变量,,,目标函数就不可能实现极值。,,例,8,,两阶段法,,例,9,,5.2

36、,退化,,5.3,检验数的几种表现形式,,5.4,单纯形法小结,,5.1,人工变量法,人为地构造一个单位矩阵来充当初始可行基,再通过单纯形迭代将它们逐个地从基变量中替换出来。若经过基的变换,基变量中不再含有非零的人工变量,这表示原问题有解。若在最终表中当所有,C,j,-z,j,≤ 0,,,而在其中还有某个非零人工变量,这表示无可行解。,,大,M,法,,两阶段法,,大,M,法,基本思想,:,假定人工变量在基变量中的价值系数为一个绝对值很大的,-M (M>>0,,对于极小化问题用,+M),,这样只要基变量中还存在人工变量,,,目标函数就不可能实现极值,.,,基本步骤,:,,1.,建立,LP,问题,

37、,,2. LP SLP,,3. SLP MSLP,,4.,单纯形迭代,.,,,min z=-3x,1,+x,2,+x,3,,s.t,,x,1,-2x,2,+x,3,≤11,,-4x,1,+x,2,+2x,3,≥,3,,-2x,1,+x,3,=1,x,j,≥0(j=1,2,3),例,8:,用大,M,法求解线性规划问题,,例,8,(解),解,:,标准化,: x,1,-2x,2,+x,3,+ x,4,=11,,-4x,1,+x,2,+2x,3,-,x,5,=,3 (SLP,问题,),,-2x,1,+x,3,=1,,x,j,≥0(j=1,2,

38、3,4,5),,,化成,MSLP,问题,:,,min z=-3x,1,+x,2,+x,3,+My,1,+My,2,,x,1,-2x,2,+x,3,+ x,4,,=11,,-4x,1,+x,2,+2x,3,-,x,5,+ y,1,=,3,,-2x,1,+x,3,+y,2,=1,,x,j,≥0(j=1,2,3,4,5),,y,1,y,2,≥0,,单纯形迭代,:,c,j,,-3 1 1 0 0 M M,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,,0,,M,,M,X

39、,4,,y,1,,y,2,1 -2 1 1 0 0 0,,-4 1 2 0 -1 1 0,,-2 0,1,0 0 0 1,11,,3,,1,,j,,-3+6M 1-M,1-3M,0 M 0 0,-4M,例,8,(解),,c,j,,-3 1 1

40、 0 0 M M,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,,0,,M,,1,X,4,,y,1,,x,3,3 -2 0 1 0 0,,0,1,0 0 -1 1,,-2 0 1 0 0 0,10,,1,,1,,j,,-1,1-M,0 0 M

41、0,-M-1,例,8,(解),,,,,,,,,,,,,,,,,,,c,j,,-3 1 1 0 0 M M,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,,0,,1,,1,X,4,,x,2,,x,3,3,0 0 1 -2,,0 1 0 0 -1,,-2 0 1 0 0,12,,1,,1,,

42、j,,-1,0 0 0 1 >0 >0,-2,例,8,(解),,X,*,=(4,1,9,0,0),T,Z,min,=-2,cj,,-3 1 1 0 0 M M,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,,-3,,1,,1,X,1,,x,2,,x,3,1 0 0 1/3 -2/3,,0 1 0 0

43、 -1,,0 0 1 2/3 -4/3,4,,1,,9,,j,,0 0 0 1/3,1/3,>0 >0,2,例,8,(解,),,兩阶段法,基本思想,:,,,它把,LP,问题分两阶段来处理人工变量,.,,第一阶段,:,建立,ASLP,问题并求解以判断原问题是否存在最优解,. ASLP,问题的目标函数取所有人工变量之和,,,并对目标函数取极小值,.,,第二阶段,:,利用第一阶段的最终单纯形表,,,计算,SLP,关于已知基的目标函数和检验数,,,直接构成,SLP,的初始单纯形表,,

44、,进行求解,.,,基本步骤,:,,1.,建立,LP,问题,,,2. LP SLP,,3. SLP ASLP,,4.,单纯形迭代求解,ASLP,问题的最优可行基,.,若基本变量组中含有取值大于零的人工变量,,,则,SLP,问题无可行解,.,,5.,单纯形迭代求解,SLP,问题,,例,9,用两阶段法求解下列线性规划问题,min z=-3 x,1,+x,2,+x,3,,,S.T.,,x,1,-2x,2,+ x,3,≤11,,-4x,1,+x,2,+2x,3,≥3,,-2x,1,+x,3,=1,,x,j,≥0(j=1,2,3),,,例,9(,解,),解:

45、,LP ASLP,问题,,min w=,y,1,+y,2,,x,1,-2x,2,+x,3,+ x,4,,=11,,-4x,1,+x,2,+2x,3,-,x,5,+ y,1,=,3,,-2x,1,+x,3,+y,2,=1,,x,j,≥0(j=1,2,3..5),,y,1,,y,2,≥0,思考:,,目标函数设为,min w=,3,y,1,+,4,y,2,,行,不行?,,c,j,,0 0 0 0 0 1 1,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2

46、,,0,,1,,1,X,4,,y,1,,y,2,1 -2 1 1 0 0 0,,-4 1 2 0 -1 1 0,,-2 0,1,0 0 0 1,11,,3,,1,,j,,6 -1,-3,0 1 0 0,-4,例,9(,解,),,例,9(,解,),cj,,0 0

47、 0 0 0 1 1,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,,0,,1,,0,X,4,,y,1,,x,3,3 -2 0 1 0 0 -1,,0,1,0 0 -1 1 -2,,-2 0 1 0 0 0 1,10,,1,,-1,,j,,0,-1,

48、0 0 1 0 2,1,,在最优表中,,,基变量已无人工变量,,,可进行第二阶段,.,cj,,0 0 0 0 0 1 1,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,,0,,0,,0,X,4,,x,2,,x,3,3 0 0 1 -2 2 -5,,0 1 0 0

49、 -1 1 -2,,-2 0 1 0 0 0 1,12,,1,,1,,j,,0 0 0 0 0 1 1,0,例,9(,解,),,例,9(,解,),cj,,-3 1 1 0 0,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,,0,,1,,1,X,4,,x,2,,x,3,3,0 0

50、 1 -2,,0 1 0 0 -1,,-2 0 1 0 0,12,,1,,1,,j,,-1,0 0 0 1,0,,所有检验数,大于或等于零,,,得最优表,. X,*,=(4,1,9,0,0),T,Z,min,=-2,cj,,0 0 0 0 0,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,,-3,

51、,1,,1,X,1,,x,2,,x,3,1 0 0 1/3 -2/3,,0 1 0 0 -1,,0 0 1 2/3 -4/3,4,,1,,9,,j,,0 0 0 1/3 1/3,2,例,9(,解,),,小结,,,,,是 否 否,,,,,是,唯一

52、最,,优解,LP,问题,引人松弛变量,`,人工,,变量,,,列出单纯形表,非基,变量,,检验数,,,j,≤0,对任,一,,j,>0,,有,a,ij,≤0,令,,k,=max{,,j,},,X,k,为,入基变量,对,所有,a,ik,≥0,,计算,min(,θ,i,),,=min(b,i,/ a,ik,),,=,θ,,l,,X,l,为出基变量,,换基,迭代,,1.X,k,替代,X,l,,2.,对主元行,,3.,对主元列,,4.,对其它行,,列变换,无最优解,无,可行解,基,变量含有,,非零人工变量,非基,变量检,,验数为零,多重最优解,打印,,结果,结束,,§6,应用举例,一般讲,一个经济

53、、管理问题凡满足以下条件时,才能建立线性规划模型:,,(,1,)要求解问题的,目标函数,能用数值指标来反映,且为,线性函数,;,,(,2,)存在着,多种方案,;,,(,3,)要求达到的目标是在一定,约束条件,下实现的,这些约束条件可用,线性等式或不等式,来描述。,,例,10,例,10,合理利用线材问题。现要做,100,套钢架,每套用长为,2.9m,,,2.1m,和,1.5m,的元钢各一根。已知原料长,7.4m,,,问应如何下料,使用的原材料最省。,,例,10,(解),解:采用套裁方案,可取方案为:,方案,,下料数,,长度,,I,,II,,III,,IV,,V,2.9,,2.1,,1.5,1,,

54、0,,3,2,,,1,,2,,2,1,,2,,,1,,3,合计,,料头,7.4,,0,7.3,,0.1,7.2,,0.2,7.1,,0.3,6.6,,0.8,,例,10,(解),为了得到,100,套钢架,需要混合使用各种下料方案。设第,i,种方案下料的原材料根数为,x,i,,(,i,=,1,,,2,,,3,,,4,,,5,),得数学模型为:,,min z=0 x,1,+0.1x,2,+0.2x,3,+0.3x,4,+0.8x,5,,x,1,+,,2x,2,+ x,4,=,100,,2x,3,+ 2x,4,+x,5,=,100,,3x,1,+,,x,2,+2,,x,3,+3x,5,=,100,,

55、x,i,≥0(i=1,2,3,4,5),,加入人工变量用单纯形法计算可得到结果。最优方案为,I,方案,下料,30,根,,II,方案,下料,10,根,,IV,方案,下料,50,根。,,例13,例,13,连续投资问题(课本,P42,),,,例,13,(解),解:,(1),确定变量,:以,x,iA,,,,x,i,B,,,,x,i,C,,,,x,i,D,,(,i,=,1,,,2,,,3,,,4,,,5,),分别表示第,i,年年初给项目,A,B,C,D,的投资额。它们都是待定的未知变量。,,(,2,),投资额应等于手中拥有的资金额,。,,(,3,)目标函数,,问题是要求在第五年末该部门手中拥有的资金额达

56、到最大,这个目标函数可表示为:,,Maxz,=,1.15,x,iA,+1.40,x,iB,+1.25,x,iC,+1.06,x,iD,,(,4,),数学模型,,(,5,)用单纯形法计算结果。,,例,13,(解),,,,,,,,,,,,,,,,A,B,C,D,1,2,3,4,5,,习题,P44,第,1,题(,1,)(,3,)或(,2,)(,4,),,第,2,题(,1,),,P45,第,4,题,(1),或(,2,),,第,6,题,(1),或(,2,)或(,3,)或(,4,),,P46,第,7,题,,作业,,P45,:,1.3,(,1,)、,1.4,(,2,),,P45,:,1.6,(,2,),,P46,:,1.7,、,1.9,,,

展开阅读全文
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

相关资源

更多
正为您匹配相似的精品文档

相关搜索

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!