Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
6
SPISTREŚCI
(rozdz.3)orazzredukowanąmetodęsympleks(rozdz.4).Wrozdziale5omó-
wionajestszczególnasytuacjazadaniaograniczonego.
Rozdział6zawierainterpretacjeizastosowaniageometryczneprogramowa-
nialiniowego.Podrozdział6.1,wktórymjestmowaointerpretacjiprogramo-
wanialiniowegowprzypadkachdwu-itrójwymiarowym,możnaprzeczytaćjuż
porozdziale2,wktórymopisanometodęsympleksową.
Rozdział7poświęconyjestprzepływomwsieciach.Przedstawionywnim
algorytmForda–Fulkersona,jestszybszyodprezentowanegowrozdziale1algo-
rytmusympleks,choćrozwiązujetylkopewienszczególnyproblemprogramo-
wanialiniowego(problemmaksymalnegoprzepływu).Wtymsamymrozdziale
omówionotakżepiękneiznanetwierdzenieomaksymalnymprzepływieimi-
nimalnymprzekroju(udowodnioneniezależnieprzezFordaiFulkersonaoraz
Eliasa,FeinsteinaiShannona).Wrozdzialetymwykazanorównież,żeinne
ważnetwierdzenia:Halla,Königa–EgerváryegoiMengeramożnaudowodnić,
korzystającztwierdzeniaomaksymalnymprzepływieiminimalnymprzekroju.
Dowiedzionowreszcie,żetoostatnietwierdzeniejestkonsekwencjązasadydu-
alności.
Wrozdziale8omówionezostałozagadnienietransportowe.Przedstawiam
wnimmetodęrozwiązywaniategoproblemuzwanąsympleksemsieciowym.Jest
onainteresującam.in.zewzględunajejpowiązaniezteoriągrafów.Wroz-
dzialezawartesąwszystkiekoniecznewiadomościnatematteoriigrafów.
Wksiążceprzedstawiamtylkojednąmetodęrozwiązywaniaproblemówpro-
gramowanialiniowego,amianowiciealgorytmsympleks(inaczej:algorytm
sympleksowywynalezionyniezależnieprzezDantzigaiKantorowicza.(por.
[3]).Przeglądróżnychmetodprogramowanialiniowegomógłbybyćtematem
osobnejksiążki;mojąintencjąjesttutajprzedstawieniemetody,którajestnaj-
bardziejnaturalnaistosunkowołatwopozwalarozwiązaćkonkretne,choćnie-
wielkie,problemynawetbezużywaniakomputera.Mimożealgorytmsymplek-
sowyniejestwielomianowy(jaktowykazanonastronie34wpodrozdziale2.5),
jegopraktycznaszybkośćjestbardzodobra.Pisząotym,międzyinnymi,auto-
rzyksiążek[5]i[24].
Przekazującksiążkęwręceczytelników,pragnęwszczególnysposóbpodzią-
kowaćosobom,któreprzyczyniłysiędojejpowstaniaiedycji.
WydaniepublikacjizostałosfinansowaneprzezrektoraAGH,profesoraTade-
uszaSłomkę,orazdziekanaWydziałuMatematykiStosowanejAGH,profesora
VsevolodaVladimirova.Obupanomprofesoromserdeczniedziękuję.
Serdeczniedziękujęrecenzentom,panomprofesoromAndrzejowiCegielskiemu
iLeonidowiPłachciezawnikliwerecenzje.
DużąpomocądlamniebyłykorektyksiążkiwykonaneprzezpaniąJoannę
Ciągałę,zastępcęredaktoranaczelnegoWydawnictwAGH.Pozwoliłyoneuczy-
nićtekstbardziejczytelnymipoprawnym.
