1. 将线性规划化为典范形式,从而可以得到一个初始基本可行解 x
(0)
(初始顶点),
将它作为迭代过程的出发点,其目标值为 z(x
(0)
)。
2. 寻找一个基本可行解 x
(1)
,使 z(x
(1)
)≤z(x
(0)
)。方法是通过消去法将产生 x
(0)
的
典范形式化为产生 x
(1)
的典范形式。
3. 继续寻找较好的基本可行解 x
(2)
,x
(3)
,…,使目标函数值不断改进,即 z(x
(1)
)≥z(x
(2)
) ≥z(x
(3)
) ≥…。当某个基本可行解再也不能被其它基本可行解改进时,它就
是所求的最优解。
Matlab 优化工具箱中采用的是投影法,它是单纯形法的一种变种。
9.2.2.2 相关函数介绍
linprog 函数
功能:求解线性规划问题。
数学模型:
其中 f, x, b, beq, lb 和 ub 为向量,A 和 Aeq 为矩阵。
语法:
x = linprog(f,A,b,Aeq,beq)
x = linprog(f,A,b,Aeq,beq,lb,ub)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
[x,fval] = linprog(...)
[x,fval,exitflag] = linprog(...)
[x,fval,exitflag,output] = linprog(...)
[x,fval,exitflag,output,lambda] = linprog(...)
描述:
x = linprog(f,A,b)求解问题 min f'*x,约束条件为 A*x <= b。
x = linprog(f,A,b,Aeq,beq)求解上面的问题,但增加等式约束,即 Aeq*x
= beq。若没有不等式存在,则令 A=[]、b=[]。
x = linprog(f,A,b,Aeq,beq,lb,ub)定义设计变量 x 的下界 lb 和上界 ub,
使得 x 始终在该范围内。若没有等式约束,令 Aeq=[]、beq=[]。
x = linprog(f,A,b,Aeq,beq,lb,ub,x0)设置初值为 x0。该选项只适用于中
型问题,缺省时大型算法将忽略初值。
x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)用 options 指定的优化参
数进行最小化。
[x,fval] = linprog(...) 返回解 x 处的目标函数值 fval。
[x,lambda,exitflag] = linprog(...)返回 exitflag 值,描述函数计算的
退出条件。
[x,lambda,exitflag,output] = linprog(...) 返回包含优化信息的输出变
量 output。
[x,fval,exitflag,output,lambda] = linprog(...) 将解 x 处的拉格朗日
乘子返回到 lambda 参数中。
变量: