单纯形法第1部分.ppt

《单纯形法第1部分.ppt》由会员分享，可在线阅读，更多相关《单纯形法第1部分.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 13 3 单纯形法单纯形法 图解法的局限性图解法的局限性(1)图解法的优点:简单、直观简单、直观;(2)局限性:对仅含有两个至多不超过三个两个至多不超过三个决策变量决策变量的线性规划才适于使用图解法，大多数情况下仅对含有两个决策变量的线性规划才使用图解法求解;(3)对含有三个以及三个以上决策变量三个以上决策变量的线性规划则应考虑使用更加有效的通用算法通用算法单纯形法来进行求解。一、单纯形法的基本思想一、单纯形法的基本思想1、顶点的逐步转移顶点的逐步转移 即从可行域的从可行域的一个顶点一个顶点（基本可行（基本可行解）开始，解）开始，转移到另一个顶点转移到另一个顶点（另一个（另一个基本可行解）

2、的迭代过程，基本可行解）的迭代过程，转移的条件转移的条件是是使使目标函数值得到改善目标函数值得到改善（逐步变优），（逐步变优），当目标函数达到最优值时，问题也就得当目标函数达到最优值时，问题也就得到了最优解。到了最优解。单纯形算法的基本思路单纯形算法的基本思路根据根据线性规划问题的可行域是凸多边线性规划问题的可行域是凸多边形或凸多面体形或凸多面体(定理定理1.1)，一个线性规划问，一个线性规划问题有最优解，就一定可以在可行域的顶点题有最优解，就一定可以在可行域的顶点上找到上找到(定理定理1.3)。于是，若某线性规划只有唯一的一个若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可最优

3、解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找优解，那么肯定在可行域的顶点中可以找到至少一个最优解。到至少一个最优解。顶点转移的依据？顶点转移的依据？转移条件？转移条件？转移结果？转移结果？使使目标函数值得到改善目标函数值得到改善得到得到LP最优解，目标函数达到最优值最优解，目标函数达到最优值（单纯形法的由来？（单纯形法的由来？）2需要解决的问题：需要解决的问题：(1)如何寻找初始顶点如何寻找初始顶点(基本可行解基本可行解)?(2)为了使目标函数逐步变优，怎么转移为了使目标函数逐步变优，怎么转移?即如

4、何找到下一顶点即如何找到下一顶点(基本可行解基本可行解)?(3)目标函数达到最优的判断标准是什么？目标函数达到最优的判断标准是什么？二、单纯形法原理（用代数方法求解二、单纯形法原理（用代数方法求解LP）例例1-7第第一一步步：引引入入非非负负的的松松弛弛变变量量x4,x5,将将该该LP化为标准型化为标准型第二步：第二步：寻求初始可行基，确定基变量寻求初始可行基，确定基变量对应的基变量是对应的基变量是x4，x5；第第三三步步：写写出出初初始始基基本本可可行行解解和和相相应应的目标函数值的目标函数值两个关键的基本表达式：两个关键的基本表达式：用非基变量表示基变量的表达式用非基变量表示基变量的表达式

5、用用非非基基变变量量表表示示目目标标函函数数的的表达式表达式请解释结果的经济含义请解释结果的经济含义不生产任何产品，资源全部节余（不生产任何产品，资源全部节余（x4=3，x5=9），三种产品的总利润为），三种产品的总利润为0！第四步：第四步：分析两个基本表达式，看看目分析两个基本表达式，看看目标函数是否可以改善？标函数是否可以改善？分析分析用非基变量表示目标函数的表达式用非基变量表示目标函数的表达式非基变量前面的系数均为正数，所以任何一非基变量前面的系数均为正数，所以任何一个个非基变量进基非基变量进基(变为基变量变为基变量)都能使都能使Z值增加值增加,通常把非基变量前面的系数叫通常把非基变量前

6、面的系数叫“检验数检验数”；选哪一个非基变量进基？选哪一个非基变量进基？选选x1为为进基变量进基变量（换入变量换入变量）问题讨论：问题讨论：能否选其他的非基变量进基？能否选其他的非基变量进基？任意一个任意一个任意一个正检验数对应的非基变量任意一个正检验数对应的非基变量最大正检验数对应的非基变量最大正检验数对应的非基变量排在排在最前面的正检验数对应的非基变量最前面的正检验数对应的非基变量 确定出基变量：确定出基变量：问题讨论问题讨论x1进进基基意意味味着着其其取取值值从从0变变成成一一个个正正数数（经经济济意义意义生产生产A产品），能否无限增大？产品），能否无限增大？当当x1增加时，增加时，x4

