文档介绍：该【《运筹学教学资料》运筹学第1章3-4节 】是由【相惜】上传分享，文档一共【41】页，该文档可以免费在线阅读，需要了解更多关于【《运筹学教学资料》运筹学第1章3-4节 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第一章 线性规划
§1 线性规划问题及其模型
§2 线性规划问题几何意义
§3 单纯形法
§4 单纯形法计算步骤
§5 单纯形法进一步讨论
§6 应用举例
本节学习要点：
1、重点掌握单纯形的变换过程及根本思路；
2、了解单纯形解的判别。
先找出一个基可行解，判断其是否为最优解；
如为否，那么转换到相邻的基可行解，并使目标函数值不断增大；
一直找到最优解为止。
定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。
单纯形法迭代的根本思路是：
3 单纯形法
单纯形法是一种迭代的算法，它的思想是在可行域的顶点——基本可行解中寻优。由于顶点是有限个,因此，算法经有限步可终止。
单纯形法的步骤
确定初始根本可行解
检验其是否最优？
寻找更好的根本可行解
是
否
STOP
方法前提：模型化为标准型
3 单纯形法
引例：
例：
3 单纯形法
为基变量
没有安排生产1、2两种产品，资源没有利用，所以利润为零。即这个基可行解不是极点。
分析：如果将非基变量转变成基变量，目标函数就可能增大。
★ 如果目标函数中还有正系数的非基变量存在，那么说明目标函数还有增大的可能。
3 单纯形法
将正系数最大的那个非基变量换入〔即该变量≠0〕,以获得该产品的最大产量和对应的最大利润。
即x2=6时可以使约束条件不被破坏。而此时x5=0，
不再适合做基变量，所以将其用x2换出，因此得到：
3 单纯形法
同理：
3 单纯形法
此时的目标函数为：
函数中的x1，仍然没有利用，其系数仍然为正数，说明目标还有增长的余地，该基可行解仍不是最优解，下一步将x1换入基变量中。
即x1=2时可以使约束条件不被破坏。而此时x3=0，
不再适合做基变量，所以将其用x1换出，因此得到：
3 单纯形法
3 单纯形法