Začíname S YALMIPom: 04. Všeobecný distribučný problém

V predchádzajúcej časti sme videli ako naformulovať distribučný problém s 2 výrobcami a 2 zákazníkmi. Teraz úlohu naformulujeme pre ľubovolný počet výrobcov a zákazníkov.

Uvažujeme, že máme $n$ výrobcov, pričom $i$-tý výrobca vie vyrobiť maximálne $p_i$ produktov pre $i=1, \ldots, n$. Každý zákazník pritom požaduje celkovo $s_j$ produktov pre $j=1, \ldots, m$. Produkty sa prepravujú po cestách, pričom konštanty $c_{i,j}$ vyjadrujú jednotkovú cenu prepravy od $i$-teho výrobcu k $j$-temu zákazníkovi. Cieľom je nájsť optimalnú alokáciu dopravných ciest tak, aby boli dodržané výrobné kapacity a boli splnené požiadavky všetkých zákazníkov. Taktiež uvažujeme, že po jednotlivých cestách môžeme prepraviť iba nezáporné množstvá (nie každá cesta však musí byť využitá).

Matematicky sa dá takýto problém naformulovať nasledovne:

Optimalizovanou premennou je matica $x \in \mathbb{R}^{n \times m}$, ktorá ma $n$ riadkov (výrobcovia) a $m$ stĺpcov (zákazníci) a $x_{i,j}$ je množstvo tovarov prepravených od $i$-teho výrobcu $j$-temu zákazníkovi.
Účelová funkcia je v tvare $\min \ \sum_{i=1}^n \sum_{j=1}^m \ c_{i,j} x_{i,j}$, kde minimalizujeme celkovú cenu prepravy medzi jednotlivými výrobcami a zákazníkmi
Pre každého výrobcu chceme, aby jeho produkcia neprekročila $s_i$. Keďže produkcia je sumou vystupujúcich prúdov, dostávame ohraničenia v tvare nerovností: $\sum_{j=1}^m x_{i,j} \le p_i$ pre každé $i=1, \ldots, n$.
Každý zákazník musí dostať správne množstvo produktov, teda $\sum_{i=1}^n x_{i,j} = s_j$ pre každé $j=1, \ldots, m$.
Prepravovať môžeme iba nezáporné množstvá, teda $x_{i,j} \ge 0$ pre všetky $i=1, \ldots, n$ a $j=1, \ldots, m$.

V YALMIPe takýto problém zapíšeme veľmi jednoducho. Najskôr vytvoríme optimalizovanú premennú, ktorá je v našom prípade maticou s $n$ riadkami a $m$ stĺpcami:

x = sdpvar(n, m, 'full')

Argument 'full' musíme pridať, aby YALMIP vedel, že nejde o symetrickú maticu.

Následne vytvoríme účelovú funkciu. Najjednoduhšie (ale aj najmenej efektívne) je použiť dve vnorené FOR-slučky:

ucelovka = 0;
for i = 1:n
  for j = 1:m
    ucelovka = ucelovka + c(i, j)*x(i, j);
  end
end

Efektívnejší je maticový zápis v tvare

ucelovka = sum(diag(c*x'));

ktorý dá rovnaký výsledok (viete prečo?)

Ostáva pridať ohraničenia. Najskôr nenegativita optimalizovaných premenných:

ohranicenia = [ x(:) >= 0 ];

Tu x(:) znamená vektorizáciu matice a ohraničenie je interpretované po prvkoch. Potom pre každého výrobcu pridáme ohraničenie na jeho maximálnu produkciu:

for i = 1:n
  ohranicenia = ohranicenia + [ sum(x(i, :)) <= p(i) ];
end

A podobne ohraničenia na spotrebu zákazníkov:

for j = 1:m
  ohranicenia = ohranicenia + [ sum(x(:, j)) == s(j) ];
end

Nakoniec problém vyriešime použitím funkcie optimize:

info = optimize(ohranicenia, ucelovka)

pričom je však potrebné zadefinovať konštanty c ($n \times m$ matica cien jednotlivých prepravných trás), vektor p ($n \times 1$ vektor maximalných produkčných kapacít jednotlivých výrobcov) a s ($m \times 1$ vektor požiadaviek jednotlivých zákazníkov).

Ako príklad uvažujme $n=100$ výrobcov a $m=500$ spotrebiteľov s náhodne určenými kapacitami/požiadavkami:

n = 100; % pocet vyrobcov
m = 500; % pocet spotrebitelov
c = rand(n, m)*10;  % nahodne prepravne ceny
p = rand(n, 1)*100; % nahodne vyrobne kapacity
s = rand(m, 1)*10;  % nahodne spotreby

Napriek tomu, že riešime problém s 50000 optimalizovanými premennými, solver GLPK dokáže tento problém vyriešiť za menej ako jednu sekundu:

info = 
    yalmiptime: 0.346750807999999
    solvertime: 0.777837192000000
          info: 'Successfully solved (GLPK-GLPKMEX-CC)'
       problem: 0

← OptiBlog