《运筹学教学资料》运筹学第1章第3-4节.pptx
22线性规划问题几何意义33单纯形法11线性规划问题及其模型66应用举例55单纯形法进一步讨论44单纯形法计算步骤第一章线性规划
01重点掌握单纯形的变换过程及基本思路;02了解单纯形解的判别。本节学习要点:
先找出一个基可行解,判断其是否为最优解;如为否,则转换到相邻的基可行解,并使目标函数值不断增大;一直找到最优解为止。定义:两个基可行解称为相邻的,如果它们之间变换且仅变换一个基变量。单纯形法迭代的基本思路是:3单纯形法
单纯形法是一种迭代的算法,它的思想是在可行域的顶点——基本可行解中寻优。由于顶点是有限个,因此,算法经有限步可终止。单纯形法的步骤确定初始基本可行解检验其是否最优?寻找更好的基本可行解是否STOP方法前提:模型化为标准型3单纯形法
引例:01例:023单纯形法
为基变量没有安排生产1、2两种产品,资源没有利用,所以利润为零。即这个基可行解不是极点。分析:如果将非基变量转变成基变量,目标函数就可能增大。★如果目标函数中还有正系数的非基变量存在,则说明目标函数还有增大的可能。3单纯形法
将正系数最大的那个非基变量换入(即该变量≠0),以获得该产品的最大产量和对应的最大利润。不再适合做基变量,所以将其用x2换出,因此得到:即x2=6时可以使约束条件不被破坏。而此时x5=0,单纯形法
3单纯形法同理:
此时的目标函数为:函数中的x1,仍然没有利用,其系数仍然为正数,说明目标还有增长的余地,该基可行解仍不是最优解,下一步将x1换入基变量中。即x1=2时可以使约束条件不被破坏。而此时x3=0,不再适合做基变量,所以将其用x1换出,因此得到:3单纯形法
3单纯形法
此时的目标函数为:该例子是一个二维的规划问题,但是在加入松弛变量x3x4x5之后就变成了高维的规划问题。这时可以想象,满足所有约束条件的可行域是高维空间的凸多面体,基可行解就是凸多面体上的顶点。下面将前面所使用的方法进行总结归纳,推导求解一般线性规划问题的基本方法——单纯形算法。函数中所有非基变量的系数都是负数,说明如果想要得到利润的增加,就需要对“不存在的、没有利用的”资源付出代价,这是不现实的,所以求解停止。也就是说,生产x12吨,生产x26吨,可以得到最的利润36万元。这个结果与前面图解法的结果相同。单纯形法1234
3.2解的判别定理给定一个初始基可行解,对线性规划问题则基可行解可写成对应的A=(B,N),3单纯形法
max称为基所对应的典式。3单纯形法
max单纯形法
线性规划典式(properform)的分量表示:称是非基变量的检验数。重要!重要!max3单纯形法
1)基可行解注:给出基后,由其典式可得出结论2)其对应目标函数值z0=CBB-1b(针对非基变量)3)检验数利用这组数来判断X0是否是最优解。3单纯形法
定理1[最优解判定准则]①如果对一切则X0是线性规划问题的最优解。②如果对一切则X0是线性规划问题的唯一最优解。③如果对一切并且存在某个则线性规划问题有无穷多最优解。④如果存在一个并且对一切则线性规划问题无最优解(也称无界解,即最优值为无穷)。设X0是基可行解,则:3单纯形法
定理2(基可行解改进定理)证明略。设X0是基可行解,典式如前所示,如果①存在一个;中至少有一个正分量;③所有的;则一定存在另一个基可行解X1,使3单纯形法
第一章线性规划011线性规划问题及其模型022线性规划问题几何意义033单纯形法044单纯形法计算步骤055单纯形法进一步讨论066应用举例07
4.1单纯形算法计算步骤单纯形算法的直接思想:1947年,提出求解线性规划的单纯形法。从一个基可行解开始,通过基变换,到另一个基可行解,逐步达到最优解的过程。基变换是通过迭代法实现的。
4.1单纯形算法计算步骤Ste