求解线性规划的 Matlab 解法
单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形
法是首先由
George Dantzig于 1947 年提出的,近 60 年来,虽有许多变形体已被开发,
但却保持着同样的基本观念。由于有如下结论:若线性规划问题有有限
最优解,则一定有某个最优解是可行区域的一个极点。基于此,单纯形
法的基本思路是:先找出可行域的一个极点,据一定规则判断其是否最
优;若否,则转换到与之相邻的另一极点,并使目标函数值更优;如此
下去,直到找到某一最优解为止。这里我们不再详细介绍单纯形法,有
兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的
Matlab 解法。
Matlab5.3 中线性规划的标准型为
T
c x such that Ax bmin
x
基本函数形式为 linprog(c,A,b),它的返回值是向量
x
的值。还有其它的一
些函数调用形式(在 Matlab 指令窗运行 help linprog 可以看到所有的函
数调用形式),如:
[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X
0
,OPTIONS)
这里 fval 返回目标函数的值,Aeq 和 beq 对应等式约束
Aeq * x beq
,LB
和 UB 分别是变量
x
的下界和上界,
x
0
是
x
的初始值,OPTIONS 是控制参
数。
例 2 求解下列线性规划问题
max z 2 x
1
3 x
2
5 x
3
x
1
x
2
x
3
7
2 x
1
5 x
2
x
3
10
x , x , x 0
1 2 3
解 (i)编写 M 文件
c=[2;3;-5];
a=[-2,5,-1]; b=-10;
aeq=[1,1,1];
beq=7;
x=linprog(-c,a,b,aeq,beq,zeros(3,1))
value=c'*x
(ii)将M文件存盘,并命名为example1.m。
(iii)在Matlab指令窗运行example1即可得所求结果。
例3 求解线性规划问题
min z 2 x
1
3 x
2
x
3