12
PROGRAMOWANIE LINIOWE
Dane są:
•
Wektor n zmiennych decyzyjnych: x
T
= {x
1
, x
2
, . . x
n
}
T
•
Liniowa funkcja celu f zależna od zmiennych
decyzyjnych:
z = f(x) =
n
n
x
c
x
c
x
c
x
c
+
+
+
+
.
.
.
.
3
3
2
2
1
1
c
1
, c
2
, . . c
n
– współczynniki kosztu c
T
= {c
1
, c
2
, . . c
n
}
T
x
c
T
z
=
•
Zbiór
m
liniowych funkcji ograniczeń
zależnych od
zmiennych decyzyjnych:
i
n
in
i
i
i
b
x
a
x
a
x
a
g
≥
+
+
+
=
.
.
.
2
2
1
1
i = 1,2, . . , m
[
]
in
i
i
i
a
a
a
"
2
1
=
a
⇒
0
≤
−
x
a
i
i
b
i
= 1,2, . ,
m
⇒
=
=
=
mn
m
m
n
n
m
m
a
a
a
a
a
a
a
a
a
b
b
b
"
#
#
#
#
"
"
#
#
2
1
2
22
21
1
12
11
2
1
2
1
,
a
a
a
A
b
0
≤
−
Ax
b
13
Sformułowanie ZPL:
Znaleźć
xˆ
takie, że:
x
c
x
c
x
T
T
z
.
min
ˆ
=
=
przy spełnieniu ograniczeń:
0
≤
−
Ax
b
A, b, c – dane; n zmiennych projektowania, m ograniczeń.
POSTAĆ KANONICZNA (Standardowa) ZPL:
•
Ograniczenia są przekształcone do ograniczeń
równościowych
⇔
wprowadzając dodatkowe
zmienne dopełniające
x
n+i
≥
0, takie, że
i
i
b
≥
a x
⇒
i
i
n
i
b
x
=
−
+
x
a
•
Wszystkie zmienne projektowania są nieujemne.
Zmienną nieokreślonego znaku zastępuje się
dwiema zmiennymi nieujemnymi, takimi, że
0
0
gdzie
≥
≥
−
=
−
+
−
+
j
j
j
j
j
x
x
x
x
x
Postać kanoniczna ZPL:
x
c
x
x
T
f
z
.
min
)
ˆ
(
=
=
przy ograniczeniach:
0
≥
=
x
b
Ax
14
METODY ROZWIĄZYWANIA ZPL
Dane jest ZPL w postaci kanonicznej:
0
ogr.
przy
.
min
≥
=
=
x
b
Ax
z
c
T
z
n – liczba zmiennych projektowania
m – liczba ograniczeń
n
m
≤
Przypadek nietrywialny m<n:
Znaleźć xˆ takie, że:
{
}
n
n
m
n
m
R
X
z
z
n
L
X
T
L
=
=
=
×
=
⇐
∈
≥
=
=
=
=
∈
c
x
b
A
x
x
b
Ax
x
x
c
x
x
dim
,
dim
,
dim
,
dim
ny
dopuszczal
obszar
,
0
,
:
gdzie
)
(
.
min
)
ˆ
(
ˆ
0
0
15
Definicje:
•
Wektor
L
X
0
∈
x
nazywamy rozwiązaniem dopuszczalnym
ZPL.
•
Macierz B o wymiarze m
x
m utworzoną z liniowo-
niezależnych kolumn macierzy A nazywamy macierzą
bazową układu równań Ax=b.
[
]
n
mn
m
m
n
n
m
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
A
"
"
#
#
#
#
"
"
#
2
1
2
1
2
22
21
1
12
11
2
1
=
=
=
na przykład:
[
] [
]
"
"
kolumn
m
n
kolumn
m
m
3
9
5
2
3
2
1
−
=
=
a
a
a
a
b
b
b
b
B
•
Wektor
b
B
x
1
−
=
B
nazywamy rozwiązaniem bazowym
układu równań Ax=b.
x
B
jest rozwiązaniem układu równań Bx
B
= b
•
Składowe wektora x
B
nazywamy zmiennymi bazowymi.
Jeżeli x
B
≥
0, to x
B
jest dopuszczalnym
rozwiązaniem bazowym.
Jeżeli x
B
> 0, to x
B
jest niezdegenerowanym
dopuszczalnym
rozwiązaniem bazowym.
Kolumna macierzy A
Wiersz macierzy A
16
Maksymalna ilość rozwiązań bazowych:
)!
(
!
!
m
n
m
n
−
•
Rozwiązanie układu Ax = b odpowiadające danemu
rozwiązaniu bazowemu
{
}
0
x
x
B
=
n (n-m)
•
Rozwiązanie optymalne xˆ ZPL : to z rozwiązań
dopuszczalnych
{
}
0
x
x
B
=
które minimalizuje funkcję
celu
x
c
T
z
=
.
17
Przykład
Założenia:
•
Firma do wytworzenia wyrobu I używa maszyn A i B, zaś
do wytworzenia wyrobu II – maszyn A i C.
•
Zdolność produkcyjna:
- maszyny A: 6 tys. sztuk/rok wyrobu I lub wyrobu II
- maszyny B: 4 tys. sztuk/rok wyrobu I
- maszyny C: 5 tys. sztuk/rok wyrobu II
•
Zysk na wyrobie I – 2 zł./szt. , na wyrobie II – 1 zł./szt.
Cel:
Ustalić optymalną wielkość produkcji x
1
wyrobu I i
x
2
wyrobu II tak, aby uzyskać maksymalny roczny zysk.
Matematyczne sformułowanie problemu:
0
,
0
C/rok
masz.
prod.
zdolnosc
5
B/rok
masz.
prod.
zdolnosc
4
A/rok
masz.
prod.
zdolnosc
6
:
ogr.
przy
2
.
max
2
1
2
1
2
1
2
1
≥
≥
≤
≤
≤
+
+
=
x
x
x
x
x
x
x
x
f
18
Sformułowanie ZPL:
≥
≥
≤
≤
≤
+
−
−
=
−
=
0
,
0
5
4
6
:
ogr.
przy
2
.
min
2
1
2
1
2
1
2
1
x
x
x
x
x
x
x
x
f
z
Postać kanoniczna ZPL:
≥
≥
≥
≥
≥
=
+
=
+
=
+
+
−
−
=
−
=
0
,
0
,
0
,
0
,
0
5
4
6
:
ogr.
przy
2
.
min
5
4
3
2
1
5
2
4
1
3
2
1
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f
z
n = 5 , m = 2
5
4
3
,
,
x
x
x
-
zmienne dopełniające
Max. liczba rozw. bazowych:
10
)!
2
5
(
!
2
!
5
=
−
19
Ograniczenia można zapisać w postaci:
Ax = b
lub
=
5
4
6
1
0
0
1
0
0
1
0
0
1
0
0
1
1
1
5
4
3
2
1
x
x
x
x
x
[ a
1
a
2
a
3
a
4
a
5
]{
x} = {b}
3 x 5 5 x 1 5 x 1
Macierze bazowe B
k
, k=1,2,...,10, są utworzone z
kombinacji kolumn macierzy A:
1)
1 2 3
2)
1 2 4
3)
1 2 5
4)
1 3 4
5)
1 3 5
6)
1 4 5
7)
2 3 4
8)
2 3 5
9)
2 4 5
10)
3 4 5
Rozwiązując kolejno układ równań:
b
x
B
=
k
B
k
(k=1,..,10)
Znajduje się rozwiązania bazowe
k
B
x i odpowiadające im
rozwiązania problemu wyjściowego
=
k
N
k
B
k
x
x
x
gdzie
0
x
=
k
N
20
Rozw. bazowe 1, 6 i 9 : niedopuszczalne
Rozw. bazowe 4 i 8 : brak (układ sprzeczny)
Rozw. bazowe 2,3,5,7 i 10: dopuszczalne
Zestawienie rozwiązań dopuszczalnych:
Nr x
1
x
2
x
3
x
4
x
5
f. celu z=-2x
1
-x
2
1 1 5 3 0 0
-7
2
4 2 0 0 3
-10
3 4 0 2 0 5
-8
4 0 5 1 4 0
-5
5 0 0 6 4 5
0
=
2
4
ˆx
należy produkować rocznie 4 tys. sztuk
wyrobu I i 2 tys. sztuk wyrobu II, uzyskując
roczny zysk w wysokości 10 tys. zł.
Rozwiązanie optymalne
21
Interpretacja geometryczna:
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
8
9
x2
x1
g3
g2
g1
z=-8
z=-7
z=-10
rozw. opt. (4 2)
kie
run
ek
zm
nie
jsz
ani
a s
ie
fun
kcj
i ce
lu
22
PODSTAWOWE WŁASNOŚCI ROZWIĄZAŃ ZPL
1. Funkcja celu i ograniczenia są funkcjami wypukłymi
(jako
funkcje
liniowe)
Stąd wynika: Zbiór rozwiązań dopuszczalnych ZPL jest
zbiorem wypukłym (
hiperwielościanem wypukłym
).
)
,
0
,
:
{
0
n
L
R
X
∈
≥
=
=
x
x
b
Ax
x
2. Jeżeli dany układ równań liniowych ograniczeń Ax=b
(gdzie dim A =
m
x
n
, dim x =
n
, dim b =
m
) ma rozwią-
zania dopuszczalne, to istnieją również bazowe rozwią-
zania dopusazczalne.
3. Rozwiązanie dopuszczalne x ZPL jest punktem wierz-
chołkowym zbioru rozwiązań dopuszczalnych
X
OL
(wierz-
chołkiem hiperwielościanu wypukłego) wtedy i tylko wte-
dy, gdy odpowiada mu bazowe rozwiązanie dopuszczalne,
tzn.
=
0
x
x
B
.
4. Jeżeli funkcja
f
(x) określona w wypukłym zbiorze
X
OL
jest ciągła i wypukła, to globalne minimum funkcji
f
występuje w punkcie (lub punktach) wierzchołkowym
zbioru
X
OL
.
23
Interpretacja geometryczna ZPL w przestrzeni rozwiązań:
Zbiór rozwiązań dopuszczalnych:
}
,
0
,
0
:
{
0
n
L
R
X
∈
≥
≤
−
=
x
x
Ax
b
x
tworzy hiperwielościan wypukły w przestrzeni zmiennych
decyzyjnych.
zbiór X0L
minimum
(jedno rozw. opt.)
hiperplaszczyzny ograniczeñ
z=const.
x2
x1
zbiór X0L
hiperplaszczyzny ograniczeñ
z=const.
x2
x1
nieskoñczenie wiele
rozwiazan optymalnych