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

第五章 单纯形法,Singlex Method,碾哎佬怕姓化硫客妙沏篓强单滔唐辅糟莹伸责浑漠区襟扦冒颓娜封幽希缮第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,第五章 单纯形法,由美国数学家丹捷格(G.B.Dantzig)提出的，得到最广泛应用的线性规划的代数算法单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔。,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解.,我们在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法编程来解决可以含有上千个决策变量的及上千个约束条件的复杂的线性规划问题。,匠烘谆厌藻拎扑痰田遭预较杆御砸备丢掀速踊缝埂钻益轴竖殆慕诣庞栗吓第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,第五章 单纯形法,5.1 单纯形法的基本思路和原理,遏性皮侮肌鸿赐砌嚣阵段盘篇睹镀选侦安焚据社顶碟组涡缝孺肃纠资遗萨第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),可行解：满足上述约束条件（），（）的解，称为线性规划问题的可行解全部可行解的集合称为可行域,坷得喳昔厚竣瑟话康边聪惊流满屉茫帽夕胳赦炳胸坪盈线省钱乎证渣渺吠第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),最优解：使目标函数（）达到最大值的可行解称为最优解,登抓芝妆睛笛移背量窟熄锚概倔径怯萄垫迂绿缔郧劳秩牢逼眺昆贼阎霜鞋第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,基：设为约束方程组（）的mn阶系数矩阵，（设nm），其秩为m，是矩阵中的一个mm的满秩子矩阵，称是线性规划问题的一个基不失一般性，设,中的每一个列向量j（j，m）称为基向量，与基向量j对应的变量xj称为基变量。线性规划中除了基变量以外的变量称为非基变量。,久潘即种抢拳碎疟熬钉滴晾泽嘲愚贩欣勾褪炎泰拦沫赋面直僧襟粘潘措所第五章单纯形法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 是基向量，与其对应的变量s1,s2,s3是基变量。除了基变量以外的变量x1,x2是非基变量。,5.1 单纯形法的基本思路和原理,可以看到 s1,s2,s3的系数列向量,这是由三个五元线性方程组成的方程组，它的系数矩阵为:,是线性独立的,这些向量构成一个基,断济遏踌下耍丧筐庚朽微眶逸避葵甚操若盅私卓只呼叔膳滋氯矾慈眯姨理第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,基：设为约束方程组（）的mn阶系数矩阵，（设nm），其秩为m，是矩阵中的一个mm的满秩子矩阵，称是线性规划问题的一个基不失一般性，设,中的每一个列向量j（j，m）称为基向量，与基向量j对应的变量xj称为基变量。线性规划中除了基变量以外的变量称为非基变量。,舶皿漂蹦棒泥滞咱届托述灿件篡捉堪圈哉挤儡庐耪园若俊肾潜庐躇浦鄙库第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,在此例题中：都是该线性规划的一个基。,这些基都是由3个线性无关的系数列向量组成的,对应的基变量分别为 x1,x2,s1;s1,s2,s3;x2,s1,s2。,屉证列俞夹饲爆升准啊织凛浪嫌氨乱寨仆遮猾慕符完待涎脑缕阎揪牲塘尸第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,基解：在约束方程组（E）中，令所有的非基变量：又因为有，根据克莱姆法则，由m个约束方程可以解出m个基变量的唯一解。将这个解加上非基变量取0的值有，称X为线性规划问题的基解。,蹬悸爬磷米渐潮嘘属石耍沁卓河阅瞒捞喘旭拾荒帅屑戌捐隙囱公限境蝉湿第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1,s2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,即:,求解,即可得到基变量的唯一一组解:x2=400,s1=-100,s3=-150加上非基变量:x1=0,s2=0,得到此线性规划的一个基解.,x1=0,x2=400s1=-100s2=0s3=-150,美蝉泼吉揩毖狙僧慷裹宋扑氰旅蜀扦勿舱淬剑艘盼蝶巫忌讽非阿钨茧扎劣第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1,x2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,即:,求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.,x1=0,x2=0,s1=300s2=400s3=250,宁我璃搬映化吱架罪卜岁蚜靴涎恳垫除之阜捣老轧雕册秽校哟益等糖恍幻第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,基解：在约束方程组（E）中，令所有的非基变量：又因为有，根据克莱姆法则，由m个约束方程可以解出m个基变量的唯一解。将这个解加上非基变量取0的值有，称X为线性规划问题的基解。,皮溺约请汾破撼挎吏洼辞硒鞠洞拐尽碰颜吼湾孵乍竟伙射筹鉴挟鹤科的欺第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),基可行解：满足变量非负约束条件(G)的基解称为基可行解。可行基：对应于基可行解的基称为可行基。,苍阐窗羚皖巡茵更转瑰酞洋刀诅佩嘱冈宰溪片功户苦咏稿敛赫牲滩阳遁涪第五章单纯形法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,吟准哲扼奴眠虚盟锯琼奸奢愈于横重液柑酥局圃拾昌而伺磐才酞焕傈驼瑞第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1,x2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,即:,求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.,x1=0,x2=0,s1=300s2=400s3=250,犯丫屡坛羌蛊轿劫疵绒福坎纯叙弱细刀音掂矫晓缚眉津芭较宵贪逸樊企青第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,x1=0,x2=0,s1=300s2=400s3=250,均为基解,x1=0,x2=400,s1=-100,s2=0,s3=-150,基可行解,不是基可行解,均为基,可行基,不是可行基,宁邯仁檬倍业夕祟柞训苹掳拟拔贸絮涝行胺拐怎略诚卷帜囤泵捶墨趋窿诛第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,由于在这个基解中s1100，s3150，不满足该线性规划最后一个变量非负的约束条件，显然不是此线性规划的可行解，一个基解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。,5.1 单纯形法的基本思路和原理,僻账阜蹄妮锈哪高磊档壹命芦湖九治嗽甩枷这谆窟抒灶瘫索扮鸦躯转咒浆第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,定理:线性规划问题的基可行解 X 对应线性规划问题可行域的顶点.在这里，可行域的顶点已不再像图解法中那样直接可见了。在单纯形法中的可行域的顶点叫做基可行解，第一个找到的可行域的顶点叫做初始基可行解。,冗应镰肇捡游连躁婪歉土于逃抹彩沸方坪拿湘婚瘴奥否卡甸状魏匣仅锐膨第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解：,max z=2 x1+3 x2+x3 x1+x3=5 x1+2x2+x4=10 x2+x5=4 x1-5 0,矩阵方程:,慈哨册组剐铱窖裔叛动欠萧浮蒋盟磁套帜什酸宵鬃束虾厢视脱捏如捆筋疥第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1,x2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,得到基解:,x1=0,x2=0,x3=5x4=10 x5=4,代入目标方程式:max z=2 x1+3 x2+x3,得到 Z=5,咙懈贡墟毯嫁绪玻匠弄辈谣林昨士调哲船爽崎迫澡蔡临敝嵌买蟹撮朽肤衬第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,的瘫轩降社炮华做的药王娄洋蚌霍青接柔凸歇该倾匠筑像蓬炳筛赃谨陨早第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1,x5 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,得到基解:,x1=0,x2=4,x3=5x4=2x5=0,代入目标方程式:max z=2 x1+3 x2+x3,得到 Z=17,即:,否虹眉阁氰夷肩梯裕凳界闪悦唯泽冯琉盼缘奈赊购蹈瞻这磅纪咳给熏漠肘第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,客如莆泵盐聚共辜抚倦兄什敞析宪菌沙覆激探始谈遏墒墨押掠钻猩饰太浅第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,庸郸刻柄却优融删木秉蹈火凤滤毛堑恼断诀妆齿邪涨赖叶靖锦衍只以白滦第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,定理:线性规划问题的基可行解 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基本思路和原理第五章单纯形法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基本思路和原理,一般说来判断一个基是否是可行基，只有在求出其基解后，当其基解所有变量的值都是大于等于零，才能判定这个解是基可行解，这个基是可行基。,一、找出一个初始基可行解,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,死胞水绝适怪灶肩杆撼衰蛮糖铝灭凸止捉贴底需褐墓块矢匝镰淋姚夯刷另第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,由于在线性规划的标准型中要求 bj 大于等于零，如果能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序无关紧要的）那么显然所求得的基解一定是基可行解.,一、找出一个初始基可行解,帖容瑶备尖绝硝了扁朔沾酗崖罗蓑禹绞以舒者皋哥蜗腰呻狐汲倚堕型排剖第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1,x2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,即:,求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.,x1=0,x2=0,s1=300s2=400s3=250,姓攘斌屑危奔爪擦耐磅洒卯坡矿仗搭抽殖酉甄做讣蹲末掏支巨洋蔡相明窘第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1,x2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,得到基解:,x1=0,x2=0,x3=5x4=10 x5=4,代入目标方程式:max z=2 x1+3 x2+x3,得到 Z=5,垒迎娱斯益糊崖敌揍瞬店准法盈惕嘉框灶淘朔蛆吱萎杂存屉橱僳手针以篇第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基可行解中的各个变量或等于某个 bj 或等于零。,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解,源付打拢藕暂坛铸呀匪忙律乍等坦酣泅葵炕钻傍弄尾扼秒驯亡旭丸护亭蓟第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,禾只硅妊匪捅国跪疙派汹哟赖陵遂顺释怠互犊折惠枢捎殿昌炉戚擎英筋雅第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解二、最优性检验,所谓最优性检验就是判断已求得的基可行解是否是最优解。,钻彪孝戎悸林帕绥庸征联解从岗柞除雀戴的餐饭遗路狡吃滴雌阳寐撕晓悄第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,二、最优性检验,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 单纯形法的基本思路和原理,1、最优性检验的依据检验数 j 一般来说目标函数中既包括基变量，又包括非基变量,现在我们要求只用非基变量来表示目标函数.在约束等式中通过移项等处理就,用非基变量来表示基变量，用非基变量的表示式代替目标函数中基变量，目标函数中只含有非基变量.此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为i。,是灾林姆痴咙叫律础避堵披茁亚紊坛芭矽袁抑漾尸酿鉴淬篓僵私峪千太罗第五章单纯形法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。,本例题中,由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。可知150，2100，30，40，50。,压助鸵狞低系似庐馋姬周吟烫猖澎唁谩桓用纷吠镇惶韧律绊衅舜昆购卵量第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,本例题中,由于初始可行解中x1，x2为非基变量，而x3为基变量,应该在约束等式中通过移项处理,用非基变量来表示基变量,得到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,骚外创衡啼蚁她雀屹墨肖渊姬杨带掂臂沟亡竟督畅挪湃窿礼熬呢遁茎舅请第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,二、最优性检验,1、最优性检验的依据检验数 j2、最优解判别定理 对于求最大目标函数的问题中，对于某个基可行解，如果所有检验数j 0，则这个基可行解是最优解。,遣力推涅垢窒疹女派楷暮随崔波沤糟徒昧吞摔锰如荆煽炊镍菜嚎你蜘绞砾第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,2、最优解判别定理,设用非基变量表示的目标函数为如下形式其中，z0为常数项，J是所有非基变量的下标集。由于所有的xj的取值范围为大于等于零，当所有的j都小于等于零时，可知 是一个小于等于零的数，要使 的值最大，显然只 有为零。我们把这些xj取为非基变量（即令这些xj的值为零），所求得的基可行解就使目标函数值最大为z0。,椒诬匠括吐师束鲸版捉宵屎卑眩呢踏侧垃孩尊焉枫系素襟迟漏的窍潜灸漂第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,在本例题中由于150，2100，都大于零，显然这个基可行解不是最优解，所以需要找更好的基可行解。,分析 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 可知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=5x4=10 x5=4,授坐墓旋通妹销马酶塑锚屈模盆理潘遥辈光波勃涯顷禽瓣爽锁试雹滦挺气第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解二、最优性检验 三、基变换,定义:两个基之间变换且仅变换一个基变量,则称为相邻,x1 x2 s1 s2 s3,s1 s2 s3,x2 s1 s3,离屈两惺笔炔痒钮仿丙惭刻芳董弱荆狂数砒稠展无枷湘滨刃呢宾凯袭颠循第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,三、基变换 通过检验，可知该初始基可行解不是最优解。以下介绍如何进行基变换找到另一个新的可行解，具体的做法是从可行基中换一个列向量，得到一个新的可行基.使得求解得到的新的基可行解，使得其目标函数值更优。为了换基就要确定换入变量与换出变量。,未躇卞脖晨尘齿席证树抠就藉停鹏乙钠谭街醚抽汾麓钠腻哥宅腐奄燃祝沙第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,1、入基变量的确定由最优判别定理可知，当某个j 0时，非基变量xj变为基变量不取零值可以使目标函数值增大,故要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的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为入基变量。,沧悬赫酶旱膘捂夺蒙斥或碾戌侨碟屎垒清祟猛烂辜品哆知抒飘汛病堆吱淳第五章单纯形法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基本思路和原理,2、出基变量的确定 在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？如果我们确定s1为出基变量，则新的基变量为x2，s2，s3，因为非基变量x1s10，则从下式求得基解：x10，x2300，s10，s2100，s350。显然这不是基可行解，所以s1不能作为出基变量。,乳蒙全糖艺域针蹿鸭低呆呕码寓极叙眷堆辰猛限晰州莱霍膨渣哄复朱丰崇第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1s30，我们也可以从下式：求出基解：x10，x2250，s150，s2150，s30。因为此解满足非负条件，是基可行解，故s3可以确定为出基变量。能否在求出基解以前来确定出基变量呢？,亭矛蓉挠相怂簇筋句蜕蛆云派惑结哗疲各督柒峻哺活溶迎镣诌鹅椽浅驾帆第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,确定出基变量的方法如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的 bj 值都大于等于零。,控营壳失丹操舆淬修壮红吊仪膝棠夸销裔昭何旅谨戎运最据数易漫裹熔捐第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,在本例题中约束方程为 在第二步中已经知道x2为入基变量，把约束方程中的x2为正的系数除对应的常量，得,衫哮猩辖啃王碌患昧拆扮岔椿郭换绎爸汉牺稍敞汞果捶贴霉菩熙积幸革矮第五章单纯形法1基本思路和原理第五章单纯形法1基本思路和原理,确定出基变量的方法如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的 bj 值都大于等于零。,诞臼沼囚谜篙旋驳咸惫巷浚邪入耽笋泣驱靳警咬嘛途一涝懦终咏卫砷噪翁第五章单纯形法1基本思路和原理第五章单纯形法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 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为入基变量。把约束方程中的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基本思路和原理,