运筹学-单纯形法灵敏度对偶

null 要求: (1)把单纯形表填写完整 (2)判断解的情况 (3)最优解,最优基,最优值,对偶价格,最优基B,B的逆 单纯形法部分 (2)某线性规划如下: Max Z(x) = 3x1 + 5x2 + x3 4x1 + 2x2 + x3 ≤ 14 S.t. x1 + x2+ x3 ≤ 4 x1 , x2 , x3 ≥ 0 最终单纯形表如下： 要求: (1)求最优基B的逆 (2)填写完整表格 (3)判断解的情况, 最优值,对偶价格,4 单纯形法部分 (3)某线性规划如下: Max Z(x) = -5x1 + 5x2 + 13x3 - x1 + x2 + 3x3 ≤ 20 S.t. 12x1 + 4x2 + 10x3 ≤ 90 x1 , x2 , x3 ≥ 0 最终单纯形表如下：6第四章 单纯形法的灵敏度分析与对偶第四章 单纯形法的灵敏度分析与对偶第一节 单纯形法的灵敏度分析 一、目标函数中变量系数Ck的灵敏度分析： 1 在最终单纯形表中Xk是非基变量 系数矩阵的增广矩阵不变,基变量的系数(CB)不变,Zk不变，δk ´ = Ck +△ Ck- Zk= δk +△ Ck≤0 △ Ck≤- δk null一、目标函数中变量系数Ck的灵敏度分析： 2 在最终单纯形表中Xk是基变量 系数矩阵的增广矩阵不变,基变量的系数(CB) 变了,Zj变了 nullnull某线性规划最终单纯形表如下,已知初始可行基是s1,s2,s3,a1二、约束方程中常数项的灵敏度分析：二、约束方程中常数项的灵敏度分析：null二、约束方程中常数项的灵敏度分析： 约束类型与对偶价格的关系 ≤ 等于松弛变量的Zj值 ≥ 等于剩余变量的- Zj值 = 等于人工变量的Zj值 等于最优基的逆变量对应的Zj值bi´= bi+△ bi只影响最终单纯形表中的b列对偶价格不变—最优基不变—基变量取值≥07常数项在什么范围内变化时，其对偶价格不变？5nullnullnull 例题：最终单纯形表如下，求对偶价格不变时的△bi变化范围 例题：最终单纯形表如下，求对偶价格不变时的△bi变化范围 （1） △b1的变化范围： -50≤△b1≤25， 250≤b1≤325（2） △b2的变化范围： -50≤△b2， 350≤b3（3） △b3的变化范围： -50≤△b3≤50， 200≤b3≤300 例题：已知某线性规划初始可行基是（S1 S2 S3 a1），最终单纯形表如下，求对偶价格不变时的△bi变化范围 例题：已知某线性规划初始可行基是（S1 S2 S3 a1），最终单纯形表如下，求对偶价格不变时的△bi变化范围 （1） △b1的变化范围： ?（2） △b2的变化范围：?（3） △b3的变化范围： ?（4） △b4的变化范围：?练习P123，3，4 三、约束方程系数矩阵的灵敏度分析： 1、变量xk系数列由pk变为pk´，在最终单纯形表上xk是非基变量 若δk´≤0，最优解不变若δk´>0，继续迭代，求出最优解影响第k列数据， 例题：现试制一新产品Ⅲ，每件需设备2台时，原材料A0.5kg，原材料B1.5kg，每件获利150元，问该厂如何决策？解：多生产一种产品，增加一列系数列δ6´<0，最优解不变，即仍生产Ⅰ50件，Ⅱ100件。 2、变量xk系数列由pk变为pk´，在最终单纯形表上xk是基变量 需要重新计算判断 练习：124页5题 四、增加一个约束条件的灵敏度分析先将最优解的变量值代入新增加的约束条件，若满足，原最优解不变，否则将新增的约束填入最终表进一步求解6 若新增约束如下：S4 0 1030 0 0 0 1 S4 0 00 0 0 0 5000 若新增约束如下：S4 0 1030 0 0 0 1 S4 0 00 0 0 0 5000 45000-10100-20-3000 若新增约束如下：S4 0 1030 0 0 0 1 S4 0 00 0 0 0 5000 -30000-10100-2030001020-1a1 -M 0 0 0 1 a1 -M -M0 50-10M 50-20M M 10M-50 20M-50 -M 经过迭代后得到最终单纯形表添加用电约束后最优解为X1=140,x2=120,x3=0 灵敏度分析 小结 学校三防设施建设情况幼儿园教研工作小结高血压知识讲座小结防范电信网络诈骗宣传幼儿园师德小结 一目标函数中变量系数变化 1 变量xk是非基变量 △ Ck≤- δk 2 变量xk是基变量 二 约束条件中常数项变化范围(对偶价格不变) 灵敏度分析小结 三 系数矩阵的灵敏度分析 1 初始单纯形表变量xk系数列pk变为pk´，在最终单纯形表上xk是非基变量 2初始单纯形表变量xk系数列pk变为pk´，在最终单纯形表上xk是基变量 重新计算 四 增加一个约束条件的灵敏度分析 若δk´≤0，最优解不变若δk´>0，继续迭代，求出最优解先将最优解的变量值代入新增加的约束条件，若满足，原最优解不变，否则将新增的约束填入最终表进一步求解 五、同类多系数发生变化时的灵敏度分析：1、允许增加百分比：实际增加量/允许增加量 2、允许减少百分比：实际减少量/允许减少量 【百分之一百法则】对于所有变化的c和b： （1）当所有c的允许增加百分比和允许减少百分比 之和不超过100％（含100％）时，最优解不变。 （2）当所有b的允许增加百分比和允许减少百分比 之和不超过100％（含100％）时，对偶价格不变。 注意： 1、当允许增加量（减少量）为无穷大时，对于 任意一个增加量（减少量）其允许增加（减少） 百分比都看成为零。 2、该法则是判断最优解或对偶价格不变的充分 不必要条件。（超过100％时，二者也可能不变） 3、该法则仅适用于价值系数Cn和资源数量bm中同类系数发生改变，当两类系数同时改变时，只能重新求解。 第二节 线性规划的对偶问题第二节 线性规划的对偶问题一、LP的对偶问题 1.引例 生产 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 问题是一个在有限资源的条件下，求使利润最大的生产计划安排问题，其数学模型为：   现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的工时和购买工厂的材料，为其加工生产别的产品，由客户支付工时费和材料费，此时工厂应考虑如何为每种资源出租或出售定价？null解:1)决策变量：设y1, y2分别表示出租或出售单位原材料的价格和单位工时的价格 3)约束条件:工厂决策者考虑： （1）出售原材料和出租设备应不少于自己生产产品的获利，否则不如自己生产为好。因此有2）目标函数：租赁方需要付出的成本. Min W=24y1+26y2null(2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底价 租赁者考虑：希望价格越低越好，否则另找他人。 能够使双方共同接受的是 ： 上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。 null对于任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形式为： 原问题（LP） 对偶问题（DP）相应的矩阵形式为：null二 如何写出线性规划的对偶问题1 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 对偶关系2 一般对偶关系线性规划问题的约束有≥ ≤ =，变量要求有≥0 ≤0 自由变量null116页null118页nullnull125，8（2）页nullnull从原问题直接写出对偶问题的结论：null原问题与对偶问题之间的关系null三、对偶单纯形法1.单纯形法的重新解释 X*是最大化LP问题最优解的充要条件是同时满足：因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行，达到求出最优解的过程。 根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解。对偶单纯形法就是根据这种思想所 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的。 null2.对偶单纯形法的计算步骤：确定出基变量:常数列中最小的负常量确定入基变量:迭代计算若常数项都非负,得到最优解