Vol.17 No.2 周汉良：线性规划问题最优解的表示 ,181 x3+x5-2x6+x,+3xg=2 x4-x5-x6+x,-2xg=4 符合定理2的(2)，除了最估极点X=(1,2,2,4,0,0,0,0)T外，用单纯形法可求出另外3 个最优极点：X2=(0,3,1,5,1,0.0,0),X=(0,0,7,8,1,3,0,0),X4=(0,0,0,19/5,1,1/5,7/5,0). 再考察相应的不等式组(4)： Xs ≤0 -x5+x6+2x,≤0 x3-2x6+x7≤0 -x5-x6+x,≤0 由第1、第2式看出属情况a:由第1式x,=0,代人第2式x6+x,≤0，得x6=x,=0.故 不存在最优极方向·所以该问题的最优解为： X-2K,含=1，A≥0i=1234 例2，设(Lp)为： minS=6-x3-x4+2x5-x6+4x, s.t.X1 +2x4-4x5+x6-2x1 =2 x2+3x3+2x4-7x5+4x6-3x7=10 x3+x4-2x5+x6-x7+xg=3 x,≥0，j=1,…,8 经单纯形法迭代化为： min S=3+3x+x s.t.X1 +2x4-4x5+x6-2x7=2 X2 -x4-x5+x6-3xg=1 x3+x4-2x5+x6-x7+xg=3 x≥0，j=1,…,8 除了最优极点X1=(2,1,3,0,0,0,0,0)T外，因x4、x6的检验数为零，且对应列有正数，非退化， 用单纯形法可求出另两个最优极点：X2=(0,2,2,1,0,0,0,0),X3=(1,0,2,0,0,1,0,0)T. 求最优极方向对应的不等式组(4)为： 2x4-4x3+x6≤0 -x4-x5+x6≤0 x4-2x5+x6≤0 属情况b.{4,5,6}有4个非空子集R,={5},R2={4,5},R,={5,6},R4={4,5,6,使得： ≤0，i=12,3,k=1,2,3,4.对应有4个最优极方向：d,=(4,1,20,1,00,0)”, d2=(2,2,1,1,1,0,0,0),d,=(3,0,1,0,1,1,0,0),d4=(1,1,0,1,1,1,0,0).该问题的最 优解为： X-店2+24，言=1≥0,1=1,2354，≥0，j=1,234 (下转186页)V b l . 1 7 N b . 2 周 汉 良 线 性规: 划 问题 最 优解 的表 示 · 1 1 8 · 3 x + s 一 x 2 x 6 + x 7 + 3 s = x 2 一 xs 4 一x x 6 + 厂 x Z x : = 4 符 合定 理 的 2 ) ( 2 , 除 了最 估 极 点 Xl = ( 1 , 2 , 2 , 4 , O , 0 , 0 , O) T 外 , 用 单 纯 形 法 可 求 出 另 外 3 个最优 极点 : r = ( 0 , 3 , l , 5 , l , O , 0 , 0 )T , X , = ( 0 , 0 , 7 , 8 , l , 3 , O , 0 )T , X 4 = ( 0 , O , 0 , 19 / 5 , l , l / 5 , 7 / 5 , O丫 . 再 考 察相 应 的不 等 式 组 ( 4) : { x s ( 0 一 x s + x 6 + 2 x 7 ( 0 x s 一 2 x 6 + x 7 毛 0 一 x s 一 x 6 + x 7 成 0 由第 1 、 第 2 式 看 出 属 情 况 :a 由第 l 式 x s = 0 , 代人第 2 式 x 6 + x 7 簇 0 , 得 x 6= x 产 0 . 故 不存在 最 优 极 方 向 . 所 以 该 问题 的最 优 解 为 : x 一 艺* ` x l , 艺又i 一 l , 又i ) o , 2 , 3 , 4 例 2 , 设 ( L p ) 为 : m i n s = 6 一 x 3 一 x 4 + Z x s 一 x 6 + 4 x 7 5 . t . x 一 + Z x ` 一 4 x s + x 6 一 2 x 7 = 2 x Z + 3 x 3 + Z x ; 一 7 x s + 4 x 6 一 3 x , = 1 0 x 3 + x 一 2 x 5 + x 6 一 x 7 + x s = 3 x , ) 0 , j = 1 , … , 8 经 单纯 形 法 迭 代化 为 : m i n s = 3 + 3 x 7 + x s 5 . t . x 一 + 2 x 4 一 4 x s + x 6 一 2 x 7 = 2 x Z 一 x 4 一 x s + x 6 一 3 x : = l x 3 + x 4 一 Z x s + x 6 一 x 7 + x s = 3 x , ) 0 , j = l , … , 8 除 了最优极点 x , = ( 2 , 1 , 3 , o , o , o , 0 , 0 ) T 外 , 因 丸 、 x 6 的检验 数 为零 , 且 对应列有正数 , 非退化 , 用 单纯 形 法 可 求 出 另 两 个 最 优 极 点 : 矛 = ( o , 2 , 2 , l , O , o , 0 , 0 ) T , x , = ( l , O , 2 , O , 0 , l , 0 , 0 ) T . 求 最 优 极 方 向对 应 的 不 等 式 组 ( 4) 为 : 2 x 4 一 4 x s + x 6 簇 0 一 x 4 一 x s + x 6 ( O x ; 一 2 x 5 + x 6 簇 O 属情 况 b . 属笋 , ` 0 , d : = ( 2 , 2 , 优 解 为 : { 4 , 5 , 6 } 有 4 个 非 空 子 集 R l = { 5 } , R Z = { 4 , 5 } , R 3 = { 5 , 6 } , R 4 = { 4 , 5 , 6 } , 使 得 : i = l , 2 , 3 , k = l , 2 , 3 , 4 . 对 应有 4 个 最 优 极 方 向 : d , = ( 4 , l , 2 , 0 , l , 0 , O , O) T , l , l , l , 0 , 0 , 0 ) T , d 3 = ( 3 , O , l , 0 , l , l , 0 , 0 ) , d 4 = ( l , l , 0 , l , l , l , 0 , O ) . 该 问题的最 3 4 X 一 落 1 “ ` X ’ 十万 , “ , d , 艺又 : = 1 ; 又 ` ) 0, , 2 , 3 ; 拜, ) O , j = l , 2 , 3 , 4 (下 转 18 6 页 )