next up previous contents index
Next: Wielo�ciany i p�przestrzenie Up: Interpretacje i zastosowania Previous: Uk�ady nier�wno�ci i r�wna�   Spis rzeczy   Indeks


Metoda Fouriera-Motzkina
redukcji uk�ad�w nier�wno�ci

Niech b�dzie dany uk�ad nier�wno�ci
(7.8) \begin{displaymath} \sum_{j=1}^n a_{ij}x_j \leq b_i \ \ \ i=1,...,m \end{displaymath}

Metoda Fouriera-Motzkina polega na stopniowej redukcji zmiennych tak, by w ko�cu otrzyma� jedn� zmienn� niezale�n�, a wi�c uk�ad trywialny. Powiedzmy od razu, �e to zmniejszanie liczby zmiennych b�dzie sie odbywa�o kosztem bardzo szybkiego wzrostu liczby nier�wno.sci.
bez straty og�lno�ci mo�na przyj��, �e w uk�adzie ([*])
-
pierwszych $m_1$ zmiennych ma przy $x_1$ wsp�czynnik dodatni,
-
nast�pne $m_2$ nier�wno�ci maj� przy $x_1$ wsp�czynnik ujemny, za�
-
w pozosta�ych $m-(m_1+m_2)$ nier�wno�ciach wsp�czynnik przy $x_1$ jest r�wny zero.
Dziel�c ka�d� z $m_1+m_2$ nier�wno�ci przez $\mid a_{i1}\mid \ (i=1,...,m_1+m_2)$ otrzymamy z ([*]) r�wnowa�ny mu uk�ad postaci
(7.9) \begin{displaymath} \left\{ \begin{array}{rrcrl} x_1 + & \sum_{j=2}^na_{ij}'... ...}'x_j & \leq & b_i' & i=m_1+m_2+1,...,m \end{array} \right. \end{displaymath}

czyli
(7.10) \begin{displaymath} \left\{ \begin{array}{rrcrl} x_1 + & \sum_{j=2}^na_{ij}'... ...'x_j & \leq & b_i'' & i=m_1+m_2+1,...,m \end{array} \right. \end{displaymath}

gdzie $a_{ij}''=a_{ij}'$ i $b_i''=b_i'$ dla $i=1,...,m_1$ i $i=m_1+m_2+1,...,m$ oraz $a_{ij}''=-a_{ij}'$ i $b_i''=-b_i'$ dla $i=m_1+1,...,m_1+m_2$.
Uk�ad ([*]) jest z kolei r�wnowa�ny
(7.11) \begin{displaymath} \left\{ \begin{array}{cl} b_{i_{1}}'' - \sum_{j=2}^na_{i... ...x_j \leq b_j'' , \ \ i=m_1+m_2+1,...,m \end{array} \right. \end{displaymath}

Zredukowane zadanie b�dzie nast�puj�cym uk�adem nier�wno�ci:
(7.12) \begin{displaymath} \left\{ \begin{array}{rcll} \sum_{j=2}^na_{i_{2}j}'' - a... ...j}''x_j & \leq & b_i'' & i=m_1+m_2+1,...,m \end{array}\right.\end{displaymath}

Sprzeczno�� uk�adu ([*]) oznacza sprzeczno�� uk�adu ([*]). Natomiast je�li uk�ad ([*]) jest niesprzeczny to ta�de rozwi�zanie $x_2,...,x_n$ mo�na rozszerzy� do rozwi�zania $x_1,x_2,...,x_n$ do��czaj�c dowolne $x_1$ spe�niaj�ce ([*]).
Zobaczymy jak opisana metoda funkcjonuje na przyk�adzie.

Przyk�ad 7.6   Niech b�dzie danu uk�ad r�wna�

\begin{displaymath} \left\{ \begin{array}{rrrrr} 2x_1+ & 4x_2 - & 6x_3 & \leq... ...& \leq & 3\\ & 3x_2- & 4x_3 & \leq & 12 \end{array} \right.\end{displaymath}

Zastosujmy do tego uk�adu kolejne etapy metody Fouriera-Motzkina. Po pierwsze, doprowadzamy do sytuacji w kt�rej wsp�czynniki przy $x_1$ s� r�wne $1$, $-1$ lub $0$

\begin{displaymath} \left\{ \begin{array}{rrrrr} x_1+ & 2x_2 - & 3x_3 & \leq ... ...& \leq & 3\\ & 3x_2- & 4x_3 & \leq & 12 \end{array} \right.\end{displaymath}

St�d
(7.13) \begin{displaymath} \left\{\begin{array}{c} 3-x_2-x_3 \leq x_1 \leq 4 - 2x_2 ... ... 5 + 2x_2 - x_3 \\ 3x_2 - 4x_3 \leq 12 \end{array} \right. \end{displaymath}

i zredukowany uk�ad nier�wno�ci

\begin{displaymath}\left\{\begin{array}{c} 3-x_2-x_3 \leq 4-2x_2+3x_3\\ 3 - x_2-x_3 \leq 5+2x_2-x_3\\ 3x_2-4x_3\leq 12 \end{array}\right.\end{displaymath}

kt�ry po zredukowaniu przyjmie posta�

\begin{displaymath}\left\{\begin{array}{c} x_2-4x_3\leq 1\\ -3x_2 = \leq 2\\ ... ...{4}{3}x_3 \leq 4\\ -x_2 \leq \frac{4}{3} \end{array}\right. \end{displaymath}

Teraz redukujemy zmienn� $x_2$:
(7.14) \begin{displaymath} \left\{\begin{array}{c} -\frac{2}{3} \leq x_2 \leq 1+4x_3... ...frac{2}{3} \leq x_2 \leq 4 + \frac{4}{3}x_3 \end{array}\right.\end{displaymath}


\begin{displaymath}\left\{\begin{array}{c} -4x_3 \leq \frac{5}{3}\\ -\frac{4}{3} x_3 \leq \frac{14}{3} \end{array}\right.\end{displaymath}

i ostatecznie $x_3 \geq -\frac{5}{12}$. Ten wynik za� oznacza, �e dla ka�dego $x_3 \geq -\frac{5}{12}$ mo�emy dzieki ([*]) i ([*]) znale�� odpowiednie warto�ci $x_2$ i $x_3$.

Zauwa�my, �e przy uk�adzie co najwy�ej trzech nier�wno�ci liczba nier�wno�ci przy kolejnych redukcjach nie zwi�ksza si� (tak w�a�nie by�o w naszym przyk�adzie). Rozwi�zuj�c samodzielnie nast�pne �wiczenia czytelnik zauwa�y, �e liczba nier�wno�ci na og� ro�nie bardzo szybko w miar� kolejnych redukcji. Wi�cej o redukcji uk�ad�w nier�wno�ci w [19].
Metoda eliminacji Fouriera-Motzkina daje nam inny algorytm rozwi�zywania PPL. Rzeczywi�cie, niech b�dzie dany PPL
(7.15) \begin{displaymath} \left\{\begin{array}{l} {\bf Ax} \leq {\bf b}\\ \hline\\ {\bf cx} \rightarrow \max \end{array} \right. \end{displaymath}

W celu znalezienia rozwi�zania optymalnego dla ([*]) zastosujmy metod� redukcji do uk�adu
(7.16) \begin{displaymath} \left\{\begin{array}{l} {\bf Ax} \leq {\bf b}\\ \lambda -{\bf cx} \leq 0 \end{array} \right. \end{displaymath}

gdzie $\lambda$ jest now� zmienn�. Redukowa� b�dziemy kolejne wsp�rz�dne wektora ${\bf x}$ tak, �e w ko�cu pozostanie nam tylko zmienna $\lambda$. Teraz wystarczy przyj�� $\lambda$ najwi�ksz� mo�liw�, by otrzyma� rozwi�zanie optymalne problemu ([*]).
Zauwa�my na koniec, �e metod� Fouriera-Motzkina mo�na stosowa� tak�e do redukowania uk�ad�w w kt�rych wyst�puj� tak�e silne nier�wno�ci.
next up previous contents index
Next: Wielo�ciany i p�przestrzenie Up: Interpretacje i zastosowania Previous: Uk�ady nier�wno�ci i r�wna�   Spis rzeczy   Indeks