6.2. Zadanie programowania liniowego
W przypadku, gdy funkcje f , g1, K, gm wstępujące w modelu matematycznym
zadania decyzyjnego, sÄ… liniowe oraz ich parametry sÄ… nielosowe model nazywamy modelem
programowania liniowego (PL). W ogólnym przypadku model taki możemy zapisać jako
jedno z dwóch zadań postaci:
PL-1. Zadanie na maksymalizacjÄ™
Znalez
ć wartość największą funkcji f (x1, x2 ,..., xn ) = c1x1 + c2 x2 + ... + cn xn
przy ograniczeniach:
a11x1 + a12 x2 + ... + a1n xn d" b1
Å„Å‚
ôÅ‚
a21x1 + a22 x2 + ... + a2n xn d" b2
òÅ‚
ôÅ‚
am1x1 + am2 x2 + ... + amn xn d" bm
ół
i warunkach brzegowych
x1, x2 , K, xn e" 0 .
PL-2. Zadanie na minimalizacjÄ™
Znalez
ć wartość największą funkcji f (x1, x2 ,..., xn ) = c1x1 + c2 x2 + ... + cn xn
przy ograniczeniach:
a11x1 + a12 x2 + ... + a1n xn e" b1
Å„Å‚
ôÅ‚
a21x1 + a22 x2 + ... + a2n xn e" b2
òÅ‚
ôÅ‚
am1x1 + am2 x2 + ... + amn xn e" bm
ół
i warunkach brzegowych
x1, x2 , K, xn e" 0 .
Można także rozważać przypadki, w których w tym samym układzie warunków występują
nierówności i równania. Nie zmniejszając ogólności rozważań, taki układy warunków mogą
być traktowane jako układy nierówności, ponieważ każde równanie można zapisać jako
koniunkcję dwóch nierówności:
a1x1 + a2 x2 + ... + an xn d" b
Å„Å‚
a1x1 + a2 x2 + ... + an xn = b Ô! .
òÅ‚
x1 + a2 x2 + ... + an xn e" b
óła1
Zwróćmy także uwagę, że każdą nierówność ze zwrotem  e"  można zamienić na
nierówność, w której wystąpi zwrot  d"  , mnożąc ją przez liczbę ujemną (np. przez -1).
OznaczajÄ…c przez: A = [aij ]m×n - macierz współczynników ukÅ‚adu ograniczeÅ„,
b = [bi ]m×1 - wektor wyrazów wolnych dla ograniczeÅ„,
c = [cj ]n×1 - wektor współczynników funkcji celu,
x = [xj ]n×1 - wektor zmiennych decyzyjnych
zadanie PL tradycyjnie zapisujemy jako:
Å„Å‚ Å„Å‚
cTx max cTx min
ôÅ‚ ôÅ‚
PL-1: lub PL-2:
A x d" b A x e" b
òÅ‚ Å„Å‚ òÅ‚ Å„Å‚
X : X :
òÅ‚x e" 0 òÅ‚x e" 0
ôÅ‚ ôÅ‚
ół ół
ół ół
Zbiór rozwiÄ…zaÅ„ dopuszczalnych X ‚" Rn , wyznaczony przez ukÅ‚ad ograniczeÅ„
i warunków brzegowych zadania PL, może być:
a) zbiorem pustym ( X = " ) - mówimy wówczas, że zadanie PL jest sprzeczne;
b) zbiorem niepustym ( X `" " ), który zawiera:
" jeden element ( X = {x0}) - wówczas zadanie PL nie jest zadaniem decyzyjnym,
ponieważ nie dokonujemy żadnego wyboru w zbiorze rozwiązań
dopuszczalnych;
" więcej niż jeden element - wówczas zadanie PL jest zadaniem decyzyjnym.
Jeżeli zbiór rozwiązań dopuszczalnych X zadania PL zawiera co najmniej dwa
elementy, to jest wypukłym i domkniętym podzbiorem przestrzeni Rn o skończonej liczbie
punktów wierzchołkowych, czyli jest wielościanem (gdy jest zbiorem ograniczonym) lub
wielościennym zbiorem wypukłym (gdy jest zbiorem nieograniczonym).
Ponieważ funkcja celu f (x) = f (x1, x2 ,..., xn ) = c1x1 + c2 x2 + ... + cn xn zadania PL jest
liniowa i jeśli zbiór X jest wypukłym i domkniętym wielościanem przestrzeni Rn , to
korzystając z twierdzenia Weierstrassa, wyznaczamy wartości funkcji f w wierzchołkach
zbioru X i wybieramy z nich tę wartość, która jest największą (dla zadania PL-1.) lub tę,
która jest najmniejszą (dla zadania PL-2.). Punkt xw , czyli wierzchołek zbioru X , w którym
ta wartość jest przez funkcję f przyjmowana, nazywamy rozwiązaniem optymalnym i
oznaczamy jako xop . Jeśli funkcja celu osiąga swoją wartość optymalną (zgodnie z przyjętym
w w
kryterium) w większej, niż jeden, liczbie wierzchołków, np. x1 , x2 , K, xw , to rozwiązaniem
s
optymalnym zadania PL jest każda nieujemna i wypukła kombinacja tych wierzchołków,
w w
czyli xop = Ä…1x1 + Ä…2 x2 +L+ Ä…s xw dla Ä…1 + Ä…2 + L + Ä…s = 1 '" Ä…1, Ä…2 ,K, Ä…s e" 0 .
s
Jeśli zbiór X jest wielościennym zbiorem wypukłym (jest zbiorem nieograniczonym), to
funkcja f (x) = c1x1 + c2 x2 + ... + cn xn może w nim nie osiągać swoich kresów. Wówczas
zadania PL-1 lub PL-2 mogą mieć nieograniczone rozwiązania optymalne ( + " lub - " ).
Własności zbioru rozwiązań dopuszczalnych oraz liniowość funkcji celu powodują, że
metody rozwiązywania zadań programowania liniowego wykorzystują wiedzę z algebry
liniowej. W szczególności zadania, w których występują dwie zmienne decyzyjne (lub liczba
zmiennych decyzyjnych może być zredukowana do dwóch) można rozwiązać metodą
graficzną. Z tą metodą zapoznać się można np. w pozycjach: [3] s. 11-18 a także [5] s. 18-35,
gdzie jest ona opisana i zilustrowana przykładami. Ogólną algebraiczną metodą
rozwiązywania zadań programowania liniowego o dowolnej liczbie zmiennych decyzyjnych
jest algorytm simpleks opisany w następnym punkcie.