Programowanie liniowe
w liczbach całkowitych

Bardzo często w zadaniach praktycznych jest tak, że jedynymi interesującymi rozwiązaniami problemów programowania matematycznego w ogólności, a liniowego w szczególności, są rozwiązania całkowite.
Dla przykładu, jeśli $x_i$ są zmiennymi decyzyjnymi, a więc mogącymi przyjmowaćtości $0$ lub $1$, to najczęściej rozwiązania niecałkowite nie mają żadnej sensownej interpretacji.

Przykład 5.2   W pewnym przedsiębiorstwie $n$ osób ma wykonywać $n$ czynności, przy czym:

-

każda osoba ma wykonywać jedną (i tylko jedną) czynność,

-

koszt przystosowania $i-$tej osoby do wykonywania $j-$ej czynności wynosi $d_{ij}$.

Zadanie polega na przyporządkowaniu każdej z osób zadania w taki sposób, by suma kosztów była możliwie najmniejsza.
Połóżmy

$$% latex2html id marker 5170 x_{ij} = \left\{ \begin{array}... ...}\\ 0 & \mbox{ w przeciwnym przypadku.} \end{array} \right.$$

Problem programowania liniowego jaki otrzymamy dla tego zadania jest następujący.
Problem przydziału:

$$\begin{array}{rcll} \sum_{i=1}^n x_{ij} & = & 1 & (j=1,...... ...}^n\sum_{j=1}^n d_{ij}x_{ij} & \rightarrow & \min \end{array}$$

Okazuje się, że zadanie programowania liniowego w liczbach całkowitych jest problemem trudnym, któremu jest poświęcona bardzo obszerna literatura. Zainteresowanego czytelnika odsyłam do rozdziału osiemnastego [19], w którym poza wielu innymi rezultatami znajdzie twierdzenie mówiące, że jeśli współczynniki macierzy ${\bf A}$ i wektora ${\bf b}$ są wymierne, to problem

$$\begin{array}{rcl} {\bf Ax} & \leq & {\bf b}\\ {\bf x} & -... ...owitych}\\ \hline {\bf cx} & \rightarrow & \max \end{array}$$

jest $\cal{NP}-$zupełny. Ogólna postać programowania liniowego w liczbach całkowitych jest następująca:

$$\left\{ \begin{array}{rcl} {\bf Ax} & \leq & {\bf b}\\ ... ...\ \hline {\bf cx} & \rightarrow & \max \end{array} \right.$$ (5.14)

Przykład 5.3   Rozważmy PPL

$$\left\{ \begin{array}{rcr} -3x_1+4x_2 & \leq & 6\\ 4x_... ...\hline 3x_1 + 2x_2 & \rightarrow & \max \end{array} \right.$$ (5.15)

Na rysunku 5.3.1 przedstawiono interpretację geometryczną zadania ().

Łatwo zauważyć, że rozwiązaniem optymalnym problemu ) jest $x_1=3, x_2=1$, a więc punkt znajdujący sie wewnątrz zbioru rozwiązań dopuszczalnych problemu powstałego z () przez usunięcie założeń o całkowitości zmiennych. Taki punkt jest oczywiście nie do wykrycia przez algorylm sympleks.$\Box$

W dalszym ciągu zajmiemy się sytuacją w której problem programowania liniowego w liczbach całkowitych ma rozwiązanie które można otrzymać stosując metodę sympleks. W rozdziale okaże się, że z takimi właśnie sytuacjami mamy do czynienia częściej niż mogłoby się, na pierwszy rzut oka, wydawać.

Definicja 5.2   Mówimy, że macierz $A$ jest totalnie unimodularna, jeżeli dla każdej podmacierzy kwadratowej $A'$ macierzy $A$ zachodzi
$\det (A') \in \{ 0,1,-1\}$.

Przykład 5.4   Z łatwością można sprawdzić, że macierz

$$A = \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array}\right]$$

jest totalnie unimodularna.

Z definicji macierzy unimodularnych wynika natychmiast, że jej współrzędne są równe $0, \ 1$ lub $-1$.
Udowodnimy następujące twierdzenie.

Twierdzenie 5.2   Niech będzie dany PPL

