内点法.m

该程序使用matlab开发的规划中的经典算法——基于对偶仿射理论的内点法

    
clc

X=[];
q=[1 1 1 1 1 1 1 1 1 1];
Q=diag(q);
A=[ 1 1 0 0 0 0 0 0 0 0
    0 0 1 1 0 0 0 0 0 0
    0 0 0 0 -1 0 0 -1 0 0
    0 0 0 0 0 -1 0 0 -1 0
    0 0 0 0 0 0 -1 0 0 -1
    -1 0 -1 0 1 1 1 0 0 0
    0 -1 0 -1 0 0 0 1 1 1
    ;-Q];
b=[20;6;-5;-10;-5;0;0;0;0;0;0;0;0;0;0;0;0];
c=[-0 -5 -4 -2 -3 -4 -5 -2 -1 -2];
c=c';

x0=[12;7;1.5;4;4;5;4;2;6;2];
r=0.5;
E=0.000001;
k=0;
xk=x0;
bool=0;

while bool==0
vk=b-A*xk;
[Svk,o]=size(vk);
    for i=1:1:Svk
        vk(i,1)=1/vk(i,1);      
    end
Dk=diag(vk);
dx=((A'*(Dk^2)*A)^(-1))*c;
dv=-A*dx;[Svk,o]=size(vk);
[Sdv,o]=size(dv);
temp=[];
    for i=1:1:Sdv
        if dv(i,1)<0
        temp1=-vk(i,1)/dv(i,1);
        temp=[temp temp1];
        end
    end

if temp==[];
    bool=1;
else    
    lmd=r.*min(temp);
    xk1=xk+lmd*dx;
    numerator=abs(c'*xk1-c'*xk);
    denominator=abs(c'*xk);
    if (numerator/denominator)<E
        bool=1;
    else
         X=[X  xk];
         solution=xk;
         xk=xk1;
    end
end
end


format long,X
format long,solution
c'*solution





运算结果：
>> 
X =

  Columns 1 through 3 

  12.00000000000000  12.06535104177430  12.13127252921698
   7.00000000000000   6.92857142857143   6.85640648011782
   1.50000000000000   1.47880553779017   1.45768202863563
   4.00000000000000   4.02034308295536   4.04061116956857
   4.00000000000000   4.01629151337127   4.03269977553992
   5.00000000000000   5.02388491283960   5.04825102498834
   4.00000000000000   4.00257422760978   4.00516093102119
   2.00000000000000   1.98291278874973   1.96568859308530
   6.00000000000000   5.97358181859732   5.94662498502070
   2.00000000000000   1.99388661735892   1.98768718448294

  Columns 4 through 6 

  12.19777929953091  12.26488683327655  12.33261129100085
   6.78348198221212   6.70977352373738   6.63525536031039
   1.43662885600468   1.41564513436219   1.39472969543946
   4.06080459432238   4.08092394894721   4.10097009549506
   4.04922590233818   4.06587104674235   4.08263640671288
   5.07311109563192   5.09847824286877   5.12436596054905
   4.00775912935212   4.01036773684579   4.01298555360259
   1.94832460302791   1.93081782615829   1.91316506478127
   5.91911412936158   5.89103334477651   5.86236615339328
   1.98139938261822   1.97502078901232   1.96854886725300

  Columns 7 through 9 

  12.40096955231524  12.46997925758572  12.53965885240247
   6.55990031022583   6.48367963973476   6.40656293629127
   1.37388107331762   1.35309748813879   1.33237682822898
   4.12094418056432   4.14084765086319   4.16068227032970
   4.09952323353726   4.11653284067366   4.13366661308792
   5.15078813622165   5.17775907024366   5.20529349610188
   4.01561125512582   4.01824338049428   4.02088031894074
   1.89536289070978   1.87740761738613   1.85929526901398
   5.83309546904025   5.80320355645016   5.77267198654473
   1.96198095663169   1.95531426042181   1.94854583294738

  Columns 10 through 12 

  12.61002763499750  12.68110580677623  12.75291452612021
   6.32851796819026   6.24951052876870   6.16950426304624
   1.31171663038216   1.29111405801304   1.27056587683659
   4.18045013906349   4.20015371436774   4.21979583425266
   4.15092601706922   4.16831261050103   4.18582805355180
   5.23340660198840   5.26211405366032   5.29143201859592
   4.02352029457561   4.02616134894628   4.02880132106417
   1.84102154632076   1.82258178850622   1.80397093085657
   5.74148158735511   5.70961239007429   5.67704356966978
   1.94167256529965   1.93469116953928   1.92759816119744

  Columns 13 through 15 

  12.82547596560187  12.89881337272414  12.97295113425463
   6.08846047432648   6.00633790785694   5.92309250813577
   1.25006842767263   1.22961759590243   1.20920877701692
   4.23937974381465   4.25890912498252   4.27838813021499
   4.20347411973490   4.22125270726690   4.23916585062744
   5.32137719143474   5.35196682065362   5.38321873638177
   4.03143782445984   4.03406822073877   4.03668958900335
   1.78518345741063   1.76621334795314   1.74705401847429
   5.64375337940685   5.60971907854235   5.57491685234510
   1.92038983986165   1.91306226759889   1.90561124493010

  Columns 16 through 18 

  13.04791484415919  13.12373137504578  13.20042895289511
   5.83867714583758   5.75304130958373   5.66613075687015
   1.18883683759075   1.16849607088659   1.14818014613448
   4.29782142084895   4.31721421093828   4.33657231759870
   4.25721573218987   4.27540469374729   4.29373524769983
   5.41515137919117   5.44778382960652   5.48113583795470
   4.03929869037330   4.04189192667252   4.04446529214405
   1.72769825406856   1.70813813304269   1.68836494075117
   5.53932172347829   5.50290745363968   5.46564643419344
   1.89803228402404   1.89032057872426   1.88247097095791

  Columns 19 through 21 

  13.27803723466478  13.35658738808793  13.43611217261641
   5.57788711734705   5.48824744026484   5.39714367618676
   1.12788205033378   1.10759402117834   1.08730746939668
   4.35590221909183   4.37521112215591   4.39450704043657
   4.31221008759274   4.33083209759281   4.34960436035692
   5.51522785400411   5.55008105561440   5.58571737530473
   4.04701431679750   4.04953399966686   4.05201872984309
   1.66836907136627   1.64813991540062   1.62766573031154
   5.42750956434002   5.38846611515273   5.34848357755791
   1.87447791299768   1.86633542495530   1.85803704677296

  Columns 22 through 24 

  13.51664601994222  13.59822511181253  13.68088745185272
   5.30450208092850   5.21024252699267   5.11427770435540
   1.06701288840823   1.04669974869940   1.02635637368545
   4.41379888631231   4.43309657897435   4.45241117235192
   4.36853016256796   4.38761299717544   4.40685656105896
   5.62215952322279   5.65943100441531   5.69755612750279
   4.05446219261637   4.05685725738081   4.05919584306932
   1.60693349089841   1.58592871541647   1.56463526231888
   5.30752749204493   5.26556125755802   5.22254591664024
   1.84957578384404   1.84094404523084   1.83213357324730

  Columns 25 through 27 

  13.76467292671302  13.84962334989388  13.93578247884028
   5.01651218810778   4.91684134485033   4.81515004246090
   1.00596979299930   0.98552556807208   0.96500758345260
   4.47175500742770   4.49114189474291   4.51058733455947
   4.42626474640254   4.44584162348374   4.46559141178480
   5.73656000076062   5.77646851008232   5.81730827116882
   4.06146875572819   4.06366549131246   4.06577399474745
   1.54303509122872   1.52110798003123   1.49883118771827
   5.17843991346925   5.13319882094616   5.08677503248258
   1.82313536293215   1.81393956963962   1.80453540260947

  Columns 28 through 30 

  14.02319599197583  14.11191140674655  14.20197791167634
   4.71131111831712   4.60518354842346   4.49661024298568
   0.94439779542690   0.92367592696275   0.90281909455197
   4.53010878438599   4.54972598661551   4.56946137320203
   4.48551843523624   4.50562705588373   4.52592157814260
   5.85910654528691   5.90189110367939   5.94569001960071
   4.06778036356389   4.06966848069226   4.07141955588480
   1.47617904960841   1.45312248751103   1.42962841187415
   5.03911741359981   4.99017090795478   4.93987609203018
   1.79491100192828   1.78505329573939   1.77494783387635

  Columns 31 through 33 

  14.29344607369843  14.38636736476474  14.48079342603080
   4.38541537107524   4.27140108561032   4.15434347617991
   0.88180134776790   0.86059309571072   0.83916038509270
   4.58934057012186   4.60939303258225   4.62965285372113
   4.54640611280257   4.56708438566152   4.58795946948337
   5.99053135809650   6.03644272065372   6.08345058252689
   4.07301154811121   4.07441843122643   4.07560925082779
   1.40565898531860   1.38117070626368   1.35611325613568
   4.88816867263456   4.83497892184921   4.78023104565942
   1.76457859325484   1.75392774933247   1.74297540670577

  Columns 34 through 36 

  14.57677494910412  14.67435999432527  14.77359147315502
   4.03398751551684   3.91004067679294   3.78216476926910
   0.81746398113855   0.79545818255769   0.77308927204453
   4.65015980671907   4.67096070575345   4.69211120987885
   4.60903340893610   4.63030669476578   4.65177752329022
   6.13157933138039   6.18084987111715   6.23127758475013
   4.07654689930443   4.07718650513164   4.07747328576869
   1.33042803165043   1.30404625126111   1.27688647617761
   4.72384248616509   4.66572316468269   4.60577468733235
   1.73169928044756   1.72007431812354   1.70807225069025

  Columns 37 through 39 

  14.87450337384837  14.97711506881332  15.08142263991264
   3.64996534631889   3.51297774436693   3.37064834851415
   0.75029345819598   0.72699409335567   0.70309783700388
   4.71367825381680   4.73574338480279   4.75840744011832
   4.67344074640493   4.69528636907886   4.71729737444427
   6.28286933836393   6.33561902540968   6.38950084362357
   4.07733964155244   4.07670115438763   4.07545097087939
   1.24885131155806   1.21982293564175   1.18965691374692
   4.54388956160633   4.47995052282897   4.41383016448750
   1.69566105901646   1.68280434242482   1.66946057834390

  Columns 40 through 42