运筹学第二对偶理论与灵敏度分析.ppt

在单纯形法中，原问题的最优解满足：??? （1）是基本解；????（2）可行；????（3）检验数 ≤0 （YA≥C），即对偶解可行。 单纯形算法是从满足（1）、（2）的一个基可行解出发，转换到另一个基可行解，一直迭代到（3）得到满足，即对偶解可行为止。 对偶单纯形法则是从满足（1）、（3）的一个对偶可行解出发，以基变量值是否全非负为检验数，连续迭代到（2）得到满足，即原问题的基解可行为止。 两种算法结果是一样的，区别是对偶单纯形法的初始解不一定可行，只要求所有检验数都非正，在保证所得解始终是对偶可行解的前提下，连续迭代到原问题的基解可行，从而取得问题的最优解 单纯形法与对偶单纯形法比较 单纯形法的步骤 对偶单纯形法的步骤 右端常数 变化 b 第一章例1中，若其它资源不变，而设备B的能力增加到32h，分析公司最优计划的变化； △b′=B-1△b= 1 5/4 -15/2 0 1/4 -1/2 0 -1/4 3/2 0 8 0 10 2 -2 = CB 0 2 1 cj－zj 基 x3 x1 x2 b 15/2+10 7/2+2 3/2-2 2 x1 0 1 0 0 1 x2 0 0 1 0 0 x3 1 0 0 0 0 x4 5/4 1/4 -1/4 -1/4 0 x5 -15/2 -1/2 3/2 -1/2 0 2 0 cj－zj x3 x1 x4 15 5 2 0 1 0 0 5 1 -4 -1 1 0 0 0 0 0 1 0 0 1 -6 -2 询痹系碑坚鲍壹叼健背轮城间缄藏簇排裙踪靳史墨戏赔及铅槐岛弛龚痈冲运筹学第二章对偶理论与灵敏度分析运筹学第二章对偶理论与灵敏度分析 * * 高迷轮怕法凉蒜仇奠夺祥剖藉巍试趁谣通钮讲传贿啪梯惜怂岩柑触稿杏溯运筹学第二章对偶理论与灵敏度分析运筹学第二章对偶理论与灵敏度分析 第二章 对偶理论与灵敏度分析 §2.1 线性规划的对偶问题 §2.2 对偶问题的基本性质 §2.3 影子价格 §2.4 对偶单纯形法 §2.5 灵敏度分析 拽寇帧缉慢七敏英爆纲役牧押治奄孔淋释鸳赎钨醉终值冻酸缉厦匹嗅鳖候运筹学第二章对偶理论与灵敏度分析运筹学第二章对偶理论与灵敏度分析 第一章例1中：美佳公司利用自身资源生产两种家电产品，其线形规划问题表示为： max z = 2x1 + x2 5x2 ≤15 St. 6x1 + 2x2≤24 x1 ＋ x2 ≤5 x1、x2 ≥0 现假定有某公司想把美佳公司的资源买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。 设y1、y2 和y3代表单位时间设备A、设备B和调试工序的出让代价， 则6 y2 ＋y3 ≥2、5y1+2y2 +y3 ≥1； 另外要求，min z=15y1+24y2 +5y3 ，且y1、y2 、y3 ≥0 即 min z=15y1+24y2 +5y3 6 y2 ＋y3 ≥2 5y1+2y2 +y3 ≥1 y1、y2 、y3 ≥0 St. §2.1 线性规划的对偶问题 对偶问题的提出 三柜溉雏辽压赊亢肩捷遭毫鸭则糊西将狐吉租冲刽挂王视考觅嘱挑镑亩烫运筹学第二章对偶理论与灵敏度分析运筹学第二章对偶理论与灵敏度分析 max z = 2x1 + x2 5x2 ≤15 6x1 + 2x2≤24 x1 + x2 ≤5 x1、x2 ≥0 St. min z=15y1+24y2 +5y3 6 y2 + y3 ≥2 5y1 + 2y2 + y3 ≥1 y1、y2 、y3 ≥0 St. 对称形式的对偶问题 对称形式 变量非负，求极大时约束条件取≤号、求极小时约束条件取≥号. Max z=(2, 1) x1 x