《第一章 1.3.1 单纯形法的基本思路》由会员分享，可在线阅读，更多相关《第一章 1.3.1 单纯形法的基本思路（33页珍藏版）》请在金锄头文库上搜索。
1、2017/9/1,1,想一想:图解法是否有局限性？,2017/9/1,2,1947年G.B.Dantzig提出的单纯形法提供了方便、有效的通用算法求解线性规划。,13 单纯形法,一、单纯形法的基本思想1、顶点的逐步转移,即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。,2017/9/1,3,根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。 于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行
2、域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。,顶点转移的依据？,2017/9/1,4,2需要解决的问题： (1)为了使目标函数逐步变优，怎麽转移？ (2)目标函数何时达到最优 判断标准是什麽？,例1-1 ,某工厂计划生产A、B两种产品，具体资料见下表，其中，一件A产品获利2元，一件B产品获利3元，问如何安排计划实现工厂利润最大化？,二、单纯形法原理（用代数方法求解LP）,2017/9/1,5,试写出线性规划模型并将其转化为标准型,2017/9/1,6,2017/9/1,7,第一步：引入非负的松弛变量和剩余变量 x3,x4,x5, 将该LP化为标准型,
3、2017/9/1,8,第二步：寻求初始可行基，确定基变量,对应的基变量是:,第三步：写出初始基本可行解和相应的 目标函数值,x3 x4 x5,2017/9/1,9,两个关键的基本表达式：用非基变量表示基变量的表达式,初始基本可行解,2017/9/1,10,用非基变量表示目标函数的表达式,不生产任何产品，资源全部节余（ x3=8 x4=16，x5=12），产品的总利润为0！,当前的目标函数值:,请解释结果的经济含义:,2017/9/1,11,第四步：分析两个基本表达式，看看目标函数是否可以改善？, 分析用非基变量表示目标函数的表达式,非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值
4、增加 通常把非基变量前面的系数叫“检验数”；,2017/9/1,12, 从经济意义上讲.安排生产任一种产品都能使利润指标增加,所以只要在目标函数的表达式中还存在有“正的检验数”的非基变量,表明目标函数值还有增加的可能,就需要将非基变量与某个基变量进行对换.,怎么换?,2017/9/1,13, 选哪一个非基变量进基？ 选x1为进基变量（换入变量） 问题讨论：能否选其他的非基变量进基？, 任意一个 任意一个正检验数对应的非基变量 最大正检验数对应的非基变量 排在最前面的正检验数对应的非基变量,为使变换后的目标函数值增加的幅度最大,一般选正检验数最大的那个非基变量做为换入变量,2017/9/1,14
5、, 确定出基变量：, x2进基意味着其取值从0变成一个正数（经济意义生产B产品），能否无限增大？, 具体如何确定换出变量？, 现在的非基变量是哪些？,问题讨论, 当x2增加时， x3、 x4、x5如何变化？,2017/9/1,15,由用非基变量表示基变量的表达式,当x2增加时， x3， x4，x5会减小，但有限度?,必须大于等于0，以保持解的可行性！,取x1等于0，则:,寻找出基变量的方法:,2017/9/1,16,这说明当x2的值从0增加到3时，原来基变量x5首先变为0，另外两个基变量X3、X4仍然为正值。因此选x5为出基变量（换出变量）。,这种用来确定出基变量的规则称为 “最小比值原则”（
6、或原则）。,2017/9/1,17, 基变换新的基变量x2, x3,x4；新的非基变量x1, x5 ；写出用非基变量表示基变量的表达式：,可得新的基本可行解 X（1）=（0,3,2,16,0）T,由,2017/9/1,18, 写出用非基变量表示目标函数的表达式:,可得相应的目标函数值为Z（1）=9,检验数仍有正的,即非基变量X1的系数为正值，目标函数值还可以增大，尚不是最优解。,返回重新进行讨论。,2017/9/1,19,第五步：上述过程何时停止？,分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！,当用非基变量表示目标函数的表达式中，非基变量的系数（检验数
7、）全部非正时，当前的基本可行解就是最优解!,为什么？,2017/9/1,20,返回进行讨论。需要进行第二次迭代，得到一组新的基本可行解,新的基本可行解： X（2）=（2,3,0,8,0）T,得到的目标函数表达式为：,检验数仍有正值,返回继续讨论。需要进行第三次迭代，得到一组新的基本可行解,2017/9/1,21,目标函数的表达式中，非基变量的系数（检验数）全部非正，当前的基本可行解就是最优解!,新的基本可行解： X（3）=（4,2,0,0,4）T,得到的目标函数表达式为：,A产品生产4件，B产品生产2件使利润最大,三、表格单纯形法： 1、 初始单纯形表的建立 (1)表格结构：,限定系数,技术系
8、数,（2）表格设计依据： 将-Z看作不参与基变换的基变量，把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组：,2017/9/1,24,取出系数写成增广矩阵的形式：,-Z X1 X2 Xn Xn+1 Xn+2 Xn+m b,-Z，Xn+1，Xn+m所对应的系数列向量构成一个初始可行基,2017/9/1,25,用矩阵的初等行变换将该基变成单位阵,这时 变成0，相应的增广矩阵变成如下形式：,其中，,2017/9/1,26,（3）检验数的两种计算方法： 利用矩阵的行变换，把目标函数表达式中基变量前面的系数变为0； 使用计算公式,增广矩阵的最后一行
9、就是用非基变量表示目标函数的表达式, (j=1,2,n)就是非基变量的检验数。,2、例1.8的表格单纯形法计算过程：,2017/9/1,27,2017/9/1,28,2017/9/1,30,X*=(4,2,0,0,4)T 相应的目标函数最优值是Zmax=14,从最优表可知: 该LP的最优解是,2017/9/1,31,分别用代数法和单纯行法求解线性规划问题,例2-1 ,某工厂计划生产A、B、C、D四种原料生产两种产品，具体资料见下表，其中，一件产品获利400元，一件产品获利600元，问如何安排计划实现工厂利润最大化？,2017/9/1,32,2017/9/1,33,X*=(2，5，0，2，16，0)T 相应的目标函数最优值是Zmax=38,
