现要求从x(2)出发构造一个改进的基可行解.因检验数λ1=3>0,故令x1=θ,x2仍取零值.根据问题的典式,θ值确定如下:
此比值对应第一个约束方程,由此可知离基变量是x3.令x3取零值,其余基变量的值确定如下:
至此得出新基可行解,这正好是x(1).
设线性规划问题LP有r个基可行解:x(1),x(2),…,x(r),且知LP的可行解集K满足
试证:LP的最优解x*满足
f(x*)=min{f(x(1)),f(x(2)),…,f(x(r)}.
设对LP施行一次单纯形迭代时,从基可行解x(1)转换到x(2),且知x(1)是非退化的,则x(1)与x(2)是LP的可行解集K的相邻极点.
对于运输问题的一个基可行解,设xkl为一非基变量,并设从xkl出发以基变量为其余顶点的闭回路为
xkl,xkq1,xp1q1,xp1q2,…,xplql,xpll.试证明:xkl对应的检验数等于该闭回路上偶序顶点对应运价之和减去奇序顶点对应运价之和,即
λkl=(ckq1+cp1q2+…+cpll)-(ckl+cp1q1+…+cplql)(此题提供了一种求检验数的方法,称之为闭回路法).
对如下线性规划问题:
min f=4x1+x2+x3,
s.t.2x1+x2+2x3=4,
3x1+3x2+x3=3,
x1,x2,x3≥0,写出对应于基B1=(p1,p3)的典式,并判别它对应的基可行解x(1)是否为问题的最优解.
X是线性规划的基本可行解则有:
A.X中的基变量非零,非基变量为零
B.X不一定满足约束条件
C.X中的基变量非负,非基变量为零
D.X是最优解