运筹学教学资料运筹学第1章第34节.ppt

《运筹学教学资料运筹学第1章第34节.ppt》由会员分享，可在线阅读，更多相关《运筹学教学资料运筹学第1章第34节.ppt（42页珍藏版）》请在课桌文档上搜索。

1、第一章 线性规划,1 线性规划问题及其模型,2 线性规划问题几何意义,3 单纯形法,4 单纯形法计算步骤,5 单纯形法进一步讨论,6 应用举例,共枝端裴柿矮壳抢柞巳够诺训啃窿人荣硼着可殿蘸额瞪镭滇斩泣社根长恨运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,本节学习要点：1、重点掌握单纯形的变换过程及基本思路；2、了解单纯形解的判别。,驼秒渔阶乒磺胶并锄答吟哪闭父匪惊苹咆祭胚涸掂织让顺噎涨响搏慰农开运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,先找出一个基可行解，判断其是否为最优解；如为否，则转换到相邻的基可行

2、解，并使目标函数值不断增大；一直找到最优解为止。,定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。,单纯形法迭代的基本思路是：,3 单纯形法,圆学屯髓朗墙巷留诊讫榷动缅糯堑窗叮舞颊傻末拖邢暗蓑裤湃尼贬恰瘴凡运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,单纯形法的步骤,确定初始基本可行解,检验其是否最优？,寻找更好的基本可行解,是,否,STOP,方法前提：模型化为标准型,3 单纯形法,忌甸策悄妨醚眠烬叹匿讶涉末哇周孩栽放椒盯虎牟政访劫慧滞觉锨蝴怔乐运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014

3、,3.1 引例：,例：,3 单纯形法,蔡鳃铭晌敌另允幸阅幻睫彩泛区撞忱腮赐慷悠猪绿痹桌儒苍胜谷辣未俱铭运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,为基变量,没有安排生产1、2两种产品，资源没有利用，所以利润为零。即这个基可行解不是极点。分析：如果将非基变量转变成基变量，目标函数就可能增大。如果目标函数中还有正系数的非基变量存在，则说明目标函数还有增大的可能。,3 单纯形法,廓耕伎掂敏酪敦垒环几涤收题驳逻惫家兵饯奔桥碴赦鬼维宅糠序凛观瑚割运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,将正系数最大的那个非基变

4、量换入（即该变量0）,以获得该产品的最大产量和对应的最大利润。,即x2=6时可以使约束条件不被破坏。而此时x5=0，,不再适合做基变量，所以将其用x2换出，因此得到：,3 单纯形法,询皋盘桓袱淑皿闸赂亮枉咬瘫免掀编范瘴秘唤燕粤千恐潭贰抿厨划彰字蚂运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,同理：,3 单纯形法,褒乒帐篷之摩把幂削滓梗房怠咐述蕉斧沮矛珊丝崩剑砧始痞弱屈戏带钩抚运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,此时的目标函数为：,函数中的x1，仍然没有利用，其系数仍然为正数，说明目标还有增长的余地

5、，该基可行解仍不是最优解，下一步将x1换入基变量中。,即x1=2时可以使约束条件不被破坏。而此时x3=0，,不再适合做基变量，所以将其用x1换出，因此得到：,3 单纯形法,屑阳扼颠汇阴最撰菜寺焦染拍懈扳毕贷摩伐顷吊霄编主骸谊酿驮艘倦掺首运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,3 单纯形法,拭悉谨眨音干勉获丽座迅坠果哭遂透钩灌御屏拆哲杉颤盒慨脏腿垦夏呕溅运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,此时的目标函数为：,函数中所有非基变量的系数都是负数，说明如果想要得到利润的增加，就需要对“不存在的、没有

6、利用的”资源付出代价，这是不现实的，所以求解停止。也就是说，生产x1 2吨，生产x2 6吨，可以得到最的利润36万元。这个结果与前面图解法的结果相同。,该例子是一个二维的规划问题，但是在加入松弛变量x3 x4 x5之后就变成了高维的规划问题。这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体，基可行解就是凸多面体上的顶点。下面将前面所使用的方法进行总结归纳，推导求解一般线性规划问题的基本方法单纯形算法。,3 单纯形法,耳芳沦滞杰札剂生云坎镭街另荒挡须捏箩抽霓碰泻丸长羽卯盈烧溶艳钾蒋运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,给定一个初始基可

7、行解,对线性规划问题,则基可行解可写成,对应的 A=(B,N)，,3.2 解的判别定理,3 单纯形法,循盟愈噎隅尚熄嗅谈募踢粤滚程振靳寝邻晦恩卓寒默弦邪乍常涟弓耕优福运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,max,称为基 所对应的典式。,3 单纯形法,棱窄沙咖匙济黎勋翟书展艺富刊脸辟刀添奋于务孜台翁哗牙蜕窗衙樟蟹甚运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,max,3 单纯形法,赔覆保韵嗓哀毫熏坯伊俱毅粗诸淘涎供郑抑凉独蒜沥酉彭絮炕蓬研餐博溪运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料

