Matlab随筆之線性規劃

原文: Matlab随筆之線性規劃

LP(Linear programming,        線性規劃               )是一種優化方法,在優化問題中        目标函數               和限制函數均為向量變量的        線性函數               ,LP問題可描述為:
min  x
s.t.
              A·x b
              Aeq·x=beq
              vlb x vub
其中 ，b,beq均為向量，A,Aeq為矩陣，x為向量變量.矩陣A和向量b是線性不等式        限制條件               的系數，      

Aeq和beq是等式

限制條件

的系數.

在MATLAB中，用于LP的求解函數為linprog.其調用格式為：
[x,fval,lambda]=linprog(f,A,b,Aeq,beq,vlb,vub,x0,options)
其中f,A,b,是不可        預設               的輸入變量，x是不可        預設               的輸出變量，它是問題的解.vlb,vub均是向量，分别表示x的下界和上界，x0為x的起始點，options為optimset函數中定義的參數的值，fval是目标函
數在解x處的值，lambda為在解x處的lagrange乘子.lambda.lower對應于vlb，lambda.upper對應于ulb，lambda.ineqlin是對應于線性不等式限制的，lambda.eqlin是對應于線性等式限制的.      

例子1

>>% 求解下列線性規劃問題 
% max z=2x1+3x2-5x3 
% s.t. x1+x2+x3=7 
%      2x1-5x2+x3>=10 
%      x1+3x2+x3<=12 
%      x1,x2,x3>=0

f=[2;3;-5];%目标函數列矩陣 
A=[-2,5,-1;1,3,1];%不等矩陣 
b=[-10;12]; 
Aeq=[1,1,1];%相等矩陣 
beq=7; 
x=linprog(-f,A,b,Aeq,beq,zeros(3,1)); 
%zeros(m,n)産生m×n的double類零矩陣，zeros(n)産生n×n的全0方陣 
value=f'*x%目标值，其值等于[x,y]=linprog(-f,A,b,Aeq,beq,zeros(3,1))的-y 
Optimization terminated.

value =

   14.5714

>> x

x =

    6.4286 
    0.5714 
    0.0000

>>      

例子2

>> % 求解下列線性規劃問題 
% min z=2x1+3x2+x3 
% s.t. x1+4x2+2x3>=8 
%      3x1+2x2>=6 
%      x1,x2,x3>=0 
f=[2;3;1]; 
A=[-1,-4,-2;-3,-2,0]; 
b=[-8;-6]; 
x=linprog(f,A,b,[],[],zeros(3,1))%無等式，用[]代替 
value=f'*x %其值等于[x,y]=linprog(f,A,b,[],[],zeros(3,1))的y 
Optimization terminated.

x =

    0.8066 
    1.7900 
    0.0166


value =

    7.0000

>>      

例子3

% min  z=|x1|+2|x2|+3|x3|+4|x4|;
% s.t.   x1-x2-x3+x4=0;
%        x1-x2+x3-3*x4=1;
%        x1-x2-2*x3+3*x4=-0.5
%目标函數 
objfun=@(x)abs(x(1))+2*abs(x(2))+3*abs(x(3))+4*abs(x(4)) 
%等式限制 
Aeq=[1 -1 -1 1 
     1 -1 1 –3 
     1 -1 -2 3];
beq=[0 1 -0.5]'; 
x0=[0 0 0 0];%給一個初值 很關鍵
x=fmincon(objfun,x0,[],[],Aeq,beq)

%下面是根據的需要改進的程式
依據：|x|=u+v,x=u-v(u,v>=0)

min z=[1 2 3 4 1 2 3 4]*[u1 u2 u3 u4 v1 v2 v3 v4];
s.t.

A=[1 -1 -1 1 -1 1 1 -1
   1 -1 1 -3 -1 1 -1 3
   1 -1 -2 3 -1 1 2 -3]

x=[u1 u2 u3 u4 v1 v2 v3 v4]'

b=[0 1 -0.5]'

Ax=b
x>=0

%目标函數
f=[1 2 3 4 1 2 3 4];
%等式限制
      

  Aeq=[1 -1 -1 1

  1 -1 1 -3

  1 -1 -2 3];

  Aeq=[Aeq,-Aeq];

beq=[0 1 -0.5]';
%邊界條件
lb=zeros(8,1);
%調用linprog
x=linprog(f,[],[],Aeq,beq,lb)

Optimization terminated.      

x =

    0.2500

    0.0000

    0.2500