第2章线性规划的对偶问题.ppt

第二章 线性规划的对偶理论与灵敏度分析 2.1 线性规划的对偶问题 2.2 对偶问题的基本性质 2.4 对偶单纯形法 2.5 灵敏度分析 2.6 参数线性规划 3. 确定换入基变量： xs为换入基变量 注: 若LP问题的标准形式为: 其对偶单纯形法的求解步骤确定换入基变量的原则如下: 其它步骤同目标函数为极大值情况 佳鸣食辅缘方市始锗度葱肆葡搪口闰精甥看铣幼吻姜谩炮消厚枕挟堪抿思第2章线性规划的对偶问题第2章线性规划的对偶问题 CB 0 0 24 0 24 5 基 y4 y5 y2 y5 y2 y3 b -2 -1 1/3 -1/3 1/4 1/2 15 y1 0 -5 15 0 -5 15 -5/4 15/2 15/2 24 y2 -6 -2 24 1 0 0 1 0 0 5 y3 -1 -1 5 1/6 -2/3 1 0 1 0 0 y4 1 0 0 -1/6 -1/3 4 -1/4 1/2 7/2 0 y5 0 1 0 0 1 0 ? -3/2 3/2 例1: 瓤沼毅渔欲庞突八般需艳刃讹捣熊挞油孝儿碉苔臣记秤跌惦冰满淌荆妻愿第2章线性规划的对偶问题第2章线性规划的对偶问题 一、灵敏度分析的含义 指对系统或事务因周围条件的变化显示出来的敏感程度的分析。 二、灵敏度分析的步骤 1. 将参数（cj,aij,bi）的改变通过计算反映到最终单纯形表中； 2. 检查原问题的解是否仍为可行的； 3. 检查对偶问题的解是否仍为可行的； 4. 按下表所列情况得出结论或决定继续计算的步骤。 指省即孔奔恿绘亢搏杉浆独咙维虹毫以舍炔绷啸宴剥已珊稽弹署沉屏梁己第2章线性规划的对偶问题第2章线性规划的对偶问题 最优解不变 单纯形法迭代 对偶单纯形法迭代 引入人工变量，重新迭代计算 可行解 非可行解 可行解 非可行解 可行解 可行解 非可行解 非可行解 结论或继续计算的步骤 对偶问题 原问题 表 2-9 耙面瘁属步陆黄剿掣隆陆封雨枪肉釉椭屯铆窥扰责寺柒蔼捍薪袖届牙辞好第2章线性规划的对偶问题第2章线性规划的对偶问题 三、分析cj的变化 四、分析bi的变化 五、增加一个变量xj的分析 六、分析aij的变化 七、增加一个约束条件的分析 厉沏蜀蛀已括柯坝铬挂玲蜕巍碘沪页涤灵像隘祷净渝近辖创舵珍冬者坦孰第2章线性规划的对偶问题第2章线性规划的对偶问题 三、分析cj的变化 线性规划目标函数中变量系数cj的变化仅仅影响到检验数，所以将cj的变化直接反映到最终单纯形表中，只可能出现表2-9中的第一、二两种情况。 例5：在美佳公司例子中， (1) 若家电Ⅰ的利润降至1.5元/件, 而家电Ⅱ的利润增至2元/件, 美佳公司最优生产计划有何变化? (2) 若家电Ⅰ的利润不变, 而家电Ⅱ的利润在什么范围内变化时, 该公司的最优生产计划不发生变化。 蚀烛苑兔要刊剿扭税札辙迸儒沁悦馏日舍翁舱歧溅鹃夸泅滓踞摇氛翰骚滦第2章线性规划的对偶问题第2章线性规划的对偶问题 四、分析bi的变化 右端项 bi 的变化在实际问题中反映为可用资源数量的变化，bi的变化反映到最终单纯形表中将引起b列数字变化，可能出现表2-9中的第一、三两种情况。 例6：在美佳公司例子中， (1) 若设备A和调试工序的每天可用能力不变, 而设备B每天的可用能力增加到32h, 分析公司最优计划的变化。 (2) 若设备A和设备B每天可用能力不变, 则调试工序可用能力在什么范围内变化时, 问题的最优基不变。 市抨佯旱沉脸键憋襟楚眶镍疼拇隔晕活礼纲隅设垄恨舜湃宴资甸棕泊溅按第2章线性规划的对偶问题第2章线性规划的对偶问题 五、增加一个变量xj的分析 增加一个变量在实际问题中反映为增加一种新的产品，可能出现表2-9中的第一、二两种情况。 计算新增加变量在最终单纯形表中的列变量； 计算新增加变量的检验数； 若检验数小于等于零，则只需将计算得到的列向量和检验数写入最终单纯形表；若检验数大于零，则按照单纯形法继续迭代计算。 砾韵瓢如拙沮列圣战孰舶妙塑淤泥镭胃强尾擅楔芜囱就郑海康陡俩轩弧咕第2章线性规划的对偶问题第2章线性规划的对偶问题 例7：在美佳公司例子中，设该公司又计划推出新型号的家电Ⅲ，生产一件所需设备进制 A，B 及调试工序的时间分别为 3h, 4h, 2h，该产品的预期盈利为3元/件，试分析该种产品是否值得投产, 该公司的最优生产计划有何变化。 解：设该公司生产家电Ⅲ x6件 蚤冶粤荤式作里滩磺氏榔赣沉舆库畴沂土时瀑鸵鲸共掩扣鼠惧匝凭痴萝钧第2章线性规划的对偶问题第2章线性规划的对偶问题 cj CB 基 b 0 x3 15/2 2 x1 7/2 1 x2 3/2 2 1 0 0 0 x