问题引入
某机床厂生产甲、乙两种机床，每台销售后的利润分别为 4000 元与 3000 元。生产甲机床需用A、B机器加工,加工时间分别为每合 2h 和1h;生产乙机床需用 A、B、C三种机器加工,加工时间为每台各1h。 若每天可用于加工的机器时数分别为A机器10h B机器8h 和C机器7h,问该厂应生产甲、己机床各儿台,才能便总利润最大？
上述问题的数学模型：设该厂生产x1台甲机床和x2台机床时总利润最大
max
z
=
4
x
1
+
3
x
2
\max z=4x1+3x2
maxz=4x1+3x2
s
.
t
{
2
x
1
+
x
2
≤
10
x
1
+
x
2
≤
8
x
2
≤
7
x
1
,
x
2
≥
0
s.t\left\{ \begin{aligned} 2x1+x2≤10 \\ x1+x2≤8 \\ x2≤7\\x1,x2≥0 \end{aligned} \right.
s.t⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧2x1+x2≤10x1+x2≤8x2≤7x1,x2≥0
线性规划问题是在一组线性约束条件的限制下，求线性目标函数的最大或者最小问题
min
x
f
T
x
\min_xf^Tx
minxfTx
s
.
t
{
A
⋅
x
≤
b
A
e
q
⋅
x
≤
b
e
q
l
b
≤
x
≤
u
b
s.t\left\{ \begin{aligned} A·x≤b \\ Aeq·x≤beq \\ lb≤x≤ub \end{aligned} \right.
s.t⎩⎪⎨⎪⎧A⋅x≤bAeq⋅x≤beqlb≤x≤ub
式中：f,x,b,beq,lb,ub为列向量，f为价值向量，b为资源向量;A,Aeq为矩阵
MATLAB中对应的命令为：
[
x
,
f
v
a
l
]
=
l
i
n
p
r
o
g
(
f
,
A
,
b
)
[x,fval]=linprog(f,A,b)
[x,fval]=linprog(f,A,b)
[
x
,
f
v
a
l
]
=
l
i
n
p
r
o
g
(
f
,
A
,
b
,
A
e
q
)
[x,fval]=linprog(f,A,b,Aeq)
[x,fval]=linprog(f,A,b,Aeq)
[
x
,
f
v
a
l
]
=
l
i
n
p
r
o
g
(
f
,
A
,
b
,
A
e
q
,
l
b
,
u
b
)
[x,fval]=linprog(f,A,b,Aeq,lb,ub)
[x,fval]=linprog(f,A,b,Aeq,lb,ub)
式中:x返回决策向量的取值;fval返回目标函数的最优值;f为价值向量;A
和b对应线性不等式约束;Aeq和 beg对应线性等式约束;lb和ub分别对应决策向量的下界向量和上界向量。
注：max和≥应该转换成min和≤
以下例子为例：
max
z
=
2
x
1
+
3
x
2
−
5
x
3
\max z=2x1+3x2-5x3
maxz=2x1+3x2−5x3
x
1
+
x
2
+
x
3
=
7
x1+x2+x3=7
x1+x2+x3=7
s
.
t
{
2
x
1
−
5
x
2
+
x
3
≥
10
x
1
+
3
x
2
+
x
3
≤
12
x
1
,
x
2
,
x
3
≥
0
s.t\left\{ \begin{aligned} 2x1-5x2+x3≥10 \\x1+3x2+x3≤12 \\ x1,x2,x3≥0 \end{aligned} \right.
s.t⎩⎪⎨⎪⎧2x1−5x2+x3≥10x1+3x2+x3≤12x1,x2,x3≥0
化为标准型，即
min
w
=
−
2
x
1
−
3
x
2
+
5
x
3
\min w=-2x1-3x2+5x3
minw=−2x1−3x2+5x3
s
.
t
{
[
−
2
5
−
1
1
3
1
]
[
x
1
x
2
x
3
]
≤
[
−
10
12
]
[
1
1
1
]
[
x
1
x
2
x
3
]
T
=
7
[
x
1
x
2
x
3
]
T
≥
[
0
0
0
]
T
s.t\left\{ \begin{aligned} \begin{bmatrix} -2&5&-1\\ 1&3&1\end{bmatrix}\begin{bmatrix} x1\\ x2\\x3\end{bmatrix}≤\begin{bmatrix} -10\\ 12\end{bmatrix} \\ \begin{bmatrix} 1&1&1\end{bmatrix}\begin{bmatrix} x1&x2&x3\end{bmatrix}^T=7 \\ \begin{bmatrix} x1&x2&x3\end{bmatrix}^T≥\begin{bmatrix} 0&0&0\end{bmatrix}^T \end{aligned}\right.
s.t⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧[−2153−11]⎣⎡x1x2x3⎦⎤≤[−1012][111][x1x2x3]T=7[x1x2x3]T≥[000]T
对应的MATLAB代码为:
f
=
[
2
;
−
3
;
5
]
;
a
=
[
−
2
,
5
,
−
1
;
1
,
3
,
1
]
;
b
=
[
−
10
,
12
]
;
a
e
q
=
[
1
,
1
,
1
]
;
b
e
q
=
7
;
[
x
,
y
]
=
l
i
n
p
r
o
g
(
f
,
a
,
b
,
b
e
q
,
z
e
r
o
s
(
3
,
1
)
)
x
,
y
=
−
y
f=[2;-3;5];\\ a=[-2,5,-1;1,3,1];\\b=[-10,12]; aeq=[1,1,1];\\ beq=7;\\ [x,y]=linprog(f,a,b,beq,zeros(3,1))\\ x,y=-y
f=[2;−3;5];a=[−2,5,−1;1,3,1];b=[−10,12];aeq=[1,1,1];beq=7;[x,y]=linprog(f,a,b,beq,zeros(3,1))x,y=−y