3179027796

Elementy Badań Operacyjnych

2. Program liniowy

Programem liniowym (PL) nazywamy zadanie o następującej postaci:

c_lx_l+c₂x₂-\—I-c_Nx_N —> max funkcja celu (funkcja kryterium) ct_nx_x + a_l2x₂ +... + a_lNx_N < Z>, a_2ix, + a₂₂x₂ +...+a_2Nx_N < b₂

>    warunki ograniczające    (1)

a_Mlx_l + a_M2x₂ +... + a_mx_N < b_KI I x,, x₂, • • •, x_N > 0 warunki brzegowe lub

c_lx_l+c₂x₂+---+c_Nx_N —> min funkcja celu (funkcja kryterium) a_nx₂ + a_l2x₂ +... + a_lNx_N > b_x a_2lx_l+a₂₂x₂+... + a_2Nx_N >b₂

>    warunki ograniczające    (2)

^aMl^Xl + ^aM₂X₂ + • • • + d_mX_M > by J

x,,x₂,-",x_A, > 0 warunki brzegowe

Program liniowy (1) nazywamy standardowym zadaniem maksymalizacji a program (2) standardowym zadaniem minimalizacji.

W programie tym występują pewne wielkości dane — parametry: aj, b„ Cj (i = 1,2 j = \,2,...,N) oraz wielkości, które należy ustalić — zmienne decyzyjne: Xj (j = 1,2

Elementami każdego programu liniowego są: warunki ograniczające, warunki brzegowe i funkcja celu. Warunki ograniczające to układ równań lub nierówności opisujących warunki działania. W konkretnych sytuacjach decyzyjnych nierówności w warunkach ograniczających mogą oczywiście mieć przeciwny zwrot, mogą to także być równości. W warunkach brzegowych zakłada się, że zmienne decyzyjne, które są pewnymi wielkościami ekonomicznymi będą liczbami nieujemnymi. Funkcja celu umożliwia wybór optymalnego przy istniejących ograniczeniach wariantu planu; może być maksymalizowana lub minimalizowana.

Zbiór wartości zmiennych decyzyjnych spełniający warunki ograniczające i warunki brzegowe nazywamy rozwiązaniem dopuszczalnym PL. Rozwiązań dopuszczalnych jest zwykle wiele. Spośród nich wybiera się takie, dla którego (których) funkcja celu przyjmuje wartość ekstremalną (w zależności od sytuacji maksymalną lub minimalną). Jest to rozwiązanie optymalne.

Standardowy program liniowy może być odpowiednio także zapisany w notacji macierzowej :

c^Tx —> max    c^Tx —> min

Ax < b    Ax > b    (3)

x > 0    x > 0

gdzie: A jest macierzą współczynników stojących po lewej stronie układu warunków ograniczających (o wymiarach MxN), b jest wektorem (kolumnowym, o wymiarach Mxl) wyrazów wolnych układu warunków ograniczających, c^T jest wektorem wierszowym (o wymiarach 1 xN) współczynników funkcji celu i x jest wektorem zmiennych decyzyjnych (o wymiarach

Nx 1).

Antoni Goryl, Anna Walkosz: Programowanie liniowe strona 4