Matlab之将非严格占优矩阵化为严格占优矩阵

这个是只是用行变换将非严格占优矩阵通过行变换转换为严格占有矩阵。

伪代码如下：

Input matrix:A

Output:

      If A can transform into a dominance with our method,we can get the dominance.

      Else output’Cannot transform the matrix into dominance’

Variable:

Set a matrix record with the size [row_of_matrix,3]

Record[row_length_matrix,3]  %This matrix is for record A’s situation.

% Record[1:,1] first volumn stands for this row of A should be put which row

% Record[1:,2] second volumn stands for whether this row satisfy the necessity of transform into a dominance.If yes,set 1;otherwise 0.

% Record[1:,3] third volumn stands for which initial row belong to.

Flag% this variable is to record whether the matrix A can transform into a dominance.

% If yes,Flag = 1;

% otherwise Flag = 0

% beneath code is to test whether the matrix can transform into a dominance

% and record the situation of every row.

for i = 1:size_of_matrix

Test every row(Record);

If test_row’s Record[1:,2] == 0

    then break and output ’Cannot transform the matrix into dominance’

    Flag = 0;

end

end

% If Flag = 1,we use row exchangement to transform A into dominance

If Flag = 1

   Row_exchangment by record.

   for i = 1:row-1

       for j = 1:row

            if record(j,1) == i         %exchange line if flag = 1,which   

                %means it can be transformed into dominance

                exchange A(i,：） and A(record(j,3),：）;

                exchange record(j,：） and record(i,：）;              

                break;

            end

        end

    end

    Display A;

end

具体实现代码如下：

% Project 1* N. F3 G+ L: \
% SMIE   name:ChenYu   class:1202   nunmber:12353032
, {  ]3 c8 D1 a: }' i4 |) n% Change nondorminant to dorminant matrix
; g* M6 M8 }0 P+ A( H( ]( ?* H' E9 i% this method is adapted for the matrix which can be changed to dorminant
$ U3 O; v9 U! k0 g. `1 _2 [% matrix only using row exchangement
1 M; U1 v. B6 \* C* L: B0 H# d% Input :A matrix
0 ]* _5 c) ^7 i) x, b6 [* \% Output:A matrix which maybe dorminant
1 E9 Q6 x8 `: [1 a8 Wfunction method1(A); m- g4 @3 G& a1 D7 D! u8 D
[row,volumn] = size(A);
4 p' a# o1 E% A/ Trecord = ones(volumn,3);                 %use this matrix to record everyline situation
6 h/ @+ Z4 {; Y* p- Zflag   = 1;                              %first volumn record if the matrix can change to5 d( j! @3 N. ]* E( w! Q+ Q
for i = 1:row                            %dominance,which row the row will

                                         �long.Second volumn record/ V0 Z5 p, z, O. W4 a
    every_line                = A(i,：）;  %whether the matrix satisfy the necessity

                                         %that everydominance
6 M6 j* @: Z) n8 q4 I    record(i,3)               = i;       %third volumn record the rowth& ?0 _" j* L  S8 {$ c9 m. ^, f
    [record(i,1),record(i,2)] = which_row(every_line);4 r4 k) b6 g) h# R# U
    if  record(i,2)           == 08 K( T8 X0 h! g
        disp('This Matrix cannot change to dorminant matrix by row exchange.');8 a# b- v* h7 G0 Q3 g
        flag                  = 0;4 a5 |; @4 X: z. m/ F: g
        break;
* {; K4 ]4 A/ x' b$ \0 S9 }    end& U; r- `; h" x; s1 S
end
' l) H5 z9 @+ L2 N: a9 n6 cif flag == 1; f* f4 e* a. _" P/ U
    for i = 1:row-14 \# ?. y; ~0 k  B2 p; v$ Q! \9 y' o
        for j = 1:row# A; t" d$ C; y) R  H
            if record(j,1) == i         %exchange line if flag = 1,which means it can be transformed4 a) [8 e; l% U# \
                b                = A(i,：）;             %into dorminance- A+ D* ~! L5 V, t% |  S& }  N8 H
                A(i,：）           = A(record(j,3),：）;
2 J/ Q; p2 m( p5 e6 ?4 y7 I+ t                A(record(j,3),：） = b;
/ i, C$ |* ~5 w6 A                temp             = record(j,：）;# z8 e. {/ P- w
                record(j,：）      = record(i,：）;
0 W: k0 {1 w- V8 ?8 N' ~! `  |                record(i,：）      = temp;6 w3 x! ?% G/ i+ B- i/ M+ Q
                break;2 ~& ~7 L0 ?) w5 v; e) E
            end
2 M( {3 \3 D8 U2 O- v6 \- P        end$ D+ x3 K! l9 A0 l0 Q/ d( s8 M
    end
0 g7 C# g; @3 s3 b- r" i    disp(A);: T8 u" j' N/ Q, i" C6 s
end

调用函数：

% function judge_row:) f5 y3 d6 W& G9 |7 ~
% this function is to judge whether the line is a line of dorminance and
' ?- h+ \# |: U: I1 {: V& U% return which row shuold this line stand
  A  F* @9 \& n+ J- h# T5 T% Input : vector(a row of the matrix)
8 P/ E# |( ~5 U* L" X; I$ a" D% Output:if(the line is dorminant) return flag = 1;
. u+ U( y: c+ a2 D7 @%                             else return flag = 0.( S# X' c) g* |( T% h8 h/ M
function [row,flag] = which_row(a)! }, R& I0 \: |$ j8 ~
n = length(a);9 z4 c& i: [$ k
max  = a(1);  h; Y5 s& K; J
flag = 0;
, ~& k8 A- {$ J  J# ?( a/ yrow  = 1;# g* Y1 t3 G7 B* d' r
for i = 2:n- r4 p5 n; J$ p1 C  ~+ T
    if max < a(i)          %fing the max value of the line" H" h  N5 a) V& F7 `& q2 n
       max = a(i);         %it's easy for us to know that if the max value is
4 v1 p6 o' v* Y: I5 y       row = i;            %larger than the rest of all sum, m6 v3 i5 L% o' B
    end                    %than the line is dorminance
0 B' M3 j0 ]7 \) Nend
8 W) H) K) a! `! R0 y3 ]and = 0;
+ T8 X( L) H# ]8 H( yfor i = 1:n2 N# s- I( m! S- z" h2 ?7 J
   if i ~= row             %compare maxvalue and rest sum; s4 D0 W9 w, C
        and = and + a(i);1 s0 V, ^* {- v" G7 J2 N, g- s
    end
/ F6 I6 s- }4 v  X2 Yend1 A8 D6 Z6 p% X) Q9 B- ^
if a(row) >= and. u1 ~) P7 E% [$ P% B4 [
    flag = 1;
. Y; M4 K9 u1 E9 J8 a7 [end