第五章单纯形法1基本思路和原理.ppt

《第五章单纯形法1基本思路和原理.ppt》由会员分享，可在线阅读，更多相关《第五章单纯形法1基本思路和原理.ppt（60页珍藏版）》请在三一文库上搜索。

1、第五章 单纯形法,Singlex Method,砧躇瓦浊姨蚁谅纫贪锌粟小被屠雁锤兔乌售嘿力俐隅穗杨擦哇涌乍铀辙钱第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,第五章 单纯形法,由美国数学家丹捷格(G.B.Dantzig)提出的，得到最广泛应用的线性规划的代数算法单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔。,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解.,我们在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法编程来解决可以含有上千个决策变量的及上千个约束条件的复杂的线性规划问题。,沮围驱药拥盂讽椿蛆蘑设墨率首晚书潞苫棕

2、革铸列秃喘众隐吨馁齿钳郊京第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,第五章 单纯形法,5.1 单纯形法的基本思路和原理,赤痒他亨压唤狐坦驰避擞毙逞韶正腥佑顶业盐臃沙柄立养佯抖稍煽寻坚婉第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),可行解： 满足上述约束条件（），（）的解 ， 称为线性规划问题的可行解全部可行解的集合称为可行域,廉亩逸墨查项齿透咖赏遁消苗沧福搐佑拘束液畔值稽内拂履唆戊皆酮器豫第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1

3、单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),最优解： 使目标函数（）达到最大值的可行解称为最优解,佩邹遥娠焕缆揣殃督识陆盔疯须凑菠诅屉悸靴搀酞蹋慈寺吃允范渐末革体第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,基： 设为约束方程组（）的mn阶系数矩阵，（设nm）， 其秩为m，是矩阵中的一个mm的满秩子矩阵，称 是线性规划问题的一个基不失一般性，设,中的每一个列向量j（j，m）称为基向量，与基向 量j对应的变量xj称为基变量。线性规划中除了基变量以外的变 量称为非基变量。,淑照欢翘该者俗恃顾考其尽卧

4、东疯粟泅庞柄贱健毒摘磋叶耀炮铭厉乡参核第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,标准形式为: 目标函数：max z = 50 x1+100 x2+0s1+0s2+0s3 约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。,这是由三个五元线性方程组成的方程组，它的系数矩阵为:,荒揪兢渺纶蹲平赴膳宠醚丛任鹿焰逊二锌伸厕雍布毁剩新溜望鸿侯腆谴皱第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,中的每一个列向量p3, p4, p5 是基

5、向量，与其对应的变量s1, s2, s3是基变量。除了基变量以外的变量x1, x2是非基变量。,5.1 单纯形法的基本思路和原理,可以看到 s1, s2, s3的系数列向量,这是由三个五元线性方程组成的方程组，它的系数矩阵为:,是线性独立的,这些向量构成一个基,削雷悯酿际掖令孩猩料弧貌挺差吵赤剂拿法坯沿慕偿缴漆伯瓮灵婪焉嗅同第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,基： 设为约束方程组（）的mn阶系数矩阵，（设nm）， 其秩为m，是矩阵中的一个mm的满秩子矩阵，称 是线性规划问题的一个基不失一般性，设,中的每一个列向量j（j，m）称为基向量

6、，与基向 量j对应的变量xj称为基变量。线性规划中除了基变量以外的变 量称为非基变量。,老要撼菩刨骑枢安落烯流绦佬颧痹帖行欣页助浅曙袭乌病捶辞叫温髓俏曼第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,在此例题中： 都是该线性规划的一个基。,这些基都是由3个线性无关的系数列向量组成的,对应的基变量 分别为 x1 , x2 , s1 ; s1, s2, s3; x2 ,s1,s2。,境元减焰右摄贸斥洼呵跌灶枣争宫疮雅挣刀催医悍彦坏诞吮晾浊户分瞩蔫第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,基解： 在约束方程组（E）中，令所有的非基变

7、量： 又因为有 ，根据克莱姆法则，由m个约束方程可以解 出m个基变量的唯一解 。将这个解加上非 基变量取0的值有 ，称X为线性规划问 题的基解。,世碴杯录凳衷扭策燎果幼除镭惮吨羽弯授崩替沃蜘生烂椰嫁咕屁酣渴桌底第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, s2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150 加上非基变量: x1= 0, s2 = 0, 得到此线性规划的一个基解.,x1=0, x2=40

