《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第三章线性规划 第三节模型求解》由会员分享，可在线阅读，更多相关《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第三章线性规划 第三节模型求解（29页珍藏版）》请在金锄头文库上搜索。
1、一、图解方法,图解方法一般只能用来解两个变量的线性规划问题，它直 观简便，虽应用范围较小，但有助于理解线性规划问题的几何 意义和解的基本情况。单纯形法是LP问题的一般解法，继图解 方法后再介绍。 例3-3 用图解法求解下面的线性规划问题 maxZ=,s.t.,解：在 直角坐标平面上作直线（图3-2），,一、图解方法,图3-2 图解法 约束条件的每一个不等式都表示一个半平面，满足约束条件 的点集是四个不等式所对应的四个半平面的公共部分，即上述两 条直线及两条坐标轴的边界所围成的凸多边形OAEC的内部及边 界。,一、图解方法,根据以上分析可知，在这个阴影部分的所有点（包括边界上的 点），满足该问题
2、的所有约束条件，这个范围以外的点，则不能同 时满足上述各约束条件。 满足所有约束条件的点称为可行点。 每一点代表该线性规划问题的一个可行方案，即一个可行解。 所有可行点的集合，是该问题的可行域。 图3-2中四边形OAEC内部及边界构成的阴影部分即为可行域，故 该问题的可行解有无数个。 一般说来，决策者感兴趣的不是可行域中所有的可行解，而是能 使目标函数值达到最优值（最大值或最小值）的可行解，这种解称 为最优可行解，简称最优解。,一、图解方法,为寻找最优解，将目标函数写成：50x1+40x2 = k，其中为 任意常数。当为不同值时，此函数表示相互平行的等值线。 令=0，先作通过原点的等值线 l3
3、: 50x1+40x2 = 0 它与可行域有交点。将这条直线沿目标函数增大的右上方 平移，过顶点E时，Z在可行域中取最大值；如继续向右上方 平移，则等值线将离开可行域（等值线与可行域没有交 点）。故E点坐标就是最优解。求l1和l2交点E坐标，得到： x1=10，x2=15，这时最优值Z=1100。 即例1中，甲产品产量为10件，乙产品产量为15件时，所获利润最大，最大利润为1100元。,一、图解方法,归纳图解法求解线性规划问题的步骤： （1）在x1ox2直角坐标平面上，根据约束条件作出可行域的图形（一般为一个凸多边形）。 （2）作出目标函数的0等值线，即目标函数值等于0的过原点的直线。 （3）
4、将0等值线沿目标函数增大的方向平移，当等值线移至与可行域的最后一个交点（一般是可行域的一个顶点）时，该交点就是所求的最优点。若等值线与可行域的一条边界重合，则最优点为无穷多个（见例3-5）。 （4）求出最优点坐标（两直线交点坐标可联立直线方程求解），即得到最优解(x1, x2)，及最优值Z（x1, x2）。,一、图解方法,例3-4 用图解法求解下列线性规划问题,maxZ =,s.t.,解：在 直角坐标系中作直线（图3-3），,得可行域OAEC。 作0等值线：,一、图解方法,E(10,15),l1,l2,20,40,20,10,10,该等值线l3斜率与l2 斜率相等，当向右上方平移到与边界线EC
5、重合时，目标函数值最大。故边界EC上的所有点，包括两个端点E（10，15）和C（0,20）都是此问题的最优解，此时目标函数的最优值为： Z（10,15）=Z（0,20）=800 这是线性规划问题有无穷多个最优解的情况。它同时说明，即使在最优解非唯一时，最优解还是会出现在可行域的一个顶点上。,图3-3 图解法,一、图解方法,例3-5 用图解法求解下列线性规划问题,maxZ=,s.t.,解：在 直角坐标系中作直线,x1,x2,l1,O,2,图3-4图解法,由图可知，可行域沿 轴无限延伸。作0等值线 并将它向右上方平移，因可行域无界，目标函数趋于无穷，该线性规划问题无有限最优解。 在实际应用中，应对
6、数学模型认真检查，适当修改，增加必要的约束条件，使可行域变为有界，再求解。,L,一、图解方法,例3-6 用图解法求解下列线性规划问题,maxZ =,s.t.,解：在 直角坐标系中作直线（图3-5）,x2,l1,l2,图3-5 图解法,各不等式对应的半平面无公共部分，即可行域是空的。不存在任一可行解，更没有最优解。 在实际应用中，可去掉一些互相矛盾的约束条件，再求解。,二、单纯形法,（一）标准形式及转化为标准形式的方法 1标准形式 线性规划模型的标准形式要求： （1）所有约束条件都由等式表示，并且等式右端的常数为非负； （2）所有决策变量为非负； （3）目标函数求最大值（也可用求最小值问题作为标
7、准形式，本 书对目标函数统一成求最大值）。 故线性规划模型的标准形式为：,maxZ =,s.t., +,二、单纯形法,（一）标准形式及转化为标准形式的方法 2一般形式化为标准形式的方法 线性规划问题的一般形式都能变换成标准形式。变 换的方法主要有以下两种： （1）若约束条件有不等式时，可在不等式的左边加 上或减去一个非负变量，使之成为等式。加入的变量 叫松弛变量，减去的变量则叫剩余变量，它们在目标 函数中系数为0； （2）若所给问题是求目标函数的最小值（如成本、 消耗），可用-1乘目标函数，化为求最大值。,二、单纯形法,（一）标准形式及转化为标准形式的方法 2一般形式化为标准形式的方法 例3-
8、7 将例3-1线性规划问题化为标准形式。,maxZ =,maxZ =,s.t.,s.t.,解：引入松弛变量 ， 可得标准形式：,二、单纯形法,例3-8 将例3-2线性规划问题化为标准形式。,解：引入剩余变量 ，并将最小值问题反号，转化为最大值问题，得标准形式：,maxZ =,s.t.,s.t.,max = -Z =,二、单纯形法,（二）单纯形法的基本思路 单纯形法是求解线性规划问题的基本方法之一。由于它的解 法很有效，而且也适用于电子计算机计算，因此使线性规划问题 在各领域得到广泛应用。 线形规划问题的数学模型化为标准形式后，变量的个数增加 了。一般地，如果包括松弛变量在内的变量个数为n ，方
9、程个数 为m，则在标准形式中，有n-m个变量等于0的可行解叫基本可 行解。又因在每一个可行域的顶点上一定有n-m个变量等于0， 故基本可行解实际上就是可行域的顶点。所以求最优解只要到基 本可行解中去寻找。 如果在n个变量个约束方程的系数矩阵中，含有m阶单位矩 阵，或经过行的初等变换后有m阶单位矩阵，那么就把m阶单位 矩阵所在的列对应的变量叫做基变量（ m个），其余的变量叫 做非基变量（n- m个）。只要令n- m个非基变量为0，即可得到 一个基本可行解。,二、单纯形法,（二）单纯形法的基本思路 单纯形法的基本思路是： 对可行域这一凸多边形的一个顶点（第一个基本可行 解）出发进行检验，如果不是最
10、优，则换一个（迭代） 更优的顶点（另一个基本可行解），使一次比一次更接 近最优解（逐步优化），直到取得最优解为止。 这一思路建立在一系列重要定理的基础上。为了更好 地领会单纯形法产生的整个思路，下面将展开几个基本 定理。先看两个重要概念：,二、单纯形法,凸集: 如果集合C中任意两个点X1，X2，其连线上的所有点也都 是集合C中的点，称C为凸集。由于X1，X2的连线可表示为,(0a1),因此凸集定义用数学解析式可表示为：对任何X1C， X2C，有 C (0集。0a1)，则称C为凸集。在图3-6中，（a）（b）（c）是凸集，（d）（e）（f）不是凸集。,(a) (b) (c) (d) (e) （f
11、） 图3-6 凸集概念 从直观上说，凸集没有凹入部分，其内部没有孔洞。,二、单纯形法,（二）单纯形法的基本思路 顶点: 凸集C中满足下述条件的点X称为顶点：如 果C中不存在任何两个不同的点X1，X2，使X成 为这两个点连线上的一个点。或者这样叙述：对 任何X1C，X2C，不存在X= （0 a 1），则称X是凸集C的顶点。,二、单纯形法,（二）单纯形法的基本思路 定理1 若线性规划问题存在可行解，则问题的可行域是凸集。（证明略） 定理2 线性规划问题的基本可行解X对应线性规划问题可行域（凸集）的顶点。（证明略） 定理3 若线性规划问题有最优解，一定存在一个基本可行解是最优解。（证明略） 由上述三
12、个定理可得出这样的结论： 线性规划问题的最优解可以通过只考虑它的基本可 行解来确定。,二、单纯形法,（三）单纯形法的解题步骤 下面通过一个计算实例来说明。 例3-10 用单纯形法求解例3-1的线性规划问题,maxZ =,s.t.,s.t.,maxZ =,解：先引入松弛变量 ，将问题化为标准形式：,二、单纯形法（三）单纯形法的解题步骤,将约束条件的增广矩阵和目标函数的系数填入下表中： 表3-4 单纯形表,单纯形表中，约束条件的系数矩阵中出现一个m阶单位矩阵，b列非负，Z行对应于单位矩阵的元素为0，这时其余的元素即为检验数。 由表3-4可看出，系数矩阵中已有2阶单位矩阵，其所在的列对应的变量x3，
13、x4叫基变量，置于左列，x1，x2叫非基变量，现令x1=0，x2=0，由标准形式等式可得x3=60，x4=80，于是得到一个基本可行解，记为X（0）=（0，0，60，80）T，这是初始可行解，其对应的目标函数值Z(0) = 0（将其填入表中右下角）。它表示：没有安排生产甲、乙产品，利润为0元。,二、单纯形法（三）单纯形法的解题步骤,最优解判定准则：当所有检验数非正时，这个解就是最优解，否则解仍可改善。 事实上，如果检验数有正数，则以该检验数为系数的非基变量取值大于0时，目标函数值仍可增大，所以这个解不是最优解；而当所有检验数非正时，非基变量取值为0，目标函数已取得极大值，所以这个解就是最优解。
14、 观察表3-4中检验数，50、40均为正数，解仍可改善。若将x1或x2变为非零变量都可使目标函数值增加。其中x1的价值系数更大，它能让目标函数增加较快，故先将x1转变为基变量，这时称之为进基变量，之后有一个基变量被换出，称为离基变量。变量调换完成之时，即可得到一个改善后的基本可行解。,二、单纯形法（三）单纯形法的解题步骤,具体调换程序如下：确定x1为进基变量后，用最小比值法则：,确定主元及离基变量，因 ，故3为主元，其所在行为主元行，主元行对应的基变量x3为离基变量。将主元用中括号标志，见表3-5。 表3-5 单纯形表的迭代,二、单纯形法（三）单纯形法的解题步骤,对主元行作初等变换，使主元变为
15、1，得表3-6。 表3-6 单纯形表的迭代,作行初等变换，将主元列其余元素变为0，得表3-7。 表3-7 单纯形表,新基变量为x1，x4，令非基变量x2，x3为0，得一基本可行解：X(1) = (20，0，0，40)T，对应目标函数值Z(1) = 1000。,二、单纯形法（三）单纯形法的解题步骤,观察表3-7中检验数，仍有正数，故其所在列对应变量确定为进基变量。 最小比值 ，故主元为 ， 为离基变量。对 进行标记，得表3-8。 表3-8单纯形表的迭代,对主元行作初等变换，使主元变为1，得表3-9。,二、单纯形法（三）单纯形法的解题步骤,表3-9单纯形表的迭代,作行初等变换，将主元列其余元素变为
16、0，得表3-10。 表3-10 单纯形表,表3-10中检验数非正，得最优解：X(2) = (10，15，0，0)T，对应目标函数值Z(2) = 1100。它表示：甲产品生产10件，乙产品生产15件时，利润最大，最大利润为1100元。,二、单纯形法（三）单纯形法的解题步骤,例3-11 用单纯形法求解例3-4中的线性规划问题,s.t.,maxZ =,解：引入松弛变量x3，x4，得标准形式： maxZ = +0 +0 s.t. 作单纯形表并进行迭代计算，见表3-12。,二、单纯形法（三）单纯形法的解题步骤,表3-12 单纯形表,二、单纯形法（三）单纯形法的解题步骤,由表3-12（）可知，检验数非正，这时已有最
