第2章-线性规划原理与解法ppt课件.ppt

第二章第二章线性规划原理与解法线性规划原理与解法2-1线性规划求解原理线性规划求解原理2-2单纯形方法单纯形方法2-3人工变量及其处理人工变量及其处理篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2-1 2-1 线性规划求解原理线性规划求解原理 1 1、举例说明、举例说明2 2、一般线性规划问题单纯形法求解基础、一般线性规划问题单纯形法求解基础单纯形法的思路：从问题的某个基可行解开始，转换到另单纯形法的思路：从问题的某个基可行解开始，转换到另一个基可行解，直到找到使目标函数最大的基可行解。一个基可行解，直到找到使目标函数最大的基可行解。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例例2-1步骤步骤1寻找初始基可行解寻找初始基可行解从约束条件的系数矩阵中可以容易地找到一个基：从约束条件的系数矩阵中可以容易地找到一个基：将上述约束条件变换形式为将上述约束条件变换形式为一、举例说明一、举例说明 令非基变量为令非基变量为0，则则即：即：为基可行解为基可行解（式（式2-1）对应的对应的为为:篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统步骤步骤2判断是否为最优解判断是否为最优解一、举例说明一、举例说明 选择选择 作为作为换入变量换入变量，可以将可以将 或或 换入基变量中。换入基变量中。同时还要找出一个同时还要找出一个换出变量换出变量。例例2-1将（式将（式2-1）带入目标函数为）带入目标函数为（式（式2-2）（式（式2-1）计算计算非基变量非基变量检验数检验数篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统步骤步骤3基变换（由一个基转向另一个基）基变换（由一个基转向另一个基）一、举例说明一、举例说明 基变换过程中的要求：基变换过程中的要求：（式（式2-3）（1）所有变量均为非负；所有变量均为非负；因为因为仍为非基变量，仍为非基变量，所以所以由式由式（2-1）和要求（和要求（1）知）知（式（式2-1）必须有必须有为了保证式（为了保证式（2-3）满足基变换要求，）满足基变换要求，此时，此时，将式（将式（2-1）进行如下基变换）进行如下基变换用用替换替换，（式（式2-4）（2）所有非基变量为）所有非基变量为0。最小最小 规则规则篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统步骤步骤3基变换基变换一、举例说明一、举例说明 利用高斯消去法将式（利用高斯消去法将式（2-4）左边变换为单）左边变换为单位矩阵（即出现基）位矩阵（即出现基）（式（式2-5）基可行解为基可行解为（式（式2-4）目标函数值目标函数值之间的联系？之间的联系？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统将式（将式（2-5）代入目标函数）代入目标函数得得:重复重复步骤步骤2判断是否为最优解判断是否为最优解（式（式2-5）篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统一、举例说明一、举例说明 步骤步骤4重复步骤重复步骤2、3，直到目标函数中非基变量的系数均为负，无改进可能，直到目标函数中非基变量的系数均为负，无改进可能，即找到最优解即找到最优解本例依次向下迭代得到的基可行解分别为：本例依次向下迭代得到的基可行解分别为：于是最优解为于是最优解为:篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统一、举例说明一、举例说明 与图解法之间的对应关系与图解法之间的对应关系2134567812340Q1Q2Q3Q4篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例例212300081612121000400140010430000816122042042-1 单纯形法单纯形法230003篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统230000812100401640010012040013230000900320300-3/2-1/801400-201/413200-3/40103001/4164001001210-1/22432160141101000-410100412283-1/221/41/4220311/2-200401/400140-1/81/21022283283-1/221/4-1/221/4最优解为：最优解为：本例题中，本例题中，X5先出基，先出基，又进基又进基篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统一、举例说明一、举例说明 由以上分析可以得出单纯形法的步骤由以上分析可以得出单纯形法的步骤:1 1、建立实际问题的线性规划数学模型；、建立实际问题的线性规划数学模型；2 2、把一般的线性规划问题化为标准形式、把一般的线性规划问题化为标准形式；3 3、确定初始基可行解；、确定初始基可行解；4 4、检验所得到的基可行解是否最优、检验所得到的基可行解是否最优;5 5、迭代，求得新的基可行解（主要确定换入变量和换出变量）；、迭代，求得新的基可行解（主要确定换入变量和换出变量）；下面将主要针对下面将主要针对3、4、5来进行讨论来进行讨论篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二、一般线性规划问题的求解基础二、一般线性规划问题的求解基础 1 1、确定初始基可行解、确定初始基可行解对于已经是对于已经是标准型标准型的线性规划问题：的线性规划问题：对于所有约束条件都是对于所有约束条件都是“”型的不等式型的不等式：对于所有约束条件都是对于所有约束条件都是“”型的不等式及等式约束情况型的不等式及等式约束情况：找到初始可行基后，将所有基变量列于等式左边，非基变量和常数列于等式右边，找到初始可行基后，将所有基变量列于等式左边，非基变量和常数列于等式右边，则可得初始可行解则可得初始可行解不失一般性，令初始可行基为不失一般性，令初始可行基为 ，则，则 （式（式2-6）一般可以直接观察得到一个初始可行基；一般可以直接观察得到一个初始可行基；对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对等式约束直接加上一个非负的人工变量。对等式约束直接加上一个非负的人工变量。（式（式2-1）通过化标准型通过化标准型加上松弛变量，加上松弛变量，可以得到一个初始可行基。可以得到一个初始可行基。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二、一般线性规划问题的求解基础二、一般线性规划问题的求解基础 2 2、最优性检验与解的判别、最优性检验与解的判别 由式（由式（2-62-6）知）知,基变量常数基变量常数其中常数和其中常数和都是经过变换之后的，与最初的不同，都是经过变换之后的，与最初的不同，用用 （式（式1-7-7）表示经过迭代之后的基变量的值。表示经过迭代之后的基变量的值。将式将式1-7-7代入目标函数代入目标函数得得称为检验数称为检验数检验数实际上就是将决策检验数实际上就是将决策变量代入目标函数后，各变量代入目标函数后，各变量在目标函数中的系数变量在目标函数中的系数篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二、一般线性规划问题的求解基础二、一般线性规划问题的求解基础 2 2、最优性检验与解的判别、最优性检验与解的判别 （1 1）最优解的判定定理：）最优解的判定定理：（3 3）无穷多最优解：）无穷多最优解：（4 4）无界解判定定理：）无界解判定定理：（以下判定定理针对标准型而言（以下判定定理针对标准型而言）对于一个基可行解，如果其对于一个基可行解，如果其所有非基变量所有非基变量的检验数的检验数 ，则该解称为最优解。则该解称为最优解。同时它对应的系数列向量所有的同时它对应的系数列向量所有的 ，则该线性规划问题具有无界解。则该线性规划问题具有无界解。已经是最优解，有已经是最优解，有某个非基变量某个非基变量的检验数的检验数 =0=0对于一个基可行解，其对于一个基可行解，其非基变量中有某个非基变量中有某个 ，（2 2）唯一最优解：）唯一最优解：所有非基变量所有非基变量的检验数都的检验数都 0 0篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二、一般线性规划问题的求解基础二、一般线性规划问题的求解基础 3 3、基变换、基变换当初始可行解不是最优解时，要从中确定一个换入变量，一个换出变量，得到一当初始可行解不是最优解时，要从中确定一个换入变量，一个换出变量，得到一个新的基可行解。个新的基可行解。（1 1）确定换入变量）确定换入变量当存在多个当存在多个 时，时，一般选一般选 ，即，即 为换入变量，为换入变量，为使目标函数增长较快，为使目标函数增长较快，但不是必须。但不是必须。例如：按上述原则，本节例子必须经过例如：按上述原则，本节例子必须经过三步迭代才能得到最优解。三步迭代才能得到最优解。2134567812340Q1Q2Q3Q4篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二、一般线性规划问题的求解基础二、一般线性规划问题的求解基础 3 3、基变换、基变换（2 2）换出变量的确定）换出变量的确定为了确保所有的变量均为非负，需确定换入变量的值为：为了确保所有的变量均为非负，需确定换入变量的值为：为了与书上后面的单纯形法统一，令式（为了与书上后面的单纯形法统一，令式（2 28 8）等于）等于则则确定确定为换出变量。为换出变量。由上例可知为了求得新的基可行解，除保证由上例可知为了求得新的基可行解，除保证 和和 外，还必须通过高斯外，还必须通过高斯消去法得到新的可行基和基可行解。消去法得到新的可行基和基可行解。即即称为最小称为最小规则规则上例上例由无界解判定定理可由无界解判定定理可知为什么知为什么换出变量为：换出变量为：式（式（28）篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统进基变量的选择出基变量的选择判优原则若目标函数最小化？若目标函数最小化？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统总总结结主要掌握的内容：主要掌握的内容：1、确定初始可行解、确定初始可行解2、解的最优性的判断、解的最优性的判断3、基变换（换入和换出变量的确定）、基变换（换入和换出变量的确定）篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统线性代数中求逆矩阵的一种方法为：线性代数中求逆矩阵的一种方法为：（B|I）-（I|B-1）经过行变换经过行变换单纯形表间的对应关系单纯形表间的对应关系篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统CBCBCN0b表头表头XBXNXSBNIb初始表初始表CBIB-1NB-1B-1b当前表当前表CB-CBICN-CBB-1N0-CBB-1检验数检验数单纯形表的矩阵表述单纯形表的矩阵表述篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统I09800320300-3/2-1/801400-201/413200-3/40103001/4164001001210-1/224101000-41010041223-1/221/420311/2-200401/400140-1/81/2102230000812100401640010012040013230000XBXSB-1B-1B-1B-12-3人工变量及其处理人工变量及其处理一、大一、大M M法法二、两阶段法二、两阶段法三、线性规划问题的各种情况讨论三、线性规划问题的各种情况讨论一、大一、大M法法当约束条件出现当约束条件出现“”或或“”时，不能直接找到单位矩阵，如下例时，不能直接找到单位矩阵，如下例例例22：构造单位矩阵构造单位矩阵约束条件为约束条件为“”时：减去剩余变量再加上时：减去剩余变量再加上人工变量人工变量约束条件为约束条件为“”时：直接加上时：直接加上人工变量人工变量目标函数中，目标函数中，剩余变量系数为剩余变量系数为0，人工变量系数：求人工变量系数：求max时，为时，为M，求求min时，为时，为M。？1-2110001131-4120-110-20100013-1-100-M-M113/210-M-M1131121一、大一、大M法法12136M-1+M-1+3M0-M00-1+3M3-1-100-M-M0111-21100011-M3-4120-1103/2-M1-2010001136M-1+M-1+3M0-M001-1+M00-M0-3M+110-21000101010-11-20-2310100-10-M-11-1+M111001-210-1-101010-11-2031201-22-50-21100011000-1-M+1-M11112103-24314001/3-2/32/3-5/301100-11-209012/3-4/34/3-7/33-1-1000-1/3-1/3-M+1/3-M+2/323-1-100-M-M3-1-190012/3-4/34/3-7/3000-1/3-1/3-M+1/3-M+2/310100-11-241001/3-2/32/3-5/32所以最优解为所以最优解为：目标函数值：目标函数值：（1 1）目标函数可以求）目标函数可以求Min，但判优准则不同，两者各有利弊。但判优准则不同，两者各有利弊。（2）约束条件为）约束条件为的不等式：的不等式：总结：总结：剩余变量人工变量剩余变量人工变量约束条件为等式：约束条件为等式：人工变量人工变量约束条件为约束条件为的不等式：的不等式：松弛变量松弛变量求求max时的时的价值系数：价值系数：0M求求max时的时的价值系数：价值系数：M求求max时的时的价值系数：价值系数：0达到最优时，最优基达到最优时，最优基可行解中仍包含人工可行解中仍包含人工变量，则变量，则二、两阶段法二、两阶段法第一阶段：第一阶段：判断原问题是否有解（借助一个辅助线性规划问题）。判断原问题是否有解（借助一个辅助线性规划问题）。（1 1）给原问题加入人工变量，构造）给原问题加入人工变量，构造“仅含人工变量的目标函数仅含人工变量的目标函数”和和“要求目要求目标实现最小化标实现最小化”。（2）用单纯形法求解上述模型，若）用单纯形法求解上述模型，若目标目标0，原问题有可行解原问题有可行解，进入第二阶段，进入第二阶段，否则，原问题无可行解。否则，原问题无可行解。第二阶段：第二阶段：求原问题的最优解。求原问题的最优解。将第一阶段计算得到的最终表将第一阶段计算得到的最终表除去人工变量除去人工变量，填入原问题目标函数填入原问题目标函数的系数的系数，进行迭代，求得最优解。，进行迭代，求得最优解。二、两阶段法二、两阶段法例例23：第一阶段第一阶段:1-211000-4120-110113101100000116-1-30100-31131-20100011211113/2100000110111-2110001113-4120-1103/211-201000116-1-3010010-21000101010-2310100-10100-10010310-11-2-1111001-2110100-11-2031201-22-50-21100010000011000第一阶段目标函数为第一阶段目标函数为0，进入第二阶段，进入第二阶段-311003001-20100-1-201001211011-100014第二阶段第二阶段000001110100-11-2031201-22-50-21100010000011000-1121130-2314001/3-2/301100-109012/3-4/3-3110001/31/3-2所以最优解为所以最优解为：目标函数值：目标函数值：14001/3-2/301100-109012/3-4/3-3110001/31/3-2最优解为最优解为：目标函数值：目标函数值：-31100-31100MM-31190012/3-4/34/3-7/30001/31/3M-1/3M-2/310100-11-241001/3-2/32/3-5/3-2两阶段法最终表两阶段法最终表大大M法最终表法最终表二、两阶段法二、两阶段法两阶段法的注意事项两阶段法的注意事项第一阶段：目标函数仅含人工变量，且目标函数求极小值，无论原第一阶段：目标函数仅含人工变量，且目标函数求极小值，无论原问题求极大还是极小。问题求极大还是极小。第二阶段：求极大值还是极小值由原问题来确定。第二阶段：求极大值还是极小值由原问题来确定。三、线性规划问题的各种情况讨论三、线性规划问题的各种情况讨论1、退化解、退化解用用确定换出变量时会出现两个或两个以上的最小比值，在下一次迭代时会有确定换出变量时会出现两个或两个以上的最小比值，在下一次迭代时会有一个或几个基变量等于一个或几个基变量等于0，这就出现了退化解。，这就出现了退化解。后果：后果：出现退化解后，可能会出现过程的循环，迭代后又回到原点，永远达不到最优。出现退化解后，可能会出现过程的循环，迭代后又回到原点，永远达不到最优。解决方法：解决方法：勃兰特法勃兰特法（2）当出现两个以上相同）当出现两个以上相同值时，始终选取值时，始终选取下标最小下标最小的变量作为换出变量。的变量作为换出变量。（1）当存在多个）当存在多个时时，始终取，始终取下标值最小下标值最小的变量作为换入变量；的变量作为换入变量；三、线性规划问题的各种情况讨论三、线性规划问题的各种情况讨论用人工变量法求解时，最优时，如果基变量中仍含有人工变量，则称该问题无可行解用人工变量法求解时，最优时，如果基变量中仍含有人工变量，则称该问题无可行解2、无可行解、无可行解3、无穷多最优解、无穷多最优解三、线性规划问题的各种情况讨论三、线性规划问题的各种情况讨论4、检验数的几种形式检验数的几种形式MaxMin0000