132 133

132 Programowanie liniowe całkowitoliczbowe

Interpretacja rozwiązania

Maksymalna wielkość sprzedaży to 8000 sztuk. Zostanie ona osiągnięta, jeśli zostaną wznowione skrypty Matematyka, Statystyka opisowa, Rachunkowość II. Alternatywny optymalny plan wydawniczy to wydanie Matematyki oraz Angielskiego.

2.4.3. Zagadnnienie lokalizacji

Przykład 2.7

Rada Miejska rozważa możliwość relokalizacji komisariatów policji w mieście tak, aby zwiększyć liczbę policjantów w rejonach o wyższej przestępczości. Proponowane lokalizacje oraz odpowiednie rejony, które każdy komisariat będzie miał pod swoją opieką, podano w tablicy 2.9.

Tablica 2.9

Proponowana lokalizacja	Rejony
A	1. 5, 7
B	1, 2, 5, 7
C	1, 3, 5
D	2. 4, 5
E	3, 4, 6
F	4. 5, 6
G	1. 5. 6, 7

Należy znaleźć najmniejszą liczbę zrelokalizowanych komisariatów pokrywających swoim zasięgiem wszystkie rejony.

Rozwiązanie

Cci

Celem jest określenie najmniejszej liczby relokalizacji komisariatów, ale takiej, aby każdy rejon był pod opieką przynajmniej jednego komisariatu.

Zmienne decyzyjne

Przyjmujemy 7 zmiennych binarnych (zero-jedynkowych) określających, czy w danym miejscu ma się znajdować komisariat, czy nie (0 oznacza, że nie, natomiast 1, że tak). Opis zmiennych znajduje się w tablicy 2.10.

Tablica 2.10

Zmienna	Opis zmiennej — lokalizacja komisariatu w miejscu	Wartość zmiennej
X|	A	(0, 1}
*2	B	(0, 1}
X3	C	(0, 1)
Xą	D	(0. 1}
Xs	E	<0. 1}
Xt	F	<0. I)
X,	G	{0, 1}

Funkcja celu x, + x2+x₃+x₄+x₅+x₆ + x₇ —» min

Warunki ograniczające:

•    rejon l:

x, +x₂+x_i+x₁ > 1,

•    rejon 2: x₂+x₄ > 1,

•    rejon 3: x₃+x₅ > 1,

•    rejon 4:

x₄ + x₅ + X_ń > 1,

•    rejon 5:

X, + X₂ + X₃+X₄+X₆+X₇ > 1,

•    rejon 6:

-*5 + X_ń + *7 > 1.

•    rejon 7:

x, + x₂+x₇ ^ 1.

Dodatkowe ograniczenia nałożone na zmienne decyzyjne: *i. x₂, x₃, x₄. x₅, x₆, x₇ e {0, 1}.