... matematycznego^1.1

Warto zauważyć i zapamiętać tę definicję, szczególnie wobec faktu, że słowo programowanie występuje także w znaczeniu bardzo różnym od rozważanego w bliskiej matematyce informatyce.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... MIAGE^1.2

Methodes Informatiques en Géstion et Economie

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... kg^2.1

To po to by Ola nie musiała jeść zbyt dużo marchewki z chlebem.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... słownika^3.1

Można wykazać, że PPL w którym występuje zjawisko cykliczności musi mieć co najmniej 7 zmiennych decyzyjnych. Przykład Chvátala jest więc, w pewnym sensie najmniejszym PPL który zapętla się.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... się^3.2

Inaczej: jeśli nie występuje zjawisko cykliczności.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... elegancją^3.3

elegancja (mat.) = prostota (wulg.)

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...błędną^3.4

Tu błędna nie pochodzi od słowa błąd a raczej od błędnego rycerza lub błędnego ognika. Taka co to raz jest a raz jej nie ma - w ogóle nie wie czego chce.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... zmiennych^3.5

Sprawdź sam jeśli nie wierzysz!

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... na\-stę\-pu\-ją\-co^3.6

Wyjątkowo w tym przypadku, wygodniej nam będzie oznaczać zmienne sztuczne przez $y_i$ zamiast, jak to było zawsze do tej pory, przez $x_{n+i}$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... niewiadomymi^4.1

Pamiętamy z dowodu twierdzenia , że w najgorszym przypadku iteracji może być $\left( \begin{array}{c} m+n\\ n \end{array} \right)$ w pierwszym i $\left( \begin{array}{c} n+m\\ m \end{array} \right)$ drugim przypadku, a więc tyle samo

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... fizycznych^4.2

W tym fragmencie tekstu słowo jednostka występuje w dwóch zupełnie różnych znaczeniach.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...$W$^4.3

Pozostałe zbiory indeksów też zostały nazwane tak, by było je można łatwiej zapamiętać: $N$ od nierówność, $R$ od równość, $P$ od pozytywne (tu w znaczeniu: nieujemne).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... bazową^5.1

Macierz bazową czasami wygodnie jest oznaczać przez ${\bf A}_B$ (by podkreślić, że powstała z macierzy ${\bf A}$), a czasami przez ${\bf B}$ (bo krócej).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...)^5.2

Nigdy nie obliczamy ${\bf y}$ przez wyliczenie macierzy ${\bf B}^{-1}$ co jest wysiłkiem dużym i zupełnie zbędnym. Szczególnie wtedy, gdybyśmy chcieli w tym celu wykorzystać zupełnie nieefektywną metodę wyznacznikową.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... pusty^5.3

Na mocy definicji przyjmujemy $\sum_{i \in \emptyset}a_{ij} = 0$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ma)^6.1

Jeżeli dolne ograniczenia są skończone, to można zmienne $x_j$ zastąpić nowymi zmiennymi $y_j=x_j-d_j$ i przyjąć standardowe ograniczenia $y_j \geq 0$ (por. Gass [10]). Ograniczenia od góry na poszczególne zmienne w praktyce występują prawie zawsze. Na przykład, jeśli zmienne $x_j$ oznaczają wielkość produktów $X_j$, $j=1,...,n$, to górne ograniczenia mogą oznaczać popyt na odpowiednie produkty.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ogra\-ni\-cze\-niom^6.2

W metodzie sympleks z którą obcujemy od trzeciego rozdziału przyjmujemy wartość $0$ dla zmiennych niebazowych, a więc także wartość indywidualnego ograniczenia (dolnego, innego nie bylo) na zmienne.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... są^6.3

właściwie mogą być

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...wy\-mia\-ro\-wych ^7.1

Chvatál w swojej książce [4] tak pisze na ten temat: ... do not try to visualize $n-$dimentional objects for $n\geq 4$. Such an effort is not only doomed to failure - it may be dangerous to your mantional health. (If you do succeed, then you are in trouble).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... wymiarowych^7.2

Bardziej dobitnie i prosto: przestrzeń $4-$wymiarowa nie jest $3-$wymiarowa
(bo $3<4$).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...wypukły ^7.3

Zbiory wypukłe odgrywają ważną rolę w wielu działach matematyki, szczególnie w analizie funkcjonalnej (por. [1]) i optymalizacji (por. [11]).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... beznadziejny^8.1

Jeszcze raz podkreślmy, co znaczy to teoretycznie: sympleks jest algorytmem niewielomianowym jak wykazuje przykład Klee-Minty'ego, w praktycznych zaś przykładach spisuje się bardzo dobrze.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... nazywamy^8.2

Niekonsekwentnie...

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... łuków^8.3

Na przykład gdy będziemy myśleli o sieciach wodociągowych, kanalizacyjnych - ale także, czasami, drogowych.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... łuków^8.4

Na przykład dla sieci komunikacyjnej.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... łuków^8.5

W sieci komunikacyjnej: gdy myślimy raczej o cenie biletu niż odległości.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... łukach^8.6

W praktyce oznacza to, że woda nie płynie jak nie ma rury.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... zmiennej^8.7

Gorąco doradzam rozwiązanie ćwiczenia właśnie teraz!

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... powiększająca^8.8

Dokładniej ścieżka powiększająca (z którą zetknęliśmy się już w dowodzie twierdzenia ) to ścieżka z $s$ do $t$ - właśnie przeszliśmy po niej pod prąd.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... całkowity^8.9

Jako pierwszy przepływ można przyjąć przepływ zerowy.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... rzeczywisty^8.10

Kłopot tylko teoretyczny. Dość trudno sobie wyobrazić zadanie praktyczne w którym niezbędne byłoby uwzględnianie ograniczeń niewymiernych na przepustowość łuków.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... podział^8.11

Przypomnijmy, że zbiory $X$ i $Y$ są podziałem $V$ jeżeli $X \cup Y = V$ i $X \cap y = \emptyset$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...$x\in e$^8.12

Zwrócić tu anleży uwagę na subtelną różnicę pomiędzy pełnym skojarzeniem w grafie zwykłym i pełnym skojarzeniem $X$ w $Y$ w grafie dwudzielnym $(X,Y;E)$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... sieci^8.13

Zauważmy, że $+\infty$ w definicji przepustowości łuków sieci $S$ można zastąpić wystarczająco dużymi liczbami całkowitymi (na przykład $\mid X \mid$).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...$W=\{ s\}$^8.14

$c(\{s\},X'\cup Y'-\{ s\})=\mid X\mid < +\infty$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... senacie^8.15

Także Senacie Akademii Górniczo-Hutniczej.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... problemami^8.16

W Senacie AGH są to Komisje do Spraw Kształcenia, Naukowa, Budżetowa i inne.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... grafów^8.17

Z pewnością powodów gwałtownego rozwoju teorii grafów było z pewnością wiele (np. znany problem czterech kolorów, liczne zastosowania (w tym w informatyce)). Niewątpliwie jednak książka Königa odegrała w tym rozwoju dużą rolę.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... problemu^8.18

Zauważmy, że ograniczenia przepustowości wierzchołków mogą występować w zagadnieniach praktycznych. W sieciach komunikacyjnych często wierzchołki oznaczają skrzyżowania ulic. Jest oczywiste, że możliwość wprowadzenia ograniczeń przepustowości wierzchołków - skrzyżowań jest tu bardzo istotna.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.