7、，x5如何变化？如何变化？现在的非基变量是哪些？现在的非基变量是哪些？具体如何确定换出变量？具体如何确定换出变量？由由用非基变量表示基变量的表达式用非基变量表示基变量的表达式 当当x1增增加加时时，x4，x5会会减减小小，但但有有限限度度必必须大于等于须大于等于0，以保持解的可行性！于是，以保持解的可行性！于是当当x1的的值值从从0增增加加到到3时时，x4首首先先变变为为0，此时，此时x5=60因此因此选选x4为出基变量（换出变量）为出基变量（换出变量）。这这种种用用来来确确定定出出基基变变量量的的规规则则称称为为“最小比值原则最小比值原则”（或（或原则）原则）。如果如果P10，会出现什么问题

8、？，会出现什么问题？最小比值原则会失效！最小比值原则会失效！Why?最小比值原则失效最小比值原则失效如果如果P1=(-1,0)T，如果如果P1=(-1,-1)T，这样做,对吗?0元素或负元素不必计算比值，解的可行性自然满足主元列全部为0元素或负元素，LP无“有限最优解”只有当只有当aik0时，时，比值才有意义比值才有意义基变换基变换新的基变量新的基变量x1,x5；新的非基变量；新的非基变量x2,x3,x4；写出写出用非基变量表示基变量的表达式：用非基变量表示基变量的表达式：可得新的基本可行解可得新的基本可行解X（1）=（3，0，0，0，6）T由由写出写出用非基变量表示目标函数的表达式用非基变量

9、表示目标函数的表达式:可得相应的目标函数值为可得相应的目标函数值为Z（1）=6检验数仍有正的检验数仍有正的返回返回进行讨论。进行讨论。第五步：第五步：上述过程何时停止？上述过程何时停止？分分析析用用非非基基变变量量表表示示目目标标函函数数的的表表达达式式，如如果果让让负负检检验验数数所所对对应应的的变变量量进进基基，目目标标函函数数值将下降！值将下降！当当用用非非基基变变量量表表示示目目标标函函数数的的表表达达式式中中，非非基基变变量量的的系系数数（检检验验数数）全全部部非非正正时时，当当前前的的基本可行解基本可行解就是就是最优解最优解!为什么？为什么？三、表格单纯形法：三、表格单纯形法：1、

10、初始单纯形表的建立初始单纯形表的建立 (1)表格结构：表格结构：jCj23300bxjx1x2x3x4x5CBXB 0X43111100X5914701 -Z023300（2）表格设计依据：）表格设计依据：将将-Z看看作作不不参参与与基基变变换换的的基基变变量量，把把目目标标函函数数表表达达式式改改写写成成方方程程的的形形式式，和和原原有有的的m个个约约束束方方程程组组成成一一个个具具有有n+m+1个个变变量量、m+1个方程的方程组：个方程的方程组：取出系数写成增广矩阵的形式：取出系数写成增广矩阵的形式：-ZX1X2XnXn+1Xn+2Xn+mb-Z，Xn+1，Xn+m所对应的系数所对应的系数

11、列向量构成一个基列向量构成一个基用矩阵的初等行变换将该基变成单位阵用矩阵的初等行变换将该基变成单位阵,这时这时变变成成0，相相应应的的增增广广矩矩阵变成如下形式：阵变成如下形式：其中，其中，j=1，2，n；（3）检验数的两种计算方法：）检验数的两种计算方法：利利用用矩矩阵阵的的行行变变换换，把把目目标标函函数数表表达达式式中中基变量前面的系数变为基变量前面的系数变为0；使用计算公式使用计算公式增增广广矩矩阵阵的的最最后后一一行行就就是是用用非非基基变变量量表表示示目目标标函函数数的的表表达达式式,(j=1,2,n)就就是是非基变量的检验数非基变量的检验数。2、例、例1-7的表格单纯形法计算过程

12、：的表格单纯形法计算过程：CB XB Cj b xj 2 3 3 0 0 x1 x2 x3 x4 x5 j 0 0 X4 X5 3 9 1 1 1 1 0 1 4 7 0 13/19/1 -Z 0 2 3 3 0 0 2 0 X1 X5 3 6 1 1 1 1 0 0 3 6 -1 1 3/1 6/3 -Z-6 0 1 1 -2 0 2 3 X1 X2 1 2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 -Z-8 0 0 -1 -5/3 -1/3从最优表可知从最优表可知:该该LP的的最优解是最优解是X*=(1,2,0,0,0)T相应的目标函数最优值是相应的目标函数最优值是Zmax=8 第二次作业第二次作业 P47：6（1，2），），7下周下周4交交