6.2. Zadanie programowania liniowego
W przypadku, gdy funkcje
m
g
g
f
,
,
,
1
K
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ę
PL-2. Zadanie na minimalizację
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ą
Znaleźć wartość największą funkcji
n
n
n
x
c
x
c
x
c
x
x
x
f
+
+
+
=
...
)
,...,
,
(
2
2
1
1
2
1
przy ograniczeniach:
≥
+
+
+
≥
+
+
+
≥
+
+
+
m
n
mn
m
m
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
...
...
...
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
i warunkach brzegowych
0
,
,
,
2
1
≥
n
x
x
x
K
.
Znaleźć wartość największą funkcji
n
n
n
x
c
x
c
x
c
x
x
x
f
+
+
+
=
...
)
,...,
,
(
2
2
1
1
2
1
przy ograniczeniach:
≤
+
+
+
≤
+
+
+
≤
+
+
+
m
n
mn
m
m
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
...
...
...
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
i warunkach brzegowych
0
,
,
,
2
1
≥
n
x
x
x
K
.
być traktowane jako układy nierówności, ponieważ każde równanie można zapisać jako
koniunkcję dwóch nierówności:
b
x
a
x
a
x
a
n
n
=
+
+
+
...
2
2
1
1
⇔
≥
+
+
+
≤
+
+
+
b
x
a
x
a
x
a
b
x
a
x
a
x
a
n
n
n
n
...
...
2
2
1
1
2
2
1
1
.
Zwróćmy także uwagę, że każdą nierówność ze zwrotem „
≥
” można zamienić na
nierówność, w której wystąpi zwrot „
≤
”, mnożąc ją przez liczbę ujemną (np. przez -1).
Oznaczając przez:
n
m
ij
a
×
=
]
[
A
- macierz współczynników układu ograniczeń,
1
]
[
×
=
m
i
b
b
- wektor wyrazów wolnych dla ograniczeń,
1
]
[
×
=
n
j
c
c
- wektor współczynników funkcji celu,
1
]
[
×
=
n
j
x
x
- wektor zmiennych decyzyjnych
zadanie PL tradycyjnie zapisujemy jako:
Zbiór rozwiązań dopuszczalnych
n
R
X
⊂
, 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 (
{ }
0
x
=
X
) - 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
n
R 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
n
n
n
x
c
x
c
x
c
x
x
x
f
f
+
+
+
=
=
...
)
,...,
,
(
)
(
2
2
1
1
2
1
x
zadania PL jest
liniowa i jeśli zbiór
X
jest wypukłym i domkniętym wielościanem przestrzeni
n
R , to
PL-1:
≥
≤
→
0
x
b
x
A
x
c
:
max
X
T
lub PL-2:
≥
≥
→
0
x
b
x
A
x
c
:
min
X
T
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
w
x , czyli wierzchołek zbioru
X
, w którym
ta wartość jest przez funkcję f przyjmowana, nazywamy rozwiązaniem optymalnym i
oznaczamy jako
op
x . Jeśli funkcja celu osiąga swoją wartość optymalną (zgodnie z przyjętym
kryterium) w większej, niż jeden, liczbie wierzchołków, np.
w
s
w
w
x
x
x
,
,
,
2
1
K
, to rozwiązaniem
optymalnym zadania PL jest każda nieujemna i wypukła kombinacja tych wierzchołków,
czyli
w
s
s
w
w
op
x
x
x
x
α
α
α
+
+
+
=
L
2
2
1
1
dla
0
,
,
,
1
2
1
2
1
≥
∧
=
+
+
+
s
s
α
α
α
α
α
α
K
L
.
Jeśli zbiór
X
jest wielościennym zbiorem wypukłym (jest zbiorem nieograniczonym), to
funkcja
n
n
x
c
x
c
x
c
f
+
+
+
=
...
)
(
2
2
1
1
x
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.