运筹学第章单纯形法.pptx

《运筹学第章单纯形法.pptx》由会员分享，可在线阅读，更多相关《运筹学第章单纯形法.pptx（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、OROR课件课件l可行域顶点的个数是否有限？可行域顶点的个数是否有限？l最优解是否一定在可行域顶点上达到？最优解是否一定在可行域顶点上达到？l如何找到顶点？如何找到顶点？l如何从一个顶点转移到另一个顶点如何从一个顶点转移到另一个顶点?导导 学学-问问题题 第1页/共30页OROR课件课件运 筹 帷 幄 之 中决 胜 千 里 之 外单纯形法第第2 2章章Simplex MethodSimplex Method第2页/共30页OROR课件课件LP 1 LP问题的几何意义2 单纯形法的经济解释3 单纯形法的计算步骤4 单纯形法的进一步讨论 5 LP问题解的讨论。导导 学学-主主要要内内容容第3页/共

2、30页重点重点单纯形法的经济含义、优化原理和计算步骤、以及有关概念。难点难点单纯形法的迭代原理和迭代方法，以及迭代过程中所反映的经济含义。OROR课件课件 导导 学学-重重点点与与难难点点第4页/共30页OROR课件课件LP 1几几何何意意义义vv基本概念基本概念基本概念基本概念1 1、凸集、凸集2 2、顶点：上式中、顶点：上式中 1 1或或0 0时对应的点。时对应的点。非凸集非凸集非凸集非凸集第5页/共30页OROR课件课件LPvv基本定理基本定理基本定理基本定理LPLP问题的可行域是凸集问题的可行域是凸集可行解是基本可行解的充要条件可行解是基本可行解的充要条件（-是是X X的非零分量所对应

3、的系数列向量线性无关）的非零分量所对应的系数列向量线性无关）基本可行解对应可行域的顶点基本可行解对应可行域的顶点有可行解必有基本可行解，即凸集有顶点有可行解必有基本可行解，即凸集有顶点最优解在可行域的顶点上达到最优解在可行域的顶点上达到 1几几何何意意义义第6页/共30页OROR课件课件LP例2.1 设有一家具厂用木材和钢材生产A,B,C三种家具，生产一件家具所需的材料、每件家具可获得的利润以及每月可供的木材自河钢材数量如下表，问此家具厂应如何安排问此家具厂应如何安排各种家具的生产量才能使企业获得最大的利润？各种家具的生产量才能使企业获得最大的利润？产 品木材 钢材单位产品获利（元）ABC 3

4、 2 1 1 4 4415材料可供量8000 3000解：设A,B,C三件家具的产量(件数)分别为x1,x2,x3，有：2经经济济解解释释第7页/共30页OROR课件课件LP模型的标准型为：系数矩阵和基：则：基变量为x4,x5;非基变量为x1,x2，x3，变换标准型的约束条件：代入目标函数：代入目标函数：Z=0+4 Z=0+4x x1 1+x x2 2+5 5x x3 3 令非基变量等于令非基变量等于0 0，基变量，基变量x x4 4=8000,=8000,x x5 5=3000=3000 初始基本可行解初始基本可行解初始基本可行解初始基本可行解 2经经济济解解释释第8页/共30页OROR课件

5、课件LP观察目标函数：选x3入基，x1,x2仍为非基变量，且为0，代入上方程组：则：基变量为x4,x3;非基变量为x1,x2 x5，变换标准型的约束条件：代入目标函数：代入目标函数：Z=3750+1.5 Z=3750+1.5x x1 1 0.250.25x x2 2 1.251.25x x5 5 令非基变量等于令非基变量等于0 0，基变量，基变量x x3 3=750,=750,x x4 4=5000=5000 基本可行解基本可行解基本可行解基本可行解当x3=750时，x5=0即为非基变量，x4=5000 2经经济济解解释释第9页/共30页OROR课件课件LP观察目标函数：选x1入基，x2,x5

6、仍为非基变量，且为0，代入上方程组：则：基变量为x1,x4;非基变量为x2,x3 x5，变换标准型的约束条件：代入目标函数：代入目标函数：Z=6000 Z=6000 x x2 2 3 3x x3 3 2 2x x5 5 令非基变量等于令非基变量等于0 0，基变量，基变量x x1 1=1500,=1500,x x4 4=3500=3500 最优解最优解当x1=1500时，x3=0即为非基变量，x4=3500 2经经济济解解释释第10页/共30页OROR课件课件LPv例题小结：明确以下问题：变量的经济意义变量的经济意义目标函数及其系数的经济意义目标函数及其系数的经济意义变量换入、换出时的经济意义变

