单纯形方法的两个变种

考虑标准形式的线性规划问题: (LP) maxinlize z=c。rz s.t. 4z一6,zJ≥0,J∈E={1,…,w).其中_∈门“‘,6∈胪,c∈彤,且以为行满秩.设有一基矩阵力。::(“,。,…,‰),相应的基变量构成的向量为z一:(zJl,…,z‘)’.引入列指标集t,。=㈦,…,√,。)及填补集瓦=层一J。和行指标集 ,={。l(刀:6)。<0, 。一I,…,Ⅲ) 、 (1)及其补集7={I,…川。)一,.我们_仃如。卜‘类型的子问题: nlax…ze z。三0 ∑孕J (2a); 。∈”H s.t.。口==以:’6一≥:(以=’ⅡJ)zJ; (2b) i虿。a q≥O,V J∈,B; (2c) zj.≥0,V i∈,. (2d)著,非空,取行指标i使得 i:Arg…