《运筹学教学资料》运筹学第1章第3-4节.ppt
《《运筹学教学资料》运筹学第1章第3-4节.ppt》由会员分享,可在线阅读,更多相关《《运筹学教学资料》运筹学第1章第3-4节.ppt(42页珍藏版)》请在三一办公上搜索。
1、第一章 线性规划,1 线性规划问题及其模型,2 线性规划问题几何意义,3 单纯形法,4 单纯形法计算步骤,5 单纯形法进一步讨论,6 应用举例,本节学习要点:1、重点掌握单纯形的变换过程及基本思路;2、了解单纯形解的判别。,先找出一个基可行解,判断其是否为最优解;如为否,则转换到相邻的基可行解,并使目标函数值不断增大;一直找到最优解为止。,定义:两个基可行解称为相邻的,如果它们之间变换且仅变换一个基变量。,单纯形法迭代的基本思路是:,3 单纯形法,单纯形法的步骤,确定初始基本可行解,检验其是否最优?,寻找更好的基本可行解,是,否,STOP,方法前提:模型化为标准型,3 单纯形法,3.1 引例:
2、,例:,3 单纯形法,为基变量,没有安排生产1、2两种产品,资源没有利用,所以利润为零。即这个基可行解不是极点。分析:如果将非基变量转变成基变量,目标函数就可能增大。如果目标函数中还有正系数的非基变量存在,则说明目标函数还有增大的可能。,3 单纯形法,将正系数最大的那个非基变量换入(即该变量0),以获得该产品的最大产量和对应的最大利润。,即x2=6时可以使约束条件不被破坏。而此时x5=0,,不再适合做基变量,所以将其用x2换出,因此得到:,3 单纯形法,同理:,3 单纯形法,此时的目标函数为:,函数中的x1,仍然没有利用,其系数仍然为正数,说明目标还有增长的余地,该基可行解仍不是最优解,下一步
3、将x1换入基变量中。,即x1=2时可以使约束条件不被破坏。而此时x3=0,,不再适合做基变量,所以将其用x1换出,因此得到:,3 单纯形法,3 单纯形法,此时的目标函数为:,函数中所有非基变量的系数都是负数,说明如果想要得到利润的增加,就需要对“不存在的、没有利用的”资源付出代价,这是不现实的,所以求解停止。也就是说,生产x1 2吨,生产x2 6吨,可以得到最的利润36万元。这个结果与前面图解法的结果相同。,该例子是一个二维的规划问题,但是在加入松弛变量x3 x4 x5之后就变成了高维的规划问题。这时可以想象,满足所有约束条件的可行域是高维空间的凸多面体,基可行解就是凸多面体上的顶点。下面将前
4、面所使用的方法进行总结归纳,推导求解一般线性规划问题的基本方法单纯形算法。,3 单纯形法,给定一个初始基可行解,对线性规划问题,则基可行解可写成,对应的 A=(B,N),,3.2 解的判别定理,3 单纯形法,max,称为基 所对应的典式。,3 单纯形法,max,3 单纯形法,线性规划典式(proper form)的分量表示:,重要!重要!,max,3 单纯形法,1)基可行解,注:给出基 后,由其典式可得出结论,2)其对应目标函数值z0=CBB-1b,利用这组数来判断X0是否是最优解。,3 单纯形法,定理1 最优解判定准则,如果对一切 则 X 0是线性规划问题的最优解。,如果对一切 则 X 0是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学教学资料 运筹学 教学 资料

链接地址:https://www.31ppt.com/p-5904500.html