$$\left\{ \begin{array}{rcl} {\bf Ax} & = & {\bf b}\\ \hline {\bf cx} & \rightarrow & \max \end{array}\right.$$ (5.16)

gdzie $A\in Z^{m\times n}$ jest macierzą rzędu $m$ i ${\bf b} \in {\bf Z}^m$. Jeśli dla każdej macierzy bazowej ${\bf A}_B$ zachodzi $\det ({\bf A})_B \in \{ 1, -1\}$, to

1. ${\bf A}_B^{-1} \in {\bf Z}^{m \times m}$,
2. każde rozwiązanie bazowe $\bar{\bf x}_B$ jest całkowite.

Dowód. W podrozdziale widzieliśmy, że ograniczenia w problemie () można zapisać w postaci

$${\bf x}_B = {\bf A}_B^{-1}({\bf b} - {\bf A}_N{\bf x}_N),$$ (5.17)

gdzie ${\bf A}_B$ i ${\bf A}_N$ są pewnymi podmacierzami macierzy ${\bf A}$, zaś ${\bf A}_B$ jest nieosobliwą macierzą kwadratową rzędu $m$. Jeśli oznaczymy wyrazy macierzy ${\bf A}_B^{-1}$ przez $d_{ij}, \ i,j=1,...,m$, to

$$d_{ij}=\frac{(-1)^{i+j}\det (({\bf A}_B)_{ij})}{\det({\bf A}_B)}$$

gdzie $({\bf A}_B)_{ij}$ jest macierzą powstałą z ${\bf A}$ przez skreślenie $j-$tego wiersza i $i-$tej kolumny. Jest więc zupełnie oczywiste, że $d_{ij} \in {\bf Z}$ dla wszystkich $i,j=1,...,m$. W rozwiązaniu bazowym $\bar{\bf x}$ mamy $\bar{\bf x}_N={\bf0}$ i $\bar{\bf x}_B={\bf A}_B^{-1}{\bf b}$ (por. ()). Ponieważ ${\bf b}$ jest z założenia wektorem o współczynnikach całkowitych, także wektor $\bar{\bf x}_B$ ma współczynniki całkowite. Twierdzenie pociąga natychmiast podany niżej ważny wniosek który ostatecznie wyjaśnia rolę macierzy totalnie unimodularnych w całkowitoliczbowym programowaniu liniowym.

Wniosek 5.3   Niech będzie dany PPL

$$\left\{ \begin{array}{rcl} {\bf Ax} & = & {\bf b}\\ \hline {\bf cx} & \rightarrow & \max \end{array}\right.$$ (5.18)

gdzie $A$ jest pewną macierzą totalnie unimodularną, zaś ${\bf b}$ wektorem o współczynnikach całkowitych.

1. Jeżeli () jest niesprzeczny, to jego rozwiązania bazowe mają wszystkie współrzędne całkowite.
2. Jeżeli istnieje rozwiązania optymalne problemu (), to istnieją takie rozwiązania optymalne których wszystkie współrzędne są całkowite.
3. Jeśli problem () jest niesprzeczny i ograniczony to algorytm sympleks znajduje takie rozwiązanie () którego wszystkie współrzędne są liczbami całkowitymi.

Wobec wniosku ważnym jest problem ozpoznania" macierzy totalnie unimodularnych. W rozdziale okaże się jak ważnym warunkiem wystarczającym dla tych macierzy jest poniższe twierdzenie.

Twierdzenie 5.4   Niech ${\bf A}\in {\bf R}^{m\times n}$ będzie macierzą spełniającą następujące warunki:

1. każdy wyraz macierzy ${\bf A}$ jest równy $1,-1$ lub $0$,
2. każda kolumna macierzy ${\bf A}$ zawiera co najwyżej dwa wyrazy niezerowe,
3. istnieje taki podział zbioru wierszy na dwa podzbiory $W_1$ i $W_2$ takie, że:

   a)

   jeśli istnieją dwa wyrazy tego samego znaku występujące w jednej kolumnie, to jeden z nich jest w wierszu zbioru $W_1$ a drugi w wierszu zbioru $W_2$,

   b)

   jeśli w pewnej kolumnie występują dwa wyrazy niezerowe przeciwnych znaków, to oba wiersze w których występują należą albo do zbioru $W_1$ albo do zbioru $W_2$.

Wtedy ${\bf A}$ jest macierzą unimodularną.

Przykład 5.5   Macierz

$${\bf B} = \left[ \begin{array}{cccccc} 1&0&-1&-1&0&0\\ 0&1... ... \end{array}\right]\begin{array}{c}W_1\\ W_1\\ W_1\end{array},$$

(podobnie jak macierz z przykładu ) spełnia założenia twierdzenia , w więc jest macierzą totalnie unimodularną.

Dowód twierdzenia . Wystarczy wykazać, że dla każdej macierzy
${\bf A}$ o $n$ wierszach i $n$ kolumnach spełniającej założenia twierdzenia $\det ({\bf A}) \in \{ 0, 1, -1 \}$. Dowód przeprowadzimy przez indukcję ze względu na $n$.
Dla $n=1$ przwdziwość twierdzenia jest oczywista. Przypuśćmy, więc, że $n>1$ i twierdzenie jest prawdziwe dla macierzy o $n-1$ wierszach i $n-1$ kolumnach. Rozpatrzymy trzy przypadki:

Przypadek 1.

Jedna z kolumn macierzy ${\bf A}$ ma wszystkie wyrazy równe $0$. Wtedy oczywiście $\det ({\bf A})=0$.

Przypadek 2.

W jednej z kolumn jest jeden wyraz różny od zera, powiedzmy że tym wyrazem jest $a_{i_0,j_0}$. Wtedy $a_{i_0,j_0} \in \{-1,1\}$. Rozwijamy wyznacznik macierzy${\bf A}$ względem kolumny $j_0$ i otrzymujemy

$$\det ({\bf A}) = (-1)^{i+j}a_{i_0,j_0}\det ({\bf A}_{i_0j_0}),$$ (5.19)

gdzie ${\bf A}_{i_0j_0}$ jest macierzą powstałą przez skreślenie w ${\bf A}$ wiersza $i_0$
i kolumny $j_0$. Zauważmy, że macierz ${\bf A}_{i_0j_0}$ jest macierzą kwadratową o $n-1$ wierszach i kolumnach spełniającą warunki twierdzenia i wobec tego $\det ({\bf A}_{i_0j_0}) \in \{ 0,1,-1\}$. Stąd i () otrzymujemy $\det ({\bf A}) \in \{ 0, 1, -1 \}$.

Przypadek 3.

Nie zachodzą przypadki 1 ani 2. Wtedy

$$\sum_{i \in W_1} a_{ij} = \sum_{i \in W_2} a_{ij}$$ (5.20)

dla każdego $j=1,...,m$. Udowodnienie, że w tym przypadku
$\det ({\bf A})=0$ jest bardzo prostym ćwiczeniem, które pozostawiam czytelnikowi (p. ćwiczenie ).