第1章运筹学基础及应用-第六版.ppt

2019/7/12,1,管理运筹学 OPERATIONS RESEARCH FOR MANAGEMENT SCIENCE,2019/7/12,2,第一章 线性规划及单纯形法 (Linear Programming & Simplex Method),1 一般线性规划问题的数学模型 2 图解法 3 单纯形法原理 4 单纯形法的计算步骤 5 单纯形法的进一步讨论 6 数据包络分析(DEA) 7 应用举例,例2(教材第9页)生产计划问题,常山机器加工厂，利用A、B、C三种不同设备加工生产、两种产品。按工艺要求，每生产一个单位的产品，需要占用三种设备2、4、0小时；每生产一个单位的产品，需要占用三种设备2、0、5小时。已知三种设备加工能力分别为12、16、15小时。且每生产一个单位的产品可获取2单位的利润；每生产一个单位的产品可获取2单位的利润。问应当如何安排加工，可使获取的总利润最大？,2019/7/12,3,2019/7/12,4,1 一般线性规划问题的数学模型 1.1 引例,问：，两种产品各加工多少单位, 可获最大利润?,2019/7/12,5,2x1+2x2 12 s.t. 4x1 16 5x2 15 x1，x2 0 注意模型特点,max Z= 2x1 +3x2,解:设产品, 产量分别为变量x1 ， x2,防灾科技学院,附例 营养配餐问题 假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分表,每天需要 3000 55 800,各种食物的营养成分表,每天需要 3000 55 800,x1 x2 x3 x4,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：,2019/7/12,10,线性规划模型的特点,决策变量：向量X=(x1 xn)T 决策人要考虑和控制的因素，非负 约束条件：关于X的线性等式或不等式 目标函数：Z=(x1 xn) 为关于X 的线性函数，求Z极大或极小,防灾科技学院,11,LP问题一般可整理为：,决策变量及各类系数之间的对应关系,防灾科技学院,12,上述模型的共同特征：,每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的； 都有关于各种资源和资源使用情况的技术数据，创造新价值的数据； 存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示; 都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。,2019/7/12,13,1.2 线性规划问题的数学模型,三个组成要素：,1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。,2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。,3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,线性规划的数学模型由三个要素构成,决策变量 Decision variables 目标函数 Objective function 约束条件 Constraints,其特征是： （1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值； （2）问题的约束条件是一组多个决策变量的线性不等式或等式。,怎样辨别一个模型是线性规划模型？,2019/7/12,15,一般线性规划问题的数学模型：,目标函数：,约束条件：,线性规划模型的简写形式(求和符号),一般线性规划(LP)问题模型向量形式,其中：,一般线性规划(LP)问题模型矩阵形式,其中：,2019/7/12,19,1.3 线性规划问题的标准形式,标准形式：,标准形式特点：,4. 决策变量取值非负。,1. 目标函数为求极大值；,2. 约束条件全为等式；,3. 约束条件右端常数项全为非负；,2019/7/12,20,一般线性规划问题如何化为标准型：,1. 目标函数求极小值：,令： ，即化为：,2019/7/12,21,2. 约束条件为不等式：,（2）当约束条件为“”时,如：,可令： ， 显然,称为松弛变量。,称为剩余变量。,2019/7/12,22,松弛变量和剩余变量统称为松弛变量,（3）目标函数中松弛变量的系数,由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利润，因此在目标函数中系数为零。,2019/7/12,23,3. 取值无约束的变量,如果变量 xj 代表某产品当年计划数与上一年计划数之差，显然 xj 的取值可能是正也可能是负，这时可令：,其中：,2019/7/12,24,例3(教材15页) 将下述LP模型化为标准型,2019/7/12,25,解：令,得标准形式为：,2019/7/12,26,线性规划问题及数学模型 线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzig）,线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzig） 1951年提出单纯形算法（Simplex）,线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzig） 1951年提出单纯形算法（Simplex） 1963年Dantzig写成“Linear Programming and Extension”,线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzig） 1951年提出单纯形算法（Simplex） 1963年Dantzig写成“Linear Programming and Extension” 1979年苏联的Khachian提出“椭球法”,线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzig） 1951年提出单纯形算法（Simplex） 1963年Dantzig写成“Linear Programming and Extension” 1979年苏联的Khachian提出“椭球法” 1984年印度的Karmarkar提出“投影梯度法”,又称多项式时间算法,线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzing） 1951年提出单纯形算法（Simplex） 1963年Dantzing写成“Linear Programming and Extension” 1979年苏联的Khachian提出“椭球法” 1984年印度的Karmarkar提出“投影梯度法” 线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,2019/7/12,33,求解线性规划问题： 就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。,1.4 线性规划问题的解的概念,2019/7/12,34,可行解：满足所有约束条件的解称为可行解，所有可行解的集合称为可行域。,2019/7/12,35,例：考察下述线性规划问题：,2019/7/12,36,（2） 基,系数矩阵A：,其中,或,2019/7/12,37,（3）基向量、基变量,（4）基解、基可行解、可行基,是对应于基,的一个基解、基可行解。,是对应于基,的一个基解、基可行解。,均是可行基 。,练习：P14， 例4,2019/7/12,38,为了便于建立 n 维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。,求解下述线性规划问题：,2 线性规划问题的图解法,2019/7/12,39,画出线性规划问题的可行域：,2019/7/12,40,1、可行域：约束条件所围成的区域。,2、基可行解：对应可行域的顶点。,3、目标函数等值线：,4、目标函数最优值: 最大截距所对应的 。,目标函数等值线有无数条，且平行。（观察规律),2019/7/12,41,解的几种情况：,(2) 无穷多最优解,(1) 唯一最优解,若目标函数改为：,约束条件不变，则:,2019/7/12,42,解的几种情况：,(4) 无界解,(3) 无可行解：当可行域为空集时，无可行解。,若目标函数不变，将约束条件1和3去掉，则可行域及解的情况见下图。,目标函数等值线,此时，目标函数等值线可以向上无穷远处平移，Z值无界。,2019/7/12,43,几点说明： 1、图解法只能用来求解含有两个决策变量的线性规划问 题。 2、若最优解存在，则必在可行域的某个顶点处取得。 3、线性规划问题的解可能是：唯一最优解、无穷多最优解、无最优解、无界解。,2019/7/12,44,3单纯形法原理,凸集：如果集合 C 中任意两个点 ，其连线上的所有点也都是集合C 中的点。,上图中（1）（2）是凸集，（3）（4）不是凸集,顶点：如果对于凸集 C 中的点 X ，不存在C 中的任意其它两个不同的点 ，使得 X 在它们的连线上，这时称 X 为凸集的顶点。,3.1 预备知识,2019/7/12,45,3.2 线性规划问题基本定理,定理1:若线性规划问题存在可行解，则问题的可行域是凸集。,证明:设 是线性规划的任意两个可行解，则,于是对于任意的 ，设 ，则,所以 也是问题的可行解，即可行域是凸集。,2019/7/12,46,引理: 线性规划问题的可行解 X为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。,证明:设 （1） 必要性显然。 （2） 设 A 的秩为m。可行解 X 的前 k 个分量为正，且它们对应的系数列向量 线性无关，则 。 当 时， 恰好构成一组基，而 就是这组基对应的基可行解。,当 时，在 基础上从其余列向量中可以找出 个线性无关的向量，恰好构成一组基，而 X 就是这组基对应的基可行解。,2019/7/12,47,定理2: 线性规划问题的基可行解 X 对应线性规划问题可行 域（凸集）的顶点。,证明:问题即是要证明: X是基可行解 X是可行域顶点，也即要证明其逆否命题： X不是基可行解 X不是可行域顶点 。,（1）X不是基可行解 X不是可行域顶点。,假设X是可行解，但不是基可行解， X 的前 k 个分量为正,其余分量为0， 则有 又X不是基可行解，所以由引理知，正分量对应的列向量 线性相关。即存在一组不全为零的数 ，使得,2019/7/12,48,用非零常数 乘以上式得： （1）+（3）得： （1）-（3）得： 令 选择合适的 ，使得所有的 于是 均是可行解，并且 ，所以 X 不是可行域顶点。,2019/7/12,49,（2）X不是可行域顶点 X不是基可行解 。,设 不是可行域的顶点，因而可以找到可行域内 另两个不同的点 ， 使得 ， 用分量表示即为：,易知，当 时，必有 所以,所以,于是（1）-（2）得,而 不全为零，于是知 线性相关，X不是基可行解。,2019/7/12,50,定理3: 若线性规划问题有最优解，一定存在一个基可行解是 最优解。,引理： 有界 凸集中的任何一点均可表示成顶点的凸组合。,证明:假设 是可行域顶点， 不是可行域顶点 ，且目标函数在 处达到最优，即 。,由引理知： 可表示为 的凸组合，即,因此,假设 是所有 中最大者，则,2019/7/12,51,而 是目标函数的最大值，所以 也是最大值， 也即，目标函数在可行域的某个顶点达到了最优。,从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。,2019/7/12,52,3.3 确定初始基可行解,寻求最优解的思路：线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然后设法转换到另一个基可行解，并使得目标函数值不断增大，直到找到最优解为止。,设给定线性规划问题：,2019/7/12,53,因此约束方程组的系数矩阵为：,添加松弛变量得其标准形为：,2019/7/12,54,由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组基，就可以求出一个基可行解：,说明：如果约束条件不全是 形式，如含所有 形式，则无法找到一个单位阵做为一组基，这时需要添加人工变量。后面的内容介绍。,称其为初始基可行解。,2019/7/12,55,3.4 从初始基可行解转换为另一个基 可行解,思路：对初始基可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。,设有初始基可行解 ，并可设前m 个 分量非零，即 ，于是,2019/7/12,56,由构造初始可行基的方法知前m 个基向量恰好是一个单位阵，所以约束方程组的增广矩阵为,由于任意系数列向量均可由基向量组线性表示，则非基向量中的 用基向量组线性表示为：,2019/7/12,57,设有 ，则,（1）+（2）得：,由此式可知，我们找到了满足约束方程组的另一个解 ，,要使其成为可行解，只要对所有i=1,2,m ，下式成立,要使其成为基可行解，上面m个式中至少有一个取零。 （基可行解中非零分量的个数不超过m 个。）,（与 比较）,2019/7/12,58,只要取,于是前m个分量中的第l个变为零，其余非负，第j个分量为正，于是非零分量的个数 ，并可证得 线性无关，所以 是新的基可行解。,2019/7/12,59,3.4 最优性检验和解的判别,设有基可行解,比较两者对应的目标函数值，哪一个更优？,2019/7/12,60,2）若对所有的 ，则 ， 就是最优解。,1）当 时， ，目标函数值得到 了改进， 不是最优解，需要继续迭代。,易知,2019/7/12,61,当所有 时，现有顶点对应的基可行解即为最优解。 当所有 时，又对某个非基变量 有 则该线性规划问题有无穷多最优解。 3. 如果存在某个 ，又 向量的所有分量 ，对任意 ，恒有 ，则存在无界解。,结论,2019/7/12,62,4 单纯形法的计算步骤,设有线性规划问题：,2019/7/12,63,(1)找到初始可行基，建立初始单纯形表.,(4) 重复二、三两步，直至找到最优解。,4 单纯形法的计算步骤,(2)进行最优性检验。 计算检验数，若所有 0 则得最优解，结束.否则转下步. 若某 0 而 0 ，则最优解无界，结束.否则转下步.,(3)从一个可行解转换到另一个目标函数值更大的基可行解。 由最大增加原则确定进基变量；由最小比值原则选择出基变量；以 为主元素进行换基迭代。,2019/7/12,64,(1)找到初始可行基，建立初始单纯形表.,是初始基。,2019/7/12,65,(2)进行最优性检验 计算检验数，若所有 0 则得最优解，结束.否则转下步. 若某 0 而 0 ，则最优解无界，结束.否则转下步.,检验数的计算方法：,基变量的检验数一定为0。判断是否达到最优时，只要考虑非基变量检验数。,2019/7/12,66,(3)从一个可行解转换到另一个目标函数值更大的基可行解。,由最小比值原则选择出基变量；,进基变量,由最大增加原则确定进基变量： 当某些非基变量的检验数 时，为使目标函数值增加地更快，一般选择正检验数中最大者对应的非基变量进基 ，成为新的基变量。,为确保新的基可行解的非零分量非负，按下述规则求得最小 比值 ，其所对应的原基变量中的 出基。,于是，新的一组基是：,2019/7/12,67,以 为主元素进行换基迭代： 即利用初等行变换将进基变量 所在的系数列变为单位列向量，而 变为1。这样原来基矩阵中的 就不再是单位向量，取而代之的是 ，这样就找到了一组新的基。,(4) 重复二、三两步，直至找到最优解。,说明：若目标函数是求最小，可以不必将其转变为求 最大，但在使用单纯形法求解时，确定进基变 量，应找负检验数中最小者，并应以检验数 全部为正作为判别最优的条件。,2019/7/12,68,解 将模型标准化,附例,2019/7/12,69,作出初始单纯形表，进行迭代,检验数最大,比值最小,2019/7/12,70,2019/7/12,71,唯一最优解 :X*=(4,6,4,0,0)T，Z*=42,2019/7/12,72,特殊情况： （1）出现两个或两个以上相同的最大 ，此时可任选一个 所对应的变量作为进基变量。 （2）利用 规则决定出基变量时，出现两个或两个以上的最小比值 ，则迭代后，会出现一个或几个基变量等于零的情况，我们称此为退化现象。进而可能会出现迭代过程的循环，致使永远达不到最优解。 出现退化现象时，可考虑采用“勃兰特”规则决定进基变量和出基变量的选择。,2019/7/12,73,5.1 人工变量,用单纯形法解题时，需要有一个单位阵作为初始基。 当约束条件都是“”时，加入松弛变量就形成了初始基。 但实际存在“”或“”型的约束，没有现成的单位矩阵。 采用人造基的办法：添加人工变量，构造单位矩阵,5 单纯形法的进一步讨论,2019/7/12,74,人工单位矩阵的构造方法 在“ ”的不等式约束中减去一个剩余变量后可变为等式约束，但此剩余变量的系数是（-1），所以再加入一个人工变量，其系数是（+1），因而在系数矩阵中可得到一个相应的单位向量，以便构成初始单位阵，即初始基矩阵。 在原本就是“ = ”的约束中可直接添加一个人工变量，以便得到初始基矩阵。 注意：人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。,求解带人工变量的线性规划有两种方法： 大M法 两阶段法,2019/7/12,75,5.2 大M法,没有单位矩阵，不符合构造初始基的条件，需加入人工变量 。 人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为（-M）。 （求最小值问题中，人工变量系数取M） M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。 如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。,2019/7/12,76,例 解线性规划,解 化为标准型,此时无单位矩阵作为初始基。,2019/7/12,77,添加人工变量，构造初始基：,注意：若求最小值问题，则目标函数中人工变量系数取M。,2019/7/12,78,初始单纯形表：,2019/7/12,79,2019/7/12,80,此时人工变量全部出基，并已达最优条件。 最优解为,，最优值为,注意：计算机上使用大M法时，需要用机器最大字长的数字 代替M，但当某些系数与之较接近时，还是可能会出错。 另外一种求解带人工变量的线性规划问题的方法不会出现这种 问题-两阶段法。,2019/7/12,81,例 解线性规划,解 按大M法构造人造基，引入人工变量x4 , x5 的辅助问题如下：,2019/7/12,82,作出单纯形表，进行迭代,2019/7/12,83,最优解 :X*=(3,0,1)T，Z*=7,2019/7/12,84,5.3 两阶段法,第一阶段：构造目标函数只含人工变量的线 性规划问题，求解后判断原线性 规划问题是否有基本可行解，若 有，则进行第二阶段 ； 第二阶段：将第一阶段的最终单纯形表所对 应的解，去掉人工变量，作为第 二阶段的初始单纯形表的初始基 可行解，进行单纯形法的迭代。,2019/7/12,85,解（1）化标准型、并添加人工变量得： （此处未将目标变为MAX）,例：,2019/7/12,86,（2）构造第一阶段问题：,说明：原问题目标函数无论是求MAX还是求MIN，构造的 第一阶段问题目标函数都是求最小MIN。,2019/7/12,87,求解第一阶段问题：,2019/7/12,88,此时所得可行解目标函数值为0，故原规划问题有基可行 解。转入第二步。,2019/7/12,89,（3）去掉人工变量，得到第二阶段的单纯形表，在此 基础上继续求解。,最优解为：,2019/7/12,90,5.4 关于解的不同情况的判别,1、无穷多最优解 例：,解：将问题化为标准型：,2019/7/12,91,2019/7/12,92,从上表中可知，已达最优解，为 ， 而 ，若将 选为进基变量迭代后，可得另一最优 解 。,上述两最优解分别对应两个顶点，而两点连线上的点均是最优解，故有无穷多最优解。,判别无穷多最优解的方法：单纯形表的检验数行已达最优性条件（全部小于或等于零），且有一个非基变量的检验数为零，此时有无穷多最优解。,2019/7/12,93,2、无可行解 例 用单纯形表求解下列线性规划问题,解：化为标准型：,2019/7/12,94,单纯形表求解线性规划问题,2019/7/12,95,单纯形法的最终表里有人工变量大于零，则此线性规划无可行解。,2019/7/12,96,3、无界解,例 用单纯形表求解下面线性规划问题。,解,2019/7/12,97,此时 的检验数仍为正，但系数列全为负，此时可判断这个线性规划问题是无界的，即目标函数值可以取得无限大。,2019/7/12,98,事实上，此从1次迭代的单纯形表中，得到约束方程：,移项可得：,由此可知，目标 函数可以任意大， 即无界。,2019/7/12,99,练习：用大M法求解下列线性规划问题,1、,2、,2019/7/12,100,解1：将模型化为标准型得：,建立单纯形表并计算如下,2019/7/12,101,显然，检验数已全部非正，已达最优解，但非基变量X2的 检验数为0，故知此问题有无穷多最优解。,2019/7/12,102,解2：将模型化为标准型得：,建立单纯形表并计算如下,2019/7/12,103,2019/7/12,104,最优解为（4，4）,第一章 线性规划及单纯形法,Linear Programming （LP）,线性规划问题及其数学模型,线性规划的图解法,线性规划的单纯形法,线性规划问题的应用,线性规划问题的求解方法,单纯形法的求解思路,是,否,循 环, 以alk为主元素进行迭代，利用初等行变换将xk所在列化 为单位向量，即alk化为1，其它元素化为0，得到改进的 可行基，转入第步。,计算步骤总结（有可行解时）, 将线性规划问题化成标准形式; 找出一个m阶单位矩阵作初始可行基，得到初始基可行解; 计算各非基变量xj的检验数j，若所有j0，则问题已得到最优解，停止计算，否则转入下步; 若存在某个s0，且对应的所有系数ais0，则此问题是无界解，停止计算，否则转入下步; 根据max j | j0 = k 原则，确定xk为入基变量，再按 = min bi /aik | aik0 = bl /alk 规则，确定xl为出基变量，得到改进的基可行解。,单纯形表,目标系数区,约束条件系数区,右端系数,检验系数区,基变量区,基变 量的 系数,目标函数中变量的系数,决策变量,约束方程组 的系数矩阵,出基 变量 判断 参数,方程 右端 常数 项,各变量的检验数,基 变 量,单纯形表,由单纯形表判别解的类别,无可行解,唯一最优解,所有,无穷多最优解,无界解（无最优解）,最优解,所有非基变量的检验数*,由单纯形表判别解的类别,无可行解,唯一最优解,所有,无穷多最优解,无界解（无最优解）,最优解,所有非基变量的检验数*,保证当前的基可行解是最优解,至少有一个等于0，如,至少有一个大于0，如,0,存在，保证当xp入基时有xl出基,两个最优解连线上的所有点都是最优解,说明能得到另一个最优基可行解,无穷多最优解,示例：,s.t.,s.t.,此时所有检验数,得到最优解,最优值为,此时所有检验数,得另一最优解,最优值为,A,1,课后题：P48 1.8,0,0,2,4,-2,3,5,2,3,5,-3/2,练习题：求ag的值，并判断表中解是否最优解,单纯形法计算时某一步的表格,为松弛变量，表中解代入目标函数后得,2019/7/12,120,小结 表格单纯形表的使用,（1）化线性规划模型为标准型，建立初始单纯形表。 （2）根据单纯形表按照最大增加原则选择进基变量； （3）按照最小比值原则选择换出变量； （4）实施矩阵的初等变换进行换基迭代； （5）建立新的单纯形表； （6）重复上述过程直到求得最优表格为止。,防灾科技学院,121,一般地讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划模型。 (1) 要求解问题的目标函数能用数值指标来表示，且为线性函数； (2) 存在着多种方案及有关数据； (3) 要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。,7 线性规划应用举例,防灾科技学院,122,例合理利用线材问题。现要做100套钢架，每套需用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。 【分析】最简单做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元钢各一根组成一套，每根原材料剩下料头0.9m（7.4-2.9-2.1-1.5=0.9)。为了做100套钢架，需用原材料100根，共有90m料头。若改为用套裁，这可以节约原材料。下面有几种套裁方案，都可以考虑采用。见表2-12。,表,7 线性规划应用举例,所有可能的裁截方案,防灾科技学院,123,表2-12-(a),建模分析,防灾科技学院,124,防灾科技学院,125,为了得到100套钢架，需要混合使用各种下料方案。设按方案下料的原材料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5。根据表2-12-(a)的方案，可列出以下数学模型：,7 线性规划应用举例,防灾科技学院,126,模型求解