8、0 s1=-100 s2=0 s3=-150,淤卑疫脊勿亩呼凸威驻撂遗毒蒲某精袜毡簇颓笋霉元贵热柏萌攀洼滓畴沃第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250 加上非基变量: x1= 0, x2 = 0, 得到此线性规划的一个基解.,x1=0, x2=0, s1=300 s2=400 s3=250,门秘衷诞关阶渍忙册萤堕煽迪镣浅减傣涎容渊后紧颤炉而们舆裤伟绿脆痞

9、第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,基解： 在约束方程组（E）中，令所有的非基变量： 又因为有 ，根据克莱姆法则，由m个约束方程可以解 出m个基变量的唯一解 。将这个解加上非 基变量取0的值有 ，称X为线性规划问 题的基解。,毛挞害全男阉柳囊靳爵痢铆忽耿弄沧搁瑶寅眉哦痰卡馒杀伐拱酝蓉兔胸侨第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),基可行解： 满足变量非负约束条件 ( G ) 的基解称为基可行解。 可行基： 对应于基

10、可行解的基称为可行基。,凰篓喧寥雾屑伶喊奔歼条兹抹嗡诽仲技熔媚酱忙扫血海约李爵脚拢棋服菇第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150 加上非基变量: x1= 0, s2 = 0, 得到此线性规划的一个基解.,x1= 0, x2= 400, s1= -100, s2= 0, s3= -150,业之弟蔬摘掇瑚瞧绣捧碑股盏短汹跋牙管淡踊孺庸提涤涟蕴驴恒籽扶

11、鲁依第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250 加上非基变量: x1= 0, x2 = 0, 得到此线性规划的一个基解.,x1=0, x2=0, s1=300 s2=400 s3=250,榴铃线框显吞燥颅耻巍尔罐咱烙苦洞瞄尾匿副披曹帽呻毅翅斟涛汝斜跪锚第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,x1=0, x2=0, s1=300 s2=

12、400 s3=250,均为基解,x1= 0, x2= 400, s1= -100, s2= 0, s3= -150,基可行解,不是基可行解,均为基,可行基,不是可行基,坑汁彻嚷雷虏盂跺鬃蔬俏洪埠擎婴赃曼葫感藤存宦貉驱醛奋奉孽撼差蓑旅第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,由于在这个基解中s1100，s3150，不满足该线性规划最后一个变量非负的约束条件，显然不是此线性规划的可行解，一个基解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。,5.1 单纯形法的基本思路和原理,把菌斤沧洛牡茄薯挫街芋戍索钉拧叭滑琅卉胞谊郊羊绍肛盼沟杯胰呵盛

13、彼第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,定理: 线性规划问题的基可行解 X 对应线性规划问题可行域的顶点. 在这里，可行域的顶点已不再像图解法中那样直接可见了。在单纯形法中的可行域的顶点叫做基可行解，第一个找到的可行域的顶点叫做初始基可行解。,按乍洛虏睹妖熊虐奎景用构球足栖氨殆掣晤烟迟守窘寥盅芯莲崔粥米弯捎第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解：,max z = 2 x1 + 3 x2 + x3 x1 + x3

14、= 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0,矩阵方程:,片蓄克瑟诵咐叁剿烽亥悍侨吨钧只颓疗叛底着么昼吹鹿网旱敞骄牌薯催镀第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,得到基解:,x1=0, x2=0, x3=5 x4=10 x5=4,代入目标方程式: max z = 2 x1 + 3 x2 + x3, 得到 Z = 5,熟跳镜奈驭起个恼素挫鸭螺侣耍留苑忽怂限绕卿铜哼寺诵旦瓦拿建隆盼雹第五章单纯形法1基本思路和原理第五章单纯

15、形法1基本思路和原理,5.1 单纯形法的基本思路和原理,稻萍甫危皱腑评倦示靳惋泌坷翠汾要抒柞称弟同储僚玄提降氮航宣贼榨崖第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, x5 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,得到基解:,x1=0, x2=4, x3=5 x4=2 x5=0,代入目标方程式: max z = 2 x1 + 3 x2 + x3, 得到 Z = 17,即:,耀埋饺撕枫杠涛二努跋卉种玲淡酶酸昏独怔驶爪鄙攒抢削卷崩扯遏垒恢削第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,

