《线性规划问题的解幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的解幻灯片.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性规划问题的解第1页，共28页，编辑于2022年，星期一v最优解：若若基基本本可可行行解解又又是是最最优优解解（也也称称基基本本最最优优解解），这这个个基基就就称称为为最最优优基基（optimal basis）。n n基本解：对于基对于基,令非基变量为零令非基变量为零,求得满足（求得满足（1-13）的解，称为基对应的基本解）的解，称为基对应的基本解（basic solution）。n n基本可行解：满足（满足（1-14）的基本解称）的基本解称为基本可行解（为基本可行解（basic feasible solution）；）；基本可行解所对应的基称为可行基基本可行解所对应的基称为可行基（feas
2、ible basis）。第2页，共28页，编辑于2022年，星期一二二.解的性质解的性质在右图中在右图中设线段长度与之比为设线段长度与之比为 ，由此得，由此得 o第3页，共28页，编辑于2022年，星期一第4页，共28页，编辑于2022年，星期一线性规划问题的几个定理线性规划问题的几个定理定理定理1-41-4 线线性性规规划划问题问题有可行解有可行解,必有基本可必有基本可行解；有最行解；有最优优解解,必有基本最必有基本最优优解。解。定理定理1-1 1-1 线线性性规规划划问题问题的可行域是凸集。的可行域是凸集。定理定理1-21-2 A A为线为线性性规规划划问题问题可行域的极点可行域的极点的充
3、要条件是的的充要条件是的A A正分量正分量对应对应的系数列向的系数列向量量线线性无关。（性无关。（证证明从略）。明从略）。定理定理1-3A是可行域的极点的充要条件是它为基本是可行域的极点的充要条件是它为基本可行解。（证明从略。）可行解。（证明从略。）第5页，共28页，编辑于2022年，星期一综上所述综上所述,我们在理论上得到了线性规划问题的以下我们在理论上得到了线性规划问题的以下结论：结论：v线线性性规规划划问题问题的可行域是一凸集（包括有界凸集和的可行域是一凸集（包括有界凸集和无界凸集）；无界凸集）；线线性性规规划划问题问题的每个基本可行解的每个基本可行解对应对应着可行域的一个极点（着可行域
4、的一个极点（顶顶点）；若点）；若线线性性规规划划问题问题有有最最优优解解,必在可行域的某一极点上得到。由此可必在可行域的某一极点上得到。由此可见见,我我们们只需在基本可行解中只需在基本可行解中寻寻求最求最优优解。如何有效地解。如何有效地寻寻求最求最优优解解,这这就是下就是下节节要介要介绍绍的的单纯单纯形法。形法。第6页，共28页，编辑于2022年，星期一1-5 1-5 单纯形法单纯形法v一、单纯形法的基本思路一、单纯形法的基本思路 如如果果线线性性规规划划问问题题存存在在最最优优解解，一一定定有有一一个个基基本本可可行行解解是是最最优优解解。因因此此单单纯纯形形法法迭迭代代的的基基本本思思路路
5、是是：先先找找出出一一个个基基本本可可行行解解，判判断断其其是是否否为为最最优优解解，如如为为否否，则则转转换换到到相相邻邻的的基基本本可可行行解解，并并使使目目标标函函数值不断增大，一直找到最优解为止。数值不断增大，一直找到最优解为止。第7页，共28页，编辑于2022年，星期一1、确定初始基可行解、确定初始基可行解 max (1-17)在约束条件（1-18）式的变量的系数矩阵中总会存在一个单位矩阵，不妨设为 (1-20)第8页，共28页，编辑于2022年，星期一式中 称为基向量,同其对应的决策变量 称为基变量,模型中的其它变量 称为非基变量。在(1-18)式中令所有非基变量等于零,即可找到一
6、个解 X=(，)T=(b1,bm,0,0)T因有b0,故X满足约束(1-19),是一个基本可行解记为 又称初始基本可行解。2、从一个基本可行解转换为相邻的基本可行解从一个基本可行解转换为相邻的基本可行解设初始基本可行解中的前m个为基变量,即第9页，共28页，编辑于2022年，星期一经一系列变换得第10页，共28页，编辑于2022年，星期一3、最优性检验和解的判别第11页，共28页，编辑于2022年，星期一v（1-24）式中因 ,所以只要 ,就v有 。通常简写为 或 ,v它是对线性规划问题的解进行最优性检验的标志 第12页，共28页，编辑于2022年，星期一第13页，共28页，编辑于2022年，
7、星期一二、单纯形法的矩阵描述二、单纯形法的矩阵描述在线性规划问题的标准型：在线性规划问题的标准型：Max第14页，共28页，编辑于2022年，星期一中，不妨设中，不妨设是一个可行基，则系数矩阵可分块为是一个可行基，则系数矩阵可分块为（，）。对对 应应 于于 的的 基基 变变 量量 为为，非非基基变变量量为为，。并并令令，其其中中为为基基变变量量的的系系数数列列向向量量，N为为非非基基变变量量的的系系数数列列向向量量。于于是是原原问问题题可可化为化为第15页，共28页，编辑于2022年，星期一v即 对约束方程两边同左乘以 ，得 =，并代入目标函数，得第16页，共28页，编辑于2022年，星期一
8、令非基变量 =0得 =,从而相应的基本可行解为 目标函数取值为 又由于 ,故有 第17页，共28页，编辑于2022年，星期一将 及Z的表达式又可写成令 ，则又有 +=+第18页，共28页，编辑于2022年，星期一第四步：重复第二、三两步，一直到计算结束为止。第四步：重复第二、三两步，一直到计算结束为止。三、单纯形法的计算步骤三、单纯形法的计算步骤根据上节中讲述的原理根据上节中讲述的原理,单纯形法的计算步骤如下：单纯形法的计算步骤如下：第一步：求初始基本可行解第一步：求初始基本可行解,列出初始单纯形表。列出初始单纯形表。第二步：最优性检验。第二步：最优性检验。第三步：从一个基本可行解转换到相邻的
9、目标函第三步：从一个基本可行解转换到相邻的目标函第三步：从一个基本可行解转换到相邻的目标函第三步：从一个基本可行解转换到相邻的目标函 数值更大的基本可行解，列出新的单纯形表。数值更大的基本可行解，列出新的单纯形表。第19页，共28页，编辑于2022年，星期一一、一、大大M M法法在在上上一一节节例例1-91-9中中，化化为为标标准准形形式式后后约约束束条条件件的的系系数数矩矩阵阵中中含含有有单单位位矩矩阵阵，以以此此作作初初始始基基，使使求求初初始始基基可可行行解解和和建建立立初初始始单单纯纯形形表表都都十十分分方方便便。但但时时常常化化为为标标准准形形后后的的约约束束条条件件的的系系数数矩矩
10、阵阵中中不不存存在在单单位位矩矩 例例1-10 1-10 用单纯形法求解线性规划问题用单纯形法求解线性规划问题 1-6.1-6.初始可行基的求法初始可行基的求法 第20页，共28页，编辑于2022年，星期一解解 先将其化成标准形有先将其化成标准形有 Max MaxMaxMax第21页，共28页，编辑于2022年，星期一这这种种情情况况下下，可可以以通通过过添添加加两两列列单单位位向向量量，使使连连同同约约束束条条件中的向量构成单位矩阵。件中的向量构成单位矩阵。是是人人为为添添加加上上去去的的，它它相相当当于于在在上上述述问问题题的的约约束束条条件件（1-34）中中添添加加变变量量，约约束束条条
11、件件(1-35)中中添添加加变变量量，变变量量相相应应称称为为人人工工变变量量。由由于于约约束束条条件件（1-34）（1-35）在在添添加加人人工工变变量量前前已已是是等等式式为为使使这这些些等等式式得得到到满满足足，因因此此在在最最优优解解中中人人工工变变量量取取值值必必须须为为零零。为为此此，令令目目标标函函数数中中人人工工变变量量的的系系数数为为任任意意大的负值，用大的负值，用“-M”代表。代表。7p第22页，共28页，编辑于2022年，星期一“-M”称称为为“罚罚因因子子”，即即只只要要人人工工变变量量取取值值大大于于零零，目目标标函函数数就就不不可可能能实实现现最最优优。因因而而添添
12、加加人人工工变变量量后后，例例1-10的的数数学学模模型型的的标标准形式就变为准形式就变为max该该模模型型中中与与 对对应应的的变变量量 为为基基变变量量，令令非非基变量等于零，即得到初始基可行解基变量等于零，即得到初始基可行解 ,并并列列出出初初始始单单纯纯形形表表。在在单单纯纯形形法法迭迭代代运运算算中中，M可可当当作作一一个个数数学学符符号号一一起起参参加加运运算算。检检验验数数中中含含M符符号号的的项项，当当M的的系系数数为为正时，该检验数为正，当正时，该检验数为正，当M的系数为负时，该项检验数为负。的系数为负时，该项检验数为负。第23页，共28页，编辑于2022年，星期一例例1-1
13、01-10添加人工变量后，用单纯形法求解的过程见下页表添加人工变量后，用单纯形法求解的过程见下页表1-1-8 8。最优解为：。最优解为：二、二、两阶段法两阶段法用大用大M M法处理人工变量，在用手工计算求解时不会碰到麻烦。但法处理人工变量，在用手工计算求解时不会碰到麻烦。但用电子计算机求解时，对用电子计算机求解时，对M M就只能在计算机内输入一个机器就只能在计算机内输入一个机器最大字长的数字。如果线性规划问题中最大字长的数字。如果线性规划问题中的或的或等参数值与这个代表等参数值与这个代表M M的数相对比较接近，的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，或远远小于这个数
14、字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，对添加人工变量后的线性规划问题分两个阶段来计算，称为两阶段法。称为两阶段法。第24页，共28页，编辑于2022年，星期一表表1-8-30100-M-M0-M-M419111100000111-1-11-200003-3-2M4M10-M004130211-10313-21-10-110660403-3100-M-3+6M04M+103M-4M01-1/21第25页，共28页，编辑于2022年，星期一入基出基原则v首先是
15、检验数 即单纯形表中系数矩阵的第 列 的价值系数 减去第 列元素乘以对应行所在的基的价值系数的和的差。v当目标函数是求max时，大者对应的列所在的变量为入基变量，如果有几个检验数一样大，且是最大者，取脚标小的变量为入基变量；当目标函数是求min时，小者为入基变量。v由于第26页，共28页，编辑于2022年，星期一续表-3 1 1 0 2/3 0 1/2 -1/2 1/6 3/20 3 0 1 1/3 0 0 0 1/3 90 0 0 0 0 1 -1/2 1/2 -1/2 -0 0 3 0 3/2 -M-3/2-M+1/2 1 3/2 3/2 0 1 0 3/4 -3/4 1/4 0 0 0
16、0 0 1 -1/2 1/2 -1/2 0 5/2 -1/2 1 0 0 -1/4 1/4 1/4 -9/2 0 0 0 -3/4 -M+3/4-M-1/4 第27页，共28页，编辑于2022年，星期一两两阶阶段段法法的的第第一一阶阶段段是是先先求求解解一一个个目目标标函函数数中中只只包包含含人人工工变变量量的的线线性性规规划划问问题题，即即令令目目标标函函数数中中其其它它变变量量的的系系数数取取零零，人人工工变变量量的的系系数数取取某某个个正正的的常常数数（一一般般取取1），够够成成新新的的目目标标函函数数，在在保保持持原原问问题题约约束束条条件件不不变变的的情情况况下下求求这这个个目目标标
17、函函数数极极小小化化时时的的解解。显显然然在在第第一一阶阶段段中中，当当人人工工变变量量取取值值全全为为0时时，目目标标函函数数值值也也为为0。这这时时候候的的最最优优解解就就是是原原线线性性规规划划问问题题的的一一个个基基本本可可行行解解。如如果果第第一一阶阶段段求求解解结结果果最最优优解解的的目目标标函函数数值值不不为为0，即即最最优优解解的的基基变变量量中中含含有有非非零零的的人人工工变变量，表明原线性规划问题无可行解。量，表明原线性规划问题无可行解。当当第第一一阶阶段段求求解解结结果果表表明明问问题题有有可可行行解解时时，第第二二阶阶段段是是在在原原问问题题中中去去除除人人工工变变量量，并并从从此此可可行行解解（即即第第一一阶阶段段的的最最优优解解）出出发发，继续寻找问题的最优解。继续寻找问题的最优解。见见34页例页例9，表，表1-7，1-8第28页，共28页，编辑于2022年，星期一