线性规划问题:
min
x
f
T
∗
x
,
\min \limits_{x} \quad f^{T}*x,
xminfT∗x,
s
.
t
.
=
{
A
∗
x
≤
b
A
e
q
∗
x
=
b
e
q
l
b
≤
x
≤
u
b
s_{.}t_{.}=\left\{ \begin{array}{rcl} A*x \leq b \\ Aeq *x=beq \\ lb \leq x \leq ub\\ \end{array} \right.
s.t.=⎩⎨⎧A∗x≤bAeq∗x=beqlb≤x≤ub
[x,fval]=linprog(f,A,b)
[x,fval]=linprog(f,A,b,Aeq,beq)
[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)
式中:x返回决策向量的取值,fval返回所要求的目标函数的最优值,A,b对应x的不等式约束;Aeq,beq对应等式约束;lb,ub对应决策变量即x的下界和上界来避免所求的x超界。(A,b,Aeq,beq,lb,ub均对应的是决策变量x的约束)
-
可以转化为线性规划的问题:
数学规划问题:
m
i
n
∣
x
1
∣
+
∣
x
2
∣
+
∣
x
3
∣
+
⋯
+
∣
x
n
∣
,
min \qquad \mid x_{1} \mid+\mid x_{2} \mid +\mid x_{3}\mid+\cdots+\mid x_{n}\mid,
min∣x1∣+∣x2∣+∣x3∣+⋯+∣xn∣,
s
.
t
.
A
∗
x
≤
b
s_{.}t_{.}\quad A*x\leq b
s.t.A∗x≤b
式中:
x
=
[
x
1
,
⋯
 
,
x
n
]
T
;
x=[x_{1},\cdots,x_{n}]^{T};
x=[x1,⋯,xn]T; A,b为相应维数的矩阵和向量。
要将上面的问题转化为线性规划问题,关键为:对任意
x
i
x_{i}
xi,存在
u
i
,
v
i
≥
0
u_{i},v_{i}\geq 0
ui,vi≥0满足
x
i
=
u
i
−
v
i
,
∣
x
i
∣
=
u
i
+
v
i
(
1
)
x_{i}=u_{i}-v_{i},\mid x_{i} \mid=u_{i}+v_{i} \qquad(1)
xi=ui−vi,∣xi∣=ui+vi(1)
由(1)式可得:只要取
u
i
=
x
i
+
∣
x
i
∣
2
,
v
i
=
∣
x
i
∣
−
x
i
2
u_{i}=\frac {x_{i}+\mid x_{i} \mid} {2},v_{i}=\frac {\mid x_{i}\mid-x_{i}} {2}
ui=2xi+∣xi∣,vi=2∣xi∣−xi即可消去
x
i
x_{i}
xi的绝对值,将数学规划问题转化为线性规划问题。
解题步骤:
Ⅰ 记
u
=
[
u
1
,
⋯
 
,
u
n
]
T
,
v
=
[
v
1
,
⋯
 
,
v
n
]
T
u=[u_{1},\cdots,u_{n}]^{T},v=[v_{1},\cdots,v_{n}]^{T}