Wykład z modelowania matematycznego. Algorytm sympleks. 1
2 Programowanie matematyczne jest to zbiór metod poszukiwania punktu optymalizującego (minimalizującego lub maksymalizującego) wartość funkcji rzeczywistej w podzbiorze przestrzeni R n. Jednym z działów programowania matematycznego jest programowanie liniowe, w którym optymalizuje się wartość funkcji liniowej na zbiorze określonym przez układ warunków (równań i nierówności) liniowych. Metoda sympleks opracowana przez Georga Dantziga jest iteracyjną metodą rozwiązywania zadań programowania liniowego za pomocą kolejnego polepszania (optymalizacji) rozwiązania. Nazwa metody pochodzi od sympleksu, czyli otoczki wypukłej zbioru (n + 1)-elementowego w przestrzeni n wymiarowej. Polega na sprawdzaniu kolejnych wierzchołków wielościanów, w ten sposób, że przechodzi się od wierzchołka do sąsiedniego wierzchołka w pewnym sympleksie optymalizując (zwiększając lub zmniejszając) wartość funkcji. 1 Podstawowe pojęcia i oznaczenia Oznaczenia: Z p,q := {t Z : p t q}, N p,q := {t N : p t q}. Dla A M m,n : A k oznacza k-tą kolumnę macierzy A, A k oznacza k-ty wiersz macierzy A. Zatem A = (A 1... A n ) lub A = (A 1... A n ) T. Dla A M m,n, m n, B N 1,n (B - zbiór m-elementowy): B := N 1,n \ B, A B := (A j1... A jm ), gdzie j 1 <... < j m, j 1,..., j m B. Definicja 1 Problemem programowania liniowego (problemem PL) nazywamy następujący problem: dla dowolnie ustalonych m, n N oraz macierzy A M m,n, b M m,1, c M 1,n, zminimalizować funkcjonał M n,1 x cx (1) przy warunkach oraz Ax = b (2) x 0. (3) Warunki (2)-(3) nazywamy warunkami ograniczającymi, zaś funkcjonał (1) nazywamy funkcją celu.. Definicja 2 Rozwiązaniem dopuszczalnym problemu PL nazywamy wektor x spełniający warunki ograniczające (2)-(3). Zbiór nazywamy zbiorem rozwiązań dopuszczalnych. D := {x M n,1 : Ax = b, x 0} (4) 2
