设LP有最优解,M是充分大的正数,使得以原点为中心以M为半径的球至少包含LP的一个最优解,则求解LP可转化为求
min cx.
s.t.Ax=b,
0≤x≤Me.
试验证:对上述问题必可起动对偶仿射尺度算法.
min cx.
s.t.Ax=b,
0≤x≤Me.
试验证:对上述问题必可起动对偶仿射尺度算法.
min cx.
s.t.Ax=b,
0≤x≤Me.
试验证:对上述问题必可起动对偶仿射尺度算法.
用单纯形法直接求极大问题的LP如下
其最优单纯形表(为什么是最优的?)如下。
(1)从表上直接读出该问题对偶问题的最优解和最优值;
(2)使当前基保持最优时,求目标函数中x1的系数C1的取值范围。
证明下述结论:
设x(1),x(2)是LP的可行解集K={x|Ax=b,x≥0)的两个极点,则x(1)与x(2)相邻的充要条件是:A的列向量集{pi|xi(1)+xi(2)>0}线性相关,且存在指标l使{pj|xi(1)+xi(2)>0,i≠l)线性无关(xi(1),xi(2)分别表示x(1),x(2)的第i个分量)
对于LP的一个基.B,若B-1b≥0,且
λN=CBB-1N-cN≤0,
则对应于B的基解x(0)便是LP的最优解.
若x(0),u(0)分别为LP,DP的可行解,且cx(0)=u(0)b,则x(0),u(0)分别为LP,DP的最优解.
已知LP数学模型:
其对偶数学模型的最优解为X*=(x1*,x2*,…,xn*),则原数学模型的最优目标函数值为__________。
线性规划原问题(LP)为:,对偶问题(DP)为:。现用单纯形法求解(LP)得最优解,则在最优单纯形表中,同时也可得到(DP)的最优解等于()。
A.最优单纯形表中松弛变量的检验数
B.最优单纯形表中非基变量的检验数的相反数
C.最优单纯形表中松弛变量的检验数的相反数
D.最优单纯形表中非基变量的检验数