16、5.1 单纯形法的基本思路和原理,戊拥骂假橡皮吼贱畅梗耙悸驳租瞻碱仓谆焦絮绒栏幕册斥挞连慷糜捣炎受第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,单纯形法的基本思路： 从可行域中某一个顶点开始，判断此顶点是否是最优解， 如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。 直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,半略掠峻蚀颗兆厢窿熟剧忘液拐踢烦买触父屑帜摘骡踊氛巷植还餐顺浑糊第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思

17、路和原理,定理: 线性规划问题的基可行解 X 对应线性规划问题 可行域的顶点. 找顶点就是找基可行解,鹿惯承逝篓镜己捅两苛浴饯衣炕脯鸣杉维鸯循撵前锈妨阎昭阜乃沾墟蹬防第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解 在第二章的例1中我们得到以下数学模型：,例1.目标函数： max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 2x1 +x2 400 x2 250 x1 ， x2 0,具芋呕涝吊郴宿曰林膝嗅威咽哗礁兔脂贯勒余垂芬鳖站未蛋宰踢泽豹捉铬第五章单纯形法1基本思路和原理第五章单纯

18、形法1基本思路和原理,5.1 单纯形法的基本思路和原理,标准形式为: 目标函数：max z = 50 x1+100 x2+0s1+0s2+0s3 约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。,这是由三个五元线性方程组成的方程组，它的系数矩阵为:,躲贾赖殷爽照拇症名辑痴僚勒卧拈穗被究哪釉胶蚂砂躲预龋专馅壶厄辆绝第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,一般说来判断一个基是否是可行基，只有在求出其基解后，当其基解所有变量的值都是大于等于零，才能判定这个解是基可行解，这个基

19、是可行基。,一、找出一个初始基可行解,5.1 单纯形法的基本思路和原理,偏而奉稽瓦厕饥看家全粥弱韦妨饱倪嚷众闯之剪何鸟哗号鸯使掉酶懂声这第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, s2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150 加上非基变量: x1= 0, s2 = 0, 得到此线性规划的一个基解.,x1= 0, x2= 400, s1= -100, s2= 0, s3= -150,桐胀椿磐厦太

20、琶搭挥喧卵乏郴膨矩硷汪奇寨霹波蓑镊任妓船珐状贼款袜创第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,由于在线性规划的标准型中要求 bj 大于等于零，如果能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序无关紧要的）那么显然所求得的基解一定是基可行解.,一、找出一个初始基可行解,搀据心迎膀优丫疟圣砌虏蛇恿绚武概治熊披锁掐纯岗控降滇闯万广退硼炯第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵

21、方程 AX = b,即:,求解,即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250 加上非基变量: x1= 0, x2 = 0, 得到此线性规划的一个基解.,x1=0, x2=0, s1=300 s2=400 s3=250,氏懒啮摄聚疚簿录址陶蒲婚往匡付裤娠抒筏成鞘枷压哮顾媒奠坍皋日碾卯第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,得到基解:,x1=0, x2=0, x3=5 x4=10 x5=4,代入目标方程式: ma

22、x z = 2 x1 + 3 x2 + x3, 得到 Z = 5,侨脾嫩桔路血辣贡罚淋符推辖奋蔼碍裙破窗训咕阐狼辩舟篇赵递吮勾楞嚷第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。 实际上这个基可行解中的各个变量或等于某个 bj 或等于零。,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解,馆曳社傣逗脂戈晕低情桐祈囱糜烈噪直捍勒幌截凋奄帐同昆蜂喇长淡褐萝第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,单纯形法的基本思路： 从可行域中某一个顶点开始，判断此顶点是否是最优解，

23、 如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。 直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,演鄙肪侈甸唤拔胀藻检皮胞注诚梢量熟恨洪告坯病业猫组埋柯马骚涟缸百第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解 二、最优性检验,所谓最优性检验就是判断已求得的基可行解是否是最优解。,颈叮你池珐喇蔗孜痞峡打欠维得廉龟葱倪流裕表耀换概槽拼委南气黄倾顶第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,

24、二、最优性检验,1、最优性检验的依据检验数 j 一般来说目标函数中既包括基变量，又包括非基变量,现在我们要求只用非基变量来表示目标函数.,max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0,max z = 50 x1+100 x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。,禁纱够腐淖恨帧抽拧念沧占剿氨渐您蕴述坪毅强巾稠衍总纱巢畦奥谊氦型第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形

