线性规划模型的单纯形法.ppt
Chapter3 线性规划模型的单纯形法线性规划模型的单纯形法(Simplex Method)(Simplex Method)线性规划问题解的相关概念及基本性质线性规划问题解的相关概念及基本性质单纯形法的基本思路单纯形法的基本思路单纯形法基本原理单纯形法基本原理单纯形表法单纯形表法单纯形法进一步讨论人工变量法单纯形法进一步讨论人工变量法 本章主要内容：本章主要内容：本章主要内容：本章主要内容：本章本章本章本章教学目的、重点、难点教学目的、重点、难点教学目的、重点、难点教学目的、重点、难点：理解线性规划模型的可行解、基本解、基本可行解等概理解线性规划模型的可行解、基本解、基本可行解等概念和这些概念之间的关系；念和这些概念之间的关系；熟悉单纯形法的基本思路和单纯形法的基本原理；熟悉单纯形法的基本思路和单纯形法的基本原理；掌握掌握单纯形法求解线性规划问题的基本步骤；掌握掌握单纯形法求解线性规划问题的基本步骤；掌握单纯形表法求出线性规划模型的基本最优解；掌握单纯形表法求出线性规划模型的基本最优解；会用计算机软件求解线性规划问题，进一步理解单纯形会用计算机软件求解线性规划问题，进一步理解单纯形法的基本原理法的基本原理Chapter3 线性规划模型的单纯形法(Simplex Method)Page 3线性规划线性规划模型解的相关概念及基本性质模型解的相关概念及基本性质1.1.线性规划问题解的相关概念线性规划问题解的相关概念线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组的方程组中找出一个解，使目标函数中找出一个解，使目标函数(1)达到最大值。达到最大值。Page 4 可行解可行解：满足：满足约束条件约束条件、的解为可行解。所有可行解的解为可行解。所有可行解的集合为可行域。的集合为可行域。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基：基：设设A为为约束条件约束条件的的mn阶系数矩阵阶系数矩阵(m04010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011基本最优解、最优值基本最优解、最优值Page 35单纯形法的计算步骤单纯形法的计算步骤例例2 用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。Page 36单纯形法的计算步骤单纯形法的计算步骤cj12100icB基变量基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x220 x x2 22 21/3150120753017131/309022560 x x1 111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3Page 37单纯形法的计算步骤单纯形法的计算步骤练习练习1 1 用单纯形法求解线性规划问题（无穷解的情况）用单纯形法求解线性规划问题（无穷解的情况）:Page 38单纯形法的计算步骤单纯形法的计算步骤练习练习2 2 用单纯形法求解线性规划问题（无界解的情况）用单纯形法求解线性规划问题（无界解的情况）:Page 39单纯形法的计算步骤单纯形法的计算步骤 关于单纯形法的补充说明：关于单纯形法的补充说明：Page 40单纯形法的计算步骤单纯形法的计算步骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握单纯形表法的解题思路及求解步骤熟练掌握单纯形表法的解题思路及求解步骤Page 41思考：思考：如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将如何构造初始可行基？单纯形法的计算步骤单纯形法的计算步骤作业：作业：P52 3、4Page 42单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法人工变量法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，为加的变量称为人工变量，构成的可行基称为人工基，用大用大MM法或两阶段法求解，这种用人工变量作桥梁的求法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。解方法称为人工变量法。Page 43单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法人工变量法：人工变量法：人工变量时为了获得初始基可行解，在约束条件化为等式后，人工变量时为了获得初始基可行解，在约束条件化为等式后，认为的加入的虚拟变量，只有当他们同时为零，即在最终的单认为的加入的虚拟变量，只有当他们同时为零，即在最终的单纯形表中它们全部变为非基变量，此时加入人工变量的等式约纯形表中它们全部变为非基变量，此时加入人工变量的等式约束才与原约束条件等价。因此在最优解的基变量中不允许含有束才与原约束条件等价。因此在最优解的基变量中不允许含有人工变量，这就要求在迭代过程中把人工变量从基变量中迭代人工变量，这就要求在迭代过程中把人工变量从基变量中迭代出去，通常采用出去，通常采用M M法和两阶段法法和两阶段法Page 44单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法人工变量、松弛变量和剩余变量是不同的，松弛变量、剩余变人工变量、松弛变量和剩余变量是不同的，松弛变量、剩余变量可以取零值，也可以取正值。但是人工变量只能取零值，否量可以取零值，也可以取正值。但是人工变量只能取零值，否则约束条件则约束条件1 1、2 2就和原始的约束条件不等价了。为了使得人工就和原始的约束条件不等价了。为了使得人工变量为零，规定人工变量在目标函数中的系数为变量为零，规定人工变量在目标函数中的系数为-M,M0,-M,M0,且为任且为任意大的数。这样只要人工变量不为零，目标函数最大值就是一意大的数。这样只要人工变量不为零，目标函数最大值就是一个任意小的数。为了使目标函数实现最大化人工变量要为零，个任意小的数。为了使目标函数实现最大化人工变量要为零，所以只有在最终单纯形表中人工变量为非基变量，人工变量的所以只有在最终单纯形表中人工变量为非基变量，人工变量的值才能是值才能是0 0。为了构造初始可行基，强行将人工变量加到约束条。为了构造初始可行基，强行将人工变量加到约束条件中去；又为了把人工变量从基变量中替换出来，就令人工变件中去；又为了把人工变量从基变量中替换出来，就令人工变量在求最大值的目标函数中为量在求最大值的目标函数中为-M,M0,-M,M0,这一方法称大这一方法称大M M法。法。大大M M法：法：Page 45单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例3 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。Page 46单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。Page 47单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3Page 48计算机软件QM求解 Page 49计算机软件QM求解 图图2求解迭代过程求解迭代过程Page 50小结：小结：学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理 2.熟练掌握单纯形表法的解题思路及求解步骤熟练掌握单纯形表法的解题思路及求解步骤 3.人工变量法人工变量法M的求解步骤的求解步骤 4.计算机软件计算机软件QM求解单纯形法求解单纯形法作业：作业：P52 3、4
