線形計画問題 | 制御系CAD

線形計画問題

[1] 　次の線形計画問題を考えます。

$\displaystyle{\boxed{ \begin{array}{l} {\rm\bf maxmize}\ f(x,y)=x+y\\ {\rm\bf subject\ to}\ \left\{\begin{array}{l} x\ge0\\ y\ge0\\ 5x+6y\le30\\ 3x+2y\le12 \end{array}\right. \end{array}} }$

これは目的関数

$\displaystyle{(1)\quad f(x,y)=x+y}$

を制約条件

$\displaystyle{(2)\quad \left\{\begin{array}{l} x\ge0\\ y\ge0\\ 5x+6y\le30\\ 3x+2y\le12 \end{array}\right. }$

の下で最小化する決定変数 $x,y$ を求める問題として定式化されています。制約条件を満たす $x,y$ の集合を実行可能領域と呼びます。この問題は図1のように図示され、実行可能領域は凸多角形となり、これを通過する直線 $y=-x+z$ のうち最大の $y$ 切片を与える端点として求められます。

図1 線形計画問題の例

●この問題を制約条件付最小化問題

$\displaystyle{\boxed{ \begin{array}{l} {\rm\bf minimize}\ f(x,y)=-(x+y)\\ {\rm\bf subject\ to}\ \left\{\begin{array}{l} x\ge0\\ y\ge0\\ 5x+6y\le30\\ 3x+2y\le12 \end{array}\right. \end{array}} }$

として、MATLABで解く場合のコードを次に示します。

MATLAB

%lp.m
%-----
 clear all close all
 x=-1:10; y=-1:10; 
 plot(x,-5/6*x+5,'b',x,-3/2*x+6,'b',x,-x+3,'r')
 axis([0 6 0 6]),grid, hold on
%------ LMIの設定
 setlmis([]); 
 x=lmivar(1,[1 1]); y=lmivar(2,[1 1]); 
 lmi1=newlmi;                   %#1: x>=0
 lmiterm([-lmi1 1 1 x],1,1);    %x in RHS 
 lmi2=newlmi;                   %#2: y>=0 
 lmiterm([-lmi2 1 1 y],1,1);    %y in RHS 
 lmi3=newlmi;                   %#3: 5x+6y-30<=0
 lmiterm([lmi3 1 1 x],5,1);     %5x in LHS
 lmiterm([lmi3 1 1 y],6,1);     %6y in LHS
 lmiterm([lmi3 1 1 0],-30);     %-30 in LHS
 lmi4=newlmi;                   %#3: 3x+2y-12<=0
 lmiterm([lmi4 1 1 x],3,1);     %3x in LHS
 lmiterm([lmi4 1 1 y],2,1);     %2y in LHS
 lmiterm([lmi4 1 1 0],-12);     %-12 in LHS
 LMIs=getlmis;  
%----- 実行可能解の存在
 [tmin,xfeas]=feasp(LMIs); tmin
 xf=dec2mat(LMIs,xfeas,x), yf=dec2mat(LMIs,xfeas,y)
 plot(xf,yf,'*')
%----- 目的関数の設定と最小解求解
 cobj=-[1 1]; 
 [cost,xopt]=mincx(LMIs,cobj); cost
 xs=dec2mat(LMIs,xopt,x), ys=dec2mat(LMIs,xopt,y)
 plot(xs,ys,'o')
%-----
%eof

実行可能解の存在をチェックする関数feapの実行結果は次のようになり、 $t<0$ の値が得られているので、一つの実行可能解が示されています。


 Solver for LMI feasibility problems L(x) < R(x)
    This solver minimizes  t  subject to  L(x) < R(x) + t*I
    The best value of t should be negative for feasibility

 Iteration   :    Best value of t so far 
 
     1                       -1.203989

 Result:  best value of t:    -1.203989
          f-radius saturation:  0.000% of R =  1.00e+09
 

tmin =
   -1.2040

xf =
    1.2781

yf =
    3.3444

制約条件付最小化問題を解く関数mincxの実行結果は次のようになり、最小解が示されています。


 Solver for linear objective minimization under LMI constraints 

 Iterations   :    Best objective value so far 
     1                  -5.075328
***                 new lower bound:    -5.611584
     2                  -5.211637
***                 new lower bound:    -5.312330
     3                  -5.248462
***                 new lower bound:    -5.298322
 Result:  feasible solution of required accuracy
          best objective value:    -5.248462
          guaranteed relative accuracy:  9.50e-03
          f-radius saturation:  0.000% of R =  1.00e+09 
 
cost =
   -5.2485

xs =
    1.4914

ys =
    3.7571