管理运筹学单纯形法.ppt

第一页，共二十九页，2022年，8月28日 5.1 线性规划求解的相关概念 一、相关定理 定理1 线性规划问题的可行解集S是凸集。 定理2 线性规划问题的基本可行解X对应于可行域S的顶点。也就是说，可行域的顶点就是线性规划问题的基本可行解。 定理3 若线性规划问题有最优解，它一定在其可行域的顶点上达到。 第二页，共二十九页，2022年，8月28日 二、基本概念 单纯形法的基本思路：单纯形法也可以说是一种找凸集极点的计算方法，但它并不是要求去计算所有的极点，而是从凸集的一个初始解出发，沿凸集的边缘逐个验算所遇到的极点，直到找到使目标函数最优的极点为止。 初始可行解:第一个找到的可行域的顶点。 三、单纯形法试算程序框图（见图5—1） 第三页，共二十九页，2022年，8月28日 开 始 转变为标准型[增加额外变量(松弛、剩余、人工变量)] 建立初始单纯形表 最优 停 找出“换入”“换出”变量 修正单纯形表 是 否 图5—1 第四页，共二十九页，2022年，8月28日 5.2 线性规划模型的变换 一、线性规划模型标准型的特点 ⑴目标函数是求极大值或极小值； ⑵所有的变量都是非负的； ⑶除变量的非负约束外，其余的约束条件都是等式约束； ⑷每个约束方程右边的常数都是非负的 。 除变量的非负约束 等式约束 思考:若右边的常数不是非负怎么办? 第五页，共二十九页，2022年，8月28日 二、线性规划模型的变换 根据线性规划模型约束条件的不同，将其划分为三种类型： 1.“≤”类型的约束条件的变换 变换的方法：在不等式中增加一个额外的变量，称为松弛变量，以S表示之。松弛变量在约束方程中的系数为1，在目标函数中的系数为0，所以它的引入并不影响目标函数值。 松弛变量即表示作为决策限制条件的某种有限资源未被利用的部分。 第六页，共二十九页，2022年，8月28日 2．“≥”类型的约束条件的变换 变换的方法：引入剩入变量及人工变量，以S和A表示。 剩余变量在约束方程中的系数为-1，在目标函数中的系数为0，人工变量在约束方程中的系数为1，在目标函数中的系数为是一任意大正数，以M表示之。在求最大值的目标函数中，M取负号；在求最小值的目标函数中，M取正号。 剩余变量一般用来表示决策要求的某一最低标准超过要求的量，人工变量仅为了单纯形法在运算上方便，无其它特殊意义。 第七页，共二十九页，2022年，8月28日 3．“=”类型的约束条件 变换的方法：引入人工变量，人工变量在约束方程中的系数为1，在目标函数中的系数为任意大的正数M。在求最大值的目标函数中，M取负号；在求最小值的目标函数中，M取正号。 第八页，共二十九页，2022年，8月28日 三、模型变换方法归纳 约束条件类型 变 换 方 法 对于约束条件 对于目标函数 ≤ +S +0·S ≥ -S+A 求max时，+0·S-MA 求min时，+0·S+MA = +A 求max时，-MA 求min时，+MA 表中，S为松弛变量或剩余变量，A为人工变量，M为一任意大的正数。 第九页，共二十九页，2022年，8月28日 单纯形法 1.单纯形法的基本思想 从一个初始的基本可行解出发，沿着不断改进目标函数值的方向进行迭代，经过若干基本可行解，直到得出最优解。 计算顺利进行的保证条件： 最优性条件：它保证每次变动不会得到更差的解 可行性条件：它保证每次变动仍是基本可行解 可行域是不变的 第十页，共二十九页，2022年，8月28日 2.单纯形法的计算步骤 将线性规划问题转化为标准型 编制初始单纯行表 判别基本可行解是否为最优 找出“换入”或“换出”变量，以便进行换基 先找出主元行与主元列：对于求极大值问题，取Cj-Zj为正数且最大者所在的列为主元列，取bi/aij为正数且最大者所在的行为主元行，主元行与主元列之交点元素称为主元素，在右上方记“*”主元素正上方对应的变量为“换入”变量，主元素左边对应的基变量为“换出”变量。 修正单纯形表 运算规则：新行主元行元素=旧行元素/主元素 其他新行元素=旧行元素-交点元素*新主元行相应元素【交点元素指该行与主元列之交点元素】 对新基本可行解进行判别，是否达到最优，是则停；否则继续上述程序 对于求最大值问题，全部判别数为零与负数时，即Cj-Zj ≤0，得最优解 第十一页，共二十九页，2022年，8月28日 线性规划模型的一般形式： 求一组变量x1，x2，……xn的值,使目标函数：Z = c1x1 + c2x2 + …… + cnxn的值最大或最小，并满足的约束条件： a11x1 + a12x2 + …… + a1nxn ≤(≥，=) b1 a21x1 + a22x2 + …… + a