《运筹学02_对偶理论与敏感性分析》由会员分享，可在线阅读，更多相关《运筹学02_对偶理论与敏感性分析（86页珍藏版）》请在金锄头文库上搜索。
1、1运筹学 第二章 对偶理论与及灵敏度分析 Dual Theory and Sensitivity Analysis2w线性规划的对偶问题概念、 理论及经济意义w线性规划的对偶单纯形法w线性规划的灵敏度分析本章内容重点31.线性规划对偶问题对偶问题的提出 例1.1:某工厂拥有A、B、C三种类型的设 备，生产甲、乙两种产品。每件产品在 生产中需要占用的设备机时数，每件产 品可以获得的利润以及三种设备可利用 的时数如下表所示：4产品甲产品乙设备能力（ h） 设备A3265设备B2140设备C0375利润（元/件）15002500 设变量xi为第i种（甲、乙）产品的生产 件数（i1, 2）5max z
2、 =1500x1 + 2500x2 s.t. 3x1 + 2x2 652x1 + x2 403x2 75x1, x2 0 若该工厂的设备都用于出租，工厂收取出租 费。试问：设备 A、B、C 每工时各如何收 费才最有竞争力？6设 y1, y2, y3 分别为每工时设备A、B、C 的出租费。min w = 65y1 + 40y2 + 75y3 s.t. 3y1 + 2y2 1500（不少于甲产品的利润） 2y1 + y2 + 3y3 2500（不少于乙产品的利润） y1, y2, y3 07max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 65 2x1 + x2 40
3、原问题 3x2 75 x1, x2 0min w = 65y1 + 40y2 + 75y3s.t. 3y1 + 2y2 15002y1 + y2 + 3y3 2500 对偶问题 y1, y2, y3 08对偶问题的定义 对称形式：互为对偶(LP) max z = c x (DP) min w = y bs.t. Ax b s.t. y A cx 0 y 0 注意： x为列向量, y为行向量。9原问题的最优单纯形表中关于对偶问题 的最优解的信息：(LP) max z = cx (DP) min w =y bs.t. Ax b s.t. yA cx 0 y 0 max z = cx 标准化 max
4、 z = cx + 0xs s.t. Ax b s.t. Ax + Ixs = b x 0 x, xs 010cB cN0cB xB b xB xN xS0 xS b B N I检验数行 cB cN0cB cN 0cB xB b xB xN xS cB xB B-1b I B-1N B-1检验数行0cN -cBB-1N - cBB-1 经过若干次迭代（标准化）原问题的初始单纯形表11当单纯形表为最优表时，检验数行为： (cB, cN, 0) - cBB-1(B, N, I) = (0, cN - cBB-1N, -cBB-1) 0 令 y=cBB-1, 易看出 yA c y 0又因为 w =
5、yb = cBB-1b = z 根据后面的强对偶理论知 cBB-1 为对偶问题的 最优解。而cBB-1就是最优单纯形表中对应于 松弛变量的检验数的负值。12例2.2： max z = 50x1 + 100x2 s.t. x1 + x2 300 2x1 + x2 400 x2 250 x1, x2 0 加松弛变量得标准形式： max z = 50x1 + 100x2 s.t. x1 + x2 + x3 = 3002x1 + x2 + x4 = 400 x2 + x5 = 250 x1, x2, x3, x4, x5 013cBB-1IB=(P1, P4, P2)B-1最优解：x1 = 50, x
6、2 = 250, x4 = 50 对偶最优解：y1 = 50, y2 = 0, y3 = 50 B-1对应的检验数 T = cBB-1。14原问题（对偶问题）对偶问题（原问题） max z = cxmin w = ybn 个变量n 个约束xj 0a1jy1 + a2jy2 + + a2jym cjxj 0a1jy1 + a2jy2 + + a2jym cjxj 无约束a1jy1 + a2jy2 + + a2jym = cjm 个约束m 个变量ai1x1 + ai2x2 + + ainxn biyi 0ai1x1 + ai2x2 + + ainxn biyi 0ai1x1 + ai2x2 + +
7、 ainxn = biyi 无约束非对称形式的对偶规划 15举列说明：设原规划中第一个约束为等式： a11x1 + + a1nxn = b1那么，这个等式与下面两个不等式等价 a11x1 + + a1nxn b1a11x1 + + a1nxn b116这样，原规划模型可以写成17此时已转化为对称形式，直接写出对偶 规划这里，把y1看作是 y1 = y1 - y1，于是 y1 没有非负限制。18例2.1 写出右 边线性规划问 题的对偶问题 。最小化问题：最小化问题的对偶问题：变成目标函 数的系数系数变成约束 条件右侧值变成第一个 约束条件的 系数反过来，由下 往上也是一样 的。192. 对偶问题
8、的基本性质(LP)Max z = j=1,2,n cj xj s.t. j=1,2,n aij xj bi , i = 1, 2, , mxj 0, j = 1, 2, , n(DP)Min w = i=1,2,m bi yi s.t. i=1,2,m aij yi cj , j = 1, 2, , nyi 0, i = 1, 2, , m20对偶规划的性质和原理定理2.0 (对称性）对偶规划的对偶规划是原规划定理2.1 (弱对偶定理） 若 x, y 分别为(LP)和(DP)的可行解，则 cx yb21推论(无界性) 若(LP)具有无界解，则(DP)无可行解。注：反之则不一定成立。 (DP)无
9、可行解，对应(LP)或有无 界解，或无可行解定理2.2 (最优性定理) 若x*, y*分别(LP)和(DP)的可行解，且 cx* = y*b, 那么x*, y*分别为(LP)和(DP)的最优解。22定理2.3 (强对偶定理)若(LP)和(DP)均可行，那么(LP)和(DP)均有最优解， 且最优值相等。定理2.4 (互补松弛定理) 若X*,Y*为最优解，Xs,Ys为原问题和对偶问题的松弛 变量，则有YsX*=0,Y*Xs=0也即，在(LP)和(DP)的最优解中： (1) 如果对应某一约束的对偶变量取值非零，则该约 束取严格等式； (2) 如果某一约束取严格不等式，则其对应的对偶变 量必取零。23
10、定理2.5 原问题单纯型表的检验数行对应对偶问题的一个基解cB cN 0cB xB b xB xN xS cB xB B-1b I B-1N B-1检验数行0cN -cBB-1N - cBB-1 24例2.3： 已知线性规划max z = 50x1 + 100x2 s.t. x1 + x2 300 2x1 + x2 400 x2 250 x1, x2 0 的最优解为 x1* = 50, x2* = 250，求出该 线性规划对偶问题的最优解。 25解： x1* + x2* = 300 y1* 0, 2x1* + x2* 0 y1* + 2y2* = 50, x2* 0 y1* + y2* + y
11、3* = 100. 所以， y1* = 50, y2* = 0, y3* = 50.26例： 已知线性规划max z = x1 + x2 s.t. -x1 + x2 + x3 2 -2x1 + x2 - x3 1 x1, x2 x3 0 试用对偶理论证明该线性规划无最优 解。 27解：min w = 2y1 + y2 s.t. - y1 - 2y2 2 y1 + y2 1 y1 - y2 0 y1 , y2 0对偶问题无可行解28wmax z =2x1 + 4x2+x3+x4ws.t. x1 + 3x2 + x4 8w 2x1 + x2 6w x2 + x3 + x4 6w x1 + x2 + x3 9wxj 0 课堂练习：已知原问题最优解为（2,2,4,0），根据对偶 理论，写出对偶问题的最优解294. 对偶单纯形法w基本思想w算法过程w算例30基本思想cB cN 0cB xB b xB xN xS cB xB B-1b I B-1N B-1检验数行0cN -cBB-1N -cBB-1 31单纯形算法cB cN 0cB xB b xB xN xS cB xB B-1b0 I B-1N B-1检验数行0 cN - cBB-1N - cBB-1 032对偶单纯形法cB cN 0cB xB b xB xN
