8107620631

Programowanie matematyczne jest to zbiór metod poszukiwania punktu optymalizującego (minimalizującego lub maksymalizującego) wartość funkcji rzeczywistej w podzbiorze przestrzeni K". 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 + l)-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:

:= {t G Z N_m := {t € N Dla A e M_m,„

• A,_k oznacza k-tą kolumnę macierzy A,

•    Aic* oznacza k-ty wiersz macierzy A.

Zatem A = (A_tl ... A„„) lub A = (Ai*... A_nt)^T.

Dla A 6 M_mi„, m < n, B C Ni,_n (B - zbiór m-elementowy):

•    B' := Ni,_n \ B,

•    A_b := (A_łJ: ...A,_jm), gdzie ji < ... < j_m, j_u ... ,j_m E 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 6 M_m,i, c € Mi _n, zminimalizować funkcjonał

M„4 3 x *—> cx    (1)

przy warunkach

Ax = b    (2)

oraz

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

V := {x E M_n,i : Ax = b,x > 0}    (4)

nazywamy zbiorem rozwiązań dopuszczalnych.

2