Podręcznik: Analiza modelu do implementacji

1. Klasy problemów i pakiety optymalizujące

1.4. Analiza modelu do implementacji

Rozważmy problem lokalizacji, którego opis oparty jest na materiale szkoleniowym [CPLEX Optimization Studio Fundamentals Tutorial](https://www.ibm.com/cloud/garage/dte/tutorial/cplex-optimization-studio-fundamentals-tutorial).

Opis. Firma rozważa kilka lokalizacji pod budowę magazynów, które wspomagałyby obsługę jej sklepów. Dany jest stały koszt otwarcia magazynu, a także koszt związany z zaopatrzeniem sklepu z każdej z potencjalnych lokalizacji. Warunki:

Każdy sklep może być zaopatrywany tylko przez jeden magazyn.
W każdej lokalizacji można postawić magazyn o określonej pojemności, wskazującej ile maksymalnie sklepów możne on obsłużyć.

Decyzje. Problemem jest podjęcie decyzji, ile magazynów i w których lokalizacjach otworzyć, aby jak najtaniej obsłużyć wszystkie sklepy.

Przykładową ilustrację zadania przedstawia poniższy rysunek z artykułu J. de Armas, et. al (2017) 'Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic', Journal of the Operational Research Society, 68:10, 1161-1176, DOI: 10.1057/s41274-016-0155-6

ilustracja zadania lokalizacji

Dla ustalenia uwagi, może przyjąć następujące dane dla naszego problemu.

Jest 5 potencjalnych lokalizacji magazynów - Bonn, Bordeaux, London, Paris, Rome oraz 10 sklepów.
Koszty stałe otwarcia magazynu są takie same dla wszystkich lokacji i wynoszą 30.
Poniższa tabela zawiera dopuszczalne pojemności magazynów i koszty zaopatrzenia sklepów.

	Bonn	Bordeaux	London	Paris	Rome
max. pojemność	1	4	2	1	3
sklep 1	20	24	11	25	30
sklep 2	28	27	82	83	74
sklep 3	74	97	71	96	70
sklep 4	2	55	73	69	61
sklep 5	46	96	59	83	4
sklep 6	42	22	29	67	59
sklep 7	1	5	73	59	56
sklep 8	10	73	13	43	96
sklep 9	93	35	63	85	46
sklep 10	47	65	55	71	95

Mogą być różne metody rozwiązywania przedstawionego problemu lokalizacji, który należy do jednego z klasycznych zadań optymalizacji. Jedną z metod jest sformułowanie problemu w postaci zadania programowania matematycznego i rozwiązanie przy użyciu solwera, co prezentujemy w tym rozdziale.

Formalnie, każdy model programowania matematycnego składa się z 3 części: oznaczeń, funkcji celu i ograniczeń. Zaczynamy od oznaczeń, które również składają się z 3 części: zbiorów, parametrów i zmiennych decyzyjnych. Parametry to wszelkie wartości liczbowe pojawiające się w sformułowaniu konkretnego przypadku liczbowego, tzw. case study. W naszym zadaniu najważniejsze dane zawiera przedstawiona powyżej tabela. Warto zwrócić uwagę, że wszelkie tabele pojawiające się w opisie zadania wskazują w naturalny sposób kandydatów do zbiorów: najczęściej znajdują się w pierwszej kolumnie, oraz/lub w pierwszym wierszu. W naszym przykładzie, dla danych przedstawionych w tabeli powyżej widzimy zbiór lokalizacji, oraz zbiór sklepów. W komórkach tabeli są parametry opisujące poszczególne lokalizacje oraz pary lokalizacja-sklep.

Uwaga - w modelach matematycznych najczęściej używamy jednoliterowych oznaczeń, a indeks dolny jest zarezerwowany dla wskazania elementu zbioru, do którego dane oznaczenie się odnosi.

Oznaczenia w analizowanym problemie:

Zbiory:

$w\in W$ lokalizacje dla magazynów (warehouses)
$s\in S$ sklepy (stores)

Parametry:

$FC$ stały koszt otwarcia magazynu (fixed cost)
$SC_{sw}$ koszt zaopatrzenia sklepu $s$ z magazynu $w$ (supply cost)
$C_w$ max. pojemność magazynu $w$ (capacity)

Zmienne decyzyjne:

$x_{sw}$ czy sklep $s$ zaopatrzany z magazynu $w$
$y_{w}$ czy magazyn $w$ otwarty

Funkcja celu:

Kolejny element to zdefiniowanie funkcji celu, pozwalającej na ocenę rozwiązania, czyli konkretnych wartości zmiennych decyzyjnych. W rozważanym przykładzie chcemy jak najtaniej otwierać magazyny, oraz przydzielać do nich obsługiwane sklepy, czyli w funkcji celu minimalizujemy koszty:

$min C o s t = \sum_{w} F C y_{w} + \sum_{s} \sum_{w} S C_{s w} x_{s w}$

Ograniczenia:

Ostatni element modelu, to wskazanie zależności, które muszą spełniać zmienne decyzyjne, aby rozwiązanie było dopuszczalne. W rozważanym problemie opisano dwa warunki, które przekładają się na matematyczny zapis trzech rodzajów ograniczeń:

(1) każdy sklep

$s$ jest obsłużony przez dokładnie jeden magazyn

$w$ :

$\sum_w x_{sw} = 1,\;\;\;\forall s\in S$
(2) sklep

$s$ może być zaopatrzany z magazynu

$w$ , o ile został on otwarty:

$x_{sw} \leq y_w,\;\;\;\forall s\in S, w\in W$
(3) liczba sklepów obsługiwanych przez otwarty magazyn

$w$ nie może przekroczyć jego pojemności:

$\sum_s x_{sw} \leq C_w\cdot y_w,\;\;\;\forall w\in W$ .

W dalszej części przedstawiamy implementację modelu w środowisku CPLEX Studio.