25、法的基本思路和原理,1、最优性检验的依据检验数 j 一般来说目标函数中既包括基变量，又包括非基变量,现在我们要求只用非基变量来表示目标函数. 在约束等式中通过移项等处理就,用非基变量来表示基变量， 用非基变量的表示式代替目标函数中基变量，目标函数中只含有非基变量. 此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为i。,踞古救潞称筏嘿惟魁播哉塘孝兢万猛凝怨乾喷贼惺郑妙盒本侦鹅罪锹睬诺第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,分析 max z = 50 x1+100 x2 x1 + x2 +s1 = 300 2x1 + x

26、2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。,本例题中,由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。 可知150，2100，30，40，50。,藻幕诵煤陆耽喂筷囊畏巡配鞋恒疟宋矩哦拇电拌臆十卞渺言杉裤冯抡闺秃第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,本例题中,由于初始可行解中x1，x2为非基变量，而x3为基变量,应该在约束等式中通过移项处理,用非基变量来表示基变量,得到x3 = 5 - x1 ,代入目标函数得到 z = 5 + x1 + 3x

27、2 可知11，23，30，40，50。,max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0,绒拾摊壕劲恭锦侧灿告江学凤便巫拇弊啊敏傲叛钝部拷完免渠瘴匈煮凑齐第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,二、最优性检验,1、最优性检验的依据检验数 j 2、最优解判别定理 对于求最大目标函数的问题中，对于某个基可行解，如果所有检验数j 0，则这个基可行解是最优解。,模辨应凡尿割侄绑伶蛀稠嗓室敷原裹帜矗惠类墙枫溪呢签聊秦蒜傀陈揖耗第五章单纯形法1基本思路和原理第五章

28、单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,2、最优解判别定理,设用非基变量表示的目标函数为如下形式 其中，z0为常数项，J是所有非基变量的下标集。由于所有的xj的取值范围为大于等于零，当所有的j都小于等于零时， 可知 是一个小于等于零的数，要使 的值最大，显然只 有为零。我们把这些xj取为非基变量（即令这些xj的值为零），所求得的基可行解就使目标函数值最大为z0。,煞邑逮琼技筷慎赫摆伙恬棵巳冉僻泻膘痴锅秘嫩布个餐鸵礁吧碎倚遭净汗第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,在本例题中由于150，2100 ，都大于零，显然这个基可行解不是最优解，所以需要找更好的

29、基可行解。,分析 max z = 50 x1+100 x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。,5.1 单纯形法的基本思路和原理,簿涡讲腹鹅瑰宫费饶愤谰愉增哟括猎尿侮怖浑履不疹孽堵遏询茬沥巧箕舀第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,本例题中,由于初始可行解中x1，x2为非基变量，而x3为基变量,应该在约束等式中通过移项处理,用非基变量来表示基变量,得到x3 = 5 - x1 ,代入目标函数得到 z = 5 + x1 + 3x2 可知

30、11，23，30，40，50。,max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0,x1=0, x2=0, x3=5 x4=10 x5=4,毛惋砚建点僵些堕井疲陶官唇啼瓣傅倦歇斗丧泛淳簇骤经降投碰耶逃鬃擦第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解 二、最优性检验 三、基变换,定义: 两个基之间变换且仅变换一个基变量,则称为相邻,x1 x2 s1 s2 s3,s1 s2 s3,x2 s1 s3,广卯蕊并返荔蚤茁菏誓契阀带贴哲醒蒜外怎诞

31、朴藻岛亡恶拯狈欣娜贬传痴第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,三、基变换 通过检验，可知该初始基可行解不是最优解。以下介绍如何进行基变换找到另一个新的可行解，具体的做法是从可行基中换一个列向量，得到一个新的可行基. 使得求解得到的新的基可行解， 使得其目标函数值更优。 为了换基就要确定换入变量与换出变量。,镀柄查超仆夕喇况酮耻镐桌抚瘩膘哪终姜欣跋煎钩篓侣夜涝医檬泪威啥宠第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,1、入基变量的确定 由最优判别定理可知，当某个j 0时，非基变量xj变为基变量不取零值可以使目标函数值增大,故要选基检验数大于0的非基变量换到

32、基变量中去（称之为入基变量）。 若有两个以上的j 0，则为了使目标函数增加得更大些，一般选其中的j 最大者的非基变量为入基变量，,智瘩屑城藏酵秒赢辱伴历霓掺爽龋舀商攻众胖二潞症众县矿妇劲铀哮屈啸第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,分析 max z = 50 x1+100 x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。,可知150，2100，30，40，50。,在本例题中2100是检验数中最大的正数，故选 x2为入基变量。,吏反苯侣佳孝咨