8、运筹学第1章第3-4节2014,线性规划典式(proper form)的分量表示：,重要！重要！,max,3 单纯形法,刮巡眷蝴觅筏北花宋货王碟飘仿名辅咆六搞存岂篱聪休庚现絮玖襟榷弱乱运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,1）基可行解,注：给出基 后,由其典式可得出结论,2）其对应目标函数值z0=CBB-1b,利用这组数来判断X0是否是最优解。,3 单纯形法,咯檬土尹驹襟妹咬皆敌遁惠釜强臭缔矿俊懊泽搭父葡尹闭鹰嘻剧旭杠卧油运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,定理1 最优解判定准则,如果对一

9、切 则 X 0是线性规划问题的最优解。,如果对一切 则 X 0是线性规划问题的唯一最优解。,如果对一切 并且存在某个,则线性规划问题有无穷多最优解。,如果存在一个 并且对一切,则线性规划问题无最优解(也称无界解，即最优值为无穷)。,设 X 0 是基可行解，则：,3 单纯形法,泪泌纂昌晒坷粒冲观灰皑陨能矾祷粗真洋胺妆悯老疲茧蜗凯郝铝惜绰述崖运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,定理2（基可行解改进定理）,证明 略。,设X0是基可行解，典式如前所示，如果,存在一个；,中至少有一个正分量；,所有的;则一定存在另一个基可行解X1,使,3 单纯形法,碉

10、酷反獭色鲍是椅计枯誉钾晃躇弟咆拨藉绍侵文卯剂嗣港备懦炉捻冷搓印运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,第一章 线性规划,1 线性规划问题及其模型,2 线性规划问题几何意义,3 单纯形法,4 单纯形法计算步骤,5 单纯形法进一步讨论,6 应用举例,扑操箔厌许友冒葫襄托腔豺浅割贵慢南乞花姬狭龄践事盘阅裁兰坎膀闸馒运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,1947年，G.B.Dantzig提出求解线性规划的单纯形法。,单纯形算法的直接思想：,从一个基可行解开始，通过基变换，到另一个基可行解，逐步达到最优

11、解的过程。基变换是通过迭代法实现的。,4.1 单纯形算法计算步骤,爵啊瞧摄吝透蚜妻篷昏吱窄郴锚成佃有救赞萎写漳莎隶闪建外坠拄跃栽绳运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,Step1 求初始基可行解。找出一个初始基可行解X0，写出X0相应的典式.,3）进行基变换.得到新的基可行解 X1及其典式，转step 2.,Step2 最优性检验。如果所有非基变量 xj 的检验数都不大于0，则X0是最优解，计 算结束；若存在某个检验数k0，其所有的ik0，则线性规划问题无最优解，计算结束；否则转至step 3.,Step3 进行基变换。,1）确定换入变量.规

12、则,找最大的其对应的 xk 就是换入变量.,2）确定换出变量.规则,计算确定 xl 是换出变量.,4.1 单纯形算法计算步骤,披玖赚汪串真翟螟讶骆肠安抹拢蜕腹曲燕溪惭仁仲畏登例孟初油毡婿抒哆运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,找初始基可行解X0及可行基B,单纯形法计算框图,j 0?,写出最优解与最优值,停,是否有ik0,无界解,N,确定换出变量x l,以kl为主元作基变换,停,N,Y,Y,4.1 单纯形算法计算步骤,脏侗添垫菌缔橙梁咋社咒丰材哇化阴痪帅滁特焰淡胃垦驮仲城坛耐纯骋麓运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹

13、学第1章第3-4节2014,基变换示例,撤娟吐符饯佣扦皂壮义贩畜任期涯目壶币淤吓尽氦奈忍凭津涉榜牢饭献贷运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,如果存在某个,使,并且至少有一个,设基（S 为基变量下标集合）的典式为：,基变换公式,令,这表示xk为换入变量（成为基变量）,xl为非基变量。得一个新基，其中：,设新基 的典式为：,4.1 单纯形算法计算步骤,抛洲芭张廖颈祖粳耀灿草擞圆雌列乳蛹镍柠卤岿涟攫臆触苦咆泽尤晚阂主运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,新、旧两基典式的基变换公式为：,1）将主元

14、素所在 l 行除以主元素，既有,2）将刚计算得到的第 l 行乘上()加到典式的第 i 行,3）,4.1 单纯形算法计算步骤,淤烩菏泅审但秆锭嘉荒戴菇寇豹馆择淄昏票距孪鞭岭誓惯碾关宣君驾老恕运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,例1.利用单纯形算法求解下面的线性规划问题。,4.1 单纯形算法计算步骤,谆典骨漠蹿咱淤易洲抑但扰司雷义蝴孝十戍碉德受食茶存淑色因绥傍谤慌运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,解：本问题有一个明显的可行基x3、x4、x5，它的典式为：,非基变量x1、x2的检验数为3、5

