中国矿业大学：《运筹学》课程教学课件（讲稿）Chapter 2 对偶理论（Duality Theory）

运筹学改进的单纯形法0312000XBbCX1X4X5X2X3X610150011X4[3]20001831X1600310-11X62030001O;03501/3151/31/3X103003-2-1X518004/34/31/3106X0100-150-13%)133Y3303P2→5=-1-11-2E,P, HIAY-1Y3//-0-11-页页顶退退出主后China University of Mining and Technology1

-11- China University of Mining and Technology 运 筹 学 2 3 1 0 0 0 θ CB XB b x1 x2 x3 x4 x5 x6 0 X4 15 1 [3] 1 1 0 0 5 0 X5 18 2 3 -1 0 1 0 6 0 X6 3 1 -1 1 0 0 1 - σj 0 2 3 1 0 0 0 3 X2 5 1/3 1 1/3 1/3 0 0 15 0 X5 3 [1] 0 -2 -1 1 0 3 0 X6 8 4/3 0 4/3 1/3 0 1 6 -15 1 0 0 -1 0 0                                                                                        3 4 3 4 3 1 3 1 3 1 3 1 1 3 1 3 1 1 2 3 1 3 1 2 2 0 1 0 - 2 1 1 -1 1 2 3 -1 1 3 1 0 1 -1 1 0 0 0 0 0 1 -1 3 3 0 1 -1 1 0 0 0 -1 -1 3 3 P  ；E P ；E A 改进的单纯形法

运筹学改进的单纯形法2310000XbXIX2X3X4X5X6BB013501/31/31/31530-210-130[1]X0804/31/304/36X7000-151-100;0001-1/32/34-AX(-%)Y03-110-2T7P =1→5=0005/3-4/34[4]X(为)(-%)00200-18-1O:0-%0台/3020-E,E,A=-2E,P =0003-%1-12-￥页页质I退出主China University of Mining and Technology广

-12- China University of Mining and Technology 运 筹 学 2 3 1 0 0 0 θ CB XB b x1 x2 x3 x4 x5 x6 3 X2 5 1/3 1 1/3 1/3 0 0 15 0 X5 3 [1] 0 -2 -1 1 0 3 0 X6 8 4/3 0 4/3 1/3 0 1 6 σj -15 1 0 0 -1 0 0 0 X2 4 0 1 1 2/3 -1/3 0 4 1 X1 3 1 0 -2 -1 1 0 - 0 X6 4 0 0 [4] 5/3 -4/3 1 1 σj -18 0 0 2 0 -1 0                                                                 0 0 4 1 0 - 2 0 1 1 0 1 0 - 2 1 0 - 1 0 1 0 1 - 0 0 1 0 1 0 - 1 0 1 0 1 - 0 3 4 3 4 3 1 3 1 3 4 3 1 2 1 3 4 3 1 3 4 3 1 E2 P1 ；E E A ；                        3 4 3 1 1 3 4 3 1 1 - 1 - P 1  改进的单纯形法

运筹学改进的单纯形法求解线性规划问题的关键是计算B-1以下介绍一种比较简便的计算方法设mXm系数矩阵A，求其逆矩阵a1a12ama21(122a2maaamlm2mmal可以先从第1列开始：a21-13-大aml主页顶退山退China University of Mining and Technology万

-13- China University of Mining and Technology 运 筹 学 设m×m系数矩阵A，求其逆矩阵                m m mm m m a a a a a a a a a A       1 2 2 1 2 2 2 1 1 1 2 1 可以先从第1列开始:                1 2 1 1 1 1 m a a a P  以下介绍一种比较简便的计算方法 求解线性规划问题的关键是计算B-1 改进的单纯形法

运筹学改进的单纯形法以au为主元素，进行变换主元素1/aala12-az/au(1)P =1二-aml/aun然后构造含有（1）列，而其他列都是单位列的矩阵11/ au0-a21/aE,→E,P :au0ml-14-大顶退山主页贝D退China University of Mining and Technology

-14- China University of Mining and Technology 运 筹 学 (1) / / 1/ 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1                                a a a a a a a a P m m    主元素 以a11为主元素, 进行变换 然后构造含有（1）列，而其他列都是单位列的矩阵                  / 1 / 1 1/ 0 0 1 1 1 2 1 1 1 1 1 1 a a a a a E m                    0 0 1 1 1  E P 改进的单纯形法

运筹学改进的单纯形法1可得到：a21a210a21-ai1a22 -12E,P =anal0(1)am1/aualay2amai2α(l)1-a21 /a-an1a22(2ma2mE,A=.·..al?(1)01aml-am /aam2aamm1进行变换而后以第2列的a()为主元素，p()-a / a21 / al?p(1)(2)2(1)-15-22X主页一页页退退出后China University of Mining and Technology

-15- China University of Mining and Technology 运 筹 学 可得到：                                                              (1) (1) 2 (1) 2 (1) 2 2 (1) 1 (1) 1 2 1 2 2 1 2 2 2 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1 1 1 0 0 1 / 1 / 1 1/ 0 0 ; 0 0 1 m mm m m m m mm m m m a a a a a a a a a a a a a a a a a a a a E A E P                 1 1 2 1 2 2 1 2 1 1 2 1 2 1 1 1 a a a a a a a  a  而后以第2列的a22 (1) 为主元素，进行变换 (2) / 1/ / (1) 2 2 (1) 2 (1) 2 2 (1) 2 2 (1) 1 2 2 (1) 2                   a a a a a P m   (1) P2 改进的单纯形法