运筹学-第七周-灵敏度-运输问题解说.pptx

第二章 对偶理论与灵敏度分析;;一般形式单纯形法计算的矩阵描述;矩阵A可以分块记为A=[B，N] 相应地，向量X和C可以记为 ;;; 对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！;1.使用条件： ①检验数全部≤0； ②右端向量列至少一个元素 0； 2. 实施对偶单纯形法的基本原则： 在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个右端负分量作为换出变量去替换某个非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。 ;3. 计算步骤： ① 建立初始单纯形表，计算检验数行。; ? 基变换： 先确定换出变量——右端向量列中的负元素（一般选最小的负元素）对应的基变量出基； ;然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。 如果 ; ?按主元素进行换基变换（初等行变换），将主元素变成1，主元列变成单位向量，得到新的单纯形表。 ;第五节 灵敏度分析; 以前讨论线性规划问题时，假定αij，bi, cj都是常数，但实际上这些系数往往是估计值或预测值。 如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。; 灵敏度分析：指对系统或事物因周围条件变化显示出来的敏感程度的分析。 线性规划模型的灵敏性分析： 研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程，称为线性规划的灵敏度分析。; 目标函数的价值系数变化 约束方程右端向量变化 约束方程组系数阵变化 决策变量或约束条件变化; LP灵敏度分析最终回答：;三、灵敏度分析的步骤;1. 价值系数cj 的变化分析;;例16：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划：;cj;Cj;2. 右端常数bi (资源系数)的变化分析;当bi发生变化时，将影响所有基变量的取值;例17：对于上例中的线性规划作下列分析： （1）b3在什么范围内变化，原最优基不变？ （2）若b3=55，求出新的最优解。 ;;（1）;（2）当 b3= 55 时 ;3. 增加一个新决策变量xj 的变化分析;对新问题：;例18： （续例）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示， P6= 。 (1) 问它的价值系数c6符合什么条件才必须安排它的生产？ (2) 设c6=3，新的最优生产计划是什么？;=B－1P6 =;Cj;4. 约束条件增减的变化分析; 将新增约束标准化，添加到原最优表格中(约束矩阵同时新增1行和1列）； 进行规格化处理——用矩阵的行变换将当前基变成单位阵；;例19：假设上例中，还要考虑一个新的资源约束：4x1+2x2≤150;;Cj;小结：系数变化对解的结果的影响;的最优单纯形表为：;1.为保持现有最优解不变，分别求出C1， C2的变化范围。;第三章 运输问题;;第一节 运输问题及其数学模型;一、运输问题的提出;例1：某运输问题的资料如下：;产地约束; 二、运输问题数学模型的一般形式 ; 产销平衡问题 产销不平衡问题 产大于销 销大于产;解：设xij(i=1,2,…，m；j=1,2,…,n)为第i个产地到第j个销地的运量，则数学模型为： ;;（1）运输问题有有限最优解。 定理: 运输问题有可行解的充要条件是产销平衡;（2）运输问题约束条件的系数矩阵;?矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0； ? 列向量Pij 中元素1分别处于第i行和第m+j行。 ? 将该矩阵分块，特点是：前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，…，m）；后n行构成m个n阶单位阵。;（3）运输问题的解;闭回路的特点：;练习：下面的折线构成的封闭曲线连接的顶点变量哪些不是闭回路？;有关闭回路的一些重要定理 ;;定理2: 若变量组 中有一个部分组构成闭回路，则该变量组对应的系数列向量线性相关。;以上的结果给出了运输问题的基的一个特征，这个结论非常重要，因为用它来判断m+n-1个变量是否构成基变量比直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。 另外，在以后还将看到利用基的这个特征可以导出求运输问题的初始基可行解的简便的方法。;第二节 表上作业法;;调 销地