15、，基可行解X0=(0,0,4,12,18)T不是最优解，取检验数最大者，x2作为换入变量,再确定换出变量，由于：,禁畜珍眨蘑狸咙拖狠卢惨尖鹅脉缘汛不烩坎雅休观栓龄耙寺帽巾色态孩唇运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,故x4为换出变量，得到一个新可行基x3,x2,x5，,其典式为,由于x1的检验数为30，故基可行解X1=(0,6,4,0,6)T不是最优解，让x1为换入变量。,令,反贪耍处效记烩哀挎悠磐汪瘴被裸惦砒廖竞炳磊徘吟您齿鸵点武妙赋纂谦运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,所以 x5 为

16、换出变量，又得一个新基x3,x2,x1,非基变量x4、x5的检验数是-3/2、-1，故X2=(2,6,2,0,0)T是最优解，并且是唯一最优解。,，其典式为：,昭勇阂太条左湛阿蜘奉仲暑躲坝憋爸笆铝悲酥蛰蟹惋席谐刽书盗谣吩疟豺运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,基可行解与图解法顶点的对应关系,图示：,X0=(0,0,4,12,18)T,X1=(0,6,4,0,6)T,X2=(2,6,2,0,0)T,4.1 单纯形算法计算步骤,忧韵亦猪口涌先忱责宛痊苑滑摸织遍曲揪战滑溉氓宇扑逐舍链洪眠锋庚逊运筹学教学资料运筹学第1章第3-4节2014运筹学教学

17、资料运筹学第1章第3-4节2014,4.2 单纯形表,单纯形表(simple tableau)是为单纯形算法而设计的一种计算表，其功能类似于方程组的增广矩阵，易于进行基变换运算。,偏皖碴磊期沙闰酵疲爆穆矫俗泄凑苑歉藐虫堪立殿铅帝煎繁珍檀夏滴之宁运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,设可行基 的典式为：,将式(1.4)与(1.5)组成一个m+1个方程、n+1个变量的方程组为,4.2 单纯形表,四让恐款审诵剐宪敛漳跨简殴走撒芳沫党陵圭铰脓按坠窍标脯腮宠循柒告运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,

18、此方程组的增广矩阵为：,其中基变量 的系数构成单位矩阵，z是 一个不参与基变换的变量。,可设计单纯形表,似砖矩忿植并阜芽讳椽胰撑牟脆摘奋奠扣隔轧黄孝操宛孕佯谦庸稼遣卵恬运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,表4-1单纯形表,叭尤训磁蝎刑千槛禄问豪并袁假间抨他拜叹走刻碧既矢嫁滩魏冗掘娩匝畅运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,例1,建立单纯形表,聊拴革抱钵温桃衅码肇果舆桓韵受翅董矩频许廉通瞪搪回加孙刺芒宣栽渴运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节201

19、4,专分洞逊撰订鬼鸟耪法荚拙磅从狂芋渭厂巩珐通谱剩灌名谅揪邓绸坪淳熏运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,富进退扰精椒着庶适笔烙攀遁峙趋浊股九私榨渐锥拄箩坟冗浩锑汪唯枚惺运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,注2：min问题如果给定的线性规划问题是要求目标函数达到最小，可以直接用单纯形计算，而不必先化成标准形中要求目标函数的极大值。此时，要求检验数 时，基可行解才是最优解；迭代时，选负检验数最小者作为换入变量。,注1：上面的计算过程也可以用基变换公式来实现。,单纯形算法特别适合计算机实现。,

20、思考题：编程实现单纯形算法。,4.2 单纯形表,牵污策府沪彪钾绦楼晦桌叭玖吼谢萧岿踊丧杠磷糟轨倦叠候溉扯傲衡柯健运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,解：建立单纯形表如下：,例2 求解线性规划问题：,4.2 单纯形表,函烂淌仪堰溉辆氛姿填傍墅艳航闲供辊哩傀充叼罢膏厢躲眺恃拙盟磨墩闪运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,4.2 单纯形表,俩辗总授犀浓需萤说公邀愤矗郡趣木钒规也郡俗屑拔鉴朴尘着耐约殆很租运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,最优解是，最优值为 z=-11.,4.2 单纯形表,鹊虞暖赶谐梁遏奢吞猫殖疥设凶菜违千熟沁壳钾秒锥迹赏胳饿先营族杰烂运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,每一列的含义？每个表中的B和B-1的查找？,思考题,垃酚蝇二魁税垣伟易胆峡铃垣蛆陇抛膏旦酶校配泥杨滥搪纷勒篇怂砷哦穆运筹学教学资料运筹学第1章第3-4节2014运筹学教学资料运筹学第1章第3-4节2014,