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
Wyszukiwarka
Podobne podstrony:
Program umiarkowany id 395519 Nieznany
Narodowy Program Zdrowia1 id 31 Nieznany
Narodowy Program Zdrowia id 314 Nieznany
Program cw3 id 395618 Nieznany
Algebra liniowa1 id 57289 Nieznany
Programowanie GUI id 395885 Nieznany
Algebra liniowa 1 3 id 57241 Nieznany
Program zjazdu id 395614 Nieznany
Program cw2 id 395617 Nieznany
badop gry liniowe id 78528 Nieznany (2)
Program cw5 id 395619 Nieznany
Program cz1 id 395054 Nieznany
Program cz10 id 395055 Nieznany
program zajec id 395592 Nieznany
Programowanie Usb C id 396388 Nieznany
Program wykladu id 395571 Nieznany
Program zajec 2 id 395593 Nieznany
program arteterapii 3 id 394997 Nieznany
więcej podobnych podstron