Začíname s YALMIPom: 06. Logická optimalizácia

Dnes si ukážeme, ako použiť YALMIP na riešenie problémov s binárnymi premennými.

Uvažujme nasledovný problém: ste hlavným architektom mesta, ktoré má 6 mestských častí (označíme ich písmenami A až F). Za úlohu máte postaviť minimálny počet požiarnych staníc (v každej časti môže byť max. jedna) tak, aby bola každá časť pokrytá požiarnikmi do 15 minút. Cestovné časy medzi jednotlivými mestskými časťami sú nasledovné:

Zadefinujme optimalizované premenné A, B, C, D, E, a F, ktoré budú mať hodnotu 1 ak v príslušnej časti postavíme stanicu a 0 v opačnom prípade. Keďže premenné nadobúdajú iba binárne hodnoty, na ich vytvorenie použijeme príkaz binvar:

binvar A B C D E F

Cieľom je minimalizovať počet postavených staníc, čo sa dá napísať v tvare

ucelovka = A + B + C + D + E + F;

Formulácia ohraničení si vyžaduje trochu uvažovania. Vezmime si prvý riadok tabuľky. Časť A bude pokrytá do 15 minút ak postavíme stanicu buď v časti A alebo v časti B (pre všetky ostatné umiestnenia je čas dojazdu vyšší ako požadovaných 15 minút). To môžeme zapísať v tvare

ohranicenia = [ true(A | B) ];

pričom A | B bude pravdivé vtedy a len vtedy, keď A alebo B (prípadne oboje zároveň) budú jednotkové. Ohraničenie používa príkaz true, ktorý vyžaduje, aby v ňom uvedený výrok (teda A | B) bol pravdivý.

Pokrytie druhej časti (riadok B tabuľky) bude zabezpečené, ak stanica bude buď v A (dojazd 10 minút), alebo v B (dojazd 0 minút), alebo v F (dojazd 10 minút):

ohranicenia = ohranicenia + [ true(A | B | F) ];

Aplikovaním rovnakého postupu na mestské časti C, D, E a F dostávame

ohranicenia = ohranicenia + [ true(C | D) ];     % cast Cohranicenia = ohranicenia + [ true(C | D | E) ]; % cast Dohranicenia = ohranicenia + [ true(D | E | F) ]; % cast Eohranicenia = ohranicenia + [ true(B | E | F) ]; % cast F

S takto definovanými ohraničeniami a účelovou funkciou môžeme problém vyriešíť pomocou príkazu optimize:

info = optimize(ohranicenia, ucelovka)yalmiptime: 0.3347solvertime: 0.0040      info: 'Successfully solved (GUROBI-GUROBI)'   problem: 0

Optimálne hodnoty rozhodovacích premenných získame cez value:

value([A B C D E F])ans = 0     1     0     1     0     0

Ako vidíme, minimálny počet požiarnych staníc je 2 a majú byť postavené v mestských častiach B a D.

Hore uvedený postup však platí iba pre jednu konkrétnu maticu dojazdov. Uvažujme teraz všeobecný scenár, kde máme n mestských častí, pričom dojazdy medzi nimi sú v matici M. Minimálny čas dojazdu označíme ako tmin. Všeobecná formulácia bude nasledovná:

n = size(M, 1);    % pocet castix = binvar(1, n);  % optimalizovane premenneucelovka = sum(x); % minimalizuj pocet stanicohranicenia = [];for i = 1:n  % pre kazdu cast najdi kandidatov v dosahu  kandidati = find(M(i, :) <= tmin);  % pozadujeme, aby bola stanica aspon v jednej z kandidatskych casti  ohranicenia = ohranicenia + [ true(or(x(kandidati))) ];endinfo = optimize(ohranicenia, ucelovka)value(x)

Zdroj: http://www.doc.ic.ac.uk/~br/berc/integerprog.pdf