7、量换入、换出时的经济意义目的在于：引入单纯形法的计算过程目的在于：引入单纯形法的计算过程目的在于：引入单纯形法的计算过程目的在于：引入单纯形法的计算过程 2经经济济解解释释第11页/共30页OROR课件课件LP将将LPLP问题化标准型，求出初始基本问题化标准型，求出初始基本可行解，并列入单纯形表可行解，并列入单纯形表是否最优？是否最优？是否无解？最优解最优解YNY无解无解N确定换入变量、换出变量，得到一确定换入变量、换出变量，得到一个新的基本可行解个新的基本可行解？3计计算算步步骤骤第12页/共30页OROR课件课件LP例2.1 线性规划问题的标准型：初始单纯形表：？推导初始解为X=(0,0,

8、0,8000,3000)Z=0 3计计算算步步骤骤第13页/共30页OROR课件课件LP检验数表达式推导：判别式：判别式：MaxZ:cj zj 0 (对于所有的非基变量）问题达到最优；对于所有的非基变量）问题达到最优；3计计算算步步骤骤第14页/共30页OROR课件课件LP换入变量的确定：换出变量的确定：系数矩阵的变换：按照增广矩阵的变换规则，将基变量的系数矩阵转化为单位矩阵，非基矩阵和资源向量作相应的变化。3计计算算步步骤骤第15页/共30页OROR课件课件LP 2000750KL4主元素x4x3057501/21/4101/450001001-15/25/4505/43/2-1/400-5

9、/4KK 50001500L1/2 3计计算算步步骤骤第16页/共30页OROR课件课件LPx4x3057501/21/4101/450001001-15/25/4505/43/2-1/400-5/4K 50001500L1/2x4x104150011/2201/235000-1/2-21-3/2428020-1-30-2最优解为：X=(1500,0,0,3500，0)Z=6000当前解为：X=(0,0,750,5000，0)Z=3750 3计计算算步步骤骤第17页/共30页OROR课件课件LP1、极小(MinS)目标函数的处理：方法一：Cj Zj 0 达到最优方法二：Zj Cj 0 达到最优

10、 4进进一一步步讨讨论论第18页/共30页OROR课件课件LP2、构造基：当约束条件为“”或“”时，需要设置“人工变量”构造基。求解方法有：方法一：大M法方法二：两阶段法 4进进一一步步讨讨论论第19页/共30页OROR课件课件LPv大M法方法要点：目标函数按下式处理（M是一个充分大的正数），约束条件不变，填入单纯形表进行求解。4进进一一步步讨讨论论第20页/共30页OROR课件课件LPv例2.2或 4进进一一步步讨讨论论第21页/共30页OROR课件课件LPv两阶段法方法要点（1）第一阶段目标函数的设置目标函数的设置：（2）转入第二阶段的条件及处理方法：条件：第一阶段满足最优性检验，且该阶段

11、的目标值条件：第一阶段满足最优性检验，且该阶段的目标值等于等于0 0，转入第二阶段；否则该问题无解，计算终止。，转入第二阶段；否则该问题无解，计算终止。处理：替换目标函数，在第一阶段最优表上继续。处理：替换目标函数，在第一阶段最优表上继续。4进进一一步步讨讨论论第22页/共30页OROR课件课件LPv学习提示学习提示学习提示学习提示：注意与图解法对比。不可行解：最终表的基变量中含人工变量；例2.3 如有线性规划 5解解的的讨讨论论第23页/共30页OROR课件课件LP两阶段法的最优单纯形表如下：人工变量人工变量无可行解无可行解 5解解的的讨讨论论第24页/共30页OROR课件课件LP无限界解：

12、5解解的的讨讨论论第25页/共30页OROR课件课件LP例2.4 如有线性规划无限界解无限界解 5解解的的讨讨论论第26页/共30页OROR课件课件LP退化解：LP问题的基本可行解中非零变量的个数少于约束条件数，也就是有基变量的取值为0。例题：下列有一求目标函数极大的LP问题的单纯形表基变量x2=0退化解退化解 5解解的的讨讨论论第27页/共30页OROR课件课件LP多重解：有非基变量的检验数等于0。例题：下表是某极大化LP问题的最优单纯形表非基变量的检验数为0最优解为X=(1500,0,0,3500,0)Z=60001/2多重解多重解 5解解的的讨讨论论第28页/共30页OROR课件课件LP1/2最优解为X1=(1500,0,0,3500,0）Z=6000最优解为X2=(0,3000,0,5000,0）Z=6000 5解解的的讨讨论论第29页/共30页感谢您的观看！第30页/共30页