管理运筹学之线性规划与单纯型法.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,*,廣東金融學院工商管理系,管理运筹学,10/30/2025,1,线性规划与单纯型法,第二讲,10/30/2025,2,由实际问题引出数学模形。,产品A,产品B,资源限量,劳动力,设备,原材料,9,4,3,4,5,10,360,200,300,利润元/KG,70,120,1.确定决策变量:设生产A,B分别为x,1,x,2,2.确定目标函数:,3.确定约束条件:,一、LP问题的基本概念,10/30/2025,3,典型的LP问题:,一、LP问题的基本概念,10/30/2025,4,用向量符号表示为:,用向量和矩阵表示为:,一、LP问题的基本概念,10/30/2025,5,1.基、基向量、基变量、非基变量,设,A为约束方程组的mn阶系数矩阵，其秩为m，B是A中的一个m阶满秩子矩阵，称B为LP问题的一个,基,。B中每一个列向量称为,基向量,，对于的变量x,j,为,基变量,，其余的变量称为,非基变量,。,一、LP问题的基本概念,10/30/2025,6,1.基、基向量、基变量、非基变量,一、LP问题的基本概念,10/30/2025,7,满足约束方程(包括非负约束)的所有解，称为,可行解。,对于某组选定的基，,令,非基变量为0，与约束方程求得的唯一解，称为,基解,。,2.可行解、基解、基可行解、可行基,一、LP问题的基本概念,10/30/2025,8,基解,中满足所有变量,非负,约束的解，称为,基可行解,。,2.可行解、基解、基可行解、可行基,与,基可行解,对应的基称为,可行基,。,一、LP问题的基本概念,10/30/2025,9,概念练习:找出下列LP问题的全部基解。,1,2,3,4,5,1,2,3,4,5,一、LP问题的基本概念,10/30/2025,10,组合,x,1,x,2,x,3,x,4,x,5,z,基可行解？,1-2,0,0,1-3,0,0,1-4,0,0,1-5,0,0,2-3,0,0,2-4,0,0,2-5,0,0,3-4,0,0,3-5,0,0,4-5,0,0,5,10,4,5,/,/,/,/,5,5,-1,20,4,5,2,17,5,5,4,10,10,-5,4,15,/,/,/,/,5,2.5,1.5,17.5,5,4,-3,22,2,4,3,19,一、LP问题的基本概念,10/30/2025,11,1.连线:,二、重要定理与引理,在n维Euclid空间中，点X与Y连线上的点，是指如下形式的点T:,当跑遍区间0,1时,相应的点T的集合就构成点X与Y之间的连线。,10/30/2025,12,2.凸集:,一个由n 维点所构成的集合K，如果对于K中任意两点X,Y K，恒有:,则n维点集K称为凸集，即K中任意两点的连线上的点也在K中。,3.凸组合:,假定有k个n 维Euclid 空间的点,它们的凸组合是指如下形式的点X:,特别，两个点X与Y的凸组合，叫做它们连线上的点。,二、重要定理与引理,10/30/2025,13,4.顶点:,设K是凸集，点X K；若对K中任何两个不同的点X,Y，以下等式,恒不,成立:,就称X为凸集K的顶点。换句话说，凸集的顶点，就是不在凸集中任意两点连线上的点。,二、重要定理与引理,10/30/2025,14,定理1.若 LP问题的可行域非空,则可行域为凸集,定理2.LP问题的基可行解X对应LP问题可行域的顶点,定理3.若LP问题有最优解，则一定存在至少一个基可行解为最优解,二、重要定理与引理,LP问题的标准型，见P20,10/30/2025,15,(1)列初始,单纯形表,三、,单纯形法的计算步骤,c,j,c,1,c,m,c,j,c,n,C,B,基,b,x,1,x,m,x,j,x,n,c,1,x,1,b,1,1,0,a,ij,a,1n,c,2,x,2,b,2,0,0,a,2j,a,2n,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,c,m,x,m,b,m,0,1,a,mj,a,mn,=c,j,-,z,j,0,0,0,10/30/2025,16,(2)从一个基可行解转换为相邻的另一个基可行解,不失一般性，,设,初始,基可行解中的前m个为基变量，,设单位矩阵的列向量为P,i,，增广矩阵中单位矩阵以外的,某个,列向量为P,j,，则P,j,可以成为P,i,的线性表达：,1,1,1,a,1j,.,a,mj,三、,单纯形法的计算步骤,10/30/2025,17,两式相加：,三、,单纯形法的计算步骤,对于一个正数：,10/30/2025,18,除了X(0)，还有其他解吗？,1,1,1,a,1j,.,a,mj,只需：,问题：X(1)是基可行解吗？,三、,单纯形法的计算步骤,10/30/2025,19,要使X(1)成为基可行解，必须满足：,且，至少一个等式成立！,显然，对于小于等于0的 a,ij,，上述不等式无条件成立；对于大于0的a,ij,，则令：,三、,单纯形法的计算步骤,10/30/2025,20,1,1,1,a,1j,.,a,mj,1,1,1,以上的系数矩阵的初等行变换，成为,换基,变换；如果,仅且,变换,一个,基变量，称对应的两个基可行解为,相邻,的基可行解。对应的顶点称为,相邻,的顶点，简称,邻点,。,三、,单纯形法的计算步骤,10/30/2025,21,将X(0),X(1)分别代入目标函数：,(3)最优性判断,三、,单纯形法的计算步骤,10/30/2025,22,其中：,称为检验数，也可表达为：,或：,三、,单纯形法的计算步骤,10/30/2025,23,【例】用单纯型法解下列LP问题：,用矩阵形式表示为：,四、应用举例,10/30/2025,24,首先构造初始单纯型表如下：,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,0,x,4,24,6,2,0,1,0,0,x,5,5,1,1,0,0,1,c,j,-z,j,2,0,0,0,1,四、应用举例,10/30/2025,25,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,0,x,4,24,6,2,0,1,0,0,x,5,5,1,1,0,0,1,c,j,-z,j,2,0,0,0,1,x,1,四、应用举例,10/30/2025,26,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,2,x,1,24,6,2,0,1,0,0,x,5,5,1,1,0,0,1,c,j,-z,j,2,0,0,0,1,x,1,四、应用举例,10/30/2025,27,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,2,x,1,4,1,2/6,0,1/6,0,0,x,5,1,0,4/6,0,-1/6,1,c,j,-z,j,0,0,0,-1/3,1/3,第一次迭代结束,四、应用举例,10/30/2025,28,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,2,x,1,4,1,2/6,0,1/6,0,0,x,5,1,0,4/6,0,-1/6,1,c,j,-z,j,0,0,0,-1/3,1/3,x,2,四、应用举例,10/30/2025,29,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15/2,0,0,1,5/4,-15/2,2,x,1,7/2,1,0,0,1/4,-1/2,1,x,2,3/2,0,1,0,-1/4,3/2,c,j,-z,j,-1/2,-1/4,0,0,0,四、应用举例,10/30/2025,30,化为标准形式：,五、单纯型法的进一步讨论人工变量法(大M法),【例】用单纯型法求解下列LP问题：,10/30/2025,31,构造初始单纯型表：,c,j,-3,0,1,0,0,-M,-M,CB,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,4,1,1,1,1,0,0,0,-M,x,6,1,-2,1,-1,0,-1,1,0,-M,x,7,9,0,3,1,0,0,0,1,c,j,-z,j,-3-2M,0,0,0,4M,-M,1,五、单纯型法的进一步讨论人工变量法(大M法),10/30/2025,32,第1次迭代：,c,j,-3,0,1,0,0,-M,-M,CB,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,3,3,0,2,1,1,-1,0,0,x,2,1,-2,1,-1,0,-1,1,0,-M,x,7,6,6,0,4,0,3,-3,1,c,j,-z,j,-3+6M,-4M,0,0,0,3M,1+4M,五、单纯型法的进一步讨论人工变量法(大M法),10/30/2025,33,第2次迭代：,c,j,-3,0,1,0,0,-M,-M,CB,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,0,0,0,0,1,-1/2,1/2,-1/2,0,x,2,3,0,1,1/3,0,0,0,1/3,-3,x,1,1,1,0,2/3,0,1/2,-1/2,1/6,c,j,-z,j,-M-3/2,-M+1/2,0,0,0,3/2,3,五、单纯型法的进一步讨论人工变量法(大M法),10/30/2025,34,第3次迭代：,c,j,-3,0,1,0,0,-M,-M,CB,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,0,0,0,0,1,-1/2,1/2,-1/2,0,x,2,5/2,-1/2,1,0,0,-1/4,1/4,1/4,1,x,3,3/2,3/2,0,1,0,3/4,-3/4,1/4,c,j,-z,j,-M+3/4,-M+1/4,-9/2,-3/4,0,0,0,五、单纯型法的进一步讨论人工变量法(大M法),10/30/2025,35,同样题目,六、单纯型法的进一步讨论两阶段法,为了保证人工变量为0，可讲目标函数设为：,10/30/2025,36,构造初始单纯型表：,c,j,0,0,0,0,0,-1,-1,CB,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,4,1,1,1,1,0,0,0,-1,x,6,1,-2,1,-1,0,-1,1,0,-1,x,7,9,0,3,1,0,0,0,1,c,j,-z,j,-2,0,0,0,4,-1,1,六、单纯型法的进一步讨论两阶段法,10/30/2025,37,第1次迭代：,c,j,0,0,0,0,0,-1,-1,CB,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,3,3,0,2,1,1,-1,0,0,x,2,1,-2,1,-1,0,-1,1,0,-1,x,7,6,6,0,4,0,3,-3,1,c,j,-z,j,6,-4,0,0,0,3,4,六、单纯型法的进一步讨论两阶段法,10/30/2025,38,第2次迭代：,c,j,0,0,0,0,0,-1,-1,CB,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,0,0,0,0,1,-1/2,1/2,-1/2,0,x,2,3,0,1,1/3,0,0,0,1/3,0,x,1,1,1,0,2/3,0,1/2,-1/2,1/6,c,j,-z,j,-1,-1,0,0,0,0,0,即，当X,(1),=(1,3,0,0,0,0,0)时，可使目标函数x,6,+x,7,取得最小，当x,6,=x,7,=0时,六、单纯型法的进一步讨论两阶段法,10/30/2025,39,上述取得最优的单纯型迭代中止的表，等价于一个约束方程组I：,而约束方程组I又等价于约束方程组II：,故，构造新的初始单纯型表如下：,六、单纯型法的进一步讨论两阶段法,10/30/2025,40,c,j,-3,0,1,0,0,CB,基,b,x,1,x,2,x,3,x,4,x,5,0,x,4,0,0,0,0,1,-1/2,0,x,2,3,0,1,1/3,0,0,-3,x,1,1,1,0,2/3,0,1/2,c,j,-z,j,六、单纯型法的进一步讨论两阶段法,10/30/2025,41,c,j,-3,0,1,0,0,CB,基,b,x,1,x,2,x,3,x,4,x,5,0,x,4,0,0,0,0,1,-1/2,0,x,2,3,0,1,1/3,0,0,-3,x,1,1,1,0,2/3,0,1/2,c,j,-z,j,第1次迭代：,0,0,0,3/2,3,六、单纯型法的进一步讨论两阶段法,10/30/2025,42,c,j,-3,0,1,0,0,CB,基,b,x,1,x,2,x,3,x,4,x,5,0,x,4,0,0,0,0,1,-1/2,0,x,2,5/2,-1/2,1,0,0,-1/4,1,x,3,3/2,3/2,0,1,0,3/4,c,j,-z,j,第1次迭代：,-9/2,-3/4,0,0,0,六、单纯型法的进一步讨论两阶段法,10/30/2025,43,七、单纯型法解的讨论,补充定理1.,如果LP问题有最优解，则,基可行解,中必有最优解。,补充定理2.若X,(1),X,(2),.,X,(K),皆为某LP问题的,最优解,，那么它们的凸组合,也是该LP问题的最优解。,补充定理3.若LP问题的可行域,有界,，而它的,基可行解,中的所有最优解为:,X,(1),X,(2),.,X,(K),那么它们的所有凸组合包括了该LP问题的所,有最优解。(证明略),以下给出三个补充定理，可看作是求解线性规划问题的基本依据。,10/30/2025,44,情况1:唯一最优解,只需,非基变量,的检验数全为负，且,基变量,中,不含,人工变量,，该解即为,唯一,最优解。,情况2:无解,1.当,非基变量,的检验数全为负，且,基变量,中,含有,人工变量,，则该LP问题无解。,2.可行域为空集。,七、单纯型法解的讨论,10/30/2025,45,情况3:解无界,对于某个,正,检验数，其对应的P,j,有,非正,的分量，该LP问题的解无界。,七、单纯型法解的讨论,10/30/2025,46,看以下例子:,c,j,1,1,0,0,CB,基,b,x,1,x,2,x,3,x,4,0,x,3,4,-2,1,1,0,0,x,4,2,1,-1,0,1,c,j,-z,j,1,1,0,0,请同学们用图解加以验证，加深印象。,七、单纯型法解的讨论,10/30/2025,47,情况4:多重最优解-无穷最优解,存在非基变量的检验数为0，该LP问题存在多重最优解。,七、单纯型法解的讨论,10/30/2025,48,八、算法的有限步中止,特别地，指迭代循环的中止。,按最小比值,来确定,出基变量,时，有时会出现多个相同的最小值-,，,从而有下一轮迭代中，基可行解会出现一个或多个基变量=0解，这种情况称为,解的退化,。,退化解的出现，是因为模型中存在,多余,的约束。,当存在退化解时，就,可能,出现迭代循环，尽管可能性很小。,10/30/2025,49,本章结束,10/30/2025,50,长风破浪会有时，直挂云帆济沧海。努力，终会有所收获，功夫不负有心人。以铜为镜，可以正衣冠；以古为镜，可以知兴替；以人为镜，可以明得失。前进的路上，要不断反思、关照自己的不足，学习更多东西，更进一步。穷则独善其身，达则兼济天下。现代社会，有很多人，钻进钱眼，不惜违法乱纪；做人，穷，也要穷的有骨气！古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。想干成大事，除了勤于修炼才华和能力，更重要的是要能坚持下来。士不可以不弘毅，任重而道远。仁以为己任，不亦重乎,?,死而后已，不亦远乎,?,心中有理想，脚下的路再远，也不会迷失方向。太上有立德，其次有立功，其次有立言，虽久不废，此谓不朽。任何事业，学业的基础，都要以自身品德的修炼为根基。饭疏食，饮水，曲肱而枕之，乐亦在其中矣。不义而富且贵，于我如浮云。财富如浮云，生不带来，死不带去，真正留下的，是我们对这个世界的贡献。英雄者，胸怀大志，腹有良策，有包藏宇宙之机，吞吐天地之志者也英雄气概，威压八万里，体恤弱小，善德加身。老当益壮，宁移白首之心；穷且益坚，不坠青云之志老去的只是身体，心灵可以永远保持丰盛。乐民之乐者，民亦乐其乐；忧民之忧者，民亦忧其忧。做领导，要能体恤下属，一味打压，尽失民心。勿以恶小而为之，勿以善小而不为。越是微小的事情，越见品质。学而不知道，与不学同；知而不能行，与不知同。知行合一，方可成就事业。以家为家，以乡为乡，以国为国，以天下为天下。若是天下人都能互相体谅，纷扰世事可以停歇。志不强者智不达，言不信者行不果。立志越高，所需要的能力越强，相应的，逼迫自己所学的，也就越多。臣心一片磁针石，不指南方不肯休。忠心，也是很多现代人缺乏的精神。吾日三省乎吾身。为人谋而不忠乎,?,与朋友交而不信乎,?,传不习乎,?,若人人皆每日反省自身，世间又会多出多少君子。人人好公，则天下太平；人人营私，则天下大乱。给世界和身边人，多一点宽容，多一份担当。为天地立心，为生民立命，为往圣继绝学，为万世开太平。立千古大志，乃是圣人也。丹青不知老将至，贫贱于我如浮云。淡看世间事，心情如浮云天行健，君子以自强不息。地势坤，君子以厚德载物。君子，生在世间，当靠自己拼搏奋斗。博学之，审问之，慎思之，明辨之，笃行之。进学之道，一步步逼近真相，逼近更高。百学须先立志。天下大事，不立志，难成！海纳百川，有容乃大；壁立千仞，无欲则刚做人，心胸要宽广。其身正，不令而行；其身不正，虽令不从。身心端正，方可知行合一。子曰,:“,知者不惑，仁者不忧，勇者不惧。”真正努力精进者，不会把时间耗费在负性情绪上。好学近乎知，力行近乎仁，知耻近乎勇。力行善事，有羞耻之心，方可成君子。操千曲尔后晓声，观千剑尔后识器做学问和学技术，都需要无数次的练习。第一个青春是上帝给的；第二个的青春是靠自己努力当眼泪流尽的时候，留下的应该是坚强。人总是珍惜未得到的，而遗忘了所拥有的。谁伤害过你，谁击溃过你，都不重要。重要的是谁让你重现笑容。幸运并非没有恐惧和烦恼；厄运并非没有安慰与希望。你不要一直不满人家，你应该一直检讨自己才对。不满人家，是苦了你自己。最深的孤独不是长久的一个人，而是心里没有了任何期望。要铭记在心；每一天都是一年中最完美的日子。只因幸福只是一个过往，沉溺在幸福中的人；一直不知道幸福却很短暂。一个人的价值，应该看他贡献什么，而不应当看他取得什么。做个明媚的女子。不倾国，不倾城，只倾其所有过的生活。生活就是生下来，活下去。人生最美的是过程，最难的是相知，最苦的是等待，最幸福的是真爱，最后悔的是错过。两个人在一起能过就好好过！不能过就麻利点分开。当一个人真正觉悟的一刻，他放下追寻外在世界的财富，而开始追寻他内心世界的真正财富。人若软弱就是自己最大的敌人。日出东海落西山，愁也一天，喜也一天。遇事不转牛角尖，人也舒坦，心也舒坦。乌云总会被驱散的，即使它笼罩了整个地球。心态便是黑暗中的那一盏明灯，可以照亮整个世界。生活不是单行线，一条路走不通，你可以转弯。给我一场车祸。要么失忆。要么死。有些人说：我爱你、又不是说我只爱你一个。生命太过短暂，今天放弃了明天不一定能得到。删掉了关于你的一切，唯独删不掉关于你的回忆。任何事都是有可能的。所以别放弃，相信自己，你可以做到的。、相信自己，坚信自己的目标，去承受常人承受不了的磨难与挫折，不断去努力、去奋斗，成功最终就会是你的！既然爱，为什么不说出口，有些东西失去了，就在也回不来了！对于人来说，问心无愧是最舒服的枕头。嫉妒他人，表明他人的成功，被人嫉妒，表明自己成功。在人之上，要把人当人；在人之下，要把自己当人。人不怕卑微，就怕失去希望，期待明天，期待阳光，人就会从卑微中站起来，带着封存梦想去拥抱蓝天。成功需要成本，时间也是一种成本，对时间的珍惜就是对成本的节约。人只要不失去方向，就不会失去自己。过去的习惯，决定今天的你，所以，过去的懒惰，决定你今天的一败涂地。让我记起容易，但让我忘记我怕我是做不到。不要跟一个人和他议论同一个圈子里的人，不管你认为他有多可靠。想象困难做出的反应，不是逃避或绕开它们，而是面对它们，同它们打交道，以一种进取的和明智的方式同它们奋斗。他不爱你，你为他挡一百颗子弹也没用。坐在电脑前，不知道做什么，却又不想关掉它。做不了决定的时候，让时间帮你决定。如果还是无法决定，做了再说。宁愿犯错，不留遗憾。发现者，尤其是一个初出茅庐的年轻发现者，需要勇气才能无视他人的冷漠和怀疑，才能坚持自己发现的意志，并把研究继续下去。我的本质不是我的意志的结果，相反，我的意志是我的本质的结果，因为我先有存在，后有意志，存在可以没有意志，但是没有存在就没有意志。公共的利益，人类的福利，可以使可憎的工作变为可贵，只有开明人士才能知道克服困难所需要的热忱。立志用功如种树然，方其根芽，犹未有干；及其有干，尚未有枝；枝而后叶，叶而后花。意志的出现不是对愿望的否定，而是把愿望合并和提升到一个更高的意识无论是美女的歌声，还是鬓狗的狂吠，无论是鳄鱼的眼泪，还是恶狼的嚎叫，都不会使我动摇。即使遇到了不幸的灾难，已经开始了的事情决不放弃。最可怕的敌人，就是没有坚强的信念。既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。意志若是屈从，不论程度如何，它都帮助了暴力。有了坚定的意志，就等于给双脚添了一对翅膀。意志坚强，只有刚强的人，才有神圣的意志，凡是战斗的人，才能取得胜利。卓越的人的一大优点是：在不利和艰难的遭遇里百折不挠。疼痛的强度，同自然赋于人类的意志和刚度成正比。能够岿然不动，坚持正见，度过难关的人是不多的。钢是在烈火和急剧冷却里锻炼出来的，所以才能坚硬和什么也不怕。我们的一代也是这样的在斗争中和可怕的考验中锻炼出来的，学习了不在生活面前屈服。只要持续地努力，不懈地奋斗，就没有征服不了的东西。,