lecture 3.pdf
(
175 KB
)
Pobierz
C:/Documents and Settings/Micha³/Pulpit/BO/bop_wyklad/W2/w2bmf.dvi
METODA SYMPLEKS
Model zagadnienia programowania liniowego jest w postaci
standardowej
:
max(min)z = c
1
x
1
+ c
2
x
2
+···+ c
n
x
n
a
11
x
1
+ a
12
x
2
+···+ a
1n
x
n
= b
1
. . .
a
m1
x
1
+ a
m2
x
2
+···+ a
mn
x
n
= b
m
x
i
0, i = 1, . . . , n
Zbiór ograniczeń można zapisać w postaci macierzowej Ax = b, x
0.
Zakładamy, że rz¸ad macierzy A jest równy m, czyli żadne równanie
nie wynika z innych równań.
1
Każdy model liniowy można sprowadzić do równoważnej postaci
standardowej w następujący sposób:
1. Ograniczenie postaci a
i1
x
1
+ a
i2
x
2
+···+ a
in
x
n
b
i
zast¸epujemy dwoma ograniczeniami:
a
i1
x
1
+ a
i2
x
2
+···+ a
in
x
n
+ s
i
= b
i
, s
i
0.
2. Ograniczenie postaci a
i1
x
1
+ a
i2
x
2
+···+ a
in
x
n
b
i
zast¸epujemy dwoma ograniczeniami:
a
i1
x
1
+ a
i2
x
2
+···+ a
in
x
n
−s
i
= b
i
, s
i
0.
3. Jeżeli zmienna x
i
może przyjmować wartości ujemne to
wykonujemy podstawienie: x
i
= u
i
−v
i
i dodajemy ograniczenia
u
i
0, v
i
0.
2
Przykład 1.
Sprowadzić do postaci standardowej problem:
max z = 2x
1
+ 3x
2
−
x
3
x
1
−
2x
2
5
x
2
+ 3x
3
3
x
1
+ x
2
−
2x
3
= 20
x
1
, x
2
0
Przekształcamy ograniczenia 1 i 2 oraz wykonujemy podstawienie
x
3
= u
3
−
v
3
co daje postać standardową:
max z = 2x
1
+ 3x
2
−
u
3
+ v
3
x
1
−
2x
2
+ s
1
= 5
x
2
+ 3u
3
+ 3v
3
−
s
2
= 3
x
1
+ x
2
−
2u
3
+ 2v
3
= 20
x
1
, x
2
, s
1
, s
2
, u
3
, v
3
0
3
Definicja 1.
Rozpatrzmy układ ograniczeń
Ax = b
. Wybierzmy
dokładnie
m
zmiennych i nadajmy pozostałym
n−m
zmiennym
wartości zerowe. Otrzymujemy w ten sposób układ
m
równań o
m
niewiadomych. Jednoznaczne rozwiazanie tego układu nazywamy
rozwiazaniem bazowym
. Wybrane zmienne nazywamy
zmiennymi bazowymi
i oznaczamy przez
ZB
natomiast pozostałe
zmienne (tj. te, którym przypisano wartości 0) nazywamy
zmiennymi niebazowymi
i oznaczamy przez
N B
.
Uwaga:
Wybrane zmienne s¸a bazowe wtedy i tylko wtedy, gdy
odpowiadaj¸ace im kolumny w macierzy A s¸a liniowo niezależne. Zbiór
tych kolumn nazywamy
baza
i oznaczamy przez B. Przez B będziemy
również oznaczać macierz utworzoną z tych kolumn.
4
Przykład 2.
Wyznaczyć kilka rozwiazań bazowych układu
ograniczeń:
x
1
+ x
2
+ 2x
4
= 3
2x
1
−x
2
−x
3
+ 4x
4
= 1
Układ ma 4 zmienne i 2 ograniczenia. Wybieramy zmienne bazowe
ZB ={x
1
, x
2
}
. Podstawiamy
x
3
= x
4
= 0
(
N B ={x
3
, x
4
}
).
Otrzymujemy układ:
x
1
+ x
2
= 3
2x
1
−x
2
= 1
Rozwiazujac układ otrzymujemy rozwiazanie bazowe:
x
1
=
3
,
x
2
= 1
3
,
x
3
= 0
,
x
4
= 0
. Bazą są wektory współczynników macierzy
A
układu równań przy zmiennych bazowych
x
1
, x
2
tj.
2
3
B =
4
1
1
5
2−1.
5
.
Plik z chomika:
Asfoora
Inne pliki z tego folderu:
lista 7.pdf
(28 KB)
lista 6.pdf
(38 KB)
lista 5.pdf
(32 KB)
lecture 6.pdf
(249 KB)
lecture 5.pdf
(195 KB)
Inne foldery tego chomika:
Komunikacja marketingowa
Koncepcje zarządzania
Kontroling
Logistyka
Makroekonomia
Zgłoś jeśli
naruszono regulamin