1.4线性规划单纯形大M法及2阶段经典运筹学

,上堂课主要内容:,1.若（LP）问题有可行解，则可行域是一个凸多边形,2.若（LP）问题有最优解，则最优解一定可以在凸多边形的某个顶点达到,4.基本可行解的个数是有限的,3.顶点与基本可行解是一一对应的,若（LP）问题有最优解，则最优解一定可以在某个基本可行解达到,找最优解可从一个基本可行解入手，通过某种方法，调整基变量，转到另一个基本可行解，并使目标函数值不断增大，通过有限次的迭代就能找到最优解,单纯形法：,B的典则形式：,取一可行基B，,E,0,常数项,初始单纯形表：,E,0,常数项,0,最优值,最优单纯形表,单纯形法的理论证明：,r(A)=m,假定,1、问题的可行解域非空,2、所有的基本可行解非退化,3、已找到一个初始基本可行解,可得一个初始基本可行解,不可行,1.4.4寻找初始基本可行解,一、两阶段法,基本思路：通过引进人工变量，构造一个辅助线性规划问题，该线性规划问题明显有一个基本可行解，通过对该问题求最优解来得到原问题的一个基本可行解,做辅助线性规划问题:,2、（2）的目标函数值S有上界，,3、（2）有最优值S*,(1),(2),定理：若辅助线性规划问题（2）的最优值S*0,则原线性规划问题（1）无可行解，因此无最优解,(1),(2),反证：,若不然，原问题（1）有可行解,矛盾,定理：若辅助线性规划问题（2）的最优值S*=0,(1),(2),因为S*=0,可证X是基本可行解,解：做辅助线性规划问题,不是典则形式,最优值S*=0,得原问题的一个基本可行解,X=（1/2,0,1/4,0,0),为原问题的最优解,最优值Z=-31/4,1-16-10102,1120-1011,208-1-100S+3,-50210000Z,0-24-111-11,1120-1011,0-24-110-2S+1,05-110-505Z+5,01/211/41/41/4-1/41/4,1201/2-3/21/23/21/2,00000-1-1S+0,01/20-11/49/411/49/4Z+31/4,01/20-11/49/411/49/4Z+31/4,最优解,X*=（1/2,0,1/4,0,0,0,0),解：做辅助线性规划问题,340-10S+12,32000Z,211002,340-1112,-50-4-10S+4,-10-200Z-4,211002,-20-4-114,辅助线性规划问题的最优解S=-40,且M充分大,1、若问题（2）有最优值,2、若问题（2）无界,练习：,单纯形法假定：,1、问题的可行解域非空,2、所有的基本可行解非退化,3、已找到一个初始基本可行解,退化解：基本可行解中某一基变量取零值,后果：在迭代过程中可能出现死循环,1.5退化、循环和防止循环的方法,解及目标函数值未变,退化解,0,0,=表1,出现循环,死循环,退化,解及目标函数值未变，,未出现循环,1,1,出现退化的原因：,在确定出基变量时，,有两个或两个以上的值相同,方法二：摄动法,避免循环的方法：,方法一；勃兰特法（Bland,1977）,方法一：勃兰特法,方法与单纯刑法相似，但入基变量和出基变量的确定方法不同,具体做法如下：,当按规则计算比值时，若存在几个i同时达到最小，取这些i对应的基变量中下标最小的基变量为出基变量,（1）入基变量的确定：,可以证明，用此方法不会产生循环,目标函数上升较慢,选取i0中下标最小的检验数k所对应的非基变量xk为入基变量,（2）出基变量的确定：,最优解,方法二：摄动法,基本思想：在各约束方