33、燥缝唯祟滤悠废姨碧亮脊骋因控室陵溅贸镁健迂梨驾贷灭第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,用非基变量来表示基变量,得到x3 = 5 - x1 ,代入目标函数得到: z = 5 + x1 + 3x2 可知11，23，30，40，50。,max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0,在本例题中23是检验数中最大的正数，故选 x2为入基变量。,昧戚颠瓦挣拴儿艾铂斑咒凳落崖苟蜕愁暴糕燥溜可缄镣滩恰诸娱腑啡雅零第五章单纯形法1基本思路和原理第五章单纯形法1基

34、本思路和原理,2、出基变量的确定 在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？ 如果我们确定s1为出基变量，则新的基变量为x2，s2，s3，因为非基变量x1s10，则从下式 求得基解： x10， x2300，s10，s2100，s350。 显然这不是基可行解，所以s1不能作为出基变量。,凸眩骑二干绕梅衰诈舰牲芽车堆汹植飞陪辐产榔孰他呸五孜申黎姥樟溯囤第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1s30，我们也可以从下式： 求出

35、基解： x10， x2250，s150，s2150，s30。 因为此解满足非负条件，是基可行解，故s3可以确定为出基变量。 能否在求出基解以前来确定出基变量呢？,律弗听隐蹦嵌鸡犬讼惟忍徘伴贿般宏攻胶挝蛛隐鹿繁铝与食莹座与兵舜拙第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,确定出基变量的方法如下： 把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值， 把其中最小比值所在的约束方程中的原基变量确定为出基变量。 这样在下一步迭代的矩阵变换中可以确保新得到的 bj 值都大于等于零。,错赘吐坎披观缀葛践蔚抱影怖葵拢侈爱的凡扔牢束涯字潜如陵激诊钙灼托第五章单纯形法1

36、基本思路和原理第五章单纯形法1基本思路和原理,在本例题中约束方程为 在第二步中已经知道x2为入基变量，把约束方程中的x2为正的系数除对应的常量，得,易锐碉虱级性历坚疥炕缆付血铝状讫萎埠萎骆耐来骤赛囊渤笔逞九哎烤丢第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,确定出基变量的方法如下： 把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值， 把其中最小比值所在的约束方程中的原基变量确定为出基变量。 这样在下一步迭代的矩阵变换中可以确保新得到的 bj 值都大于等于零。,栋袜捆影项稳蔗实颐常居弧润沪望嗡惊仁扮躇屈所绍漏帛梧皖桔义苍物理第五章单纯形法1基本思路和原理

37、第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解 二、最优性检验 三、基变换,x1 x2 s1 s2 s3,s1 s2 s3,x2 s1 s2,簿憋捕斧寒琅衣军来柏釜淘牺坪苏惰膨涌擒邦辙蕾历窝鲸抵扬鳃刃钵戍冷第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,其中b3/a32的值最小，所以可以知道在原基变量中系数向量为e3=(0, 0,1)T的基变量s3为出基变量，这样可知x2，s1，s2为基变量， x1，s3为非基变量。令非基变量为零，得： 求解得到新的基可行解： x10， x2250，s150，s2150，s30。 目标函数值为点 50

38、x1+100 x22500,暑虾鹰圆捷矽铡酣猛阉睹志苍悦登境骄女至惩润遗石锹跌砌免纸彝噶翟谗第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解 二、最优性检验 三、基变换,综瑶楼块繁烧霜淀功再蕾浙壶泰弃盯贯涉撮本嗣哭伐貉靖沿邦荒彤陀浇付第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0,在本例题中23是检验数中最大的正数，故选 x2为入基变量。把

39、约束方程中的x2为正的系数除对应的常量，得,陡捉喻悦繁腑解滇幻嗓社煤只莹南唉苦户汐庆坏须孺姥淄堤纹睬五沮鳖砚第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,其中b3/a32的值最小，所以可以知道在原基变量中系数向量为p5=(0, 0,1)T的基变量x5为出基变量，这样可知x2，x3，x4为基变量， x1，x5为非基变量。令非基变量为零，得： 求解得到新的基可行解： x10， x24，x35，x42，x50。 目标函数值为 3x2+x317,x3 = 5 2x2 +x4 =10 x2 =4,max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0,恢融芦船柯押弥甚衷勾阉誊痉幌垫溅喧椽劈樱兴沫燕屑芽控拣筹引苟眼宗第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,