wzbo-wyklad nr 2a, MATERIAŁY DYDAKTYCZNE, WYBRANE ZAGADNIENIA BADAŃ OPERACYJNYCH
[ Pobierz całość w formacie PDF ]
Wybrane zagadnienia
badań operacyjnych
badań operacyjnych
Wykład 2a
Metoda simpleks rozwiązywania zadań
programowania liniowego
Prowadzący:
dr in
ż
ż. Zbigniew TARAPATA
Dane kontaktowe:
e-mail:
Zbigniew.Tarapata@wat.edu.pl
tel.
: 83-94-13, 83-94-73
1
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
POSTAĆ KANONICZNA ZADANIA PROGRAMOWANIA
PROGRAMOWANIA
LINIOWEGO - PRZYPOMNIENIE
PRZYPOMNIENIE
Przypomnijmy : Postać kanoniczna zadania optymalizacji
liniowej definiowana jest następująco:
Wyznaczyć x(x
1
, x
2
, x
3
,..., x
n
) takie, aby
=
przy ograniczeniach:
f
(
x
)
min{
c
1
x
1
+
c
2
x
2
+
c
3
x
3
+
...
+
c
n
x
n
}
n-zmiennych
a
11
x
1
+
a
12
x
2
+
a
13
x
3
+
...
+
a
1
n
x
n
=
b
1
a
21
x
1
+
a
22
x
2
+
a
23
x
3
+
...
+
a
2
n
x
n
=
b
2
21
1
22
2
23
3
2
n
n
2
m-ograniczeń
a
m
1
x
1
+
a
m
2
x
2
+
a
m
3
x
3
+
...
+
a
mn
x
n
=
b
m
x
1
,
x
2
,
x
3
,...,
x
n
≥
0
2
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
WWW:
POSTAĆ KANONICZNA ZADANIA
LINIOWEGO
Wyznaczyć x=(x
1
,x
2
,x
3
,..., x )takie,aby
min
POSTAĆ KANONICZNA ZADANIA PROGRAMOWANIA
PROGRAMOWANIA
LINIOWEGO - PRZYPOMNIENIE
PRZYPOMNIENIE
W zapisie wektorowo-macierzowym otrzymamy następującą
postać:
min
c
,
x
A
=
⋅
x
b
x
≥
0
gdzie:
c
=
[ ]
c
1
...
c
n
a
a
...
a
x
b
x
b
11
12
1
n
1
1
a
a
...
a
x
b
2
2
A
=
21
22
2
n
x
=
b
=
...
...
...
...
...
...
x
b
a
a
...
a
n
m
1
m
2
mn
3
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład
Wyznaczyć x=(x
1
, x
2
, x
3
) takie, aby
min{
f
(
x
)
=
2
x
1
+
4
x
2
−
x
3
}
przy ograniczeniach:
Mamy trzy zmienne decyzyjne,
dwa ograniczenia (n=3, m=2),
jednak postać ta jest postacią
kanoniczną.
2
x
1
+
3
2
−
4
x
3
=
10
4
x
−
5
x
+
x
=
5
1
2
3
W tym przypadku na przykład
a 2a 4a 5b 10 itd
x
,
x
,
x
≥
0
a
11
=2, a
13
=-4, a
22
=-5, b
1
=10 itd.
1
2
3
≥
0
Wszystkie zadania optymalizacji liniowej sprowadzić musimy
przede wszystkim do postaci kanonicznej.
4
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
POSTAĆ KANONICZNA ZADANIA
LINIOWEGO
Sprowadzanie zadań optymalizacji liniowej do postaci kanonicznej
f(x)
;
b) Jeśli mamy ograniczenie typu „
≥
”, to od lewej strony
odejmujemy nową zmienną (tzw. „sztuczną”) i zamieniamy
nierówność na równość;
współczynnik
max f(x)
f(x) =– min
min –f(x)
współczynnik tej
tej nowej
nowej zmiennej
zmiennej w
(zero);
c) Jeśli mamy ograniczenie typu „
≤
”, to do lewej strony
kryterium wynosi
wynosi 00(zero)
c) Jeśli mamy ograniczenie typu „
≤
, to do lewej strony
dodajemy nową zmienną (tzw. „sztuczną”) i zamieniamy
nierówność na równość;
współczynnik
współczynnik tej
tej nowej
nowej zmiennej
zmiennej w
funkcji kryterium
kryterium wynosi
wynosi również
również 00(zero)
(zero).
5
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład (sprowadzanie zadania do postaci kanonicznej)
Załóżmy, że mamy zadanie optymalizacji postaci :
}
max
f
(
x
)
=
max{
x
1
+
x
2
c =
(
przy ograniczeniach:
pyg
2
x
1
+
x
2
≤
2
2
1
2
x
+
x
2
≥
1
A
=
1
2
b
=
1
1
2
3
4
4
3
x
+
x
4
=
4
1
2
x
1
,
x
2
≥
0
x
=
x
1
x
2
6
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
a) Jeśli szukamy zmiennych maksymalizujących funkcję
kryterium, to zamieniamy ją na przemnożoną przez (-1)
i wtedy szukamy już zmiennych minimalizujących nową
i wtedy szukamy już zmiennych minimalizujących nową
funkcję,tzn.
max
funkcji
funkcji kryterium
funkcji
Przykład (cd.)
Sprowadźmy zadanie do postaci kanonicznej.
Najpierw zamieniamy „max” na „min” mnożąc funkcję przez –1:
}
x
1
+
x
2
}
=
−
min{
−
x
1
−
x
2
+
0
⋅
x
3
+
0
⋅
x
4
2
Zmieniamy ograniczenia
2
c
=
( −
−
1
1
b
=
1
2
x
+
x
+
x
=
4
1
2
3
2
1
1
0
x
+
2
x
−
x
=
1
1
2
4
A
=
1
2
0
−
1
x
3
x
+
x
4
=
4
1
2
x
1
2
3
4
0
0
x
=
2
x
,
x
≥
0
1
2
x
3
min
c
x
x
Zapis wektorowo-macierzowy
4
A =
⋅
x
b
x ≥
0
7
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
ELEMENTY ANALIZY WYPUKŁEJ
Definicja
Zbiór
Ω
nazywamy wypukłym jeśli dla każdych dwóch punktów
x,y
∈Ω
punkt z=
θ⋅
x+(1-
θ
)y należy do
Ω
dla każdego
θ∈
[0,1].
x
z
y
x
z
y
Ω
Ω
Ω
- zbiór wypukły
Ω
- zbiór, który nie jest wypukły
Definicja
j
Hiperpłaszczyzną H
α
w przestrzeni E
n
nazywamy zbiór
H
=
{
x
∈
E
n
:
a
,
x
=
α
,
a
∈
E
n
,
α
∈
R
α
gdzie
<
a,x
>
- iloczyn skalarny wektorów a oraz x.
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
8
max{
Definicja
Hiperpłaszczyzna H
α
generuje dwie półprzestrzenie domknięte
H
−
=
{
x
∈
E
n
:
a
,
x
≤
α
H
+
=
{
x
∈
E
n
:
a
,
x
≥
α
α
α
Definicja
Zbiorem wielościennym (simpleksem) nazywamy zbiór
Ω
postaci
Ω
=
∩
m
i
{
x
∈
E
n
:
a
,
x
≤
b
}
i
i
=
1
Definicja
Funkcja rzeczywista f określona na wypukłym zbiorze
Ω
nazywa
nazywa
się wypukłą
, jeśli dla każdego x,y
∈Ω
oraz dla każdego
θ∈
[0,1]
spełniona jest nierówność
θ
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
f
(
⋅
x
+
(
−
θ
)
⋅
y
)
≤
θ
⋅
f
(
x
)
+
(
−
θ
)
⋅
f
(
y
)
9
Jeśli natomiast spełniona jest nierówność
f
(
θ
⋅
x
+
(
−
θ
)
⋅
y
)
≥
θ
⋅
f
(
x
)
+
(
−
θ
)
⋅
f
(
y
)
to funkcję f nazywamy
wklęsłą
wklęsłą
.
Uwaga: funkcja liniowa f(x)=
<
a,x
>
jest jednocześnie wypukła i
g
j
( )
, j j
yp
wklęsła.
Twierdzenie
m
=
∑
=
Funkcja postaci
F
(
x
)
λ
i
⋅
f
i
(
x
)
λ
i
≥
0
i
=
1
,...,
m
i
1
jest wypukła, jeśli f
i
(x) są wypukłe, i=1,...,m.
Wniosek
kł j śli f ()
kł i1
Zbiór postaci
Ω
=
{
x
∈
E
n
:
A
⋅
x
=
b
,
x
≥
0
gdzie A=[a
ij
]
mxn
jest wypukły.
10
Wybrane zagadnienia badań operacyjnych – Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Definicja
Definicja
się wypukłą
jt
[ Pobierz całość w formacie PDF ]